Znate što znači optimizirati sustav da biste dobili najbolji mogući rezultat ako ste student strojarstva ili inženjer.
Optimiziranje rješenja ključ je uspjeha u svemu, od izgradnje mostova do izrade softvera.
Ideja o osnovnom izvedivom rješenju dolazi u ovom trenutku.
To je osnovna ideja u linearnom programiranju koja vam omogućuje da shvatite koje je od niza mogućih rješenja najbolje.
Ali zašto je to toliko važno? U ovom ću članku govoriti o osnovnim izvedivim rješenjima i kako se mogu koristiti za rješavanje inženjerskih problema u stvarnom svijetu.
Govorit ću o tome kako ih pronaći, od čega su napravljene i zašto su važne.
Dakle, bez obzira jeste li iskusni inženjer ili student koji tek počinje, pođite s nama dok ja uronim u svijet osnovnih izvedivih rješenja i pokažem vam kako koristiti snagu linearnog programiranja.
Razumijevanje osnovnog izvedivog rješenja
Formalna definicija:
Osnovno rješenje modela linearnog programa u kojem su sve varijable nenegativne.
Osnovno izvedivo rješenje (BFS) ključna je ideja u linearnom programiranju koja pomaže u pronalaženju najboljih rješenja.
BFS je rješenje s najmanjim mogućim brojem varijabli različitih od nule.
To je kut poliedra izvedivih rješenja.
Drugim riječima, BFS je osnovno rješenje koje zadovoljava nenegativna ograničenja i nalazi se u izvedivoj regiji ili problematičnom području.
Pronalaženje optimalnog osnovnog izvedivog rješenja
Da bismo pronašli najbolji BFS, moramo učiniti sljedeće:
- Napišite program u standardnom obliku za linearni niz.
- Pretvorite sustav nejednakosti u proširenu matricu.
- Utvrdite koje su varijable osnovne, a koje nisu.
- Odredite koje su osnovne varijable u odnosu na druge varijable.
- Stavite ove izraze u funkciju cilja kako biste dobili funkciju samo onih varijabli koje nisu osnovne.
- Pronađite neosnovnu varijablu koja se može povećati bez kršenja ograničenja i koja će poboljšati funkciju cilja.
Ova varijabla je sada osnovna varijabla, a jedna od ostalih osnovnih varijabli više nije osnovna varijabla.
Ako postoji optimalno rješenje, ono mora biti na jednom od krajeva, ili vrhova, regije u kojoj su rješenja moguća.
Dakle, ako LP ima optimalno rješenje, ono ima optimalno rješenje u ekstremnoj točki izvedivog skupa.
Također, uvijek postoji optimalni BFS ako postoji optimalno rješenje.
Korištenje Simplex metode za pronalaženje optimalnog BFS-a
Simpleks metoda je algoritam za rješavanje problema u linearnom programiranju.
Premješta se s jednog BFS-a na "susjedni" BFS korištenjem pivot procedure.
U pivot proceduri, nebazična varijabla se bira da postane osnovna varijabla, a zatim se trenutni BFS koristi za rješavanje novih osnovnih varijabli.
Kad se nijedna neosnovna varijabla ne može promijeniti kako bi funkcija cilja bila bolja, algoritam je gotov.
Zašto su osnovna izvediva rješenja ključna za rješavanje složenih inženjerskih problema
Još uvijek je teško razumjeti? Da malo promijenim gledište:
Tko uopće treba jednostavne, djelotvorne odgovore? Samo stavite sve zajedno i nadajte se najboljem.
Uostalom, kome treba optimizacija kada je kaos mnogo zabavniji? Dobrodošli u svijet nenegativnih varijabli, gdje je sve samo sugestija i gdje je neuspjeh gotovo siguran.
Ili je?
Istražimo zašto je naizgled osnovni koncept osnovnih izvedivih rješenja sve samo ne bazičan i zašto bi oni mogli biti ključ za rješavanje čak i najsloženijih inženjerskih problema.
U redu, to je bila samo šala napravljena da izgleda kao TV reklama.
Sada se vratimo na objašnjenje.
Pronalaženje osnovnog izvedivog rješenja
Osnovno izvedivo rješenje (BFS) rješenje je problema linearne optimizacije koje zadovoljava sva ograničenja i ima najmanji broj varijabli različitih od nule.
Svaki BFS je kut poliedra izvedivih rješenja s geometrijske točke gledišta.
Ako postoji najbolje rješenje, mora postojati i najbolji prvi korak.
U ovom ćemo članku govoriti o tome kako pronaći početno osnovno izvedivo rješenje, kako pronaći sva osnovna izvediva rješenja i kako pronaći osnovno izvedivo rješenje bez zaostalih varijabli.
Pronalaženje početnog osnovnog izvedivog rješenja
Možemo koristiti različite metode, ovisno o tome kako je problem postavljen, kako bismo pronašli početno osnovno rješenje koje funkcionira za problem linearne optimizacije.
Jedan od načina je dodavanje slabih varijabli ograničenjima nejednakosti i postavljanje svih ostalih varijabli na nulu.
Slack varijable postaju osnovne varijable, a ostale su nebazične varijable.
Dvofazna Simplex metoda još je jedan način rješavanja problema.
Ova metoda uključuje rješavanje dodatnog problema linearnog programiranja kako bi se pronašlo početno osnovno rješenje koje je izvedivo.
Nakon što se pronađe početno osnovno izvedivo rješenje, Simplex metoda se može koristiti za prijelaz s jednog osnovnog izvedivog rješenja na sljedeće, a zatim na najbolje rješenje.
Pronalaženje svih osnovnih izvedivih rješenja
Može postojati više od jednog osnovnog rješenja koje funkcionira za linearni program.
Sustav možemo promijeniti dodavanjem slack varijabli, a zatim pomoću novog sustava pronaći sva osnovna izvediva rješenja za linearni program.
Zatim se ta osnovna izvediva rješenja koriste za pronalaženje osnovnih izvedivih rješenja za izvorni problem.
Pronalaženje osnovnog izvedivog rješenja bez slabih varijabli
Moramo upotrijebiti slabe varijable kako bismo se riješili manje od ograničenja kako bismo mogli pronaći osnovno rješenje koje radi bez slabih varijabli.
Slack varijabla je samo razlika između desne strane ograničenja i lijeve strane.
Na primjer, za prvo ograničenje definiramo slack varijablu x4 = 14 - 2x1 - x2 - x3. U smislu ove nove varijable, prvo ograničenje jednostavno je ekvivalentno x4 ≥ 0, što je ograničenje pozitivnosti za x4.
Kada dodamo ove slabe varijable, dobivamo linearni program koji je isti kao izvorni, osim što su sva ograničenja ili jednadžbe ili ograničenja koja govore da je nešto pozitivno.
Skup osnovnih varijabli, koje u osnovnom rješenju imaju vrijednosti različite od nule, naziva se baza.
Varijable koje u osnovnom rješenju imaju vrijednost nula nisu bazične varijable.
Da bismo pronašli najbolje rješenje, moramo pronaći vektor x koji zadovoljava sva pravila i ima najveću ili najmanju vrijednost za cilj.
Ali pronalaženje najboljeg rješenja zahtijeva više koraka od samog pronalaženja rješenja koje funkcionira i nema zaostale varijable.
Nije uvijek moguće pronaći osnovno rješenje bez slabih varijabli, posebno za probleme s ograničenjima manjim od toga.
Da biste pronašli osnovno izvedivo rješenje, trebate upotrijebiti simpleks metodu ili neki drugi algoritam linearnog programiranja kako biste pronašli rješenje koje zadovoljava sva ograničenja i ima najmanje varijabli različitih od nule.
Svojstva i značaj osnovnog izvodljivog rješenja
Svojstva osnovnog izvedivog rješenja
Osnovno izvedivo rješenje ima najviše m varijabli koje nisu nula i najmanje nm varijabli koje su nula, gdje je n broj varijabli odluke, a m broj ograničenja.
BFS je kut poliedra mogućih rješenja, a svaki BFS ima n aktivnih ograničenja koja su linearno neovisna.
Ako postoji najbolje rješenje, mora postojati i najbolji prvi korak.
Najvažnija stvar kod osnovnih izvedivih rješenja je da su krajevi skupa konveksnih rješenja za problem linearnog programiranja.
Kako bi pronašao najbolji odgovor, simpleks algoritam prolazi kroz niz BFS-ova.
Simplex algoritam pretražuje sva osnovna moguća rješenja na organiziran način kako bi pronašao najbolje.
Značaj osnovnog izvedivog rješenja
Pronalaženje osnovnog rješenja koje je moguće važno je jer pomaže pronaći najbolji odgovor na probleme linearnog programiranja.
Također daje početak složenim algoritmima i može se koristiti za određivanje je li linearni program moguć ili ne.
Da biste pronašli sva osnovna izvediva rješenja za linearni program, možete promijeniti sustav dodavanjem slack varijabli i zatim koristiti promijenjeni sustav za pronalaženje svih osnovnih izvedivih rješenja.
Zatim se ta osnovna izvediva rješenja koriste za pronalaženje osnovnih izvedivih rješenja za izvorni problem.
Video: Osnovna izvediva rješenja
Savjet: Uključite tipku titlova ako vam je potrebna. Odaberite "automatski prijevod" u gumbu postavki, ako niste upoznati s govornim jezikom. Možda ćete prvo morati kliknuti na jezik videozapisa prije nego što vaš omiljeni jezik postane dostupan za prijevod.
Slučajevi upotrebe
| Korišteno u: | Opis: |
|---|---|
| Raspodjela resursa: | BFS se može koristiti za podjelu ograničenih resursa između nekoliko projekata tako da se najviše može učiniti s najmanje. Ova se metoda može koristiti u mnogim različitim područjima, poput prijevoza, poljoprivrede i financija. |
| Optimizacija mreže: | BFS se može koristiti za bolji rad komunikacijskih, transportnih i logističkih mreža. BFS može pomoći u pronalaženju najboljih ruta za robu i usluge, skratiti vrijeme i novac potrošen na prijevoz te ubrzati i napraviti preciznije isporuke. |
| Planiranje proizvodnje: | BFS se može koristiti za planiranje proizvodnje tako da se resursi poput rada, sirovina i opreme koriste na najbolji mogući način kako bi se iz njih izvuklo najviše. BFS može pomoći u smanjenju troškova proizvodnje, smanjenju otpada i poboljšanju učinkovitosti. |
| Financijsko planiranje: | U financijskom planiranju, BFS se može koristiti za optimizaciju investicijskih portfelja, smanjenje rizika i vraćanje najviše novca. BFS može pomoći u pronalaženju najboljeg načina za podjelu imovine, smanjenje transakcijskih troškova i zarađivanje više novca. |
| Upravljanje opskrbnim lancem: | BFS se može koristiti za poboljšanje protoka robe i usluga od dobavljača do kupaca kao dio upravljanja opskrbnim lancem. BFS može pomoći u pronalaženju najbolje količine zaliha za držanje pri ruci, skratiti vrijeme isporuke i poboljšati korisničku uslugu. |
Zaključak
Kako se ovaj pogled na osnovna izvediva rješenja približava kraju, jasno je da su oni važan alat za svakog inženjera ili studenta inženjerstva.
Od pronalaženja najboljeg načina za izgradnju kompliciranog sustava do maksimalnog iskorištavanja dostupnih resursa, osnovna izvediva rješenja pružaju okvir za postizanje najboljeg mogućeg rezultata.
Ali više od toga da su samo korisni, oni pokazuju koliko matematika može biti elegantna i lijepa.
Nevjerojatno je da komplicirane probleme možete svesti na jednostavan skup jednadžbi i zatim koristiti te jednadžbe za rješavanje problema u stvarnom svijetu.
To je dobar podsjetnik da se inženjerstvo bavi rješavanjem problema i da korištenjem moći matematike možemo pronaći odgovore za koje se nekada mislilo da su nemogući.
Dakle, dok budete učili više o inženjerstvu, imajte na umu ono što ste naučili o jednostavnim rješenjima koja funkcioniraju i koristite ih kako biste svijet učinili boljim, učinkovitijim mjestom.
Linkovi i reference
knjige:
- Linearno programiranje: temelji i proširenja
- Linearno programiranje: teorija i primjena
Dijeli…
