Шапкин А.С., Шапкин В.А. Задачи по высшей математике, теории вероятностей, математической статистике, математическому программированию с решениями

Подождите немного. Документ загружается.

371

Ïðè îãðàíè÷åíèÿõ











≥≥

≥+

≤+

,0 ,0

,10

,6962958

,4803232

,3122413

(7.1)

íàéòè ìàêñèìóì ëèíåéíîé ôóíêöèè

Z = 4x

+ 3x

. (7.2)

Ãåîìåòðè÷åñêîå ðåøåíèå çàäà÷è

Ïîñêîëüêó çàäà÷à äâóõìåðíàÿ, òî åå ìîæíî ðåøèòü ãðàôè÷åñêè.

Ñèñòåìà îãðàíè÷åíèé (7.1) äàåò ìíîãîóãîëüíèê ðåøåíèé. Äëÿ

åãî ïîñòðîåíèÿ ïðîâîäèì ïðÿìûå, ÿâëÿþùèåñÿ ãðàíèöàìè ìíî-

ãîóãîëüíèêà è ñ ïîìîùüþ ïðîáíîé òî÷êè, íàïðèìåð (0; 0), îïðå-

äåëèì ïîëóïëîñêîñòè, çàäàâàåìûå ýòèìè ïðÿìûìè (ðèñ. 86):

: 13x

+ 24x

= 312,

: 32x

+ 32x

= 480,

: 58x

+ 29x

= 696,

: x

+ x

= 10.

Â ïåðåñå÷åíèè ñîîòâåòñòâóþùèõ ïîëóïëîñêîñòåé ïîëó÷èì øå-

ñòèóãîëüíèê ABCDEF.

Ðèñ. 86

z = z

max

z = 0

010121524

•

• •

•

= (4; 3)

372

Äëÿ íàõîæäåíèÿ max z ïîñòðîèì èç íà÷àëà êîîðäèíàò âåêòîð

)3 ;4(=n

è ïåðïåíäèêóëÿðíóþ åìó ëèíèþ óðîâíÿ z = 0, ò.å. ïðÿ-

ìóþ 4x

+ 3x

= 0.

Äàëåå ïåðåäâèãàåì ëèíèþ óðîâíÿ z = const â íàïðàâëåíèè âîç-

ðàñòàíèÿ z, ò.å. ïàðàëëåëüíî ñàìîé ñåáå â íàïðàâëåíèè âåêòîðà

n .

Â ïîñëåäíåé ïåðåñåêàåìîé âåðøèíå D ïîëó÷àåì íàèáîëüøåå çíà-

÷åíèå z. Âåðøèíà D  ýòî òî÷êà ïåðåñå÷åíèÿ ïðÿìûõ l

è l

Íàõîäèì êîîðäèíàòû òî÷êè D èç ñèñòåìû:













.242

,15

,6962958

,4803232

Ðåøàÿ ñèñòåìó, íàéäåì, ÷òî õ

= 9, õ

= 6, ò.å. D (9; 6) è ïðè

ýòîì z = 4 · 9 + 3 · 6 = 54 (óñë. åä.).

Äëÿ ðåøåíèÿ çàäà÷è ñèìïëåêñ  ìåòîäîì ïðèâåäåì ñèñòåìó

îãðàíè÷åíèé (7.1) ê ôîðìå ðàâåíñòâ ñ ïîìîùüþ íåîòðèöàòåëüíûõ

äîïîëíèòåëüíûõ ïåðåìåííûõ y

(i = 1, 2, 3, 4):











=++

,034

,10

,242

,15

,3122413

421

321

221

121

Zxx

yxx

(7.3)

ïðè ýòîì x

≥ 0 (j = 1, 2); y

≥ 0 (i = 1, 2, 3, 4).

Çàïèñûâàåì ñèñòåìó ñ ïîìîùüþ óêîðî÷åííûõ òàáëèö (òàáë. 7.1).

Òàáëèöà 7.1

13 24 = 312

1 1 = 15

2 1 = 24

1 1 = 10

Z 4 3 = 0

Òàê êàê â I  ñòîëáöå åñòü îòðèöàòåëüíûé ýëåìåíò, òî åãî íóæ-

íî ñäåëàòü ïîëîæèòåëüíûì. Âûáèðàåì ó

 ñòðîêó ñ îòðèöàòåëü-

íûì ñâîáîäíûì ÷ëåíîì «10».

373

Â ýòîé æå ñòðîêå åñòü îòðèöàòåëüíûå ýëåìåíòû, âûáèðàåì êà-

êîé-íèáóäü èç íèõ, íàïðèìåð, «1» â õ

 ñòîëáöå. È õ

 ñòîë-

áåö ïðèíèìàåì â êà÷åñòâå ðàçðåøàþùåãî ñòîëáöà.

Äåëèì ñâîáîäíûå ÷ëåíû íà ñîîòâåòñòâóþùèå ýëåìåíòû ðàçðå-

øàþùåãî ñòîëáöà, ïîëó÷àåì {24, 15, 12, 10} è íàèìåíüøåå ïîëî-

æèòåëüíîå îòíîøåíèå áóäåò ñîîòâåòñòâîâàòü ðàçðåøàþùåé ñòðî-

êå, ñëåäîâàòåëüíî, ó

 ñòðîêà ÿâëÿåòñÿ ðàçðåøàþùåé, à ýëåìåíò

1 ðàçðåøàþùèì ýëåìåíòîì. Ñîâåðøàåì øàã ìîäèôèöèðîâàí-

íîãî æîðäàíîâà èñêëþ÷åíèÿ (ØÌÆÈ) ñ ðàçðåøàþùèì ýëåìåí-

òîì 1 ïî ïðàâèëó:

1) íà ìåñòå ðàçðåøàþùåãî ýëåìåíòà ñòîèò âåëè÷èíà åìó îá-

ðàòíàÿ;

2) ýëåìåíòû ðàçðåøàþùåé ñòðîêè äåëÿòñÿ íà ðàçðåøàþùèé

ýëåìåíò;

3) ýëåìåíòû ðàçðåøàþùåãî ñòîëáöà äåëÿòñÿ íà ðàçðåøàþùèé

ýëåìåíò è çíàê ìåíÿåòñÿ;

4) îñòàëüíûå ýëåìåíòû íîâîé òàáëèöû íàõîäÿòñÿ ïî ôîðìóëå

ïðÿìîóãîëüíèêà [17, ñòð. 52]:

ýëåìåíò éðàçðåøàþùè

ñòîëáöà ðàçð.

ýëåì. ñîîòâåò.

ñòðîêè ðàçð.

ýëåì. ñîîòâåò.

ýëåìåíòû

ñòàðûå

ýëåìåíòû

íîâûå

⋅

−=

Ïîëó÷àåì òàáë. 7.2, ïðè ýòîì ïåðåìåííûå õ

è y

ìåíÿþòñÿ

ìåñòàìè. Èç òàáëèöû âèäíî, ÷òî ñâîáîäíûå êîýôôèöèåíòû â I 

ñòîëáöå íå îòðèöàòåëüíû, ñëåäîâàòåëüíî, ïîëó÷åíî îïîðíîå ðå-

øåíèå: õ

= 10, õ

= 0, y

= 182, y

= 5, y

= 4, y

= 0, Z = 40. Ãåîìåò-

ðè÷åñêè ýòî îçíà÷àåò, ÷òî ìû íàõîäèìñÿ â âåðøèíå F (10;0) ìíî-

ãîóãîëüíèêà ðåøåíèé ABCDEF.

Òàáëèöà 7.2

13 11 = 182

10= 5

21= 4

1 1 = 10

Z 4 1 = 40

374

Ýòî ðåøåíèå íå ÿâëÿåòñÿ îïòèìàëüíûì, òàê êàê â Z  ñòðîêå

èìååòñÿ îòðèöàòåëüíûé êîýôôèöèåíò, óëó÷øàåì ïëàí.

Âûáèðàåì ðàçðåøàþùèé ýëåìåíò ïî ïðàâèëó: âûáèðàåì ñòîë-

áåö ñ íàèìåíüøèì îòðèöàòåëüíûì ýëåìåíòîì â z-ñòðîêå  ðàçðå-

øàþùèé ñòîëáåö, äåëèì ñâîáîäíûå ÷ëåíû â I-ñòîëáöå íà ñîîòâåò-

ñòâóþùèå êîýôôèöèåíòû è íàèìåíüøåå ïîëîæèòåëüíîå îòíîøå-

íèå ñîîòâåòñòâóåò ðàçðåøàþùåé ñòðîêå. Íà ïåðåñå÷åíèè ñòîèò

ðàçðåøàþùèé ýëåìåíò 2 . Ñîâåðøàÿ ØÌÆÈ ñ ðàçðåøàþùèì

ýëåìåíòîì 2 ïî âûøå ïðèâåäåííîìó ïðàâèëó, ïîëó÷àåì òàáë. 7.3.

Òàáëèöà 7.3



= 156



−

= 3

−

= 2

= 12

Z 21= 48

Ðåøåíèå, ïîëó÷àåìîå èç òàáë. 7.3, òàêæå íå ÿâëÿåòñÿ îïòè-

ìàëüíûì, òàê êàê â Z-ñòðîêå èìååòñÿ îòðèöàòåëüíûé êîýôôè-

öèåíò. Îïðåäåëÿÿ èç òàáë. 7.3 ðàçðåøàþùèé ýëåìåíò

Òàáëèöà 7.4

11 35 = 51

1 2 = 6

01= 5

11= 9

Z 1 2 = 54

375

ñîâåðøàÿ ØÌÆÈ, ïðèõîäèì ê òàáë. 7.4, â êîòîðîé âñå êîýôôèöè-

åíòû â Z-ñòðîêå íåîòðèöàòåëüíû, à, ñëåäîâàòåëüíî, max Z óæå

äîñòèãíóò è åìó ñîîòâåòñòâóåò ðåøåíèå õ

= 9, õ

= 6, ïðè ýòîì

max

= 54 (óñë. åä.).

Îòâåò: ìàêñèìàëüíàÿ ïðèáûëü Z = 54 (óñë. åä.) äîñòèãàåòñÿ ïðè

èçãîòîâëåíèè 9 åäèíèö èçäåëèé I è 6 åäèíèö èçäåëèé II.

7.1.2. Òðàíñïîðòíàÿ çàäà÷à

Ýòî çàäà÷à î íàèáîëåå ýêîíîìíîì ïëàíå ïåðåâîçîê îäíî-

ðîäíîãî èëè âçàèìîçàìåíÿåìîãî ïðîäóêòà èç ïóíêòîâ ïðîèçâîä-

ñòâà (ñòàíöèé îòïðàâëåíèÿ) â ïóíêòû ïîòðåáëåíèÿ (ñòàíöèè íà-

çíà÷åíèÿ).

Òðàíñïîðòíàÿ çàäà÷à ÿâëÿåòñÿ âàæíåéøåé ÷àñòíîé ìîäåëüþ

ëèíåéíîãî ïðîãðàììèðîâàíèÿ, èìåþùåé îáøèðíûå ïðàêòè÷åñêèå

ïðèëîæåíèÿ íå òîëüêî ê ïðîáëåìàì òðàíñïîðòà. Îñîáî âàæíîå

çíà÷åíèå îíà èìååò â äåëå ðàöèîíàëèçàöèè ïîñòàâîê âàæíåéøèõ

âèäîâ ïðîìûøëåííîé è ñåëüñêîõîçÿéñòâåííîé ïðîäóêöèè, à òàê-

æå îïòèìàëüíîãî ïëàíèðîâàíèÿ ãðóçîïîòîêîâ è ðàáîòû ðàçëè÷-

íûõ âèäîâ òðàíñïîðòà.

7.1.2.1. Ïîñòàíîâêà çàäà÷è

è åå ìàòåìàòè÷åñêàÿ ìîäåëü

Íåêîòîðûé îäíîðîäíûé ïðîäóêò ïðîèçâîäèòñÿ â m ïóíêòàõ

ïðîèçâîäñòâà À

, À

, , À

. Çàäàí îáúåì ïðîèçâîäñòâà à

ïóíêòà

).,1( miA

Ïðîèçâåäåííûé ïðîäóêò äîëæåí áûòü ïåðåâåçåí â n

ïóíêòîâ ïîòðåáëåíèÿ B

, B

, , B

. Èçâåñòåí ñïðîñ b

ïóíêòà

),1( njB

. Çàäàíû òàêæå òðàíñïîðòíûå èçäåðæêè Ñ

, ñâÿçàííûå

ñ ïåðåâîçêîé åäèíèöû ïðîäóêòà èç ïóíêòà À

â ïóíêò Â

. Òðåáóåò-

ñÿ ñîñòàâèòü ïëàí ïåðåâîçîê, îáåñïå÷èâàþùèé ïðè ìèíèìàëüíûõ

òðàíñïîðòíûõ ðàñõîäàõ (èçäåðæêàõ) óäîâëåòâîðåíèÿ ñïðîñà âñåõ

ïóíêòîâ ïîòðåáëåíèÿ çà ñ÷åò ïðîäóêòà, ïðîèçâåäåííîãî âî âñåõ

ïóíêòàõ ïðîèçâîäñòâà.

Îáîçíà÷èì ÷åðåç õ

êîëè÷åñòâî åäèíèö ãðóçà, çàïëàíèðîâàí-

íûõ ê ïåðåâîçêå îò i-ãî ïîñòàâùèêà ê j-ìó ïîòðåáèòåëþ. Òîãäà óñ-

ëîâèå çàäà÷è ìîæíî çàïèñàòü â âèäå òàáë. 7.5, êîòîðóþ â äàëüíåé-

øåì áóäåì íàçûâàòü ìàòðèöåé ïëàíèðîâàíèÿ.

376

Òàáëèöà 7.5

Ïîòðåáèòåëè

 B

 ñ

  

 ñ

  

 ñ

Ïîòðåáíîñòè b

 b

Σa

Σb

Ïîýòîìó ìàòåìàòè÷åñêàÿ ôîðìóëèðîâêà òðàíñïîðòíîé çàäà-

÷è ñâîäèòñÿ ê ìèíèìèçàöèè ëèíåéíîé ôîðìû

∑∑

ijij

xCZ

(7.4)

ïðè îãðàíè÷åíèÿõ

∑

iij

miax

,,1 ,

(7.5)

(îãðàíè÷åíèÿ ïî çàïàñàì),

∑

jij

,,1 ,

(7.6)

(îãðàíè÷åíèÿ ïî ïîòðåáíîñòÿì),

≥ 0. (7.7)

Ðàçëè÷àþò çàäà÷è ñ çàêðûòîé ìîäåëüþ, êîãäà

∑∑

îòêðûòîé ìîäåëüþ, êîãäà

∑∑

≠

, ò.å. áàëàíñ ìåæäó çàïàñà-

ìè è ïîòðåáíîñòÿìè îòñóòñòâóåò.

Ïîñòàâùèêè Çàïàñû

377

Íåîáõîäèìûì è äîñòàòî÷íûì óñëîâèåì ðàçðåøèìîñòè òðàíñ-

ïîðòíîé çàäà÷è ÿâëÿåòñÿ ðàâåíñòâî ñóììàðíûõ çàïàñîâ ñóììàð-

íûì ïîòðåáíîñòÿì, ò.å.

∑∑

Åñëè

∑∑

òî ââîäÿò ôèêòèâíûé (n + 1)-é ïóíêò íàçíà-

÷åíèÿ ñ ïîòðåáíîñòüþ

∑∑

−=

bab

è ïîëàãàþò c

i,n+1

= 0,

. ,1 mi =

Åñëè

∑∑

, òî ââîäÿò ôèêòèâíûé (m + 1)-é ïóíêò

îòïðàâëåíèÿ ñ çàïàñàìè ãðóçà

∑∑

−=

aba

è ïðèíèìàþò

m+1,j

= 0,

. ,1 nj =

Ìàòåìàòè÷åñêàÿ ìîäåëü òðàíñïîðòíîé çàäà÷è îòíîñèòñÿ ê çàäà-

÷àì ëèíåéíîãî ïðîãðàììèðîâàíèÿ è ìîæåò áûòü ðåøåíà ñèìïëåêñ-

íûì ìåòîäîì. Îäíàêî ââèäó èñêëþ÷èòåëüíîé ïðàêòè÷åñêîé âàæíî-

ñòè ýòîé çàäà÷è è ñïåöèôèêè îãðàíè÷åíèé (7.5)  (7.7): îãðàíè÷åíèÿ

çàäàíû â âèäå óðàâíåíèé; êàæäàÿ íåèçâåñòíàÿ âõîäèò ëèøü â äâà óðàâ-

íåíèÿ, êîýôôèöèåíòû ïðè íåèçâåñòíûõ  åäèíèöû, äëÿ åå ðåøåíèÿ

ñîçäàíû ñïåöèàëüíûå àëãîðèòìû. Ñàìûì ðàñïðîñòðàíåííûì ìåòî-

äîì ðåøåíèÿ òðàíñïîðòíîé çàäà÷è ÿâëÿåòñÿ ìåòîä ïîòåíöèàëîâ.

Ðåøåíèå òðàíñïîðòíîé çàäà÷è ðàçáèâàåòñÿ íà äâà ýòàïà:

1. Îïðåäåëåíèå íà÷àëüíîãî äîïóñòèìîãî áàçèñíîãî ðåøåíèÿ (ïåð-

âîãî îïîðíîãî ïëàíà)  ïåðâîíà÷àëüíîå ðàñïðåäåëåíèå ïîñòàâîê.

2. Ïîñòðîåíèå ïîñëåäîâàòåëüíûõ èòåðàöèé (øàãîâ), óëó÷øà-

þùèõ îïîðíûå ïëàíû (êàæäûé íîâûé ïëàí íå äîëæåí óâåëè÷è-

âàòü ñóììàðíûå çàòðàòû).

Ïîñëå âûïîëíåíèÿ ïåðâîãî ýòàïà øàãè âòîðîãî ýòàïà ïðîâî-

äÿòñÿ äî òåõ ïîð, ïîêà íå áóäåò íàéäåíî îïòèìàëüíîå ðàñïðåäåëå-

íèå ïîñòàâîê.

7.1.2.2. Ïîñòðîåíèå ïåðâîíà÷àëüíîãî îïîðíîãî ïëàíà

Ðàññìîòðèì äâà ìåòîäà ïîñòðîåíèÿ ïåðâîãî îïîðíîãî ïëàíà.

Ïëàí ñîñòàâëÿåòñÿ ïîñëåäîâàòåëüíûì çàïîëíåíèåì ïî îäíîé

êëåòêå â òàáëèöå ïåðåâîçîê òàê, ÷òî êàæäûé ðàç ëèáî ïîëíîñòüþ

óäîâëåòâîðÿåòñÿ ïîòðåáíîñòü îäíîãî èç ïîòðåáèòåëåé, ëèáî ïîë-

íîñòüþ ââîçèòñÿ ãðóç îò íåêîòîðîãî ïîñòàâùèêà. Â òåîðèè äîêà-

378

çûâàåòñÿ, ÷òî áàçèñíîå ðåøåíèå ñèñòåìû îãðàíè÷åíèé (èç m + n

óðàâíåíèé ñ mn ïåðåìåííûìè) â óñëîâèÿõ òðàíñïîðòíîé çàäà÷è

èìååò m + n  1 áàçèñíûõ ïåðåìåííûõ (åå ðàíã ðàâåí m + n  1),

ïîýòîìó, ñîâåðøèâ m + n  1 óêàçàííûõ øàãîâ, ïîëó÷èì ïåðâûé

îïîðíûé ïëàí. Ðàçëè÷èå äâóõ ìåòîäîâ îòûñêàíèÿ ïåðâîãî îïîð-

íîãî ïëàíà ñîñòîèò â ðàçëè÷èè ñïîñîáîâ âûáîðà ïîñëåäîâàòåëü-

íîñòè çàïîëíåíèÿ êëåòîê.

Äèàãîíàëüíûé ìåòîä èëè ìåòîä ñåâåðî-çàïàäíîãî óãëà. Ïðè

ýòîì ìåòîäå íà êàæäîì øàãå ïîñòðîåíèÿ ïåðâîãî îïîðíîãî ïëà-

íà çàïîëíÿåòñÿ âåðõíÿÿ ëåâàÿ êëåòêà («ñåâåðî-çàïàäíûé óãîë»)

îñòàâøåéñÿ ÷àñòè òàáëèöû. Ïðè òàêîì ìåòîäå çàïîëíåíèå òàá-

ëèöû íà÷èíàåòñÿ ñ êëåòêè ïåðåìåííîãî õ

è çàêàí÷èâàåòñÿ â

êëåòêå íåèçâåñòíîãî õ

, ò.å. èäåò êàê áû ïî äèàãîíàëè òàáëèöû

ïåðåâîçîê.

Ìåòîä íàèìåíüøåé ñòîèìîñòè. Èñõîäíîå îïîðíîå ðåøåíèå,

ïîñòðîåííîå äèàãîíàëüíûì ìåòîäîì, êàê ïðàâèëî, îêàçûâàåòñÿ

âåñüìà äàëåêèì îò îïòèìàëüíîãî, òàê êàê ïðè åãî îïðåäåëåíèè

ñîâåðøåííî èãíîðèðóþòñÿ âåëè÷èíû çàòðàò ñ

. Ïîýòîìó òðåáó-

þòñÿ â äàëüíåéøèõ ðàñ÷åòàõ ìíîãî èòåðàöèé äëÿ äîñòèæåíèÿ îï-

òèìàëüíîãî ïëàíà. ×èñëî èòåðàöèé ìîæíî ñîêðàòèòü, åñëè èñõîä-

íûé ïëàí ñòðîèòü ïî áîëåå ðàöèîíàëüíîìó ïðàâèëó «ìèíèìàëü-

íîãî ýëåìåíòà». Ñóùíîñòü åãî ñîñòîèò â òîì, ÷òî íà êàæäîì øàãå

çàïîëíÿåòñÿ êëåòêà ñ íàèìåíüøåé âåëè÷èíîé ñ

. Åñëè òàêàÿ êëåò-

êà íå åäèíñòâåííàÿ, òî ëó÷øå çàïîëíÿòü òó, ïî âåðòèêàëè èëè ãî-

ðèçîíòàëè êîòîðîé âñòðå÷àþòñÿ áîëüøèå ñ

, à â ïðèíöèïå çàïîë-

íÿåòñÿ ëþáàÿ èç íèõ.

Ïóñòü ýòî áóäåò êëåòêà (i, j). Çàïèøåì â ýòó êëåòêó õ

= min (a

, b

Åñëè a

< b

, òî çàïàñû ïîñòàâùèêà À

èñ÷åðïàíû, à ïîòðåáíîñòü Â

ñòàëà

ijj

abb

−=

′

Ïîýòîìó, íå ïðèíèìàÿ áîëåå âî âíèìàíèå i-þ

ñòðîêó, ñíîâà èùåì êëåòêó ñ íàèìåíüøåé ñòîèìîñòüþ ïåðåâîçîê

è çàïîëíÿåì åå ñ ó÷åòîì èçìåíèâøèõñÿ ïîòðåáíîñòåé. Äëÿ ñëó÷àÿ

> b

èç ðàññìîòðåíèÿ èñêëþ÷àåòñÿ j-é ñòîëáåö, à çàïàñû À

ïîëà-

ãàþòñÿ ðàâíûìè

jii

baa

−=

′

Ïðîäîëæàåì ýòîò ïðîöåññ äî òåõ ïîð,

ïîêà âñå çàïàñû íå áóäóò èñ÷åðïàíû, à âñå ïîòðåáíîñòè  óäîâ-

ëåòâîðåíû. Íåîáõîäèìî îòìåòèòü, ÷òî ïðè íàëè÷èè â òàáëèöå

êëåòîê ñ îäèíàêîâûìè òàðèôàìè, ïëàíû, ïîëó÷åííûå ñ ïîìîùüþ

ýòîãî ìåòîäà, ìîãóò áûòü ðàçíûìè, îäíàêî îíè, íåñîìíåííî, áëè-

æå ê îïòèìàëüíîìó, ÷åì ïëàí, ñîñòàâëåííûé ïî ìåòîäó ñåâåðî-

çàïàäíîãî óãëà.

379

Ïðåæäå ÷åì ïåðåéòè ê àíàëèçó îïòèìàëüíîñòè ïëàíîâ è ñïî-

ñîáàì èõ óëó÷øåíèÿ, âûÿñíèì, êàêèì òðåáîâàíèÿì äîëæíû óäîâ-

ëåòâîðÿòü ñîñòàâëÿåìûå ïëàíû. Äëÿ ýòîãî âåðíåìñÿ ê ñèñòåìå îã-

ðàíè÷åíèé (7.5)  (7.7). Î÷åâèäíî, ÷òî ïåðâàÿ ãðóïïà óðàâíåíèé

òðåáóåò, ÷òîáû ñóììà ýëåìåíòîâ ïëàíà ïî i-é ñòðîêå ðàâíÿëàñü à

; ,1 mi =

à âòîðàÿ ãðóïïà  ÷òîáû ñóììà ýëåìåíòîâ ïî j-ìó ñòîëá-

öó áûëà ðàâíà b

. ,1 nj

Óñëîâèå çàêðûòîñòè ìîäåëè òðàíñïîðò-

íîé çàäà÷è îçíà÷àåò, ÷òî ñðåäè m + n óðàâíåíèé ñèñòåìû îãðàíè-

÷åíèé íåçàâèñèìûõ òîëüêî m + n  1, ïîýòîìó â ëþáîì áàçèñíîì

ðåøåíèè ýòîé ñèñòåìû äîëæíî áûòü m + n  1 áàçèñíûõ ïåðåìåí-

íûõ. Ïîñêîëüêó ñâîáîäíûå ïåðåìåííûå â òàêîì ðåøåíèè ðàâíû

íóëþ, òî â òðàíñïîðòíîé òàáëèöå èì áóäóò ñîîòâåòñòâîâàòü ïóñ-

òûå êëåòè.

Êëåòêè òàáëèöû, â êîòîðûõ çàïèñàíû îòëè÷íûå îò íóëÿ ïåðå-

âîçêè, íàçûâàþòñÿ áàçèñíûìè, à îñòàëüíûå (ïóñòûå)  ñâîáîä-

íûìè.

Â òåîðèè äîêàçàíî, ÷òî áàçèñíîå ðåøåíèå ñèñòåìû îãðàíè÷å-

íèé (7.5)  (7.7) â óñëîâèÿõ òðàíñïîðòíîé çàäà÷è äîëæíî èìåòü

m + n  1 áàçèñíûõ ïåðåìåííûõ.

Ïëàí íàçûâàåòñÿ âûðîæäåííûì, åñëè êîëè÷åñòâî áàçèñíûõ

êëåòîê â íåì ìåíüøå, ÷åì m + n  1.

Åñëè íà êàêîì-òî ýòàïå ðåøåíèÿ ïîëó÷èëñÿ âûðîæäåííûé

ïëàí, òî åãî íåîáõîäèìî ïîïîëíèòü, ïðîñòàâèâ â íåäîñòàþùåì

÷èñëå êëåòîê 0 è òåì ñàìûì îáúÿâèâ èõ áàçèñíûìè. Ïîñêîëüêó

ýòèì äîïîëíèòåëüíûì êëåòêàì áóäóò îòâå÷àòü íóëåâûå ïåðåâîç-

êè, òî îáùèé áàëàíñ è ñóììàðíàÿ ñòîèìîñòü ïåðåâîçîê ïëàíà ïðè

ýòîì íå èçìåíèòñÿ. Îäíàêî ïðîâîäèòü ïîïîëíåíèå ïëàíà, âûáè-

ðàÿ êëåòêè ïðîèçâîëüíî, íåëüçÿ. Ïðèâåäåì óñëîâèÿ, êîòîðûì äîë-

æåí ñîîòâåòñòâîâàòü ïîïîëíåííûé ïëàí.

Öèêëîì â òðàíñïîðòíîé òàáëèöå íàçûâàåòñÿ íåñêîëüêî êëå-

òîê, ñîåäèíåííûõ çàìêíóòîé ëîìàíîé ëèíèåé òàê, ÷òîáû äâå ñî-

ñåäíèå âåðøèíû ëîìàíîé áûëè ðàñïîëîæåíû ëèáî â îäíîé ñòðî-

êå, ëèáî â îäíîì ñòîëáöå. Ëîìàíàÿ ìîæåò èìåòü òî÷êè ñàìîïåðå-

ñå÷åíèÿ, íî íå â êëåòêàõ öèêëà.

Ïëàí íàçûâàåòñÿ àöèêëè÷åñêèì, åñëè åãî áàçèñíûå êëåòêè íå

ñîäåðæàò öèêëîâ.

Äîêàçàíî, ÷òî îïòèìàëüíûå ïëàíû ÿâëÿþòñÿ àöèêëè÷åñêèìè,

ïîýòîìó è ïåðâîíà÷àëüíûé ïëàí òàêæå äîëæåí óäîâëåòâîðÿòü ýòî-

ìó òðåáîâàíèþ. Çàìåòèì, ÷òî ïëàíû, ïîëó÷åííûå ñ ïîìîùüþ ìå-

380

òîäîâ ñåâåðî-çàïàäíîãî óãëà è íàèìåíüøåé ñòîèìîñòè, àöèêëè-

÷åñêèå. Îäíàêî åñëè ïëàí îêàçàëñÿ âûðîæäåííûì, òî ïðè åãî ïî-

ïîëíåíèè òðåáîâàíèå àöèêëè÷íîñòè íåîáõîäèìî ó÷èòûâàòü.

7.1.2.3. Îïòèìàëüíîñòü áàçèñíîãî ðåøåíèÿ.

Ìåòîä ïîòåíöèàëîâ

Ïîëó÷èâ ïåðâûé îïîðíûé ïëàí, ñëåäóåò ïðîâåðèòü åãî îïòè-

ìàëüíîñòü è, åñëè òðåáóåòñÿ, ïåðåéòè ê íîâîìó îïîðíîìó ïëàíó ñ

ëó÷øèì çíà÷åíèåì öåëåâîé ôóíêöèè Z. Äëÿ ýòîãî ïðèìåíÿþò ìå-

òîä ïîòåíöèàëîâ. Êàæäîìó ïîñòàâùèêó À

è êàæäîìó ïîòðåáèòå-

ëþ Â

ñîïîñòàâëÿþò, ñîîòâåòñòâåííî, âåëè÷èíû U

è V

 ïîòåí-

öèàëû ýòèõ ïóíêòîâ.

Äëÿ òîãî ÷òîáû íåêîòîðûé îïîðíûé ïëàí

|| *

òðàíñ-

ïîðòíîé çàäà÷è áûë îïòèìàëüíûì, íåîáõîäèìî è äîñòàòî÷íî,

÷òîáû åìó ñîîòâåòñòâîâàëà ñèñòåìà èç (m + n) ÷èñåë

óäîâ-

ëåòâîðÿþùèõ óñëîâèÿì:

 (U

+ V

) = 0 äëÿ x

≥ 0 (7.8)

(äëÿ çàíÿòûõ êëåòîê) è

) ,1 ; ,1( ,0)( njmiVUCC

jiijij

==≥+−=∆

(7.9)

(äëÿ ñâîáîäíûõ êëåòîê).

×èñëà

íàçûâàþòñÿ ïîòåíöèàëàìè ñîîòâåòñòâåííî ïðî-

èçâîäèòåëåé è ïîòðåáèòåëåé, âñÿ èõ ñèñòåìà  ïîòåíöèàëüíîé, à

óñëîâèÿ (7.8)  (7.9)  óñëîâèÿìè ïîòåíöèàëüíîñòè ñèñòåìû

}; ,{

êàæäîå â îòäåëüíîñòè íåðàâåíñòâî (ðàâåíñòâî) íàçûâà-

åòñÿ óñëîâèåì ïîòåíöèàëüíîñòè äëÿ ñîîòâåòñòâóþùåé êëåòêè (i, j).

Ïîñêîëüêó ÷èñëî íåèçâåñòíûõ ïîòåíöèàëîâ (m + n) âñåãäà íà

åäèíèöó áîëüøå ÷èñëà óðàâíåíèé (÷èñëà çàïîëíåííûõ êëåòîê)

N = m + n  1, òî âûáèðàåì ñòðîêó, ãäå åñòü çàíÿòàÿ êëåòêà

è äëÿ ýòîé ñòðîêè íàçíà÷àåì ïîòåíöèàë ðàâíûì íóëþ, íàïðè-

ìåð U

= 0, è ëåãêî íàõîäèì ïîñëåäîâàòåëüíî èç óðàâíåíèé (7.8)

çíà÷åíèÿ îñòàëüíûõ ïîòåíöèàëîâ.

Åñëè æå ÷èñëî çàïîëíåííûõ êëåòîê N < m + n  1, òî ââîäèì

äîïîëíèòåëüíî íåîáõîäèìîå êîëè÷åñòâî çàíÿòûõ êëåòîê ñ íóëå-