Оптимизации выпуска продукции симплекс-методом

Получаем следующую задачу: найти наибольшее значение целевой функции
L = 32x1+24x2+9x3+15x4→ max
на множестве решений системы линейных неравенств (допустимом множестве):
7x1+5x2+3x3+6x4=78 , 20x1+13x2+17x3+35x4=500 12x1+16x2+9x3+18x4=250 x1,x2,x3,x4≥0.
Приведем систему к единичной матрице методом жордановских преобразований.1. В качестве базовой переменной можно выбрать x2.Разрешающий элемент РЭ=5. Строка, соответствующая переменной x1, получена в результате деления всех элементов строки x2 на разрешающий элемент РЭ=5. На месте разрешающего элемента получаем 1. В остальных клетках столбца x1 записываем нули.Все остальные элементы определяются по правилу прямоугольника.Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.НЭ = СЭ - (А*В)/РЭСТЭ - элемент старого плана, РЭ - разрешающий элемент (5), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.Представим расчет каждого элемента в виде таблицы:
7 : 5 5 : 5 3 : 5 6 : 5 78 : 5
20-(7 • 13):5 13-(5 • 13):5 17-(3 • 13):5 35-(6 • 13):5 500-(78 • 13):5
12-(7 • 16):5 16-(5 • 16):5 9-(3 • 16):5 18-(6 • 16):5 250-(78 • 16):5
Получаем новую матрицу:
7/5 1 3/5 6/5 78/5
9/5 0 46/5 97/5 1486/5
-52/5 0 -3/5 -6/5 2/5
2 . В качестве базовой переменной можно выбрать x3.Разрешающий элемент РЭ=91/5. Строка, соответствующая переменной x2, получена в результате деления всех элементов строки x3 на разрешающий элемент РЭ=91/5. На месте разрешающего элемента получаем 1. В остальных клетках столбца x2 записываем нули.Все остальные элементы определяются по правилу прямоугольника.Представим расчет каждого элемента в виде таблицы:
12/5-(14/5 • 3/5):91/5 1-(0 • 3/5):91/5 3/5-(91/5 • 3/5):91/5 11/5-(192/5 • 3/5):91/5 153/5-(2971/5 • 3/5):91/5
14/5 : 91/5 0 : 91/5 91/5 : 91/5 192/5 : 91/5 2971/5 : 91/5
-102/5-(14/5 • -3/5):91/5 0-(0 • -3/5):91/5 -3/5-(91/5 • -3/5):91/5 -11/5-(192/5 • -3/5):91/5 2/5-(2971/5 • -3/5):91/5
Получаем новую матрицу:
59/46 1 0 -3/46 -87/23
9/46 0 1 97/46 743/23
-473/46 0 0 3/46 455/23
3. В качестве базовой переменной можно выбрать x4.Разрешающий элемент РЭ=3/46. Строка, соответствующая переменной x3, получена в результате деления всех элементов строки x4 на разрешающий элемент РЭ=3/46. На месте разрешающего элемента получаем 1. В остальных клетках столбца x3 записываем нули.Все остальные элементы определяются по правилу прямоугольника.Представим расчет каждого элемента в виде таблицы:
113/46-(-1013/46 • -3/46):3/46 1-(0 • -3/46):3/46 0-(0 • -3/46):3/46 -3/46-(3/46 • -3/46):3/46 -318/23-(1918/23 • -3/46):3/46
9/46-(-1013/46 • 25/46):3/46 0-(0 • 25/46):3/46 1-(0 • 25/46):3/46 25/46-(3/46 • 25/46):3/46 327/23-(1918/23 • 25/46):3/46
-1013/46 : 3/46 0 : 3/46 0 : 3/46 3/46 : 3/46 1918/23 : 3/46
Получаем новую матрицу:
-9 1 0 0 16
998/3 0 1 0 -1822/3
-473/3 0 0 1 910/3
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (2,3,4).Выразим базисные переменные через остальные:x2 = 9x1+16x3 = -998/3x1-6071/3x4 = 473/3x1+3031/3Подставим их в целевую функцию:F(X) = 32x1+24(9x1+16)+9(-998/3x1-6071/3)+15(473/3x1+3031/3)илиF(X) = -381x1-532Выразим базисные переменные через остальные:x2 = 9x1+16x3 = -998/3x1-6071/3x4 = 473/3x1+3031/3Подставим их в целевую функцию:F(X) = 32x1+24(9x1+16)+9(-998/3x1-6071/3)+15(473/3x1+3031/3)илиF(X) = -381x1-532-9x1+x2=16998/3x1+x3=-6071/3-473/3x1+x4=3031/3При вычислениях значение Fc = -532 временно не учитываем.Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
A = -9 1 0 0
998/3 0 1 0
-473/3 0 0 1
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.Решим систему уравнений относительно базисных переменных: x2, x3, x4Полагая, что свободные переменные равны 0, получим первый опорный план:X0 = (0,16,-6071/3,3031/3)Базисное решение называется допустимым, если оно неотрицательно.
Базис B x1 x2 x3 x4
x2 16 -9 1 0 0
x3 -1822/3 998/3 0 1 0
x4 910/3 -473/3 0 0 1
F(X0) 0 381 0 0 0
Переходим к основному алгоритму симплекс-метода.1