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

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

некоторую другую задачу ЛП называемую двойственной или сопряженной по отношению

к исходной или прямой задаче
(1).

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

При условии (2):

отношению к задаче (1)-(2).
Задачи (1)-(2) и (3)-(4) двойственную пару задач.
Двойственные

задачи получаются друг из друга транспонированием, при этом значение оптимума целевой функции меняется на противоположный.

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

максимум, а целевая функция двойственной (3)-(4) – на минимум.
Матрица составленная

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




Число переменных в двойственной задаче (3)-(4) равно числу ограничений системы (2) исходной задачи (1)-(2), а число ограничений в системе (4) двойственной задачи- числу переменных в исходной задаче.

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

(3) двойственной задачи (3)-(4) являются свободные члены в системе (2)

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

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

(4) двойственной задачи являются неравенствами вида “

обеих задач могут принимать только лишь неотрицательные значения.

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

Несимметричные

двойственной к ней. Исходная задача: найти максимум функции

(5)

при условии
(6)
(7)

Двойственная задача

– найти минимум функции

(8) , (9)

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

(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) являются оптимальными планами этих задач тогда и только тогда, когда для любого выполняется равенство

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

следующих трех взаимно исключающих друг друга случаев:
обе задачи имеют

планы;
планы имеет только одна задача;
для каждой задачи двойственной пары множество планов пусто.

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