Двойственные задачи линейного программирования
Для изготовления четырех видов продукции используют три вида сырья. Запасы сырья, нормы его расходов и прибыль от реализации каждого продукта приведены в таблице 2.
Таблица 2 – Исходные данные
Тип сырья Нормы затрат ресурсов на единицу продукции Запасы сырья
А Б В Г
I 1 0 2 1 180
II 0 1 3 2 210
III 4 2 0 4 800
Цена изделия 9 6 4 7
При решении задачи на максимум общей стоимости выпускаемой продукции были получены следующие результаты:
x1 = 95, x2 = 210, x3 = 16, x4 = 0.
Требуется:
Сформулировать прямую оптимизационную задачу на максимум общей стоимости, указать оптимальную производственную программу (пояснить нулевые значения x3 и x4).
Сформулировать двойственную задачу и найти ее оптимальный план.
Проанализировать использование ресурсов в оптимальном плане.
Определить, как изменится общая стоимость продукции и план выпуска при увеличении запасов сырья II и III вида на 120 и 160 единиц соответственно и одновременном уменьшении на 60 единиц запасов сырья I вида.
Определить целесообразность включения в план изделия «Д» ценой 12 ед., на изготовление которого расходуется 2 единицы каждого вида сырья.
Решение
Пусть , – объем производства продукции видов «А», «Б», «В» и «Г».
Система ограничений на использование ресурсов:
Ограничения на неотрицательность переменных модели:
, .
Целевая функция – общая стоимость выпускаемой продукции. Ее нужно максимизировать:
.
Решение прямой задачи:
x1 = 95, x2 = 210, x3 = 16, x4 = 0.
Тот факт, что x3 = 0 и , x4 = 0 означает, что продукцию видов «В» и «Г» производить невыгодно, исходя из критерия максимизации общей стоимости выпускаемой продукции.
Пусть yi, – двойственная или стоимостная оценка единицы i-го вида ресурса.
Составляем двойственную задачу:
каждому ограничению поставим в соответствие двойственную переменную , число переменных исходной задачи равно числу ограничений двойственной;
так как целевая функция прямой задачи исследуется на max, то целевая функция двойственной задачи будет исследоваться на min;
свободные члены системы ограничений прямой задачи станут коэффициентами целевой функции двойственной;
коэффициенты целевой функции прямой задачи станут свободными членами системы ограничений двойственной задачи;
матрицы коэффициентов систем ограничений прямой и двойственной задач являются транспонированными друг к другу.
Исходная задача:
,
Двойственная задача:
Решаем задачу в MS Excel
. Массив (B3:D3) соответствует переменным двойственной задачи (рис. 4). В ячейку F5 вводится формула СУММПРОИЗВ(B4:D4;B5:D5), задающая значение целевой функции. Аналогичные формулы вводятся и в ячейках E8:E10.
Для решения задачи воспользуемся макрофункцией Поиск решения, которая вызывается из меню Данные. Задаём параметры поиска решения. Вводим адрес целевой ячейки $F$5, указываем направление оптимизации целевой задача – Минимум. Задаём, что нужно изменять ячейки $B$3:$D$3. Добавляем ограничения из системы, указанной выше, используя еще одно условие неотрицательности переменных задачи, ведь число сотрудников должно быть целым числом
Задать вопрос
на новый заказ в Автор24.
