CATEGORII DOCUMENTE |
Astronomie | Biofizica | Biologie | Botanica | Carti | Chimie | Copii |
Educatie civica | Fabule ghicitori | Fizica | Gramatica | Joc | Literatura romana | Logica |
Matematica | Poezii | Psihologie psihiatrie | Sociologie |
Metoda simplex de rezolvare a unui program liniar standard
Fie programul standard
(S) |
| |
| ||
|
cu notatiile din paragraful
1. Daca vectorii coloana ai matricei
formeaza o baza in
, atunci
se numesc coordonate bazice (variabile de
baza). Matricea
poate fi descompusa in doua submatrice
formata din vectorii
si
formata cu celelalte coloane, deci:
|
si analog
|
iar forma standard se scrie
| |
| |
|
Facand calculele, rezulta
| |
| |
|
O solutie a sistemului (4.9) este
|
Luand
aici obtinem o solutie de baza pentru (4.9.) si
anume
|
Daca spunem ca baza
este primal admisibila. Daca vectorul
(
) are
aceste componente in raport cu baza B iar
,
|
cu .
Dispunand de o baza primal admisibila se intocmeste tabelul simplex in care trecem:
a) solutia
b)
c) valoarea functiei obiectiv corespunzatoare
solutiei de baza.
d) care reprezinta
coordonatele vectorilor
,
in baza
. daca
este baza canonica
sunt coeficientii din sistemul de restrictii
dat.
e)
se calculeaza
f)
se calculeaza diferentele
Un astfel de tabel
simplex, considerand ca , arata deci sub forma:
In
continuare se aplica testul de optimalitate al solutiei si bazat pe urmatoarele teoreme pe care le dam
fara demonstratie si anume:
Teorema 4.1. Daca pentru toti
, problema
de programare liniara are optim finit si
Teorema 4.2. Daca pentru
un indice pentru care
toate componentele
, programul
are optim infinit.
a. Daca toti
atunci
este solutia optima si
b. Daca exista cel putin o
diferenta atunci solutia nu
este optima. In acest caz exista urmatoarele posibilitati:
a. Fie asa incat
si daca toti
, problema nu are optim finit.
b. Fie cu
si exista cel
putin un
, atunci solutia poate fi imbunatatita.
Se trece la prima iteratie prin care se determina vectorul care intra in baza si vectorul care iese din baza. Indicele k al vectorului care intra in baza ne este dat de:
|
iar indicele h al vectorului care iese din baza este dat de:
|
In acest mod vectorului din baza ii ia locul vectorul
Se stabileste elementul pivot ykh ykh si se recalculeaza toate elementele tabloului simplex si se obtine o noua solutie de baza. Daca aceasta solutie nu este optima se trece la iterata urmatoare.
Exemplul 4.1 Sa se rezolve problema de programare liniara
Solutie
,
.
Vectorii si
formeaza o baza.
Variabilele bazice sunt si
.
Alcatuim tabelul simplex:
| |||||||
|
|
|
|
|
|
|
|
|
| ||||||
| |||||||
|
| ||||||
|
Cea mai mare diferenta pozitiva este c1 - f1 = 3 si avem yi1 > deci solutia poate fi imbunatatita.
In baza va intra vectorul Pentru a vedea ce vector iese in baza calculam
deci din baza iese vectorul . Pivotul
este 4.
Tabelul simplex din iterata urmatoare este:
| |||||||
|
|
|
|
|
|
|
|
| |||||||
|
| ||||||
| |||||||
|
Mai avem o diferenta pozitiva deci in baza intra vectorul
si iese vectorul
deoarece pe coloana lui
avem o singura coordonata pozitiva 3/2.
Pivotul este 3/2. Tabloul simplex in iterata urmatoare este:
| |||||||
|
|
|
|
|
|
|
|
| |||||||
| |||||||
| |||||||
|
Avem
doua diferente pozitive dar pe coloanele lor ele-mentele
transformate sunt negative deci problema nu
are optim finit.
Politica de confidentialitate | Termeni si conditii de utilizare |
Vizualizari: 2778
Importanta:
Termeni si conditii de utilizare | Contact
© SCRIGROUP 2025 . All rights reserved