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