Home - Rasfoiesc.com
Educatie Sanatate Inginerie Business Familie Hobby Legal
Doar rabdarea si perseverenta in invatare aduce rezultate bune.stiinta, numere naturale, teoreme, multimi, calcule, ecuatii, sisteme




Biologie Chimie Didactica Fizica Geografie Informatica
Istorie Literatura Matematica Psihologie

Matematica


Index » educatie » Matematica
Programarea liniara in numere intregi


Programarea liniara in numere intregi


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

Aplicatii

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 urbana cat si in cea rurala. Managerii firmei vor sa stie cate locatii trebuie sa deschida si unde pentru ca profitul obtinut sa fie maxim, in conditiile in care se conosc datele prezentate in tabelul de mai jos:

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?





Politica de confidentialitate





Copyright © 2024 - Toate drepturile rezervate

Matematica


Statistica


Elipsoidul
SOLUTII SI BAREME - Clasa a VII-a (CONCURSUL DE MATEMATICA)
Vectori in plan - aplicatii
Paraboloidul eliptic
Relatii binare intre multimi
LIMITE DE FUNCTII
FUNCTII - proprietati
Ecuatii de recurenta liniara de ordinul intai
Vectori
ELEMENTE DE COMBINATORICA




termeni
contact

adauga