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

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

b j

10

4

9

6

ai

6

6

3

4

2

4

8

4

3

4

1

4

2

10

4

0*

3

5

3

9

1

5

2

4

3

5

6

Здес ьп р и в ы чи с лен и и

элем ен т а x22

′

′

= 4. П оэт ом у, н а п р и -

ока за лос ь a2

= b2

м ер , за п олн яет с я т олько в т ор а я с т р ока и п ола га ет с я

′

= 0. П ос ле чего

b2

x32

= 0. Зв ездочкойп ом ечен ба зи с н ы йэлем ен т , р а в н ы йн улю.

Зн а я и с ходн ую ба зи с н ую т очку,

м ы м ож ем

п р одолж и т ьр еш ен и е т р а н с п ор т -

н ойза да чи м ет одом

п от ен ци а лов ,

кот ор ы йяв ляет с я н ес колькои н ойфор м ой

и злож ен и я с и м п лекс н ого м ет ода ,

с в яза н н ой с о с п еци фи кой т р а н с п ор т н ой

за да чи . В п ер в ую очер едьза м ет и м ,

чт оцелев а я фун кци я в т р а н с п ор т н ойза -

да че м и н и м и зи р ует с я, п оэт ом уп р и

в ы бор е в ект ор а ,

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

в в оди т с я

в ба зи с

н а очер едн ойи т ер а ци и ,

будет в ы би р а т ьс я в ект ор с

от р и ца т ельн ой

оцен кой. Для оп р еделен и я в и да

оцен окв т р а н с п ор т н ойза да че в ос п ользуем -

с я за м еча н и ем

1 к§6, в

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

кот ор ы м

оцен ка

j -й п ер ем ен н ой

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

п р а в ойча с т ям и

j -го огр а н и че-

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

j =

T

j

− c j y,

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

н егов ект ор а

y ,

кот ор ы йм ож н он а йт и и з ус лов и я

T

0,

J B=.k =

k− c ky

A

k

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

m

n

å i

i

+ å j v j b→ mina u

i=1

j=1

=

,

,=j 1,+m

≤i

cu v

iji

j

, 1n

где

,=

u- пiер ем ен н ы е дв ойс т в ен н ойза да чи , с оот в ет с т в ующ и е огр а н и -

i

, m1

чен и ям

(2), а

j , =

, 1nv- п ерj ем ен н ы е дв ойс т в ен н ойза да чи , от в еча ющ и е ог-

р а н и чен и ям (3). В с оот в ет с т в и и

с да н н ы м

в и дом

дв ойс т в ен н ойза да чи оцен ки

в

т р а н с п ор т н ойза да че будут и м ет ьв и д

=

,

,=j 1, m −=i

−cu

v

ij

j

i

ij, 1n

п р и чем

п ер ем ен н ы е

,=

uи

i

j , =

т а в ляют с обойп р ои зв оль-

i

, m1

, 1nvп р едсj

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

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

+

=

j),i, Ω(

B ,cu

v

iji

j

(5)

где Ω B -

м н ож ес т в оба зи с н ы х п а р

и н декс ов . За м ет и м , чт ос и с т ем а

(5) и м е-

ет n + m п ер ем ен н ы х и m + n − 1 ур а в н ен и е. Ра н г с и с т ем ы р а в ен m + n − 1.

О т с юда

с ледует ,

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

н а -

п р и м ер ,

u1 = 0 , а

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

п оцеп очке.

Сфор м ули р уем т еп ер ь кр и т ер и й оп т и м а льн ос т и

для т р а н с п ор т н ойза да чи .

0

П ус т ь

= , n1 - н,=jекот, m1(ор Xо),iе баxзи с н ое р еш ен и е т р а н с п ор т н ой

ij

за да чи ,

Ω B - м н ож ес т в оба зи с н ы х п а р и н декс ов

да н н огоба зи с н огор еш ен и я,

0

0

,= , m1u и

, = , 1nv- п рj ои зв ольн ое р еш ен и е

с и с т ем ы

i

i j

+

=

j),i, Ω(

B .cu v

iji

j

Ес ли

с ущ ес т в ует п а р а и н декс ов (i, j) Ω B , для кот ор ой

0

+

0 > uciji ,

v j

т ос ущ ес т в ует ба зи с н ое р еш ен и е X = (xij ), для кот ор ого

m

ij

≤

m

x0 c,

ij

c

x

(6)

ijåå

ij

å å

i 1 j 1

i=1 j=1

= =

ес ли

для

в с ех

п а р

и н декс ов

(i, j) Ω

B

в ы п олн ен о

0 +

0 ≤uc

iji

,

vт о

j

0

= , n1 - р,=ешj ,ен1m(и еX),iза да xчи . За м ет и м , чт одля т р а н с п ор т н ойза -

ij

да чи

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

за да ча

п р и

с облюден и и

ба ла н с а в с егда

р а зр еш

и м а . О т м ет и м

т а кж е, чт он ер а в ен с т в о(6)

яв ляет с я н ес т р оги м в

с в язи

с в озм ож н ос т ью в ы р ож ден н ос т и

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

К а к с ледует

и з а лгор и т м а

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

ес ли

с ущ ес т в ует

в ект ор

Ai

j

0

с п олож и т ельн ойоцен кой, т ов ект ор

Ai

j

0

долж ен бы т ьв в еден в ба зи с .

0

0

Для в в еден и я в ект ор а в ба зи с н уж н озн а т ьегот екущ и е коор ди н а т ы . За м ет и м ,

чт оэт и

коор ди н а т ы яв ляют с я коэффи ци ен т а м и

р а злож ен и я в ект ор а

Ai

j

0

п о

0

т екущ ем уба зи с у. В т р а н с п ор т н ойза да чи для оп р еделен и я коор ди н а т и с п оль-

зует с я п он ят и е ци кла .

О п ределен ие. Говор ят , чт

о множ ест

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

(i, j) обр а зует

цикл, еслиихмож но р а сп олож ит ь, на п р имер , в следую щ ей п оследова т ель-

ност и:

→

→

→ →

→

k

k

→

j

0

) .i О,т (- j

0

) i , ( j

k

0

мет им, чт о ка ж ды е две р ядом ст оящ ие п а р ы

индексов долж ны

имет ьоди-

на ковы е номер а ст р ок илиодина ковы е номер а ст олбцов . Са мип а р ы , входя-

щ ие в цикл,

на зы ва ю т

ся элемент

а мицикла ..

Ра с с м

от р и м п р и м ер

ци кла .

*

*

*

*

*

*

*

*

*

Ц и кл, кот ор ы йи с п ользует с я в

а лгор и т м е р еш ен и я т р а н с п ор т н ойза да -

чи ,

с т р ои т с я с ледующ и м обр а зом . Ст а в ят с я (*) в клет ка х и з м н ож ес т в а Ω B

и в

клет ке i0

j0 )(, кот,

ор а я будет в в оди т ьс я в

ба зи с . П р ос м а т р и в а ют с я в с е

с т р оки т а бли цы

и в ы чер ки в а ют с я т е с т р оки , в

кот ор ы х и м еет с я н е более од-

гоэлем ен т а . За т ем с н ов а п р ос м а т р и в а ют с я с т р оки и

т .д. О с т а в ш и ес я элем ен -

т ы обр а зуют ци кл.

К огда ци кл п ос т р оен , м ож н ос ледующ и м обр а зом

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

в в оди м огов ект ор а : п ер ен ум ер ов а т ьв с е элем ен т ы

ци кла , п р и с в ои в

в в оди м о-

м у элем ен т у 0, с ледующ ем у - 1

и

т .д.; коэффи ци ен т ы

р а злож ен и я в ект ор а

Ai j

0

р а в н ы

+1 п ов ект ор а м и з ци кла

с н ечет н ы м и

н ом ер а м и , -1 - п о элем ен -

0

т а м

ци кла

с чет н ы м и

н ом ер а м и

и

0 п ов ект ор а м , н е в ходящ и м в

ци кл. О бо-

зн а чи м чер ез Ω + м н ож ес т в ои н декс ов

(i, j) с чет н ы м и

н ом ер а м и ,

чер ез Ω −

- м н ож ес т в ои н декс ов

(i, j) с

н ечет н ы м и

н ом ер а м и .

Зн а я коор ди н а т ы

в ект ор а

Ai

j

0

,

егом ож н ов в ес т и в ба зи с п оп р а в и ла м

0

с и м п лекс н ого м ет ода . П ос кольку коор ди н а т ы в в оди м ого в ект ор а

р а в н ы +1

и ли

-1, т озн а чен и е

θ = min

xij0 = x

0*

* . Вект ор

с

(i*

, j* ) Ω B , н а

кот ор ом

i j)( ,Ω −

i j

дос т и га ет с я эт от м и н и м ум , с чи т а ет с я в

да льн ейш

ем

н еба зи с н ы м . О с т а льн ы е

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

н ов ойба зи с н ойт очки п ер ес чи т ы в а ют с я п офор м уле:

H

0

θ

+

ij

ij

j i Ω x;= x+), , (

H

0

θ

−

ij

ij

j i Ω x;= x−), , (

xijH

= xij п оэлем ен т а м , н е в ходящ и м

в

ци кл.

Вы чи с лен и е н ов огозн а чен и я фун кци и цели м ож ет бы т ьп р ои зв еден оп о

фор м уле

LH

= L − θ i0 j0 .

М ож ет ока за т ьс я, чт о

θ =

min

−

xij0

дос т и га ет с я в

н ес кольки х н ечет н ы х

i j)( ,Ω

элем ен т а х ци кла . Тогда н еба зи с н ы м

для н ов ойба зи с н ойт очки с чи т а ет с я

т олькооди н и з н и х,

н а п р и м ер т от , кот ор ом ус оот в ет с т в ует н а и больш ее зн а -

Л

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

Алго рит м

м ет о да п о т ен циало в

И

т ер а ци я 0.

0.1.

О п р еделяет с я н а ча льн ы йба зи с с п ом ощ ью любогои з а лгор и т м ов п о-

с т р оен и я н а ча льн ойба зи с н ойт очки .

( 0 ) =

å

xij0 c, Ωij - м нLожxес т в о

0.2.

Вы чи с ляет с я зн а чен и е фун кци и цели

ба зи с н ы х и н декс ов .

i, jΩ

0.3.

П ола га ем

к=0.

И

т ер а ци я к+1.

П ус т ьн а к-т ойи т ер а ци и п олучен а ба зи с н а я т очка xk

с озн а чен и ем целев ой

фун кци и L(xk ).

j = 1j

− 1

i

Ω.uvЕс ли)c н,,екот( ор ое

k+1.1. П ола га ют

u1 = 0 и оп р еделяют

j

v

s

в ы чи с лен о, т ооп р еделяют

=

−

si

s)i ,,Ω( vu, и тc.д., п ока н е будут в ы -

is

чи с лен ы в с е i

,=

j

, 1muи i j ,= , 1nv.

= +

− cuij

v j

i

ij

k+1.3. Вы би р а ют

i

j

=

i, j

ij .

max

0

0

k+1.4. Ес ли

i0 j0

≤ 0,

т оос т а н ов ,

x k - р еш ен и е за да чи .

i0 j0 )(в м, ес т е с ба зи с н ы м

и п а р а м и

и н декс ов .

П ус т ь Ω + -м н ож ес т в очет н ы х элем ен т ов

ци кла , Ω −

- м н ож ес т в он ечет н ы х

элем ен т ов ци кла без

i0 j0 )(.

,

k+1.6. О п р еделяют Θ =

min

−

xijk .

i j)( ,Ω

k+1.7. П ола га ют

xk +1

= Θ ,

k +1

i0 j0

−

k

Θ

ij

ij

j),i,Ω( x ,= x−

k +1

k

Θ

+

ij

ij

j),i, Ω( x ,= x+

k 1

k

+

+

−

), , (

ij

ij

j xi

x = ΩΩ) . Ω ( \

k+1.8. О п р еделяют c

=

max

c

ij

и элем ен т

c

il jl

с чи т а ют н еба зи с н ы м .

l l

)( ,

i j

Ω − x =0 i j ,

ij

k+1.9. Вы чи с ляют

k +1

=

xk L) − ΘΔ(( L

x).

i j

0

0

Ц и кл обр а зуют элем ен т ы (1,3)→

(1,4) → (4,4) → (4,3).

Ω +

=

Ω −

=

)}.

3, 4( ),

4, 1 {(

)}, 4, 4 {(

1.6

Θ = min(6,5) = 5.

1.7

0

Θ

1

1

1

= ,+6x =x5

1

=

,-0x =5 5 = ,-1

13

14

43

x44

0

1

1

1

1

= x, 6=

, 2

0,

21

23

25

31

x42 = . 8x = , x12

1.8

И м еет с я т олькооди н элем ен т (4,3) и з Ω , для кот ор ого x430

= 0. П оэт ом у

он

с т а н ов и т с я

н еба зи с н ы м .

Нов а я

ба зи с н а я

т очка

и м еет

в и д

æ0

0

ö1 50

ç

6

÷

0

2

00

ç

÷

x1 = ç

0

÷

0

0

0

12

ç

÷

ç

0

÷

0 80

è

ø 6

1.9

1

0

x1

13

x

L

L x

= 61

-3* 5=

76

-

)

( (

)

И т ер а ци я 2.

13

2.1, 2.2

ui

vj

3

-1

3

2

1

0

-4

-5

*

*

-4

0

*

-5

*

-3

*

-3