 |
|
 |  |
|
|
| |
 | Biologie | Chimie | Didactica | Fizica | Geografie | Informatica |
| Istorie | Literatura | Matematica | Psihologie |
Metode si instrumente de management industrialMaster ML +IMFP
Tema 2.3
Programarea liniara in numere intregi
In modelarea unor probleme economice, este uneori necesar ca variabilele de decizie sa fie numere intregi nenegative. Astfel de probleme le intalnim in literatura de specialitate sub numele de Integer Linear Programming (ILP).
Modelele de tipul ILP sunt folosite in management pentru rezolvarea problemelor care nu accepta o parte fractionara a valorilor optime (numar de oameni, numar de masini etc) sau pentru optimizarea deciziilor de tipul da/nu sau actioneaza/nu actiona, caz in care variabilele de decizie pot lua doar doua valori: 1 pentru "da/actioneaza" si 0 pentru "nu/nu actiona".
Pentru determinarea solutiei optime in numere intregi exista mai multe metode, printre care metoda "Branch and Bound", in traducere "Ramifica si margineste", utilizata si in programele pe calculator.
In principiu, metoda "Branch and Bound" ramifica, adica partitioneaza (imparte) multimea solutiilor admisibile in parti mai mici apoi margineste adica optimizeaza functia obiectiv pe fiecare dintre partile rezultate. Unele dintre aceste parti sunt ramificate si marginite in continuare; altele nu sunt ramificate, deoarece se poate constata usor ca nu pot contine solutia optima. Ideea metodei este de a gasi solutia optima fara a inspecta toate solutiile admisibile ale problemei.
In toate etapele de rezolvare, solutia optima se gaseste utilizand algoritmul simplex.
Pentru a intelege principiul de lucru al metodei, se considera urmatorul model matematic, a carui solutie optima trebuie determinata in numere intregi si pozitive:
x1 =
9,5; x2 = 1,25; max f(x) = 33,5 care nu este in numere intregi.
Prin aplicarea
algoritmului simplex, rezulta solutia (cu xi 0) optima:
Se
observa ca
, deci pentru ca 
sa fie intreg trebuie ca 
Se ramifica problema data, rezultand alte doua probleme:
Problema 2
x1 = 9;
x2 = 1,5; max f(x) = 33.
care are solutia optima:
Problema 3
care are solutia optima: x =
10; x 0,5; max f(x) = 32.
Nici problema 2, nici problema 3 nu au solutii optime
in numere intregi, asa ca ramificarea continua. Din problema 2
rezulta alte doua probleme, problema 4 si problema 5, deoarece
si pentru ca sa fie intrg 
Problema 4
a carei solutie optima este: x =
9, x = 1, maxf(x) = 31.
Problema 4 are solutia optima in numere intregi, dar aceasta solutie poate sa nu fie optima pentru problema initiala, daca exista si alte solutii, pentru care functia obiectiv are o valoare mai mare.
Problema
5
intregi, mai buna decat a problemei 4.
cu solutia optima: x = 8, x = 2, max f(x) = 32,
solutie in numere
Similar,
din problema 3 pot decurge alte doua probleme, deoarece 
Problema 6
cu
solutia: x = 10,33; x = 0; max f(x) = 31, care nu este in numere intregi.
Problema 7
care nu are
solutie.
Rezulta ca solutia optima a problemei date este solutia problemei 5.
O reprezentare sugestiva a principiului de lucru a metodei "Branch and Bound" este cea a unui arbore cu ramuri (fig. 1).
Fig.1
O firma utilizeaza patru procese tehnologice pentru realizarea a doua produse A si B: primele doua procese pentru produsul A, iar ultimile doua procese pentru produsul B. In fiecare proces tehnologic se folosesc trei resurse: R1 - forta de munca, R2 - un material M1 (kg), R3 - un material M2 (cutii), conform tabelului de mai jos, unde se dau consumurile specifice, cantitatile disponibile si beneficiile unitare.
|
Produs A |
Produs B |
Disponibil |
|||
|
Proces P1 |
Proces P2 |
Proces P3 |
Proces P4 |
||
|
R1 | |||||
|
R2 |
| ||||
|
R3 | |||||
|
Beneficiul unitar | |||||
Sa se stabileasca planul de productie, astfel incat beneficiul total sa fie maxim.
Stabilim
drept variabile de decizie,
notate cu 
numarul proceselor tehnologice de fiecare tip ce vor fi
folosite pentru obtinerea beneficiului total maxim, urmand ca prin
insumarea corespunzatoare a acestora sa se determine numarul de
produse A si B necesar sa se realizeze. Evident, necunoscutele de
decizie trebuie sa fie numere intregi.
Restrictiile problemei sunt date de cantitatile disponibile de resurse avute la dispozitie, iar functia obiectiv inseamna maximizarea beneficiului total realizat pe seama beneficiilor unitare aduse de fiecare proces tehnologic aplicat pentru realizarea, in conditiile date, a celor doua produse.
Modelul matematic este:
Rezolvarea problemei cu produsul software WinQSB - modulul Linear and Integer Programming incepe prin specificarea parametrilor problemei de rezolvat: numarul de variabile si de restrictii ( respectiv 4 si 3), criteriul pentru functia obiectiv (maximizare) tipul variabilelor (nenegative intregi) si modul in care vor fi introduse datele problemei (matricial sau normal) in fereastra de dialog deschisa prin selectarea optiunii File→New
Pentru optiunea Spreadsheet Matrix Form introducere datelor problemei sub forma matriciala se completeaza tabloul oferit de program cu coeficientii functiei obiectiv si termenii liberi ai restrictiilor.
Se poate obtine direct solutia finala, prin selectarea optiunii Solve the Problem din meniul Solve and Analyze sau se pot vizualiza pasii parcursi in rezolvarea problemei - optiunea Solve and Display Steps din acelasi meniu. In cazul in care exista o solutie optima se va afisa un raport al acesteia, in caz contrar programul face o analiza a variabilelor si restrictiilor problemei.
Problema din exemplul luat are o solutia optima prezentata in rezumat in Solution Summary din meniul Results
Rezulta ca pentru fabricarea produsului A se utilizeaza atat procesul tehnologic 1, x = 5, cat si procesul tehnologic 2, x = 3, rezultand 8 unitati de produs A realizate. Pentru produsul B, se foloseste numai procesul tehnologic 3, x = 7 (x = 0), rezultand 7 unitati de produs B. Numai in aceste conditii, beneficiul total obtinut din vanzarea produselor este maxim, egal cu 98 u.m.
Raportul final al problemei, afisat prin selectarea optiunii Solve the Problem serveste la realizarea analizei de senzitivitate indicand costurile reduse, preturile umbra, intervalele de variatie ale parametrilor problemei pentru ca solutia de baza, primala sau duala, sa ramana optima.
Exista patru proiecte ce se vor derula pe perioada a trei ani consecutivi, avand fiecare urmatoarele caracteristici:
|
Venituri returnate pe proiecte |
Cereri de capital pe ani si proiecte |
|||
|
Proiect |
Venit |
Anul de derulare |
||
|
I |
II |
III |
||
|
|
||||
|
Capital total disponibil | ||||
Se cere sa se stabileasca ce proiecte vor fi alese pentru a maximiza venitul final total rezultat in urma derularii acestora
Rezolvare
Se observa ca solutia problemei nu poate avea parte fractionara, in plus va trebui sa raspunda la intrebarea: care proiecte vor fi alese spre executie si care nu, astfel incat obiectivul problemei sa fie atins. Variabilele de decizie xj , sunt variabile binare cu urmatoarele valori:
xj = 1, daca se decide executarea proiectului j = 1,2,3,4;
xj = 0, daca se decide ca proiectul sa nu se execute.
Restrictiile problemei sunt impuse de capitalul disponibil in fiecare an si sunt urmatoarele :
Functia obiectiv este maximizarea venitului total posibil de obtinut din proiecte:
Rezolvarea problemei cu produsul software WinQSB presupune incarcarea datelor problemei prin intermediul unor formulare asigurate de program. Se definesc mai intai parametrii problemei:
Se scrie apoi modelul matematic al problemei (in forma aleasa - normala sau matriciala) forma matriciala insemnand completarea tabloului de date oferit de program cu coeficientii functiei obiectiv si termenii liberi ai restrictiilor.
Rezolvarea problemei se face utilizand metoda Branch and Bound, solutia optima fiind
Decizia propusa este de a alege spre executie numai proiectele 3 si 4, pentru ca oricare alta alegere ar determina obtinerea unui venit total inferior cifrei de 600 u.m. sau nu ar respecta restrictiile impuse.
Probleme propuse spre rezolvare
Firma
Boxcar
Burger doreste sa mareasca
numarul restaurantelor sale de tip fast - food, atat in zona
|
Mediul rural |
Mediul urban |
|
|
Investitia necesara locatie [u.m.] | ||
|
Numar necesar de personal / locatie | ||
|
Profit estimat/locatie [u.m.] |
Strategia firmei impune, in plus, urmatoarele conditii :
personalul angajat nu trebuie sa depaseasca 19 persoane ;
cel putin doua locatii trebuie deschise in mediul urban ;
totalul investitiei nu trebuie sa depaseasca 2.700 u.m.;
investitia din mediul rural trebuie sa fie de cel putin 1000 u.m.
S.C. Electronic Combinations S.A. produce sisteme radio portabile si are patru canale de distributie posibile pentru un nou produs :
Distribuitori de echipamente de telecomunicatii
Distribuitori de echipamente pentru afaceri
Retea nationala de magazine
Comenzi prin posta
Profitabilitatea, costurile de publicitate si efortul personalului care se ocupa de vanzari pentru noul produs difera functie de canalul de distributie, dupa cum se vede in tabelul urmator .
|
Canal de distributie |
Profit unitar [u.m.] |
Cost unitar de publicitate [u.m.] |
Efort de vanzare [ore] |
|
Distribuitori de echipamente de telecomunicatii | |||
|
Distribuitori de echipamente pentru afaceri | |||
|
Retea nationala de magazine | |||
|
Comenzi prin posta |
Bugetul de publicitate al firmei este de 5000 u.m. si sunt disponibile maxim 1800 ore pentru vanzare. Conducerea firmei a decis producerea a exact 600 unitati de sisteme radio portabile in perioda curenta. In plus, exista deja un contract cu o retea nationala de magazine in care se specifica faptul ca cel putin 150 de unitati de produs trebuie vandute astfel.
Firma doreste sa stie cate unitati de produs sa vanda prin fiecare canal de distributie si cum sa aloce bugetul pentru publicitate si timpul de vanzare disponibile, atfel incat profitul sa fie maxim.
O intreprindere de transport in comun doreste sa stabileasca numarul de soferi pe care sa ii angajeze. Soferii lucreaza cinci zile consecutive si au doua zile libere, in fiecare saptamana.
Numarul minim de soferi pe zi este: luni 17, marti 13, miercuri 15, joi 19, vineri 14, sambata 16, duminica 11.
Care este numarul minim de angajati? Cati soferi incep lucrul in fiecare zi a saptamanii? Cati dintre angajati vor fi distribuiti zilnic pentru alte activitati?
O companie a cumparat la mare un teren pe care poate construi casute de vacanta de doua tipuri, C Si C . Pe acest teren se pot construi cel mult 25 de casute.
Pentru o casuta C sunt necesare 40 de ore de munca pentru zidari si 25 de ore de munca pentru dulgheri, iar pentru C , 20 de ore de munca pentru zidari si 60 de ore pentru dulgheri.
Casutele se vor inchiria cu 1.275 u.m., respectiv 1250 u.m.
a) Cate casute din fiecare tip poate construi compania pentru a-si maximiza profitul?
b) Un vecin cu terenul doreste sa vanda cinci loturi, pe care se pot construi in plus cinci casute, doua casute tip C1 si trei casute tip C2, fiecare lot costand 1.500 u.m. Care va fi profitul in acest caz? Va cumpara compania cele cinci loturi?
c) Cate loturi poate cumpara?
d) Dar daca fiecare dintre cele cinci loturi costa 1.000 u.m., care va fi decizia?
Copyright © 2024 - Toate drepturile rezervate
