Problemi optimizacije: koncept, metode rješenja i klasifikacija

Optimizacija pomaže u pronalaženju najboljeg rezultata koji donosi profit, smanjuje troškove ili postavlja parametar koji uzrokuje neuspjehe u poslovnom procesu.

Ovaj proces se takođe naziva matematičko programiranje. Rješava problem utvrđivanja raspodjele ograničenih resursa potrebnih za postizanje cilja koji je postavio šef zadatka optimizacije. Od svih mogućih opcija, poželjno je pronaći onu koja maksimizira (ili smanjuje) kontrolni parametar, na primer, profit ili trošak. Modeli optimizacije se nazivaju i propisani ili normativni, jer nastoje pronaći moguću strategiju za posao.

Istorija razvoja

Linearno programiranje (LP) radi sa klasom problema optimizacije gdje su sva ograničenja linearna.

Predstavlja kratku istoriju razvoja LP:

• 1762. Lagrange je riješio jednostavne probleme optimizacije sa ograničenjima jednakosti.
• Godine 1820, Gauss je riješio linearni sistem jednačina koristeći izuzetak.
• 1866. godine Wilhelm Jordan usavršio je metodu pronalaženja grešaka najmanje kvadrata kao kriterij usklađenosti. Sada se zove korišćenje Gauss metode-Jordan.
• 1945. godine pojavio se digitalni računar.
• 1947. godine Danzig je izumio simpleks metode.
• 1968. Fiacco i McCormick uveli su metodu " unutrašnje tačke.
• . Karmarkar je 1984. godine primijenio unutrašnju metodu za rješavanje linearnih programa, dodajući svoju inovativnu analizu.

LP se pokazao kao izuzetno moćan alat i za modeliranje stvarnih problema i kao široko korištena matematička teorija. Međutim, mnogi zanimljivi problemi optimizacije su nelinearni.

Šta učiniti u ovom slučaju? Proučavanje takvih problema uključuje raznoliku mješavinu linearne algebre, višedimenzionalnog računa, numeričke analize i računskih metoda. Naučnici se bave razvojem računskih algoritama, uključujući metode unutrašnjih tačaka za linearno programiranje, geometriju, analizu konveksnih skupova i funkcija, kao i proučavanjem posebno strukturiranih problema poput kvadratnog programiranja.

Nelinearna optimizacija pruža temeljno razumijevanje matematičke analize i široko se koristi u različitim oblastima kao što su inženjering, regresijska analiza, upravljanje zalihama, Geofizička istraživanja i ekonomija.

Klasifikacija problema optimizacije

Važan korak u procesu optimizacije je klasifikacija modela, jer su njihovi algoritmi rješenja prilagođeni određenom tipu.

1. Zadaci sa diskretnom i kontinuiranom optimizacijom. Neki modeli imaju smisla samo ako varijable uzimaju vrijednosti iz diskretnog skupa podskupa cijelih brojeva. Drugi sadrže podatke koji mogu imati bilo koju stvarnu vrijednost. Obično su lakši za rješavanje. Poboljšanja algoritama u kombinaciji sa napretkom kompjuterske tehnologije dramatično su povećala veličinu i složenost zadatka optimizacije linearno programiranje.

2. Neograničena i ograničena optimizacija. Druga važna razlika su zadaci u kojima nema ograničenja za varijable. Može se široko kretati od jednostavnih procjena do sistema jednakosti i nejednakosti koji modeliraju složene odnose između podataka. Takvi problemi optimizacije mogu se dalje klasifikovati po prirodi funkcija (linearne i nelinearne, konveksne i glatke, diferencijabilne i nediferencibilne).

3. Problemi sa izvodljivošću. Njihov cilj je pronaći vrijednosti varijabli koje zadovoljavaju ograničenja modela bez ikakvog specifičnog cilja optimizacije.

4. Komplementarni zadaci. Rasprostranjeni su u tehnologiji i ekonomiji. Cilj je pronaći rješenje koje zadovoljava uslove komplementarnosti. U praksi se zadaci s više ciljeva često preformuliraju u jedan cilj.

5. Deterministički vs. stohastička optimizacija. Sa determinističkom optimizacijom pretpostavlja se da su podaci za problem apsolutno tačni. Međutim, po mnogim aktuelnim pitanjima, oni se ne mogu znati iz više razloga.

Prvi je povezan sa jednostavnom greškom mjerenja. Drugi razlog je fundamentalniji. Sastoji se u činjenici da neki podaci predstavljaju informacije o budućnosti, na primjer, potražnja za proizvodom ili cijena za budući vremenski period. Prilikom optimizacije u stohastičkim uslovima optimizacije, nesigurnost je uključena u model.

Glavne komponente

Objektivna funkcija je ona koju treba minimizirati ili maksimizirati. Većina vrsta problema optimizacije ima jednu objektivnu funkciju. Ako ne, , tada se često mogu preformulisati tako da se izvrše.

Dva izuzetka od ovog pravila:

1. Zadatak traženja cilja. U većini poslovnih aplikacija, menadžer želi postići određeni cilj, istovremeno zadovoljavajući ograničenja modela. Korisnik ne želi posebno nešto optimizirati, pa nema smisla definirati ciljnu funkciju. Ovaj tip obično se naziva kao problem izvodljivosti.

2. Višestruke objektivne funkcije. Često korisnik želi optimizirati nekoliko različitih ciljeva odjednom. Obično su nekompatibilni. Varijable koje optimiziraju jedan cilj mogu biti daleko od najbolje za ostali.

Vrste komponenti:

• Upravljani ulazni podaci su skup varijabli odlučivanja koje utiču na vrijednost objektivne funkcije. U proizvodni zadatak varijable mogu uključivati dodjelu različitih raspoloživih resursa ili rad potreban za svaku radnju.
• Ograničenja su odnosi između varijabilnih rješenja i parametara. Za proizvodni problem nema smisla provoditi veliku količinu vremena na bilo kojoj aktivnosti, stoga su sve" privremene " varijable ograničene.
• Moguća i optimalna rešenja. Vrijednost rješenja za varijable, na kojem sva ograničenja su ispunjeni se zove izvodljivo. Većina algoritama ga prvo pronađe, a zatim pokušajte poboljšati. Konačno, oni mijenjaju varijable kako bi prešli s jednog izvedivog rješenja na drugo. Ovaj proces se ponavlja sve dok objektivna funkcija ne dostigne svoj maksimum ili minimum. Ovaj rezultat se naziva optimalnim rješenjem.

Algoritmi problema optimizacije razvijeni za sljedeće matematičke programe se široko koriste:

• Konveksno.
• Dijeljeno.
• Kvadratna.
• Geometrijski.

Google Linear Solvers

Linearna optimizacija ili programiranje je naziv koji se daje računskom procesu optimalnog rješavanja problema. Modeliran je kao skup linearnih odnosa koji nastaju u mnogim naučnim i inženjerskim disciplinama.

Google nudi tri načina za rješavanje problema linearne optimizacije:

• Open source library Glop.
• Dodatak za linearnu optimizaciju za Google tabele.
• Linearna Optimizacija usluga u Google Apps Script.

Glop je Google-ov ugrađeni linearni Rješavač. Dostupan je sa otvorenim kodom. Moguće je pristupiti Glop-u preko or-Tools linear solver packera, koji je omot za Glop.

Modul linearne optimizacije za Google tabele omogućava vam da izvršite linearnu formulaciju problema optimizacije unosom podataka u tabelu.

Kvadratno programiranje

Premium Solver platforma koristi proširenu LP/kvadratnu verziju Simplex metode sa ograničenjima obrade zadataka LP i QP do 2000 varijabilnih rješenja.

Sqp Solver za velike probleme koristi modernu implementaciju sparsity active set metode za rješavanje problema kvadratnog programiranja (QP) . Mehanizam za rješavanje XPRESS koristi prirodno proširenje metode "" Do riješiti probleme sa QP.

MOSEK Solver koristi metode ugrađene "Unutrašnja tačka" i auto-dual. Ovo je posebno efikasno za labavo povezane QP zadatke. Također može riješiti probleme velikog kvadratnog ograničenja (QCP) i programiranja konusa drugog reda (SOCP).

Proračuni za više operacija

Oni su prilično uspješno koriste koristeći mogućnosti Microsoft Office, na primjer, rješavanje problema optimizacije u Excelu.

U gornjoj tabeli, sljedeće oznake su:

• K1-K6-kupci koji trebaju obezbijediti proizvod.
• S1-S6 su potencijalne proizvodne lokacije koje se mogu izgraditi za ovo. Može se kreirati 1,2,3,4,5 ili svih 6 lokacija.

Za svaki objekt postoje fiksni troškovi navedeni u koloni I (Fix).

Ako lokacija ništa ne promijeni, neće se uzeti u obzir. Tada neće biti fiksnih troškova.

Identificirajte potencijalne lokacije kako biste dobili najnižu cijenu.

Pod ovim uslovima, lokacija je ili utvrđena ili ne. Ova dva stanja su sljedeća: "tačno-netačno" ili "1-0". Postoji šest država za šest lokacija, na primjer, samo je šesto postavljeno za 000001, za 111111 - sve.

U binarnom brojevnom sistemu postoje tačno 63 različite varijante od 000001 (1) do 111111 (63).

L2-L64 bi sada trebao imati {= višestruka operacija (K1)}, ovo su rezultati svih alternativnih rješenja. Tada je minimalna vrijednost = Min(L), a odgovarajuća alternativa je indeks (K).

CJELOBROJNO programiranje CPLEX

Ponekad linearni odnosi nisu dovoljni da uhvate suštinu poslovnog problema. Ovo je posebno tačno kada odluke uključuju diskretne izbore, kao što je otvaranje skladišta na određenoj lokaciji ili ne. U ovim situacijama potrebno je koristiti cjelobrojno programiranje.

Ako problem uključuje oba diskretna i kontinuirana selekcija, to je mješoviti cijeli program. Može imati linearne, konveksne kvadratne probleme i ista ograničenja drugog reda.

Cjelobrojni programi su mnogo složeniji od linearnih, ali imaju važne poslovne aplikacije. CPLEX softver koristi složene matematičke metode za rješavanje cjelobrojnih problema. Njegove metode uključuju sistematsko traženje mogućih kombinacija diskretnih varijabli koristeći linearne ili kvadratne programske relaksacije za izračunavanje granica vrijednosti optimalnog rješenja.

Oni također koriste LP i druge metode rješavanja problema optimizacije za izračunavanje ograničenja.

Standardni Microsoft Excel Solver

Ova tehnologija koristi osnovnu implementaciju osnovne Simplex metode za rješavanje LP problema. Ograničeno je na 200 varijabli. "Premium Solver" koristi poboljšanu primarnu simpleks metodu sa dvosmjernim granicama za varijable. Platforma Premium Solver koristi proširenu verziju LP/Quadratic Simplex solvera za rješavanje problema optimizacije sa do 2000 varijabilnih rješenja.

Veliki LP za Premium Solver platformu primjenjuje modernu implementaciju jednostavne i dvostruke simplex metode, koja koristi rijetkost u LP modelu za uštedu vremena i memorije, napredne strategije za ažuriranje i refaktoriranje matrica, višestruke i djelomične cijene i rotacije, kao i za prevazilaženje degeneracije. Ovaj mehanizam je dostupan u tri verzije (sa mogućnošću rukovanja do 8.000, 32.000 ili neograničenim brojem varijabli i ograničenja).

MOSEK Solver uključuje primarnu i dual simplex metodu koja također koristi rijetkost i koristi napredne strategije za ažuriranje matrice i "refaktorizaciju". Rješava probleme neograničene veličine, testirano je na problemi sa linearnim programiranjem sa milionima varijabilnih rješenja.

Primjer korak po korak u Excelu

Da biste definirali model zadatka optimizacije u Excelu, izvršite sljedeće korake:

• Organizirajte podatke za problem u proračunskoj tablici u logički oblik.
• Odaberite ćeliju za čuvanje svaka varijabla.
• Stvorite formulu za izračunavanje ciljnog matematičkog modela problema optimizacije u ćeliji.
• Kreirajte formule za izračunavanje lijeve strane svakog ograničenja.
• Koristite Excel dijaloge za izvještavanje "Solver" o varijablama odluka, ciljevima, ograničenjima i željenim granicama od ovih parametara.
• Lansiranje "Solver", za pronalaženje optimalnog rješenja.
• Kreirajte Excel list.
• Organizirajte podatke za problem u Excelu, gdje se izračunava formula za funkciju cilja i ograničenja.

U gornjoj tabeli, ćelije B4, C4, D4 i E4 su rezervisane da predstavljaju varijable odluke X 1, X 2, X 3 i X 4. Primjeri rješenja:

• Model asortimana proizvoda (profit za svaku vrstu proizvoda 450, 1150, 800 i 400 dolara) unesen je u ćelije B5, C5, D5 i E5, respektivno. Ovo vam omogućava da izračunate cilj u F5 = B5 * B4 + C5 * C4 + D5 * D4 + E5 * E4 ili F5: = SUMPRODUCT (B5:E5, B4:E4).
• B8 uvodi količinu resursa, potrebno za proizvodite svaku vrstu proizvoda.
• Formula za F8: = SUMPRODUCT (B8: E8, $ B$4: $ E$4).
• Kopirajte ovu formulu u F9. Znakovi dolara u $B$4: $E$4 ukazuju na to da ovaj raspon ćelija ostaje konstantan.
• U G8 se uvodi raspoloživa količina resursa svake vrste, koja odgovara vrijednostima ograničenja s desne strane. Ovo vam omogućava da ih izrazite ovako: F11<= G8: G11.
• Ovo je ekvivalentno četiri ograničenja F8<= G8, F9 <= G9, F10 <= G10 i F11 <= G11. Ovaj set možete uneti direktno u dijaloge Solver zajedno sa uslovima ne-negativnosti B4: E4> = 0

Područja praktične primjene metode

Linearna optimizacija ima mnogo praktičnih primjena kao primjer problema optimizacije:

Kompanija može napraviti nekoliko proizvoda sa poznatom marginom doprinosa. Za proizvodnju jedinice svakog proizvoda potrebna je određena količina ograničenih resursa. Zadatak je stvoriti proizvodni program za određivanje koliko svakog proizvoda treba proizvesti tako da se profit kompanije maksimizira bez kršenja ograničenja resursa.

Problemi sa mešanjem su rešenje problema optimizacije povezanih sa kombinovanjem sastojaka u konačni proizvod. Primjer za to je problem prehrane, koji je proučavao George Danzig 1947. godine. Daju se brojne sirovine, na primjer, zob, svinjsko i suncokretovo ulje, kao i sadržaj hranjivih tvari u njima, na primjer, proteini, masti, vitamin A i njihova cijena po kilogramu. Zadatak je miješati jedan ili više finalnih proizvoda od sirovina uz minimalne troškove, pod uslovom da minimum i maksimum ograničenja za njihovu nutritivnu vrijednost su ispunjena.

Klasična primjena problema linearne optimizacije je određivanje usmjeravanja za potrebe prometa u telekomunikacijskim ili transportnim mrežama. Istovremeno, tokovi moraju biti usmereni kroz mrežu na način da svi saobraćajni zahtevi budu ispunjeni bez kršenja uslova propusnog opsega.

U okviru matematičke teorije, linearna optimizacija se može koristiti za izračunavanje optimalnih strategija u igrama nulte sume za dvije osobe. U ovom slučaju, raspodjela vjerovatnoće se izračunava za svakog učesnika, što je koeficijent nasumičnog miješanja njegovih strategija.

Nijedan uspješan poslovni proces u svijetu nije moguć bez optimizacije. Dostupni su mnogi algoritmi za optimizaciju. Neke metode su pogodne samo za određene vrste problema. Važno je znati prepoznati njihove karakteristike i odaberite odgovarajuću metodu rješenja.