Seda võetakse transpordi transpordi optimaalsuse kriteeriumina. Objektiivsed funktsioonid

Arvestustöö nr 4: TRANSPORTPROBLEEM

Transpordiprobleemi üldine sõnastus on määrata kindlaks optimaalne plaan mõne homogeense kauba transportimiseks lähtepunktidest (tootmine) sihtpunkti (tarbimiseni). Sellisel juhul võetakse optimaalsuse kriteeriumiks tavaliselt kas kogu veose transpordi minimaalne maksumus või minimaalne selle kohaletoimetamise aeg. Vaatleme transpordiprobleemi, mille optimaalsuse kriteeriumiks on kogu veose transpordi minimaalne maksumus. Tähistagem kaubaühiku transportimise tariifidega -ndast lähtepunktist -ndasse sihtpunkti, - kaubavaru -ndas lähtepunktis, - kaubavajadusega -ndas lähtepunktis. sihtpunkt ja - kaubaühikute arv, mis veetakse -ndast lähtepunktist sihtkohta. Tavaliselt kirjutatakse transpordiülesande lähteandmed tabeli kujul.

tootmine	Tarbimispunktid				tootmine
tarbija

Koostame ülesande matemaatilise mudeli.

(1)

piirangute all

Kutsutakse plaani, milles funktsioon (1) võtab oma minimaalse väärtuse optimaalne plaan transpordi ülesanne.

Transpordiprobleemi lahendatavuse tingimus

Teoreem: Transpordiprobleemi lahendamiseks on vajalik ja piisav, et lähtepunktide kaubavarud võrduvad kauba nõudlusega sihtpunktides, s.t et võrdsus oleks

Sellise transpordiprobleemi mudelit nimetatakse suletud, või suletud, või tasakaalustatud, muidu nimetatakse mudelit avatud.

Kui tegemist on fiktiivne - vajadusega sihtkohta ; samamoodi, kui võetakse kasutusele fiktiivne lähtepunkt koos kaubareserviga ja vastavad tariifid loetakse võrdseks nulliga: . See taandab ülesande tavapäraseks transpordiprobleemiks. Järgnevalt käsitleme transpordiprobleemi suletud mudelit.

Lähte- ja sihtpunktidega transpordiprobleemi muutujate arv on võrdne ja võrrandite arv süsteemis (2)-(4) on . Kuna eeldame, et tingimus (5) on täidetud, on lineaarselt sõltumatute võrrandite arv võrdne . Seetõttu ei saa võrdlusdisainil olla rohkem kui null tundmatut. Kui võrdlusplaanis on nullist erinevate komponentide arv täpselt võrdne , siis plaanitakse välja kutsuda mitte-mandunud, ja kui vähem, siis degenereerunud.

Esialgse võrdlusplaani koostamine

Võrdlusplaani määramiseks on mitu meetodit: meetod loodenurk (diagonaal meetod), meetod kõige vähem kulu (minimaalne element), meetod kahekordne eelistus ja meetod Vogeli lähendus.

Vaatame lühidalt igaüks neist.

1.Loodenurga meetod. Võrdlusplaani leidmisel arvestatakse igal sammul esimest ülejäänud lähtepunktidest ja esimest ülejäänud sihtkohtadest. Tingimuste tabeli lahtrite täitmine algab tundmatu jaoks ülemisest vasakpoolsest lahtrist (“loodenurk”) ja lõpeb tundmatu lahtriga, s.o. justkui diagonaalselt üle laua.

2. Väikseima kulu meetod. Meetodi olemus seisneb selles, et kogu kulude tabelist valitakse välja väikseim ja sellele vastavasse lahtrisse paigutatakse numbritest väiksem ja seejärel kas tarnijale vastav rida, kelle varud on täielikult ära kasutatud. , või veerg, mis vastab tarbijale, kelle vajadused on täielikult rahuldatud, või nii rida kui ka veerg, kui tarnija varud on ammendatud ja kliendi vajadused rahuldatud. Ülejäänud kulutabeli hulgast valitakse taas madalaim maksumus ja varude jaotamise protsess jätkub, kuni kõik varud on jaotatud ja nõuded täidetud.

3. Kahekordse eelistuse meetod. Meetodi olemus on järgmine. Märgistage igas veerus madalaima kuluga lahter √-märgiga. Seejärel tehakse sama igas reas. Selle tulemusena on mõned lahtrid tähistatud "√√". Need sisaldavad minimaalset kulu nii veergude kui ka ridade kaupa. Nendesse lahtritesse paigutatakse maksimaalsed võimalikud liiklusmahud, jättes iga kord vastavaid veerge või ridu arvesse võtmata. Seejärel jaotatakse transport lahtrite vahel, mis on tähistatud “√”-ga. Ülejäänud tabelis on transport jaotatud madalaima maksumuse järgi.

4. Vogeli lähendamise meetod. Selle meetodi abil võrdlusplaani määramisel leitakse igal iteratsioonil kõigis veergudes ja kõikides ridades nendes kirjutatud kahe minimaalse tariifi erinevus. Need erinevused sisestatakse ülesande tingimuste tabelis spetsiaalselt määratud reale ja veergu. Näidatud erinevuste hulgast valitakse maksimum. Reas (või veerus), millele see erinevus vastab, määratakse minimaalne tariif. Lahter, kuhu see on kirjutatud, täidetakse selle iteratsiooniga.

Optimaalsuse kriteeriumi määramine

Kasutades esialgse toetusplaani koostamiseks kaalutletud meetodeid, saate hankida degenereerunud või mitte-mandunud tugiplaani. Transpordiprobleemi kui lineaarse programmeerimisülesande konstrueeritud plaani saab optimaalseks viia simpleksmeetodi abil. Kuid sisaldavate simplekstabelite kohmakuse tõttu tp tundmatute ja suure hulga arvutustööga, kasutatakse optimaalse plaani saamiseks lihtsamaid meetodeid. Kõige sagedamini kasutatav meetod on potentsiaalne meetod (modifitseeritud jaotusmeetod).

Potentsiaalne meetod.

Potentsiaalne meetod võimaldab kindlaks määrata, lähtudes kindlast etalontranspordiplaanist, konstrueerida transpordiprobleemi lahendus lõplike sammude (iteratsioonide) kaupa.

Selle meetodi abil transpordiprobleemi optimaalse plaani määramise üldpõhimõte sarnaneb lineaarse programmeerimisülesande lahendamise põhimõttele simpleksmeetodi abil, nimelt: kõigepealt leitakse transpordiprobleemi võrdlusplaan ja seejärel tehakse see järjestikku. optimaalse plaani saamiseni.

Loome topeltprobleemi

1. - ükskõik milline

3.

Las olla plaan

Teoreem(optimaalsuse kriteerium): selleks, et transpordiprobleemi puhul oleks vastuvõetav transpordiplaan optimaalne, on vajalik ja piisav, et on olemas arvud , , sellised,

Kui. (7)

numbrid ja nimetatakse vastavalt lähte- ja sihtpotentsiaalideks.

Sõnastatud teoreem võimaldab koostada algoritmi transpordiprobleemile lahenduse leidmiseks. See on järgmine. Laske võrdlusplaan leida, kasutades ühte ülalkirjeldatud meetoditest. Selle plaani jaoks, milles on põhielemendid, on võimalik määrata potentsiaalid nii, et tingimus (6) on täidetud. Kuna süsteem (2)-(4) sisaldab võrrandeid ja tundmatuid, saab neist ühe suvaliselt seada (näiteks nulliga võrdseks). Pärast seda määratakse ülejäänud potentsiaalid võrranditest (6) ja arvutatakse väärtused iga vaba lahtri jaoks. Kui nii selgub, on plaan optimaalne. Kui vähemalt ühes vabas lahtris, siis plaan ei ole optimaalne ja seda saab parandada, kandes seda läbi sellele vabale lahtrile vastava tsükli.

Tsükkel transpordiprobleemi tingimuste tabelis nimetatakse katkendjoont, mille tipud asuvad tabeli hõivatud lahtrites ning lingid piki ridu ja veerge ning tsükli iga tipu juures on täpselt kaks linki, millest üks on reas ja teine ​​veerus. Kui tsükli moodustav katkendjoon lõikub, siis iselõikepunktid ei ole tipud.

Plaani täiustamise protsess jätkub, kuni tingimused (7) on täidetud.

Näide transpordiprobleemi lahendamisest.

Ülesanne. Neli baasi A 1, A 2, A 3, A 4 said homogeenset lasti järgmistes kogustes: a 1 tonn - baasi A 1 ja 2 tonni - baasi A 2 ja 3 tonni - baasi A 3 ja 4 tonni - baasi A 4. Vastuvõetud veos tuleb transportida viide punkti: b 1 tonni - baasi B 1, b 2 tonni - baasi B 2, b 3 tonni - baasi B 3, b 4 tonni - baasi B 4, b 5 tonni - baasi B5. Sihtkohtade vahelised kaugused kuvatakse kaugusmaatriksis.

lähtepunktid	sihtkohad
vajadustele

Transpordi maksumus on proportsionaalne kauba koguse ja vahemaaga, mille jooksul seda lasti transporditakse. Planeerige transport nii, et selle kogumaksumus oleks minimaalne.

Lahendus. Kontrollime transpordiprobleemi tasakaalu selleks on vaja, et

, .

1. Lahendage ülesanne diagonaalmeetodil või loodenurga meetodil.

Plaani saamise protsessi saab esitada tabeli kujul:

lähtepunktid

Transpordiprobleemi üldine sõnastus seisneb optimaalse plaani kindlaksmääramises mõne homogeense kauba transportimiseks. m lähtekohad (tarnijad) A1, A2, . . ., A m V n tarbimispunktid (tarbijad) B1, B2, . . . Bn nii, et:

Eemaldage tarnijatelt kogu last;

Rahuldage iga tarbija nõudlus;

Tagada minimaalsed transpordi kogukulud kõigi kaupade transportimisel.

Mõelge transpordiprobleemile kui optimaalsuse kriteerium, mis kasutab kogu veose transpordi minimaalset kulu.

Tähistame:

ai - kauba olemasolu i -th lähtepunkt https://pandia.ru/text/78/103/images/image205_0.gif" width="81" height="27 src=">;

сij - kaubaühiku transpordi maksumus i th lähtepunkt kl j tarbimiskoht (transporditariif);

xij - alates veetud kauba kogus i th lähtepunkt kl j sihtkoht, sihtkoht, xij ≥ 0.

Transpordiprobleemi matemaatiline sõnastus seisneb mittenegatiivse lahenduse leidmises lineaarvõrrandisüsteemile, milles sihtfunktsioon võtab minimaalse väärtuse.

Kirjutame üles transpordiülesande matemaatilise mudeli.

On vaja määrata maatriks ), mis vastab järgmistele tingimustele:

https://pandia.ru/text/78/103/images/image210_0.gif" width="74" height="45">.gif" width="47" height="21">.gif" width= "63" height="20"> (5,3)

ja annab sihtfunktsiooni minimaalse väärtuse

L () = https://pandia.ru/text/78/103/images/image215_0.gif" width="36" height="24"> rahuldavad lineaarvõrrandisüsteemi (5.1), (5.2) ja mittenegatiivsuse tingimus, See tagab igale tarbijale vajaliku kauba kohaletoimetamise, olemasoleva kauba eemaldamise kõigilt tarnijatelt ja välistab ka tagasiveo.

Definitsioon 1. Lineaarvõrrandisüsteemide (5.1) ja (5.2) mittenegatiivset lahendust, mis on määratletud maatriksiga ), nimetatakse transpordiprobleemi teostatav plaan.

Definitsioon 2. Plaan) https://pandia.ru/text/78/103/images/image218_0.gif" width="23" height="24">, mida nimetatakse põhi- või referentsiks.

4. määratlus. Kui võrdlusplaanis on mitu nullist erinevat muutuja väärtust>https://pandia.ru/text/78/103/images/image219_0.gif" width="55" height="22">.gif " width="55" height ="22"> > , sisestatakse väljamõeldud (n+ 1) sihtkoht koos nõudega miljardit+1 = − https://pandia.ru/text/78/103/images/image221_0.gif" width="83 height=22" height="22">

Kui< https://pandia.ru/text/78/103/images/image220_0.gif" width="56 height=25" height="25">.gif" width="79" height="22 src=">

Vaatleme üht transpordiprobleemi esimese referentsplaani koostamise meetodit – minimaalse kulu meetodit ehk ühikukulu maatriksi parimat elementi.

Definitsioon 6. Ühikukulude (tariifide) maatriksi parimaks elemendiks on väikseim tariif, kui ülesanne on seatud sihtfunktsiooni miinimumile, kõrgeim tariif - kui ülesanne on seatud maksimumile.

Algoritm esimese võrdlusplaani koostamiseks.

1. Ühikukulude maatriksi hulgast leiame parima tariifi.

2. Täida jaotustabeli lahter valitud tariifiga maksimaalse võimaliku kaubamahuga, arvestades rea- ja veerupiiranguid. Sel juhul eemaldatakse tarnijalt kogu veos või rahuldatakse tarbija vajadused täielikult. Tabeli rida või veerg jäetakse kaalumisest välja ja ei osale edasises levitamises.

3. Ülejäänud tariifide hulgast valime uuesti välja parima ja protsess jätkub seni, kuni kogu veos on laiali jagatud.

Kui transpordiprobleemi mudel on avatud ja kasutusele võetakse fiktiivne tarnija või tarbija, siis toimub esmalt jaotus tegelikele tarnijatele ja tarbijatele ning viimasena suunatakse jaotamata veos fiktiivselt tarnijalt või fiktiivsele tarbijale.

Täiustame transpordiprobleemi esimest referentsplaani veelgi ja saame potentsiaalse meetodi abil optimaalse plaani.

3. teoreem . Transpordiülesande plaan ) on optimaalne, kui on olemas arvude ui ja vj (nimetatakse potentsiaalideks) süsteem (m + n), mis vastab tingimustele:

(5.6)

(5.7)

Potentsiaalid ui ja vj on algsest transpordiprobleemist koosneva duaalprobleemi muutujad ning tähistavad kaubaühiku hindamist vastavalt lähte- ja sihtpunktis.

Tähistame: ) vaba (tühja) tabelilahtri hinnangut.

Definitsioon 7. Transpordiprobleemi võrdlusplaan on optimaalne, kui jaotustabeli vabade lahtrite kõik hinnangud (ülesanne on seatud miinimumini).

Potentsiaalse meetodi algoritm

1. Esimese võrdlusplaani koostamine transpordiprobleem minimaalse kulu meetodil.

2. Plaani degeneratsiooni kontrollimine .

Potentsiaale saab arvutada ainult mitte-mandunud plaani jaoks. Kui võrdlusplaani hõivatud lahtrite arv (põhimuutujate arv) on väiksem kui (m+n−1), siis sisestame tabeli ühte vabasse lahtrisse nulli, nii et hõivatud lahtrite koguarv saab võrdseks (m+n−1). Null sisestatakse parima tariifiga lahtrisse, mis kuulub reale või veergu. Esimese võrdlusplaani koostamisel samaaegselt läbi kriipsutatud. Sel juhul ei tohiks fiktiivselt nulliga hõivatud tabelilahter moodustada suletud ristkülikukujulist kontuuri teiste hõivatud tabeli lahtritega.

3. Eesmärgi funktsiooni väärtuse arvutamine (5.4) summeerides tariifide (ühikuhinna) korrutised veetud kauba mahuga tabeli kõigi hõivatud lahtrite kohta.

4. Plaani optimaalsuse kontrollimine.

Me määrame potentsiaalid. Iga hõivatud lahtri jaoks kirjutame üles võrrandi, mille tulemusena saame (m + n−1) võrrandite süsteemi (m + n) muutujatega.

Kuna muutujate arv on suurem kui võrrandite arv, ei ole saadud süsteem defineeritud ja sellel on lõpmatu arv lahendeid..gif" width="70" height="22">, siis määratakse ülejäänud potentsiaalid üheselt, ja nende väärtused sisestatakse jaotustabelite lisareale ja veergu.

Iga vaba lahtri jaoks määrame hinnangud https://pandia.ru/text/78/103/images/image233.gif" width="72 height=24" height="24">(probleem on lahendatud sihtfunktsiooni miinimum), siis leitakse optimaalne plaan Kui vähemalt üks vaba lahtri hinnang ei rahulda optimaalsuse tingimust, siis on vaja plaani parandada koormuse ümberjagamisega.

5.

Kõigist vabade rakkude positiivsetest hinnangutest valime suurima (ülesanne on seatud miinimumini); kõigist negatiivsetest – absoluutväärtuselt suurim (ülesanne seatakse maksimumile). Kõrgeimale punktisummale vastav lahter tuleks täita, st koorem tuleb sinna saata. Valitud lahtri täitmisega on vaja muuta mitmes teises hõivatud lahtris registreeritud ja täidetavaga seotud varustuse mahtu, nn tsüklit.

Tsükkel ehk ristkülikukujuline kontuur transpordiülesande jaotustabelis on katkendjoon, mille tipud asuvad tabeli hõivatud lahtrites ning lingid piki ridu ja veerge ning igas tabeli tipus. tsüklis on täpselt kaks linki, millest üks on real, teine ​​veerus . Kui tsükli moodustav katkendjoon lõikub, siis ei ole lõikepunktid tipud. Iga vaba raku jaoks saab konstrueerida ühe tsükli.

Tsükli tippudele, alustades laadimiseks valitud lahtris asuvast tipust, omistatakse vaheldumisi märgid “+” ja “−”. Nimetame neid lahtreid plussiks ja miinuseks.

Miinuslahtrites olevate kaubamahtude hulgast valime väikseima ja tähistame seda θ. Jaotame θ väärtuse mööda kontuuri ümber, lisades θ plusslahtrites olevatele vastavatele kaubamahtudele ja lahutades θ tabeli miinus lahtrites olevatest kaubamahtudest. Selle tulemusena hõivatakse vaba ja laadimiseks valitud lahter ning üks kontuuri hõivatud lahtrist saab vabaks.

Kontrollime saadud võrdlusplaani optimaalsust, st naaseme algoritmi neljandasse etappi.

Märkmed.

1. Kui konstrueeritud tsükli miinuslahtrid sisaldavad kahte või enamat identset miinimumväärtust, siis kaubamahtude ümberjaotamisel ei vabastata mitte üks, vaid kaks või enam lahtrit. Sel juhul muutub plaan taandarenguks. Lahenduse jätkamiseks on vaja hõivata üks või mitu tabeli üheaegselt vabastatud lahtrit nulliga ja eelistatakse parima tariifiga lahtreid. Sisestatakse nii palju nulle, et äsja saadud võrdlusplaanis on hõivatud lahtrite (põhimuutujate) arv täpselt (m + n−1).

2. Kui transpordiülesande optimaalses plaanis on mõne vaba lahtri hinnang võrdne nulliga), siis on ülesandel palju optimaalseid plaane. Nullskooriga lahtri jaoks saate luua tsükli ja koormuse ümber jaotada. Selle tulemusena on saadud plaan ka optimaalne ja sellel on sama sihtfunktsiooni väärtus.

3. Sihtfunktsiooni väärtuse igal iteratsioonil saab arvutada järgmiselt:

(ülesanne on seatud miinimumini),

(ülesanne on seatud maksimumile),

kus on mööda kontuuri teisaldatud lasti maht;

Vaba lahtri hinnang, kuhu koormus uuele võrdlusplaanile üleminekul suunatakse;

− eesmärgifunktsiooni väärtus k-ndas iteratsioonis;

− eesmärgifunktsiooni väärtus eelmisel iteratsioonil.

Näide.

Hulgimüügibaasi kolmes laos on homogeensed kaubad koguses 40, 80 ja 80 ühikut. Seda lasti tuleb transportida nelja kauplusesse, millest igaüks peab vastu võtma vastavalt 70, 20, 60 ja 60 ühikut. Tarnekulud kaubaühiku kohta (tariifid) igast laost ) kõikidesse kauplustesse ) on antud maatriksiga .

Koostada homogeense kauba vedamise plaan minimaalsete transpordikuludega (tingimuslikud numbrid).

Lahendus.

1. Kontrollime probleemi lahendamiseks vajalikku ja piisavat tingimust:

40+80+80 = 200,

70+20+60+60 = 210.

Nagu näete, ületab kauba kogunõudlus hulgimüügibaasi ladudes olevaid varusid. Sellest tulenevalt on transpordiprobleemi mudel avatud ja sellel puudub algsel kujul lahendus. Kinnise mudeli saamiseks võtame kasutusele täiendava (fiktiivse) lao A4, mille kaubavaru on võrdne A 4 = 210 – 200 = 10 ühikut. Eeldame, et kaubaühiku transportimise tariifid laost A4 kõikidesse kauplustesse on võrdsed nulliga.

Sisestame kõik algandmed tabelisse 7.

						Reservid
	A 1
	A 2		3
	A 3
	A 4
Vajadused					210 210

2. Esimese võrdlusplaani koostamine minimaalse kulu meetodil.

Tariifide hulgas on minimaalne või parim C14 = 1. Saadame lahtrisse A1B4 maksimaalse võimaliku koormuse, mis võrdub min(60,40) = 40. Seejärel x 14 = 40. Laost A1 on kõik kaubad välja viidud, kuid neljanda kaupluse nõudlus on 20 ühiku võrra rahuldamata. rida A1 ei võeta arvesse.

Ülejäänud tariifide hulgas on minimaalne element C23 = 2. Kauba min(60,80) = 60 saadame lahtrisse A2B3 Sel juhul ei arvestata veergu B3 ning laost A2 on eemaldamata 20 ühikut.

Ülejäänud elementidest on miinimum C22 = 3. Lahtrisse A2B2 saadame koormuse summas min(20,20) = 20. Sel juhul kriipsutatakse läbi rida A2 ja veerg B2 üheaegselt.

Valime minimaalse elemendi C31 = 4. Saadame koormuse, mis on võrdne min(70,80) = 70, lahtrisse A3B1 Sel juhul jäetakse veerg B1 arvestamata ja laost A3 pole eemaldatud 10 ühikut. Ülejäänud kauba saadame kolmandast laost kraaniavasse A3B4, x 34 = 10. Neljanda poe nõudlust ei rahuldata 10 ühiku võrra. saadame 10 ühikut fiktiivselt tarnijalt - laost A4. lasti kambris A4B4, x 44 = 10.

Selle tulemusel saadakse esimene võrdlusplaan, mis on vastuvõetav, kuna kogu veos on ladudest välja viidud ja kõigi kaupluste vajadused on rahuldatud.

3. Plaani degeneratsiooni kontrollimine.

Esimeses võrdlusplaanis on hõivatud lahtrite või baasmuutujate arv kuus. transpordiprobleemi plaan on degenereerunud, kuna mitte-mandunud plaanis on põhimuutujate arv võrdne m + n – 1 = 4 + 4 – 1 = 7. Ülesande lahendamise jätkamiseks tuleb võrdlusplaani täiendada fiktiivse transpordi kasutuselevõtuga, st hõivata üks vabadest nulli lahtritega.

Esimese võrdlusplaani koostamisel tõmmati rida A2 ja veerg B2 üheaegselt läbi, mistõttu plaan taandus. Fiktiivse transpordi õigust nõuavad rea A2 ja veeru B2 vabad lahtrid, millel on miinimumtariif ja mis ei moodusta hõivatud lahtritega suletud ristkülikukujulist kontuuri. Sellised rakud on A2B4 ja A3B2. Me suuname nulli lahtrisse A2B4.

4. Sihtfunktsiooni väärtuse arvutamine.

Esimese võrdlusplaani sihtfunktsiooni väärtus määratakse kõigi tabeli hõivatud lahtrite tariifide ja veetava lasti mahtude korrutiste liitmisel.

L(X1) = 4∙70 + 3∙20 + 2∙60 + 1∙40 + 3∙0 + 6∙10 + 0∙10 = 560 (tuhat rubla).

5. Optimaalse seisundi kontrollimine.

Arvutame tabeli hõivatud lahtrite potentsiaalid tingimuse järgi: https://pandia.ru/text/78/103/images/image260_0.gif" width="139" height="22">Alates teadmata arvust potentsiaal on suurem kui võrrandite arv (m + n > m + n – 1), siis võtame ühe potentsiaalidest, mis on võrdne nulliga..gif" width="115 height=154" height="154">

Eeldusel, et saame https://pandia.ru/text/78/103/images/image265_0.gif" width="82" height="22">, ,https://pandia.ru/text/78/103 / images/image268_0.gif" width="193" height="22">

Arvutatud potentsiaalid sisestame tabelisse 7. Arvutame vabade rakkude hinnangud.

https://pandia.ru/text/78/103/images/image270_0.gif" width="167" height="22 src=">,

https://pandia.ru/text/78/103/images/image272_0.gif" width="210" height="22 src=">,

https://pandia.ru/text/78/103/images/image274_0.gif" width="183" height="22 src=">,

https://pandia.ru/text/78/103/images/image276_0.gif" width="153" height="22 src=">,

Esimene võrdlusplaan ei ole optimaalne, kuna vabade lahtrite ja rakkude kohta on positiivsed hinnangud. Valime vaba lahtri maksimaalse positiivse hinnangu - .

6. Uue võrdlusplaani koostamine.

Lahtri A3B2 jaoks konstrueerime ristkülikukujulise suletud vooluringi (0 tabel 7) ja jaotame koormuse ahelale ümber. Kontuuri tippudele, alustades vabas lahtris A3B2 asuvast tipust, omistatakse vaheldumisi märgid “+” ja “−”.

Miinuslahtrites olevatest kaubamahtudest valige väikseim, st θ = min(20,10) = 10. Lisage plusslahtrites olevatele lastimahtudele väärtus θ = 10, lahutage lastimahtudest miinuslahtrites suletud silmus. Selle tulemusena saame uue võrdlusplaani, mis on näidatud tabelis 8.

Eelmises lõigus öeldu põhjal on järgmine: transpordiprobleemi põhilahenduse optimaalsuse kriteerium: kui mõne põhilise transpordiplaani puhul on kõikide vabade rakkude tsüklite algebralised tariifide summad mittenegatiivsed, siis on see plaan optimaalne.

See eeldab meetodit transpordiprobleemi optimaalse lahenduse leidmiseks, mis seisneb selles, et mõne põhilahenduse olemasolul arvutavad nad kõigi vabade rakkude tariifide algebralised summad. Kui optimaalsuse kriteerium on täidetud, on see lahendus optimaalne; kui on negatiivsete algebraliste tariifide summadega lahtreid, liiguvad need uuele alusele, arvutades ümber vastavalt ühele sellisele lahtrile vastava tsükli järgi. Sel viisil saadud uus põhilahendus tuleb parem kui algne - selle rakendamise kulud on väiksemad. Uue lahenduse puhul kontrollitakse ka optimaalsuse kriteeriumi teostatavust ja vajadusel tehakse uuesti tsükli ümberarvutus ühele negatiivse algebralise tariifide summaga lahtrile jne.

Lõpliku arvu sammude järel jõuavad nad soovitud optimaalse põhilahenduseni.

Kui kõigi vabade rakkude tariifide algebralised summad on positiivsed, on meil ainulaadne optimaalne lahendus; kui kõigi vabade lahtrite algebralised tariifide summad on mittenegatiivsed, kuid nende hulgas on nulliga võrdseid tariifide algebralisi summasid, siis pole optimaalne lahendus ainus: tsükli kaudu nullalgebralise lahtri jaoks ümber arvutades tariifide summa, saame sama optimaalse lahenduse, kuid erineb algsest (mõlema plaani kulud on samad).

Sõltuvalt vabade rakkude tariifide algebraliste summade arvutamise meetoditest on transpordiprobleemile optimaalse lahenduse leidmiseks kaks meetodit:

Jaotusmeetod. Selle meetodi abil ehitatakse iga tühja lahtri jaoks tsükkel ja iga tsükli jaoks arvutatakse otse tariifide algebraline summa.

Potentsiaalide meetod. Selle meetodiga leitakse esmalt baaside ja tarbijate potentsiaalid ning seejärel arvutatakse potentsiaalide abil iga tühja lahtri jaoks algebraline tariifide summa.

Potentsiaalse meetodi eelised võrreldes jaotusmeetodiga seisnevad selles, et iga tühja lahtri jaoks pole vaja tsükleid konstrueerida ning tariifide algebraliste summade arvutamine on lihtsam. Ehitatakse ainult üks tsükkel - see, mille abil ümberarvutus tehakse.

Potentsiaalset meetodit kasutades ei saa rääkida tariifide algebraliste summade märgist, vaid kaudsete tariifide võrdlemisest tõelistega. Nõue, et tariifide algebralised summad oleksid mittenegatiivsed, asendatakse tingimusega, et kaudsed tariifid ei ületa tõelisi.

Tuleb meeles pidada, et potentsiaalid (nagu ka tsüklid) määratakse iga uue baasjoone jaoks uuesti.

Eespool käsitlesime transpordiprobleemi suletud mudelit, õige tasakaaluga, kui tingimus (1.3) on täidetud. Kui (1.4) (avatud mudel) on täidetud, võib transpordiülesande tasakaal rikkuda kahes suunas:

1. Varude kogus lähtepunktides ületab esitatud taotluste koguse (ülevarudega transpordiülesanne):

a i > b j (kus i=1,...,m ; j=1,...,n);

2. Esitatud taotluste hulk ületab olemasolevaid reserve (transpordiprobleem taotluste ülejäägiga):

ja mina< b j (где i=1,...,m ; j=1,...,n);

Vaatleme neid kahte juhtumit järjestikku:

Transpordiprobleem liigse laoseisuga.

Redigeerime selle õige tasakaaluga eelnevalt käsitletud transpordiprobleemiks. Selleks tutvustame lisaks saadaolevale n sihtkohale B 1, B 2, ..., B n veel ühe fiktiivse sihtkoha B n +1, millele määrame fiktiivse taotluse, mis võrdub üleliigse laoseisuga. taotlusi

b n+1 = a i - b j (kus i=1,...,m ; j=1,...,n) ,

ja transpordikulud kõikidest lähtepunktidest fiktiivsesse sihtkohta b n +1 loetakse võrdseks nulliga. Võttes kasutusele fiktiivse sihtkoha B n +1 selle taotlusega b n +1, oleme transpordiprobleemi tasakaalu võrdsustanud ja nüüd saab selle õige bilansiga liiniveoprobleemina lahendada.

Transpordiprobleem liigsete taotluste tõttu.

Selle probleemi saab taandada õige tasakaaluga tavaveoprobleemiks, kui võtta kasutusele fiktiivne lähtepunkt A m+1, mille varu a m+1 on võrdne puuduva laovaruga ja transpordikulu fiktiivsest lähtepunktist. kõikidele sihtkohtadele eeldatakse, et see on null.

Transpordiprobleemi lahendamisel on oluline optimaalsuse kriteeriumi valik. Teatavasti saab hinnangu umbkaudse planeeringu majanduslikule efektiivsusele määrata ühe või teise kriteeriumi järgi, mis on planeeringu arvutamise aluseks. See kriteerium on planeeringu kvaliteeti iseloomustav majandusnäitaja. Seni ei ole üldtunnustatud ühtset majanduslikke tegureid igakülgselt arvesse võtvat kriteeriumi. Transpordiprobleemi lahendamisel kasutatakse erinevatel juhtudel optimaalsuse kriteeriumina järgmisi näitajaid:

1) Veotöö maht (kriteerium - vahemaa t/km). Minimaalne läbisõit on mugav transpordiplaanide hindamiseks, kuna transpordikaugust saab hõlpsalt ja täpselt määrata igas suunas. Seetõttu ei saa see kriteerium lahendada transpordiprobleeme, mis hõlmavad paljusid transpordiliike. Seda kasutatakse edukalt maanteetranspordi transpordiprobleemide lahendamisel. Optimaalsete skeemide väljatöötamisel homogeense kauba transpordiks sõidukitega.

2) Kauba veo tariifitasu (kriteerium - veotasude tariifid). Võimaldab hankida transpordiskeemi, mis on ettevõtte isemajandavate näitajate seisukohalt parim. Kõik lisatasud ja ka kehtivad soodustariifid muudavad selle kasutamise keeruliseks.

3) Tegevuskulud kauba transportimisel (kriteerium - tegevuskulude maksumus). Täpsemalt peegeldab erinevate transpordiliikide transpordi kuluefektiivsust. Võimaldab teha teadlikke järeldusi ühelt transpordiliigilt teisele ülemineku otstarbekuse kohta.

4) Kaupade tarneajad (kriteerium - ajakulu).

5) Tasandatud kulud (arvestades tegevuskulusid, olenevalt liikluse mahust ja investeeringust veeremisse).

6) Arvestatud kulud (arvestades veeremirajatiste ehitamise kapitaliinvesteeringute tegevuskulusid).

,

kus on tegevuskulud,

Hinnanguline investeeringutõhususe suhe,

Kapitaliinvesteeringud 1 tonni lasti kohta kogu lõigul,

T - reisiaeg,

C - ühe tonni lasti hind.

Võimaldab terviklikumalt hinnata transpordiplaanide erinevate võimaluste ratsionaliseerimist, väljendades üsna täielikult mitmete majandustegurite kvantitatiivset ja samaaegset mõju.

Vaatleme transpordiprobleemi, mille optimaalsuse kriteeriumiks on kogu veose transpordi minimaalne maksumus. Tähistagem läbi kaubaühiku i-ndast lähtepunktist j-ndasse sihtpunkti vedamise tariifide kaudu – i-ndas lähtepunktis olevad kaubavarud, läbi – nõuded kaubale kl. j-ndast sihtpunktist ja selle kaudu – i-ndast lähtepunktist j-ndasse sihtkohta veetud kaubaühikute arv. Seejärel seisneb ülesande matemaatiline formuleerimine funktsiooni minimaalse väärtuse määramises

tingimustel

(2)

(3)

(4)

Kuna muutujad täita lineaarvõrrandi (2) ja (3) süsteeme ning mittenegatiivsuse tingimust (4), siis on tagatud olemasoleva lasti eemaldamine kõikidest lähtepunktidest, vajaliku koguse lasti kohaletoimetamine igasse sihtkohta ning tagasisaatmine transport on välistatud.

Seega on T-probleem LP probleem m*n muutujate arv ja m+n piirangute arv - võrdsused.

Ilmselgelt on tarnijate veoste kogusaadavus võrdne ja kauba kogunõudlus sihtkohtades võrdub ühikutega. Kui kauba kogunõudlus sihtkohtades võrdub kauba pakkumisega lähtekohtades, s.o.

siis nimetatakse sellise transpordiprobleemi mudelit suletud või tasakaalustatud.

On mitmeid praktilisi probleeme, mille puhul tasakaalutingimus ei ole täidetud. Selliseid mudeleid nimetatakse avatud. Võimalikke juhtumeid on kaks:

Esimesel juhul on nõudluse täielik rahuldamine võimatu.

Sellise probleemi saab taandada tavapäraseks transpordiprobleemiks järgmiselt. Kui nõudlus ületab laoseisu, st fiktiivne ( m+1)-s lähtepunkt koos kaubareserviga ja tariifid eeldatakse nulliks:

Siis peate minimeerima

tingimustel

Vaatleme nüüd teist juhtumit.

Samamoodi, kui fiktiivne ( n+1)-s sihtkoht vajadusega ja vastavad tariifid loetakse võrdseks nulliga:

Seejärel kirjutatakse vastav T-ülesanne järgmiselt:

Minimeeri

tingimustel:

See taandab probleemi tavaliseks transpordiprobleemiks, mille optimaalsest plaanist saadakse algse probleemi optimaalne plaan.

Järgnevalt käsitleme transpordiprobleemi suletud mudelit. Kui konkreetse ülesande mudel on avatud, siis kirjutame ülaltoodust lähtuvalt ülesande tingimuste tabeli ümber nii, et võrdsus (5) on täidetud.

Mõnel juhul peate täpsustama, et tooteid ei saa teatud marsruute mööda transportida. Seejärel määratakse nendel marsruutidel transpordikulud nii, et need ületavad võimalikult suuri transpordikulusid (et mööda ligipääsmatuid marsruute ei oleks kasumlik transportida) - probleemi lahendamisel minimaalselt. Maksimaalselt – vastupidi.

Mõnikord tuleb arvestada sellega, et mõne väljastuspunkti ja mõne tarbimiskoha vahel on sõlmitud lepingud kindlate tarnemahtude kohta, siis tuleb garanteeritud tarne maht edasisest arvestamisest välja jätta. Selleks lahutatakse garanteeritud tarne maht järgmistest väärtustest:

· vastava väljastuspunkti laost;

· vastavalt vastava sihtkoha vajadustele.

Näide.

Neli selles majanduspiirkonnas asuvat ettevõtet kasutavad toodete tootmiseks kolme tüüpi toorainet. Iga ettevõtte toorainevajadus on vastavalt 120, 50, 190 ja 110 ühikut. Tooraine on koondatud kolme vastuvõtmiskohta ja varud on vastavalt 160, 140, 170 ühikut. Toorainet saab importida igasse ettevõttesse mis tahes vastuvõtupunktist. Transporditariifid on teadaolevad kogused ja määratud maatriksiga

Koostage transpordiplaan, milles transpordi kogumaksumus on minimaalne.

Lahendus. Tähistagem i-ndast vastuvõtupunktist j-ndasse ettevõttesse transporditud tooraine ühikute arvuga. Seejärel tagatakse vajalike ja saadaolevate toorainete tarnimise ja äraveo tingimused järgmiste võrdsuste täitmisega:

(6)

Selle plaaniga transport, on transpordi kogumaksumus

Seega seisneb selle transpordiülesande matemaatiline formuleerimine lineaarvõrrandisüsteemile (6) sellise mittenegatiivse lahenduse leidmises, milles sihtfunktsioon (7) omandab minimaalse väärtuse.

Transpordiprobleemi lahendus

Peamised sammud transpordiprobleemi lahendamisel:

1. Leidke esialgne teostatav plaan.

2. Valige mittepõhimuutujate hulgast see, mis baasi sisestatakse. Kui kõik mittepõhimuutujad vastavad optimaalsuse tingimustele, viige lahendus lõpule, vastasel juhul jätkake järgmise sammuga. samm.

3. Valige baasist tuletatud muutuja ja leidke uus põhilahendus. Naaske 2. sammu juurde.

Maatriksiga määratletud lineaarvõrrandisüsteemide (2) ja (3) mittenegatiivne lahendus , nimetatakse transpordiprobleemide plaaniks. T-ülesande etalon- (põhi)plaaniks nimetatakse mis tahes selle lubatavat põhilahendust.

Tavaliselt kirjutatakse transpordiülesande lähteandmed tabeli kujul.

Maatriksit C nimetatakse transpordikulude maatriksiks, maatriksit X, mis rahuldab T-ülesande (2) ja (3) tingimusi, nimetatakse transpordiplaaniks ja muutujaid transpordiks. Plaani, mille puhul eesmärkfunktsioon on minimaalne, nimetatakse optimaalseks.

Muutujate arv transpordiprobleemis m lähtepunktid ja n sihtkohad on võrdsed m*n, ja võrrandite arv süsteemides (2) ja (3) on võrdne m+n. Kuna eeldame, et tingimus (5) on täidetud, on lineaarselt sõltumatute võrrandite arv võrdne m+n–1. Järelikult ei saa transpordiprobleemi võrdlusplaanis olla rohkem kui m+n–1 nullist erinevad tundmatud.

Kui võrdlusplaanis on nullist erineva komponentide arv täpselt m+n–1, siis on plaan mitte-mandunud ja kui seda on vähem, siis on see mandunud.

Nagu iga lineaarse programmeerimise probleemi puhul, on transpordiprobleemi optimaalne plaan ka võrdlusplaan.

Lubatava (viite)plaani koostamine transpordiprobleemis

Analoogiliselt teiste lineaarse programmeerimise probleemidega algab transpordiprobleemi lahendamine vastuvõetava põhiplaani koostamisest. T-probleemi esialgsete võrdlusplaanide koostamiseks on mitu meetodit. Nendest kõige levinumad loodenurga meetod Ja minimaalse elemendi meetod.

Lihtsaim viis selle leidmiseks põhineb nn loodenurga meetodil. Meetodi olemus seisneb kõigi esimeses, teises jne tootmispunktis saadaolevate varude järjestikuses jaotamises esimeses, teises jne tarbimispunktis. Iga jaotamise etapp taandub katsele reservid täielikult ammendada järgmises tootmispunktis või katsele järgmises tarbimiskohas vajadusi täielikult rahuldada. Igal sammul q näidatakse praeguste jaotamata reservide väärtused ja i(q ) ja praegused rahuldamata vajadused - b j (q ) . Vastuvõetava esialgse plaani ehitamine loodenurga meetodil algab transporditabeli vasakust ülanurgast, samas kui eeldame a i (0) = a i, b j (0) = b j . Järgmise real asuva lahtri jaoks i ja veerg j , jaotamata varude väärtused i -th tootmispunkt ja rahuldamata vajadus j tarbimispunktis, valitakse nende hulgast miinimum ja määratakse transpordimahuks nende punktide vahel: x i, j =min(a i (q) , b j (q) ) . Pärast seda vähendatakse vastavates punktides jaotamata varu ja rahuldamata vajaduse väärtusi selle summa võrra:

a i (q+1) = a i (q) - x i, j, b j (q+1) = b j (q) - x i, j

Ilmselt on igal etapil täidetud vähemalt üks võrdsustest: ja i (q+1) = 0 või b j (q+1) = 0 . Kui esimene on tõene, siis tähendab see, et kogu i-nda tootmispunkti laovaru on ammendunud ja on vaja jätkata varude jaotamist tootmispunktis i+1 , st liikuda veerus allapoole järgmisesse lahtrisse. Kui b j (q+1) = 0, see tähendab, et on vaja j punkt, millele järgneb üleminek rea paremal pool asuvasse lahtrisse. Äsja valitud lahter muutub praeguseks ja sellega korratakse kõiki ülaltoodud toiminguid.

Varude ja vajaduste tasakaalu tingimusest lähtudes ei ole raske tõestada, et piiratud arvu etappidega saame vastuvõetava plaani. Sama tingimuse tõttu ei saa algoritmi sammude arv olla suurem kui m+n-1 , jääb seetõttu alati vabaks (null) mn-(m+n-1) rakud. Seetõttu on saadud plaan elementaarne. Võimalik, et mingis vahepealses etapis osutub praegune jaotamata varu võrdne praeguse rahuldamata nõudlusega (a i (q) = b j (q)) . Sel juhul toimub üleminek järgmisse lahtrisse diagonaalis (hetkel tootmis- ja tarbimispunktid muutuvad samaaegselt) ja see tähendab ühe nullist erineva komponendi "kadumist" plaanis või muus. sõnadega, ehitatud plaani mandumine.

Loodenurga meetodil koostatud lubatava plaani eripäraks on see, et sellel olev sihtfunktsioon omandab väärtuse, mis reeglina pole kaugeltki optimaalne. See juhtub seetõttu, et selle ehitamisel ei võeta väärtusi mingil moel arvesse c i , j . Sellega seoses kasutatakse praktikas esialgse plaani saamiseks teist meetodit - minimaalse elemendi meetod, milles liiklusmahtude jaotamisel hõivatakse kõigepealt madalaima hinnaga lahtrid.

Näide võrdlusplaani leidmisest

F = 14 x 11 + 28 x 12 + 21 x 13 + 28 x 14 + 10 x 21 + 17 x 22 + 15 x 23 + 24 x 24 + 14 x 31 + 30 x 32 + 25 x 33 + 21 x 34

Esialgne plaan on saadud loodenurga meetodil. Ülesanne on tasakaalus (suletud).

Tabel 1

Transpordi maksumus selle plaani alusel on: 1681:

F = 14 * 27 + 28 * 0 + 21 * 0 + 28 * 0 + 10 * 6 + 17 * 13 + 15 * 1 + 24 * 0 + 14 * 0 + 30 * 0 + 25 * 26 + 21 * 17 = 1681

Transpordiplaan

on optimaalne plaan siis ja ainult siis, kui on olemas maksesüsteem

mille puhul on täidetud järgmised tingimused:

Tõestus. Sõnastame teise duaalsusteoreemi transpordiülesande muutujate osas.

rahuldada otsese probleemi piiranguid ja

täita duaalprobleemi piiranguid, siis plaani optimaalsuse tagamiseks

see on vajalik ja piisav tingimuste täitmiseks

Tingimus a) on täidetud otsese probleemi kõigi vastuvõetavate lahenduste puhul, kuna

Tingimust b) saab kirjutada komplementaarse mittejäikuse järelmina, nimelt

Niisiis, põhimuutujate jaoks

meil on võrdsus

ja mittepõhimuutujate puhul

sellest piisab kahe muutuja lubatavuse rahuldamiseks

Seega on meil kriteeriumi tingimused 1) ja 2).

Kriteerium on tõestatud.

9.5 Transpordiprobleemi referentsplaani koostamine

Transpordiprobleemi lahendamise meetodid taanduvad lihtsatele toimingutele transporditabeliga, mille vorm on:

Põhiline transporditabeli lahtrid on lahtrid koos

isiklik null-positiivsest transpordist, ülejäänud rakud on vabad. Põhilahtrid moodustavad transpordiprobleemi võrdlusplaani, kui on täidetud kaks tingimust:

1) veo hulk igal real on võrdne selle laoseisuga

2) veo hulk igas veerus on võrdne vastavaga

nõudluse veerg

Transpordiprobleemi võrdlusplaan ei sisalda rohkem kui n+m-1

nullist erinev transport

Referentsplaani nimetatakse degenereerunud, kui nullist erineva vedude arv

vähem ja n+m-1, võrdlusplaan - mitte-mandunud, kui number

nullist erinev transport on võrdne n+m-1.

Vaatleme meetodeid tugiplaani koostamiseks mitte-mandunud ja degenereerunud juhtudel.

Loodenurga meetod

Mõelge siis tühja laua "loodenurka".

seal on lahter, mis vastab esimesele tarnijale ja esimesele tarbijale.

Võimalikke juhtumeid on kolm.

See tähendab, et esimene tarnija saatis kogu toodetud toote esimesele tarbijale ja temale

aktsia on null, nii et

Sel juhul on rahuldamata nõudlus esimeses tarbimiskohas võrdne

see tähendab, et esimese tarbija nõudlus on täielikult rahuldatud ja seetõttu

ja toote ülejäänud osa esimeses tootmispunktis on võrdne

Nii tarnija kui ka tarbija võib kaalumisest kõrvale jätta. Kui aga aatomi plaan osutub mandunud,

seetõttu arvatakse tavaliselt, et pensionile läheb ainult tarnija,

ja tarbijate nõudlus jääb rahuldamata ja on võrdne nulliga.

Pärast seda käsitleme ülejäänud mitte-

täitke osa tabelist ja korrake samu samme. Tulemusena

peale n+m-1 sammu saame võrdlusplaani.

10. Transpordiprobleemi matemaatiline mudel. Avatud ja suletud ülesanded. Vastuvõetavad, võrdlus- ja optimaalsed transpordiplaanid.

Mõiste "transpordiprobleem" ühendab ühe matemaatilise mudeliga laia valikut probleeme. Need ülesanded kuuluvad lineaarse programmeerimise ülesannete hulka ja neid saab lahendada simpleksmeetodi abil. Transpordiprobleemi piirangute süsteemi maatriks on aga nii ainulaadne, et selle lahendamiseks on välja töötatud spetsiaalsed meetodid. Need meetodid, nagu ka simpleksmeetod, võimaldavad leida esialgse etalonlahenduse ja seejärel seda täiustades saada optimaalse lahenduse.

Avatud ja suletud transpordiülesanded . TK-d on kahte tüüpi: avatud TK ja suletud TK.

Transpordiprobleemi nimetatakse suletuks, kui see on rahuldatud tasakaalu seisund: toodangu kogumaht võrdub tarbimise kogumahuga:

Tuleb märkida, et matemaatiline mudel täpsustab suletud transpordiprobleemi.

Avatud TK esineb kahel juhul.

Esimene juhtum. Kogu tootmismaht on väiksem kui kogutarbimise maht:

Teatavasti on transpordiprobleemi vastuvõetava lahenduse leidmiseks vajalik ja piisav, et probleem suletakse. Seetõttu tuleb avatud tüüpi transpordiprobleem esmalt taandada suletud probleemiks, mille jaoks tuuakse tootmismahuga sisse fiktiivne tootmispunkt numbriga m+1:

, (3.3)

samal ajal uskuda.

Teine juhtum. Kogu tootmismaht on suurem kui kogutarbimise maht:

Tehniliste kirjelduste vähendamiseks suletud tüübiks võetakse kasutusele fiktiivne tarbimiskoht numbriga n+1 koos tarbimismahuga:

, (3.5)

samal ajal uskuda.

Lahendusmeetodid.

· Kuidas saab lineaarse programmeerimise TK ülesannet lahendada simpleksmeetodil.

· Samuti on välja töötatud spetsiaalsed (efektiivsemad) meetodid transpordiprobleemi lahendamiseks: üldistatud ungari meetod; loodenurga meetod, võrdlusplaani leidmise miinimumelemendi meetod; potentsiaalide meetod optimaalse plaani leidmiseks.

11. Esialgse (referentsi) transpordiplaani koostamine loodenurga meetodil ja vähima kulu meetodil.

1.Loodenurga meetod. Võrdlusplaani leidmisel arvestatakse igal sammul esimest ülejäänud lähtepunktidest ja esimest ülejäänud sihtkohtadest. Tingimuste tabeli lahtrite täitmine algab tundmatu jaoks ülemisest vasakpoolsest lahtrist (“loodenurk”) ja lõpeb tundmatu lahtriga, s.o. justkui diagonaalselt üle laua.

2. Väikseima kulu meetod. Meetodi olemus seisneb selles, et kogu kulude tabelist valitakse välja väikseim ja sellele vastavasse lahtrisse paigutatakse numbritest väiksem ja seejärel kas tarnijale vastav rida, kelle varud on täielikult ära kasutatud. , või veerg, mis vastab tarbijale, kelle vajadused on täielikult rahuldatud, või nii rida kui ka veerg, kui tarnija varud on ammendatud ja kliendi vajadused rahuldatud. Ülejäänud kulutabeli hulgast valitakse taas madalaim maksumus ja varude jaotamise protsess jätkub, kuni kõik varud on jaotatud ja nõuded täidetud.