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

Выработать и принять оптимальное решение в задаче с линейными функциями при целочисленных аргументах методом Гомори (задача задана в формализованном виде) F(X) = 3x1 + 4x2 → max; при ограничениях: x1 + 2x2 ≤ 4, x1 + x2 ≤ 3, 2x1 + x2 ≤ 8 x1,x2 ≥ 0 . x1,x2 - целочисленные F(X) = 3x1 + 4x2 → max; при ограничениях: x1 + 2x2 ≤ 4, x1 + x2 ≤ 3, 2x1 + x2 ≤ 8 x1,x2 ≥ 0 . x1,x2 - целочисленные

Решим прямую задачу линейного программирования симплексным методом с использованием симплексной таблицы.
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x3. В 2-м неравенстве смысла (≤) вводим базисную переменную x4. В 3-м неравенстве смысла (≤) вводим базисную переменную x5.
x1+2x2+x3 = 4
x1+x2+x4 = 3
2x1+x2+x5 = 8
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
A = 1 2 1 0 0
1 1 0 1 0
2 1 0 0 1
Базисные переменные –это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x3, x4, x5
Полагая, что свободные переменные равны 0, получим первый опорный план:
X0 = (0,0,4,3,8)
Базисное решение называется допустимым, если оно неотрицательно.
Базис B x1 x2 x3 x4 x5
x3 4 1 2 1 0 0
x4 3 1 1 0 1 0
x5 8 2 1 0 0 1
F(X0) 0 -3 -4 0 0 0
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2

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