Использование двойственных оценок для экономико-математического моделирования

Использование двойственных оценок для экономико-математического  анализа.

Пусть  мы  имеем следующую задачу линейного  программирования на максимум, называемую исходной (или прямой):

(с,х)→ max           (1)

при условиях                

Ах≤Ь                (2)   

х³0.                 (3)

Это задача записана в стандартной  форме. Двойственная задача представляет собой следующую задачу на минимум:

(b,y)→ min          (4)

при условиях                

А^Ty≥c                (5)

y³0,                 (6)

где (y₁,y₂,…,y_m) - вектор неизвестных размерности m, A^T - матрица, транспонированная к матрице А прямой задачи.

Двойственная  задача является также задачей линейного  программирования, число неизвестных  у нее равно числу ограничений  исходной задачи. Задачи (1)-(3) и (4)-(6) называются симметричными двойственными задачами.

 Они обладают  следующими свойствами:

1. В одной  задаче ищут максимум линейной  функции,  в другой – минимум.

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

3. Каждая из  задач задана в стандартной  форме, причем в задаче максимизации все неравенства вида «≤», а в задаче минимизации все неравенства вида «≥».

4. Матрицы коэффициентов  при переменных обеих задач  являются транспонированными друг к другу.

5. Число неравенств  в системе ограничений одной  задачи совпадает с числом  переменных в другой задаче.

6. Условия не  отрицательности переменных имеются  в обеих задачах.

 

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

Исходная:

Определить  вектор х, минимизирующий функцию (с,х) при условиях Ах=Ь, х≥0.

Двойственная:

Определить  вектор yÎR^m,  максимизирующий функцию g=(b,y) при условии A^Ty≤c. На знаки компонент y_i ограничения не накладываются.

Аналогично для задачи на максимум двойственная задача имеет вид: определить вектор yÎR^m,  минимизирующий функцию g=(b,y) при условии A^Ty≥c.

 

Симметричные двойственные задачи легко приводятся к записи в виде несимметричных задач. Действительно, введя uÎR^m, запишем исходную задачу в виде: определить х,u, доставляющие min (c, х) при условиях Ах-Еu=b, х≥О,  u≥О.

Тогда двойственная задача запишется так:

определить yÎR^m,  доставляющий max g=(b,y) при  условиях  A^Ty≤c, y≥0.

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

Если из двух задач-исходной и двойственной одна имеет оптимальное решение, то и другая имеет решение, причем:

Max(c,x)=(c,x^*)=(y^*,b)=Min(y,b).

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

Продемонстрируем экономическую интерпретацию результатов теории двойственности для задачи составления плана производства, описанной в лекции . Суть ее состоит в нахождении таких объемов выпуска n видов продукции, для производства которых затрачиваются m видов ресурсов в объемах, не превосходящих имеющихся запасов и при этом выручка от реализации продукции должна быть максимальной. Экономико-математическая модель этой задачи представляет собой задачу линейного программирования:

(с,х)→ max    

при ограничениях на использование ресурсов              

Ах≤Ь

х³0.

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

(b,y)→ min  

при условиях                

А^Ty≥c

y³0,

Так как по теореме  двойственности  , то естественно считать, что размерность (единицы измерения) у целевых функций одинаковы. В исходной задаче целевая функция представляет собой стоимостное выражение выручки от реализации, значит, в двойственной задаче так же есть стоимость. Так как компоненты вектора b суть объемы наличных ресурсов в натуральном выражении, то естественно считать, что компоненты вектора y^* в некотором смысле цены этих ресурсов. В литературе двойственные переменные называют по-разному: двойственными оценками, объективно обусловленными оценками, стоимостными оценками ресурсов.

Условие равенства  значений целевых функций в точке  оптимума означает, что, если на ресурсы установлены цены y^*, то производству с точки зрения дохода безразлично: произвести продукцию и реализовать ее по ценам С, или реализовать ресурсы по ценам y^*.

Предположим, что  для некоторого ресурса i его двойственная оценка в оптимальном плане больше нуля (y_i^*>0). Cоответствующее ограничение исходной задачи выполняется как точное равенство: . Другими словами, для выпуска оптимального плана производства продукции данный ресурс используется полностью и в этом смысле для производства он дефицитен. Наоборот, если какое-то ограничение-неравенство исходной задачи в оптимальном плане выполняется как строгое неравенство  , то есть не весь ресурс используется и он недефицитен, то соответствующая двойственная оценка равна нулю (y_i^*=0).

Таким образом, двойственные оценки характеризуют  ресурсы с точки зрения их степени дефицитности для данной задачи.

если некоторый j-й продукт в оптимальной производственной программе производится, то есть , то соответствующее ограничение-неравенство двойственной задачи выполняется как точное равенство где сумма соответствует стоимости всех ресурсов, используемых на производство единицы продукции вида j, вычисленную в ценах y_i^*. Таким образом, для ненулевых выпусков продукции затраты на их производство равны ценам реализации, то есть имеет место равновесие и этот продукт производится в количестве . Если затраты на выпуск продукции превышают цену реализации, то такой продукт не выпускается.

Рассмотрим еще один экономический  аспект теории двойственности, отвечающий на вопрос: может ли увеличение количества ресурсов привести к росту выручки. Другими словами, если запас i-го ресурса увеличить на величину , то как изменится величина . Согласно теории двойственности .

 

 

 

 

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

Двойственные оценки можно также использовать для  определения эффективности введения в модель новой переменной x_n+1 (например, нового продукта). При этом задается коэффициент целевой функции c_n+1 и вектор коэффициентов A_n+1. Пусть y* -вектор двойственных оценок исходной задачи. Тогда можно вычислить приведенную оценку A_n+1:  c_n+1 –у* A_n+1  (это доказано в теореме двойственности). Если она положительна, то (в задаче на максимум) введение новой переменной приведет к увеличению целевой функции, если неположительна, то данная переменная не будет входить в оптимальное решение, не улучшит его.