Завод изготовляет корпуса для холодильников и комплектует их оборудованием

Пусть холодильников «Саратов» необходимо выпускать х1, «Норд» – х2, «Бирюса» – х3, «Свияга» – х4, «Атлант» – х5, тогда ограничения
по трудозатратам:2x1+3x2+5x3+4x4+4x5≤9000,
по металлу:2x1+2x2+4x3+5x4≤8500,
по пластику:x1+3x2+2x3+4x5≤4000,
по краске:x1+2x2+3x3+3x4+2x5≤5000,
по неотрицательности переменных:
х1>0,
х2>0,
х3>0,
х4>0,
х5>0,
х1 – целое,
х2 – целое,
х3 – целое,
х4 – целое,
х5 – целое.
Прибыль определяется как F(X)=40x1+70x2+120x3+120x4+50x5, которую необходимо максимизировать.
Математическая модель задачи имеет вид:
F(X)=40x1+70x2+120x3+120x4+50x5 → max
2x1+3x2+5x3+4x4+4x5≤9000,
2x1+2x2+4x3+5x4≤8500,
x1+3x2+2x3+4x5≤4000,
x1+2x2+3x3+3x4+2x5≤5000,
х1>0,
х2>0,
х3>0,
х4>0,
х5>0,
х1 – целое,
х2 – целое,
х3 – целое,
х4 – целое,
х5 – целое.
Решим прямую задачу линейного программирования симплексным методом с использованием симплексной таблицы.
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x6. В 2-м неравенстве смысла (≤) вводим базисную переменную x7. В 3-м неравенстве смысла (≤) вводим базисную переменную x8. В 4-м неравенстве смысла (≤) вводим базисную переменную x9.
2x1+3x2+5x3+4x4+4x5+x6 = 90002x1+2x2+4x3+5x4+x7 = 8500x1+3x2+2x3+4x5+x8 = 4000x1+2x2+3x3+3x4+2x5+x9 = 5000
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
2 3 5 4 4 1 0 0 0
2 2 4 5 0 0 1 0 0
1 3 2 0 4 0 0 1 0
1 2 3 3 2 0 0 0 1
Базисные переменные – это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x6, x7, x8, x9
Полагая, что свободные переменные равны 0, получим первый опорный план:
X0 = (0,0,0,0,0,9000,8500,4000,5000)
Базисное решение называется допустимым, если оно неотрицательно.
Базис B x1 x2 x3 x4 x5 x6 x7 x8 x9
x6 9000 2 3 5 4 4 1 0 0 0
x7 8500 2 2 4 5 0 0 1 0 0
x8 4000 1 3 2 0 4 0 0 1 0
x9 5000 1 2 3 3 2 0 0 0 1
F(X0) 0 -40 -70 -120 -120 -50 0 0 0 0
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1 . Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x4, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai4и из них выберем наименьшее:
min (9000 : 4 , 8500 : 5 , - , 5000 : 3 ) = 16662/3
Следовательно, 4-ая строка является ведущей.
Разрешающий элемент равен (3) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 x5 x6 x7 x8 x9 min
x6 9000 2 3 5 4 4 1 0 0 0 2250
x7 8500 2 2 4 5 0 0 1 0 0 1700
x8 4000 1 3 2 0 4 0 0 1 0 -
x9 5000 1 2 3 3 2 0 0 0 1 5000/3
F(X1) 0 -40 -70 -120 -120 -50 0 0 0 0
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. Вместо переменной x9 в план 1 войдет переменная x4.
Строка, соответствующая переменной x4 в плане 1, получена в результате деления всех элементов строки x9 плана 0 на разрешающий элемент РЭ=3. На месте разрешающего элемента получаем 1. В остальных клетках столбца x4 записываем нули.
Таким образом, в новом плане 1 заполнены строка x4 и столбец x4. Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А∙В)/РЭ
СТЭ - элемент старого плана,
РЭ - разрешающий элемент (3),
А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Получаем новую симплекс-таблицу:
Базис B x1 x2 x3 x4 x5 x6 x7 x8 x9
x6 7000/3 2/3 1/3 1 0 4/3 1 0 0 -4/3
x7 500/3 1/3 -4/3 -1 0 -10/3 0 1 0 -5/3
x8 4000 1 3 2 0 4 0 0 1 0
x4 5000/3 1/3 2/3 1 1 2/3 0 0 0 1/3
F(X1) 200000 0 10 0 0 30 0 0 0 40
1