Ako ste inženjer ili student strojarstva, možda znate što znači optimizirati.
Da biste dobili najbolji mogući rezultat, važno je pronaći najbolji način za obavljanje stvari.
U linearnom programiranju možete koristiti osnovno rješenje da pronađete najbolje rješenje.
Ali što je osnovno rješenje i zašto je inženjerima toliko važno da znaju o njima? U ovom ću članku govoriti o tome što su osnovna rješenja, zašto su važna u inženjerstvu i kako se mogu koristiti za postizanje najboljih rezultata u različitim situacijama.
Zato se zakopčajte i pripremite za uronjenje u svijet osnovnih rješenja, gdje ću razotkriti misterije i pokazati vam koliko ova tehnika može biti moćna.
Osnovna rješenja u linearnom programiranju
Formalna definicija:
Rješenje modela linearnog programa koji se sastoji od m jednadžbi u n varijabli dobiva se rješavanjem za m varijabli u smislu preostalih (nm) varijabli i postavljanjem (nm) varijabli na nulu.
Osnovno rješenje u linearnom programiranju je način rješavanja problema linearnog programiranja koji zadovoljava određene tehničke zahtjeve.
Konkretno, vektor x je osnovno rješenje za poliedar ako su vektori {ai : xi = 0} linearno neovisni.
To znači da su stupci od A koji imaju varijable xi koje nisu nula linearno neovisni.
Osnovno rješenje s nenegativnim komponentama naziva se osnovno izvedivo rješenje (BFS) (BFS).
BFS ispunjava sva pravila koja definiraju poliedar.
Svaki BFS je kut poliedra izvedivih rješenja s geometrijske točke gledišta.
Da biste pronašli osnovno rješenje, morate postaviti nm varijabli koje nisu bazične na nulu i riješiti m varijabli koje su bazične.
Moguće je da različite baze dovedu do istog osnovnog rješenja, što znači da može postojati više od jednog načina za rješavanje istog problema.
Simplex metoda je iterativni proces koji prelazi s jednog BFS-a na sljedeći BFS dok se ne pronađe najbolji BFS.
Nakon što upotrijebimo simpleks metodu za pronalaženje BFS-a, možemo reći je li rješenje najbolje tako da vidimo da li neki drugi BFS u blizini daje bolju vrijednost za funkciju cilja.
Ako nema takvog BFS-a, onda je trenutni BFS najbolji.
Model linearnog programiranja
Model linearnog programiranja uključuje tri glavne komponente: varijable odluke, ciljnu funkciju i ograničenja.
I funkcija cilja i ograničenja moraju biti linearne funkcije, a varijable odluke moraju biti kontinuirane.
Funkcija cilja se koristi za povećanje ili smanjenje broja koji predstavlja dobit, trošak, broj proizvedenih proizvoda itd.
Ograničenja su granice ili restrikcije ukupne količine određenog resursa koji je potreban za obavljanje zadataka koji će odrediti razinu uspjeha u varijablama odlučivanja.
Osim toga, neki linearni programi zahtijevaju da sve varijable odluke budu nenegativne.
U modelima linearnog programiranja također možete koristiti cjelobrojne i binarne varijable.
Binarne varijable mogu imati samo vrijednost 0 ili 1, dakle mogu imati samo vrijednost 0 ili 1.
Simpleksna metoda
Jedan od najčešće korištenih načina rješavanja problema linearnog programiranja je Simpleks metoda.
Osnovna rješenja su važna u simpleks metodi jer odgovaraju kutnim točkama izvedive regije, a simpleks metoda se kreće od jednog kuta do drugog dok se ne nađe optimalno rješenje.
Simpleksna metoda je brz način da se pronađe najbolji odgovor na problem linearnog programiranja korištenjem svojstava osnovnih rješenja.
Da bismo koristili simpleks metodu za pronalaženje najboljeg BFS-a, moramo pronaći bazu B za matricu ograničenja A i riješiti sustav Ax = b sa svim varijablama osim baze postavljene na nulu.
Rezultirajuće vrijednosti za osnovne varijable čine BFS.
Ako postoji optimalno rješenje, onda postoji optimalni BFS.
Simplex metoda pomiče se s jednog BFS-a na susjedni BFS dok se ne postigne optimalni BFS korištenjem pivot postupaka.
Usporedba između osnovnih rješenja i izvedivih rješenja
Razlika između osnovnog rješenja i izvedivog rješenja je u tome što osnovno rješenje ne mora ispunjavati nikakve uvjete.
Konkretno, mora imati vektore koji su linearno neovisni i imaju različite vrijednosti za xi, a x mora biti manji od 0.
S druge strane, izvedivo rješenje je svaka točka koja se uklapa u granice problema.
Ali nisu sva izvediva rješenja osnovna izvediva rješenja.
Osnovna izvediva rješenja (BFS) su samo ona koja odgovaraju kutovima poliedra izvedivih rješenja.
Povratak na osnove: Otključavanje snage osnovnih rješenja u inženjerstvu
Još uvijek je teško razumjeti? Da malo promijenim gledište:
Muka vam je od korištenja kompliciranih metoda i algoritama za rješavanje teških problema? Želite li da postoji jednostavniji, izravniji način za rješavanje problema vašeg modela linearnog programa?
Pa, ne brinite, jer je odgovor ovdje: riješite m varijabli u smislu preostalih (nm) varijabli i postavite (nm) varijabli na nulu.
Kome trebaju algoritmi koji zvuče otmjeno kad se možete vratiti osnovama? Stoga odložite svoje kalkulatore i počnimo učiti o jednostavnim rješenjima.
U redu, to je bila samo šala napravljena da izgleda kao TV reklama.
Sada se vratimo na objašnjenje.
Osnovno rješenje linearnog programiranja
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: | Osnovno rješenje može se koristiti u problemima raspodjele resursa, gdje je cilj podijeliti ograničene resurse između konkurentskih potreba. Na primjer, tvrtka će možda morati podijeliti svoj proračun između različitih odjela ili projekata. Koristeći osnovna rješenja, mogu otkriti najbolji način da iskoriste svoje resurse kako bi zaradili najviše novca ili potrošili što je manje moguće. |
| Planiranje proizvodnje: | U planiranju proizvodnje, osnovno rješenje može se koristiti za određivanje najbolje kombinacije proizvoda za izradu kako bi se zaradilo najviše novca. Korištenjem osnovnog rješenja tvrtke mogu pronaći najbolju proizvodnu kombinaciju koja donosi najviše novca i košta najmanje. |
| Zakazivanje: | Osnovno rješenje može se koristiti za određivanje rasporeda zadataka ili poslova tako da se mogu izvršiti na najučinkovitiji način. Na primjer, tvrtka će možda morati planirati radno vrijeme svojih zaposlenika kako bi osigurala dovoljno radnika kada je posao zauzet. Korištenjem osnovnog rješenja mogu smisliti najbolji način za raspored stvari tako da ima što manje zastoja i da se što više posla obavi. |
| Upravljanje opskrbnim lancem: | U upravljanju opskrbnim lancem, cilj je osigurati da se roba i usluge kreću od dobavljača do kupca što je moguće glatko. Na primjer, tvrtka će možda trebati pronaći najbolje rute za prijevoz robe tako da troškovi budu minimalni, a roba isporučena na vrijeme. Korištenjem osnovnih rješenja mogu pronaći najbolji plan za upravljanje opskrbnim lancem koji održava niske troškove i čini kupce zadovoljnima. |
| Optimizacija portfelja: | U optimizaciji portfelja, gdje je cilj pronaći najbolju kombinaciju ulaganja kako bi se zaradilo najviše novca uz najmanji rizik, mogu se koristiti osnovna rješenja. Na primjer, investicijska tvrtka možda će morati pronaći najbolju kombinaciju dionica, obveznica i drugih vrijednosnih papira kako bi pomogla svojim klijentima da ostvare svoje investicijske ciljeve. Korištenjem jednostavnog rješenja mogu pronaći najbolji način za kombiniranje svojih portfelja kako bi ostvarili najbolje povrate uz najmanji rizik. |
Zaključak
Zaključno, ideja o osnovnom rješenju vrlo je važna u području inženjerstva i može se koristiti na mnogo različitih načina.
Znajući što je osnovno rješenje i što ono radi u linearnom programiranju, možemo poboljšati rješenja, smanjiti troškove i učiniti ih učinkovitijima.
No važno je upamtiti da osnovno rješenje nije jedno rješenje za sve, iako je moćan alat.
Da biste dobili najbolje rezultate, svaki problem treba pažljivo sagledati i razmisliti o njemu.
Kao inženjeri, moramo stalno istraživati kako nam osnovna rješenja i druge tehnike optimizacije mogu pomoći da napredujemo i dođemo do novih ideja.
Dakle, prepoznajmo snagu jednostavnih rješenja i nastavimo pomicati granice mogućeg korištenjem novih tehnika i strategija.
Linkovi i reference
knjige:
- Linearno programiranje Vaseka Chvatala
- Modeliranje i rješavanje linearnog programiranja s R-om, Jose M. Sallan
Dijeli…
