Лабораторная работа №8. Метод Гомори для решения задач целочисленного линейного программирования

< c, x> ® m,

A x = b, (4. 2)

x ³ 0

x_i Î целые, iÎ {1, 2, 3,..., n}=[1..n].

Метод Гомори предполагает следующую последовательность действий для решения задачи (4.2).

Шаг 1. Отбросим условие целочисленности

< c, x> ® m,

A x = b, (4. 3)

x_i ³ 0, iÎ {1, 2, 3,..., n}=[1..n],

получим задачу линейного программирования (4.3).

Шаг 2. Решим задачу (4.3) одним из алгоритмов симплекс-метода. Если полученное оптимальное оптимальное решение X целочисленное (т.е. x_i целые для всех iÎ [1..n]), то алгоритм прекращает работу, иначе переходим к шагу 3.

Шаг 3. Если задача решалась симплекс-методом, значение базисных переменных x_i записано в столбце b симплекс-таблицы, внебазисные переменные равны нулю. Среди элементов столбца b ищем нецелочисленные. Если таких несколько, то обычно берется такое i₀, что i₀= argmax{b(i)| iÎ [1..m]}, составляется дополнительное ограничение (отсечение Гомори):

å {- frac (a(i₀ , j)) ´ x(i)| jÎ [,..n] £ - frac (b(i₀)), (4.4)

где frac(a) - дробные части числа a.

Приводим это ограничение к каноническому виду, приписываем к последней cтроке симплекс - таблицы и решаем двойственным симплекс-методом. Получив оптимальное решение, переходим к выполнению шага 2.

 

Пример.

 

x₁ + x₂ ® max,

2 x₁ + x₂ £ 2,

x₁ +2 x₂ £ 2,

x_i ³ 0, x_i - целые, i=1, 2.

 

Занесем данные в симплекс-таблицу:

Xb	b	X1	X2	Y1	Y2
Y1	2	2	1	1	0
Y2	2	1	2	0	1
d	0	-1	-1	0	0

Решив эту задачу без условия целочисленности, получим симплекс-таблицу.

Xb	b	X1	X2	Y1	Y2
X1	0.67	1	0	0.67	-0.33
X2	0.67	0	1	- 0.33	0.67
d	1.33	0	0	0.33	0.33

 

Из этой таблицы получаем X₁=0.67, X₂=0.67, т.е. решение не целочисленное, строим дополнительное ограничение по первой строке (можно и по второй): -0.67Y₁ - 0.67Y₂ £ -0.67.

Приводим его к каноническому виду -0.67Y₁ - 0.67Y₂ + Y₃ = -0.67

и приписываем к симплекс-таблице:

 

Xb	b	X1	X2	Y1	Y2	Y3
X1	0.67	1.0	0	0.67	- 0.33	0
X2	0.67	0	1	-0.33	-0.67	0
Y3	-0.67	0	0	-0.67	-0.67	1
d	1.33	0	0	0.33	-0.33	0

 

Решаем двойственным симплекс-методом:

 

Xb	b	X1	X2	Y1	Y2	Y3
X1	0	1.0	0	0	-1	1
X2	1	0	1	0	1	0
Y1	1	0	0	1	1	1
d	1.33	0	0	0	0	0.5

 

Получим целочисленное решение X₁= 0, X₂=1, Y₁=1, Y₂=0, Y₃=0, Y₁, Y₂, Y₃ - дополнительные переменные. Ответ: X₁= 0, X₂=1.

Задание 8

 

Решить задачу из лабораторной работы N13 " Лабораторного практикума по методам оптимизации", добавить к условиям задачи условия целочисленности. Исходной таблицей для метода Гомори взять последнюю симплекс-таблицу лабораторных работ 14-15. Если в ней получено целочисленное решение, то задание скорректировать у преподавателя.

 

Метод ветвей и границ (алгоритм Ленд и Дойга) для решения задач целочисленного линейного программирования.

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

< c, x> ® max,

A x = b, (4. 5.)

x ³ 0,

x_i - целые, i Î [1..n].

Для ее решения применим метод ветвей и границ.