Če ste inženir ali študent tehnike, morda veste, kaj pomeni optimizirati.
Da bi dosegli najboljši možni rezultat, je pomembno najti najboljši način za stvari.
Pri linearnem programiranju lahko uporabite osnovno rešitev, da poiščete najboljšo rešitev.
Toda kaj je osnovna rešitev in zakaj je za inženirje tako pomembno, da vedo zanje? V tem članku bom govoril o tem, kaj so osnovne rešitve, zakaj so pomembne v inženirstvu in kako jih je mogoče uporabiti za doseganje najboljših rezultatov v različnih situacijah.
Zato se pripnite in se pripravite, da se potopite v svet osnovnih rešitev, kjer bom razkril skrivnosti in vam pokazal, kako močna je lahko ta tehnika.
Osnovne rešitve v linearnem programiranju
Formalna opredelitev:
Rešitev modela linearnega programa, sestavljenega iz m enačb v n spremenljivkah, dobimo z reševanjem za m spremenljivk glede na preostale (nm) spremenljivk in nastavitvijo (nm) spremenljivk na nič.
Osnovna rešitev v linearnem programiranju je način za rešitev problema linearnega programiranja, ki izpolnjuje določene tehnične zahteve.
Zlasti vektor x je osnovna rešitev za polieder, če sta vektorja {ai : xi = 0} linearno neodvisna.
To pomeni, da so stolpci A, ki imajo spremenljivke xi, ki niso nič, linearno neodvisni.
Osnovna rešitev z nenegativnimi komponentami se imenuje osnovna izvedljiva rešitev (BFS) (BFS).
BFS izpolnjuje vsa pravila, ki definirajo polieder.
Vsak BFS je kotiček poliedra izvedljivih rešitev z geometrijskega vidika.
Če želite najti osnovno rešitev, morate nm spremenljivk, ki niso bazične, nastaviti na nič in rešiti m spremenljivk, ki so osnovne.
Možno je, da različne osnove vodijo do iste osnovne rešitve, kar pomeni, da lahko obstaja več kot en način za rešitev istega problema.
Metoda Simplex je iterativni proces, ki se premika od enega BFS do naslednjega BFS, dokler ne najde najboljšega BFS.
Po uporabi metode simpleksa za iskanje BFS lahko ugotovimo, ali je rešitev najboljša, tako da vidimo, ali katera koli druga BFS v bližini daje boljšo vrednost za ciljno funkcijo.
Če takega BFS ni, je trenutni BFS najboljši.
Model linearnega programiranja
Model linearnega programiranja vključuje tri glavne komponente: odločitvene spremenljivke, ciljno funkcijo in omejitve.
Ciljna funkcija in omejitve morajo biti linearne funkcije, odločitvene spremenljivke pa zvezne.
Ciljna funkcija se uporablja za povečanje ali zmanjšanje števila, ki predstavlja dobiček, stroške, število izdelanih izdelkov itd.
Omejitve so meje ali omejitve skupne količine določenega vira, ki je potreben za opravljanje nalog, ki bodo določile stopnjo uspeha v odločitvenih spremenljivkah.
Poleg tega nekateri linearni programi zahtevajo, da so vse odločitvene spremenljivke nenegativne.
V modelih linearnega programiranja lahko uporabite tudi cele in binarne spremenljivke.
Binarne spremenljivke imajo lahko le vrednost 0 ali 1, torej imajo lahko le vrednost 0 ali 1.
Simpleksna metoda
Eden najpogosteje uporabljenih načinov reševanja problemov linearnega programiranja je metoda Simplex.
Osnovne rešitve so pri simpleks metodi pomembne, ker ustrezajo kotnim točkam izvedljivega območja, pri simpleks metodi pa se premika od enega vogala do drugega, dokler ne najde optimalne rešitve.
Simpleksna metoda je hiter način za iskanje najboljšega odgovora na problem linearnega programiranja z uporabo lastnosti osnovnih rešitev.
Če želimo uporabiti metodo simpleksa za iskanje najboljšega BFS, moramo najti osnovo B za matriko omejitev A in rešiti sistem Ax = b z vsemi spremenljivkami, ki niso osnova, nastavljena na nič.
Dobljene vrednosti za osnovne spremenljivke tvorijo BFS.
Če obstaja optimalna rešitev, potem obstaja optimalen BFS.
Metoda Simplex se premakne z ene BFS na sosednjo BFS, dokler ne doseže optimalne BFS z uporabo vrtilnih postopkov.
Primerjava med osnovnimi rešitvami in izvedljivimi rešitvami
Razlika med osnovno in izvedljivo rešitvijo je v tem, da za osnovno rešitev ni treba izpolnjevati nobenih pogojev.
Zlasti mora imeti vektorje, ki so linearno neodvisni in imajo različne vrednosti za xi, x pa mora biti manjši od 0.
Po drugi strani pa je izvedljiva rešitev vsaka točka, ki se ujema z mejami problema.
Niso pa vse izvedljive rešitve osnovne izvedljive rešitve.
Osnovne izvedljive rešitve (BFS) so samo tiste, ki se ujemajo z vogali poliedra izvedljivih rešitev.
Nazaj k osnovam: Odklepanje moči osnovnih rešitev v inženirstvu
Še vedno težko razumeti? Naj malo spremenim pogled:
Ste siti uporabe zapletenih metod in algoritmov za reševanje težkih problemov? Ali želite, da bi obstajal enostavnejši in enostavnejši način za reševanje vaših težav z modelom linearnega programa?
No, ne skrbite, saj je odgovor tukaj: rešite m spremenljivk glede na preostale (nm) spremenljivk in nastavite (nm) spremenljivk na nič.
Kdo potrebuje algoritme, ki se slišijo modno, ko se lahko vrnete k osnovam? Zato pospravite svoje kalkulatorje in se začnimo učiti o preprostih rešitvah.
V redu, to je bila samo šala, ki je izgledala kot TV oglas.
Zdaj pa se vrnimo k razlagi.
Osnovna rešitev Linearno programiranje
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: | Osnovna rešitev se lahko uporablja pri problemih dodeljevanja virov, kjer je cilj razdeliti omejene vire med konkurenčne potrebe. Na primer, podjetje bo morda moralo svoj proračun razdeliti med različne oddelke ali projekte. Z uporabo osnovnih rešitev lahko ugotovijo, kako najbolje uporabiti svoje vire, da bi zaslužili največ denarja ali porabili čim manj. |
| Načrtovanje proizvodnje: | Pri načrtovanju proizvodnje lahko osnovno rešitev uporabimo za določitev najboljše mešanice izdelkov, ki jih je treba narediti, da bi zaslužili največ denarja. Podjetja lahko z osnovno rešitvijo najdejo najboljšo proizvodno mešanico, ki prinaša največ denarja in najmanj stroškov. |
| Razporejanje: | Z osnovno rešitvijo lahko ugotovite, kako načrtovati naloge ali opravila, tako da jih je mogoče opraviti na najučinkovitejši način. Na primer, podjetje bo morda moralo načrtovati delovni čas svojih zaposlenih, da zagotovi dovolj delavcev, ko je posel zaseden. Z uporabo osnovne rešitve lahko ugotovijo najboljši način za načrtovanje stvari, tako da je čim manj izpadov in da se opravi čim več dela. |
| Upravljanje dobavne verige: | Pri upravljanju dobavne verige je cilj zagotoviti, da se blago in storitve čim bolj gladko premikajo od dobavitelja do kupca. Na primer, podjetje bo morda moralo ugotoviti najboljše poti za prevoz blaga, tako da bodo stroški čim nižji in da bo blago dostavljeno pravočasno. Z uporabo osnovnih rešitev lahko najdejo najboljši načrt za upravljanje dobavne verige, ki ohranja nizke stroške in zadovoljne stranke. |
| Optimizacija portfelja: | Pri optimizaciji portfelja, kjer je cilj najti najboljšo kombinacijo naložb, da bi zaslužili največ denarja ob najmanjšem tveganju, je mogoče uporabiti osnovne rešitve. Na primer, investicijsko podjetje bo morda moralo ugotoviti najboljšo kombinacijo delnic, obveznic in drugih vrednostnih papirjev, da bi svojim strankam pomagalo pri doseganju naložbenih ciljev. Z uporabo preproste rešitve lahko najdejo najboljši način za mešanje svojih portfeljev, tako da dobijo najboljše donose ob najmanjšem tveganju. |
Zaključek
Skratka, ideja osnovne rešitve je zelo pomembna na področju inženiringa in jo je mogoče uporabiti na veliko različnih načinov.
Če vemo, kaj je osnovna rešitev in kaj počne v linearnem programiranju, lahko izboljšamo rešitve, zmanjšamo stroške in jih naredimo učinkovitejše.
Pomembno pa si je zapomniti, da osnovna rešitev ni rešitev, ki bi ustrezala vsem, čeprav je močno orodje.
Za najboljše rezultate je treba vsako težavo natančno preučiti in o njej razmisliti.
Kot inženirji moramo nenehno iskati, kako nam lahko osnovne rešitve in druge optimizacijske tehnike pomagajo napredovati in pripraviti nove zamisli.
Zato prepoznajmo moč preprostih rešitev in še naprej premikajmo meje možnega z uporabo novih tehnik in strategij.
Povezave in reference
knjige:
- Linearno programiranje Vaseka Chvatala
- Modeliranje in reševanje linearnega programiranja z R, Jose M. Sallan
Delite na...
