Составить план выпуска, при котором достигается максимальная прибыль

Пусть необходимо выпустить продукта А1 – х1, продукта А2 – х2, продукта А3 – х3, продукта А4 – х4, тогда ограничения
по сырью 1:10x1+5x2+8x3+8x4≤500,по сырью 2:10x1+22x2+22x3+12x4≤1200,по сырью 3:14x1+9x2+7x3+16x4≤800,по сырью 4:23x1+22x2+35x3+38x4≤2000,
по неотрицательности переменных:
х1>0,
х2>0,
х3>0,
х4>0.
Прибыль определяется как F(X)=224x1+346x2+162x3+204x4, которую необходимо максимизировать.
Математическая модель задачи имеет вид:
F(X)=224x1+346x2+162x3+204x4 → max
10x1+5x2+8x3+8x4≤500,10x1+22x2+22x3+12x4≤1200,14x1+9x2+7x3+16x4≤800,23x1+22x2+35x3+38x4≤2000,
х1>0,
х2>0,
х3>0,
х4>0.
Решим прямую задачу линейного программирования симплексным методом с использованием симплексной таблицы.
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x5. В 2-м неравенстве смысла (≤) вводим базисную переменную x6. В 3-м неравенстве смысла (≤) вводим базисную переменную x7. В 4-м неравенстве смысла (≤) вводим базисную переменную x8.
10x1+5x2+8x3+8x4+x5 = 50010x1+22x2+22x3+12x4+x6 = 120014x1+9x2+7x3+16x4+x7 = 80023x1+22x2+35x3+38x4+x8 = 2000
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
10 5 8 8 1 0 0 0
10 22 22 12 0 1 0 0
14 9 7 16 0 0 1 0
23 22 35 38 0 0 0 1
Базисные переменные – это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x5, x6, x7, x8
Полагая, что свободные переменные равны 0, получим первый опорный план:
X0 = (0,0,0,0,500,1200,800,2000)
Базисное решение называется допустимым, если оно неотрицательно.
Базис B x1 x2 x3 x4 x5 x6 x7 x8
x5 500 10 5 8 8 1 0 0 0
x6 1200 10 22 22 12 0 1 0 0
x7 800 14 9 7 16 0 0 1 0
x8 2000 23 22 35 38 0 0 0 1
F(X0) 0 -224 -346 -162 -204 0 0 0 0
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1 . Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai2и из них выберем наименьшее:
min (500 : 5 , 1200 : 22 , 800 : 9 , 2000 : 22 ) = 546/11
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (22) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 x5 x6 x7 x8 min
x5 500 10 5 8 8 1 0 0 0 100
x6 1200 10 22 22 12 0 1 0 0 600/11
x7 800 14 9 7 16 0 0 1 0 800/9
x8 2000 23 22 35 38 0 0 0 1 1000/11
F(X1) 0 -224 -346 -162 -204 0 0 0 0
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. Вместо переменной x6 в план 1 войдет переменная x2.
Строка, соответствующая переменной x2 в плане 1, получена в результате деления всех элементов строки x6 плана 0 на разрешающий элемент РЭ=22