Некоторая фирма выпускает четыре вида (различной) продукции, используя четыре вида сырья. В таблице указаны:
технологические коэффициенты аy, которые показывают, сколько единиц i-го вида сырья требуется для производства одной единицы j-го вида продукции;
прибыль сj, получаемая от производства j-го вида продукции (в нижней строке таблицы);
запасы сырья в планируемый период (в тех же единицах).
Составить такой план выпуска продукции, при котором будет обеспечена максимальная прибыль.
Решение задачи оформить поэтапно:
1) составить математическую модель задачи;
2) привести задачу к каноническому виду, пояснить экономический смысл
дополнительных переменных;
3) решить задачу симплекс-методом;
4) определить количество неизрасходованного сырья при найденном оптимальном плане;
5) построить двойственную задачу, решить ее;
6) дать экономический анализ двойственной задачи, оценить целесообразность введения в план нового вида продукции, если затраты на производство этой продукции и получаемая прибыль заданы в последней графе таблицы.
Виды
продукции
Виды сырья
Технологические коэффициенты аy Запасы
сырья
Новый вид продукции
A B C D
I 0,5 0,5 0,5 0 400 1
II 2,5 1 1 0 100 3
III 2,5 1 1 5 300 0
IV 0 2 1 2,5 500 4
Прибыль сj
3 5 4 5
61
Решение
Составим математическую модель задачи
х1 – количество выпускаемой продукции А
х2 – количество выпускаемой продукции В
х3 - – количество выпускаемой продукции С
х4 -– количество выпускаемой продукции D
Так как запасы сырья ограничены, то составим неравенства системы ограничений
0,5x1+ 0,5x2+0,5 x3≤4002,5x1+ x2+x3 ≤1002,5x1+ x2+ x3+ 5x4 ≤3002 x2+ x3+2, 5x4 ≤500х1, х2, х3, х4≥0
По своему экономическому содержанию переменные х1, х2, х3, х4 могут принимать только неотрицательные значения.
F = 3x1 + 5x2 + 4x3 + 5x4 → max - целевая функция (прибыль от производства выпущенной продукции)
Получили задачу линейного программирования – при имеющихся запасах сырья и прибыли зав единицу продукции, составить такой план, чтобы получить наибольший доход.
Введем дополнительные переменные х5, х6, х7, х8 – количество неиспользованного сырья. Запишем эту задачу в канонической форме
0,5x1+ 0,5x2+0,5 x3+x5=4002,5x1+ x2+x3 +x6=1002,5x1+ x2+ x3+ 5x4 +x7=3002 x2+ x3+2, 5x4 +x8=500xi≥0 i=1,2,3,4,5,6,7,8
F = 3x1 + 5x2 + 4x3 + 5x4 → max
Решим задачу симплекс-методом. Составим первую симплексную таблицу.
В качестве базисных переменных выберем переменные х5, х6, х7, х8, так как они входят только в одно уравнение и с единичным коэффициентом. Составим первый опорный план.
Базис хi
В х1 х2 х3 х4 х5 х6 х7 Х8
х5 400 0,5 0,5 0,5
0 1 0 0 0
х6 100 2,5 1 1
0 0 1 0 0
х7 300 2,5 1 1 5 0 0 1 0
Х8 500 0 2 1 2,5 0 0 0 1
F 0 -3 -5 -4 -5 0 0 0 0
Данный план не оптимален, т. к. в индексной строке имеются отрицательные элементы
.
Итерация 1
В качестве нового ведущего столбца возьмем столбец с наибольшим по модулю значением. Это четвертый столбец (выделим цветом) max-3, -5, -4=5
Для определения ведущей строки разделим столбец В на элементы ведущего столбца и найдем наименьшее значение (делим на положительные числа) min{-, -, 3005, 5002,5}=60
Третья строка будет ведущей (выделим цветом )
На пересечении ведущего столбца и ведущей строки стоит разрешающий элемент - 5
Пересчитаем симплекс-таблицу: в новом плане вместо переменной х7, в новый план войдет переменная х4, ведущую строку разделим на 5, на месте разрешающего элемента запишем 1, в остальных клетках столбца х4 запишем нули, остальные элементы таблицы пересчитаем по правилу прямоугольника
Базис хi
В х1 х2 х3 х4 х5 х6 х7 Х8 biai>0
х5 400 0,5 0,5 0,5
0 1 0 0 0 -
х6 100 2,5 1 1
0 0 1 0 0 -
х7 300 2,5 1 1 5 0 0 1 0 300/5=60 (min)
Х8 500 0 2 1 2,5 0 0 0 1 500/2,5=200
F 0 -3 -5 -4 -5 0 0 0 0
В индексной строке:
0--5*3005=300 -3--5*2,55=-0,5 -5--5*15=-4
-4--5*15=-3 0--5*05=00--5*15=1
В столбце В:
400-300*05=400 100-300*05=100 500-300*2,55=350
Остальные элементы:
0,5-2,5*05=0,5 2,5-2,5*05=2,5 0-2,5*2,55=-1,25
0,5-1*05=0,5 1-1*05=1 2-1*2,55=1,5
0,5-1*05=0,5 1-1*05=1 1-1*2,55=0,5 1-0*05=1 0-0*05=0 0-0*2,55=0
0-0*05=0 1-0*05=1 0-0*2,55=0
0-1*05=0 0-1*05=0 0-1*2,55=-0,5
0-0*05=0 0-0*05=1 1-0*2,55=1
Получим новую таблицу
Базис хi
В х1 х2 х3 х4 х5 х6 х7 Х8
х5 400 0,5 0,5 0,5
0 1 0 0 0
х6 100 2,5 1 1
0 0 1 0 0
Х4 60 0,5 15
15
1 0 0 15
0
Х8 350 -1,25 1,5 0,5 0 0 0 -0,5 1
F 300 -0,5 -4 -3 0 0 0 1 0
Данный план не оптимален, т