PROGRAMARE LINIARA

Introducere.

Progamarea liniara, ca disciplina matematica, a aparut la mijlocul secolului nostru, primele lucrari fiind publicate de L. Kantorovici (1939) si F. Hitchcock (1941).Primele probleme rezolvate se refereau la organizarea optima a transporturilor maritime, necesitatile de aprovizionare a frontului, planificarea misiunilor aviatiei de bombardament.In 1947 G. Dantzig si J. Von Newmann creeaza metoda simplex care sta la baza rezolvarii problemelor de programare liniara. Ulterior programarea liniara a cunoscut un mare avant prin lucrarile unor matematicieni si economisti ca T. Koopmans, L. Ford, D. Fulkerson, W. Cooper, H. Kuhn, gasindu-si un camp foarte larg de aplicatii in economie.Necesitatile reale ale vietii economice au condus la aparitia si dezvoltarea altor tipuri de programari, cum ar fi:

programarea patratica,

programarea convexa,

programarea in numere intregi,

programarea stohastica,

programarea dinamica,

toate acestea fiind inglobate in termenul generic de programare matematica.

3.1 Determinanti numerici

Fie data o matrice patratica arbitrara de ordin n:

Fiecarei din matricele de acest tip ii poate fi asocia o valoare numerica, numita determinant. Vom defini aceasta valoare in mod inductiv, folisind pentru determinantul matricei A notatia det(A) .

I.   Ordinul matricei A este 1. Matricea este formata dintr-un singur element a₁₁. Determinantul matricei A va fi chiar valoarea elementului a₁₁.

Exemplu:

II.     Pentru o matrice de ordinul 2

determinantul va fi egal cu valoarea expresiei a₁₁a₂₂ - a₁₂a₂₁ (diferenta produselor elementelor de pe diagonala principala si cea secundara).

Exemplu:

III.   Pentru o matrice de ordinul 3
 
determinantul poate fi calculat folosind regula lui Sarrus (regula diagonalelor si a triunghiurilor). Termenii cu semnul (+) in suma ce corespunde valorii determinantului se obtin inmultind elementele de pe diagonala principala si cele din virfurile triunghiurilor, care au bazele paralele cu diagonala principala (fig 1). Termenii cu semnul (-) se obtin inmultind numerele de pe diagonala secundara si cele din virfurile triunghiurilor, care au bazele paralele cu diagonala secundara (fig 2).

Astfel, pentru o matricea (1) determinantul poate fi calculat direct dupa formula:

Exemplu:

Pentru definitia determinantului unei matrice de ordin n se va folosi suplimentar notiunea de minor:

Vom cerceta matricea din exemplul precedent. Pentru a calcula minorul A_1,2 a elementului a_1,2 vom exclude din matrice linia 1 si coloana 2:

IV.

O generalizare a acestei definitii este data urmatoarea teorema:

Conform definitiei

Fie data matricea de ordinul 4:

Fiecare dintre minorii A_1,j , j=1,..,4 este determinantul unei matrice de ordinul 3 si poate fi calculat direct.

Algoritmul de calcul.

Fie data matricea A de ordinul n:

Algoritmul de calcul al determinantului unei matrice de ordin n se bazeaza direct pe definitie.

Vom folosi dezvoltarea determinantului dupa prima linie a matricei.

In aceasta formula elementele necunoscute sint minorii elementelor din prima linie. Fie un minor arbitrar A_1,j. El este determinantul unei matrice de ordinul n-1. Pentru a-l calcula urmeaza sa rezolvam o problema echivalenta cu problema initiala, dar de dimensiune mai mica. Deoarece se respecta regula de consistenta putem aplica un algoritm recursiv.

a) Exista un caz elementar: matricea, ce corespunde minorului curent are ordinul 1

b) La nivelul k se fac k apeluri pentru pentru calculul determinantilor de ordin k-1. Prin urmare procesul converge spre un caz elementar.

Fie matricea A are ordinul R

Algoritm (R):

Cazul elementar

Daca ordinunul matricei A este 1, atunci determinantul este egal cu valoarea unicului element al matricei.

In caz contrar

Cazul de reducere

Se dezvolta determinantul matricei A dupa prima linie. Valoarea determinantului  se initializeaza cu 0.

Pentru j de la 1 la R

a.  Se formeaza matricea prin excluderea din matricea curenta A a liniei 1 si coloanei j. (Ordinul este R-1. Ea corespunde minorului)

b. Se calculeaza determinantul det() al matricei utilizind algoritmul curent.

c.  Se actualizeaza valoarea determinantului D= D+ (-1)^1+jdet()

Urmatoarele proprietati ale determinantilor permit calculul lor fara a recurge la calcularea minorilor.

Aceste trei proprietati permit elaborarea unui algoritm simplu pentru calculul determinantilor.

Primul algoritm de calcul al determinantilor de ordin n se va baza pe proprietatile 1-3, enumerate anterior. Scopul este de a aduce determinantul la forma triunghiulara (adica de o parte a diagonalei principale sa fie doar zerouri). Pentru a realiza acest scop, se va folosi iterativ proprietatea 3:

Fie pe linia i elementul a_ii 0. Daca linia i se inmulteste cu - a_ki/a_ii si se adauga la linia k

valoarea determinantului nu se va schimba. In acelasi timp, elementul a_ki va deveni 0. Intr-adevar, pentru el se obtine: a_ki + a_ii (- a_ki/a_ii ) = a_ki + (- a_ki ) = 0. Prin urmare, in cazul aplicarii consecutive a acestei proceduri pentru toti k > i, in coloana i a determinanului mai jos de diagonala principala apar zerouri. De aici rezulta si algoritmul integral:

Numarul liniei (i) - 0

Numarul liniei se mareste cu 1 (i:=i+1)

A. Daca elementul a_ii 0 atunci consideram j:=i+1;

si pentru fiecare din liniile (j) de la i+1 la n repetam procedura (P):

(P) linia i o inmultim cu - a_ji/a_ii si o adaugam la linia j

B. Daca a_ii = 0 atunci mai intii cercetam elementul a_ji pe liniile situate sub linia i (coloana i). Daca detectam un element nenul (fie in linia k), schimbam cu locurile liniile i si k, apoi realizam procedura (P). Daca toate elementele in coloana i situate mai jos de rindul i sint 0, atunci valoarea determinantului este 0, corespunzator se incheie lucrul algoritmului.

Daca i< n revenim la pasul 1.

Calculam produsul elementelor de pe diagonala principala

Forma standard a problemelor programarii liniare.

S-ar parea ca diferite probleme ale programarii liniare se formuleaza si rezolva in mod diferit. In general insa ele toate pot fi aduse la o forma standard, in care functia scop trebuie minimizata, iar toate sistemele de restrictii sunt egalitati cu variabile nenegative.

Vom aduce orice problema la forma standard, folosind urmatorul set de reguli:

Maximizarea functiei scop z = c x + c x + . + c_nx_n este echivalenta cu minimizarea functiei
z = -c x - c x - . - c_nx_n

Restrictiile in forma de inegalitati cu semn pot fi aduse la egalitate prin adaugarea unei variabile suplimentare (auxiliare), de ex. a_j x + a_j x + . + a_jnx_n b_j se inlocuieste prin

a_j x + a_j x + . + a_jnx_n + x_n+j = b_j . Variabila noua (x_n+j ) este si ea nenegativa. Exact la fel se aduc la egalitate si inegalitatile, care contin

de ex. a_j x + a_j x + . + a_jnx_n b_j se inlocuieste prin

a_j x + a_j x + . + a_jnx_n - x_n+j = b_j . Variabila noua (x_n+j) este si ea nenegativa.

Daca o careva variabila poate primi orice valori, iar restrictiile cer valoarea ei pozitiva, o putem aduce la forma x_k = x _k - x _k unde x _k 0 si x _k

Asa dar, forma generala a problemei programarii liniare este: de a minimiza functia  
z = c^Tx (c, x - vectori)

in conditiile

x

si Ax = b, unde b > 0

Problema adusa la forma standard contine nu numai variabilele initiale, ci si cele suplimentare, introduse in procesul de egalizare a matricei.

Exemplul 1. De a minimiza functia z = - 3x₁ - 4x₂ in restrictiile x₁ , x₂ 0 si

x x x + x + x₃ = 20

-x + x 20 -x + x + x = 20

x x + x = 10

x 5 x + x = 5

In forma matriceala problema poate fi expusa in felul urmator:

si x_j 0 j= 1,2,..n

Pentru primul exemplu avem un sistem de ecuatii cu 6 variabile din 4 ecuatii, pentru al doilea - din 2 ecuatii cu 4 necunoscute.

In caz general, daca avem m ecuatii cu n necunoscute (n > m), putem egala cu 0 n-m din variabile, iar pentru celelalte m variabile de rezolvat sistemul de ecuatii prin careva metoda numerica. Daca solutia obtinuta este unica, ea se numeste si bazica. Daca e admisibila se numeste solutie bazica admisibila. Variabilele care au fost egalate cu 0 se numesc nebazice (auxiliare), celelalte - bazice si formeaza o baza.

GENERALIZARI

Problema programarii liniare se rezolva simplu in plan, dar nu si in spatiul n-dimensional. Vom da cateva definitii, care ne vor ajuta in motivarea metodei de rezolvare a problemei:

punct al spatiului n-dimensional - vectorul x echivalent

Segmentul PQ, unde P, Q sunt 2 puncte reprezentate de vectorii p, q e format din punctele, pentru care este adevarata afirmatia:

ap a )q; 0 a

Def. Multimea se va numi convexa, daca pentru orice 2 puncte ale ei P si Q segmentul PQ de asemenea apartine multimii.

Def. Punct extremal al multimii convexe, va fi orice punct, care apartine multimii, dar nu este punct interior nici pentru un segment, care uneste 2 puncte ale multimii date.

Def. Invelis convex al punctelor P₁, P₂, P₃, . P_n, preyentate prin vectorii p₁, p₂, p₃, . p_n va fi multimea de puncte determinate de relatia

a p₁ a p₂ + a p₃ a_np_n 0 a_i

si

Exemple 1 - multime convexa, 2 - neconvexa.

Rezultatele de baza ale programarii liniare:

Din cele expuse mai sus putem realiza urmatoarea forma a problemei de programare liniara:

de minimizat functia z =c x + c x + . + c_nx_n in setul de restrictii:

a x₁ + a x + . a _nx_n = b

a x + a x + . a _nx_n = b

a_m x + a_m x + . a_mnx_n = b_m,   si x ,x , . x_n > 0.

Restrictiile pot fi date in forma matriceala Ax = b, x > 0, unde matricea A are rangul m.(<n).

Pentru calculul solutiei problemei vom folosi urmatoarele afirmatii (fara demonstratie:)

Afirmatia 1 Daca restrictiile au o solutie admisibila, atunci ele au si o solutie bazica

Afirmatia 2 Domeniul solutiilor admisibile este o multime convexa.

Afirmatia 3 Solutiile admisibile bazice corespund punctelor extreme a multimii convexe.

Afirmatia 4 Daca functia scop are un minimum finit, atunci cel putin una din solutiile optimale este bazica.

ALGORITMUL SIMPLEX

Este un algoritm aplicativ, care a fost realizat inca pana la utilizarea calculatoarelor electronice, dar putin utilizat din motivul unui volum mare de calcule, necesare de efectuat. Algoritmul este prezentat in forma algebrica, ceea ce usureaza mult procesul de programare a lui.

Metoda simplex pentru o solutie initiala bazica admisibila data.

Fie data problema:

de minimizat functia z =c x + c x + . + c_nx_n in setul de restrictii:

a x + a x + . a _nx_n = b ,A

a x + a x + . a _nx_n = b

a_m x + a_m x + . a_mnx_n = b_m,   si x ,x , . x_n > .

sau Ax = b, x > 0, in presupunerea existentei unei solutii bazice, care satisface conditiile initiale.

Se pune problema de a gasi o asemenea solutie bazica, care ar satisface restrictiile problemei. Pentru aceasta e necesar de determinat o matrice nesingulara (determinantul careia e diferit de 0) B (m x m) generata de m coloane ale matricei A. Daca aceste coloane corespund variabilelor x ,x , . x_m atunci blocul de restricti poate fi modificat astfel, incit aceste variabile sa fie exprimate prin vectorul b si celelalte variabile, care nu intra in baza. Atunci blocul de restrictii poate fi adus la forma:

x + . + . + a _m+ x_m+ + a _m+ x_m+ . + a _1nx_n = b

x + . + a _m+ x_m+ + a _m+ x_m+ . + a _nx_n = b

x_m+ a _{m m+} x_m+ + a _{m m+} x_m+ . + a _mnx_n = b _m,

si x ,x , . x_n >

Daca in (*) vom inmulti fiecare din restrictii corespunzator la c_i, apoi vom scadea rezultatele din functia scop, variabilele x ,x , . x_m vor fi excluse din finctia scop, care va capata forma:

c _m+ x_m+ + c _m+ x_m+ + . + c _nx_n = z - z (**) unde

Transformarile realizate nu schimba relatiile din expresia initiala, deci solutiile noii probleme sunt aceleasi ca si pentru cea initiala. Expresiile (*) si (**) se numesc formele canonice ale bazei x ,x , . , x_m . Daca vom considera x_m+ , x_m+ , x_n egale cu 0, atunci setul

x =b ; x =b ; . x_m =b _m; x_m+ ; x_m+ ; . x_n = descrie o solutie bazica. Daca toti b _i atunci solutia este si admisibila.

Metoda simplex consta in determinarea unei solutii initiale admisibile, prin crearea unei baze de variabile, apoi in imbunatatirea acestei solutii pana cand e posibil, inlocuind cate una variabilele din baza.

Exemplul 1

x₁ - x₂ = z

x x

x x

x x

Aducem problema la o forma standard:

x x + x =

x x + x =

x x = z

coeficientii b_i sunt pozitivi, variabilele noi au coeficientii 1, deci solutia

(0, 0, 1700, 1600) este admisibila.

Deoarece functia scop este exprimata prin variabilele nebazice cu coeficienti negativi, orice crestere a valorilor acestor variabile va da o micsorare a functiei scop. Alegem una din variabilele x sau x (care nu intra in baza) si ii dam crestere. Cresterea ei nu poate fi infinita, deoarece influenteaza asupra valorilor variabilelor din baza. Fie ca am ales x₂ pentru introducere in baza (in functia scop coeficientul lui este mai mare).

Deoarece

x x + x = T x daca x

x x + x = T x daca x

Deci nu putem mari valoarea lui x mai mult decat cu (minimul din valori) fara a transforma x intr-o marime negativa.

A doua ecuatie a sistemului de restrictii poate fi prezentata in felul urmator:

2/5x + x + 1/5x =

Pentru a elimina variabila x₂ din celelalte restrictii si functia scop, inmultim ecuatia aleasa cu coeficientii respectivi si o adunam la restrictii sau functia scop. In exemplul de mai sus, inmultind-o cu 4 o scadem din prima ecuatie a blocului de restrictii, iar inmultind-o cu -4 - din functia scop.

In rezultat obtinem excluderea ei din toate ecuatiile, cu exceptia celei de-a doua restrictii.

Problema initiala capata forma:   

7/5x + x + 4/5 x =

2/5x x + x =

-2/5x + 4/5 x = z +

baza fiind formata din variabilele x si x . Studiind functia scop observam, ca putem micsora valoarea ei doar in procesul cresterii lui x . Cu cat?

Prima ecuatie din blocul de restrictii il trece pe x₃ in 0 pentru x

A doua ecuatie din blocul de restrictii il trece pe x₃ in 0 pentru x Valoarea minimala este 300. Excludem x din cealalta restrictie, apoi din functia scop:

x + + 5/7x - 4/7 x =

x - 2/7 x + 3/7 x =

2/7x + 4/7 x = z +

Observam, ca majorarea oricarei variabile din functia scop ar duce la cresterea ei, deci minimul a fost obtinut.

Procesul iterativ se ilustreaza mai bine prin tabele simplex, construite dupa urmatoarea regula:

In caz general tabelul are forma

Insasi procesul iteratiei se divide in trei etape (pasi)

Determinarea variabilei pentru includerea in baza. Fie x_m+1 x_m+2 x_{m+3 .} x_n nebazice. Determinam minimul dintre coeficientii c_m+1 c_m+2 c_{m+3 .} c_n . Fie acesta c_s . Daca el este negativ, atunci cresterea x_s va duce la minimizarea functiei scop.

D e terminarea variabilei, ce urmeaza a fi exclusa din baza Cu cat putem majora variabila noua x_s fara a schimba semnul variabilelor bazice? Daca in restrictia i a _is >0 atunci valoarea maximala pe care o poate primi x_s este b _i / a _is , altfel x_i va deveni negativ. Daca in restrictia a _is < 0 atunci la cresterea x_s variabila x_i va creste si ea. Asa dar x_s poate fi majorat pana la

Daca acest minimum se obtine in randul r x_r se transforma in 0 cand x_s = b _r/ a _rs celelalte variabile ramanand nenegative.

a _rs - elementul pivot

randul r - rand pivot

coloana s - coloana pivot.

Construirea noii forme canonice Noua baza e x , x , x , . ,x_s , .. x_m Mai intai coeficientul de pe langa x_s in randul pivot il facem 1, impartind tot randul la a _rs, apoi lichidam x_s din celelalte restrictii. Pentru aceasta din randul i (i r) cu coeficientul a _is pe langa x_s vom scadea a _ss x (randul pivot ). Pentru a transforma functia scop cu coeficientul c _s ( < 0 ) vom scadea c _s x (randul pivot) din functia scop. Dupa realizarea transformarilor, tabela va avea forma:

unde:

b⁺_{r =} b^'_r / a'_rs

a⁺_{r,j =} a^'_r,j / a'_rs j= 1, .. , n

b⁺_{i =} b^'_i - a'_is b⁺_r    i r

a⁺_ij = a^'_ij - a^'_is a⁺_r,j i r

c⁺_j = c _j - c _s a⁺_r,  j= 1, .. , n

z⁺₀ = z + c _s b⁺_r

Dupa constructia noului tabel se verifica prezenta coeficientilor negativi in functia scop. In cazul existentei se va repeta inca o iteratie.

Exemplu:

x x + x =

x + x + x =

x x = z

In cazul cand valori negative nu sunt, dar este 0, avem mai multe solutii optimale. In acest caz le putem genera repetand iteratiile dupa elementele cu indicatori nuli.

Exemplu:

x - x - x =

x + x =

-x - x = z

Includem in baza x₁ si x_4. Atunci x = x + x + , sau z = - x - x

In cazul, cand avem valori negative, dar coeficientii coloanei pivot sunt 0 sau negativi, avem o crestere infinita dupa variabila respectiva.