Rezolvarea problemelor de maxim/minim - probleme de Optimizare folosind programul SOLVER
1 .20.2. Probleme care conduc la programe lunare
Exemplul 1: Folosirea eficienta a resurselor
Avem la dispozitie mai multe resurse (materie prima, forta de munca, masini unelte, resurse financiare) care sunt date în cantitati limitate.
Notam cu:
i nr.ordine al resursei;
bi = cantitatea disponibila din resursa i
Cu aceste resurse se pot desfasura mai multe activitati (procese de productie).
j = nr. ordine al activitatii desfasurate sau al pr 646e414g odusului fabricat
xj = nivelul (necunoscut) la care trebuie sa se desfasoare actvitatea j; de exemplu fabricarea unui anumit produs j, deci xj va fi cantitatea care se va produce.
aij cantitatea din resursa i necesara pentru a produce o unitate din produsul j (activitatea j), adica consumul specific pe unitatea de produs; (aici aij depinde doar de tipul produsului si de resursa si nu de cantitatile produse).
Vom exprima câteva marimi:
aij xj = cantitatea de resursa i folosita pentru a produce cantitatea xj a produsului j;
ai1 * x1 + ai2 * x2 + .....ain * xn = cantitatea totala din resursa i folosita pentru a produce toate produsele în cantitatile x1, x2.......xn;
ai1 * x1 + ai2 * x2 + .....ain *xn ≤ bi - restrictia (consumul din resursa i trebuie sa fie mai mic decât disponibilului), cu i=1,m
restrictiile privind limita pentru fiecare resursa disponibila;
xj 0 restrictii de nenegativitate (4)
j = 1, n - cantitatea pe care o producem trebuie sa fie mai mare decât 0 .
Observatii:
i. inecuatiile (3) se numesc restrictiile problemei.
ii. inecuatiile (4) se numesc conditii de nenegativitate.
Notam cu:
cj = pretul de vânzare al unei unitati din produsul j;
dj = pretul de cost al unei unitati din produsul j.
venitul total
chelutieli de productie
beneficiul
= 
Problema care se pune:
xj ≥ 0 (j=1,n)
min
xj ≥ 0 (j=1,n)
max
xj ≥ 0
Probleme de programare liniara sau program liniar.
Exemplul 2
O întreprindere produce 3 tipuri de produse, notate cu j (j 1,3), de exemplu TV, boxe si microfoane, realizate prin asamblarea a 5 tipuri de componente, notate cu j ( 1,5), de exemplu sasiu, tub catodic, con de microfon, fir de alimentare, componta electronica.
Variabilele de decizie sunt cantitatile xj care se fabrica din fiecare produs. Se cunosc consumurile specifice aij, adica numarul de componente care intra în fiecare produs, profiturile Pj pe unitatea de produs j, stocurile disponibile Si pentru fiecare componenta i si exponentul de diminuare a venitului s (0.9).
Se cauta optimizarea productiei pentru a avea un profit maxim.
1.20.3. Rezolvarea cu EXCEL
Datele problemei se introduc în celulele foii de calcul, iar programul SOLVER foloseste 4 categorii:
cu functia obiectiv f (x1.........xn), m ≤ n (pe scurt, celula obiectiv - target cell);
cu variabilele independente sau altfel spus, de decizie (pe scurt, celule variabile - changing cells) (x1.........xm) (m ≤ 200) ce intervin în expresia functiei obiectiv;
cu variabilele dependente (xm .1.........xn) ce se exprima în functie de cele independente;
cu restrictiile (contraints) inferioare (>=) sau de egalitate (=) asupra celulelor de orice fel, sau de tip întreg (pentru cele cu variabilele).
Observatie:
i. se pot defini maximum doua restrictii pentru fiecare celula variabila si maximum 100 în rest.
Etapele rezolvarii:
Scrierea tabelelor cu datele problemei si cu relatiile lor;
Definirea si rezolvarea modelului problemei (cu ajutorul lui Solver);
Generarea si interpretarea rapoartelor predefinite (cu rezultatele optimizarii);
Reluarea datelor si rezultatelor sau a modelelor problemei.
Scrierea tabelelor cu datele problemei si relatiile lor
Se deschide un registru de lucru (worbook) nou (prin comanda File New) sau unul vechi (prin comanda File Open...).
Se denumeste foaia de lucru, se introduc si se aranjeaza datele si formulele într-un mod cât mai inteligibil (de preferinta, într-un singur tabel).
Se indica formatul elementelor tabelului (individual sau în totalitate), eventual cu ajutorul unor stiluri preformate sau al comenzii Format AutoFormat.
Se salveaza registrul prin comanda File Save sau File Save...Daca se doreste salvarea valorilor initiale ale problemei, se executa Tools Scenarios si se indica celule cu viitoarele variabile independente.
Fig. 1. Aranjarea datelor în foaia de calcul
Definirea si rezolvarea modelului problemei
2.1) Se executa comanda Tools Solver... si se indica în caseta Solver Parameters (figura 2) natura celulelor (cu functia obiectiv, cu variabilele de decizie), tipul optimizarii (minimizare, maximizare sau atingerea unei valori date a functiei obiectiv) si restrictiile.
Figura 2
Ultimele se pot adauga prin butonul Add si prin indicarea, în caseta Add Constraints (figura 3), a celulelor supuse restrictiilor, a naturii restrictiilor (≤, ≥ sau variabilele de tip întreg) si a valorii lor, se pot modifica prin butonul Change... si se pot înlatura prin butonul Delete. Referintele absolute si mixte se indica prin simbolul " Valorile implicite ale parametrilor se pot restabili cu ajutorul butonului Reset All. Celulele cu variabilele de decizie se pot determina automat cu ajutorul butonului Guess.
Fig. 3
2.2) Se indica, prin butonul Options... si caseta Solver Options (figura 4), modul de rezol,vare al problemei: durata maxima, numarul maxim de iteratii, precizia de satisfacere a valorii obiectiv si a restrictiilor (între 0 si 1), toleranta la rotunjirea variabilelor întregi, natura explicita a modelului (liniar sau nu), întreruperea sau nu a rezolvarii dupa fiecare iteratie (pentru aratarea rezultatelor partiale), scalarea sau nu a valorilor variabilelor (pentru înlaturarea diferentelor prea mari între ordinele de marime ale datelor), folosirea extrapolarii liniare (prin tangenta) sau patratice (pentru determinarea valorii initiale a variabilelor de decizie),folosirea diferentelor la dreapta sau centrate (pentru estimarea derivatelor partiale ale functiilor), folosirea metodei lui Newton sau a gradientului conjugat (pentru stabilirea directiei de cautare a optimului, la fiecare iteratie).
Fig. 4
2.3) Daca se doreste salvarea modelului si a modului de rezolvare (indicate anterior în casetele Solver Parameters si Solver Options), se apasa butonul Save Model..din caseta Solver Options, indicându-se apoi numele modelului si zona din foaia de lucru în care va fi salvat automat. Zona este formata din minimum 3 celule aranjate pe verticala, ce contin functia obiectiv, celulele variabile si optiunile de executie pentru Solver, la care se mai adauga câte o celula pentru fiecare restrictie. Daca sunt mai multe modele în aceeasi foaie, se recomanda scrierea unui test de identificare pentru fiecare zona.
2.4) Se trece la rezolvarea problemei, prin apasarea butonului Solve din caseta Solver Parameters. Rezolvarea se face prin iteratii. La fiecare iteratie, Solver foloseste (pentru recalcularea foii) un nou set de valori pentru celulele cu variabile, examinându-se restrictiile si valoarea functiei obiectiv. Iteratiile se opresc atunci când:
s-a gasit o solutie cu o precizie acceptabila
sau
nu mai este posibil nici un progres în calcule
sau
s-a efectuat numarul de iteratii indicat ori s-a scurs timpul de calculat alocat.
În primul caz, daca toate restrictiile si conditiile de optimalitate sunt satisfacute cu toleranta si precizia indicate, este afisat mesajul "Solver found a solution", iar daca toate restrictiile sunt satisfacute, dar (din diferite motive) nu s-a gasit o solutie optima (ci doar una posibila), este afisat mesajul "Solver converged to the current solution".
Dupa ce rezolvarea s-a terminat, Excel afiseaza un mesaj cu urmatoarele optiuni de continuare:
se pastreaza solutia gasita de Solver;
se restabilesc valorile originale din model;
se salveaza solutia ca un scenariu (apasând butonul Save Scenario) si indicând numele scenariuului în caseta de dialog ce apare;
se genereaza unul sau mai multe din cele 3 rapoarte predefinite ale lui Solver.
3) Generarea si interpretarea rapoartelor predefinite
3.1) Se selecteaza rapoartele dorite din caseta cu numele lor (Answer, Sensibility, Limits) - fig. 5; rapoartele se genereaza automat ca niste foi de lucru ale registrului, la apasarea butonului OK.
Fig. 5
3.2) Se alege foaia de lucru cu numele raportului dorit; drept urmare, continutul acesteia este afisat pe ecran.
Raportul de raspuns (figura 6) contine: valoarea finala a celulei obiecitv, pentru fiecare cleula variabila - valoarea initiala si finala, iar pentru fiecare restrictie - valoarea ei, formula, starea (de "lipire" sau de "ne-lipire", dupa cum valoarea finala a celulei este egala sau nu cu valoarea initiala a restrictiei) si diferenta dintre valoarea finala si cea initiala a restrictiei.
Fig. 6
Raportul de sensibilitate difera în raport de tipul modelului (liniar sau neliniar). Pentru modelele liniare, raportul (figura 6) cuprinde, pentru fiecare celula variabila: valoarea finala (în solutia gasita), costul redus (cresterea în celula obiectiv, datorita cresterii cu o unitate a celulei variabile), coeficientul obiectivului (raportul dintre valoarea finala a celulei obiectiv si cea a variabilei), cresterea si descresterea permise (schimbarea în coeficientul obiectiv, înainte de cresterea / descresterea în valoarea optima a oricarei variabile de decizie); pentru fiecare restrictie: pretul umbra (cresterea în celula obiectiv datorita cresterii cu o unitate în partea dreapta a restrictiei), partea dreapta (right hand - R.H.) a restrictiei (valoarea atribuita initial), cresterea si descresterea permise (schimbarea în partea dreapta a restrictiei, înainte de cresterea / descresterea în valoarea optima a oricarei variabile de decizie). Pentru modele neliniare, raportul cuprinde, pentru fiecare celula variabila, gradientul redus (corespondentul costului redus de la modelele liniare), iar pentru fiecare restrictie - multiplicatorul Lagrange (corespondentul pretului umbra).
Raportul despre limita (figura 7) contine valoarea celulei obiectiv si, pentru fiecare variabila de decizie: valoarea finala, limita inferioaa si superioara (cea mai mica, respectiv cea mai mare valoare posibila a ei, când toate celelalte variabile de deicizie sunt fixe si împreuna satisfac totusi restrictiile) si rezulattele din obiectiv (valorile functiei obiectiv) corespunzatoare acestor limite.
Fig. 7
4) Reluarea datelor si rezultatelor sau a modelelor problemei
Datele initiale ale problemei, respectiv rezultatele ei (salvate ca scenariu, înainte de, respectiv dupa rezolvarea ei) se pot afisa prin executarea comenzii Tools/Scenarios....Modelele problemei (salvate înaintea rezolvarii ei), se pot reexecuta (eventual, redefinite) ajutorul butonului Load Model... din caseta Solver Options, prin indicarea zonei de salvare anterioara.
|
