Ako ste inženjer ili student tehnike, možda znate šta znači optimizirati.
Da biste postigli 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 biste pronašli najbolje rješenje.
Ali šta je osnovno rešenje i zašto je toliko važno da inženjeri znaju za njih? U ovom članku ću govoriti o tome koja su osnovna rješenja, zašto su važna u inženjeringu i kako se mogu koristiti za postizanje najboljih rezultata u različitim situacijama.
Zato se vežite i pripremite se da zaronite u svijet osnovnih rješenja, gdje ću razbiti misterije i pokazati vam koliko moćna ova tehnika može biti.
Osnovna rješenja u linearnom programiranju
Formalna definicija:
Rješenje linearnog programskog modela koji se sastoji od m jednačina u n varijabli dobiva se rješavanjem za m varijabli u smislu preostalih (nm) varijabli i postavljanjem (nm) varijabli jednakim nuli.
Osnovno rješenje u linearnom programiranju je način rješavanja problema linearnog programiranja koji ispunjava određene tehničke zahtjeve.
Konkretno, vektor x je osnovno rješenje za poliedar ako su vektori {ai : xi = 0} linearno nezavisni.
To znači da su kolone A koje imaju varijable xi koje nisu nula linearno nezavisne.
Osnovno rješenje s nenegativnim komponentama naziva se osnovno izvedivo rješenje (BFS) (BFS).
BFS ispunjava sva pravila koja definiraju poliedar.
Svaki BFS je ugao poliedra izvodljivih rješenja sa geometrijske tačke gledišta.
Da biste pronašli osnovno rješenje, morate postaviti nm varijabli koje nisu osnovne na nulu i riješiti m varijabli koje su osnovne.
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 rješavanja istog problema.
Simpleks metoda je iterativni proces koji se kreće od jednog BFS do sledećeg BFS dok ne pronađe najbolji BFS.
Nakon upotrebe simpleks metode za pronalaženje BFS-a, možemo reći da li je rješenje najbolje tako što ćemo vidjeti da li bilo koji drugi BFS u blizini daje bolju vrijednost za ciljnu funkciju.
Ako takav BFS ne postoji, onda je trenutni BFS najbolji.
Model linearnog programiranja
Model linearnog programiranja uključuje tri glavne komponente: varijable odluke, funkciju cilja i ograničenja.
I ciljna funkcija 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 profit, trošak, broj proizvedenih proizvoda itd.
Ograničenja su ograničenja ili ograničenja ukupnog iznosa određenog resursa koji je potreban za obavljanje zadataka koji će odrediti nivo uspjeha u varijablama odlučivanja.
Osim toga, neki linearni programi zahtijevaju da sve varijable odluke budu nenegativne.
U modelima linearnog programiranja možete koristiti i cjelobrojne i binarne varijable.
Binarne varijable mogu imati samo vrijednost 0 ili 1, tako da mogu imati samo vrijednost 0 ili 1.
Simpleks 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 tačkama izvodljivog područja, a simpleks metoda se kreće od jednog ugla do drugog dok se ne pronađe optimalno rješenje.
Simpleks metoda je brz način da se pronađe najbolji odgovor na problem linearnog programiranja koristeći svojstva 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 sistem Ax = b sa svim varijablama osim baze postavljene na nulu.
Rezultirajuće vrijednosti za osnovne varijable formiraju BFS.
Ako postoji optimalno rješenje, onda postoji i optimalni BFS.
Simpleks metoda se kreće sa jednog BFS na susedni BFS dok ne dostigne optimalni BFS korišćenjem stožernih procedura.
Poređenje između osnovnih i izvodljivih rješenja
Razlika između osnovnog rješenja i izvodljivog rješenja je u tome što osnovno rješenje ne mora ispunjavati nikakve uslove.
Konkretno, mora imati vektore koji su linearno nezavisni i imaju različite od nule vrijednosti za xi, a x mora biti manji od 0.
S druge strane, izvodljivo rješenje je svaka tačka koja se uklapa u granice problema.
Ali nisu sva izvodljiva rješenja osnovna izvodljiva rješenja.
Osnovna izvodljiva rješenja (BFS) su samo ona koja odgovaraju uglovima poliedra izvodljivih rješenja.
Povratak na osnove: otključavanje moći osnovnih rješenja u inženjeringu
Još uvijek je teško razumjeti? Dozvolite mi da malo promijenim tačku gledišta:
Da li vam je muka od upotrebe komplikovanih metoda i algoritama za rešavanje teških problema? Želite li da postoji jednostavniji, jednostavniji način rješavanja problema vašeg linearnog programskog modela?
Pa, ne brinite, jer je odgovor ovdje: riješite za m varijabli u smislu preostalih (nm) varijabli i postavite (nm) varijable na nulu.
Kome trebaju algoritmi koji zvuče otmjeno kada se možete vratiti osnovama? Zato 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.
Vratimo se sada na objašnjenje.
Osnovno rješenje Linearno programiranje
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: | Osnovno rješenje se može koristiti u problemima alokacije resursa, gdje je cilj podjela ograničenih resursa među konkurentnim potrebama. Na primjer, kompanija će možda morati podijeliti svoj budžet između različitih odjela ili projekata. Koristeći osnovna rješenja, oni mogu pronaći 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 se može koristiti za pronalaženje najbolje kombinacije proizvoda za proizvodnju kako bi se zaradilo najviše novca. Kompanije mogu pronaći najbolji proizvodni miks koji donosi najviše novca i najmanje košta korištenjem osnovnog rješenja. |
| Zakazivanje: | Osnovno rješenje se može koristiti da se otkrije kako rasporediti zadatke ili poslove tako da se mogu obaviti na najefikasniji način. Na primjer, kompanija će možda morati planirati radno vrijeme svojih zaposlenika kako bi osigurala da imaju dovoljno radnika kada je posao zauzet. Koristeći osnovno rješenje, oni mogu smisliti najbolji način da rasporede stvari tako da bude što manje zastoja i da se obavi što više posla. |
| Upravljanje lancem nabavke: | U upravljanju lancem nabavke, cilj je osigurati da se roba i usluge kreću što je lakše moguće od dobavljača do kupca. Na primjer, preduzeće će možda morati da pronađe najbolje rute za transport robe tako da troškovi budu svedeni na minimum i da se roba isporuči na vreme. Koristeći osnovna rješenja, oni mogu pronaći najbolji plan za upravljanje lancem opskrbe koji održava niske troškove i čini kupce zadovoljnim. |
| Optimizacija portfelja: | U optimizaciji portfelja, gdje je cilj pronaći najbolju kombinaciju investicija kako biste zaradili najviše novca uz najmanji rizik, mogu se koristiti osnovna rješenja. Na primjer, investiciona firma će možda morati da pronađe najbolju kombinaciju dionica, obveznica i drugih vrijednosnih papira kako bi pomogla svojim klijentima da postignu svoje investicijske ciljeve. Koristeći jednostavno rješenje, oni mogu pronaći najbolji način da pomiješaju svoje portfelje tako da ostvare najbolje povrate uz najmanji rizik. |
Zaključak
Zaključno, ideja o osnovnom rješenju je vrlo važna u području inženjeringa i može se koristiti na mnogo različitih načina.
Znajući šta je osnovno rješenje i šta ono radi u linearnom programiranju, možemo poboljšati rješenja, smanjiti troškove i učiniti ih efikasnijim.
Ali važno je zapamtiti da osnovno rješenje nije rješenje za sve, iako je moćan alat.
Da biste dobili najbolje rezultate, svaki problem treba pažljivo razmotriti i razmisliti o njemu.
Kao inženjeri, moramo nastaviti istraživati kako nam osnovna rješenja i druge tehnike optimizacije mogu pomoći da napredujemo i dođemo do novih ideja.
Dakle, hajde da prepoznamo moć jednostavnih rješenja i nastavimo pomicati granice mogućeg koristeći nove tehnike i strategije.
Linkovi i reference
knjige:
- Linearno programiranje Vaseka Chvatala
- Modeliranje i rješavanje linearnog programiranja s R, Jose M. Sallan
Podijelite na…
