Экономические свойства двойственных оценок

Двойственная задача линейного программирования

ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

ОПТИМАЛЬНЫХ РЕШЕНИЙ ЗАДАЧ

Лекция4. ЭКОНОМИКО-МАТЕМАТИЧЕСКИЙ АНАЛИЗ

1. Двойственная задача линейного программирования

2. Экономические свойства двойственных оценок

3. Анализ оптимального решения по последней симплексной таблице

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

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

Прямая задача может быть записана следующим образом:

(1)

(2)

(3)

Переменные двойственной задачи y_i называют объективно обусловленными оценками, или двойственными оценками. Модель двойственной задачи имеет вид:

(4)

(5)

(6)

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

Двойственная по отношению к исходной задача составляется по следующим правилам:

1) Целевая функция исходной задачи (1) формулируется на максимум, а целевая функция двойственной задачи (4) – на минимум. В задаче на максимум все неравенства в функциональных ограничениях имеют вид , а в задаче на минимум – вид .

2) Матрица ,

составлена из коэффициентов при неизвестных в системе ограничений исходной задачи (2), аналогичная матрица в двойственной задаче получается транспортированием:

.

3) Число переменных в двойственной задаче равно числу функциональных ограничений исходной задачи (2), а число ограничений в системе двойственной задачи (5) – числу переменных в исходной задаче.

4) Коэффициентами при неизвестных в целевой функции двойственной задачи (4) являются свободные члены в системе ограничений исходной задачи (2), а правыми частями в ограничениях двойственной задачи (5) – коэффициенты при неизвестных в целевой функции исходной задачи (1).

5) Каждому ограничению одной задачи соответствует переменная другой задачи: номер переменной совпадает с номером ограничения. При этом ограничению, записанному в виде неравенства , соответствует переменная, связанная условием неотрицательности. Если функциональное ограничение исходной задачи является равенством, то соответствующая переменная двойственной задачи может принимать как положительные, так и отрицательные значения.

В несимметричных двойственных задачах система ограничений исходной задачи задается в виде равенств, а двойственной – в виде неравенств, причем в последней переменные могут быть и отрицательными. В симметричных задачах система ограничений как исходной, так и двойственной задачи задается неравенствами, причем на двойственные переменные налагается условие неотрицательности.

Первая теорема двойственности утверждает:

1. Если прямая и двойственная задачи имеют оптимальные решения, то значения целевых функций в их оптимальных планах совпадают: max f() = min g().

2. Если прямая задача имеет допустимые решения, а ее целевая функция не ограничена сверху, то двойственная задача не имеет допустимых планов.

3. Если двойственная задача имеет допустимые решения, а целевая функция не ограничена снизу, то прямая задача не имеет допустимых решений.

4. Обе из рассматриваемых задач не имеют допустимых решений.

Вторая теорема двойственности утверждает правила дополняющей нежесткости. Пусть = (x_l,x₂,...,x_n) – допустимое решение прямой задачи (1)-(3), а = (y₁, y₂,...,y_m) – допустимое решение двойственной задачи (4)-(6). Для того чтобы они были оптимальными решениями соответствующих взаимодвойственных задач (1)-(3) и (4)-(6), необходимо и достаточно, чтобы выполнялись следующие соотношения:

, (7)

. (8)

Условия (7) и (8) позволяют по данным оптимального решения одной из взаимодвойственных задач найти оптимальное решение другой задачи.

Конкретными экономическими свойствами оценок y_i оптимального плана является:

Свойство 1. Оценки как мера дефицитности ресурсов и продукции.

Свойство 2. Оценки как мера влияния ограничений на функционал.

Свойство 3. Оценки как инструмент определения эффективности отдельных вариантов.

Свойство 4. Оценки как инструмент балансирования суммарных затрат и результатов.

Экономическое истолкование оценок есть интерпретация их общих экономико-математических свойств применительно к конкретному содержанию задачи. Не использованный полностью в оптимальном плане ресурс получает нулевую оценку. Нулевая оценка ресурса свидетельствует о его недефицитности. Ресурс недефицитен не из-за его неограниченных запасов (они ограничены величиной b_i), а из-за невозможности его полного использования в оптимальном плане. Так как суммарный расход недефицитного ресурса меньше его общего количества, то план производства им не лимитируется. Данный ресурс не препятствует и дальше максимизировать целевую функцию f().

Ограничивают целевую функцию дефицитные ресурсы. В рассматриваемой сельскохозяйственной задаче – пашня и механизированные работы. Они полностью использованы в оптимальном плане. Оценка таких ресурсов положительна (у₁ =1; y₃ =0,75). Трудовые ресурсы имеют нулевую оценку (у₂=0), они недефицитны.

Оценка ресурса показывает, на сколько изменится критерий оптимальности при изменении количества данного ресурса на единицу. Для

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

Если в хозяйстве будет возможность приобрести дополнительно 1 га пашни, то при его использовании стоимость продукции возрастет на 1 тыс. руб. Увеличение механизированных работ на 1 усл. га позволит произвести дополнительно продукции на 750 руб. Величина двойственных оценок в данном случае может служить предельной ценой, которая приемлема при покупке ресурсов.

Двойственные оценки могут быть использованы для определения эффективности производства других видов продукции, которые не входили в условия задачи. Например, если производство картофеля требует в расчете на 1 га посадки: 1 га пашни, 100 чел. – дн., 10 усл. га, то стоимость реализованной с 1 га продукции для целесообразности возделывания этой культуры должно быть не менее: тыс. руб.

Дата добавления: 2014-01-05