Решить задачу линейного программирования симплекс-методом

Пусть необходимо выпускать изделий 1 – х1, изделий 2 – х2, изделий 3 – х3, тогда ограничения
по оборудованию А:6x1+x2≤60,по оборудованию Б:x1+5x2+x3≤80,по оборудованию В:3x2+4x3≤80,по оборудованию Г:2x1+3x2+2x3≤50,по оборудованию Д:3x1+4x3≤56,
по неотрицательности переменных:
х1>0,
х2>0,
х3>0.
Прибыль определяется как F(X)=6x1+5x2+7x3, которую необходимо максимизировать.
Математическая модель имеет вид:
F(X) = 6x1+5x2+7x3 → max
6x1+x2≤60,x1+5x2+x3≤80,3x2+4x3≤80,2x1+3x2+2x3≤50,3x1+4x3≤56,
х1>0,
х2>0,
х3>0.
Решим прямую задачу линейного программирования симплексным методом с использованием симплексной таблицы.
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x4. В 2-м неравенстве смысла (≤) вводим базисную переменную x5. В 3-м неравенстве смысла (≤) вводим базисную переменную x6. В 4-м неравенстве смысла (≤) вводим базисную переменную x7. В 5-м неравенстве смысла (≤) вводим базисную переменную x8.
6x1+x2+x4 = 60x1+5x2+x3+x5 = 803x2+4x3+x6 = 802x1+3x2+2x3+x7 = 503x1+4x3+x8 = 56
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
6 1 0 1 0 0 0 0
1 5 1 0 1 0 0 0
0 3 4 0 0 1 0 0
2 3 2 0 0 0 1 0
3 0 4 0 0 0 0 1
Базисные переменные – это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x4, x5, x6, x7, x8
Полагая, что свободные переменные равны 0, получим первый опорный план:
X0 = (0,0,0,60,80,80,50,56)
Базисное решение называется допустимым, если оно неотрицательно.
Базис B x1 x2 x3 x4 x5 x6 x7 x8
x4 60 6 1 0 1 0 0 0 0
x5 80 1 5 1 0 1 0 0 0
x6 80 0 3 4 0 0 1 0 0
x7 50 2 3 2 0 0 0 1 0
x8 56 3 0 4 0 0 0 0 1
F(X0) 0 -6 -5 -7 0 0 0 0 0
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1 . Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai3и из них выберем наименьшее:
min (- , 80 : 1 , 80 : 4 , 50 : 2 , 56 : 4 ) = 14
Следовательно, 5-ая строка является ведущей.
Разрешающий элемент равен (4) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 x5 x6 x7 x8 min
x4 60 6 1 0 1 0 0 0 0 -
x5 80 1 5 1 0 1 0 0 0 80
x6 80 0 3 4 0 0 1 0 0 20
x7 50 2 3 2 0 0 0 1 0 25
x8 56 3 0 4 0 0 0 0 1 14
F(X1) 0 -6 -5 -7 0 0 0 0 0
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. Вместо переменной x8 в план 1 войдет переменная x3.
Строка, соответствующая переменной x3 в плане 1, получена в результате деления всех элементов строки x8 плана 0 на разрешающий элемент РЭ=4