| Home / lib / M_Mathematics / MOc_Optimization and control / | ||
Kofman A., Anri-Laborder A. (_Kaufmann A., Henry-Labordere A._) Metody i modeli issledovanija operacij. Celochislennoe programmirovanie (Mir, 1977)(ru)(600dpi)(T)(432s)_MOc_.djvu |
|
Size 9.4Mb Date Feb 25, 2005 |
следующем виде:
U^)eG#(^/^)eG A1.4)
]) В дальнейшем мы опускаем слова «определяемое графом G cz E X
Алгоритмы и эвристические методы
185
или в виде
(х, у) е G ФФ (у, х) е G, A1.5)
так как импликация относится как к паре (у,х), так и к паре
{х%у)...
Следовательно, пара (х, х)
не принадлежит этому графу...
A1.11)
Из A1.11) видно, что все элементы располагаются в после-
последовательности, которая характеризует совершенный порядок...
Рассмотрим в качестве примера граф, изображенный на
фиг...
Можно проверить, что структура обладает следующими
свойствами2)...
Алгоритмы и эвристические методы
199
и A1.39) удовлетворяются для любых троек элементов, напри-
например:
В A (D V Е) = В A F = В,
(В A D) V (В А Е) = В V В = В...
на 4-,
^ на ^, 0 на 1 и 1 на 0 можно поставить в соответствие дру-
другое истинное соотношение, являющееся двойственным исход-
исходному...
Пусть даны две булевы матрицы [Л]тХг и [В]гХп- Булевым
произведением этих матриц назовем матрицу [С]тхп, элементы
которой определяются следующим образом:
СИ = «п • Ьц 4- ai2...
A2.38)
Читателю предлагается проверить, для каких из приведен-
приведенных выше операций верны аналогичные соотношения...
Алгоритмы и эвристические методы 213
о
где ? обозначает, что выполняется суммирование в соответ-
соответствии с формулой A2.17)...
Из выражения
A2.43) следует, что k ^ п — 1 и
[A]r < [A]k при г < k,
]A]r=[A]k при г>?...
Метод дерева (метод ветвлений)
Если число переменных больше 4, то процесс составления
таблиц оказывается трудоемким...
Часто оказывается, что для построения реше-
решений можно ограничиться неполным деревом...
Метод ветвлений может быть использован и для решения
неравенств; для этого их достаточно привести к уравнениям, ис-
используя свойства A3.29), A3.30), A3.43) или A3.44)...
Рассмо-
Рассмотрим на примере порядок выполнения операций...
Из чисто методических соображений мы были, на-
например, вынуждены видоизменить описание метода Гомори
в области асимптотического программирования; для изложения
этого метода необходимо использование основных понятий со-
современной алгебры, которые в настоящее время бесспорно яв-
являются классическими, но многими читателями «старшего» по-
поколения нередко активно не используются (например, понятия
изоморфизма и гомоморфизма, понятие группы и т...
| © 2007 eKnigu | ||