Creeaza.com - informatii profesionale despre


Simplitatea lucrurilor complicate - Referate profesionale unice



Acasa » referate » informatica
Definitii si teoreme de baza ale programarii liniare

Definitii si teoreme de baza ale programarii liniare



Definitii si teoreme de baza ale programarii liniare

           

            Definitia 1: o solutie admisibila a problemei de programare liniara este un vector X=(X1, X2, ,Xn) care satisface sistemul de acuatii al restrictiilor de nenegativitate.

            Definitia 2: o solutie admisibila de baza este o solutie admisibia care contine cel putin n – m componente Xi care au valoarea zero.

n – numarul de variabile

m – numarul de ecuatii ale sistemului de restrictii

            Definitia 3: o solutie admisibila de baza nedegenerata are exact m componenete ale vectorului X cu valoare pozitiva.


            Definitia 4: o solutie optimala este o solutie admisibila care optimizeaza (maximizeaza sau minimizeaza) functia obiectiv.

            Teorema 1:  functia obiectiv iti realizeaza optimul intr-un punct extrem al multimii restrictiilor. Daca isi realizeaza optimul in mai mult de un punct extrem atunci functia obiectiv are aceeasi valoare in fiecare punct de pe segmentul de dreapta ce uneste doua puncte optimale.

            Teorema 2: un vector X=(X1, X2, ,Xn) este un punct extrem al multimii restrictiilor unei probleme de programare liniara daca si numai daca X este o solutie admisibila de baza.

            Pe baza celor enuntate o problema de programare liniara adusa la forma standard are o solutie care extremizeaza functia obiectiv, pentru una din solutiile admisibile da baza ale sistemului de restrictii in prezenta conditiilor de nenegativitate.

            Sa consideram sistemul de restrictii:

                    :alk

            Pentru a aduce acest sistem la o forma din care se poate deduce direct o solutie admisibila de baza se efectueaza o serie de operatii elementare prin care se elimina pe rand o parte din necunoscute din toate liniile cu exceptia unei singure linii.

            Sa presupunem ca am ales variabila Xk care se va elimina din toate ecuatiile cu exceptia ecuatiei l. Coeficientul pe care-l are variabila Xk in ecuatia l se va numi element de pivot si trebuie sa fie diferit de zero (alk – elementul pivot ales in cazul nostru).

            Pentru a elimina variabila Xk din toate celelalte ecuatii vom proceda astfel:

Ø     Se imparte ecuatia prin elementul pivot alk;

Ø     Ecuatia l, in noua forma, o vom inmulti succesiv cu coeficientii a1k/a2k//amk;

Ø     Si o vom scade din ecuatiile 1, 2 respectiv m.

In aceste fel variabila Xk va mai apare doar in ecuatia l, iar sistemul va avea urmatoarea forma:

Coeficientii sistemului vor suporta urmatoarele modificari:

*  

 (cazul nostru)

*  

Aceasta operatie de eliminare a unei variabile din toate liniile unui sistem cu exceptia unei singure linii se numeste pivotare. Sistemul obtinut admite aceleasi solutii cu sistemul initial adica vor fi echivalente. Pornind de la acest ultim sistem se procedeaza in mod similar la eliminarea unei noi necunoscute s. a. m. d. ajungandu-se in final la un sistem echivalent de forma:

*

            Una din solutiile acestui sistem este de forma:

             

Daca toti  sunt nenegativi o solutie admisibila de baza care va candida pentru solutia optima va fi cea data mai sus, iar variabilele ,  le vom numi variabile ale bazei.

Daca sistemului * i se va aplica o noua operatie de pivotare alegand ca element pivot elementul  in care q>m, ales astfel incat Xp este o variabila de baza, iar Xq este o variabila din afara bazei se va ajunge la un sistem similar, dar in care s-a efectuat o interschimbare in sensul ca Xp nu va mai face parte din baza, iar Xq va deveni variabila a bazei.

Deoarece functia obiectiv a unei probleme de programare liniara este o expresie liniara de variabilele Xi ce poate fi atasata sistemului si tratata in acelasi mod. Atasand functia obiectiv ca cea de a m+1 ecuatie in urma pivotarii se va ajunge la urmatorul sistem:

** 



Acest ultim sistem admite ca solutie:

Trecerea de la o solutie admisibila de baza la o alta solutie admisibila de baza

Sa consideram sistemul de restrictii rezultat in urma pivotarii (**). Daca coeficientii , , ,  sunt toti pozitivi atunci extremizarea functiei obiectiv va fi:

Daca cel putin unul din coeficienti este negativ atunci exista cel putin o alta solutie admisibila de baza care conduce la o valoare mai mare a functiei obiectiv. Pentru a demonstra acest lucru sa consideram coeficientu Ct ca fiind mai mic decat zero. Stiind ca Xt≥0 putem sa consideram Xt>0, iar restul variabilelor  (s-a renuntat la scrierea indicilor superiori de pivotare). In acest caz functia obiectiv va avea forma:

> pentru ca Ct<0

Deci se poate gasi o solutie mai buna si asta cu cat Xt are valoare mai mare. Pentru a compara aceasta solutie cu cea precedenta va trebui sa introducem variabila Xt in baza scotand o variabila Xs. Aceasta schimbare a lui Xs cu Xt in baza se efectueaza cu ajutorul unei noi operatii de pivotare. Se pune problema: cum alegem variabila Xs care trebuie scoasa din baza. Vom alege Xs astfel incat pe masura cresterii varibilei Xt sa fie indeplinita pentru prima data conditia:

Cu alte cuvinte va trebui sa alegem acea variabila Xs pentru care rapotul  este minim:

,

Daca mai multi dintre coeficientii Cm+1 Cm sunt negativi procedeul descris ramane valabil cu conditia sa introducem in baza variabila Xt care conduce la un maxim de crestere a functiei obiectiv, adica cea pentru care coeficientul Ct are valoarea cea mai mica (sau in modul valoarea cea mai mare).

Daca in urma unei noi operatii de pivotare tot nu s-a ajuns ca toti coeficientii sa fie pozitivi se vor continua pivotarile pana cand va fi indeplinita aceasta conditie. Daca pentru un Xt aflat in afara bazei si caruia ii corespunde Ct<0 vom avea conditia ca ait≤0, vom fi in cazul unui domeniu nemarginit, caz in care functia obiectiv va tinde la ¥.

Gasirea initiala a unei solutii admisibile de baza

Nu intotdeauna sistemul restrictiilor se poate aduce la o forma similara cu sistemul **, forma din care sa rezulte prima solutie admisibila de baza. De aceea, de multe ori va trebui sa calculam acea prima solutie admisibila de baza.

O metoda ar fi aceea a utilizarii unor variabile artificiale nenegative, adica in cazul in care sistemul restrictiilor este format din inegalitate fara a pierde generalitatea putem adauga fiecarei ecuatii cate o variabila artificiala Xn+1, Xn+2, , Xn+m≥0 nenegativa care sa transforme sistemul de inecuatii in sistem de ecuatii:

Acestui sistem ii vom atasa functia obiectiv care va fi completata cu functia obiectiv artificiala:

Solutia admisibila de baza pe care o putem considera  poate fi de forma:

 

Solutia este admisibila daca toti coeficientii bi sunt pozitivi. Aceasta conditie poate fi asigurata prin inmultirea cu (-1) a ecuatiilor inainte de adaugarea variabilelor auxiliare. Pentru a rezolva problema initiala va trebui sa obtinem o solutie optima care sa nu contina doar variabile artificiale (auxiliare ). Acest lucru va fi posibil atunci cand functia obiectiv artificiala va avea valoarea zero ceea ce inseamna ca Xi=0, .

 Daca maximul functiei obiectiv artificiale nu este zero inseamna ca nu exista o solutie admisibila de baza.








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




Cautarea de siruri Knuth-Morris-Pratt
Cautarea de siruri directa
E-mail-ul ca instrument de marketing
Translatorul
DATE, INFORMATII, CUNOSTINTE, ENTROPIE INFORMATIONALA
DE LA INFORMATICA CLASICA LA INFORMATICA UTILIZATORULUI FINAL
Principiile marketingului electronic
Asupra altor metode de inmultire binara


Termeni si conditii
Contact
Creeaza si tu