Optimizācija palīdz atrast labāko rezultātu, kas nes peļņu, samazina izmaksas vai nosaka parametru, kas izraisa biznesa procesa kļūmes.
Šo procesu sauc arī par matemātisko programmēšanu. Tas atrisina optimizācijas problēmas vadītāja izvirzītā mērķa sasniegšanai nepieciešamo ierobežoto resursu sadalījuma noteikšanas problēmu. No visām iespējamām iespējām vēlams atrast to, kas maksimāli palielina (vai samazina) kontrolējošo parametru, piemēram, peļņu vai izmaksas. Optimizācijas modeļus sauc arī par preskriptīviem vai normatīviem, jo tie cenšas atrast biznesam īstenojamu stratēģiju.
Attīstības vēsture
Lineārā programmēšana (LP) darbojas ar optimizācijas problēmu klasi, kur visi ierobežojumi ir lineāri.
Iepazīstam īsu LP attīstības vēsturi:
- 1762. gadā Lagranžs atrisināja vienkāršas optimizācijas problēmas ar vienlīdzības ierobežojumiem.
- 1820. gadā Gauss nolēmalineāra vienādojumu sistēma, izmantojot elimināciju.
- 1866. gadā Vilhelms Džordans pilnveidoja mazāko kvadrātu kļūdu atrašanas metodi kā piemērotu kritēriju. Tagad to sauc par Gausa-Jordaņa metodi.
- Ciparu dators parādījās 1945. gadā.
- Danciga 1947. gadā izgudroja vienkāršās metodes.
- 1968. gadā Fiacco un McCormick ieviesa Inside Point metodi.
- 1984. gadā Karmarkars izmantoja interjera metodi, lai atrisinātu lineāras programmas, pievienojot savu novatorisko analīzi.
LP ir izrādījies ārkārtīgi spēcīgs instruments gan reālu problēmu modelēšanai, gan kā plaši pielietota matemātiskā teorija. Tomēr daudzas interesantas optimizācijas problēmas ir nelineāras.
Ko darīt šajā gadījumā? Šādu problēmu izpēte ietver dažādu lineārās algebras, daudzfaktoru aprēķinu, skaitliskās analīzes un skaitļošanas metožu sajaukumu. Zinātnieki izstrādā skaitļošanas algoritmus, tostarp iekšējo punktu metodes lineārajai programmēšanai, ģeometrijai, izliektu kopu un funkciju analīzei un īpaši strukturētu problēmu, piemēram, kvadrātiskās programmēšanas, izpētei.
Nelineārā optimizācija sniedz fundamentālu izpratni par matemātisko analīzi, un to plaši izmanto dažādās jomās, piemēram, inženierzinātnēs, regresijas analīzē, resursu pārvaldībā, ģeofizikālajā izpētē un ekonomikā.
Optimizācijas problēmu klasifikācija
Svarīgs solisOptimizācijas process ir modeļu klasifikācija, jo to risināšanas algoritmi ir pielāgoti noteiktam tipam.
1. Problēmas ar diskrētu un nepārtrauktu optimizāciju. Dažiem modeļiem ir jēga tikai tad, ja mainīgie ņem vērtības no diskrētas veselu skaitļu apakškopas. Citi satur datus, kas var iegūt jebkādu reālu vērtību. Tos parasti ir vieglāk atrisināt. Algoritmu uzlabojumi apvienojumā ar datortehnoloģiju attīstību ir ievērojami palielinājuši lineārās programmēšanas optimizācijas problēmas apjomu un sarežģītību.
2. Neierobežota un ierobežota optimizācija. Vēl viena svarīga atšķirība ir uzdevumi, kuros mainīgajiem lielumiem nav ierobežojumu. Tas var būt plašs, sākot no vienkāršiem aprēķiniem līdz vienādību un nevienlīdzību sistēmām, kas modelē sarežģītas attiecības starp datiem. Šādas optimizācijas problēmas var sīkāk klasificēt pēc funkciju būtības (lineāras un nelineāras, izliektas un gludas, diferencējamas un nediferencējamas).
3. Priekšizpētes uzdevumi. Viņu mērķis ir atrast mainīgas vērtības, kas atbilst modeļa ierobežojumiem bez īpaša optimizācijas mērķa.
4. Komplementaritātes uzdevumi. Tos plaši izmanto tehnoloģijā un ekonomikā. Mērķis ir atrast risinājumu, kas atbilst komplementaritātes nosacījumiem. Praksē uzdevumi ar vairākiem mērķiem bieži tiek pārformulēti par vienu mērķi.
5. Deterministiskā un stohastiskā optimizācija. Deterministiskā optimizācija pieņem, ka dati paruzdevumi ir pilnīgi precīzi. Tomēr daudzos aktuālos jautājumos tos nevar zināt vairāku iemeslu dēļ.
Pirmais ir saistīts ar vienkāršu mērījumu kļūdu. Otrs iemesls ir daudz būtiskāks. Tas ir saistīts ar faktu, ka daži dati atspoguļo informāciju par nākotni, piemēram, preces pieprasījumu vai cenu nākotnē. Veicot optimizāciju stohastiskās optimizācijas apstākļos, modelī ir iekļauta nenoteiktība.
Galvenās sastāvdaļas
Mērķa funkcija ir tā, kas jāsamazina vai jāpalielina. Lielākajai daļai optimizācijas problēmu veidu ir viena mērķa funkcija. Ja nē, tos bieži var pārformulēt, lai tie darbotos.
Divi izņēmumi šim noteikumam:
1. Mērķa meklēšanas uzdevums. Lielākajā daļā biznesa lietojumprogrammu vadītājs vēlas sasniegt konkrētu mērķi, vienlaikus izpildot modeļa ierobežojumus. Lietotājs īpaši nevēlas kaut ko optimizēt, tāpēc nav jēgas definēt mērķa funkciju. Šo veidu parasti dēvē par apmierinātības problēmu.
2. Daudz objektīvu iezīmju. Bieži vien lietotājs vēlas vienlaikus optimizēt vairākus dažādus mērķus. Tie parasti ir nesaderīgi. Mainīgie, kas optimizē vienam mērķim, var nebūt piemērotākie citiem.
Komponentu veidi:
- Kontrolēta ievade ir lēmumu mainīgo kopa, kas ietekmē mērķa funkcijas vērtību. Ražošanas uzdevumā mainīgie var ietvert dažādu pieejamo resursu vai tam nepieciešamā darbaspēka sadalījumukatra darbība.
- Ierobežojumi ir attiecības starp lēmumu mainīgajiem un parametriem. Ražošanas problēmas gadījumā nav jēgas tērēt daudz laika nevienai darbībai, tāpēc ierobežojiet visus "pagaidu" mainīgos.
- Iespējami un optimāli risinājumi. Mainīgo lielumu lēmuma vērtību, saskaņā ar kuru ir izpildīti visi ierobežojumi, sauc par apmierinošu. Lielākā daļa algoritmu vispirms to atrod, pēc tam mēģina to uzlabot. Visbeidzot, viņi maina mainīgos, lai pārietu no viena iespējama risinājuma uz citu. Šo procesu atkārto, līdz mērķa funkcija sasniedz maksimumu vai minimumu. Šo rezultātu sauc par optimālo risinājumu.
Plaši tiek izmantoti optimizācijas uzdevumu algoritmi, kas izstrādāti šādām matemātiskām programmām:
- Izliekta.
- Atdalāms.
- Kvadrātiskais.
- Ģeometriski.
Google lineārie risinātāji
Lineārā optimizācija vai programmēšana ir skaitļošanas procesa nosaukums, lai optimāli atrisinātu problēmu. Tas ir modelēts kā lineāru attiecību kopums, kas rodas daudzās zinātnes un inženierzinātņu disciplīnās.
Google piedāvā trīs veidus, kā atrisināt lineārās optimizācijas problēmas:
- Apmetiet atvērtā pirmkoda bibliotēku.
- Lineārās optimizācijas papildinājums pakalpojumam Google izklājlapas.
- Lineārā optimizācijas pakalpojums Google Apps skriptā.
Glop ir iebūvēts Googlelineārais risinātājs. Tas ir pieejams atvērtā avotā. Varat piekļūt Glop, izmantojot OR-Tools lineāro risinātāju iesaiņojumu, kas ir Glop iesaiņojums.
Google izklājlapu lineārās optimizācijas modulis ļauj veikt optimizācijas problēmas lineāru izklāstu, ievadot datus izklājlapā.
Kvadrātiskā programmēšana
Premium Solver platforma izmanto Simplex metodes paplašināto LP/Quadratic versiju ar LP un QP problēmu apstrādes ierobežojumiem līdz 2000 lēmumu mainīgajiem.
SQP Solver liela mēroga problēmām izmanto modernu aktīvās kopas metodes ieviešanu ar retumu, lai atrisinātu kvadrātiskās programmēšanas (QP) problēmas. XPRESS Solver dzinējs izmanto dabisku "Interior Point" vai Ņūtona barjeras metodes paplašinājumu, lai atrisinātu QP problēmas.
MOSEK Solver lieto iegultās "Inside Point" un automātiskās dubultās metodes. Tas ir īpaši efektīvi brīvi savienotu QP problēmu gadījumā. Tas var arī atrisināt skalas kvadrātiskā ierobežojuma (QCP) un otrās kārtas konusa programmēšanas (SOCP) problēmas.
Vairāku darbību aprēķini
Tās diezgan veiksmīgi tiek izmantotas, izmantojot Microsoft Office līdzekļus, piemēram, risinot optimizācijas uzdevumus programmā Excel.
Iepriekšējā tabulā ir šādi simboli:
- K1 - K6 - klienti, kuriem nepieciešams nodrošināt preces.
- S1 - S6 ir potenciālās ražošanas vietas, kuras varētu izveidot šim nolūkam. Var izveidot1, 2, 3, 4, 5 vai visas 6 atrašanās vietas.
Katrai iekārtai ir fiksētas izmaksas, kas norādītas I slejā (Fix).
Ja atrašanās vieta neko nemaina, tā netiks ieskaitīta. Tad nebūs fiksētu izmaksu.
Identificējiet iespējamās atrašanās vietas, lai iegūtu viszemākās izmaksas.
Šajos apstākļos atrašanās vieta ir noteikta vai nav. Šie divi stāvokļi ir: "TRUE - FALSE" vai "1 - 0". Sešām atrašanās vietām ir seši stāvokļi, piemēram, 000001 ir iestatīts tikai sestajā, 111111 ir visas.
Bināro skaitļu sistēmā ir tieši 63 dažādas opcijas no 000001 (1) līdz 111111 (63).
L2-L64 tagad ir jālasa {=MULTIPLE OPERATION (K1)}. Šie ir visu alternatīvo risinājumu rezultāti. Tad minimālā vērtība ir=Min (L) un atbilstošā alternatīva ir INDEX (K).
CPLEX veselo skaitļu programmēšana
Dažreiz ar lineārām attiecībām nepietiek, lai izprastu biznesa problēmas būtību. Tas jo īpaši attiecas uz gadījumiem, kad lēmumi ir saistīti ar diskrētu izvēli, piemēram, atvērt vai neatvērt noliktavu noteiktā vietā. Šādās situācijās ir jāizmanto veselu skaitļu programmēšana.
Ja problēma ir saistīta gan ar diskrētu, gan nepārtrauktu izvēli, tā ir jaukta veselu skaitļu programma. Tam var būt lineāras, izliektas kvadrātiskas problēmas un tie paši otrās kārtas ierobežojumi.
Veselu skaitļu programmas ir daudz sarežģītākas nekā lineārās programmas, taču tām ir svarīgas biznesa lietojumprogrammas. ProgrammatūraCPLEX programmatūra izmanto sarežģītas matemātiskas metodes, lai atrisinātu veselu skaitļu problēmas. Viņa metodes ietver sistemātisku diskrētu mainīgo iespējamo kombināciju meklēšanu, izmantojot lineāras vai kvadrātiskas programmatūras relaksācijas, lai aprēķinātu optimālā risinājuma vērtības robežas.
Tie izmanto arī LP un citas optimizācijas problēmu risināšanas metodes, lai aprēķinātu ierobežojumus.
Standarta Microsoft Excel risinātājs
Šī tehnoloģija izmanto galvenās Simplex metodes pamata ieviešanu, lai atrisinātu LP problēmas. Tas ir ierobežots līdz 200 mainīgajiem. "Premium Solver" izmanto uzlabotu primāro simpleksu metodi ar mainīgo lielumu divpusējām robežām. Premium Solver platforma izmanto paplašinātu LP/Quadratic Simplex Solver versiju, lai atrisinātu optimizācijas problēmu ar līdz pat 2000 lēmumu mainīgajiem.
Liela mēroga LP platformai Premium Solver izmanto vismodernāko vienkāršās un dubultās vienkāršās metodes ieviešanu, kas LP modelī izmanto retumu, lai ietaupītu laiku un atmiņu, uzlabotas atjaunināšanas stratēģijas un refaktorēšanas matricas, daudzkārtēja un daļēja cenu noteikšana un rotācijas, kā arī deģenerācijas pārvarēšanai. Šis dzinējs ir pieejams trīs versijās (var apstrādāt līdz pat 8000, 32 000 vai neierobežotu mainīgo un ierobežojumu skaitu).
MOSEK Solver ietver primāro un duālo simpleksu - metodi, kas izmanto arī retumu un izmanto uzlabotas stratēģijas matricas atjaunināšanai un "refaktorizācijai". Tas atrisina neierobežota izmēra problēmas, bijapārbaudīts uz lineārās programmēšanas problēmām ar miljoniem lēmumu mainīgo.
Soli pa solim piemērs programmā EXCEL
Lai definētu optimizācijas problēmas modeli programmā Excel, veiciet šādas darbības:
- Kārtojiet problēmas datus izklājlapā loģiskā formā.
- Atlasiet šūnu, lai saglabātu katru mainīgo.
- Šūnā izveidojiet formulu optimizācijas uzdevuma mērķa matemātiskā modeļa aprēķināšanai.
- Izveidojiet formulas, lai aprēķinātu katra ierobežojuma kreiso pusi.
- Izmantojiet dialoglodziņus programmā Excel, lai informētu Solver par lēmumu mainīgajiem, mērķiem, ierobežojumiem un vēlamajām šo parametru robežām.
- Palaidiet "Solver", lai atrastu optimālo risinājumu.
- Izveidojiet Excel lapu.
- Sakārtojiet problēmas datus programmā Excel, kur tiek aprēķināta mērķa funkcijas un ierobežojuma formula.
Iepriekšējā tabulā šūnas B4, C4, D4 un E4 ir rezervētas, lai attēlotu lēmumu mainīgos X 1, X 2, X 3 un X 4. Lēmumu piemēri:
- Produktu klāsta modelis (450 USD, 1150 USD, 800 USD un 400 USD peļņa par produktu) tika ievadīts attiecīgi šūnās B5, C5, D5 un E5. Tas ļauj aprēķināt mērķi F5=B5B4 + C5C4 + D5D4 + E5E4 vai F5:=SUMPRODUCT (B5: E5, B4: E4).
- B8 ievadiet katra produkta veida ražošanai nepieciešamo resursu daudzumu.
- Formula F8:=SUMPRODUCT(B8:E8, $B$4:$E$4).
- Kopēt šoformula F9. Dolāra zīmes $B$4:$E$4 norāda, ka šis šūnu diapazons paliek nemainīgs.
- G8 ievadiet katra veida pieejamo resursu apjomu, kas atbilst labajā pusē esošo ierobežojumu vērtībām. Tas ļauj tos izteikt šādi: F11<=G8: G11.
- Tas ir līdzvērtīgs četriem ierobežojumiem F8<=G8, F9 <=G9, F10 <=G10 un F11=0
Metodes praktiskā pielietojuma jomas
Lineārajai optimizācijai ir daudz praktisku pielietojumu kā optimizācijas problēmas piemērs:
Uzņēmums var izgatavot vairākus produktus ar zināmu ieguldījumu rezervi. Katras preces vienības ražošanai nepieciešams zināms ierobežotu resursu apjoms. Uzdevums ir izveidot ražošanas programmu, lai noteiktu, cik daudz no katra produkta jāsaražo, lai uzņēmuma peļņa tiktu maksimāli palielināta, nepārkāpjot resursu ierobežojumus.
Sajaukšanas problēmas ir risinājums optimizācijas problēmām, kas saistītas ar sastāvdaļu apvienošanu galaproduktā. Piemērs tam ir diētas problēma, kuru 1947. gadā pētīja Džordžs Dancigs. Tiek dotas vairākas izejvielas, piemēram, auzu, cūkgaļas un saulespuķu eļļa, kā arī to uzturvērtības, piemēram, olb altumvielas, tauki, A vitamīns, un to cena par kilogramu. Izaicinājums ir sajaukt vienu vai vairākus galaproduktus no izejvielām par iespējami zemākām izmaksām, vienlaikus ievērojot minimālo un maksimālo to uzturvērtības ierobežojumu.
Klasisks lineārās optimizācijas problēmas pielietojums ir maršrutēšanas noteikšana vajadzībāmsatiksme telekomunikāciju vai transporta tīklos. Tajā pašā laikā plūsmas ir jāmaršrutē caur tīklu tā, lai visas satiksmes prasības tiktu izpildītas, nepārkāpjot joslas platuma nosacījumus.
Matemātikas teorijā lineāro optimizāciju var izmantot, lai aprēķinātu optimālās stratēģijas nulles summas spēlēs diviem cilvēkiem. Šajā gadījumā katram dalībniekam tiek aprēķināts varbūtības sadalījums, kas ir viņa stratēģiju nejaušās sajaukšanas koeficients.
Neviens veiksmīgs biznesa process pasaulē nav iespējams bez optimizācijas. Ir pieejami daudzi optimizācijas algoritmi. Dažas metodes ir piemērotas tikai noteikta veida problēmām. Ir svarīgi spēt atpazīt to īpašības un izvēlēties piemērotu risinājuma metodi.
