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

L*: ~ ~ ~

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

~~~

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

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

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

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

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

~ ~ ~

~ ~ ~

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

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

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

Следствия:

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

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

3. Если , то

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

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

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

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

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

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

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

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

1. Если

2. Если

3. Если

4. Если

Экономическая интерпретация условия оптимальности

1. Если оптимальная двойственная оценка i-го ресурса положительна, то при работе по оптимальному плану ресурс используется полностью

2. Если при работе по оптимальному плану i-ый ресурс используется не полностью, то оптимальная двойственная оценка = 0 (не влияет на решение)

3. Если при работе по оптимальному плану j-ая технология используется, то эта технология не убыточна в ценах(сколько затратили, столько получили)

4. Если в ценах j-ая технология убыточна, то при работе по оптимальному плану она не используется.

Алгоритм применения условия оптимальности при решении задач лп

Дан n-мерный вектори задача ЛП (L). С помощью условия оптимальности определить, будет ли данный вектор оптимален в задаче (L).

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

2. Определить вид множества U– ограничения двойственной задачи

3. Написать условие дополняющей нежесткости с подстановкой . Получим систему линейных алгебраических уравнений для определения.

4. Решаем эту систему, находим .

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

6. Если да (принадлежит), то – оптимальный в задачеL, если нет (не принадлежит) тоне оптимальный в задачеL.

16. Свойства закрытой транспортной модели.

Транспортная задача:

Задача называется закрытой (замкнутой), если выполняется условие баланса:

– необходимое и достаточное условие решения задачи

,

, состоит из столбцов, каждый из которых содержит всего две единички:

i

m+j

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

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

Если задача незамкнута

1. – есть избыток продукции

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

2. – есть дефицит продукции, всем не хватит.

В этом случае определяют меру штрафа r_jза недоставкуj-му потребителю единицы продукции. Затраты увеличиваются

И вводят фиктивного производителя. Тарифы на перевозку от введенного производителя устанавливаются равной мере штрафа

Если предпочтений нет, то штрафы можно установить нулевыми (r_j= 0)

17. Модели транспортного типа.