Rolul calculatorului în rezolvarea problemei complementarității

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: 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: 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). 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: z1 +z2 = = =q (1. 4) -1 -2 -6 q2 z1 (0, z2 (0 exprimat ca o combinatie liniara nenegativa de vectorii si -2 -1 Multimea tuturor combinatiilor lineare nenegative de vectori si -1 -2 -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. P.

C.

L. (1. 1) este de ordin 2. Intr-o P.

C.

L. de ordin n vor fi 2n variabile. Problemele de ordin 2 pot fi rezolvate prin trasarea tuturor conurilor complementare si verificarea daca vectorul q se afla in aceste conuri. Pentru rezolvarea problemelor de ordin mai mare avem nevoie de algoritmi eficienti si calculatoare care pot obtine solutii folosind acesti algoritmi.

1. 2. Importanta problemei complementaritatii si rolul calculatorului in rezolvarea ei Exemplu: Fie K suprafata poliedrala convexa hasurata ca in Fig. 2. Fie P puctul de coordonate (-2, -1). Se cere sa se gaseasca punctul K cel mai apropiat de P (se considera dinstanta euclidiana). Probleme de acest fel apar foarte des in inginerie si in aplicatiile cercetarii operationale.

Fiecare punct din K poate fi exprimat co o combinatie convexa de puncte de extrem (sau puncte unghiulare) A, B, C, D, i.

e., coordonatele puctelor generale din K sunt ( (1+4 (2+5 (3+5 (4, 3 (1+0 (2+2 (3+4 (4) unde ...

C. ZIDAROIU SI S. STEFANESCU - "CERCETARI OPERATIONALE"

ALBERT G. HOLZMAN - "OPERATIONS RESEARCH METHODOLOGY"

R. FLETCHER - "PRACTICAL METHODS OF OPTIMIZATION"