Добавил:

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

Вуз:

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

Предмет:

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

Файл:

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

.).pdf

Скачиваний:

Добавлен:

21.05.2015

Размер:

538.99 Кб

Скачать

☆

<<< < Предыдущая 12 / 62 3 4 5 6 > Следующая >>>

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

Задачи длясам о ст о ят ельн о го реш ен ия

1. П р и в ес т и кка н он и чес койфор м е с ледующ и е за да чи ли н ейн огоп р огр а м м и - р ов а н и я:

а ) x1 - x 2 + 3x3 ® min		б) 2x1 + x 2 - x 3 ® max
2x1 - x 2 + 3x 3 £ 5		x1 - 2x 2 + x 3 ³ 4
x1	+ 2x 3 = 8	x1 + x 2 - 3x 3 £ 9

- x1 - 2x 2

³1

x1 ³ 0, x 2 ³ 0, x3 ³ 0;

в) 2x1 - x 2 + 3x 3 + x 4 - 2x 5

x1 + 2x 2 - x 3 - 2x 4 + x 5

-2x2 + 4x3 + x4

x1 + 3x2 + 2x3 =10 x1 ³ 0, x 3 ³ 0 ;

® min

=-5

£4

	x 2 ³ 0, x 3 ³ 0, x 5 ³ 0 ;
г)	x1 + 2x 2 + 3x 3 + 2x 4 + x 5 ® max
-	+ +	-	+ x5 ³ x64	x33x1 2x2	4
	-	+	+ 4 + x5 = x2 x13 2x2		3

x1 ³ 0, x3 ³ 0, x 4 ³ 0, x 5 £ 0;

2. П р и в ес т и кс и м м ет р и чн ойфор м е с ледующ и е за да чи ли н ейн огоп р огр а м -

ми р ов а н и я:

а) 2x1 - x 2 + 3x 3 + x 4 - 2x 5 ® min

2x1 - x 2 - 3x 3 + x 4 - x 5 = 4

x1 + 2x 2 + 3x 3 + 3x 4 + x 5 =15

2x1 - 2x2 - x3 - 6x4 + 2x5 = 8

x1 ³ 0, x 2 ³ 0, x 3 ³ 0, x 4 ³ 0, x 5 ³ 0; б) x1 - 2x 2 + 2x 3 + x 4 + 2x 5 ® max

x1 - x 2 + 2x 3 - 3x 4 + x 5 = -2

- x1 + 2x2 - x 3 + 2x4 + 7x5 = 3

2x1 + 3x 2 - 4x 3 + x 4 - x 5 £ 6

x1 ³ 0, x 2 ³ 0, x 3 ³ 0, x 4 ³ 0, x 5 ³ 0

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

§3.

А лго рит м

п еребо ра базисн ы хреш ен ий

сист ем

лин ейн ы хурав н ен ий

В § 2 бы ла в в еден а

ка н он и чес ка я фор м а

ЗЛ П , кот ор а я в

м а т р и чн ом

в и -

де м ож ет бы т ьп ер еп и с а н а с ледующ и м

обр а зом :

= T x ®c maxz x

(

)

(1)

Ax = b , (b ³ 0)

(2)

x ³ 0 ,

(3)

где

,=j , m1

, i)=

, 1n

О чев и дн о, чт ор еш ен и я за да чи

Л П

(1) - (3) н а ходят с я с р еди

р еш ен и йс и с т е-

м ы

ли н ейн ы х ур а в н ен и йAx = b. Ра с с м от р и м

с п ос обп ер ебор а

р еш ен и йда н -

н ойс и с т ем ы для с луча я, когда р а н г м а т р и цы r(A) = m. И

з кур с а

ли н ейн ойа л-

гебр ы и зв ес т н о, чт о с и с т ем а

(2) с п ом ощ ью п р еобр а зов а н и йЖ ор да н а - Г а ус -

с а м ож ет бы т ьп р и в еден а кв и ду

+ ~~ =

x A Ex

(4)

где E - еди н и чн а я м

а т р и ца р а зм

ер а

еет р а зм ер ы

m×(n-m)

m× m , м а т р и ца A и м

и элем ен т ы

р езульт а т е п р еобр а зов а н и йЖ ор да н а -Г а ус с а ,

aij , п олучен н ы е в

- в ект ор р а зм ер а

m, п олучен н ы йи з в ект ор а

b в с ледс т в и е п р еобр а зов а н и й.

Си с т ем а

ур а в н ен и й(4) м ож ет

бы т ь п ер еп и с а н а в коор ди н а т н ойфор м е с ле-

дующ и м

обр а зом :

- å ~ij

È n},

,...J ,

I1{I ,i

x,(5)a

Î =

j J

где I - м н ож ес т в ои н декс ов за в и с и м ы х п ер ем ен н ы х , J - м н ож ес т в ои н декс ов

с в ободн ы х п ер ем ен н ы х,

æ x

x = ç

÷ Î Rn . Ф ор м ула (5) п р едс т а в ляет с обойфор -

ç ~

è x

м улу общ его р еш ен и я с и с т ем ы

(2). На п ом н и м , чт олюбое ча с т н ое р еш ен и е

с и с т ем ы м ож ет бы т ьп олучен ои з фор м улы общ егор еш ен и я п ут ем фи кс и р о-

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

в ы чи с лен и ем

п о фор м уле (5) зн а чен и йза в и с и м ы х п ер ем ен н ы х. В да льн ейш ем н а с будут

и н т ер ес ов а т ь ча с т н ы е р еш ен и я в и да

Î J ), j=т .=е. ,в0ектxÎо(-I ,xi

р ы ,

с в ободн ы е п ер ем ен н ы е кот ор ы х п олож ен ы р а в н ы м и 0.

Та ки е в ект ор ы

н а зы в а ют с я ба зи с н ы м и

р еш

ен и ям и

с и с т ем ы

ли н ейн ы х ур а в н ен и й(2). М а к-

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

Cnm . П е-

р ебр а т ьв с е ба зи с н ы е р еш ен и я с и с т ем ы ли н ейн ы х ур а в н ен и йм ож н о,

ор га н и -

зов а в п ер ебор фор м ул общ егор еш ен и я. О чев и дн о, чт оэт о м ож н оос ущ ес т -

в и т ь с и с п ользов а н и ем

м ет ода

Ж ор да н а -Г а ус с а , н а п р и м ер ,

п о с ледующ ей

с хем е.

Алго рит м

п еребо ра

1. П олучи т ьм ет одом Ж ор да н а -Г а ус с а

п р ои зв ольн ую фор м улуобщ егор еш е-

н и я в и да (5). П олож и т ьN=1.

				Л и нейн ое п р огр а м м и р ов а ни е
2.	За п ом н и т ьм н ож ес т в о I N . П олож и т ь		= N ,	= J N . JI I
3.	Вы бр а т ьн ом ер k и з м н ож ес т в а J. За м ен и т ьJ н а			J\{k}.
4.	Вы бр а т ь l I т а кой, чт о alk ¹ 0 . Ес ли т а ки х н ом ер ов l в I н ет , т оп ер ейт и к
п .7.
5. Ес ли м н ож ес т в о N		È Ik} уж{ lе}\р{а с с м от р ен о, т оза м ен и т ь I н а I \ {l}и
п ер ейт и кп .6, и н а че п ер ейт и кп .8.
6.	Ес ли I= Ø т оп олож и т ь I N и п ер ейт и кп .7, и н а че п ер ейт и кп .4.
7.	Ес ли J=Ø , т о о ст ан о в	- п олучен ы	в с е в озм ож н ы е фор м улы общ егор е-
ш ен и я, и н а че п ер ейт и кп .3.

8. О с ущ ес т в и т ь п р еобр а зов а н и я Ж ор да н а -Г а ус с а с н а п р а в ляющ и м

элем ен -

т ом

alk доп олучен и я в

k-м

с т олбце еди н и чн огов ект ор а . За м ен и т ьN н а

N+1.

П олож и т ь

N =

È k}.{П lерI }\ейт{ Iи кп .2 .

П р и м ер 1. На йт и ба зи с н ы е р еш ен и я с и с т ем ы ур а в н ен и й.

ìx

= 2 - 2x

í 1

îx3 = 4 + x2

Реш ен и е. Здес ь I={1,3},J={2}. О фор м и т ь п р оцедур у р еш ен и я удобн ов

в и де

с ледующ ей т а бли цы ,

где

чер ез Aj

обозн а чен ы

в ект ор ы -с т олбцы

м а т р и цы

(с т олбцы коэффи ци ен т ов п р и п ер ем ен н ойxj).

alk

коммент .

k=2

J1={2}

-1

a12 =2

1/2

k=1

J2 ={1}

1/2

a21 -нет *

a31 =1/2

-4

-1

a23 -нет *

О СТА НО В

a13 -нет *

* (в ы бор эт огоэлем ен т а п ор ож да ет "с т а р ое" м н ож ес т в оI)

На да н н ы х т р ех и т ер а ци ях п олучен ы ба зи с н ы е р еш ен и я с и с т ем ы с оот в ет с т -

в ен н оx1=(2,0,4), x2=(0,1,5), x3=(10,-4,0).

К а кв и дн ои з р а с с м от р ен н огоп р и м ер а , н е в с е п олучен н ы е в р езульт а т е п ер е- бор а ба зи с н ы е р еш ен и я с и с т ем ы ли н ейн ы х ур а в н ен и йяв ляют с я доп ус т и м ы - м и т очка м и в с оот в ет с т в ующ ейза да че ли н ейн огоп р огр а м м и р ов а н и я (1) - (3), т а кка кн е удов лет в ор яют ус лов и ю н еот р и ца т ельн ос т и (3). П р оцедур уп ер е-

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

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

1а . П олучи т ь п р ои зв ольн ое н еот р и ца т ельн ое ба зи с н ое р еш ен и е. П олож и т ь

N=1.

3а . Вы бр а т ь k J т а кое, чт о aik > 0 . За м ен и т ьJ н а J\{k}.

4а . Вы бр а т ь l I

т а кое, чт о

= min

. Ес ли т а ки х н ом ер ов

l в I н ет , т о

alk

п ер ейт и кп .7.

i:aik >0

aik

П р и м ер

2. На йт и

н еот р и ца т ельн ы е ба зи с н ы е р еш

ен и я

с и с т ем ы ур а в н ен и й.

=xx2 +-x

+ 4

1 3

2 x4 = 5x31 + x32 +

Реш ен и е.

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

м ож ет

бы т ьп ер еп и с а -

н а с ледующ и м обр а зом :

x3 -=4x2

- x1

x 4

+ x=2

+x1

П олож и м

N=1. Тогда I 1={3,4},J 1={1,2}..

К а ки

п р и м ер е 1, офор м и м

р еш

ен и е в

в и де в т а бли цы . Доба в и м

с т олбец Θ ,

в кот ор ы йбудем

п ом ещ а т ьот н ош ен и е

bi /aik для aik >0

alk

коммент .

11/4

7/2

11/16

k=2,l=3

J1={1,2}

3/4

-1/2

-1

a32 =4

11/16

7/8

1/4

11/14

k=1,l=2

J2 ={1,3}

23/16

3/8

1/4

23/6

a21 =7/8

11/14

8/7

2/7

k=2

О СТА НО В

8/7

-3/7

1/7

a12 -нет

k=3

a13 -нет

На да н н ы х

и т ер а ци ях п олучен ы

ба зи с н ы е р еш ен и я с и с т ем ы

с оот в ет с т в ен н о

3 =

= ,0,0,

(

),x

,0,

(0,

Задачи длясам о ст о ят ельн о го реш ен ия

1. На йт и

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

а ) x1 − 2x 2 + 4x3 − x4 = 1

2x1 + 3x 2 + x 3 + 2x 4 = 3 ;

б) x1 + x2 + x 3 + x4 = 3 2x1 − x 2 + x 3 − 2x 4 = 2 ;

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

2. На йт и в с е н еот р и ца т ельн ы е ба зи с н ы е р еш ен и я с ледующ ейс и с т ем ы ур а в - н ен и й:

ax1 + x 2 + x 3 + x 4 = 1 x1 + bx 2 + cx 3 + x 4 = 1

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

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

		§4. Алго рит м	сим п лек сн о го м ет о да
	Доп уст има я т очка ЗЛ П		=	1 2	xn ) xнаx зы,...xва, ет( ся, ба зисной, если
вект	ор ы -ст олбцы ма т р ицы A: Ai1			Ai	, k ≤ n , соот,...,				вет ст вую щ ие ее нену-
				k
левы м коор дина т а м, являю т ся линейно неза висимы ми.
	П ока ж ем ,	ка кп р ов ер яет с я,	яв ляет с я ли			за да н н а я т очка ба зи с н ой, н а
п р и м	ер е.
	П р и м ер 1.	П ус т ьус лов и я (2) н екот ор ойза да чи							ли н ейн огоп р огр а м м и -
р ов а н и я и м еют в и д					x4 = 3x23x1+- x2 + 2
		ì			x4 = 3x23x1+- x2 + 2
		í			x2x		-= 3x		+
		î			x2x	4	-= 3x	3	+
		î			1	4		3
П р ов ер и т ь, яв ляет с я ли т очка x=(1,0 ,0,1)Т					ба зи с н ой.

Реш ен и е. Та кка ккоор ди н а т ы т очки н еот р и ца т ельн ы и удов лет в ор яют за да н -

н ойс и с т ем е ур а в н ен и й, т оон а

п ооп р еделен и ю яв ляет с я доп ус т и м ой. Вв е-

дем в

р а с с м от р ен и е в ект ор ы

, A

,-Aс т олбцыA

м а т р и цы огр а н и чен и й:

2ö

æ− 1ö

2 ö

æ1

с и с т емA а ур а в н ен и йп ос ле п од-

= ç

÷,

= ç

÷,

= ç

÷, A

= ç

÷ . ТогдаAA

ç ÷

è1 ø

è 0

-1ø

è2

с т а н ов ки в н ее коор ди н а т

п р ов ер яем ойт очки п р и м ет

в и д:

= b

x A A x

В с оот в ет с т в и и

оп р еделен и ем

ба зи с н ойт очки , в ект ор ы A1 и A4 с ле-

дует п р ов ер и т ь н а

ли н ейн ую н еза в и с и м ос т ь. И

з кур с а ли н ейн ойа лгебр ы и з-

в ес т н о, чт о

в ект ор ы

яв ляют с я ли н ейн он еза в и с и м ы м и , ес ли р а н г м а т р и цы ,

с ос т а в лен н ойи з эт и х в ект ор ов , р а в ен и х коли чес т в у.

Та кка к оп р едели т ельм а т р и цы

¹ 0, т оее р а н г р а в ен 2, и в ект ор ы

ли н ейн он еза в и с и м ы . Следов а т ельн о, т очка (1,0,0,1)Т яв ляет с я ба зи с н ой.

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

И з оп р еделен и я с ледует , чт очи с лоп олож и т ельн ы х коор ди н а т ба зи с н ой

т очки н е м ож ет бы т ьболее чем

m. Еслиба зисна я т очка содер ж ит р овно m

п олож ит

ельны хкоор дина т

, т

о она на зы ва ет

ся невы р ож денной, в п р от ив-

ном случа е - вы р ож денной.

За да ча на зы ва ет ся невы р ож денной, еслидоп ус-

т имое множ ест во не имеет

вы р ож денны хба зисны хт очек.

К а кс ледует

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

т и м ого м н ож ес т в а

ЗЛ

(1) - (3) с ов п а да ют с

н еот р и ца т ельн ы м и ба зи с н ы м и

р еш

ен и ям и с и с т ем ы

ли н ейн ы х ур а в н ен и й(2). Та ки м обр а зом , а лгор и т м п е-

р ебор а

н еот р и ца т ельн ы х ба зи с н ы х р еш ен и йс и с т ем ы с ов п а да ет с а лгор и т -

м ом

п ер ебор а

ба зи с н ы х т очекс оот в ет с т в ующ его доп ус т и м ого м н ож ес т в а .

Следует от м ет и т ь, чт ов

н а ча ле п ер ебор а долж н а бы т ьи зв ес т н а и с ходн а я ба -

зи с н а я т очка . И

т а к, п ус т ьи м еет с я ба зи с н а я

т очка доп ус т и м огом н ож ес т в а

ЗЛ П

Î J). j==Коор,дина0xÎ xIт ыi;

(xi ,, Ix, будемi

в да льнейшем

на зы ва т ь ба зисны ми,

j = 0,x J - jнеба зисны ми. Соот вет ст венно множ е-

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

в а ет с я с оот в ет с т в ующ и йба зи с , с ос т оящ и йи з в ект ор ов	i , AI . Оi бозн а чи м
егочер ез B. За м ет и м да лее, чт ока ж да я и т ер а ци я м ет ода	Ж ор да н а -Г а ус с а с о-
от в ет с т в ует п ер еходу от одн ойба зи с н ойт очки кдр угойп р и за м ен е одн ой
ба зи с н ой (за в и с и м ой) п ер ем ен н ой н а одн у н еба зи с н ую (с в ободн ую). П р и
эт ом в ы бор уп одлеж и т н ом ер н еба зи с н ойп ер ем ен н ойk и ж ес т кооп р еделяет -
с я н ом ер ба зи с н ойп ер ем ен н ойl (с м от р и п ун кт ы 3а и 4а	а лгор и т м а ).
К оор ди н а т ы н ов ойба зи с н ойт очки в ы чи с ляют с я с ледующ и м обр а зом :

x aI

ixl

ikj

¹ k)x. j ÎJ

,j=

, 0 (8)= ; ( Î

alk

Та ки м

обр а зом , р а н ее п олучен а лгор и т м , п озв оляющ и йп ер ебр а т ьв с е

ба зи с н ы е т очки

ЗЛ П . О дн а ко п р и

п ои с ке м а кс и м ум а

н е и м еет

с м ы с ла р а с -

с м а т р и в а т ь т е

т очки , кот ор ы е

обес п ечи в а ют

м ен ьш ее зн а чен и е

целев ой

фун кци и , чем

уж е и зв ес т н ы е. С целью в н ес ен и я т а когоуп ор ядочен и я в а лго-

р и т м п ер ебор а

в ы чи с ли м

зн а чен и е целев ойфун кци и

в т очке

xBH , п р едс т а в -

лен н ойв в и де (8).

О бозн а чи м

Θ =

= min

Тогда

alk

aik

i åi

iki

- c

)

a c Q- ( x c= Q

kåi

i I

− c

Н а зовем оценкой вект ор а

величину

(cв aма т

р ичной

−1

i I

ф ор ме

- c

cAc- вектB

ор коэф ф ициент ов целевой ф ункциип р и

ба зисны хп ер еменны х).

В да н н ы х обозн а чен и ях

xB L) = (L(DxkQ). -

(9)

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

н а

Эт а фор м ула п озв оляет ув и дет ь, чт оес ли в ы бр а н оk т а кое, чт о

k<0, т о

с ледующ ейи т ер а ци и

будет п олучен а

т очка с больш и м

зн а чен и ем

целев ой

фун кци и

(т . к. Θ

≥0). Ес ли

k>0, т оп р ои зойдет ум ен ьш ен и е целев ойфун к-

ци и , п р и

k=0 зн а чен и е целев ойфун кци и н е и зм ен и т с я.

Eс ли k<0, н ов с е

aik ≤ 0, т о, в ы би р а я любое п олож и т ельн ое чи с лов ка чес т в е Θ , будем п олу-

ча т ь доп ус т и м ую, н о н е ба зи с н ую т очку(с м . ф-лу

(8)). Зн а чен и е целев ой

фун кци и

эт ойт очке и зм ен яет с я в с оот в ет с т в и и с

фор м улой(9),

п оэт ом у

ес ли

в ы би р а т ь ка кугодн обольш и м ,

т озн а чен и е фун кци и

цели

будет н е-

огр а н и чен н о ув ели чи в а т ьс я. Следов а т ельн о, в

т а ком с луча е м ож н ос дела т ь

в ы в од он еогр а н и чен н ос т и

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

доп ус т и м ом м н ож ес т в е.

Тео рем а 1. Есливсе оценки,

соот вет ст вую щ ие

некот ор ой ба зисной

т очке

xB , неот

р ица т

ельны ,

т о ест ь

³т0j,о т-а -

cD c=a

,"1n

i I

ка я т

очка являет ся оп т

има льной в за да че (1)-(3).

Сфор м ули р ов а н н ы е фа кт ы

п озв оляют с кон с т р уи р ов а т ьа лгор и т м ба зо-

в огос и м п лекс н огом ет ода .

Алго рит м

базо в о го сим п лек сн о го м ет о да

На ча ло. За да н а

и с ходн а я ба зи с н а я т очка

xB : BT

Î J). j==

, 0xÎ xI i; (x

Вы чи с ли т ьоцен ки п офор м уле

= å

−

j ,j ijJ. i j

c a

i I

П р ов ер и т ь, ес ли в с е

j ≥0,

т оп ер ейт и кп .8.

П р ов ер и т ь, ес ли

в с е aik ≤

, 0т оп ерk ейт: J и к0п .10.

Вы бр а т ьk:

k<0 и в ект ор Ak и м еет хот я бы одн ус т р ого

п олож и т ельн ую коор ди н а т у(в озм ож ен п р ои зв ольн ы йв ы бор т а когон ом ер а k,

н а п р и м

ер ,

max

)

j: j<0

Вы чи с ли т ьп а р а м ет р Θ п офор м уле

Q =

alk

min

aik

i:aik >0

О с ущ ес т в и т ьп ер еход кн ов ойба зи с н ойт очке с п ом ощ ью м ет ода

Ж ор да н а -Г а ус с а

с н а п р а в ляющ и м

элем ен т ом

alk.

И зм ен и т ьи с ходн ую и н фор м а ци ю:

x aI

ikj

¹ k)x. j ÎJ ,j= , 0 = ; ( Î ;

alk

I ← I \ {l} {k}; J ← J \ {l} {k}

П ер ейт и кп .1.

s J :

= 0 ,т ов ы п и с а т ьот в ет : xB

Ес ли

с ущ ес т в ует н ом ер

- оп т и м а льн а я

т очка, в

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

Ес ли

для в с ех

j J,

j > 0, т ов ы п и с а т ьот в ет :

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

xB - еди н с т в ен н ое р еш ен и е за да чи .

10. Вы п и с а т ь от в ет : за да ча	р еш ен и йн е и м еет					и з-за	н еогр а н и чен н ос т и
в ойфун кци и н а доп ус т и м ом	м н ож ес т в е: sup z(x) = +¥
П р и м ер 2. Реш и т ьза да чу				Ω
П р и м ер 2. Реш и т ьза да чу
−	+		−	+ x	5	→xmax x x		x 2 2
					5	4	3 1	2
ì		x31		x2 =1		+-	+
ï			x4 x1 =1x2 - +
í			x4 x1 =1x2 - +
ï				x5 = 2x1 + x2 +
î				x5 = 2x1 + x2 +
xi ³	i =		1	0,
xi ³	i =	5,	1	0,

целе-

Реш ен и е. О фор м и м						р еш ен и е за да чи						в	в и де т а бли цы . В п ер в ом с т олбце п о-
м ес т и м	т екущ и е ба зи с н ы е п ер ем ен н ы е, в ов т ор ом														- и х	коэффи ци ен т ы		в це-
лев ойфун кци и , в т р ет ьем -									ба зи с н ы е коор ди н а т ы						т екущ ейт очки		xB . Да лее
п ер еп и с ы в а ем				элем ен т ы м а т р и цы								aij ,	п ом ещ а я н а д ка ж ды м с т олбцом						ко-
эффи ци ен т с оот в ет с т в ующ ей п ер ем ен н ой в														целев ой фун кци и .			П ос ледн и й
с т олбец п р едн а зн а ча ет с я для оп р еделен и я зн а чен и я Θ .																В от дельн ойс т р оке
в ы чи с ляют с я				оцен ки в ект ор ов							Aj. В ячейке,			н а ходящ ейс я н а п ер ес ечен и и
оцен очн ойс т р оки и						с т олбца			x	,	п ом ещ а ем зн а чен и е целев ойфун кци и								в т е-
кущ ейба зи с н ойт очке.

B		CB			x		2				-1		3		-2	1	Θ
B		CB			x			A1			A2		A3		A4	A5	Θ
x3		3			1			-1			1		1		0	0	―
x4		-2			1		1				-1		0		1	0	1
x5		1			2		1				1		0		0	1	2
			j		3			-6			7		0		0	0
			j		3						7		0		0	0
x3		3			2		0				0		1		1	0
x1		2			1		1				-1		0		1	0
x5		1			1		0				2		0		-1	1
			j		9		0				1		0		6	0

П ос колькун а				п ер в ойи т ер а ци и							1 <0, в		ба зи с в в оди т с я в ект ор A1.
Θ =	1	2		=1, т}.е,. в ка чесmin{т в е н а п р а в ляющ егоэлем ен т а в ы би р а ет с я														a21 .
Θ =	1		1															a21 .
Та кка кн а в т ор ойи т ер а ци и									в с е		j ≥0, т оос т а н ов , п олучен а оп т и м а льн а я
т очка	*	=				). Пxос кольк(1,0,2,0,1ун а н еба зи с н ы х в ект ор а х j > 0, т ор еш е-
н и е в за да че еди н с т в ен н о.
П р и м ер	3. Реш и т ьза да чу

−	+	+
ì		1
ï
í
ï	3
î	3
xi ³	i =		1 0,
xi ³	i =	6,	1 0,

Реш ен и е.

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

−		+ x	6	→xmax x				4	2 x	x 2	3
			6		5			4	31	2
x42	x3 =1x				+		−		+
x5		=1x1		x2	-		+
x	6	= 2 xx -			x	2	+
	6		1 3			2

B	CB		x	2	-1		1	3	-2	1	Θ
B	CB		x	A1		A2	A3	A4	A5	A6	Θ
x4	3	1		-1		1	-1	1	0	0	―
x5	-2	1		1	-1		0	0	1	0	1
x6	1	2		1	-3		1	0	0	1	2
	j	3		-6	3		-3	0	0	0
x4	3	2		0	0		-1	1	1	0
x1	2	1		1	-1		0	0	1	0
x6	1	1		0	-2		1	0	-1	1
	j	9		0		-3	-3	0	6	0
	j	9		0			-3	0	6	0

На в т ор ойи т ер а ци и п олуча ем , чт ооцен ка 2 <0, н ов с т олбце A2 н ет п оло- ж и т ельн ы х элем ен т ов . Эт оозн а ча ет , чт оцелев а я фун кци я н е огр а н и чен а н а

доп ус т и м ом				м н ож ес т в е, т .е. sup z(x) = +¥ .
									Ω
						Задачи длясам о ст о ят ельн о го реш ен ия
1.	Реш и т ьс и м п лекс- м ет одом									за да чуЛ П , п р едв а р и т ельн оп р и в едя ее кка н о-
									−		−		+ ax			→ xmax x											н и чес ком ув и ду.
									−		−		+ ax		4	→ xmax x								2
															4						31			2
								− + 2 − + x											4		≤x2x					x	2
																			4		1 3						2
									+ + − 2x4 ≤ 12x31																x2				bx
																		x		4	£ 62x;		31		x+2 cx+ 4
																				4			31					2
								x j	³					1	0,
								x j	³		j =		4,	1	0,
		а	в		с			а	в			с						а				в				с				а	в	с
1		2	3		-1		6	5	2			3		11			2					1				2			16	3	3	1
2		3	1		1		7	4	3			6		12			3					3				4			17	4	1	2
3		4	2		-1		8	6	1			5		13			5					2				-1			18	3	1	0
4		7	2		3		9	2	2			2		14			7					1				5			19	4	1	3
5		8	3		4		10	5	3			7		15			6					3				8			20	5	2	6

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

2. П р ов ер и т ь, яв ляет с я ли

т очка

x0 р еш

ен и ем

за да чи Л П :

−

→ maxx

a3 x

) 2

5 3

-7x= x +14x+

- 75 + 6

-10=x

x+x 20 -x- 4-5

3 1

x j

j =

)

(2,0,0,3,0

−

→ minx

x31-1=x 2

+ - +

+ x

= x4x- 2x

-2 6

x j

j =

)

(2,1,0,0,0

3. И

с п ользуя т еор и ю с и м п лекс - м ет ода ,

н а йт и

в с е зн а чен и я к, п р и

кот ор ы х

т очка

) яв ляетx с(1,2,0,1,0я р еш ен и ем

за да чи

−

→ maxx

kxx

1 3

− + +

− + 3x5 = 0 x4

2x3x1

−

− x53=x15x4

x+ -7=x;x

+- -

1 3

x j ³

j =

§5. М ет о д иск усст в ен н о го базиса и M-м ет о д реш ен ия

п ро изв о льн о й задачи лин ейн о го п ро грам м иро в ан ия

В с луча е,

ес ли

за да ча

ли н ейн ого п р огр а м м и р ов а н и я за да н а

в п р ои з-

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

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

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

т оес т ь и с ходн ы йба зи с . Для от ы с ка н и я н а -

ча льн ойба зи с н ойт очки

м ож ет

бы т ь и с п ользов а н

п р и ем , за ключа ющ и йс я в

с озда н и и

с п еци а льн ой за да чи ,

с в яза н н ой с

и с ходн ой с ледующ и м

обр а зом :

п р и

р еш ен и и с озда н н ойза да чи

с и м п лекс н ы м

м ет одом

ли бобудет

п олучен а

и с ком а я ба зи с н а я т очка ,

ли бо будет

обн а р уж ен а

п ус т от а

доп ус т и м огом н о-

ж ес т в а

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

П ус т ьЗЛ П

за да н а

ка н он и чес ком в и де (1)-(3). Вв едем н ов ы е (и с кус с т -

в ен н ы е)

п ер ем ен н ы е в

огр а н и чен и я за да чи т а к,

чт обы

р езульт а т е обр а зо-

в а лс я еди н и чн ы йба зи с

(п ояв и ла с ь в озм ож н ос т ь в ы п и с а т ь и с ходн ую ба зи с -

н ую т очку):

Ax + Ez=b (b³ 0)

x ³0, z ³0.

<<< < Предыдущая 12 / 62 3 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	3	6	-2	6	2	4	-4	11	3	2	0	16	6	5	-3
2	2	3	0	7	3	5	-2	12	4	5	-3	17	2	6	-1
3	5	4	-1	8	3	4	-1	13	5	2	-1	18	4	2	-4
4	6	2	-3	9	2	5	0	14	4	3	-4	19	5	6	0
5	5	3	-4	10	6	3	-3	15	6	4	-2	20	4	6	-2

B	CB		x	2	-1		1	3	-2	1	Θ
B	CB		x	A1		A2	A3	A4	A5	A6	Θ
x4	3	1		-1		1	-1	1	0	0	―
x5	-2	1		1	-1		0	0	1	0	1
x6	1	2		1	-3		1	0	0	1	2
	j	3		-6	3		-3	0	0	0
x4	3	2		0	0		-1	1	1	0
x1	2	1		1	-1		0	0	1	0
x6	1	1		0	-2		1	0	-1	1
	j	9		0		-3	-3	0	6	0
	j	9		0			-3	0	6	0

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

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

B	CB		x	2	-1		1	3	-2	1	Θ
B	CB		x	A1		A2	A3	A4	A5	A6	Θ
x4	3	1		-1		1	-1	1	0	0	―
x5	-2	1		1	-1		0	0	1	0	1
x6	1	2		1	-3		1	0	0	1	2
	j	3		-6	3		-3	0	0	0
x4	3	2		0	0		-1	1	1	0
x1	2	1		1	-1		0	0	1	0
x6	1	1		0	-2		1	0	-1	1
	j	9		0		-3	-3	0	6	0
	j	9		0			-3	0	6	0

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

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

B	CB		x	2	-1		1	3	-2	1	Θ
B	CB		x	A1		A2	A3	A4	A5	A6	Θ
x4	3	1		-1		1	-1	1	0	0	―
x5	-2	1		1	-1		0	0	1	0	1
x6	1	2		1	-3		1	0	0	1	2
	j	3		-6	3		-3	0	0	0
x4	3	2		0	0		-1	1	1	0
x1	2	1		1	-1		0	0	1	0
x6	1	1		0	-2		1	0	-1	1
	j	9		0		-3	-3	0	6	0
	j	9		0			-3	0	6	0