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=(X₁, X₂, ,X_n) 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 X_i 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=(X₁, X₂, ,X_n) 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:

:a_lk

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 X_k care se va elimina din toate ecuatiile cu exceptia ecuatiei l. Coeficientul pe care-l are variabila X_k in ecuatia l se va numi element de pivot si trebuie sa fie diferit de zero (a_lk - elementul pivot ales in cazul nostru).

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

Se imparte ecuatia prin elementul pivot a_lk;

Ecuatia l, in noua forma, o vom inmulti succesiv cu coeficientii a_1k/a_2k//a_mk;

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

In aceste fel variabila X_k 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 X_p este o variabila de baza, iar X_q este o variabila din afara bazei se va ajunge la un sistem similar, dar in care s-a efectuat o interschimbare in sensul ca X_p nu va mai face parte din baza, iar X_q va deveni variabila a bazei.

Deoarece functia obiectiv a unei probleme de programare liniara este o expresie liniara de variabilele X_i 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 C_t ca fiind mai mic decat zero. Stiind ca X_t≥0 putem sa consideram X_t>0, iar restul variabilelor (s-a renuntat la scrierea indicilor superiori de pivotare). In acest caz functia obiectiv va avea forma:

> pentru ca C_t<0

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

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

,

Daca mai multi dintre coeficientii C_m+1 C_m sunt negativi procedeul descris ramane valabil cu conditia sa introducem in baza variabila X_t care conduce la un maxim de crestere a functiei obiectiv, adica cea pentru care coeficientul C_t 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 X_t aflat in afara bazei si caruia ii corespunde C_t<0 vom avea conditia ca a_it≤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 X_n+1, X_n+2, , X_n+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 b_i 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 X_i=0, .

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