Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf

314 ГЛ. 15. СМЕШАННЫЙ АЛГОРИТМ

Если требуется, чтобы xs было целым и^ is ^ /го, то из (14) получим

Только что было доказано, что элемент ai0 производящей строки после одной итерации либо увеличивается до следующего целого, либо уменьшается до ближайшего, не превосходящего его целого значения. Чтобы доказать конечность, кроме обычного предположения о существовании нижней границы для оптималь­ ного значения z, необходимо сделать дополнительное предполо­ жение о том, что оптимальное значение z должно быть целочис­ ленным. В исходной таблице расположим в верхней части все т! ограничений, левые части которых подчинены требованию цело­

шается на каждой итерации и элемент ai0 производящей строки уменьшается или увеличивается до следующего целого, а00 не мо­ жет уменьшаться бесконечно и при этом оставаться больше пред­ полагаемой нижней границы. Поэтому а00 должно оставаться

постоянным для всех t > t0. Таким образом, через конечное число

шагов в качестве производящей строки будет выбираться первая, если а10 нецелое. Тогда а10 не может увеличиться до ближайшего целого для t 3> t0, поскольку это противоречило бы лексикографи­ ческому уменьшению столбца а* (я00 остается неизменным для t > t0). Следовательно, после определенного числа шагов а10

также должно стать фиксированным целым числом. Подобным

15.2. Метод разбиения в смешанном целочисленном программи­ ровании (Бендере [18])

Рассмотрим смешанную задачу целочисленного программи­

т. е. требуется, чтобы только компоненты вектора у были целыми. Для заданного значения у задача (1) примет следующий вид:

минимизировать

ctx х)

не зависит от у. Во-вторых, вне зависимости от величины у макси­ мум линейной формы и (Ь — А 2у) всегда достигается в одной

из вершин выпуклого многогранника, определяемого условием uAt ^ сь в предположении, что это множество ограниченное. Пусть up (р — 1, . . ., Р) — произвольная вершина этого выпук­

Если задача (3) не имеет допустимых решений, то по теореме двойственности задача (2 ) либо не имеет допустимых решений,,

либо целевая функция на множестве допустимых решений неограничена. Если у задачи (3) нет конечного оптимального решения,, то задача (2) не имеет допустимых решений. И в том и в другом случае задача (1 ) не имеет конечного оптимального решения.

‘Поэтому нас интересует лишь тот случай, когда задача (3) обла­ дает оптимальным решением. Следует заметить, что в этом случае выпуклое множество, определяемое условиями uAi ^ с4, и ^ О,

неограничена, однако оптимальная вершина, связанная с опти­ мальной величиной у, имеет конечные координаты. Такая ситуа­ ция показана на рис. 15.1, где кружком обозначена оптимальная вершина, а выпуклое множество неограничено.

В случае когда и принимает неограниченные значения для определенных значений (Ь — А 2у), можно добавить к ограниче­

ниям uAi ^ с4, и ^ 0 еще одно: 2 ui ^ М, где М — достаточно большая положительная константа. Такое ограничение показано на рис. 15.1 пунктирной линией.