Optimizacija vam pomaže pronaći najbolji rezultat koji donosi profit, smanjuje troškove ili postavlja parametar koji uzrokuje neuspjehe poslovnih procesa.
Ovaj proces se također naziva matematičko programiranje. Rješava problem određivanja raspodjele ograničenih resursa potrebnih za postizanje cilja koji je postavio voditelj optimizacijskog problema. Od svih mogućih opcija, poželjno je pronaći onu koja maksimizira (ili smanjuje) kontrolni parametar, na primjer, dobit ili trošak. Optimizacijski modeli se također nazivaju preskriptivnim ili normativnim jer nastoje pronaći izvedivu strategiju za poslovanje.
Povijest razvoja
Linearno programiranje (LP) radi s klasom problema optimizacije gdje su sva ograničenja linearna.
Predstavljamo kratku povijest razvoja LP-a:
- Godine 1762. Lagrange je riješio jednostavne probleme optimizacije s ograničenjima jednakosti.
- Gauss je 1820. odlučiolinearni sustav jednadžbi pomoću eliminacije.
- Godine 1866. Wilhelm Jordan je usavršio metodu pronalaženja pogrešaka najmanjih kvadrata kao prikladnog kriterija. Ovo se sada zove Gauss-Jordanova metoda.
- Digitalno računalo pojavilo se 1945.
- Danzig je izumio simpleks metode 1947.
- 1968. godine, Fiacco i McCormick uveli su metodu unutarnje točke.
- Godine 1984. Karmarkar je primijenio unutarnju 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 primjenjivana matematička teorija. Međutim, mnogi zanimljivi problemi optimizacije su nelinearni.
Što 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. Znanstvenici razvijaju računske algoritme, uključujući metode unutarnje točke za linearno programiranje, geometriju, analizu konveksnih skupova i funkcija te proučavanje posebno strukturiranih problema kao što je kvadratno programiranje.
Nelinearna optimizacija pruža temeljno razumijevanje matematičke analize i naširoko se koristi u različitim područjima kao što su inženjering, regresijska analiza, upravljanje resursima, geofizička istraživanja i ekonomija.
Klasifikacija problema optimizacije
Važan korakProces optimizacije je klasifikacija modela, budući da su njihovi algoritmi rješenja prilagođeni određenom tipu.
1. Problemi s 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 računalne 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 sustava 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 uvjete komplementarnosti. U praksi se zadaci s nekoliko ciljeva često preformuliraju u one s jednim ciljem.
5. Deterministička naspram stohastičke optimizacije. Deterministička optimizacija pretpostavlja da podaci zazadaci su potpuno točni. Međutim, o mnogim aktualnim temama oni se ne mogu znati iz više razloga.
Prvi se odnosi na jednostavnu pogrešku mjerenja. Drugi razlog je temeljniji. 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 uvjetima 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 preformulirati da rade.
Dvije iznimke 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. Puno objektivnih značajki. Često bi korisnik želio optimizirati nekoliko različitih ciljeva odjednom. Obično su nespojive. Varijable koje se optimiziraju za jedan cilj možda neće biti najbolje za druge.
Vrste komponenti:
- Kontrolirani ulaz je skup varijabli odlučivanja koje utječu na vrijednost ciljne funkcije. U proizvodnom zadatku, varijable mogu uključivati distribuciju različitih raspoloživih resursa ili potrebnog radasvaka radnja.
- Ograničenja su odnosi između varijabli odluke i parametara. Za proizvodni problem, nema smisla trošiti puno vremena na bilo koju aktivnost, stoga 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 ga pokuša poboljšati. Konačno, mijenjaju varijable kako bi prešli s jednog izvedivog rješenja na drugo. Ovaj proces se ponavlja sve dok funkcija cilja ne dosegne svoj maksimum ili minimum. Ovaj rezultat naziva se optimalnim rješenjem.
Algoritmi optimizacijskih problema razvijeni za sljedeće matematičke programe se široko koriste:
- konveksno.
- Odvojivo.
- Kvadratna.
- geometrijski.
Google linearni rješavači
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 znanstvenim i inženjerskim disciplinama.
Google nudi tri načina rješavanja problema linearne optimizacije:
- Glop open source knjižnica.
- Dodatak za linearnu optimizaciju za Google tablice.
- Usluga linearne optimizacije u Google Apps Script.
Glop je ugrađen u Googlelinearni rješavač. Dostupan je u otvorenom kodu. Možete pristupiti Glop-u putem omota linearnog rješavača OR-Tools, koji je omot za Glop.
Modul linearne optimizacije za Google tablice omogućuje vam da izvedete linearnu izjavu o problemu optimizacije unosom podataka u proračunsku tablicu.
Kvadratično programiranje
Platforma Premium Solver koristi proširenu LP/kvadratičnu verziju Simplex metode s ograničenjima obrade LP i QP problema do 2000 varijabli odluke.
SQP Solver za probleme velikih razmjera koristi modernu implementaciju metode aktivnog skupa s rijetkošću za rješavanje problema kvadratnog programiranja (QP). XPRESS Solver motor koristi prirodno proširenje metode "Interior Point" ili Newton Barrier za rješavanje QP problema.
MOSEK Solver primjenjuje ugrađenu "unutarnju točku" i automatske dvostruke metode. Ovo je posebno učinkovito 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 značajki, na primjer, rješavanje problema optimizacije u Excelu.
U gornjoj tablici simboli su:
- K1 - K6 - kupci koji trebaju osigurati robu.
- S1 - S6 su potencijalna proizvodna mjesta koja bi se mogla izgraditi za to. Može se kreirati1, 2, 3, 4, 5 ili svih 6 lokacija.
Postoje fiksni troškovi za svaki objekt naveden u stupcu I (popravak).
Ako lokacija ništa ne promijeni, neće se računati. Tada neće biti fiksnih troškova.
Odredite potencijalne lokacije kako biste ostvarili najnižu cijenu.
U ovim uvjetima, 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 šesto, 111111 je postavljeno na sve.
U binarnom brojevnom sustavu postoje točno 63 različite opcije od 000001 (1) do 111111 (63).
L2-L64 sada treba glasiti {=MULTIPLE OPERATION (K1)}, ovo su rezultati svih alternativnih rješenja. Tada je minimalna vrijednost=Min (L), a odgovarajuća alternativa je INDEX (K).
CPLEX cjelobrojno programiranje
Ponekad linearni odnos nije dovoljan da se dođe do srži poslovnog problema. To je osobito istinito kada odluke uključuju diskretne izbore, poput otvaranja ili ne otvaranja skladišta na određenom mjestu. U tim se situacijama mora koristiti cjelobrojno programiranje.
Ako problem uključuje i diskretne i kontinuirane izbore, radi se o mješovitom cjelobrojnom programu. 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. SoftverSoftver CPLEX koristi složene matematičke metode za rješavanje cjelobrojnih problema. Njegove metode uključuju sustavno 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.
Standardni 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šanu primarnu simpleks metodu s dvostranim granicama za varijable. Platforma Premium Solver koristi proširenu verziju LP/Quadratic Simplex Solver za rješavanje problema optimizacije s do 2000 varijabli odluke.
Veliki LP za platformu Premium Solver primjenjuje najsuvremeniju 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 djelomično određivanje cijena i rotacije, te za prevladavanje degeneracije. Ovaj motor je dostupan u tri verzije (sposoban rukovati s do 8.000, 32.000 ili neograničenim varijablama i ograničenjima).
MOSEK Solver uključuje primarni i dualni simpleks, metodu koja također iskorištava rijetkost i koristi napredne strategije za ažuriranje matrice i "refaktorizaciju". Rješava probleme neograničene veličine, biotestirano na problemima linearnog programiranja s milijunima 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 tablici u logičnom obliku.
- Odaberite ćeliju za pohranjivanje svake varijable.
- Kreirajte u ćeliji formulu za izračun ciljnog matematičkog modela optimizacijskog problema.
- Stvorite formule za izračunavanje lijeve strane svakog ograničenja.
- Koristite dijaloške okvire u Excelu da biste Solveru rekli o varijablama odluke, ciljevima, ograničenjima i željenim granicama tih parametara.
- Pokrenite "Solver" da pronađete optimalno rješenje.
- Izradite Excel tablicu.
- Organizirajte podatke za problem u Excelu gdje se izračunava formula za funkciju cilja i ograničenje.
U gornjoj tablici ćelije B4, C4, D4 i E4 rezervirane su za predstavljanje varijabli odluke X 1, X 2, X 3 i X 4. Primjeri odluke:
- Model miksa proizvoda (450 USD, 1150 USD, 800 USD i 400 USD dobiti po proizvodu) unesen je u ćelije B5, C5, D5 i E5, redom. To omogućuje da se cilj izračuna u F5=B5B4 + C5C4 + D5D4 + E5E4 ili F5:=ZUMPROIZVOD (B5: E5, B4: E4).
- U B8 unesite količinu resursa potrebnih za proizvodnju svake vrste proizvoda.
- Formula za F8:=SUMPRODUCT(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 s desne strane. To vam omogućuje da ih izrazite ovako: F11<=G8: G11.
- Ovo je ekvivalentno četiri ograničenja F8<=G8, F9 <=G9, F10 <=G10 i F11=0
Područja praktične primjene metode
Linearna optimizacija ima mnogo praktičnih primjena kao primjer problema optimizacije:
Tvrtka može proizvesti nekoliko proizvoda s poznatom maržom doprinosa. Proizvodnja jedinice svakog artikla zahtijeva poznatu količinu ograničenih resursa. Zadatak je stvoriti proizvodni program koji će odrediti koliko svakog proizvoda treba proizvesti kako bi se profit tvrtke povećao 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. Daje se niz sirovina, poput zobi, svinjetine i suncokretovog ulja, uz njihovu nutritivnu vrijednost, kao što su proteini, masti, vitamin A, te njihovu cijenu po kilogramu. Izazov je pomiješati jedan ili više krajnjih proizvoda od sirovina uz najnižu moguću cijenu uz poštivanje minimalnih i maksimalnih ograničenja njihove nutritivne vrijednosti.
Klasična primjena problema linearne optimizacije je određivanje usmjeravanja za potrebepromet u telekomunikacijskim ili prometnim mrežama. Istodobno, tokovi se moraju usmjeravati kroz mrežu na takav način da se ispune svi prometni zahtjevi bez kršenja uvjeta propusnosti.
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 izračunava se distribucija vjerojatnosti za svakog sudionika, što je koeficijent slučajnog miješanja njegovih strategija.
Nijedan uspješan poslovni proces u svijetu nije moguć bez optimizacije. Dostupni su mnogi algoritmi za optimizaciju. Neke su metode prikladne samo za određene vrste problema. Važno je znati prepoznati njihove karakteristike i odabrati odgovarajuću metodu rješenja.
