МЕТОД ГОМОРИ-3

Постановка целочисленной задачи линейного программирования (ЦЗЛП).

Найти вектор x=(x1...,xn), что минимизирует целевую функцию

L(x)= c1x1 + ... + cnxn (11.1)

и удовлетворяет систему ограничений

a11x1 + . . . + a1n xn = a10

. . . . . . . . . . . . . . . . . . . . . . . (11.2)

am1x1 + . . . + amnxn = am0

xj³0, j=1...,n (11.3)

xj — цели, j=1...,n. (11.4)

Изложение метода Гомори-3.

Метод Гомори-3 заключается в следующем.

Пусть ограничение (11.2) ЗЛП (11.1)–(11.3) приведены к почти каноничному виду:

xi +aі,m+1xm+1 +...+ainxn =ai0, i=1...,m (11.5)

где aij, i=1...,m, j=0,m+1...,n — цели и симплекс - разницы Dj³0, j=1...,n.

Если ai0³0, i=1...,m, то ограничения (11.5) определяют оптимальное решение ЦЗЛП (11.1)–(11.4), иначе определяется некоторое целочисленное почти допустимое базисное решение (МДБР) исходной ЗЛП. Можно бы было, конечно, выбрать один из индексов и, для которого ai0<0, и выполнить итерацию двойственного симплекс-метода. Однако в этом случае целочисленность новых параметров была бы, вообще говоря, нарушенная через необходимость деления на ведущий элемент превращения. Этого можно избежать лишь тогда, когда ведущий элемент равняется –1. Оказывается, что можно построить дополнительное ограничение, которому удовлетворяют все целочисленные развязки ЦЗЛП и которое вместе с тем определяет ведущий строка превращения, что имеет ведущий элемент –1. Строится оно за l-м ограничением системы (11.5), для которого ai0минимальное среди отрицательных ai0, и имеет вид:

xn+1 +am+1,m+1xm+1 +...+am+1,nxn =am+1,0

где xn+1 ³ 0 — дополнительная переменная

am+1,j= [alj/a], j=0,m+1...,n

a = max { –alj}, j=m+1...,n.

Следовательно, имеющаяся симплекс-таблица расширяется за счет (m+1) -ой строки с элементами am+1,j(am+1,j=0при j=1...,m) но единичного столбца An+1, что отвечает дополнительной переменной xn+1. Потом выполняется итерация двойственного симплекс-метода с (m+1) -м ведущим рядком.


Алгоритм метода Гомори-3.

1. Приводим исходную ЗЛП (11.1)–(11.3) к почти каноничной ЗЛП (МКЗЛП) с целочисленными коэффициентами, что определяет целочисленный МДБР x(0), для которого Dj³0, j=1...,n.

2. Пусть на s-й итерации полученная полностью целочисленная МКЗЛП

xi +aі,M+1xM+1 +...+aiNxN =ai0, i=1...,M

что определяет целочисленный N-мерный МДБР

x(s)= (a10..aM0,0..,0).

3. Если ai0³0, i=1...,M, то конец: x(s) — оптимальное решение ЦЗЛП. Иначе

4. Если для некоторого и такого, что ai0<0aij³0, j=1...,N, то конец: исходная ЦЗЛП не имеет допустимых решений. Если таких и нет, то

5. Находим l=argmin{ai0},где и: ai0<0. Определяем a=max{–alj}, j=M+1...,N, и строим дополнительное ограничение

xN+1 +aM+1,M+1xM+1 +...+aM+1,NxN =aM+1,0

где xN+1³0 — дополнительная переменная aM+1,j— целая часть отношения alj/a, j=0,M+1...,N.

6.Расширяем симплекс-таблицу за счет (M+1) -ой строки (дополнительное ограничение) и (N+1) -го столбца, что отвечает дополнительной переменной xN+1.