Optimizacijski problemi: koncept, metode reševanja in klasifikacija

Optimizacija pomaga najti najboljši rezultat, ki prinaša dobiček, zmanjšuje stroške ali določa parameter, ki povzroča napake v poslovnem procesu.

Ta postopek se imenuje tudi matematično programiranje. Rešuje problem določanja razporeditve omejenih virov, potrebnih za dosego cilja, ki ga je določil vodja optimizacijskega problema. Med vsemi dopustnimi različicami je zaželeno najti tisto, ki maksimizira (ali minimizira) kontrolni parameter, npr. dobiček ali stroške. Optimizacijski modeli se imenujejo tudi normativni ali preskriptivni, ker skušajo najti možno strategijo za podjetje.

Zgodovina razvoja

Linearno programiranje (LP) se ukvarja z razredom optimizacijskih problemov, kjer so vse omejitve linearne.

Predstavlja kratko zgodovino razvoja sistema LP:

• Lagrange je leta 1762 reševal preproste optimizacijske probleme z omejitvami enakosti.
• Leta 1820 je Gauss rešil linearni sistem enačb z eliminacijo.
• Leta 1866 je Wilhelm Jordan izboljšal metodo najmanjših kvadratov za ugotavljanje napak kot merila ustreznosti. Zdaj se imenuje Gauss-Jordanija .
• Leta 1945 se je pojavil digitalni računalnik.
• Leta 1947 je Danzig izumil simpleksne metode.
• Leta 1968 sta Fiacco in McCormick predstavila metodo notranjih točk.
• Leta 1984 je Carmarkar uporabil notranjo metodo za reševanje linearnih programov in dodal svojo inovativno analizo.

LP se je izkazal za izredno močno orodje, tako za modeliranje problemov iz resničnega sveta kot tudi za široko uporabno matematično teorijo. Vendar je veliko zanimivih optimizacijskih problemov nelinearnih.

Kaj storiti v tem primeru?? Študij takšnih problemov vključuje raznoliko mešanico linearne algebre, multivariatnega računa, numerične analize in računalniških metod. Raziskovalci se ukvarjajo z razvojem računalniških algoritmov, vključno z metodami notranjih točk za linearno programiranje, geometrijo, analizo konveksnih množic in funkcij ter študijem posebej strukturiranih problemov, kot je kvadratno programiranje.

Nelinearna optimizacija omogoča temeljno razumevanje matematične analize in se pogosto uporablja na različnih področjih, kot so inženirstvo, regresijska analiza, nadzor zalog, geofizikalne raziskave in ekonomija.

Razvrstitev nalog optimizacije

Pomemben korak v postopku optimizacije je razvrščanje modelov, saj so njihovi algoritmi za reševanje prilagojeni določeni vrsti.

1. Naloge diskretne in zvezne optimizacije. Nekateri modeli so smiselni le, če imajo spremenljivke vrednosti iz diskretne podmnožice celih števil. Drugi vsebujejo podatke, ki lahko pridobijo pravo vrednost. običajno jih je lažje rešiti. Izboljšave algoritmov so skupaj z napredkom v računalništvu močno povečale velikost in zapletenost problema optimizacije linearno programiranje.

2. Neomejena in omejena optimizacija. Druga pomembna razlika je, da gre za probleme, pri katerih ni omejitev za spremenljivke. Lahko se gibljejo od preprostih ocen do sistemov enačb in neenačb, ki modelirajo zapletene odnose med podatki. Takšne optimizacijske probleme lahko nadalje razvrstimo glede na naravo funkcij (linearne in nelinearne, konveksne in gladke, diferencirane in nediferencirane).

3. Težave z izvedljivostjo. Njihov cilj je najti vrednosti spremenljivk, ki izpolnjujejo omejitve modela brez posebnega cilja optimizacije.

4. Problemi komplementarnosti. Razširjeni so v inženirstvu in ekonomiji. Cilj je najti rešitev, ki izpolnjuje pogoj dodatnosti. V praksi se cilji z več kot enim ciljem pogosto preoblikujejo v en sam cilj.

5. Deterministična in stohastična optimizacija. Pri deterministični optimizaciji se predpostavlja, da so podatki za problem popolnoma natančni. Vendar jih za mnoga pomembna vprašanja ni mogoče poznati iz več razlogov.

Prva je posledica preproste napake pri merjenju. Drugi razlog je bolj temeljnega pomena. Drugi razlog je, da nekateri podatki predstavljajo informacije o prihodnosti, npr. povpraševanje po izdelku ali cena za prihodnje obdobje. Pri stohastični optimizaciji je negotovost vključena v model.

Glavni sestavni deli

Ciljna funkcija je funkcija, ki jo je treba zmanjšati ali povečati. Večina vrst optimizacijskih problemov ima eno ciljno funkcijo. Če ne, jih je pogosto mogoče preoblikovati tako, da delujejo.

Pri tem pravilu obstajata dve izjemi:

1. Problem iskanja cilja. V večini poslovnih aplikacij želi vodja doseči določen cilj, pri tem pa upoštevati omejitve modela. Uporabnik ne želi optimizirati ničesar, zato nima smisla določati ciljne funkcije. Ta vrsta Običajno se imenuje problem izvedljivosti.

2. Nabor ciljnih funkcij. Pogosto želi uporabnik optimizirati več različnih ciljev hkrati. Običajno so nezdružljivi. Spremenljivke, ki optimizirajo en sam cilj, so lahko daleč od najboljše za drugih.

Vrste komponent:

• Nadzorovani vhodi so niz spremenljivk odločanja, ki vplivajo na vrednost ciljne funkcije. Pri proizvodnem problemu lahko spremenljivke vključujejo dodelitev različnih razpoložljivih virov ali delo, ki je potrebno za vsako dejanje.
• Omejitve so razmerja med spremenljivkami odločanja in parametri. Pri proizvodnem problemu ni smiselno porabiti veliko časa za katero koli dejavnost, zato omejite vse "časovne" spremenljivke.
• Možne in optimalne rešitve. Vrednost rešitve za spremenljivke, v katerem so izpolnjene vse omejitve, se imenuje izvedljiva. Večina algoritmov ga najprej najde, nato ga poskuša izboljšati. Na koncu spremenijo spremenljivke, da preidejo od ene izvedljive rešitve k drugi. Ta postopek se ponavlja, dokler ciljna funkcija ne doseže svojega maksimuma ali minimuma. Ta rezultat se imenuje optimalna rešitev.

Algoritmi za optimizacijo, razviti za naslednje matematične programe, se pogosto uporabljajo:

• Konveksni.
• Ločljivo.
• Kvadratični.
• Geometrijski.

Googlovi linearni reševalniki

Linearna optimizacija ali programiranje je ime za računalniški postopek optimalnega reševanja problema. Modelira se kot niz linearnih razmerij, ki se pojavljajo v številnih znanstvenih in inženirskih disciplinah.

Google ponuja tri metode rešitve linearnih problemov optimizacije:

• Odprtokodna knjižnica Glop.
• Dodatek za linearno optimizacijo za Google Sheets.
• Storitev linearne optimizacije v Google Apps Script.

Glop je Googlov vgrajeni linearni reševalnik. Na voljo je kot odprta koda. Do programa Glop lahko dostopate prek pakirnika OR-Tools za linearno reševanje, ki je lupina za program Glop.

Modul za linearno optimizacijo za Google Sheets vam omogoča izvedbo problema linearne optimizacije z vnosom podatkov v preglednico.

Kvadratično programiranje

Premium Solver uporablja razširjeno različico metode Simplex z omejitvami obdelave problemov LP in QP do 2000 spremenljivih rešitev.

SQP Solver za obsežne probleme uporablja sodobno implementacijo metode redkih aktivnih množic za reševanje problemov kvadratnega programiranja (QP). Mehanizem XPRESS Solver uporablja naravno razširitev "Notranja točka" ali Newton-Barrier za metoda reševanja problemov QP.

MOSEK Solver uporablja metode implementiranih "notranja točka" in samostojni. To je še posebej učinkovito pri šibko povezanih problemih QP. Reši lahko tudi probleme skaliranja kvadratne omejitve (QCP) in stožčastega programiranja drugega reda (SOCP).

Večoperacijski izračuni

Dokaj uspešno uporabljajo funkcije paketa Microsoft Office, npr. reševanje optimizacijskih problemov v programu Excel.

V zgornji tabeli so takšni zapisi:

• K1 - K6 - stranke, ki morajo zagotoviti blago.
• S1 - S6 so potencialne proizvodne lokacije, ki jih je mogoče zgraditi za ta namen. Na voljo je lahko 1,2,3,4,5 ali vseh 6 lokacij.

Vsaka postavka ima fiksne stroške, ki so prikazani v stolpcu I (Fix).

Če se lokacija ne spremeni, se ne upošteva. Potem ni fiksnih stroškov.

Določite potencialne lokacije za doseganje najnižjih stroškov.

V teh pogojih je lokacija nastavljena ali ne. Ti dve državi sta: "TRUE - FALSE" ali "1 - 0". Za šest lokacij obstaja šest stanj, na primer za 000001 je samo šestica, za 111111 so vse.

V binarnem zapisu obstaja natanko 63 različnih različic od 000001 (1) do 111111 (63).

L2-L64 mora biti zdaj {= MNOŽIČNA OPERACIJA (K1)}, to so rezultati vseh možnosti. Potem je najmanjša vrednost = Min (L), ustrezna alternativa pa je INDEX (K).

CPLEX Celoštevilsko programiranje

Včasih linearna razmerja ne zadostujejo, da bi zajeli bistvo poslovnega problema. To še posebej velja za odločitve, ki vključujejo diskretne izbire, na primer, ali odpreti skladišče na določeni lokaciji ali ne. V teh primerih je treba uporabiti celoštevilsko programiranje.

Če težava vključuje sam kot diskretne in zvezne izbire, je mešani celoštevilski program. Lahko gre za linearne, konveksne in kvadratne probleme ter enake omejitve drugega reda.

Celoštevilski programi so veliko bolj zapleteni od linearnih, vendar imajo pomembno poslovno uporabo. Programska 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 linearnega ali kvadratnega programiranja za izračun mejnih vrednosti optimalne rešitve.

Za izračun omejitev uporabljajo tudi LP in druge metode reševanja optimizacijskih problemov.

Standardni reševalnik programa Microsoft Excel

Ta tehnika uporablja osnovno implementacijo osnovne simpleksne metode za reševanje problemov LP. Omejen je na 200 spremenljivk. "Premium Solver" Uporablja izboljšano primarno simpleksno metodo z obojestranskimi mejami za spremenljivke. Platforma Premium Solver uporablja razširjeno različico rešitve LP/Quadratic Simplex Solver za reševanje optimizacijskega problema z do 2 000 spremenljivkami odločanja.

Velik obseg LP za platformo Premium Solver uporablja najsodobnejšo implementacijo enostavne in dvojne simpleksne metode, ki uporablja redkost v modelu LP za prihranek časa in pomnilnika, napredne strategije za posodobitve in preoblikovanje matrik, večkratno in delno določanje cen in rotacije ter za premagovanje degeneracije. Ta motor je na voljo v treh različicah (z možnostjo obdelave do 8.000, 32.000 ali neomejenih spremenljivk in omejitev).

Reševalnik MOSEK vključuje primarno in dvojno simpleksno metodo, ki prav tako izkorišča redkost in uporablja napredne strategije za posodabljanje matrik in "refaktorizacijo". Rešuje težave neomejene velikosti, preizkušen je bil na problemi linearnega programiranja z milijoni spremenljivk odločanja.

Primer po korakih v programu EXCEL

Za opredelitev problema optimizacije modela v programu Excel so izvedeni naslednji koraki:

• uredite podatke za problem v preglednici v v logični obliki.
• Izberite celico za shranjevanje vsaka spremenljivka.
• V celici ustvarite formulo za izračun ciljnega matematičnega modela problema optimizacije.
• Ustvarite formule za izračun leve strani vsake omejitve.
• Uporaba pogovornih oken v Excelu za komuniciranje "Rešite" o spremenljivkah odločanja, ciljih, omejitvah in želenih mejah teh parametrov.
• Spustite "Rešitelj", poiskati najboljšo rešitev.
• Ustvarite Excelov list.
• Uredite podatke za problem v Excelu, kjer se izračunata formula za ciljno funkcijo in omejitev.

V zgornji preglednici so celice B4, C4, D4 in E4 rezervirane za spremenljivke sprejemanje odločitev X 1, X 2, X 3 in X 4. Primeri odločitev:

• Model obsega izdelkov (dobički za vsako vrsto izdelka so 450 USD, 1150 USD, 800 USD in 400 USD) je bil vnesen v celice B5, C5, D5 in E5. To izračuna cilj v F5 = B5 * B4 + C5 * C4 + D5 * D4 + E5 * E4 ali F5: = SUMPRODUCT (B5: E5, B4: E4).
• V polje B8 vnesite število virov, potrebno za proizvodnja vsake vrste izdelka.
• Formula za F8: = SUMPRODUCT (B8: E8, $ B$4: $ E$4).
• Kopirajte to formulo v F9. Znaki dolarja v B$4: E$4 pomenijo, da ta obseg celic ostaja konstanten.
• V polje G8 vnesite razpoložljivo količino vsake vrste vira, ki ustreza omejitvenim vrednostim na desni strani. To jih izraža na naslednji način: F11<= G8: G11.
• To je enakovredno štirim omejitvam F8<= G8, F9 <= G9, F10 <= G10 in F11 <= G11. Ta niz lahko vnesete neposredno v pogovorna okna Solverja skupaj s pogoji nenegativnosti B4: E4> = 0

Področja praktične uporabe metode

Linearna optimizacija se kot primer optimizacijskega problema velikokrat uporablja v praksi:

Podjetje lahko proizvaja več izdelkov z znano stopnjo prispevka. Proizvodnja enote vsakega izdelka zahteva znano količino končnih virov. Naloga je izdelati proizvodni program, ki bo določil, koliko posameznega izdelka je treba proizvesti tako, da bo dobiček podjetja čim večji, ne da bi pri tem kršili omejitve virov.

Problemi mešanja so optimizacijski problemi, povezani z združevanjem sestavin v končni izdelek. Primer tega je problem prehrane, ki ga je leta 1947 preučeval George Danzig. Navedena je vrsta surovin, npr. oves, svinjina in sončnično olje, in njihova vsebnost hranil, npr. beljakovin, maščob, vitamina A, ter njihova cena na kilogram. Cilj je zmešati enega ali več končnih izdelkov iz surovin po najnižjih možnih stroških, ob upoštevanju najmanjša in največja vrednost omejitve zaradi njihove hranilne vrednosti.

Klasična uporaba linearnega optimizacijskega problema je določanje zahtev za usmerjanje prometa v telekomunikacijskih ali transportnih omrežjih. Tokove je treba usmerjati po omrežju tako, da so izpolnjene vse prometne zahteve, ne da bi bile ogrožene.

V okviru matematične teorije lahko z linearno optimizacijo izračunamo optimalne strategije v igrah z ničelno vsoto za dve osebi. S tem se izračuna porazdelitev verjetnosti za vsakega udeleženca, ki je koeficient naključnega mešanja njihovih strategij.

Noben uspešen poslovni proces na svetu ni mogoč brez optimizacije. Na voljo je veliko optimizacijskih algoritmov. Nekatere metode so primerne le za določene vrste problemov. Pomembno je, da znamo prepoznati njihove značilnosti in izbrati ustrezno metodo reševanja.