Problema complementarității

Capitolul 1

Problema complementaritatii

1.1.Introducere

Fie Rn un spatiu vectorial euclidian de dimensiune n.Fie M o matrice patratica de rang n si q un vector coloana in Rn.Se considera problema:sa se gaseasca w1,..,wn,z1,…,zn cu proprietatille:

w-Mz=q, w 0, z 0 si wizi=0 pentru toti i

Ca un exemplu concret,fie

2 1 -5

n=2 M= q=

1 2 -6

Pentru acest caz,problema asociata ce trebuie rezolvata este:

w1 -2z1-z2 = -5

w2-z1-2z2= -6 (1.1)

cu variabilele w1,w2,z1,z2 0 si w1z1=w2z2=0

Probleme de acest fel,cunoscute sub denumirea de problemele complementaritatii liniare (P.C.L.) ,se pot intalni in programarea liniara,programarea patratica,in teoria jocurilor si in numeroase alte domenii.Problema (1.1) poate fi scrisa si sub forma de ecuatie vectoriala:

1 0 -2 -1 -5

w1 +w2 +z1 +z2 = (1.2)

2 1 -1 -2 -6

w1,w2,z1,z2 0 si w1z1=w2z2=0 (1.3)

Pentru orice solutie care satisface (1.3),cel putin una dintre variabilele din perechea (w1,z1) trebuie sa fie egala cu zero,deoarece w1z1=0.Analog si pentru perechea (w2,z2).O metoda de rezolvare pentru aceasta problema este:se alege cate o variabila din fiecare pereche (w1,z1),(w2,z2) si se egaleaza aceste variabile cu valoarea zero in sistemul de ecuatii (1.2).Variabilele ramase in sistem se numesc variabile active.Dupa eliminarea variabilelor nule din (1.2),daca sistemul obtinut are o solutie in care varibilele active sunt nenegative,aceasta va fi solutie pentru (1.2),(1.3).

-2 -1

Fig.1. Pos ,

-1 -2

Notam cu (q1,q2) vectorul constant (-5,-6) din (1.2).Alegem w1,w2 ca variabile cu valoare zero.Rezulta ca variabilele active sunt z1,z2.Dupa

inlocuirea w1,w2=0 in (1.2),sistemul obtinut este:

-2 -1 -5 q1

z1 +z2 = = =q (1.4)

-1 -2 -6 q2

z1 0 , z2 0

Sistemul redus (1.4) are o solutie daca si numai daca vectorul q poate fi

-2 -1

exprimat ca o combinatie liniara nenegativa de vectorii si

-1 -2

-2 -1

Multimea tuturor combinatiilor lineare nenegative de vectori si

-1 -2

reprezinta un con in spatiul de coordonate q1 si q2 ,ca in Fig1.Daca vectorul

-5

dat q= se afla in acest con. Atunci P.C.L.(1.1) are o solutie in care

-6

variabilele active sunt z1 , z2 si w1=w2=0.

Verificam daca punctul (-5,-6) se afla in acest con si daca solutia pentru (1.4) este (z1 , z2 )=(4/3,7/3) si rezulta ca solutia pentru (1.1) este

(w1,w2 , z1 , z2 )=( 0,0,4/3,7/3).

Conul din Fig.1 se numeste conul complementar asociat P.C.L (1.1).Conurile complementare sunt generalizari ale claselor de sferturi de cerc sau ale claselor de ortanti.