Решить задачу оптимизации выпуска продукции симплекс-методом.
Для выпуска четырех видов продукции требуются затраты сырья, рабочего времени и оборудования. Сформулировать экономико-математическую модель задачи на максимум прибыли и найти оптимальный план выпуска продукции.
Исходные данные приведены в таблице соответствующего варианта. Имеющееся сырье необходимо использовать полностью.
Тип ресурса Нормы затрат ресурсов
на единицу продукции Запасы
ресурсов
1 2 3 4
Сырье 2 2 1 2 30
Рабочее время 11 7 9 15 300
Оборудование 5 7 4 8 150
Прибыль на единицу продукции 15 13 8 8
Ответ
максимальная прибыль в размере 240 ед. будет достигнута в том случае, если выпускать 30 ед. третьей продукции, а остальную продукцию выпускать не выгодно.
Решение
Составим математическую модель задачи. В задаче: i= 1,2,3 (имеется три типа ресурсов) и j= 1,2,3,4 ( имеется продукция четырех видов)
Так как необходимо определить количество каждого вида продукции, то переменными в модели являются:
x1 – количество единиц 1-й продукции,
x2 – количество единиц 2-й продукции,
x3 – количество единиц 3-й продукции,
x4 – количество единиц 4-й продукции.
Целевая функция (прибыль):
Учитывая заданные нормы затрат ресурсов на единицу продукции, а также требования о том, что сырье должно быть использовано полностью, получим систему ограничений:
Для сырья получим строгое равенство, а рабочее время и оборудование ограничиваются неравенствами «≤», так как этих ресурсов нельзя использовать больше, чем есть в наличии.
Еще нужно добавить ограничения х1 ≥ 0; х2 ≥ 0; х3 ≥ 0; х4 ≥ 0 (из экономического смысла, т.к. количество продукта не может быть отрицательным)
Таким образом, получаем задачу линейного программирования:
Т.к. все входящие в модель функции (ограниченная и целевая функция) являются линейными, то данная задача относится к классу задач линейного программирования (ЛП).
Перейдем от неравенств к уравнениям, прибавляя к левым частям 2-го и 3-го неравенств новые неотрицательные переменные х5, х6 ≥ 0:
Система ограничений не содержит единичной матрицы, поэтому для построения начального опорного плана используем метод искусственного базиса
. Запишем расширенную задачу.
В первое уравнение вводим искусственную переменную х7 ≥ 0. Таким образом расширенная задача имеет вид:
Составим первую симплекс – таблицу для расширенной задачи.
Каждое Zj совпадает со скалярным произведением хj ∙ С, в последние две строки и М записываем оценки j = Zj – Cj, причем в -строку записываем части разностей j, которые не зависят от М, а в М лишь коэффициенты при М.
В столбце Сбаз записаны коэффициенты линейной функции Z, которые отвечают векторам базиса. В столбце х0 записан исходный (начальный) опорный план, здесь же вследствие дальнейших вычислений получим оптимальный план.
Проверку плана на оптимальность ведем по строке М, а после исключения из базиса всех искусственных векторов - по –строке.
Таблица І
і Баз Сбаз х0 15 13 8 8 0 0 М
х1 х2 х3 х4 х5 х6 х7
1 х7 М 30 2 2 1 2 0 0 1
2 х5 0 300 11 7 9 15 1 0 0
3 х6
150 5 7 4 8 0 1 0
0 -15 -13 -8 -8 0 0 0
М
-30 -2 -2 -1 -2 0 0 0
После заполнения таблицы надо выполнить такие операции:
1. Рассмотреть значения оценок j и определить, не является ли данний опорный план оптимальным, то есть или не выполняется условие j ≥ 0 для всех j;
2. Если для некоторых оценок j 0, то выбрать вектор, который надо ввести в базис, для чего найти индекс j , для которого достигается max модуля j, то есть выбираем столбец, в котором стоит самая большая по модулю отрицательная оценка
Задать вопрос
на новый заказ в Автор24.
