CuprinsIntroducere 31 Teoriaproblemelordeoptimizareliniarcurestricii 71.1 Forme ale modelului de optimizare liniar cu restricii . . . . . . . . . 71.2 Soluii ale problemei de optimizare liniar cu restricii . . . . . . . . . 91.3 Trecereaunei problemedeprogramareliniarcurestricii delaoform matematic de prezentare la alta. . . . . . . . . . . . . . . . . 131.4 Rezolvarea numeric a modelelor cum restricii i dou variabile . . . 181.5 Rezolvarea numeric a problemelor de programare liniar cu restriciicu algoritmul simplex primal . . . . . . . . . . . . . . . . . . . . . . . 261.6 Rezolvarea modelelor care nu admit soluii de baz iniial . . . . . . 361.7 Dualitatea n programarea liniar . . . . . . . . . . . . . . . . . . . . 411.8 Algoritmul simplex dual . . . . . . . . . . . . . . . . . . . . . . . . . 461.9 Determinareasoluiilorproblemei dualecuajutorul ultimului tabelsimplex al problemei primale. . . . . . . . . . . . . . . . . . . . . . . 491.10Reoptimizarea soluiilor unei probleme de programare liniar. . . . . 521.11Programare discret . . . . . . . . . . . . . . . . . . . . . . . . . . . 581.11.1 Metode de tip tietur. Metoda lui Gomory. . . . . . . . . . 592 Modelespecialedeprogramareliniar. Problemadetransport 652.1 Formularea problemei, proprieti generale . . . . . . . . . . . . . . . 652.2 Proprieti ale matricei coecienilor . . . . . . . . . . . . . . . . . . 682.3 Proprieti grace ale problemei de transport . . . . . . . . . . . . . 682.4 Determinarea unei soluii de baz . . . . . . . . . . . . . . . . . . . . 712.5 Adaptarea algoritmului simplex . . . . . . . . . . . . . . . . . . . . . 712.6 Utilizarea problemei duale . . . . . . . . . . . . . . . . . . . . . . . . 742.7 Algoritmul de transport . . . . . . . . . . . . . . . . . . . . . . . . . 752.8 Probleme propuse i rezolvate . . . . . . . . . . . . . . . . . . . . . . 763 Elementedeteoriajocurilor 873.1 Noiuni introductive . . . . . . . . . . . . . . . . . . . . . . . . . . . 873.1.1 Noiuni de baz. . . . . . . . . . . . . . . . . . . . . . . . . . 873.1.2 Clasicarea jocurilor . . . . . . . . . . . . . . . . . . . . . . . 8814 Jocurimatriciale 894.1 Strategii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 904.1.1 Strategii optime ntr-un joc matriceal . . . . . . . . . . . . . . 904.1.2 Strategii optime ntr-un joc matriceal simetric . . . . . . . . . 954.1.3 Proprieti ale strategiilor optime i ale valorii unui joc matriceal 964.2 Principiul dominrii . . . . . . . . . . . . . . . . . . . . . . . . . . . . 974.3 Strategii pure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 994.4 Rezolvarea jocurilor matriceale . . . . . . . . . . . . . . . . . . . . . .1014.4.1 Rezolvarea jocurilor matriceale cu punct a . . . . . . . . . . .1014.4.2 Rezolvarea jocurilor matriciale prin reducere la modele de op-timizare liniar cu restricii . . . . . . . . . . . . . . . . . . .103Bibliograe 1192IntroducereCercetarea operaional este una dintre cele mai noi ramuri ale matematicii apli-cate. Ea a aprut dup 1950 i se ocup cu problema gsirii unor soluii optime sauapropiatedeceleoptimepentrufenomenedincelemaidiversedomeniialenaturiii societii.i propunesserveascfactorilordedecizielafundamentareahotrrilorlor.Problemelecareapar azi nfaafactorilor dedecizie, conductori deorganizaiieconomice sau militare, sunt att de complexe, nct vechile procedee de conducerebazate pe intuiie, experien i bun sim au devenit nesatisfctoare.Utilizareametodelorcercetriioperaionalentehnicieconomieaconduslarezultate remarcabile, ceea ce a adus dup sine dezvoltarea n continuare a cercetriioperaionale. Nusepoateconcepeconducereaunei activiti tehnico-economiceimportante fr metodele cercetrii operaionale.S-audatmultedeniii alecercetrii operaionalei auexistati multeargu-menteconformcreiacercetareaoperaionalnupoatedenit. Totui, pentrunelegerea naturii cercetrii operaionale se poate da urmtoarea deniie.Cercetarea operaional reprezint:1) aplicarea metodelor tiinice2) de ctre o echip interdisciplinar3) la studiul problemelor legate de conducerea sistemelor organizate (om-main)cuscopul obinerii unorsoluii caresserveascctmai bineintereseleorganizaiei n ansamblu.Caracteristicile eseniale ale cercetrii operaionale sunt:- abordarea n ansamblu a problemelor- utilizarea unei echipamente interdisciplinare- aplicarea metodelor tiinice la problemele de conducereNoiunidebazalecercetriioperaionaleDeniia1. Prinoperaiesenelegeunansambludeaciunindreptatesprere-alizareaunuianumitscop. Oriceoperaieareunsingurscopcarepoatecompusdin mai multe obiective.De exemplu, n cazul unei operaii dintr-o intreprindere scopul poate realizareaunui anumitnumrdeprodusentr-uninterval detimpdat, urmndobiectivele3privind satisfacerea prescripiilor de calitate, reducerea cheltuielilor materiale etc.Deniia2. Senumeteparteoperativmulimeaacelorpersoanesaufactoricare acioneaz ntr-o operaie pentru ndeplinirea scopului propus.Deniia 3. Prin mijloace active nelegem anumite resurse care stau la dispoziiaprii operative. Prinfolosirealor(deregulcheltuielilelor)parteaoperativirealizeaz scopul.Deniia4. Modul deutilizareamijloaceloractive, senumetestrategia(saupolitica) prii operative.Acele strategii care conduc la realizarea scopului se numesc strategiioptime.Problemacentralal cercetrii operaionaleestedeterminareastrategiilorop-time.Observaia1. Rezultatele unei operaii depindde strategia aleas adic de factoricontrolabili i de factori care nu pot inuenate de partea operativ i care formeazcondiiile efecturii operaiei.nagricultur,deexemplucondiiilemeteorologicereprezintfactorinecontro-labili.Modelematematicen studiul oricrei operaii (indiferent de domeniul creia i aparine) se deosebescpatru etape fundamentale:a) analiza operaiei - cutarea i descrierea mijloacelor de aciune care ar puteaduce la atingerea scopului operaieib)construireaunui model matematical operaiei caresdeaodescrierematematic a scopuluic) estimarea i compararea ecacitii diverselor strategii pe baza modeluluiconstruitd) studierea strategiilor optime i a metodelor matematice cu ajutorul crorapot obinute.Modelul trebuie s reecte ct mai exact procesul real - pe de alt parte trebuies e ct mai simplu.Nu exist o metod genaral pentru crearea unui model.Noiunea de model matematic este tot att de veche ca matematica.ncontinuareprezentmoschemgeneral, ncaresencadreaznu-meroasemodele.Desfurareaunei operaii poatedescrismatematiccuajutorul unui punctdintr-unspaiundimensional,numitspaiul fazelor. Fiex(t) =(x1(t), . . . , xn(t))punctul care descrie starea sistemului la momentult.(Presupunem cx(t) descrie complet desfurarea operaiei n cadrul modeluluimatematic.)4De obicei cu ct n este mai mare cu att desfurarea operaiei este descris maiprecis, dar pe de alt parte modelul devine mai complicat.Mijloaceleactivesuntcaracterizateprincantitatealor. Demulteori suntdediferite categorii (de exemplu bani, for de munc, maini-unelte, etc.)Matematicleputemdescriecuunvector(a1, . . . , am).Faptulcacestemijloacesuntlimitatematematic putem descrie ca: ai a0i.Posibilitiledeaciunealeprii operative(strategiile) sunt reprezentatenmodel prinalegereaunui set defuncii u1, . . . , ukcaredepindevident destareasistemului n momentul t, x(t). Aceast dependen descriem cu un sistem de ecuaiisau inecuaii cu necunoscutele(uj(t, x1, . . . , xn)).Deci, stareaxi(x1, . . . , xn) depindedestrategiauji cteodatdeoseriedefactori necontrolabili descrise matematic cu funciiley1(t), . . . , yp(t).Stadiul derealizareascopului estestabilitcuofunciereal(saumai multefuncii)notatcuf(x)-numitfunciedescop(saufunciedeecien, funcieobiectiv). Deoarece starea sistemului x, este determinat de factori controlabiliu1, . . . , uki nunelecazuri i defactori necontrolabili y1(t), . . . , yp(t)rezultcfuncia de scop este o funcional:f(u1, . . . , uk, y1, . . . , yp)Partea operativ trebuie s-i aleag funciileu1, . . . , ukastfel nct scopul urmrits e realizat.Ctevamodelematematicea) Un model de planicare a produciei.OintreprindereproducenproduseP1, . . . , Pn, folosindmresurseR1, . . . , Rm(materii prime, maini-unelte, fordemuncetc.) decaredispunencantitileb1, . . . , bm.tiindcproducereaunei uniti dinprodusul Pj, j {1, . . . , n}, aducein-treprinderii beneciulcji necesitaijuniti din resursaRi,i {1, . . . , m}seceresseplaniceproducia, adicssestabileascncecantiti sseproduc ecare dintre cele n produse astfel nct beneciul total al intreprinderii se maxim.Notmpentruecarej {1, . . . , n}cuujcantitatea(nuniti)dinprodusulPjce urmeaz a produs.Beneciul total al intreprinderii este:f(u1, . . . , un) = c1u1 + +cnun(1)iar cantitileu1, . . . , untrebuie s satisfac urmtorul sistem de inecuaii_ nj=1aijuj bi, i = 1, muj 0, j= 1, n(2)5Avemmodelul careconstnmaximizareafunciei (1)pemulimeasoluiilorsistemului (2).Modelul poate mbuntit.a) Dac se cere producerea a unor cantiti minime u01, . . . , u0n (respectiv maximey01, . . . , y0n)atunci adaugm restriciile:u0j uj, j= 1, n (sau uj y0j, j= 1, n)b) Dac se cere ca volumul total al produciei s nu coboare sub o anumit limitu0, atunci matematic avem condiia: u0 u1 + + unc) Scopul nu este neaprat maximizarea beneciului. Scopul poate s eobinereaunui venitmaximnvalutsaurealizareaunui venitmaximdevaluti realizarea unui beneciu maxim. Dac djeste venitul de valut dup produsul Pjatunci avem(c1 + d1)u1 + + (cn + dn)un(alte exemple vezi [Szab]).Principalele capitole ale cercetrii operaionale sunt:- teoria problemelor de optimizare cu restricii- teoria jocurilor- teoria grafurilor- programarea operativ a produciei- teoria stocurilor- teoria echipamentelor- teoria fenomenelor de ateptare.Cercetarea operaional este o ramur ale matematicii aplicate, ceea ce nseamnc pentru studiul modelelor sunt necesare cunotine de matematici superioare, cumar algebr liniar, analiz matematic, analiz funcional, teoria probabilitilor,ecuaii difereniale, geometrie diferenial.61TeoriaproblemelordeoptimizareliniarcurestriciiTeoriaproblemelordeoptimizarecurestricii esteoramuracercetrii oper-aionalecarestudiazoptimizareauneiasaumai multor funcii peundomeniu,denitdeomulimederestriciidateasupravariabilelorindependenteicarepotexprima diferite condiii economice.Dupnaturamatematicafunciei(funciilor)descopiarestriciilorputemdistinge diferite clase de probleme de optimizare cu restricii cum ar de exemplumodele de optimizare liniar,neliniar,n numere ntregi,stohastic,parametric,multicriterial.n continuare vom studia doar modelele de optimizare liniar cu restricii.1.1 Forme ale modelului de optimizare liniar curestriciintr-unfenomeneconomicsaudeorganizarepotnterveni mai multevariabilecare nu au sens dect cu condiia ca ele s e pozitive, negative sau nule.Modelul matematic al unui fenomen este un model matematic al unei prob-leme de optimizare liniar cu restricii dac este format dintr-un anmit numrde restricii date asupra variabilelor independente (care sunt liniare i pot inegal-itisauegaliti)iofunciedescopcareestedeasemenealiniar;iarproblemacaresepuneestedeterminareavaloriioptimealefuncieidescoppedomeniulde-terminat de aceste restricii.Deniia1.1.1. Formageneralaproblemei deoptimizareliniarcurestriciiprin deniie este7___f= c1x1+ c2x2+ c3x3 min / maxA11x1+ A12x2+ A13x3 b1A21x1+ A22x2+ A23x3= b2A31x1+ A32x2+ A33x3 b3x1 0, x2 0, x3de semn oarecare(1.1)undeA =__A11A12A13A21A22A23A31A32A33__ Mm,nf: RnRx = (x1, x2, ..., xl, xl+1, ...xr, xr+1, ..., xn) Rnx1= (x1, ...xl); x2= (xl+1, ...xr); x3= (xr+1, ..., xn)x = (x1x2x3) Rnb1= (b1, ...bk); b2= (bk+1, ...bp); b3= (bp+1, ..., bm)b = (b1b2b3) Rmc1= (c1, ...cl); c2= (cl+1, ...cr); c3= (cr+1, ..., cn)c = (c1c2c3) RnDeniia1.1.2. Senumeteformastandardal problemeideoptimizareliniarcu restricii modelul:___f(x) =

nj=1cjxj min(max)

nj=1aijxj= bi, i = 1, mxj 0, j= 1, nncontinuarepentrusimplicareascrierii vomfolosi reprezentareamatricial,adic:___f(x) = (c, x) min/maxAx = b , A Mm,n(R)x 0 b Rm, c Rnunde(, ): Rn RnResteprodusul scalareuclideanal vectorilordinspaiulvectorial Rn.Deniia1.1.3. Formacanonic al unui model de minimizare este:___f(x) = (c, x) minAx b , A Mm,n(R)x 0 b Rm, c RnForma canonic al problemei de maximizare este:8___f(x) = (c, x) maxAx b , A Mm,n(R)x 0 b Rm, c Rn1.2 Soluii ale problemei de optimizare liniar curestriciiA.CazulformeistandardFie modelul___f(x) = (c, x) minAx = b , A Mm,n(R)x 0 b Rm, c RnPresupunemcsistemul derestricii Ax=barecel puinosoluie. ncazcontrar nu are sens problema de optimizare considerat.Vom presupune pe tot parcursul expunerii c: rang A = m.Dac rang A < m atunci n caz de compatibilitate ar insemna c unele restriciisunt consecine ale celorlalte, adic modelul construit cu scopul efecturii unei studiia unui fenomen economic, nu este corect.Vom presupune de asemenea m < n (pentru evitarea unicitii soluiilor sistemulde restricii nu lum cazulm = n).Evident, cu aceste considerente sistemul liniar de ecuaiiAx = b este un sistemnedeterminat, n consecin admite o innitate de soluii.Deniia1.2.1. Osoluieasistemului deecuaii Ax=b carevericnpluscondiiadenenegativitate(x 0)senumetesoluieadmisibilsauprogramalproblemei.Mulimea soluiilor posibile vom nota cuS.Deniia1.2.2. O soluie posibil,x, al problemei se numete programoptim,soluieoptimdacvericcondiiadeoptim: (c, x) (c, x),undex Soare-care(dacavemminimizare),i (c, x) (c, x), undex Soarecare(dacavemmaximizare).n continuare prezentm cteva proprieti ale mulimilor de soluii.n acest scop ntroducem nite noiuni necesare.Deniia 1.2.3.MulimeaM Rnse numete convex dac pentru oricare doupunctealesale x1, x2M, segmentul [x1, x2] determinat deacestedoupuncteaparine n intregime mulimii date.Deniia1.2.4. MulimeaM Rneste convex dac pentru oricex1, x2 Mi [0, 1] avemx1 + (1 )x2 M.9x1 + (1 )x2cu [0, 1], se numete combinaia convex a punctelor date.Mulimile convexe pot mrginite i nemrginite.Mulimeavidi mulimeaformatdintr-unsingur element sunt consideratemulimi convexe.Deniia1.2.5. FieX Rn. Mulimea punctelorx Xcare veric relaia:n

i=1aixi= bdetermin un hiperplan.Mulimea punctelorx Xcare veric relaia:n

i=1aixi bformeaz un semispaiu.Intersecia unui numr nit de semispaiin

j=1aijxj bi(i = 1, m)se numete tronson.Teorema1.2.6. Hiperplanul, semispaiul i tronsonul sunt mulimi convexe.Demonstraie. [Szab].Teorema1.2.7. Mulimea soluiilor posibile este o mulime convex.Demonstraie. [Szab].Teorema1.2.8. Mulimea soluiilor optime este o mulime convex.Demonstraie. [Szab].Observaia 1.2.9.Din punct de vedere practic teorema este foarte important. Nearatcoricemodel deprogramareliniaradmiteeosoluieoptimunic,eoinnitate de soluii optime.Teorema 1.2.10. O soluie posibil este soluie optim pentru modelul de optimizareliniar cu restricii dac i numai dac este un punct extrem pentru mulimeaS.Dup cum s-a artat mai sus restriciile unui model liniar formeaz un tronson.Se poate arta c orice soluie corespunznd optimului trebuie s se gseasc n unuldinvrfuriletronsonului. Cualtecuvintemodeluladmitesoluieoptimnumaincazul n care tronsonul este mrginit (adic restriciile formeaz un poliedru).Deci, din mulimeaS, care admite o innitate de elemente, ne ntereseaz doaracele puncte care reprezint vrfurile poliedrului.n acest scop introducem o alt noiune.10Deniia 1.2.11.O soluie posibilx Scu cel multm componente strict pozitivesenumetesoluie de bazdaccoloanelematricei A, carecorespundacestorcomponente, formeaz o baz nRm.Deniia1.2.12. Osoluiedebazsenumetenedegeneratdacareexact mcomponente nenule i degenerat n caz contrar.Teorema1.2.13. Orice soluie de baz a unei probleme de programare liniar esteun punct extrem al mulimiiS, i reciproc, orice punct extrem al mulimiiSeste osoluie de baz.Dac determinm cu un procedeu soluiile bazice atunci prin nlocuirea acestoran funcia de scop putem determina soluia optim al problemei considerate.Cte soluii de baz are un model cun variabile im restricii?Folosinddeniiasoluieibaziceesteuorsobservmcleputemobinemnurma rezolvrii tuturor sistemelor Cramer de m ecuaii i m necunoscute, pe care leputem forma din sistemul de restriciiAx = b.Astfel se poate arma c numrul soluiilor bazice este cel multCmn .ExempluS se determine soluiile bazice ale problemei considerate.___f(x) = 2x1 +x2 + 2x3 + x4 + 3x5 max2x1 + x2 + x3x4x5= 2x1 + 2x2x3x4 + 3x5= 4xj 0, j= 1, 5Matricea restriciilor este:A =_2 1 1 1 11 2 1 1 3_rang A = 2NotmCij, i 0}5. Pentru ecarei B+cerceteaz semnul numerelorij, j B.Se pot ivi dou situaii:a) Dac existi B+astfel nct pentru oricej B ij 0,atunci specic faptul c funcia de scop al problemei este nemrginit inferiorpemulimeasoluiilor posibilei problemanuadmitesoluieoptim(avemoptim innit).STOPb) pentru oricei B+exist cel puin unj B astfel nctij> 06. alege indiceleh B+7. alege indicelek B astfel nct:0khk= min_0jhj, j B, hj> 0_8. nlocuiete n bazaBvectorulAkcuAhi cu noua baz astfel obinut trecila pasul (2).Bazelesemodicpncndseajungelaunadincriteriiledeopriredatenalgoritm.Pentru aplicarea algoritmului se ntocmesc tabele, numite tabele simplex pri-mal.ntocmireatabelelorsimplexprimalSepresupunecs-adeterminatobazprimal admisibil, B, al problemei deoptimizare liniar considerat.28Construim tabelul de mai jos:1 2 3 6 7 8 4 5 9 10 Sectoarele indicate n tabel se completeaz dup regula urmtoare:- n sectorul 1 se trece numrul de ordine al tabelului simplex- n sectorul 2 se trec punctele bazeiB(m coloane)Ajcuj B- n sectorul 3 se trec puncteleAi, i B- n sectorul 4 se trec numerele0j, j B- n sectorul 5 se treced0, valoarea funciei de scop pentru soluia posibilxB- n sectorul 6 se trec numereleij, j B(care intervin n reprezentarea luiAin bazaB, pentru oricei B;Ai=

jB ijAj)- n sectorul 7 se trec, pentru ecarei B numereledicalculate cu formula:di=

jBijcj cin sectoarele 8 i 9, scriem nite valori care nu erau menionate n algoritm, nsvor folosite pentru vericarea corectitudinii calculelor.- n sectorul 8 scriem numerele notate cupi, i B : pi= 1

jB ij di- n sectorul 9 scriem numrulp0= 1

jB 0j d0.Dupcompletareacelor9sectoareseaplicpasul 4al algoritmului, adicseefectueaz testarea optimalitii al soluiei posibilexB.Dac soluia bazic nu este optim, dar problema dat nu are optim innit (severic n pasul 5), atunci se alegeh, adic o linie din tabel, numit liniepivot.Se recomand pentru reducerea numrului de iteraii s e ales indicele pentrucaredh= max{di: i B+}Cu alegerea luih se alege de fapt vectorul care va ntra n baz, de aceea pasul (6)se numete criteriu de intrare n baz.Acum urmeaz completarea sectorului 10.- n sectorul 10 se trec cturile0jhjmenionate n pasul (7). (Dac hj< 0 atunciraportul nu se calculeaz , la locul respectiv n tabel punem bar.)Coloana corespunztoare indiceluik (ales n pasul 7 al algoritmului) se numetecoloanpivot.Alegerea coloanei pivot se numete criteriu de ieire din baz.29hk (elementul care se a la intersecia liniei pivot cu coloana pivot) se numeteelementpivot.Aici se termin prima iteraie simplex primal.n continuare n baza Bnlocuim punctul Akcu Ahi cu baza astfel obinut setrece la ntocmirea noului tabel simplex.Trecereadintr-untabelsimplexnaltulLa o iteraie de ordinulr avem tabelul simplex primal:r . . . Aj. . . Ak. . . . . . . . . . . . . . . . . . . . . . . . . . .Ai. . . ij. . . ik. . . dipi. . . . . .Ah. . . hj. . . hk. . . dhph. . . . . . . . . xBj. . . xBk. . . d0p0 . . . xBj/hj. . . xBk /hk Completarea tabelului:- numrul din sectorul 1 se mrete cu o unitate- n sectorul 2 vectorulAkse nlocuiete cuAh- n sectorul 3 vectorulAhse nlocuiete cuAk- n locul elementului pivot punem inversul acestuia, adic1/hk- pe coloana pivot elementele se nmulesc cu1/hk- pe linia pivot elementele se nmulesc cu 1/hk- numerele din sectoarele 4, 5, 6, 7, 8, 9 se calculeaz folosind regula dreptunghi-uluiAvnd patru numere , , , , aezate astfel nct s formeze vrfurile unui drep-tunghi

cu reguladreptunghiului n locul lui vom scrie numrul undeeste ales astfel nct s e chiar elementul pivothk.Astfel avem urmtorul tabel la iteraia de ordinulr + 1 :30r + 1 . . . Aj. . . Ak. . . . . . . . . . . . . . . . . . . . . . . . . . .Ai. . . ij hjikhk. . .ikhk. . . diikdhhkpiikphhk. . . . . .Ah. . . hjhk. . .1hk. . . dhhkphhk. . . . . . . . . xBjhjxBkhk. . .xBkhk. . . d0xBkdhhkp0xBkphhk . . . . . . Exemplu: S se determine soluia optim al problemei:___f(x) = x1x23x3 + 5x4 minx1 + x2 +x3 +x4= 1x12x2 + 3x3 +x5= 2x1x2 + x6= 3xj 0, j= 1, 6Matricea restriciilor este:A1A2A3A4A5A6A =__1 1 1 1 0 01 2 3 0 1 01 1 0 0 0 1__ProblemadatestenformastandarddelucrudeoarecenmatriceaAesteinclus o matrice unitate de ordinul 3, iar componentele vectoruluib sunt pozitive.Deci putem aplica direct algoritmul simplex primal.AlegembazaB=(A4, A5, A6). Dacmodelul estenformastandarddelucruatuncibazaprimaladmisibilpecarealegemestebazcanonic. Aceastalegereeste foarte avantajoas deoarece, dup cum este cunoscut, n baza canonic ecarevector i pstreaz coordonatele iniiale. Deci nu trebuiesc calculate valorile0jiij. Astfel putem nlocui n tabel coordinatele iniiale ale vectorului b i a vectorilorAi.Putem scrie:1 A4A5A6 A1-1 1 1 -6 6A21 -2 -1 6 -3A31 3 0 8 -11 1 2 3 5 -10 1 2/3 - xB= (0 0 0 1 2 3)f(xB) = d0= 5312 A4A3A6 A1-4/3 1/3 1 -26/3 29/3A25/3 -2/3 -1 34/3 -31/3A5-1/3 1/3 0 -8/3 11/3 1/3 2/3 3 -1/3 -8/3 1/5 - - xB= (0 0 2/3 1/3 0 3)f(xB) = 1/33 A2A3A6 A1-4/5 -1/5 1/5 2/5 7/5A43/5 2/5 3/5 -34/5 31/5A5-1/5 1/5 -1/5 -2/5 8/5 1/5 4/5 16/5 -13/5 -3/5 - - 16 xB= (0 1/5 4/5 0 0 16/5)f(xB) = 13/54 A2A3A1 A64 1 5 -2 -7A43 1 3 -8 2A5-1 0 -1 0 3 13 4 16 -9 -23 - - - Soluia optim al problemei este: x0= (16 13 4 0 0 0) fmin= d0= 9.Ssedeterminesoluiaoptim!___f= 2x1 +x2 + 3x3 + 5x4 + 9x5 minx1 + 2x3 + x4 + 3x5= 15x2 + x3 + 2x4 + x5= 12x 0A =__A1A2A3A4A51 0 2 1 30 1 1 2 1__B= (A1, A2)321 A1A2 A32 1 2 -4A41 2 -1 -1A53 1 -2 -1 15 12 42 -68 15/2 12 xB= (15 12 0 0 0)2 A3A2 A11/2 -1/2 -1 2A41/2 3/2 -2 1A53/2 -1/2 -5 5 15/2 9/2 27 -38 - - Soluia optim al problemei estex0= (0 9/2 15/2 0 0) fmin= 27Bazele teoretice ale algoritmului simplex primal (vezi [Szab]).Observaia 1.5.4. Este sucient s cunoatem algoritmul simplex pentru rezolvareaproblemelor de minimizare.Dacavemunmodel demaximizareatuncivomnmuliformal funciadescopcu 1 i rezolvm modelul cu funcia de scop fpentru care evident avem de deter-minatvaloareaminim,peacelaidomeniu,determinatderestriciileproblemeidemaximizare. Soluiaoptimal acestuimodel esteoptimipentrumodelul iniial,iarfmax= d0= fmin.Sconsidermproblema:___f(x) = 2x2 + x3 maxx1 +x22x3 73x1 + x2 + 2x3 3x R3+___f(x) = 2x2x3 minx1 + x22x3 +x4= 73x1 + x2 + 2x3 + x5= 3x R5+Matricea restriciilor este:A1A2A3A4A5_1 1 2 1 03 1 2 0 1_Modelul consideratestenformastandarddelucru. Rezolvmcualgoritmulsimplex primal.331 A4A5 A11 -3 0 3A21 1 2 -3A3-2 2 1 0 7 3 0 -9 7 3 2 A4A2 A14 -3 6 -6A5-1 1 -2 3A3-4 2 -3 6 4 3 -6 0 1 - 3 A1A2 A41/4 3/4 -6/4 6/4A5-1/4 1/4 -2/4 6/4A3-1 -1 3 0 1 6 -12 6 Exist n acest tabel d3= 3 > 0 pentru care toate numerele 31= 1 < 0, 32=10, 35>0. Avemastfel:3 A3A5 A12 -1 0 0A43 -1 -3 2A2-1 1 -1 2 8 2 -44 35 x02= (0, 0, 8, 0, 2) fmax= 44Deciamobinutdousoluiioptime, ceeacenseamncproblemaareoptimmultiplu. Mulimea soluiilor optime este combinaia convex a soluiilor obinute:35x0= x01+ (1 )x02, pentru orice [0, 1]. Avem:x0= ______40006______+ (1 )______00802______=______408 806 + 2 2______, [0, 1]Observaia 1.5.7.Pentru = 0 sau = 1 avem soluiile bazice calculate mai sus.Pentru (0, 1)obinemisoluiioptimenebazice(deexemplupentru=0, 5).Deci n cazul optimului multipluS SB.Numai n cazul soluiei optime unice avemS SB.1.6 Rezolvareamodelelor carenuadmit soluii debaziniialAlgoritmul simplex primal poate utilizat cu succes numai n cazul n care modelulde optimizare liniar cu restricii este n forma standard de lucru.naceste cazuri soluiaasociatbazei canonice este soluie de baziniial,deoarece dup cum s-a artat baza este primal admisibil.Dac modelul dat spre rezolvare nu este n forma standard de lucru atunci primadatavemnevoiedeunprocedeucucareputemgeneraobazprimaladmisibil,adic o soluie bazic iniial.nacestscoppoateaplicatmetodacelordoufazesaumetodacoecienilorde penalizare. n continuare vom prezenta aceste metode.I. MetodacelordoufazeCumetodacelordoufazenprimafazdelucrudeterminmosoluiebaziciniial dup care n faza a doua de lucru rezolvm modelul considerat cu algoritmulsimplex primal.Fie urmtorul model de programare liniar cu restricii:___f= (c, x) maxAx = bx 0Presupunem c problema dat nu este n forma standard de lucru, adic nu admitesoluie de baz iniial.ncontinuarenscopul aplicrii metodei celordoufazevompresupunectoatecompenentelelui bsuntpozitiveinmatriceaAnuesteinclusomatriceunitatedeordinulm.ntroducemvariabile articiale ui, i =1, mcuscopul obinerii unei matriciunitate de ordinulm n matricea restriciilor.Dup introducerea variabilelor articiale se efectueaz:36(a) - rezolvarea unei probleme de minimizare, obinut n urma nlocuirii funcieide scop al problemei date cu o funcie,format din suma tuturor variabilelor arti-ciale.___g=

mi=1ui minAx + ImU= bx 0, u 0(b) dup rezolvarea problemei din punctul (a) cu algoritmul simplex primal tre-cem n faza a doua de lucru unde vom ntlni una din urmtoarele situaii:1. Dacgmin= 0, ui= 0 pentru oricei = 1, m, i nici un vector articial nu esten baza optim, atunci ncepem rezolvarea problemei iniiale.Soluia obinut n prima faz de lucru este soluie bazic iniial pentru prob-lema considerat, iar baza optim este baz primal admisibil.2. Dacgmin=0, ui=0, i=1, m, darcel puinunvectorarticial seanbaza optim,atunci soluia problemei rezolvate este soluie optim i pentruproblema iniial.Valoareafunciei descopputemobineprincalcul direct(nlocuindsoluiaoptim n funcia de scop). Evident, n acest caz problema iniial are soluieoptim degenerat.3. Dacgmin = 0, (nseamn c exist cel puin o variabil articial strict poz-itiv n soluie) atunci problema considerat nu admite soluie optim.Prezentmcteunexemplupentruecarecaznparte!(a)___f= 3x1 + 2x2 + x3 + 2x4 max2x1 + x2 + x3 + 2x4= 12x1 + 2x2 + x3 + 3x4= 14x 0Problema nu este n forma standard de lucru, deci nu putem aplica n mod directalgoritmul simplexprimal. Cumetodacelor doufazevomdeterminaosoluiebazic iniial, o baz primal admisibil.n prima faz de lucru rezolvm modelul:___g= u1 + u2 min2x1 + x2 + x3 + 2x4 + u1= 12x1 + 2x2 + x3 + 3x4 + u2= 14x 0, u 037A1A2A3A4u1u2A =_2 1 1 2 1 01 2 1 3 0 1_1 u1u2 A12 1 3 -5A21 2 3 -5A31 1 2 -3A42 3 5 -9 12 14 26 -51 6 14/3 2 u1A4 A14/3 1/3 4/3 -2A2-1/3 2/3 -1/3 1A31/3 1/3 1/3 0u2-2/3 1/3 -5/3 3 8/3 14/3 8/3 -9 2 14 nurmtorul tabel simpexputemreducenumrul liniilor, deoareceliniavec-torului articial ntotdeauna vom putea elimina. Dac reuim s scoatem un vectorarticialdinbaznuvomaveainteresuls-lintroducemnbazlaoaltiteraiesimplex.3 A1A4 u13/4 -1/4 -1 3/2A2-1/4 3/4 0 1/2A31/4 1/4 0 +1/2 2 4 0 -5 Toate difereneledisunt negative, nseamn c am ajuns la ultima iteraie sim-plex. Deoarecegmin= 0, u1= u2= 0, B0= (A1A4) rezult c soluia obinutxB= (2 0 0 4) este soluie de baz iniial petru problema dat.De fapt, n prima faz de lucru transformm modelul iniial astfel:___f= 3x1 + 2x2 + x3 + 2x4 maxx114x2 +14x3= 234x2 +14x3 +x4= 4x 038Acestmodelestenformastandarddelucru. Rezolvmcualgoritmulsimplexprimal.1 A1A4 A2-1/4 3/4 5/4 -3/4A31/4 1/4 -1/4 3/4 2 4 -14 9 - 16/3 2 A1A2 A41/3 4/3 -5/3 1A31/3 1/3 -2/3 1 10/3 16/3 -62/2 39/3 x0=_103 ,163 , 0, 0_fmax=623= d0.Se poate observa, c nu este necesar s scriem modelul transformat, ci n ultimultabel simplex, obinut n prima faz de lucru, eliminnd linia vectorului articial ieliminnd elementele din sectoarele 5,7,8,i 9 cu ajutorul funciei de scop al problemeiiniiale putem ntocmi primul tabel din faza a doua de lucru.(b)Fieproblema:___f= 2x1 + x2 + x3 min2x1 + 3x2 + 3x3= 12x1 + x2 + 2x3= 8x 0Rezolvm problema n mod analog.A1A2A3A =_2 3 31 1 2_I.___g= u1 + u2 min2x1 + 3x2 + 3x3 + u1= 12x1 + x2 + 2x3 + u2= 8x R+, u R2+A1A2A3u1u2A =_2 3 3 1 01 1 2 0 1_B= (u1, u2)391 u1u2 A12 1 3 -5A23 1 4 -7A33 2 5 -9 12 8 20 -39 4 4 2 A3u2 A12/3 -1/3 -1/3 1A21 -1 -1 2u11/3 -2/3 -5/3 3 4 0 0 -3 n prima faz de lucru am obinutgmin=0 x0=(0, 0, 4) B=(x3, u2) cuu2=0deci soluiaobinutestesoluie optim i pentru problema iniial iar valoarea funciei de scop obinem princalcul direct i va fmin= 4.(c)___f= 2x1 + x2 + x3 + 2x4 min2x1 + x2 + 2x3 + 2x4= 16x1 +x2 + 2x3 + 2x4= 102x1 + x2 + x3 + 2x4= 20x 0n prima faz de lucru scriem:A =__2 1 2 21 1 2 22 1 1 2__I.___g= u1 +u2 + u3 min2x1 + x2 + 2x3 + 2x4 + u1= 16x1 + x2 + 2x3 + 2x4 + u2= 102x1 + x2 +x3 + 2x4 + u3= 20x R4+, u R3+A1A2A3A4u1u2u3A =__2 1 2 2 1 0 01 1 2 2 0 1 02 1 1 2 0 0 1__B= (u1, u2, u3)401 u1u2u3 A12 1 2 5 -9A21 1 1 3 -5A32 2 1 5 -9A42 2 2 6 -11 16 10 20 46 -91 8 5 10 2 u1A4u3 A11 1/2 1 2 -7/2A20 1/2 0 0 1/2A30 1 -1 -1 2u2-1 1/2 -1 -3 11/2 6 5 10 16 -36 6 10 10 3 A1A4u3 u11 -1/2 -1 -2 7/2A20 1/2 0 0 1/2A30 1 -1 -1 2 6 2 4 4 -15 gmin= d0= 4 = 0u1= u2= 0, u3= 4Deoarecegmin= 4 = 0 problema iniial nu admite soluie.Degenerareiciclarenaplicareaalgoritmuluisimplex(vezi[Szab]).1.7 DualitateanprogramarealiniarDualitatea ocup un loc important n programarea liniar, att din punct de vedereteoretic, ct i din punct de vedere practic.Fie urmtoarea problem de programare liniar n forma general___f= c1x1+ c2x2+ c3x3 minA11x1+ A12x2+ A13x3 b1A21x1+A22x2+ A23x3= b2A31x1+ A32x2+ A33x3 b3x1 0, x2 0, x3de semn oarecare(1.13)41Deniia1.7.1. Fiind dat problema (1) se numete dual a sa problema:___g= b1y1+ b2y2+ b3y3 maxAT11y1+ AT21y2+ AT31y3 c1AT12y1+ AT22y2+ AT32y3 c2AT13y1+ AT23y2+ AT33y3= c3y1 0, y2de semn oarecare y3 0.(1.14)Adic pentru ecare caz avem urmtoarele situaii:(P)___c1x1+c2x2+ c3x3 maxA11x1+ A12x2+ A13x3 b1A21x1+ A22x2+ A23x3= b2A31x1+ A32x2+ A33x3 b3x1 0, x2 0, x3de semn oarecare(D)___b1y1+b2y2+ b3y3 minAT11y1+ AT21y2+ AT31y3 c1AT21y1+ AT22y2+ AT23y3 c2AT31y1+ AT32y2+ AT33y3= c3y 0, y2de semn oarecarey3 0(P)___c1x1+ c2x2+c3x3 minA11x1+ A12x2+ A13x3 b1A21x1+ A22x2+ A23x3= b2A31x1+ A32x2+ A33x3 b3x1 0, x2 0, x3de semn oarecare(D)___y1b1+ y2b2+ y3b3 maxAT11y1+AT21y2+AT31y3 c1AT21y1+AT22y2+AT23y3 c2AT31y1+ AT32y2+ AT33y3= c3y1 0, y2de semn oarecare , y3 0Observaia 1.7.2.Este uor de vzut c duala problemei duale este chiar problemaprimal. Dinacest motivvomspunecproblemele(1)- (2)(respectiv(P)-(D))formeaz uncupludeproblemeduale.Analiznd cuplurile de probleme duale date, putem deduce legtura dintre prob-lema primal i problema dual, adic:a)formafuncieiobiectivdin(P)implicformafuncieiobiectivdindual(ireciproc);b)formarestriciilorproblemei primaleimplicsemnelevariabilelordualei (ireciproc);c)semnelevariabilelorproblemei primaleimplicformarestriciilorproblemeiduale (i reciproc).Adic explicit putem spune c:421. -dacnproblema(P)seceremaximizareatuncinduala(D)seceremini-mizare;2. -numrulvariabilelorproblemeiprimaledeterminnumrulderestriciialeproblemei duale;3. - numrul de restricii ale primalei d numrul de variabile ale problemei duale;4. - termenii liberi din (P) devin coecienii funciei de scop n (D);5. - coecienii funciei de scop din (P) devin termenii liberi n (D)6. -dacAestematriceacoecienilorproblemei(P)atunci ATvamatriceacoecienilor problemei (D)7. - dac (P) are restricii concordante atunci (D) are variabile pozitive- dac (P) are restricii neconcordante inegaliti atunci (D) are variabile neg-ative- dac(P)arerestricii neconcordanteegaliti atunci (D)arevariabiledesemn oarecare8. - dac (P) are variabile pozitive atunci (D) va avea restricii concordante-dac(P)arevariabilenegativeatunci(D)vaavearestriciineconcordanteinegaliti- dac (P) are variabile de semn oarecare atunci (D) va avea restricii necon-cordante egalitiDeniia1.7.3. Orestriciedeforma , respectiv ncazul unei problemedemaximizare, respectiv de minimizare se numete restricie concordant.Orestriciedeforma ,respectiv ncazul uneiproblemedemaximizare,re-spectiv de minimizare se numete restricie neconcordant de tip inegalitate.Un motiv al denirii problemelor duale este i acela al posibilitii de soluionaremai rapid a uneia din elementele cuplului primal - dual.Interesul se concentreaz asupra modului n care gsim soluia celuilalt elemental cuplului.Se poate vedea c dualitatea se poate deni n mod echivalent utiliznd oricaredintre cuplurile de probleme duale.Aceastanseamncputemstudiaproprietilededualitatepeoricaredintrecuplurile de probleme duale, fr a restrnge prin aceasta generalitatea.Cuplul de probleme duale care este remarcabil prin simetria sa (ambele problemesunt n form canonic), se numete cupludualsimetric:(P) {x Rn| Ax b, x 0} min(D) {u Rm| ATu c, u 0} max43Teoremealedualitiisuntteoremecarearatcntreelementelecupluluidual nu exist doar o legtur formal ci i o puternic interdependen a soluiiloracestora.n continuare prezentm un exemplu practic.Se urmrete stabilirea hranei raionale pentru animale, hran care s conin nmodobligatoriupatruelementenutritive, A, B, Ci D. SeproducdounutreuriMi Ncare conin aceste elemente. Un kilogram din nutreul Mconine 100 gramedin elementulA, 100 grame dinCi 200 grame dinD.1 kg din nutreul Nconine 100 grame din elementul B, 200 grame din elementulCi 100 grame dinD.Un animaltrebuie s consume pezicelpuin0,4 kg dinA;0,6 kg dinB;2 kgdinCi 1,7 kg dinD.NutreulMcost 10 unit./kg, iar nutreulNcost 4 unit/kg.Cecantiti denutreuri Mi Ntrebuiescfolositepezi i pecapdeanimalpentru a obine hrana cea mai ieftin?Dac notm cantitile prescrise cu x1, x2, atunci imediat putem formula matem-atic scopul i restriciile problemei propuse spre rezolvare.Avem:___f= 10x1 + 4x2 min0, 1x1 0, 40, 1x2 0, 60, 1x1 + 0, 2x2 20, 2x1 + 0, 1x2 1, 7(1.15)Folosind algoritmul simplex obinem soluia optimx1= 4, x2= 9.Valoarea optim a funciei de scop estefmin= 76.n continuare, s studiem problema care se pune unui concurent al vnztoruluinutreurilorMiN.Acest concurent vinde i elementele A, B, C, D. El tie c vnzrile lui sunt egalecu cantitile prescrise pe zi i pe cap de animal, i dorete s ae cu ce pre unitartrebuie s vnd elementele, pentru ca beneciul lui s e maxim.Cu aceste considerente putem formula urmtoarea problem de optimizare:- beneciul poate descris matematic cu funciag= 0, 4y1 + 0, 6y2 + 2y3 + 1, 7y4 max- pentru formularea restriciilor lum n considerare faptul c vnztorul nu vndecu preuri mai ridicate dect ale concurentului su.Astfel putem scrie0, 1y1 + 0, 1y3 + 0, 2y4 100, 1y2 + 0, 2y3 + 0, 1y4 4y1, y2, y3, y4 0(1.16)44Cu metodele prezentate n paragrafele anterioare soluia problemei este:y1= 20, y2= 0, y3= 0, y4= 40 fmax= 76Observaie:- problemei (1.15) i corespunde problema (1.16) n care datele au fost inversate- de aceast inversare este legat o proprietate foarte importantmax g= min f= 76Se poate demonstra c proprietatea este general.Fie cuplul dual:(P)___f(x) = (c, x) minAx = bx 0(D)___g(v) = (b, v) maxATv cv de semn oarecareDeniia 1.7.4.O baz B a problemei (P) se numete baz dual admisibil dacdi 0 pentru oricarei B.Denumirea de baz dual admisibil provine de la proprietatea exprimat n ur-mtoarea teorem.Teorema 1.7.5.DacBeste o baz dual admisibil a problemei (P) atunci soluiavB, al sistemului de ecuaii denit nRmprin:(Aj, v) = cj, j Beste o soluie posibil a problemei duale.Demonstraie. [Szab].Observaie:ngeneralsoluiabazicxB,asociatuneibazedualadmisibileBaproblemei(P)nuesteosoluieposibilaproblemei (P)(deoarececoordonatelepotstrictnegative).Deci o baz dual admisibil nu este ntotdeauna i o baz admisibil.Teorema 1.7.6.FieBo baz al problemei (P) care este primal i dual admisibil.Atunci:xBeste soluia optim a problemei (P)vBeste soluia optim a problemei (D)i(xB, c) = d0= (vB, b).Demonstraie. [Szab].451.8 Algoritmul simplexdualFie urmtorul model de minimizare cu restricii:___f(x) = (c, x) minAx = b , A Mm,n(R)x 0 b Rm, c Rn(1.17)Folosind proprietatea de dualitate se poate formula un algoritm pentru rezolvareamodelelor liniare cu restricii, numit algoritmul simplex dual.n continuare prezentm etapele algoritmului.1. alege o bazBdual admisibil al problemei (1.17)2. determin numerele0j(b =

jB 0jAj) i numereleij( pentru oricei B)Ai=

jB ijAj3. calculeaz numruld0=

jB ojcji pentru oricei B difereneledi=

jB ijcj ci4. cerceteaz semnul numerelor0j, j BSe pot ivi dou situaii:(a)dacpentruoricej B, 0j 0,atuncispeciccpunctul xB=x0=(x01, . . . , x0n) Rn, x0j=_0j, j B0 , j kbesteosoluieoptimalproblemei(1.17),d0este valoarea minim a funciei de scop, i oprete-l algoritmulSTOPb)dacexistcelpuinunj B, 0j 0).Aici n sectorul 10 scriem cturilediikpentru i B pentru care ik< 0. Folosindaceste rapoarte alegem indiceleh din etapa 7 al algoritmului.La o iteraie de ordinulr avem tabelul:r . . . Aj. . . Ak. . . . . . . . . . . . . . . . . . . . . . . . . . .Ai. . . ij. . . ik. . . dipidi/ik. . . . . .Ah. . . hj. . . hk. . . dhphdh/hk. . . . . . . . . xBj. . . xBk. . . d0p0Schimbareabazeiserealizeazprinschimbareaunuivectordinbaz. Laalgo-ritmulsimplexdualprimadatestealesvectorulcareiesedinbazidupaceeavectorul care intr n locul acestuia n baz.Alegerea luiAk(kdin pasul 6) se efectueaz prin alegerea coloanei pivot.Alegerea vectoruluiAh(h din pasul 7) se realizeaz prin alegerea liniei pivot.hkse numete element pivot.47Trecerea dintr-un tabel simplex dual n altul se realizeaz folosind regula nvatla aplicarea algoritmului simplex primal. Regula de vericare este aceeai.Observaie:LaalgoritmulsimplexprimalpornimcuobazBprimaladmisibililucrmpn cnd devine dual admisibil (evident n cazul n care problema admite optimnit).Valoarea funciei de scop descrete dup ecare iteraie.Laalgoritmul simplexdual pornimcuobazBdual admisibili continumalgoritmul pncndbazadevine primal admisibil. Valoareafunciei de scopcretelaecareiteraie,deoarecepeparcurslucrmcusoluiibazicecarenusuntposibile.Exemplu:S se rezolve problema urmtoare cu algoritmul simplex dual.___f(x) = x1 + 2x2 + 3x3 minx1x2 + x3= 73x1 + x3x4= 10x1 + 2x3x5= 15xj 0, j= 1, 5A =__1 1 1 0 03 0 1 1 01 0 2 0 1__b =__71015__A1A2A3A4A5Dacnmodelul considerat matricearestriciilorncludeomatriceunitatedeordinul m, darnutoatecomponentelevectorului bsunt pozitiveatunci ngeneralbaza canonic este baz dual admisibil.n acest caz este mult mai ecient algoritmul simplex dual, deoarece nu se ncarcmodelul cu variabile articiale, pe de alt parte dac exist optim nit atunci vomputeaobinenurmarezolvriiuneisingureprobleme(cumetodacelordoufazetrebuie s rezolvm dou probleme).nmulind restriciile cu1 putemobserva imediat c sistemul de vectori(A2, A4, A5) este o baz canonic, iar din primul tabel vom putea deduce dac estedual admisibil pentru acest model.c = (1, 2, 3, 0, 0)1 A2A4A5 A1-1 -3 -1 -3 9 3A3-1 -1 -2 -5 10 5/2 -7 -10 -15 -14 47 482 A2A4A3 A1-1/2 -5/2 1/2 -1/2 4 1/5A5-1/2 -1/2 -1/2 -5/2 5 5 1/2 -5/2 15/2 47/2 -28 3 A2A1A3 A4-1/5 -2/5 1/5 -1/5 8/5A5-2/5 1/5 -3/5 -12/5 21/5 1 1 7 24 -32 Soluia optim al problemei estex0= (1 2 7 0 0) d0= 24 = fminBazele teoretice ale algoritmului simplex dual (vezi [Szab]).1.9 Determinareasoluiilorproblemeidualecuaju-torul ultimului tabel simplexal problemei pri-maleConsiderm modelul liniar cu restricii n forma standard:(P)___f(x) = (x, c) minAx = bx c(1.18)Scriem matricea restriciilor, transpusa acestei matrici i formulm duala problemeiconsiderate:A =___a11. . . a1n...am1. . . amn___AT=___a11. . . am1...a1n. . . amn___(D)___g(v) = (v, b) maxm

i=1ajivi cjj= 1, nvide semn oarecare i = 1, mPresupunem c problema primal are optim nit.Teorema1.9.1. DacBestebazoptimaproblemei (P) atunci soluiavBasistemului de ecuaii denit nRmprin(Aj, vB) = cjj B (1.19)este soluia optim a problemei duale.49Demonstraie. [Szab].Deci, dup rezolvarea problemei primale, dac construimsistemul liniar deecuaii dat n teorem putem obine soluiile problemei duale.n continuare vom presupune c matriceaA conine o matrice unitate de ordinm, i artm c soluiile problemei duale, n acest caz, pot citite direct din ultimultabel simplex al problemei primale.Notm cuAki= ei, i = 1, m (ei Rmelementele bazei canonice (e1, . . . , em)). Baza canoni-c cu care ncepem aplicarea algoritmului simplex esteBc= (Ak1. . . Akm).Bo= {Aj1, . . . , Ajm}este baza optim obinut n ultimul tabel.Se poate deduce urmtorul rezultat:dac pentru un indicei {1, . . . , m} avemki B, ceea ce nseamnkij=_0 , dac j = ki1 , dac j= kiatuncivBi= cki.iar ncazulcndavemki BatuncivBi= cki + dki.n consecin, coordonatele vectoruluivBsunt date de relaia:vBi=_cki, ki Bcki + dki, ki = Bi pot determinate din ultimul tabel simplex.Fie urmtoarea problem de optimizare liniar cu restricii.Exemplu:(P)___f= x1x23x3 + 5x4 minx1 + x2 + x3 + x4= 1x12x2 + 3x3 + x5= 2x1x2 + x6= 3xj 0, j= 1, 6Sseformulezedualaproblemeipropuseissedeterminesoluiileproblemeiduale!Scriem matricea restriciilor problemei primale.50A1A2A3A4A5A6A =__1 1 1 1 0 01 2 3 0 1 01 1 0 0 0 1__(1.20)Deoarece primala are trei restricii duala va avea trei variabile, pe care le notmcuv1, v2, v3. Cu ajutorul matriceiATputem scrie problema dual.(D)___g= v1 + 2v2 + 3v3 maxv1 + v2 + v3 1v12v2v3 1v1 + 3v2 3v1 5v2 0v3 0Problema este n forma standard de lucru,avem baza canonic Bc= (A4, A5, A6)care este baz primal admisibil prin urmare putem aplica metoda simplex primal.1 A4A5A6 A1-1 1 1 -6 6A21 -2 -1 6 -3A31 3 0 8 -11 1 2 3 5 -10 1 2/3 - 2 A4A3A6 A1-4/3 1/3 1 -26/3 29/3A25/3 -2/3 -1 34/3 -31/3A5-1/3 1/3 0 -8/3 11/3 1/3 2/3 3 -1/3 -8/3 1/5 - - 3 A2A3A6 A1-4/5 -1/5 1/5 2/5 7/5A43/5 2/5 3/5 -34/5 31/5A5-1/5 1/5 -1/5 -2/5 8/5 1/5 4/5 16/5 -13/5 -3/5 - - 16 514 A2A3A1 A64 1 5 -2 -7A43 1 3 -8 2A5-1 0 -1 0 3 13 4 16 -9 -23 - - - Soluia optim al problemei primale estex0= (16 13 4 0 0 0).n continuare determinm soluiile optime ale problemei duale, folosind relaia:v0i=_cki, ki Bcki + dki, ki BConform relaiei date putem scrie:v01 e1= A4 Bov02 e2= A5 Bov03 e3= A5 Bov01= c4 + d4= 5 8 = 3v02= c5 + d5= 0 + 0 = 0v03= c6 + d6= 0 2 = 2Deci,v0= (3 0 2) igmax= 3 + 2 0 + 3 (2) = 9 = d0= fmin.Legtura dintre soluiile unui cuplu dual (vezi [Szab]).1.10 Reoptimizarea soluiilor unei probleme de pro-gramareliniarPracticapunenfaamatematicii situaiainstabilitii variantei optime, obinutpentru un anumit model liniar la un moment dat, ca urmare a unui ntreg ansamblude factori economici,politici,sociali,etc.,care pot inuena elementele modelului,conducnd n spe la modicri ale acestora i implicit la modicarea modelului.Aceste inuene se pot materializa prin:- modicri ale termenului liber,- modicri ale coecientului funciei obiectiv,- modicri ale coloanelor matricei coecienilor,- modicri ale liniilor matricei coecienilor,- modicri ale numrului de restriii ale problemei,- modicri ale numrului de variabile ale problemei.Aceste modicri atrag dup sine, n mod evident, rezolvarea unei probleme noide programare liniar.52ntrebarea care se pune: Nu se poate rezolva problema modicat prin folosirearezultatelor obinute n urma rezolvrii problemei iniiale?Rspunsul este armativ i pentru ecare caz n parte au fost formulate diferitemetode de rezolvare.Ne vom opri asupra uneia dintre aceste cazuri prezentate, deoarece vom utilizala rezolvarea modelelor discrete, i la rezolvarea unor modele neliniare.Rezolvarea unei probleme de optimizare liniar cu restricii sub formastandardces-aobinutprinadugareauneirestriciiiauneivariabilepozitiveFie modelele liniare(1)___f(x) =

nj=1xjcj min

nj=1aijxj= bi, i = 1, mxj 0, j= 1, n(2)___f(x) =

nj=1xjcj min

nj=1aijxj= bii = 1, m

nj=1am+1jxj + xn+1= bm+1xj 0undecj, aij, bi R, m, n R date,m < n.Problema (2) este obinut, din modelul (1), n urma adugrii unei restricii ia unei variabile.Astfel avemoproblemdeprogramareliniarnRn, problema(1)i oprob-lemdeprogramareliniarnRn+1,problema(2),obinutdinproblema(1)prinadugarea unei restricii i a unei variabile.Matricile restriciilor sunt:A1. . . AnA11An1An+11A =___a11. . . a1n...am1. . . amn___A1=_____a11. . . a1n0...am1. . . amn0am+1,1. . . am+1,n1_____unde vectorii coloanA1, . . . , An Rm, A1, . . . , An+1 Rm+1.Analiznd matricile se poate observa uor c intre vectorii coloan are loc relaiaAj1= (Aj, am+1,j) RmRpentru oricej= 1, n iAn+11= (m, 1) RmR.Adic:A11= (A1, am+1,1) RmRA21= (A2, am+1,2) RmR...An1= (An, am+1,n) RmR53Presupunem c problema (1) admite soluie optim, obinut cu algoritmul sim-plex primal sau dual, i vom nota cux0 Rn.n ultimul tabel simplex (primal sau dual) notnd cu (ji, . . . , jm) o submulime aindicilor(1, 2, . . . , n) atunci(Aj1, . . . , Ajm) va reprezenta baza optim al problemei(1).Teorema1.10.1. Sistemul devectori B1=(Aj11, . . . , Ajm1, An+11)esteobazdualadmisibil pentru problema (2).Demonstraie. Avem de demonstrat prima dat c acest sistem de vectori este bazpentru problema (2). Astfel trebuie artat c formeaz un sistem liniar independentde vectori.A1. . . AnA11An1An+11A =___a11. . . a1n...am1. . . amn___A1=_____a11. . . a1n0...am1. . . amn0am+1,1. . . am+1,n1_____Dezvoltmdeterminantul dupultimacoloan, ncaredoar ultimul elementestediferitdezero. Determinantul deordinul mastfel obinutesteformatdincomponentele vectorilor care formeaz baza optim, prin urmare acest determinantva diferit de zero, ceea ce nseamn c sistemul de vectori este baz.La demonstrarea faptului c aceast baz este dual admisibil vom reveni dupstabilirea modului de completare a tabelului simplex dual n scopul rezolvrii prob-lemei (2).Completarea tabelului simplex dual.nultimul tabel al problemei rezolvatevectorii carenuauintratnformareabazei suntAi1= (ij1, . . . , ijm)unde coordonateleijk, k = 1, m sunt scrise n sectorul 6 n tabel.Dacanalizmacestultimtabel i sistemul devectori B1vomputeaobservacacelecoloaneledinmatriceaA1caresuntcoresponztoareexactindicilorivorreprezenta vectorii care nu intr n formarea bazeiB1.Noile coordonate ale acestor vectori n bazaB1vom nota cuAi1= ij1 Aj11+ + ijmAjm1+ in+1An+11i B1PutemscrieacestrelaiefolosindlegturiledintrecoloanelematricilorAi A1nforma:(Ai, am+1i) = ij1(Aj1, am+1j1) + + ijm(Ajm, an+1jm) + in+1(m, 1) i kb154Astfel obinemin+1= m+1im

k=1ijkam+1jkn mod analog putem deduce0j1= 0j1, . . . 0jm= 0jmiar0n+1= x0n+1= bm+1m

k=1x0jkam+1jkNumerele de control pot obinute dinpi= piin+1p0= p00n+1Astfel se poate deduce uor c diferenele di i d0 sunt egale cu cele din ultimul tabelal problemei rezolvate, adic au loc relaiiled0= d0, di= di i BceeacearatcbazaB1estebazdual admisibili teoremaastfel estecompletdemonstrat.Exemplu:Fie problemele:___f(x) = x1x2 + 2x3 + x4 minx1 + x2 + x3= 32x1 + x2 + x4= 4x1 0, x4 0___f(x) = x1x2 + 2x3 + x4 minx1 + x2 + x3= 32x1 + x2 + x4= 43x12x2 + 6x4 + x5= 1x1, . . . , x5 0A1A2A3A4A11A21A31A41A51A =_1 1 1 02 1 0 1_A1=__1 1 1 0 02 1 0 1 03 2 0 6 1__551 A3A4 A11 2 3 -5A21 1 4 -5 3 4 10 -16 3 4 2 A2A4 A11 1 -1 0A31 -1 -4 5 3 1 -2 -1 Dup dou iteraii avem soluia optim al primei problemex0= (0 3 0 1); fmin= 2.Pe baza teoremei putem scrie baza dual admisibil pentru modelul doi:B= (A21A41A51)1 A21A41A51 A111 1 -1 -1 1 1A311 -1 8 -4 -3 -1/2 3 1 -1 -2 0 Completarea tabelului simplex dual se va realiza cu ajutorul relaiilor date.Putem scrie:1,5= a3,1(1 a32 + 1 a34) = 3 (1 (2) + 1 6) sauA11= 1 A2+ 1 A4+ A51A11= 1 (1 1 2) + 1 (0 1 6) +(0 0 1)A11= (1 1 + 1 2 + 6 +)(1 2 3) = (1 2 4 +)4 + = 3 = 1A31= 1 A213A41 + A51A31= 1 (1 1 2) 1(0 1 6) +(0 0 1)(1 0 0) = (1, 1 1, 2 6 + ) = 805= b3(02 32 +04 34) = 1 (3 (1) + 1 6) = 1Dup alegerea elementului pivot trecem la completarea urmtorului tabel.562 A2A4A1 A51 1 -1 -1 1A39 7 -8 -12 5 2 0 1 -1 -1 Deci soluia optim al problemei a doua este:x0= (1 2 0 0 0) fmin= 1.Dac nu folosim reoptimizare atunci rezolvarea problemei doi este mai complicatnecesit mult mai mult timp. Din matricea A1 se poate observa c problema nu esten forma standard de lucru i nici algoritmul simplex dual nu putem aplica n moddirect. Problema se va rezolva cu metoda celor dou faze sau metoda coecienilorde penalizare.Reoptimizareaputemaplicai invers. Avndoproblemsprerezolvare, elim-innddinrestricii i variabile(dacestecazul)putemrezolvaproblemaredus,dup care cu reoptimizare vom putea obine soluia optim al problemei iniiale.Exemplu:S se rezolve problema:___f(x) = x26x3 + 2x5 minx1 + 3x2x3= 72x2 + 4x3 +x4= 124x2 + 3x3 + 8x5 + x6= 10x1 + 2x2 + x3 + x4 + x6 + x7= 20x1, . . . , x7 0A =____1 3 1 0 0 0 00 2 4 1 0 0 00 4 3 0 8 1 01 2 1 1 0 1 1____c = (0 1 6 0 2 0 0)b = (7 12 10 20)Putem elimina ultima restricie i variabila x7, deoarece nu apere dect n ultimarestricie.Astfel prima dat vom rezolva problema:___f(x) = x26x3 + 2x5 minx1 + 3x2x3= 72x2 + 4x3 + x4= 124x2 + 3x3 + 8x5 + x6= 10x1. . . x6 0dup care aplicm reoptimizarea.Soluia optim al problemei iniiale va x0= (0 4 5 0 0 11)d0= fmin= 26.571.11 ProgramarediscretBazele programrii discrete (vezi [Szab]).Sunt douprincipii debazcarestaulabazametodelor numericeelaboratepentru rezolvarea modelelor discrete.1. PrincipiulrelaxriiDintre toate tipurile programrii matematice,pentru prima dat a aprut pro-gramarea liniar. Astfel este natural ideea ca rezolvarea problemelor de programarediscret s e redus la rezolvarea numeric ale acestor probleme.Un punct de plecare n acest sens avem imediat, deoarece dac n modelul___f(x) = (c, x) opt.Ax = bx Nnrenunm la condiia de ntegritate a variabilelor atunci avem o problem de progra-mare liniar. Rezolvnd problema dac soluiax0veric condiiilex Natuncirezult c avem soluie optim i pentru problema discret.n continuare enunm principiul relaxrii.FieS, Tdoumulimi oarecareastfel nct S T. Fief : TRofuncieoarecare. Dac problema_f(x) maxx Tadmite soluie optim notat cuyiy Satunciyva deasemenea soluie optim pentru problema_f(x) maxx SPrima problem prin deniie se numete problem relaxat.Metodele de tip tietur i metoda mrginirii i separrii sunt construite pe acestprincipiu.Dei principiul relaxrii esteunprincipiudestul detrivial esteuninstrumentfoarte util.Practic este util atunci cnd rezolvarea problemei relaxate este mult mai simpl.2. PrincipiulluiBellmannLa orice algoritm de determinare a drumului optim ntr-un graf orientat se poateasocia un procedeu de programare discret.Interesul se concetreaz asupra ecienei.Metodederezolvarebaztepeprincipiul lui Bellmanvorstudiatencadrulprogramrii dinamice discrete.58n continuare considerm problema:___f(x) = 7x1 + 5x2 max6x1 + 9x2 547x1 + 6x2 42x1 4x1, x2 N96(d2)(d3)(d1)yxEvident mulimea soluiilor posibile esteS = {(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6)(1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5)(2, 0), (2, 1), (2, 2), (2, 3), (2, 4)(3, 0), (3, 1), (3, 2), (3, 3)(4, 0), (4, 1), (4, 2)}Cutmsoluiantr-unpoliedruconvex. Lundnvelitoareaconvexapunctelorobinem un poliedru mai mic.Soluia optim al problemei discrete va x = (4 2), iar soluia problemei relaxateestex0= (4 7/3), adic punctul de intersecie a dreptelor(d3) (d2).1.11.1 Metodedetiptietur. Metodalui GomoryAlgoritmul lui Gomory, este o metod de tip tietur i a fost formulat n 1959.Fie modelul liniar cu restricii n numere ntregi59___f(x) = (x, c) minAx = bx Nn(1.21)Asociem acestui model problema relaxat___f(x) = (x, c) minAx = bx 0(1.22)care este o problem de programare liniar obinuit.Notm cuS= {x Nn:Ax = b} mulimea soluiilor posibile ale problemei deminimizare total ntreagi cu S1= {x Rn: Ax = b, x 0} mulimea soluiilor admisibile ale problemeirelaxate.Evident are loc relaiaS S1.n continuare prezentm algoritmul lui Gomory.1. Se va rezolva problema relaxat cu una din algoritmile nvate i se va notacux1 S1soluia optim obinut.2. Aplicm principiul relaxrii, adic vericm(a)dacx1S x1estesoluiaproblemeideminimizaretotalntreagioprete-l algoritmul;(b)dacx1S, adiccel puinocomponentavectorului nuestenumrnatural atunci se va continua algoritmul.3. Notm cuBobaza optim al problemei relaxate. Deoarecex1 Srezult ccel puin una din numerele0jnu este natural, adic j B : 0j N.4. Se va alege o astfel de indicej, i se va construi o nou problem astfel___f(x) = (x, c) minAx = b

iB{ij}xi {0j}/ (1)x 0(1.23)Mulimea soluiilor posibile ale problemei (1.23) se va nota cuS2= {x Rn: Ax = b,

iB{ij}xi {0j}, x 0}.60Au loc relaiileS2 S1(chiar se poate arta cS2 S1)S S2.Problema, n scopul rezolvrii, se va transforma astfel:___f(x) = (x, c) minAx = b

iB{ij}xi + xn+1= {0j}x 0, xn+1 0(1.24)Se poate observa uor c acest model poate rezolvat cu ajutorul reoptimizrii.Soluiaacestei problemevaavea(n + 1)coordonate. Sevorluaprimelencomponente pe care le vom nota cux2 S2.5. Cu soluiax2astfel obinut se va trece la pasul 2 din algoritm.Observaie:Mulimeasoluiilor posibile Sesteaproximatcuunir demulimi tot mairestrictive, care sunt mulimile soluiilor posibile ale modelelor liniare construite npasul 4 din algoritm.Sepoatedemonstracncazul ncaredateledeintrarealeproblemei, A, c, b,sunt formatedinnumerentregi; iar mulimeaSestemrginitatunci dupunnumrnitdepai sevaobinesoluiaoptimaleproblemei deminimizaretotalntreag.Inegalitatea

iB{ij}xi {0j}se numete tietura lui Gomory, unde{x} reprezint partea fracionar anumrului realx.Pentru oricex R avemx = {x} + [x], unde [x]este partea ntreag a numrului.Teorema 1.11.1.Presupunem c problema relaxat admite soluie optim, funciade scop este mrginit inferior (pentruf(x0) w : w f(x0)).Dup un numr nit de iteraii ne vom ntlni cu una din urmtoarele situaii:1. obinem soluia optim pentru problema de programare total ntreag;2. gsimf(x0) < w;3. demonstrm despre o variabil c poate lua numai valori negative.61Exemplu:___f(x) = x16x2 +x3 min2x13x2 + x3= 2x1 + 3x2 + x4= 33x1 + 6x2 + x5= 3x1, . . . , x5 N___f(x) = x16x2 + x3 min2x13x2 + x3= 2x1 + 3x2 + x4= 33x1 + 6x2 + x5= 3xj 0, j= 1, 5Matricea problemei relaxate esteA =__2 3 1 0 01 3 0 1 03 6 0 0 1__A1A2A3A4A5Problema este n forma standard de lucru i vom rezolva cu algoritmul simplexprimal.1 A3A4A5 A12 1 3 1 -6A2-3 3 6 3 -8 2 3 3 2 -9 - 1 1/2 2 A3A4A2 A17/2 -1/2 1/2 -1/2 -2A51/2 -1/2 1/6 -1/2 4/3 7/2 3/2 1/2 1/2 -5 Soluia optim estex1=_0 127232 0_d0= fmin=12j {2, 3, 4}02=12 N62Pentruj= 2 ales din mulimea2 3 4 scriem tietura lui Gomory.

iB{ij}xi {0j}j= 2 02=12 {02} =12i B = 1 5 13=72 12=12{5,2} =165,2=16 {52} =16Folosind tietura lui Gomory putem scrie modelul:___f(x) = x16x2 +x3 min2x13x2 + x3= 2x1 + 3x2 + x4= 33x1 + 6x2 +x5= 312x1 +16x5 12x1. . . x5 0___f(x) = x16x2 + x3 min2x13x2 + x3= 2x1 + 3x2 + x4= 33x1 + 6x2 + x5= 312x116x5 + x6= 12x1. . . x6 0Rezolvm cu reoptimizare. Matricea problemei esteA1=____2 3 1 0 0 01 3 0 1 0 03 6 0 0 1 0120 0 0 161____b1=____23312____A11A21A31A41A51A61c =_1 6 1 0 0 0_Vom rezolva cu algoritmul simplex dual. Putem scrie:1 A31A41A21A61 A117/2 -1/2 1/2 -1/2 -1/2 -3/2 1A511/2 -1/2 1/6 -1/6 -1/2 3/2 3 7/2 3/2 1/2 -1/2 1/2 -9/2 La completarea tabelului folosim calculele:A11=72A3112A41 +12A21 +A61=72(1, 0, 0, 0) 12(0, 1, 0, 0) ++12(3, 3, 6, 0) +(0, 0, 0, 1) =_72 32, 12+32, 3, _= (2, 1, 3, )_2, 1, 3, 12_= (2, 1, 3, ) = 12b1=72A31 +32A41 +12A21 + A61 = 12632 A31A41A21A11 A617 -1 1 -2 -1 -3A51-2/3 -1/3 0 1/3 -1/3 2 0 2 0 1 1 -3 Soluia optim din acest ultim tabel estex2= (1, 0, 0, 2, 0) S, deci pe baza principiului de relaxare este soluie i pentruproblema iniial.d0= 1 = fminS se rezolve problema___f(x) = 6x1 + 5x2 + 3x3 max2x1 + 3x2 + 3x3 2003x1 + 4x2 + 2x3 3004x3 + 3x2 + 4x3 360x1, x2, x3 NA =__2 3 33 4 24 3 4__Problema relaxat n forma standard este___f(x) = 6x15x23x3 min2x1 + 3x2 + 3x3 + x4= 2003x1 + 4x2 + 2x3 + x5= 3004x1 + 3x2 + 4x3 + x6= 360xj 0; j= 1, 6Acest model poate rezolvat cu algoritmul simplex primal, dup care folosim metodalui Gomory.642Modelespecialedeprogramareliniar. Problemadetransport2.1 Formulareaproblemei, proprieti generalen acest paragraf vom prezenta o problem particular de programare liniar.Din punct de vedere economic se poate formula urmtoarea problem.Fiem centre de aprovizionare (depozitare) notate cuA1, . . . , Am.Fien centre de consum (beneciari) notate cuB1, . . . , Bn.Dac un produs omogen este depozitat n cantitileai, i = 1, m n centreleAi,i estecerutdectrebeneciari ncantitateabj, j =1, n, iarcosturileunitaredetransport de la centrulAila beneciarulBjsunt egale cucijatuncisseorganizezetransportul astfel nctcheltuieliledetransportseminime!Dac notm cu xijcantitatea de produs care va transportat de la furnizorul ila consumatorulj, atunci matematic putem descrie problema cu urmtorul model:___f=m

i=1n

j=1cijxij minn

j=1xij ai, i = 1, mm

i=1xij bj, j= 1, nxij 0,m

i=1ai n

j=1bj, cij 0(2.1)Funciaobiectivreprezintevidentcheltuieliletotale, prinurmarescopul esteminimizarea acestora.Primele m restriciin

j=1xij ai, i = 1, marat c totalul cerut de consumatori65de la furnizoruli nu poate depi disponibilul acestuia,iar urmtoarelen restriciim

i=1xij bj, j=1, n se refer la faptulc totaluldistribuit de ctre furnizori trebuie s e cel puin egal cu necesarul consumatorilor.Restriciile

ai

nj=1bj, cij 0 arat c disponibilul total este cel puin egalcu necesarul total.Sepoateobservauorcacestmodelnumitmodel liniardetransportesteoproblemdeprogramareliniarcum + nrestriciii m nvariabile. Problemeipropuse i putem asocia urmtorul graf orientat, numit reea de transport:bmAiBA1AmB1Bnbib1Bja1aiamANodul A se numete nod de intrare n reea, iar nodul B nod de ieire din reea.Deniia2.1.1. Dac ai>

bjsau ai

jbjatunci seintroduceunconsumatorctiv(Bn+1)al cruinecesar este egal cum

i=1ain

j=1bj, iar costurile unitare de transport ind nule.Dac

iai40=b1 + b2 + b3 + b4rezultcproblemaesteneechilibrat. Vomintroduceunbeneciarctivi vomaveaurmtorul tabel detransport:2 1 3 2 0 151 2 3 1 0 153 2 1 2 0 209 8 8 15 10 50Folosind metoda colului de N-V, vom determina o soluie bazic iniial. Putemscrie pentru celulele alese: x11= min(15, 9) = 9 x12= min(6, 8) = 6 x22= min(15, 2) = 2 x23= min(13, 8) = 8 x24= min(5, 15) = 5 x34= min(20, 10) = 10 x35= min(10, 10) = 10Vom introduce soluiile obinute n tabel i vom avea:v1v2v3v4v52 1u19 63 2 0 152 3 1u212 8 50 152 0u33 2 110 10209 8 8 15 10 50Valoarea funciei de scop pentru aceast soluie bazic este:f(xB) = 2 9 +1 6 +2 2 +3 8 +1 5 +2 10 = 18 +6 +4 +24 +5 +20 = 77 u.m.81nscopul vericrii optimalitii, determinmvalorilevariabilelor duale. Putemscrie sistemul liniar nedeterminat:___u1 +v1= 2u1 +v2= 1u2 +v2= 2u2 +v3= 3u2 +v4= 1u3 +v4= 2u3 +v5= 0Lundu1= 0, obinemu2= 1u3= 2v1= 2v2= 1v3= 2v4= 0v5= 2.Condiia de optimcij (ui +vj) 0 pentru oricei = 1, 3 ij= 1, 5 o vericmfolosind tabelul ajuttor:21 2 0-2 0201031220211-220301001123-12-1 -32000Deoarece exist(i, j) pentru carecij (ui +vj) < 0, nseamn c soluia bazicnu este optim. min{2, 1, 3} = 3, astfel vom alege celula liber (3,3) cu carevom construi-ciclul. n acest scop revenim la tabelul de transport:2 19 63 2 0 152 3 18 5120 151 2 0103 210209 8 8 15 1050Pe-ciclul construit lund o direcie de parcurgere, putem scrie:Q_e3e3_+ ( x23Q) _e2e3_+ ( x24 + Q) _e2e4_ ( x34Q) _e3e4_.Observaie. ColoaneledinmatricearestriciilorA, corespunztoarecelulelorcare formeaz - ciclul, formeaz un sistem liniar dependent de vectori. Adic orice82combinaie liniar a vectorilor respectivi egal cu zero nu implic egalitatea cu zeroa coecienilor combinaiei liniare. Pe baza teoremei 1.3.4 avem:_e3e3__e2e3_+_e2e4__e3e4_= 0Vom nmuli egalitatea cu o cantitateQ = 0 i vom avea:Q_e3e3_Q_e2e3_+ Q_e2e4_Q_e3e4_= 0.Considerm un vector:v= x23_e2e3_+ x24_e2e4_+ x34_e3e4_,combinaialiniaravectorilorbazici din-ciclu, lacareadugmvectorul nul.Astfel putem scrie:v= Q_e3e3_+ ( x23Q) _e2e3_+ ( x24 + Q) _e2e4_+ ( x34Q) _e3e4_iavemchiarcombinaialiniaravectorilordin-ciclunformancareamscris.Continum prin nlocuirea valorilor actuale ale variabilelor xij, i obinem:Q_e3e3_+ (8 Q) _e2e3_+ (5 +Q) _e2e4_+ (10 Q) _e3e4_.Dintre soluiile ecuaiilor 8 Q = 0 i 10 Q = 0, vom alege valoarea minim iastfel pentruQ=8 celula (2,3) va iei din baz. Efectum apoio redistribuire pe-ciclu i obinem urmtorul tabel de transport:2 19 63 2 0 152 1123130 151 2 03 28 2 10209 8 8 15 10 5083Valoarea funciei de scop (costul transportului) pentru aceast soluie va :f(xB) = 29+16+22+113+18+22+010 = 18+6+4+13+8+4 = 53 < 77 u.m.Continum cu vericarea optimalitii. Avem de rezolvat sistemul:___u1 +v1= 2u1 +v2= 1u2 +v2= 2u2 +v4= 1u3 +v3= 1u3 +v4= 2u3 +v4= 0.Lund u1= 0, avem pe rnd soluiile:u2= 1 v1= 2u3= 2 v2= 1v3= 1v4= 0v5= 2Folosim tabelulajuttor:2 1 -1 0 -20201034220211-22033100123-12-1102000Exist(i, j) pentru carecij (ui + vj) < 0, ceea ce nseamn c nu am obinutsoluia optim. Alegem celula liber (2,1) care va intra n baz i cu care construim-ciclul. Revenim iari la tabelul de transport:2 19 63 2 0 151 2 123130 151 2 03 28 2 10209 8 8 15 10 5084Putem scrie:Q_e2e1_+ ( x11Q) _e1e1_+ ( x12 + Q) _e1e2_+ ( x22Q) _e2e2_Q_e2e1_+ (9 Q) _e1e1_+ (6 +Q) _e1e2_+ (2 Q) _e2e2_Alegemdintresoluiileecuaiilor9 Q=0i 2 Q=0minimul, adicQ=2.celula (2,2) va iei din baz. Pe -ciclul construit, efectum o redistribuire i obinemurmtorul tabel:2 17 83 2 0 151 122 3130 151 2 03 28 2 10209 8 8 15 10 50Valoarea funciei de scop pentru aceast soluie va :f(xB) = 2 7 + 1 8 + 1 2 + 1 13 + 1 8 + 2 2 = 14 + 10 + 13 + 12 = 49u.m.n continuare, va vericat optimalitatea soluiei i vom avea de rezolvat sistemulde ecuaii:___u1 + v1= 2u1 + v2= 1u2 + v1= 1u2 + v4= 1u3 + v3= 1u3 + v4= 2u3 + v5= 0.Soluiile sistemului sunt:u1= 0u2= 1u3= 0v1= 2v2= 1v3= 1v4= 2v5= 0.Construim tabelul ajuttor:852 1 1 2 002010322000-1102233100103121102000Deoarece pentru oricei=1, 3 ij=1, 5 diferenelecij (ui + vj) 0, rezultc soluia obinut este optim ifmin= 49 u.m.ProblemepropuseS se rezolve urmtoarele probleme de transport:1.2 1 3 2 1501 2 3 1 1503 2 1 2 20090 75 85 150Soluia este: x11= 75, x12= 75, x21= 15, x24= 135, x33= 85, x34= 15.Cost de transportCT= 490.2.1 3 4 2 602 1 2 3 2804 1 3 2 21080 200 70 250Soluia este: x11= 60, x21= 205, x22= 190, x23= 70, x32= 10, x34= 200.Cost de transportCT= 840.863Elementedeteoriajocurilor3.1 Noiuni introductive3.1.1 Noiuni debazTeoria jocurilor este teoria matematic a situaiilor de conict.Deniia 3.1.1.Prin situaii de conict nelegem situaiile n care se ntlnescdou sau mai multe pri a cror activitate urmrete un scop bine determinat i ncare interesele prilor sunt contrarii.Oricesituaiedeconict, luatdinviaadetoatezilele, estecomplexcunu-meroi factori secundari.Pentruaputeaefectuaoanalizmatematicasituaiei deconicttrebuiesneglijm aceti factori secundari i s construim un model al situaiei. Acest modelsimplicat, model formal al situaiei de conict, este numit jocmatematic.n continuare denim elementelefundamentalealeunuijocmatematic.Deniia3.1.2. Prinpartidnelegemunprocesformat dintr-osuccesiunedeaciuni (mutri)executate, rndpernd, dupanumitereguli careconstituiecar-acteristicajocului. Aciunilesuntexecutatedeunnumrnitdepersoanenumitejuctori (sau parteneri).ntr-un joc exist o regul de repartiie de valori ntre juctori; care permiteecrui juctor s-i xeze ca scop realizarea unei valori ct mai mari.Pentruformulareamatematicasituaiei deconict, descriereaunui joc,considermn juctori, notate cui {1, 2, . . . , n}.FieAimulimea aciunilor care sunt la dispoziia juctoruluii, i = 1, n.Dac lum ai Ai, atunci spunem c juctorul i a ales aciunea aii {1, . . . , n}.Utilitateaalegerii aciunii aipentrujuctorul i poatemsuratcuofunciereal, notat cufi, care reprezent ctigul juctoruluii, pentrui = 1, n.87Problema central a teoriei jocurilor,este cum s-i aleag juctoruli aciuneaaica s obin un ctig maxim, innd seama c i ceilali juctori urmresc acestscop.3.1.2 ClasicareajocurilorJocurile pot clasicate dup diferite criterii.a) Dupnumruljuctorilor putem distinge jocuri cu 2 juctori, 3 juctori,etc.Deobicei numrul juctorilor nucoincidecunumrul persoanelor zicecareparticip la joc, acestea pot forma coaliii.Numrul juctorilorestedeterminatdemulimeaintereselorcontrarii careseconfrunt.Deexemplujocul bridgeesteunjocmatematiccudoi juctori (dei numrulpersoanelorzicecareparticipeste4);unatacaerianpoatemodelatcuunjoccu doi juctori.b) Dac pentru un joc cun juctori existunnumrrealc astfel nctf1(a1i1, . . . , anin) + + fn(a1i1, . . . , anin) = c, pentru orice(a1i1, . . . , anin) A1 Anatunci spunem c acest joc este un joccusumconstant.Dacc = 0 atunci se numete joccusumnul.c) Dup numrul aciunilor care stau la dispoziia ecrui juctor putem distingejocuri nite, dac A1, . . . , An sunt mulimi nite; i jocuri innite dac exist celpuin o mulimeAi, i {1, . . . , n} cu o innitate de elemente.d) Dup natura aciunilor care stau la baza juctorilor distingem jocuri cu aci-uneliber i aciunealeatoare.O aciuneai Aiesteliber dac ea poate utilizat de ctre juctoruli norice moment.Oaciuneai Aiestealeatoaredacestealeascuajutorul unui mecanismaleator (zar, urn cu bile, rulet).Deexempluahul esteunjoccuaciuni libere, iar tableleunjoccuaciunialeatoare.e) Dup informaia disponibil ecrui juctor exist- joc cu informaiecomplet - ecare juctor cunoate ntreaga desfurare ajocului atunci cnd alege o anumit aciune;- joc cu informaie incomplet - juctorul nu cunoate ce cri posed ceilalijuctori - deci nu cunoate nici mulimea aciunilor acestora.Majoritateajocurilorcunsemntatepracticsuntjocuri cuinformaii incom-plete. Necunoaterea aciunilor adversarilor este de obicei o caracteristic a situai-ilor de conict.Scurt istoric (vezi [Szab]).884Jocurimatricialen continuare vom studia jocurile nite cu doi juctori i cu sum nul. Acesteareprezint o clas important de jocuri.Considerm doi juctori notate cu 1 i 2. Notm cuA1= {a11, . . . , a1m} mulimea aciunilor juctorului 1 iA2= {a22, . . . , a2n} mulimea aciunilor juctorului 2Presupunem c pe parcursul partidei juctorul 1 alege aciunea a1i, iar juctorul2 alege aciuneaa2j.Juctorii nu au informaie n legtur cu alegerea fcut de cellalt.Presupunem c n urma acestor alegeri juctorul 1 obine ctigulf1(a1i, a2j), iarjuctorul 2 obine ctigulf2(a1i, a2j), i are loc relaiaf1(a1i, a2j) + f2(a1i, a2j) = 0 f1(a1i, a2j) = f2(a1i, a2j)Astfel, sepoatearmacntr-unjoccu2juctori i sumnulestesucientscunoatemctigul juctorului 1. Ctigul juctorului 2esteopusul ctiguluirealizat de ctre juctorul 1.Deci unjocnitcudoi juctori i cusumnulestecompletdescrisdacsecunosc mulimile niteA1, A2i funcia realf1: A1A2 R.Tripletul (A1, A2, f1) care caracterizeaz jocul poate reprezentat cu urmtorultabel:A1A2a21. . . a2j. . . a2na1c11. . . c1j. . . c1n......aici1. . . cij. . . cin......amcm1. . . cmj. . . cmn89undecij= f1(a1i, a2j) este ctigul juctorului 1.MatriceaC=(cij)i,jsenumetematriceactigurilor(saumatriceaplilor,matricea jocului).Jocul nit cu 2 juctori i sum nul este complet determinat de tripletulG = (A1, A2, C), undeC Mm,n.Prima etap n cercetarea situaiilor de conict este stabilirea aciunilor jucto-rilor i ntocmirea matricei de pli.Exemplu: jocul MorraEsteunjoccudoijuctori(cares-apracticatnItaliaantic)ncarejuctoriiarat simultan unul sau dou degete i n acelai timp strig numrul degetelor pecare cred c arat adversarul.Regula de repartiie:-dacnumaiunuldintrejuctorighicetenumruldegetelorartatedeadver-sar, atunci elprimetedelaacestaatteauniti monetarectedegeteauartatmpreun. Dacambii juctori ghicescsaunici unul nughiceteatunci nici unuldintre ei nu primete nimic.La acest joc ecare juctor poate alege una dintre urmtoarele patru aciuni:- s arate un deget i s strige unu (1, 1)- s arate dou degete i s strige unu (2, 1)- s arate un deget i s strige doi (1, 2)- s arate dou degete i s strige doi (2, 2).Matricea ctigurilor este:A1 \ A2(1, 1) (1, 2) (2, 1) (2, 2)(1, 1) 0 2 -3 0(1, 2) -2 0 0 3(2, 1) 3 0 0 -4(2, 2) 0 -3 4 0Observaie. Aceast teorie este mai important pentru modul de abordare aproblemelor de competiie dect pentru tratarea lor sistematic.4.1 Strategii4.1.1 Strategii optimentr-unjocmatricealDeniia 4.1.1.Prin strategia unui juctor se nelege un ansamblu de reguli caredenescnmodunicalegereaaciunilorliberenfunciedesituaiaconcretivitn decursul jocului.De obicei alegerea unei aciuni libere este efectuat de juctor n decursul joculuin funcie de situaia concret ivit.90Totui, dinpunctdevedereteoreticesteposibil catoateacestesituaii seprevzute de juctor naintea nceperii jocului,de aceea la nceput juctorul trebuiesprevadngndtoatesituaiileisaleagsoluiasapentruecaredintreele,ceea ce nseamn c juctorul a ales o strategie bine denit.Teoria jocurilor urmrete gsirea celor mai bune strategii pentru ecare juctor.Juctorul trebuiesianconsiderarecadversarul estecel puintotattdepriceput ca i el i s fac totul pentru impiedicarea scopului acestuia.Teoriajocurilornusemizeazpeincapacitateaadversarului, ci dincontrsebazeaz pe calitile intelectuale ale juctorilor. Principiul juctorilor este principiullipsei de risc.Un juctor alege strategia lund n considerare aciunea cea mai defavorabil pecare i-o rezerv adversarul.n continuare prezentm formularea matematic al strategiei.FieA1= {a11, . . . , a1m} mulimea aciunilor juctorului 1,A2= {a21, . . . , a2n} mulimea aciunilor juctorului 2 iC= (cij)i,jmatricea plilor.Jucndu-se mai multe partide presupunem c juctorul 1 alegeaciuneaa11cu probabilitatea (ponderea)x1aciuneaa12cu probabilitateax2. . .aciuneaa1icu probabilitateaxi. . .aciuneaa1mcu probabilitateaxm.Vectorulx = (x1, . . . , xm) Rmse numete strategia juctorului 1.Ponderile arart n ce msur sunt folosite aciunile, care stau la dispoziia juc-torului, pentru a atinge scopul propus.Evident, oricestrategiex=(x1, . . . , xm)ajuctorului 1vericproprietateax Rm+i mi=1xi= 1.Vom nota cuXmulimea tuturor strategiilor ale juctorului 1.Adic:X= {x Rm+m

i=1xi= 1}n mod analog putem deni strategia juctorului 2.Jucndu-se mai multe partide presupunem c juctorul 2 alegeaciuneaa21cu probabilitatea (ponderea)y1aciuneaa22cu probabilitateay2. . .aciuneaa2jcu probabilitateayj. . .aciuneaa2ncu probabilitateayn.Vectoruly= (y1, . . . , yn) Rnse numete strategia juctorului 2.91Vom nota cuY= {y= (y1, . . . , yn) Rn+|n

j=1yj= 1}mulimea strategiilor juctorului 2.Dacntr-opartidjuctorul 1alegeaciuneaa1iiar juctorul 2aciuneaa2jatunci ctigul juctorului 1, cu notaiile ntroduse n primul capitol, estecij.Dar probabilitile cucare aufost alese aceste aciuni sunt xirespectivyj.Alegerile se fac n mod independent ceea ce nseamn c probabilitatea acestei alegeriestexiyj,(adicprodusulprobabilitilor). Deci, probabilitateactigului cijestexiyj.Astfel ctigul juctorului 1putemdescriematematiccuovariabilaleatoarediscret care ia valorilecijcu probabilitilexiyj,(i, j) {1, . . . , m} {1, . . . , n}.Valoarea medie al variabilei aleatoare discrete este:F(x, y) =m

i=1n

j=1cijxiyj= (x, Cy)Funcia F: XY R se numete funcie de ctig mediu i reprezint ctiguljuctorului 1, dac n decursul partidelor juctorii folosesc strategiilex iy.StrategiioptimeCu ajutorul funciei de ctig mediu putem deni strategiile optime ale jucto-rilor.Dac juctorul 1 folosete strategiax Xatunci el ctig cel puinF(x) = minyYF(x, y)indiferent de strategia utilizat de ctre juctorul 2.Juctor urmrete obinerea unui ctig maxim, iar cel mai mare ctig ce poate realizat de ctre el este:maxxXF(x) = maxxX(minyYF(x, y)) (4.1)deoarece va alege o strategie pentru a-i maximiza ctigurile.Oricestrategiecaregaranteazjuctorului 1unctigmediuegal cu(4.1)senumete strategie maximin.Deci, o strategiex0 Xa juctorului 1 se numete strategie maximin dac:F(x0) = maxxXF(x)Astfel putem formula urmtoarea problem de maximizare (a crei soluie estex0) :(A)___F(x) : x X} maxunde F: X R denit prinF(x) = minyYF(x, y) pentru orice x X.92Soluia optim a problemei (A), notat cux0,este strategic maximin pentru juc-torul 1.Juctorul 2 urmrete realizarea unei pierderi minime. Astfel, folosind un raion-ament analog, putem scrie c juctorul 2 pierde cel multF(y) = maxxXF(x, y)dac folosete strategiay Y.Pentru a-i minimiza pierderile alege o strategie pentru care obine:minyYF(y) = minyYmaxxXF(x, y) (4.2)Strategia care garanteaz juctorului 2 pierdere minim este egal cu (4.2) i senumete startegie minimax.Deci, o strategiey0 Ya juctorului 2 se numete strategie minimax dacF(y0) = minyYF(y)Strategiile minimax sunt soluiile problemei de minimizare(B)___F(y) : y Y } min undeF: Y R denit prinF(y) = maxxX F(x, y) pentru orice y Y.Deniia4.1.2. FieX, Y doumulimi nevide, oarecarei F : X Y Roaplicaie. Spunemcpunctul (x0, y0) X Y esteunpunct aal funciei Frelativ la mulimeaX Y dac:F(x, y0) F(x0, y0) F(x0, y) pentru orice (x, y) X Y.Exemplu:Considerm mulimileX= Y= R, F: X Y R denit prinF(x, y) = x2a2+y2b2pentru orice(x, y) X Y,a, b R.Reprezentnd aceast suprafa de ordinul doix2a2+y2b2= zobinem un paraboloid - hiperbolic.93OzSe poate verica uor c punctul(0, 0) este un punct a al funcieiFrelativ lamulimeaX Y, deoareceF(x, 0) F(0, 0) F(0, y)pentru orice(x, y) X Y.Fundamentarea teoretic vezi [Szab].Teorema4.1.3. Pentru orice joc matriceal sunt adevrate urmtoarele armaii1. dac(x0, y0) X Y esteunpunctaalfuncieiFrelativlaX Y atuncix0esteostrategiemaximinal juctorului1i y0esteostrategieminimaxaljuctorului 2.2. dac x0 Xeste o strategie maximin al juctorului 1 i y0 Yeste o strategieminimax al juctorului 2 atunci(x0, y0) este un punct a al funcieiFrelativlaX Y.Demonstraie. [Szab].Observaia 4.1.4.Din teorema 4.1.3 rezult c cele mai bune strategii pentru juc-torul 1 sunt strategiile maximin i pentru juctorul 2 strategiile minimax.Deoarece(x0, y0) este un punct a pentru funciaF, are loc relaiaF(x, y0) F(x0, y0) F(x0, y) pentru orice (x, y) X Y.Nici unul dintre juctori nu este interesat s-i schimbe strategia. Se poate observadinaceastinegalitatecpentruoricealtstrategiex Xctigul juctorului 1devinemaimic,iarpentruoricealtstrategiey Y pierderilejuctorului2devinmai mari.94Perechea(x0, y0)senumetesoluiaajocului matriceal (undex0, y0suntstrategii optime).Pe baza teoremelor prezentate se poate arma c(x0, y0) X Y este soluiajocului matriceal dac i numai dac este un punct a al funciei Frelativ la XY.NumrulF(x0, y0)not=w se numete valoareajocului matriceal.Din3.1.12rezultcunjocmatricealareosingurvaloareegalcunumerele(4.1), (4.2).weste cel mai mare ctig al juctorului 1 pe care poate spera s i-l asigure ieste cea mai mic pierdere pe care juctorul 2 poate s o aib.A rezolva un joc matriceal nseamn a gsi o soluie a jocului i valoarea jocului.4.1.2 Strategii optimentr-unjocmatriceal simetricDeniia4.1.5. Fie o matrice ptraticC Mn(R).Matricea se numete strmb simetric dac elementele de pe diagonala princi-pal sunt egale cu 0 iar succesiunea elementelor de pe linii este aceeai cu succesiuneaelementelor pe coloane cu semn schimbat.AdicCT= C.De exemplu matricea__0 1 21 0 32 3 0__este o matrice strmb simetric.Deniia4.1.6. Unjocmatriceal G=(A1, A2, C)senumetejocsimetricdac|A1| = |A2| = n iC Mn(R) este strmb simetric.Teorema4.1.7. Valoareaunui jocmatriceal simetricestezeroi oricestrategieoptim pentru unul dintre juctori este optim i pentru cellalt juctor.Demonstraie. [Szab].Observaia 4.1.8.Dac valoarea unui joc matriceal este zero nseamn c juctorul1 nu ctig nimic i juctorul 2 nu pierde nimic, adic regulile jocului nu favorizeazpe nici unul din juctoriUn joc matricial cu valoarea zero se numete jocechitabil.Dinteorema4.1.7rezultcoricejocsimetricestejocechitabilnsreciprocaarmaiei nu este adevrat.954.1.3 ProprietialestrategiiloroptimeialevaloriiunuijocmatricealOrice joc matriceal are cel puin o soluie deoarece funcia Fare cel puin un puncta (vezi consecina 3.1.12) relativ la mulimeaX Y.Teorema4.1.9. Un joc matriceal are e o soluie unic, e o innitate de soluii.n continuare prezentm cteva proprieti care arat cum se schimb valoareajocului dac efectum operaii aritmetice asupra elementelor matricei de pli.Teorema4.1.10. Fie un numr real oarecare notat cukiG = (A1, A2, C) un jocmatriceal cu matricea de pliC=___c11. . . c1n...cm1. . . cmn___Dac G = (A1, A2, C) este un joc matriceal cu matricea de pliC=___c11 +k . . . c1n + k...cm1 +k . . . cmn + k___atunci are loc relaia w = w + ki orice soluie a uneia dintre jocuri este soluie ipentru cellalt joc matriceal.Demonstraie. [Szab].Reciproca armaiei se demonstreaz n mod analog.Teorema4.1.11. Fiek > 0, k R. DacG = (A1, A2, C) este un joc matriceal cumatricea de pliC=___c11. . . c1n...cm1. . . cmn___iar G = (A1, A2, C) este un joc matriceal cu matricea de pliC=___kc11. . . kc1n...kcm1. . . kcmn___atunci w=k wioricesoluieauneiadintrejocuriestesoluieipentrucellaltjoc.Demonstraiaesteuoar, sefoloseteunraonamentanalogcucel utilizatlademonstrarea teoremei 4.1.10.964.2 Principiul dominriiDin matricea de pli se poate deduce dac alegerea anumitor aciuni este dezavan-tajos pentru juctori.Pentru o nelegere mai profund considerm un exemplu. Considerm joculA1 \ A2a21a22a23a24a113 3 -6 -5a121 2 4 3a130 2 -3 2Juctorul 1 urmrete obinerea unui ctig maxim.Dac alege aciunea a13 atuncise poate observa c ctigurile obinute (scrise n linia a 3-a) sunt mai mici sau egaledect ctigurile obinute cu alegerea aciuniia12(linia a doua). Deci, indiferent destrategia folosit de ctre juctorul 2, juctorul 1 nu va alege aciuneaa13, deoareceeste dezavantajoas pentru el. Astfel putem tia linia a treia din matricea de pli,adic putem elimina aciuneaa13din mulimea aciunilorA1.Astfel obinem jocul matricealA1 \ A2a21a22a23a24a113 3 -6 -5a121 2 4 3Acum analizm matricea de pli din punctul de vedere al juctorului 2. Acestjuctorurmreteminimizareapierderilor. Putemobservacncoloanaadouatoate elementele sunt mai mari sau egale dect n prima coloan. Astfel juctorul 2nu va alege niciodat aciuneaa22, deci coloana a doua poate tiat din matriceade pli, aciuneaa22poate eliminat din mulimea aciunilorA2.Astfel se obine jocul redusA1 \ A2a21a23a24a113 -6 -5a121 4 3Deniia4.2.1.Fie spaiul Rn, n N. Considerm punctelex = (x1, . . . , xn) Rniy=(y1, . . . , yn) Rn.Introducemorelaiedeordineastfel: x yispunemcxeste dominat dey(sauydomin pex) dacxj yjpentru oricej= 1, n.Fie jocul matriceal de tipulmnA1 \ A2a21a22. . . a2na11c11c12. . . c1na12c21c22. . . c2n......a1mcm1cm2. . . cmn97Putem arma c o aciune care corespunde unei liniidominate de o alt linieeste dezavantajoas pentru juctorul1,i o aciune care corespunde unei coloanecare domin o alt coloan este dezavantajoas pentru juctorul 2. Aceste aciunidezavantajoase pentru juctori pot eliminate.Aceast regul de reducere al matricei de pli este numit principiul dominrii.Teoremele urmtoare prezintlegturadintre strategiile optime i principiuldominrii.Teorema4.2.2.FieG = (A1, A2, C) un joc matriceal de tipulmn. Presupunemcliniapamatricei Cestedominatdeliniaq, iar G=(A1, A2, C)esteunjocmatriceal detipul (m 1) n, ncare A1=A1\{a1p}i ncarematricea Cesteobinut prin eliminarea linieip din matriceaC.Sunt adevrate urmtoarele armaii:1. Dac x0= ( x01, . . . , x0p1, x0p+1, . . . , x0m) este o strategie optim pentru juctorul1 n jocul G, atuncix0= ( x01, . . . , x0p1, 0, x0p+1, . . . , x0m) este o strategie optimal juctorului 1 n jocul G.2. Fiecarestrategieoptimal juctorului 2njocul Gesteoptimpentruacestjuctor i n jocul G.3. w = w(valoarea jocului G este egal cu valoarea joculuiG)Teorema 4.2.3.Fie G = (A1, A2, C) un joc matriceal de tipul mn n care coloanar al matricei C domin coloana s, iar G = (A1, A2, C) este un joc matriceal de tipulm(n1) n care A2= A2\{a2r} i n care Ceste obinut prin eliminarea coloaneirdinC.Sunt adevrate urmtoarele armaii:1. Dac y0=( y01, . . . , y0r1, y0r+1, . . . , y0n)esteostrategieoptimal juctorului 2n joculG, atunciy0= ( y01, . . . , y0r1, 0, y0r+1, . . . , y0n) este o strategie optim aljuctorului 2 n jocul G.2. Fiecare strategie optim al juctorului 1 n jocul G este optim pentru el i njocul G.3. w = w.Cu principiul dominrii putem reduce matricea jocului prin eliminarea aciunilordezavantajoase.984.3 Strategii pureFieG = (A1, A2, C), un joc matriceal cuC Mm,n.Fiemulimiledeindici I = {1, 2, . . . , m}, J = {1, 2, . . . , n}. X, Y reprezintmulimea strategiilor ale juctorilor.tim c x Rmeste o strategie pentru juctorul 1 dac xi 0 pentru orice i Ii mi=1xi= 1.Deniia4.3.1. Ostrategiex=(x1, . . . , xm)al juctorului 1pentrucareexisti Iastfel nctxi= 1, se numete strategiepur pentru juctorul 1.Se poate observa c juctorul 1 posed m strategii pure care sunt chiar elementelebazei canonice al spaiului Rm, i n continuare le vom nota cuei, i I.Observaia4.3.2. Oricestrategieal juctorului1poatescriscaocombinaieliniar a strategiilor pure.Folosirea unei strategii pureeide ctre juctorul 1 exprim faptul c juctorul 1alege pe tot parcursul jocului aceeai aciunea1i.n mod analog denim strategiile pure ale juctorului 2.tim c y Rneste o strategie pentru juctorul 2 dac yj 0 pentru orice j Ji nj=1yj= 1.Deniia4.3.3. Ostrategie y =(y1, . . . , yn) al juctorului 2pentrucareexistj Jastfel nctyj= 1, se numete strategiepur pentru juctorul 2.Juctorul 2 posedn strategii pure care sunt chiar elementele bazei canonice alspaiului Rn, i n continuare le vom nota cu ej, j J. Cele n strategii pure, ej, j J,formeaz baz canonic nRn.Observaia 4.3.4. Orice strategie al juctorului 2 este o combinaie liniar a strate-giilor pure.Folosireauneistrategiipure, ej, exprimfaptul cjuctorul 2alegepetotpar-cursul jocului aceeai aciunea2j.Urmtoareleteoremeprezintproprieti alefunciei dectigmediudacsefolosesc strategii pure.Teorema4.3.5. ntr-unjocmatriceal detipul m nsuntadevrateurmtoarelearmaii(1) x X minyYF(x, y) = minjJF(x, ej)(2) y Y maxxXF(x, y) = maxiIF(ei, y)Demonstraie. [Szab].99Consecina4.3.6. Valoarea unui joc matriceal w, veric relaiaw w wDemonstraie. [Szab].Acum prezentm cteva criterii pentru determinarea strategiilor optime.Teorema4.3.7. Dacx0esteostrategieal juctorului1ntr-unjocmatriceal detipul mn, cu valoareaw, atunci urmtoarele armaii sunt echivalente1. x0este o strategie optim a juctorului 12. este adevrat egalitatea:minjJF(x0, ej) = w3. pentru oricej Jeste ndeplinit inegalitateaw F(x0, ej)Demonstraie. [Szab].Teorema 4.3.8.Dac y0este o strategie pentru juctorul 2 ntr-un joc matriceal detipul mn, iar w este valoarea jocului atunci urmtoarele armaii sunt echivalente:1. y0este strategie optim pentru juctorul 22. este adevrat:w = max F(ei, y0), i I3. pentru ecarei Ieste ndeplinit inegalitateaF(ei, y0) w.Demonstraiasefacefolosindunraionamentanalogcucel folositlademon-strarea teoremei 4.3.7.Teorema4.3.9. Dacx0esteostrategiepentrujuctorul 1i y0ostrategiealjuctorului 2 ntr-un joc matriceal de tipul mn, iarw R, este valoarea jocului,atunci sunt echivalente urmtoarele armaii:1. (x0, y0) este o soluie a jocului iweste valoarea sa2. este adevrat relaia:maxiIF(ei, y0) = w = minjJF(x0, ej)3. Pentru ecare(i, j) I JavemF(ei, y0) w F(x0, ej)Demonstraie. Folosim teoremele 4.3.7 i 4.3.8.1004.4 Rezolvareajocurilormatriceale4.4.1 RezolvareajocurilormatricealecupunctaTeorema4.4.1. FieG = (A1, A2, C) un joc matriceal,C Mm,n(R).Dac matricea de pli admite punct aatunciw = w = wi sunt adevrate urmtoarele armaii:1. ci0j0 Ceste un punct a al matriceiC, adicminjJci0j= w i maxiIcij0= w2. Dacci0j0 Ceste un punct a al maticeiC, atunci(ei0, ej0) RmRnesteo soluie a jocului ici0j0este valoarea jocului.Demonstraie. [Szab].Cu ajutorul teoremei jocurile matriceale cu punct a rezolvm dup urmtoareaschem:1. analizmmatriceadepli C Mm,n, i aplicmprincipiul dominrii daceste posibil2. determinm numerelew = maxiIi= maxiIminjJcijw = minjJj= minjJmaxiIcijdacw=wrezultcmatriceadepliadmitepuncta,valoareaobinuteste valoarea jocului.(w este maximul minimelor din linii, iar w este minimul maximelor din coloane)3. din pasul 2 determinmi0 Iij0 Jastfel ncti0= minjJci0j= wj0= maxiIcij0= wLundx0= ei0iy0= ej0 (x0, y0) este soluia jocului.Observaia 4.4.2.Dac matricea de pli admite punct a atunci juctorii folosescstrategii pure, ceea ce nseamn c pe tot parcursul jocului juctorii folosesc o singuraciune.101Exemplu1.Considerm jocul matricealA1 \ A2a21a22a23a110,30 0,25 0,15a120,18 0,14 0,16a130,35 0,22 0,17a140,21 0,16 0,10Calculm valorile:w = maximinjcij= max(0, 15; 0, 14; 0, 17; 0, 10) = 0, 17w = minjmaxicij= min(0, 35; 0, 25; 0, 17) = 0, 17w = w w = 0, 17i0= 3 x0= (0 0 1 0) este strategie optim pentru juctorul 1j0= 3 y0= (0 0 1) este strategie optim pentru juctorul 2.Observaia 4.4.3.Dac aplicm principiul dominrii, atunci putem elimina aciu-nilea11, a12ia14din mulimeaA1i aciunilea21, a22din mulimeaA2. Astfel obinemjocul redusA1 \A2a23a310,17Aplicm teoremele 4.2.2, 4.2.3 i putem scriew = 0, 17x0= (0 0 1 0),y0= (0 0 1).Observaia 4.4.4.Exist jocuri n care matricea de pli admite mai multe punctedea. nacestecazuri juctorii pot folosi mai multestrategii optime. Strategiaoptim poate ales folosind un criteriu diferit de cel stabilit n joc.2. Fie jocul cu matriceaC=____2 9 3 17 6 5 82 3 4 105 6 5 6____Calculm valorilew = max(1, 5, 2, 5) = 5w = min(7, 9, 5, 10) = 5w = 5102Deoarecew = w putem scriew = c23 i0= 2 j0= 3 x01= (0, 1, 0, 0), y01= (0, 0, 1, 0)sauw = c43 i0= 4 j0= 3 x02= (0, 0, 0, 1), y02= (0, 0, 1, 0)4.4.2 RezolvareajocurilormatricialeprinreducerelamodeledeoptimizareliniarcurestriciiFie jocul matricealG=(A1, A2, C), C Mm,n(R). Strategiile optime ale juc-torilor sunt soluiile problemelor de optimizare:(A)___{F(x) | x X} maxx XF: X R, denit prinF(x) = minyYF(x, y)(B)___{F(y) | y Y } miny YF: Y R, denit prinF(y) = maxxX F(x, y)undeXiYreprezint mulimea strategiilor juctorilor.Folosindstrategiilepure(teorema4.3.5)acesteproblemepotscrisenurm-toarea form echivalent._minjJ F(x, ej) maxx X(4.3)i_maxiI F(ei, y) miny Y(4.4)Notm cus = minjJ F(x, ej).Putem scries = minjJ_m

i=1cijxi_m

i=1cijxi m

i=1cijxis, 0 pentru orice j JNotm cut = maxiI F(ei, y).Putem scrie103t = maxiI_n

j=1cijyj_n

j=1cijyj n

j=1cijyj t, 0 pentru orice i IAstfel avem urmtoarele probleme echivalente cu cele de mai sus:___s max

mi=1cijxis 0, j= 1, n

mi=1xi= 1,xi 0, i = 1, m(4.5)___t min

nj=1cijyj t 0, i = 1, m

nj=1yj= 1,yj 0, j= 1, n(4.6)Acum analizm restriciilem

i=1cijxis 0, j= 1, nPresupunem cs > 0 i mprim restriciile cus. Obinem astfelm

i=1cijxis 1 0, j= 1, nNotmxis= uipentru oricei = 1, m.Are loc relaiam

i=1xis=m

i=1ui m

i=1ui=1sn mod analog vom transcrie problema (4.6). Avem:n

j=1cijyj t 0, i = 1, m.104Presupunem ct > 0 i mprim restriciile cut. Obinem astfeln

j=1cijyjt1 0, i = 1, mNotmyjt= vjpentru oricej= 1, n.Are loc relaian

j=1yjt=n

j=1vj n

j=1vj=1tAstfel problemele (4.5), (4.6) sunt echivalente cu___

mi=1ui min

mi=1cijui 1, j= 1, nui 0, i = 1, m(4.7)___

nj=1vj max

nj=1cijvj 1, i = 1, mvj 0, j= 1, n(4.8)Se poate observa uor c problemele (4.7), (4.8) formeaz un cuplu dual.Teorema4.4.5. Dacw>0i x0Rm, y0Rnsuntsoluiileproblemelor(A)i(B)atunciu0=x0wiv0=y0wsuntsoluiileproblemelor(4.7)i(4.8)iarelocrelaia:m

i=1u0i=n

j=1v0j=1wDemonstraie. [Szab].Teorema4.4.6. Dacu0Rmiv0Rnsunt soluiile problemelor (4.7) i (4.8)atunci w=1

mi=1u0i=1

nj=1v0ji x0=wu0, y0=wv0suntsoluiileproblemelor(A) i (B).Demonstraie. [Szab].105Exemplu:1. Fie jocul matricealA1 \ A2(1) (2) (3)(1) -1 1 1(2) 2 -2 2(3) 3 3 -3Calculm valorilew = max{1, 2, 3} = 1w = min{3, 3, 2} = 2Deoarece w = w rezult c matricea de pli nu admite punct a. Pentru a determinastrategiile optime ale juctorilor vom utiliza teorema de mai sus. Strategiile optimevom determina prin intermediul unor modele de optimizare liniar cu restricii.Deoarece w=1 0(ceeacenseamnctrebuies avemw> 0, w> 0). Aplicm teorema 4.4.5. Vom considerak= 2 (cel mai micnumr real care adunat la elementele matricei de pli ne dw > 0, w > 0).Obinem astfel matriceaC=__1 3 34 0 45 5 1__pentru carew = max{1, 0, 1} = 1w = min{5, 5, 4} = 4Aplicmteorema4.4.5. Strategiileoptimevomputeadeterminacuajutorulsoluiilor optime ale modelelor___f(u) = u1 + u2 + u3 minu1 + 4u2 + 5u3 13u1 + 5u3 13u1 + 4u2u3 1u1, u2, u3 0(4.9)i___g= v1 + v2 + v3 maxv1 + 3v2 + 3v3 14v1 + 4v3 15v1 + 5v2v3 1v1, v2, v3 0(4.10)106Primul model se poate rezolva cu algoritmul simplex dual, iar problema a douacu algoritmul simplex primal.Vom rezolva problema (4.9).___f= u1 + u2 + u3 minu14u25u3 + u4= 13u15u3 + u5= 13u14u2 + u3 + u6= 1u1, . . . , u6 0A =____1 4 5 1 0 03 0 5 0 1 03 4 1 0 0 1A1A2A3A4A5A6____B= (A4, A5, A6) b =__111__1 A4A5A6 A1-1 -3 -3 -1 9 1A2-4 0 -4 -1 10 1/4A3-5 -5 1 -1 11 1/5 -1 -1 -1 0 4 2 A3A5A6 A11/5 -2 -16/5 -4/5 34/5 1/4A24/5 4 -24/5 -1/5 6/5 1/24A4-1/5 -1 1/5 -1/5 11/5 - 1/5 0 -6/5 1/5 9/5 3 A3A5A2 A1-1/3 -14/3 2/3 -2/3 6 1/7A61/6 5/6 -5/24 -1/24 1/4 -A4-1/6 -5/6 -1/24 -5/24 9/4 1/4 0 -1 1/4 1/4 3/2 4 A3A1A2 A5-1/14 -3/14 1/7 -1/7 9/7A63/28 -5/28 -5/56 -9/56 37/28A4-3/28 5/28 -9/56 -5/56 33/28 1/14 3/14 3/28 11/28 3/14 107Soluia optim esteu0=_314,328,114_.Modelul(4.10)estedualaproblemei rezolvate. Astfel dinultimul tabel putemciti soluiile dualei,v0=_556, 17,956_.Valoarea jocului(A1, A2,C) este w =1

3i=1u0i=1d0=2811x0= wu0 x0=_314 2811,328 2811,114 2811_=_611,311,211_y0= w v0 y0=_522,411,922_Valoarea jocului iniial estew = w 2 =2811 2 =611Jocul nu este echitabil.2. Fie jocul matriceal cu matricea de pli:C=__2 3 6 53 4 5 62 3 4 7__Aplicm principiul dominrii. Din punctul de vedere al juctorului 1 prima aciunenuesteavantajoasprinurmareputemeliminaprimaliniedinmatriceadepli.Sepoateobservauorcpentrujuctorul2nusuntavantajoaseaciunilea21i a24ceea ce nseamn c coloana a doua i a patra poate eliminat.Astfel avem de rezolvat jocul redus cu matricea de pli:C=_3 52 4_w = max{5, 2} = 2w = min{3, 4} = 3Lumk = 3 i obinemC=_6 21 7_Modelele liniare asociate matricei de pli sunt:___u1 +u2 min6u1 + u2 12u1 + 7u2 1ui 0, i = 1, 2___v1 + v2 max6v12v2 1v1 + 7v2 1v1, v2 0108Vom rezolva primul model liniar.___u1 + u2 min6u1u2 + u3= 12u17u2 +u4= 1ui 0, i = 1, 4A1A2A3A4A =_ 6 1 1 02 7 0 1_Aplicm algoritmul simplex dual.1 A3A4 A1-6 2 -1 6 1/6A2-1 -7 -1 10 1 -1 -1 0 3 2 A1A4 A3-1/6 2/6 -1/6 -A21/6 -44/6 -5/6 5/44 1/6 -8/6 1/6 3 A1A2 A3-7/44 -2/44 -9/44A41/44 -6/44 -5/44 6/44 8/44 14/44 Soluia optim esteu0= (6/44 8/44). Valoarea joculuiCeste w =1d0=4414.t1 e1= A3 B0t1= 944t2 e2= A4 B0t2= 544Deci soluia problemei a doua este: v0= (9/44, 5/44).109Strategiile optime ale juctorilor suntx0= u0 w = (6/14, 8/14) = (3/7, 4/7)y0= v0 w = (9/14, 5/14)Valoarea jocului iniial este:w =4414 3 =44 4214=214=17.Deoarece am aplicat la nceput principiul dominrii strategiile optime ale juctorilorn jocul considerat sunt: x0= (0 3/7 4/7),y0= (9/14 0 5/14 0).Rezolvareajocurilordetipul2 m, (n 2) (vezi [Szab]).110111112113114115116117118Bibliograe[Bla] BlagaL., LupaL., Elementedeprogramareliniar, Cluj-Napoca, Riso-print, 2003.[Bre] Breckner W., Cercetare operaional, Cluj-Napoca, Universitatea "Babe-Bolyai", 1981.[Char] Charnes A., and Cooper W. W., ManagementModelsandIndustrialAp-plicationofLinearProgramming, vol. I and II, New York, John Wiley &Sons, Inc., 1960.[Gas] Saul L. Gass, Linear Programming, An International Thomson PublishingCompany, 1985.[Szab] Szab Zs., Cercetri operaionale, Editura Universitii "Petru Maior" Tg.Mure, ISBN 973-7