Optimizacija vam pomaga najti najboljši rezultat, ki prinaša dobiček, znižuje stroške ali nastavi parameter, ki povzroča napake v poslovnih procesih.
Ta proces se imenuje tudi matematično programiranje. Rešuje problem določanja porazdelitve omejenih virov, potrebnih za doseganje cilja, ki ga je postavil vodja optimizacijskega problema. Med vsemi možnimi možnostmi je zaželeno najti tisto, ki poveča (ali zmanjša) kontrolni parameter, na primer dobiček ali stroške. Optimizacijski modeli se imenujejo tudi predpisani ali normativni, ker iščejo izvedljivo strategijo za podjetje.
zgodovina razvoja
Linearno programiranje (LP) deluje z razredom optimizacijskih problemov, kjer so vse omejitve linearne.
Predstavljamo kratko zgodovino razvoja LP:
- Leta 1762 je Lagrange rešil preproste optimizacijske probleme z omejitvami enakosti.
- Leta 1820 se je Gauss odločillinearni sistem enačb z uporabo izločanja.
- Leta 1866 je Wilhelm Jordan izpopolnil metodo iskanja napak najmanjših kvadratov kot ustreznega merila. To se zdaj imenuje Gauss-Jordanova metoda.
- Digitalni računalnik se je pojavil leta 1945.
- Danzig je izumil simpleks metode leta 1947.
- Leta 1968 sta Fiacco in McCormick predstavila metodo Inside Point.
- Leta 1984 je Karmarkar uporabil notranjo metodo za reševanje linearnih programov in dodal svojo inovativno analizo.
LP se je izkazal za izjemno zmogljivo orodje tako za modeliranje resničnih problemov kot tudi kot široko uporabna matematična teorija. Vendar pa je veliko zanimivih optimizacijskih problemov nelinearnih.
Kaj storiti v tem primeru? Preučevanje takšnih problemov vključuje raznoliko mešanico linearne algebre, multivariatnega računa, numerične analize in računalniških metod. Znanstveniki razvijajo računalniške algoritme, vključno z metodami notranjih točk za linearno programiranje, geometrijo, analizo konveksnih nizov in funkcij ter preučevanjem posebej strukturiranih problemov, kot je kvadratno programiranje.
Nelinearna optimizacija zagotavlja temeljno razumevanje matematične analize in se pogosto uporablja na različnih področjih, kot so inženiring, regresijska analiza, upravljanje virov, geofizikalno raziskovanje in ekonomija.
Razvrstitev težav pri optimizaciji
Pomemben korakProces optimizacije je razvrščanje modelov, saj so njihovi algoritmi rešitev prilagojeni določenemu tipu.
1. Težave z diskretno in kontinuirano optimizacijo. Nekateri modeli so smiselni le, če spremenljivke vzamejo vrednosti iz diskretne podmnožice celih števil. Drugi vsebujejo podatke, ki lahko dobijo katero koli resnično vrednost. Običajno jih je lažje rešiti. Izboljšave algoritmov v kombinaciji z napredkom računalniške tehnologije so dramatično povečale velikost in kompleksnost optimizacijskega problema linearnega programiranja.
2. Neomejena in omejena optimizacija. Druga pomembna razlika so naloge, pri katerih ni omejitev glede spremenljivk. Lahko se zelo giblje od preprostih ocenjevalnikov do sistemov enakosti in neenakosti, ki modelirajo zapletena razmerja med podatki. Takšne optimizacijske probleme je mogoče nadalje razvrstiti glede na naravo funkcij (linearne in nelinearne, konveksne in gladke, diferencibilne in nediferencirane).
3. Naloge izvedljivosti. Njihov cilj je najti spremenljivke vrednosti, ki izpolnjujejo omejitve modela brez posebnega cilja optimizacije.
4. Komplementarne naloge. Široko se uporabljajo v tehnologiji in ekonomiji. Cilj je najti rešitev, ki izpolnjuje pogoje komplementarnosti. V praksi se naloge z več cilji pogosto preoblikujejo v enociljne.
5. Deterministična v primerjavi s stohastično optimizacijo. Deterministična optimizacija predpostavlja, da so podatki zanaloge so popolnoma točne. Vendar pa o številnih aktualnih temah niso znani iz več razlogov.
Prva je povezana s preprosto napako pri merjenju. Drugi razlog je bolj temeljni. Leži v tem, da nekateri podatki predstavljajo informacije o prihodnosti, na primer povpraševanje po izdelku ali ceno za prihodnje časovno obdobje. Pri optimizaciji v pogojih stohastične optimizacije je v model vključena negotovost.
Glavne komponente
Ciljna funkcija je tista, ki jo je treba zmanjšati ali povečati. Večina vrst optimizacijskih problemov ima eno ciljno funkcijo. Če ne, jih je mogoče pogosto preoblikovati, da delujejo.
Dve izjemi od tega pravila:
1. Ciljna iskalna naloga. V večini poslovnih aplikacij želi upravitelj doseči določen cilj, hkrati pa zadovoljiti omejitve modela. Uporabnik ne želi nečesa posebej optimizirati, zato nima smisla definirati ciljne funkcije. Ta vrsta se običajno imenuje problem zadovoljivosti.
2. Veliko objektivnih lastnosti. Pogosto bi uporabnik želel optimizirati več različnih ciljev hkrati. Običajno so nezdružljivi. Spremenljivke, ki optimizirajo za en cilj, morda niso najboljše za druge.
Vrste komponent:
- Kontrolirani vhod je nabor spremenljivk odločanja, ki vplivajo na vrednost ciljne funkcije. V proizvodni nalogi lahko spremenljivke vključujejo porazdelitev različnih razpoložljivih virov ali delovne sile, ki je potrebna za tovsako dejanje.
- Omejitve so razmerja med spremenljivkami odločitve in parametri. Za proizvodni problem ni smiselno porabiti veliko časa za nobeno dejavnost, zato omejite vse "začasne" spremenljivke.
- Možne in optimalne rešitve. Vrednost odločitve za spremenljivke, pri kateri so izpolnjene vse omejitve, se imenuje zadovoljiva. Večina algoritmov ga najprej najde, nato pa ga poskuša izboljšati. Končno spremenijo spremenljivke, da se premaknejo od ene izvedljive rešitve v drugo. Ta postopek se ponavlja, dokler ciljna funkcija ne doseže svojega maksimuma ali minimuma. Ta rezultat se imenuje optimalna rešitev.
Algoritmi optimizacijskih problemov, razviti za naslednje matematične programe, se pogosto uporabljajo:
- konveksno.
- ločljivo.
- kvadratično.
- geometrijsko.
Google Linear Solvers
Linearna optimizacija ali programiranje je ime za računski proces optimalnega reševanja problema. Modeliran je kot niz linearnih razmerij, ki se pojavljajo v številnih znanstvenih in inženirskih disciplinah.
Google ponuja tri načine za reševanje problemov linearne optimizacije:
- Glop odprtokodna knjižnica.
- Dodatek za linearno optimizacijo za Google Preglednice.
- Storitev linearne optimizacije v Google Apps Script.
Glop je vgrajen v Googlelinearni reševalec. Na voljo je v odprtokodni obliki. Do Glopa lahko dostopate prek linearnega reševalnega ovoja OR-Tools, ki je ovoj za Glop.
Modul za linearno optimizacijo za Google Preglednice vam omogoča, da izvedete linearno izjavo optimizacijskega problema z vnosom podatkov v preglednico.
Kvadratično programiranje
Platforma Premium Solver uporablja razširjeno LP/kvadratično različico metode Simplex z omejitvami obdelave težav LP in QP do 2000 spremenljivk odločanja.
SQP Solver za velike probleme uporablja sodobno izvedbo metode aktivnega niza z redkostjo za reševanje problemov kvadratnega programiranja (QP). Motor XPRESS Solver uporablja naravno razširitev metode "Notranja točka" ali Newton Barrier za reševanje težav QP.
MOSEK Solver uporablja vdelano "notranjo točko" in samodejne dvojne metode. To je še posebej učinkovito pri ohlapno povezanih težavah QP. Prav tako lahko reši težave s kvadratno omejitvijo lestvice (QCP) in programiranjem stožca drugega reda (SOCP).
Izračuni z več operacijami
Uspešno se uporabljajo pri uporabi funkcij Microsoft Office, na primer pri reševanju problemov optimizacije v Excelu.
V zgornji tabeli so simboli:
- K1 - K6 - stranke, ki morajo zagotoviti blago.
- S1 - S6 so potencialna proizvodna mesta, ki bi jih lahko zgradili za to. Lahko se ustvari1, 2, 3, 4, 5 ali vseh 6 lokacij.
Za vsak objekt, naveden v stolpcu I (popravek), obstajajo fiksni stroški.
Če lokacija nič ne spremeni, se ne bo štela. Potem ne bo fiksnih stroškov.
Ugotovite potencialne lokacije za najnižjo ceno.
V teh pogojih je lokacija določena ali ne. Ti dve stanji sta: "TRUE - FALSE" ali "1 - 0". Obstaja šest stanj za šest lokacij, na primer 000001 je nastavljen samo na šesto, 111111 je nastavljen na vse.
V binarnem številskem sistemu je natanko 63 različnih možnosti od 000001 (1) do 111111 (63).
L2-L64 naj se zdaj glasi {=MULTIPLE OPERATION (K1)}, to so rezultati vseh alternativnih rešitev. Potem je najmanjša vrednost=Min (L) in ustrezna alternativa je INDEX (K).
CPLEX celoštevilsko programiranje
Včasih linearno razmerje ni dovolj, da bi prišli do bistva poslovnega problema. To še posebej velja, kadar odločitve vključujejo diskretne izbire, na primer, ali odpreti skladišče na določeni lokaciji ali ne. V teh situacijah je treba uporabiti celoštevilsko programiranje.
Če problem vključuje diskretne in neprekinjene izbire, gre za mešani celoštevilski program. Lahko ima linearne, konveksne kvadratne probleme in iste omejitve drugega reda.
Integer programi so veliko bolj zapleteni kot linearni programi, vendar imajo pomembne poslovne aplikacije. Programska opremaProgramska oprema CPLEX uporablja zapletene matematične metode za reševanje celoštevilskih problemov. Njegove metode vključujejo sistematično iskanje možnih kombinacij diskretnih spremenljivk z uporabo linearnih ali kvadratnih programskih sprostitev za izračun mej vrednosti optimalne rešitve.
Za izračun omejitev uporabljajo tudi LP in druge metode reševanja optimizacijskih problemov.
Standard Microsoft Excel Solver
Ta tehnologija uporablja osnovno implementacijo glavne metode Simplex za reševanje problemov LP. Omejen je na 200 spremenljivk. "Premium Solver" uporablja izboljšano primarno simpleksno metodo z dvostranskimi mejami za spremenljivke. Platforma Premium Solver uporablja razširjeno različico LP/Quadratic Simplex Solver za reševanje optimizacijskega problema z do 2000 odločitvenimi spremenljivkami.
Veliki LP za platformo Premium Solver uporablja najsodobnejšo izvedbo preproste in dvojne simpleksne metode, ki uporablja redkost v modelu LP za prihranek časa in spomina, napredne strategije za posodabljanje in matrike preoblikovanja, večkratno in delno določanje cen in rotacije ter za premagovanje degeneracije. Ta motor je na voljo v treh različicah (zmožnost obdelave do 8.000, 32.000 ali neomejenih spremenljivk in omejitev).
MOSEK Solver vključuje primarni in dvojni simpleks, metodo, ki prav tako izkorišča redkost in uporablja napredne strategije za posodabljanje matrik in "refaktorizacijo". Rešuje težave neomejene velikosti, je bilopreizkušeno na težavah z linearnim programiranjem z milijoni spremenljivk odločanja.
Primer po korakih v EXCEL-u
Če želite definirati optimizacijski model problema v Excelu, izvedite naslednje korake:
- Organizirajte podatke za problem v preglednici v logični obliki.
- Izberite celico za shranjevanje vsake spremenljivke.
- V celici ustvarite formulo za izračun ciljnega matematičnega modela optimizacijskega problema.
- Ustvarite formule za izračun leve strani vsake omejitve.
- Uporabite pogovorna okna v Excelu, da Solverju poveste o spremenljivkah odločitve, ciljih, omejitvah in želenih mejah teh parametrov.
- Zaženite "Solver", da poiščete optimalno rešitev.
- Ustvarite Excelov list.
- Organizirajte podatke za problem v Excelu, kjer se izračuna formula za ciljno funkcijo in omejitev.
V zgornji tabeli so celice B4, C4, D4 in E4 rezervirane za predstavljanje spremenljivk odločitve X 1, X 2, X 3 in X 4. Primeri odločitev:
- Model mešanice izdelkov (450 $, 1150 $, 800 $ in 400 $ dobička na izdelek) je bil vnesen v celice B5, C5, D5 oziroma E5. To omogoča, da se cilj izračuna v F5=B5B4 + C5C4 + D5D4 + E5E4 ali F5:=SUMPRODUCT (B5: E5, B4: E4).
- V B8 vnesite količino virov, potrebnih za izdelavo posamezne vrste izdelka.
- Formula za F8:=SUMPRODUCT(B8:E8, $B$4:$E$4).
- Kopiraj toformula v F9. Dolarski znaki v $B$4:$E$4 kažejo, da ta obseg celic ostaja konstanten.
- V G8 vnesite razpoložljivo količino virov vsake vrste, ki ustreza vrednostim omejitev na desni. To vam omogoča, da jih izrazite takole: F11<=G8: G11.
- To je enako štirim omejitvam F8<=G8, F9 <=G9, F10 <=G10 in F11=0
Področja praktične uporabe metode
Linearna optimizacija ima veliko praktičnih aplikacij kot primer optimizacijskega problema:
Podjetje lahko izdela več izdelkov z znano maržo prispevka. Proizvodnja enote vsakega predmeta zahteva znano količino omejenih virov. Naloga je ustvariti proizvodni program, ki bo določil, koliko posameznega izdelka je treba proizvesti, tako da je dobiček podjetja čim večji, ne da bi pri tem kršili omejitve virov.
Težave z mešanjem so rešitev za probleme optimizacije, povezane s kombiniranjem sestavin v končni izdelek. Primer tega je problem prehrane, ki ga je leta 1947 preučil George Danzig. Navedene so številne surovine, kot so oves, svinjina in sončnično olje, skupaj z njihovo hranilno vsebnostjo, kot so beljakovine, maščobe, vitamin A, in njihova cena za kilogram. Izziv je zmešati enega ali več končnih izdelkov iz surovin po najnižji možni ceni ob spoštovanju najnižje in največje omejitve njihove hranilne vrednosti.
Klasična uporaba problema linearne optimizacije je določiti usmerjanje za potrebepromet v telekomunikacijskih ali prometnih omrežjih. Hkrati je treba tokove usmerjati skozi omrežje tako, da so izpolnjene vse prometne zahteve brez kršenja pogojev pasovne širine.
V matematični teoriji se lahko linearna optimizacija uporablja za izračun optimalnih strategij v igrah z ničelno vsoto za dve osebi. V tem primeru se izračuna porazdelitev verjetnosti za vsakega udeleženca, ki je koeficient naključnega mešanja njegovih strategij.
Noben uspešen poslovni proces na svetu ni mogoč brez optimizacije. Na voljo je veliko algoritmov za optimizacijo. Nekatere metode so primerne le za določene vrste težav. Pomembno je, da znate prepoznati njihove značilnosti in izbrati ustrezno metodo rešitve.
