Цех может производить в день до 50 изделий А и до 20 изделий Б.

Цех может производить в день до 50 изделий А и до 20 изделий Б. Суточный ресурс металла составляет 60 кг, при этом на изделие А расходуется 1 кг и на изделие Б – 2 кг. Составить план выпуска изделий, обеспечивающий цеху максимальную прибыль, если известно, что изделий А стоит в два раза больше изделия Б.

Математическая модель задачи:
1. Целевая функция:
F(X) = 2x1+x2 → max
2. Условия-ограничения:
x1≤50
x2≤20
x1+2x2≤60
Перейдем к канонической форме. В 1-м неравенстве смысла (≤) вводим базисную переменную x3. В 2-м неравенстве смысла (≤) вводим базисную переменную x4. В 3-м неравенстве смысла (≤) вводим базисную переменную x5:
x1+x3 = 50
x2+x4 = 20
x1+2x2+x5 = 60
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
A = 1 0 1 0 0
0 1 0 1 0
1 2 0 0 1
Полагая, что свободные переменные равны 0, получим первый опорный план: X0 = (0,0,50,20,60)
Базис B x1
x2
x3
x4
x5
x3
50 1 0 1 0 0
x4
20 0 1 0 1 0
x5
60 1 2 0 0 1
F(X0) 0 -2 -1 0 0 0
Итерация №0.
Текущий опорный план является неоптимальным, поскольку в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления: bi / ai1 и из них выберем наименьшее: min (50 : 1 , – , 60 : 1 ) = 50, т. е. 1-я строка является ведущей.
Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1
x2
x3
x4
x5
min
x3
50 1 0 1 0 0 50
x4
20 0 1 0 1 0 -
x5
60 1 2 0 0 1 60
F(X1) 0 -2 -1 0 0 0
В следующей симплексной таблице вместо переменной x3 в план 1 войдет переменная x1.
Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки x3 плана 0 на разрешающий элемент РЭ=1

. На месте разрешающего элемента получаем 1. В остальных клетках столбца x1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x1 и столбец x1. Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Расчет каждого элемента представлен ниже в таблице:
B x1
x2
x3
x4
x5
50 : 1 1 : 1 0 : 1 1 : 1 0 : 1 0 : 1
20-(50 × 0):1 0-(1 × 0):1 1-(0 × 0):1 0-(1 × 0):1 1-(0 × 0):1 0-(0 × 0):1
60-(50 × 1):1 1-(1 × 1):1 2-(0 × 1):1 0-(1 × 1):1 0-(0 × 1):1 1-(0 × 1):1
0-(50 × -2):1 -2-(1 × -2):1 -1-(0 × -2):1 0-(1 × -2):1 0-(0 × -2):1 0-(0 × -2):1
Новая симплекс-таблица:
Базис B x1
x2
x3
x4
x5
x1
50 1 0 1 0 0
x4
20 0 1 0 1 0
x5
10 0 2 -1 0 1
F(X1) 100 0 -1 2 0 0
Итерация №1.
Данный опорный план также является неоптимальным, поскольку в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления: bi / ai2 и из них выберем наименьшее: min (- , 20 : 1 , 10 : 2 ) = 5, т. е