ГЛАВА 7. ТРЕТИЙ АЛГОРИТМ ГОМОРИ И ЕГО МОДИФИКАЦИЯ

В этой главе излагается третий алгоритм Гомори [85а], [86], в литературе часто называемый полностью целочисленным, и при некоторых условиях доказывается его конечность. Приведен пример, когда эти условия нарушены и конечность алгоритма Гомори не имеет места. Предложена модификация алгоритма, обеспечивающая конечность при менее ограничительных условиях (пример и модификация алгоритма предложены Финкельштейном [32]).

§ 1 О влиянии ошибок округления. Идея третьего алгоритма Гомори

1.1. Известно (см., например, Джекобе [101]), что влияние ошибок округления может привести к получению ошибочного решения при применении симплекс-метода (прямого или двойственного) в обычной задаче линейного программирования. При решении же с помощью изложенных выше алгоритмов целочисленной задачи линейного программирования влияние ошибок округления существенно усиливается по следующим причинам: 1) Увеличение объема вычислений из-за многократного применения -метода. 2) Возможность грубых сшибок

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

От вредного влияния ошибок округления свободен третий алгоритм, предложенный Гомори [86] для решения полностью целочисленной задачи линейного программирования:

Максимизировать

при условиях

1.2. Опишем идею третьего алгоритма Гомори. Пусть условия задачи линейного программирования записаны в виде -нормальной таблицы Проводя последовательно итерации -метода, получим конечную последовательность -нормальных таблиц

последняя из которых является допустимой.

Допустим, что исходная таблица являлась полностью целочисленной (т. е. все ее элементы были целыми числами). Почему последующие таблицы могут быть нецелочисленными? Это возможно потому, что, кроме операций сложения (вычитания) и умножения, при переходе от таблицы к таблице имеется еще операция деления на направляющий элемент. Если бы

направляющий элемент на всех итерациях был равен то целочисленность таблицы То повлекла бы за собой и целочисленность всех остальных таблиц, оптимальный план задачи (соответствующий таблице ) оказался бы одновременно и оптимальным планом задачи

Разумеется, нельзя в общем случае гарантировать, что на каждой итерации -метода направляющий элемент будет равен Можно, однако (основываясь на опыте первого алгоритма) попытаться так модифицировать определение правильного отсечения, что если соответствующую ему (отсечению) строку принять за направляющую, то направляющий элемент (при выборе столбца по правилам -метода) окажется равным

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

соответствующий таблице не является расширенным планом. Надо построить линейную функцию

удовлетворяющую следующим условиям:

I. Условие целочисленности.

II. Условие отсечения.

III. Условие правильности. Для любого плана X задачи выполняется неравенство

IV. Условие сохранения цело численности. Если среди чисел есть отрицательные,

то

Условие означает, что если строка выбирается в качестве направляющей, то направляющий элемент равен

Замечание 1.1. Из условий (1.9) — (1.10) следует, что направляющий столбец однозначно определяется набором отрицательных элементов направляющей строки

1.3. Если удастся построить целочисленное правильное отсечение, соответствующее условиям (1.5) — то логическая схема алгоритма будет выглядеть следующим образом.

Начиная с исходной недопустимой таблицы строим последовательность таблиц

каждая из которых является целочисленной и -нормальной. Если таблица окажется допустимой, то соответствующий ей -псевдоплан окажется одновременно и оптимальным планом задачи Если же таблица окажется недопустимой, то строим целочисленное правильное отсечение, удовлетворяющее условиям (1.5) — (1.10). Приписываем соответствующую строку к таблице снизу, принимаем ее за направляющую и проделываем одну итерацию -метода. Получаем новую таблицу (целочисленную и -нормальную).