Решение задач симплекс-методом
ЗАДАЧА 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
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9
