Optimizimi ju ndihmon të gjeni rezultatin më të mirë që sjell fitim, zvogëlon kostot ose vendos një parametër që shkakton dështime të procesit të biznesit.
Ky proces quhet edhe programim matematikor. Ai zgjidh problemin e përcaktimit të shpërndarjes së burimeve të kufizuara të nevojshme për të arritur qëllimin e vendosur nga kreu i problemit të optimizimit. Nga të gjitha opsionet e mundshme, është e dëshirueshme të gjesh atë që maksimizon (ose zvogëlon) parametrin kontrollues, për shembull, fitimin ose koston. Modelet e optimizimit quhen gjithashtu përshkrues ose normativë sepse ato kërkojnë të gjejnë një strategji të mundshme për biznesin.
Historiku i zhvillimit
Programimi linear (LP) punon me një klasë problemesh optimizimi ku të gjitha kufizimet janë lineare.
Prezantimi i një historie të shkurtër të zhvillimit të LP:
- Në 1762, Lagranzhi zgjidhi probleme të thjeshta optimizimi me kufizime barazie.
- Në 1820, Gauss vendosisistemi linear i ekuacioneve duke përdorur eliminimin.
- Në vitin 1866, Wilhelm Jordan përsosi metodën e gjetjes së gabimeve të katrorëve më të vegjël si një kriter i përshtatshëm. Kjo tani quhet metoda Gauss-Jordan.
- Kompjuteri dixhital u shfaq në vitin 1945.
- Danzig shpiku metoda simplex në 1947.
- Në vitin 1968, Fiacco dhe McCormick prezantuan metodën Inside Point.
- Në vitin 1984, Karmarkar aplikoi metodën e brendshme për të zgjidhur programet lineare, duke shtuar analizën e tij novatore.
LP është dëshmuar të jetë një mjet jashtëzakonisht i fuqishëm si për modelimin e problemeve të botës reale, ashtu edhe si një teori matematikore e aplikuar gjerësisht. Megjithatë, shumë probleme interesante të optimizimit janë jolineare.
Çfarë duhet të bëni në këtë rast? Studimi i problemeve të tilla përfshin një përzierje të larmishme të algjebrës lineare, llogaritjeve me shumë variacione, analizave numerike dhe metodave llogaritëse. Shkencëtarët po zhvillojnë algoritme llogaritëse, duke përfshirë metodat e pikës së brendshme për programimin linear, gjeometrinë, analizën e grupeve dhe funksioneve konvekse dhe studimin e problemeve të strukturuara posaçërisht si programimi kuadratik.
Optimizimi jolinear ofron një kuptim themelor të analizës matematikore dhe përdoret gjerësisht në fusha të ndryshme si inxhinieria, analiza e regresionit, menaxhimi i burimeve, eksplorimi gjeofizik dhe ekonomia.
Klasifikimi i problemeve të optimizimit
Një hap i rëndësishëm nëProcesi i optimizimit është klasifikimi i modeleve, pasi algoritmet e tyre të zgjidhjes janë përshtatur për një lloj të caktuar.
1. Probleme me optimizimin diskret dhe të vazhdueshëm. Disa modele kanë kuptim vetëm nëse variablat marrin vlera nga një nëngrup diskrete numrash të plotë. Të tjerat përmbajnë të dhëna që mund të marrin çdo vlerë reale. Zakonisht ato janë më të lehta për t'u zgjidhur. Përmirësimet në algoritme, të kombinuara me përparimet në teknologjinë kompjuterike, kanë rritur në mënyrë dramatike madhësinë dhe kompleksitetin e një problemi të optimizimit të programimit linear.
2. Optimizimi i pakufizuar dhe i kufizuar. Një tjetër ndryshim i rëndësishëm janë detyrat ku nuk ka kufizime për variablat. Mund të variojë gjerësisht nga vlerësuesit e thjeshtë deri te sistemet e barazive dhe pabarazive që modelojnë marrëdhënie komplekse midis të dhënave. Probleme të tilla optimizimi mund të klasifikohen më tej sipas natyrës së funksioneve (lineare dhe jolineare, konvekse dhe të lëmuara, të diferencueshme dhe jo të diferencueshme).
3. Detyrat e fizibilitetit. Qëllimi i tyre është të gjejnë vlera të ndryshueshme që plotësojnë kufizimet e modelit pa ndonjë qëllim specifik optimizimi.
4. Detyrat plotësuese. Ato përdoren gjerësisht në teknologji dhe ekonomi. Qëllimi është të gjendet një zgjidhje që plotëson kushtet e komplementaritetit. Në praktikë, detyrat me disa qëllime shpesh riformulohen në objektiva të vetëm.
5. Optimizimi përcaktues kundrejt atij stokastik. Optimizimi përcaktues supozon se të dhënat përdetyrat janë plotësisht të sakta. Megjithatë, për shumë çështje aktuale ato nuk mund të njihen për një sërë arsyesh.
E para ka të bëjë me një gabim të thjeshtë matjeje. Arsyeja e dytë është më themelore. Ai qëndron në faktin se disa të dhëna përfaqësojnë informacion për të ardhmen, për shembull, kërkesën për një produkt ose çmimin për një periudhë të ardhshme kohore. Kur optimizohet në kushte të optimizimit stokastik, pasiguria përfshihet në model.
Përbërësit kryesor
Funksioni objektiv është ai që duhet minimizuar ose maksimizuar. Shumica e llojeve të problemeve të optimizimit kanë një funksion objektiv. Nëse jo, ato shpesh mund të riformulohen për të funksionuar.
Dy përjashtime nga ky rregull:
1. Detyra e kërkimit të synuar. Në shumicën e aplikacioneve të biznesit, menaxheri dëshiron të arrijë një qëllim specifik duke përmbushur kufizimet e modelit. Përdoruesi nuk dëshiron veçanërisht të optimizojë diçka, kështu që nuk ka kuptim të përcaktojë një funksion objektiv. Ky lloj zakonisht quhet problem i kënaqshmërisë.
2. Shumë karakteristika objektive. Shpesh, një përdorues dëshiron të optimizojë disa qëllime të ndryshme në të njëjtën kohë. Zakonisht ato janë të papajtueshme. Variablat që optimizohen për një qëllim mund të mos jenë më të mirat për të tjerët.
Llojet e komponentëve:
- Një hyrje e kontrolluar është një grup variablash vendimi që ndikojnë në vlerën e një funksioni objektiv. Në një detyrë prodhimi, variablat mund të përfshijnë shpërndarjen e burimeve të ndryshme të disponueshme ose punën e nevojshmeçdo veprim.
- Kufizimet janë marrëdhënie ndërmjet variablave të vendimit dhe parametrave. Për një problem prodhimi, nuk ka kuptim të shpenzoni shumë kohë në ndonjë aktivitet, ndaj kufizoni të gjitha variablat "të përkohshëm".
- Zgjidhje të mundshme dhe optimale. Vlera e vendimit për variablat, sipas të cilave plotësohen të gjitha kufizimet, quhet e kënaqshme. Shumica e algoritmeve fillimisht e gjejnë atë, pastaj përpiqen ta përmirësojnë. Së fundi, ata ndryshojnë variablat për të kaluar nga një zgjidhje e mundshme në tjetrën. Ky proces përsëritet derisa funksioni objektiv të arrijë maksimumin ose minimumin e tij. Ky rezultat quhet zgjidhja optimale.
Algoritmet e problemeve të optimizimit të zhvilluara për programet e mëposhtme matematikore përdoren gjerësisht:
- Konveks.
- E ndashme.
- Kuadratik.
- Geometrike.
Zgjitës linear i Google
Optimizimi ose programimi linear është emri që i jepet procesit llogaritës të zgjidhjes optimale të një problemi. Ai është modeluar si një grup marrëdhëniesh lineare që lindin në shumë disiplina shkencore dhe inxhinierike.
Google ofron tre mënyra për të zgjidhur problemet e optimizimit linear:
- Biblioteka Glop me burim të hapur.
- Shtesë e Optimizimit linear për Fletët e Google.
- Shërbimi i Optimizimit Linear në Skriptin e Aplikacioneve të Google.
Glop është i integruar në Googlezgjidhës linear. Është në dispozicion në burim të hapur. Ju mund të përdorni Glop përmes mbështjellësit linear të zgjidhjes OR-Tools, i cili është një mbështjellës për Glop.
Moduli i optimizimit linear për Fletët e Google ju lejon të kryeni një deklaratë lineare të problemit të optimizimit duke futur të dhëna në një fletëllogaritëse.
Programim kuadratik
Platforma Premium Solver përdor një version të zgjeruar LP/Kuadratik të metodës Simplex me kufizime të përpunimit të problemeve LP dhe QP deri në 2000 variabla vendimesh.
Zgjitësi SQP për probleme në shkallë të gjerë përdor një zbatim modern të metodës së grupit aktiv me rrallësi për të zgjidhur problemet e programimit kuadratik (QP). Motori XPRESS Solver përdor një shtrirje natyrale të metodës "Pika e Brendshme" ose Njuton Barrier për të zgjidhur problemet QP.
MOSEK Solver zbaton metodat e integruara "Inside Point" dhe automatikisht të dyfishta. Kjo është veçanërisht e efektshme për problemet QP të lidhura lirshëm. Mund të zgjidhë gjithashtu problemet e kufizimit kuadratik të shkallës (QCP) dhe programimit të konit të rendit të dytë (SOCP).
Llogaritjet me shumë funksione
Ato përdoren me mjaft sukses me përdorimin e veçorive të Microsoft Office, për shembull, zgjidhja e problemeve të optimizimit në Excel.
Në tabelën e mësipërme, simbolet janë:
- K1 - K6 - klientët që duhet të ofrojnë mallra.
- S1 - S6 janë vende të mundshme prodhimi që mund të ndërtohen për këtë. Mund të krijohet1, 2, 3, 4, 5 ose të 6 vendndodhjet.
Ka kosto fikse për çdo objekt të listuar në kolonën I (Fix).
Nëse vendndodhja nuk ndryshon asgjë, nuk do të llogaritet. Atëherë nuk do të ketë kosto fikse.
Identifikoni vendndodhjet e mundshme për të marrë koston më të ulët.
Në këto kushte, vendndodhja ose vendoset ose jo. Këto dy gjendje janë: "E VËRTETË - E FALSE" ose "1 - 0". Ka gjashtë gjendje për gjashtë vendndodhje, për shembull, 000001 është caktuar vetëm në të gjashtin, 111111 është caktuar për të gjitha.
Në sistemin e numrave binar, ekzistojnë saktësisht 63 opsione të ndryshme nga 000001 (1) në 111111 (63).
L2-L64 tani duhet të lexojë {=MULTIPLE OPERATION (K1)}, këto janë rezultatet e të gjitha zgjidhjeve alternative. Atëherë vlera minimale është=Min (L) dhe alternativa përkatëse është INDEX (K).
CPLEX Programim me numra të plotë
Ndonjëherë një marrëdhënie lineare nuk mjafton për të arritur në thelbin e një problemi biznesi. Kjo është veçanërisht e vërtetë kur vendimet përfshijnë zgjedhje diskrete, të tilla si hapja ose jo e një magazine në një vend të caktuar. Në këto situata, duhet të përdoret programimi me numra të plotë.
Nëse problemi përfshin zgjedhje diskrete dhe të vazhdueshme, është një program i përzier me numra të plotë. Mund të ketë probleme kuadratike lineare, konvekse dhe të njëjtat kufizime të rendit të dytë.
Programet me numra të plotë janë shumë më komplekse se programet lineare, por ato kanë aplikacione të rëndësishme biznesi. SoftwareSoftueri CPLEX përdor metoda komplekse matematikore për të zgjidhur problemet me numra të plotë. Metodat e tij përfshijnë kërkimin sistematik të kombinimeve të mundshme të variablave diskrete duke përdorur relaksime lineare ose kuadratike të softuerit për të llogaritur kufijtë në vlerën e zgjidhjes optimale.
Ata përdorin gjithashtu LP dhe metoda të tjera të zgjidhjes së problemeve të optimizimit për të llogaritur kufizimet.
Zgjitësi standard i Microsoft Excel
Kjo teknologji përdor zbatimin bazë të metodës kryesore Simplex për të zgjidhur problemet LP. Është i kufizuar në 200 variabla. "Zgjitësi Premium" përdor një metodë të përmirësuar primare simplex me kufij të dyanshëm për variablat. Platforma Premium Solver përdor një version të zgjeruar të LP/Quadratic Simplex Solver për të zgjidhur një problem optimizimi me deri në 2000 variabla vendimi.
LP në shkallë të gjerë për platformën Premium Solver aplikon një implementim më të avancuar të metodës së thjeshtë dhe të dyfishtë simplex, e cila përdor pakësimin në modelin LP për të kursyer kohë dhe kujtesë, strategji të avancuara për përditësimin dhe matricat e rifaktorimit, çmimet dhe rrotullimet e shumëfishta dhe të pjesshme, dhe për tejkalimin e degjenerimit. Ky motor është i disponueshëm në tre versione (i aftë për të trajtuar deri në 8,000, 32,000 ose variabla dhe kufij të pakufizuar).
MOSEK Solver përfshin simplex primar dhe dual, një metodë që shfrytëzon gjithashtu pakësimin dhe përdor strategji të avancuara për përditësimin dhe "rifaktorizimin" e matricës. Ai zgjidh probleme me përmasa të pakufizuara, ishtetestuar në problemet e programimit linear me miliona variabla vendimesh.
Shembull hap pas hapi në EXCEL
Për të përcaktuar modelin e problemit të optimizimit në Excel, kryeni hapat e mëposhtëm:
- Organizoni të dhënat për problemin në një fletëllogaritëse në një formë logjike.
- Zgjidh një qelizë për të ruajtur secilën variabël.
- Krijoni në qelizë një formulë për llogaritjen e modelit të synuar matematikor të problemit të optimizimit.
- Krijoni formula për të llogaritur anën e majtë të çdo kufizimi.
- Përdor dialogët në Excel për t'i treguar Solver variablat e vendimit, objektivat, kufizimet dhe kufijtë e dëshiruar në ato parametra.
- Ekzekutoni "Solver" për të gjetur zgjidhjen optimale.
- Krijoni një fletë Excel.
- Organizoni të dhënat për problemin në Excel ku llogaritet formula për funksionin objektiv dhe kufizimin.
Në tabelën e mësipërme, qelizat B4, C4, D4 dhe E4 janë rezervuar për të përfaqësuar variablat e vendimit X 1, X 2, X 3 dhe X 4. Shembuj vendimi:
- Modeli i përzierjes së produktit (450$, 1150$, 800$ dhe 400$ fitim për produkt) u fut në qelizat B5, C5, D5 dhe E5, respektivisht. Kjo lejon që objektivi të llogaritet në F5=B5B4 + C5C4 + D5D4 + E5E4 ose F5:=SUMPRODUCT (B5: E5, B4: E4).
- Në B8 shkruani sasinë e burimeve të nevojshme për të prodhuar çdo lloj produkti.
- Formula për F8:=SUMPRODUCT(B8:E8, $B$4:$E$4).
- Kopjo këtëformula në F9. Shenjat e dollarit në $B$4:$E$4 tregojnë se kjo gamë qelizash mbetet konstante.
- Në G8 shkruani sasinë e disponueshme të burimeve të secilit lloj, që korrespondon me vlerat e kufizimeve në të djathtë. Kjo ju lejon t'i shprehni ato si kjo: F11<=G8: G11.
- Kjo është ekuivalente me katër kufij F8<=G8, F9 <=G9, F10 <=G10 dhe F11=0
Fushat e zbatimit praktik të metodës
Optimizimi linear ka shumë aplikime praktike si shembull i një problemi optimizimi:
Një kompani mund të prodhojë disa produkte me një marzh të njohur kontributi. Prodhimi i një njësie të çdo artikulli kërkon një sasi të njohur burimesh të kufizuara. Detyra është të krijohet një program prodhimi për të përcaktuar se sa nga çdo produkt duhet të prodhohet në mënyrë që fitimi i kompanisë të maksimizohet pa shkelur kufizimet e burimeve.
Problemet e përzierjes janë zgjidhja e problemeve të optimizimit që lidhen me kombinimin e përbërësve në produktin përfundimtar. Një shembull i kësaj është problemi i dietës i studiuar nga George Danzig në 1947. Jepen një sërë lëndësh të para, si tërshëra, vaji i derrit dhe luledielli, së bashku me përmbajtjen e tyre ushqyese, si proteina, yndyra, vitamina A dhe çmimi i tyre për kilogram. Sfida është të përzieni një ose më shumë produkte përfundimtare nga lëndët e para me koston më të ulët të mundshme duke respektuar kufijtë minimalë dhe maksimalë për vlerën e tyre ushqyese.
Një aplikim klasik i një problemi të optimizimit linear është përcaktimi i rrugëzimit për nevojattrafiku në rrjetet e telekomunikacionit apo transportit. Në të njëjtën kohë, flukset duhet të drejtohen përmes rrjetit në mënyrë të tillë që të gjitha kërkesat e trafikut të përmbushen pa shkelur kushtet e gjerësisë së brezit.
Në teorinë matematikore, optimizimi linear mund të përdoret për të llogaritur strategjitë optimale në lojërat me shumë zero për dy persona. Në këtë rast, llogaritet shpërndarja e probabilitetit për çdo pjesëmarrës, e cila është koeficienti i përzierjes së rastësishme të strategjive të tij.
Asnjë proces i suksesshëm biznesi në botë nuk është i mundur pa optimizim. Ka shumë algoritme optimizimi në dispozicion. Disa metoda janë të përshtatshme vetëm për lloje të caktuara të problemeve. Është e rëndësishme të jeni në gjendje të njihni karakteristikat e tyre dhe të zgjidhni metodën e duhur të zgjidhjes.
