Analiza de senzitivitate a unei probleme de programare liniara

Analiza de senzitivitate a unei probleme de programare liniara

O problema de programare liniara contine, pe langa variabilele de decizie care trebuie aflate, o serie de marimi constante, presupuse cunoscute: coeficientii tehnologici a_ij, disponibilul/necesarul de resurse bi, componentele vectorului costurilor cj. Eficienta practica a solutiei optime gasite depinde, evident, de precizia cu care s-a determinat nivelul acestor componente. Pe de alta parte, in situatiile concrete, deseori apar modificari frecvente ale conditiilor in care se desfasoara activitatile economice, ceea ce a impus necesitatea elaborarii unor modele matematice care sa tina seama de caracterul dinamic al fenomenelor economice.

Reoptimizarea unei probleme de programare liniara consta in recalcularea solutiei optime in cazul in care se modifica o parte dintre conditiile initiale.

Astfel, componentele vectorului termenilor liberi se pot modifica fata de nivelul lor prestabilit ca urmare a schimbarii capacitatii mijloacelor de munca, a disponibilului de forta de munca, materii prime, materiale.

Schimbarea tehnologiei de fabricatie are efecte directe asupra costurilor de productie si asupra consumurilor specifice de resurse.

Daca in perioada de plan se asimileaza un nou produs, in modelul de programare liniara trebuie introdusa o noua variabila de decizie, iar inlocuirea unei surse de energie cu alta, a unui material cu altul etc. presupune includerea in model a unor restrictii suplimentare.

In astfel de situatii, se pune problema daca solutia optima obtinuta pe baza conditiilor initiale mai ramane optima si dupa modificarea acestora. Este necesar ca solutia optima sa fie verificata in noile conditii, iar daca nu mai este optima, atunci se pune problema de a gasi metode de reoptimizare a solutiei, metode care sa utilizeze rezultatele anterioare, pentru a reduce astfel volumul de munca necesar.

Asadar, in vederea reoptimizarii unei probleme de programare liniara este necesar sa se parcurga urmatoarele etape:

Verificarea optimalitatii solutiei in conditiile shimbarii datelor initiale.

Determinarea solutiei optime a problemei modificate, daca solutia nu mai este optima.

In continuare se vor trata cateva cazuri de reoptimizare, pe baza formei standard a unei probleme de programare liniara.

Modificarea vectorului termenilor liberi,

Deoarece matricea coeficientilor tehnologici ramane aceeasi, baza problemei initiale ramane baza si in problema modificata.

Solutia de baza este: iar

Noua solutie ar putea sa nu aiba toate componentele pozitive (dupa cum sunt componentele noului vector , dar sigur toti raman pozitivi, fiind aceiasi cu cei ai solutiei optime initiale.

Pot apare doua cazuri:

a.    Daca , ea este solutie optima a problemei modificate;

b.   Daca are cel putin o componenta negativa, pentru a gasi solutia optima a problemei modificate se aplica algoritmul simplex dual.

Modificarea vectorului costurilor

Deoarece matricea A si vectorul b raman aceleasi, avem acelasi sistem de restrictii si deci aceeasi multime de solutii admisibile. Solutia optima a problemei initiale, fiind solutie de baza admisibila a sistemului de restrictii, va fi solutie admisibila de baza si in problema modificata. Dispunem deci de o solutie admisibila de baza si se poate aplica algoritmul simplex primal direct de la ultimul tabel al problemei initiale, in care se inlocuieste vectorul costurilor c cu vectorul modificat si se recalculeaza , obtinandu-se o noua valoare

a.    Daca criteriul de optim este indeplinit (toti , pentru o problema de minim si toti , pentru o problema de maxim) inseamna ca noua solutie va fi solutie optima.

b.   Daca criteriul de optim nu este indeplinit, se continua optimizarea ei, utilizand algoritmul simplex.

Modificarea coeficientilor unei variabile

Efectul este modificarea coloanei din matricea A si/sau a coeficientului din functia obiectiv. Exista doua posibilitati:

Coloana aj nu face parte din baza B a problemei initiale. In acest caz baza B a problemei initiale ramane baza si in problema modificata, solutia corespunzatoare este aceeasi: si tabelul simplex este cel corespunzator problemei initiale in care se modifica doar coloana variabilei xj:

Sunt posibile doua cazuri:

Daca criteriul de optim este indeplinit (toti, pentru o problema de minim si toti , pentru o problema de maxim), solutia optima a problemei initiale ramane solutie optima si in problema modificata.

Daca criteriul de optim nu este indeplinit, se continua rezolvarea problemei cu algoritmul simplex.

Coloana aj face parte din baza B. In acest caz fosta baza nu mai exista in maticea A a problemei modificate. Se aplica urmatorul procedeu:

a.    In problema modificata adusa la forma canonica se scriu toti termenii cu variabila xj ca o suma de doi termeni, unul avand drept coeficient pe cel initial, iar celalalt diferenta dintre noul coeficient si cel initial:

b.   In toti termenii de forma si se inlocuieste variabila xj cu o noua variabila y si se adauga la sistemul de restrictii restrictia xj = y, obtinandu-se o problema echivalenta.

c.    Pentru noua problema se cauta o solutie de baza admisibila cu care se continua algoritmul simplex.

Adaugarea unei restrictii

In problema modificata se va adauga o linie la matricea A si un element la vectorul b. Se verifica daca solutia optima a problemei initiale verifica noua restrictie. Daca o verifica ea este solutie optima si a problemei modificate. Daca nu o verifica, se va cauta in continuare solutia optima.

Din ultimul tabel simplex al problemei initiale, putem scrie:

de unde se scot variabilele principale in functie de cele secundare, se inlocuiesc in noua restrictie si se face ca termenul liber obtinut sa fie pozitiv (eventual prin inmultirea restrictiei cu -1). Se adauga restrictia sub forma obtinuta la sistemul de restrictii initial, scris sub forma corespunzatoare ultimului tabel simplex.

Sunt posibile trei cazuri:

Daca restrictia nou introdusa este de tipul , se introduce variabila de compensare s cu coeficient +1. Se va forma o matrice unitate din coloanele corespunzatoare variabilelor principale initiale si coloana variabilei s. Tabelul simplex corespunzator va fi tabelul problemei initiale la care se adauga o linie si o coloana in plus. Coloana va fi un vectorul unitar corespunzator lui s, iar pe linie coeficientii cs vor fi: egali cu zero in coloana coeficientilor functiei obiectiv corespunzatori variabilelor din baza, s in coloana variabilelor bazei, bm+1 in coloana solutiei de baza, coeficientii noii restrictii (adusa la ultima forma) in interiorul tabelului si 1 in dreptul noii variabile s.

Solutia gasita are toate componentele pozitive si toti pozitivi, deci este solutia optima cautata.

Daca restrictia este de tipul , variabila de compensare se introduce cu coeficienrul -1 si solutia corespunzatoare este doar dual admisibila.

Se va cauta solutia optima cu ajutorul algoritmului simplex dual.

Daca restrictia este de tipul "=", se introduce variabila artificiala a, cu , se construieste tabelul asociat (ca in cazul 1) si se obtine o solutie admisibila cu depinzand de M.

Se continua algoritmul simplex primal pana la gasirea solutiei optime.