Obiective de optimizare: concept, metode de soluționare și clasificare

Optimizarea ajută la găsirea celui mai bun rezultat, care aduce profit, reduce costurile sau stabilește un parametru care determină eșecul proceselor de afaceri.

Acest proces se mai numește și programare matematică. Rezolvă problema determinării alocării resurselor constrânse necesare pentru atingerea obiectivului stabilit de managerul unei probleme de optimizare. Dintre toate opțiunile posibile, este de dorit să o găsim pe cea care maximizează (sau reduce) parametrul de control, de exemplu, profitul sau costul. Modelele de optimizare se mai numesc și prescriptive sau normative, deoarece caută să găsească o strategie posibilă pentru o afacere.

Istoria dezvoltării

Programarea liniară (LP) se ocupă cu o clasă de probleme de optimizare în care toate constrângerile sunt liniare.

Prezintă un scurt istoric al dezvoltării LP:

• În 1762, Lagrange a rezolvat probleme simple de optimizare cu constrângeri de egalitate.
• În 1820, Gauss a rezolvat un sistem liniar de ecuații folosind excluderea.
• În 1866, William Jordan a perfecționat metoda de găsire a erorilor celor mai mici pătrate ca un criteriu pentru. Acum se numește prin metoda Gauss-Iordania .
• În 1945, a apărut calculatorul digital.
• În 1947, Danzig a inventat metodele simplex.
• În 1968, Fiacco și McCormick au introdus metoda Inner Point.
• În 1984, Carmarkar a aplicat metoda interioară pentru a rezolva programe liniare, adăugând inovația sa.

LP s-a dovedit a fi un instrument extrem de puternic, atât pentru modelarea problemelor din lumea reală, cât și ca o teorie matematică aplicată pe scară largă. Cu toate acestea, multe probleme de optimizare interesante sunt neliniare.

Ce trebuie făcut în acest caz? Studiul unor astfel de probleme implică un amestec divers 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 seturilor ș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 ingineria, analiza regresiei, managementul stocurilor, cercetarea geofizică și economia.

Clasificarea problemelor de optimizare

O etapă importantă în procesul de optimizare este clasificarea modelelor, deoarece algoritmii acestora sunt adaptați la un anumit tip de.

1. Probleme de optimizare discrete și continue. Unele modele au sens doar dacă variabilele iau valori dintr-un subset discret de numere întregi. Altele conțin date care pot lua orice valoare reală. Acestea tind să fie mai ușor de rezolvat. Îmbunătățirea algoritmilor, combinată cu progresele în domeniul informaticii, a crescut dramatic dimensiunea și complexitatea problemei de optimizare programare liniară.

2. Optimizare fără constrângeri și cu constrângeri. O altă distincție importantă este între problemele în care nu există nici o constrângere asupra variabilelor. Acestea pot varia foarte mult, de la simple estimări la sisteme de ecuații ș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. Probleme de fezabilitate. Obiectivul lor este de a găsi valori ale variabilelor care să satisfacă constrângerile modelului, fără un obiectiv de optimizare special.

4. Probleme de complementaritate. Acestea sunt frecvente în inginerie și economie. Scopul este de a găsi o soluție care să satisfacă condițiile de adiționalitate. În practică, problemele cu obiective multiple sunt adesea reformulate în probleme cu un singur obiectiv.

5. Optimizare deterministă versus optimizare stocastică. În optimizarea deterministă, se presupune că datele problemei sunt perfect exacte. Cu toate acestea, pentru multe aspecte relevante, acestea nu pot fi cunoscute din mai multe motive.

Prima are de-a face cu o simplă eroare de măsurare. Al doilea motiv este mai fundamental. Acest lucru se datorează faptului că unele date reprezintă informații despre viitor, cum ar fi cererea pentru un produs sau prețul pentru o perioadă de timp viitoare. În cazul optimizării în condiții de optimizare stocastică, incertitudinea este inclusă în model.

Componente de bază

O funcție țintă este o funcție care trebuie minimizată sau maximizată. Cele mai multe tipuri de probleme de optimizare au o funcție obiectiv. În caz contrar, acestea pot fi adesea reformulate astfel încât să poată fi.

Două excepții de la această regulă:

1. Problema de căutare a țintei. În majoritatea aplicațiilor de afaceri, managerul dorește să atingă un obiectiv specific, satisfăcând în același timp constrângerile modelului. Utilizatorul nu dorește în mod special să optimizeze ceva, așa că nu are rost să definească o funcție țintă. Acest tip de este denumită de obicei o problemă de fezabilitate.

2. Un set de funcții obiective. Adesea, utilizatorul ar dori să optimizeze mai multe obiective diferite în același timp. Acestea sunt de obicei incompatibile. Variabilele care optimizează un singur obiectiv pot fi departe de a fi cel mai bun pentru alții.

Tipuri de componente:

• Intrările controlate sunt setul de variabile de decizie care afectează valoarea funcției țintă. Într-o problemă de producție, variabilele pot include alocarea diferitelor resurse disponibile sau forța de muncă necesară pentru fiecare activitate.
• Constrângerile sunt relații între variabilele de decizie și parametri. Nu are sens ca o problemă de producție să petreacă o cantitate mare de timp pentru orice activitate, așa că limitați toate variabilele "timp".
• Soluții posibile și optime. Valoarea soluției pentru variabile, în care toate constrângerile sunt satisfăcute, se numește fezabilă. Majoritatea algoritmilor o găsesc mai întâi, apoi încearcă să o îmbunătățească. În cele din urmă, ei schimbă variabilele pentru a trece de la o soluție fezabilă la alta. Acest proces se repetă până când funcția țintă atinge maximul sau minimul. Acest rezultat se numește o soluție optimă.

Algoritmii de optimizare dezvoltați pentru următoarele programe matematice sunt utilizați pe scară largă:

• Convex.
• Divizibil.
• Cuadratură.
• Geometric.

Solutori liniari Google

Optimizarea sau programarea liniară este denumirea dată procesului de calcul pentru rezolvarea optimă a unei probleme. Este modelat ca un set de relații liniare care apar în multe discipline științifice și inginerești.

Google sugerează trei moduri Soluții de optimizare liniară:

• Biblioteca open source Glop.
• Optimizare liniară add-on pentru Google Sheets.
• Serviciul de optimizare liniară în Google Apps Script.

Glop este rezolvatorul liniar încorporat de Google. Este disponibil ca sursă deschisă. Puteți accesa Glop prin intermediul pachetului de rezolvare liniară OR-Tools, care este un shell pentru Glop.

Modulul de optimizare liniară pentru Google Sheets permite realizarea formulării liniare a problemei de optimizare prin introducerea datelor într-o foaie de calcul.

Programarea pătratică

Platforma Premium Solver utilizează o versiune extinsă LP/Quadratic a metodei Simplex cu constrângeri de procesare a problemelor LP și QP de până la 2000 de soluții variabile.

SQP Solver pentru probleme la scară largă utilizează o implementare modernă a metodei Active Set Sparse pentru rezolvarea problemelor de programare pătratică (QP). XPRESS Solver utilizează o extensie naturală a metodei "Punct intern" sau Newton-Barrier la rezolvarea problemelor QP.

MOSEK Solver aplică metode de implementare "Punct intern" și autodual. Acest lucru este deosebit de eficient pentru problemele QP slab cuplate. Acesta poate rezolva, de asemenea, probleme de scalare a constrângerilor pătratice (QCP) și de programare a conurilor de ordinul al doilea (SOCP).

Calcule cu mai multe operații

Acestea sunt utilizate cu succes cu funcțiile Microsoft Office, de exemplu, rezolvarea problemelor de optimizare în Excel.

În tabelul de mai sus, se utilizează următoarele denumiri:

• K1 - K6 - clienți care urmează să fie aprovizionați.
• S1 - S6 sunt potențialele situri de producție care pot fi construite pentru această. Pot fi create 1,2,3,4,5 sau toate cele 6 locații.

Există costuri fixe pentru fiecare obiect, enumerate în coloana I (Fix).

Dacă locația nu schimbă nimic, nu va fi luată în considerare. În acest caz, nu există costuri fixe.

Determinați locațiile potențiale pentru a obține cel mai mic cost.

În aceste condiții, locația este fie setată, fie nu. Aceste două state sunt: "TRUE - FALSE" sau "1 - 0". Există șase stări pentru șase locații, de exemplu, pentru 000001 doar a șasea este setată, pentru 11111111 toate.

În notație binară există exact 63 de opțiuni diferite, de la 000001 (1) la 11111111 (63).

L2-L64 ar trebui să fie acum {= MULTIPLE OPERATION (K1)}, acestea sunt rezultatele tuturor soluțiilor alternative. Atunci valoarea minimă este = Min (L), iar alternativa corespunzătoare este INDEX (K).

Programarea în numere întregi CPLEX

Uneori, relațiile liniare nu sunt suficiente pentru a surprinde esența 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 folosită programarea cu numere întregi.

În cazul în care problema implică ca alegere discretă și continuă, este un program mixt de numere întregi. Poate avea probleme liniare, convexe pătratice și aceleași constrângeri de ordinul doi.

Programele întregi sunt mult mai complexe decât cele liniare, dar au aplicații importante în afaceri. Software-ul CPLEX utilizează metode matematice sofisticate pentru a rezolva probleme de numere întregi. Metodele sale implică o căutare 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, utilizează LP și alte metode de rezolvare a problemelor de optimizare pentru a calcula limitele.

Solver standard Microsoft Excel Solver

Această tehnică utilizează o implementare de bază a metodei Simplex de bază pentru a rezolva probleme LP. Este limitat la 200 de variabile. "Premium Solver" utilizează o metodă simplex primară îmbunătățită cu limite bilaterale pentru variabilele. Platforma Premium Solver utilizează o versiune extinsă a LP/Quadratic Simplex Solver pentru a rezolva o problemă de optimizare cu până la 2.000 de variabile de decizie.

Platforma LP la scară largă pentru Premium Solver aplică o implementare de ultimă generație a metodei Simplex și Dual Simplex, care utilizează sparsity în modelul LP pentru a economisi timp și memorie, strategii avansate pentru actualizări și refactorizări de matrice, prețuri și rotații multiple și parțiale și pentru a depăși degenerarea. Acest mecanism este disponibil în trei versiuni (cu posibilitatea de a gestiona până la 8.000, 32.000 sau un număr nelimitat de variabile și constrângeri).

MOSEK Solver include simplex primar și dual, o metodă care exploatează, de asemenea, sparsity și utilizează strategii avansate pentru actualizări de matrice și "refactorizare". Rezolvă probleme de dimensiuni nelimitate și a fost testat pe Sarcini de programare liniară Cu milioane de variabile de decizie.

Exemplu pas cu pas în EXCEL

Pentru a defini un model de problemă de optimizare în Excel, efectuați următorii pași:

• Organizarea datelor pentru o problemă într-o foaie de calcul, în mod într-o formă logică.
• Selectați celula pentru a stoca fiecare variabilă.
• Creați o formulă în celulă care calculează modelul matematic țintă al problemei de optimizare.
• să creeze formule pentru a calcula partea stângă a fiecărei constrângeri.
• Utilizați dialogurile din Excel pentru a comunica "Solver" cu privire la variabilele de decizie, obiectivele, constrângerile și limitele dorite a acestor parametri.
• Rulați "Solver", pentru a găsi o soluție optimă.
• Creați o foaie Excel.
• Aranjați datele problemei în Excel, unde se calculează formulele pentru funcția obiectiv și pentru constrângere.

În tabelul de mai sus, celulele B4, C4, D4 și E4 sunt rezervate pentru a reprezenta variabilele luarea deciziilor X 1, X 2, X 3 și X 4. Exemple de soluții:

• Modelul gamei de produse (profituri pentru fiecare tip de produs 450 $, 1 150 $, 800 $ și 400 $) a fost introdus în celulele B5, C5, D5 și, respectiv, E5. Se calculează ținta în F5 = B5 * B4 + C5 * C4 + D5 * D4 + E5 * E4 sau F5: = SUMPRODUCT (B5: E5, B4: E4).
• În B8 se introduce numărul de resurse, necesare pentru producția fiecărui tip de produs.
• Formula pentru F8: = SUMPRODUCT (B8: E8, $ B$4: $ E$4).
• Copiați această formulă în F9. Semnele de dolar din $ 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, care corespunde valorilor constrângerilor din dreapta. Aceasta le exprimă în felul următor: F11<= G8: G11.
• Acest lucru este echivalent cu cele patru constrângeri F8<= G8, F9 <= G9, F10 <= G10 și F11 <= G11. Puteți introduce acest set direct în fereastra de dialog Solver împreună cu condițiile de non-negativitate B4: E4> = 0

Domenii de aplicare practică a metodei

Optimizarea liniară are multe aplicații practice, fiind un exemplu de problemă de optimizare:

O companie poate realiza mai multe produse cu o marjă de contribuție cunoscută. Producerea unei unități din fiecare produs necesită o cantitate cunoscută de resurse finite. Provocarea este de a crea un program de producție pentru a determina cât de mult din fiecare produs ar trebui să fie produs într-un mod care să maximizeze profitul companiei fără a încălca constrângerile de resurse.

Problemele de amestecare sunt probleme de optimizare asociate cu combinarea ingredientelor într-un produs final. Un exemplu în acest sens este problema dietei studiată de George Danzig în 1947. Sunt prezentate o serie de materii prime, cum ar fi ovăzul, carnea de porc și uleiul de floarea-soarelui, împreună cu conținutul lor nutritiv, cum ar fi proteinele, grăsimile, vitamina A și prețul lor pe kilogram. Sarcina este de a amesteca unul sau mai multe produse finale din materii prime la cel mai mic cost posibil, cu respectarea următoarelor condiții minim și maxim limite pentru valoarea lor nutritivă.

O aplicație clasică a problemei de optimizare liniară este determinarea cerințelor de rutare a traficului în rețelele de telecomunicații sau de transport. În acest fel, fluxurile trebuie să fie rutate prin rețea astfel încât toate cerințele de trafic să fie îndeplinite fără a compromite condițiile de lățime de bandă.

În cadrul teoriei matematice, optimizarea liniară poate fi utilizată pentru a calcula strategiile optime în jocurile cu sumă nulă pentru două persoane. Astfel se calculează distribuția de probabilitate pentru fiecare participant, care este coeficientul de amestecare aleatorie a strategiilor lor.

Nici un proces de afaceri de succes din 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 recunoaștem caracteristicile și să alegem o metodă adecvată de abordare a acestora.