Haupt- Andere Disziplinen Bücher Matisch mathematische programuvannya - Nakonechny S.І. |
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 Aі 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 Aі 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:
- Sumarno obsyag produktsії scho vivozitsya Haut i-ten Artikel Got dorіvnyuvati Lager produktsії in danomu punktі:
- Sumarno obsyag produktsії, scho kutanen importiert j-ten spozhivachevі, Got Yogo dorіvnyuvati Notwendigkeit:
- 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.
Kommentare
im Auge kommentierte halten , dass der Inhalt und der Ton Ihrer Nachrichten , die Gefühle von echten Menschen verletzen können, Respekt und Toleranz gegenüber seinen Gesprächspartnern, auch wenn Sie Ihr Verhalten in Bezug auf die Meinungsfreiheit und die Anonymität des Internets, ändert ihre Meinung nicht teilen, nicht nur virtuell, sondern realen Welt. Alle Kommentare werden aus dem Index, Spam - Kontrolle versteckt.