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

Задачей целочисленноголинейного программирования (ЗЦЛП) называют ЗЛП, в которой на переменные налагается дополнительное ограничение – условие целочисленности. ЗЦЛП имеет вид:

       (1)

(2)

             (3)

- целые числа;     (4)

где N₁ – некоторое подмножество множества индексов N ={1,2, …,n}.

Если N₁=N, то задачу (1) – (4) называют полностью целочисленной, если N₁¹N, - частично целочисленной.

Метод Гомориявляется одним из методов решения задач целочисленного линейного программирования. Идея метода Гомори решения задачи (1) – (4) заключается в следующем. Отбрасывается условие целочисленности (4), и полученная ЗЛП (1) – (3) решается симплекс-методом. Если оптимальное решение задачи (1) – (3) удовлетворяет ограничению (4), т.е. является целочисленным, то оно является и решением исходной задачи (1) – (4). Если оптимальное решение задачи (1) – (3) не удовлетворяет ограничению (4), то к основным ограничениям (2) добавляется новое линейное ограничение, обладающее следующими свойствами: 1) оптимальный нецелочисленный план задачи (1) – (3) ему не удовлетворяет; 2) любой целочисленный план задачи (1) – (3) ему удовлетворяет. Затем решается расширенная задача. Процесс повторяется до получения целочисленного решения. Способы построения дополнительного линейного ограничения различны для полностью и частично целочисленных ЗЛП. В силу свойств 1 и 2 дополнительное ограничение называют еще отсечением Гомори, а метод Гомори – методом отсечения.

Рассмотрим метод Гомори для решения полностью целочисленных ЗЛП. Пусть задача (1) – (3) решена симплекс-методом, х⁰ – ее оптимальный план, а табл. 7.1 - оптимальная симплексная таблица.

 Таблица 6.1

Если все значения х⁰_ip - целые, то х⁰ – решение задачи (1) – (4). Пусть среди чисел х⁰_ip  есть нецелочисленные. Выберем из них число с максимальной дробной частью:

Дополнительное линейное ограничение, или отсечение Гомори, будет иметь вид

                   (5)

В ограничение (5) вводим дополнительную переменную

      (6)

где x_n+1³0. Равенство (6) умножим на -1 и получим

(7)

Припишем ограничение (7) к симплексной таблице 1. При том переменная x_n+1 будет базисной. Получим расширенную таблицу 2.

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

Таблица 6.2

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

2. Для чисел с одинаковыми знаками составляют симплексные отношения.

3. Наименьшее симплексное отношение определяет разрешающую строку. На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент.

4. С найденным разрешающим элементом выполняют симплексные преобразования.

Пример. Предприятие производит две модели А и В сборных книжных полок. Их производство ограничено наличием сырья (высококачественных досок) и временем машинной обработки. Для каждого изделия модели А требуется 2 м² досок, а для изделия В – 5 м². Малое предприятие может получить от своих поставщиков до 1600 м² досок в неделю. Для изготовления каждого изделия модели А требуется 10 мин машинной обработки, а изделие модели В – 12 мин. Время машинной обработки в неделю 100 ч. Сколько изделий каждой модели следует выпускать малому предприятию в неделю для получения максимальной прибыли, если каждое изделие модели А приносит 20 ден. ед. прибыли, а каждое изделие модели В – 40 ден. ед.?

Решение Математическая модель задачи имеет вид

x₁, x₂ – целые.

Преобразуем задачу, умножив обе части второго неравенства на 30. Получим задачу

x₁, x₂ – целые.

По методу Гомори для определения оптимального плана задачи ,решим ЗЛП симплекс-методом. Приведем ее к каноническому виду:

В процессе решения задачи получаются следующие симплекс таблицы

Таблица 6.3

Таблица 6. 4

Таблица 6.5

БП	сБ	А0	х1	х2	х3	x4
			20	40	0	0
х2	40		0	1	5/13	-2/13
х1	20		1	0	-6/13	5/13
zj-cj			0	0	80/13	20/13

Табл.6.5 – оптимальная симплексная таблица,

x⁰=(x⁰₁;x⁰₂), где x⁰₁= , x⁰₂=  - оптимальный план задачи. Так как оптимальный план задачи нецелочисленный, он не является оптимальным планом ЗЦЛП. Следуя методу Гомори, находим

По первой строке табл.7.5 строим дополнительное линейное ограничение:

  (*)

Так как

ограничение (*) примет вид

Введем в ограничение дополнительную переменную

Домножим ограничение на -1:

Припишем ограничение к табл.7.5 и получим табл.7.6

Таблица 7.6

БП	сБ	А0	х1	х2	х3	x4	x5
			20	40	0	0	0
х2	40		0	1	5/13	-2/13	0
х1	20		1	0	-6/13	5/13	0
x5	0		0	0	-5/13	-11/13	1
zj-cj			0	0	80/13	20/13	0

Следуя методу Гомори, выполним симплексные преобразования табл.6.6 с разрешающим элементом -11/13. Получим табл.6.7.

Таблица 6.7

БП	сБ	А0	х1	х2	х3	x4	x5
			20	40	0	0	0
х2	40
х1	20
x4	0	1
zj-cj			0	0	60/11	0	20/11

Имеем оптимальный целочисленный план расширенной задачи. Тогда оптимальный план исходной задачи х⁰=(415;154).