Теорема равновесия

Задача 2
Составить двойственную задачу к задаче 1. Найти ее решение по теореме равновесия.

Теорема равновесия. Пусть и - допустимые планы пары двойственных задач в симметричной форме. Эти планы являются оптимальными тогда и только тогда, когда выполняются следующие условия дополняющей нежесткости:


Теорема 4 позволяет определить оптимальное решение одной из пары двойственных задач по решению другой. Если ограничение одной задачи при подстановке оптимального решения обращается в строгое неравенство, то соответствующая двойственная переменная в оптимальном решении двойственной задачи равна 0. Если в оптимальном плане одной задачи какая-нибудь переменная положительна, то соответствующее ей ограничение двойственной задачи является уравнением.
Дадим экономическую интерпретацию условиям дополняющей нежесткости. Если в оптимальном решении какое-нибудь сырье имеет отличную от 0 оценку, то оно будет израсходовано полностью (ресурс является дефицитным). Если сырье расходуется не полностью (находится в избытке), то его оценка равна 0. Таким образом, получаем, что двойственные оценки – это мера дефицитности сырья. Оценка показывает, на сколько возрастет значение целевой функции при увеличении запаса соответствующего сырья на 1 ед. Если некоторый вид продукции входит в план производства, то затраты на его производство совпадают со стоимостью произведенной продукции. Если затраты на производство какого-нибудь вида продукции больше стоимости продукции, то продукция не производится.
В случае если одна из пары двойственных задач содержит две переменных, ее можно решить графически, а, затем, найти решение двойственной задачи, используя Теоремы 3 и 4. При этом могут возникнуть 3 случая: обе задачи имеют допустимые решения, допустимые решения имеет только одна задача, обе задачи не имеют допустимых решений.

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

, если известно решение исходной задачи: .
Построим двойственную задачу. Согласуем знаки неравенств с целью исходной задачи.


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


Найдем оптимальное решение двойственной задачи по теореме равновесия. Запишем условия дополняющей нежесткости.

Подставим в составленную систему оптимальное решение исходной задачи: .


Произведение равно нулю, если один из множителей равен 0. Получаем

Тогда,

Оптимальное решение двойственной задачи По Теореме 3 . Окончательно,.

Пример 3
Составить двойственную задачу к задаче из примера раздела 1.5 и найти ее решение по теореме равновесия


В разделе 1.5 было найдено решение исходной задачи средствами MS Excel:

Составим двойственную задачу. Знаки неравенств уже согласованы с целью задачи.


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


Найдем оптимальное решение двойственной задачи по теореме равновесия. Запишем условия дополняющей нежесткости.

Подставим в составленную систему оптимальное решение исходной задачи: .

Произведение равно нулю, если один из множителей равен 0. Получаем

Тогда,


Вычтем из первого уравнения второе:
Þ

Оптимальное решение двойственной задачи По Теореме 3 .
Окончательно,

загрузка...