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

если они выполнены, то конец, текущее базисцое решение опти­

и дописать ее внизу таблицы, т. е. добавить к ограничениям задачи уравнение (2), где X = avs.

Ш а г 4. Провести преобразование таблицы, используя отсече­ ние (2) как ведущую строку. Слабая переменная sh в (2) станет

небазисной. Вернуться к шагу 1.

Графически условия задачи и четыре отсечения, последовательно получающиеся в ходе решения, показаны на рис. 17.1. После введения слабых переменных (х3, а:4) задача записана в табл. 17.1. Выберем столбец под переменной xt в качестве ведущего. Строка с обозначением xt является ведущей строкой в симплекс-алгоритме

и поэтому выбирается как производящая. Запишем отсечение, полученное из этой строки, в последней строке таблицы. Новая переменная st является слабой переменной в отсечении. Отсечение

образование таблицы использует столбец под xt и строку s± в каче­

стве ведущих. В результате получается табл. 17.2. Н а рис. 17.1 это отсечение обозначено через

Выберем для введения в базис переменную х2. Строка х3 является ведущей строкой симплекс-алгоритма и, следовательно, производящей строкой. Отсечение записано в нижней строке таб­ лицы. Результат выполнения преобразования показан в табл. 17.3. Н а рис. 17.1 это отсечение обозначено через с2.

строкой является строка х 3. Получим отсечение и проведем пре­

образование. Результат записан в табл. 17.4. Как обычно, после того как преобразование таблицы произведено., ведущая строка

*2+

4 -

3

Р и с . 17.1.

вычеркивается из таблицы. Н а рис. 17.1 соответствующее отсе­ чение обозначено через с3.

После преобразования с ведущим элементом, указанным в табл. 17.4, получим оптимальную табл. 17.5. Соответствующее

■с тем, что отсечение (2) может иметь нулевое значение в столбце констант, т. е.

Так случилось на второй и третьей итерации в описанном выше примере. Если в отсечении в столбце констант появляется нуль, то преобразование таблицы, в котором отсечение служит ведущей «трокой, не приводит к изменению столбца констант а0. Поэтому

преодолеть не более чем за конечное число преобразований. Средства, используемые для преодоления вырожденности в линей­ ном программировании, к сожалению, не годятся для случая целочисленных задач. В линейном программировании трудность вырожденности обходят в конечном счете путем обращения к ко­ нечности множества базисных решений, которая следует из того, что в задачах линейного программирования число переменных и ограничений фиксировано (и конечно). Методы отсекающей пло­ скости в целочисленном программировании систематически созда­ ют новые ограничения и переменные и тем самым делают невоз­ м о ж н ы м применение способов разрешения проблемы вырожден­ ности, используемых в линейном программировании.

Проблема конечности в прямых алгоритмах станет понятней, если ввести различие между стационарными циклами (вырожден­

ными преобразованиями, о которых говорилось выше, т. е. при av0/avs = 0) и переходными циклами (преобразованиями, которые

приводят к новому решению с положительным приращением

цикл приведет к увеличению значения целевой функции по край­ ней мере на единицу. Очевидно тогда, что достаточно конечного числа переходных циклов для получения оптимального решения совместной задачи с ограниченной целевой функцией. Основная проблема конечности сводится к доказательству того факта, что любая последовательность стационарных циклов конечна 1).

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

И в-третьих, строка, используемая в качестве производящей для получения отсечения Гомори не всегда является ведущей строкой симплекс-алгоритма; вместо того чтобы определять производящую строку по правилу проверки отношения, она будет выбираться из множества подходящих строк согласно другому правилу, которое входит в класс правил, гарантирующих конечность.

о прямом алгоритме и доказательстве его конечности, мы обычно не будем делать различия между стационарными и переходными циклами. (Впервые Гловер предложил алгоритм, в котором в явном виде не было этого разли­ чия, см. [76].) Однако можно привести изложение алгоритма и доказатель­ ство его конечности с учетом этого различия. (См. Бен-Израел и Чарнес [17] и Юнг [224], [225]). При вычислениях, возможно, стоит учитывать указан­ ное различие.