П.1. Экономическая интерпретация двойственных задач

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

 

Первая фирма. Пусть производится n (1, 2, …, j, …, n) видов продукции, при этом используется m видов сырья, запасы которого b₁, b₂, …, b_m. При этом известна технология изготовления продукции, согласно которой на производство единицы продукции j-го вида идет a_ij единиц ресурса i. Цена от реализации единицы продукции j-го типа составляет C_j у.е. Требуется составить план выпуска продукции, который обеспечивал бы первой фирме максимальную прибыль.

Перед нами типичная задача на использование ресурсов. Математическая модель данной задачи имеет вид:

Требуется максимизировать функцию

Z = C₁x₁ + … + C_nx_n

при ограничениях

Здесь x_j (j = 1, …, n) – количество единиц продукции j.

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

Обозначим у_i – цена в у.е. единицы сырья i-го вида (i = 1, 2, …, m), получим, что общие затраты на приобретение сырья можно определить следующим образом:

f = b₁y₁ + b₂y₂ + … + b_my_m.

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

Систему ограничений задачи можно получить из следующих соображений. В каком случае первая фирма согласится продать свои ресурсы и прекратить выпуск n видов продукции? Только в том случае, когда прибыль от реализации единицы каждого вида продукции будет не больше, чем цена, установленная второй фирмой на ресурсы, затраченные на производство единицы этой продукции. Например, согласно технологии на единицу первого вида продукции затрачивается количество единиц первого ресурса а₁₁, второго – а₂₁, …, m-го – a_m1. Прибыль от реализации составляет С₁ у.е. Таким образом, для совершения сделки необходимо выполнение неравенства

а₁₁y₁ + а₂₁y₂ + … + а_m1y_m ³ С₁.

Рассуждая аналогичным образом, получим систему неравенств

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

1. Если одна задача состоит в отыскании минимума целевой функции, то целью другой задачи будет нахождение максимума функции.

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

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

4. Матрицы при переменных в системах ограничений задач являются транспонированными друг другу (см. [8]).

5. При стандартной записи двойственных задач в системе ограничений задачи на максимум все знаки неравенств «£ » (использовать запасов не более, чем …), для задачи на минимум «³ » (затратить средств не менее, чем…).

6. В одной и другой задаче имеются условия неотрицательности.

Обычно задачу, которую ставят первой, называют исходной задачей, задачу, которая составляется по исходной задаче, – двойственной задачей (см. табл. 5.1).

Таблица 5.1.

Исходная задача		Двойственная задача
Z = C X ® max A X £ A0 X ³ 0		f = Y A0 AT Y ³ C Y ³ 0
Двойственная задача		Исходная задача

 

Замечание 5.1. Систему А ограничений A^T Y ³ C, используя правило умножения матриц, можно переписать следующим образом:

Y × A ³ C.

 

П.2. Теоремы двойственности

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

Теорема 5.1. (первая теорема двойственности) Если из пары двойственных задач одна имеет оптимальное решение, то и другая задача имеет оптимальное решение, причем

z_max = f_min.

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

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

Положим, что найдено решение задачи линейного программирования, в которой максимизируется функция

Z = C X, (5.1)

где С = (С₁, С₂, …, С_n) – матрица строка, – матрица столбец, которая удовлетворяет ограничениям

А Х £ А₀, Х ³ 0,

где А = (a_ij) – матрица коэффициентов при переменных, .

Для решения поставленной задачи симплексным методом необходимо было все неравенства привести к уравнениям путем прибавления дополнительных неотрицательных переменных x_{n + 1}, …, x_{n + m}. При этом ограничения запишутся в виде

А Х^* = А₀, Х^* ³ 0,

где Х^* = (х₁, х₂, …, x_n, x_{n + 1}, …, x_{n + 1}).

Положим, что поставленная задача обладает оптимальным планом Х_опт, причем базисными переменными являются . Векторы A₁, A₂, …, A_m образуют базис, координаты векторов составляют единичную матрицу Е размером m ´ m.

Двойственной для задач (5.1) и (5.2) является следующая задача

f = Y A₀ ® min, (5.4)

(5.5)

Доказательство.

Выбираем из матрицы А те столбцы, которые соответствуют базисным векторам в оптимальном решении задачи. Обозначим полученную матрицу через D = {A₁, A₂, …, A_m}.

Для каждого вектора A_j (j = 1, …, n+ m) существует вектор X_j(x_1j, …, x_mj) такой, что

A_j = D X_j

или

D^-1 A_j = X_j

где D^-1 обозначает матрицу, обратную D.

Для оптимального плана Х_опт( , …, ) справедливы соотношения:

A₀ = D X_опт или D^-1 A₀ = X_опт, (5.6)

A_j = D или D^-1 A_j = , (5.7)

где ( , …, ), - координаты вектора A_j в базисе A₁, …, A_m.

Поскольку по предположению план Х_опт является оптимальным, то согласно теореме 4.1 выполняются соотношения

Z_j – C_j = – C_j ³ 0,

где С_опт = (С₁, C₂, …, C_m).

Будем искать оптимальный план двойственной задачи (5.4), (5.5) в виде

Y_опт = С_опт D^-1. (5.8)

Для того, чтобы доказать, что план Y_опт = ( , , …, ) является оптимальным, необходимо показать, что выполняются два условия:

1) для вектора Y_опт справедливы неравенства (5.5), т.е. Y_опт является решением двойственной задачи;

2) для других решений Y двойственной задачи выполняются условия f(Y) ³ f(Y_опт), т.е. Y_опт является оптимальным планом двойственной задачи.

Докажем, что первое условие выполняется для каждого вектора A_j
(j = 1, …, n+ m).

Y_опт A_j ³ C_j Û С_опт D^-1 A_j - C_j ³ 0 Û С_опт X_j - C_j ³ 0 – верно.

Значит, первое условие выполняется.

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

f(Y_опт) = Y_опт A₀ = С_опт D^-1 A₀ = С_опт Х_опт = Z_max.

Рассмотрим любой другой план двойственной задачи Y. Для него выполняются неравенства

Y A ³ C. (5.9)

Умножим неравенства (5.9) справой стороны на неотрицательную матрицу Х, являющуюся произвольным планом исходной задачи. Получим

Y A X ³ C X = Z(X).

С другой стороны, для плана Х выполняются соотношения

А Х £ А₀. (5.10)

Умножим обе части (5.10) слева на матрицу Y, получим

Y А Х £ Y А₀ = f(Y).

Таким образом

Z(X) £ Y A X £ f(Y). (5.11)

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

Z(X_опт) = Z_max £ f(Y).

Это означает, что для любого плана двойственной задачи выполняется условие f(Y) ³ f(Y_опт) = Z_опт, т.е. Y_опт является оптимальным планом двойственной задачи.

Докажем вторую часть утверждения теоремы. Пусть линейная функция исходной задачи не ограничена сверху. Тогда из (5.11) следует, что f(Y) ³ ¥. Это выражение лишено смысла, следовательно, двойственная задача не имеет решений.

Первая теорема двойственности имеет совершенно ясный экономический смысл. Так цены у₁, …, у_m получили название учетных или теневых цен. В отличии от цен на продукцию С₁, …, С_n, которые задаются до начала производства извне, теневые цены на ресурсы определяются только в процессе решения задачи. Согласно первой теории двойственности план производства Х(х₁, …, х_n) и учетный набор цен на ресурсы Y(у₁, …, у_m) оказываются оптимальными в том и только том случае, когда прибыль от реализации продукции, найденная при известных ценах С₁, …, С_n, равна затратам на ресурсы по учетным ценам у₁, у₂, …, у_m.

Очевидно, что при увеличении прибыльности первого предприятия, описанного в п.1 данного параграфа, второму предприятию будет сложнее (в смысле денежных затрат) перекупить у него ресурсы. Данный факт нашел свое отражение в знаменитом фильме с участием Дж.Фокса «Секрет его успеха». Опуская комедийные повороты сюжета и блестящую игру актеров, можно сказать, что в фильме сталкиваются две экономические концепции. Старое управление крупной компании, столкнувшись с угрозой быть купленной конкурентами, ведет политику на жесткую экономию и сокращение производства. Молодой менеджер, только что окончивший университет, напротив предлагает шаги для быстрого экономического развития, полагая, что ни у кого не хватит средств купить прибыльную, перспективную компанию. В результате он оказывается прав. Следует традиционный happy end, участие в котором, несомненно, принимали труды Канторовича и Данцига.

Перед доказательством теоремы 5.1 в условие исходной задачи были введены дополнительные переменные x_n+1, …, x_n+m. Вторая теорема двойственности устанавливает связь между первоначальными переменными двойственной задачи у₁, …, у_m и дополнительными переменными исходной задачи.

Теорема 5.2. (Вторая теорема двойственности*) Положительным компонентам оптимального решения одной из взаимно двойственных симметричных задач соответствуют нулевые компоненты оптимального решения другой задачи, т.е. для любых i = 1, 2, …, m и j = 1, 2, …, n: если , то ; если , то и наоборот, , то , если , то .

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

, i = 1, 2, …, m, x_j ³ 0, x_{n + i} ³ 0, (5.12)

, j = 1, 2, …, n, y_i ³ 0, y_{m + j} ³ 0. (5.13)

Выразим из (5.12) и (5.13) дополнительные переменные.

, (5.14)

. (5.15)

Умножим все уравнения (5.14) на соответствующие переменные y_i ³ 0, а все уравнения (5.15) на x_j ³ 0. Получим

, (5.16)

. (5.17)

Сложим все равенства (5.16) и все равенства (5.17), получим:

, (5.18)

. (5.19)

Положим, что планы X(x₁, …, x_n, x_{n + 1}, …, x_{n + m}), Y(y₁, …, y_m, y_{m + 1}, …, y_{m + n}) – оптимальные, тогда

.

Складывая (5.18) и (5.19), получим

.

Поскольку и , то полученное соотношение может выполняться только при условии, что

(5.20)

Условия (5.20) будут выполняться, если каждое из слагаемых в уравнениях будет равно нулю, т.е.

Таким образом, утверждение теоремы доказано.

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

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

Согласно результатам теоремы 5.1 оптимальный план двойственной задачи можно получить по формуле

Y_опт = D^-1 С_опт.

Однако, если использовать симплексную таблицу, то можно обнаружить, что в ней содержится не только решение исходной задачи, но и матрица D^-1, а также значение Y_опт.

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

 

 

Таблица 5.2.

Базис	Сбазиса	А0	С1	С2	…	Сn		…
А1	А2	…	Аn	Аn+1	…	Аn+m
Аn+1		b1	a11	a12	…	a1n		…
Аn+2		b2	a21	a22	…	a2n		…
…	…	…	…	…	…	…	…	…	…
Аn+m		bm	am1	am2	…	amn		…
Zj – Cj		Z1– C1	Z2– C2	…	Zn– Cn		…

 

Последние m векторов A_n+1, …, A_n+m образуют единичную матрицу Е(m ´ m).

Положим, что при оптимальном плане в базис входят векторы A₁, A₂, …, A_m. Тогда симплексная таблица при последней итерации будет иметь вид.

Таблица 5.3.

Базис	Сбазиса	А0	С1	С2	…	Сm	…	Сn		…
А1	А2	…	Аm	…	Аn	Аn+1	…	Аn+m
А1	С1				…		…			…
А2	С2				…		…			…
…	…	…	…	…	…	…	…	…	…	…	…
Аm	Сm				…		…			…
Zj – Cj	Zmax			…		…	Zn-Cn	Zn+1	…	Zn+m

 

При этом последние A_n+1, …, A_n+m столбцов образуют матрицу D^-1, которая получена методом присоединения единичной матрицы (см. [8]). Оценки Z_n+1, …, Z_n+m рассчитываются по формуле

.

Таким образом, согласно теореме 5.2, устанавливающей соответствие между переменными x_n+j и y_j, получим

, , …, .

Если же исходная задача заключается в нахождении минимума функции, то добавочные переменные y_m+1, y_m+2, …, y_n+m входят со знаком «минус», обратную матрицу - Е(n ´ n). В этом случае будут справедливы соотношения:

, , …, .

П р и м е р 5.1. Предприятие выпускает два вида продукции. Для производства единицы продукции первого типа требуется 12 кг ресурсов А, 4 кг ресурсов В и 2 кг ресурсов С. Для производства единицы продукции второго вида затраты ресурсов следующие: 3 кг – А, 6 кг – В, 14 кг – С. Запасы ресурсов А, В и С составляют 264 кг, 148 кг, 280 кг соответственно. Прибыль от реализации единицы первой продукции – 6 у.е., второй – 4 у.е. Требуется поставить для данной задачи двойственную и найти оптимальные значения и оптимальные планы задач.

Решение. Экономико-математическая модель исходной задачи имеет вид:

Z = 6x₁ + 4x₂ ® max.

Здесь х₁ – количество единиц продукции первого вида, х₂ – количество единиц продукции второго вида.

Модель двойственной задачи имеет вид:

f = 264 y₁ + 148 y₂ + 280 y₃ ® min.

Здесь y₁, y₂, y₃ – теневые цены на ресурсы А, В, С соответственно.

Решим исходную задачу симплексным методом. Для этого введем дополнительные переменные х₃ ³ 0, х₄ ³ 0, х₅ ³ 0.

Z = 6 x₁ + 4x₂ + 0 x₃ + 0 x₄ + 0 x₅ ® max.

Составим симплексную таблицу.

Таблица 5.4.

Базис	Сбазиса	А0	С1=6	С2=4	С3=0	С4=0	С5=0
А1	А2	А3	А4	А5
А3
А4
А5
Zj – Cj		– 6	– 4
А1				1/4	1/12
А4					– 1/3
А5				27/2	– 1/6
Zj – Cj			– 5/2	1/2
А1					1/10	– 1/20
А2					– 1/15	1/5
А5					11/15	– 27/10
Zj – Cj				1/3	1/2

 

Поскольку в строке Z_j – C_j после второй итерации нет отрицательных чисел, то полученный план является оптимальным.

Z_max = 162,

Х_опт (19, 12, 0, 0, 74).

Запишем решение двойственной задачи. Согласно теореме 5.1

f_min = Z_max = 162.

Оптимальный план двойственной задачи найдем по итоговым оценкам А₃, А₄, А₅:

у₁ = Z₃ – C₃ = 1/3,

у₂ = Z₄ – C₄ = 1/2,

у₃ = Z₅ – C₅ = 0.

Сделаем проверку. Для этого подставим значения у₁, у₂, у₃ в целевую функцию

– верно.

 

⇐ Предыдущая12345678Следующая ⇒

Поделиться: