Метод Гóмори (метод отсекающих плоскостей)

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

1. Нахождение решения зцчп начинают с определения оптимального решения задачи без учёта требования целочисленности переменных.

После того, как это решение найдено, просматривают его компоненты. Если среди них нет дробных чисел, то найденное решение является оптимальным решением ЗЦЧП.

Если же некоторая переменная принимает дробное значение, то к системе уравнений необходимо добавить дополнительное ограничение.

(2) Составляют дополнительное неравенство: ,

где и - преобразованные исходные величины и , значения которых взяты из последней симплексной таблицы;

и - дробные части чисел¹.

Если дробные значения принимают несколько переменных, то дополнительное неравенство составляют для переменной, имеющей максимальную дробную часть (дополнительное ограничение может составляться и для целевой функции).

(3) Используя двойственный симплекс-метод, находят решение задачи, полученной в результате присоединения дополнительного ограничения.

(4) Если в найденном решении задачи переменные опять принимают дробные значения, то снова добавляют одно дополнительное ограничение, и процесс вычислений повторяют.

Если на некотором шаге при использовании двойственного симплекс-метода обнаружится отсутствие допустимого решения, то рассматриваемая ЗЦЧП не имеет допустимого целочисленного решения.

Пример 1.

Р е ш е н и е. Обе части первого неравенства системы ограничений умножим на 2 (чтобы коэффициенты при переменных стали целыми):

				ОЗЛП
1						2					3
	6	-1	3				2											3
	35	7	1				33											4
	0	7	9				-18	10	-3			-63					-63	-63	0

Дополнительное ограничение составим для переменной . Из последней симплексной таблицы имеем: ,

.

Дополнительное ограничение имеет вид:

,

или .

Умножим неравенство на и преобразуем его в уравнение:

,

.

Переменную введём в базис:

.

4				Использование двойственного симплекс-метода приводит к таблице 5.	5
						3	0	1		3	3	0
											4
											1
	-63					-59	-1	-8		-59	-59	0

Так как решение опять не является целочисленным, необходимо продолжить процесс введения отсечений.

Из последней таблицы: ,

.

,

или .

Умножим неравенство на и преобразуем его в уравнение:

,

,

.

Добавим это уравнение к последней таблице.

6				Использование двойственного симплекс-метода приводит к таблице 7.	7
	3	0	1			3	0	1
						4	1	-1
						1	1	-4
						4	-7	6
	-59	-1	-8			-55	-7	-2

Таблица 7 даёт оптимальное целочисленное решение исходной задачи:

при , .

Графическое решение

Область допустимых решений задачи без учёта требования целочисленности приведена на рисунке.

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

Первое дополнительное неравенство умножим на 22.

Получим: .

Запишем это неравенство в переменных и :

,

, , , .

Второе дополнительное неравенство умножим на 7.

Получим: .

Запишем это неравенство в переменных и :

, ,

, ,

, .

Пример 2. В цехе предприятия решено установить дополнительное оборудование, для размещения которого выделено 19/3 м² площади.

На приобретение оборудования предприятие может израсходовать 10 000 ден.ед., при этом оно может купить оборудование двух видов.

Комплект оборудования I вида стоит 1 000 ден.ед., а II вида – 3 000 ден.ед.

Приобретение одного комплекта оборудования I вида позволяет увеличить выпуск продукции в смену на 2 ед., а одного комплекта оборудования II вида – на 4 ед.

Зная, что для установки одного комплекта оборудования I вида требуется 2 м² площади, а оборудования II вида – 1 м² площади, определить такой набор дополнительного оборудования, который даёт возможность максимально увеличить выпуск продукции.

Математическая модель задачи

		ОЗЛП

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

												др.ч.
	10	1	3		3,33	0,33	0,33		2,73	-0,07	0,4	0,73
	19	6	3		9	5	-1		1,8	0,2	-0,2	0,8
	0	2	4		-13,33	0,67	-1,33		-14,53	-0,13	-1,2	0,47
Дополнительное ограничение:
					2,73	-0,07	0,4		3	-0,33	0,67
					1,8	0,2	-0,2		1	1	-1
					-0,8	-0,2	-0,8		4	-5	4
					-14,53	-0,13	-1,2		-14	-0,67	-0,67
						0,67	1,5

Ответ: , , , т.е. предприятию следует купить один комплект оборудования I-го вида и три комплекта оборудования II-го вида; увеличение выпуска продукции составит при этом 14 единиц в смену.