Линейная_алгебра_УП_очная_ЭлРес

					работы		МБИ
2.10. Взаимно двойственные задачи линейного программирования
Определение. Взаимно двойственными задачами линейного
программирования (ЛП) называется пара задач вида:
		n
(1)	f(X) = γj xj + γ0 (max),
		j 1
	n
(2)	a ij	xj	≤ bi , i I M={1,2,…,m},
	j 1
	n
(3)	a ij	xj	= bi , i M \ I,
	j 1
самостоятельной
(4)	xj ≥ 0,		j J N=(1, 2, …, n}					и
(4’)	yi ≥ 0,	m	i I M=(1,ВПО2, …, m}.					.
(1’)	φ(Y) = bi yi + γ0 (min),							г
	m	i 1
(2’)	a ij	yi ≥ γj , j J N={1,2,…,n},
	i 1					2013
	m
(3’)	a ij yi		= γj , j N \ J,
	i 1
Если дана задача ЛП,			о для нее всегда можно построить взаимно
двойственную задачу ЛП, используя следующие правила.
			Москва
10. Одна из пары взаимно двойственных з д ч ЛП должна быть задачей на
Пример. Длястудентовзадачи ЛП на максимум построить взаимно двойственную
максимум и левая час ь ее системы условийЧОУ				не больше правой, то есть между
левой и правой ча тями истемы усло ий неравенство вида:								≤ . Тогда другая из

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

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

задачу ЛП на минимум.

91

f(x) =

x1

+

2x2

–

x3

(max)

работы

x1

+ x2

– 2x3

≤ 3,

1

1

–2

3

*

1

2

–1

1

*

2x1

– x2

+

x3

= 4,

2

–1

1

4

1

–1

1

2

–x1

+ x2

+ 4x3

≤ 5,

–1

1

4

5

*

–2

1

4

–1

x1 ≥0.

1

2

–1

0

3

4

5

0

*

*

*

φ(y) =

3y1+

4y2

+

5y3

(min),

МБИ

y1

+

2y2

–

y3

≥ 1,

y1

–

y2

+

y3

= 2,

–2y1+

y2

+

4y3

= –1,

y1

≥0,

y3

≥0.

Отметим, что:

самостоятельной

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

ВПО

ограничений в системе условий другой из взаимно двойственных задач ЛП;

неотрицательным переменным

дн й из взаимно двойственных

задач ЛП

соответствуют неравенства в системе ограничений другой из взаимно

двойственных задач ЛП;

2013

координаты вектора ограничений одной из взаимно двойственных.

задач ЛП

являются коэффициентами при переменных в целевой функцииг

другой из

взаимно двойственных задач ЛП.

ЧОУ

Важнейшие частные случаи взаимно двойственных задач линейного

программирования:

1.

Симметричная пара взаимно двойственных задач ЛП ( I = M, J = N):

n

Москва

m

f(X) =

γj

xj

+ γ0

(max),

bi yi

+ γ0 (min),

φ(Y) =

j 1

студентов

i 1

n

m

a ij

a ij

yi

≥ γj , j =1,2,…,n,

xj ≤ bi , i =1,2,…,m,

j 1

xj ≥ 0, j=1, 2, …, n.

i 1

yi ≥ 0, i=1, 2, …, m.

2.

Несимметричная пара взаимно дв йственных задач ЛП ( I = Ø, J = N):

n

m

f(X) =

γj

xj

+ γ0

(max),

φ(Y) = bi yi

+ γ0 (min),

j 1

i 1

n

m

a ij

xj = bi , i =1,2,…,m,

a ij

yi

≥ γj , j =1,2,…,n,

j 1

i 1

Для

xj ≥ 0, j=1, 2, …, n.

yi, i=1, 2, …, m.

i 1

=(k1, …, kn)

и

β=( 1,

…, m)

являются

Лемма. Если

векторы α

допустимыми решениями взаимно двойственных

задач ЛП

(1) – (4) и (1’) –

(4’) соответс венно,

о выполняются неравенства:

n

kj ) i ≤ bi i, i=1, 2, …, m,

(L1)

( aij

j 1

(L2)

m

I)kj ≥ γj kj, j=1, 2, …, n.

( aij

92

n

работы

n

▲ Если i I, то aij kj

≤ bi и i ≥ 0

( aij

kj

) i ≤ bi

i. Если же ,

j 1

j 1

n

n

i M \ I, то aij kj = bi

и для

i,

справедливо

( aij kj )

i

= bi i.

j 1

j 1

Следовательно, для любых

i = 1, 2, …, m

вып лняется неравенство

(L1) .

Справедливость неравенства

(L2) доказывается аналогично. ■

10.

Основные свойства взаимно двойственных задач ЛП

Если векторы α =(k1, …, kn)

и β=( 1, …, m) являются допустимыми

решениями

взаимно двойственных

задач

ЛП

(1)

–

(4) и

(1’)

– (4’)

т.е. системасамостоятельнойусловий этой задачи является несовместной.

соответственно, то f(α) ≤ φ(β).

1 +…ВПО+ bm m + γ0

≤ φ(β).

=( a1j kj )

1 +…+ ( amj

kj ) m + γ0 =b1

▲ Значение целевой функции ЗЛП

(1) – (4) на допустимомМБИ

векторе α

=(k1, …, kn) с учетом доказанной леммы м жно записать в виде

.

m

m

г

f(α) = γ1k1 +…+ γтkn + γ0 ≤( ai1 i) k1 +…+ ( ain i) kn + γ0 =

i 1

i 1

2013

=(a11 1+…+am1 m)k1+…+(a1n 1+…+amn m)kn+γ0 = =(a11k1+…+a1nkn)

1+…+(am1k1+…+amnkn) m+γ0 =

ЧОУ

n

n

j 1

j 1

Следовательно, f(α) ≤ φ(β). ■

20.

Если

векторы α0

и β0

являются

допустимыми

решениями взаимно

двойственных задач ЛП

Москва

(1) – (4) и (1’) – (4’) соответственно, и f(α0) = φ(β0),

то векторы α0 и β0 – птимальные решения этих з д ч соответственно.

студентов

α задачи ЛП

(1) – (4) по

▲ Для произвольного допустимого решения

свойству 10

выполнят я нера енст о f(α) ≤ φ(β0). Так как по условию f(α0) =

φ(β0), то f(α) ≤ f(α0) и по

пределению ве тор

α0 является оптимальным

решением ЗЛП (1) – (4).

Опти

альность век ора β0 доказывается аналогично. ■

30.

Если целев я фу кция

од ой

из взаимно

двойственных

задач ЛП

неограниченна на множ стве допустимых решений этой задачи, то другая

взаимно двой твенная за ача ЛП не имеет ни одного допустимого решения,
Для
▲ Доказательство проведем от противного. Пусть целевая функция –
φ(β) задачи	ЛП	(1’) – (4’) неограниченна снизу на множестве допустимых
решений, а	задача	ЛП (1) – (4) имеет допустимое решение – α. Тогда по

свойству 10 для любого допустимого решения – β задачи ЛП (1’) – (4’) должно

выполняется неравенство: f(α)	≤ φ(β).	Это	неравенство противоречит
неограниченности снизу целевой	функции	φ(β)	на множестве допустимых

93

двойственных задач ЛП	не имеет ни одногоработыдопустимого решения,		т. е.,
решений этой задачи. Следовательно, задача ЛП (1) – (4)		не имеет ни одного
допустимого решения, т. е.	система условий этой задачи несовместна. ■
Теоремы двойственнос и
Теорема 1. Если одна из взаимно двойственных		задач ЛП	имеет
оптимальное решение, то и другая взаимно двойственная задача ЛП			имеет

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

Если же целевая функция одной из взаимно двойственных задач ЛП

неограниченна на множестве допустимых				ешений,				то вторая из взаимно
	самостоятельной0 0		0	0		0				0
система условий второй задачи несовместна.				ВПО				МБИ
▲ Доказательство теоремы следует из сформулированных выше
свойств.■								2013		г
	0	0		0	)		0	0		.0
Теорема 2. Пусть векторы α =(x1			, …, xn			и β		=(y1	, …, ym ) являются
допустимыми решениями взаимно двойственных						задач ЛП				(1) – (4) и (1’) –
	ЧОУ

(4’) соответственно. Для того, чтобы векторы α0 и β0 были оптимальными

решениями этих задач н обходимо и достаточно выполнение следующих равенств:

xj0	m	– γj ) = 0,	j=1,	, …, n;
	( aij yi0
	i 1	Москва
yi0	n	– bi ) = 0,	i=1, 2, …, m.
	( aij xj0
студентов
	j 1
▲ Необходимо ть.	Пусть екторы α0		и β0	оптимальные решения

взаимно двойственных задач ЛП (1) – (4) и (1’) – (4’) соответственно. Тогда по свойству 20 вып лняется равенство f(α0) = φ(β0), которое можно записать в виде:

γ1x10 + … + γnxn0 + γ0 = b1y10 + … + bmym0 + γ0.

				m
Это равенство с учетом соотношения (L2) , т. е. ( aij yi0)xj0 ≥ γj xj0, j=1, 2, …, n,
				i 1
равно ильно неравенству:
Для	m	yi	m	≥ b1y1 + … + bmym
	( ai1		) x1 + … +( aiт yi ) xт
	i 1		i 1
(a11y10+…+am1ym0)x10+…+(a1ny10+…+amnym0)xn0+γ0 ≥ b1y10 + … + bmym0
	(a11x10+…+a1nxn0 – b1)y10+…+(am1x10+…+amnxn0 – bm)ym ≥ 0
	( n		a1j xj 0– b1) y10 +…+ ( n	amj xj0 – bm) ym0≥ 0.
		j 1	j 1
	В то же время, из условий задач (1) – (4)			и (1’) – (4’) следует, что каждое

94

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

n

xj 0– b1) y10

n

( a1j

+…+ ( amj xj0 – bm) ym0= 0

j 1

j 1

Однако сумма неположительных слагаемых может равняться нулю

только тогда, когда каждое из слагаемых равно нулю, т. е.

yi0

n

( aij xj0

– bi ) = 0, i=1, 2, …, m.

j 1

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

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

работы

первого соотношенияМБИв утверждении

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

для

выполнения

теоремы доказывается аналогично.

Достаточность. Пусть выпол яются равенства:

m

j=1, 2, …, n; .

xj0 ( aij

yi0

– γj ) = 0,

i 1

г

yi0

n

– bi ) = 0, i=1, 2, …, m.

( aij xj0

j 1

ВПО

Тогда f(α0) = γ1x10 + … + γnxn0 + γ0

m

m

= xj0 ( aij yi0) + … +

xj ( aij yi0) + γ0=

i 1

i 1

= (a11y10+…+am1ym0)x10+…+(a1ny10+…+amnym0)xn0+γ0

=

= (a11x10+…+a1nxn0)y10+…+(am1x10+…+amnxn0)ym+ γ0 =

= b1y10 + … + bmym0 + γ0.= φ(β0)

2013

т. е. f(α0) = φ(β0). О куда с учетом свойства 20

следует, что векторы α0 и β0

ЧОУ

задач ЛП

(1) – (4) и (1’) – (4’)

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

соответственно.■

α0

Пример. Дано

= (1. 0 , –4) –

оптимальное решение задачи ЛП на

минимум.

f(X) = 2 x1

– 4 x3

(min)

x1

–

x2

– 2 x3

≤

1,

x1

– 3 x2

≥ 9,

x1

+

x2

– 2 x3

≥ 7,

x1

≥0

x2

≥0

Москва

самостоятельной

Найти оптимальное решение взаимно двойственной задачи ЛП на

максимум, использ я 2-ю теорему двойственности.

Для

▲ Перепишем данную задачу ЛП в стандартной форме и, используя

студентов

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

f(X) = 2 x1	–	4 x3	(min)
– x1	+	x2	≥ –1,
			95

–

2y2

–

2y3

=

–4,

работы

x1

– 3 x2

– 2 x3

≥ 9,

x1

+

x2

– 2 x3

≥ 7,

x1≥0,

x2≥0.

–1

1

0

–1

*

–1

1

1

2

*

МБИ

1

–3

–2

9

*

1

–3

1

0

*

1

1

–2

7

*

0

–2

–2

–4

2

0

–4

0

–1

9

7

0

*

*

*

*

*

φ(Y) =

– y1

+

9y2

+

7y3

(max)

– y1

+ y2

+ y3

≤ 2,

y1

–

3y2

+

y3

≤

0,

самостоятельной

ВПО

y20(x10 – 3x20

– 2 x30 – 9) = 0,

y1≥0,

y2≥0,

y3≥0.

Согласно

второй

тереме

дв йственности

должны выполняться

следующие соотношения:

.

x10(–y10 + y20

+ y30 – 2) = 0,

2013

– y10

+ y20

+ y30 = 2,

x20(y10 – 3y20

+ y30 ) = 0,

x30(–2y20 – 2y30 + 4) = 0,

ЧОУ

г

y10(– x10 + x20 + 1) = 0,

y30(x10 + x20 – 2 x30 – 7) = 0.

Подставляя

координа ы вектора α0 = (1. 0 , –4) в выписанные

соотношения, получаем систему:

является оптимальным решением этой задачиМоскватогда и только тогда, когда среди

– 2y20

– 2y30

= – 4,

y3

0

= 0.

студентов

Откуда следует, что β0=(0, 2, 0) я ляется оптимальным решением взаимно

двойственной

задачи ЛП

к данн й задаче,

так

как

этот вектор является

допустимым решением двойс венной задачи и значение целевой функции на этом векторе совпадает со значением целев й функции исходной задачи на ее оптимальном решении, т. е. φ(β0) = f(α0) = 18. ■

Следствие (из второй теоремы двойственности). Пусть вектор α0 =(x10, …, xn0) является допустимым решением задач ЛП (1) – (4). Тогда вектор α0

Для
решений системы уравнений:
m
aij yi= γj , если xj0>0,			j J N ={1, 2, …, n};
i 1
	n
yi=0, если aij xj0 < bi		,	i I M={1,2,…,m},

j 1

содержится хотя бы одно допустимое решение двойственной задачи. Пример. Дана задача ЛП:

96

f(X) =	x1	+	2 x2	+	3x3	(max)		работы
								Является ли вектор α = (1, 1, 1)
	x1	–	x2	–	x3	≤	1,	оптимальн м решением этой
	x1	+	x2	–	x3	≤	1,	задачи?
	x1≥0,		x2≥0,		x3≥0.
								▲ Подставив координаты
вектора	в систему условий, убеждаемся, что эт т вект р является допустимым

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

двойственную задачу:
φ(Y) =	y1	+	y2	(min),		Согласно следствию, каждой положительной
	y1	+	y2	≥	1,	координате допустимого решения задачи на
	– y1	+	y2	≥	2,	максимум соответствует равенство в системе
	– y1	–	y2	≥	3,
	самостоятельной
	y1≥0,		y2≥0.			ограничений двойственной задачи на
минимум,							ВПО	решения в
	а строгому неравенству при подстановке допустимогоМБИ

задачу на максимум соответствует нулев е значение двойственной переменной
задачи на минимум.. Таким образом, получаем систему:				.
y1 + y2 = 1,			2013	г
–y1 + y2	= 2, Ø,	ЧОУ
–y1 – y2 = 3,
y1 = 0,

которая является несовместной и поэтому не может содержать допустимых

решений двойственной задачи. Поэтому вектор			α= (1, 1,	1) не является
оптимальным решением исх дной задачи.■
студентов		исходной	задачи	линейного
Экономическое	содержание

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

Рассмотрим, например, следующую итуацию. Имеется m видов ресурсов в количествах b1, b2, … , bm единиц кажд го ресурса. На основе этих ресурсов можно производить продукцию n различными технологическими способами. При этом за единицу времени использования j-го технологического способа

(j =1, 2, …, n)	расходу тся	aij единиц	i-го ресурса (i =1, 2, …, m) и
производится про укция, ценностью γj единицМосква.
Спрашивается, как оценить имеющиеся ресурсы в зависимости от
технологических возможностей производства продукции?
Определим производственную программу (план), как вектор α = (x1, …,
xj, …, xn), где	xj – время	использования	j-го технологического способа

производства продукции, при чем xj ≥ 0 , (j =1, 2, …, n), так как этот
технологическийДля	способ либо используется при производстве продукции, либо

97

не используется.		работы
При этом	общие затраты	i-го ресурса не должны превышать наличия
	n
этого ресурса,	т. е. a ij xj	≤ bi , i ={1,2,…,m}, а	ценность продукции,
	j 1		МБИ
			n
производимой по программе α = (x1, …, xj, …, xn) равна			f(X) = γj xj.
			j 1
Определим ценности имеющихся ресурсов, как вектор β = (y1, …, yi, …,

ym), где yi – некоторая единица ценности i-го ресурса (i =1, 2, …, m), при чем yi ≥ 0, так как этот ресурс имеет ценность п и использовании некоторого

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

самостоятельной

ВПО

технологического способа.

m

Тогда величина aijyi

есть ценность всех видов ресурсов, расходуемых

i 1

.

за

единицу

времени

при

использова ии j-го

технологического способа

m

г

производства продукции. Очевид о, что эта величина не может быть меньше

2013

ценности γj продукции, производимой при использовании j-го

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

a ij yi ≥ γj , j ={1,2,…,n},

ЧОУ

i

так

как в

противном

случае,

часть

ценности

производимой

продукции

m

возникала бы из «ничего». При этом величина φ(Y) =

bi

yi

определяет

Москва

i 1

ценность всех имеющихся ресурсов.

Так как в сбалансир ванной экономике ценность всей производимой

студентов

продукции при любой производственной прогр мме α не может превышать

ценности всех используемых ресурсов при любом

екторе оценок β, то имеет

место неравенство f(α) ≤ φ(β).

Следовательно, величина

(α,β) =

φ(β) – f(α) характеризует потери при

производстве продукции в зависимости от выбора векторов производственной программы α и ценности ресурсов β. Для уменьшения потерь при производстве

продукции, эти векторы		необходимо	выбирать так, чтобы	ценность
		n
производимой продукции		– γj xj	была максимальная, а	ценность
		j 1
			m
используемых в производстве ресурсов – bi yi – минимальная.
			i 1
Таким образом, приходим к паре взаимно двойственных задач линейного
программирования:
Для	n		m
			φ(Y) = bi yi
f(X) = γj xj (max),
	j 1		i 1

98

n		работы
		m
a ij xj ≤ bi	, i ={1,2,…,m},	a ij	yi ≥ γj , j ={1,2,…,n},
j 1		i 1
xj ≥ 0 , ( j =1, 2, …, n),		yi ≥ 0,	(i =1, 2, …, m).
Из первой	теоремы двойственности	следует, ч о при оптимальной
			МБИ
программе производства продукции α0 =		(x10, …, xj0, …, xn0),		и при

оптимальном векторе ценности ресурсов β0 = (y10, …, yi0, …, ym0) производственные потери равны нулю.

Из второй теоремы двойственности следуют условия на оптимальную производственную программу α0 = (x10, …, xj0, …, xn0), и оптимальный вектор

ценности ресурсов		β0	= (y10, …, yi0, …, ym0) ,		которые			заключаются в
	самостоятельной
следующем.						0
Если	ценность i–го ресурса положительна, т. е. yi						> 0, ,то этот ресурс
			n
используется полностью, т. е. a ij xj0 = bi.								г
			j 1
						n
Если					2013				< bi, то его
	i–й ресурс используется не полностью, т. е.					a ij.xj0
						j 1
ценность равна нулю, т. е. yi0 = 0.
Если при производстве продукции используетсяВПО						j-й		технологический
способ, т. е. xj0 >		0 , то ц нность расходуемых в единицу времени ресурсов
				m	yi0 = γj .
равна ценности производимой продукции, т. е. a ij
				i 1
Если	при	j-м	технологическом способе		производства				продукции

ценность затрачиваемых ресурсов больше ценности производимой продукции,
	m	студентов
т. е. a ij yi0 > γj , о данный технологическийЧОУ			способ производства продукции
	i 1
не используется, т. е. xj0 = 0.
Ответьте на вопросы
1.	Напишите пару взаим о двойственных задач линейного программирования.
2.	Опишите схему формирования двойственной задачи к данной задаче.
3.	Как оотно ятся число п р менных и число ограничений для пары взаимно
	двойственных за ач линейного программированияМосква			?
4.	Напишите симметричную пару взаимно двойственных задач .
5.	Сформулируйте лемму о допустимых решениях пары взаимно двойственных
	задач.
6.	Как соотно ят я величины целевых функций пары взаимно двойственных
	задач на их допустимых решениях?
7.	КогдаДля	допустимые решения пары взаимно двойственных задач линейного

99

	работы
	программирования являются оптимальными решениями этих задач?
8.	Какова система ограничений одной из пары взаимно двойственных задач
	линейного программирования, если целевая функция другой задачи не
	ограничена на множестве своих допустимых решений?
9.	Сформулируйте 1-ю теорему двойственности.

10.Сформулируйте и докажите 2-ю теорему двойственности.

11.Когда можно использовать следствие из 2-й теоремы двойственности?

12. Опишите		схему		формирования пары вз имно двойственных задач
	линейного программирования при плани овании работы предприятия.
13. Как используется ресурс, если его ценность положительна?
	самостоятельной
14. Если ресурс используется не полностью, то какова ценность этого ресурса?
15.							ВПО
	Если некоторый технологический способ используетсяМБИпри производстве
	продукции, то какова ценность расх дуемых при этом ресурсов?
16.	Если технологический способ					таков,	что при		.
								производстве продукции
	ценность	затрачиваемых ресурсов					больше	ценности	г	производимой
								2013
	продукции, то нужен ли данный технологический способ производству?
Решите самостоятельно						ЧОУ
Задача 1. Составить двойств нную задачу к данной задаче:
	f(X) = 3x1 – 2x2 +4x3 (max),
		3x1 – x2 + 4x3 ≤ 5,				Москва
		2 x1 – x2 –x3 ≥ 5,
		x1	+ x2	–5x3	≥ 2,
		x1	– x2	+ 3x3	≤ 4,
			студентов
		xj ≥ 0, j=1, 2, 3.
	f(X) = x1 + x2 +x3 (min),
		x1 – x2 + x3 ≤ 3,
		2x1 + 2x2 –5x3 = 4,
		x1 – x2 + 5x3 ≤ 10,
		x2≥ 0.
	f(X) = 3x1 – x2 +8x3 (max),
		x1 + x2 – x3 ≤ 5,

x1 + x2 – x3 ≥ 7, x1 ≥ 0, x3 ≥ 0.

Задача 2. Зная оптимальное решение данной задачи, найти оптимальное
решение двойственной задачи, используя вторую теорему двойственности.
2.1.Для	f(X) = 4x1 + 12x2 +x3 (min),
	3 x1 + 2 x2 + x3 ≥ 3,
	100