Similar presentations:
Методы решения ЗЛП. Двойственность. Анализ оптимальных решений ЗЛП. (Леция 3)
1. Методы решения ЗЛП. Двойственность. Анализ оптимальных решений ЗЛП
Лекция3
Add Your Company
Slogan
Методы решения ЗЛП.
Двойственность.
Анализ оптимальных
решений ЗЛП
2.
Свойства решений ЗЛП.
1. Область
допустимых значений задачи линейного
программирования выпукла
2. Целевая функция ЗЛП достигает своего минимального
(максимального) значения в угловой точке многогранника
решений. Если целевая функция достигает своего
экстремального значения более чем в одной угловой
точке многогранника решений, то она достигает того же
значения в любой линейной выпуклой комбинации этих
угловых точек.
www.wondershare.com
3. Геометрическая интерпретация
www.wondershare.com4.
Симплекс-методwww.wondershare.com
5.
Симплекс-методМетоды контроля:
1. Z-оценки при базисных переменных равны нулю
2. Значения правой части всегда неотрицательны
3. Значение целевой функции на каждом шаге не
ухудшается.
Зацикливание
Зацикливание
может
возникать
при
наличии
вырожденного опорного решения. Выражается в том,
что значение целевой функции на следующем шаге не
меняется.
www.wondershare.com
6.
Исследование оптимальных решенийИсследование на устойчивость
Исследование на устойчивость – исследование диапазона
изменения правых частей системы ограничений, при котором
.
найденное
оптимальное решение не изменяется.
Исследование на чувствительность
При исследовании на чувствительность исследуется
зависимость решения ЗЛП от небольших изменений
коэффициентов в условии задачи. При этом предыдущее
решение
может
стать
либо
недопустимым,
либо
неоптимальным.
• К недопустимости пред. решения могут привести
изменения запасов ресурсов и/или добавление новых
ограничений.
• К неоптимальности пред. решения могут привести
изменение
целевой
функции
и/или
изменение
технологических коэффициентов и/или включение в модель
нового вида производственной деятельности.
www.wondershare.com
7.
Анализ решения ЗЛП.
www.wondershare.com
8.
Анализ решения ЗЛП.
www.wondershare.com
9.
Анализ решения ЗЛП.
www.wondershare.com
10.
Графический анализ чувствительностиИзменение коэффициентов целевой функции
.
www.wondershare.com
11.
Графический анализ чувствительностиДоступность ресурсов
.
www.wondershare.com
12.
Графический анализ чувствительностиДоступность ресурсов
.
www.wondershare.com
13.
Двойственность в линейном программированииПравила построения двойственных задач:
1. Если в исходной задаче целевая функция
исследуется на min, то в двойственной задаче она
будет исследоваться на max и наоборот.
2. Если в исходной задаче n переменных и m
уравнений, то в двойственной задаче будет m
переменных и n уравнений.
3.
Коэффициенты целевой функции исходной
задачи становятся правыми частями ограничений
двойственной задачи, а правые части системы
ограничений
исходной
задачи
становятся
коэффициентами целевой функции исходной задачи.
www.wondershare.com
14.
Двойственность в линейном программировании4. Матрица
ограничений
двойственной
задачи получается из матрицы ограничений
исходной
задачи транспонированием.
.
xk 0,
то
в
5. Если в исходной задаче
двойственной
задаче
k-ое
ограничение
будет
неравенством, если же в исходной задаче x k не имело
ограничений на знак, то k-ое ограничение в
двойственной задаче будет равенством.
6. Если в исходной задаче l-ое ограничение неравенство, то в двойственной задаче y 0 ; если
l
же в исходной задаче l-ое ограничение - равенство, то
в двойственной задаче нет ограничений на знак yi.
www.wondershare.com
15.
Пара симметричных двойственных задач.www.wondershare.com
16.
Экономический смысл двойственности.
www.wondershare.com
17.
Исследование на чувствительность.
www.wondershare.com
18.
Экономический смысл двойственностиF 2 x1 3 x2 max
Z 18 y1 16 y2
x1 3 x2 18
2 x x 16
1 2
x2 5
3 x1 21
x1 , x2 0
F
*
5 y3 21 y4 min
y1 2 y2 3 y4 2
3 y1 y2 y3 3
y1 , y2 , y3 , y4 0
max
Z
*
min
24
www.wondershare.com
19.
Экономический смысл двойственностиЗадача 1
Остатки ресурсов (ед.)
Число единиц
продукции
x*1 = 6 x*2 = 4 x*3 = 0
x*4 = 0 x*5 = 1 x*6 = 3
y*5 = 0 y*6 = 0 y*1 = 4/5 y*2 = 3/5 y*3 = 0 y*4 = 0
Превышение
Условные цены ресурсов
затрат на
ресурсы над
ценой
реализации
Задача 2
Компоненты оптимального решения двойственной задачи
называются оптимальными двойственными оценками исходной
задачи (скрытые доходы).
Они определяют степень дефицитности ресурса.
www.wondershare.com
20.
Метод искусственного базисаZ 3x 2 x min
1
2
5 x 3x 5,
1
2
3x 10 x 10.
2
1
5 3
5
3 10
10
x ,x 0
1 2
Z 3x 2 x Mx Mx min
1
2
3
4
5 x 3x x 5,
1
2 3
3x 10 x x 10.
1
2 4
5 3 1 0 5
3 10 0 1 10
x ,x ,x ,x 0
1 2 3 4
www.wondershare.com
21.
Метод искусственного базисаВ результате может быть:
1. Получено оптимальное решение, в котором все
искусственные переменные равны нулю. Это и есть
оптимальное решение задачи.
2. Получено оптимальное решение, в котором хотя бы
одна искусственная переменная осталась в базисе.
Это означает, что исходная задача не имеет решения,
т.е. ОДЗ пустая.
3. В искусственной задаче видно, что целевая функция
не ограничена на ОДЗ.
www.wondershare.com