Optimizavimas padeda rasti geriausią rezultatą, kuris atneša pelno, sumažina išlaidas arba nustato parametrą, sukeliantį verslo procesų nesėkmes.
Šis procesas dar vadinamas matematiniu programavimu. Ji išsprendžia ribotų išteklių, reikalingų optimizavimo uždavinio vadovo iškeltam tikslui pasiekti, paskirstymo nustatymo problemą. Iš visų galimų variantų pageidautina rasti tą, kuris maksimaliai padidina (arba sumažina) valdymo parametrą, pavyzdžiui, pelną ar sąnaudas. Optimizavimo modeliai taip pat vadinami įsakomaisiais arba normatyviniais, nes jais siekiama rasti įmanomą verslo strategiją.
Plėtros istorija
Tiesinis programavimas (LP) veikia su optimizavimo problemų klase, kai visi apribojimai yra tiesiniai.
Pristatome trumpą LP kūrimo istoriją:
- 1762 m. Lagrange'as išsprendė paprastas optimizavimo problemas su lygybės apribojimais.
- 1820 m. Gaussas nusprendėtiesinė lygčių sistema naudojant eliminavimą.
- 1866 m. Wilhelmas Jordanas ištobulino mažiausiųjų kvadratų klaidų nustatymo metodą kaip tinkamumo kriterijų. Dabar tai vadinama Gauso-Jordano metodu.
- Skaitmeninis kompiuteris pasirodė 1945 m.
- Dancigas išrado simpleksinius metodus 1947 m.
- 1968 m. Fiacco ir McCormick pristatė „Inside Point“metodą.
- 1984 m. Karmarkaras taikė interjero metodą tiesinėms programoms spręsti, pridėdamas savo naujovišką analizę.
LP pasirodė esąs itin galingas įrankis modeliuojant realaus pasaulio problemas ir kaip plačiai taikoma matematinė teorija. Tačiau daugelis įdomių optimizavimo problemų yra nelinijinės.
Ką daryti tokiu atveju? Tokių problemų tyrimas apima įvairų tiesinės algebros, daugiamačių skaičiavimų, skaitmeninės analizės ir skaičiavimo metodų derinį. Mokslininkai kuria skaičiavimo algoritmus, įskaitant vidinius taškų metodus, skirtus tiesiniam programavimui, geometrijai, išgaubtų aibių ir funkcijų analizei bei specialiai struktūrizuotų problemų, tokių kaip kvadratinis programavimas, studijoms.
Netiesinis optimizavimas suteikia pagrindinį matematinės analizės supratimą ir yra plačiai naudojamas įvairiose srityse, tokiose kaip inžinerija, regresinė analizė, išteklių valdymas, geofizinis tyrinėjimas ir ekonomika.
Optimizavimo problemų klasifikacija
Svarbus žingsnisOptimizavimo procesas yra modelių klasifikavimas, nes jų sprendimo algoritmai yra pritaikyti tam tikram tipui.
1. Diskretaus ir nuolatinio optimizavimo problemos. Kai kurie modeliai prasmingi tik tuo atveju, jei kintamieji paima reikšmes iš atskiro sveikųjų skaičių poaibio. Kituose yra duomenų, kurie gali įgyti bet kokią realią vertę. Paprastai juos lengviau išspręsti. Algoritmų patobulinimai kartu su kompiuterių technologijų pažanga smarkiai padidino linijinio programavimo optimizavimo problemos dydį ir sudėtingumą.
2. Neribotas ir ribotas optimizavimas. Kitas svarbus skirtumas yra užduotys, kuriose kintamiesiems nėra jokių apribojimų. Jis gali būti labai įvairus – nuo paprastų įverčių iki lygybių ir nelygybių sistemų, kurios modeliuoja sudėtingus duomenų ryšius. Tokios optimizavimo problemos gali būti toliau klasifikuojamos pagal funkcijų pobūdį (tiesinės ir netiesinės, išgaubtos ir lygios, diferencijuojamos ir nediferencijuojamos).
3. Galimybių užduotys. Jų tikslas – rasti kintamąsias reikšmes, kurios tenkintų modelio apribojimus be jokio konkretaus optimizavimo tikslo.
4. Komplementarumo užduotys. Jie plačiai naudojami technologijų ir ekonomikos srityse. Tikslas – rasti sprendimą, kuris tenkintų papildomumo sąlygas. Praktikoje užduotys su keliais tikslais dažnai performuluojamos į vieną tikslą.
5. Deterministinis ir stochastinis optimizavimas. Deterministinis optimizavimas daro prielaidą, kad duomenys užužduotys yra visiškai tikslios. Tačiau dėl daugelio aktualių klausimų jų negalima žinoti dėl kelių priežasčių.
Pirmasis yra susijęs su paprasta matavimo klaida. Antroji priežastis yra esminė. Tai slypi tame, kad kai kurie duomenys atspindi informaciją apie ateitį, pavyzdžiui, prekės paklausą ar kainą būsimam laikotarpiui. Optimizuojant stochastinio optimizavimo sąlygomis, į modelį įtraukiamas neapibrėžtis.
Pagrindiniai komponentai
Tikslo funkcija turi būti sumažinta arba padidinta. Dauguma optimizavimo problemų tipų turi vieną tikslinę funkciją. Jei ne, jie dažnai gali būti performuluoti, kad veiktų.
Dvi šios taisyklės išimtys:
1. Tikslinės paieškos užduotis. Daugumoje verslo programų vadovas nori pasiekti konkretų tikslą, tenkindamas modelio apribojimus. Vartotojas ne itin nori kažko optimizuoti, todėl nėra prasmės apibrėžti tikslo funkciją. Šis tipas paprastai vadinamas patenkinimo problema.
2. Daug objektyvių savybių. Dažnai vartotojas nori vienu metu optimizuoti kelis skirtingus tikslus. Paprastai jie yra nesuderinami. Kintamieji, kurie optimizuoja vieną tikslą, gali būti netinkami kitiems.
Komponentų tipai:
- Valdoma įvestis yra sprendimo kintamųjų, turinčių įtakos tikslo funkcijos vertei, rinkinys. Gamybos užduotyje kintamieji gali apimti įvairių turimų išteklių arba tam reikalingos darbo jėgos paskirstymąkiekvienas veiksmas.
- Apribojimai yra ryšiai tarp sprendimo kintamųjų ir parametrų. Kilus gamybos problemai, nėra prasmės skirti daug laiko jokiai veiklai, todėl apribokite visus „laikinus“kintamuosius.
- Galimi ir optimalūs sprendimai. Kintamųjų sprendimo reikšmė, pagal kurią tenkinami visi apribojimai, vadinama patenkinama. Dauguma algoritmų pirmiausia jį suranda, tada bando patobulinti. Galiausiai jie keičia kintamuosius, kad pereitų nuo vieno įmanomo sprendimo prie kito. Šis procesas kartojamas tol, kol tikslo funkcija pasiekia maksimumą arba minimumą. Šis rezultatas vadinamas optimaliu sprendimu.
Plačiai naudojami optimizavimo uždavinių algoritmai, sukurti šioms matematinėms programoms:
- Išgaubtas.
- Atskiriama.
- Kvadratinis.
- Geometrinis.
Google Linear Solvers
Tiesinis optimizavimas arba programavimas – tai skaičiavimo procesas, skirtas optimaliai išspręsti problemą. Jis modeliuojamas kaip linijinių ryšių, atsirandančių daugelyje mokslo ir inžinerijos disciplinų, rinkinys.
Google siūlo tris linijinio optimizavimo problemų sprendimo būdus:
- Grop atvirojo kodo biblioteką.
- Tiesijinio optimizavimo priedas, skirtas „Google“skaičiuoklėms.
- Tiesijinio optimizavimo paslauga „Google Apps Script“.
Glop yra integruotas į „Google“.tiesinis sprendėjas. Jis prieinamas atvirojo kodo. „Glop“galite pasiekti naudodami „OR-Tools“linijinį tirpiklio įvyniotuvą, kuris yra „Glop“įvynioklis.
Tiesijinis „Google“skaičiuoklių optimizavimo modulis leidžia atlikti tiesinį optimizavimo problemos teiginį įvedant duomenis į skaičiuoklę.
Kvadratinis programavimas
Premium Solver platforma naudoja išplėstinę LP/kvadratinę Simplex metodo versiją su LP ir QP problemų apdorojimo ribomis iki 2000 sprendimo kintamųjų.
SQP Solver didelės apimties problemoms spręsti naudoja šiuolaikišką aktyviojo rinkinio metodo įgyvendinimą su retumu, kad išspręstų kvadratinio programavimo (QP) problemas. XPRESS Solver variklis naudoja natūralų „Interior Point“arba Niutono barjero metodo išplėtimą, kad išspręstų QP problemas.
MOSEK Solver taiko įterptąjį „vidinį tašką“ir automatinio dvigubo nustatymo metodus. Tai ypač efektyvu esant laisvai susietoms QP problemoms. Jis taip pat gali išspręsti skalės kvadratinio apribojimo (QCP) ir antrosios eilės kūgio programavimo (SOCP) problemas.
Kelių operacijų skaičiavimai
Jos gana sėkmingai naudojamos naudojant Microsoft Office funkcijas, pavyzdžiui, sprendžiant optimizavimo problemas programoje Excel.
Aukščiau pateiktoje lentelėje simboliai yra:
- K1 – K6 – klientai, kuriems reikia tiekti prekes.
- S1 – S6 yra potencialios gamybos vietos, kurias būtų galima pastatyti šiam tikslui. Galima sukurti1, 2, 3, 4, 5 arba visos 6 vietos.
Kiekvienai I stulpelyje (Pataisyta) nurodytai įmonei yra nustatytos fiksuotos išlaidos.
Jei vieta nieko nepakeis, ji nebus skaičiuojama. Tada nebus jokių fiksuotų išlaidų.
Nustatykite galimas vietas, kad gautumėte mažiausią kainą.
Šiomis sąlygomis vieta yra nustatyta arba ne. Šios dvi būsenos yra: "TRUE - FALSE" arba "1 - 0". Šešiose vietose yra šešios būsenos, pavyzdžiui, 000001 nustatyta tik šeštoje, 111111 – visos.
Dvejetainėje skaičių sistemoje yra lygiai 63 skirtingos parinktys nuo 000001 (1) iki 111111 (63).
L2-L64 dabar turėtų būti rodomas {=MULTIPLE OPERATION (K1)}, tai yra visų alternatyvių sprendimų rezultatai. Tada mažiausia reikšmė yra=Min (L), o atitinkama alternatyva yra INDEX (K).
CPLEX sveikųjų skaičių programavimas
Kartais linijinių santykių nepakanka norint išsiaiškinti verslo problemos esmę. Tai ypač aktualu, kai sprendimai susiję su diskretiškais pasirinkimais, pavyzdžiui, atidaryti sandėlį tam tikroje vietoje ar ne. Tokiose situacijose turi būti naudojamas sveikųjų skaičių programavimas.
Jei problema apima ir atskirus, ir nuolatinius pasirinkimus, tai yra mišrių sveikųjų skaičių programa. Jis gali turėti tiesines, išgaubtas kvadratines problemas ir tuos pačius antros eilės apribojimus.
Sveikų skaičių programos yra daug sudėtingesnės nei linijinės, tačiau jos turi svarbių verslo programų. Programinė įrangaCPLEX programinė įranga naudoja sudėtingus matematinius metodus sveikųjų skaičių problemoms spręsti. Jo metodai apima sistemingą galimų diskrečiųjų kintamųjų derinių paiešką, naudojant linijinius arba kvadratinius programinės įrangos atsipalaidavimus, siekiant apskaičiuoti optimalaus sprendimo vertės ribas.
Jie taip pat naudoja LP ir kitus optimizavimo problemų sprendimo metodus apribojimams apskaičiuoti.
Standartinis Microsoft Excel Solver
Ši technologija naudoja pagrindinį pagrindinio Simplex metodo įgyvendinimą LP problemoms spręsti. Jis apribotas iki 200 kintamųjų. „Premium Solver“naudoja patobulintą pirminį simplekso metodą su dvipusėmis kintamųjų ribomis. „Premium Solver“platforma naudoja išplėstinę LP/Quadratic Simplex Solver versiją, kad išspręstų optimizavimo problemą su iki 2000 sprendimų kintamųjų.
Didelio masto LP, skirta Premium Solver platformai, taiko pažangiausią paprasto ir dvigubo vienakrypčio metodo įgyvendinimą, kuris naudoja LP modelio retumą, kad sutaupytų laiką ir atmintį, pažangias atnaujinimo strategijas ir pertvarkymo matricos, daugkartinė ir dalinė kainodara ir rotacijos, ir degeneracijai įveikti. Šis variklis yra trijų versijų (gali apdoroti iki 8 000, 32 000 arba neribotą kintamųjų ir apribojimų skaičių).
MOSEK Solver apima pirminį ir dvigubą simpleksą – metodą, kuris taip pat išnaudoja retumą ir naudoja pažangias matricos atnaujinimo ir „refaktorizacijos“strategijas. Jis išsprendžia neriboto dydžio problemas, buvoišbandyta tiesinio programavimo problemomis su milijonais sprendimų kintamųjų.
Žingsnis po žingsnio pavyzdys programoje EXCEL
Norėdami apibrėžti optimizavimo problemos modelį programoje „Excel“, atlikite šiuos veiksmus:
- Logine forma sutvarkykite problemos duomenis skaičiuoklėje.
- Pasirinkite langelį, kad išsaugotumėte kiekvieną kintamąjį.
- Ląstelėje sukurkite formulę, skirtą tiksliniam optimizavimo uždavinio matematiniam modeliui apskaičiuoti.
- Sukurkite formules kiekvieno apribojimo kairiajai pusei apskaičiuoti.
- Naudokite dialogo langus programoje „Excel“, kad praneštumėte Solver apie sprendimų kintamuosius, tikslus, apribojimus ir norimas šių parametrų ribas.
- Paleiskite „Solver“, kad rastumėte optimalų sprendimą.
- Sukurkite „Excel“lapą.
- Tvarkykite problemos duomenis programoje Excel, kur apskaičiuojama tikslo funkcijos ir apribojimo formulė.
Aukščiau pateiktoje lentelėje langeliai B4, C4, D4 ir E4 buvo rezervuoti, kad pavaizduotų sprendimų kintamuosius X 1, X 2, X 3 ir X 4. Sprendimo pavyzdžiai:
- Produktų derinio modelis (450 USD, 1150 USD, 800 USD ir 400 USD pelnas vienam produktui) buvo įvestas atitinkamai B5, C5, D5 ir E5 langeliuose. Tai leidžia apskaičiuoti tikslą F5=B5B4 + C5C4 + D5D4 + E5E4 arba F5:=SUMPRODUCT (B5: E5, B4: E4).
- B8 įveskite išteklių kiekį, reikalingą kiekvieno tipo produktui pagaminti.
- F8 formulė:=SUMPRODUKTAS(B8:E8, $B$4:$E$4).
- Nukopijuokite taiformulė F9. Dolerio ženklai $B$4:$E$4 rodo, kad šis langelių diapazonas išlieka pastovus.
- G8 įveskite turimą kiekvieno tipo išteklių kiekį, atitinkantį dešinėje esančių apribojimų reikšmes. Tai leidžia juos išreikšti taip: F11<=G8: G11.
- Tai atitinka keturias ribas F8<=G8, F9 <=G9, F10 <=G10 ir F11=0
Praktinio metodo taikymo sritys
Tiesinis optimizavimas turi daug praktinių pritaikymų kaip optimizavimo problemos pavyzdys:
Įmonė gali pagaminti kelis produktus su žinoma įnašo marža. Kiekvienos prekės vienetui pagaminti reikia žinomo kiekio ribotų išteklių. Užduotis yra sukurti gamybos programą, kad būtų nustatyta, kiek kiekvieno produkto turi būti pagaminta, kad įmonės pelnas būtų maksimalus nepažeidžiant išteklių apribojimų.
Maišymo problemos yra optimizavimo problemų, susijusių su sudedamųjų dalių sujungimu į galutinį produktą, sprendimas. To pavyzdys yra dietos problema, kurią 1947 m. nagrinėjo George'as Dancigas. Pateikiama nemažai žaliavų, tokių kaip avižų, kiaulienos ir saulėgrąžų aliejus, kartu su jų maistinėmis medžiagomis, tokiomis kaip b altymai, riebalai, vitaminas A, ir jų kilogramo kaina. Iššūkis yra sumaišyti vieną ar daugiau galutinių produktų iš žaliavų už mažiausią įmanomą kainą, laikantis minimalių ir didžiausių jų maistinės vertės ribų.
Klasikinis linijinio optimizavimo uždavinio taikymas yra maršruto nustatymas pagal poreikiussrautas telekomunikacijų ar transporto tinkluose. Tuo pačiu metu srautai turi būti nukreipiami per tinklą taip, kad būtų tenkinami visi srauto reikalavimai nepažeidžiant pralaidumo sąlygų.
Matematinėje teorijoje tiesinis optimizavimas gali būti naudojamas optimalioms strategijoms apskaičiuoti nulinės sumos žaidimuose dviems žmonėms. Tokiu atveju apskaičiuojamas kiekvieno dalyvio tikimybių skirstinys, kuris yra jo strategijų atsitiktinio maišymo koeficientas.
Joks sėkmingas verslo procesas pasaulyje neįmanomas be optimizavimo. Yra daug optimizavimo algoritmų. Kai kurie metodai tinka tik tam tikroms problemoms spręsti. Svarbu mokėti atpažinti jų ypatybes ir pasirinkti tinkamą sprendimo būdą.
