Matisch mathematische programuvannya - Nakonechny S.І.

5. ROZDІL Transportprobleme

"In allen Teilen der Welt

ihre eigenen, manchmal sogar sehr

andere Teile des neugierigen "

Works Prutkov

Transportproblem Je Arten von Problemen lіnіynogo programuvannya, Otzhe, її rozv'yazok mozhna otrimati zvichaynim Simplex - Methode. Allerdings deyakih vipadkah zastosuvannya unіversalnih algoritmіv Je neratsіonalnim. Spetsifіchna Struktur transportnoї zadachі daє zmogu otrimati alternative Methoden vіdshukannya optimalen Plan in viglyadі prostіshoї in porіvnyannі s Simplex-Methode obchislyuvalnoї Verfahren. Verkehrsprobleme nalezhit eingeben rozpodіlchih Aufgaben lіnіynogo programuvannya. Ekonomіchny zmіst solche Probleme Mauger stosuvatisya rіznomanіtnih Probleme scho perevazhno zovsіm nicht іz transportiert vantazhіv, Jak, napriklad, zadachі optimale rozmіschennya virobnitstva, skladіv optimale priznachennya Toscho pov'yazano. Deyakі s rozglyanemo solche Probleme in tsomu rozdіlі.

5.1. Ekonomichna i matisch mathematische Formulierung transportnoї zadachі

Klasichna Transportprobleme lіnіynogo programuvannya formulyuєtsya so: deyaky odnorіdny Produkt, scho in znahoditsya m postachalnikіv in obsyagah odinits vіdpovіdno neobhіdno n spozhivacham tragen in obsyagah odinits. Wenn tsomu vikonuєtsya Umov scho zagalny nayavny obsyag produktsії in postachalnikіv dorіvnyuє zagalnomu popitu vsіh spozhivachіv. Vіdomі vartostі transportiert odinitsі produktsії od Haut th postachalnika die Haut vj th spozhivacha, scho Yak podanі Elements Geist matritsі:

Neobhіdno viznachiti transportiert Plan für alle yakogo Produkciya Bula b Vivaise od postachalnikіv, povnіstyu zadovolenі erfordern spozhivachіv i Wert vsіh transportiert Bula b mіnіmalnoyu Summe.

In takіy postanovtsі zadachі efektivnіst Plan durch viznachaєtsya Yogo vartіstyu i taka Problem Got Titel transportnoї für kriterієm vartostі zadachі transportiert.

Zapishemo її matisch mathematischen Modell. Poznachimo durch obsyag produktsії scho transportiert od postachalnika up spozhivacha . Todі Köpfen zadachі zruchno Steuern haben viglyadі takoї tablitsі:

Tabelle 5.1

Spozhivachі

B1

B2

...

Bn

Postachalniki

b1

b2

...

bn

A1

a1

c11

x11

c12

x12

...

s1n

x1n

A2

a2

c21

x21

c22

x22

...

S2N

x2n

...

...

...

...

...

...

bin

und m

SM1

XM1

SM2

xm2

...

SMN

xmn

Mayutsya vikonuvatisya takі Köpfe:

  1. Sumarno obsyag produktsії scho vivozitsya Haut i-ten Artikel Got dorіvnyuvati Lager produktsії in danomu punktі:

  1. Sumarno obsyag produktsії, scho kutanen importiert j-ten spozhivachevі, Got Yogo dorіvnyuvati Notwendigkeit:

  1. Sumarno vartіst vsіh schuldig Buti mіnіmalnoyu transportiert:

Offensichtlich ist die scho .

In skorochenіy formі matisch mathematisches Modell der Aufnahme transportnoї für kriterієm vartostі zadachі transportiert Got Taqiy viglyad:

(5.1)

für obmezhen:

; (5.2)

; (5.3)

. (5.4)

In rozglyanutіy zadachі Got vikonuvatisya Umov:

. (5.5)

Verkehrsprobleme nazivayut zbalansovanoyu, Closed-abo, Yakscho vikonuєtsya Umov (5.5). Gut Yakscho taka Umov nicht vikonuєtsya, das Transportproblem nazivayut nezbalansovanoyu, abo vіdkritoyu.

Domovimosya bis transportnoї zadachі nazivati ob yaky nevіd'єmny rozv'yazok Sistemi obmezhen (5.2) - (5.4), yaky poznachayut Matrix . Bedeutung nevіdomih Werte - Obsyagi produktsії scho Mühe Buti perevezenі od i- x postachalnikіv bis j -x spozhivachіv, nazivatimemo transportiert.

Optimal Plan transportnoї zadachі nazivayut Matrix Yak, zadovolnyaє Köpfe zadachі, i für yakoї tsіlova funktsіya (5.1) nabiraє naymenshogo Werte.

Satz (Umov іsnuvannya rozv'yazku transportnoї zadachі): i neobhіdnoyu dostatnoyu Köpfen іsnuvannya rozv'yazku transportnoї zadachі (5.1) - (5.4) Je її zbalansovanіst: .

GEBRACHT. Neobhіdnіst. Nekhay Problem (5.1) - (5.4) Got rozv'yazok , Todі für Demba vikonuyutsya rіvnyannya-obmezhennya (5.2) i (5.3). Pіdsumuєmo vіdpovіdno lіvі die Chastain rіvnyan Systeme pravі (5.2) i (5.3). Matimemo:

, (5.6)

(5.7)

Oskіlki lіvі Chastain rіvnyan (5.6), dass (5.7) zbіgayutsya dann pravі takozh rіvnі ein odnіy, Otzhe, vikonuєtsya Umov:

. (5.8)

Dostatnіst. Potrіbno Show, scho für zadanoї Minds (5.8) b іsnuє Hoca ein zadachі Plan i tsіlova funktsіya auf mnozhinі planіv obmezhena.

Nekhay = W> 0 Die Größe Rozglyanemo ( ). Pіdstavivshi Werte in obmezhen zadachі (5.1) - (5.4) matimemo:

;

.

Oskіlki Minds (5.2), dass (5.3) vikonuyutsya, die Je-up navedenoї transportnoї zadachі.

Viberemo s elementіv naybіlshe Werte i durch poznachimo yogo . Yakscho zamіniti in tsіlovіy funktsії (5.1) an OAO Alle koefіtsієnti Dann vrahovuyuchi (5.2), matimemo:

.

Viberemo s elementіv naymenshe Werte i durch poznachimo yogo . Yakscho zamіniti in tsіlovіy funktsії (5.1) an OAO Alle koefіtsієnti Dann vrahovuyuchi (5.2), matimemo:

.

Tobto tsіlova funktsіya auf mnozhinі Zulässigkeit planіv transportnoї zadachі Je obmezhenoyu:

.

Satz gebracht.

Yakscho bei perevіrtsі zbalansovanostі (5.5) viyavilosya scho Ja vіdkritoyu Transportproblem, dann її neobhіdno Zvesti zu Closed-Typ. Tse zdіysnyuєtsya Einführung fіktivnogo (umovnogo) postachalnika in razі perevischennya zagalnogo popitu über Bestände іz Ressource obsyagom . Yakscho Gut zagalnі Reserven postachalnikіv perevischuyut Popit spozhivachіv Dann auf die Closed-Typ Aufgabe zvoditsya Einführung fіktivnogo (umovnogo) spozhivacha s erfordern .

Vartіst transportiert odinitsі produktsії od fіktivnogo postachalnika (Abo fіktivnogo spozhivacha Vor) Haut Zi spozhivachіv (virobnikіv) Got dorіvnyuvati Null abo Buti nabagato bіlshoyu für realnі vitrati . Yak Regel solche razі vikoristovuyut nulovі Werte vartostey transportiert scho daє zmogu sprostiti obchislennya.

Yak zgaduvalosya Vische, Transportproblem (5.1) - (5.4) Je zvichaynoyu Aufgaben lіnіynogo programuvannya i Mauger Buti rozv'yazana Simplex-Methode, aber osoblivostі pobudovi matematichnoї modelі transportnoї zadachі geben zmogu rozv'yazati її prostіshe. Leicht pomіtiti scho OAO Alle koefіtsієnti bei zmіnnih in rіvnyannyah (5.2) (5.3) dorіvnyuyut odinitsі, und das System selbst obmezhen (5.2), (5.3) wird in kanonіchnіy formі gegeben. Krіm von obmezhen System (5.2) (5.3) Mio. nevіdomih skladaєtsya s , dass m + n rіvnyan, SSMSC pov'yazanі ihn spіvvіdnoshennyam mіzh (5.8). Yakscho Ihre vіdpovіdno pravі hinzufügen, die Chastain rіvnyan Systeme lіvі (5.2), dass (5.3), die zwei otrimaєmo odnakovih rіvnyannya:

;

.

Nayavnіst in sistemі obmezhen dvoh odnakovih rіvnyan svіdchit über її lіnіynu zalezhnіst. Yakscho odne s Tsikh rіvnyan vіdkinuti, die zagalnomu vipadku System obmezhen bude mіstiti m + n - 1 lіnіyno Platz rіvnyannya, Otzhe, їh mozhna rozv'yazati vіdnosno m + n - 1 Grund zmіnnih. Nazvemo Förderprogramm transportnoї zadachі Taqiy Zulässigkeit її Plan scho mіstit nicht bіlsh nіzh m + n - 1 dodatnih Komponente und OAO Alle INSHI Yogo Komponenten dorіvnyuyut Null. Taqiy Plan Je nevirodzhenim. Nun Yakscho Anzahl der Basis zmіnnih Mensch nіzh m + n - 1, dann virodzheny Förderprogramms maєmo.