Метод Гомори

Алгоритм метода:

1) Отбрасывается условие целочисленности и полученная ЗЛП решается симплекс-методом.

2) Если оптимальное решение ЗЛП удовлетворяет ограничению целочисленности, то оно и является решением исходной задачи.

3) Если оптимальное решение ЗЛП не удовлетворяет ограничению целочисленности, то к основным ограничениям добавляется новое линейное ограничение, обладающее следующими свойствами:

а) оптимальный нецелочисленный план задачи ему не удовлетворяет;

б) любой целочисленный план задачи ему удовлетворяет.

4) Решается расширенная задача.

5) Процесс повторяется до получения целочисленного решения.

Определение 9.2.Дополнительное ограничение, где фигурные скобки означают дробную часть соответствующего числа, называется сечением Гомори, а метод Гомори – методом сечения.

Задача.Контейнер объемом помещен на контейнеровоз грузоподъемностью 12т. Контейнер требуется заполнить грузом двух наименований. Масса единицы груза, объем единицы груза, стоимости приведены в таблице:

Вид груза	т		ден.ед.

Требуется загрузить контейнеровоз таким образом, чтобы стоимость перевозимого груза была максимальной.

Решим задачу методом Гомори.

Введем обозначения: х₁ – количество груза первого вида, х₂ – количество груза второго вида. Тогда экономико-математическая модель задачи примет вид:

.

Преобразуем математическую модель ЗЛП без учета целочисленности переменных к допустимому предпочтительному виду канонической формы:

.

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

*
	-10	-12*
	*	5/2			-1/2	19/2
	1/2			1/2	5/2
	-4*				-30
				2/5	-1/5	19/5
			-1/5	3/5	3/5
			8/5	26/5	-226/5

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

Замечание 9.1. Если имеется несколько дробных , то для той у которой дробная часть больше всего составляется ограничение.

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

,

иначе

.

Преобразуем полученное ограничение к канонической форме с предпочтительной переменной:

.

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

				2/5	-1/5		19/5
			-1/5	3/5		3/5
			-2/5	-4/5		-4/5
			8/5*	26/5		-226/5
					-5/2
						-42

Оптимальное решение расширенной ЗЛП удовлетворяет ограничению целочисленности.

Ответ: , .

Таким образом, контейнер надо загрузить 3 ед. груза первого вида и 1 ед. второго вида, при этом стоимость перевозимого груза максимальна и равна 42 ден. ед.

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