Двойственная задача
На основании информации, приведенной в таблице, была решена задача оптимального использования ресурсов на максимум общей стоимости.
Ресурсы Нормы затрат ресурсов на единицу продукции Запасы
1 вид 2 1 3 200
2 вид 1 2 4 180
3 вид 2 4 1 240
Цена 40 60 80
Требуется:
1. Сформулировать прямую оптимизационную задачу на максимум общей стоимости продукции, указать оптимальную производственную программу.
2. Сформулировать двойственную задачу и найти ее оптимальный план.
3. Проанализировать использование ресурсов в оптимальном плане.
4. Определить, как изменятся общая стоимость продукции и план выпуска при увеличении запасов сырья на 18 ед.
5.Определить целесообразность включения в план изделия четвертого вида, на
изготовление которого расходуется по две единицы каждого вида ресурсов ценой 70 ед.
Обозначим
х1 - план выпуска продукции вида 1
х2 - план выпуска продукции вида 2
х3 - план выпуска продукции вида 3
прямая задача линейного программирования
-99060280670F(X) = 40x1+60x2+80x3
2x1+x2+3x3≤200
x1+2x2+4x3≤180
2x1+4x2+x3≤240
х1,х2,х3 ≥ 0
Составим шаблон решения задачи в Excel
Заполним окно инструмента Поиск решений
Решение
Оптимальный план прямой задачи
х1 = 61,9
х2 = 24,76
х3 = 17,14
Построим двойственную задачу
Расширенная матрица А прямой задачи
2 1 3 200
А = 1 2 4 180
2 4 1 240
40 60 80
Транспонированная матрица AT
2 1 2 40
1 2 4 60
3 4 1 80
200 180 240 0
Условиям неотрицательности переменных исходной задачи соответствуют неравенства-ограничения двойственной,
направленные в другую сторону. И наоборот, неравенствам-ограничениям в исходной соответствуют условия неотрицательности в двойственной.
-127635269875Двойственная задача
200y1+180y2+240y3 → min
2y1+y2+2y3≥40
y1+2y2+4y3≥60
3y1+4y2+y3≥80
y1 ≥ 0
y2 ≥ 0
y3 ≥ 0
Применяя теорему двойственности, получим решение двойственной задачи по известному решению исходной задачи.
Найдем решение двойственной задачи у* воспользовавшись второй теоремой двойственности и известным оптимальным планом х*.
Поскольку x1>0, 1-е ограничение в двойственной задаче будет равенством.
Поскольку x2>0, 2-е ограничение в двойственной задаче будет равенством.
Поскольку x3>0, 3-е ограничение в двойственной задаче будет равенством.
-127635582930Таким образом, решение двойственной задачи сводится к решению уравнений при следующих условиях:
2y1+y2+2y3 = 40
y1+2y2+4y3 = 60
3y1+4y2+y3 = 80
200y1+180y2+240y3 → min
АХ=В Х = А-1В
2 1 2
40
0,666667 -0,33333 2,78E-17
А = 1 2 4
В = 60
А-1 = -0,52381 0,190476 0,285714
3 4 1
80
0,095238 0,238095 -0,14286
6,67
А-1В = 13,33
6,67
Решение двойственной задачи
y1 = 6,67
y2 = 13,33
y3 = 6,67
Это - объективно обусловленные оценки ресурсов (теневые, условные, скрытые цены ресурсов)
Анализ использования ресурсов
Окончательное значение = Ограничение правая сторона – ресурсы используются полностью.
Определим, как изменятся общая стоимость продукции и план выпуска при увеличении запасов сырья на 18 ед.
Целевая функция вырастет на 480 ед.
Выпуск х1 вырастет на 4,29
Выпуск х2 вырастет на 1,71
Выпуск х3 вырастет на 2,57
Определим целесообразность включения в план изделия четвертого вида, на изготовление которого расходуется по две единицы каждого вида ресурсов ценой 70 ед.
2*6.667 + 2*13.333 + 2*6.667 = 53.333 ≤ 70
Поскольку реальная цена новой группы продукции меньше или равна, то производство продукции нового вида выгодно.
Задать вопрос
на новый заказ в Автор24.
