Creeaza.com - informatii profesionale despre


Simplitatea lucrurilor complicate - Referate profesionale unice
Acasa » referate » informatica
Analiza de senzitivitate a unei probleme de programare liniara

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 aij, 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.







Politica de confidentialitate







creeaza logo.com Copyright © 2023 - Toate drepturile rezervate.
Toate documentele au caracter informativ cu scop educational.


Proiecte

vezi toate proiectele
PROIECT DE LECTIE CLASA A II-A, Educatie plastica, Tehnica marmorata
PROIECT DIDACTIC 5-7 ani activitate matematica - „Cum este si cum nu este aceasta piesa”
Proiect Circuite Digitale
Organizarea si conducerea procesului tehnologic proiectat

Lucrari de diploma

vezi toate lucrarile de diploma
LUCRARE DE DIPLOMA - Rolul asistentului medical in ingrijirea pacientului cu A.V.C.
Spatiul romanesc, intre diplomatie si conflict in Evul Mediu
Lucrare de diploma managementul firmei “diagnosticul si evaluarea firmei”
Lucrare de diploma Facultatea de Textile – Pielarie - Tehnologia confectiilor din piele si inlocuitori - PROIECTAREA CONSTRUCTIV TEHNOLOGICA A UNUI PR

Lucrari licenta

vezi toate lucrarile de licenta
Lucrare de licenta contabilitate si informatica de gestiune - politici si tratamente contabile privind leasingul (ias 17). prevalenta economicului asupra juridicului
Lucrare de licenta educatie fizica si sport - sistemul de selectie in jocul de handbal pentru copii de 10-11 ani in concordanta cu cerintele handbalul
Lucrare de licenta - cercetare si analiza financiara asupra deseurilor de ambalaje la sc.ambalaje sa
LUCRARE DE LICENTA - Asigurarea calitatii la firma Trans

Lucrari doctorat

vezi toate lucrarile de doctorat
Diagnosticul ecografic in unele afectiuni gastroduodenale si hepatobiliare la animalele de companie - TEZA DE DOCTORAT
Doctorat - Modele dinamice de simulare ale accidentelor rutiere produse intre autovehicul si pieton
LUCRARE DE DOCTORAT ZOOTEHNIE - AMELIORARE - Estimarea valorii economice a caracterelor din obiectivul ameliorarii intr-o linie materna de porcine

Proiecte de atestat

vezi toate proiectele de atestat
Lucrare atestat informatica - „administrarea gradinii botanice”
Lucrare atestat Tehnician operator tehnica de calcul - Sursa de tensiune cu tranzistoare npn
ATESTAT PROFESIONAL LA INFORMATICA - programare FoxPro for Windows
Proiect atestat tehnician in turism - carnaval la venezia

Notiunea de sistem informatic
ANALIZA SI PROIECTAREA ORIENTATA OBIECT A SISTEMELOR INFORMATICE - APOO
SISTEME INFORMATIONALE SI SISTEME INFORMATICE IN GESTIUNEA ORGANIZATIILOR
SISTEMUL INFORMATIC , INSTRUMENT AL MANAGEMENTULUI ORGANIZATIILOR ECONOMICO-SOCIALE
Clasificarea informatiei
Sinteza unui dispozitiv secvential de inmultire a numerelor binare reprezentate in semn-marime
CONCEPTUL DE DATA SI INFORMATIE
Analiza de senzitivitate a unei probleme de programare liniara



Termeni si conditii
Contact
Creeaza si tu