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.





loading...




Politica de confidentialitate

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


Proiecte

vezi toate proiectele
 PROIECT DE LECTIE CLASA: a X a EDUCATIE MUZICALA - OPERA IN GERMANIA SI RUSIA
 PROIECT DIDACTIC 3-5 ani Limba si comunicare - Strugurele, de Maria Gaitan
 Proiect instalatii electrice - Sa se proiecteze instalatia electrica si de forta a unei microintreprinderi la alegerea studentului
 PROIECT - Ingineria reglarii automate - sistemul de reglare automata a unei actionari cu motor electric

Lucrari de diploma

vezi toate lucrarile de diploma
 LUCRARE DE DIPLOMA - Rolul asistentului medical in ingrijirea pacientului cu A.V.C.
 Relatiile diplomatice dintre Romania si Austro- Ungaria din a doua jumatate a secolului al XIX-lea
 Lucrare de diploma managementul firmei “diagnosticul si evaluarea firmei”
 Lucrare de diploma tehnologia confectiilor din piele si inlocuitor - proiectarea constructiv tehnologica a unui produs de incaltaminte tip cizma scurt

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 - studiu asupra imbunataȚirii motricitaȚii in lectia de educatie fizica la clasele a v-a de la &
 Lucrare de licenta ecologie si protectia mediului - aspecte ecologice privind fauna de orthoptere si mantide din parcul national muntii macinului
 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
 PROIECT ATESTAT INFORMATICA - GESTIONAREA STOCULUI UNEI FARMACII
 LUCRARE DE ATESTAT ELECTRONIST - TEHNICA DE CALCUL - Placa de baza
 Evidenta a clientilor dar si a serviciilor in Visual Fox pro 9 - Lucrare de atestat
 Lucrare atestat Tehnician in turism - CALITATEA SERVICIILOR TURISTICE




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