ALGORITMUL SIMPLEX - Algoritmul simplex dual

ALGORITMUL SIMPLEX

• Algoritmul simplex se bazeaza pe metoda eliminarii complete de rezolvare a unui sistem de ecuatii liniare adaptata scopului urmarit, adica gasirea numai a solutiilor cu componente nenegative, respectiv a solutiei pentru care functia liniara f are valoarea optima.
• Presupunem mai departe ca opt = max, deoarece daca se cere minim din relatia max (-f) = - min (f) rezulta ca este suficient sa se determine max (-f), iar apoi cu semn schimbat vom avea min f.

• Intrebarile la care trebuie sa raspunda algoritmul simplex sunt urmatoarele: cum pornim, cum trecem de la o solutie la alta mai buna si cum ne oprim.
• Fie problema de programare liniara:

• Folosind metoda eliminarii complete se determina o solutie de baza si presupunem ca s-au redus primele m coloane:

• In ipoteza ca b _i 0, i = solutia de baza este:

x _B⁰ = ( b b ., b_m, 0, ., 0 ) ^t si f (x _B⁰ ) = c₁ b + c₂ b + . + c_m b_m

• Trecem de la solutia de baza x _B⁰ la o alta solutie de baza x _B¹ care sa fie mai buna si in care necunoscuta principala sa fie x _m+1 in locul lui x ₁. Aceasta se face reducand coloana lui x _m+1 si presupunand ca pivot este    a _{1, m+1}.
• Avem:

• Daca elementele de pe ultima coloana sunt 0 atunci solutia nou obtinuta este solutie de baza:

x _B¹ =

Avem si , i = rezulta a _1m+1 >0 si (raport minim) adica trecerea de la o solutie de baza la alta solutie de baza se face reducand o coloana cu respectarea conditiilor in alegerea pivotului:

- elementul pivot trebuie sa fie pozitiv;

- daca in coloana care se reduce sunt mai multe elemente pozitive atunci pivotul va fi acela care furnizeaza cel mai mic raport cand termenii liberi se impart la elementele pozitive corespunzatoare, din aceasta coloana.

• Solutia obtinuta x _B¹ va fi mai buna decat x _B⁰ daca f (x _B¹ ) - f (x _B⁰ ) >
• Avem f (x _B¹ ) - f (x _B⁰ ) = c _m+1 - c ₁ b - c ₂ - . - c _m =

= c _m+1 - (c ₁ a _1m+1 + c ₂ a _2m+1 + .+ c _m a _mm+1 )

d (c _m+1 -f _m+1) daca f _m+1 = c ₁ a _1m+1 + c ₂ a _2m+1 +.+ c _m a _mm+1 = c _BP _m+1

• Cum d > 0 se obtine conditia c _m+1 - f _m+1 > 0, care ne asigura ca prin trecerea de la x _B⁰ la solutia x _B¹ s-a obtinut o solutie mai buna.
• Atunci cand toate diferentele c _j - f _j 0 solutia nu se mai poate imbunatatii si acea solutie de baza este solutia optima a problemei.

Etapele algoritmului simplex sunt:

• se determina o solutie de baza a problemei;
• se calculeaza valorile f _j = c _B P _j, j = ;
• daca exista diferente c _j - f _j > 0 se trece la o alta solutie de baza (prin reducerea coloanei cu diferenta c _j - f _j cea mai mare) iar daca nu exista c _j - f _j > 0 se trece la etapa 5;
• se repeta etapele 2 si 3 pana nu mai exista diferente c _j - f _j >
• se scrie solutia optima: variabilele bazice au valorile corespunzatoare in coloana termenilor liberi, iar cele secundare sunt toate zero, iar valoarea pentru f _max = c_B B ^-1 b.
• Calculele presupuse de etapele algoritmului simplex se pot organiza intr-un tabel informational, denumit tabelul simplex, in care sunt usor de gasit numeroase informatii ale solutionarii prin intermediul rezultatelor numerice.
• Prin trecerea de la o etapa (iteratie) a tabloului simplex la alta se tine seama de urmatoarele reguli:

se imparte linia pivotului cu pivotul;

coloana pivotului va avea cifra 1 in locul pivotului si zero in rest;

elementele celorlalte coloane ale noului tablou simplex se determina folosind regula dreptunghiului.

• Cazul solutiei infinite. Exista situatii in care functia de optimizat are un maxim infinit, adica valoarea ei poate fi facuta oricat de mare. Aceasta se intampla daca exista o diferenta c_j - f_j pozitiva, dar pe coloana acesteia nu exista nici un element pozitiv, care sa fie luat pivot.
• Degenerarea in problemele de programare liniara. Solutia de baza este degenerata daca numarul componentelor sale mai mari decat 0 este mai mic decat m (in coloana b exista 0). Aceasta situatie apare, fie la inceput, fie pe parcurs, cand la introducerea in baza a unui vector, exista mai multe componente pozitive care furnizeaza acelasi raport minim. Pentru a evita fenomenul de ciclare, elementul pivot va fi ales acela care furnizeaza cea mai mica linie in ordonarea lexicografica.
• Definitie Linia (x₁, x₂, ., x_n ; x) este mai mica in ordonarea lexicografica decat linia (y₁, y₂, ., y_n ; y) daca x < y sau x = y si x₁ < y₁, sau x = y, x₁ = y₁, si x₂ < y₂, sau . x = y, x₁ = y₁, . , x_n-1 = y_n-1 si x_n < y_n.
• Solutii multiple. Solutia generala. Analizand tabelul simplex care contine solutia optima se constata ca numarul zerourilor din linia diferentelor c _j - f _j este mai mare decat m (diferentele c _j - f _j corespunzatoare vectorilor bazei optime sunt nule ) atunci problema poate avea mai multe solutii optime. Celelalte solutii optime se obtin reducand pe rand, daca este posibil, coloanele care au diferenta c _j - f _j = 0. Dupa obtinerea tuturor solutiilor optime se scrie solutia generala ca si combinatie liniara convexa a acestora.
• Probleme cu solutii impuse. Exista situatii practice in care, din motive diverse, anumite componente ale solutiei sunt restrictionate sa ia:

1. anumite valori, adica x_j = p_j pentru un j dat;

2. valori in anumite intervale, adica p_j x_j q_j, pentru un j dat.

Astfel de situatii sunt socotite modele sau probleme cu solutii impuse atunci cand restrictii precum cele mentionate sunt altele decat cele de semn.

• Daca se impune conditia x_j = p_j, atunci se reduce problema la (n-1) variabile, renuntand la variabila x_j in functia obiectiv, dar si in restrictiile problemei.
• Daca se adauga o restrictie de tipul p_j x_j q_j atunci la restrictiile problemei initiale se mai adauga noi restrictii p_j x_j si x_j q_j.
• Solutiile problemelor "cu solutii impuse" nu mai sunt solutii de baza (ele pot avea mai multe componente strict pozitive decat dimensiunea bazei).
• Exemplu Sa se rezolve problema de programare liniara:

max f = 4 x ₁ +2 x ₂ + 5 x ₃ + x ₄

Pentru rezolvare construim tabelul simplex urmator:

• Astfel, solutia optima a problemei generale este:

x _opt = (1, 2, 2, 0) ^t, f _max = 18.

• Se vede ca nu au fost scrise valorile necunoscutelor de compensare

x ₅ = 2, x ₆ = 0, x₇ = 0.

DUALITATEA

Fie problema de programare liniara numita problema primala (1)

min f = cx

(1)

Definitie Se numeste duala acestei probleme urmatoarea problema de programare liniara: max g = yb

(2)

Teorema Are loc una si numai una din afirmatiile:

a) ambele probleme au solutii optime finite si atunci g _max = f _min

b) una dintre probleme are solutie infinita, iar cealalta problema nu are solutie (posibila) (este incompatibila)

c) una dintre probleme are solutie degenerata, iar cealalta problema poate avea solutii optime multiple.

Definitie Se numeste cuplu de probleme duale forma simetrica problemele urmatoare:

min f = cx max g = yb

si (2)

DIAGRAMA LUI TUCKER

x = (x₁, x₂, .. , x_n) ^t - vectorul variabilelor primale de structura

x = (x_n+1, x_n+2, .. , x_n+m) ^t - vectorul variabilelor primale de compensare

y = (y₁, y₂, .. , y_n) - vectorul variabilelor duale de compensare

y = (y_n+1, y_n+2, .. , y_n+m) - vectorul variabilelor duale de structura

In iteratia optima a tabelului simplex se afla componentele solutiilor ambelor probleme, adica:

Exemplu Sa se rezolve problemele duale simetrice:

max f = 3 x₁ + 5 x₂ + 2 x₃ min g = 6 y₄ + 5 y₅ + 7 y₆

   

Rezolvare:

Vom rezolva, pe rand, cele doua probleme cu algoritmul simplex si apoi vom evidentia, in fiecare tabel si solutia optima a celeilalte probleme:

Astfel solutia optima este: x _opt = (1/ 2, 9/4, 0, 0, 0, 33/4 ) ^t, f_max = 51/4.

Solutia problemei duale este y _opt = (0, 0, 11/4, 1/ 4, 9/4, 0 ), valori luate din linia c_j - f_j dar cu semn schimbat iar g _min = 51/4.

Ne putem convinge de acest fapt prin rezolvarea directa a problemei duale:

Cum toate diferentele b_i - g_i 0, avem solutia optima g _min = 51/4 cu y_opt = (0, 0, 11/4, 1/ 4, 9/4, 0) respectiv pentru problema primala avem x _opt = (1/ 2, 9/4, 0, 0, 0, 33/4 ) ^t, valori luate din linia b_i - g_i iar f_max = 51/4 = g _min . Se vede, intr-adevar, ca s-au obtinut aceleasi solutii.

Algoritmul simplex dual

Exista situatii cand prin inmultirea unor restrictii cu (-1) apar in tabel vectori ce pot fi considerati in baza, caz in care se adopta o metoda putin modificata fata de algoritmul simplex. De fapt este vorba de aplicarea algoritmului simplex, dar asupra problemei duale. Etapele sunt aceleasi, dar, daca in coloana b exista elemente negative, atunci alegerea elementului pivot se va face respectand urmatoarele doua conditii:

- pe linia elementului negativ din coloana b se alege element pivot negativ;

- daca sunt mai multe elemente negative pe aceasta linie atunci pivotul va fi acela care furnizeaza cel mai mic raport, in valoare absoluta, dar considerat fata de elementele corespunzatoare din

linia c _j - f _j.

Exemplul Sa se rezolve, folosind algoritmul simplex dual urmatoarea problema de programare liniara:

min f = 4 x₁ + 5 x₂ + 3 x₃

Rezolvare:

min f = 4 x₁ + 5 x₂ + 3 x₃

Solutia optima va fi x _opt = (21/5, 0, 2/5, 7, 0, 0) ^t si f _min = 18.

REOPTIMIZAREA PROBLEMELOR DE PROGRAMARE LINIARA

Modificarea vectorului c

• Pornind de la solutia optima a problemei (1) vrem sa determinam solutia optima a problemei

(1) (2)

• Se pleaca de la iteratia optima a tabelului simplex a problemei (1) in care se recalculeaza elementele liniei c_j⁽¹⁾ - f_j⁽¹⁾ :

daca c_j⁽¹⁾ - f_j⁽¹⁾ 0 atunci solutia optima a problemei (1) este solutie

optima si pentru problema (2)

daca c_j⁽¹⁾ - f_j⁽¹⁾ > 0 atunci se trece la imbunatatirea solutiei .

Modificarea vectorului b

Pornind de la solutia optima a problemei (1) vrem sa determinam solutia optima a problemei

(3)

Se considera iteratia optima a problemei (1) in care se recalculeaza coloana termenilor liberi B ^-1 b ⁽¹⁾:

daca B ^-1 b ⁽¹⁾ 0 atunci solutia este optima;

daca exista elemente in aceasta coloana negative, atunci se continua cu

algoritmul simplex dual.

Modificarea unui vector coloana P _j din matricea A

Pornind de la solutia optima a problemei (1) vrem sa determinam solutia optima a problemei .

(4)

Se considera iteratia optima a problemei (1) in care se recalculeaza elementele coloanei P _j astfel B ^-1 P _j⁽¹⁾ .

- daca vectorul P _j nu face parte din baza optima atunci se verifica conditia de optim doar pentru acest vector si se actioneaza in consecinta;

- daca vectorul P _j face parte din baza optima atunci se trece la schimbarea bazei.

Adaugarea de noi coloane la matricea A

Pornind de la solutia optima a problemei (1) vrem sa determinam solutia optima a problemei:

(5)

Pentru reoptimizare se procedeaza ca in precedentele cazuri utilizand B^-1. Se vor calcula valorile din liniile f _j si c _j - f _j corespunzatoare noii coloane si se va actiona in consecinta.

Modificarea unei linii a matricei restrictiilor

- Pornind de la solutia optima a problemei (1) vrem sa determinam solutia optima a problemei:

(6)

- Modificarea unei linii a matricei restrictiilor inseamna de fapt modificarea simultana a mai multor coloane ale acestei matrici si ca urmare sunt posibile cazurile:

1) linia modificata nu schimba elementele coloanelor bazice si atunci sunt afectate doar diferentele c_j-f_{j ,}

2) linia modificata schimba elemente ale coloanelor bazice si atunci sunt afectate atat diferentele c_j-f_j cat si solutia x_B.

Observatie

Utilitatea practica a reoptimizarii se poate reflecta prin:

1) eficienta procedeului in raport cu solutionarea problemei modificate ca o problema noua, atunci cand se poate, deoarece calculele se reiau de la solutia optima a problemei date si se studiaza efectul modificarilor asupra optimalitatii solutiei;

2) posibilitatea simularii unor modificari pentru a cunoaste existenta sau inexistenta unor solutii optime sub influenta variatiilor elementelor definitorii ale modelului.

PROGRAMARE LINIARA PARAMETRICA

Consideram problema de programare liniara:

si vom analiza cazurile cand vectorii b si respectiv c depind liniar de un parametru.

Parametrizarea vectorului c

Fie problema de programare liniara parametrica

unde vectori constanti.

Pentru rezolvarea problemei (2) se parcurg etapele:

- pentru t = t₀ (fixat) se rezolva problema cu algoritmul simplex;

- se reoptimizeaza problema de la 1) cu datele c(t);

- din conditiile de optim c_j(t) - f_j(t) 0 se deduce un subinterval [ ] in care solutia gasita este optima.

daca [α, β] = [a, b] atunci rezolvarea s-a incheiat.

daca [α, β] [a, b] atunci se trece la etapa urmatoare;

- se ia si se continua cu reoptimizarea obtinand un nou subinterval [α₁, β₁] etc. se continua astfel, pana cand reunirea subintervalelor gasite coincide cu [a, b].

Observatie Conditiile de optim c_j(t) - f_j(t) 0 sunt cele care conduc la determinarea subintervalelor in care solutia este optima.

Parametrizarea vectorului b

In problema de programare liniara parametrica

unde b(t) = b¹ +tb², t[a, b], b¹ +b² vectori constanti

Pentru rezolvarea problemei (3) se parcurg etapele:

- pentru t = t₀ [a, b] se rezolva problema in mod obisnuit;

- se reoptimizeaza problema de la 1) cu datele d(t);

- din conditiile de admisibilitate B^-1b(t) 0 se deduce un interval real [α, β] in care solutia gasita este admisibila deci si optima. Daca [α, β] = [a, b] rezolvarea s-a incheiat, astfel ([α, β] [a, b]) se trece la etapa urmatoare.

- se ia t[a, b][α, β] si se continua cu reoptimizarea aplicand algoritmul simplex dual, pana cand reuniunea subintervalelor gasite coincide cu [a, b].

Observatie Conditiile de admisibilitate B^-1b(t) 0 sunt acelea care conduc la determinarea subintervalelor in care solutia este optima.

PROBLEME DE TRANSPORT

• Sa consideram m furnizori (distribuitori, producatori, etc.) F ₁ - F_m ai unui produs identic de care ei dispun in cantitatile a ₁ -a _m precum si n consumatori sau beneficiari (utilizatori) B ₁ - B _n al caror necesar este respectiv b ₁ - b _n . Sa notam cu x _ij cantitatea care se transporta (transfera , aloca) de la F _i la B _j si cu c_ij cheltuielile unitare de transport de la F _i la B _j. Costul transportului cantitatii x _ij de la F _i la B _j va fi egal cu c _ij x _ij iar pentru toti furnizorii si toti beneficiarii costul total va fi egal cu f = care trebuie minimizat. Evident, la nivelul furnizorului F _i cantitatea totala furnizata va fi egala cu , iar tot ceea ce ii poate reveni beneficiarului B _j este . Se cauta acea varianta de transport (sau de alocare) care sa satisfaca toti partenerii F _i si B _j si sa conduca la un cost total minim, ceea ce inseamna problema:

1. De obicei se urmareste satisfacerea totala atat a cererii cat si a disponibilului si prin urmare restrictiile problemei apar ca egalitati. Acestora li se pot adauga si alte restrictii cu semnificatii diverse.

2. Daca in locul unui anumit produs care sa poata fi efectiv transportat consideram ca a ₁ - a _m sunt suprafete cultivabile de o aceeasi calitate, iar B ₁ . B_n sunt n culturi care au nevoie de un astfel de teren, atunci problema amplasarii optime a culturilor are modelul matematic anterior, dar nu este vorba de o operatiune de transport. Este unul din motivele pentru care spunem modele de tip transport.

• Alocarea optima de fonduri banesti

Sa consideram un anumit fond banesc de valoare S unitati monetare (u.m) care trebuie repartizat sau alocat:

1. la un moment dat pentru n activitati sau

2. unei anumite activitati la n momente (adica esalonat).

Sa notam cu x _j, j =, partea din fond care se aloca pentru activitatea de ordin j (sau la momentul j) si cu c_j, profitul unitar realizat pentru fiecare unitate monetara investita sau alocata. Atunci profitul total va fi: f = c₁ x₁ + c₂ x₂ + . + c_n x_n urmand a fi maximizat, ceea ce conduce la problema:

Este posibila adaugarea unor restrictii de forma a _j x _j b _j j p n, in care x _j a _j > 0 ar insemna "un prag sau nivel minimal necesar util" sub care investitia nu prezinta interes, iar x _j b _j < S ar insemna "un nivel maximal posibil de credit garantat" care poate fi acoperit de catre debitor prin diverse garantii sau cu averea sa. In acest caz problema devine:

• Avand in vedere consideratiile si exemplul prezentat, putem rezuma faptul ca, sub forma generala, un model liniar de tip transport poate fi scris astfel:

unde: - reprezinta fie costul total al operatiunii de tip transport (cand opt = min), fie profitul total al operatiunii de tip transport (cand opt = max).

a_i reprezinta disponibilul furnizorului F_i, ;

b_j reprezinta necesarul beneficiarului B_j, ;

c_ij reprezinta costul unitar (sau profitul unitar) pe relatia ;

x_ij reprezinta cantitatea transportata (alocata, repartizata, transferata) de la furnizorul F_i la beneficiarul B_j, ;

restrictia arata ca nu se poate aloca tuturor beneficiarilor mai mult decat este disponibil furnizorului F_i;

restrictia arata ca de la toti furnizorii se aloca pentru beneficiarul B_j cel putin cat este necesarul sau;

reprezinta disponibilul (sau oferta) tuturor furnizorilor iar reprezinta necesarul (sau cererea) tuturor beneficiarilor in ipoteza ca insumarile au sens (in caz contrar nu are sens problema).

Se spune ca o problema de tip transport este:

echilibrata daca oferta totala este egala cu cererea totala a = b

neechilibrata daca oferta totala difera de cererea totala (a ≠ b)

• Pentru a evita explicatii si scrieri numeroase si greoaie in prezentarea unei probleme de tip transport, cel mai adesea, se recurge la sintetizarea tuturor informatiilor (cerere, oferta, costuri sau beneficii unitare) intr-un tabel sub forma urmatoare: (precizand doar cerinta min sau max).

cij

1. Ansamblul    poarta denumirea de casuta.

	xij

2. Conceptul de echilibrare este fundamental pentru construirea procedurii de solutionare a unei probleme de tip transport.

3. Daca egalitatea intre disponibilul total si necesarul total nu are loc se poate trece la o problema echilibrata prin considerarea fie a unui furnizor fictiv, F_m+1, fie a unui beneficiar fictiv, B_n+1, care ofera sau solicita, diferenta dintre cele doua sume.

4. Intrucat algoritmul presupune un volum mare de calcule, pentru acest tip de problema de programare liniara se va prezenta un algoritm distributiv.

• Metode de gasire a unei solutii initiale

a) Metoda nord-vest consta in a atribui, pe rand, valori variabilelor incepand cu cea din coltul nord-vest a tabelului, apoi se continua la fel cu subtabelul ramas.

Astfel x₁₁ = min (a₁, b₁), daca min (a₁, b₁) = a₁ atunci x₁₂ = =x_1n = 0, daca min (a₁, b₁) = b₁ atunci x₂₁ = = x_m1 = 0 si apoi vom continua cu x₂₁ = min (a₂, b₁-a₁) respectiv in cealalta situatie cu x₁₂ = min (a₁-b₁, b₂) etc.

Acest procedeu se repeta pana cand este atribuita si ultima valoare variabilelor.

Valoarea 0 este marcata in tabel printr-un punct.

• Exemplu Sa se stabileasca o solutie initiala folosind metoda nord-vest pentru problema de transport avand modelul matematic urmator:

[min]f = 4x₁₁ + 2x₁₂ + x₁₃ + 2x₂₁ + x₂₂ + 3x₂₃

f = 4 10 + 2 30 + 1 5 + 3 20 = 165.

b) Metoda elementului (costului ) minim consta in a atribui, pe rand, valori variabilelor incepand cu aceea pentru care costul unitar este minim. Apoi se continua cu variabila pentru care costul unitar este minim dintre cele ramase etc. Daca sunt mai multe costuri minime egale atunci se va considera mai intai acea variabila care poate lua valoare mai mare. Valoarea variabilei se determina ca si la metoda nord-vest, considerand minimul dintre disponibilul si necesarul corespunzator.

c) Metoda costului minim pe linie consta din a aloca pentru fiecare casuta (i, j) o cantitate x_ij egala cu minimul dintre cererea si oferta existenta in momentul acelei alocari, procedeul aplicandu-se pe fiecare linie in ordinea crescatoare a costurilor unitare c_ij. Algoritmul poate incepe cu oricare linie dar pentru organizarea calculelor acesta incepe cu prima linie si decurge ca si in cazul metodei coltului din nord-vest.

d) Metoda costului minim pe coloana este un procedeu analog cu precedentul cu singura deosebire ca se aplica pe fiecare coloana, preferabil incepand cu prima coloana.

• Exemplu Folosind metoda elementului minim sa se stabileasca o solutie initiala pentru problema formulata in exemplul precedent.