SIAD Seminar 1 Modele – optimizarea Optimizarea cu ajutorul unui algoritm – programare matematică Programarea matematică reprezintă un set de metode… [620511]

SIAD Seminar 1 Modele – optimizarea Optimizarea cu ajutorul unui algoritm – programare matematică Programarea matematică reprezintă un set de metode și instrumente pentru rezolvarea problemelor manageriale în care decidentul trebuie să aloce o cantitate limitată de resurse mai multor activități în scopul optimizării valorii unui obiectiv (măsurabil). Cea mai cunoscută și des utilizată metodă o reprezintă programarea liniară care presupune: • un set de elemente măsurabile, valori pentru care se caută valoarea optimă – variabilele de decizie; • un set de restricții asupra acestor variabile, care sunt reprezentate sub forma unor relații (de egalitate sau inegalitate față de anumite valori) liniare – de exemplu, într-o problemă de alocare a resurselor, cantitatea acestora este limitată; • o funcție obiectiv – o relație matematică liniară între variabilele de decizie și scopul urmărit – a cărei valoare trebuie maximizată (mărimea profitului, de exemplu) sau minimizată (nivelul costurilor, de exemplu); • existența unor legături între toate aceste elemente, reprezentate prin relații matematice (ecuații) în care intervin coeficienți în cadrul modelului de programare liniară Modelul unei probleme de programare liniară se reprezintă astfel: • determinarea min (max) unei funcții obiectiv de una sau mai multe variabile ale cărei valori trebuie sa satisfacă o mulțime (posibil vidă) de condiții implicite (ce apar sub forma unor ecuații și/sau inecuații numite restricții) sau explicite (condiții care se referă la felul valorilor pe care le pot lua variabilele). • problemele de programare matematică sunt caracterizate de prezența restricțiilor “inegalităti “ și a condițiilor explicite impuse cel puțin unora dintre variabile. Deosebim : – probleme de programare liniară (relații liniare intre variabile). Rezolvarea acestora se bazează pe algoritmul Simplex (G.B.Dantzing 1947) care oferă o soluție optimă într-un număr finit de pași. – probleme de programare neliniară (există cel puțin o relație neliniară între variabile). Metodele de rezolvare a acestor probleme oferă doar o aproximare a soluției optime și se pot clasifica în: metode de tip Simplex, metode provenite din programarea dinamica, metode gradient.

Forma generala a modelului de programare liniara este: (1) max (min) f(x1,x2,…….,xn) = c1x1 + c2x2 +………cnxn (2) (1) funcția obiectiv (2) restricții Forma standard : toate restricțiile sunt ecuații și toate variabilele sunt >=0 Forma canonica : toate restricțiile sunt concordante și toate variabilele sunt >=0 Aceste probleme se rezolvă cu ajutorul unui algoritm – algoritmul SIMPLEX (Dantzing 1951)– care constituie o procedură iterativă, la fiecare pas obținându-se o îmbunătățire a soluției, oferind în final: – soluția admisibilă (satisface doar condițiile explicite) SAU – soluția optimă Există programe standard pentru rezolvarea problemelor de programare liniară (de exemplu, în EXCEL, componenta SOLVER). axaxanxnbaxaxanxnbamxamxamnxnbm11112211211222221122+++£+++³+++£ìíïïïïîïïïï…………………………………………………………………….max(min) f(x) = cx Ax = B x >=0 max f(x) = cx Ax <= B x>=0 min f(x) =cx Ax >=B x >=0

Problema 1 O companie producatoare de echipamente (4 tipuri de produse) doreste sa-si eficientizeze planul de productie in luna urmatoare. Datele referitoare la costurile cu materiile prime, resursa umana si cererea pentru produsele respective sunt cele din tabelele de mai jos. Date de intrare salariu orar 8 cost unitar m1 0.5 cost unitar m2 0.75 produse p1 p2 p3 p4 ore munca/p 2 1 3 2 m1/p 4 2 1 2 m2/p 6 2 1 2 pret vanzare/p 28.5 12.5 29.25 21.5 Plan de productie p1 p2 p3 p4 cerere 1000 2000 500 1000 utilizat disponibil ore munca 4000 m1 6000 m2 10000 Determinati planul optim de productie Problema 2. În următoarele 4 luni, o companie producătoare de încălțăminte va trebui să satisfacă următoarele cereri de perechi de pantofi: 3000 în luna 1, 5000 în luna 2, 3000 în luna 3 și

1000 în luna 4. La începutul primei luni există 500 de perechi de pantofi în stociar firma are 1000 de muncitori. Fiecare muncitor este plătit cu 1500$ pe lună pentru un timp de ucru de 160 de ore. Un muncitor poate presta până la 20 de ore suplimentare pe lună, fiind plătit cu 13$ pentru fiecare oră suplimentară. Pentru a produce o pereche de pantofi, sunt necesare 4 ore și materii prime în valoare de 15$. La începutul fiecărei luni se pot angaja sau concedia muncitori. Costurile fixe pentru concedierea unui muncitor sunt de 2000$ iar pentru angajare de 1600$. La sfârșitul fiecărei luni, pentru fiecare pereche cheltuielile de stocare sunt de 3$. Se pornește de la premisa că producția unei luni se va utiliza pentru satisfacerea cererii acelei luni, iar prețul de vânzare va fi constant pentru cele 4 luni. a). Se dorește determinarea prgramului de angajări/cincedieri și producție care să minimizeze costurile totale în cele 4 luni. b) Sa se modifice modelul de la punctul a) pentru situatia in care este permisa reprogramarea – cererea poate fi satisfacuta mai tarziu decat apare. In acest caz, costul unitar la sfarsitul fiecarei luni pentru fiecare produs cerut dar nelivrat este de 20$ (se presupune ca stocul final poate fi negativ).