Optimeerimine aitab teil leida parima tulemuse, mis toob kasumit, vähendab kulusid või määrab parameetri, mis põhjustab äriprotsesside tõrkeid.
Seda protsessi nimetatakse ka matemaatiliseks programmeerimiseks. See lahendab optimeerimisülesande juhi seatud eesmärgi saavutamiseks vajalike piiratud ressursside jaotuse määramise probleemi. Kõigist võimalikest valikutest on soovitav leida see, mis maksimeerib (või vähendab) kontrolliparameetrit, näiteks kasumit või kulu. Optimeerimismudeleid nimetatakse ka ettekirjutavateks või normatiivseteks, kuna nende eesmärk on leida ettevõtte jaoks teostatav strateegia.
Arenguajalugu
Lineaarne programmeerimine (LP) töötab optimeerimisprobleemide klassiga, kus kõik piirangud on lineaarsed.
Esitan lühid alt LP arengulugu:
- Aastal 1762 lahendas Lagrange lihtsad optimeerimisülesanded võrdsuse piirangutega.
- 1820. aastal otsustas Gausslineaarne võrrandisüsteem eliminatsiooni abil.
- 1866. aastal täiustas Wilhelm Jordan vähimruutude vigade leidmise meetodit sobivuse kriteeriumina. Seda nimetatakse nüüd Gaussi-Jordani meetodiks.
- Digitaalne arvuti ilmus 1945. aastal.
- Danzig leiutas simpleksmeetodid 1947. aastal.
- 1968. aastal tutvustasid Fiacco ja McCormick Inside Pointi meetodit.
- 1984. aastal rakendas Karmarkar lineaarsete programmide lahendamiseks interjööri meetodit, lisades oma uuendusliku analüüsi.
LP on osutunud äärmiselt võimsaks vahendiks nii reaalmaailma probleemide modelleerimiseks kui ka laialdaselt kasutatava matemaatilise teooriana. Paljud huvitavad optimeerimisprobleemid on aga mittelineaarsed.
Mida sel juhul teha? Selliste probleemide uurimine hõlmab lineaaralgebra, mitme muutujaga arvutuse, arvanalüüsi ja arvutusmeetodite mitmekülgset segu. Teadlased töötavad välja arvutusalgoritme, sealhulgas sisepunktide meetodeid lineaarseks programmeerimiseks, geomeetriaks, kumerate hulkade ja funktsioonide analüüsiks ning spetsiaalselt struktureeritud probleemide uurimiseks, nagu ruutprogrammeerimine.
Mittelineaarne optimeerimine annab põhjapaneva arusaama matemaatilisest analüüsist ja seda kasutatakse laialdaselt erinevates valdkondades, nagu tehnika, regressioonanalüüs, ressursside haldamine, geofüüsikaline uurimine ja majandus.
Optimeerimisprobleemide klassifikatsioon
Oluline sammOptimeerimisprotsess on mudelite klassifitseerimine, kuna nende lahendusalgoritmid on kohandatud konkreetsele tüübile.
1. Probleemid diskreetse ja pideva optimeerimisega. Mõned mudelid on mõttekad ainult siis, kui muutujad võtavad väärtused täisarvude diskreetsest alamhulgast. Teised sisaldavad andmeid, mis võivad omandada mis tahes tegeliku väärtuse. Tavaliselt on neid lihtsam lahendada. Algoritmide täiustused koos arvutitehnoloogia edusammudega on järsult suurendanud lineaarse programmeerimise optimeerimise probleemi suurust ja keerukust.
2. Piiramatu ja piiratud optimeerimine. Teine oluline erinevus on ülesanded, kus muutujatele ei ole piiranguid. See võib ulatuda paljudest lihtsatest hinnangutest kuni võrdsuse ja ebavõrdsuse süsteemideni, mis modelleerivad keerulisi andmete vahelisi seoseid. Selliseid optimeerimisülesandeid saab täiendav alt liigitada funktsioonide olemuse järgi (lineaarne ja mittelineaarne, kumer ja sile, diferentseeruv ja mittediferentseeruv).
3. Teostatavusülesanded. Nende eesmärk on leida muutuvaid väärtusi, mis vastavad mudeli piirangutele ilma konkreetse optimeerimiseesmärgita.
4. Komplementaarsuse ülesanded. Neid kasutatakse laialdaselt tehnoloogias ja majanduses. Eesmärk on leida lahendus, mis vastab komplementaarsuse tingimustele. Praktikas sõnastatakse mitme eesmärgiga ülesanded sageli ümber ühe eesmärgiga ülesanneteks.
5. Deterministlik versus stohhastiline optimeerimine. Deterministlik optimeerimine eeldab, et andmedülesanded on täiesti täpsed. Paljude päevakajaliste küsimuste puhul ei saa need aga mitmel põhjusel teada.
Esimene on seotud lihtsa mõõtmisveaga. Teine põhjus on põhimõttelisem. See seisneb selles, et mõned andmed esindavad teavet tuleviku kohta, näiteks nõudlust toote järele või hinda tulevase perioodi kohta. Stohhastilise optimeerimise tingimustes optimeerimisel kaasatakse mudelisse määramatus.
Põhikomponendid
Eesmärgifunktsioon on see, mida tuleb minimeerida või maksimeerida. Enamikul optimeerimisprobleemide tüüpidel on üks eesmärkfunktsioon. Kui ei, siis saab need sageli ümber sõnastada, et need töötaksid.
Kaks erandit sellest reeglist:
1. Sihtotsingu ülesanne. Enamikus ärirakendustes soovib juht saavutada konkreetse eesmärgi, täites samal ajal mudeli piiranguid. Kasutaja ei taha eriti midagi optimeerida, seega pole mõtet sihtfunktsiooni defineerida. Seda tüüpi nimetatakse tavaliselt rahuldamisprobleemiks.
2. Palju objektiivseid jooni. Sageli soovib kasutaja optimeerida mitut erinevat eesmärki korraga. Tavaliselt on need kokkusobimatud. Muutujad, mis optimeerivad ühe eesmärgi jaoks, ei pruugi olla teiste jaoks parimad.
Komponentide tüübid:
- Juhitud sisend on otsustusmuutujate kogum, mis mõjutab sihtfunktsiooni väärtust. Tootmisülesandes võivad muutujad hõlmata erinevate saadaolevate ressursside või selleks vajaliku tööjõu jaotustiga toiming.
- Piirangud on seosed otsustusmuutujate ja parameetrite vahel. Tootmisprobleemi korral ei ole mõttekas kulutada palju aega ühelegi tegevusele, seega piira kõiki "ajutisi" muutujaid.
- Võimalikud ja optimaalsed lahendused. Muutujate otsuse väärtust, mille puhul on täidetud kõik piirangud, nimetatakse rahuldatavaks. Enamik algoritme leiab selle esm alt üles, seejärel proovib seda parandada. Lõpuks muudavad nad muutujaid, et liikuda ühelt võimalikult lahenduselt teisele. Seda protsessi korratakse, kuni eesmärgifunktsioon saavutab maksimumi või miinimumi. Seda tulemust nimetatakse optimaalseks lahenduseks.
Järgmiste matemaatiliste programmide jaoks välja töötatud optimeerimisülesannete algoritme kasutatakse laialdaselt:
- Kumer.
- Separable.
- Kvadraat.
- Geomeetriline.
Google Linear Solvers
Lineaarne optimeerimine või programmeerimine on probleemi optimaalse lahendamise arvutusprotsessi nimi. See on modelleeritud lineaarsete seoste kogumina, mis tekivad paljudes teadus- ja inseneriteadustes.
Google pakub lineaarse optimeerimise probleemide lahendamiseks kolme võimalust:
- Avatud lähtekoodiga kogu.
- Google'i arvutustabelite lineaarse optimeerimise lisandmoodul.
- Lineaarne optimeerimisteenus Google Apps Scriptis.
Glop on Google'isse sisse ehitatudlineaarne lahendaja. See on saadaval avatud lähtekoodiga. Glopile pääsete juurde OR-Toolsi lineaarse lahendaja ümbrise kaudu, mis on Glopi ümbris.
Google'i arvutustabelite lineaarne optimeerimismoodul võimaldab teil esitada optimeerimisprobleemi lineaarse avalduse, sisestades andmed arvutustabelisse.
Kvadraatprogrammeerimine
Premium Solveri platvorm kasutab Simplex-meetodi laiendatud LP/Quadratic versiooni koos LP ja QP probleemide töötlemise piirangutega kuni 2000 otsustusmuutujaga.
SQP Lahendaja suuremahuliste ülesannete jaoks kasutab hõredusega aktiivse hulga meetodi kaasaegset teostust, et lahendada ruutprogrammeerimise (QP) probleeme. XPRESS Solver mootor kasutab QP probleemide lahendamiseks "Interior Point" või Newtoni barjääri meetodi loomulikku laiendust.
MOSEK Solver rakendab manustatud "Inside Point" ja automaatse duaali meetodeid. See on eriti tõhus lõdv alt seotud QP probleemide korral. See võib lahendada ka skaala ruutpiirangu (QCP) ja teise järgu koonuse programmeerimise (SOCP) probleeme.
Mitme toiminguga arvutused
Neid kasutatakse üsna eduk alt Microsoft Office'i funktsioonide kasutamisel, näiteks optimeerimisprobleemide lahendamisel Excelis.
Ül altoodud tabelis on sümbolid järgmised:
- K1 – K6 – kliendid, kes peavad kaupa pakkuma.
- S1 – S6 on potentsiaalsed tootmiskohad, mida võiks selleks ehitada. Saab luua1, 2, 3, 4, 5 või kõik 6 asukohta.
Iga veerus I (Parandus) loetletud rajatise kohta kehtivad püsikulud.
Kui asukoht midagi ei muuda, ei lähe see arvesse. Siis ei kaasne püsikulusid.
Tuvastage potentsiaalsed asukohad, et saada madalaim hind.
Nendel tingimustel on asukoht kas kindlaks määratud või mitte. Need kaks olekut on: "TRUE - FALSE" või "1 - 0". Kuue asukoha jaoks on kuus olekut, näiteks 000001 on seatud ainult kuuendaks, 111111 on kõik.
Kahendarvusüsteemis on täpselt 63 erinevat valikut vahemikus 000001 (1) kuni 111111 (63).
L2-L64 peaks nüüd olema kirjas {=MULTIPLE OPERATION (K1)}, need on kõigi alternatiivsete lahenduste tulemused. Siis on minimaalne väärtus=Min (L) ja vastav alternatiiv on INDEX (K).
CPLEX täisarvuline programmeerimine
Mõnikord ei piisa lineaarsest suhtest, et jõuda äriprobleemi tuumani. See kehtib eriti siis, kui otsused hõlmavad diskreetseid valikuid, näiteks kas avada teatud kohas ladu või mitte. Sellistes olukordades tuleb kasutada täisarvulist programmeerimist.
Kui probleem hõlmab nii diskreetseid kui ka pidevaid valikuid, on tegemist segatäisarvu programmiga. Sellel võivad olla lineaarsed, kumerad ruutprobleemid ja samad teist järku piirangud.
Täisarvulised programmid on palju keerukamad kui lineaarsed programmid, kuid neil on olulised ärirakendused. TarkvaraCPLEX-tarkvara kasutab täisarvuülesannete lahendamiseks keerulisi matemaatilisi meetodeid. Tema meetodid hõlmavad diskreetsete muutujate võimalike kombinatsioonide süstemaatilist otsimist, kasutades lineaarseid või ruutkeskseid tarkvararelaksatsioone, et arvutada optimaalse lahenduse väärtuse piirid.
Nad kasutavad piirangute arvutamiseks ka LP-d ja muid optimeerimisprobleemide lahendamise meetodeid.
Standardne Microsoft Exceli lahendaja
See tehnoloogia kasutab LP-probleemide lahendamiseks Simplexi põhimeetodi põhirakendust. See on piiratud 200 muutujaga. "Premium Solver" kasutab täiustatud esmast simpleksmeetodit muutujate kahepoolsete piiridega. Premium Solveri platvorm kasutab kuni 2000 otsustusmuutujaga optimeerimisprobleemi lahendamiseks LP/Quadratic Simplex Solveri laiendatud versiooni.
Suuremahuline LP Premium Solveri platvormi jaoks rakendab lihtsa ja topeltsimpleksmeetodi tipptasemel teostust, mis kasutab LP-mudelis hõredust, et säästa aega ja mälu, täiustatud strateegiaid värskendamiseks ja refaktori maatriksid, mitmekordne ja osaline hinnakujundus ja rotatsioonid ning degeneratsiooni ületamiseks. See mootor on saadaval kolmes versioonis (suudab käsitleda kuni 8000, 32 000 või piiramatut muutujat ja piirangut).
MOSEK Solver sisaldab primaarset ja duaalset simpleksi meetodit, mis kasutab ära ka hõredust ja kasutab maatriksi värskendamiseks ja "refaktoriseerimiseks" täiustatud strateegiaid. See lahendab piiramatu suurusega probleeme, olitestitud miljonite otsustusmuutujatega lineaarse programmeerimise probleemidega.
Samm-sammuline näide EXCELis
Optimeerimisprobleemi mudeli määratlemiseks Excelis tehke järgmised toimingud:
- Korraldage ülesande andmed arvutustabelis loogilises vormis.
- Valige iga muutuja salvestamiseks lahter.
- Looge lahtrisse valem optimeerimisülesande sihtmärgi matemaatilise mudeli arvutamiseks.
- Looge valemid, et arvutada iga piirangu vasak pool.
- Kasutage Exceli dialooge, et anda Solverile teada nende parameetrite otsustusmuutujatest, sihtmärkidest, piirangutest ja soovitud piiridest.
- Optimaalse lahenduse leidmiseks käivitage "Solver".
- Looge Exceli leht.
- Korraldage ülesande andmed Excelis, kus arvutatakse eesmärgifunktsiooni ja piirangu valem.
Ül altoodud tabelis on lahtrid B4, C4, D4 ja E4 reserveeritud, et esindada otsustusmuutujaid X 1, X 2, X 3 ja X 4. Otsuste näited:
- Tootevaliku mudel (450 $, 1150 $, 800 $ ja 400 $ kasum toote kohta) sisestati vastav alt lahtritesse B5, C5, D5 ja E5. See võimaldab sihtmärgi arvutada kujul F5=B5B4 + C5C4 + D5D4 + E5E4 või F5:=SUMPRODUCT (B5: E5, B4: E4).
- B8 sisestage iga tootetüübi valmistamiseks vajalike ressursside hulk.
- Valem for F8:=SUMPRODUCT(B8:E8, $B$4:$E$4).
- Kopeerige seevalem F9-s. Dollarimärgid $B$4:$E$4 näitavad, et see lahtrivahemik jääb muutumatuks.
- G8-s sisestage iga tüübi saadaolev ressursside hulk, mis vastab paremal asuvate piirangute väärtustele. See võimaldab teil neid väljendada järgmiselt: F11<=G8: G11.
- See võrdub nelja piiranguga F8<=G8, F9 <=G9, F10 <=G10 ja F11=0
Meetodi praktilise rakendusvaldkonnad
Lineaarsel optimeerimisel on optimeerimisprobleemi näitena palju praktilisi rakendusi:
Ettevõte võib toota mitut toodet teadaoleva panusemarginaaliga. Iga kauba ühiku tootmine nõuab teadaolev alt piiratud ressursse. Ülesandeks on luua tootmisprogramm, et määrata kindlaks, kui palju igast tootest tuleks toota, et ettevõtte kasum oleks maksimaalne ilma ressursipiiranguid rikkumata.
Segamisprobleemid on lahendus optimeerimisprobleemidele, mis on seotud koostisainete kombineerimisega lõpptooteks. Selle näiteks on George Danzigi 1947. aastal uuritud toitumisprobleem. Antakse mitmeid tooraineid, nagu kaer, sealiha ja päevalilleõli, koos nende toiteväärtusega, nagu valk, rasv, A-vitamiin, ja nende kilogrammi hind. Väljakutseks on ühe või mitme lõpptoote segamine toorainest madalaima võimaliku kuluga, järgides samal ajal nende toiteväärtuse miinimum- ja maksimumpiiranguid.
Lineaarse optimeerimise probleemi klassikaline rakendus on marsruutimise määramine vastav alt vajadusteleliiklust telekommunikatsiooni- või transpordivõrkudes. Samal ajal tuleb vood läbi võrgu suunata nii, et kõik liiklusnõuded oleksid täidetud ilma ribalaiuse tingimusi rikkumata.
Matemaatika teoorias saab lineaarset optimeerimist kasutada optimaalsete strateegiate arvutamiseks nullsummamängudes kahele inimesele. Sel juhul arvutatakse iga osaleja tõenäosusjaotus, mis on tema strateegiate juhusliku segunemise koefitsient.
Ükski edukas äriprotsess maailmas pole võimalik ilma optimeerimiseta. Saadaval on palju optimeerimisalgoritme. Mõned meetodid sobivad ainult teatud tüüpi probleemide jaoks. Oluline on osata ära tunda nende omadused ja valida sobiv lahendusmeetod.
