Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Воронежский государственный университет

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

Лин. програм. учеб. пособие (Азарнова Т. В

.).pdf

Скачиваний:

Добавлен:

21.05.2015

Размер:

538.99 Кб

Скачать

☆

<<< < Предыдущая 1 23 / 63 4 5 6 > Следующая >>>

Л и нейн ое п р огр а м м и р ов а ни е

О чев и дн о,

чт он а ча льн а я ба зи с н а я т очка м ож ет

бы т ь в ы п и с а н а в

в и де

)=. ,Таi1 =коb ,е пz=рxеобрn ;а зов,j(1 а н и, 0е и с ходн ой за да чи

н е

æ xö

æ x

где

яв ляет с я экв и в а лен т н ы м . О дн а ко, ка клегкоза м ет и т ь, т очка м ç

÷ = ç

÷,

в с е z i = 0 с оот в ет с т в уют

è z ø

è0

т очки x , яв ляющ и ес я доп ус т и м ы м и

и с ходн ой

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

ж ела т ельн ос ос т а в и т ь н ов ую за да чу т а ки м

обр а зом ,

чт обы ее р еш ен и ям и яв ляли с ь в ект ор ы в и да x1 xn

) 0Эт,..а, цель0, (м ож,..,ет

бы т ь дос т и гн ут а

за

с чет

с озда н и я с п еци а льн ойцелев ойфун кци и ,

н а п р и м ер ,

å zi ® min . И т а к,

с в яж ем

с и с ходн ой за да чей н ов ую (и с кус с т в ен н ую) z-

i=1

за да чув и да

å zi ® min

i=1

Та кка кв р еш ен а

0	0
1	n

Ax + Ez=b (b³ 0) x ³0, z ³0.

эт ойза да че и м еет с я и с ходн а я ба зи с н а я т очка, т оза да ча м ож ет бы т ь

ба зов ы м с и м п лекс н ы м м ет одом . П ус т ь		п олучен о р еш ен и е
0	0	m	0

1	zm )x ,сzо,знx..,а чен и ем( целев,.., ойфун кци и р а в н ы м	μ0 = å zi

i=1

Тео рем а 1. Ес ли	п р и р еш ен и и z-за да чи			п олучен ооп т и м а льн ое зн а че-
н и е целев ойфун кци и μ	0	= 0 , т от очка	x0	x0 ) (яв ляет,.., с я ба зи с н ойв и с ход-
	0		1	n

н ойза да че. Ес ли μ0 > 0 , т одоп ус т и м ое м н ож ес т в ои с ходн ойза да чи п ус т о. Та ки м обр а зом м ож ет бы т ь р еш ен а п р облем а от ы с ка н и я и с ходн ой

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

р еш ен и и	ЗЛ П н е яв ляет с я р а ци он а льн ы м , т а кка кт р ебует р еш ен и я фа кт и че-
с ки дв ух за да ч: с н а ча ла z-за да чи , а			за т ем - и с ходн ой. Сущ ес т в ует м ет од, п о-
зв оляющ и йобъеди н и т ьэт и дв а эт а п а .
M-м ет о д. П оус лов и ю и с ходн ойза да чи с ос т а в ляет с я в с п ом ога т ельн а я
М -за да ча	в и да
	n		m
	å j	j -	å zi	®Mmaxc x
	J =1		i=1
	Ax + Ez=b (b³ 0)
		x ³0, z ³0.
Здес ь z -	и с кус с т в ен н ы е п ер ем ен н ы е, в в еден н ы е в ус лов и е за да чи с целью
обес п ечен и я и с ходн ойба зи с н ойт очки , с и м в олом M обозн а чен о- н екот ор ое
п олож и т ельн ое чи с ло. Ес ли М		дос т а т очн о в ели ко, т о с ла га ем ы е с п олож и -
т ельн ы м и	zi ум ен ьш а ют зн а чен и е целев ойфун кци и , чт он ев ы годн ос т очки
зр ен и я м а кс и м и за ци и . П р ои с ходи т			ка кбы	"ш т р а фов а н и е" целев ойфун кци и
за т о, чт ов ы бр а н а т очка с п олож и т ельн ы м и				коор ди н а т а м и zi . В с в язи с эт и м

Л и нейное п р огр а м м и р ов а ни е
с ледует ож и да т ь, чт ов оп т и м а льн ойт очке п р и дос т а т очн обольш ом		M в с е
зн а чен и я zi будут р а в н ы н улю. О дн а коэт ов озм ож н от ольков с луча е,		ес ли в
и с ходн ойза да че доп ус т и м ое м н ож ес т в о н е п ус т о. И м еет м ес т о с ледующ а я
т еор ем а .
Тео рем а 2. Ес ли и с ходн а я за да ча и м еет р еш ен и е, т ос ущ ес т в ует		т а кое
чи с лоM0, чт оп р и в с ех M>M0 в с п ом ога т ельн а я М -за да ча т ож е и м еет		р еш е-
æ	* ö
н и е, и в любом ее р еш ен и и ç x	÷ т очка z=0, а x будет р еш ен и ем и с ходн ой
ç	* ÷
è z	ø

за да чи .

С ледст в ие 1. Ес ли п р и р еш ен и и п р ои зв ольн ойза да чи ли н ейн огоп р о- гр а м м и р ов а н и я М -м ет одом будет п олучен а т а ка я оп т и м а льн а я т очка, чт о z*¹ 0, т ов и с ходн ойза да че доп ус т и м ое м н ож ес т в оп ус т о.

И з т еор ем ы с ледует , чт ор еш ен и е м ож н оос ущ ес т в лят ь, фи кс и р уя н е- кот ор ое больш ое чи с лоM, одн а кообы чн оп ос т уп а ют и н а че, и с п ользуя п р и н -

ци п м ет ода и с кус с т в ен н огоба зи с а . Ч и с лоM п р и эт ом	н е фи кс и р ует с я, ос т а в -
ляет с я в за да че в ка чес т в е п а р а м ет р а , кот ор ы йп озв оляет		ос ущ ес т в лят ь н е-
п р ер ы в н ое дв ухэт а п н ое р еш ен и е за да чи . На п ер в ом	эт а п е а лгор и т м а ос ущ е-
	β0	m
с т в ляет с я м а кс и м и за ци я в т ор ойгр уп п ы с ла га ем ы х	β0	M å zi ® max=, а-
		i=1

п ос ле дос т и ж ен и я м а кс и м ум а н еп р ер ы в н оп ер еходят коп т и м и за ци и и с ход- н ойцелев ойфун кци и , ли бодела ют в ы в од он ер а зр еш и м ос т и и с ходн ойза да - чи . До т ех п ор п ока п ер ем ен н ы е zi>0, т .е. яв ляют с я ба зи с н ы м и , и зн а чен и е

целев ойфун кци и , и		оцен ки j	м ож н оп р едс т а в и т ьв в и де α j + β j	,=	M, 1n	. j
Следов а т ельн о, ес ли		в в оди т ь в	ба зи с т а койв ект ор Aj, чт ос оот в ет с т в ующ ее
зн а чен и е	β j <0, т оэт оп р и в едет кув ели чен и ю зн а чен и я β0 . М а кс и м а льн ое
зн а чен и е	будет п олучен о, когда в с е β j будут н еот р и ца т ельн ы м и . О чев и дн о,
чт оп р и эт ом в озм ож н ы дв е с и т уа ци и : β 0 < 0 и β 0 = 0 . Ра с с м от р и м				оба эт и
с луча я.

1. О п т и м а льн ое зн а чен и е β 0 < 0 . На ли чи е т а койс и т уа ци и н а одн ойи з и т ер а ци йозн а ча ет , чт одоп ус т и м ое м н ож ес т в ои с ходн ойза да чи п ус т о, т .к.

оп т и м а льн а я т очка и м еет коор ди н а т ы zi >0.

2. О п т и м а льн ое зн а чен и е β0 = 0 . Та койв а р и а н т в озм ож ен , в с в ою оче- р едь, в дв ух с и т уа ци ях:

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

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

Л и нейн ое п р огр а м м и р ов а ни е

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

яв ляет с я оп т и м а льн ой. Следов а т ельн о, н еобходи м о п р одолж и т ь п ои с к, н е
ум ен ьш		а я п р и эт ом п олучен н ое оп т и м а льн ое зн а чен и е β 0 = 0 . П о оцен ка м
α j	< 0 (ес ли			т а ки е	ес т ь) оп р еделяет с я в ект ор для в в еден и я в ба зи с н а да н н ой
и т ер а ци и .			П р оцес с		п р одолж а ет с я до т ех п ор , п ока н е и с чезн ут т а ки е j, чт о
α j	<	β j	=	, 0с оот в0ет, с т в ующ и йс т олбец Aj и м еет элем ен т ы aij>0.
	И т а к, с фор м ули р уем окон ча т ельн ы й алго рит м реш ен ияп ро изв о ль-
н о й задачи лин ейн о го п ро грам м иро в ан ия.
1.	П р и в ес т и за да чукка н он и чес ком ув и ду.
2.	П р ов ер и т ьн а ли чи е еди н и чн огоба зи с а с р еди с т олбцов м а т р и цы огр а н и че-
	н и й. Ес ли еди н и чн ы йба зи с и м еет с я, т оп ер ейт и кп .5.
3.	Вв ес т и		в	за да чу и с кус с т в ен н ы е п ер ем ен н ы е т а к, чт обы с р еди			с т олбцов
	п олучен н ойм а т р и цы п ояв и лс я еди н и чн ы йба зи с в п р ос т р а н с т в е Rm , где m
	- чи с лоогр а н и чен и йза да чи .
4.	Сос т а в и т ь М -				за да чу: в в ес т и	и с кус с т в ен н ы е п ер ем ен н ы е в	целев ую
	фун кци ю с коэффи ци ен т а м и , р а в н ы м и - М .
5.	Сос т а в и т ьи с ходн ую т а бли цудля офор м лен и я р еш ен и я за да чи . Ес ли да н -
	н ы йп ун кт в ы п олн яет с я п ос ле п ун кт а 2, т офр а гм ен т т а бли цы за в ер ш а ет с я
	одн ойоцен очн ой с т р окой, ес ли					п ос ле п ун кт а 4, т о дв ум я с т р ока м и для
	оцен ок			= α	+ Mβ j (jп ер в аj я - для чи с ел α j , в т ор а я - для β j ).

Вы чи с ли т ь оцен ки

в с ех

в ект ор ов -огр а н и чен и й за да чи

п о

фор м ула м

- c

cПaр и

н а ли чи и и с кус с т в ен н ы х в ект ор ов в ба зи с е п олучи м

i I

α j

+ Mβj

. П ом ес т и т ь α j

в ы р а ж ен и я в и да

в п ер в ую оцен очн ую с т р оку,

β j - в ов т ор ую (н и ж н юю).

П р и н а ли чи и дв ух оцен очн ы х с т р окп р ов ер и т ь, ес ли в с е β j

³ 0, т оп ер ей-

т и кп .11, и н а че - кп .9 с чи с ла м и

β j . Ес ли

ос т а ла с ьодн а оцен очн а я с т р о-

ка, т о п р ов ер и т ь ус лов и е

j ³ 0 .

Ес ли эт оус лов и е в ы п олн яет с я, т оп е-

р ейт и кп .12.

П р ос м от р ет ьв ект ор ы -с т олбцы Aj, для кот ор ы х α j <0. Ес ли

с р еди н и х с у-

щ ес т в ует

т а кой, чт ов с е егокоор ди н а т ы aij ≤ 0, т оп ер ейт и

кп .13, и н а че -

кп .9 с чи с ла м и

j = α j .

О п р едели т ь н а п р а в ляющ и й элем ен т для в ы п олн ен и я и т ер а ци и

п о м ет о-

дуЖ ор да н а -Г а ус с а . Ном ер с т олбца k м ож ет бы т ьв ы бр а н любы м

с р еди т ех

j, для кот ор ы х

j < 0. Ном ер с т р оки l оп р еделяет с я с ледующ и м

обр а зом :

= min

, где

- ба зи с н ы е коор ди н а т ы

п р ов ер яем ойба зи с н ойт очки ,

alk

aik >0 aik

alk

- н а п р а в ляющ и йэлем ен т .

Л и нейное п р огр а м м и р ов а ни е

10.П ер ейт и	кн ов ойба зи с н ойт очке. О с ущ ес т в и т ьп р еобр а зов а н и я Ж ор да н а -
Г а ус с а с	н а п р а в ляющ и м элем ен т ом alk. Вы бр ос и т ьи з р а с с м от р ен и я и с кус -

с т в ен н ы йв ект ор , ес ли он н а да н н ойи т ер а ци и с т а л н еба зи с н ы м . П ер ейт и к

п .6.
11.П р оа н а ли зи р ов а т ь зн а чен и е целев ой фун кци и в		да н н ой ба зи с н ой т очке
( B ) = α0	+ Mβ 0 . Есz лиx β 0 = 0 , т о п р ов ер и т ь н а ли чи е и с кус с т в ен н ы х
в ект ор ов в	ба зи с е. Ес ли и с кус с т в ен н ы х в ект ор ов	в ба зи с е н ет , т ов ы чер к-

н ут ьв т ор ую оцен очн ую с т р окуи п ер ейт и кв ы п олн ен и ю п .7. Ес ли и с кус -

с т в ен н ы е п ер ем ен н ы е и м еют с я с р еди ба зи с н ы х (он и п р и				эт ом р а в н ы н у-
лю), т о п р ов ер и т ь н ер а в ен с т в о α j ³ 0 для т ех н ом ер ов				j ,	для кот ор ы х
β j = 0.Ес ли н ер а в ен с т в а		в ы п олн яют с я, т оп олучен ор еш		ен и е за да чи . П е-
р ейт и кп .15. Ес ли	с р еди	α j , т а ки х чт о β j = 0 с ущ ес т в уют т а ки е, чт о
α j < 0, т оп ер ейт и	кп .8, где п р ов ер ке будут п одв ер га т ьс я т олькот е в ек-
т ор ы Aj , для кот ор ы х α j		< 0, β j = 0. Ес ли в в ы р а ж ен и и		α0	+ Mβ 0 и м еет
м ес т он ер а в ен с т в о β 0 < 0 , т оп ер ейт и кп .14.
12.П р ов ер ка еди н с т в ен н ос т и		р еш ен и я.	j = 0, т ов
Ес ли с р еди н еба зи с н ы х в ект ор ов ес т ьт а ки е, чт о					за да че и м е-
ет с я бес чи с лен н ое м н ож ес т в ор еш ен и й. И с ключен и е с ос т а в ляет с луча й,
когда бы ла с дела н а	за м ен а п ер ем ен н ы х xs=xs'-xs''.		В эт ом	с луча е, ес ли од-

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

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

j ³ 0,т оза да ча	и м еет еди н с т в ен н ое р еш ен и е. П ер ейт и кп .15.
13.О с т а н ов . За да ча	н е и м еет р еш ен и я и з-за		н еогр а н и чен н ос т и целев ойфун к-
ци и н а доп ус т и м ом		м н ож ес т в е. П ер ейт и	кп .15.
14. О с т а н ов . За да ча	н	е и м еет р еш ен и я и з-за	п ус т от ы и с ходн огодоп ус т и м ого

мн ож ес т в а .

15.Вы п и с а т ьот в ет .

П р и м ер 1. Реш и т ьЗЛ П .

+ -x ®xmax

14 3

+ + 2 + x4 = 4x3x1


-	+	x13 =25 x2 3
+	+	xx = 13x			3
		41
x j ³	j =			1	0,
			4,

Реш ен и е.

3 7

23 7

Л и нейн ое п р огр а м м и р ов а ни е

Та кка кв за да че н ет н а ча льн огоба зи с а , с ос т а в и м																	М -за да чу.
+		−					−		−	− Mz		31		→ maxMz			Mz	3	xx x	3	7
+ + 2 + + z1 = 4x4												31			2		1 4	3
+ + 2 + + z1 = 4x4											x3x1			x2
−		+1					+2z2 =x53			2x	3
+		+					+ z	3	= 13xx	x			23		7
								3	4 1	3
x j ³		j =				1 0,
x j ³		j =		4,		1 0,
За п и ш		ем да н н ы е в т а бли цу.

B	CB				x				3	0				7		-1	-M		-M	-M			Θ
B	CB				x				A1	A2				A3		A4	z1		z2	z3			Θ
z1		-M	4						1	1				2		1	1		0	0			4
z2		-M	5						1	-2				3		0	0		1	0			5
z3		-M	13						3	0				7		2	0		0	1		4 1
																						3
α				0					-3	0				-7		1	0		0	0
β				-21					-5	1				-12		-3	0		0	0
x1		3		4					1	1				2		1			0	0		2
z2		-M		1					0	-3				1		-1			1	0			1
z3		-M		1					0	-3				1		-1			0	1			1
α			12						0	3				-1		4			0	0
β				-2					0	6				-2		2			0	0
x1		3		2					1	7				0		3				0
x3		7		1					0	-3				1		-1				0
z3		-M		0					0	0				0		0				1
α			13						0	0				0		3				0

На да н н ойи т ер а ци и п олучен о, чт от р ет ье ур а в н ен и е в с и с т ем е, оп р еделяю-

щ ейх, яв ляет с я ли ш н и м . И с ключа я его, п олуча ем

экв и в а лен т н ую с и с т ем у.

Та кка кв с е j = α j ≥ 0, т оос т а н ов , н а йден а оп т и м а льн а я т очка x*

= (2,0,1,0).

L(x*) = 13. П ос колькун а н еба зи с н ом

в ект ор е оцен ка

2 = 0 , т ов

за да че и м е-

ет с я бес чи с лен н ое м н ож ес т в ор еш ен и й.

П р и м ер 2. Реш и т ьЗЛ П .

− x

→xmax

+ 4

−

x= 9

−

+ x

=x3

x3 3

+ +1 x54 2= 4x3

x j ³

j =

Реш ен и е.

Л и нейное п р огр а м м и р ов а ни е
Та кка кв				за да че п р и с ут с т в ует т олькооди н ба зи с н ы йв ект ор A3, с ос т а в и м М -
за да чу, доба в и в и с кус с т в ен н ы е п ер ем ен н ы е в														1 и 2 огр а н и чен и е.
							+ 3 −		−		1 − Mz2 → maxMz					1 4	xx 3			x
						2 + 4			−			+ z1			=x49x1	x2
							−	+		+				+ z2 = 3x4 x1			x32 3			2
									+	+ +1 x54 2= 4x3						x2
									x j ³	j =			.1		0,
									x j ³	j =		4,	.1		0,
За п и ш		ем	да н н ы е в			т а бли цу.

B	CB				x	1		0	3		-1				-M	-M			Θ
B	CB				x	A1		A2	A3		A4				z1	z2			Θ
z1		-M		9		2		4	0		-1				1	0		9/4
z2		-M		3		-3		2	0		3				0	1		3/2
x3		3		4		1		5	1		2				0	0			4/5
α				12		2		15	0		7				0	0
β				-12		1		-6	0		-2				0	0
z1		-M		4		1		0	2		1				1	0
z2		-M		7/5		-17/5		0	-2/5		11/5				0	1
x2		0		4/5		1/5		1	1/5		2/5				0	0
α				0		-1		0	-3		1				0	0
β				-36/5		11/5		0	6/5		2/5				0	0

К а кв и дн ои з да н н ойт а бли цы , да льн ейш ее улучш ен и е р еш ен и я н ев озм ож н о, т а кка кв о2-йоцен очн ойс т р оке н е ока за лос ьот р и ца т ельн ы х элем ен т ов . Следов а т ельн о, дос т и гн ут ооп т и м а льн ое р еш ен и е М - за да чи . Нои с кус с т в ен -

н ы е п ер ем ен н ы е z1 , z2	н е в ы в еден ы и з ба зи с а и						н е р а в н ы н улю, с ледов а -
т ельн ои с ходн а я за да ча	н е и м еет р еш ен и я, т а кка кее доп ус т и м ое м н ож ес т в о
п ус т о.
Задачи длясам о ст о ят ельн о го реш ен ия
1. Реш и т ь М - м ет одом	за да чу Л П ,	п р едв а р и т ельн о п р и в едя ее кка н он и че-
с ком ув и ду.	+ −	− 2x			→ minx x

		1			5 2		3
	− 2	+xx			= −x3
				1 4	2
	3x2 − x4 + x5 ≤ 5
	x2 +	x5		³ 3
	x3 - 2x4			= 2
	x j ³					1	0,
			j =		5,

Л и нейн ое п р огр а м м и р ов а ни е

2. Реш и т ьМ - м ет одом за да чуЛ П .
−	+	− 3x	5	→ maxx	x	2
			5	31		2
− 2	+	+		− 5 = a	4 x


2	- x - xb- x5 += 1
		b		+1
	x +	x c-	x + x		5	= 8;
		c +1			5	4
		c +1
x j ³	j =	. 5, 1		0,

x	x	x
2
31	2
31	2

	а	в	с		а	в	с		а	в	с		а	в	с

1	1	1	2	6	6	2	2	11	2	2	3	16	3	2	4
2	2	1	2	7	7	2	2	12	4	2	3	17	6	2	4
3	3	1	2	8	2	1	3	13	6	2	3	18	3	3	4
4	4	1	2	9	4	1	3	14	3	1	4	19	6	3	4
5	5	2	2	10	6	1	3	15	6	1	4	20	3	4	4

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

Ра с с м от р и м

за да чули н ейн огоп р огр а м м и р ов а н и я, за п и с а н н ую в п р ои з-

в ольн ой фор м е:

åcj xj

(min)

max

j=1

j ij

, 1m

£i=, ³)(b ,

a x

j=1

x j

зна к

jна=

, ) т р ебова ний ³

, 1n

Да н н ую за да чубудем

н а зы в а т ь и с ходн ой. П од дв ойс т в ен н ойза да чей(ДЗ) к

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

п ос ледующ и м п р а в и ла м , п р и в еден н ы м

т а бли це.

с ходн а я за да ча

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

åc j x j ® max

åbi

yi ® min

j=1

i=1

yi ³ 0

j £ijbi

j=1

yi ≤ 0

j ³ijbi

j=1

Л и нейное п р огр а м м и р ов а ни е

−

зна ка

лю бого

j =ijbi a x

j=1

x j

³ 0

³ijc ja

i=1

x j

£ 0

£ijc ja

i=1

x j

зна ка

лю бого

=ijc ja

За м

i=1

еча н и е. К огда

целев а я фун кци я в

и с ходн ойза да че м и н и м и зи р ует -

с я, т а бли ца

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

Да н н а я т а бли ца

п озв оляет

с фор м ули р ов а т ь н ес колькообщ и х п р а в и л

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

∙

К а ж дом у i-м у

огр а н и чен и ю

и с ходн ой за да чи

с оот в ет с т в ует

п ер е-

м ен н а я yi в

ДЗ и , н а обор от , ка ж дом уk-м уогр а н и чен и ю ДЗ с оот в ет -

∙

с т в ует п ер ем ен н а я xk и с ходн ойза да чи .

М а т р и цы огр а н и чен и йв

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

∙

т р а н с п он и р ов а н ы .

П р а в ы е ча с т и

огр а н и чен и йи с ходн ойза да чи

с т а н ов ят с я коэффи ци -

ен т а м и целев ойфун кци и

ДЗ, а

коэффи ци ен т ы

целев ойфун кци и

∙

и с ходн ойза да чи - п р а в ы м и

ча с т ям и

огр а н и чен и йв ДЗ.

Ес ли

целев а я фун кци я в

и с ходн ойза да че м а кс и м и зи р ов а ла с ь (м и -

н и м и зи р ов а ла с ь), т о в ДЗ целев а я фун кци я м и н и м и зи р ует с я (м а к-

с и м и зи р ует с я);

с п ользуя да н н ое п р а в и лоп ос т р ои м

ДЗ кЗЛ П , за п и с а н н ойв с и м м ет -

р и чн ойфор м е. В ДЗ целев а я фун кци я м и н и м и зи р ует с я :

åbi yi

® min .

i=1

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

в и д

j £ijbi ,aп оx-

j=1

эт ом ун а в с е п ер ем ен н ы е ДЗ будет

п р и с ут с т в ов а т ьт р ебов а н и е н еот р и ца т ель-

н ос т и

i ³

. На0i, в с е п ер ем ен н ы е в

с и м м ет р и чн ойфор м е п р и с ут с т -

, m1

в ует т р ебов а н и е н еот р и ца т ельн ос т и ,

п оэт ом у огр а н и чен и я ДЗ будут

и м ет ь

в и д

, 1n

. Иjт а кc, мaыyп олучи ли за да чу

i=1

åbi yi

® min

i=1

, 1n

c a y

i=1

yi ³

i = ,..., m .1

Л и нейн ое п р огр а м м и р ов а ни е

Ес ли п р ов ес т и а н а логи чн ы е р а с с уж ден и я для п ос т р оен и я ДЗ для ЗЛ П ,

за п и с а н н ойв	ка н он и чес койфор м е, т ом ы п олучи м за да чув и да :
		m
		åbi yi	® min
		i=1
	m
	å	i ³ij j	= ,,..., n . 1					j	c a	y
	i=1
П р и м ер	1. П ос т р ои т ьДЗ кс ледующ ейза да че
	+	-	- x	4	®xminx		x	2	6	4	5
				4		1 3		2
		- - 4 - x4 £ 7x31					3x2
	- + - - x4 ³ 6x31						x2
	-	+ 2	-xx	= -x1
			1 3			2
Реш ен и е.		x1 ³	x2 £ 0			0,
Реш ен и е.
В ДЗ ки с ходн ойза да че будет 3 п ер ем ен н ы х (в и с ходн ойза да че 3 огр а -
н и чен и я) и 4	огр а н и чен и я (в и с ходн ойза да че 4 п ер ем ен н ы х). П ос кольку в

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

с лев а н а п р а в о. Для и ллюс т р а ци и

п ос т р ои м

а н а логи чн ую т а бли цудля да н н ой

кон кр ет н ойза да чи .

с ходн а я за да ча

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

- x

®xminx

-yy

®ymax

1 3

- - 4 - x4 £ 7x31

3x2

y1 £ 0

- + - - x4 ³ 6x31

y2 ³ 0

+ 2

-xx

= -x1

зна ка

1 3

x1 ³ 0

4 - - y31 £ 4y2

x2 £ 0

- + + 2y3y1³ 5 y2

зна ка

лю бого

- - y

= -y1

зна ка

лю бого

- 3y1 - y2 = -6

лю бого

За м ет и м , чт оп р еж де чем с т р ои т ьдв ойс т в ен н ую за да чу, и с ходн ую м ож н ов н а ча ле п р и в ес т и кс и м м ет р и чн ойи ли ка н он и чес койфор м е, а за т ем

п ош а блон укп олучен н ойфор м е за да чи п ос т р ои т ьдв ойс т в ен н ую. П р и эт ом

п олучен н ы е р а зн ы м и		с п ос оба м и дв ойс т в ен н ы е за да чи		будут экв и в а лен т н ы -
м и .
Вы п и ш ем	ос н ов н ы е п р а кт и чес ки зн а чи м ы е с в ойс т в а , кот ор ы е с п р а в ед-
ли в ы для п а р ы	дв ойс т в ен н ы х за да ч. Ра с с м от р и м , н а п р и м ер , в				ка чес т в е п а р ы
дв ойс т в ен н ы х	за да ч	с и м м ет р и чн ую	и дв ойс т в ен н ую	к н ей.	В м а т р и чн ой
фор м е он и за п и с ы в а ют с я с ледующ и м			обр а зом :
cT x → max		bT y ® min

Л	и нейное п р огр а м м и р ов а ни е
	Ax £ b		T	³ cA y
	x ³ 0		y ³ 0
	С в о йст в о	1. За да ча дв ойс т в ен н а я кдв ойс т в ен н ойяв ляет с я и с ходн ой.
	С в о йст в о	2. Для любы х x доп ус т и м ы х в				и с ходн ойза да че и			y доп ус -
т и м ы х в дв ойс т в ен н ойс п р а в едли в он ер а в ен с т в о
				T	£ T y bc x
	С в о йст в о	3. Ес ли и с ходн а я за да ча н е и м еет р еш ен и я и з-за н еогр а н и -
чен н ос т и целев ойфун кци и н а доп ус т и м ом м н ож ес т в е, т одоп ус т и м ое м н о-
ж ес т в одв ойс т в ен н ойза да чи п ус т о.
	С в о йст в о	4. Возм ож ен в а р и а н т , когда доп ус т и м ы е м н ож ес т в а и с ход-
н ойи дв ойс т в ен н ойза да ч одн ов р ем ен н оп ус т ы .
	В ка чес т в е п р и м ер а		р а с с м от р и м		с ледующ ую дв ойс т в ен н ую п а р у
	x1 + 2x2 → max				− 4y1 + y2 → min
	- 3x1 - x2 £ -4				- y1 + y2 = 13		3
	3x1 + x2 £ 1				- y1 + y2 = 2
					y1 ³	y2 ³ 0		0,
	С в о йст в о	5. Ес ли с ущ ес т в ует т очка x0 , доп ус т и м а я в и с ходн ойза да че
и	т очка y0 , доп ус т и м а я в		дв ойс т в ен н ойза да че,			т а ки е, чт о	T	0 =	T y0 ,bтcо x
x0 - р еш ен и е и с ходн ой, а			y0 - р еш ен и е дв ойс т в ен н ойза да чи .
	Тео рем а	1. (П ер в а я т еор ем а			дв ойс т в ен н ос т и ). Если одна				из за да ч
(двойст венна я илиисходна я) имеет				р ешение, т о идвойст венна я к ней имеет
р ешение, п р ичем оп т има льны е зна чения целевы хф ункций совп а да ю т .
	Тео рем а 2. (Вт ор а я т еор ем а			дв ойс т в ен н ос т и ) Для т ого,				чт обы доп ус-
т	има я в исходной за да че т очка			x0	и доп уст има я в двойст венной за да че

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

(

= , n1

иj0ли,

0 ç

0y) a( -x T cy0x)A= 0c

i=1

( y- Axby0 )= b0.

= , m1

0iи,ли

0 ç

(x 0 a)

÷ ij

j=1

За м еча н и е 1.В с и м п лекс - п р оцедур е ос ущ ес т в ляет с я п ер ебор ба зи с ов

B (н ев ы р ож ден н ы х)

п одм а т р и ц и с ходн ойм а т р и цы

A т а ки м

обр а зом , чт о

1. На

ка ж дойи т ер а ци и

м ет ода

в ект ор

= B−1b яв ляет с я

= ç

÷ , где x

è0

доп ус т и м ы м

в и с ходн ойза да че, т .е.

B =

xB ³b0; Ax

<<< < Предыдущая 1 23 / 63 4 5 6 > Следующая >>>

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

#
20.05.201539.94 Кб63Лекция. Обработка звучащей речи.doc
#
20.05.2015337.55 Кб7Ленина.rtf
#
17.07.20191.4 Mб76лесомелиорация курск. кулешова.docx
#
19.03.2016142.85 Кб27ЛетописьПознания.doc
#
22.08.201938.25 Кб2лизации расплавленного базальта.docx
#
21.05.2015538.99 Кб15Лин. програм. учеб. пособие (Азарнова Т. В.).pdf
#
20.05.201546.59 Кб9ЛИннгв идеи эпохи возрождения (2).doc
#
21.05.20151.38 Mб78Линтер методичка.pdf
#
19.03.201693.18 Кб1Липинский Д.А. Проблемы совершен. проц. отв..doc
#
21.05.2015210.4 Кб15литература 17-18вв.pdf
#
19.03.2016501.25 Кб219литература 18 века 1.doc

	а	в	с		а	в	с		а	в	с		а	в	с

1	1	1	2	6	6	2	2	11	2	2	3	16	3	2	4
2	2	1	2	7	7	2	2	12	4	2	3	17	6	2	4
3	3	1	2	8	2	1	3	13	6	2	3	18	3	3	4
4	4	1	2	9	4	1	3	14	3	1	4	19	6	3	4
5	5	2	2	10	6	1	3	15	6	1	4	20	3	4	4

	а	в	с		а	в	с		а	в	с		а	в	с

1	1	1	2	6	6	2	2	11	2	2	3	16	3	2	4
2	2	1	2	7	7	2	2	12	4	2	3	17	6	2	4
3	3	1	2	8	2	1	3	13	6	2	3	18	3	3	4
4	4	1	2	9	4	1	3	14	3	1	4	19	6	3	4
5	5	2	2	10	6	1	3	15	6	1	4	20	3	4	4

	а	в	с		а	в	с		а	в	с		а	в	с

1	1	1	2	6	6	2	2	11	2	2	3	16	3	2	4
2	2	1	2	7	7	2	2	12	4	2	3	17	6	2	4
3	3	1	2	8	2	1	3	13	6	2	3	18	3	3	4
4	4	1	2	9	4	1	3	14	3	1	4	19	6	3	4
5	5	2	2	10	6	1	3	15	6	1	4	20	3	4	4