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

Рассмотрим задачу 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) Если