Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  

CATEGORII DOCUMENTE





AccessAdobe photoshopAlgoritmiAutocadBaze de dateCC sharp
CalculatoareCorel drawDot netExcelFox proFrontpageHardware
HtmlInternetJavaLinuxMatlabMs dosPascal
PhpPower pointRetele calculatoareSqlTutorialsWebdesignWindows
WordXml


ALGORITMUL SIMPLEX

algoritmi

+ Font mai mare | - Font mai mic







DOCUMENTE SIMILARE

Trimite pe Messenger
Structuri de date
Algoritmi semnatura digitala
SYSAMO-SISTEM EXPERT PENTRU AMORTIZAREA IMOBILIZARILOR CORPORALE
Proiect - dispozitivul de comanda pentru un automat de schimbat bani (monede)
METODE DE SORTARE
Optimizarea fluxurilor informationale ale unei case de schimb valutar
PROIECT ASDN - Sinteza unui ceas electronic desteptator
Scheme logice si pseudocod - Reprezentarea algoritmilor prin scheme logice
ATESTAT ALGORITMI
Arbori de decizie - Inteligenta artificiala

ALGORITMUL  SIMPLEX

 

Reamintim ca presupunem ca problema este la forma standard de maxim si ca dispunem de o solutie de baza admisibila.

 



Pasul 1.    Se construieste tabelul simplex corespunzator bazei de care dispunem in ordinea urmatoare:

1.      pe linia a doua se trec toate variabilele intr-o ordine oarecare;

2.      pe prima linie se trec coeficientii functiei obiectiv, fiecare deasupra variabilei corespunzatoare;

3.      se construieste matricea A, fiecare coloana fiind formata din coeficientii unei variabile din toate ecuatiile (ordinea in care se parcurg ecuatiile trebuie sa fie aceeasi pentru toate variabilele), avand grija ca, coloanele sa fie trecute in ordinea in care au fost trecute variabilele pe linia 2;

4.      se construieste baza B, ordinea coloanelor fiind cea in care apar ele in matricea A;

5.      se calculeaza B-1;

6.      se calculeaza B-1A si se trece in partea centrala a tabelului;

7.      se trec variabilele principale in a doua coloana, in asa fel incat, la intersectia liniei si coloanei corespunzatoare acestei variabile, sa se afle valoarea 1.

8.      se trec in prima coloana coeficientii corespunzatori variabilelor principale din functia obiectiv, fiecare in dreptul variabilei corespunzatoare;

9.      se calculeaza solutia de baza cu formula B-1b, avand grija ca ordinea in care au fost trecuti termenii liberi in vectorul b sa fie aceeasi cu ordinea in care au fost parcurse ecuatiile la formarea matricii A;

10.  se trec in a treia coloana valorile variabilelor principale din solutia de baza, fiecare in dreptul variabilei corespunzatoare;

11.  se calculeaza f(xB) inmultind doua cate doua componentele coloanei 1 cu cele din coloana 3 aflate pe aceeasi linie si adunand toate produsele intre ele (adica facem produsul scalar dintre cB si xB);

12.  se calculeaza pe rand fiecare zj j = 1,,n un zj obtinandu-se inmultind scalar cB cu coloana j din B-1A aflata in centrul tabelului (aceasta linie se calculeaza si se trece doar in primul tabel, scopul ei fiind calcularea lui D);

13.  se calculeaza pe rand fiecare Dj j = 1,,n scazand din linia lui z linia lui c (Dj = zj - cj)

 

Pasul 2.    Se analizeaza valorile Dj corespunzatoare variabilelor secundare (e usor de vazut ca intotdeauna, cei corespunzatori variabilelor principale sunt toti 0, deci neinteresanti).

-      daca toti sunt mai mari sau egali cu 0 atunci solutia actuala este cea optima. Daca exista Dj = 0 in afara bazei, atunci pot aparea doua cazuri:

1)      toate elementele din coloana aj din B-1A sunt mai mici sau egale cu 0. Atunci toate solutiile de forma xB - ajl sunt solutii optime, unde l > 0 oarecare;

2)      exista o componenta aij a coloanei aj strict pozitiva. Atunci introducand variabila xj in baza in locul variabilei principala xi obtinem alta solutie de baza optima.

Daca apar numai cazuri de tipul 2), obtinem toate solutiile de baza optime, multimea tuturor solutiilor optime fiind formata din toate combinatiile convexe ale acestora. Daca apare si cazul 1) atunci multimea solutiilor optime este nemarginita fiind formata din combinatiile convexe ale solutiilor de forma  xB - ajl unde xB sunt toate solutiile optime de baza.

-      daca exista Dj < 0 atunci il alegem pe cel mai negativ: Dk = . Variabila xj va fi cea care intra in noua baza. Daca minimul este multiplu atunci alegem, la intamplare, unul dintre acestia (cei minimi).

Pasul 3.    Se analizeaza elementele coloanei aj din B-1A, corespunzatoare variabilei alese la pasul 2.

 

-       Daca toate sunt mai mici sau egale cu 0 atunci problema are optim infinit si algoritmul ia sfarsit;

-       Daca exista componente strict pozitive, pentru acestea se calculeaza rapoartele qs = . Variabila xi corespunzatoare raportului minim este cea care va iesi din baza. Daca acest minim este multiplu sunt posibile doua cazuri:

1)      minimul este strict pozitiv. In acest caz se alege unul dintre acestia la intamplare;

2)      minimul este 0. Atunci xi corespunzatori sunt 0, deci solutia este degenerata si noua solutie este la fel de buna. Aceasta situatie poate duce la ciclarea algoritmului si alegerea la intamplare nu mai este suficienta, fiind nevoie de o regula de alegere suplimentara care sa evite ciclarea. O metoda de alegere se bazeaza pe faptul ca, asa cum vom vedea, intotdeauna prima baza este matricea unitate si in dreptul ei, in toate tabelele simplex, se va afla inversa bazei corespunzator fiecaruia. In acest caz, pentru pozitiile in care s-a obtinut minimul impartim prima coloana a lui B-1 la coloana aj si alegem minimul dintre aceste rapoarte. Daca minimul dintre acestia este tot multiplu continuam procedeul, pentru pozitiile ce dau noul minim, cu coloana a doua din B-1 si asa mai departe, pana minimul ramane unic. Nu este posibil sa se epuizeze toate coloanele lui B-1 si minimul sa ramana multiplu, deoarece, in acest caz, am avea: , pentru toti indicii jk ai coloanelor lui B-1, i1 si i2 fiind doi din indicii care dau acelasi minim pana la sfarsit sau altfel scris  pentru orice jk T liniile i1 si i2 din B-1 sunt proportionale, fapt ce contrazice faptul ca B-1 este inversabila.

Pasul 4.    Se calculeaza componentele tabelului simplex corespunzator noii baze pe baza tabelului actual si folosind urmatoarele reguli:

1.      se incadreaza elementul aij, aflat la intersectia coloanei variabilei care intra in baza cu linia variabilei care iese din baza, care a fost numit de Danzig pivot, intr-un dreptunghi

2.      coloana pivotului va avea 1 in dreptul pivotului si 0 in rest (inclusiv Dj);

3.      linia pivotului este linia actuala impartita la pivot (inclusiv in solutia de baza);

4.      restul elementelor se calculeaza cu regula dreptunghiului (inclusiv solutia de baza, D si f(xB)). Regula dreptunghiului se bazeaza pe observatia ca in toate formulele prin care se calculeaza acestea nu apare decat valoarea lor actuala, pivotul si cele doua elemente care ar completa dreptunghiul ce are pozitia de calculat si pivotul pe diagonala. Regula dreptunghiului se enunta literar astfel: 'noua valoare = produsul dintre elementele de pe diagonala pivotului minus produsul dintre cele aflate pe cealalta diagonala totul impartit la pivot'. (pentru scurtarea timpului de lucru se poate observa ca elementele unei linii care are 0 pe coloana pivotului raman aceleasi si de asemenea elementele unei coloane care are 0 pe linia pivotului)

Operatia de calculare a noului tabel prin regulile de mai sus poarta denumirea de pivotare.

Pasul 5.    Se reia algoritmul de la pasul 2.

 

 

Exemplu: Fie problema de programare liniara:

 

 

pentru care stim ca baza formata din coloanele a1, a2, a3 este admisibila. Pentru rezolvare vom aduce problema la forma standard de maxim introducand variabilele de abatere x7, x8, x9 obtinand:

 

 

Vom aseza in tabelul simplex variabilele in ordinea indicilor si vom avea:

c = , A = , B = , cB =

vom calcula matricea B-1 =   si pe baza acesteia solutia de baza xB = B-1b = si matricea B-1A =  care se trec in tabelul simplex:

 

 

 

 

 3   2    1      4      3       5      0       0        0

cB

xB

xB

 x1  x2  x3     x4     x5     x6     x7      x8      x9

3

 

2

 

1

x1

 

x2

 

x3

1

 

2

 

3

 

 

 

 

 

 

 

 

 

si in final se vor calcula valoarea functiei obiectiv in aceasta solutie, zj si Dj:

 

 

 

 3   2    1      4      3       5      0       0        0

cB

xB

xB

 x1  x2  x3     x4     x5     x6     x7      x8      x9

3

 


2

 


1

x1

 

x2

 

x3

 

1

 

2

 

3

 

 

10

 

 

 

 

Din tabel se observa ca exista Dj < 0, acestia fiind D4, D5, D6, D8  iar minimul lor este D6.

Observatie Daca vom cauta acel Dj care da cea mai buna imbunatatire vom avea de gasit acel Dj dintre cei negativi pentru care se obtine  si deci de calculat:

 = =

 = =

 = =

 = =

si in final max ( , , , ) =  si corespunde tot lui D6.

In concluzie, solutia actuala nu este optima si solutia cea mai buna dintre cele posibile ca succesoare va avea variabila x6 printre cele principale.

Analizand coloana a6 observam ca exista componente strict pozitive (de fapt, in acest caz sunt chiar toate) si calculam pentru acestea rapoartele qi obtinand:

 

q1 =  = ,   q2 =  = 14,   q3 =  =    

deci minimul corespunde variabilei x1 si aceasta este cea care va iesi din baza. In cest moment cunoastem noua baza si vom construi tabelul simplex pe baza regulilor de calcul de la pasul 4:

 

1.      pivotul este a16 =

4.      de exemplu, pentru elementul de pe pozitia a34 avem dreptunghiul:

 

 

 

 

 

 

 

 


si noua valoare de pe aceasta pozitie va fi:   =  1

In final, tabelul corespunzator noii baze va fi:

 

 

 

 

 3      2    1      4      3     5      0       0      0

cB

xB

xB

 x1    x2   x3    x4     x5    x6     x7      x8    x9

5

 

2

 

1

x6

 

x2

 

x3

 

 

 

Continuand algoritmul vom gasi tabelele:

 

 

 

 

 3      2    1      4      3     5      0       0      0

cB

xB

xB

 x1    x2   x3    x4     x5    x6     x7      x8    x9

5

 

2

 

0

x6

 

x2

 

x8

 

 

 

 

 

 

 

 

 3        2     1      4      3    5      0      0     0

cB

xB

xB

 x1      x2    x3    x4     x5   x6     x7    x8    x9

5

 

3

 

0

x6

 

x5

 

x8

5

 

1

 

2

 

 

28

 

Ultimul tabel contine solutia optima, deoarece toti Dj 0. Deoarece nu mai exista nici un Dj = 0 in afara celor din baza rezulta ca solutia optima este unica.

 

 

Determinarea unei solutii de baza admisibile de start

 

Presupunem inca odata ca problema este la forma standard.

Algoritmul simplex necesita, pentru pornire, o solutie admisibila de baza. Gasirea acesteia pur si simplu prin incercari nu este deloc o sarcina usoara, gandindu-ne ca aceasta presupune gasirea unui minor principal, inversarea acestuia si calcularea solutiei, abia in acest moment putand vedea daca aceasta are toate componentele pozitive, aceasta cautare putand dura foarte mult.

Rezolvarea problemei pleaca de la observatia ca singura baza pentru care calculul de mai sus se poate face imediat este matricea unitate, caz in care solutia de baza corespunzatoare este chiar vectorul termenilor liberi. Aceasta presupune ca problema sa aiba toti termenii liberi mai mari sau egali cu 0 si in matricea A sa existe toate coloanele matricii unitate.

Daca toti termenii liberi pot fi facuti mai mari sau egali cu 0 foarte simplu, prin inmultirea eventual cu 1 a restrictiei respective, existenta tuturor coloanelor matricii unitate este evident ca este foarte putin probabila si mai greu de obtinut.

In acest sens plecam de la observatia ca existenta unui vector din coloana unitate printre coloanele matricii A este echivalenta cu existenta unei variabile care apare doar in ecuatia corespunzatoare lui 1 din acel vector, cu coeficientul 1. Acest lucru poate fi obtinut  in doua moduri:

 

a)      Incepand de la prima ecuatie, cautam o variabila care are coeficientul de acelasi semn cu termenul liber, o scoatem din aceasta ecuatie in functie de celelalte variabile, o inlocuim in celelalte si repetam procedeul pornind de la a doua ecuatie. Pot aparea trei cazuri:

1)      la un moment dat obtinem o ecuatie in care toti coeficientii variabilelor au semn contrar termenului liber, macar unul dintre toti fiind diferit de 0. In acest caz ecuatia nu are evident solutie admisibila(pozitiva) si deci problema nu are solutie;

2)      toti coeficientii variabilelor si termenul liber sunt 0. In acest caz rezulta ca aceasta ecuatie rezulta din cele anterioare si ea va fi eliminata, trecandu-se la urmatoarea;

3)      se epuizeaza toate ecuatiile. In acest moment, variabilele care au fost scoase din fiecare ecuatie formeaza baza dorita.

Procedeul de mai sus poate parea atractiv, dar presupune introducerea unui algoritm diferit de simplex, cu efect asupra omogenitatii calculelor si a vitezei de lucru. De asemenea, prin efectuarea calculelor de mai sus, datele problemei nu mai au semnificatia economica initiala, ne mai putandu-se face interpretari economice.

b)     Pentru toti vectorii coloana introducem in ecuatiile corespunzatoare cate o variabila cu coeficientul 1. Vom obtine evident un nou sistem de restrictii si ramane de vazut ce legatura este intre solutiile acestuia si cel initial. Cele doua sisteme au forma:

Ax = b     si    Ax + y = b

Este evident ca o solutie a primului sistem este solutie si a celui de-al doilea (luam y = 0) iar o solutie a celui de-al doilea este solutie si pentru primul doar daca y = 0. Scopul nostru va fi deci, ca pornind de la solutia initiala a celei de-a doua probleme sa ajungem la o solutie a acesteia in care y = 0. Tinand cont ca in solutiile de baza, variabilele secundare sunt toate egale cu 0, vom incerca sa scoatem din baza variabilele y. Scopul algoritmului simplex este insa maximizarea functiei obiectiv, nu scoaterea a uneia sau alteia din variabile din baza. Pentru a echivala cele doua scopuri putem proceda in doua feluri:

1)      Alegem o noua functie obiectiv care sa-si atinga extremul printre solutiile pozitive chiar pentru y = 0 si in momentul cand am obtinut solutia respectiva pornim cu aceasta ca solutie initiala algoritmul simplex pentru fosta problema.

2)      Adaugam la fosta functie obiectiv noile variabile cu niste coeficienti de asemenea natura alesi incat aportul variabilelor y la valoarea functiei sa fie contrar scopului dorit (foarte mari pozitivi intr-o problema de minim si foarte mari negativi intr-o problema de maxim).

 

Vom detalia in continuare cele doua metode:

 

Algoritmul simplex in doua faze

 

Data problema de programare liniara la forma standard de maxim:

 

 

in care am aranjat deja ca toti termenii liberi sa fie pozitivi (b 0).

 

Faza 1 Construim problema:

 

pe care o rezolvam cu algoritmul simplex pornind rezolvarea de la baza matrice unitate, putand ajunge la doua situatii:

 

1)      minimul functiei g este strict pozitiv. Aceasta este echivalent cu faptul ca egalitatea Ax + y = b se poate obtine doar pentru y > 0 sau altfel spus Ax > b pentru orice x 0, deci sistemul Ax = b nu are solutii admisibile si in concluzie problema initiala nu are solutie.

2)      minimul functiei g este 0. In acest caz, solutia optima obtinuta are y = 0, deci verifica Ax = b fiind in concluzie o solutie admisibila de baza a primei probleme.

 

Faza 2 Incepand de la solutia gasita la faza 1 se rezolva problema initiala cu algoritmul simplex.

 

Dezavantajul metodei consta in faptul ca tabelul simplex final de la faza 1 trebuie modificat pentru a obtine tabelul simplex initial de la faza 2 (vectorii x, c, cB, z, D, f(xB), se elimina coloanele corespunzatoare lui y) si in plus nu vom mai avea in tabelele simplex ale problemei initiale inversa bazei (care se gasea in dreptul coloanelor matricii unitate din prima faza) necesara in anumite variante ale algoritmului simplex.

 

 

Metoda bazei artificiale (metoda penalizarii)

 

Data problema de programare liniara la forma standard de maxim:

 

 

in care am aranjat deja ca toti termenii liberi sa fie pozitivi (b 0).

 

Construim problema:

 

in care M este o constanta presupusa foarte mare (mai mare decat orice constanta care ar putea apare in rezolvarea problemei). Rezolvam problema cu algoritmul simplex pornind rezolvarea de la baza matrice unitate, putand ajunge la trei situatii:

 

1)      problema are optim infinit. In acest caz, problema initiala are optim infinit.

2)      problema are optim finit si in solutia de baza avem cel putin o variabila din vectorul y. In acest caz problema initiala nu are solutii admisibile.

3)      problema are optim finit si in solutia de baza nu avem nici o variabila din vectorul y. In acest caz problema initiala are optim finit, solutia optima si maximul functiei fiind aceleasi cu cele ale problemei modificate.

 

In final vom remarca faptul ca variabilele y nu corespund unor marimi economice ca celelalte, ele fiind introduse doar ca un artificiu de calcul pentru a putea porni algoritmul simplex. Din acest motiv ele se numesc variabile artificiale.


 

Exemplu Fie problema de programare liniara:

 

Forma standard a problemei va fi:

 

Avem deja termenii liberi si o coloana a matricii unitate  corespunzatoare variabilei x3. Pentru a obtine si a doua coloana  vom introduce variabila x5 cu coeficientul 1 in a doua ecuatie si in final vom avea de rezolvat problema:

 

Algoritmul simplex in doua faze

Metoda bazei artificiale

 

 

 

Aplicand algoritmul simplex in doua faze vom obtine in prima faza succesiunea de tabele:

 

 

 

 

0

0

0

0

1

cB

xB

xB

x1

x2

x3

x4

x5

0

x3

10

3

1

1

0

0

1

x5

2

1

4

0



-1

1

 

 

2

1

4

0

-1

1

 

 

 

1

4

0

-1

0

 

 

 

 

0

0

0

0

1

cB

xB

xB

x1

x2

x3

x4

x5

0

x3

0

1

0

x2

1

0

 

 

0

0

0

0

0

-1

 

Am obtinut optimul egal cu 0 in solutia de baza (x3,x2) care va fi solutia initiala pentru algoritmul simplex aplicat problemei initiale in a doua faza. Eliminam din tabel coloana lui x5, inlocuim valorile coeficientilor functiei obiectiv si deci si valoarea acesteia, valorile D si obtinem tabelul:


 


 

 

2

3

0

0

cB

xB

xB

x1

x2

x3

x4

0

x3

0

1

3

x2

1

0

 

 

0

0

 

 

 

 

2

3

0

0

cB

xB

xB

x1

x2

x3

x4

0

x3

4

0

-11

1

3

2

x1

2

1

4

0

-1

 

 

4

0

5

0

-2

 

 

 

 

2

3

0

0

cB

xB

xB

x1

x2

x3

x4

0

x4

0

1

2

x1

1

0

 

 

0

0

 

 

 

 

2

3

0

0

cB

xB

xB

x1

x2

x3

x4

0

x4

38

11

0

4

1

3

x2

10

3

1

1

0

 

 

30

7

0

3

0

 

Solutia optima a primei probleme este deci x1 = 0 si x2 = 10 care da un maxim al functiei egal cu 30. Daca aplicam a doua metoda vom obtine succesiv tabele:

 

 

 

 

2

3

0

0

-M

cB

xB

xB

x1

x2

x3

x4

x5

0

x3

10

3

1

1

0

0

-M

x5

2

1

4

0

-1

1

 

 

-2M

-M

-4M

0

M

-M

 

 

 

-M-2

-4M-3

0

M

0

 

 

 

 

2

3

0

0

-M

cB

xB

xB

x1

x2

x3

x4

x5

0

x3

0

1

3

x2

1

0

 

 

0

0

M+

 

 

 

 

2

3

0

0

-M

cB

xB

xB

x1

x2

x3

x4

x5

0

x3

4

0

-11

1

3

-3

2

x1

2

1

4

0

-1

1

 

 

4

0

5

0

-2

2+M

 

 

 

 

2

3

0

0

-M

cB

xB




xB

x1

x2

x3

x4

x5

0

x4

0

1

-1

2

x1

1

0

0

 

 

0

0

M

 

 

 

 

2

3

0

0

-M

cB

xB

xB

x1

x2

x3

x4

x5

0

x4

38

11

0

4

1

-1

3

x2

10

3

1

1

0

0

 

 

30

7

0

3

0

M

 

Rezultatul final este evident acelasi.

 

 

VARIANTE  ALE  ALGORITMULUI  SIMPLEX

 

1.      Algoritmul simplex dual

 

Pentru expunerea acestui algoritm trebuie introduse notiunile de baza dual admisibila si solutie dual admisibila de baza. Prin definitie numim:

 

solutie de baza dual admisibila

=

solutie de baza pentru care toti Dj 0

baza dual admisibila

=

baza corespunzatoare unei solutii de baza dual admisibile

Ca si in cazul algoritmului simplex, pentru a putea rezolva problema cu algoritmul simplex dual trebuie sa dispunem deja de o baza initiala dual admisibila. Aceasta solutie poate exista ca urmare a unor calcule anterioare (vezi capitolul cu reoptimizarea) sau, ca si in cazul algoritmului simplex, poate fi aplicata o procedura prin care sa gasim aceasta baza. Prezentarea acesteia este mai complicata decat cea de la algoritmul simplex astfel incat:

 

-     daca dispunem de o baza dual admisibila vom rezolva problema cu algoritmul simplex dual

-     daca nu dispunem de o baza dual admisibila vom rezolva problema cu algoritmul simplex.

 

Pentru a evita orice confuzie, vom numi in continuare algoritmul simplex obisnuit algoritm simplex primal si o baza admisibila baza primal admisibila.

Se observa ca o solutie dual admisibila nu este in general primal admisibila si reciproc, iar o solutie care este simultan primal si dual admisibila este o solutie optima si reciproc.

Presupunem ca am adus problema la forma standard de maxim si dispunem de o baza dual admisibila si dispunem deja de de o baza dual admisibila. Algoritmul simplex dual consta in urmatorii pasi:

 

Pasul 1.    Se construieste tabelul simplex asociat acestei baze, la fel ca si la algoritmul simplex primal;

Pasul 2.    Se analizeaza componentele solutiei:

- Daca toate componentele sunt mai mari sau egale cu 0 atunci solutia este si primal admisibila, deci optima.

- Daca exista componente strict negative, variabila corespunzatoare celei mai negative (xi = ) este cea care iese din baza. Daca minimul este multiplu se ia una la intamplare.

Pasul 3.    Se analizeaza linia li corespunzatoare variabilei xi aleasa la pasul 2:

- Daca toate componentele aij j = 1,,n sunt mai mari sau egale cu 0, atunci am avea o ecuatie cu toti coeficientii necunoscutelor pozitivi si termenul liber strict negativ, deci problema nu are solutii primal admisibile.

- Daca exista componente strict negative, atunci pentru acestea se gaseste acel indice pentru care se obtine  (prin  am notat modulul numarului a). Daca minimul este multiplu alegem unul dintre acestia la intamplare. Variabila corespunzatoare acestuia este cea care intra in baza.

Pasul 4.    Se construieste tabelul corespunzator noii baze aplicand aceleasi reguli ca la algoritmul simplex primal;

Pasul 5.    Se reia algoritmul de la pasul 2

 

 

2.      Forma secundara

 

Este evident ca modul de organizare al datelor in tabelul simplex nu este unicul mod de a organiza datele intr-un tabel. Forma secundara este tocmai o astfel de alternativa. Presupunem si in acest caz ca problema este la forma standard de maxim, ca problema este la forma standard si ca dispunem de o solutie initiala de baza care este primal sau dual admisibila.

 

Pasul 1.    Datele problemei vor fi organizate intr-un tabel de forma:

 

 

 

 

cS

c

x

f

xS

 

 

f(xB)

DS

cB

xB

xB = B-1b

B-1S

cS

xS

0

In-m

 

Se observa ca singura diferenta este ca la coloana variabilelor bazei din stanga se adauga si cele secundare, pe orizontala se lasa doar variabilele secundare iar in loc de matricea unitate in dreptul variabilelor principale vom avea matricea unitate in dreptul celor secundare (dar cu minus), D fiind calculat la fel, neglijandu-se cei din dreptul variabilelor principale, care oricum erau 0.

 

Pasul 2.    +   Pasul 3.  Se gasesc variabila care iese din baza si cea care intra in baza cu aceleasi reguli ca la algoritmul simplex primal sau, dupa caz, ca la cel dual.


 

Pasul 4.     Se construieste tabelul asociat noii baze aplicand regulile:

 

1)      Pivotul este acelasi ca la tabelul simplex;

2)      Linia pivotului are 1 in dreptul pivotului si 0 in rest;

3)      Coloana pivotului se imparte la pivotul cu semn schimbat

4)      Celelalte elemente se calculeaza cu regula dreptunghiului

 

Pasul 5.      Se reia algoritmul de la pasul 2.

 

Exemplu Fie problema de programare liniara rezolvata mai sus:

 

Forma standard a problemei va fi:

iar dupa introducerea variabilelor artificiale obtinem:

Tabelul corespunzator va fi:

 

 

 

 

2

3

0

cB

xB

xB

x1

x2

x4

 

 

-2M

-M-2

-4M-3

M

2

x1

0

-1

0

0

3

x2

0

0

-1

0

0

x3

10

3

1

0

0

x4

0

0

0

-1

-M

x5

2

1

4

-1

 

Aplicam simplex primal si obtinem cel mai negativ Dj corespunzator lui x2 si qi minim corespunzator lui x5. In acest moment avem o solutie de baza a problemei initiale si putem elimina variabila x5. Obtinem:

 

 

 

 

 


2

-M

0

 

 

 

 

2

0

cB

xB

xB

x1

x5

x4

 

cB

xB

xB

x1

x4

 

 

M+

-

 

 

 

-

2

x1

0

-1

0

0

 

2

x1

0

-1

0

3

x2

-

3

x2

-

0

x3

 

-

 

0

x3

 

0

x4

0

0

0

-1

 

0

x4

0

0

-1

-M

x5

0

0

-1

0

 

 

 

 

 

 

 

si in continuare:


 

 

 

 

3

0

 

 

 

 

3

0

cB

xB

xB

x2

x4

 

cB

xB

xB

x2

x3

 

 

4

5

-2

 

 

 

2

x1

2

4

-1

 

2

x1

 

3

x2

0

-1

0

3

x2

0

-1



0

0

x3

4

-11

3

 

0

x3

0

0

-1

0

x4

0

0

-1

 

0

x4

 

 

 

 

 

2

0

 

cB

xB

xB

x1

x3

 

 

 

30

7

3

2

x1

0

-1

0

 

3

x2

10

3

1

 

0

x3

0

0

-1

 

0

x4

38

11

4

 

Din rezolvarea de mai sus se observa ca aceasta metoda este mai eficienta doar daca numarul variabilelor secundare este mai mic decat numarul variabilelor principale. Totusi, motivul principal pentru care a fost introdusa aceasta varianta, este existenta unor probleme in care, pe parcursul rezolvarii, se adauga foarte multe restrictii (de exemplu rezolvarea problemelor in numere intregi), pentru o restrictie in plus tabelul simplex marindu-se cu o linie si o coloana (cum se va vedea la capitolul de reoptimizare) iar tabelul corespunzator formei secundare doar cu o linie.

 

 

3.      Forma revizuita a algoritmului simplex

 

O problema mare (de exemplu cu 1000 variabile si 100 restrictii) necesita in algoritmul simplex introducerea, memorarea si lucrul cu un tabel cu 100.000 componente, adica un numar imens de date. Din acest motiv, si remarcand faptul ca in algoritmul simplex doar o parte din acestea contribuie efectiv la luarea deciziilor, s-a construit un algoritm care sa tina cont de observatiile de mai sus, numit 'forma revizuita a algoritmului simplex', in care se lucreaza cu minimul necesar din datele tabelului simplex. Astfel, pentru testarea solutiei actuale si trecerea eventuala la o noua baza avem nevoie doar de urmatoarele elemente:

(1)   inversa bazei curente B-1

(2)   componentele vectorului D pentru a face testul de optim si a gasi variabila care intra in baza (daca solutia nu e optima)

(3)   coloana ak din B-1A corespunzatoare celui mai negativ Dj (daca exista strict negativi) pentru a face testul de optim infinit

(4)   solutia curenta pentru a gasi variabila care iese din baza (daca mai e cazul)

 

Aceste elemente se aseaza intr-un tabel de forma:

 

 

 

cB

 

 

 

 

xB

 

 

xB = B-1b

 

 

B-1

 

 

f(xB)

π = B-1

 

numit tabelul simplex redus.

Operatiile ce se efectueaza in cadrul algoritmului simplex revizuit sunt (presupunem ca problema este la forma standard de maxim si detinem o solutie admisibila de baza si inversa bazei corespunzatoare):

 

Pasul 1.    Se calculeaza Dj corespunzatori variabilelor secundare cu formula cunoscuta:

 

Dj = B-1Pj - cj = πPj - cj

 

unde Pj este coloana corespunzatoare variabilei xj din matricea initiala.

 

Pasul 2.    Se analizeaza Dj calculati:

 

-       daca toti sunt mai mari sau egali cu 0 solutia curenta este optima. STOP

-       daca exista Dj strict negativi se alege minimul dintre acestia Dk, variabila xk va intra in baza si se trece la pasul 3.

 

Pasul 3.    Se calculeaza ak = B-1Pk care se ataseaza ca noua coloana la tabel:

 

 

 

cB

 

 

 

 

xB

 

 

xB = B-1b

 

 

B-1

 

 

ak = B-1Pk

 

 

f(xB)

π = B-1

Dk

 

Pasul 4.    Se analizeaza componentele coloanei ak:

 

-       daca toate sunt mai mici sau egale cu 0 problema are optim infinit. STOP

-       daca exista aik strict pozitivi se alege cel pentru care se obtine:

 

ark =

 

si variabila xr va iesi din baza apoi se trece la pasul 5.

 

Pasul 5.    Se pivoteaza intregul tabel simplex si se elimina ultima coloana.

Pasul 6.    Se reia algoritmul de la pasul 2.

 

 

Exemplu Fie problema de programare liniara rezolvata mai sus:

 

Forma standard a problemei va fi:

iar dupa introducerea variabilelor artificiale obtinem:

 

Iteratia  1.  Prima baza este B = I2 = B-1 corespunzatoare variabilelor x3 si x5 de unde rezulta xB =  si π = (0,-M)I2 = (0,-M). Primul tabel redus va fi:

 

0

-M

x3

x5

10

2

1

0

0

1

 

 

-2M

0

-M

 

Se calculeaza DS = πS cS = (0,-M)    =  de unde rezulta ca cel mai negativ este D2 si vom calcula coloana a2 = I2 =  care se adauga la tabelul anterior rezultand:

 

0

-M

x3

x5

10

2

1

0

0

1

1

4

 

 

-2M

0

-M

-4M-3

 

qi minim este cel corespunzator lui x5 si deci variabila x2 va intra in locul variabilei x5.

Dupa pivotare si eliminarea ultimei coloane obtinem:

 

0

3

x3

x2

1

0

-

 

 

0

 

Deoarece variabila artificiala x5 a iesit din baza ea va fi eliminata din problema.

Iteratia 2.   DS = πS cS = (0,)    = ( )

cel mai negativ este D1 si vom calcula coloana a1 = =  care se adauga la tabelul anterior rezultand:

0

3

x3

x2

1

0

-

 

 

0

 

 

qi minim este cel corespunzator lui x2 si deci variabila x1 va intra in locul variabilei x2.

Dupa pivotare si eliminarea ultimei coloane obtinem:

 

0

2

x3

x1

4

2

1

0

-3

1

 

 

4

0

2

 

Iteratia 3.   DS = πS cS = (0,2)    = ( )

cel mai negativ este D4 si vom calcula coloana a4 = =  care se adauga la tabelul anterior rezultand:

 

0

2

x3

x1

4

2

1

0

-3

1

3

-1

 

 

4

0

2

-2

 

 

qi minim este cel corespunzator lui x3 si deci variabila x4 va intra in locul variabilei x3.

Dupa pivotare si eliminarea ultimei coloane obtinem:

 

0

2

x4

x1

-1

0

 

 

0

 

Iteratia 4.   DS = πS cS = ( ,0)    = ( )

cel mai negativ este D2 si vom calcula coloana a2 = =  care se adauga la tabelul anterior rezultand:

 

0

2

x4

x1

-1

0

 

 

0

 

 

qi minim este cel corespunzator lui x1 si deci variabila x2 va intra in locul variabilei x1.

Dupa pivotare si eliminarea ultimei coloane obtinem:

 

0

3

x4

x2

38

10

4

1

-1

0

 

 

30

3

0

 

Iteratia 5. DS = πS cS = (3,0)    = ( ) >0 deci solutia este optima (si unica) STOP

 

Chiar daca la prima vedere calculele par mai imprastiate si deci mai lente, pentru probleme mari, pe calculator se economiseste foarte multa memorie si se mareste foarte mult viteza de calcul.

Totusi, marele avantaj al acestei metode este acela ca, la fiecare iteratie, se folosesc datele problemei initiale, ceea ce face ca erorile inerente de rotunjire sa nu se propage, ramanand in limite acceptabile.

 

 








Politica de confidentialitate

DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 2476
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2019 . All rights reserved

Distribuie URL

Adauga cod HTML in site