+ All Categories
Home > Documents > 77448001 Cercetari Operation Ale Optimizari Liniare

77448001 Cercetari Operation Ale Optimizari Liniare

Date post: 18-Jul-2015
Category:
Upload: pulea-spataru
View: 463 times
Download: 2 times
Share this document with a friend

of 305

Transcript

iiJATEK 2005/3/1110:29page1#1iiiiii11 martie 2005iiJATEK 2005/3/1110:29page2#2iiiiii2iiJATEK 2005/3/1110:29page3#3iiiiiiDedic aceast carte icelor mele,Dalma i MariettaPrefaDatorit posibilitilor oferite n practic, programarea matematiccunoateodinamicspectaculoas. Programareamatematicdevineim-perativndeterminareasoluiilorpentrufenomeneledincelemai diversedomenii social-economice i pentru o varietate de probleme decizionale.n acest sens, responsabilitatea revine celor care construiesc i rezolv mo-dele ale fenomenelor, deoarece modelarea, rezolvarea i interpretarea solui-ilor obinute trebuie s e conforme cu realitatea obiectiv. Altfel ar apreaerori cantitative.Carteaprezintnmodriguros, dinpunctdevederematematic, teoriamodelelordeoptimizareliniarcurestricii. Suntprezentatemetodenu-merice de rezolvare - algoritmul simplex i metoda punctelor interioare.De asemenea sunt tratate modele de optimizare rezolvabile cu algoritmulsimplex, teoria jocurilor matriceale i modele speciale de optimizare liniar.Cartea cuprinde, pe lng prezentarea teoretic, un numr mare de problemerezolvate i aplicative din domeniul economic.Demonstraiileprezentate, aparent, suntlipsitedeinterespentruciti-torii nematematicieni, pentru cei interesai doar de aplicarea metodelor, nsevideniazvaloareadeadevraproprietiloriaarmaiilorprezentate.Noiunile din algebra liniar i analiza matematic necesare comprehensiuniiaspectelor tratate n carte fac obiectul Anexei 2.Carteaestedestinatstudenilordelafacultiledetiineeconomice,matematic, inginerie economic - inginerie i management, adresndu-se nacelai timp i unui grup larg de cititori dornici s se iniieze n acest domeniusau s aprofundeze instrumente tiinice de optimizare a diverselor problemecu care se confrunt n practica economic.Mulumescreferenilor, doamnei conf. dr. LianaLupa, Universitatea"Babe-Bolyai"Cluj-Napocai conf. dr. AdrianPetrescu, Universitatea"Petru Maior", Trgu-Mure, pentru observaiile pertinente de care am inutseama n mbuntirea calitii volumului de fa!3iiJATEK 2005/3/1110:29page4#4iiiiii4Mulumesc prietenelor mele, Luminia Chiorean, pentru sugestiile date nurma lecturrii manuscrisului, respectiv Csizmadia Erzsbet, pentru ajutorulsubstanial acordat n tehnoredactarea computerizat!Mulumescpersonalului delaTipograaMasterDruck, nspecial d-luidirectorKloszViktori d-lui Kuti Zoltn, pentruamabilitatei sprijinulacordat n editarea crii!Mai cu seam, rmn recunosctoare familiei mele, soului i celor douice, pentrucontextul moral benec: nelegereai rbdareafrdecarecartea nu ar prins contur!AutoareaiiJATEK 2005/3/1110:29page5#5iiiiiiCuprins1 Introducere 91.1 Caracteristici eseniale ale cercetrii opera-ionale. . . . . . . 91.2 Introducere n optimizare . . . . . . . . . . . . . . . . . . . . 141.3 Modele tip de optimizare . . . . . . . . . . . . . . . . . . . . . 152 Teoria problemelor de optimizare liniar cu restricii 212.1 Forme ale modelului de optimizare liniar cu res-tricii . . . . 232.2 Soluii ale problemei de optimizare liniar cu res-tricii . . . . 242.3 Teoria poliedrelor, inegaliti liniare i programare liniar . . 282.4 Trecerea unei probleme de programare liniar cu restricii dela o form matematic de prezentare la alta . . . . . . . . . . 332.5 Rezolvarea grac a modelelor cum restricii i dou variabile 393 Metoda simplex 473.1 Noiuni introductive . . . . . . . . . . . . . . . . . . . . . . . 473.2 Bazele teoretice ale algoritmului simplex primal . . . . . . . . 563.3 Rezolvarea modelelor care, iniial, nu admit soluii de baz . . 643.4 Degenerare i ciclare n aplicarea algoritmului simplex . . . . 754 Teoria dualitii 814.1 Introducere n dualitate . . . . . . . . . . . . . . . . . . . . . 814.2 Formularea problemei duale . . . . . . . . . . . . . . . . . . . 824.3 Interpretarea economic a dualitii . . . . . . . . . . . . . . 854.4 Teoreme de dualitate. . . . . . . . . . . . . . . . . . . . . . . 864.5 Algoritmul simplex dual . . . . . . . . . . . . . . . . . . . . . 914.6 Bazele teoretice ale algoritmului simplex dual . . . . . . . . . 954.7 Determinarea soluiilor problemei duale cu ajutorul ultimuluitabel simplex al problemei primale . . . . . . . . . . . . . . . 994.8 Legtura dintre soluiile unui cuplu dual . . . . . . . . . . . . 1045iiJATEK 2005/3/1110:29page6#6iiiiii65 Reoptimizare 1095.1 Reoptimizarea n urma modicrii termenului liber . . . . . . 1105.2 Reoptimizarea n urma modicrii coecienilor funciei de scop1145.3 Reoptimizarea n urma modicrii matricei res-triciilor . . . 1186 Tipuri speciale de probleme de optimizare 1256.1 Programare discret . . . . . . . . . . . . . . . . . . . . . . . 1256.1.1 Bazele programrii discrete . . . . . . . . . . . . . . . 1256.1.2 Metode de tip tietur. Metoda lui Gomory . . . . . 1296.1.3 Programare dinamic discret. . . . . . . . . . . . . . 1356.2 Programare liniar parametric . . . . . . . . . . . . . . . . . 1356.2.1 Parametrizarea membrului drept . . . . . . . . . . . . 1376.2.2 Parametrizarea funciei de scop. . . . . . . . . . . . . 1416.3 Programare hiperbolic . . . . . . . . . . . . . . . . . . . . . 1496.4 Programare multicriterial. . . . . . . . . . . . . . . . . . . . 1577 Problema de transport 1717.1 Formularea problemei. Proprieti generale . . . . . . . . . . 1717.1.1 Proprieti ale matricei coecienilor . . . . . . . . . . 1767.1.2 Proprieti grace ale problemei de transport . . . . . 1767.1.3 Determinarea unei soluii de baz . . . . . . . . . . . . 1797.1.4 Adaptarea algoritmului simplex. . . . . . . . . . . . . 1807.1.5 Utilizarea problemei duale. . . . . . . . . . . . . . . . 1827.1.6 Algoritmul de transport . . . . . . . . . . . . . . . . . 1837.1.7 Probleme propuse i rezolvate. . . . . . . . . . . . . . 1858 Teoria jocurilor 2118.1 Introducere n teoria jocurilor . . . . . . . . . . . . . . . . . . 2118.2 Jocuri matriceale . . . . . . . . . . . . . . . . . . . . . . . . . 2138.3 Strategii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2148.3.1 Strategii optime . . . . . . . . . . . . . . . . . . . . . 2168.3.2 Strategii optime ntr-un joc matriceal simetric . . . . . 2248.3.3 Proprieti ale strategiilor optime i ale valorii unui jocmatriceal . . . . . . . . . . . . . . . . . . . . . . . . . 2258.3.4 Strategii pure . . . . . . . . . . . . . . . . . . . . . . . 2278.4 Principiul dominrii . . . . . . . . . . . . . . . . . . . . . . . 2318.5 Rezolvarea jocurilor matriceale . . . . . . . . . . . . . . . . . 2338.5.1 Rezolvarea jocurilor matriceale cu punct a . . . . . . 2338.5.2 Metode generale de rezolvare a jocurilor matriceale . . 2378.5.3 Rezolvarea jocurilor matriceale prin reducere la modelede optimizare liniar cu restricii . . . . . . . . . . . . 2408.5.4 Rezolvarea jocurilor de tipul 2 m, (n 2) . . . . . . 249iiJATEK 2005/3/1110:29page7#7iiiiii79 Metoda punctelor interioare 2579.1 Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2579.2 Metoda Karmarkar . . . . . . . . . . . . . . . . . . . . . . . . 2609.3 Concluzii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271Anexa 1 273Anexa 2 289Anexa 3 297Bibliograe 299iiJATEK 2005/3/1110:29page8#8iiiiii8iiJATEK 2005/3/1110:29page9#9iiiiiiCapitolul 1Introducere1.1 Caracteristici eseniale ale cercetrii opera-ionaleCercetarea operaional este una dintre cele mai noi ramuri ale matema-ticii aplicate.A aprut dup 1950 i, datorit aplicabilitii largi i a utilitiisemnicative, cunoate o dezvoltare extrem de rapid. La dezvoltarea sa re-marcabil, un rol semnicativ l-au jucat revoluia industrial (prin cretereacomplexitii problemelor) i dezvoltarea spectaculoas a tehnicii de calcul.Cercetarea operaional se ocup cu determinarea deciziei optime n urmarezolvrii modelelor deterministice i stohastice construite pentrustudiulfenomenelor din cele mai diverse domenii ale vieii.Scurt istoricPrimele activiti n acest domeniu au aprut n timpul celui de-al doileaRzboi Mondial, cnd oerii forelor militare aliate au efectuat analiza ope-raiilor militareprinconstruireai rezolvareaunor modeledeoptimizareliniar[Mau]. ncdinperioada1935-1937, oameni detiini cercet-tori au fost solicitai s-i aduc contribuia n vederea elaborrii strategiilori astudiu-lui problemelor detacticmilitar. n1938, A.P. RoweesteconductorulacestuigrupnBawdsey(Anglia), locdelansareacercetriioperaionale. n anul 1942,cpitanul american W.D. Baker a creat grupulASWORG (Anti-Submarine Warfare Operations Research Group) care a de-venitmai trziuORG(Operational ResearchGroup). nfrunteaacestuigrup a fost invitat Philip M. Morse din Massachusetts i William Shockleyde la Bell Laboratories (pentru contribuia adus la tranzistoare, va obinepremiul Nobel).9iiJATEK 2005/3/1110:29page10#10iiiiii10 1. Introduceren paralel se poate observa propagarea acestor metode de lucru n diferiteramuri ale economiei. S-a constatat c i n domenii nemilitare pot formu-late probleme asemntoare, dar ntr-un alt context. Astfel, n 1941, FrankHitchcock [Hit] i, n mod independent, n 1947, T.C. Koopmans [Koo] for-muleazproblemadetransport. G. Stigler [Sti], n1945, formuleazunmodelmatematicpentrustabilireahraneiraionalepentruanimale. Prob-lemagene-raldeprogramareliniarafoststudiatiaplicatn1947deG.B. Dantzig, Marshall Wood i de asociaii lor de la Departamentul ForelorAeriene (U.S. Department of Air Force). Metoda elaborat este cunoscutsub denumirea de metoda simplex.Prima conferin de programare matematic, cunoscut ca "zero sympo-sium", are loc n 1949.naintedesfritul anilor1950, existadejaoteoriebinedezvoltataprogramrii liniare, a programrii dinamice, a teoriei relor de ateptare i ateoriei stocrii. Condiii necesare de optim n programarea neliniar au fostformulate de H.W. Kuhn i A.W. Tucker [Kuh] n 1951.Acestrezultatesteindependentdecel obinuti prezentatntezadedoctorat a lui W. Karush [Kar] n 1939.nianuarie1952afostrezolvat, pentruprimadat, pecalculator, unmodel de programare liniar (National Bureau of Standards SEAC Machine).Apare primul program comercial de programare liniar n anul 1954 (cuajutorul acestuia, o problem de amestec n domeniul petro-chimic s-a rezol-vat n 10 ore). R.E. Gomory [Gom] prezint o metod general de rezolvarea modelelor de programare n numere ntregi n anul 1958.Analiza circuitelor i a reelelor reprezenta dintotdeauna o problem im-portant n electrotehnic. Unele noiuni ale acestei teorii s-au dovedit ex-trem de utile n teoria informaiei, n cibernetic, n planicarea proiectelor decercetare i de dezoltare. Borz Allen i Hamilton dezvolt programul PERT(Program Evaluation and Review Technique) i metoda drumului critic CPM(Critical Path Method). PERT poate aplicat cu succes dac incertitudineaprivind previziunea duratei activitilor este mare i se dorete vericarea e-cace a timpului de rulare a proiectului. Proiectele de cercetare i dezvoltareintr n aceast categorie. PERT a fost folosit prima dat n Statele Uniteale Americii, n 1958, n programul de rachete balistice ale otei i a reduscu doi ani timpul prevzut pentru lansarea rachetelor Polaris.Pogramul CPM este extrem de util atunci cnd durata activitilor poate precizat (de exemplu, n urma unor experiene anterioare), aceste duratesunt exibile (pot uor modicate, de exemplu, prin schimbarea numru-lui de angajai) i se urmrete raportul dintre timpul i costurile necesarerealizrii planului. n general proiectele de construcii i de ntreinere suntde acest tip. Programele PERT i CPM sunt utile n proiectare. Aceste pro-gramenusuntperfecte, nupotaplicatefrvericareaipotezelor, altfeliiJATEK 2005/3/1110:29page11#11iiiiii1.1. Caracteristici eseniale ale cercetrii operaionale 11rezultateleobinutesunteronate. nacestsens, potconsultatelucrrile[Wei], [Ken].AV. Klee i G.J. Minty [Kle],n 1972,arat c algoritmul simplex esteunalgoritmdecomplexitateexponenial. Alteexemple, privindecienacomputaional a algoritmului, pot gsite n [Pap], [Len], [Dob].n1979, matematicianulrusL.G.Khachiyan[Kha]apublicatunalgo-ritm de complexitate polinomial pentru rezolvarea modelelor de optimizareliniar, numit"algoritmelipsoidal". Acestalgoritmaredoar importanteoretic, ind inecient n practic, dup cum arat analizele comparativefcute de McCall [McC] n 1980 i Dantzig [Dan] n 1979.N. Karmarkar, programator la AT&T Bell Laboratories, a dezvoltat al-goritmul elipsoidal ca s devin ecient i n practic. n 1984, Karmarkar[Karm] prezint un algoritm de complexitate polinomial pentru rezolvareamodelelorliniare. Aaplicatmetodapunctelorinterioarepentrurezolvareamodelelor liniare la care a adugat o analiz inovatoare. Astfel a obinut unalgoritmdecomplexitatepolinomial, ecientnpractic, mai performantdect algoritmul simplex n cazul modelelor de mari dimensiuni.Metoda lui Karmarkar a fost utilizat de ctre Comanda Militar Ame-rican a Podurilor Aeriene (Military Airlift Command) pentru a determinafrecvena zborurilor i tipul de aeronav necesar planicrii zborurilor. Mod-elul liniar obinut pentru studiul acestei probleme coninea 150 000 de vari-abilei12000derestriciiisoluias-aobinutntr-oor. Cualgoritmulsimplex o problem cu o structur asemntoare format numai din 36 000de variabile i 10 000 de restricii a fost rezolvat n 4 ore.Testele preliminare au artat c algoritmul Karmarkar este de 50 de orimai rapid dect algoritmul simplex, n cazul problemelor de mari dimensiuni.Metodapunctelor interioareafost introdusn1960dectreFiacco[Fia] i McCormick, ca apoi s e abandonat. Karmakar a readus n cen-trul ateniei aceast metod. n prezent exist sute de variante ale metodeipunctelor interioare i au fost publicate peste 2000 de articole. Pentru studiulacestei teorii se recomand [Meg], [Nes], [Roo], [Gje], [Wri].Impactul cercetrii operaionaleImpactul cercetrii operaionale asupra conducerii ntreprinderilor i a in-stituiilor este n continu cretere. Msura impactului nu poate comparatcu nici o alt descoperire.n1972, E. Turban[Tur] a publicat unsondaj privinddimensiuneaaplicrii metodelor cercetrii operaionale din anul 1969. Dintre 500 de com-panii, considerate, dup"Fortune", celemai mari, aufostalesecompaniiindustrialei companii dintoatecategoriiledeservicii (bnci, transport,asigurri, comer). Aufosttrimise475dechestionarepentrudirectorii iiiJATEK 2005/3/1110:29page12#12iiiiii12 1. Introducereconductorii de companii. S-a constatat c, dup analiza statistic i simu-lare, programarea liniar era metoda cea mai frecvent aplicat. Majoritateacompaniilor au folosit n aplicarea metodelor i tehnica de calcul.n 1977, Ledbetter i Cox [Led] au publicat un sondaj asemntor privindsituaia aplicrii metodelor cercetrii operaionale n anul 1975. Au obinutun rezultat asemntor. Aadar s-au conrmat rezultatele sondajului datede Turban.n 1976, Fabozzi i Valente [Fab] public rezultatul unui sondaj referitorla anul 1974 n care s-au analizat domeniile de aplicare a programrii liniareia programriidinamice. Cercettoriiauajuns laconcluzia c aplicaiilecelemai importanteseconcretizeazladeterminareaamestecului depro-duse, la planicarea timpului de lucru, planicarea investiiilor, planicareananciar, analiza bugetului, analiza unicrii i cumprrii companiilor.Datorit impactului semnicativ, pe plan mondial, s-au format societinaionalei internaionaledecercetareoperaional. Astfel la1ianuarie1959, cuparticipareaapeste30deri, s-acreatFederaiaInternaionalde Cer-cetare Operaional (IFORS). n anul 1952, a fost fondat SocietateaAmeri-can de Cercetri Operaionale (ORSA) (n anul 1987, pentru primadatnistoriasocietii, ocupfunciadepreedinteodoamn, JudithS.Liebman). A fostcreatInstitutuldeManagementn1953 (TIMS).ORSAscoate revista "Operations Research", iar TIMS, revista "Management Sci-ence",iar cele dou societi public revistele "Mathematics of OperationsResearch" i "Interfaces". Aceste reviste sunt generoase n informaii, pub-licnd anual, n peste 3000 de pagini, cele mai noi rezultate din domeniu. Re-viste asemntoare sunt editate i n Anglia, Frana, Italia, Japonia, Canada,Germania. n 1995, prin unicarea celor dou societi ORSA i TIMS, s-aformat Institutul de Cercetri Operaionale i de Management (INFORMS).O serie de rezultate remarcabile ale cercetrii operaionale au fost apreci-ate cu premiul Nobel n Economie. De exemplu, n 1972, Sir John R. Hicks iKenneth J. Arrow obin premiul pentru contribuiile aduse n teoria generala echilibrului economic; n anul 1973, Wassily Leontief obine premiul pentrudezvoltarea i aplicarea modelelor input-output n problemele importante aleeconomiei; n 1975, L.V. Kantorovich i T.C. Koopmans obin acest premiupentru contribuia adus la dezvoltarea teoriei alocrii optime a resurselor; n1990, H.M. Markowitz, Marton M. Miller i Wiliam F. Sharpe obin premiulpentru munca de pionieriat n teoria economiei nanciare; n 1994, John C.Harsnyi, John F. Nash i Reinhard Selten obin premiul pentru rezultateleobinute n analiza echilibrului n teoria jocurilor "necooperative".iiJATEK 2005/3/1110:29page13#13iiiiii1.1. Caracteristici eseniale ale cercetrii operaionale 13Obiectul cercetrii operaionaleCitind i analiznd literatura de specialitate, se poate observa c existo serie de deniii ale cercetrii operaionale. n continuare, prezentm sursebi-bliograce ce ofer asemenea deniii:1943, Morse i Kimball [Mor]; 1978,CharlesJ. Sippl i CharlesP. Sippl [Sip]; 1996, Hillier&Lieberman[Hil],Ronald L. Rardin; 1998, [Rar] etc.nconcluzie, sepoatespuneccercetareaoperaionalesteoramuramatematicii aplicatecareseocupcumodelareaproblemelor complexedeinginerie, management, marketing, educaie, sntate (teoretic, dinoricedomeniual activitiiumane), analizeazacestemodelecuscopul obineriisoluiilor posibile i aplic metodele analitice ale matematicii n scopul deter-minrii deciziilor (soluiilor, politicilor, strategiilor) optime.Fiindoramuramatematicii aplicate, pentrustudiul modelelorsuntnecesare cunotine de matematici superioare, cumar algebraliniar,analiza matematic, analiza funcional, teoria probabilitilor, ecuaii difer-eniale, geometrie diferenial.n continuare, prezentm cteva noiuni de baz.Deniia 1.[Bre] Prin operaie se nelege un ansamblu de aciuni ndrep-tate spre realizarea unui anumit scop. Orice operaie are un singur scop carepoate compus din mai multe obiective.Deniia2. [Bre] Se numete parteoperativ mulimea acelor persoanesau factori care acioneaz ntr-o operaie pentru ndeplinirea scopului pro-pus.Deniia3. [Bre] Prinmijloaceactivenelegemanumiteresursecarestauladispoziiapriioperative. Prinfolosirealor(deregulcheltuielilelor) partea operativ i realizeaz scopul.Deniia4. Modul de utilizare a mijloacelor active se numete strategia(sau politica) prii operative.Acelestrategii careconduclarealizareascopului senumescstrategiioptime .Observaia 1.Rezultatele unei operaii depind de strategia aleas, adic defactorii controlabili i de factori care nu pot inuenai de partea operativi care formeaz condiiile efecturii operaiei.nagricultur, deexemplu, condiiilemeteorologicereprezintfactoriinecontrolabili.n studiul oricrei operaii (indiferent de domeniul cruia i aparine), sedeosebesc patru etape fundamentale:iiJATEK 2005/3/1110:29page14#14iiiiii14 1. Introducerea) analiza operaiei - cutarea i descrierea mijloacelor de aciune carear putea duce la atingerea scopului operaiei;b)construireaunui model matematical operaiei caresofereodescriere matematic a scopului;c)estimareai comparareaecacitiidiverselorstrategiipebazamodelului construit;d)studiereastrategiilor optimei ametodelor matematicecuajutorul crora pot obinute.Pe de o parte, modelul trebuie s reecte ct mai exact procesul real, pede alt parte, trebuie s e ct mai simplu.Pentru studiul modelrii se recomand [Morr], [Wil].1.2 Introducere n optimizareExistfoartepuinenoiuni tiiniceuzualeattntiin, cti nviaa de toate zilele, precum noiunea de "optim" i derivatele acestuia.Rdcinile optimizrii se regsesc, de exemplu, n lucrrile matematicia-nului francez Jean Baptiste Joseph Fourier (1768-1830), Farkas Gyula (1847-1930), matematician maghiar, Hermann Minkowski (1864-1909), matemati-cian german. n 1762, Lagrange rezolv o problem de optimizare cu restriciisimple format din egaliti. n mod independent,Farkas i Minkowski austudiatinegalitileliniare. n1918, HaarAlfredageneralizatrezultatulobinut de Minkowski-Farkas pentru cazul neomogen.Se poate observac, ntoate domeniile vieii, existtendina"opti-mizrii" activitilor. Putem auzi de planicarea optim a produciei,alo-carea optim a resurselor, organizarea optim a circulaiei, repartizarea op-tim a sarcinilor de producie, planicarea optim a invesiiilor, organizareaoptim a timpului,organizarea optim a transportului,continundu-se ex-emplele.A avea o "activitate optim" nseamn de fapt a o alege, n condiii binestabilite, din mulimea activitilor posibile, pe cea care este cea mai bundintr-un anumit punct de vedere.Reinem c obiectul optimului nu este ntotdeauna bine denit.Considerndproblemaalegeriicandidailornurmaunuitest, obinemunobiectoptimsubiectiv, indcbaremul deevaluarestabilitpentrutestpoateinuenaierarhiacandidailor. Optimul poateales i dupmaimulte criterii, caz n care avem un optim multicriterial.Dintre problemele de optim n cadrul acestei cri vom studia doar pro-blemele pentru care:- criteriile de optim pot formulate cu funcii reale sau funcii vector den variabile reale liniare sau neliniare;iiJATEK 2005/3/1110:29page15#15iiiiii1.3. Modele tip de optimizare 15- ntrebrile decizionale sunt ntrebri cantitative (ct este valoarea vari-abileixj, j 1, . . . , n ?);- variabilele decizionale sunt soluiile unui sistem liniar de inecuaii.Acesteproblemesenumescproblemedeprogramarematematicsau optimizare matematic cu restricii.Teoria problemelor de optimizare cu restricii este o ramur a cercetriioperaionale care studiaz optimizarea uneia sau a mai multor funcii pe undomeniu denit de o mulime de restricii date asupra variabilelor indepen-dente, restricii care pot exprima diferite condiii economice.Dup natura matematic a funciei (funciilor) de scop i a restriciilorputem distinge diferite clase de probleme de optimizare cu restricii, cum ar, deexemplu: modeledeoptimizareliniar, neliniar, nnumerentregi,stohastic, parametric, multicriterial etc.Vom studia acele probleme de programare matematic care pot rezol-vate cu algoritmul simplex, modele care pot reduse la modele de optimizareliniar cu restricii.1.3 Modele tip de optimizaren acest paragraf vom prezenta cteva exemple reprezentative de progra-mare liniar.(a) Un model de planicare a producieiOntreprindere produce n produse P1, . . . , Pn, folosind mresurseR1, . . . , Rm (materii prime, maini-unelte, for de munc etc.) de care dis-pune n cantitileb1, . . . , bm.tiind c producerea unei uniti din produsul Pj, j 1, . . . , n aduce n-treprinderii beneciul cj i necesit aij uniti din resursa Ri, i 1, . . . , m,seceresseplaniceproducia, adicssestabileascncecantitisseproducecaredintrecelenproduse, astfel nctbeneciul total alntreprinderii s e maxim.Notmpentruecare j 1, . . . , ncuxjcantitatea(nuniti)dinprodusulPjce urmeaz a produs.Beneciul total al ntreprinderii este:f(x1, . . . , xn) = c1x1 + +cnxn(1.1)iar cantitilex1, . . . , xn trebuie s verice urmtorul sistem de inecuaii:___n

j=1aijxj bi, i = 1, mxj 0, j = 1, n(1.2)iiJATEK 2005/3/1110:29page16#16iiiiii16 1. IntroducereAvemmodelul careconstnmaximizareafunciei (1.1) pemulimeasoluiilor sistemului (1.2).Modelul poate reformulat dup scopul urmrit.- Dacsecereproducereaunorcantiti minimex01, . . . , x0n(respectivmaximey01, . . . , y0n), atunci adaugm restriciile:x0j xj, j = 1, n (sau xj y0j, j = 1, n)- Dac se cere ca volumul total al produciei s nu coboare sub o anumitlimitx0, atunci din punct de vedere matematic avem condiia:x0 x1 + +xn- Scopul nu este neaprat maximizarea beneciului. Scopul poate s eobinereaunui venitmaximnvalutsaurealizareaunui venitmaximdevaluti realizareaunui beneciumaxim. Dacdjestevenitul devalutdup produsulPj, atunci avem: (c1 +d1)u1 + + (cn +dn)un(b) Un model de amestecUn astfel de model este problema dietei (vezi paragraful 4.3).Dac ntr-o problem de amestec aij reprezint cantitatea de substan si,i = 1, m coninut ntr-o unitate din componentaPj,j = 1, n a amesteculuii amestecul trebuie s conin cel puinbi uniti din substanasi,i = 1, ki cel mult Bi uniti din substana si, i = k + 1, m, atunci se cere realizareaamestecului cu cost minim, tiind c costurile unitare din componentelePjsuntcj,j = 1, n.Notm cuxjnumrul de uniti din componentelePj. Putem scrie:___f(x) =n

j=1cjxj minn

j=1aijxj bi, i = 1, kn

j=1aijxj Bi, i = k + 1, mxj 0, j = 1, n(c) Problema rucsaculuiUn turist vrea s-i ia n rucsac cteva din obiecteleX1, X2, . . . , Xn. Elcunoate greutatea ecrui obiect P1, . . . , Pn i volumul corespunztor (loculocupat de un obiect) V1, . . . , Vn. Turistul nu poate duce o greutate total maiiiJATEK 2005/3/1110:29page17#17iiiiii1.3. Modele tip de optimizare 17mare dectP, iar volumul maxim al rucsacului esteV. Fiecare obiect are ovaloare subiectivk1, . . . , kn.Ce obiecte trebuie alese pentru a obine o utilitate total maxim?Notm cu xi valorile asociate obiectelor Xi. Vom avea xi = 1 dac obiec-tulXi este pus n rucsac, respectivxi = 0 n caz contrar.Modelul matematic ataat problemei este:___f(x) =n

i=1xiki maxn

i=1Pixi Pn

i=1Vixi Vxi 0, 1, i 1, nModelul obinut este un model discret, un model de programare n numerentregi.(d) Model de alocare a resurselorSse repartizeze nresurse, notate cuR1, R2, . . . , Rnpe nactivitiA1, A2, . . . , An, astfel nct:- ecare resurs s e repartizat la cte o singur activitate;- ecrei activiti s i se repartizeze cte o singur resurs.Se introduce un criteriu de alegere a "posibilitii optime". n acest scopse introduc anumite costuri ce corespund diferitelor grupe formate din cteo resurs i cte o activitate. Astfel, cuplului (Ri, Aj) format din resursa Ri,i = 1, 2, . . . , n i din activitatea Aj, j = 1, 2, . . . , n i corespunde valoarea Cijnumit costul repartizrii resursei Ri pe activitatea Aj. Pentru ecare repar-tizare a celor n resurse pe cele n activiti, n condiiile precizate mai sus, vacorespunde n acest mod un cost total, egal cu suma costurilor repartizrilordiferitelor cupluri ce formeaz repartizarea dat.Se cere repartizarea resurselor pe activiti, astfel nct costul total s eminim (maxim), n funcie de natura problemei propuse spre rezolvare.Seintroducvariabilelexij, i, j 1, 2, . . . , ndeniteastfel: xij=1,dac resursaRi este repartizat pe activitateaAjixij = 0. n caz contrar,iiJATEK 2005/3/1110:29page18#18iiiiii18 1. Introducerepstrnd aceste notaii, modelul matematic al problemei este:___f(x) =n

i=1n

j=1cijxij minn

i=1xij = 1, pentru i = 1, nn

j=1xij = 1, pentru j = 1, nxij 0, 1, pentru i = 1, n i j = 1, n(e) Problema de transportFiemcentredeaprovizionare(depozitare)notatecuA1, . . . , Ami ncentre de consum (beneciari) notate cuB1, . . . , Bn.Dacunprodus omogenestedepozitat ncantitile ai, i =1, mncentreleAii estecerutdectrebeneciari ncantitateabj, j =1, n, iarcosturile unitare de transport de la centrulAila beneciarul Bjsunt egalecucij,atunciseceresseorganizezetransportul, astfel nctcheltuieliledetransport s e minime!Dacnotmcuxijcantitateadeproduscarevatransportatdelafurnizorul i la consumatorul j,atunci,matematic,putem descrie problemacu urmtorul model:___f(x) =m

i=1n

j=1cijxij minn

j=1xij ai, i = 1, mm

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

i=1ai n

j=1bj.(1.3)Funcia obiectiv reprezint evident cheltuielile totale; prin urmare, scopulconst n minimizarea acestora.iiJATEK 2005/3/1110:29page19#19iiiiii1.3. Modele tip de optimizare 19(f ) O problem de atribuireFie m tipuri de maini, al cror timp de funcionare este respectiv egal cut1, . . . , ti, . . . , tm uniti de timp. Cu aceste maini se pot produce n tipuri deproduse, planicate ntr-un numr der1, . . . , rj, . . . , rn. Timpul ij, n caremainadetipiproduceunprodusdetipj,variaznfunciedealegereatipului de main pe care este fabricat produsul. Costurile de fabricaie potvaria i n funcie de perechile (i, j), dar nu sunt neaprat proporionale cutimpul ij. Dacsenoteazcucijcosturiledefabricaie, atunci sepuneproblemadeterminriiunuiplandeproduciepentrurealizareaproduselorn cantitile menionate, cu un cost total minim.Dac notm cu xij numrul unitilor din produsul j fabricate pe mainade tipi, atunci modelul acestei probleme va :___m

i=1n

j=1cijxij minn

j=1ijxij ti, pentru i = 1, mm

i=1xij = rj, pentru j = 1, nxij 0, pentru i = 1, m i j = 1, nSepoateobservacmodelul prezentatesteogeneralizareamodeluluipro-blemei de transport.(g) Generalizarea problemei de transportntr-o staie cum garaje suntt1, . . . , ti, . . . , tmcamioane cu aceleai ca-paciti de transport. ntr-o anumit zi se solicit f1, . . . , fk, . . . , fs camioanede ctre beneciari pentru transportarea unui produs omogen care poate ncrcat de lan depozite. La un depozit se pot ncrca, n acelai timp, unnumr der1, . . . , rj, . . . , rncamioane. Costurile de transport se modic nfuncie de drumul parcurs de camioane, adic depinde de modul de gruparea indicilor (i, j, k). Notnd cu cijk aceste costuri, se cere construirea planuluide dirijare n condiiile menionate, astfel nct costul total de transport se minim.Dac se noteaz cuxijknumrul camioanelor dirijate de la garajul i ladepozitulj i la beneciarulk, atunci modelul acestei probleme este:iiJATEK 2005/3/1110:29page20#20iiiiii20 1. Introducere___m

i=1n

j=1s

k=1cijkxijk minn

j=1s

k=1xijk = ti, i = 1, mm

i=1s

k=1xijk = rj, j = 1, nm

i=1n

j=1xijk = fk, k = 1, sxijk 0, pentru i = 1, m; j = 1, n i k = 1, s(h) Planicarea investiiilorFie o societate care dispune de o sum de S uniti monetare, sum carepoate folosit n diverse activiti notate cu 1, 2, . . . n.Dac investiia la activitatea j aduce un beneciu bju.m., atunci se ceredeterminarea unui plan de investiii cu beneciu total maxim.Dacsenoteazcuxj, j=1, nsumainvestitnactivitateaj,atuncimodelul matematic al problemei este:___f(x) =

nj=1bjxj maxn

j=1xj S, j = 1, nxj 0, j = 1, niiJATEK 2005/3/1110:29page21#21iiiiiiCapitolul 2Teoria problemelor deoptimizare liniar cu restriciiProblema general de programare liniar a fost formulat pentru primadat n anul 1939 de ctre L.V. Kantorovici ([Kan]) i a fost prezentat mpre-un cu o metod de rezolvare, numit metoda "multiplicatorilor rezolvani".Kantorovici recunoate c o serie de probleme economice pot descrise cuacelai model matematici pentruacestemodelepotelaboratemetodenumerice de rezolvare.n 1941, Frank Hitchcock ([Hit]) a formulat modelul de transport (care, deasemenea, este un model special de programare liniar). O analiz riguroasa problemeia fostefectuatdeT.C.Koopmans ([Koop]),n1949. GeorgeStigler ([Sti]), n1945, formuleazunmodel matematicpentrustabilireahranei raionale pentru animale.Toate aceste modele mpreun cu alte modele speciale din timpul celui deal doilea Rzboi Mondial arat necesitatea elaborrii unor metode ecientede rezolvare numeric ale acestora.O importan deosebit pentru programarea liniar a constituit-o metodasimplexelaborat n1947 de ctre George Dantzig[Dant]. Pentrude-scoperirea i dezvoltarea programrii liniare, n 1976, Dantzig a primit pre-miul naional al Statelor Unite ale Americii.NoiuneadedualitateafostintrodusdectreJohnvonNeumannn1947 i a fost publicat la scurt timp n lucrarea cu titlul "On maximizationproblem", Institute for Advanced Study, Princetown, New Jersey, noiembrie,1947. Neumann recunoate importana conceptului de dualitate, instrumen-tul matematic care unete teoria jocurilor cu teoria problemelor de optimizareliniar cu restricii.O teorem explicit de dualitate a fost publicat i demonstrat de ctre21iiJATEK 2005/3/1110:29page22#22iiiiii22 1. IntroducereGale, Kuhn i Tucker n 1951, capitolul 19 din [Dant].Metodasimplexnuacopernntregimeproblemalegatderezolvareanumeric a problemelor de optimizare liniar cu restricii. Aceast metodnu are o variant de complexitate polinomial.n 1979, matematicianul rus Leonid Khachiyan [Kha] public un algoritmde complexitate polinomial pentru rezolvarea modelelor liniare. Algoritmuldiferdemetodasimplex, folosindu-sedeunirdeelipsoidecareconducspresoluiaoptimamodelului. Dinpunctdevedereteoretic, rezultatuleste semnicativ, dar practic nu nlocuiete algoritmul simplex.n 1984, Narendra Karmarkar [Karm] public un alt algoritmcarefolosetesfereigeometrieproiectivpentruconstruireaunuiircarecon-verge ctre soluia optim a problemei de optimizare liniar cu restricii.Modelul matematic de programare liniar utilizat n reprezentarea unuisistemeconomicesteconstruitdintr-unansambluderelaii liniare, dintrecareunareectobiectivul urmrit, iar celelaltecuprindrestriciileeco-nomice sau tehnologice.Unde putem aplica modelul de programare liniar?Acest model acoper o clas de probleme de mare importan practic,cumsuntceledeplanicare, organizare, amestec, transporturi, investiii,reparaii i altele.O serie de probleme, care nu sunt probleme de programare liniar, pot reduse prin transformri convenabile la acest tip de model.Oaltclasdeprobleme, carenusuntliniare, potrezolvateprinin-termediul unui ir de modele liniare, ale cror soluii determin un ir careadmite un subir convergent ctre soluia optim a modelului considerat.Faptul c, ntr-unmodel de programare liniar, funciade scopesteliniar atrage dup sine dou proprieti importante. Pe de o parte, valorilevariabilelor independente din funcia de scop sunt proporionale cu valoareavariabileirespective(daccosturileunitaredeproduciereprezintxu.m.pentru un produsp xat, atunci pentrun produse vor den ori mai mare)- adic are loc proprietatea de proporionalitate.Pedealtparte, valorilecomponentelorfuncieidescopsuntindepen-dente ntre ele (dac se producn produse, atunci costurile de producie aleprodusului pinusuntinuenatedecosturiledeproduciealeprodusuluipj). Aceast proprietate este cunoscut ca proprietatea de aditivitate.Pe lng proprietile prezentate, un model liniar, care descrie unfenomeneconomic,o problem practic,trebuies verice proprietatea dedivizibilitate i certitudine.Prin proprietatea de divizibilitate se nelege c variabilele pot lua i va-lori raionale. Modelele n care variabilele pot lua doar valori ntregi vor prezentate n paragraful 6.1.iiJATEK 2005/3/1110:29page23#23iiiiii2.1. Forme ale modelului de optimizare liniar cu restricii 23Proprietatea de certitudinenseamnctoatedateledeintrare(coe-cieniifuncieidescop, elementelematriceirestriciilor, termeniiliberidinmembrul drept al restriciilor) sunt cunoscute apriori.Pentrurezolvareanumericaproblemelordeoptimizareliniarcure-stricii sunt necesare cunotine de algebr liniar (v. Anexa2).2.1 Formealemodelului deoptimizareliniarcures-triciiLamodelareaunui fenomenngeneral estefolositunnumrmaredevariabile i modelul este bine denit doar n cazul n care aceste variabile pot pozitive, negative sau chiar de semn variabil.Modelul matematic al unui fenomen este un model matematic al uneiprobleme de optimizare liniar cu restricii, dac este format dintr-unanumit numr de restricii date asupra variabilelor independente (care suntliniarei potinegaliti sauegaliti)i ofunciedescopcareestedeasemenea liniar. Problema care se pune este determinarea valorii optime afunciei de scop pe domeniul determinat de aceste restricii.Deniia 2.1.1.Forma general a problemei de optimizare liniar cu res-tricii prin deniie este:___f(x) = c1x1+c2x2+c3x3 min / maxA11x1+A12x2+A13x3 b1A21x1+A22x2+A23x3= b2A31x1+A32x2+A33x3 b3x1i 0, i = 1, l x2j 0, j = l + 1, r x3k, k = r + 1, n de semn oarecareunde:A =__A11A12A13A21A22A23A31A32A33__ /m,n(R),f: RnRx = (x1, x2, . . . , xl, xl+1, . . . , xr, xr+1, . . . , xn)not=(x1x2x3) Rnx1= (x1, . . . , xl); x2= (xl+1, . . . , xr); x3= (xr+1, . . . , xn)b1= (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) Rn.iiJATEK 2005/3/1110:29page24#24iiiiii24 2. Teoria problemelor de optimizare liniar cu restriciiDeniia2.1.2. Senumeteformastandardaproblemei deoptimizareliniar cu restricii urmtorul model:___f(x) =n

j=1cjxj min /maxn

j=1aijxj = bi, i = 1, mxj 0, j = 1, nsau n forma matriceal:___f(x) = (c, x) min/maxAx = bx 0,unde(, ): Rn RnResteprodusul scalareuclideanal vectorilordinspaiul vectorial Rn,A /m,n(R),b Rm,c Rn.Deniia 2.1.3. Forma canonica unui model de minimizare prindeniie este:___f(x) = (c, x) minAx bx 0undeA /m,n(R),b Rm,c Rn.Formacanonic a problemei de maximizare este:___f(x) = (c, x) maxAx bx 0undeA /m,n(R),b Rm,c Rn.2.2 Soluii aleproblemei deoptimizareliniarcures-triciinacestparagrafvomprecizacondiiilenecesarepentrurezolvareanu-mericaproblemei deoptimizareliniarcurestricii i vomdeni ctevatipuri de soluii care pot asociate problemei propuse spre rezolvare.iiJATEK 2005/3/1110:29page25#25iiiiii2.2. Soluii ale problemei de optimizare liniar cu restricii 25A. Cazul formei standardFie modelul:___f(x) = (c, x) min/maxAx = bx 0(2.1)undeA /m,n(R),b Rm,c Rn,f: RnR.Vom presupune c sistemul de restricii Ax =b are cel puin o soluie.n caz contrar, problema de optimizare considerat nu are sens.Pe tot parcursul expunerii vom presupune c rang A = m.Dac rang A 0,atunci formeaz mulimea:B+ = i B : di> 0.5. Pentru ecarei B+ s se verice semnul numerelorij, j B.Se pot ivi dou situaii:a) Dac existi B+ astfel nct pentru oricej B, ij 0,atunci funcia de scop a problemei este nemrginit inferior pemulimeasoluiilorposibilei problemanuadmitesoluie(seobineoptim innit).iiJATEK 2005/3/1110:29page50#50iiiiii50 3. Metoda simplexAltfel:b)dacpentruoricei B+existcel puinunj Bastfel nctij> 0 atunci se va trece la pasul urmtor6. s se determine un indiceh B+,7. s se determine un indicek B astfel nct:0khk= min_0jhj, j B, hj> 0_.8. S se nlocuiasc n bazaBvectorul AkcuAhi cu noua baz astfelobinut se va trece la pasul (2) din algoritm.Bazele se modic pn cnd se va ajunge la unul din criteriile de opriredate n algoritm.Pentru aplicarea algoritmului sentocmesctabele,numite tabelesim-plex primal.ntocmirea tabelelor simplex primalSevapresupunecs-adeterminatobazprimaladmisibilB,pentrupro-blema de optimizare liniar considerat.Se va construi tabelul de mai jos:2

1 2 3

3 6 7 8 4 5 9 10 Sectoarele indicate n tabel se vor completa dup urmtoarea regul:- n sectorul 1 se va trece numrul de ordine al tabelului simplex;- n sectorul 2 se vor trece componentele bazeiB (m coloane)Aj,j B;- n sectorul 3 se vor trece puncteleAi, i B;- n sectorul 4 vor scrise numerele0j, j B;- nsectorul5 se va trece numrul d0, valoarea funcieide scoppentrusoluia posibilxB;- n sectorul 6 vor scrise numereleij, j B;iiJATEK 2005/3/1110:29page51#51iiiiii3.1. Noiuni de baz 51- n sectorul 7 se trec, pentru ecarei B, numereledi.Folosirea sectoarelor 8 i 9 este opional, pot trecute nite valori carenueraumenionatenalgoritm, nscarepotfolositepentruvericareacorectitudinii calculelor:- n sectorul 8 vor scrise numerele notate cupi, i B :pi = 1

jB ij di;- n sectorul 9 va scris numrulp0 = 1

jB 0j d0.Dup completarea celor 9 sectoare se va aplica pasul 4 din algoritm, adicse va efectua testarea optimalitii soluiei posibilexB.Dac soluia bazic nu este optim i problema dat nu are optim innit(se veric n pasul 5), atunci se va alegeh, adic o linie din tabel, numitlinie pivot.Pentru reducerea numrului de iteraii se recomand s e aleas o liniepentru care:dh = maxdi : i B+(S-a constatat c, n urma alegerii n acest mod a liniei de pivot, se reducenumrul iteraiilor simplex).Cu alegerea lui h se alege de fapt vectorul care va intra n baz. Pasul(6) se numete criteriu de intrare n baz.Urmeaz completarea sectorului 10 din tabel.nsectorul 10vor trecutecturile0jhjmenionatenpasul (7) dinalgoritm. (Dachj 0, d3> 0. Trecem la urmtoarea iteraie simplex: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 - - xB= (0 0 2/3 1/3 0 3)f(xB) = 1/3.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 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 - - - iiJATEK 2005/3/1110:29page55#55iiiiii3.1. Noiuni de baz 55Soluia optim a problemei este: x0= (16 13 4 0 0 0), iar valoarea op-tim a funciei de scop este fmin = d0 = 9.2. S se determine soluia optim a problemei:___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__Se va alege bazaB = (A1, A2), baz primal admisibil.Aplicndalgoritmulsimplexprimal, sevorobineperndurmtoareletabele:1 A1A2 A32 1 2 -4A41 2 -1 -1A53 1 -2 -1 15 12 42 -68 15/2 12 xB= (15 12 0 0 0), f(x)B= 422 A3A2 A11/2 -1/2 -1 2A41/2 3/2 -2 1A53/2 -1/2 -5 5 15/2 9/2 27 -38 - - iiJATEK 2005/3/1110:29page56#56iiiiii56 3. Metoda simplexSoluia optim a problemei este:x0= (0 9/2 15/2 0 0) i fmin = 27.3.2 Bazele teoretice ale algoritmului simplex primalTeorema 3.2.1.(Criteriul de mbuntire a soluiei) Fie xBo soluiebazic nedegenerat.Dac exist cel puin un indice j = 1, n pentru care avemdj< 0 n cazul unei probleme de maxim (saudj> 0 n cazul unei problemede minim), atunci se poate determina o alt soluie de bazxB

care s deao valoare mai bun dect xBpentru funcia de scop, iar baza corespunztoaresoluiei xB

sdiferedebazacorespunztoaresoluiei xBprintr-unsingurvector.Demonstraie. Putem presupune, fr restrngerea generalitii (variabilelepot renumerotate), c:xB= (x1, . . . , xm, 0, . . . , 0)adic:B = (A1, A2, . . . , Am),pentru modelul:___f(x) = (c, x) maxAx = bx 0Daccalculmdifereneledicuformuladi=ci

jB ijcjpentruoricei B,atuncicriteriuldembuntirepentrumodeledemaximizarevaidentic cu cel folosit la modelele de minimizare.Adic, n cazul problemelor de maximizare, de asemenea, algoritmul sim-plex va continuat, dac exist cel puin uni B astfel nctdi> 0.AcumconstruimB

astfelnctnbazaBnlocuimvectorul AkcuAh(modul de alegere a vectorilor va precizat mai trziu).Presupunem cB

este o baz pentru modelul considerat.Atunci soluia asociat acestei baze o putem scrie n forma:xB

= (y1, . . . , yk1, 0, yk+1, . . . , ym, 0, . . . , 0, yh, 0, . . . , 0).I. Cercetm alegerea vectorului Akce trebuie nlocuit n bazaB, astfelnct soluiaxB

s e posibil.Adic s avem yi 0, i 1, 2, . . . , k 1, k +1, . . . , m, h, (se va vericaaceast condiie mai trziu).iiJATEK 2005/3/1110:29page57#57iiiiii3.2. Bazele teoretice ale algoritmului simplex primal 57Folosind faptul cxBixB

satisfac sistemul de restricii, scriem:___m

j=1xjAj=m

j=1j=kyjAj+yhAh= bAh=

mj=1hjAjn urma acestor egaliti avem:m

j=1xjAj=m

j=1j=kyjAj+yhm

j=1hjAjPutem scrie:m

j=1xjAj=m

j=1j=kyjAj+yhm

j=1j=khjAj+yhhkAkm

j=1xjAj=m

j=1j=k[yj +yhhj]Aj+yhhkAk(3.6)Deci n bazaB, am obinut dou descompuneri pentru vectorulb. Deoarecedescompunerea unui vector ntr-o baz este unic, rezult c trebuie s aibloc relaiile:xj = yj +yhhjpentru j 1, k 1, k + 1, . . . , mxk = yhhk(3.7)Aceste relaii dau posibilitatea calculrii componentelor soluiei xBn funciede componentele soluieixB

.Dar scopul urmrit este acela de a exprima componentele soluieixB

nfuncie de componentele soluieixB.Astfel relaiile (3.7) vor scrise n urmtoarea form:yh =xkhkyj = xj yhhj = xj xkhk hjpentruj 1, . . . , k 1, k + 1, . . . , m.(3.8)Pentruailustramodul deutilizareaformulelor(3.8), prezentmtabelulsimplex:iiJATEK 2005/3/1110:29page58#58iiiiii58 3. Metoda simplexr . . . Aj. . . Ak. . . x x. . . . . . . . . . . . . . . . . . . . . . . .Ai. . . ij. . . ik. . . dipi. . . . . .Ah. . . hj. . . hk. . . dhph. . . . . .x . . . xBj. . . xBk. . . d0p0x . . . xBj/hj. . . xBk /hkx xAvemdh> 0, astfel putem alegeAh, ca vector care intr n baz.n formula (3.8) apare elementul hk, care se gsete la intersecia coloaneivectorului Ak, care va iei din baz, cu linia vectoruluiAh, care va intra nbaz.hkse numete element pivot.Componentayh (cu notaiile folosite0h) ce urmeaz s ia locul compo-nentei xk(adic0k) se obine prin mprirea acesteia cu elementul pivot_0h =0khk_.Celelaltecomponentebazicealesoluiei xB

secalculeazprinreguladrept-unghiului dat, astfel:yk =xkhki yj =xjhk xkhjhkDar vectorulAknu a fost nc precizat.Fixarea acestui vector se va face cu condiia ca soluia xB

s e posibil.Astfel relum condiiile yj 0, i 1, . . . , k1, k+1, . . . , m, h. Pe bazarelaiilor (3.8), va trebui s avem:xkhk 0 (3.9)xj xkhk hj 0, pentru j 1, . . . , k 1, k + 1, . . . , m.(3.10)Din ipotez (xBsoluie bazic posibil) avem xk> 0 rezult pe baza inegal-itii (3.9) c elementul pivothktrebuie s e strict pozitiv.Acum considerm inegalitatea (3.10).tim cxjixksunt pozitive (xBsoluie bazic posibil).Va trebui s avem:xj xkhk hj 0.Dachj 0 atunci inegalitatea este evident.Notm mulimea indicilorj, pentru carehj> 0, cu:J = j [ hj> 0 (B+ = j [ hj> 0)iiJATEK 2005/3/1110:29page59#59iiiiii3.2. Bazele teoretice ale algoritmului simplex primal 59Putem scrie atunci:xkhkxjhj, j J,ceea ce nseamn c indicelek corespunztor vectoruluiAk, ce urmeaz a eliminat din bazaB, se poate determina cu ajutorul relaiei:xkhk= minjJ_xjhj_= min_0jhj[ hj> 0_(3.11)Pentru utilizarea relaiei (3.11) se ataeaz tabelului o linie suplimentar(sectorul 10)ncaresetrecrapoarteledintrecomponentelesoluiei xBicomponentele corespunztoare vectorului Ahce intr n baz (rapoarte ce secalculeaz numai pentru componentele strict pozitive de pe liniah).Dachj 0 atunci se bareaz locul respectiv din tabel.Dintrerapoartelepozitivedinsectorul10, pebazarelaiei(3.11), vaales cel cu valoarea minim, obinndu-se vectorul Ak, care va eliminat dinbazaB.Dac avem mai multe rapoarte minime egale, atunci poate ales oricaredintre ele. n acest caz vom obine o soluie degenerat (n urmtorul tabelsimplex, printre numerele0jvom avea zerouri).Aceast regul poart numele de criteriu de ieire din baz.II. Avem de demonstrat c soluiaxB

construit n etapa (I) a demon-straiei estentr-adevr mai bundect soluiaxB, adicarelocrelaiaf(xB

) > f(xB).Folosind relaiile (3.8), calculm diferena:f(xB

) f(xB) =____m

j=1j=kcjyj +chyh____m

j=1cjxj ==m

j=1j=kcj_xj xkhk hj_+ch xkhkm

j=1cjxj(3.12)Adunnd i scznd termenul obinut pentruj=kn prima sum de maisus, aceasta se poate scrie sub forma:m

j=1j=kcj_xj xkhkhj_=m

j=1cj_xj xkhkhj_ck_xk xkhkhk_=m

j=1cj_xj xkhkhj_0iiJATEK 2005/3/1110:29page60#60iiiiii60 3. Metoda simplexnlocuind n relaia (3.12), putem scrie:f(xB

) f(xB) =m

j=1cj_xj xkhkhj_+chxkhkm

j=1cjxj ==m

j=1cjxj m

j=1cjxkhkhj +chxkhkm

j=1cjxj == chxkhkm

j=1cjxkhkhj =xkhk__ch m

j=1cjhj__=xkhkdhEvidentctrebuiesavemdh>0, nctinegalitateacerutsaibloc(aadar alegem vectorulAh).Atunci f(xB

) f(xB)>0 f(xB

) f(xB). Oastfel dealegeresenumete criteriu de intrare n baz.Teorema 3.2.2. (Testul de optimalitate)Dac pentru o soluie bazic avem di 0 (i = 1, n) n cazul unei problemede minimizare (sau di 0, i = 1, n pentru o problem de maximizare), atuncisoluia este optim (problema are optim nit).Demonstraie. FiexBo soluie de baz.Frrestrngereageneralitii putemscrieB=(A1, . . . , Am)i xB=(x01, . . . , x0m, 0, . . . , 0), x0i 0.Considerm o soluie posibilx S oarecare,x = (x1, . . . , xn).Avnd problema de maximizare considerat mai sus, vom demonstra c:f(x) f(x0) 0.DeoarecexB, x sunt soluii posibile, rezult c veric sistemul de restricii.Avem:n

j=1xjAj=m

k=1x0kAk= b (3.13)VectoriidinAcarenuaparinlui Bpotscriicaocombinaieliniarabazei, adic:Aj=m

k=1jkAk(3.14)nlocuim n relaia (3.13) i obinem:n

j=1xj_m

k=1jkAk_=m

k=1x0kAkm

k=1__n

j=1xjjk__Ak=m

k=1x0kAkiiJATEK 2005/3/1110:29page61#61iiiiii3.2. Bazele teoretice ale algoritmului simplex primal 61Astfel s-a obinut descompunerea vectorului b n bazaB, care,ind unic,se poate scrie:n

j=1xjjk = x0k, k = 1, m (3.15)Acum revenim la ceea ce avem de demonstrat i scriem:f(x) f(x0) =n

j=1cjxj m

k=1ckx0k ==n

j=1cjxj m

k=1ck__n

j=1xjjk__==n

j=1cjxj n

j=1xj_m

k=1ckjk_==n

j=1xj_cj m

k=1ckjk_= n

j=1xjdjDeoarece dj 0 pentru orice j = 1, n rezult c f(x) f(x0) 0 i teoremaeste demonstrat.Teorema 3.2.3. (recunoaterea optimului innit)Dac exist un indiceh B cudh> 0, astfel nct toate numerelehj 0,j B, atunci problema are optim innit.Demonstraie. Avemhj 0 pentru oricej B.I. Fiehj = 0 pentru oricej B.Putem alegeh ca linie pivot, deoarecedh> 0.Dar avnd pentru oricej B,hj 0_yh =xkhkyj = xj yhhj_, rezultc din (3.7)soluia i evident funcia obiectiv devine innit.II.Dachj 0 pentru care toate numerele31 = 1 0, 35> 0.Avem astfel:3 A3A5 A12 -1 0 0A43 -1 -3 2A2-1 1 -1 2 8 2 -44 35 Soluia optim obinut estex02= (0, 0, 8, 0, 2), iarfmax = 44.Deci am obinut dou soluii optime, ceea ce nseamn c problema areoptim multiplu. Mulimea soluiilor optime este combinaia convex a solui-ilor obinute:x0= x01+ (1 )x02, pentru orice [0, 1]. Avem:x0= ______40006______+ (1 )______00802______=______408 806 + 2 2______, [0, 1]Observaie. Pentru=0sau=1avemsoluiilebazicecalculatemaisus. Pentru (0, 1) obinem i soluii optime nebazice (de exemplu, pentru = 0, 5). Deci n cazul optimului multipluS , SB.Numai n cazul soluiei optime unice avemS SB.3.3 Rezolvarea modelelor care, iniial, nu admitsoluii de bazAlgoritmulsimplexprimalpoateutilizatcusuccesnumaincazulncaremodelul deoptimizareliniarcurestricii estenformastandarddelucru.iiJATEK 2005/3/1110:29page65#65iiiiii3.3. Rezolvarea modelelor care nu admit iniial soluii de baz 65nacestecazurisoluiaasociatbazeicanoniceestesoluiedebazin-iial, deoarece dup cum s-a artat baza este primal admisibil.Dacmodelul dat sprerezolvarenuestenformastandarddelucru,atunciprimadattrebuieformulatunprocedeucucaresepoategeneraobaz primal admisibil, adic o soluie bazic iniial.n acest scop poate aplicat metoda celor dou faze sau metoda coe-cienilor de penalizare. n continuare, vom prezenta aceste metode.I. Metoda celor dou fazeCumetodacelordoufaze, nprimafazdelucru, sevadeterminaosoluie bazic iniial dup care, n faza a doua de lucru, se va rezolva modelulconsiderat cu algoritmul simplex primal.Fie urmtorul model de programare liniar cu restricii:___f(x) = (c, x) max / minAx = bx 0Presupunem c problema dat nu este n forma standard de lucru, adic nuadmite soluie de baz iniial.ncontinuare, nscopulaplicriimetodeicelordoufaze, frrestrn-gerea generalitii, vompresupunectoatecomponentelelui bsuntpozitivei nmatriceaAnuesteinclusomatriceunitatedeor-dinulm.Introducem variabile articialeui,i = 1, m cu scopul obinerii unei ma-trici unitate de ordinulm n matricea restriciilor.Dup introducerea variabilelor articiale se efectueaz:(a)rezolvareauneiproblemedeminimizareobinutenurmanlocuiriifunciei descopaproblemei datecuofuncieformatdinsumatuturorvariabilelor articiale:___g(u) =m

i=1ui minAx +ImU= bx 0, u 0(b)duprezolvareaproblemei delapunctul (a)cualgoritmul simplexprimal, trecem n faza a doua de lucru unde vom ntlni una din urmtoarelesituaii:1. Dacgmin = 0, ui = 0 pentru oricei = 1, m, i nici un vector articialnu este n baza optim, atunci se va ncepe rezolvarea problemei iniiale.iiJATEK 2005/3/1110:29page66#66iiiiii66 3. Metoda simplexSoluia obinut, n prima faz de lucru, este soluie bazic iniial pen-tru problema considerat, iar baza optim este baz primal admisibil.2. Dac gmin = 0, ui = 0, i = 1, m, dar cel puin un vector articial se an baza optim, atunci soluia problemei rezolvate este soluie optimi pentru problema iniial.Valoareafunciei descopsevaobineprincalcul direct (nlocuindsoluiaoptimnfunciadescop). Evidentnacestcaz, problemainiial are soluie optim degenerat.3. Dac gmin ,= 0, (nseamn c exist cel puin o variabil articial strictpozitiv n soluie), atunci problema considerat nu admite soluie op-tim.Probleme rezolvatePrezentm un exemplu pentru ecare caz n parte.(a) S se determine soluia optim a problemei:(a)___f(x) = 3x1 + 2x2 +x3 + 2x4 max2x1 +x2 +x3 + 2x4 = 12x1 + 2x2 +x3 + 3x4 = 14x 0Problema nu este n forma standard de lucru, deci nu se poate aplica nmod direct algoritmul simplex primal.Cumetodacelordoufazesevadeterminaosoluiebaziciniial, obaz primal admisibil.n prima faz de lucru se va rezolva modelul:___g(u) = u1 +u2 min2x1 +x2 +x3 + 2x4 +u1 = 12x1 + 2x2 +x3 + 3x4 +u2 = 14x 0, u 0Matricea restriciilor este:A1A2A3A4u1u2A =_2 1 1 2 1 01 2 1 3 0 1_Avem, pe rnd, tabelele simplex:iiJATEK 2005/3/1110:29page67#67iiiiii3.3. Rezolvarea modelelor care nu admit iniial soluii de baz 671 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 n urmtorul tabel simpex, putem reduce numrul liniilor, deoarece liniavectorului articial u2ntotdeaunaovomputeaelimina. Dacreuimsscoatem un vector articial din baz, nu vom avea interesul s-l introducemnc o dat la o alt iteraie simplex. Putem scrie: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 Dac toate difereneledi sunt negative, nseamn c am ajuns la ultimaiteraiesimplex, deoarecegmin=0, u1=u2=0, B0=(A1A4)rezultcsoluia obinutxB= (2 0 0 4) este soluie de baz iniial petru prob-lema dat.De fapt, nprimafazde lucru, se urmrete schimbareaformei dereprezentare. Din tabelul 3, dac scriem matricea restriciilor:A =_1 1/4 1/4 00 3/4 1/4 1_i vectorulb = (2 4) atunci modelul iniial se transform astfel:iiJATEK 2005/3/1110:29page68#68iiiiii68 3. Metoda simplex___f(x) = 3x1 + 2x2 +x3 + 2x4 maxx1 14x2 + 14x3 = 234x2 + 14x3 +x4 = 4x 0Acest model este n forma standard de lucru. Se va rezolva cu algoritmulsimplex primal. Se vor obine pe rnd: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/3 39/3 x0=_103, 163, 0, 0_fmax =623= d0.Sepoateobservacnuestenecesarssescriedupprimafazdelu-cru modelul transformat, ci din ultimul tabel simplex, obinut n prima fazdelucru, nurmaeliminrii liniei vectorului articial u1i aeliminrii el-ementelor din sectoarele 5,7,8 i 9 cu ajutorul funciei de scop a problemeiiniiale putem ntocmi primul tabel din faza a doua de lucru.(b) S se rezolve problema:___f(x) = 2x1 +x2 +x3 min2x1 + 3x2 + 3x3 = 12x1 +x2 + 2x3 = 8x 0Matricea restriciilor ind:iiJATEK 2005/3/1110:29page69#69iiiiii3.3. Rezolvarea modelelor care nu admit iniial soluii de baz 69A1A2A3A =_2 3 31 1 2_modelul nu este n forma standard de lucru.I. Scriem:___g(u) = 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)1 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 s-a obinut gmin = 0 x0= (0, 0, 4) B = (x3, u2)cuu2=0, deci soluiaobinutestesoluieoptimi pentruproblemainiial,iar valoarea funciei de scop se va obine prin calcul direct i va fmin = 4.iiJATEK 2005/3/1110:29page70#70iiiiii70 3. Metoda simplex(c). S se arate c problema nu admite soluie optim:Fie modelul:___f(x) = 2x1 +x2 +x3 + 2x4 min2x1 +x2 + 2x3 + 2x4 = 16x1 +x2 + 2x3 + 2x4 = 102x1 +x2 +x3 + 2x4 = 20x 0cu:A =__2 1 2 21 1 2 22 1 1 2__.I. n prima faz de lucru scriem:___g(u) = 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)1 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 iiJATEK 2005/3/1110:29page71#71iiiiii3.3. Rezolvarea modelelor care nu admit iniial soluii de baz 713 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.II. Metoda coecienilor de penalizareFie modelul:___f(x) = (c, x) min / maxAx = b , A /m,n(R)x 0 b Rm, c Rn(3.16)Presupunem c problema (3.16) nu este n forma standard de lucru, adic nmatricea A nu avem o matrice unitate de ordinul m. Fr restrngerea gene-ralitii, putem presupune c toate componentele vectoruluib sunt pozitive.Introducem variabile articiale (maximumm astfel de variabile) cu scopulobinerii unei matrici unitate de ordinulm.Aceste variabile stric vechiul echilibru al restriciilor i soluiile modelu-lui (model lrgit) astfel obinut, n general, nu corespund cu soluiile mod-elului propus spre rezolvare.Evident, pentrucaosoluieamodeluluilrgitsesoluieipentrumodeluliniial, trebuiecaneatoatevariabilelearticialesenule. DeaceeaformanulareavariabilelorarticialeprinintroducereaacestoranfunciadescopcuuncoecientM(prinadunarencazul problemelordeminimizare i prin scdere n cazul problemelor de maximizare).Coecientul depenalizareMesteconsideratcaunnumrarbitrarpo-zitiv, relativ mare fa de ceilali coecieni din model.Rolul acestor coecieni de penalizare este acela de a nu lsa funcia descop s-i ating valoarea optim pn cnd nu se anuleaz toate variabilelearticiale.Observaie.1. Dac prin aplicarea algoritmului s-a ajuns la o soluie optim a mod-eluluilrgit, frcatoatevariabilelearticialesaibvalorinulenaceast soluie, atunci modelul iniial nu admite soluie optim.iiJATEK 2005/3/1110:29page72#72iiiiii72 3. Metoda simplex2. n calculele manuale nu este necesar particularizarea valorii lui M. Peparcursul algoritmului simplex l privim ca pe un numr relativ maren raport cu celelalte valori numerice din model.3. Deoarece valorile variabilelor articiale trebuie s e nule, orice vectorarticial ieit din baz nu va mai cercetat pentru o eventual introdu-cerenbaz(deci nusecalculeazdiferenadi), iar laurmtoareaiteraie linia respectiv se va elimina din tabel.Problem rezolvat1. Fie modelul de optimizare liniar:___f(x) = 5x1 + 5x2 + 4x3 maxx1 +x2 +x3 602x1 +x2 + 3x3 90x2 + 2x3 40xj 0, j = 1, 3___f(x) = 5x1 5x2 4x3 minx1 +x2 +x3 +x4 = 602x1 +x2 + 3x3 x5 = 90x2 + 2x3 x6 = 40xj 0, j = 1, 6A =__1 1 1 1 0 02 1 3 0 1 00 1 2 0 0 1_____f(x) = 5x1 5x2 4x3 +Mu1 +Mu2 minx1 +x2 +x3 +x4 = 602x1 +x2 + 3x3 x5 +u1 = 90x2 + 2x3 x6 +u2 = 40xj 0, u1 0, u2 0A1A2A3A4A5A6u1u2A =__1 1 1 1 0 0 0 02 1 3 0 -1 0 1 00 1 2 0 0 -1 0 1__, B = (A4, u1, u2)Aplicnd algoritmul, vom obine urmtoarele tabele:iiJATEK 2005/3/1110:29page73#73iiiiii3.3. Rezolvarea modelelor care nu admit iniial soluii de baz 731 A4u1u2 A11 2 0 5 + 2M 2M 7A21 1 1 5 + 2M 2M 7A31 3 2 4 + 5M 5M 9A50 -1 0 M 2 +MA60 0 -1 M 2 +M 60 90 40 130M 130M 18960 30 20 2 A4u1A3 A11 2 0 5 + 2M 2M 7A21/2 -1/2 1/2 3 M/2 M/2 5/2u2-1/2 -3/2 1/2 2 + 5M/2 (5M + 1)/2A50 -1 0 M M + 2A61/2 3/2 -1/2 (3M + 4)/2 -5/2-3M/2* 40 30 20 80 + 30M 30M 9* 40 15 - 3 A4A1A3 u1-1/2 1/2 0 (5 + 2M)/2 M + 7/2A23/4 -1/4 1/2 17/4 -17/4A51/2 -1/2 0 5/2 -3/2A6-1/4 3/4 -1/2 -7/4 11/4 25 15 20 -155 96 100/3 - 40 4 A2A1A3 A44/3 1/3 -2/3 -17/3 17/3A52/3 -1/3 -1/3 -1/3 4/3A61/3 2/3 -1/3 -1/3 4/3 100/3 70/3 10/3 -890/3 713/3 Soluia optim este: x0=_703, 1003, 103_ ifmax = d0 =8903.Observaie. n urma aplicrii metodei se poate ntmpla ca:iiJATEK 2005/3/1110:29page74#74iiiiii74 3. Metoda simplex1. variabila articial s e eliminat din tabelul simplex, obinnd astfelo soluie de pornire pentru problema iniial i se va continua algoritmulsimplex primal;2. variabilele articiale rmn n soluia nal, dar cu valoarea zero, ceeacenseamncproblemainiialadmitesoluie(nudepindedevari-abilele articiale);3. variabilele articiale rmnnsoluia nal, i cel puinuna estenenul; cazncareproblemainiialnuadmitesoluie(sistemul derestriciiAx = b poate compatibil, dar nu admite soluie de baz).2. S se rezolve problema:___f(x) = x1 + 2x2 + 2x3 +x4 minx1 + 2x2 + 2x3 +x4 = 102x1 +x2 + 2x3 + 2x4 = 12x1 + 2x2 + 2x3 + 2x4 = 16xj 0, j = 1, 4A =__1 2 2 12 1 2 21 2 2 2__Introducemvariabilearticiale, deoareceproblemaconsideratnuestenforma standard de lucru:___f(x) = x1 + 2x2 + 2x3 +x4 +Mu1 +Mu2 +Mu3 minx1 + 2x2 + 2x3 +x4 +u1 = 102x1 +x2 + 2x3 + 2x4 +u2 = 12x1 + 2x2 + 2x3 + 2x4 +u3 = 16xj 0, j = 1, 4, ui 0,i = 1, 3Aplicm metoda coecienilor de penalizare, pornind cu baza B =(u1, u2, u3) primal admisibil.Efectund calculele, se obin tabelele:1 u1u2u3 A11 2 1 4M 1 4M 2A22 1 2 5M 2 5M 2A32 2 2 6M 2 6M 3A41 2 2 5M 1 5M 3 10 12 16 38M 38M 37 5 6 8 iiJATEK 2005/3/1110:29page75#75iiiiii3.4. Degenerare i ciclare n aplicarea algoritmului simplex 752 A3u2u3 A11/2 1 0 M M 1/2A21 -1 0 M M + 1u11/2 -1 -1 3M + 1 3M + 3/2A41/2 1 1 2M 2M 3/2 5 2 6 8M + 10 8M 22 10 2 6 3 A3A4u3 A10 1 -1 M M + 1A23/2 -1 1 M M 1/2u2-1/2 1 -1 2M 2M + 3/2 4 2 4 4M + 10 4M 19 8/3 4 4 A2A4u3 A10 1 -1 M M + 1A32/3 2/3 -2/3 2M/3 1/3 + 2M/3 8/3 14/3 4/3 4M/3 + 10 (4M + 53)/3 Deoarece din ultimul tabel simplex primal avem x2 =83x4 =143u3 =43rezult c problema considerat nu admite soluie optim.3.4 Degenerarei ciclarenaplicareaalgoritmuluisimplexnurmaaplicrii algoritmului simplexprimal nuntotdeaunaobinemsoluiaoptim, dei modelul admiteoptimnit, deoarecenunelecazuriapare fenomenul de ciclare.Acest fenomen poate s apar din mai multe motive, cum ar de exemplu:1. dac soluia bazic este degenerat, adic numrul componentelorstrictpozitiveestemai micdectdimensiuneabazei (avem0j=0pentruj B);2. dac n sectorul 10 avem mai multe rapoarte minime egale;iiJATEK 2005/3/1110:29page76#76iiiiii76 3. Metoda simplex3. dacpornimalgoritmul cuosoluiebazicdegenerat(adicexisti = 1, m pentru carebi = 0).Deoarece numrul soluiilor bazice este cel multCmn(m 0 astfel nct soluia bazicxB() = B1b()iiJATEK 2005/3/1110:29page78#78iiiiii78 3. Metoda simplexa problemei obinute dup introducerea lui, corespunztor luiB s e nede-generat pentru orice (0, 0).Demonstraie. [Chr], [Gas]Pe baza teoremei, avem de rezolvat problema:___f(x) =34x4 20x5 + 12x6 6x7 maxx1 + 14x4 8x5 x6 + 9x7 = x2 + 12x4 12x5 12x6 + 3x7 = x3 +x6 = 1x 0b = (, , 1). Aplicnd algoritmul simplex se va obine soluia optim:x0=_34, 0, 0, 1, 0, 1, 0_iar valoarea funciei de scop va fmax = 5/4.Observaie. Sepoatedemonstracnumrul minimdeiteraii, nurmacruia apare fenomenul de ciclare, este 6 [Yud].Degenerarea nu cauzeaz ntotdeauna fenomenul de ciclare.Fie de exemplu urmtorul model:___f(x) = 2x1 x2 +x3 + 10x4 x5 maxx1 + 2x4 x5 = 0x2 +x4 2x5 = 0x3 +x4 +x5 = 12x 0Aplicnd algoritmul simplex primal (se poate observa uor c problemaeste n forma standard de lucru), dup 2 iteraii se va obine soluia optimx0= (0, 12, 0, 4, 8)i valoarea optim a funciei de scopfmax = 20.Marshall i Suurballe [Mars] arat c fenomenul de ciclare poate s aparn cazul n care modelul admite cel puin dou restricii, cel puin ase vari-abile i cel puin trei variabile nebazice.n continuare,prezentm dou exemple construite de Marshall i Suur-balle pentru fenomenul de ciclare.iiJATEK 2005/3/1110:29page79#79iiiiii3.4. Degenerare i ciclare n aplicarea algoritmului simplex 79___f(x) = 2x2 + 4x4 + 4x6 minx1 3x2 x3 x4 x5 + 6x6 = 02x2 +x3 3x4 x5 + 2x6 = 0x 0___f(x) = 25x5 25x6 + 95x7 minx1 + 35x5 325x6 + 245x7 = 0x2 + 15x5 95x6 + 35x7 = 0x3 + 25x5 85x6 + 15x7 = 0x4 +x6 = 1x 0Ssearatec, laurmtorul exempludatdeH.W.Kuhni publicatn[Bal], dup ase iteraii, apare fenomenul de ciclare.___f(x) = 2x4 3x5 +x6 + 12x7 min2x4 9x5 +x6 + 9x7 = 0x2 + 13x4 +x5 13x6 2x7 = 0x3 + 2x4 + 3x5 x6 12x7 = 2x 0iiJATEK 2005/3/1110:29page80#80iiiiii80 3. Metoda simplexiiJATEK 2005/3/1110:29page81#81iiiiiiCapitolul 4Teoria dualitii4.1 Introducere n dualitateDualitatea ocup un loc important n programarea liniar, att din punctde vedere teoretic, ct i din punct de vedere practic.Teoria dualitii const n construirea pentru problema dat:(P) f(x) : x S mina unei probleme duale:(D) f(y) : y S maxi nindicareaunorcondiii ncareproblemele(P)i (D)auurmtoareleproprieti:1. pentru ecarex S i ecarey S avemf(y) f(x);2. dac (P) admite soluie optim, atunci rezult c i (D) admite soluieoptim, iar valorile optime sunt egale;3. dac (D) admite soluie optim, atunci rezult c i (P) admite soluieoptim, iar valorile optime sunt egale;4. dacx0 S este soluie optim a problemei (P) i y0 S este soluieoptim pentru problema (D), atuncif(x0) = f(y0);5. dacunadinproblemeareoptiminnit, atunci cealaltnuadmitesoluie posibil (adic optim) i reciproc.81iiJATEK 2005/3/1110:29page82#82iiiiii82 4. Teoria dualitii4.2 Formularea problemei dualeFie urmtoarea problem de programare liniar n forma general:___f(x) = c1x1+c2x2+c3x3 minA11x1+A12x2+A13x3 b1A21x1+A22x2+A23x3= b2A31x1+A32x2+A33x3 b3x1 0, x2 0, x3de semn oarecare(4.1)Deniia4.2.1. Fiinddatproblema(4.1), senumetedualasaprob-lema:___g(y) = b1y1+b2y2+b3y3 maxAT11y1+AT21y2+AT31y3 c1AT12y1+AT22y2+AT32y3 c2AT13y1+AT23y2+AT33y3= c3y1 0, y2de semn oarecare y3 0.(4.2)Modelul (4.1)senumeteproblemprimali sevanotacu(P), iarmodelul (4.2) se numete problem dual i se va nota cu (D).Deci pentru ecare caz n parte avem urmtoarele modele:(P)___f(x) = c1x1+c2x2+c3x3 maxA11x1+A12x2+A13x3 b1A21x1+A22x2+A23x3= b2A31x1+A32x2+A33x3 b3x1 0, x2 0, x3de semn oarecare(D)___g(y) = b1y1+b2y2+b3y3 minAT11y1+AT21y2+AT31y3 c1AT21y1+AT22y2+AT23y3 c2AT31y1+AT32y2+AT33y3= c3y

0, y2de semn oarecarey3 0iiJATEK 2005/3/1110:29page83#83iiiiii4.2. Formularea problemei duale 83(P)___f(x) = c1x1+c2x2+c3x3 minA11x1+A12x2+A13x3 b1A21x1+A22x2+A23x3= b2A31x1+A32x2+A33x3 b3x1 0, x2 0, x3de semn oarecare(D)___g(y) = y1b1+y2b2+y3b3 maxAT11y1+AT21y2+AT31y3 c1AT21y1+AT22y2+AT23y3 c2AT31y1+AT32y2+AT33y3= c3y1 0, y2de semn oarecare, y3 0Observaia 4.2.1.Se observ c duala problemei duale este chiar problemaprimal. Din acest motiv vom spune c problemele (4.1) - (4.2) (respectiv(P)-(D)) formeaz un cuplu de probleme duale.Analiznd cuplurile de probleme duale date, putem formula urmtoarelelegturi dintre elementele cuplului:a) forma funciei obiectiv din (P) implic forma funciei obiectiv din dual(i reciproc);b) forma restriciilor problemei primale implic semnele variabilelordualei (i reciproc);c) semnele variabilelor problemei primale implic forma restriciilor pro-blemei duale (i reciproc).Explicit se pot formula urmtoarele:dac n problema (P) se cere maximizare/ minimizare, atunci n duala(D) se cere minimizare / maximizare;numrul variabilelor problemei primale determin numrul de restriciiale problemei duale;numrul de restricii ale primalei d numrul de variabile ale problemeiduale;termenii liberi din (P) devin coecienii funciei de scop n (D);coecienii funciei de scop din (P) devin termenii liberi n (D);dacA este matricea coecienilor problemei (P), atunciATva ma-tricea coecienilor problemei; (D)dac (P) are restricii concordante, atunci (D) are variabile pozitive;dac(P)arerestriciineconcordanteinegaliti, atunci(D)arevari-abile negative;iiJATEK 2005/3/1110:29page84#84iiiiii84 4. Teoria dualitiidac (P) are restricii neconcordante egaliti, atunci (D) are variabilede semn oarecare;dac(P)arevariabilepozitive, atunci (D)vaavearestricii concor-dante;dac (P) are variabile negative, atunci (D) va avea restricii neconcor-dante inegaliti;dac (P) are variabile de semn oarecare,atunci (D) va avea restriciineconcordante egaliti.Deniia4.2.2. Orestriciedeforma , respectiv ncazul unei prob-lemedemaximizare/minimizaresenumeterestricieconcordant. Orestriciedeforma , respectiv ncazul unei problemedemaximizare/minimizare se numete restricieneconcordant de tip inegalitate.Se poate observa c restricia concordant este identic cu tipul restrici-ilor din forma canonic a problemei primale.Se pot demonstra urmtoarele teoreme:Teorema 4.2.2. Dac:(P)___f(x) = (c, x) maxAx bx 0atunci:(D)___g(y) = (b, y) minATy cy 0Teorema 4.2.3. Dac:(P)___f(x) = (c, x) minAx bx 0atunci:(D)___g(y) = (b, y) maxATy cy 0Cuplul de probleme duale, remarcabil prin simetria sa (ambele problemesunt n form canonic), se numete cuplu dual simetric:(P) x Rn[ Ax b, x 0 min(D) u Rm[ ATu c, u 0 maxiiJATEK 2005/3/1110:29page85#85iiiiii4.3. Interpretarea economic a dualitii 85Unmotival denirii problemelordualeestei acelaal posibilitii desoluionare mai rapid a unuia din elementele cuplului primal - dual.Interesul se concentreaz asupra modului n care gsim soluia celuilaltelement al cuplului.Se poate vedea c dualitatea se poate deni n mod echivalent utilizndoricare dintre cuplurile de probleme duale.Aceasta nseamn c putem studia proprietile de dualitate pe oricaredintrecupluriledeproblemeduale, frarestrngeprinaceastagenerali-tatea.4.3 Interpretarea economic a dualitiin continuare prezentm o problem aplicativ.Seurmretestabilireahranei raionalepentruanimale, hrancaresconin n mod obligatoriu patru elemente nutritive, A, B, C i D. Se producdou nutreuri M i N care conin aceste elemente. Un kilogram din nutreulMconine 100 grame din elementul A, 100 grame din C i 200 grame din D.1 kg din nutreulNconine 100 grame din elementulB, 200 grame dinelementulCi 100 grame dinD.Un animal trebuie s consume pe zi cel puin 0,4 kg din A; 0,6 kg din B;2 kg dinCi 1,7 kg dinD.NutreulMcost 10 u.m./kg, iar nutreulNcost 4 u.m./kg.Ce cantiti de nutreuri M i N trebuie folosite pe zi i pe cap de animalpentru a obine hrana cea mai ieftin?Dac notm cantitile prescrise cu x1, x2, atunci putem formula matem-atic scopul i restriciile problemei propuse spre rezolvare.Avem:___f(x) = 10x1 + 4x2 min0, 1x1 0, 40, 1x2 0, 60, 1x1 + 0, 2x2 20, 2x1 + 0, 1x2 1, 7(4.3)Folosind algoritmul simplex se obine soluia optimx1 = 4, x2 = 9.Valoarea optim a funciei de scop estefmin = 76 u.m.n continuare, s studiem problema care se pune unui concurent al vnz-torului nutreurilorMiN.Acestconcurentvindei elementeleA, B, C, D. El tiecvnzrileluisunt egale cu cantitile prescrise pe zi i pe cap de animal i dorete s aecu ce pre unitar trebuie s vnd elementele pentru ca beneciul lui s emaxim.iiJATEK 2005/3/1110:29page86#86iiiiii86 4. Teoria dualitiiCuacesteconsiderente, putemformulaurmtoareaproblemdeopti-mizare:- beneciul poate descris matematic cu funcia:g(y) = 0, 4y1 + 0, 6y2 + 2y3 + 1, 7y4 max- pentru formularea restriciilor, lum n considerare faptul c vnztorul nuvinde cu preuri mai ridicate dect cele ale concurentului su.Astfel putem scrie:0, 1y1 + 0, 1y3 + 0, 2y4 100, 1y2 + 0, 2y3 + 0, 1y4 4y1, y2, y3, y4 0(4.4)Cu metodele prezentate n paragrafele anterioare soluia problemei este:y1 = 20, y2 = 0, y3 = 0, y4 = 40 fmax = 76Observaie. Problemei (4.3) i corespunde problema (4.4) n care datele aufost inversate. De aceast inversare este legat o proprietate foarte impor-tant, i anume:max g(y) = min f(x) = 76.Proprietatea, dup cum se va arta n continuare, este general.4.4 Teoreme de dualitateTeoreme ale dualitii sunt acelea care arat c, ntre elementele cuplu-lui dual, nu exist doar o legtur formal, ci i o puternic interdependena soluiilor acestora.Fie problema de optimizare liniar cu restricii i duala sa:(P)___f(x) =n

j=1cjxj minn

j=1aijxj bi, i = 1, mxj 0 j = 1, n(4.5)(D)___g(v) =m

i=1bivi maxm

i=1ajivi cj, j = 1, nvi 0 i = 1, m(4.6)iiJATEK 2005/3/1110:29page87#87iiiiii4.4. Teoreme de dualitate 87Scriind matriceal avem:(P)___f(x) = (x, c) minAx bx 0(D)___g(v) = (v, b) maxATv cv 0Vom arta c problemele sunt legate prin proprietatea max g = minf.Astfel cutareaoptimului unei problemepoatenlocuitcucutareaoptimului problemei duale.Dualitatea este o noiune important att din punctul de vedere al con-cepteloreconomice, ctidincelalmetodelordecalcul(deobicei, dualulare o semnicaie economic articial).Pentru studiul dualitii problemelor de optimizare liniar cu restricii iformularea teoremelor de dualitate considerm cuplul de probleme (P) - (D)de mai sus.Notm cu:S = x Rn: Ax = b, x 0mulimea soluiilor admisibile problemei (P) iS = v Rm: ATv cmulimea soluiilor admisibile problemei (D).Teorema4.4.1. Pentru oricex Si oricev Sare loc: (v, b) (x, c)(adicvaloareafunciei descopadualei nudepetevaloareafunciei descop a primalei).Demonstraie.x S Ax = b, x 0v S ATv c(v, b) = (v, Ax) = (ATv, x) =n

j=1_m

i=1bijvi_xj

cjxj = (x, c),deoarecexj 0, j B.Teorema 4.4.2. Dacx0 S, v0 Sastfel nct (x0, c) = (v0, b)atunci sunt adevrate armaiile:(i)x0este soluie optim pentru (P);(ii)v0este soluie optim pentru (D).iiJATEK 2005/3/1110:29page88#88iiiiii88 4. Teoria dualitiiDemonstraie.(i) pentru oricex S din teorema 4.4.1 (x, c) (v0, b)ip= (x0, c);(ii) pentru oricev S din teorema 4.4.1 (v, b) (x0, c)ip= (v0, b)Pentruprimadatconceptul dedualitateaproblemelordeoptimizarecu restricii a fost pus n eviden pentru probleme de optimizare liniar cures-tricii.n1961, P. Wolfeextindeteoriadualitii problemelor deoptimizareliniar la o clas mai general de probleme de optimizare (pentru problemedeoptimizarecurestricii cufuncii descopdifereniabilei curestriciidifereniabile.)n continuare, prezentm particularizarea acestor rezultate pentru modeleliniare cu restricii, iar demonstraia acestora ntr-un cadru general poate consultat n [Bre].Fie cuplul dual:(P)___f(x) = (x, c) minAx bx 0i (D)___f(v) = (v, b) maxATv cv de semn oarecareS iS este mulimea soluiilor posibile ale modelelor considerate.Teorema 4.4.3. (Teorema de dualitate)Dac una dintre problemele (P) sau (D) are soluie, atunci i cealalt areo soluie i valorile optime ale funciilor de scop sunt egale.Teoremadedualitatesedatoreazlui Neumann(1947)i Gale, Kuhn,Tucker (1951) i este o consecin a teoremei fundamentale a inegalitilorliniare (Farkas).Teorema 4.4.4.DacS ,= , atunci urmtoarele armaii sunt echivalente:1. problema (P) are o soluie;2. mulimeaS ,= ;3. funciafeste mrginit inferior peS.Teorema 4.4.5. Dac S ,= , atunci urmtoarele armaii sunt echivalente:(i) problema (D) are o soluie;(ii) mulimeaS ,= ;(iii) funciafeste mrginit superior peS.Urmtoarea teorem, cunoscut ca teorema ecarturilor comple-mentare, formuleazuncriteriupentrucadousoluii posibile x0Siv0 S s e soluii optime ale problemelor duale (P) i (D).iiJATEK 2005/3/1110:29page89#89iiiiii4.4. Teoreme de dualitate 89Teorema4.4.6. Fiex0Si v0S. Pentrucax0seosoluieaproblemei (P) iv0a problemei duale (D) este necesar i sucient ca:(v0, Ax0b) = 0 i (c ATv0, x0) = 0Demonstraie. "Necesitatea"Presupunem cx0este soluia problemei (P)iv0este soluia problemei(D), atunci rezult cf(x0) = f(v0) f(x0) f(v0) = 0.Avem:0 = (x0, c) (v0, b) = (x0, c) (v0, b) + (v0, Ax0) (v0, Ax0) = (x0, c) (ATv0, x0) + (v0, Ax0) (v0, b) == (x0, c ATv0) + (v0, Ax0b)deoarece (x0, ATv0) = (ATv0, x0).Astfel am obinut:(x0, c ATv0) + (v0, Ax0b) = 0 (4.7)Dar:x0 Sv0 S_(v0, Ax0b) 0(c ATv0, x0) 0(4.8)Din relaiile (4.7) i (4.8) rezult c:(x0, c ATv0) = 0 i (v0, Ax0b) = 0"Suciena"Presupunem c au loc relaiile:(v0, Ax0b) = 0 i (c ATv0, x0) = 0Putem scrie:0 = (v0, Ax0b) + (c ATv0, x0) = (v0, Ax0) (v0, b) + (c, x0) (ATv0, x0) = (c, x0) (v0, b)Deci: (c, x0) =(v0, b)dar x0Si v0Srezultcx0estesoluiaproblemei (P),v0este soluia optim al problemei (D).Fie cuplul dual:(P)___f(x) = (c, x) minAx = bx 0(D)___g(v) = (b, v) maxATv cv de semn oarecareiiJATEK 2005/3/1110:29page90#90iiiiii90 4. Teoria dualitiiDeniia 4.4.1. O bazBa problemei (P) se numete baz dual admis-ibil, dacdi 0 pentru oricarei B.Denumirea de baz dual admisibil provine de la proprietatea exprimatprin urmtoarea teorem.Teorema 4.4.7.Dac B este o baz dual admisibil a problemei (P), atuncisoluiavBa sistemului de ecuaii denit n Rmprin:(Aj, v) = cj, j Beste o soluie posibil a problemei duale.Demonstraie. tiind c pentru oricei BavemAi= jB ijAji bazaB este dual admisibil (B = A1. . . Am), putem scrie:0 di=

jBijcj ci =

jBij(Aj, v) ci == (

jBijAj, v) ci = (Ai, v) ci. (4.9)Deci pentru oricei B avem (Ai, v) ci 0.A rmas de artat c: AT v c.Dinrelaiaobinuti folosindproprietateacvsatisfacesistemul deecuaii, putem scrie:AT v = ((A1, v), (A2, v), . . . , (An, v)) cObservaie. ngeneral soluiabazicxBasociatunei bazedual admisi-bileBa problemei (P) nu este o soluie posibil a problemei (P) (deoarececoordonatele pot strict negative).Deci o baz dual admisibil nu este ntotdeauna i o baz primal admis-ibil.Teorema4.4.8. Fie Bobazaproblemei (P) careesteprimal i dualadmisi-bil. Urmtoarele armaii sunt adevrate:(a)xBeste soluia optim a problemei (P);(b)vBeste soluia optim a problemei (D);(c) (xB, c) = d0 = (vB, b).Demonstraie.B este o baz primal admisibil pentru problema (P) xB S.B este o baz dual admisibil pentru problema (D) vB S.iiJATEK 2005/3/1110:29page91#91iiiiii4.5. Algoritmul simplex dual 91Trebuie demonstrat c (vB, b) = (xB, c) i atunci pe baza teoremei 4.4.2xBva soluie optim pentru (P), iarvBsoluie optim pentru (D):xB S (xB, c) =

jB0jcjnot=d0vBSrezultcestesoluiasistemuluideecuaii(Aj, vB)=cj, j B.Avem astfel:(vB, b) = (vB,

jB0jAj) =

jB0j(vB, Aj) =

jB0jcj = d0.Deci am obinut:(xB, c) = d0 = (vB, b)Pe baza teoremei de dualitate 4.4.2 rezult c xBeste soluie optim pentru(P),vBsoluie optim pentru (D).Deniia4.4.2. DacBesteobazprimal i dual admisibil, atunci senumete baz optim.4.5 Algoritmul simplex dualFie urmtorul model de minimizare cu restricii:___f(x) = (c, x) minAx = bx 0(4.10)A /m,n(R), b Rm, c Rn,f: RnR.Folosind proprietatea de dualitate, se poate formula un algoritm pentrurezolvarea modelelor liniare cu restricii, numit algoritmul simplex dual.n continuare, prezentm etapele algoritmului.1. s se determine o bazB dual admisibil a problemei (4.10);2. ssecalculezenumerele0jinumereleijfolosindrelaiile(3.2) i(3.3);3. s se calculeze numruld0 i pentru oricei B s se determine difer-eneledi folosind relaiile (3.4) i (3.5);4. s se studieze semnul numerelor0j, j B.Se pot ivi dou situaii:iiJATEK 2005/3/1110:29page92#92iiiiii92 4. Teoria dualitii(a) dac pentru oricej B, 0j 0, atunci s se specice c punctulxB=x0=(x01, . . . , x0n) Rn, x0j=_0j, j B0 , j Besteosoluieoptim a problemei (4.10),d0 este valoarea minim a funciei de scop;altfelb) dacexistcel puinunj B, 0j 0, atunci cu algoritmulsimplex primal se va determina soluia optim al problemei (5.6).Observaie. Formulnd duala problemelor considerate, putem scrie:(D1)___g(y) = (v, b) max / minATy cy de semn oarecare(D2)___g(y) = (y, b) max / minATy c

y de semn oarecareunde vectorul c

= c +c, adic (D2,) se obine din (D1) n urma modicriitermenilor liberi. Astfel se poate aplica n scopul determinrii soluiei optimeproblemei (D2) reoptimizarea n urma modicrii termenilor liberi prezentatn paragraful anterior.iiJATEK 2005/3/1110:29page116#116iiiiii116 5. Reoptimizarea soluiilor unei probleme de programare liniarProblem rezolvatFie urmtorul model de programare liniar:___f(x) = 2x1 + 3x2 maxx1 + 2x2 83x1 + 2x2 12x R2+Forma standard a problemei este:___f(x) = 2x1 3x2 minx1 + 2x2 +x3 = 83x1 + 2x2 +x4 = 12x R4+de unde scriem matricea restriciilor:A1A2A3A4A =_1 2 1 03 2 0 1_.Problema se rezolv cu algoritmul simplex primal, obinnd pe rnd urm-toarele tabele simplex:1. A3A4 A11 3 2 -5A22 2 3 -6 8 12 0 -19 4 6 2. A2A4 A11/2 2 1/2 -2A31/2 -1 -3/2 3 4 4 -12 5 8 2 3. A2A1 A4-1 /4 1/2 -1/4 1A33/4 -1/2 -5/4 2 3 2 -13 9 iiJATEK 2005/3/1110:29page117#117iiiiii5.2. Reoptimizarea n urma modicrii funciei de scop 117x0=(2 3)estesoluiaoptimaproblemei. Variabileleecartsunt: x3=x4 = 0. Valoarea optim a funciei de scop estefmax = (13) = 13.n continuare, se consider un model liniar obinut din modelul rezolvatprin modicarea discret a vectoruluic, formulat astfel:___f(x) = 3x1 +x2 maxx1 + 2x2 83x1 + 2x2 12x R2+Avem:c = (2 3) R2; c

= (3 1) R2.Forma standard a problemei considerate este:___f(x) = 3x1 x2 minx1 + 2x2 +x3 = 83x1 + 2x2 +x4 = 12x R4+Pe baza teoremei 5.2.1, putem considera sistemul de vectoriB = (A2A1),care este baz primal admisibil pentru acest model.Putem scrie:1 A2A1 A4-1/4 1/2 -5/4 2A33/4 -1/2 3/4 0 3 2 -9 5 4 - Baza nu este dual admisibil, deci continum algoritmul:2 A3A1 A4-1/3 1/3 -1 2A24/3 2/3 -1 0 4 4 -12 5 Soluiaoptimaproblemei este x0=(4 0), fmax=12, iar variabileleauxiliare suntx3 = 4,x4 = 0.iiJATEK 2005/3/1110:29page118#118iiiiii118 5. Reoptimizarea soluiilor unei probleme de programare liniar5.3 Reoptimizarea n urma modicrii matricei res-triciilorPrivind acest tip de reoptimizare, ne vom opri asupra cazului n care mod-icarea se produce n urma adugrii unei restricii la sistemul de restriciial problemei iniial rezolvate i al unei variabile.Acesttipdereoptimizareesteutilizatlarezolvareamodelelordiscrete,precum i la rezolvarea unor modele neliniare.Rezolvareaunei problemedeoptimizareliniarcurestricii subformastandardobinutprinadugareaunei restricii i auneivariabile pozitiveFie modelele liniare:(1)___f(x) =n

j=1xjcj minn

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

j=1xjcj minn

j=1aijxj = bii = 1, mn

j=1am+1jxj +xn+1 = bm+1xj 0, j = 1, n + 1undecj, aij, bi R.Problema (2)se obine din problema (1) prin adugarea unei restricii ia unei variabile.Astfel avem o problem de programare liniar n Rn(problema (1)) i oproblem de programare liniar n Rn+1(problema (2)).Matricile restriciilor sunt:A1. . . AnA11An1An+11A =___a11. . . a1n...am1. . . amn___A1 =_____a11. . . a1n0...am1. . . amn0am+1,1. . . am+1,n1_____unde s-a notat cuA1, . . . , An, A11, . . . , An+11vectorii coloan ale matricilorAiA1 iarA1, . . . , An Rm, A11, . . . , An+11 Rm+1.iiJATEK 2005/3/1110:29page119#119iiiiii5.3. Reoptimizarea n urma modicrii matricei restriciilor 119Dinanalizamatricilorseobservuorcntrevectorii coloanarelocrelaia:Aj1 = (Aj, am+1,j) RmRpentru oricej = 1, n iAn+11= (m, 1) RmR.Presupunem c problema (1) admite soluie optim, notat n continuarecux0 Rn.nultimul tabel simplex, dacvomnotacu j1, . . . , jmosubmulimea mulimii 1, 2, . . . , n, atunci (Aj1, . . . , Ajm) va reprezenta baza optim aproblemei (1).Teorema5.3.1. Sistemul de vectoriB1 = (Aj11, . . . , Ajm1, An+11) este o bazdual admisibil pentru problema (2).Demonstraie. Sedemonstreazprimadatcacestsistemdevectoriestebaz pentru problema (2).n acest sens trebuie demonstrat c determinantul format din componen-tele vectorilor este diferit de zero (adic formeaz un sistem liniar indepen-dent de vectori). Dezvoltm determinantul:Aj11. . . Ajm1An+11D =a1j1. . . a1jm0.........amj1. . . amjm0am+1,j1. . . am+1,jm1dup ultima coloan, n care doar ultimul element este diferit de zero. De-terminantul de ordinulm astfel obinut:D

=a1j1. . . a1jm.........amj1amjmesteformatdincomponentelevectorilorcareformeazbazaoptim, prinurmare acest determinant va diferit de zero, ceea ce nseamn c sistemulde vectori formeaz o baz.ncontinuare, vomlucranipotezacsistemuldevecori B1estebazdual admisibil. Lademonstraie, vomreveni dupstabilireamodului decompletare a tabelului simplex dual n vederea rezolvrii problemei (2).Ultimul tabel al problemei rezolvate (1) arat astfel.iiJATEK 2005/3/1110:29page120#120iiiiii120 5. Reoptimizarea soluiilor unei probleme de programare liniarult. Aj1. . . Ajm Aiij1. . . ijmd0p0 0j1. . . 0jmdipiunde sistemul de vectori din sectorul 2, B0 = (Aj1. . . Ajm) este baza optim.Vectorii care nu au intrat n formarea bazei sunt:Ai1 = (ij1, . . . , ijm)unde coordonateleijk, k = 1, m sunt scrise n sectorul 6 n tabel,i B.Dac analizm acest ultim tabel i sistemul de vectoriB1, se observ cacelecoloanedinmatriceaA1, caresuntcorespunztoareexactindicilori,vor reprezenta vectorii care nu intr n formarea bazeiB1.Primul tabel simplex al problemei (2) este:1. Aj11. . . Ajm1An+11 Ai1

ij1. . .

ijm

i,n+1d

ip

i

0j1. . .

0jm

0,n+1d

0p

0Vectorii care nu au intrat n baz se scriu ca o combinaie liniar a bazeiB1.Ai1 =

ij1Aj11+ +

ijmAjm1+

i,n+1An+11i B1Putem scrie aceast relaie folosind legtura dintre coloanele matricilorA iA1 astfel:(Ai, am+1,i) =

ij1(Aj1, am+1,j1)++

ijm(Ajm, am+1,jm)+

i,n+1(m, 1) i B1Aceast egalitate din Rm+1este echivalent cu sistemul:_Ai=

ij1Aj1+ +

ijmAjmi Bam+1,i =

ij1am+1,j1 + +

ijmam+1,jm +

i,n+1

ij1 = ij1, . . . ,

ijm = ijmdeoarece scrierea unui vector ntr-o baz se poate realiza n mod unic.iiJATEK 2005/3/1110:29page121#121iiiiii5.3. Reoptimizarea n urma modicrii matricei restriciilor 121Astfel obinem din a doua egalitate:

i,n+1 = am+1,i m

k=1ijkam+1,jkn mod analog, putem deduce:

0j1 = 0j1, . . . ,

0jm = 0jmiar0,n+1 = x0n+1 = bm+1 m

k=10jkam+1,jkNumerele de control pot obinute din:p

i = pi in+1, i B.p

0 = p0 0n+1.Diferenele d

i i d

0 sunt egale cu cele din ultimul tabel al problemei rezolvate,deoarece variabila xn+1 are coecientul zero n funcia de scop. Astfel au locrelaiile:d

0 = d0, d

i = di i B,ceeacearatcbazaB1estebazdual admisibil. Astfel teoremaestecomplet demonstrat.Problem rezolvatSe consider urmtoarele probleme:___f(x) = x1 x2 + 2x3 +x4 minx1 +x2 +x3 = 32x1 +x2 +x4 = 4x1 0, x4 0___f(x) = x1 x2 + 2x3 +x4 minx1 +x2 +x3 = 32x1 +x2 +x4 = 43x1 2x2 + 6x4 +x5 = 1x1, . . . , x5 0Matricile restriciilor sunt:A1A2A3A4A11A21A31A41A51A =_1 1 1 02 1 0 1_A1 =__1 1 1 0 02 1 0 1 03 -2 0 6 1__Prima problem este n forma standard de lucru. Tabelele simplex primalsunt:iiJATEK 2005/3/1110:29page122#122iiiiii122 5. Reoptimizarea soluiilor unei probleme de programare liniar1 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, soluia optim a primei probleme este:x0= (0 3 0 1); fmin = 2.Acum trecem la rezolvarea celei de-a doua probleme.Folosind teorema 5.3.1, scriem baza dual admisibil pentru modelul doi:B1 = (A21A41A51)Se completeaz primul tabel simplex dual:1 A21A41A51 A111 1 -1 -1 1 1A311 -1 8 -4 -3 - 3 1 -1 -2 0 Completarea tabelului simplex dual s-a realizat cu ajutorul relaiilor date.Putem scrie:

15=a31 (1a32 + 1a34) = 3 (1(2) + 16) sauscriindvectorul, carenuintrnformareabazei, caocombinaieliniarabazei, putem calcula coordonatele necunoscute astfel:A11= 1A21 + 1A41 +A51A11= 1(1 1 2) + 1(0 1 6) +(0 0 1)(1 2 3) = (1 2 4 +) = 1.n mod analog, putem scrie:A31= 1A21 1A41 +35A51(1 0 0) = 1(1 1 2) 1(0 1 6) +35(0 0 1)35= 8b1= 3A21 + 1A41 +05A51(3 4 1) = 3(1 1 2) + 1(0 1 6) +05(0 0 1)a05= 1Dup alegerea elementului pivot, trecem la completarea urmtorului tabelsimplex dual:iiJATEK 2005/3/1110:29page123#123iiiiii5.3. Reoptimizarea n urma modicrii matricei restriciilor 1232 A21A41A11 A511 1 -1 -1 1A319 7 -8 -12 5 2 0 1 -1 -1 Soluia optim a celei de-a doua probleme este:x0= (1 2 0 0 0) fmin = 1.Observaie. Dacnufolosimreoptimizarea, atunci rezolvareacelei de-adouaproblemeestemai complicat, necesitmai multeiteraii i tabelesimplex cu dimensiuni mai mari.Analiznd matriceaA1, se poate observa c problema nu este n formastandarddelucru. Algoritmulsimplexdualnusepoateaplicanmoddi-rect. Problema poate rezolvat cu metoda celor dou faze sau cu metodacoecienilor de penalizare.Reoptimizarea poate aplicat i ntr-un alt context. Avnd o problemdat spre rezolvare, eliminnd din restricii i variabile (dac este cazul, adicvariabilele eliminate nu apar n alte restricii i n funcia de scop),putemrezolvaproblemaredus, dupcare, cureoptimizare, vomobinesoluiaoptim a problemei iniiale.Problem rezolvat:___f(x) = x2 6x3 + 2x5 minx1 + 3x2 x3 = 72x2 + 4x3 +x4 = 124x2 + 3x3 + 8x5 +x6 = 10x1 + 2x2 +x3 +x4 +x6 +x7 = 20x1, . . . , x7 0Matricea restriciilor este:A =____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). Se poate elimina ultimarestricie i variabila x7, deoarece nu apare dect n ultima restricie. Astfel,iiJATEK 2005/3/1110:29page124#124iiiiii124 5. Reoptimizarea soluiilor unei probleme de programare liniarmai nti, se va rezolva problema:___f(x) = x2 6x3 + 2x5 minx1 + 3x2 x3 = 72x2 + 4x3 +x4 = 124x2 + 3x3 + 8x5 +x6 = 10x1. . . x6 0dup care se aplic reoptimizarea:A1A2A3A4A5A6A =__1 3 -1 0 0 00 -2 4 1 0 00 -4 3 0 8 1__Problema este n forma standard de lucru i se va rezolva cu algoritmulsimplexprimal. Dupreoptimizare, obinemsoluiaoptimaproblemeiiniiale care va x0= (0 4 5 0 0 11),d0 = fmin = 26.iiJATEK 2005/3/1110:29page125#125iiiiiiCapitolul 6Tipuri speciale de probleme deoptimizaren acest capitol, prezentm modele de probleme de optimizare care pot rezolvate cu algoritmul simplex.6.1 Programare discret6.1.1 Bazele programrii discreteObiectul programrii discrete este rezolvarea unor anumite probleme deoptimizare.Deniia 6.1.1. Programarea discret studiaz probleme de forma:_f(x) min/ maxx S,undeSeste o mulime numrabil.n literatura de specialitate internaional, n cadrul programrii discrete,nuexistoterminologieunic. nacestsens, suntfolositedenumiriledeprogramare n numere ntregi i programare combinatorial.Aceste tipuri de modele pot mprite n dou mari grupe:A. Modele care formal seamn cu modelele programrii liniare, dar sunti alte condiii puse asupra variabilelor pe lng condiia de nenegativitate.Aceste condiii, care determin tipurile de probleme discrete, pot :A1: xi = 0 sau 1 (unde notm cuxi variabilele problemei);A2: xi [0, d], xi ntreg (d N xat);A3: xi 0, xi ntregi.125iiJATEK 2005/3/1110:29page126#126iiiiii126 6. Tipuri speciale de probleme de optimizareSe poate observa c A3 A2 A1, implicaia reciproc neavnd loc. nconcluzie, dac avem o metod de rezolvare pentru probleme cele mai gen-eraleA3, atunci rezult c aceste metode pot folosite i pentru rezolvareaproblemelorA2 iA1.B. Cea de-a doua grup const n probleme mixte n care avem restriciidetipul A1, A2, A3doar pentruunelevariabile, iar pentrucelelaltedoarcondiia de nenegativitate.Un exemplu cunoscut n acest domeniu este problema rucsacului (veziparagraful 1.3).n continuare,prezentm cteva modele discrete care vor scoate n evi-den probleme eseniale legate de rezolvabilitatea modelelor discrete.Vom prezenta modele discrete n R2, care pot rezolvate pe cale grac.Fie modelul:___f(x) = 2x1 x2 max2x1 x2 0x2 1x1, x2 0, x1, x2 Nn acelai sistem de coordonate, reprezentm dreptele:(d1)2x1 x2 = 0 (d2) x2 + 1 = 0x2(d1)(d2)x1 2Observaie. Dac pentru o problem de programare discret ne rezummla raionamentul folosit, n cazul modelelor liniare putem grei.iiJATEK 2005/3/1110:29page127#127iiiiii6.1. Programare discret 127Exemplu.___f(x) = 5x1 x2 max5x1 x2 0x1 1x1, x2 0, x1, x2 Nn mod analog lucrnd, vom obine:x2(d1)(d2)1x1nvelitoareaconvexapunctelorconv a1, . . . , an(puncteledeinter-secieadreptelor)nuesteneapratunpoliedru. Deexemplu, lamodelulconsiderat, nvelitoarea convex tinde spre dreapta5x1 = x2, dar nu atinge.Deci trebuie luat n considerare cazul n care exist soluie admisibil, funciade scop este mrginit. i totui nu exist soluie optim.Are loc urmtorul rezultat:Teorema 6.1.1. Fie modelul:___f(x, y) = cx +dy min(max)Ax +By = bx Np+y Rq+A /mpB /mqNotm cuC = conv (S).Dac Ai Bsunt formate dinnumere raionale, atunci Ceste unpoliedru.iiJATEK 2005/3/1110:29page128#128iiiiii128 6. Tipuri speciale de probleme de optimizareObservaie. n orice caz practic, teorema asigur existena soluiei optime,dacexistsoluieadmisibili funciadescopest


Recommended