Первый алгоритм Гомори для решения полностью целочисленной задачи линейного программирования

Все алгоритмы Гомори представляют собой реализацию метода отсечений. Каждый дает свое правило построения отсечений.

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

Определение. Неравенство или (*)

называется правильным отсечением, если оно удовлетворяет следующим условиям:

I. Условие отсечения. не удовлетворяет неравенству (*), т.е.

.

II. Условие правильности. Если – план задачи , то удовлетворяет неравенству (*), т.е.

Первый алгоритм Гомори предназначен для решения полностью целочисленных задач линейного программирования

(1)

, , (2)

, , (3)

‑ целые, . (4)

Пусть – оптимальный опорный план задачи (1)‑(3). Выразим целевую функцию и все переменные (j Î N), соответствующие оптимальному опорному плану .

, . (5)

Пусть x – вещественное число. Целой частью x называется наибольшее целое число, не превышающее x. Целая часть x обозначается [ x ]. Дробной частью x называется число

{ x } = x – [ x ].

Пример:

, , .

Теорема. Пусть

1) , ; (6)

2) – план задачи (1‑4).

Тогда

– целое (7)

³ 0. (8)

Замечание. Если все целые числа, то условия теоремы распространяются на случай .

Следствие. Пусть не удовлетворяет условию целочисленности (4), так что для некоторого ()

– нецелое. (**)

Тогда соотношения (6), (8) задают правильное отсечение.

,

³ 0.

Если гарантируется целочисленность целевой функции , то .

 

Схема метода отсечений выглядит следующим образом. Имеется задача (1‑4) .

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

Если этот план не является решением , то строится правильное отсечение, отбрасывающее этот план и решается задача , на втором этапе и т.д. … . Оптимальный план вспомогательной задачи линейного программирования определяются неоднозначно, т.к. может иметь много решений. Поэтому Гомори предложил вместо задачи решать l ‑задачу . l ‑оптимальный план определяется единственным образом.

Вычисления в методе Гомори проводятся в соответствии с l ‑методом.

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

(n + 2)´(k + 1)

где n — количество переменных в , а k – число небазисных переменных в ней.

Этот приём основан на том, что дополнительные ограничения (правильные отсечения)

интересует нас не сами по себе, а только как способ отсечения нецелочисленного оптимума и перехода от задачи к задаче .

Дополнительная переменная (r ³ 0), связанная с правильным отсечением, выводится из базиса сразу же после введения ограничения

³ 0,

.

Идея Гомори заключается в следующем:

а) Сразу же после вывода ³ 0 из базиса (r ³ 0) соответствующая строка вычёркивается из расширенной симплексной таблицы.

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

Таким образом число столбцов в таблице не превышает k +1 (равно), а число строк – n +2, где n +1 строка соответствует и одна в момент её включения.

Необходимо отметить, что алгоритм Гомори неприменим в следующих случаях:

Если задача имеет решение, но не имеет решения l ‑задача , т.е. множество оптимальных планов не пусто, то и не ограничено.

Блок‑схема алгоритма

 

Начальная итерация.

Решаем l ‑задачу . Если она неразрешима, то неразрешима и задача . Если разрешима и l ‑оптимальный план удовлетворяет условию целочисленности, то является оптимальным планом задачи . Если не удовлетворяет условию целочисленности, то переходим к общей итерации.

r -я общая итерация ( r ³0).

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

, .

Выберем наименьшую (по номеру) строку, которой соответствует нецелочисленная компонента

(если целочисленность целевой функции гарантирована, то ) и строится соответствующее правильное отсечение

(*)

³ 0

– целое.

Строка приписывается снизу к таблице . Получается недопустимая (только по строке !) и l ‑нормальная таблица, к которой применим l ‑метод. Причём после вывода из базиса соответствующая строка вычёркивается, а после введения в базис (l ³ n +1) соответствующая строка не восстанавливается. Если в итоге получаем симплексную таблицу, которой соответствует неразрешимая задача ЛП, то и задача неразрешима. Если же получим допустимую и l ‑нормальную таблицу , то проверяем соответствующий l ‑оптимальный опорный на целочисленность (). Если удовлетворяет условию целочисленности, то он является оптимальным решением , если нет, то переходим к (r +1)-й итерации.

 

Пример. Решить следующую задачу целочисленного линейного программирования, используя первый алгоритм Гомори:

при

,

4,

³ 0, .

Решение:

Правильные отсечения в этом алгоритме строятся по правилу:

.

0.

=		-1	-1
=		-1
=			-1
=
=
=			-5

=
=
=			-1
=		-2
=		-1
=	-23	-4	-9

2.

=
=	40/9	5/9	1/9
=	23/9	4/9	-1/9
=		-6
=		-1
=			-1
=	-4/9	-5/9	-1/9

 

Отсечение строилось по строке .

=	74/11	1/11	9/11
=
=	30/11	1/11	-2/11
=		-1
=	3/11	-1/11	-9/11
=	29/11	5/11	-51/11
=	-8/11	-1/11	-9/11

3.

=
=
=			-1
=	-3	-11
=		-1
=			-9

 

Отсечение строилось по строке .

5.

=
=
=			-1
=		-11
=		-1
=	-1		-9

6.

=
=	35/9	5/9	1/9
=	19/9	4/9	-1/9
=		-6
=		-1
=			-1
=	-8/9	-5/9	-1/9

 

Отсечение строилось по строке .

7.

=
=
=			-1
=	-1	-11
=		-1
=			-9

8.

=	65/11	1/11	9/11
=
=	32/11	1/11	-2/11
=		-1
=	12/11	-1/11
=	83/11	5/11	-54/11
=	-10/11	-1/11	-9/11

 

Отсечение строилось по строке .

 

9.

=
=
=			-1
=		-11
=		-1
=			-9

 

l -нормальная симплексная таблица с целочисленным планом.

Ответ: ; .