Составить план выпуска, при котором достигается максимальная прибыль. Решить задачу Симплекс методом. Виды сырья

Составить план выпуска, при котором достигается максимальная прибыль. Решить задачу Симплекс методом. Виды сырья (ресурса) указаны под именем Р1- Р4; технологические коэффициенты на пересечении столбцов А и строк Р. А1 А2 А3 А4 Запас Р1 10 5 8 8 500 Р2 10 22 22 12 1200 Р3 14 9 7 16 800 Р4 23 22 35 38 2000 Прибыль 224 346 162 204

Пусть необходимо выпустить продукта А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