Задача 1 (Ассортиментная задача)

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

Виды сырья Расход сырья на единицу продукции Общий запас сырья, ед.
М1 М2 М3
П1 2 (а11) 3 (а12) 1 (а13) 303 (b1)
П2 4 (а21) 2 (а22) 3 (а23) 275 (b2)
П3 3 (а31) 1 (а32) 4 (а33) 200 (b3)
Уровень прибыли на единицу продукции 24 (С1) 20 (С2) 28 (С3)

Для их производства используется основные виды ресурсов (сырья) трёх видов, условно названных П1, П2, П3 (в ед.).

Расход каждого ресурса на производство единицы продукции является заданной величиной, определяется по рецептуре и обозначается символами а11, а12, …, а32, а33, где а – норма расхода, первая подстрочная 1, 2, 3 – номер ресурса, вторая подстрочная 1, 2, 3 – номер ассортиментной группы конфет.

Наличие каждого ресурса для производства всех групп конфет принимается как известная величина и обозначается символами b1, b2, b3.

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

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

Поскольку решение задачи заключается в поиске такого плана производства, который обеспечивал бы в принятых условиях наибольший доход, принимаются те величины, которые являются неизвестными и обозначающими количества каждой группы конфет, включаемых в план производства: х1 для М1; х2 для М2; х3 для М3.

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

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

Целевая функция (суммарный доход)

Условия неотрицательности переменных

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

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

Целевая функция (суммарный доход)

Условия неотрицательности переменных

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

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

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



Сj P0 X0
X1 X2 X3 X4 X5 X6
X4
X5
X6
F -24 -20 -28

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

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

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

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

I итерация

Сj P0 X0
X1 X2 X3 X4 X5 X6
X4 5/4 11/4 -1/4
X5 7/4 5/4 -3/4
X6 3/4 1/4 1/4
F -3 -13

Затем элементы столбца X0 (свободные величины) делят на соответствующие коэффициенты ключевого столбца и полученные результаты сопоставляют между собой. Строка с наименьшим отношением принимается за ключевую и также для удобства выделяется. В нашем случае

Наименьшее отношение 50 имеет строка X4. Она и будет ключевой. Ключевой элемент 28.

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

В столбцах P0 и Cj занимают место вводимая в план неизвестная x1 с прибылью 28.

Остальные элементы преобразуются по следующему правилу:

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

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

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

Следуя этому правилу, преобразование элементов столбцов будет:

Включение на первой итерации в план неизвестной x1 (выпуска продукции П вида) обеспечит сумму прибыли 1400 рублей.

Решение задачи продолжается, так как в целевой строке два отрицательных элемента. Наибольший по модулю элемент (-13). Он находится в столбце X3, который принимается за разрешающий, а ключевой строкой будет X4.

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

II итерация

Сj P0 X0
X1 X2 X3 X4 X5 X6
X2 5/11 4/11 -1/11
X5 13/11 -5/11 -7/11
X3 7/11 -1/11 3/11
F 32/11 52/11 64/11




8259999097045983.html
8260040050843084.html
    PR.RU™