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







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


Comentarii literare

ALEXANDRU LAPUSNEANUL COMENTARIUL NUVELEI
Amintiri din copilarie de Ion Creanga comentariu
Baltagul - Mihail Sadoveanu - comentariu
BASMUL POPULAR PRASLEA CEL VOINIC SI MERELE DE AUR - comentariu

Personaje din literatura

Baltagul – caracterizarea personajelor
Caracterizare Alexandru Lapusneanul
Caracterizarea lui Gavilescu
Caracterizarea personajelor negative din basmul

Tehnica si mecanica

Cuplaje - definitii. notatii. exemple. repere istorice.
Actionare macara
Reprezentarea si cotarea filetelor

Economie

Criza financiara forteaza grupurile din industria siderurgica sa-si reduca productia si sa amane investitii
Metode de evaluare bazate pe venituri (metode de evaluare financiare)
Indicatori Macroeconomici

Geografie

Turismul pe terra
Vulcanii Și mediul
Padurile pe terra si industrializarea lemnului



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