Znate šta znači optimizovati sistem da biste dobili najbolji mogući rezultat ako ste student mašinstva ili inženjer.
Optimizacija rješenja je ključ uspjeha u svemu, od izgradnje mostova do izrade softvera.
Ideja o osnovnom izvodljivom rješenju dolazi u ovom trenutku.
To je osnovna ideja u linearnom programiranju koja vam omogućava da shvatite koje je od skupa mogućih rješenja najbolje.
Ali zašto je to toliko važno? U ovom članku ću govoriti o osnovnim izvodljivim rješenjima i kako se ona mogu koristiti za rješavanje inženjerskih problema u stvarnom svijetu.
Govorit ću o tome kako ih pronaći, od čega su napravljeni i zašto su važni.
Dakle, bez obzira da li ste iskusni inženjer ili student koji tek počinje, pođite s nama dok zaronim u svijet osnovnih izvodljivih rješenja i pokažem vam kako koristiti snagu linearnog programiranja.
Razumijevanje osnovnog izvodljivog rješenja
Formalna definicija:
Osnovno rješenje za linearni programski model u kojem su sve varijable nenegativne.
Osnovno izvodljivo rješenje (BFS) je ključna ideja u linearnom programiranju koja pomaže u pronalaženju najboljih rješenja.
BFS je rješenje sa najmanjim mogućim brojem varijabli koje nisu nula.
To je ugao poliedra izvodljivih rješenja.
Drugim riječima, BFS je osnovno rješenje koje zadovoljava nenegativna ograničenja i nalazi se u izvodljivoj regiji ili problemskom području.
Pronalaženje optimalnog osnovnog izvodljivog rješenja
Da bismo pronašli najbolji BFS, moramo uraditi sljedeće:
- Napišite program u standardnom obliku za linearni niz.
- Pretvorite sistem nejednakosti u proširenu matricu.
- Otkrijte koje su varijable osnovne, a koje nisu.
- Otkrijte koje su osnovne varijable u smislu ostalih varijabli.
- Stavite ove izraze u funkciju cilja da dobijete funkciju samo varijabli koje nisu osnovne.
- Pronađite ne-osnovnu varijablu koja se može povećati bez kršenja bilo kakvih ograničenja i koja će učiniti funkciju cilja boljom.
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 područja gdje su rješenja moguća.
Dakle, ako LP ima optimalno rješenje, on ima optimalno rješenje u ekstremnoj tački izvodljivog skupa.
Također, uvijek postoji optimalan 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.
Pomiče se sa jednog BFS-a na "susedni" BFS korišćenjem pivot procedure.
U pivot proceduri, neosnovna varijabla se bira da postane osnovna varijabla, a zatim se trenutni BFS koristi za rješavanje novih osnovnih varijabli.
Kada se nijedna ne-bazna varijabla ne može promijeniti da bi funkcija cilja bila bolja, algoritam je gotov.
Zašto su osnovna izvodljiva rješenja ključna za rješavanje složenih inženjerskih problema
Još uvijek je teško razumjeti? Dozvolite mi da malo promijenim tačku gledišta:
Kome su uopće potrebni jednostavni, izvodljivi odgovori? Samo saberite sve i nadajte se najboljem.
Uostalom, kome je potrebna optimizacija kada je haos mnogo zabavniji? Dobrodošli u svijet nenegativnih varijabli, gdje je sve samo sugestija, a neuspjeh je gotovo siguran.
Ili je to?
Hajde da istražimo zašto je naizgled osnovni koncept osnovnih izvodljivih rješenja sve samo ne osnovni i zašto oni mogu biti samo ključ za rješavanje čak i najsloženijih inženjerskih problema.
U redu, to je bila samo šala napravljena da izgleda kao TV reklama.
Vratimo se sada na objašnjenje.
Pronalaženje osnovnog izvodljivog rješenja
Osnovno izvedivo rješenje (BFS) je rješenje za problem linearne optimizacije koje zadovoljava sva ograničenja i ima najmanji broj varijabli koje nisu nula.
Svaki BFS je ugao poliedra izvodljivih rješenja sa geometrijske tačke gledišta.
Ako postoji najbolje rješenje, mora postojati i najbolji prvi korak.
U ovom članku ćemo govoriti o tome kako pronaći početno osnovno izvedivo rješenje, kako pronaći sva osnovna izvodljiva rješenja i kako pronaći osnovno izvedivo rješenje bez nepostojanih varijabli.
Pronalaženje početnog osnovnog izvodljivog rješenja
Možemo koristiti različite metode, ovisno o tome kako je problem postavljen, da pronađemo početno osnovno rješenje koje radi za problem linearne optimizacije.
Jedan od načina je da se ograničenjima nejednakosti dodaju slabe varijable i sve ostale varijable postavite na nulu.
Slack varijable postaju osnovne varijable, a ostale su ne-bazične varijable.
Dvofazna Simpleks metoda je još 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 izvodljivo.
Jednom kada se nađe početno osnovno izvedivo rješenje, Simpleks metoda se može koristiti za prelazak s jednog osnovnog izvodljivog rješenja na sljedeće, a zatim na najbolje rješenje.
Pronalaženje svih osnovnih izvodljivih rješenja
Može postojati više od jednog osnovnog rješenja koje radi za linearni program.
Možemo promijeniti sistem dodavanjem zapuštenih varijabli, a zatim koristiti novi sistem da pronađemo sva osnovna izvodljiva rješenja za linearni program.
Zatim se ova osnovna izvodljiva rješenja koriste za pronalaženje osnovnih izvodljivih rješenja za originalni problem.
Pronalaženje osnovnog izvodljivog rješenja bez slack varijabli
Moramo da koristimo slabe varijable da bismo se oslobodili manjih ograničenja kako bismo mogli pronaći osnovno reš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 labavu varijablu x4 = 14 - 2x1 - x2 - x3. U smislu ove nove varijable, prvo ograničenje je jednostavno ekvivalentno x4 ≥ 0, što je pozitivno ograničenje za x4.
Kada dodamo ove slabe varijable, dobijamo linearni program koji je isti kao i originalni, osim što su sva ograničenja ili jednadžbe ili ograničenja koja govore da je nešto pozitivno.
Skup osnovnih varijabli, koje imaju vrijednosti različite od nule u osnovnom rješenju, naziva se baza.
Varijable koje imaju vrijednost nula u osnovnom rješenju nisu osnovne varijable.
Da bismo pronašli najbolje rješenje, moramo pronaći vektor x koji ispunjava sva pravila i koji ima najveću ili najmanju vrijednost za cilj.
Ali pronalaženje najboljeg rješenja zahtijeva više koraka nego samo pronalaženje rješenja koje funkcionira i nema labavih varijabli.
Nije uvijek moguće pronaći osnovno rješenje bez labavih varijabli, posebno za probleme sa ograničenjima koja su manja.
Da biste pronašli osnovno izvedivo rješenje, trebate koristiti simpleks metodu ili drugi algoritam linearnog programiranja kako biste potražili 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 izvodljivog rješenja
Osnovno izvodljivo rješenje ima najviše m varijabli koje nisu nula i najmanje nm varijabli koje su nula, gdje je n broj varijabli odlučivanja, a m broj ograničenja.
BFS je ugao poliedra mogućih rješenja, a svaki BFS ima n aktivnih ograničenja koja su linearno nezavisna.
Ako postoji najbolje rješenje, mora postojati i najbolji prvi korak.
Najvažnija stvar kod osnovnih izvodljivih rješenja je da su ona krajevi skupa konveksnih rješenja za problem linearnog programiranja.
Da bi se pronašao najbolji odgovor, simpleks algoritam prolazi kroz niz BFS-ova.
Simpleks algoritam pretražuje sva osnovna moguća rješenja na organiziran način kako bi pronašao najbolje.
Značaj osnovnog izvodljivog rješenja
Pronalaženje osnovnog mogućeg rješenja je važno jer pomaže u pronalaženju najboljeg odgovora na probleme linearnog programiranja.
Također daje složenim algoritmima mjesto za početak i može se koristiti da se utvrdi da li je linearni program moguć ili ne.
Da biste pronašli sva osnovna izvodljiva rješenja za linearni program, možete promijeniti sistem dodavanjem nepovezanih varijabli, a zatim koristiti promijenjeni sistem da pronađete sva osnovna izvodljiva rješenja.
Zatim se ova osnovna izvodljiva rješenja koriste za pronalaženje osnovnih izvodljivih rješenja za originalni problem.
Video: Osnovna izvodljiva rješenja
Savjet: Uključite dugme za titl ako vam je potrebno. Odaberite "automatski prijevod" u gumbu za podešavanja, ako niste upoznati sa govornim jezikom. Možda ćete morati prvo kliknuti na jezik videozapisa prije nego što vaš omiljeni jezik postane dostupan za prijevod.
Slučajevi upotrebe
| Koristi se u: | Opis: |
|---|---|
| Raspodjela resursa: | BFS se može koristiti za podjelu ograničenih resursa na nekoliko projekata tako da se najviše može učiniti s najmanje. Ova metoda se može koristiti u mnogim različitim poljima, kao što su transport, poljoprivreda i finansije. |
| Optimizacija mreže: | BFS se može koristiti za bolje funkcioniranje komunikacijskih, transportnih i logističkih mreža. BFS može pomoći u pronalaženju najboljih ruta za robu i usluge, smanjiti vrijeme i novac potrošen na transport, te ubrzati i izvršiti preciznije isporuke. |
| Planiranje proizvodnje: | BFS se može koristiti za planiranje proizvodnje tako da se resursi poput radne snage, sirovina i opreme koriste na najbolji mogući način kako bi se iz njih izvukla maksimum. BFS može pomoći u smanjenju troškova proizvodnje, smanjenju otpada i poboljšanju efikasnosti. |
| finansijsko planiranje: | U finansijskom planiranju, BFS se može koristiti za optimizaciju investicionih portfelja, smanjenje rizika i vraćanje najviše novca. BFS može pomoći u pronalaženju najboljeg načina za podjelu imovine, snižavanje troškova transakcije i zaradu više novca. |
| Upravljanje lancem nabavke: | BFS se može koristiti za poboljšanje protoka roba i usluga od dobavljača do kupaca kao dio upravljanja lancem nabavke. BFS može pomoći u pronalaženju najbolje količine zaliha koju treba držati pri ruci, skratiti vrijeme isporuke i poboljšati korisničku uslugu. |
Zaključak
Kako se ovaj pogled na osnovna izvodljiva rješenja bliži kraju, jasno je da su ona važan alat za svakog inženjera ili studenta inženjerstva.
Od pronalaženja najboljeg načina za izgradnju komplikovanog sistema do maksimalnog iskorištavanja raspoloživih resursa, osnovna izvodljiva rješenja pružaju okvir za postizanje najboljeg mogućeg rezultata.
Ali više od toga da budu samo korisni, oni pokazuju koliko matematika može biti elegantna i lijepa.
Nevjerovatno je da možete svesti komplikovane probleme na jednostavan skup jednačina, a zatim koristiti te jednačine za rješavanje problema u stvarnom svijetu.
Dobar je podsjetnik da je inženjering sve u rješavanju problema i da korištenjem moći matematike možemo pronaći odgovore za koje se nekada smatralo da su nemogući.
Dakle, dok učite više o inženjeringu, imajte na umu ono što ste naučili o jednostavnim rješenjima koja funkcioniraju i koristite ih da svijet učinite boljim i efikasnijim mjestom.
Linkovi i reference
knjige:
- Linearno programiranje: temelji i proširenja
- Linearno programiranje: teorija i primjene
Podijelite na…
