Mulţimi poliedrale, vârfuri şi soluţii admisibile de bază

Mulţimea de soluţii a unui sistem de ecuaţii şi inecuaţii lineare o numim mulţime poliedrală. Mulţimea poliedrală e numită poliedru convex dacă este mărginită, adică se conţine într-o sferă de rază finită cu centrul în originea de coordonate. Se numeşte punct de vârf, sau vârf al mulţimii X, punctul x care nu aparţine nici unui segment ce uneşte două puncte diferite ale mulţimii X. Punctele de vârf ale unei  mulţimi poliedrale mai sunt numite şi puncte de colţ.

Cea mai mică mulţime convexă care conţine mulţimea dată se numeşte învelitoare convexă. Existenţa învelitoarei convexe o garantează teorema despre convexitatea intersecţiei unei mulţimi de mulţimi convexe. Astfel, e valabilă şi o altă definiţie a învelitoarei convexe, echivalentă cu cea de mai sus:  intersecţia tuturor mulţimilor convexe ce conţin mulţimea dată e numită învelitoare convexă a acestei mulţimi.

Combinaţia liniară λ1x1 + λ2x2 +…+ λkxk a unui sistem de vectori (puncte) x1, x2,… xk ∈ Rn e numită:

  1. conică, dacă λj≥0, j=1,…,k;
  2. afină, dacă λ12+…+λk=1;
  3. convexă, dacă λj≥0, j=1,…,k,  λ12+…+λk=1.

Teorema 1. I. Orice poliedru convex coincide cu învelitoarea convexă a vârfurilor sale.
II. Orice poliedru convex coincide cu mulţimea combinaţiilor convexe ale vârfurilor sale.
III. Învelitoarea convexă a unui număr finit de puncte reprezintă un poliedru convex.

Vom cerceta problema standard de programare liniară:

cTx → max,______(1)

Ax  =  b,________ (2)

x ≥ 0,___________(3)

A – matrice m×n, x, c ∈ Rn, b ∈ Rm. Vom nota cu X mulţimea de soluţii admisibile a sistemului (2)-(3). Evident, dim(X) ≤ n – rang(A). Reamintim că mulţimea X este convexă.

Vom presupune, în continuare, că X≠Ø şi rang(A) = m. Ca urmare m ≤ n. Problema (1)-(3) poate fi interpretată astfel: dintre toate reprezentările vectorului b ca o combinaţie conică a vectorilor-coloane A1, A2 ,…, An ai matricei A de ales acea reprezentare pentru care valoarea funcţiei obiectiv (1) este maximă.

Punctul x=(x1, x2,…, xn)T ce satisface sistemul (2) se numeşte soluţie de bază a sistemului (2) (a problemei (1)-(3)) dacă sistemul de vectori-coloane ale matricei A, ce corespund componentelor nenule ale lui x, este liniar independent. Bază, corespunzătoare soluţiei de bază x, vom numi orice sistem din m vectori-coloane ai matricei A care este liniar independent şi include toate coloanele matricei A ce corespund componentelor nenule ale lui x.

Dacă  Aj1, Aj2, …, Ajm (ji< jk,  pentru i<k) sunt m coloane liniar independente ale matricei A, B este matricea formată din aceste m coloane şi J={j1, j2,…, jm} este mulţimea indicilor, atunci punctul x cu componentele:

xj = (B-1b)j, dacă  j∈J,
xj = 0, în caz contrar,

este soluţie de bază ce corespunde bazei B;  B-1 – inversa matricei B; xj, j∈J, – variabile de bază; restul variabilelor – libere (secundare, nebazice). Soluţia de bază se numeşte soluţie admisibilă de bază (soluţie de reper, soluţie realizabilă) dacă ea satisface condiţiile de nenegativitate (3).

Notând: cu xB vectorul format din componentele variabilelor de bază; cu xS vectorul format din variabilele secundare; cu S matricea formată din coloanele matricei A, corespunzătoare variabilelor secundare, (2) se scrie

BxB + SxS = b.

Înmulţind la stânga cu B-1, ajungem la expresia xB = B-1b – B-1S xS, din care se obţine soluţia de bază xB=B-1b, xS=0.

Teorema 2. Punctul x ∈ X este vârf al mulţimii X , dacă şi numai dacă  x este soluţie admisibilă de bază.

Demonstraţie. Necesitate. Fie  x=(x1, x2,…, xn)T un punct de vârf al mulţimii X. Evident – este edmisibil.  Pornind de la contrariu, vom presupune că  x  nu este soluţie admisibilă de bază, adică vectorii Aj1, Aj2, …, Ajr, ce corespund componentelor nenule ale lui x, sunt liniar dependenţi,  adică există numerele δ1, δ2,…, δr, nu toate nule, pentru care

δ1Aj1 + δ2Aj2 + … + δrAjr =0. _____(4)

Deoarece xjk >0 (k=1,…,r), conchidem că există β >0, suficient de mic, astfel că:

xjk + βδk ≥ 0,
xjk + βδk ≥ 0,

pentru k=1,…,r. De aici şi din (4) rezultă că x’= x + βδ, x”=  x – βδ, sunt soluţii admisibile. Deci  x poate fi reprezentat ca o combinaţie liniară a punctelor x’, x”, adică, spre exemplu, x=1/2 x’+ 1/2 x”, ceea ce contrazice ipoteza că x e punct de vârf.

Reciproc, fie  x o soluţie admisibilă de bază. Reiese că vectorii Aj1, Aj2, …, Ajr, corespunzători componentelor nenule ale lui x, sunt liniar independenţi, iar reprezentarea b=xj1Aj1+ xj2Aj2+ …+ xjrAjr este unică. Din această unicitate şi din (3) rezultă că x nu poate fi reprezentat ca o combinaţie convexă a altor două puncte admisibile. Q.E.D.

Teorema 3. Dacă problema (1)-(3) are soluţii admisibile X≠∅, atunci ea are cel puţin o soluţie admisibilă  de bază (X are cel puţin un vârf).

Demonstraţie. Reamintim supoziţia rang(A)=m. Fie x o soluţie admisibilă. Vom construi în baza ei o soluţie admisibilă de bază presupunând că x are n-r componente nule şi r componente pozitive. Fără a reduce din generalitate, fie xj=0, j=r+1,…,n, şi

x1A1 + x2A2 + … + xrAr = b,______(5)

unde xj>0,  j=1,…,r;  Aj, j=1,…,r, – coloane ale matricei A. Dacă Aj, j=1,…,r, sunt liniar independente, atunci r ≤ m şi x este soluţie admisibilă de bază cu m-r componente de bază nule.

Dacă Aj, j=1,…,r, sunt liniar dependente, atunci

α1A1 + α2A2 + … + αrAr=0,

pentru careva αj, j=1,…,r, ce nu sunt concomitent nule. Fie αk>0. Atunci:

Ak=-∑rj≠k,j=1 αjAj / αk_______ (6)

şi, substituind (6) în (5), obţinem:

0Ak +∑rj≠k, j=1 (xj – αjxkk) Aj=b.

Selectînd k astfel ca

xkk= minα_j >0 xjj,

obţinem că x’ cu componentele:

x’j = xj – αjxkk ≥ 0,  j=1,…,r, j≠k;
x’j = 0, j=r+1,…,n,____________

constituie o soluţie admisibilă de bază cu cel mult r-1 componente pozitive. Aşadar, numărul componentelor pozitive s-a micşorat.

Repetând acelaşi procedeu, vom ajunge la situaţia când numărul componentelor pozitive nu va depăşi m, indiciu că soluţia admisibilă de bază a fost construită.  Q.E.D.

Teorema 4. Dacă problema (1)-(3) are valoare optimă finită, ea se atinge şi într-un punct de vârf al mulţimii admisibile X.

Demonstraţie. Deoarece (1)-(3) are soluţie optimă, rezultă că există un aşa punct x* pentru care se atinge valoarea optimă α* = cTx*. Poliedrul definit de sistemul

cTx = α*,
Ax =b,___
x ≥ 0,____

reprezintă mulţimea  X* de soluţii optime. Conform teoremei 3, X* conţine cel puţin un punct de vârf. Q.E.D.

Teorema 5. Orice punct de maxim local al problemei (1)-(3) este şi punct de maxim global.

Demonstraţie. De la absurd, fie xº ∈ X un punct de maxim local iar x* ∈ X un punct admisibil în care cTx* > cTxº. De aici şi din relaţia

cT(λx* + (1-λ)xº) = λcTx* + (1-λ)cTxº,

adevărată pentru orice λ ∈ [0, 1], reiese că   cT(λx* + (1-λ)xº)> cTxº. Valoarea λ poate fi oricât de apropiată de zero mică şi atunci x= λx* + (1-λ)xº ∈ X poate fi apropiat oricât de mult de xº, ceea ce contravine ipotezei că xº este punct de maxim local, existând puncte x=λx*+ (1-λ)xº în vecinătatea oricât de apropiată a lui xº în care valoarea funcţiei obiectiv este mai mare decât în xº.  Q.E.D.

Teoremele 2-5 ne dau posibilitatea să conturăm o metodă, deocamdată ipotetică, de soluţionare a problemelor de programare liniară (1)-(3) în cazul în care se ştie că problema are soluţie finită. Se  construieşte mulţimea soluţiilor admisibile de bază (care conţine nu mai mult decât Cnm elemente în problema standard) şi pentru fiecare soluţie admisibilă de bază se calculează valoarea funcţiei obiectiv. În calitate de soluţie optimă se alege elementul pentru care valoarea funcţiei obiectiv este maximă. Practic, procedeul se realizează în baza metodei Gauss-Jordan de soluţionare a sistemelor de ecuaţii liniare şi se numeşte metodă simplex de rezolvare a problemelor de programare liniară.

Sursa: V. Ungureanu, Programarea Matematică, Chişinău, USM, 2001.

http://www.youtube.com/p/7128910CD2E1A695?hl=en_US&fs=1

Anunțuri

6 comentarii la “Mulţimi poliedrale, vârfuri şi soluţii admisibile de bază

  1. Draga Valeriu,
    Daca te-as fi avut profesor de matematica , mi-ar fi placut sa aprofundez aceasta disciplina.
    Asa am fost nevoita sa aleg un domeniu in care pot trisa , adica il pot face si modifica conform simtirii mele.

  2. Multumesc, Mariana! Ne realizam destinele, fiecare in domeniul sau! Toate sunt importante, si ratiunea, si simtirile, si…! Sincer, mi-ar placea sa am mai multe vieti, ca sa pot incerca mai multe destine! Dar… E bine ca avem macar unul 😉

  3. Salutare dl Valeriu,

    Sunt și eu o fostă studentă a USM. Îmi sunteți cunoscut, dar nu am făcut lecție cu dvs. Am obținut titlu de magistru în matematică cu media generală 8,50 (opt, 50) în anul 2002.
    În funcție de profesor, am lucrat doar doi ani de zile, la scoala Nr.35, Ciocana și la liceul Liviu Deleanu, Buicani.
    Am avut și eu, ca toată lumea provocări în viața. Am părăsit casa părintească în anul 2003, pe când aveam 23 ani. Plecasem în lumea mare și anume Ialia. În Moldova m-am întors pe 2 aprilie 2010. Din anumite motive peronale, nu am reușit să mă angajezi nici la un serviciu, însă aproximativ de o lună lucrez la compania WebNg. De blogul dvs. am aflat de la managerul companiei Vitalie Lazu, și el un fost student al USM, specialitatea fizica.
    De puțin timp am și eu blogul meu. Nu am încă experiență de a lucra bine cu un blog, dar munca mă va ajuta să definesc sensul propriei valori.
    Lumea are nevoie de oameni de spirit, energici, ambițioși cu o etică solidă a muncii. Persoanele sincere dedicate propriei munci se întâlnesc atât de rar, încât sunt privite deseori ca persoane dubioase. Iar asta duce la neîncredere și chiar la oprimare.
    După Anul Nou 2011, m-am apropiat de catedra de analiză matematică pentru a mă informa cum aș putea face pentru a lua doctoratul în matematică. Multe nu le cunosc, dar toți oamenii prin natură au dorința de a ști.

    Mai jos este adresa de la un articol publicat pe blocul meu:
    http://diana.webng.md/2011/03/intrebam-ca-sa-%c8%99tim/

    Cele bune,
    Diana-Domnica.

  4. Salut, Diana,

    Ma bucur sa am un nou cititor al blogului – o fosta studenta a Facultatii de Matematica si Informatica. Ma bucur sa aflu ca esti o natura creativa si deschisa. Multi deschid bloguri si in scurt timp le abandoneaza deoarece se cere si aici o munca insistenta si de durata. Am vizitat blogul tau. Sunt teme si subiecte interesante. Iti urez succes in aceasta activitate, dar si in tot ce faci. Iti urez si succes in definitivarea unei teze de doctorat.

    Esti totdeauna binevenita pe blogul meu. Voi vizita cu placere si blogul tau.

    Numai bine!

Lasă un răspuns

Completează mai jos detaliile tale sau dă clic pe un icon pentru a te autentifica:

Logo WordPress.com

Comentezi folosind contul tău WordPress.com. Dezautentificare / Schimbă )

Poză Twitter

Comentezi folosind contul tău Twitter. Dezautentificare / Schimbă )

Fotografie Facebook

Comentezi folosind contul tău Facebook. Dezautentificare / Schimbă )

Fotografie Google+

Comentezi folosind contul tău Google+. Dezautentificare / Schimbă )

Conectare la %s