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:

1.   Verificarea optimalitatii solutiei in conditiile shimbarii datelor initiale.

2.   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:



1.   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.

2.   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:

1.   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.

2.   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.

3.   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

.com Copyright © 2019 - Toate drepturile rezervate.
Toate documentele au caracter informativ cu scop educational.


Proiecte

vezi toate proiectele
 PROIECT DE LECTIE Clasa: I Matematica - Adunarea si scaderea numerelor naturale de la 0 la 30, fara trecere peste ordin
 Proiect didactic Grupa: mijlocie - Consolidarea mersului in echilibru pe o linie trasata pe sol (30 cm)
 Redresor electronic automat pentru incarcarea bateriilor auto - proiect atestat
 Proiectarea instalatiilor de alimentare ale motoarelor cu aprindere prin scanteie cu carburator

Lucrari de diploma

vezi toate lucrarile de diploma
 Lucrare de diploma - eritrodermia psoriazica
 ACTIUNEA DIPLOMATICA A ROMANIEI LA CONFERINTA DE PACE DE LA PARIS (1946-1947)
 Proiect diploma Finante Banci - REALIZAREA INSPECTIEI FISCALE LA O SOCIETATE COMERCIALA
 Lucrare de diploma managementul firmei “diagnosticul si evaluarea firmei”

Lucrari licenta

vezi toate lucrarile de licenta
 CONTABILITATEA FINANCIARA TESTE GRILA LICENTA
 LUCRARE DE LICENTA - FACULTATEA DE EDUCATIE FIZICA SI SPORT
 Lucrare de licenta stiintele naturii siecologie - 'surse de poluare a clisurii dunarii”
 LUCRARE DE LICENTA - Gestiunea stocurilor de materii prime si materiale

Lucrari doctorat

vezi toate lucrarile de doctorat
 Doctorat - Modele dinamice de simulare ale accidentelor rutiere produse intre autovehicul si pieton
 Diagnosticul ecografic in unele afectiuni gastroduodenale si hepatobiliare la animalele de companie - TEZA DE DOCTORAT
 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
 Proiect atestat informatica- Tehnician operator tehnica de calcul - Unitati de Stocare
 LUCRARE DE ATESTAT ELECTRONIST - TEHNICA DE CALCUL - Placa de baza
 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