Похожие презентации:
Решение задач линейного программирования симплекс-методом. Двойственность ЗЛП
1. Решение задач линейного программирования симплекс-методом. Двойственность ЗЛП.
12.
1. Основы симплексного метода2. Пример решения ЗЛП симплексным
методом
3. Основы теории
двойственности ЗЛП
4. Примеры построения
двойственных задач
2
3.
1. Основы симплексного метода3
4.
45.
56.
67.
78.
89.
910.
1011.
1112.
1213.
1314.
1415.
2. Пример решения ЗЛП симплекснымметодом
15
16.
1617.
1718.
1819.
1920.
2021.
2122.
2223.
2324.
ПРИМЕР РЕШЕНИЯ ЭТОЙ ЖЕ ЗАДАЧИ ВПАКЕТЕ MATHCAD
24
25.
2526.
2627.
3. Основы теории двойственностиЗЛП
27
28.
МОДЕЛИ ДВОЙСТВЕННЫХ ЗАДАЧ ВЛИНЕЙНОМ ПРОГРАММИРОВАНИИ
28
29.
2930.
3031.
ПРИМЕР31
32.
3233.
3334.
3435.
ПОЛУЧЕНИЕ РЕШЕНИЯ ДВОЙСТВЕННОЙЗАДАЧИ ПО РЕЗУЛЬТАТАМ РЕШЕНИЯ ПРЯМОЙ
ЗАДАЧИ
Первая теорема двойственности:
Если существует единственное решение
исходной (прямой) задачи, то существует
и единственное решение двойственной
задачи, причем значения целевых функций
на оптимальных решениях совпадают:
max F = min FД.
35
36.
3637.
При построении двойственной задачииспользуются следующие правила:
• каждому ограничению исходной задачи
соответствует переменная двойственной
задачи;
37
38.
• каждой переменной исходной задачисоответствует ограничение
двойственной, причем коэффициентами
при неизвестных в i-м ограничении
служат коэффициенты при xi в
ограничениях исходной задачи;
38
39.
• коэффициентами при неизвестных в ЦФдвойственной задачи являются свободные
члены (правые части) в системе
ограничений исходной задачи, а правыми
частями в системе ограничений
двойственной задачи – коэффициенты при
неизвестных в ЦФ исходной, и если
исходная задача формулируется для
нахождения максимума, то двойственная для нахождения минимума (и наоборот).
39
40.
4. Примеры построения двойственных задачПример 1. Исходная задача – задача о раскрое
материала (рассматривали ранее)
40
41.
4142.
4243.
Кроме того, при использованиинадстройки «Поиск решения» в пакете MS
Excel:
если решить исходную задачу с помощью
этого средства и получить отчет по
устойчивости, то значения в графе
Лагранжа множитель (Теневая цена)
отчета по устойчивости есть оптимальные
значения двойственных переменных:
43
44.
4445.
Пример 2. Исходная задача – задача опланировании производства продукции
45
46.
Пример 2. Исходная задача – задача опланировании производства продукции
46
47.
4748.
4849.
Двойственная задача к рассматриваемойзадаче планирования производства продукции:
49
50.
5051.
Согласно первой теореме двойственности:51
52.
Для рассматриваемой задачи можно показать,что имеется следующее следствие первой
теоремы двойственности -
52
53.
(при использовании надстройки «Поискрешения» в пакете MS Excel).
53
54.
Удобно использовать надстройку«Поиск решения» в пакете MS Excel:
если решить исходную задачу с помощью
этого средства и получить отчет по
устойчивости, то значения в графе
Теневая цена отчета по устойчивости
есть оптимальные значения
двойственных переменных.
54