Математическая теория двойственности и применение её в экономическом анализе

y₂ > 0,

(-y₁) + 2y₂ >(-1),

y₁ – y₂ + y₃ = -3, y₃ > 0

Оптимальный план исходной задачи X = (0; 1/3; 0; 11/3; 4; 0), при котором получим Z_min= -46/3. Используя эту итерацию, найдем оптимальный план двойственной задачи. Согласно теореме двойственности оптимальный план двойственной задачи находится из соотношения Y= C*D^-1, где матрица D^-1 - матрица, обратная матрице, составленной из компонент векторов, входящих в последний базис, при котором получен оптимальный план исходной задачи. В последний базис входят векторы A_5, A_4, A_2; значит,

1 -1 2

D = (A _5, A _4, A ₂₎ = -1 2 -4

1 0 3

Обратная матрица D ^-1 образована из коэффициентов, стоящих в столбцах A₁, A₃, A₆ четвертой итерации:

2 1 0

D ^{-1 =} -1/3 1/3 2/3

-2/3 -1/3 1/3

Из этой же итерации следует С = (–3; –1; 1). Таким образом

2 1 0

Y=С*D^-1 =(-3; – 1; 1) -1/3 1/3 2/3

-2/3 1/3 1/3

Y=(-19/3; – 11/3; – 1/3),

т.е. y_i =С*Х_i, где Х_i – коэффициенты разложения последней итерации, стоящие в столбцах векторов первоначального единичного базиса.

Итак, i-ю двойственную переменную можно получить из значения оценки (m+1) – й строки, стоящей против соответствующего вектора, входившего в первоначальный единичный базис, если к ней прибавить соответствующее значение коэффициента линейной функции:

у₁ =–19/3+0=–19/3; y₂ =-11/3+0=-11/3; у₃ =-1/3+0=-1/3

При этом плане maxf=-46/3

 

1.2.2 Симметричные двойственные  задачи

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

Исходная задача. Найти  матрицу-столбец Х=(x₁, x₂,…, x_n), которая удовлетворяет системе ограничений

 

(1.12). АХ>А₀, Х>0 и минимизирует линейную функцию Z=СХ

 

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

Используя симметричность, можно выбрать задачу, более удобную  для решения. Объем задачи, решаемой с помощью ЭВМ, ограничен числом включаемых строк, поэтому задача, довольно громоздкая в исходной постановке, может быть упрощена в двойственной формулировке. При вычислениях без помощи машин использование двойственности упрощает вычисления.

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

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

Пример 1. (Задача оптимального использования ресурсов).

Пусть для выпуска  четырех видов продукции P1, P2, Р3, Р4 на предприятии используют три вида сырья Si, S2 и S3. Объемы выделенного сырья, нормы расхода сырья и прибыль на единицу продукции при изготовлении каждого вида продукции приведены в табл. 3.1. Требуется определить план выпуска продукции, обеспечивающий наибольшую прибыль.

Составим экономико-математическую модель задачи оптимального использования  ресурсов на максимум прибыли. В качестве неизвестных примем объем выпуска  продукции j-го вида Xj (j = 1,2,3,4).

Таблица 3.1

Вид сырья	Запасы  сырья	Вид продукции
		Р1			Р2				Р3	Р4
S1 S2 S3	35 30 40		4 1 3			2 1 1			2 2 2		3 3 1
Прибыль				14			10	14			11

 

 

 

Модель задачи f(Х)=14х₁ + 10х₂ + 14х₃ + 11х₄ ®max

                                   4x₁ + 2х₂ + 2х3 + 3х₄ £35

                                    х₁ + х₂ + 2х₃ + 3х₄ £ 30

                                   3х₁ + х₂+ 2х₃ + х₄ £40

                                    х_j³ 0, j= 1, 2, 3, 4.

Теперь сформулируем двойственную задачу. Пусть некая  организация решила закупить все  ресурсы рассматриваемого предприятия. При этом необходимо установить оптимальную цену на приобретаемые ресурсы y₁,у₂,у₃ исходя из следующих объективных условий:

1) покупающая организация старается  минимизировать общую стоимость  ресурсов;

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

Согласно первому  условию общая стоимость сырья  выразится величиной g(Y) = 35у₁ + 30у₂ + 40у₃ ® min. Согласно второму требованию вводятся ограничения: на единицу первого вида продукции расходуются четыре единицы первого ресурса ценой у₁, одна единица второго ресурса ценой у₂ и три единицы третьего ресурса ценой у₃- Стоимость всех ресурсов, расходуемых на производство единицы первого вида продукции, равна 4y₁ + у₂ + 3у₃ и должна составлять не менее 14, т. е. 4у₁ + у₂ + Зу₃ ³ 14.

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

4y₁ + у₂ + 3у₃ ³ 14,

2y₁ + y₂ + y₃ ³ 10,

2y₁ + 2у₂ + 2у₃ ³ 14,

3y₁ + 3у₂ + у₃ ³ 11.

По экономическому смыслу цены неотрицательные:

у₁ > 0 , у₂ > 0 , у₃ > 0 .

Получили симметричную пару взаимодвойственных задач. В результате решения данной задачи симплексным  методом получен оптимальный  план X = (0;5;12,5;0); Y = (3;4;0).

 

Экономический смысл первой теоремы двойственности следующий. План производства X и набор оценок ресурсов Y оказываются оптимальными тогда и только тогда, когда прибыль от реализации продукции, определенная при известных заранее ценах продукции с1, с2, ...сn, равна затратам на ресурсы по «внутренним» (определяемым только из решения задачи) ценам ресурсов y1, y2 ,...ym. Для всех же других планов X и Y обеих задач прибыль от продукции всегда меньше (или равна) стоимости затраченных ресурсов: f(X) < g(Y) , т. е. ценность всей выпущенной продукции не превосходит суммарной оценки имеющихся ресурсов. Значит величина g(Y) - f(X) характеризует производственные потери в зависимости от рассматриваемой производственной программы и выбранных оценок ресурсов. Из первой теоремы двойственности следует, что при оптимальных производственной программе и векторе оценок ресурсов производственные потери равны нулю.

Экономический смысл первой теоремы двойственности можно интерпретировать и так: предприятию  безразлично, производить ли продукцию по оптимальному плану X и получить максимальную прибыль либо продать ресурсы по оптимальным ценам Y и возместить от продажи равные ей минимальные затраты на ресурсы.

Из второй теоремы  двойственности в данном случае следуют  такие требования на оптимальную  производственную программу X (x1, x2,…,xn) и оптимальный вектор оценок У = (y1, y2,…,ym):

если yi > 0, то

(3.10)

 если , то y_i=0, I=  

 

если х_j>0, то    

                 (3.11)

если  , то x_j=0, j=

 

Условия (3.10) можно  интерпретировать так: если оценка j/i единицы  ресурса г-го вида положительна, то при оптимальной производственной программе этот ресурс используется полностью; если же ресурс используется не полностью, то его оценка равна нулю. Из условия (3.11) следует, что если j-й вид продукции вошел в оптимальный план, то он в оптимальных оценках не убыточен; если же j-й вид продукции убыточен, то он не войдет в план, не будет выпускаться.

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

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

 

 

 

 

 

1.3 Виды математических моделей двойственных задач

 

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

• Симметричные задачи

(1) Исходная задача Двойственная задача

Z_min=CX; f_max =Y>A₀;

AX=A₀; YA=С

X>0 Y>0

(2) Исходная задача  Двойственная задача

Z_max =CX; f_min =YA_0;

AX=A₀; YA=С

X>0 Y>0

• Несимметричные задачи

(3) Исходная задача  Двойственная задача

Z_min=CX; f_max=YA₀;

AX=A₀; YA=С

X>0

(4) Исходная задача Двойственная задача

Z_max=CX; f_min=YA₀;

AX=A₀; YA=С

X>0

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

1.4 Двойственный симплексный  метод

 

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

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

b_i являются оценками плана двойственной задачи. С_j являются оценками плана исходной задачи.

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

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

Допустим нужно определить исходную задачу линейного программирования, которая поставлена в общем виде: минимизировать функцию Z=СХ при АХ=A₀, Х>0. Значит в двойственной задаче следует максимизировать функцию f=YA₀ при YA>С. Пусть определен следующий базис D=(A₁, А₂,…, А_i,…, А_m), причем в нем хотя бы одна из компонент вектора Х=D^-1A₀=(x₁, x₂,…, x_i,…, x_m) отрицательная. Для всех векторов A_j используется следующее соотношение Z_j–C_j >0 (i=1,2,…, n).

Пользуясь теоремой двойственности, Y=С_базD^-1 является планом двойственной задачи. Этот план не оптимальный. Потому что оценки оптимального плана двойственной задачи должны быть неотрицательными и выбранный базис X содержит отрицательную компоненту и не является планом исходной задачи, а с другой стороны.