Двойственные задачи линейного программирования

Сентябрь 3, 2022

Главная
Алгебра
Двойственные задачи линейного программирования

Содержание

2. Первая (основная) теорема двойственности Теорема: Если одна из сопряженных задач имеет оптимальное решение, то и вторая
3. Вторая теорема двойственности Теорема: Для того чтобы два допустимых решения и пары двойственных задач были их
4. Правила построения двойственных задач: 1. Если в исходной задаче целевая функция исследуется на min, то в
5. 4. Матрица ограничений двойственной задачи получается из матрицы ограничений исходной задачи транспонированием. 5. Если в исходной
6. Пара симметричных двойственных задач Пары сопряженных переменных Основные Дополнительные Дополнительные Основные
7. Важно знать Объективно обусловленные оценки ресурсов определяют степень дефицитности ресурсов: по оптимальному плану производства дефицитные (т.е.
8. Пара симметричных двойственных задач Пары сопряженных переменных Основные Дополнительные Дополнительные Основные
9. Экономический смысл основной теоремы двойственности План производства и набор цен ресурсов оказываются оптимальными тогда и только
10. Исследование на устойчивость Исследование на устойчивость – исследование диапазона изменения правых частей системы ограничений, при котором
12. Скачать презентацию

Слайд 2

Первая (основная) теорема двойственности
Теорема: Если одна из сопряженных задач имеет

оптимальное решение, то и вторая имеет оптимальное решение, при этом
Fmax = Zmin или F(X*) = Z(Y*).
Если линейная функция одной из задач не ограничена, то условия другой задачи противоречивы.
Пример:

F = 2 х1 + 3 х2 ? max
при ограничениях:
х1 + 3х2 <= 18
2х1 + х2 <= 16
х2 <= 5
3x1 <= 21
х1, х2 >= 0
F max = 24

Z =18y1 + 16y2 +5y3 + 21y4 ? min при ограничениях:
y1 + 2 y2 + 3 y4 >= 2
3 y1 + y2 + y3 >= 3
y1, y2, y3, y4 >= 0
Z min = 24

Х* = (х1*, х2*, …,хn*)

Y* = (y1*, y2*, …, ym*)

Слайд 3

Вторая теорема двойственности
Теорема: Для того чтобы два допустимых решения и

пары двойственных задач были их оптимальными решениями необходимо и достаточно, чтобы они удовлетворяли системе уравнений

(1)

Соответствие между первоначальными переменными одной из двойственных задач и дополнительными переменными другой задачи:

Слайд 4

Правила построения двойственных задач:
1. Если в исходной задаче целевая функция исследуется

на min, то в двойственной задаче она будет исследоваться на max и наоборот.
2. Если в исходной задаче n переменных и m уравнений, то в двойственной задаче будет m переменных и n уравнений.
3. Коэффициенты целевой функции исходной задачи становятся правыми частями ограничений двойственной задачи, а правые части системы ограничений исходной задачи становятся коэффициентами целевой функции исходной задачи.

Слайд 5

4. Матрица ограничений двойственной задачи получается из матрицы ограничений исходной

задачи транспонированием.
5. Если в исходной задаче то в двойственной задаче k-ое ограничение будет неравенством, если же в исходной задаче не имело ограничений на знак, то k-ое ограничение в двойственной задаче будет равенством.
6. Если в исходной задаче l-ое ограничение - неравенство, то в двойственной задаче ; если же в исходной задаче l-ое ограничение - равенство, то в двойственной задаче нет ограничений на знак yi.

Слайд 6

Пара симметричных двойственных задач

Пары сопряженных переменных
Основные Дополнительные
Дополнительные

Основные

Слайд 7

Важно знать
Объективно обусловленные оценки ресурсов определяют степень дефицитности ресурсов: по оптимальному

плану производства дефицитные (т.е. полностью использованные) ресурсы получают ненулевые оценки, а недефицитные – нулевые оценки.
Положительным (ненулевым) компонентам оптимального решения одной из взаимно двойственных задач соответствуют нулевые компоненты оптимального решения другой задачи.

Слайд 8

Пара симметричных двойственных задач

Пары сопряженных переменных
Основные Дополнительные
Дополнительные

Основные

Слайд 9

Экономический смысл основной теоремы двойственности
План производства
и набор цен

ресурсов

оказываются оптимальными тогда и только тогда, когда прибыль (выручка) от продукции, найденная при “внешних”(известных заранее) ценах

,равна затратам на ресурсы при “внутренних” (определяемым только из решения задачи) ценах

Для всех других планов X и Y обеих задач прибыль (выручка) от продукции всегда меньше (или равна) затратам на ресурсы.

Слайд 10

Исследование на устойчивость
Исследование на устойчивость – исследование диапазона изменения правых частей

системы ограничений, при котором найденное оптимальное решение не изменяется.
Исследование на чувствительность
При исследовании на чувствительность исследуется зависимость решения линейного программирования от небольших изменений коэффициентов в условии задачи. При этом предыдущее решение может стать либо недопустимым, либо неоптимальным.
К недопустимости пред. решения могут привести изменения запасов ресурсов и/или добавление новых ограничений.
К неоптимальности пред. решения могут привести изменение целевой функции и/или изменение технологических коэффициентов и/или включение в модель нового вида производственной деятельности.

Двойственные задачи линейного программирования

Содержание

Первая (основная) теорема двойственности Теорема: Если одна из сопряженных задач имеет

Вторая теорема двойственности Теорема: Для того чтобы два допустимых решения и

Правила построения двойственных задач:1. Если в исходной задаче целевая функция исследуется

4. Матрица ограничений двойственной задачи получается из матрицы ограничений исходной

Пара симметричных двойственных задач Пары сопряженных переменных Основные Дополнительные Дополнительные

Важно знать Объективно обусловленные оценки ресурсов определяют степень дефицитности ресурсов: по оптимальному

Пара симметричных двойственных задач Пары сопряженных переменных Основные Дополнительные Дополнительные

Экономический смысл основной теоремы двойственности План производства и набор цен

Исследование на устойчивостьИсследование на устойчивость – исследование диапазона изменения правых частей

Похожие презентации

Первая (основная) теорема двойственности
Теорема: Если одна из сопряженных задач имеет

Вторая теорема двойственности
Теорема: Для того чтобы два допустимых решения и

Правила построения двойственных задач:
1. Если в исходной задаче целевая функция исследуется

Пара симметричных двойственных задач

Пары сопряженных переменных
Основные Дополнительные
Дополнительные

Важно знать
Объективно обусловленные оценки ресурсов определяют степень дефицитности ресурсов: по оптимальному

Пара симметричных двойственных задач

Пары сопряженных переменных
Основные Дополнительные
Дополнительные

Экономический смысл основной теоремы двойственности
План производства
и набор цен

Исследование на устойчивость
Исследование на устойчивость – исследование диапазона изменения правых частей