Прямая и двойственная задача линейного программирования. Лекция 5

1. Лекция 5 Прямая и двойственная задача линейного программирования

Вопрос 1. Определение двойственной задачи
Вопрос 2. Связь между решениями прямой и
двойственной задачи

2. Определение двойственной задачи

Вопрос 1. Определение двойственной задачи
Определение двойственной задачи
Каждой задаче линейного программирования
можно определенным образом сопоставить
некоторую другую задачу ЛП называемую
двойственной или сопряженной по отношению
к исходной или прямой задаче
(1).
При условии
(2):

3. Определение

Вопрос 1. Определение двойственной задачи
Определение
Задача, состоявшая в нахождении минимального значения
функции
(3)
при условиях
(4)
называется двойственной по отношению к задаче (1)-(2).
Задачи (1)-(2) и (3)-(4) двойственную пару задач.
Двойственные задачи получаются друг из друга
транспонированием, при этом значение оптимума
целевой функции меняется на противоположный.

4. Правила составления двойственной задачи

Вопрос 1. Определение двойственной задачи
Правила составления двойственной задачи
1.
2.
3.
Целевая функция исходной задачи (1)-(2) задается на
максимум, а целевая функция двойственной (3)-(4) – на
минимум.
Матрица составленная из коэффициентов при неизвестных в
системе ограничений (2) исходной задачи (1)-(2), и
аналогичная матрица в двойственной задаче (3)-(4)
получаются друг из друга транспонированием.
Число переменных в двойственной задаче (3)-(4) равно числу
ограничений системы (2) исходной задачи (1)-(2), а число
ограничений в системе (4) двойственной задачи- числу
переменных в исходной задаче.

5. Правила составления двойственной задачи (продолжение)

Вопрос 1. Определение двойственной задачи
Правила составления двойственной задачи (продолжение)
4.
5.
Коэффициентами при неизвестных в целевой функции (3)
двойственной задачи (3)-(4) являются свободные члены в
системе (2) исходной задачи (1)-(2),
а правыми частями в соотношениях системы (4) двойственной
задачи – коэффициенты при неизвестных в целевой функции
(1) исходной задачи.
Если переменная xj исходной задачи (1)-(2) может принимать
только лишь положительные значения, то j–е условие
в системе (4) двойственной задачи (3)-(4) является
неравенством вида xj >0.
Если же переменная xj может принимать как положительные,
так и отрицательные значения, то c1-е соотношения в системе
(34) представляет собой уравнение.

6. Двойственные пары задач подразделяются на

Вопрос 1. Определение двойственной задачи
Двойственные пары задач подразделяются на
Симметричные
Ограничения (2) прямой
задачи и соотношения (4)
двойственной задачи
являются неравенствами
вида “<”.
Таким
образом,
переменные обеих задач
могут принимать только
лишь
неотрицательные
значения.
Несимметричные

7.

Вопрос 2. Связь между решениями прямой и двойственной задачи
Рассмотрим пару двойственных задач, образованную
основной задачей линейного программирования и
двойственной к ней.
Исходная задача: найти максимум функции
(5)
при условии
(6)
(7)
Двойственная задача – найти минимум функции
(8) ,
(9)

8.

Вопрос 2. Связь между решениями прямой и двойственной задачи

9. Теорема двойственности

Вопрос 2. Связь между решениями прямой и двойственной задачи
Теорема двойственности
Лемма 1. Если Х – некоторый план исходной задачи (5) – (7), a Y
– произвольный план двойственной задачи (6), (9), то значение
целевой функции исходной задачи при плане Х всегда не
превосходит значения целевой функции двойственной задачи
при плане Y, т. е.
Лемма 2. Если для некоторых планов X* и Y* задач (5) – (7) и
(8), (9), то X* – оптимальный план исходной задачи, а Y* –
оптимальный план двойственной задачи.
Первая теорема двойственности. Если одна из задач
двойственной пары (5) – (7) или (8), (9) имеет оптимальный
план, то и другая имеет оптимальный план и значения целевых
функций задач при их оптимальных планах равны между собой,
т. е.
Если же целевая функция одной задачи из двойственной пары
неограничена (для исходной (5) – (7) – сверху, для двойственной
(8), (9) – снизу), то другая задача вообще не имеет планов.
Вторая теорема двойственности. План задачи (5) – (7) и план
задачи (8), (9) являются оптимальными планами этих задач
тогда и только тогда, когда для любого выполняется равенство

10. Геометрическая интерпретация двойственных задач

Вопрос 2. Связь между решениями прямой и двойственной задачи
Геометрическая интерпретация
двойственных задач
1.
2.
3.
При этом имеет место один из
следующих трех взаимно исключающих
друг друга случаев:
обе задачи имеют планы;
планы имеет только одна задача;
для каждой задачи двойственной пары
множество планов пусто.