Problema Complementaritatii

Imagine preview
(8/10 din 1 vot)

Acest curs prezinta Problema Complementaritatii.
Mai jos poate fi vizualizat cuprinsul si un extras din document (aprox. 2 pagini).

Arhiva contine 1 fisier doc de 82 de pagini .

Iti recomandam sa te uiti bine pe extras, cuprins si pe imaginile oferite iar daca este ceea ce-ti trebuie pentru documentarea ta, il poti descarca.

Fratele cel mare te iubeste, acest download este gratuit. Yupyy!

Domeniu: Matematica

Cuprins

CAP.1.PROBLEMA COMPLEMENTARITATII
1.1.Introducere 4
1.2.Importanta problemei complementaritatii si rolul
calculatorului in rezolvarea ei 7
1.3.Notatii 10
1.4.Conurile complementare 12
1.5.Problema complementaritatii liniare 14
1.6.Aplicatii 15
1.6.1.Programarea liniara 15
1.6.2.Programarea patratica 17
1.6.3.Jocuri de doua persoane 18
1.6.4.Alte aplicatii 19
1.7.Clase de matrici 20
1.8.Algoritmi pentru rezolvarea problemei
complementaritatii liniare 21
1.8.1.Bazele 22
1.8.2.Operatii pivot 24
1.8.3.Baza initiala 26
1.8.4.Proprietatile bazele 27
1.8.5.Bazele complementare admisibile aproape
adiacente 28
1.8.6.Regula pivotului complementar 28
1.8.7.Incheierea 29
1.9.Exemple numerice 30
1.10.Conditii 35
1.11.Alti algoritmi 35
1.12.Rezumat al rezultatelor teoretice 36
1.13.Probleme nerezolvabile 36
1.14.Problema complementaritatii neliniare 37
1.15.Metode de calcul a punctelor fixe 38
CAP.2.PROBLEMA COMPLEMENTARITATII IN
PROGRAMAREA PATRATICA
2.1.Restrictii ecuatii 41
2.2.Metoda multiplicatorilor Lagrange 53
2.3.Metoda multimii active 58
2.4.Proprietati avansate 65
2.5.Probleme speciale de programare patratica 68
2.6.Pivotarea complementara si alte metode 72
2.7.Exercitii 81
BIBLIOGRAFIE 82

Extras din document

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.

Fisiere in arhiva (1):

  • Problema Complementaritatii.doc