Лабораторная работа по менеджменту на тему Решить методом Гомори задачу целочисленного программирования

Найти максимум целевой функции F(X) = 7x1 + 9x2 при следующих условиях ограничений:
- 2 x1 + 3x2≤6
7x1 + x2≤35
x1, x2 ≥0, x1, x2 –целые.

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме). В 1-м неравенстве смысла (≤) вводим базисную переменную x3. В 2-м неравенстве смысла (≤) вводим базисную переменную x4.
-2x1+3x2+x3 = 6
7x1+x2+x4 = 35
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
A = -2 3 1 0
7 1 0 1



X0 = (0,0,6,35)
Базисное решение называется допустимым, если оно неотрицательно.
Базис B x1 x2 x3 x4
x3 6 -2 3 1 0
x4 35 7 1 0 1
F(X0) 0 -7 -9 0 0

Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai2
и из них выберем наименьшее:
min (6 : 3 , 35 : 1 ) = 2
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (3) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 min
x3 6 -2 3 1 0 2
x4 35 7 1 0 1 35
F(X1) 0 -7 -9 0 0

4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. Вместо переменной x3 в план 1 войдет переменная x2. Строка, соответствующая переменной x2 в плане 1, получена в результате деления всех элементов строки x3 плана 0 на разрешающий элемент РЭ=3. На месте разрешающего элемента получаем 1. В остальных клетках столбца x2 записываем нули.
Таким образом, в новом плане 1 заполнены строка x2 и столбец x2. Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника. Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ. НЭ = СЭ - (А*В)/РЭ