Optimizarea vă ajută să găsiți cel mai bun rezultat care aduce profit, reduce costurile sau setează un parametru care cauzează eșecurile proceselor de afaceri.
Acest proces se mai numește și programare matematică. Rezolvă problema determinării repartizării resurselor limitate necesare atingerii scopului stabilit de șeful problemei de optimizare. Dintre toate opțiunile posibile, este de dorit să o găsiți pe cea care maximizează (sau reduce) parametrul de control, de exemplu, profitul sau costul. Modelele de optimizare mai sunt numite prescriptive sau normative, deoarece caută să găsească o strategie fezabilă pentru afacere.
Istoricul dezvoltării
Programarea liniară (LP) funcționează cu o clasă de probleme de optimizare în care toate constrângerile sunt liniare.
Prezentarea unui scurt istoric al dezvoltării LP:
- În 1762, Lagrange a rezolvat probleme simple de optimizare cu constrângeri de egalitate.
- În 1820, Gauss a decissistem liniar de ecuații folosind eliminarea.
- În 1866, Wilhelm Jordan a perfecționat metoda de găsire a erorilor celor mai mici pătrate ca criteriu de potrivire. Aceasta se numește acum metoda Gauss-Iordan.
- Computerul digital a apărut în 1945.
- Danzig a inventat metode simplex în 1947.
- În 1968, Fiacco și McCormick au introdus metoda Inside Point.
- În 1984, Karmarkar a aplicat metoda interioară pentru a rezolva programe liniare, adăugând analiza sa inovatoare.
LP s-a dovedit a fi un instrument extrem de puternic atât pentru modelarea problemelor din lumea reală, cât și ca teorie matematică aplicată pe scară largă. Cu toate acestea, multe probleme interesante de optimizare sunt neliniare.
Ce să faci în acest caz? Studiul unor astfel de probleme implică un amestec variat de algebră liniară, calcul multivariat, analiză numerică și metode de calcul. Oamenii de știință dezvoltă algoritmi de calcul, inclusiv metode de punct interior pentru programarea liniară, geometrie, analiza mulțimilor și funcțiilor convexe și studiul problemelor special structurate, cum ar fi programarea pătratică.
Optimizarea neliniară oferă o înțelegere fundamentală a analizei matematice și este utilizată pe scară largă în diverse domenii, cum ar fi inginerie, analiza regresiei, managementul resurselor, explorarea geofizică și economie.
Clasificarea problemelor de optimizare
Un pas important înProcesul de optimizare este clasificarea modelelor, deoarece algoritmii lor de soluție sunt adaptați unui anumit tip.
1. Probleme cu optimizarea discretă și continuă. Unele modele au sens numai dacă variabilele iau valori dintr-un subset discret de numere întregi. Altele conțin date care pot lua orice valoare reală. Ele sunt de obicei mai ușor de rezolvat. Îmbunătățirile în algoritmi, combinate cu progresele în tehnologia computerelor, au crescut dramatic dimensiunea și complexitatea unei probleme de optimizare a programării liniare.
2. Optimizare nelimitată și limitată. O altă diferență importantă este sarcinile în care nu există nicio constrângere asupra variabilelor. Poate varia de la simple estimatori la sisteme de egalități și inegalități care modelează relații complexe între date. Astfel de probleme de optimizare pot fi clasificate în continuare în funcție de natura funcțiilor (liniare și neliniare, convexe și netede, diferențiabile și nediferențiabile).
3. Sarcini de fezabilitate. Scopul lor este să găsească valori variabile care să satisfacă constrângerile modelului fără niciun obiectiv specific de optimizare.
4. Sarcini de complementaritate. Sunt utilizate pe scară largă în tehnologie și economie. Scopul este de a găsi o soluție care să satisfacă condițiile de complementaritate. În practică, sarcinile cu mai multe obiective sunt adesea reformulate în unele cu un singur obiectiv.
5. Optimizare deterministă versus optimizare stocastică. Optimizarea deterministă presupune că datele pentrusarcinile sunt complet exacte. Cu toate acestea, cu privire la multe probleme de actualitate, acestea nu pot fi cunoscute din mai multe motive.
Primul are legătură cu o eroare simplă de măsurare. Al doilea motiv este mai fundamental. Constă în faptul că unele date reprezintă informații despre viitor, de exemplu, cererea pentru un produs sau prețul pentru o perioadă viitoare de timp. La optimizarea în condiții de optimizare stocastică, incertitudinea este inclusă în model.
Componente principale
Funcția obiectiv este cea care trebuie minimizată sau maximizată. Cele mai multe tipuri de probleme de optimizare au o singură funcție obiectiv. Dacă nu, ele pot fi adesea reformulate pentru a funcționa.
Două excepții de la această regulă:
1. Sarcina de căutare vizată. În majoritatea aplicațiilor de afaceri, managerul dorește să atingă un obiectiv specific, în timp ce satisface constrângerile modelului. Utilizatorul nu dorește în mod deosebit să optimizeze ceva, așa că nu are sens să definească o funcție obiectivă. Acest tip este denumit în mod obișnuit o problemă de satisfacție.
2. O mulțime de caracteristici obiective. Adesea, un utilizator ar dori să optimizeze mai multe obiective diferite simultan. Ele sunt de obicei incompatibile. Variabilele care optimizează pentru un singur obiectiv pot să nu fie cele mai bune pentru alții.
Tipuri de componente:
- O intrare controlată este un set de variabile de decizie care afectează valoarea unei funcții obiectiv. Într-o sarcină de producție, variabilele pot include distribuția diferitelor resurse disponibile sau a forței de muncă necesarefiecare acțiune.
- Constrângerile sunt relații între variabilele de decizie și parametrii. Pentru o problemă de producție, nu are sens să petreci mult timp pe orice activitate, așa că limitează toate variabilele „temporale”.
- Soluții posibile și optime. Valoarea deciziei pentru variabile, sub care toate constrângerile sunt satisfăcute, se numește satisfăcătoare. Majoritatea algoritmilor îl găsesc mai întâi, apoi încearcă să îl îmbunătățească. În cele din urmă, schimbă variabilele pentru a trece de la o soluție fezabilă la alta. Acest proces se repetă până când funcția obiectiv atinge maximum sau minim. Acest rezultat se numește soluția optimă.
Algoritmii de probleme de optimizare dezvoltați pentru următoarele programe matematice sunt utilizați pe scară largă:
- Convex.
- Separabil.
- Cuadratic.
- Geometric.
Rezolvatori liniari Google
Optimizare liniară sau programare este numele dat procesului de calcul al rezolvării optime a unei probleme. Este modelat ca un set de relații liniare care apar în multe discipline științifice și de inginerie.
Google oferă trei moduri de a rezolva problemele de optimizare liniară:
- Glop bibliotecă open source.
- Supliment de optimizare liniară pentru Foi de calcul Google.
- Serviciul de optimizare liniară în Google Apps Script.
Glop este integrat în Googlerezolvator liniar. Este disponibil în sursă deschisă. Puteți accesa Glop prin pachetul de soluționare liniară OR-Tools, care este un pachet pentru Glop.
Modulul de optimizare liniară pentru Foi de calcul Google vă permite să efectuați o declarație liniară a problemei de optimizare prin introducerea datelor într-o foaie de calcul.
Programare cadranică
Platforma Premium Solver folosește o versiune extinsă LP/Quadratic a metodei Simplex cu limite de procesare a problemelor LP și QP de până la 2000 de variabile de decizie.
SQP Solver pentru probleme la scară mare folosește o implementare modernă a metodei seturilor active cu rarefiate pentru a rezolva probleme de programare pătratică (QP). Motorul XPRESS Solver utilizează o extensie naturală a metodei „Punctul interior” sau Newton Barrier pentru a rezolva problemele QP.
MOSEK Solver aplică metode „Inside Point” încorporate și automate duale. Acest lucru este eficient în special pentru problemele QP slab cuplate. De asemenea, poate rezolva problemele de constrângere cuadratică la scară (QCP) și de programare a conurilor de ordinul al doilea (SOCP).
Calcule cu mai multe operații
Sunt folosite destul de cu succes cu utilizarea caracteristicilor Microsoft Office, de exemplu, rezolvarea problemelor de optimizare în Excel.
În tabelul de mai sus, simbolurile sunt:
- K1 - K6 - clienți care trebuie să furnizeze bunuri.
- S1 - S6 sunt potențiale site-uri de producție care ar putea fi construite pentru asta. Poate fi creat1, 2, 3, 4, 5 sau toate cele 6 locații.
Există costuri fixe pentru fiecare facilitate enumerată în coloana I (Remediere).
Dacă locația nu schimbă nimic, nu va conta. Atunci nu vor exista costuri fixe.
Identificați locațiile potențiale pentru a obține cel mai mic cost.
În aceste condiții, locația este fie stabilită, fie nu. Aceste două stări sunt: „adevărat – fals” sau „1 - 0”. Există șase stări pentru șase locații, de exemplu, 000001 este setat doar la a șasea, 111111 este setat la toate.
În sistemul de numere binar, există exact 63 de opțiuni diferite de la 000001 (1) la 111111 (63).
L2-L64 ar trebui să citească acum {=OPERAȚII MULTIPLE (K1)}, acestea sunt rezultatele tuturor soluțiilor alternative. Atunci valoarea minimă este=Min (L) și alternativa corespunzătoare este INDEX (K).
Programare cu numere întregi CPLEX
Uneori, o relație liniară nu este suficientă pentru a ajunge în miezul unei probleme de afaceri. Acest lucru este valabil mai ales atunci când deciziile implică alegeri discrete, cum ar fi deschiderea sau nu a unui depozit într-o anumită locație. În aceste situații, trebuie utilizată programarea cu numere întregi.
Dacă problema implică atât alegeri discrete, cât și continue, este un program cu numere întregi mixte. Poate avea probleme patratice liniare, convexe și aceleași constrângeri de ordinul doi.
Programele cu numere întregi sunt mult mai complexe decât programele liniare, dar au aplicații importante de afaceri. SoftwareSoftware-ul CPLEX utilizează metode matematice complexe pentru a rezolva probleme cu numere întregi. Metodele sale implică căutarea sistematică a posibilelor combinații de variabile discrete folosind relaxări software liniare sau pătratice pentru a calcula limitele valorii soluției optime.
De asemenea, folosesc LP și alte metode de rezolvare a problemelor de optimizare pentru a calcula constrângeri.
Solutor standard Microsoft Excel
Această tehnologie folosește implementarea de bază a metodei principale Simplex pentru a rezolva problemele LP. Este limitat la 200 de variabile. „Premium Solver” folosește o metodă simplex primară îmbunătățită, cu limite cu două fețe pentru variabile. Platforma Premium Solver folosește o versiune extinsă a LP/Quadratic Simplex Solver pentru a rezolva o problemă de optimizare cu până la 2000 de variabile de decizie.
Large-scale LP pentru platforma Premium Solver aplică o implementare de ultimă generație a metodei simplex și duble simplex, care utilizează dispersitatea în modelul LP pentru a economisi timp și memorie, strategii avansate de actualizare și matrici de refactorizare, prețuri multiple și parțiale și rotații și pentru depășirea degenerării. Acest motor este disponibil în trei versiuni (capabil să gestioneze până la 8.000, 32.000 sau variabile și limite nelimitate).
MOSEK Solver include primar și dual simplex, o metodă care exploatează, de asemenea, sparsitatea și utilizează strategii avansate pentru actualizarea matricei și „refactorizare”. Rezolvă probleme de dimensiuni nelimitate, a fosttestat pe probleme de programare liniară cu milioane de variabile de decizie.
Exemplu pas cu pas în EXCEL
Pentru a defini modelul problemei de optimizare în Excel, efectuați următorii pași:
- Organizați datele pentru problemă într-o foaie de calcul într-o formă logică.
- Selectați o celulă pentru a stoca fiecare variabilă.
- Creați în celulă o formulă pentru calcularea modelului matematic țintă al problemei de optimizare.
- Creați formule pentru a calcula partea stângă a fiecărei constrângeri.
- Utilizați casetele de dialog în Excel pentru a spune Solver despre variabilele de decizie, obiectivele, constrângerile și limitele dorite ale acelor parametri.
- Rulați „Solver” pentru a găsi soluția optimă.
- Creați o foaie Excel.
- Organizați datele pentru problema în Excel unde se calculează formula funcției și constrângerii obiectiv.
În tabelul de mai sus, celulele B4, C4, D4 și E4 au fost rezervate pentru a reprezenta variabilele de decizie X 1, X 2, X 3 și X 4. Exemple de decizie:
- Modelul mix de produse (450 USD, 1150 USD, 800 USD și 400 USD profit per produs) a fost introdus în celulele B5, C5, D5 și, respectiv, E5. Acest lucru permite ținta să fie calculată în F5=B5B4 + C5C4 + D5D4 + E5E4 sau F5:=SUMPRODUS (B5: E5, B4: E4).
- În B8 introduceți cantitatea de resurse necesare pentru fabricarea fiecărui tip de produs.
- Formulă pentru F8:=SUMAPRODUS(B8:E8, $B$4:$E$4).
- Copiați acest lucruformula în F9. Semnele dolarului în $B$4:$E$4 indică faptul că acest interval de celule rămâne constant.
- În G8 introduceți cantitatea disponibilă de resurse de fiecare tip, corespunzătoare valorilor restricțiilor din dreapta. Acest lucru vă permite să le exprimați astfel: F11<=G8: G11.
- Acest lucru este echivalent cu patru limite F8<=G8, F9 <=G9, F10 <=G10 și F11=0
Domenii de aplicare practică a metodei
Optimizarea liniară are multe aplicații practice ca exemplu de problemă de optimizare:
O companie poate realiza mai multe produse cu o marjă de contribuție cunoscută. Producția unei unități din fiecare articol necesită o cantitate cunoscută de resurse limitate. Sarcina este de a crea un program de producție pentru a determina cât de mult din fiecare produs ar trebui să fie produs, astfel încât profitul companiei să fie maximizat fără a încălca constrângerile de resurse.
Problemele de amestecare sunt soluția la problemele de optimizare legate de combinarea ingredientelor în produsul final. Un exemplu în acest sens este problema dietei studiată de George Danzig în 1947. Sunt oferite o serie de materii prime, cum ar fi ovăz, carne de porc și ulei de floarea soarelui, împreună cu conținutul lor nutrițional, precum proteine, grăsimi, vitamina A și prețul lor pe kilogram. Provocarea este de a amesteca unul sau mai multe produse finite din materii prime la cel mai mic cost posibil, respectând în același timp limitele minime și maxime ale valorii lor nutriționale.
O aplicație clasică a unei probleme de optimizare liniară este de a determina rutarea pentru nevoitrafic în rețelele de telecomunicații sau de transport. În același timp, fluxurile trebuie direcționate prin rețea în așa fel încât toate cerințele de trafic să fie îndeplinite fără a încălca condițiile de lățime de bandă.
În teoria matematică, optimizarea liniară poate fi folosită pentru a calcula strategii optime în jocuri cu sumă zero pentru două persoane. În acest caz, se calculează distribuția de probabilitate pentru fiecare participant, care este coeficientul de amestecare aleatorie a strategiilor sale.
Niciun proces de afaceri de succes în lume nu este posibil fără optimizare. Există mulți algoritmi de optimizare disponibili. Unele metode sunt potrivite doar pentru anumite tipuri de probleme. Este important să le poți recunoaște caracteristicile și să selectezi metoda de soluție adecvată.
