Iš to, kas buvo pasakyta ankstesnėje pastraipoje, seka: Pagrindinio transporto problemos sprendimo optimalumo kriterijus: jei kokiam nors pagrindiniam transportavimo planui algebrinės tarifų sumos pagal ciklus visoms laisvoms ląstelėms yra neneigiamos, tai šis planas yra optimalus.
Tai reiškia metodą, kaip rasti optimalų transporto problemos sprendimą, kuris susideda iš to, kad, turėdami tam tikrą pagrindinį sprendimą, jie apskaičiuoja algebrines visų laisvų ląstelių tarifų sumas. Jei optimalumo kriterijus tenkinamas, tai šis sprendimas yra optimalus; jei yra langelių su neigiamomis algebrinėmis tarifų sumomis, tada jie pereina prie naujo pagrindo, perskaičiuodami pagal ciklą, atitinkantį vieną iš tokių langelių. Tokiu būdu gautas naujas bazinis sprendimas bus geresnis už pirminį – jo įgyvendinimo kaštai bus mažesni. Naujam sprendimui taip pat patikrinamas optimalumo kriterijaus tinkamumas ir, jei reikia, dar kartą atliekamas ciklo perskaičiavimas vienam iš langelių su neigiama algebrine tarifų suma ir pan.
Po tam tikro skaičiaus žingsnių jie pasiekia norimą optimalų pagrindinį sprendimą.
Jei algebrinės visų laisvųjų langelių tarifų sumos yra teigiamos, turime unikalų optimalų sprendimą; jei visų laisvųjų langelių algebrinės tarifų sumos yra neneigiamos, bet tarp jų yra algebrinių tarifų sumų, lygių nuliui, tada optimalus sprendimas nėra vienintelis: perskaičiuojant per ciklą ląstelei su nuline algebrine tarifų sumą, gauname tą patį optimalų sprendimą, bet skirtingą nuo pirminio (abiejų planų išlaidos bus vienodos).
Priklausomai nuo laisvų ląstelių tarifų algebrinių sumų apskaičiavimo metodų, yra du būdai optimaliam transporto problemos sprendimui rasti:
Paskirstymo būdas. Taikant šį metodą, kiekvienam tuščiam langeliui sukuriamas ciklas ir kiekvienam ciklui tiesiogiai apskaičiuojama algebrinė tarifų suma.
Potencialų metodas.Šiuo metodu pirmiausia surandami bazių ir vartotojų potencialai, o vėliau, naudojant potencialus, apskaičiuojama algebrinė tarifų suma kiekvienam tuščiam langeliui.
Potencialaus metodo pranašumai, lyginant su paskirstymo metodu, yra tai, kad nereikia konstruoti ciklų kiekvienam iš tuščių langelių ir supaprastinamas algebrinių tarifų sumų skaičiavimas. Sukurtas tik vienas ciklas - tas, kuriuo atliekamas perskaičiavimas.
Naudodami potencialų metodą galime kalbėti ne apie algebrinių tarifų sumų ženklą, o apie netiesioginių tarifų palyginimą su tikraisiais. Reikalavimas, kad algebrinės tarifų sumos būtų neneigiamos, pakeičiamas sąlyga, kad netiesioginiai tarifai neviršytų tikrųjų.
Reikėtų nepamiršti, kad potencialai (kaip ir ciklai) nustatomi iš naujo kiekvienai naujai bazinei linijai.
Aukščiau nagrinėjome uždarą transporto problemos modelį su teisinga pusiausvyra, kai tenkinama (1.3) sąlyga. Jei įvykdytas (1.4) (atviras modelis), transporto užduoties pusiausvyra gali būti sutrikdyta dviem kryptimis:
1. Atsargų kiekis išvykimo vietose viršija pateiktų paraiškų kiekį (transporto užduotis su atsargų pertekliumi):
a i > b j (kur i=1,...,m ; j=1,...,n);
2. Pateiktų paraiškų kiekis viršija turimus rezervus (transporto problema su paraiškų pertekliumi):
ir aš< b j (где i=1,...,m ; j=1,...,n);
Panagrinėkime šiuos du atvejus paeiliui:
Transporto problema dėl perteklinių atsargų.
Sumažinkite ją iki anksčiau svarstytos transporto problemos su teisingu balansu. Norėdami tai padaryti, be turimų n paskirties vietų B 1, B 2, ..., B n, pristatome dar vieną fiktyvią paskirties vietą B n +1, kuriai priskiriame fiktyvią užklausą, lygią atsargų pertekliui. prašymus
b n+1 = a i - b j (kur i=1,...,m ; j=1,...,n) ,
o transportavimo iš visų išvykimo taškų iki fiktyvios paskirties vietos b n +1 kaina bus laikoma lygi nuliui. Įvesdami fiktyvų tikslą B n +1 su jo prašymu b n +1, išlyginome transporto problemos pusiausvyrą ir dabar ją galima išspręsti kaip reguliaraus transporto problemą su teisingu balansu.
Transporto problema dėl perteklinių užklausų.
Šią problemą galima sumažinti iki reguliaraus transporto problemos su teisingu balansu, jei įvesime fiktyvų išvykimo tašką A m +1 su atsargomis a m +1, lygiu trūkstamoms atsargoms, ir transportavimo iš fiktyvaus išvykimo taško kainą. į visas paskirties vietas laikoma nuliu.
Bendra transporto problemos formuluotė susideda iš optimalaus plano gabenti kai kuriuos vienarūšius krovinius iš m išvykimo punktai (tiekėjai) A1, A2, . . ., A m V n vartojimo taškai (vartotojai) B1, B2, . . . Bn taip, kad:
Pašalinti visus krovinius iš tiekėjų;
Patenkinti kiekvieno vartotojo poreikius;
Užtikrinti minimalias bendrąsias transporto išlaidas gabenant visas prekes.
Apsvarstykite transporto problemą kaip optimalumo kriterijus, kuris naudoja minimalias viso krovinio pervežimo išlaidas.
Pažymime:
ai - krovinio prieinamumas i -asis išvykimo taškas https://pandia.ru/text/78/103/images/image205_0.gif" width="81" height="27 src=">;
сij - krovinio vieneto pervežimo išlaidos iš i išvykimo taške j vartojimo vieta (transportavimo tarifas);
xij - iš vežamo krovinio kiekis i išvykimo taške j tikslas, paskirties vieta, xij ≥ 0.
Transporto problemos matematinė formuluotė susideda iš neneigiamo tiesinių lygčių sistemos, kurioje tikslo funkcija turi mažiausią reikšmę, sprendimo.
Užrašykime matematinį transporto problemos modelį.
Būtina nustatyti matricą ), kuri atitinka šias sąlygas:
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)
ir pateikia mažiausią tikslo funkcijos reikšmę
L () = https://pandia.ru/text/78/103/images/image215_0.gif" width="36" height="24"> atitinka tiesinių lygčių sistemą (5.1), (5.2) ir neneigiamumo sąlyga, Tai užtikrina reikiamo krovinio pristatymą kiekvienam vartotojui, turimų krovinių pašalinimą iš visų tiekėjų, o taip pat eliminuoja grąžinimo transportavimą.
1 apibrėžimas. Bet koks neneigiamas tiesinių lygčių sistemų (5.1) ir (5.2), apibrėžtų matrica ), sprendinys vadinamas įgyvendinamas transporto problemos planas.
Apibrėžimas 2. Planas) https://pandia.ru/text/78/103/images/image218_0.gif" width="23" height="24">, vadinamas pagrindiniu arba nuoroda.
4 apibrėžimas. Jei atskaitos plane yra keletas nulinių kintamųjų verčių https://pandia.ru/text/78/103/images/image219_0.gif" width="55" height="22">.gif " width="55" height ="22"> > , įvedama fiktyvi (n+ 1) paskirties vieta su reikalavimu mlrd+1 = – https://pandia.ru/text/78/103/images/image221_0.gif" width="83 height=22" height="22">
Jeigu< https://pandia.ru/text/78/103/images/image220_0.gif" width="56 height=25" height="25">.gif" width="79" height="22 src=">
Panagrinėkime vieną iš transporto problemos pirmojo atskaitos plano sudarymo būdų – minimalių sąnaudų metodą arba geriausią vieneto sąnaudų matricos elementą.
6 apibrėžimas. Geriausias vieneto kaštų (tarifų) matricos elementas bus mažiausias tarifas, jei užduotis bus nustatyta į tikslinės funkcijos minimumą, didžiausias tarifas – jei uždavinys nustatytas maksimaliai.
Pirmojo atskaitos plano sudarymo algoritmas.
1. Tarp vieneto kaštų matricos randame geriausią tarifą.
2. Paskirstymo lentelės langelyje užpildykite pasirinktą tarifą su maksimaliu galimu krovinio kiekiu, atsižvelgiant į eilučių ir stulpelių apribojimus. Tokiu atveju arba visas krovinys išimamas iš tiekėjo, arba visiškai patenkinami vartotojo poreikiai. Lentelės eilutė arba stulpelis išbraukiamas iš svarstymo ir toliau platinant nedalyvauja.
3. Iš likusių tarifų vėl išrenkame geriausią ir procesas tęsiasi tol, kol bus paskirstytas visas krovinys.
Jei transporto problemos modelis yra atviras ir įvedamas fiktyvus tiekėjas ar vartotojas, tada pirmiausia vykdomas paskirstymas tikriems tiekėjams ir vartotojams, o galiausiai nepaskirstytas krovinys siunčiamas iš fiktyvaus tiekėjo arba fiktyviam vartotojui.
Toliau tobuliname pirmąjį transporto problemos etaloninį planą ir gauname optimalų planą naudojant potencialų metodą.
3 teorema . Transporto problemos planas ) yra optimalus, jei yra skaičių ui ir vj (vadinamų potencialais) sistema (m + n), kuri tenkina sąlygas:
(5.6)
(5.7)
Potencialai ui ir vj yra dvigubos problemos, sudarytos iš pradinės transporto problemos, kintamieji ir žymi krovinio vieneto įvertinimą atitinkamai kilmės ir paskirties taškuose.
Pažymėkime: ) laisvos (neužimtos) lentelės langelio įvertį.
7 apibrėžimas. Transporto problemos atskaitos planas yra optimalus, jei visi paskirstymo lentelės laisvųjų langelių įverčiai (uždavinys nustatytas iki minimumo).
Potencialaus metodo algoritmas
1. Pirmojo etaloninio plano kūrimas transporto problema naudojant minimalių sąnaudų metodą.
2. Plano išsigimimo tikrinimas .
Potencialai gali būti skaičiuojami tik neišsigimusio plano atveju. Jei atskaitos plane užimtų langelių skaičius (pagrindinių kintamųjų skaičius) yra mažesnis nei (m+n−1), tada viename iš laisvų lentelės langelių įrašome nulį, kad bendras užimtų langelių skaičius tampa lygus (m+n−1). Nulis įvedamas į langelį su geriausiu tarifu, kuris priklauso eilutei ar stulpeliui. Sudarant pirmąjį orientacinį planą, kartu nubraukta. Šiuo atveju lentelės langelis, fiktyviai užimtas nuliu, neturėtų sudaryti uždaro stačiakampio kontūro su kitais užimtais lentelės langeliais.
3. Tikslo funkcijos reikšmės apskaičiavimas (5.4) susumavus tarifų sandaugas (vieneto sąnaudas) pagal pervežto krovinio tūrį visoms užimtoms lentelės ląstelėms.
4. Plano optimalumo tikrinimas.
Mes nustatome potencialus. Kiekvienai užimtai ląstelei rašome lygtį, todėl gauname (m + n−1) lygčių sistemą su (m + n) kintamaisiais.
Kadangi kintamųjų skaičius yra didesnis už lygčių skaičių, gauta sistema nėra apibrėžta ir turi begalinį sprendinių skaičių..gif" width="70" height="22">, tada likę potencialai nustatomi vienareikšmiškai, o jų reikšmės įrašomos į papildomą paskirstymo lentelių eilutę ir stulpelį.
Kiekvienam laisvam langeliui nustatome įvertinimus https://pandia.ru/text/78/103/images/image233.gif" width="72 height=24" height="24">(problema išspręsta tikslo funkcijos minimumas), tada rastas optimalus planas.Jei bent vienas laisvos langelio ivertis netenkina optimalumo slygos, tai plana btina tobulinti perskirstant apkrov.
5.
Iš visų teigiamų laisvųjų langelių įverčių pasirenkame didžiausią (užduotis nustatyta iki minimumo); iš visų neigiamų – didžiausia absoliučia reikšme (užduotis nustatyta maksimaliai). Ląstelė, kuri atitinka aukščiausią balą, turi būti užpildyta, t. y. į ją turi būti siunčiama apkrova. Užpildant pasirinktą langelį, reikia pakeisti tiekimo apimtį, įrašytą daugelyje kitų užimtų langelių ir susietų su užpildomu, vadinamąjį ciklą.
Ciklas arba stačiakampis kontūras transporto uždavinio paskirstymo lentelėje yra trūkinė linija, kurios viršūnės yra užimtose lentelės langeliuose, o nuorodos yra išilgai eilučių ir stulpelių bei kiekvienoje viršūnėje. cikle yra lygiai dvi nuorodos, iš kurių viena yra eilutėje, kita stulpelyje . Jei ciklą sudaranti trūkinė linija susikerta, tada susikirtimo taškai nėra viršūnės. Kiekvienai laisvai ląstelei galima sukurti vieną ciklą.
Ciklo viršūnės, pradedant nuo viršūnės, esančios pasirinktame pakrovimui langelyje, pakaitomis priskiriamos ženklais „+“ ir „-“. Šias ląsteles vadinsime pliusais ir minusais.
Iš krovinio tūrių minusinėse ląstelėse pasirenkame mažiausią ir pažymime jį θ. Perskirstome θ reikšmę išilgai kontūro, pridėdami θ prie atitinkamų krovinio tūrių pliuso langeliuose ir atimdami θ iš krovinio tūrių lentelės minuso langeliuose. Dėl to ląstelė, kuri buvo laisva ir pasirinkta įkelti, tampa užimta, o viena iš užimtų kontūro langelių tampa laisva.
Patikriname gauto atskaitos plano optimalumą, t.y. grįžtame į ketvirtą algoritmo etapą.
Pastabos.
1. Jeigu sukonstruoto ciklo minuso langeliuose yra dvi ar daugiau identiškų minimalių dydžių, tai perskirstant krovinių kiekius išleidžiama ne viena, o dvi ar daugiau langelių. Tokiu atveju planas išsigimsta. Norint tęsti sprendimą, reikia užimti vieną ar daugiau vienu metu atlaisvintų lentelės langelių su nuliu, o pirmenybė teikiama ląstelėms su geriausiu tarifu. Įvedama tiek nulių, kad naujai gautame atskaitos plane užimtų langelių (pagrindinių kintamųjų) skaičius būtų tiksliai (m + n−1).
2. Jeigu transporto uždavinio optimaliame plane kurio nors laisvo langelio įvertis lygus nuliui), tai problema turi daug optimalių planų. Ląstelėje, kurios balas nulinis, galite sukurti ciklą ir perskirstyti apkrovą. Dėl to gautas planas taip pat bus optimalus ir turės tokią pačią tikslo funkcijos reikšmę.
3. Tikslo funkcijos reikšmę kiekvienoje iteracijoje galima apskaičiuoti taip:
(užduotis nustatyta iki minimumo),
(užduotis nustatyta maksimaliai),
kur kontūru judančio krovinio tūris;
Laisvos ląstelės, į kurią nukreipiama apkrova, įvertinimas pereinant prie naujo etaloninio plano;
− tikslo funkcijos reikšmė k-oje iteracijoje;
− tikslo funkcijos reikšmė ankstesnėje iteracijoje.
Pavyzdys.
Trijuose didmeninės prekybos bazės sandėliuose yra vienarūšių krovinių po 40, 80 ir 80 vnt. Šis krovinys turi būti gabenamas į keturias parduotuves, kurių kiekviena turi gauti atitinkamai 70, 20, 60 ir 60 vnt. Pristatymo išlaidos vienam krovinio vienetui (tarifai) iš kiekvieno sandėlio 
) į visas parduotuves 
) pateikiami matrica 
.
Sudaryti vienarūšių krovinių pervežimo minimaliomis transporto sąnaudomis planą (sąlyginiai skaičiai).
Sprendimas.
1. Patikrinkime reikalingą ir pakankamą problemos sprendimo sąlygą:
40+80+80 = 200,
70+20+60+60 = 210.
Kaip matote, bendra krovinių paklausa viršija jo atsargas didmeninės prekybos bazės sandėliuose. Vadinasi, transporto problemos modelis yra atviras ir neturi pirminės formos sprendimo. Norėdami gauti uždarą modelį, pristatome papildomą (fiktyvų) sandėlį A4 su krovinių atsarga, lygia A 4 = 210 – 200 = 10 vnt. Darome prielaidą, kad krovinio vieneto gabenimo iš sandėlio A4 į visas parduotuves tarifai yra lygūs nuliui.
Visus pradinius duomenis įvedame į 7 lentelę.
Atsargos |
||||||||
|
A 1 | ||||||||
|
A 2 |  3
| |||||||
|
A 3 | ||||||||
|
A 4 | ||||||||
Poreikiai | 210 210 |
2. Pirmojo pamatinio plano sukūrimas naudojant minimalių išlaidų metodą.
Tarp tarifų mažiausias arba geriausias yra C14 = 1. Į langelį A1B4 siunčiame didžiausią galimą apkrovą, lygią min(60,40) = 40. Tada x 14 = 40. Iš sandėlio A1 išvežtas visas krovinys, tačiau ketvirtos parduotuvės poreikis nepatenkintas 20 vnt. A1 eilutė neatsižvelgiama.
Tarp likusių tarifų minimalus elementas C23 = 2. Krovinį min(60,80) = 60 siunčiame į langelį A2B3. Šiuo atveju stulpelis B3 nenagrinėjamas, o iš sandėlio A2 nepaimta 20 vnt.
Iš likusių elementų minimumas yra C22 = 3. A2B2 langelyje siunčiame apkrovą min(20,20) = 20. Šiuo atveju eilutė A2 ir stulpelis B2 vienu metu perbraukiami.
Parenkame minimalų elementą C31 = 4. Į langelį A3B1 siunčiame apkrovą, lygią min(70,80) = 70. Šiuo atveju į stulpelį B1 neatsižvelgiama, o iš sandėlio A3 nepaimta 10 vnt. Likusius krovinius iš trečiojo sandėlio siunčiame į čiaupo angą A3B4, x 34 = 10. Ketvirtos parduotuvės paklausa nepatenkinama 10 vnt. atsiųsime 10 vnt. iš fiktyvaus tiekėjo - sandėlio A4. krovinys kameroje A4B4, x 44 = 10.
Dėl to gaunamas pirmasis orientacinis planas, kuris yra priimtinas, nes visi kroviniai išvežti iš sandėlių ir patenkinti visų parduotuvių poreikiai.
3. Plano išsigimimo tikrinimas.
Pirmajame atskaitos plane užimtų langelių arba bazinių kintamųjų skaičius yra šeši. transporto problemos planas yra išsigimęs, nes pagrindinių kintamųjų skaičius nedegeneruotame plane lygus m + n – 1 = 4 + 4 – 1 = 7. Norint toliau spręsti problemą, reikia papildyti pamatinį planą įvedant fiktyvų transportą, t.y., užimti vieną iš laisvųjų su nuliniais langeliais.
Statant pirmąjį etaloninį planą, A2 eilutė ir B2 stulpelis vienu metu buvo perbraukti, todėl planas išsigimė. Į fiktyvaus pervežimo teisę pretenduoja A2 eilutės ir B2 stulpelio laisvieji langeliai, kurie turi minimalų tarifą ir nesudaro uždaro stačiakampio kontūro su užimtomis celėmis. Šios ląstelės yra A2B4 ir A3B2. Į langelį A2B4 siunčiame nulį.
4. Tikslinės funkcijos reikšmės apskaičiavimas.
Pirmojo etaloninio plano tikslinės funkcijos reikšmė nustatoma susumavus visų užimtų lentelės langelių tarifų ir vežamų krovinių apimčių sandaugą.
L(X1) = 4∙70 + 3∙20 + 2∙60 + 1∙40 + 3∙0 + 6∙10 + 0∙10 = 560 (tūkstantis rublių).
5. Optimalumo būklės tikrinimas.
Apskaičiuokime lentelės užimtų langelių potencialus pagal sąlygą: https://pandia.ru/text/78/103/images/image260_0.gif" width="139" height="22">Nuo nežinomo skaičiaus potencialai yra didesnis nei lygčių skaičius (m + n > m + n – 1), tada imame vieną iš potencialų, lygių nuliui..gif" width="115 height=154" height="154">
Darant prielaidą, kad gausime 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">
Apskaičiuotus potencialus įrašome į 7 lentelę. Apskaičiuokime laisvųjų langelių įverčius.
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=">,
Pirmasis atskaitos planas nėra optimalus, nes yra teigiamų laisvųjų langelių ir . Mes pasirenkame didžiausią teigiamą laisvos ląstelės įvertinimą - .
6. Naujo orientacinio plano kūrimas.
Ląstelėje A3B2 sukonstruosime stačiakampę uždarą grandinę (0 7 lentelė) ir perskirstysime apkrovą grandinei. Kontūro viršūnės, pradedant nuo viršūnės, esančios laisvajame langelyje A3B2, pakaitomis priskiriamos ženklais „+“ ir „−“.
Iš krovinio tūrių minuso langeliuose pasirinkite mažiausią, t.y. θ = min(20,10) = 10. Pridėkite reikšmę θ = 10 prie krovinio tūrių pliuso langeliuose, atimkite iš krovinio tūrių minuso langeliuose uždarytuose. kilpa. Dėl to gauname naują atskaitos planą, parodytą 8 lentelėje.
Sprendžiant transporto problemą, svarbus optimalumo kriterijaus pasirinkimas. Kaip žinia, apytikslio plano ekonominio naudingumo įvertinimą gali lemti vienas ar kitas plano skaičiavimo pagrindas. Šis kriterijus yra ekonominis rodiklis, apibūdinantis plano kokybę. Iki šiol nėra visuotinai priimto vieno kriterijaus, kuris visapusiškai atsižvelgtų į ekonominius veiksnius. Sprendžiant transporto problemą, optimalumo kriterijumi įvairiais atvejais naudojami šie rodikliai:
1) Transporto darbų apimtis (kriterijus - atstumas t/km). Minimali rida yra patogi vertinant transportavimo planus, nes transportavimo atstumą galima lengvai ir tiksliai nustatyti bet kuria kryptimi. Todėl šis kriterijus negali išspręsti transporto problemų, susijusių su daugeliu transporto rūšių. Jis sėkmingai naudojamas sprendžiant kelių transporto transporto problemas. Kuriant optimalias vienarūšių krovinių vežimo transporto priemonėmis schemas.
2) Tarifinis mokestis už krovinių gabenimą (kriterijus - gabenimo mokesčių tarifai). Leidžia gauti transporto schemą, kuri yra pati geriausia įmonės savarankiškų rodiklių požiūriu. Visi papildomi mokesčiai, taip pat esami lengvatiniai tarifai apsunkina naudojimą.
3) Eksploatacinės išlaidos kroviniams gabenti (kriterijus - veiklos sąnaudų kaina). Tiksliau atspindi pervežimo įvairiomis transporto rūšimis ekonomiškumą. Leidžia padaryti pagrįstas išvadas apie galimybę pereiti nuo vienos transporto rūšies į kitą.
4) Prekių pristatymo terminai (kriterijus – laiko sąnaudos).
5) Išlygintos sąnaudos (atsižvelgiant į eksploatavimo išlaidas, priklausomai nuo eismo dydžio ir investicijų į riedmenis).
6) Pateiktos sąnaudos (atsižvelgiant į visas kapitalo investicijų į riedmenų įrenginių statybą eksploatacines išlaidas).
kur yra veiklos išlaidos,
Numatomas investicijų efektyvumo koeficientas,
Kapitalinės investicijos 1 tonai krovinio visame ruože,
T – kelionės laikas,
C – vienos tonos krovinio kaina.
Leidžia išsamiau įvertinti įvairių transportavimo planų variantų racionalizavimą, gana išsamiai išreiškiant kiekybinę ir vienu metu kelių ekonominių veiksnių įtaką.
Panagrinėkime transporto problemą, kurios optimalumo kriterijus yra minimalios viso krovinio pervežimo išlaidos. Krovinio vieneto gabenimo iš i-ojo išvykimo punkto į j-ąjį paskirties tašką tarifais pažymėkime – krovinio atsargas i-ajame išvykimo taške, – reikalavimus kroviniui i-oje išvykimo vietoje. j-asis paskirties taškas, o iki – krovinių, pervežtų iš i-ojo išvykimo punkto į j-ąją paskirties vietą, skaičius. Tada matematinė problemos formuluotė susideda iš minimalios funkcijos reikšmės nustatymo
sąlygomis
Kadangi kintamieji atitinka tiesinių lygčių (2) ir (3) sistemas bei neneigiamumo sąlygą (4), užtikrinamas esamo krovinio išvežimas iš visų išvykimo taškų, reikiamo krovinio kiekio pristatymas į kiekvieną paskirties vietą, ir atgalinis transportas neįtraukiamas.
Taigi, T problema yra LP problema m*n kintamųjų skaičius ir m+n apribojimų skaičius – lygybės.
Akivaizdu, kad bendras krovinių prieinamumas iš tiekėjų yra lygus , o bendra krovinių paklausa paskirties vietose yra lygi vnt. Jeigu bendra krovinių paklausa paskirties vietose yra lygi krovinių pasiūlai pradinėse vietose, t.y.
tada vadinamas tokios transporto problemos modelis uždaryta arba subalansuotas.
Yra keletas praktinių problemų, kai balanso sąlyga netenkinama. Tokie modeliai vadinami atviras. Galimi du atvejai:
Pirmuoju atveju visiškai patenkinti paklausą neįmanoma.
Tokia problema gali būti sumažinta iki įprasto transporto problemos taip. Jei paklausa viršija atsargas, t. y. fiktyvus ( m+1)-tas išvykimo taškas su krovinio rezervu ir tarifai yra nuliniai:
Tada reikia sumažinti
sąlygomis
Dabar panagrinėkime antrąjį atvejį.
Panašiai, kai fiktyvus ( n+1) paskirties vieta su paklausa ir atitinkamais tarifais laikoma lygia nuliui:
Tada atitinkama T problema bus parašyta taip:
Sumažinti
tokiomis sąlygomis:
Tai sumažina problemą iki įprastos transporto problemos, iš kurios optimalaus plano gaunamas optimalus pirminės problemos planas.
Toliau apžvelgsime uždarą transporto problemos modelį. Jei konkrečios problemos modelis yra atviras, tai remdamiesi tuo, kas išdėstyta aukščiau, uždavinio sąlygų lentelę perrašysime taip, kad būtų įvykdyta lygybė (5).
Kai kuriais atvejais reikia nurodyti, kad produktai negali būti gabenami tam tikrais maršrutais. Tada pervežimo šiais maršrutais kaštai nustatomi taip, kad viršytų didžiausias galimų transportavimo kaštus (kad būtų nuostolinga vežti nepasiekiamais maršrutais) – sprendžiant problemą minimaliai. Maksimaliai – atvirkščiai.
Kartais reikia atsižvelgti į tai, kad tarp kai kurių išsiuntimo vietų ir kai kurių vartojimo taškų buvo sudarytos sutartys dėl fiksuotų tiekimo kiekių, tada būtina toliau svarstyti garantuoto pristatymo apimtį. Norėdami tai padaryti, garantuoto tiekimo kiekis atimamas iš šių verčių:
· iš atitinkamo išsiuntimo punkto atsargų;
· pagal atitinkamos paskirties vietos poreikius.
Darbo pabaiga -
Ši tema priklauso skyriui:
Transporto užduotis
Pavyzdys.. keturios tam tikro ekonominio regiono įmonės produkcijos gamybai..
Jei jums reikia papildomos medžiagos šia tema arba neradote to, ko ieškojote, rekomenduojame pasinaudoti paieška mūsų darbų duomenų bazėje:
Ką darysime su gauta medžiaga:
Jei ši medžiaga jums buvo naudinga, galite ją išsaugoti savo puslapyje socialiniuose tinkluose:
Projektavimo parametrai. Šis terminas žymi nepriklausomus kintamuosius parametrus, kurie visiškai ir nedviprasmiškai lemia sprendžiamą projektavimo problemą. Projektavimo parametrai yra nežinomi dydžiai, kurių reikšmės apskaičiuojamos optimizavimo proceso metu. Bet kokie pagrindiniai arba išvestiniai dydžiai, naudojami kiekybiškai apibūdinti sistemą, gali būti naudojami kaip projektavimo parametrai. Taigi, tai gali būti nežinomos ilgio, masės, laiko, temperatūros reikšmės. Projektavimo parametrų skaičius apibūdina tam tikros projektavimo problemos sudėtingumo laipsnį. Paprastai projektinių parametrų skaičius žymimas n, o patys projektiniai parametrai – x su atitinkamais indeksais. Taigi n šio uždavinio projektiniai parametrai bus pažymėti
X1, X2, X3,...Xp.
Reikėtų pažymėti, kad projektiniai parametrai kai kuriuose šaltiniuose gali būti vadinami vidiniais kontroliuojamais parametrais.
Tikslinė funkcija. Tai išraiška, kurios vertę inžinierius siekia maksimaliai arba minimaliai. Tikslinė funkcija leidžia kiekybiškai palyginti du alternatyvius sprendimus. Matematiniu požiūriu tikslo funkcija apibūdina tam tikrą (n+1) matmenų paviršių. Jo vertė nustatoma pagal projektinius parametrus
M = M (x1,x2,…,xn).
Inžinerinėje praktikoje dažnai sutinkamų objektyvių funkcijų pavyzdžiai yra kaina, svoris, stiprumas, matmenys, efektyvumas. Jei projektinis parametras yra tik vienas, tai tikslo funkcija gali būti pavaizduota kreive plokštumoje (1 pav.). Jei yra du projektavimo parametrai, tai objektyvo funkcija bus vaizduojama kaip paviršius trimatėje erdvėje (2 pav.). Esant trims ar daugiau projektavimo parametrų, tikslinės funkcijos nurodyti paviršiai vadinami hiperpaviršiais ir negali būti pavaizduoti įprastomis priemonėmis. Optimizavimo procese didelį vaidmenį atlieka tikslo funkcijos paviršiaus topologinės savybės, nes nuo jų priklauso efektyviausio algoritmo pasirinkimas.
1 pav. Vienmatė tikslo funkcija.
2 pav. Dvimatė tikslo funkcija.
Tikslinė funkcija kai kuriais atvejais gali būti netikėčiausių formų. Pavyzdžiui, ji ne visada gali būti išreikšta uždara matematine forma; kitais atvejais tai gali būti atskira tiesinė funkcija. Norint nurodyti tikslo funkciją, kartais gali prireikti techninių duomenų lentelės (pavyzdžiui, vandens garų būklės lentelės) arba gali prireikti eksperimento. Kai kuriais atvejais projektavimo parametrai ima tik sveikųjų skaičių. Pavyzdys galėtų būti dantų skaičius pavarų dėžėje arba varžtų skaičius flanše. Kartais dizaino parametrai turi tik dvi reikšmes – taip arba ne. Į kokybinius parametrus, tokius kaip prekę įsigijusio pirkėjo pasitenkinimas, patikimumas, estetika, optimizavimo procese sunku atsižvelgti, nes jų beveik neįmanoma apibūdinti kiekybiškai. Tačiau, kad ir kokia forma būtų pateikta tikslo funkcija, ji turi būti nedviprasmiška projektinių parametrų funkcija.
Daugeliui optimizavimo problemų reikia įdiegti daugiau nei vieną tikslo funkciją. Kartais vienas iš jų gali būti nesuderinamas su kitu. Pavyzdys yra orlaivio konstrukcija, kai vienu metu reikalaujama didžiausio stiprumo, minimalaus svorio ir minimalių sąnaudų. Tokiais atvejais projektuotojas turi įvesti prioritetų sistemą ir kiekvienai tikslinei funkcijai priskirti tam tikrą bematį faktorių. Dėl to atsiranda „kompromisinė funkcija“, leidžianti optimizavimo proceso metu naudoti vieną sudėtinę tikslo funkciją.
Ieškokite minimumo ir maksimumo. Vieni optimizavimo algoritmai skirti surasti maksimumą, kiti – surasti minimumą. Tačiau, nepaisant sprendžiamos ekstremalios problemos tipo, galite naudoti tą patį algoritmą, nes sumažinimo problemą galima lengvai paversti maksimalia paieškos problema, pakeitus tikslo funkcijos ženklą. Ši technika pavaizduota 3 pav.
3 pav. Kai minimalaus uždavinio tikslo funkcijos ženklas pasikeičia į priešingą, jis paverčia jį maksimalia problema.
Dizaino erdvė. Tai yra srities, apibrėžtos visais n projektavimo parametrais, pavadinimas. Projektavimo erdvė nėra tokia didelė, kaip gali atrodyti, nes ją paprastai riboja daugybė sąlygų, susijusių su fiziniu problemos pobūdžiu. Apribojimai gali būti tokie stiprūs, kad problema neturės vieno patenkinamo sprendimo. Apribojimai skirstomi į dvi grupes: apribojimai – lygybė ir apribojimai – nelygybė.
Lygybės apribojimai – tai priklausomybės tarp projektavimo parametrų, į kurias reikia atsižvelgti ieškant sprendimo. Juose atsispindi gamtos dėsniai, ekonomika, teisė, vyraujantys skoniai ir reikalingų medžiagų prieinamumas. Apribojimų – lygybių skaičius gali būti bet koks. Jie atrodo kaip
C1 (X1, X2, X3, . . ., Xn) = 0,
C2 (X1, X2, X3, ..., X n) = 0,
..……………………………..
Cj(X1, X2, X 3,..., Xn) = 0.
Nelygybės apribojimai yra ypatingas apribojimų tipas, išreikštas nelygybėmis. Bendru atveju jų gali būti tiek, kiek norite, ir visi jie turi formą
z1 ?r1(X1, X2, X3, . . ., Xn) ?Z1
z2 ?r2(X1, X2, X3, . . ., Xn) ?Z2
………………………………………
zk ?rk(X1, X2, X3, . . ., Xn) ?Zk
Pažymėtina, kad labai dažnai dėl apribojimų optimali tikslo funkcijos reikšmė nepasiekiama ten, kur jos paviršius turi nulinį gradientą. Dažnai geriausias sprendimas atitinka vieną iš projektavimo erdvės ribų.
Tiesioginiai ir funkciniai apribojimai. Tiesioginiai apribojimai turi formą
xni? xi? xвi pas i? ,
čia xнi, xвi yra mažiausios ir didžiausios leistinos i-ojo valdomo parametro reikšmės; n yra valdomų parametrų erdvės matmuo. Pavyzdžiui, daugelio objektų elementų parametrai negali būti neigiami: xнi ? 0 (geometriniai matmenys, elektrinė varža, masė ir kt.).
Funkciniai apribojimai, kaip taisyklė, reiškia išvesties parametrų, kurie nėra įtraukti į tikslinę funkciją, veikimo sąlygas. Funkciniai apribojimai gali būti:
- 1) lygybių tipas
- w(X) = 0; (2.1)
- 2) nelygybių tipas
tz (X) › 0, (2.2)
kur w(X) ir q(X) yra vektorinės funkcijos.
Tiesioginiai ir funkciniai apribojimai sudaro leistiną paieškos sritį:
ХД = (Х | w(Х) = 0, ц (Х)›0, xi › xнi ,
xi ‹ xвi už i ? ).
Jei apribojimai (2.1) ir (2.2) sutampa su veikimo sąlygomis, tada leistina sritis dar vadinama XP veikimo sritimi.
Bet kuris iš kompaktiniam diskui priklausančių taškų X yra įmanomas problemos sprendimas. Parametrinė sintezė dažnai keliama kaip bet kokių galimų sprendimų nustatymo problema. Tačiau daug svarbiau yra išspręsti optimizavimo problemą – rasti optimalų sprendimą tarp galimų.
Vietinis optimalumas. Tai yra taško projektavimo erdvėje pavadinimas, kuriame tikslinė funkcija turi didžiausią vertę, palyginti su jos vertėmis visuose kituose taškuose, esančiuose šalia jos. 4 paveiksle parodyta vienmatė tikslo funkcija, turinti du vietinius optimalius. Dažnai projektavimo erdvėje yra daug vietinių optimalų, todėl reikia stengtis, kad pirmasis nebūtų klaidingas dėl optimalaus problemos sprendimo.
4 pav. Savavališka tikslo funkcija gali turėti keletą lokalinių optimalų.
Pasaulinis optimalumas yra optimalus sprendimas visai dizaino erdvei. Jis yra geresnis už visus kitus sprendimus, atitinkančius vietinius optimalus, ir būtent tai yra tai, ko dizaineris ieško. Gali būti, kad skirtingose projektavimo erdvės dalyse yra keletas vienodų globalių optimalų. Tai leidžia pasirinkti geriausią variantą iš vienodų optimalių variantų, remiantis tikslo funkcija. Tokiu atveju dizaineris gali pasirinkti parinktį intuityviai arba remdamasis gautų variantų palyginimu.
Kriterijų parinkimas. Pagrindinė problema nustatant ekstremalias problemas yra tikslo funkcijos formulavimas. Tikslinės funkcijos pasirinkimo sunkumai slypi tame, kad bet kuris techninis objektas iš pradžių turi vektorinį optimalumo kriterijų (daugiakriterijų) pobūdį. Be to, patobulinus vieną iš išvesties parametrų, kaip taisyklė, pablogėja kitas, nes visi išvesties parametrai yra tų pačių valdomų parametrų funkcijos ir negali keistis nepriklausomai vienas nuo kito. Tokie išvesties parametrai vadinami konfliktiniais parametrais.
Turi būti viena tikslinė funkcija (unikalumo principas). Kelių kriterijų problemos redukavimas iki vieno kriterijaus uždavinio vadinamas vektorinio kriterijaus konvoliucija. Užduotis surasti jo ekstremumą sumažinama iki matematinio programavimo problemos. Atsižvelgiant į tai, kaip skaliarinėje kokybės funkcijoje parenkami ir derinami išvesties parametrai, išskiriami daliniai, adityviniai, dauginamieji, minimalūs, statistiniai kriterijai ir kiti kriterijai. Techninio objekto projektavimo techninėse specifikacijose nurodyti pagrindiniai išėjimo parametrų reikalavimai. Šie reikalavimai išreiškiami konkrečiais skaitiniais duomenimis, jų kitimo diapazonu, eksploatavimo sąlygomis ir priimtinomis mažiausiomis arba didžiausiomis vertėmis. Reikalingi ryšiai tarp išvesties parametrų ir techninių reikalavimų (TR) vadinami veikimo sąlygomis ir rašomi tokia forma:
yi< TTi , i О ; yi >TTj, j O;
yr = TTr ± ?yr; r O .
kur yi, yj, yr - išvesties parametrų rinkinys;
TTi, TTj, TTr - reikalingos atitinkamų išvesties parametrų kiekybinės vertės pagal technines specifikacijas;
Yr – leistinas r-ojo išėjimo parametro nuokrypis nuo techninėse specifikacijose nurodytos TTr reikšmės.
Eksploatacinės sąlygos turi lemiamą reikšmę kuriant techninius prietaisus, nes projektavimo užduotis yra parinkti tokį projektinį sprendimą, kuriame visos eksploatavimo sąlygos būtų geriausiai tenkinamos per visą išorinių parametrų pokyčių diapazoną ir kai tenkinami visi techninių specifikacijų reikalavimai. .
Konkretūs kriterijai gali būti naudojami tais atvejais, kai tarp išvesties parametrų galima išskirti vieną pagrindinį parametrą yi(X), kuris labiausiai atspindi projektuojamo objekto efektyvumą. Šis parametras laikomas tikslo funkcija. Tokių parametrų pavyzdžiai: energetiniam objektui – galia, technologinei mašinai – našumas, transporto priemonei – keliamoji galia. Daugeliui techninių objektų šis parametras yra kaina. Visų kitų objekto išvesties parametrų veikimo sąlygos vadinamos funkciniais apribojimais. Optimizavimas, pagrįstas tokia formuluote, vadinamas optimizavimu pagal tam tikrą kriterijų.
Šio metodo privalumas yra jo paprastumas, reikšmingas trūkumas yra tai, kad didelę naudingumo ribą galima gauti tik pagrindiniam parametrui, kuris yra priimtas kaip tikslinė funkcija, o kiti išvesties parametrai neturės jokių ribinių dydžių.
Svertinio priedo kriterijus naudojamas tada, kai eksploatacinės sąlygos leidžia atskirti dvi išėjimo parametrų grupes. Pirmoji grupė apima išvesties parametrus, kurių reikšmės optimizavimo proceso metu turėtų būti padidintos y+i(X) (našumas, atsparumas triukšmui, veikimo be gedimų tikimybė ir kt.), antroji grupė – išėjimo parametrai, kurių vertės turėtų būti sumažintos y-i (X) (kuro sąnaudos, pereinamojo proceso trukmė, viršijimas, poslinkis ir kt.). Sujungus kelis išvesties parametrus, kurie paprastai turi skirtingus fizinius matmenis, į vieną skaliarinę tikslo funkciją, reikia iš anksto normalizuoti šiuos parametrus. Toliau bus aptariami parametrų normalizavimo metodai. Kol kas darysime prielaidą, kad visi y(X) yra bedimensiniai ir tarp jų nėra tokių, kurie atitiktų lygybės tipo veikimo sąlygas. Tada tikslo funkcijos sumažinimo atveju vektoriaus kriterijaus konvoliucija bus tokia forma
kur aj>0 yra svertinis koeficientas, nulemiantis j-ojo išvesties parametro svarbos laipsnį (dažniausiai aj pasirenka projektuotojas ir optimizavimo proceso metu išlieka pastovus).
Tikslinė funkcija formoje (2.1), išreiškianti adityvinį kriterijų, gali būti rašoma ir tuo atveju, kai visos arba pagrindinės atlikimo sąlygos turi lygybių formą. Tada tikslo funkcija
nustato yj(X) vidutinį kvadratinį artėjimą prie pateiktų techninių reikalavimų TTj.
Dauginimo kriterijus galima naudoti tais atvejais, kai nėra lygybės tipo veikimo sąlygų ir išvesties parametrai negali turėti nulinių reikšmių. Tada multiplikacinė tikslo funkcija, kurią reikia sumažinti, turi formą
Vienas reikšmingiausių tiek adityvinių, tiek dauginamųjų kriterijų trūkumų yra tai, kad formuluojant problemą neatsižvelgta į techninius reikalavimus išvesties parametrams.
Funkcijų formos kriterijus naudojamas, kai užduotyje nustatytas geriausios nurodytos (atskaitos) charakteristikos yCT(X, y) atitikimas su atitinkama projektuojamo objekto išvesties charakteristika y(X, y), kur y yra koks nors kintamasis, pavyzdžiui, dažnis, laikas, pasirinktas fazės kintamasis. Šios užduotys apima: automatinės valdymo sistemos, kuri užtikrina reikiamo tipo pereinamąjį procesą kontroliuojamam parametrui, projektavimą; tranzistoriaus modelio parametrų, užtikrinančių maksimalų sutapimą tarp jo teorinių srovės-įtampos charakteristikų ir eksperimentinių, nustatymas; ieškoti sijų sekcijų parametrų, kurių reikšmės geriausiai sutampa su pateiktą įtempių diagramą su apskaičiuotąja ir kt.
Tam tikro optimizavimo kriterijaus naudojimas šiais atvejais susijęs su nuolatinių charakteristikų pakeitimu baigtiniu mazginių taškų rinkiniu ir vienos iš šių tikslinių funkcijų, kurias reikia sumažinti, pasirinkimas:
čia p – mazginių taškų uj skaičius kintamojo u ašyje; aj - svoriniai koeficientai, kurių reikšmės yra didesnės, tuo mažesnis nuokrypis y(X, φj) - yTT(X, φj) turi būti gautas j-ajame taške.
Maximin (minimax) kriterijai leidžia pasiekti vieną iš optimalaus dizaino tikslų – kuo geriau patenkinti eksploatacines sąlygas.
Įveskime kiekybinį j-osios veiklos sąlygos įvykdymo laipsnio įvertinimą, pažymime zj ir pavadinkime parametro yj našumo rezervu. J-ojo išvesties parametro paraštės apskaičiavimas gali būti atliekamas įvairiais būdais, pavyzdžiui,
čia aj yra svorio koeficientas; yjnom - vardinė j-ojo išėjimo parametro vertė; dj yra reikšmė, apibūdinanti j-ojo išvesties parametro sklaidą.
Čia daroma prielaida, kad visi santykiai redukuojami iki formos yi< TТj. Если yi >TTj, tada -yj< -TТj . Следует принимать аj >1 (rekomenduojamos reikšmės 5 ? aj ? 20), jei norima pasiekti j-ąjį techninį reikalavimą su tam tikra paklaida, t. y. yj = TTj ± ?yj; aj=l, jei reikia gauti didžiausią įmanomą įvertį zj.
Techninės sistemos veikimo kokybę apibūdina išėjimo parametrų vektorius, taigi ir vektorius Z=(zm,zm,…,zm). Todėl tikslinė funkcija turėtų būti suformuota kaip kokia nors vertinimo vektoriaus funkcija μ(Z). Pavyzdžiui, jei tikslinė funkcija laiko tik to išvesties parametro rezervą, kuris tam tikrame taške X yra pats blogiausias techninių specifikacijų reikalavimų tenkinimo požiūriu, tada
čia m – darbingumo rezervų skaičius.
Dabar natūralu iškelti tokią paieškos strategiją X, kuri maksimaliai padidintų rezervų minimumą, t.y.
kur HD yra paieškos sritis.
Optimizavimo kriterijus su tikslo funkcija (2.6) vadinamas maksimalaus kriterijumi.
Statistiniai kriterijai. Optimizavimas naudojant statistinius kriterijus yra skirtas gauti maksimalią našumo tikimybę P. Ši tikimybė laikoma tiksline funkcija. Tada mes turime problemą
Valdomųjų ir išėjimo parametrų normalizavimas. Valdomųjų parametrų erdvė yra metrinė. Todėl, renkantis paieškos žingsnių kryptis ir reikšmes, būtina įvesti vienokią ar kitokią normą, identifikuojamą su atstumu tarp dviejų taškų. Pastaroji daro prielaidą, kad visi valdomi parametrai turi tą patį matmenį arba yra be matmenų.
Galimi įvairūs normavimo būdai. Kaip pavyzdį apsvarstykite logaritminio normalizavimo metodą, kurio pranašumas yra perėjimas nuo absoliučių parametrų prieaugių prie santykinių. Šiuo atveju i ir valdomas parametras ui paverčiamas bedimensiniu xi taip:
kur oi yra koeficientas, skaičiais lygus parametro ui vienetui.
Išėjimo parametrų normalizavimas gali būti atliekamas naudojant svorinius koeficientus, kaip ir adityviniame kriterijuje, arba pereinant nuo уj prie našumo rezervų zj pagal (2.5).
