Для изготовления изделий типа А и В используется сырье трех видов, запасы каждого из которых . На производство одного изделия типа А требуется затратить кг сырья первого вида, кг сырья второго вида, кг сырья третьего вида. На одно изделие типа В расходуется соответственно кг сырья каждого вида. Прибыль от реализации единицы изделия А составляет (ден. ед.), а изделия В - (ден. ед.). Составить план производства изделий А и В, обеспечивающий максимальную прибыль от их реализации. Решить задачу симплекс-методом, а также дать геометрическое истолкование задачи. Все данные приведены в следующей таблице:
№
Варианта Изделие типа А
Изделие типа В
Запасы сырья
Затраты сырья на 1 кг изделия Цена 1 изделия Затраты сырья на 1 кг изделия Цена 1 изделия
10 3 4 3 2 5 8 11 3 453 616 627
Ответ
необходимо выпускать только изделия вида А в количесвтое 151 ед, чтобы получить максимальную прибыль в размере 302 ден ед
Решение
Построим математическую модель задачи.
Пусть х1-количество изделий вида А, ед, х2 - количество изделий вида В, ед запланированных к производству. Для их изготовления потребуется (3 х1 +5х2) единиц ресурса I, (4х1 +8х2) единиц ресурса II, (3х1 +11х2) единиц ресурса III. Так как, потребление ресурсов I, II, III не должно превышать их запасов, то связь между потреблением ресурсов и их запасами выразится системой неравенств:
3x1+5х2≤4534x1+8х2≤6163x1+11x2≤627
По смыслу задачи переменные х1 ≥ 0, х2 ≥0.
Конечную цель решаемой задачи – получение максимальной прибыли при реализации продукции – выразим как функцию двух переменных х1 и х2.
Суммарная прибыль составит 2х1 от реализации продукции А и 3х 2 от реализации продукции В, то есть : F = 2х1 +3х 2. →max.
Решим задачу симплекс методом
переход к канонической форме3x1+5x2+x3 = 453 4x1+8x2+x4 = 616 3x1+11x2+x5 = 627 Базисные переменные : x3, x4, x5 получим первый опорный план: X0 = (0,0,453,616,627) Базисное решение называется допустимым, если оно неотрицательно.
Базис B x1 x2 x3 x4 x5 min
x3 453 3 5 1 0 0 453/5
x4 616 4 8 0 1 0 77
x5 627 3 11 0 0 1 57
F(X) 0 -2 -3 0 0 0
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю. Вычислим значения Di по строкам как частное от деления: bi / ai2 и из них выберем наименьшее: min (453 : 5 , 616 : 8 , 627 : 11 ) = 57 Следовательно, 3-ая строка является ведущей. Разрешающий элемент равен (11) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 x5 min
x3 168 18/11 0 1 0 -5/11 308/3
x4 160 20/11 0 0 1 -8/11 88
x2 57 3/11 1 0 0 1/11 209
F(X) 171 -13/11 0 0 0 3/11
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю. Вычислим значения Di по строкам как частное от деления: bi / ai1 и из них выберем наименьшее: min (168 : 17/11 , 160 : 19/11 , 57 : 3/11 ) = 88 Следовательно, 2-ая строка является ведущей. Разрешающий элемент равен (19/11) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 x5 min
x3 24 0 0 1 -9/10 1/5 120
x1 88 1 0 0 11/20 -2/5 -
x2 33 0 1 0 -3/20 1/5 165
F(X) 275 0 0 0 13/20 -1/5
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. В качестве ведущего выберем столбец, соответствующий переменной x5, так как это наибольший коэффициент по модулю. Вычислим значения Di по строкам как частное от деления: bi / ai5 и из них выберем наименьшее: min (24 : 1/5 , - , 33 : 1/5 ) = 120 Следовательно, 1-ая строка является ведущей. Разрешающий элемент равен (1/5) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 x3 x4 x5 min
x5 120 0 0 5 -9/2 1 -
x1 136 1 0 2 -5/4 0 -
x2 9 0 1 -1 3/4 0 12
F(X) 299 0 0 1 -1/4 0
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. В качестве ведущего выберем столбец, соответствующий переменной x4, так как это наибольший коэффициент по модулю. Вычислим значения Di по строкам как частное от деления: bi / ai4 и из них выберем наименьшее: min (- , - , 9 : 3/4 ) = 12 Следовательно, 3-ая строка является ведущей. Разрешающий элемент равен (3/4) и находится на пересечении ведущего столбца и ведущей строки.
Получаем новую симплекс-таблицу:
Базис B x1 x2 x3 x4 x5
x5 174 0 6 -1 0 1
x1 151 1 5/3 1/3 0 0
x4 12 0 4/3 -4/3 1 0
F(X) 302 0 1/3 2/3 0 0
Среди значений индексной строки нет отрицательных