METODA SIMPLEX
EXEMPLUL 2
În partea dreaptă avem condiția inițială a problemei.
Etapa preliminară
Etapa preliminară începe cu necesitatea de a scăpa de valorile negative (dacă
există) din partea dreaptă a restricțiilor. Pentru care restricțiile corespunzătoare sunt
înmulțite cu -1. După această manipulare, semnul inegalității este inversat.
Apoi, trebuie să scăpați de inegalități, pentru care introducem variabile de
compensare în partea stângă a inegalităților. Dacă avem o inegalitate a formei ≤, atunci
variabila compensatoare are semnul +, dacă avem inegalitatea formei ≥, atunci variabila
compensatoare are semnul -. Variabilele compensatoare sunt incluse în funcția obiectivă a
problemei cu un coeficient zero.
Acum, în sistemul de constrângeri este necesar să se găsească un număr suficient de
variabile de bază. Fiecare constrângere trebuie să aibă o variabilă de bază. Elementul de
bază este o variabilă care are un coeficient de 1 și se găsește doar într-o singură
constrângere. Dacă nu există variabile de bază într-o anumită restricție, atunci le adăugăm
artificial, iar variabilele artificiale intră în funcția obiectivă cu coeficientul -M dacă funcția
obiectivă tinde spre max și M, dacă funcția obiectivă tinde spre min.
Iterare: 1
Elemente ale bazei coloanei (B)
Transferați pe tabel elementele de bază pe care le-am identificat în etapa preliminară:
B1 = x3; B2 = x5;
Elementele coloanei Cb
Fiecare celulă a acestei coloane este egală cu coeficientul, care corespunde variabilei de bază din
rândul corespunzător. Cb1 = 0; Cb2 = -M.
Valorile variabilelor variabile și coloana P
În această etapă, nu sunt necesare calcule, trebuie doar să transferați valorile din etapa preliminară
în celulele de tabel corespunzătoare: P 1 = 15; P2 = 6; x1,1 = 2; x1,2 = 4; x1,3 = 1; x1,4 = 0; x1,5 = 0; x2,1
= -4; x2,2 = 3; x2,3 = 0; x2,4 = -1; x2,5 = 1.
Valoarea funcției obiective
Calculăm valoarea funcției obiectiv multiplicând elementar coloana Cb cu coloana P, adăugând
rezultatele produselor. MaxP = (Cb1 * P01) + (Cb11 * P2 = (0 * 15) + (-M * 6) = -6M;
Variabile de control evaluate
Calculăm estimările pentru fiecare variabilă controlată, înmulțind în funcție de element valoarea
coloanei variabilei, cu valoarea coloanei Cb, însumând rezultatele produselor și scăzând
coeficientul funcției obiective din suma lor această variabilă.
Maxx1 = ((Cb1 * x1,1) + (Cb2 * x2,1)) - kx1 = ((0 * 2) + (-M * -4)) - -22 = 4M + 22;
Maxx2 = ((Cb1 * x1,2) + (Cb2 * x2,2)) - kx2 = ((0 * 4) + (-M * 3)) - 11 = -3M-11;
Maxx3 = ((Cb1 * x1,3) + (Cb2 * x2,3)) - kx3 = ((0 * 1) + (-M * 0)) - -M = 0;
Maxx4 = ((Cb1 * x1,4) + (Cb2 * x2,4)) - kx4 = ((0 * 0) + (-M * -1)) - 0 = M;
Maxx5 = ((Cb1 * x1,5) + (Cb2 * x2,5)) - kx5 = ((0 * 0) + (-M * 1)) - -M = 0.
Elementele coloanei Q
Deoarece există valori negative între estimările variabilelor controlate, tabelul actual nu are încă o
soluție optimă. Prin urmare, în bază introducem variabila cu cea mai mică estimare negativă.
Numărul de variabile din bază este întotdeauna constant, deci este necesar să alegem ce variabilă să
derivăm din bază, pentru care calculăm Q. Elementele coloanei Q sunt calculate prin împărțirea
valorilor din coloana P la valoarea din coloana corespunzătoare variabilei care este introdusă în
bază: Q1=P1/x1,2=15/4=3,75; Q2=P2 /x2,2=6/3=2. Deducem din bază variabila cu cea mai mică valoare
pozitivă a lui Q. La intersecția liniei care corespunde variabilei care este derivată din bază și a
coloanei care corespunde variabilei care este introdusă în bază, se află elementul de rezolvare. Acest
element ne va permite să calculăm elementele tabelului următoarei iterații.
Iterare: 2
Elemente ale bazei coloanei (B)
Pentru rezultatele calculelor iterației anterioare, eliminăm variabila din baza x5 și punem în locul ei
x2. Toate celelalte celule rămân neschimbate.
Elementele coloanei Cb
Fiecare celulă a acestei coloane este egală cu coeficientul, care corespunde variabilei de bază din
rândul corespunzător. Cb1 = 0; Cb2 = 11;
Valorile variabilelor variabile și coloana P
Datele din iterația anterioară sunt luate ca date inițiale. Umpleți toate celulele cu zerouri
corespunzătoare variabilei care tocmai a fost introdusă în bază: x1,2 = 0; Elementul de rezoluție
rămâne neschimbat. Transferăm rândul cu elementul de rezolvare din tabelul anterior în tabelul
curent, împărțind elementar valorile acestuia în elementul de rezolvare:
P2 = P2 / x2,2 = 6/3 = 2; x2,1 = x2,1 / x2,2 = -4 / 3 = -1,33; x2,2 = x2,2 / x2,2 = 3/3 = 1; x2,3 = x2,3 / x2,2 = 0/3
= 0; x2,4 = x2,4 / x2,2 = -1/3 = -0,33; x2,5 = x2,5 / x2,2 = 1/3 = 0,33.
Celulele goale rămase, cu excepția rândului estimărilor și a coloanei Q, sunt calculate utilizând
metoda dreptunghiului, în raport cu elementul de rezolvare:
P1 = (P1 * x2,2) - (x1,2 * P2) / x2,2 = ((15 * 3) - (4 * 6)) / 3 = 7;
x1,1 = ((x1,1 * x2,2) - (x1,2 * x2,1)) / x2,2 = ((2 * 3) - (4 * -4)) / 3 = 7,33;
x1,2 = ((x1,2 * x2,2) - (x1,2 * x2,2)) / x2,2 = ((4 * 3) - (4 * 3)) / 3 = 0;
x1,4 = ((x1,4 * x2,2) - (x1,2 * x2,4)) / x2,2 = ((0 * 3) - (4 * -1)) / 3 = 1,33;
x1,5 = ((x1,5 * x2,2) - (x1,2 * x2,5)) / x2,2 = ((0 * 3) - (4 * 1)) / 3 = -1,33;
Valoarea funcției obiective
Calculăm valoarea funcției obiectiv multiplicând elementar coloana Cb cu coloana P, adăugând
rezultatele produselor. MaxP = (Cb1 * P01) + (Cb11 * P2 )= (0 * 7) + (11 * 2) = 22;
Variabile de control evaluate
Calculăm estimările pentru fiecare variabilă controlată, înmulțind în funcție de element valoarea
coloanei variabilei, cu valoarea coloanei Cb, însumând rezultatele produselor și scăzând
coeficientul funcției obiective din suma lor această variabilă.
Maxx1 = ((Cb1 * x1,1) + (Cb2 * x2,1)) - kx1 = ((0 * 7.33) + (11 * -1.33)) - -22 = 7.33;
Maxx2 = ((Cb1 * x1,2) + (Cb2 * x2,2)) - kx2 = ((0 * 0) + (11 * 1)) - 11 = 0;
Maxx3 = ((Cb1 * x1,3) + (Cb2 * x2,3)) - kx3 = ((0 * 1) + (11 * 0)) - 0 = 0;
Maxx4 = ((Cb1 * x1,4) + (Cb2 * x2,4)) - kx4 = ((0 * 1.33) + (11 * -0.33)) - 0 = -3.67;
Maxx5 = ((Cb1 * x1,5) + (Cb2 * x2,5)) - kx5 = ((0 * -1.33) + (11 * 0.33)) - -M =M+3.67
Elementele coloanei Q
Deoarece există valori negative între estimările variabilelor controlate, tabelul actual nu are încă o
soluție optimă. Prin urmare, în bază introducem variabila cu cea mai mică estimare negativă.
Numărul de variabile din bază este întotdeauna constant, deci este necesar să alegem ce variabilă să
derivăm din bază, pentru care calculăm Q. Elementele coloanei Q sunt calculate prin împărțirea
valorilor din coloana P la valoarea din coloana corespunzătoare variabilei care este introdusă în
bază: Q1 = P1 / x1,4 = 7 / 1,33 = 5,25; Q2 = P2 / x2,4 = 2 / -0,33 = -6;
Deducem din bază variabila cu cea mai mică valoare pozitivă a lui Q. La intersecția liniei care
corespunde variabilei care este derivată din bază și a coloanei care corespunde variabilei care este
introdusă în bază, se află elementul de rezolvare. Acest element ne va permite să calculăm
elementele tabelului următoarei iterații.
Iterare: 3
Elemente ale bazei coloanei (B)
Pentru rezultatele calculelor iterației anterioare, eliminăm variabila din baza x3 și punem în locul ei
x4. Toate celelalte celule rămân neschimbate.
Elementele coloanei Cb
Fiecare celulă a acestei coloane este egală cu coeficientul, care corespunde variabilei de bază din
rândul corespunzător. Cb1 = 0; Cb2 = 11;
Valorile variabilelor variabile și coloana P
Datele din iterația anterioară sunt luate ca date inițiale. Umpleți toate celulele cu zerouri
corespunzătoare variabilei care tocmai a fost introdusă în bază: x 2,4 = 0; Elementul de rezoluție
rămâne neschimbat. Transferăm rândul cu elementul de rezolvare din tabelul anterior în tabelul
curent, împărțind elementar valorile acestuia în elementul de rezolvare:
P1 = P1 / x1,4 = 7 / 1,33 = 5,25; x1,1 = x1,1 / x1,4 = 7,33 / 1,33 = 5,5; x1,2 = x1,2 / x1,4 = 0 / 1,33 = 0;
x1,3 = x1,3 / x1,4 = 1 / 1,33 = 0,75; x1,4 = x1,4 / x1,4 = 1,33 / 1,33 = 1; x1,5 = x15 / x1,4 = -1,33 / 1,33 = -1;
Celulele goale rămase, cu excepția rândului estimărilor și a coloanei Q, sunt calculate utilizând
metoda dreptunghiului, în raport cu elementul de rezolvare:
P2 = (P2 * x1,4) - (x2,4 * P1) / x1,4 = ((2 * 1,33) - (-0,33 * 7)) / 1,33 = 3,75;
x2,1 = ((x2,1 * x1,4) - (x2,4 * x1,1)) / x1,4 = ((-1,33 * 1,33) - (-0,33 * 7,33)) / 1,33 = 0,5;
x2,2 = ((x2,2 * x1,4) - (x2,4 * x1,2)) / x1,4 = ((1 * 1,33) - (-0,33 * 0)) / 1,33 = 1;
x2,3 = ((x2,3 * x1,4) - (x2,4 * x1,3)) / x1,4 = ((0 * 1,33) - (-0,33 * 1)) / 1,33 = 0,25;
x2,4 = ((x2,4 * x1,4) - (x2,4 * x1,4)) / x1,4 = ((-0,33 * 1,33) - (-0,33 * 1,33)) / 1,33 = 0;
Valoarea funcției obiective
Calculăm valoarea funcției obiectiv multiplicând elementar coloana Cb cu coloana P, adăugând
rezultatele produselor. MaxP = (Cb1 * P01) + (Cb11 * P2 = (0 * 5,25) + (11 * 3,75) = 41,25;
Variabile de control evaluate
Calculăm estimările pentru fiecare variabilă controlată, înmulțind în funcție de element valoarea
coloanei variabilei, cu valoarea coloanei Cb, însumând rezultatele produselor și scăzând
coeficientul funcției obiective din suma lor, cu această variabilă.
Maxx1 = ((Cb1 * x1,1) + (Cb2 * x2,1)) - kx1 = ((0 * 5,5) + (11 * 0,5)) - -22 = 27,5;
Maxx2 = ((Cb1 * x1,2) + (Cb2 * x2,2)) - kx2 = ((0 * 0) + (11 * 1)) - 11 = 0;
Maxx3 = ((Cb1 * x1,3) + (Cb2 * x2,3)) - kx3 = ((0 * 0,75) + (11 * 0,25)) - 0 = 2,75;
Maxx4 = ((Cb1 * x1,4) + (Cb2 * x2,4)) - kx4 = ((0 * 1) + (11 * 0)) - 0 = 0;
Maxx5 = ((Cb1 * x1,5) + (Cb2 * x2,5)) - kx5 = ((0 * -1) + (11 * 0)) - -M = M;
Răspuns:
Deoarece nu există valori negative între estimările variabilelor controlate, tabelul actual are o
soluție optimă. Valoarea funcției obiective: F * = 41,25;
Variabilele prezente în bază sunt egale cu celulele corespunzătoare ale coloanei P, toate celelalte
variabile sunt egale cu zero: x1 = 0; x2 = 3,75;
SOLUȚIA PROBLEMEI:
• F* = 41,25
• X* = (0; 3.75)