Получение целочисленного решения методом Гомори

Оптимальный план нашей задачи для критерия «выручка» имел вид:

Значение целевой функции на данном плане тысяч рублей.

Требуется построить правильное сечение для одной из компонент плана. Наибольшая дробная часть у третей компоненты (0,8).

где – элементы таблицы в строке выбранного вектора кроме 3го элемента, {…} – дробная часть от числа, – 3я компонента плана.

Так выходит:

И при переходе к уравнению:

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

 

Таблица 3. Двойственный симплекс метод

Сσ	Базис	А0=b	A1	A2	A3	A4	A5	A6
	A1	6,4				0,4
	A2						0,6
	A3	0,8				-0,2	-0,2
	A6	-0,8				-0,8	-0,8
		314,6				1,6	7,4
	A1						-0,4
	A2						0,6	0,75
	A3							-0,25
	А4							-1,25
							5,8	9,25

 

Решение получилось целочисленным. Нет необходимости применять метод Гомори ещё раз. Оптимальный целочисленный план можно записать так:

Таким образом, производя 6 единиц продукции первого вида, 11 единиц продукции второго вида и 1 продукцию третьего вида мы можем получить 313 тысяч рублей выручки.