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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

,

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

m+j

i

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

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

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

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

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

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

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

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

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

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