Меню Главная Юридпсихология Этика эстетика Электротехника Эктеория Физика Управление персоналом Уголовный процесс Уголовное право Схемотехника Стратегический менеджмент САПР Ресторанно-гостиничный бизнес бытовое обслуживан Реклама и PR Режущий инструмент Неопределено Метрология Матметоды в эк-ке Исторические личности Искусство и культура Информатика Иностранные языки Гражданское процессуальное право Гражданское право Государственное регулирование и налогообложение Сонник Карта сайта Поиск По всему сайту Статьи Комментарии Файлы Форум Гостевая Ссылки Новости	Решение задач симплекс-методом Решение задач симплекс-методом ЗАДАЧА 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 руб.

Снижение запасов сырья приводит к изменениям выпуска продукции и суммы прибыли в обратном порядке.

Элементы целевой строки оптимального плана называются двойственными оценками, которые определяют величину изменения прибыли при изменении за­пасов сырья на I ед.

Страницы: 1, 2, 3, 4, 5, 6

     Наверх    

© 2009 Все права защищены.