Двойственность в линейном программировании

Размещено на http://www.allbest.ru/

Двойственность в линейном программировании

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

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

Рассмотрим стандартную задачу ЛП с n переменными и m ограничениями в форме неравенств

f(x) = c₁ x₁ + c₂ x₂ + …+ c_n x_n --max,

a₁₁ x₁ + a₁₂ x₂ + … + a_1n x_n b₁,

a₂₁ x₁ + a₂₂ x₂ + … + a_2n x_n b₂,

…………………………………….……

a_m1 x₁ + a_m2 x₂ + … + a_mn x_n b_m,

x_j 0, j = 1, 2, …, n.

Двойственной к ней называется задача ЛП следующего вида:

g(y) = b₁ y₁+ b₂ y₂ + …+ b_m y_m??min

a₁₁ y₁ + a₂₁ y₂ + … + a_m1 y_m c₁

a₁₂ y₁ + a₂₂ y₂ + … + a_m2 y_m c₂

………………………….………………

a_1n y₁ + a_2n y₂ + … + a_mn y_m c_n

y_i 0, i = 1, 2, …, m.

Выписывая матрицы условий для прямой и двойственной задачи

,

видим, что А_дв = А^T_пр.

Следовательно, пара двойственных задач может быть записана в матричной форме:

Прямая задача ЛП	Двойственная задача ЛП
f(x) = < c, x > max; Ax ?b, x ?0.	g(y) = < b, y > min; ATy ?с, y ?0.

2. Симметричная пара двойственных задач

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

Правила построения двойственной задачи к стандартной задаче ЛП.

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

· Если прямая задача есть задача на max при ограничениях «», то двойственная задача - задача на min при ограничениях «».

· Правые части ограничений прямой задачи - числа b_i - становятся коэффициентами целевой функции двойственной задачи.

· Коэффициенты целевой функции прямой задачи - числа c_j - становятся правыми частями ограничений двойственной задачи ЛП.

· j - й столбец матрицы условий прямой задачи превращается в j - ю строку матрицы условий двойственной задачи.

· Переменные прямой и двойственной задачи неотрицательны.

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

f(x)=2x₁-4x₂ --max;

x₁+ 3x₂ 8,

-3x₁+ x₂-- -7,

2x₁ - 5x₂-- 10,

x₁, x₂-- 0.

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

g(y)=8 y₁-7y₂+10 y₃ min;

y₁ - 3 y₂+ 2 y₃-- 2,

3y₁+ y₂ -5 y₃-- -4,

y₁, y₂ 0.

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

Сначала приведем двойственную задачу к стандартному виду

g(y)= -8y₁+7y₂-10y₃ max;

y₁+ 3y₂ - 2y₃-- -2,

- 3y₁ - y₂+ 5y₃-- 4,

y₁, y₂ 0.

Построим к ней двойственную задачу по правилам 1-6, обозначая двойственные переменные через x_1, x_2.

f(x)= - 2x₁+ 4 x₂ min;

- x₁ - 3x₂ -8,

3x₁ - x₂ -- 7,

-2x₁+ 5x₂ -- -10,

x₁, x₂-- 0.

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

Из вышесказанного следует, что если прямая задача имеет вид:

f(x) = < c, x > min;

Ax --b, x 0,

то двойственной к ней будет задача

g(y) = < b, y > max;

A^Ty --с, y --0.

3. Экономический смысл двойственной задачи

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

Предприятие после выпуска основной продукции имеет излишки ресурсов двух типов: R₁ - 10 единиц, R₂ - 8 единиц. Существует два способа распорядиться этими ресурсами:

· организовать из них выпуск 3 новых видов продукции: P₁, P₂, P₃.

· продать их.

Рассмотрим оба способа.

Исходные данные приведены в таблице:

Ресурсы	Расход ресурса на единицу продукции	Запас ресурсов
	P1	P2	P3
R1	1	2	1	10
R2	2	1	3	8
Удельная прибыль	$6	$4	$4

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

Пусть x_j - план выпуска продукции P_j.

Тогда целевая функция будет выглядеть следующим образом:

f(x)=6x₁+4x₂+4x₃ max;

Ограничения по ресурсам:

x₁+2x₂+x₃ 10,

2x₁+x₂+3x₃ 8,

x_j 0, j=1,2,3.

Получили стандартную задачу ЛП.

Рассмотрим второй способ использования ресурсов, а именно, их продажу.

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

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

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

Пусть y₁ - цена одной единицы ресурса R_1, y₂ - цена одной единицы ресурса R_2.

Интерес покупателя будет выражаться целевой функцией, равной суммарной стоимости приобретаемых ресурсов

g(y) = 10 y₁+ 8 y₂ min.

Интерес продавца будет описываться ограничениями:

y₁+2y₂ --6,

2y₁+y₂ 4,

y₁+3y₂ 4,

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

Присоединяя естественные условия неотрицательности цен:

y₁, y₂, y₃ 0,

получаем двойственную задачу ЛП.

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

Прямая задача Определить такой план выпуска продукции x =(x1, x2,…, xn), используя ограниченные запасы ресурсов, при котором прибыль от реализации продукции будет максимальной.	Двойственная задача Установить такой набор цен ресурсов y =(y1, y2,…, ym), при которых стоимость ресурсов, затраченных на выпуск единицы продукции будет не ниже прибыли от ее реализации, но при этом суммарная стоимость затрат будет минимальна.

Цены ресурсов y₁, y₂,…, y_m носят названия теневых, неявных или внутренних цен. Эти названия отличают их от «внешних», заранее известных цен с₁, с₂,…, с_n на выпускаемую продукцию. Цены y₁, y₂,…, y_m на ресурсы определяются из решения двойственной задачи и характеризуют стоимость затрат на выпуск конкретных видов продукции, поэтому их часто называют двойственными оценками ресурсов.

4. Несимметричная пара двойственных задач

Пусть теперь исходная задача - каноническая, то есть имеет вид:

f(x) = < c, x > max;	(4.1)
Ax = b,	(4.2)
x 0.	(4.3)

Здесь x = (x_1,…, x_n), c = (c_1,…, c_n), b = (b₁,…, b_m), так что число уравнений в системе (4.2) равно m.

Для построения двойственной задачи к задаче (4.1) - (4.3) сведем ее к стандартной форме.

Каждое равенство в (4.2) заменим парой неравенств

Ax b,

Ax b,

или, что то же самое

Ax b,

- Ax - b,

Получим стандартную задачу ЛП с 2m ограничениями.

f(x)=< c, x > max;

Ax b,

- Ax - b,

x 0.

Построим к ней двойственную задачу ЛП по известным правилам.

Для этого введем двойственные переменные:

u = (u_1,…, u_m) 0,

v = (v_1,…, v_m) 0.

Заметим, что, так как в прямой задаче ЛП было 2m ограничений, то в двойственной будет 2m переменных.

Целевая функция двойственной задачи примет вид:

g (u, v)=< b, u > + < - b, v > min,

а ограничения запишутся так:

A^Tu - A^Tv c,

u 0, v 0.

Перепишем эту задачу более компактно:

g (u, v)=< b, u - v> min,

A^T (u - v) c,

u 0, v 0.

Введем новый вектор двойственных переменных y = (y_1, y_2,…, y_m) с координатами y_i = u_i - v_i. Поскольку разность неотрицательных чисел может быть и отрицательной (например, 2-5= -3), то двойственные переменные y_i не имеют ограничений по знаку.

Таким образом, двойственная задача к канонической будет иметь вид:

g(y) = < b, y > min;

A^Ty 0,

y - переменная любого знака!

5. Таблицы для построения двойственной задачи

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

Прямая задача линейного программирования	Двойственная задача линейного программирования
Целевая функция	< c, x > max	< b, y > min	Целевая функция
Тип i-го ограничения	[Ax]i bi	yi 0	Знак i-й переменной
	[Ax]i bi	yi 0
	[Ax]i = bi	yi - любого знака
Знак j-ой переменной	xj 0	[ATy]j cj	Тип j-го ограничения
	xj 0	[ATy]j cj
	xj ? свободная переменная	[ATy]j = cj

Прямая задача линейного Программирования	Двойственная задача линейного программирования
Целевая функция	< c, x > min	< b, y > ?max	Целевая функция
Тип i-го ограничения	[Ax]i bi	yi ?0	Знак i-ой переменной
	[Ax]i bi	yi 0
	[Ax]i = bi	yi - любого знака
Знак j-ой переменной	xj 0	[ATy]j cj	Тип j-го ограничения
	xj 0	[ATy]j cj
	xj ? свободная переменная	[ATy]j = cj

Задание. Составить двойственные задачи к следующим задачам ЛП.

1. f(x) = 2x₁ - 2x₂+ 3x₃ - 6x₄ max

-2x₁+ x₂ - 2x₃ + x₄ = -10

x₁ - 5x₂ - x₃ + 2x₄ = 35

x_j --0, j=1,2,3,4

2. f(x) = - x₁ - 3x₂+ x₃ min

x₁+ x₂+ x₃ 6

x₁ - x₂+ x₃ 8

x_j 0, j=1,2,3

3. f(x) = 9x₁+ 2x₂+ 3x₃+ 2x₄ min

- x₁+ x₂+ 2x₃ = 2

3x₁+ x₂ - x₃ - 4x₄ = -1

x_j 0, j=1,2,3,4

4. f(x) = x₁ - 2x₂ max

x₁+ x₂ 4

3 x₁ - x₂ 8

4x₁+ x₂ 0

x₂ 0

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

Рассмотрим симметричную пару двойственных задач:

f(x) = < c, x > max;	(4.4)	g(y) = < b, y > min;	(4.7)
Ax b	(4.5)	ATy c	(4.8)
x 0	(4.6)	(y 0	(4.9)
x = (x1,…, xn)		y = (y1,…, ym)

Между решениями этих задач существует тесная связь, отражаемая следующими свойствами и теоремами.

7. Первая теорема двойственности

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

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

f(x^*) = g(x^*) или < c, x^*> = < b, y^*>.

Если же целевая функция одной из пары двойственных задач не ограничена на своём множестве планов (прямая - сверху, двойственная - снизу), то множество планов другой задачи пусто.

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

Утверждение второй части теоремы легко доказывается от противного. Предположим, что в прямой задаче (4.4) - (4.6) целевая функция не ограничена сверху на множестве X, то есть max f(x) Ґ--, xО X, но множество планов Y двойственной задачи не пусто - существует хотя бы одна точка yО Y. Тогда в силу основного неравенства теории двойственности: max f(x) --g(y), что противоречит неограниченности целевой функции прямой задачи. Таким образом, неограниченность сверху целевой функции исходной задачи влечет за собой несовместность ограничений двойственной задачи. Аналогично доказывается, что из неограниченности снизу двойственной целевой функции g(y) на множестве Y, следует пустота множества планов X прямой задачи.

Интересно, что обратное утверждение не верно. Из пустоты множества планов одной задачи еще не следует неограниченность целевой функции в двойственной к ней задаче. (Оба множества могут быть пусты).

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

8. Вторая теорема двойственности

Теорема 2. Планы x^* = (x₁^*,…, x_n^*) и y^* = (y₁^*,…, y_m^*) - оптимальны (каждый в своей задаче), тогда и только тогда, когда выполняются условия:

< Ax^* - b, y^* > = 0, (4.15)

< A^Ty^* - c, x^* > = 0, (4.16)

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

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

Прямая задача ЛП	Двойственная задача ЛП
f(x) = < c, x > max	g(y) = < b, y > min
(4.17) Ax = b	ATy c
x 0

Необходимость.

Пусть x^*, y^* - оптимальные планы прямой и двойственной задач соответственно. Покажем, что условия (4.15), (4.16) выполняются.

Заметим, что при x = x^* из (4.17) следует (4.15). Так как Ax^* - b= 0, значит и скалярное произведение <Ax^* - b, y^* > тоже равно нулю. По первой теореме двойственности для оптимальных планов x^*, y^* выполняется равенство: < c, x* > = < b, y^* >. Подставим сюда выражение для b из (14): b = Ax^*. Используя правило перекидки, получим:

< c, x^* > = < Ax^*, y^* >= < x^*, A^Ty^* > = < A^Ty^*, x^* >,

откуда следует < A^Ty^* - c, x^* > = 0. А это не что иное как условие (4.16)

Достаточность.

Пусть для допустимых планов x^*, y^* справедливо (4.15), (4.16). Докажем их оптимальность.

Условия (4.15) и (4.16) можно записать следующим образом

< Ax^*, y^* > = < b, y^* >, < A^Ty^*, x^* > = < c, x^* >.

По правилу перекидки < Ax^*, y^* > = < A^Ty^*, x^* >. Так как левые части условий равны, то равны и правые части:

< b, y^* > = < c, x^* >,

отсюда по свойству 2 заключаем, что x^* - оптимальный план прямой задачи,

y^* - оптимальный план двойственной задачи. Что и требовалось доказать.

9. Условия равновесия

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

< Ax^* - b, y^* > = 0, (4.18)

< A^Ty^* - c, x^* > = 0. (4.19)

Содержательный смысл условий (1) - (2) рассмотрим для симметричной пары двойственных задач. Запишем эту пару в координатной форме:



Прямая задача ЛП	Двойственная задача ЛП
f(x) = c1 x1 + … + cn xn max	g(y) = b1 y1+ …+ bm ym??min
ai1 x1 + … + ain xn bi, i =1,…, m	a1j y1 + … + amj ym cj, j = 1,…, n
xj 0, j = 1,…, n	yi 0, i = 1,…, m

Раскрывая скалярные произведения, распишем условия (4.18) и (4.19) более подробно.

е--(a_i1 x₁* + … + a_in x_n* - b_i) y_i* = 0, (4.20)

е--(a_1j y₁* + … + a_mj y_m* - c_j) x_j* = 0. (4.21)

В сумме (4.20) каждое слагаемое есть произведение разности левой и правой частей ограничения прямой задачи на соответствующую двойственную переменную. Очевидно, что все слагаемые имеют один и тот же знак «0», так как разности в круглых скобках меньше или равны нулю, а y_i 0. Отсюда следует, что сумма (4.20) равна нулю тогда и только тогда, когда каждое слагаемое в ней равно нулю.

(a_i1 x₁* + … + a_in x_n* - b_i) y_i* = 0, i =1,…, m. (4.22)

двойственность неравенство равновесие линейный

В сумме (4.21) каждое слагаемое равно произведению разности левой и правой частей ограничения двойственной задачи на соответствующую переменную прямой задачи. Все слагаемые в этой сумме одного знака (0), так как разности в круглых скобках и переменные x_j* неотрицательны. Для того, чтобы сумма равнялась нулю, любое слагаемое в сумме должно быть равно нулю.

(a_1j y₁* + … + a_mj y_m* - c_j) x_j* = 0, j = 1,…, n. (4.23)

Учитывая знаки сомножителей в произведении (4.22), из него можно получить пару условий

Если a_i1 x₁* + … + a_in x_n* < b_i, то y_i* = 0. (4.22a)

Если y_i* > 0, то a_i1 x₁* + … + a_in x_n* = b_i. (4.22b)

Аналогично, из (6) следует пара условий

Если a_1j y₁* + … + a_mj y_m* > c_j, то x_j* = 0. (4.23a)

Если x_j* > 0, то a_1j y₁* + … + a_mj y_m* c_j. (4.23b)

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

· если какое-либо ограничение одной задачи на оптимальном плане выполняется как строгое неравенство, то соответствующая координата оптимального плана другой задачи равна нулю (условия (4.22a) и (4.23a)).

· Если какая-либо координата оптимального плана одной задачи положительна, то соответствующее ограничение другой задачи обращается в равенство (условия (4.22b) и (4.23b)).

Эти условия называются условиями дополняющей нежесткости или условиями равновесия.

10. Геометрический смысл условий равновесия

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

a_i1 x₁ + … + a_in x_n b_i (4.24)

называется связным или активным на плане x', если на этом плане оно обращается в равенство

a_i1 x₁' + … + a_in x_n' b_i.

Определение 2. Ограничение (4.24) называется несвязным (неактивным, пассивным) на плане x', если на этом плане оно выполняется как строгое неравенство

a_i1 x₁' + … + a_in x_n' < b_i.

Геометрически, ограничение, активное в точке x', проходит через эту точку, а неактивное - не проходит.

На рисунке в точке x' P₁ и P₃ - активные, связные ограничения; P₂ - неактивное ограничение. В точке x» P_1, P₂ - активные ограничения; P₃ - неактивное ограничение.

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

На оптимальных планах двойственных задач

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

· положительной переменной оптимального плана одной задачи соответствует активное ограничение другой задачи.

Литература

1. Айвазян С.А., Иванова С.С. Эконометрика. Краткий курс: учеб. пособие / С.А. Айвазян, С.С. Иванова. - М.: Маркет ДС, 2007. - 104 с.

2. Бородич С.А. Вводный курс эконометрики: Учебное пособие. - Мн.: БГУ, 2009. - 354 с.

3. Бывшев В.А. Эконометрика: учеб. пособие / В.А. Бывшев. - М.: Финансы и статистика, 2008. - 480 с.

4. Доугерти Кристофер. Введение в эконометрику: Учебник для экон. спец. вузов / Пер. с англ. Е.Н. Лукаш и др. - М.: ИНФРА-М, 2007. - 402 с.

5. Дубров А.М., Мхитарян В.С., Трошин Л.И. Многомерные статистические методы: Учебник. - М.: Финансы и статистика, 2009. - 352 с.

6. Дуброва Т.А. Прогнозирование социально-экономических процессов. Статистические методы и модели: учеб. пособие / Т.А. Дуброва. - М.: Маркет ДС, 2007. - 192 с.

7. Магнус Я.Р., Катышев П.К., Пересецкий А.А. Эконометрика. Начальный курс: Учебник. -3-е изд., перераб. и доп. - М.: Дело, 2008. - 400 с.

8. Методы математической статистики в обработке экономической информации: учеб. пособие / Т.Т. Цымбаленко, А.Н. Баудаков, О.С. Цымбаленко и др.; под ред. проф. Т.Т. Цымбаленко. - М.: Финансы и статистика; Ставрополь: АРГУС, 2007. - 200 с.

9. Палий И.А. Прикладная статистика: Учебное пособие. - М.: Издательско-торговая корпорация «Дашков и К», 2008. - 224 с.

10. Порядина О.В. Эконометрическое моделирование линейных уравнений регрессии: Учебное пособие. - Йошкар-Ола: МарГТУ, 2006. - 92 с.

11. Практикум по эконометрике: Учеб. пособие / И.И. Елисеева, С.В. Курышева, Н.М. Гордеенко и др.; Под ред. И.И. Елисеевой. - 2-е изд., перераб. и доп. - М.: Финансы и статистика, 2007. - 344 с.

12. Прикладная статистика. Основы эконометрики: Учебник для вузов: В 2 т. 2-у изд., испр. - Т. 2: Айвазян С.А. Основы эконометрики. - М.: ЮНИТИ-ДАНА, 2009. - 432 с.

13. Симчера В.М. Методы многомерного анализа статистических данных: учеб. пособие. - М.: Финансы и статистика, 2008. - 400 с.

14. Чураков Е.П. Прогнозирование эконометрических временных рядов: учеб. пособие / Е.П. Чураков. - М.: Финансы и статистика, 2008. - 208 с.

15. Эконометрика: учеб. / под ред. д-ра экон. наук, проф. В.С. Мхитаряна. - М.: Проспект, 2008. - 384 с.

16. Эконометрика: учеб. / под ред. И.И. Елисеевой. - М.: Проспект, 2009. - 288 с.

17. Эконометрика: Учебник/И.И. Елисеева, С.В. Курышева, Т.В. Костеева и др., Под ред. И.И. Елисеевой. - 2-е изд., перераб. и доп. - М.: Финансы и статистика, 2006. - 576 с.

Размещено на Allbest.ru