ТРАНСПОРТНАЯ ЗАДАЧА

Рис. 4.2. Метод отсечения Гомори

Формирование правильного отсечения. После каждой итерации симплекс-метода система ограничений ЗЛП имеет вид

, (4.1)

где {БП} – множество базисных переменных.

Если выполняется условие оптимальности задачи, то все Находим оптимальное решение. Если все компоненты оптимального плана целочисленны, то задача решена. Предположим, что некоторые β₀ – нецелые. Пусть компонента i₀ – нецелая. Рассмотрим i₀-е равенство системы (4.1), для которой выполняется условие оптимальности, т. е.

. (4.2)

Перейдем к дальнейшему изучению уравнения (4.2). Найдем целую и дробную части его коэффициентов и . Т.к. по определению дробной части числа , получим:

. (4.3)

Так как первое слагаемое равенства (4.3) есть целое число, то, для того чтобы было целым, необходимо, чтобы второе слагаемое также было целым, т. е. величина

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

В самом деле, величинане может быть отрицательной. Из определения дробной части числа следует, что . Так как
– целое, то из предположения, что > 0, должно следовать , что противоречит определению дробной части числа.

Итак, доказано, что любое допустимое решение целочисленной задачи должно удовлетворять неравенству

. (4.4)

Теорема 4.1. Неравенство (4.4) определяет правильное отсечение Гомори, т. е.: 1) является линейным; 2) отсекает найденное оптимальное нецелочисленное решение ЗЛП; 3) не отсекает ни одного целочисленного плана ЗЛП.

Доказательство.

1. Линейность соотношения (4.4) очевидна.

2. Пусть х*_нц – оптимальный нецелочисленный план ЗЛП, причем, например, координата есть число нецелое. Покажем, что это решение не удовлетворяет условию (4.4). Поскольку х*_нц оптимален,то. Поэтому

. (4.5)

Учитывая равенство (4.5), из условия (4.4) имеем , что противоречит определению дробной части числа. Итак, оптимальное решение х*_нц ЗЛП не удовлетворяет условию (4.4).

3. Требование 3 по существу доказано при формировании условия (4.4). В самом деле, предположим, что существует целая точка х*_ц ЗЛП, которая не удовлетворяет условию (4.4), т. е.

. (4.6)

Так как и , то, учитывая неравенство (4.6), получаем

а это противоречит тому, что для всех планов целочисленной задачи есть число целое.

Таким образом, соотношение (4.4) определяет правильное отсечение Гомори.

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

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

Опишем алгоритм метода Гомори, использующий симплекс-метод.

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

2. Среди нецелых элементов выбирается произвольный элемент (например, с максимальной дробной частью). По r-й строке симплекс-таблицы составляется дополнительное ограничение вида

(для определенности мы полагаем, что свободные переменные имеют номера т+1, …, п ). С помощью вспомогательной переменной это ограничение представляется в виде равенства

и вводится в симплекс-таблицу дополнительной строкой.

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

3. Для перехода к допустимому базисному решению производятся следующие операции:

а) строка с отрицательным свободным членом считается разрешающей;

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

где минимум берется по всем отрицательным ;

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

4. Если найденное в разделе 3 решение задачи линейного программирования удовлетворяет условию целочисленности,товычисления завершаются, а если нет, то продолжаются переходом к разделу 2 описания алгоритма.

Описанный алгоритм позволяет найти решениеполностью целочисленной задачи линейного программированияили установить отсутствие решений за конечное число итераций.

Пример 4.1. В качестве примера решим следующую задачу целочисленного программирования методом Гомори:

Введя дополнительные переменные, запишем эту задачу в каноническом виде:

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

Одна из угловых точек допустимогомножества нецелочисленной задачи очевидна: (0, 0, 40, 29). Запишем симплекс-таблицу для этой угловой точки:

	х₁	х₂
х₃	-1	10
х₄
		-20

Решение нецелочисленной задачи находится за две итерации симплекс-метода:

	х₁	х₃		х₄	х₂
х₂	-1/10	1/10	х₃	1/42	4/42	9/2
х₄	42/10	-2/10	х₁	10/42	-2/42
	-1			10/42	82/42

Это решение не удовлетворяет условию целочисленности, поэтому дополняем последнюю симплекс-таблицу новой строкой. Для перехода к допустимому базисному решению находим разрешающий элемент по описанному правилу и преобразуем симплекс-таблицу.

	х₄	х₂			х₅	х₂
х₃	1/42	4/42	9/2	х₃
х₁	10/42	-2/42		х₁		-1
x₅	-1/42	-4/42	-1/2	х₄	-42
	10/42	82/42

Последняя симплекс-таблицане только соответствует допустимому базисному решению, но и дает решение рассматриваемой задачи:
х*=(0, 4), f*=-80.