Контрольная работа: Решение задач симплекс методом

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

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

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

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

Расход каждого ресурса на производство единицы продукции является за­данной величиной, определяется по рецептуре и обозначается символами а₁₁ , 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 руб.