Problema de programare liniara
Se considera o problema de alocare a resurselor materiale cu maximizarea profitului. Din trei resurse R1 , R2 , R3 se fabrica trei produse P1, P2 , P3 . Disponibilul de resurse, consumul de resurse pe produs si profitul unitar sunt date in tabelul nr.1 .
Se cere:
a) Sa se scrie modelul matematic al problemei de programare liniara pentru alocarea resurselor cu maximizarea profitului;
b) Sa se aduca problema de problema de programare liniara obtinuta la forma standard si sa se determine solutia de baza;
c) Trebuie determinata solutia optima, deci ce cantitate se va fabrica din fiecare produs, astfel incat profitul obtinut sa fie maxim.
Tabelul nr.1.
Pj
Ri P1 P2 P3 Resurse disponibile
bi
R1 3 1 2 100
R2 1 2 1 120
R3 2 1 1 130
Profitul unitar
cj 36 40 48
Rezolvare
a) Se noteaza cu Xj cantitatea din produsul Pj ce se va fabrica, j = 1, 2, 3 . Modelul matematic este problema de programare liniara (1).
3.X1 + X2 + 2.X3 100
X1 + 2 . X2 + X3 120 (1)
2.X1 + X2 + X3 130
X1 0 , X2 0 , X3 0
f(X1, X2, X3) = 36. X1 + 40 . X2 + 48 . X3
max f(X1, X2, X3)
b) Problema de programare liniara (1) este la forma canonica, problema de maximizare, care se va aduce la forma standard, problema de maximizare (2).
3.X1 + X2 + 2.X3 + X4 = 100
X1 + 2 . X2 + X3 + X5 = 120 (2)
2.X1 + X2 + X3 + X6 = 130
X1 0 , X2 0 , X3 0 , X4 0 , X5 0 , X6 0
f(X1, X2, X3) = 36. X1 + 40 . X2 + 48 . X3
max f(X1, X2, X3)
Matricea A
P1 P2 P3 P4 P5 P6
m = 3 , n = 6 ;
Baza spatiului vectorial R3 este B = {P4 , P5 , P6 }, deci variabilele de baza sunt X4 , X5 , X6 pentru care se determina valorile initiale egaland cu zero variabilele care nu sunt de baza, adica X1 = X2 = X3 = 0 ce se inlocuiesc in restrictii.
Se obtine: X4 = 100 , X5 = 120 , X6 = 130 .
c) Se va completa tabelul simplex al problemei, tabelul nr.2. Se va utiliza algoritmul simplex.
Tabelul nr.2
cB cj
36 40 48 0 0 0
2.1 VB P0 P1 P2 P3
P4 P5 P6
0 X4
100 3 1 2 1 0 0
0 X5 120 1 2 1 0 1 0
0 X6 130 2 1 1 0 0 1
Z0 = 0 cj - zj 36 40 48 0 0 0
48 X3 50 3/2 1/2
1 1/2 0 0
0 X5
70 -1/2 3/2 0 -1/2 1 0
0 X6 80 1/2 1/2 0 -1/2 0 1
Z0=2400 cj - zj -36 16 0 -24 0 0
48 X3 80/3 5/3 0 1 2/3 -1/3 0
40 X2 140/3 -1/3 1 0 -1/3 2/3 0
0 X6 170/3 2/3 0 0 -1/3 -1/3 1
Z0 =9440/3 cj - zj -92/3 0 0 -56/3 -32/3 0
Solutia optima este:
X1 = 0 ; X2 = 140/3 ; X3 = 80/3 ; X4 = 0 ; X5 = 0 ; X6 = 170/3 ;
Max f = Z0 = 9440/3
Solutia optima a problemei initiale este:
X1 = 0 ; X2 = 140/3 ; X3 = 80/3 ; max f = 9440/3
,
1. Problema de transport
Un produs se afla in diverse cantitati in depozitele A1, A2, A3 si trebuie transportat in centrele de consum B1, B2, B3 , B4. Oferta, cererea si costurile unitare de transport sunt date in tabelul nr.
Pentru a descărca acest document,
trebuie să te autentifici in contul tău.