Решение задач симплекс методом (стр. 1 из 4)
ЗАДАЧА 1
Составить модель оптимального выпуска продукции для цеха кондитерской фабрики. Виды выпускаемой продукции (М), виды основного сырья (П) и его запасы, нормы расхода сырья на единицу, уровни прибыли приведены в таблице. Рассчитать план и провести его анализ.
| Виды сырья | Расходы сырья на единицу продукции | Общий запас сырья, ед. | |||
| М1 | М2 | М3 | |||
| П1 | 2 | 4 | 3 | 266 | |
| П2 | 1 | 3 | 4 | 200 | |
| П3 | 3 | 2 | 1 | 303 | |
| Уровень прибыли на ед. продукции | 20 | 24 | 28 | ||
Содержание задачи.
Цех кондитерской фабрики вырабатывает три ассортиментные группы конфет, условно обозначенные М1, М2, М3 /в ед./.
Для их производства используются основные виды ресурсов /сырья/ трех видов, условно названных П1, П2, П3 /в ед./.
Расход каждого ресурса на производство единицы продукции является заданной величиной, определяется по рецептуре и обозначается символами а11, a12..., а33, где а - норма расхода, первая подстрочная 1 – номер ресурса, вторая подстрочная 1, 2, 3 – номер ассортиментной группы конфет.
Наличие каждого ресурса для производства всех, групп конфет принимается как известная величина и обозначается символами в1, в2, в3.
Прибыль на продукцию также принимается как известная величина и обозначается символами c1, c2, с3.
Перечисленные параметры являются величинами известными и выражаются в единых единицах измерения, кроме прибыли. Прибыль или другой какой показатель, являющийся критерием оптимальности, выражается в единицах измерения дохода /например, прибыли/, получаемого от производства единицы продукции в денежном или другом каком-нибудь выражении.
Поскольку решение задачи заключается в поиске такого плана производства, который обеспечивал бы в принятых условиях наибольший доход, принимаются те величины, которые являются неизвестными и обозначающими количества каждой группы конфет, включаемых в план производства: x1 для M1; х2 для М2; х3 для М3.
Экономико-математическая модель в символическом виде.
Система ограничений
Целевая функция /суммарный доход/ F = с1х1 + с2х2 + с3х3 = мах
Условия неотрицательности неизвестных х1 ≥ 0, х2 ≥ 0, х3 ≥ 0
Символическая модель, наполненная численной информацией, будет иметь следующий вид:
2x1 + 4x2 + 3x3 ≤ 266
1x1 + 3x2 + 4x3 ≤ 200
3x1 + 2x2 + 1x3 ≤ 303
Прибыль от реализации выпускаемой продукции должна быть максимальной, то есть F= 20х1 + 24х2 + 28х3= max;
Решение задачи.
Для решения задачи симплексным методом неравенства преобразуются в эквивалентные равенства путем добавления в каждое неравенство по одному дополнительному неизвестному с коэффициентом + 1 и нулевым уравнением прибыли. Для удобства расчетов левые и правые части уравнений меняются местами. В этом случае исходные неравенства примут вид симплексных уравнений:
266 = 2x1 + 4x2 + 3x3 + 1x4
200 = 1x1 + 3x2 + 4x3 + 1x5
303 = 3x1 + 2х2 + 1x3 + 1x6
F= 20х1 + 24х2 + 28х3 + 0x4 + 0x5 + 0x6
Коэффициенты при неизвестных записываются в симплексной таблице, в которой выполняются расчеты и отражаются полученные результаты.
Исходная таблица
| cj | p0 | x0 | 20 | 24 | 28 | 0 | 0 | 0 |
| x1 | х2 | х3 | х4 | х5 | х6 | |||
| 0 | х4 | 266 | 2 | 4 | 3 | 1 | 0 | 0 |
| 0 | х5 | 200 | 1 | 3 | 4 | 0 | 1 | 0 |
| 0 | х6 | 303 | 3 | 2 | 1 | 0 | 0 | 1 |
| Zj - Cj | 0 | -20 | -24 | -28 | 0 | 0 | 0 | |
В столбцах таблицы записывают: в первом (Cj) – прибыль единицы продукции, которая вводится в план выпуска; во втором (Р0) – неизвестные, включаемые в план; в третьем (Х0) – свободные величины; в остальных – коэффициенты при неизвестных уравнений. В верхней части этих столбцов отражаются коэффициенты при неизвестных целевой функции.
В нижней строке (целевой) записываются получаемые расчетным путем показатели: в столбце х0 – суммарная прибыль планового выпуска, в остальных столбцах – прибыль единицы продукции с отрицательным знаком.
В последних трех столбцах коэффициенты при дополнительных неизвестных, равные единице, расположены по диагонали. Эта часть таблицы, называемая единичной подматрицей, необходима для вычислительных и аналитических целей.
При решении задач на максимум целевой функции наличие в целевой строке отрицательных чисел указывает на возможность начала или продолжения решения задачи. Порядок решения таков: из отрицательных чисел целевой строки выбирается наибольшее по модулю. Столбец, в котором оно находится, принимается за ключевой (или разрешающий) и для удобства расчетов выделяется. В нашем примере таким столбцом будет Х3, имеющий в целевой строке наибольшую по модулю величину -28.
1-ая итерация
| cj | p1 | x0 | x1 | х2 | х3 | х4 | х5 | х6 |
| 0 | х4 | 116 | 1.3 | 1.75 | 0 | 1 | -1 | 0 |
| 28 | х3 | 50 | 0.3 | 0.75 | 1 | 0 | 0.3 | 0 |
| 0 | х6 | 253 | 2.8 | 1.25 | 0 | 0 | -0 | 1 |
| Zj - Cj | 1400 | -13 | -3 | 0 | 0 | 7 | 0 | |
Затем элементы столбца Х0 (свободные величины) делят на соответствующие коэффициенты ключевого столбца и полученные результаты сопоставляют между собой. Строка с наименьшим отношением принимается за ключевую и также для удобства выделяется. В нашем случае 266/3 = 88,7; 200/4 = 50; 303/1 = 303. Наименьшее отношение 50 имеет срока х5, она и будет ключевой. Ключевой элемент 4.
Далее элементы таблицы преобразуются и записываются в новую таблицу. Первоначально преобразуют элементы ключевой строки путем деления их на ключевой элемент. Преобразованные элементы записывают в том же самом месте.
В столбцах Ро и Cj занимают место вводимая в план неизвестная х3 с прибылью 28 (итерация 1-я). Остальные элементы преобразуются по следующему правилу:
- для преобразуемого элемента в его столбце находят элемент ключевой строки, а в его строке - элемент ключевого столбца;
- соответствующие элементы ключевой строки и ключевого столбца перемножаются и полученное произведение делят на ключевой момент;
- частное от деления вычитают из значения элемента, которое он имел до преобразования, и полученный результат будет преобразованным элементом, который записывается в новую таблицу в том же самом месте. Следуя этому правилу, преобразование элементов столбца х0 будет:
Включение на первой итерации в план неизвестной х3 обеспечит сумму прибыли 1400 руб.
Решение задачи продолжается, так как в целевой строке два отрицательных элемента. Наибольший по модулю элемент -13. Он находится в столбце х1, который принимается за ключевой, а ключевой строкой будет х6 (116:1,3=92,8; 50:0,3=200; 253:2,8=92), ключевым элементом 2,8. Элементы таблицы преобразуются в том же порядке по изложенному правилу и записываются в новую таблицу.
2-я итерация
| cj | p2 | x0 | x1 | х2 | х3 | х4 | х5 | х6 |
| 0 | х4 | 1 | 0 | 1.18 | 0 | 1 | -1 | -0.5 |
| 28 | х3 | 27 | 0 | 0.64 | 1 | 0 | 0.3 | -0.1 |
| 13 | х1 | 92 | 1 | 0 | 0 | 0 | 0 | 0 |
| Zj - Cj | 2596 | 0 | 2.91 | 0 | 0 | 5.8 | 4.7 | |
В последней таблице целевая строка имеет только положительные элементы. Это значит, что составленный план оптимален и дальнейшее улучшение его невозможно.
Как видно из таблицы, оптимальный план предусматривает выпуск продукции П1 27 ед. (х1 = 27), П3 92 ед. (х3 = 92), дополнительного неизвестного П4 1 ед. (х4 = 1). П2 и дополнительные неизвестные в план не вошли, следовательно, х2 = 0, х5 = 0 х6 = 0. Подставив значения неизвестных в уравнения, получим:
2 * 92 + 4 * 0 + 3 * 27 + 1 = 266
1 * 92 + 3 * 0 + 4 * 27 + 0 = 200
3 * 92 + 2 * 0 + 1 * 27 + 0 = 303
F = 20 * 92 + 24 * 0 + 27 * 28 = 2596
Анализ оптимального плана.
а) Запасы сырья трех видов используются не полностью, так как х4 = 1, а х5 = х6 = 0.
б) Рассмотрим элементы матрицы.
От выпуска продукции II следует отказаться.
Элементы столбца х5 показывают, что увеличение запасов сахара на I ед. (х5 = 1) позволит увеличить выпуск продукции III вида на 0,3 ед. Сумма прибыли увеличится на 5,8 руб.
Элементы столбца х6 показывают, что увеличение запасов жира на I ед. (х6 = 1) позволит уменьшить выпуск только продукции III вида на 0,1 ед. (27 - 0.1) Сумма прибыли увеличится на 4,7 руб.