183653 (Решение задач симплекс-методом)

19

ЗАДАЧА 1

Составить модель оптимального выпуска продукции для цеха кондитер­ской фабрики. Виды выпускаемой продукции (М), виды основного сырья (П) и его запасы, нормы расхода сырья на единицу, уровни прибыли приведены в таб­лице. Рассчитать план и провести его анализ.

Содержание задачи.

Цех кондитерской фабрики вырабатывает три ассортиментные группы конфет, условно обозначенные М₁, М₂, М₃ /в ед./.

Для их производства используются основные виды ресурсов /сырья/ трех видов, условно названных П₁, П₂, П₃ /в ед./.

Расход каждого ресурса на производство единицы продукции является за­данной величиной, определяется по рецептуре и обозначается символами а₁₁, a₁₂..., а₃₃, где а - норма расхода, первая подстрочная 1 – номер ресурса, вторая подстрочная 1, 2, 3 – номер ассортиментной группы конфет.

Наличие каждого ресурса для производства всех, групп конфет принимает­ся как известная величина и обозначается символами в₁, в₂, в₃.

Прибыль на продукцию также принимается как известная величина и обо­значается символами c₁, c₂, с₃.

Перечисленные параметры являются величинами известными и выражают­ся в единых единицах измерения, кроме прибыли. Прибыль или другой какой показатель, являющийся критерием оптимальности, выражается в единицах из­мерения дохода /например, прибыли/, получаемого от производства единицы продукции в денежном или другом каком-нибудь выражении.

Поскольку решение задачи заключается в поиске такого плана производст­ва, который обеспечивал бы в принятых условиях наибольший доход, принима­ются те величины, которые являются неизвестными и обозначающими количест­ва каждой группы конфет, включаемых в план производства: x₁ для M₁; х₂ для М₂; х₃ для М₃.

Экономико-математическая модель в символическом виде.

Система ограничений

Целевая функция /суммарный доход/ F = с₁х₁ + с₂х₂ + с₃х₃ = мах

Условия неотрицательности неизвестных х₁ ≥ 0, х₂ ≥ 0, х₃ ≥ 0

Символическая модель, наполненная численной информацией, будет иметь следующий вид:

2x₁ + 4x₂ + 3x₃ ≤ 266

1x₁ + 3x₂ + 4x₃ ≤ 200

3x₁ + 2x₂ + 1x₃ ≤ 303

Прибыль от реализации выпускаемой продукции должна быть максималь­ной, то есть F = 20х₁ + 24х₂ + 28х₃ = max;

Решение задачи.

Для решения задачи симплексным методом неравенства преобразуются в эквивалентные равенства путем добавления в каждое неравенство по одному до­полнительному неизвестному с коэффициентом + 1 и нулевым уравнением при­были. Для удобства расчетов левые и правые части уравнений меняются места­ми. В этом случае исходные неравенства примут вид симплексных уравнений:

266 = 2x₁ + 4x₂ + 3x₃ + 1x₄

200 = 1x₁ + 3x₂ + 4x₃ + 1x₅

303 = 3x₁ + 2х₂ + 1x₃ + 1x₆

F = 20х₁ + 24х₂ + 28х₃ + 0x₄ + 0x₅ + 0x₆

Коэффициенты при неизвестных записываются в симплексной таблице, в которой выполняются расчеты и отражаются полученные результаты.

Исходная таблица

В столбцах таблицы записывают: в первом (C_j) – прибыль единицы про­дукции, которая вводится в план выпуска; во втором (Р₀) – неизвестные, вклю­чаемые в план; в третьем (Х₀) – свободные величины; в остальных – коэффици­енты при неизвестных уравнений. В верхней части этих столбцов отражаются коэффициенты при неизвестных целевой функции.

В нижней строке (целевой) записываются получаемые расчетным путем показатели: в столбце х₀ – суммарная прибыль планового выпуска, в остальных столбцах – прибыль единицы продукции с отрицательным знаком.

В последних трех столбцах коэффициенты при дополнительных неизвест­ных, равные единице, расположены по диагонали. Эта часть таблицы, называе­мая единичной подматрицей, необходима для вычислительных и аналитических целей.

При решении задач на максимум целевой функции наличие в целевой строке отрицательных чисел указывает на возможность начала или продолжения решения задачи. Порядок решения таков: из отрицательных чисел целевой строки выбирается наибольшее по модулю. Столбец, в котором оно находится, принимается за ключевой (или разрешающий) и для удобства расчетов выделя­ется. В нашем примере таким столбцом будет Х₃, имеющий в целевой строке наибольшую по модулю величину -28.

1-ая итерация

Затем элементы столбца Х₀ (свободные величины) делят на соответствую­щие коэффициенты ключевого столбца и полученные результаты сопоставляют между собой. Строка с наименьшим отношением принимается за ключевую и также для удобства выделяется. В нашем случае 266/3 = 88,7; 200/4 = 50; 303/1 = 303. Наименьшее отношение 50 имеет срока х₅, она и будет ключевой. Ключевой элемент 4.

Далее элементы таблицы преобразуются и записываются в новую таблицу. Первоначально преобразуют элементы ключевой строки путем деления их на ключевой элемент. Преобразованные элементы записывают в том же самом месте.

В столбцах Р_о и C_j занимают место вводимая в план неизвестная х₃ с при­былью 28 (итерация 1-я). Остальные элементы преобразуются по следующему правилу:

- для преобразуемого элемента в его столбце находят элемент ключевой строки, а в его строке - элемент ключевого столбца;

- соответствующие элементы ключевой строки и ключевого столбца пере­множаются и полученное произведение делят на ключевой момент;

- частное от деления вычитают из значения элемента, которое он имел до преобразования, и полученный результат будет преобразованным элементом, ко­торый записывается в новую таблицу в том же самом месте. Следуя этому пра­вилу, преобразование элементов столбца х₀ будет:

Включение на первой итерации в план неизвестной х₃ обеспечит сумму прибыли 1400 руб.

Решение задачи продолжается, так как в целевой строке два отрицатель­ных элемента. Наибольший по модулю элемент -13. Он находится в столбце х₁, который принимается за ключевой, а ключевой строкой будет х₆ (116:1,3=92,8; 50:0,3=200; 253:2,8=92), ключевым элементом 2,8. Элементы таблицы преобра­зуются в том же порядке по изложенному правилу и записываются в новую таб­лицу.

2-я итерация

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