Задача целочисленного линейного програмування. Метод гомори-3

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

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

L(x)= c₁x₁ + ... + c_nx_n (11.1)

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

a₁₁x₁ + . . . + a_1n x_n = a₁₀

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

a_m1x1 + . . . + a_mnx_n = a_m0

x_j0, j=1...,n (11.3)

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

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

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

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

x_i +_і,m+1 x_m+1 +...+_in x_n =_i0, i=1...,m (11.5)

где _ij, i=1...,m, j=0,m+1...,n — цели и симплекс - разницы _j0, j=1...,n.

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

x_n+1 +_m+1,m+1x_m+1+...+_m+1,nx_n =_m+1,0

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

_m+1,j = [_lj], j=0,m+1...,n

= max { –_lj }, j=m+1...,n.

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

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

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

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

x_i +_і,M+1 x_M+1 +...+_iN x_N =_i0, i=1...,M

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

x(s)= (₁₀.._M0,0..,0).

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

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

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

x_N+1 +_M+1,M+1x_M+1+...+_M+1,Nx_N =_M+1,0

где x_N+10 — дополнительная переменная _M+1,j — целая часть отношения _lj, j=0,M+1...,N.

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

Задание.

Решить методом Гомори-3 задачи целочисленного линейного программирования, условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1–№9), а также следующие задачи.

Во всех задачах, которые предлагаются ниже, все переменные неотъемлемые и целые.

1)	– x1 – 5 x2  max	2)	3 x1 + 2 x2  min	3)	x1 + 3x2  min
	12 x1 – 3 x2  8		– 3 x2  2		x1 + 6x2  5
	– 3 x1 + 9 x2  8		– 2 x1 + 2 x2  2		– 5x1 + 19x2  13
	– x1 + 3 x2  3;		2 x1 – x2  1;		– 3x1 + 6x2  2;

4)	7x1 + 12x2  min	5)	–3x1 – 8x2  max	6)	10x1 + 7x2  min
	4x1 – 23x2  –14		–2x1 + 10x2  4		2x1 – 12x2  –9
	–12x1 + 2x2  –9		–3x1 – 5x2  –10		x1 + 4x2  10
	–13x1 – x2  –10;		2x1 – x2  2;		4x1 – 2x2  14;

7)	– 3 x4 – 2 x5  max	8)	3 x2 + x5  min
	x1 – 5 x4 + x5 = –15		– 2 x2 + x3 – 18 x5 = –20
	x3 + x4 – 8 x5 = – 9		x1 + x2 – 15 x5 = – 7
	x2 – x4 – 10 x5 = –19;		– 5 x2 + x4 + x5 = – 9.

Ответы:

1) x* = (2; 2), L(x*)= –12.

2) x* = (1; 0), L(x*)= 3.

3) x* = (0; 1), L(x*)= 3.

4) x* = (1; 1), L(x*)= 19.

5) x* = (2; 1), L(x*)= –14.

6) x* = (5; 2), L(x*)= 64.

7) x* = (3; 5; 3; 4; 2), L(x*)= –16.

8) x* = (6; 2; 2; 0; 1), L(x*)= 7.

Лабораторная работа 12.