Če ste študent strojništva ali inženir, veste, kaj pomeni optimizirati sistem za doseganje najboljših možnih rezultatov.
Optimizacija rešitve je ključ do uspeha pri vsem, od gradnje mostov do izdelave programske opreme.
Na tej točki se pojavi ideja o osnovni izvedljivi rešitvi.
To je osnovna ideja linearnega programiranja, ki vam omogoča, da ugotovite, katera od nabora možnih rešitev je najboljša.
Toda zakaj je to tako pomembno? V tem članku bom govoril o osnovnih izvedljivih rešitvah in o tem, kako jih je mogoče uporabiti za reševanje inženirskih problemov v resničnem svetu.
Govoril bom o tem, kako jih najti, iz česa so narejeni in zakaj so pomembni.
Ne glede na to, ali ste izkušen inženir ali študent, ki šele začenja, pojdite z nami, ko se potopim v svet osnovnih izvedljivih rešitev in vam pokažem, kako uporabljati moč linearnega programiranja.
Razumevanje osnovne izvedljive rešitve
Formalna opredelitev:
Osnovna rešitev modela linearnega programa, v katerem so vse spremenljivke nenegativne.
Osnovna izvedljiva rešitev (BFS) je ključna ideja v linearnem programiranju, ki pomaga najti najboljše rešitve.
BFS je rešitev z najmanjšim možnim številom neničelnih spremenljivk.
Je kotiček poliedra izvedljivih rešitev.
Z drugimi besedami, BFS je osnovna rešitev, ki ustreza nenegativnim omejitvam in je v izvedljivi regiji ali problemskem območju.
Iskanje optimalne osnovne izvedljive rešitve
Da bi našli najboljši BFS, moramo storiti naslednje:
- Napišite program v standardni obliki za linearno zaporedje.
- Sistem neenačb spremenite v razširjeno matriko.
- Ugotovite, katere spremenljivke so osnovne in katere ne.
- Ugotovite, katere so osnovne spremenljivke glede na druge spremenljivke.
- Vstavite te izraze v ciljno funkcijo, da dobite funkcijo samo spremenljivk, ki niso osnovne.
- Poiščite nebazično spremenljivko, ki jo je mogoče povečati, ne da bi kršili omejitve, in ki bo izboljšala funkcijo cilja.
Ta spremenljivka je zdaj osnovna spremenljivka, ena od drugih osnovnih spremenljivk pa ni več osnovna spremenljivka.
Če obstaja optimalna rešitev, mora biti na enem od koncev ali oglišč območja, kjer so možne rešitve.
Torej, če ima LP optimalno rešitev, ima optimalno rešitev na skrajni točki izvedljive množice.
Prav tako vedno obstaja optimalen BFS, če obstaja optimalna rešitev.
Uporaba metode Simplex za iskanje optimalne BFS
Simpleksna metoda je algoritem za reševanje problemov linearnega programiranja.
Premika se iz ene BFS v "sosednjo" BFS z uporabo vrtilnega postopka.
V vrtilnem postopku je izbrana neosnovna spremenljivka, ki postane osnovna spremenljivka, nato pa se trenutni BFS uporabi za rešitev novih osnovnih spremenljivk.
Ko nobene nebazične spremenljivke ni mogoče spremeniti, da bi bila funkcija cilja boljša, je algoritem končan.
Zakaj so osnovne izvedljive rešitve ključne za reševanje kompleksnih inženirskih problemov
Še vedno težko razumeti? Naj malo spremenim pogled:
Kdo sploh potrebuje preproste, izvedljive odgovore? Samo vrzite vse skupaj in upajte na najboljše.
Konec koncev, kdo potrebuje optimizacijo, ko je kaos toliko bolj zabaven? Dobrodošli v svetu nenegativnih spremenljivk, kjer je vse le predlog in je neuspeh skoraj gotov.
Ali pač?
Raziščimo, zakaj je navidezno osnovni koncept osnovnih izvedljivih rešitev vse prej kot bazičen in zakaj so lahko le ključ do rešitve celo najbolj zapletenih inženirskih problemov.
V redu, to je bila samo šala, ki je izgledala kot TV oglas.
Zdaj pa se vrnimo k razlagi.
Iskanje osnovne izvedljive rešitve
Osnovna izvedljiva rešitev (BFS) je rešitev problema linearne optimizacije, ki izpolnjuje vse omejitve in ima najmanjše število neničelnih spremenljivk.
Vsak BFS je kotiček poliedra izvedljivih rešitev z geometrijskega vidika.
Če obstaja najboljša rešitev, mora obstajati tudi najboljši prvi korak.
V tem članku bomo govorili o tem, kako najti začetno osnovno izvedljivo rešitev, kako poiskati vse osnovne izvedljive rešitve in kako najti osnovno izvedljivo rešitev brez spremenljivk.
Iskanje začetne osnovne izvedljive rešitve
Uporabimo lahko različne metode, odvisno od tega, kako je problem nastavljen, da poiščemo začetno osnovno rešitev, ki deluje za problem linearne optimizacije.
Eden od načinov je, da omejitvam na neenakosti dodate spremenljivke ohlapnosti in nastavite vse druge spremenljivke na nič.
Slack spremenljivke postanejo osnovne spremenljivke, ostale pa so nebazične spremenljivke.
Dvofazna Simplex metoda je še en način za rešitev problema.
Ta metoda vključuje reševanje dodatnega problema linearnega programiranja za iskanje začetne osnovne rešitve, ki je izvedljiva.
Ko je najdena začetna osnovna izvedljiva rešitev, je mogoče uporabiti metodo Simplex za prehod od ene osnovne izvedljive rešitve k naslednji in nato do najboljše rešitve.
Iskanje vseh osnovnih izvedljivih rešitev
Obstaja lahko več kot ena osnovna rešitev, ki deluje za linearni program.
Sistem lahko spremenimo z dodajanjem spremenljivk slack in nato uporabimo nov sistem za iskanje vseh osnovnih izvedljivih rešitev za linearni program.
Nato se te osnovne izvedljive rešitve uporabijo za iskanje osnovnih izvedljivih rešitev za prvotni problem.
Iskanje osnovne izvedljive rešitve brez ohlapnih spremenljivk
Uporabiti moramo začasne spremenljivke, da se znebimo omejitev manj kot, da lahko najdemo osnovno rešitev, ki deluje brez ohlapnih spremenljivk.
Slack spremenljivka je le razlika med desno stranjo omejitve in levo stranjo.
Na primer, za prvo omejitev definiramo ohlapno spremenljivko x4 = 14 - 2x1 - x2 - x3. V smislu te nove spremenljivke je prva omejitev enakovredna preprosto x4 ≥ 0, kar je omejitev pozitivnosti za x4.
Ko dodamo te ohlapne spremenljivke, dobimo linearni program, ki je enak prvotnemu, le da so vse omejitve enačbe ali omejitve, ki pravijo, da je nekaj pozitivno.
Množico osnovnih spremenljivk, ki imajo v osnovni rešitvi vrednosti, ki niso nič, imenujemo baza.
Spremenljivke, ki imajo v osnovni rešitvi vrednost nič, niso osnovne spremenljivke.
Da bi našli najboljšo rešitev, moramo najti vektor x, ki ustreza vsem pravilom in ima največjo ali najmanjšo vrednost za cilj.
Toda iskanje najboljše rešitve zahteva več korakov kot le iskanje rešitve, ki deluje in nima ohlapnih spremenljivk.
Ni vedno mogoče najti osnovne rešitve brez ohlapnih spremenljivk, zlasti za težave z manj kot omejitvami.
Če želite najti osnovno izvedljivo rešitev, morate uporabiti metodo simpleksa ali drug algoritem linearnega programiranja, da poiščete rešitev, ki izpolnjuje vse omejitve in ima najmanj spremenljivk, ki niso nič.
Lastnosti in pomen osnovne izvedljive rešitve
Lastnosti osnovne izvedljive rešitve
Osnovna izvedljiva rešitev ima največ m spremenljivk, ki niso nič, in vsaj nm spremenljivk, ki so nič, kjer je n število odločitvenih spremenljivk in m število omejitev.
BFS je vogal poliedra možnih rešitev in vsak BFS ima n aktivnih omejitev, ki so linearno neodvisne.
Če obstaja najboljša rešitev, mora obstajati tudi najboljši prvi korak.
Najpomembnejša stvar pri osnovnih izvedljivih rešitvah je, da so konci nabora konveksnih rešitev za problem linearnega programiranja.
Za iskanje najboljšega odgovora gre algoritem simplex skozi vrsto BFS.
Algoritem Simplex na organiziran način preišče vse osnovne možne rešitve, da bi našel najboljšo.
Pomen osnovne izvedljive rešitve
Iskanje osnovne rešitve, ki je mogoča, je pomembno, ker pomaga najti najboljši odgovor na težave linearnega programiranja.
Prav tako daje zapletenim algoritmom začetek in se lahko uporabi za ugotovitev, ali je linearni program možen ali ne.
Če želite poiskati vse osnovne izvedljive rešitve za linearni program, lahko spremenite sistem z dodajanjem spremenljivk slack in nato uporabite spremenjen sistem za iskanje vseh osnovnih izvedljivih rešitev.
Nato se te osnovne izvedljive rešitve uporabijo za iskanje osnovnih izvedljivih rešitev za prvotni problem.
Video: Osnovne izvedljive rešitve
Nasvet: Vklopite gumb za napise, če ga potrebujete. V gumbu z nastavitvami izberite »samodejno prevajanje«, če govorjenega jezika niste seznanjeni. Morda boste morali najprej klikniti jezik videoposnetka, preden postane vaš najljubši jezik na voljo za prevod.
Primeri uporabe
| Uporablja se v: | Opis: |
|---|---|
| Dodelitev sredstev: | BFS se lahko uporablja za razdelitev omejenih virov med več projektov, tako da je mogoče narediti največ z najmanj. Ta metoda se lahko uporablja na številnih različnih področjih, kot so prevoz, kmetijstvo in finance. |
| Optimizacija omrežja: | BFS se lahko uporablja za izboljšanje delovanja komunikacijskih, transportnih in logističnih omrežij. BFS lahko pomaga najti najboljše poti za blago in storitve, zmanjša čas in denar, porabljen za prevoz, ter pospeši in naredi natančnejše dostave. |
| Načrtovanje proizvodnje: | BFS se lahko uporablja za načrtovanje proizvodnje, tako da se viri, kot so delovna sila, surovine in oprema, uporabijo na najboljši možni način, da jih kar najbolje izkoristite. BFS lahko pomaga znižati proizvodne stroške, zmanjša količino odpadkov in izboljša učinkovitost. |
| Finančno načrtovanje: | Pri finančnem načrtovanju se lahko BFS uporablja za optimizacijo naložbenih portfeljev, zmanjšanje tveganja in povrnitev največ denarja. BFS lahko pomaga najti najboljši način za razdelitev sredstev, znižanje transakcijskih stroškov in več zaslužka. |
| Upravljanje dobavne verige: | BFS se lahko uporablja za izboljšanje pretoka blaga in storitev od dobaviteljev do strank kot del upravljanja dobavne verige. BFS lahko pomaga ugotoviti najboljšo količino zalog, ki jo imate pri roki, skrajša dobavne roke in izboljša storitve za stranke. |
Zaključek
Ko se ta pogled na osnovne izvedljive rešitve bliža koncu, je jasno, da so pomembno orodje za vsakega inženirja ali študenta inženirstva.
Od ugotavljanja najboljšega načina za izgradnjo zapletenega sistema do čim večjega izkoriščanja razpoložljivih virov, osnovne izvedljive rešitve zagotavljajo okvir za doseganje najboljših možnih rezultatov.
Toda več kot le uporabne, pokažejo, kako elegantna in lepa je lahko matematika.
Neverjetno je, da lahko zapletene probleme strnete na preprost nabor enačb in nato uporabite te enačbe za reševanje problemov v resničnem svetu.
To je dober opomnik, da je inženiring namenjen reševanju problemov in da lahko z uporabo moči matematike najdemo odgovore, za katere smo nekoč mislili, da so nemogoči.
Torej, ko se naučite več o inženirstvu, ne pozabite, kaj ste se naučili o preprostih rešitvah, ki delujejo, in jih uporabite, da naredite svet boljši in učinkovitejši.
Povezave in reference
knjige:
- Linearno programiranje: Osnove in razširitve
- Linearno programiranje: teorija in aplikacije
Delite na...
