Двойственные модели ЛП, их экономическая интерпретация

Рассмотрим задачу L планирования производства (1-ый вариант).

Скалярная форма	Матричная форма	Векторная форма

m ресурсов.

b_i – объем i-го ресурса
n технологий
а_ij – затраты i-го ресурса при использовании j-ой технологии в единицу времени
c_j – получаемая ценность при использовании j-ой технологии в единицу времени

x_j – время работы j-ой технологии.

x = (x₁, …, x_n)

Оценим ценность затраченную и полученную в единицу времени

u_i – ценность единицы i-го ресурса

Скалярная форма	Матричная форма	Векторная форма

Δ – потери

x – план производства

L*– двойственная задача к задаче L

Скалярная форма	Матричная форма	Векторная форма

Двойственная задача возникает как задача минимизации потерь ценности в производстве, при условии, что само производство функционирует оптимальным образом, то есть в соответствии с оптимальным планом задачи L.

Правила построения двойственных моделей.

	L		L*
1.	Задача на max		Задача на min
2.	Матрица условий A		Матрица условий AT
3.	m ограничений n переменных		n ограничений m переменных
4.	с – вектор цели b – вектор ограничений		b – вектор цели c – вектор ограничений
5.	Ограничение ≤		Ограничение ≥
6.	x ≥ 0		y ≥ 0

Двойственная у двойственной

L*: ~ ~ ~

Переходим к двойственной

~ ~ ~

Теорема: двойственная задача для двойственной совпадает с исходной.

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

	Прямая		Двойственная
1.
2.
3.
4.

Для 3 и 4 если в исходной ограничения =, то в двойственной переменные свободные и наоборот, если в исходной переменные свободные, то в двойственной ограничения =.

Как получили 3:

~ ~ ~

~ ~ ~

Теоремы двойственности в ЛП.

Слабая теорема двойственности

–целевая функция двойственной задачи ≥ целевой функции исходной задачи.

Следствия:

1) Если , то – решение исходной (L), – решение двойственной (L*)

2) Если и , то (L) и (L*) имеют решение

3) Если , то

Если в двойственной , то

Сильная теорема двойственности

Если разрешима одна из двух задач (L) или (L*), то разрешима и другая и их оптимальные значения совпадают.

Условия оптимальности в ЛП и их экономический смысл.

L – стандартная задача, L* – двойственная задача.

Вектор оптимален в (L) ó

– условие оптимальности

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

1) Если

2) Если

3) Если

4) Если