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

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

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

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

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

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

. . . . . . . . . . . . . . . . . . . . . . . (9.2)

a_m1x1 + . . . + a_mnx_n = a_m0

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

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

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

Метод Гомори-1 является одним из методов отсечения, идея которых заключается в следующем.

Решается вспомогательная ЗЛП (9.1)–(9.3), которую получают из исходной ЦЗЛП (9.1)–(9.4) отбрасыванием условия целочисленности переменных (9.4). Если оптимальное решение вспомогательной ЗЛП — целочисленный, то он будет и решением исходной ЦЗЛП. Если же полученное решение вспомогательной задачи не является целочисленным, то от развязанной ЗЛП переходят к новой вспомогательной ЗЛП присоединением линейного ограничения, которое удовлетворяют целочисленные развязки исходной ЦЗЛП и которое не удовлетворяет полученное нецелочисленное решение вспомогательной ЗЛП. Упомянутое дополнительное линейное ограничение определяет некоторую отрезающую плоскость и называется правильным відтином (ограничением). Присоединение новых правильных ограничений рассмотрена к начальной вспомогательной ЗЛП осуществляется до тех пор, пока на некотором шаге не будет получено целочисленное решение вспомогательной задачи, которое, очевидно, будет оптимальным решением исходной ЦЗЛП. В методе Гоморi-1правильный ограничение строится таким образом.

Пусть на последней итерации симплекс-метода при решении вспомогательной ЗЛП непрямые ограничения этой задачи приобрели вид:

xi + а_і,m+1 xm+1+...+ а_in xn = а_i0, i=1...,m

и, таким образом, решением вспомогательной ЗЛП будет вектор

x = (а₁₀..., а_m0,0...,0 ).

Пусть существует номер r такой, что а_r0 — дробь, и, как всегда {z} — дробная часть z. Тогда правильный відтин методу Гомори-1задается неравенством:

{ а_r,m+1} xm+1+...+ { а_rn} xn  { а_r0} .

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

1. Решаем вспомогательную ЗЛП (9.1)–(9.3). Пусть x(0) — ее оптимальное решение. Если оптимальное решение не существует, то исходная ЦЗЛП также не имеет оптимального решения.

2. Пусть на s-й итерации развязана вспомогательная ЗЛП, что имеет M ограничений и N переменных, x(s) — ее оптимальное решение.

Будем считать, что x(s) определяется каноничными ограничениями последней итерации, то есть:

x_i + b_i,M+1 x_M+1 +...+ b_iN x_N = b_i0, i=1...,M

Откуда

x(s)= ( b₁₀...,b_M0,0,...,0 ).

3. Если b_i0 (i=1...,M) — цели, то — конец, x(s) является оптимальным решением исходной ЦЗЛП. Если существует хотя бы одно и такое, что _bi0 — дробь, то переход к пункту 4.

4. Находим r=min{i}по всем и таким, что b_i0 — дробь и строим дополнительное ограничение

x_N+1 – {_br,M+1} x_M+1 –...– {b_rN} x_N = – {b_r0}

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

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

6. Решаем расширенную таким образом ЗЛП двойственным симплекс-методом и переходим к пункту 2 с заменой s на s+1. Если при этом на какой-либо итерации двойственного симплекс-метода одна из дополнительных переменных задачи повторно становится базисной, то исключаются из последующего рассмотрения соответствующие ей строка и столбец.

Программное обеспечение.

Обучающий модуль, с помощью которого полностью целочисленная задача линейного программирования Решается в диалоге с пользователем за выложенным алгоритмом, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПЗ–МО.

Задание.

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

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

1)	5 x1 + 6 x2 + 6 x3  min	2)	6 x1 + 4 x2  min
	2 x1 + 4 x2  10		2 x1 + x2  3
	3 x1 + 2 x2 + 2 x3  10;		x1 – x2  1;

3)	6 x1 + 4 x2  min	4)	x1 + x2  min
	2 x1 + x2  3		– x1 – x2 + x5 = –1
	x1 – 2 x2  2		–2 x1 + 2 x2 + x3 = –2
	3 x1 + 2 x2  1;		–4 x1 + 2 x2 + x4 = –1;

5)	6 x1 + 4 x2  min	6)	2 x1 + 3 x2  min
	2 x1 + x2  3		x1 + 2 x2  16
	x1 – x2  1;		2 x1 + x2  16;

7)	5 x1 – 3 x2  max	8)	5 x2 + 7 x4  min
	3 x1 + 2 x2  6		– 10 x2 + x3 + x4 = –16
	2 x1 – 3 x2  – 6		x1 – 3 x2 – 3 x4 = –12
	x1 – x2  4		– 6 x2 – 2 x4 + x5 = –17;

9)	– 5 x4 – 7 x5  max	10)	8 x1 + 2 x2  max
	x1 – x4 – 2 x5 = – 7		x1 – 4 x2 + x3 = 4
	– x3 + 3 x4 – 6 x5 = – 3		– 4 x1 + x2 + x4 = 4
	x2 – x4 – 4 x5 = –11;		x1 + x2 + x5 = 6.

Ответы:

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

2) x* = (1; 1), L(x*)= 10.

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

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

5) x* = (2; 0), L(x*)= 12.

6) x* = (6; 5), L(x*)= 27.

7) x* = (18; 14), L(x*)= 48.

8) x* = (0; 4; 24; 0; 7), L(x*)= 20.

9) x* = (0; 0; 0; 3; 2), L(x*)= 29.

10) x* = (5; 1; 0; 0; 0), L(x*)= 42.

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