Optimizacija vam pomaže da pronađete najbolji rezultat koji donosi profit, smanjuje troškove ili postavlja parametar koji uzrokuje neuspjehe poslovnih procesa.
Ovaj proces se naziva i matematičko programiranje. Njime se rješava problem određivanja raspodjele ograničenih resursa neophodnih za postizanje cilja koji je postavio rukovodilac optimizacijskog problema. Od svih mogućih opcija, poželjno je pronaći onu koja maksimizira (ili smanjuje) kontrolni parametar, na primjer, profit ili trošak. Optimizacijski modeli se također nazivaju preskriptivnim ili normativnim jer nastoje pronaći izvodljivu strategiju za poslovanje.
Historija razvoja
Linearno programiranje (LP) radi s klasom problema optimizacije gdje su sva ograničenja linearna.
Predstavljamo kratku istoriju razvoja LP-a:
- Godine 1762. Lagrange je riješio jednostavne probleme optimizacije sa ograničenjima jednakosti.
- Godine 1820, Gauss je odlučiolinearni sistem jednadžbi koristeći eliminaciju.
- Godine 1866. Wilhelm Jordan je usavršio metodu pronalaženja grešaka najmanjih kvadrata kao kriterija uklapanja. Ovo se sada zove Gauss-Jordan metoda.
- Digitalni kompjuter se pojavio 1945.
- Danzig je izmislio simpleks metode 1947.
- 1968. godine, Fiacco i McCormick uveli su metodu unutrašnje tačke.
- Godine 1984. Karmarkar je 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 problema iz stvarnog svijeta i kao široko primijenjena 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, multivarijantnog računa, numeričke analize i računskih metoda. Naučnici razvijaju računske algoritme, uključujući metode unutrašnje tačke za linearno programiranje, geometriju, analizu konveksnih skupova i funkcija i proučavanje posebno strukturiranih problema kao što je kvadratno programiranje.
Nelinearna optimizacija pruža temeljno razumijevanje matematičke analize i široko se koristi u različitim poljima kao što su inženjering, regresiona analiza, upravljanje resursima, geofizička istraživanja i ekonomija.
Klasifikacija problema optimizacije
Važan korakProces optimizacije je klasifikacija modela, jer su njihovi algoritmi rješenja prilagođeni određenom tipu.
1. Problemi sa diskretnom i kontinuiranom optimizacijom. Neki modeli imaju smisla samo ako varijable uzimaju vrijednosti iz diskretnog podskupa cijelih brojeva. Drugi sadrže podatke koji mogu poprimiti bilo koju stvarnu vrijednost. Obično ih je lakše riješiti. Poboljšanja u algoritmima, u kombinaciji s napretkom kompjuterske tehnologije, dramatično su povećala veličinu i složenost problema optimizacije linearnog programiranja.
2. Neograničena i ograničena optimizacija. Druga važna razlika su zadaci kod kojih nema ograničenja na 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 klasificirati prema prirodi funkcija (linearne i nelinearne, konveksne i glatke, diferencibilne i nediferencirane).
3. Zadaci izvodljivosti. Njihov cilj je pronaći varijabilne vrijednosti koje zadovoljavaju ograničenja modela bez ikakvog specifičnog cilja optimizacije.
4. Komplementarni zadaci. Široko se koriste 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 one s jednim ciljem.
5. Deterministička nasuprot stohastičkoj optimizaciji. Deterministička optimizacija pretpostavlja da podaci zazadaci su potpuno tačni. Međutim, o mnogim aktuelnim temama oni se ne mogu znati iz više razloga.
Prvi se odnosi na jednostavnu grešku mjerenja. Drugi razlog je fundamentalniji. Ona leži u činjenici da neki podaci predstavljaju informaciju o budućnosti, na primjer, potražnja za proizvodom ili cijena za budući vremenski period. Prilikom optimizacije u uslovima stohastičke optimizacije, nesigurnost je uključena u model.
Glavne komponente
Ciljna funkcija je ona koju treba minimizirati ili maksimizirati. Većina tipova optimizacijskih problema ima jednu ciljnu funkciju. Ako ne, često se mogu preformulisati da rade.
Dva izuzetka od ovog pravila:
1. Zadatak traženja cilja. U većini poslovnih aplikacija, menadžer želi postići određeni cilj dok zadovoljava ograničenja modela. Korisnik ne želi nešto posebno optimizirati, pa nema smisla definirati funkciju cilja. Ovaj tip se obično naziva problemom zadovoljavanja.
2. Mnogo objektivnih karakteristika. Često bi korisnik želio optimizirati nekoliko različitih ciljeva odjednom. Obično su nekompatibilni. Varijable koje se optimiziraju za jedan cilj možda neće biti najbolje za druge.
Vrste komponenti:
- Kontrolisani ulaz je skup varijabli odlučivanja koje utiču na vrijednost ciljne funkcije. U proizvodnom zadatku, varijable mogu uključivati distribuciju različitih raspoloživih resursa ili potrebnog radasvaka akcija.
- Ograničenja su odnosi između varijabli odlučivanja i parametara. Za proizvodni problem, nema smisla trošiti puno vremena na bilo koju aktivnost, zato ograničite sve "privremene" varijable.
- Moguća i optimalna rješenja. Vrijednost odluke za varijable, pod kojom su sva ograničenja zadovoljena, naziva se zadovoljavajuća. Većina algoritama prvo ga pronađe, a zatim pokuša da ga poboljša. Konačno, oni mijenjaju varijable kako bi prešli s jednog izvodljivog rješenja na drugo. Ovaj proces se ponavlja sve dok funkcija cilja ne dostigne svoj maksimum ili minimum. Ovaj rezultat se naziva optimalnim rješenjem.
Algoritmi optimizacijskih problema razvijeni za sljedeće matematičke programe se široko koriste:
- konveksno.
- Odvojivo.
- Quadratic.
- Geometrijski.
Google Linearni Solvers
Linearna optimizacija ili programiranje je naziv koji se daje računarskom 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:
- Glop open source biblioteka.
- Dodatak za linearnu optimizaciju za Google tabele.
- Usluga linearne optimizacije u Google Apps Script-u.
Glop je ugrađen u Googlelinearni rješavač. Dostupan je u otvorenom kodu. Možete pristupiti Glop-u kroz OR-Tools linearni solver omotač, koji je omot za Glop.
Modul linearne optimizacije za Google Sheets vam omogućava da izvedete linearnu izjavu o problemu optimizacije unosom podataka u tabelu.
Kvadratično programiranje
Platforma Premium Solver koristi proširenu LP/kvadratičnu verziju Simplex metode sa ograničenjima obrade LP i QP problema do 2000 varijabli odluke.
SQP Solver za probleme velikih razmjera koristi modernu implementaciju metode aktivnog skupa sa rijetkošću za rješavanje problema kvadratnog programiranja (QP). XPRESS Solver motor koristi prirodno proširenje metode "unutrašnje tačke" ili Newton Barrier za rješavanje QP problema.
MOSEK Solver primjenjuje ugrađenu "Inside Point" i auto-dual metode. Ovo je posebno efikasno za labavo povezane QP probleme. Također može riješiti probleme kvadratnog ograničenja (QCP) i programiranja konusa drugog reda (SOCP).
Izračuni s više operacija
Prilično se uspješno koriste uz korištenje Microsoft Office funkcija, na primjer, rješavanje problema optimizacije u Excel-u.
U gornjoj tabeli, simboli su:
- K1 - K6 - kupci koji trebaju obezbijediti robu.
- S1 - S6 su potencijalna proizvodna mjesta koja bi se mogla izgraditi za ovo. Može se kreirati1, 2, 3, 4, 5 ili svih 6 lokacija.
Postoje fiksni troškovi za svaki objekat naveden u koloni I (fix).
Ako lokacija ništa ne promijeni, neće se računati. Tada neće biti fiksnih troškova.
Identifikujte potencijalne lokacije da ostvarite najnižu cenu.
U ovim uslovima, lokacija je ili utvrđena ili ne. Ova dva stanja su: "TRUE - FALSE" ili "1 - 0". Postoji šest stanja za šest lokacija, na primjer, 000001 je postavljeno samo na šestu, 111111 je postavljeno na sve.
U binarnom brojevnom sistemu postoje tačno 63 različite opcije od 000001 (1) do 111111 (63).
L2-L64 sada treba da glasi {=MULTIPLE OPERATION (K1)}, ovo su rezultati svih alternativnih rješenja. Tada je minimalna vrijednost=Min (L), a odgovarajuća alternativa je INDEX (K).
CPLEX integer programiranje
Ponekad linearni odnos nije dovoljan da se dođe do srži poslovnog problema. Ovo je posebno istinito kada odluke uključuju diskretne izbore, kao što je da li otvoriti skladište na određenoj lokaciji ili ne. U ovim situacijama se mora koristiti cjelobrojno programiranje.
Ako problem uključuje i diskretne i kontinuirane izbore, to je mješoviti cjelobrojni program. Može imati linearne, konveksne kvadratne probleme i ista ograničenja drugog reda.
Cjelobrojni programi su mnogo složeniji od linearnih programa, ali imaju važne poslovne aplikacije. SoftverCPLEX 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 softverske 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.
Standard Microsoft Excel Solver
Ova tehnologija koristi osnovnu implementaciju glavne Simplex metode za rješavanje LP problema. Ograničen je na 200 varijabli. "Premium Solver" koristi poboljšani primarni simpleks metod sa dvostranim granicama za varijable. Platforma Premium Solver koristi proširenu verziju LP/Quadratic Simplex Solver-a za rješavanje problema optimizacije sa do 2000 varijabli odlučivanja.
Veliki LP za platformu Premium Solver primjenjuje najsavremeniju implementaciju jednostavne i dvostruke simpleks metode, koja koristi rijetkost u LP modelu za uštedu vremena i memorije, napredne strategije za ažuriranje i matrice za refaktoriranje, višestruko i parcijalno određivanje cijena i rotacije, te za prevazilaženje degeneracije. Ovaj motor je dostupan u tri verzije (sposoban za rukovanje do 8,000, 32,000, ili neograničene varijable i ograničenja).
MOSEK Solver uključuje primarni i dualni simpleks, metodu koja također koristi rijetkost i koristi napredne strategije za ažuriranje matrice i "refaktorizaciju". Rješava probleme neograničene veličine, biotestirano na problemima linearnog programiranja sa milionima varijabli odlučivanja.
Primjer korak po korak u EXCEL-u
Da biste definirali model problema optimizacije u Excelu, izvršite sljedeće korake:
- Organizirajte podatke za problem u proračunskoj tabeli u logičnom obliku.
- Odaberite ćeliju za pohranjivanje svake varijable.
- Kreirajte u ćeliji formulu za izračunavanje ciljnog matematičkog modela optimizacijskog problema.
- Kreirajte formule za izračunavanje lijeve strane svakog ograničenja.
- Koristite dijaloge u Excel-u da kažete Solveru o varijablama odluke, ciljevima, ograničenjima i željenim granicama tih parametara.
- Pokrenite "Solver" da pronađete optimalno rješenje.
- Kreirajte Excel list.
- Organizirajte podatke za problem u Excelu gdje se izračunava formula za funkciju cilja i ograničenje.
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 odluke:
- Model miksa proizvoda ($450, $1150, $800 i $400 profita po proizvodu) unesen je u ćelije B5, C5, D5 i E5, respektivno. Ovo omogućava da se cilj izračuna u F5=B5B4 + C5C4 + D5D4 + E5E4 ili F5:=ZBIR (B5: E5, B4: E4).
- U B8 unesite količinu resursa potrebnih za proizvodnju svake vrste proizvoda.
- Formula za F8:=SUMPROIZVOD(B8:E8, $B$4:$E$4).
- Kopiraj ovoformula u F9. Znakovi dolara u $B$4:$E$4 pokazuju da ovaj raspon ćelija ostaje konstantan.
- U G8 unesite dostupnu količinu resursa svake vrste, koja odgovara vrijednostima ograničenja na desnoj strani. 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=0
Polja praktične primjene metode
Linearna optimizacija ima mnogo praktičnih primjena kao primjer problema optimizacije:
Kompanija može napraviti nekoliko proizvoda sa poznatom maržom doprinosa. Proizvodnja jedinice svakog artikla zahtijeva poznatu količinu ograničenih resursa. Zadatak je kreirati proizvodni program koji će odrediti koliko svakog proizvoda treba proizvesti kako bi profit kompanije bio maksimiziran bez kršenja ograničenja resursa.
Problemi miješanja su rješenje za probleme optimizacije koji se odnose na kombiniranje sastojaka u konačni proizvod. Primjer za to je problem prehrane koji je proučavao George Danzig 1947. godine. Daju se brojne sirovine, kao što su zob, svinjetina i suncokretovo ulje, zajedno sa njihovim nutritivnim sadržajem, kao što su proteini, masti, vitamin A, i njihova cijena po kilogramu. Izazov je pomiješati jedan ili više krajnjih proizvoda od sirovina uz najnižu moguću cijenu uz poštovanje minimalnih i maksimalnih ograničenja njihove nutritivne vrijednosti.
Klasična primjena problema linearne optimizacije je određivanje rutiranja za potrebesaobraćaja u telekomunikacijskim ili transportnim mrežama. Istovremeno, tokovi moraju biti rutirani kroz mrežu na takav način da su ispunjeni svi zahtjevi za promet bez kršenja uslova propusnog opsega.
U matematičkoj teoriji, linearna optimizacija se može koristiti za izračunavanje optimalnih strategija u igrama s nultom sumom za dvije osobe. U ovom slučaju se izračunava distribucija vjerovatnoće za svakog učesnika, što je koeficijent slučajnog miješanja njegovih strategija.
Nijedan uspješan poslovni proces u svijetu nije moguć bez optimizacije. Postoji mnogo dostupnih algoritama za optimizaciju. Neke metode su prikladne samo za određene vrste problema. Važno je znati prepoznati njihove karakteristike i odabrati odgovarajući metod rješenja.
