Jūs žinote, ką reiškia optimizuoti sistemą, kad gautumėte geriausią įmanomą rezultatą, jei esate inžinieriaus studentas arba inžinierius.
Sprendimo optimizavimas yra raktas į sėkmę visame kame – nuo tiltų kūrimo iki programinės įrangos kūrimo.
Šiuo metu kyla mintis apie pagrindinį įmanomą sprendimą.
Tai pagrindinė linijinio programavimo idėja, leidžianti išsiaiškinti, kuris iš galimų sprendimų rinkinio yra geriausias.
Bet kodėl tai taip svarbu? Šiame straipsnyje kalbėsiu apie pagrindinius įmanomus sprendimus ir kaip juos galima panaudoti sprendžiant inžinerines problemas realiame pasaulyje.
Pakalbėsiu apie tai, kaip juos rasti, iš ko jie pagaminti ir kodėl jie svarbūs.
Taigi, nesvarbu, ar esate patyręs inžinierius, ar tik pradedantis studentas, atvykite su mumis, kai pasineriu į pagrindinių įmanomų sprendimų pasaulį ir parodysiu, kaip panaudoti linijinio programavimo galią.
Pagrindinio įmanomo sprendimo supratimas
Oficialus apibrėžimas:
Pagrindinis linijinio programos modelio sprendimas, kuriame visi kintamieji yra neneigiami.
Pagrindinis įmanomas sprendimas (BFS) yra pagrindinė linijinio programavimo idėja, padedanti rasti geriausius sprendimus.
BFS yra sprendimas, turintis mažiausią įmanomą nulinių kintamųjų skaičių.
Tai galimų sprendimų daugiakampio kampas.
Kitaip tariant, BFS yra pagrindinis sprendimas, kuris atitinka neneigiamus suvaržymus ir yra įmanomoje srityje arba probleminėje srityje.
Optimalaus pagrindinio įmanomo sprendimo radimas
Norėdami rasti geriausią BFS, turime atlikti šiuos veiksmus:
- Parašykite programą standartine forma tiesinei sekai.
- Paverskite nelygybių sistemą padidinta matrica.
- Išsiaiškinkite, kurie kintamieji yra pagrindiniai, o kurie ne.
- Išsiaiškinkite, kokie yra pagrindiniai kintamieji, palyginti su kitais kintamaisiais.
- Įdėkite šias išraiškas į tikslo funkciją, kad gautumėte tik tų kintamųjų, kurie nėra pagrindiniai, funkciją.
- Raskite nepagrindinį kintamąjį, kurį galima padidinti nepažeidžiant jokių apribojimų ir kuris pagerins tikslo funkciją.
Šis kintamasis dabar yra pagrindinis kintamasis, o vienas iš kitų pagrindinių kintamųjų nebėra pagrindinis kintamasis.
Jei yra optimalus sprendimas, jis turi būti viename iš srities, kurioje galimi sprendimai, galų arba viršūnių.
Taigi, jei LP turi optimalų sprendimą, jis turi optimalų sprendimą kraštutiniame įmanomos aibės taške.
Be to, visada yra optimalus BFS, jei yra optimalus sprendimas.
Simplekso metodo naudojimas norint rasti optimalų BFS
Simplekso metodas yra linijinio programavimo problemų sprendimo algoritmas.
Jis perkeliamas iš vieno BFS į „gretimą“ BFS naudojant sukimosi procedūrą.
Susukimo procedūroje pasirenkamas ne pagrindinis kintamasis, kuris tampa pagrindiniu kintamuoju, o tada dabartinis BFS naudojamas naujiems pagrindiniams kintamiesiems išspręsti.
Kai negalima pakeisti jokio nepagrindinio kintamojo, kad tikslo funkcija būtų geresnė, atliekamas algoritmas.
Kodėl pagrindiniai įmanomi sprendimai yra labai svarbūs sprendžiant sudėtingas inžinerines problemas
Vis dar sunku suprasti? Šiek tiek pakeisiu požiūrį:
Kam vis tiek reikia paprastų, veiksmingų atsakymų? Tiesiog sudėkite viską ir tikėkitės geriausio.
Galų gale, kam reikia optimizavimo, kai chaosas yra daug linksmesnis? Sveiki atvykę į neneigiamų kintamųjų pasaulį, kuriame viskas yra tik pasiūlymas, o nesėkmė beveik neabejotina.
Ar tai yra?
Panagrinėkime, kodėl iš pažiūros pagrindinė pagrindinių galimų sprendimų samprata yra ne kas kita, nei pagrindinė ir kodėl jie gali būti tik raktas sprendžiant net sudėtingiausias inžinerines problemas.
Gerai, tai buvo tik pokštas, panašus į TV reklamą.
Dabar grįžkime prie paaiškinimo.
Pagrindinio įmanomo sprendimo radimas
Pagrindinis įmanomas sprendimas (BFS) yra linijinio optimizavimo problemos sprendimas, atitinkantis visus apribojimus ir turintis mažiausiai nulinių kintamųjų.
Kiekvienas BFS yra geometriniu požiūriu įmanomų sprendimų daugiakampio kampas.
Jei yra geriausias sprendimas, turi būti ir geriausias pirmasis žingsnis.
Šiame straipsnyje kalbėsime apie tai, kaip rasti pradinį pagrindinį įmanomą sprendimą, kaip rasti visus pagrindinius įmanomus sprendimus ir kaip rasti pagrindinį įmanomą sprendimą be kintamųjų.
Pradinio pagrindinio įmanomo sprendimo radimas
Galime naudoti skirtingus metodus, priklausomai nuo to, kaip problema nustatyta, kad surastume pradinį pagrindinį sprendimą, tinkantį tiesinio optimizavimo problemai.
Vienas iš būdų yra pridėti nelygybių suvaržymus laisvus kintamuosius ir visus kitus kintamuosius nustatyti į nulį.
Laisvieji kintamieji tampa pagrindiniais kintamaisiais, o likusieji yra ne pagrindiniai kintamieji.
Dviejų fazių simplekso metodas yra dar vienas problemos sprendimo būdas.
Šis metodas apima papildomo linijinio programavimo problemos sprendimą, kad būtų galima rasti pradinį pagrindinį įmanomą sprendimą.
Suradus pradinį pagrindinį įmanomą sprendimą, paprastasis metodas gali būti naudojamas norint pereiti nuo vieno pagrindinio įmanomo sprendimo prie kito ir tada prie geriausio sprendimo.
Visų pagrindinių įmanomų sprendimų paieška
Gali būti daugiau nei vienas pagrindinis sprendimas, tinkantis linijinei programai.
Mes galime pakeisti sistemą pridėdami laisvųjų kintamųjų ir tada naudoti naują sistemą, kad surastume visus pagrindinius įmanomus linijinės programos sprendimus.
Tada šie pagrindiniai galimi sprendimai naudojami ieškant pagrindinių galimų pradinės problemos sprendimų.
Rasti pagrindinį įmanomą sprendimą be jokių kintamųjų
Turime naudoti laisvuosius kintamuosius, kad atsikratytume mažesnių nei suvaržymų, kad galėtume rasti pagrindinį sprendimą, kuris veiktų be laisvųjų kintamųjų.
Laisvas kintamasis yra tik skirtumas tarp dešinės ir kairiosios apribojimo pusės.
Pavyzdžiui, pirmajam apribojimui apibrėžiame laisvąjį kintamąjį x4 = 14 - 2x1 - x2 - x3. Kalbant apie šį naują kintamąjį, pirmasis apribojimas yra tiesiog lygus x4 ≥ 0, o tai yra x4 teigiamumo apribojimas.
Kai pridedame šiuos laisvus kintamuosius, gauname linijinę programą, kuri yra tokia pati kaip ir pradinė, išskyrus tai, kad visi apribojimai yra lygtys arba apribojimai, kurie sako, kad kažkas yra teigiama.
Pagrindinių kintamųjų, kurių reikšmės pagrindiniame sprendime yra kitos nei nulis, aibė vadinama baze.
Kintamieji, kurių reikšmė pagrindiniame sprendime yra nulis, nėra pagrindiniai kintamieji.
Norėdami rasti geriausią sprendimą, turime rasti vektorių x, kuris atitiktų visas taisykles ir gautų didžiausią arba mažiausią tikslo reikšmę.
Tačiau ieškant geriausio sprendimo reikia daugiau žingsnių, nei rasti sprendimą, kuris veikia ir neturi kintamųjų.
Ne visada įmanoma rasti pagrindinį sprendimą be kintamųjų, ypač problemų, susijusių su mažesniais apribojimais.
Norėdami rasti pagrindinį įmanomą sprendimą, turite naudoti simplekso metodą arba kitą linijinio programavimo algoritmą, kad surastumėte sprendimą, atitinkantį visus apribojimus ir turintį mažiausiai nulinių kintamųjų.
Pagrindinio įmanomo sprendimo savybės ir reikšmė
Pagrindinio įmanomo sprendimo savybės
Pagrindinis įmanomas sprendimas turi daugiausia m kintamųjų, kurie nėra lygūs nuliui, ir mažiausiai nm kintamųjų, kurie yra lygūs nuliui, kur n yra sprendimo kintamųjų skaičius, o m yra apribojimų skaičius.
BFS yra galimų sprendimų daugiakampio kampas, o kiekvienas BFS turi n aktyvių apribojimų, kurie yra tiesiškai nepriklausomi.
Jei yra geriausias sprendimas, turi būti ir geriausias pirmasis žingsnis.
Svarbiausias dalykas kalbant apie pagrindinius galimus sprendimus yra tai, kad jie yra linijinio programavimo problemos išgaubtų sprendimų rinkinio galai.
Norint rasti geriausią atsakymą, simplekso algoritmas eina per BFS seriją.
Simplex algoritmas organizuotai ieško visų pagrindinių galimų sprendimų, kad rastų geriausią.
Pagrindinio įmanomo sprendimo reikšmė
Svarbu rasti pagrindinį įmanomą sprendimą, nes jis padeda rasti geriausią atsakymą į linijinio programavimo problemas.
Tai taip pat suteikia galimybę pradėti sudėtingus algoritmus ir gali būti naudojamas išsiaiškinti, ar linijinė programa įmanoma, ar ne.
Norėdami rasti visus pagrindinius įmanomus linijinės programos sprendimus, galite pakeisti sistemą pridėdami laisvų kintamųjų ir tada naudoti pakeistą sistemą, kad rastumėte visus pagrindinius galimus sprendimus.
Tada šie pagrindiniai galimi sprendimai naudojami ieškant pagrindinių galimų pradinės problemos sprendimų.
Vaizdo įrašas: pagrindiniai galimi sprendimai
Patarimas: jei reikia, įjunkite antraštės mygtuką. Jei nesate susipažinę su šnekamąja kalba, nustatymų mygtuke pasirinkite „automatinis vertimas“. Gali tekti pirmiausia spustelėti vaizdo įrašo kalbą, kad jūsų mėgstamiausia kalba taptų prieinama versti.
Naudojimo atvejai
| Naudojamas: | Apibūdinimas: |
|---|---|
| Išteklių paskirstymas: | BFS gali būti naudojamas ribotiems ištekliams padalyti tarp kelių projektų, kad kuo mažiau būtų galima nuveikti daugiausiai. Šis metodas gali būti naudojamas įvairiose srityse, pavyzdžiui, transporto, ūkininkavimo ir finansų srityse. |
| Tinklo optimizavimas: | BFS gali būti naudojamas siekiant pagerinti ryšių, transporto ir logistikos tinklų veikimą. BFS gali padėti rasti geriausius prekių ir paslaugų maršrutus, sutrumpinti transportavimui skiriamą laiką ir pinigus bei pagreitinti ir tiksliau pristatyti prekes. |
| Gamybos planavimas: | BFS gali būti naudojamas planuojant gamybą taip, kad ištekliai, tokie kaip darbo jėga, žaliavos ir įranga, būtų naudojami geriausiu būdu, kad būtų galima išnaudoti visas jų galimybes. BFS gali padėti sumažinti gamybos sąnaudas, sumažinti atliekas ir pagerinti efektyvumą. |
| Finansų planavimas: | Finansų planavime BFS gali būti naudojamas siekiant optimizuoti investicijų portfelius, sumažinti riziką ir susigrąžinti daugiausia pinigų. BFS gali padėti rasti geriausią būdą padalyti turtą, sumažinti sandorių išlaidas ir užsidirbti daugiau pinigų. |
| Tiekimo grandinės valdymas: | BFS gali būti naudojamas siekiant pagerinti prekių ir paslaugų srautą iš tiekėjų klientams, kaip tiekimo grandinės valdymo dalį. BFS gali padėti išsiaiškinti geriausią atsargų kiekį po ranka, sutrumpinti pristatymo laiką ir pagerinti klientų aptarnavimą. |
Išvada
Kai šis pagrindinių galimų sprendimų žvilgsnis baigiasi, akivaizdu, kad jie yra svarbus įrankis bet kuriam inžinieriui ar inžinieriaus studentui.
Nuo geriausio būdo sukurti sudėtingą sistemą iki didžiausio turimų išteklių panaudojimo – pagrindiniai įmanomi sprendimai suteikia pagrindą pasiekti geriausią įmanomą rezultatą.
Tačiau jie ne tik yra naudingi, bet ir parodo, kokia elegantiška ir graži gali būti matematika.
Nuostabu, kad sudėtingas problemas galite suvesti į paprastą lygčių rinkinį ir tada panaudoti tas lygtis sprendžiant problemas realiame pasaulyje.
Tai geras priminimas, kad inžinerija yra skirta problemų sprendimui ir kad naudodamiesi matematikos galia galime rasti atsakymus, kurie kažkada buvo manomi neįmanomi.
Taigi, mokydamiesi daugiau apie inžineriją, atminkite, ką sužinojote apie paprastus veikiančius sprendimus ir naudokite juos, kad pasaulis taptų geresnis ir efektyvesnis.
Nuorodos ir nuorodos
Knygos:
- Linijinis programavimas: pagrindai ir plėtiniai
- Linijinis programavimas: teorija ir taikymas
Pasidalinti…
