Линейные и нелинейные модели в экономике

    Теорема об оценках.

    Значения  переменных Y_i в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов bi системы ограничений-неравенств прямой задачи на величину

    Решая ЗЛП  симплексным методом, мы одновременно решаем двойственную ЗЛП. Переменные двойственной задачи yi называют объективно обусловленными оценками.

    Рассмотрим  экономическую интерпретацию двойственной задачи на примере задачи оптимального использования ресурсов.

5. Области допустимых решений  для двойственных переменных

    Вид ограничений прямой задачи, а также  дополнительные и искусственные  переменные, образующие начальный допустимый базис, определяют ОДР для соответствующих  двойственных переменных.

    1. Рассмотрим ограничение (2) прямой  задачи:

     Область допустимых решений ДП ( ) определяется знаками ограничений (8) и (9) двойственной задачи и знаком ограничения (2) прямой задачи. Для определения ОДР найдём ограничения ДЗ, соответствующие остаточным переменным ПЗ. Коэффициенты целевой функции для остаточных переменных равны нулю ( ).Т. о., при решении задачи максимизации ограничениям прямой задачи, имеющим знак ограничения , соответствуют неотрицательные двойственные переменные: .

    2. Рассмотрим ограничение (3) прямой  задачи:

     .

    При введении искусственных переменных в целевую функцию вводятся коэффициенты штрафа М, поэтому для задачи максимизации получим:

2. .

    Т. о., при решении задачи максимизации ограничениям прямой задачи, имеющим  знак равенства, соответствуют двойственные переменные, не ограниченные в знаке  .

    3. Рассмотрим ограничение (4) прямой  задачи:

    В целевой функции избыточные переменные имеют коэффициенты, равные нулю ( ), а искусственные переменные коэффициенты, равные величине штрафа со своим знаком, в результате для задачи максимизации получим:

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

    4. Если в прямой задаче есть  переменная, неограниченная в знаке,  то в двойственной задаче получатся  два ограничения, имеющие одинаковые  коэффициенты при двойственных  переменных, но разные знаки ограничений. Для удобства решения эти ограничения сворачивают в одно со знаком равенства (тем самым число ограничений двойственной задачи сводится к числу исходных переменных прямой задачи).

    По  аналогии можно записать условия  двойственной задачи при решении  задачи минимизации. Для удобства пользования  некоторые соотношения при переходе от прямой задаче к двойственной приведены  в таблице.

    Таблица 1.1 Переход от прямой задачи к двойственной

    В двойственной задаче переменные могут  быть неотрицательными ( ), не ограниченными в знаке ( ), неположительными ( ). При решении ДЗ, как и ПЗ должны выполняться условия неотрицательности ограничений и переменных. Для представления двойственной задачи в стандартной форме используются следующие подстановки:

если  переменная не ограничена в знаке, то ;

если  , то .

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

    После приведения ДЗ к стандартному виду используется симплекс - метод. Алгоритм получения решения тот же, что  и для прямой задачи.