4.2 Решение методом Гомори.

Одним из методов решения задач линейного целочисленного программирования является метод Гомори. Сущность метода заключается в построении ограничений, отсекающих нецелочисленные решения задачи линейного программирования, но не отсекающих ни одного целочисленного плана [5].

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

1. Решаем задачу симплексным методом без учета условия целочисленности. Если все компоненты оптимального плана целые, то он является оптимальным и для задачи целочисленного программирования. Если обнаруживается неразрешимость задачи, то и неразрешима задача целочисленного программирования.

2. Если среди компонент оптимального решения есть нецелые, то к ограничениям задачи добавляем новое ограничение, обладающее следующими свойствами:

- оно должно быть линейным;

- должно отсекать найденный оптимальный нецелочисленный план;

- не должно отсекать ни одного целочисленного плана.

Для удобного представление решения используется программа для работы с электронными таблицами MS Excel.

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

Определим минимальное значение целевой функции

при следующих условиях-ограничений:

Введем искусственные переменные x: в 1-м равенстве вводим переменную x₄; в 2-м равенстве вводим переменную x₅;

Для постановки задачи на минимум целевую функцию запишем так:

За использование искусственных переменных, вводимых в целевую функцию, накладывается так называемый штраф величиной М, очень большое положительное число, которое обычно не задается.

Полученный базис называется искусственным, а метод решения называется методом искусственного базиса.

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

Из уравнений выражаем искусственные переменные:

которые подставим в целевую функцию:

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.

Экономический смысл дополнительных переменных: дополнительные перемены задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана.

Решим систему уравнений относительно базисных переменных: x₄, x₅

Полагая, что свободные переменные равны 0, получим первый опорный план:

X₁ = (0,0,0,30,6)

Базисное решение называется допустимым, если оно неотрицательно.

Переходим к основному алгоритму симплекс-метода.

Проводим итерацию №0 для проверки критерия оптимальности.

Проверка критерия оптимальности.

Текущий опорный план не оптимален, так как в индексной строке находятся положительные коэффициенты.

Определение новой базисной переменной.

В качестве ведущего выберем столбец, соответствующий переменной x₃, так как это наибольший коэффициент.

Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i3

и из них выберем наименьшее:

min (30 : 6 , 6 : 1 ) = 5

Следовательно, 1-ая строка является ведущей.

Разрешающий элемент равен (6) и находится на пересечении ведущего столбца и ведущей строки (Таблица 6).

Таблица 6 – Симплекс-таблица с выделенным разрешающим элементом

Базис	B	x1	x2	x3	x4	x5
x4	30	5	4	6	1	0
x5	6	1	1	1	0	1
F(X1)	36M	-3+6M	-4+5M	-2+7M	0	0

Формируем следующую часть симплексной таблицы.

Вместо переменной x₄ в план 1 войдет переменная x₃.

Строка, соответствующая переменной x₃ в плане 1, получена в результате деления всех элементов строки x₄ плана 0 на разрешающий элемент 6

На месте разрешающего элемента в плане 1 получаем 1.

В остальных клетках столбца x₃ плана 1 записываем нули.

Таким образом, в новом плане 1 заполнены строка x₃ и столбец x₃.

Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.

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

Проводим пересчет симплекс-таблицу по разрешающему элементу (Таблица 7).

Таблица 7 – Симплекс-таблица после совершения итерации №0

Базис	B	x1	x2	x3	x4	x5
x3	5	^5/6	^2/3	1	^1/6	0
x5	1	^1/6	^1/3	0	^-1/6	1
F(X1)	10+M	-1^1/3+M	-2^2/3+M	0	^1/3-1^1/6M	0

Проводим итерацию №1 для проверки критерия оптимальности.

Текущий опорный план не оптимален, так как в индексной строке находятся положительные коэффициенты.

Определение новой базисной переменной.

В качестве ведущего выберем столбец, соответствующий переменной x₂, так как это наибольший коэффициент.

Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i2

и из них выберем наименьшее:

min (5 : ²/₃ , 1 : ¹/₃ ) = 3

Следовательно, 2-ая строка является ведущей.

Разрешающий элемент равен (¹/₃) и находится на пересечении ведущего столбца и ведущей строки. (Таблица 8)

Таблица 8 – Симплекс-таблица с выделенным разрешающим элементом

Базис	B	x1	x2	x3	x4	x5
x3	5	^5/6	^2/3	1	^1/6	0
x5	1	^1/6	^1/3	0	^-1/6	1
Базис	B	x1	x2	x3	x4	x5
F(X2)	10+M	-1^1/3+M	-2^2/3+M	0	^1/3-1^1/6M	0

Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x₅ в план 2 войдет переменная x₂.

Строка, соответствующая переменной x₂ в плане 2, получена в результате деления всех элементов строки x₅ плана 1 на разрешающий элемент ¹/₃

На месте разрешающего элемента в плане 2 получаем 1.

В остальных клетках столбца x₂ плана 2 записываем нули.

Таким образом, в новом плане 2 заполнены строка x₂ и столбец x₂.

Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.

Получаем новую симплекс-таблицу:

Таблица 9 – Симплекс-таблица после совершения итерации №1

Базис	B	x1	x2	x3	x4	x5
x3	3	^1/2	0	1	^1/2	-2
x2	3	^1/2	1	0	^-1/2	3
F(X2)	18	0	0	0	-1-M	8-M

Проверка критерия оптимальности.

Среди значений индексной строки нет положительных. Поэтому эта таблица определяет оптимальный план задачи.

Окончательный вариант симплекс-таблицы:

Базис	B	x1	x2	x3	x4	x5
x3	3	^1/2	0	1	^1/2	-2
x2	3	^1/2	1	0	^-1/2	3
F(X2)	18	0	0	0	-1-M	8-M

Так как в оптимальном решении отсутствуют искусственные переменные (они равны нулю), то данное решение является допустимым.

Оптимальный план можно записать так:

Решение получилось целочисленным. Нет необходимости применять метод Гомори.

Оптимальный целочисленный план можно записать так: