solutionarea matematica a probl economice

7/26/2019 Solutionarea Matematica a Probl Economice

1/388

1

UNIVERSITATEA LIBER INTERNAIONAL DIN MOLDOVA

Maximilian Silvestru

Soluionare matematic a problemelor

economice

CHIINU2012


2/388

2

n fiecare tiin este numai attatiin ct matematic conine.

Emanuil Kant

Totalitatea indicatorilor i ametodelor de gestionare a

economiei constituie proces economic.

Procesele economice expuse

n limbaj matematic constituiemodelare matematic a proceseloreconomice.

Modelarea matematic permiteutilizarea n programarea economic a potenialeloruriae ale tiinelor matematice;

permite utilizarea n programareaeconomic a calculatoarelor.


3/388

3

CUPRINS:

Introducere........... 81. Modelarea matematic aproblemelor de optimizare................................................... 11

1.1.Metode clasice de optimizare........................ 111.1.1. Cazul unei singure variabile.................................... 111.1.2. Cazul mai multor variabile................... ........... 14

1.2.Exemple de probleme, care conduc la programe liniare................ 161.2.1. Folosirea eficient a resurselor limitate................... 161.2.2. O problem de transport...................................................... 181.2.3. Un program de producie i stocaj....................... 201.2.4. Probleme de amestec............................... 201.2.5. Utilizarea optim a capacitii mainilor............. 201.2.6. O problem de investiii.............. 211.2.7. Reducerea pierderilor la tierea materialelor............... 211.2.8. Probleme de ordonanare......................... 22

1.3.Elemente ale programrii liniare............................ 221.3.1. Forma general a proramelor liniareInterpretarea geometric a unei probleme

de programare liniar............................................................................... 221.3.2. Programe de baz............................. 251.3.3. O metod de rezolvare a problemelor de programare liniar...... 271.3.4. O metod de rezolvare a problemelor de programare liniar...... 30

Bibliografie .............................. 31

2. Modele tipice de programare................... 32

2.1.Problema itinerarului nchis........... 322.2.Problema de transport........ 352.3.Problema de transport a lui Koopmans.......... 392.4.Probleme de repartiie........ 422.5.Probleme de amestec......... 452.6.O prblem dinamic: desfurarea produciei i stocurile......... 472.7.O alt problem dinamic: depozitarea mrfurilor........ 512.8.Prgramarea investiiilor: alegerea variantelor................ 532.9.Programarea investiiilor: alegerea orientrii.................... 552.10. Programarea investiiilor: repartiia investiiilor n timp...... 592.11.

Exemple de aplicare a analizei activitii.................. 61Bibliografie .............. 64

3. Elemente de teoria ateptrii........ 653.1.Definiii i notaii........... 653.2.Un model matematic.......... 663.3.Modele cu o singur staie de serviciu........... 683.3.1. Un model cu sosiri aleatoare i repartiia timpului de serviciu oarecare..... 683.3.2. Alte modele cu o singur staie.... 69

3.4.Modele cu mai multe staii............. 703.4.1. Uniti solicitante provenind dintr-o populaie infinit........... 71


4/388

4

3.4.2. Uniti solicitante provenind dintr-o populaie finit.......... 713.5.Aplicaii economice ale teoriei ateptrii............... 723.5.1. Domenii n care este aplicabil teoria ateptrii.............. 723.5.2. Un exemplu numeric....................... 73

Bibliografie. ............. 75

4. Elemente de teoria stocurilor............................... 764.1.Modele stochastice de gestiune a stocurilor.......... 774.1.1. Modele stochastice cu cost depenurie.... 774.1.2. Modele cu probabilitate de penurie ........................................ 78

4.2.Exemple numerice............. 804.2.1. Exemple numerice n cazul cercetrii deterministe......... 804.2.2. Exemple numerice n cazul cererii aleatoare............... 81

Bibliografie.... .............. 82

5. Programarea dinamic a aprovizionrilor i stocurilor n condiii de certitudine........ 835.1.Mrimea optim a unui lot achiziionat................. 835.2.Prima variant a formei generale a problemei de programare a aprivizionrilor i

stocurilor........88

5.3.Cazul n care loturile achiziionate nu sunt neaprat egale ntre ele...... 895.4.Cazul n care capacitatea depozitului este limitat........ 915.5.Cazul utilizrii neuniforme a stocului n timp....... 93Bibliografie ...... 98

6. Programarea dinamic a aprovizionrilor i stocurilor n condiii de incertitudine.... 996.1.Cazul n care probabilitatea ca stocul de rezerv s fie insuficient (coeficientul de

risc) este egal cu o mrime dat. Repartiia normal a probabilitii................... 996.2.Varianta n care repartiia probabilitii necesarului este o repartiie Poisson. 1046.3.Varianta n care repartiia probabilitii necesarului este rectangular

(uniform) ......................................... 1056.4.Stabilirea mrimii optime a coeficientului de risc i a rezervei optime n funcie decheltuielile pe care le comport deficitul, precum i depozitarea stocurilor....... 107Bibliografie. ..... 113

7. Funcii de producie, regula de aur a acumulrii..... 1147.1.Factorii de producie - Fora de munc i fondurile - ca elemente de calcul n

modele de cretere..... 1147.1.1.Neluarea n considerare a substituiei factorilor...... 1167.1.2. Relaxarea lipsei de situaie a factorilor prin programarea liniar........................ 1177.1.3. Modaliti de luare n considerare a caracterului continuu variabil i

substituibil al factorilor........................................................................................ 119

7.2.Funcii i factori de producie n exprimarea ,,per capita......................................... 1207.3.Determinatea cantitativ a contribuiei factorilor la realizarea produciei........ 123

7.4.Rata marginal de substituire a factorilor i elasticitatea de substituie aacestora...................................................................................................................... 126


5/388

5

7.5.Relaii cantitative dintre modificrile factorilor i cele ale produciei studiate cuajutorul funciilor de producie.................................................................................. 129

7.5.1. Ipoteza 1: Elasticitatea de substituie a factorilor egal cu zero; elasticitateaproduciei n raport cu fondurile i cu fora de munc egal cu 1 (decirandamentul factorilor constant).......................................................................... 130

7.5.2.

Ipoteza 2: Elasticitatea de substituie a factorilor egal cu 1; elasticitateaproduciei n raport cu fondurile i cu fora de munc egal cu 1 (decirandamentul factorilor constant).......................................................................... 130

7.5.2.1.Randamentul factorilor.................................................................................. 130

7.5.2.2.Analiza privind coninutul parametrilor funciei Cobb-Douglas................... 1317.5.2.3.Folosirea funciei Cobb-Douglas, exprimat n mrimi per capita, la

determinarea ratei de substituie i a ratei de elasticitate afactorilor........................................................................................................ 135

7.5.3. Ipoteza 3: Elasticitatea de substituie a factorilor cuprins ntre 0 i + ;randamentul factorilor constant...........................................................................

136

7.5.4.

Ipoteza 4: Elasticitatea de substituie a factorilor cuprins ntre 0 i ;randamentul factorilor cresctor sau descresctor............................................... 137

7.6.Starea de cretere echilibrat cu factori nesubstituibili; Modelul Harrod-Domar........................................................................................................................ 138

7.6.1. Cteva precizri preliminare privind unele relaii cantitativemacroeconomice.................................................................................................. 138

7.6.2. Relaiile fundamentale privind echilibrul dinamic n domeniulproduciei............................................................................................................. 139

7.6.3. Luarea n considerare a utilizrii forei de munc n cadrul echilibrului

dinamic cu factori nesubstuibili........................................................................... 1437.7.Modele neoclasice de cretere economic fr progres tehnic.......... 1477.7.1. Modelul de cretere al lui Solow......................................................................... 1487.7.1.1. Analiza calitativ a soluiilor......................................................................... 1497.7.1.2. Analiza cantitativ a soluiilor....................................................................... 155

7.7.2.Noiuni preliminare privind regula de aur a acumulrii.................................... 1587.8.Progresul tehnic i modele neoclasice....................................................................... 1617.8.1. Cteva consideraii privind sporirea contribuiei progresului tehnico-tiinific

la creterea economic.........................................................................................161

7.8.2. Influena progresului tehnic asupra proporiilor resurselor utilizate i asupraoutputului. 163

7.8.2.1. Tipuri de progres tehnic................................................................................. 165

7.8.2.2. Forme de exprimare a progresului tehnic neutru........................................... 168

7.8.3. Modele neoclasice cu progres tehnic nencorporat.. 1757.8.3.1. Modele cu funcii de producie cu coeficieni fixi......... 1757.8.3.2. Modele cu funcii de producie n care factorii snt continuu

substituibili .... 1787.8.3.2.1. Proiectarea pe termen lung a traiectoriei produciei... 1787.8.3.2.2. Analiza cantitativ a stabilitii traiectoriei pe termen lung a

produciei................................

180

7.8.3.2.3. Proiectarea traiectoriei pe termen lung a fondurilor de producie per 186


6/388

6

capita ..........................................................................................................

7.8.3.3. Luarea n considerare a deprecierii fizice i morale a fondurilor...... 1897.9.Regula de aur a acumulrii........ 1907.9.1. Definirea unor noiuni specifice.................. 1917.9.2. Descrierea cazului particular al regulii de aur a acumulrii.................... 192

7.10.

Prezentarea regulii de aur n forma genralizat.... 197Bibliografie ...... 201

8. Dinamica proceselor de reglare....................................... 2028.1.Interpretarea dinamic a multiplicatorului lui Keynes i a schemei

reproduciei 2028.2.Condiia de convergen a matricei......... 2048.3.Interpretarea dinamic a formulei fundamentale a teoriei reglrii........ 2068.4.Un exemplu de desfurare n timp a unui proces de reglare........ 2108.5.Dinamica procesului reproduciei...... 2138.6.Schemele bloc ale proceselor dinamice......... 2158.7.Dinamica formrii preului de pia....... 2188.8.Teoria stabilitii sistemelor de reglare...... 2218.8.1. Analiza general a dinamicii proceselor de reglare................. 2218.8.2. Dinamica proceselor de reglare continui............. 2238.8.3. Probleme practice de reglare............... 2278.8.4. Un exemplu: problema reaciei la stimulente...... 230

Bibliografie ...... 236

9. Balana legturilor dintre ramuri.......................................... 2379.1.Sistemul de balane al economiei naionale i conducerea planificat a

economiei........... 2379.2.Balana legturilor dintre ramuri parte component a balanei economiei

naionale. 2399.3.Balana legturilor dintre ramuri i conturile economiei naionale....... 2419.4.Prezentarea modelului. Model deschis i model nchis......... 2449.5.Modelul balanei legturilor dintre ramuri n expresie natural............ 2479.6.Modelul balanei legturilor dintre ramuri n expresie valoric............ 2539.6.1. Schema i modelul matematic......................... 2539.6.2. Cazuri particulare........................ 2609.6.3. Ajustarea coeficienilor tehnologici..................... 263

9.7.Coeficienii repartizrii produciei..................... 2659.8.Analiza i interpretarea matricei ............... 2689.9.Determinarea coeficienilor cheltuielilor totale pe baza coeficienilor de cheltuieli

directe i indirecte.............. 2799.10. Calculul coeficienilor cheltuielilor totale prin iteraii.. 2899.11. Legtura dintre balana n expresie natural i cea n expresie valoric... 2979.12. Metode de caracterizare a ansamblului economiei naionale.... 3009.12.1.

Schema lui Fr. Quesnay....................... 3019.12.2.Prezentarea schemelor de reproducie ale lui Carl Marx, cu ajutorul balanei


7/388

7

legturilor dintre ramuri... 3039.12.3.Modelul lui L. Walras.. 3089.12.4.Balana economiei naionale a U.R.S.S. pentru anul 1923/1924..... 3109.12.5.Metoda inputoutput.. 312

9.13. Interpretarea cibernetic a balanei legturilor dintre ramuri.... 314

Bibliografie ...... 322

10. Analiza dinamic a legturilor dintre ramuri........... 32310.1.Modelul dinamic al lui W. Leontief..... 32310.2.Modelul dinamic al lui O. Lange..... 32710.3.Influena structurii materiale a investiiilor asupra creterii produciei sociale... 334Bibliografie ...... 339

Anex....... 340Elemente de calcul matricial............ 340A.1. Vectori i operaii cu vectori............. 340A.2. Algebra matricelor.... 350A.3. Folosirea calculului matricial n descrierea procesului de fabricaie.... 381A.4. Rezolvarea sistemelor de ecuaii liniare cu ajutorul calculului matricial. 385A.5. Ecuaii caracteristice. Rdcini caracteristice i vectori caracteristici.. 390Bibliografie ...... 390


8/388

8

INTRODUCERE

Obiectul lucrrii de fa este analiza proceselor economice n limbajul simbolurilor, nlimbajul matematic. Muli factori contribuie la dezvoltarea foarte lent a teoriei economice. nviziunea noastr tiina economic ar fi avut soarta fizicii n dezvoltarea sa, dac mai puin ar fi

fost influenat defactorii politici i mai mult apela la un limbaj de expunere a coninutului, lalimbajul matematicii. Matematica pune ntr-o lumin nou problemele economice, ofer uninstrument eficient i n aplicrile practice, i n elaborrile teoretice.

Una dintre cele mai tinere ramuri ale matematicii aplicative o constituie metodele

matematice n economie, numite metode economico-matematice.Pn la ce de al doilea rzboi mondial au existat preocupri de a crea modele i metode

matematice n economie. Rzboiul a pus ns cu insisten problema mobilizrii totale a tuturorresurselor n btlie nct toate ramurile matematicii care puteau oferi instrumente utile de calculn cutarea rspunsului la ntrebarea: care este modul optim de aciune?, au fost solicitate s-idea contribuia. Rezultatul a fost o colecie de metode de optimizare, un nceput puternic dedezvoltare a economiei bazat pe alte principii, concepte i modaliti. Dup rzboi s-a produs un

transfer util i rapid al metodelor matematice n domeniuleconomic. Metodele matematice staula baza gestiunii ntreprinderilor, la studiul balanelor economice, la elaborarea programelor dedezvoltare economic a ramurilor, a economiei naionale. Metodele matematice cu succes pot fiutilizate: n domeniul de natur economic, financiar, comercial, de organizare a produciei, acomportamentului uman etc.

n situaia, cnd numrul populaiei este n cretere, iar volumul resurselor naturaleantrenate n circuitul economic n descretere, problemele ecologice devin tot mai acute,metodele matematice au nc o ocazie de dezvoltare considerabil. Metodele matematice nu autendina de a se constitui ntr-o disciplin matematic distinct, n-au obiectul su bine definit ele constau din aparate i procedee de o mare diversitatepentru muli cercettori ele continus rmn o simpl colecie fr nume i statut definitiv, o list de simple procedee convenabilen aplicaii. n pofida caracterului eteroclit, metodele matematice, care au attea definiii ciautori se ocup de ele, au remarcabile puncte comune. Toate se refer la probleme care au unnumr mare de soluii admisibile. Metodele matematice ofer procedee de selecie din spaiulsoluiilor a unei singure soluii, care satisface una sau mai multe condiii. Aceasta este soluiaoptim.

Lucrarea de fa cuprinde cele mai diverse procese economice expuse n limbajulmatematic.

Prin proces economicvom nelege totalitatea indicatorilor i a metodelor de gestionareeconomic.

Metodele economico-matematice, algoritmii pentru soluionarea problemelor examinate,diversitatea domeniilor economice de unde sunt preluate problemele, pot servi un suport

bibliografic pentru efectuarea celor mai diferite lucrri.Noiunea de model provine de la cuvntul latin modulus, ceea ce nseamn: mostr,

msur. n prezent aceast noiune are un sens mai larg i reprezint un obiect, care cuprinde undomeniu larg de metode utilizate pentru cunoaterea practic i tiinific a diverselor obiecte destudiu.

Prin modelvom nelege un proces sau fenomen reprezentat material sau imaginar carenlocuiete obiectul originar.

Modelul poate fi considerat ca o reprezentare izomorf a realitii. Modelul, oferind oimagine intuitiv i riguroas n sensul structurii logice a fenomenului studiat, faciliteazdescoperirea unor legiti i legturi imposibile sau greu de gsit pe alte ci.

Dup felul lor modelele pot fi:


9/388

9

modele matematice utilizate pentru rezolvarea unor modele fizice (reproducerea

fizic a situaiei reale); modele verbaledescriptive (utilizate n toate disciplinile nematimatizate); modele conceptual-matematice care reproduc realitatea obiectiv prin simbolica

riguroas matematic, respectnd legitile impuse de aceasta.

Situaiile economice pot fi exprimate prin modele economico-matematice. Grupareaacestor modele poate fi fcut dup urmtoarele criterii:

A. n funcie de sfera de reflectare a problematicii economice:

modele microeconomiceaplicate la nivel de ntreprindere, trust, companie; modele mezoeconomiceaplicate la nivel regional, teritorial; modele macroeconomicemodele de ansamblu ale economiei.

B. n funcie de domeniul de provenien i concepie:

modele cibernetico-economice (de reglare); modele econometrice (de explicare a unor tendine); modele ale cercetrii operaionale (permit obinerea soluiilor optime pentru

fenomenul studiat);

modele de decizie (lund n considerare mai multe criterii se determin soluiaeficient);

modele de simulare (stabilesc modul de funcionare a obiectului studiat).

C. n funcie de caracterul variabilelor: modele deterministe (mrimi cunoscute);

modele stochastice (mrimi care intervin cu o anumit probabilitate).

D. n funcie de factorul de timp: modele statice (valabile pentru o anumit perioad); modele dinamice (utilepentru o perioad de timp).

E. n funcie de proprietatea continuitii: modele discrete, secveniale; modele continue.

F. n funcie de sfera i structura proceselor de reflectare: modele cu profil tehnologic;

modele informaional-decizionale; modele ale relaiilor umane; modele informatice.

Pentru elaborarea modelului matematic a unui proces concret studiat se parcurg

urmtoarele etape: elaborarea modelului;

studierea modelului;

mbuntirea modelului iniial; implementarea modelului.


10/388

10

Modelarea este o component a tratrii cibernetice a proceselor economice i invers otratare sistemiceste imposibil fr formalizarea proceselor n limbaj matematic.

Modelarea matematic a unor procese economice n condiii de incertitudine, de totalincertitudine, ne impune necesitatea de msurare a incertitudinii. Modelarea matematic a

proceselor economice contribuie la integrarea cunotinelor economice, la clasificarea isistematizarea acestora. Modelarea devine un fel de totalizare a cunotinelor din economiageneral, macroeconomie, microeconomie, statistic, analiza matematic, algebr, teoria

probabilitilor, programrii matematice, statisticii etc.Modelarea proceselor economice are un loc deosebit i foarte important n soluionarea

problemelor economice, n cercetrile tiinifice.


11/388

11

CAPITOLUL I: MODELAREA MATEMATIC A PROBLEMELOR DE OPTIMIZARE

1.1. METODE CLASICE DE OPTIMIZARE

Matematica clasic are ca instrumente principale de rezolvare a problemelor de extremcalculul diferenial i calculul variaiilor. Din pcate, aceste metode se dovedesc n foarte multe

cazuri inaplicabile; chiar n cazurile n care se pot aplica, ele ofer mai degrab procedee

teoretice pentru obinerea de soluii analitice, dect procedee de calcul pentru aflarea soluiilor

numerice dorite. Din acest motiv a fost necesar s se gseasc procedee iterative de calcul

(algoritmi); datorit existenei potenialului de calcul al calculatoarelor electronice moderne,

aceti algoritmi permit rezolvarea unor importante clase de probleme practice. Este instructiv s

artm n cteva cuvinte care snt dificultile pe care le ntmpinm n rezolvarea problemelor deextrem liber sau legat cu metodele clasice.

1.1.1.CAZUL UNEI SINGURE VARIABILE

Problema

(1.1) ,(1.2)

,

unde este derivabil pentru orice , se rezolv calculnd rdcinile reale aleecuaiei ,care se numescpuncte staionareale funciei .Punctele de extrem (de maxim sau minim) seafl printre aceste rdcini. Pentru a testa dac un punct staionar este punct de extrem, se

presupune c funcia are derivate de ordinul al doilea n acest punct i se trage concluzia c este un punct de maxim sau minim relativ dup cum

,sau

. Dac

,

este posibil ca punctuls nu fie punct de extrem. Mai precis, dac presupunem c , , , , , ,atunci avem rezultatul urmtor: dac este numr par, este punct de maxim sau de minimdup cum sau ; dac este numr impar, atunci nu este punct deextrem.

nfig. 1.1este redat graficul unei funcii pentru . Punctele staionaresnt

,

, , . Dintre acestea, punctele de maxim relativ snt

, , ,

punctele de minim relativ snt , , , , iar punctul nu este punct de extrem.


12/388

12

Punctul de maxim absolut este , iar punctul de minim absolut este . Prin urmare,problema (1.1), (1.2) are singura soluie optim f(x)

( ) x0 x1 x2 x3 x4 x5 x6 x7 x8 x9

Fig. 1.1

Dac n locul condiiei (1.2) impunem condiia

(1.2)

,

problema (1.1), (1.2) se complic. ntr-adevr, n acest caz, punctele de extrem pot s

nu fie puncte staionare, cum se vede n fig. 1.2, unde punctele staionare snt i (respectiv maxim i minim relativ), iar punctele i snt respectiv minimul imaximul absolut, fr s fie puncte staionare. Problema (1.1), (1.2) are n acest caz

singura soluie optim . Prin urmare, rezolvarea problemei (1.1), (1.2) cerecompararea valorilor funciei nu numai n punctele de maxim (sau minim) relativ,aflate prin anularea derivatei nti, dar i n punctele de la extremitile intervaluluinchis . Aceast dificultate este din ce n ce mai evident odat cu cretereanumrului variabilelor i devine un obstacol aproape imposibil de trecut cnd numrul

variabilelor este mare.

Exist un caz simplu, n care anularea derivatei nu d nici o informaie despre

punctele de extrem, i anume cazul n careeste o funcie liniar:

.


13/388

13

f(x)

[ ] x0 x1 x2

Fig. 1.2

Derivata este n acest caz , iar mulimea punctelor staionare este intervalulnchis dac i mulimea vid dac . nlturnd deci cazul banal , observm c funcia liniar nu are puncte staionare,

f(x)

[ ] x

0 Fig. 1.3

punctele sale de extrem aflndu-se la extremitile intervalului . n fig. 1.3(pentrucazul unei funcii liniare cresctoare) punctul de minim absolut este , iar punctul demaxim absolut este .

Proprietatea aceasta se menine cnd numrul variabilelor este mai mare ca 1, iar

intervalul nchis

este nlocuit cu un poliedru convex.

Dac funcianu este derivabil, metoda expus este evident inaplicabil. Din pcate, n


14/388

14

multe probleme concrete apar funcii nederivabile; acest fapt, pe lng multe altele, face necesar

cunoaterea altor metode de optimizare.

1.1.2.CAZUL MAI MULTOR VARIABILE

S considerm problema

(1.3) ,undeeste o funcie difereniabil pe o mulime deschis . Punctele staionare alefuncieise obin ca soluii ale sistemului , ,care este n general greu de rezolvat, chiar numeric. Punctele de extrem se afl printre

punctele staionare ale funciei ; pentru a testa dac un punct staionar este sau nupunct de extrem, este necesar s se presupun c funcia are derivate de ordinul doicontinue n vecintatea punctului i s se analizeze, dac formaptratic

este definit sau nedefinit. n primul caz punctul

este punct de maxim sau de minim,

dup cum sau ; n al doilea caz punctul nu este punct de extrem.Dac forma este degenerat, se ridic probleme deosebit de dificile. Dacfuncia nu are derivate pariale continue n vecintatea punctelor staionare, testareaoptimalitii punctelor staionare devine un obstacol aproape imposibil de trecut, cnd

numrul variabilelor este mare. Este evident inaplicabilitatea acestei metode n cazul

unei funcii nedifereniabile, caz care se ntlnete frecvent n practic. nc i maicomplicat devine rezolvarea problemei

(1.4) ,(1.5) , .Orice punct care este soluie a sistemului de ecuaii 1:

(1.6) , ,(1.7)

, ,

1Se presupune c rangul matricei este egal cu.


15/388

15

este numitpunct staionar condiionat al funciei . Numerele reale , , careapar n ecuaia (1.7) snt numite multiplicatori Lagrange. Dac i , , sntdifereniabile n vecintatea unui punct de extremum condiionat, atunci punctul este punct staionar condiionat, reciproca fiind n general fals.

Dac introducem funcia lui Lagrange (lagrangianul) asociat problemei (1.4),(1.5): ,atunci sistemul de ecuaii (1.1.1.6), (1.1.1.7) devine

(1.8) , ,

(1.9) , .

Printre punctele staionare condiionate obinute din (1.8), (1.9) se afl punctelede extrem condiionat. Verificarea optimalitii se face tot cu ajutorul unei forme

ptratice n ipoteza c funciile i au derivate pariale continue de ordinul al doilean vecintatea punctelor staionare condiionate.

n afara dificultilor deja semnalate privind presupunerile asupra proprietilor

de regularitate ale funciilor i , trebuie s precizm aici c unele restricii sntdestul de rar ntlnite n formularea problemelor cu caracter economic; n mod obinuit

aceste restricii snt inecuaii. n acest caz metodele clasice devin aproape imposibil deaplicat. ntr-adevr, punctele de extrem pot s se afle n acest caz pe frontiera

domeniului nchis , i nu numai printre punctele staionare aflate n interiorul domeniului , verificareaoptimalitii fiind n acest caz foarte dificil.

n cazul unei probleme de programare liniar, de exemplu, informaia pe care o

cptm anulnd derivatele pariale este nul, toate punctele de extrem aflndu -se pe

frontiera domeniului nchis .Metodele calculului diferenial nu se pot aplica problemelor de un anumit tip,

ntruct acolo nu exist posibilitatea variaiei continue a variabilelor independente, cu

excepia unor cazuri izolate, cnd aceast variaie poate fi introdus prin anumite

artificii. Observaii asemntoare se pot face i n privina aplicabilitii metodei

calculului variaional clasic la probleme cu caracter economic.

Din cele remarcate mai sus n legtur cu posibilitile i limitele calculului

diferenial clasic se pune n eviden necesitatea noilor metode de optimizare, metode

care reuesc s suplineasc, uneori n parte, alteori n totalitate deficienele semnalate.


16/388

16

n cele ce urmeaz se va putea urmri modul n care diferite metode de optimizare

reuesc aceast performan, limitele lor, precum i necesitatea unor cercetri care s

permit abordarea unor noi clase de probleme nerezolvate.

1.2. EXEMPLE DE PROBLEME,CARE CONDUC LA PROGRAME LINIARE

1.2.1. FOLOSIREA EFICIENT A RESURSELOR LIMITATE

O problem practic ce se pune deseori unui conductor de ntreprindere este urmtoarea.

Avem la dispoziie mai multe resurse (materie prim, for de munc, maini-unelte, resurse

financiare etc.) care ne snt date n cantiti limitate. Vom nota cu numrul de ordine al resurseii cu cantitile disponibile din aceste resurse. Cu ajutorul acestor resurse se pot desfura maimulte activiti (de exemplu, procese de producie). Vom nota cu numrul de ordine alactivitii desfurate i cu nivelul (necunoscut) la care trebuie s se desfoare aceastactivitate. De exemplu, dac considerm procesul de producie

care const n fabricarea unui

anumit produs, vom nota cu cantitatea ce va fi produs. Vom nota prin cantitatea dinresursa

necesar pentru producerea unei uniti din produsul

(din activitatea

n general).

Presupunem aici c nu depinde dect de tipul resursei ( ) i de tipul produsului realizat () inu de cantitile produse, ceea ce constituie evident o simplificare a situaiei reale.Cu aceste notaii putem exprima acum cteva mrimi care ne intereseaz foarte mult, i

anume:

cantitatea din resursafolosit pentru producerea cantitii , care este ; cantitatea total din resursa folosit pentru producia total format din

produse:

.Deoarece nu putem consuma din resursa mai mult dect cantitatea pe care o avem ladispoziie, trebuie s fie respectat condiia

pentru fiecare resursdin cele resurse pe care le avem la dispoziie, adic(1.10) .Deoarece

reprezint cantitatea ce trebuie produs din sortimentul

, ea nu poate fi un numr

negative

(1.11) ,


17/388

17

adic poate fi numai un numr pozitiv sau nul (nenegativ).

Inecuaiile (1.10) se numesc restriciile problemei, iar (1.11) snt condiiile de

nenegativitate.

Sistemul de inecuaii liniare (1.10), (1.11) poate avea o infinitate de soluii, o soluie

unic sau nici o soluie (sistem contradictoriu sau incompatibil), cum se va vedea ulterior. Cazulcel mai frecvent pentru problemele practice corect puse este cazul n care sistemul (1.10), (1.11)

are o infinitate de soluii. Prin urmare, este posibil s organizm procesele de producie pentru

fabricarea sortimentelorj (1 j n) ntr-o infinitate de feluri, respectnd condiiile de folosire a

resurselor limitate (1.10). Acest fapt face evident imposibilitatea practic a conductorului de

ntreprindere de a compara toate variantele de plan posibile pentru adoptarea unei decizii

adecvate.

Adoptarea unei variante de plan (lucrarea deciziei) se face pe baza unui criteriueconomic, ca, de exemplu, venitul sau beneficiul maxim. Dac notm prin cjpreul de vnzare al

unei uniti din procesul j i prin djpreul de cost unitar pentru acelai produs2, atunci venitul

total realizat va fi , iar cheltuielile de producie vor fi , deci beneficiulobinut va fi

sau

(1.12) Problema care se pune este de a afla acea (acele) variant de plan, adic acea (acele)

soluie a sistemului de inegaliti (1.10), (1.11), care d beneficiului (1.12) valoarea maxim.

Aceast problem economic devine n acest moment o problem matematic:

(1.13) ,(1.14) ,(1.15) ,care este oproblem de programare liniarsau unprogram liniar.

1.2.2.O PROBLEM DE TRANSPORT

2Presupunem evident c att preul de vnzare, ct i preul de cost nu depind de cantitatea produs, ceea ce

reprezint o simplificare care n multe cazuri este prea departe de realitate.


18/388

18

Avem mcentre de aprovizionare (depozite) i ncentre de consum (uzine, magazine etc.).

Dorim s determinm un plan de transport pentru un produs omogencare se afl n cantitatea ai

la depozitul i (1 i m) i este cerut n cantitatea bjla depozitulj(1 j n). S notm prin xij

cantitatea (necuscut) ce va fi transportat de la depozitul i la centrul de consum j i prin cij

preul3

transportului unei uniti din produsul considerat de la depozitul ila centrul de consumj.Se pot examina atunci urmtoarele mrimi:

cantitatea transportat de la depozitulila toate cele n centre de consum este

xi1+ xi2+ ... + xin;

cantitatea transportat de la toate cele mdepozite la centrul de consumj este

x1j+ x2j+ ... + xmj;

costul transportului de la depozitul ila centrul de consumjeste cijxij.

Prin cantitatea calculat mai sus reprezint chiar cantitatea ai aflat la depozitulii deci(1.16) .A doua cantitate necesarul la centrul deconsumj:

(1.17) .O condiie evident este

(1.18) xij 0, 1 i m, 1 j n.

Costul total al transportului de la toate depozitele la toate centrele de consum este

.Pentru ca s se poat efectua transportul este necesarca .Sistemul de ecuaii liniare (1.16), (1.17) are n aceste condiii o infinitate de soluii.

Dintre acestea trebuie alese acelea care dau costului total de transport valoarea minim. Obinem

din nou un program liniar

(1.19)

;

(1.20) .(1.21) .(1.22) xij 0, 1 i m, 1 j n.

care se numeteprogram de transport.

Programe liniare de acelai tip s apar i n alte ecuaii. Dac, de exemplu, este vorba de

aprovizionarea unui grup de uzine dirijate de un centru comun, atunci exist m centre de

aprovizionare i npuncte pe consum i se cere determinarea unui plan de transport (xij), 1 i

3Se presupune deci implicit c acest cost unitar nu depinde de cantitatea transportat pe ruta respectiv.


19/388

19

m, 1 j n, care s minimizeze cheltuielile totale de transport

(1.23) ,n condiiile

(1.24)

,

(1.25) ,(1.26) xij 0, 1 i m, 1 j n,unde ai, 1 i m, snt capacitile centrelor de depozitare, bj, 1 j n,snt cantitile necesare

uzinelor, iar cijeste costul unitar de transport de la depozitul i la uzinaj. Condiiile (1.24), (1.25)

au interpretri economice evidente. Pentru a exista soluii, este necesar ca .Problema se poate pune i invers, considernd problema unui plan de transport de la mai

multe uzine i, 1 i m, la punctele de desfacerej, 1 j n. Dac ai, 1 i m, reprezint acum

capacitile de producie ale uzinelor, iar bj, 1 j n, reprezint capacitile de depozitare ale

punctelor de desfacere, se obine un model similar n care grupurile de inecuaii (1.24) i (1.25)

se transform prin schimbarea sensului inegalitilor.

n sfrit, se poate include, n acest din urm caz, i cheltuielile de producie, urmrind

minimizarea costului total de producie i transport; problema poate fi nc complicat acceptnd

centre intermediare de transport i considernd i cheltuielile provenite din stocaj n aceste centre

i n punctele de desfacere.

1.2.3. UN PROGRAM DE PRODUCIE I STOCAJ

n cursul a nluni trebuie produse ri,1 j n, uniti dintr-o anumit categorie. Un orar

normal permite un volum de producie de i,, 1 j n, uniti pe lun. Se poate prevedea oproducie suplimentar de i, 1 j n, uniti lunare.

Costurile unitare de producie snt ci, c'i lunar, respectiv n primul i n al doilea caz.

Costul unitar de stocaj pe lun este d. Se cere s se afle cantitile xi, ,si, 1 i n, ce trebuieproduse n orar normal, n ore suplimentare, respectiv cantitile stocate, astfel nct s fierespectate condiiile

(1.27) ,(1.28) 0 xi i;1 i n,(1.29) 0 ;1 i n,(1.30) si 0; 1 i n,

i s se obin minimul cheltuielilor de producie i stocaj:(1.31) .


20/388

20

1.2.4. PROBLEME DE AMESTEC

Una dintre primele probleme practice, formulat i rezolvat ca problem de programare

liniar, este aa-numita problem a dietei. Ea const n aflarea unei diete dintr-un numr dat dealimente, care s satisfac anumite cerine biologice i s fie n acelai timp cea mai ieftin.

Mai precis, fie aij cantitatea din principiu nutritiv i, 1 i m, coninut ntr-o unitate din

alimentul j, 1 j n. Este necesar ca dieta s conin cel puin biuniti din principiul nutritiv i,

1 i m. Dac cj, 1 j n, snt costurile unei uniti din alimentulj, problema const n aflarea

cantitilorxj, 1 j n, de alimente pe care trebuie s le cuprind dieta, astfel nct s obinem

minimul costului total

(1.32) i s fie respectate restriciile(1.33) ,(1.34) xj 0, 1 j n.

Problemele de acelai tip apar atunci cnd se urmrete formarea unor amestecuri de

ingrediente, care s aib anumite proprieti (specificate n fiecare caz concret) i astfel o

caracteristic a amestecului s fie optim dintr-un anumit punct de vedere. Probleme de diet

apar, de exemplu, n alctuirea raiilor pentru animale n yootehnie, pentru calculareaamestecului optim de ngrminte n agricultur, n industria chimic pentru diverse amestecuri,

n industria petrolier pentru amestecuri de benzin etc.

1.2.5. UTILIZAREA OPTIM A CAPACITII MAINILOR

Se pune urmtoarea problem: o ntreprindere produce mai multe produse care pot fi

fabricate pe aceeai main a crei capacitate de producie pe o perioad este limitat; se cere un

program de producie care s asigure utilizarea optim a mainilor.

Mai precis, uzina produce nproduse distincte, care pot fi produse cu ajutorul a mmaini

(sau secii de producie) care au capaciti limitate. Notm aij, 1 i m, 1 j n, procentul din

capacitatea mainii ipe perioada considerat necesar pentru producerea unei uniti din produsul

j, iar prin xj, 1 j n, numrul unitilor din produsul j fabricate n cursul perioadei. Avem

restricii de capacitatea de forma

(1.35)

,

i problema se completeaz adugnd la (1.35)


21/388

21

(1.36) xj 0, 1 j n,

(1.37) ,unde cjsnt beneficiile unitare.

1.2.6. O PROBLEM DE INVESTIII

Avem la dispoziie o sum total Scare poate fi investit n diverse activiti j,1 j n,

fiecareproducnd un anumit beneficiu unitaraj, 1 j n. Dacxj, 1 j n, este suma investit

pentru activitateaj,problema este

(1.38) ;(1.39)

;

(1.40) xj 0, 1 j n.

Problema poate fi complicat inc dnd anumite reguli suplimentare n legtur cu

posibilitatea de investiie, cu existena unui risc al investiiilor i cu neliniaritatea beneficiului

total.

1.2.7. REDUCEREA PIERDERILOR LA TIEREA MATERIALELOR

Vom considera o problem simpl, care apare n activitatea de tiere a hrtiei la o fabricde celuloz, care produce rulouri de hrtie de lime dat, depinznd de caracteristicile mainii.

Aceste ruoluri trebuie tiate pentru a satisface comenzile beneficiarilor, ceea ce genereaz

anumite pierderi; problema este s se minimizeze aceste piederi. S notm prin ai, 1 i m, bi,

1 i m, respectiv limea i lungimea celor m rulouri comandate, iar prin l limea ruloului

standart produs de main. Se determin toate combinaiile posibile k, 1 k N, n care poate fi

tiat ruloul standart pentru a obine dik, 1 i m, 1 k N, rulouri de lime ai(evident 0 dik

unde prin [x] se noteaz partea ntreag a lui x). Dac se noteaz cuxk, 1 k N, lungimearuloului standart n cazul n care se aplic tierea de tipul k, avem condiiile ,xk 0, 1 k N,

sau nforma standard*

(1.41) ;(1.42) xk 0, 1 k N;

(1.43) 0, 1 i m.Dac notm cuck, 1 k N,pierderea prin tiere n cazul procedeului de tipk,pierderea


22/388

22

total care trebuie minimizat va fi:

(1.44) .Formularea (1.41) (1.44) presupune existena unei singure maini; cazul mai multor

maini este mai dificil.

1.2.8. PROBLEME DE ORDONANARE

Pentru realizarea unei lucrri complexe este necesar s se execute activitile pariale i, 1

i n, ale cror durate di, 1 i n, snt cunoscute. Problema care se pune este s se afle

momentele ti, 1 i n, la care trebuie s nceap realizarea activitilor pariale i,astfel nct s se

minimizeze timpul n care toate activitile snt terminate.

S presupunem, de exemplu, c trebuie s avem ndeplinite condiiile date n tabelul demai jos.

Activitilepariale (i)

Cerinele care trebuie satisfcutela nceperea activitii i

Durata n zile aactivitii i

1 ncepe dup 2 zile de la debutul lucrrii 102 ncepe dup 3 zile de la debutul lucrrii 123 ncepe dup 4 zile de la debutul lucrrii 84 activitile 1 i 3 terminate 55 75% din activitatea 2 i 20% din activitatea 4 terminate 15

6 Activitile 2,4 i 5 terminate 14Dac notm cu t0momentul de debut al lucrrii i cu tfmomentul n care se termin toate

activitile, problema se poate scrie sub forma

t1- t0 2; t2- t0 3; t3- t0 4;

t4t1 10; t4t3 8; t5t2 9;

t5t4 1; t6t2 12; t6t4 5;

t6t5 15; tft6 14;

ti 0, 1 i 6;

min tf,

adic este un program liniar.

1.3. ELEMENTE ALE PROGRAMRII LINIARE

1.3.1. FORMA GENERAL A PRORAMELOR LINIARE

Din exemplele considerate rezult c restriciile unui program liniar pot fi inegaliti de


23/388

23

forma , inegaliti de forma sau egaliti. Variabilele care intervin ntr-un program liniar snt

n mod obinuit supuse condiiei de nenegativitate, dei pot exista cazuri n care trebuie s fie

nepozitive sau oarecare. n sfrit, funcia obiectiv poate fi minimizat sau maximizat. Forma

generala unui program liniar este deci urmtoarea:

(1.45) min (max) [ x1 +

x2

+ x3

],

A11x1+ A12x

2+ A13x

3 b1,

A21x1+ A22x

2+ A23x

3 b2,

A31x1+ A32x

2+ A33x

3 b3,

x1 0,x2 0, x3 oarecare,

unde x i x snt vectori ale cror componente snt supuse condiiilor de nenegativitate i

nepozivitate respectiv, iar x este vectorul ale crui componente sntnumere reale oarecare.

Un program liniar n care toate restriciile snt ecuaii i toate variabilele snt supusecondiiei de nenegativitate se numete program liniar n forma standart. Un astfel de program

liniar are deci forma

min (max) (c'x),

(1.46) Ax = b, x 0.

Un program liniar areforma canonicatunci cnd este scris sub forma

min c'x, max c'x

sau

(1.47) Ax b, Ax b,

x 0, x 0.

O restricie a unui program liniar este numit concordant dac este o inegalitate de tipul

ntr-o problem de minimizare sau o inegalitate de tipul ntr-o problem de maximizare. Un

program liniar are deci forma canonic dac toate restriciile snt concordante i toate variabilele

snt supuse condiiei de nenegativitate.

Programele liniare n forma standard sau n forma canonic snt aparent mai puin

generale dect forma (1.45). Vom arta n cele ce urmeaz c, n realitate, toate formele indicate

snt echivalente n sensul c orice program liniar se poate aduce la forma standart sau la forma

canonic, folosind urmtoarele transformri echivalente:

(a) sensul unei inegaliti se schimb prin nmulire cu 1;

(b) transformarea inecuaiilor n ecuaii: o inecuaiei de forma a'x bpoate fi scris

ca o ecuaiea'x + y = b, introducnd o variabil (numit variabil ecart, variabil abateresau

variabil de compensare) y 0; o inecuaie de forma a'x bse transform n ecuaiaa'x - y = b

prin scderea variabilei ecart y 0; variabilele ecart nu apar n funcia obiectiv (adic apar cu

coeficieni nuli);


24/388

24

(c) o ecuaie a'x b este echivalent cu dou inegaliti de sens contrar: a'x bia'x b;

(d) o variabil supus condiiei de nepozivitate (adic x 0) se transform ntr-o

variabil nenegativ prin substituiax' = -x;

(e)

o variabil oarecare x(adic o variabil creia nu i se impune restricie de semn)se poate nlocui cu dou variabile nenegativex' ix'' legate prin relaiax = x' - x'';

(f) deoarece ,o problem de minimizare se poate transforma ntr-o problem de maximizare i invers,

schimbnd semnele coeficienilor din fucia obiectiv.

Exemplu.S se aduc la forma standart i la forma canonic urmtorul program liniar:min (2x1x2+ 4x3),

2x1x2= 10,

x1+ 2x2 1,

2x1x23x3 - 2,

x1 0,x2oarecare,x3 0.

nlocuid variabila oarecare x2 cu diferena a dou variabile nenegativex2 =x4x5, fcnd

substituiax

3= - x

6i introducnd variabilele ecart

x7i

x8n cele dou inecuaiiale problemei,

obinem forma standard

min (2x1x4+x5- 4x6),

2x1x4+x5= 10,

x1+2x4- 2x5x7= 1,

2x1x4+x5+3x6+x8= - 2,

x1,x4,x5,x6,x7, x8 0.

Pentru a aduce problema la foma canonic vom transforma prima ecuaie n dou

ineciuaii de sens contrar; pentru ca toate inecuaiile problemei s fie concordante vom nmuli

cu -1 toate inecuaiile de forma deoarece problema este de minimizare. Fcnd aceleai

nlocuiri ale variabilelorx2ix3, obinem forma canonic

min (2x1x4+x5- 4x6),

2x1x4+x5 10,

-2x1+x4-x5 -10,

x1+ 2x4- 2x5 1,

-2x1+x4-x53x6 2,

x1,x4,x5,x6 0.


25/388

25

1.3.2. INTERPRETAREA GEOMETRIC A UNEI PROBLEME

DE PROGRAMARE LINIAR

O interpretare geometric a unei probleme de programare se poate obine simplu n cazul

cnd problema are numai dou variabile i se prezint sub forma canonic. Orice problem de

programare liniar care conine numai dou variabile se poate rezova grafic; dei lipsit de

importan practic, o astfel de rezolvare este foarte instruciv i permite utilizarea unui imbaj

intuitiv comod, care se poate extinde destul de uor la cazul general a nvariabile.

Exemplu.S considerm problema sub forma canonic:(1.48) max (0,5x1+x2)

x1 2

(1.49) x1+x2 3

-x1+x2 1

x1,x2 0

Ecuaiilex1= 2,x1+ x2= 3, -x1+ x2=1 snt drepte n planul cu axele de coordonate Ox1,

Ox2fig.(4) i mpart planul n semiplane. Semiplanul x1 2 determinat de dreapta (CD):x1= 2

este cel n care se afl originea O (0, 0). Toate punctele situate pe figur la dreapta dreptei CD

(adic semiplanul x1 > 2) au drept coordonate numerele (x1, x2) care nu pot fi soluii ale

sistemului (1.49). nzr-o manier analoag sntem condui la concluzia c toate punctele (x1,x2)

care aparin semiplanelor x1 + x2 > 1 sau x1 + x2 > 3 nu pot fi soluii ale sistemului (1.49).

condiiile de nenegativitatex1 0,x2 0 snt reprezentate prin semiplanele care conin sensurile

pozitive ale axelor Ox1i respectiv Ox2. Punctele care aparin poligonuluiOABCDau deci drept

coordonate soluiile sistemului (1.49).

Mai general, mulimea soluiilor sistemului ,xj 0, 1 j n,

poate fi considerat ca intersecia celor m + n semispaii determinate de hiperplanele

corespunztoare: ,xj 0, 1 j n.


26/388

26

x1+ x2= max(

)

B(1, 2)

A(0, 1)

C(2, 1)

x1+ x2=d

D(2, 0)

O(0, 0)

Fig. 1.4

Este clar c o interpretare grafic este n general imposibil, dar limbajul geometric poate

fi extins n mod natural.

Dreapta

(1.50) 0,5x1+x2= d

va fi numit curb de nivel a fuciei obiectiv. Distana dintre origine i dreapta (2.41) este . Evident, valoarea maxim a lui d(adic a funciei obiectiv) este obinut atuncicnd are valoarea maxim. Cum soluia optim (x1, x2) satisface att sistemul (2.40) ct i

ecuaia (2.41), este clar c dreapta (2.41) trebuie s aib un punct n comun cu poligonul OABCD

astfel nct s fie maxim. Aceste condiii snt satisfcute evident de coordonatele punctului B;

deci, 1= 1, 2= 2.Se observ din acest exemplu c soluia optim a unei probleme de programare liniareste unul din vrfurile tronsonului soluiilor, proprietatea care, aa cum vom vedea ulterior, este

general. Pentru exemplul considerat aici, tronsonul soluiilor este poligonul OABCDdin fig.4.

Dac schimbm funcia obiectiv (2.39) cu alta este posibil ca soluia optim a problemei s fie un

vrf al poligonului. n acest caz cnd curbele de nivel ale funciei obiectiv snt drepte paralele cu

una dintre laturile poligonului, soluiile optime snt n numr infinit, corespunznd punctelor de

pe latura poligonului paralel cu curba de nivel a funciei obiectiv. De exemplu, pentru problemamaximizrii funciei obiectiv


27/388

27

(1.51) max (x1+x2)

n condiiile (1.49), curbelede nivel

(1.52) x1+x2= d

snt drepte paralele cu latura (BC) i deci soluiile optime snt vrfurile B(1,2), C(2,1) sau orice

punct (x1,x2)interior segmentuluiBC.

Exemplul 2.Pentru problema de programare liniar

(1.53) max (x1+x2), x1-x2 0,

(1.54) 0,5x1+x2 0

x1,x2 0,

x2

,

x1+x2= d

O (0,0) x1

Fig. 1.5

mulimea soluiilor este reprezentat n fig.5; curbele de nivel ale funciei obiectiv (1.53) snt

drepte care au n comun cu tronsonul definit de (1.54) un segment, orict de mare ar fi distana de

la aceste drepte la origin. Prin urmare, funcia obiectiv poate lua valori orict de mari, adic are

valoare optim infinit.

Exemplul 3. Este uor de vzut c, dac la restriciile problemei de programare liniar

(1,48), (1.49) adugm restricia

x1+x2 4,

problema obinut nu are nici o soluie admisibil.

Din cele trei exemple date rezult c o problem de programare liniar are un program

optim (i deci valoarea optim a funciei obiectiv este finit), sau valoarea funciei obiectiv este

infinit, sau nu are programe.

1.3.3. PROGRAME DE BAZ

S considerm un program liniar n forma standard:


28/388

28

(1.55) minc'x,

Ax = b,

x 0,

unde matriceaA cu m linii i ncoloane are rangul egal cu m, adic vectorii ai= (ai1, ..., ain)', 1 i

m, snt liniar independeni. Presupunem n plus c m< ndeoarece, n caz contrar, ar exista osingur soluie admisibil a sistemului (1.55) i optimizarea este banal.

DEFINIIA 1. Vectorul x = (x1, ..., xn)' este numit soluie de baz a problemei (1.55)

dac snt ndeplinite urmtoarele condiii:

1.

vectorulxeste soluie a sistemuluiAx = b;

2. coloanele matriceiAcare corespund componentelor nenule ale vectorului xsnt

vectori liniar independeni.

DEFINIIA 2. Soluia de baz x este numit admisibil dac toate componentele

vectoruluixsnt nenegative4.

DEFINIIA 3. Soluia (admisibil) de baz x este numit nedegenerat dac are exact

m componente nenule i degenerat n caz contrar.

DEFINIIA 4. O matrice ptrat nesingularBformat cu m coloane ale matriceiA

este numit baz.

Fie xBvectorul format cu variabilele asociate coloanelor unei baze Bextras din matricea

A; componentele vectorului xB snt numite variabile de baz. Fie xS vectorul care conine

variabilele nebazice i fie S matricea format cu coloanele rmase din matricea A dup

extragerea bazei B. Sistemul de ecuaii Ax = bpoate fi scris de asemenea sub forma urmtoare:

(1.56) BxB+ SxS= b.

Este clar c fiecrei baze B i corespunde soluia de baz xB= B-1b, xS= 0. nmulind (1.61) la

stnga cu inversa matricei B, obinem

(1.57) xB= B-1b - B-1SxS.

Prin urmare, soluia de baz xB= B-1b, xS= 0 care corespunde bazeiB se poate obine din relaia

(1.57) punndxS= 0.

Dac soluia de baz x este nedegenerat, atunci coloanele matricei A corespunztoare

celor m componente nenule ale lui x formeaz evident o baz. Dac soluia de baz x este

degenerat, atunci existn general mai multe baze crora le corespunde aceastsoluie de baz.

4O soluie admisibil va fi numit de asemeneaprogram.


29/388

29

Importana programelor de baz n programarea liniar va fi pus n eviden de cele

douteoreme care urmeaz.

TEOREMA 1. Dacprogramul liniar (1.55) are un program, atunci el are cel puin un

program de baz.Demonstraie. Fie x un program al problemei (1.55). S notm prin p numrul

componentelor pozitive ale vectorului x. Fra restrnge generalitatea, putem presupune ccele

p componente diferite de zero ale vectorului x snt chiar primele pcomponente, adicx = (x1

. . . , xp,0 , . . . , 0)'.

Dacp= 0, atunci x = 0. Deoarece x= 0este n mod evident o soluie admisibilde baz,

teorema este demonstratn acest caz.

Dacp >0, snt douposibiliti:a)Coloanele a1, . . . , ap ale matricei A, care corespund celor pcomponente nenule ale

vectorului x, snt liniar independente. Prin urmare, x este program de baz pentru (2.46) i

teorema este demonstrati n acest caz.

b)Vectorii a1, . . . , ap snt liniar dependeni. n acest caz, conform definiiei, exist

numereley 1, y 2, ,yp,nu toate nule, astfel nct savem satisfcutrelaia

(1.58) ay

+ + apyp= 0.

Dac notm prin yvectorul cu primele p componente y 1, y 2, ..., yp, iar urmtoarele n p

componente nule, adic y= ( y 1, y 2, . . . , yp, 0 , . . . , 0)', relaia (1.58) se mai poate scrie sub

forma Ay = 0cu y 0. Este clar c avem atunci

(1.59) A(x+y) = Ax + Az = b

pentru orice numr real ; cu alte cuvine x+yeste soluie a sstemului de ecuaii Ax = bpentru

orice numrR . Putem acum determina valori ale lui pentru x+y 0. S notm pentru

aceasta prin I1 mulimea indicilor i,1 i m,pentru careyi> 0 i I2mulimea indicilor i, 1 i

m,pentru careyi < 0. Fie

(1.60) ,-, dac ,

(1.61) ,+, dac .

Este atunci clar c pentru orice pentru care

min ( - 1,2)avem ndeplinit i condiia x+ y 0. Putem alege acum o valoare 0 pentru care vectorul x+


30/388

30

0y s aib cel multp1componente pozitive. ntr-adevr, putem lua 0 = - 1 dac 2 = + i

0= 2 dac 1 = - .

Coloanele corspunztoare componentelor pozitive ( n nmr de cel mult p 1) ale

programului x + 0y pot fi sau liniar independente ( cazul (a) studiat mai sus) sau liniar

dependente. nultimul caz se reia raionamentul de mai sus; ntr-un numr finit de etape vomajnge la caul (a) i vom obine deci un program de baz.

TEOREMA 2.Dac problema de programare liniar (1.55) are un program optim,

atunci are un program optim de baz.

Demostraie. Fie x un program optim care are primele p component positive. Ca i n

teorema precedent, pentru p = 0 rezultatul se obine imediat. Dac p > 0, atunci avem de

considerat dou cazuri:(a)

Vectorii a1, a

2, , apsnt dependeni. n acest caz demostraia este determinat

deoarece x este chiar program de baz.

(b) Vetorii a1, a

2, , ap snt liniar dependeni. Ca i n demonstraia teoremei

precedente, rezult c exist un vector y = (y1, y2, , yp, 0, , 0)', astfel nct s avem

ndeplinit condiia Ay = 0cu y 0i deci x+ yeste soluie a sistemului de ecuaii Ax = b

pentru orice numr real . Dac n plus alegem sufficient de mic, adic, mai precis, min (-1, 2), rezult c x + y este chiar program; 1 i 2 snt numerele definite mai sus, n

demostraia teoremei precedente, de (1.60) i (1.61).

Deoarece xeste program optim i x+ y este program, rezult

c'x c'x + c'y,

de unde obinem c'y 0.Nu putem avea c'y 0, deoarece, alegnd de semn contrar lui c'y,

am obine c'y< 0. Rezult atunci c c'y = 0, ceea ce arat c x+ y este de asemenea cu o

unitate numrul componentelor positive ale programului optimx+ y, alegnd n mod convenabil

valoarea lui ( = 0). Dac un numr finit de etape ajungem la cazul (a), adic obinem un

program de baz optim.

1.3.4. O METOD DE REZOLVARE A PROBLEMELOR

DE PROGRAMARE LINIAR

Din rezultatele obinute mai sus rezult c pentru aflarea programelor optime putem

proceda n modul urmtor:

(a)

Determinm toate soluiile de baz ale sistemului de mecuaii cu nnecunoscute

(m n), dintre care unele sntadmisibile, adic snt programe de baz.


31/388

31

(b) Comparm valorile funciei obiectiv pentru aceste programe de baz i

determinm soluia (sau soluiile) optim.

Exemplu.S rezolvm prin metoda expus mai sus problema de programare liniar:

max (x1+x2),

4x1+ x2 16,

x1+ 3x2 15,

x1,x2 0.

Introducnd variabilele ecart y1, y2 0, obinem forma standart a acesteio probleme de

programare liniar

max (x1+x2),

4x1+ x2+y1 = 16,x1+ 3x2+y2 = 15,

x1,x2,y1,y2 0.

Numrul maxim al bazelor corespunztoare matricei probleme de programare liniar este i corespunde numrului combinrilor de m = 2 coloane ale matricei A care pot fi selectate

pentru formarea unei baze. Soluiile de baz ale problemei noastre snt date ntabelul de mai jos.

Acest tabel conine de asemenea valorile funciei obiectiv care corespund acestor soluii de baz.

Valoarea maxim a funciei obiectiv este egal cu 7 i programul optim estex1= 3,x2 = 4.

Variabilele de baz Soluia de baz Valoarea funciei obiectiv(x1,x2) (3, 4) 7

(x1,y1) (15, -44) -

(x1,y2) (4, 11) 4

(x2,y1) (5, 11) 5

(x2,y2) (16, -33) -

(y1,y2) (16, 15) 0

Trebuie s observm aici c numrul maxim al soluiilor de baz (adic n!/m!(n - m)!)

crete foarte repede odat cu creterea lui mi n, ceea ce face dificil aplicarea acestei metode.

BIBLIOGRAFIE:

Mircea Malia, Corneliu Zidroiu, Matematica organizrii, ediia a doua, Editura

Tehnic, Bucureti, 1975.


32/388

32

CAPITOLUL II : MODELE TIPICE DE PROGRAMARE

Vom ncepe expunerea sistematic a teoriei programrii cu examinarea unei serii de

scheme (modele) tipice pe care le utilizeaz aceast teorie pentru rezolvarea unor probleme din

domeniul economiei. Cu acest prilej, ne vom limita numai la formularea problemelor, fr a

prezenta metodele de rezolvare numeric a lor. Scopul pe care vi-l propun aici este de a nfia

domeniul de aplicare a teoriei programrii, fr a intra n tehnica utilizrii ei.

2.1. PROBLEMA INTINERARULUI NCHIS5

S presupunem c pe o hart snt notate patru orae: , , i . n oraul se aflsediul unei firme comerciale, de unde aceasta trimite un voiajor comercial cu sarcina de a vizitaoraele , i i de a se rentoarce n oraul . Traseul voiajorului poate fi diferit, dar ntructnumrul oraelor este egal cu 4, numrul de ,,ordini (moduri de succesiune) n care acestea pot

fi vizitate6este egal cu . Este lesne de artat c n cazul n care numrul deorae este egal cu ,numrul de trasee diferite reprezint .

Problema const n alegerea dintre toate traseele posibile a acelui traseu care face s fie

minime cheltuielile de transport ale voiajorului comercial. Cu acest prilej se presupune ccheltuielile de transport , ntre dou localiti luate n mod arbitrar, sntcunoscute. Fr a micora gradul de generalitatea problemei, se poate considera c cheltuielile

de transport dintr-o localitate n alta snt proporionale cu distana dintre ele. n acest caz,

problema se reduce la aflarea celui mai scurt traseu al voiajorului comercial.

Cel mai simplu, aceast problem poate fi rezolvat prin ,,metoda ncercrilor i eroilor,

bazat n cazul de fa pe calcularea cheltuielilor voiajorului comercial pentru transportul pe

fiecare traseu posibil. S ncercm s soluionm problemapentru patru orae; s admitem ccheltuielile de trasport (exprimate, de pild, n zloi) ntre dou orae oarecare proporionale cu

distanele dintre aceste orae snt egale cu numerele nscrise pe schia i n tabelul (matricea)

cheltuielilor, pe care le prezentm mai jos:

5 n literatura american, aceast problem poart denumirea de problema voiajorului comercial ( the travellingsalesman problem).6n cazul nostru, ,,ordinile de vizitare a oraelor pot fi urm toarele: ; ; ; ; i .


33/388

33

A C D

A

B

C

D

01214

23

12017

25

14170

30

232530

0

B

25 12 17

14

A

23

D 30 C

Fig. 2.1

Cheltuielile de transport pe diferite trasee snt urmtoarele:

, , .Este lesne de neles c cheltuielile de trasport n sens contrar, adic pe celelalte trei

trasee: , i snt de asemenea egale, respectiv cu 82, 81 i 79.Aceasta se explic prin faptul c n exemplul nostru tabelul cheltuielilor este simetric n raport cu

diagonala sa principal. Aceasta nseamn c, de pild, cheltuielile de trasport pe traseul

snt

egale cu cheltuielile de trasport n sens contrar, adic pe traseul .Din calculul pe care l-am prezentat rezult c traseele i snt traseeoptime deoarece cu acest prilej scopul propus se realizeaz cu cheltuieli minime de mijloace.

Dar utilizarea acestei metode de soluionare a problemei itinerariului nchis este posibil

numai n cazul n care numrul de orae pe care trebuie s le viziteze voiajorul comercial este

mic. ntr-adevr, dac avem, de pild 12 orae, numrul itinerarelor posibile reprezint

i deci chiar n condiiile matricei simetrice a cheltuielilor ar trebui s se efectueze

, adic aproape 20 de milioane de calcule. Este limpede c utilizarea metodei ,,ncercrilor ieroilor pe care am nfiat-o mai nainte devine n asemenea cazuri practic imposibil. De

aceea este necesar s se gseasc metode care s permit s se soluioneze aceast problem n

mod simplificat7.

S ncercm acum s formulm problema itinerarului nchis, n limbaj matematic.

7Problema voiajorului comercial n forma sa general nu a fost rezolvat pn n prezent. Exist metode de

rezolvare a ei pentru cazurile n care matricea cheltuielilor este simetric (

,pentru

) i

metode aproximative de rezolvare, pentru cazurile n care matricea cheltuielilor este nesimetric. Unii autori care s -au ocupat de aceast problem au emis ipoteza c nu existo metod universal de rezolvare a problemei voiajoruluicomercial n form general.


34/388

34

S admitem c s-au stabilit orae pe care trebuie s le viziteze un voiajor comercial ic cheltuielile de transport din oraul n oraul snt prezentate n matricea:

.

Problema const n determinarea traseului optim al voiajorului comercial, adic a unui

traseu n care cheltuielile de transport din oraul numrul 1 prin toate celelalte orae i cu

rentoarcerea n oraul numrul 1 s fie minim.

S notm cheltuielile pentru etapele succesive ale cltoriei dintr-un punct n altul cu.Din condiiile problemei rezult c indicele poate lua succesiv valorile: , iarindicele

valorile

. Indicii

pot reprezenta permutri ale

numerelor .Cheltuielile totale ale voiajorului comercial pentru cltoria pe un anumit traseu pot finotate n forma urmtoare: ,unde indici i ai elementelor acestei sume formeaz una din grupele de numere posibile,stabilite mai sus: i .

Dac, de pild,

itraseul trece succesiv prin oraele notate cu

, atunci

cheltuielile totale ale voiajorului comercial snt: .Problema se reduce la aflarea acelei permutri de numere , pentrucare: . .

Din aceast formulare matematic a problemei rezult n mod limpede c este foartedificil s se gseasc o metod general de rezolvare a ei.

nc din acest prim exemplu de problem problema voiajorului comercial se

contureaz o anumit schem dup care se formuleaz problemele de teorie a programrii.

nainte de toate, observm c datele problemei (n exemplu nostru cheltuielile de trasport dintr-

un ora n altul) snt prezentate sub form matricial. n afar de aceasta, exist o anumit funcie

obiectiv , care trebuie fcut minim sau maxim cu ajutorul unei alegeri corespunztoare avariabilelor din problem.

n problema voiajorului comercial, variabilele au un caracter specific. Ele snt diverse


35/388

35

permutri ale numerelor , care repezint numerele oraelor pe care trebuie s leviziteze voiajorul comercial. n afar de aceasta, variabilele trebuie s ntruneasc unele condiii

suplimentare (aa-numitele condiii auxiliare); n cazul nostru, permutrile indicelui alelementelor funciei obiectiv ncep cu

, iar permutrile indicelui

se termin cu

.

n sfrit, trebuie s remarcm c schema problemei voiajorului comercial (lucru valabil ipentru alte probleme pe care le vom examina n continuare) se aplic i n alte domenii ale

programrii, care aparent nu au nimic comun cu schema care a servit la construirea modelului

examinat.

2.2. PROBLEMA DE

TRANSPORT

n literatura referitoare la teoria programrii, problema de transport este prezentat n

diverse variante; una dintre variantele cele mai simple o vom examina n paragraful de fa.

S admitem c exist trei ntreprinderi productoare (de pild, de maini agricole), care

aprovizioneaz cinci puncte de desfacere (de pild, cooperative steti).

ntreprinderiproductoare :

200 500 300

100 200

150 50

100 400

Puncte de

desfacere

Fig. 2.2

Fiecare ntreprindere are un anumit volum al produciei, s presupunem 200, 500 i 300 de

uniti i exist o anumit regul de repartiie a produciei totale (1 000 de uniti) ntre punctele

de desfacere (vezi schema). Se pune problema cum trebuie expediat producia diferitelor

ntreprinderi la punctele de desfacere, n aa fel nct cheltuielile de transport s fie minime. Dac

admitem cu acest prilej c cheltuielile de transport snt proporionale cu distana dintre

ntreprindere i punctele de desfacere, atunci problema const n minimizarea volumului

transporturilor, n tone-kilometri8.

8Aceast problem poate fi formulat i n alt mod. Poate fi vorba nu de determinarea numrului minim de tone-

1 2 3 4 5

1 2 3

2 3 4 51


36/388

36

Uneori rezolvarea problemei poate fi simpl, bazndu-se pe metoda ,,ncercrilor i

eroilor, ndeosebi etunci cnd intr n joc un numr mic de productori i puncte de desfacere.

Pe msur ce numrul acestora se mrete, problema se complic.

S examinm aceast problem n forma sa general i s -o formulm n limbaj

matematic.

S presupunem c numrul de ntreprinderi care fabric produsele respective reprezint, iar numrul punctelor de desfacere a acestor produse este egal cu . S notm cu cantitatea de produse n tone, expediat n decurs, s zicem, deun andin ntreprinderea , n punctul de desfacere. Mrimile formeaz matricea repartizrii

produciei

...

... ..................................... ... S admitem pentru simplificare c . Aceasta nseamn c transporturile de

produse merg ntr-un singur sens (de la ntreprindere spre punctele de desfacere), adic nu exist

restituiri ale unei pri a produselor de la punctele de desfacere la ntreprindere.

S observm c rndurile matricei repartiiei reprezint producia expediat din

ntreprinderea respectiv spre diferitele puncte de desfacere, iar coloanele matricei reprezintcantitatea de produse obinute de punctul de desfacere respectiv de la diferitele ntreprinderi.

Unele elemente ale matricei repartiiei pot fi, evident, egale cu zero. Dac, de pild, ,aceasta nseamn c ntreprinderea n general nu-i expediaz producia sa spre punctul dedesfacere.

S admitem mai departe c cheltuielile unitare pentru transportul produciei de la

ntreprinderi la punctele de desfacere snt cunoscute. S presupunem c aceste cheltuieli

formeaz urmtoarea matrice a cheltuielilor:

kilometri, ci de minimizarea numrului de vagoane de cale ferat angajate pentru transport, a numrului deautocamioane .a.m.d.

... ... ..................................... ...


37/388

37

Mrimea reprezint cheltuielile de transport al unei tone de produse de lantreprinderea la punctul de desfacere. Dac presupunem c cheltuielile de transport snt

proporionale cu distana pe care se efectueaz transportul, atunci dup cum s-a artat mai

nainte, se poate admite c elementele matricei cheltuielilor exprim distanele dintre punctele

respective. Din condiiile problemei rezult n mod evident c toate elementele matriceicheltuielilor satisfac condiia .

S admitem mai departe c fiecare ntreprindere are o anumit capacitate de producie, de

pild anual, i c necesitile anuale ale diferitelor puncte de desfacerereprezint . Atunci, dup cum lesne ne putem convinge, obinem urmtoare leecuaii9:

(2.1)

(2.2) .S observm c numrul de ecuaii (2.1) i (2.2) reprezint . Dar dac avem nvedere faptul c producia total a tuturor ntreprinderilor este egal cu cantitatea total de

produse, obinut de punctele de desfacere, adic , atunci printre cele ecuaii(2.1) i (2.2), numai snt independente. Aceasta nseamn c dac snt date ecuaii ale sistemelor (2.1) i (2.2), atunci ecuaia a acestui sistem poate fi aflat ca ocombinaie a celor

ecuaii date.

Deoarece cheltuielile de transport ale produselor de la ntreprinderea la punctele dedesfacerereprezint , cheltuielile totale pentru transportul produselor de la ntreprinderila punctele de desfacere reprezint: .

Problema const n determinarea necunoscutelor (a elementelor matricei repartiiei),care s satisfac condiia:

(2.3)

,

pentru care cheltuielile snt minime, adic:(2.4) ,fiind totodat satisfcute condiiile suplimentare exprimate prin ecuaiile (2.3) i (2.4).

S examinm mai amnunit schema matematic prezentat a problemei de transport. Pe

baza acestui exemplu observm n primul rnd c problemele de programare se reduc la

maximizarea sau minimizarea unei anumite funcii, numit funcie obictiv i c pentru fiecare

program care urmrete minimizarea funciei obiectiv se poate ntocmi un aa-numit program

9Simbolul nseamn c nsumarea se extinde asupra tuturor elementelor cu indicele . Aceasta este forma

prescurtat a simbolului .


38/388

38

dual, care maximizeaz o alt funcie; invers, pentru programul care maximizeaz funcia

obiectiv se poate ntocmi un program dual care minimizeaz o alt funcie.

nlocuirea unui program dat printr-un program dual se efectueaz prin transformarea

corespunztoare a funciei obiectiv. Dac, de pild, n problema de repartiie pe care o examinm

introducem calculul profitului unui trust care se ocup cu producia i distribuia unui produs dat,atunci profitul total al acestui trust dac admitem c preurile i cheltuielile specifice de

producie, de transport etc. snt constante , ar depinde de programul de repartiie a produciei

diferitelor ntreprinderi ntre diferitele puncte de desfacere. Nivelul maxim al profitului se atinge,

n aceste condiii, prin minimizarea cheltuielilor de transport. Minimizarea acestor cheltuieli este

echivalent cu maximizarea profitului.

Aceast propritate a programrii, numit dualitateeste o proprietate general a schemelor

de programare. Ea decurge din existena a dou variante de aplicare a principiilor economicitii.Acum s examinm mai ndeaproape condiiile (2.1), (2.2) i (2.3)care creeaz anumite

restricii pentru variabilele . S remarcm n primul rndfaptul c condiiile(2.1) i (2.2),prezentate n form de egalitate, pot fi nlocuite prin inegaliti.

Atunci condiia ar nsemna, de pild, c nu este obligatoriu ca ntreaga producie antreprinderii s fie expediat spre punctele de desfacere. n acest caz, ar fi vorba de problema,,stocurilor pe care am evitat-o pentru a nu complica problema pe care o examinm. n mod

analog, condiia nseamn c la punctele de desfacere se pot crea stocuri.Condiiile (2.1) i (2.2),sub form de egaliti sau inegaliti, prin caracterul i sensul lorsnt definite, de obicei, ca nite condiii (relaii) de echilibru10, iar restriciile de tipul (2.3) se

numesc condiii de nenegativitate (de extrem)11. Acest ultim termen este legat de reprezentarea

grafic a modelelor de programare de care ne vom ocupa mai jos.

n orice problem de programare joac un rol deosebit condiiile de echiliru, prezentate

sub form de ecuaii, deoarece ele limiteaz numrul necunoscutelor pe care le putem liber alege.

Rezolvnd, de pild, o problem de repartiie oarecare, trebuie s aflm

necunoscute

. Dar ntruct aceste necunoscute trebuie s satisfac ecuaii de echilibru, de aici ar rezulta c avem libertatea de a alege numai necunoscute. Dar calculnd gradele de libertate n acest exemplu concret trebuie s introducem o

anumit corecie. ntr-adevr, dup cum s-a artat mai sus, din nsi formularea problemei

10n original, warunki bilansoweN.T.

11

n original, warunki brzegowecondiii de delimitare, de extrem; am preferat ns expresia mai direct condiiide nenegativitate N.T.


39/388

39

rezult c dintre cele ecuaii de echilibru (2.1) i (2.2), snt independente numai . De aceea, n ultim analiz, putem alege numai necunoscute,ceea ce exprimm atunci cnd spunem c avem grade de libertate.

Ecuaiile de echilibru (2.1) i (2.2),precum i condiiile de nenegativitate determin, ca s

ne exprimm n limbaj geometric, domeniul soluiilor admisibile, care are grade de libertate. Dintre aceste soluii admisibile se aleg acele soluii care fac minim (saumaxim) funcia obiectiv.

Vom remarca n continuare c, n exemplul examinat, att ecuaiile de echilibru (2.1) i

(2.2), ct i funcia obiectiv (2.4) snt relaii liniare n raport cu necunoscutele . nasemeneacazuri, problema cercetat face parte dinprogramarea liniar. Dac funcia obiectiv sau relaiile

de echilibru snt neliniare, atunci problema face parte din programarea neliniar.

La prima vedere s-ar prea c problemele de programare liniar se rezolv mai uor dectproblemele de programare neliniar. Dar aceast prere nu corespunde realitii. Este adevrat c

n programarea liniar este mai uor s se formuleze matematic problema, ns calculele de

rezolvare snt, de regul, mai dificile dect n cazul problemelor de programare neliniar. Aceasta

se datorete mai ales faptului c n programarea liniar nu este cu putin s se aplice calculul

diferenial pentru aflarea valorilor extreme ale funciei obiectiv.

2.3. PROBLEMA DE TRANSPORT ALUI KOOPMANS

S examinm o alt variant, istoricete mai veche, a problemei de transport, de care,

pentru prima dat, s-a ocupat cunoscutul economist T. C. Koopmans12. Problema studiat de

Koopmans se refer la trasporturile de materiale de rzboi, efectuate n periada celui de-al doilea

rzboi mondial, din S.U.A. n Anglia i retur. Dar ntruct cantitile de produse transportate n

cele dou sensuri erau diferite, navele circulaude multe ori goale sau incomplet ncrcate. Avnd

n vedere i faptul c transporturile pe mare ale aliailor se aflau sub ameninara submarinelor i

a aviaiei germane se punea problema asigurrii unei asemenea utilizri a mijloacelor de

transport nct s se reduc la minimum capacitatea de transport neutilizat (n tone -kilometri) i

implicit s se reduc pierderile de nave.

Dei istoricete problema de transport a lui Koopmans a avut un caracter tactico -militar,

12 T. C. Koopmans, Optimum Utilization of the Transportation System, n Econometrica, 1949 (Supplement).

Vezi, de asemenea, T. C. Koopmans, S. Reiter, A Model of Transportation, n culegerea Activity Analysis of

Production and Allocation, New York, 1951. Problema de transport a lui Koopmans este examinat, de asemenea,n cartea O. Lange, Wstep do ekonometrii, Varovia, 1961, p. 284 i urm.


40/388

40

ea poate fi considerat dup cum a fcut mai trziu nsui Koopmans i ca o problem

economic. Fapt este c reducerea capacitii de transport neutilizate a navelor mrete

rentabilitatea transporturilor maritime. Firete c soluia optim a acestei probleme pe plan

mondial ar fi posibil numai n cazul n care ar exista o form oarecare de administrare

internaional a navelor i de dirijare a transporturilor maritime. n sfrit, trebuie s adugm cmodelul lui Koopmans poate s-i gseasc aplicare nu numai n transportul maritim, dar i n

transportul feroviar, n cel auto, precum i n alte domenii similare.

Vom da formularea matematic a acestei probleme.

S presupunem c exist porturi din care se expediaz i n care sosesc ncrcturi. Snotm cu un volum dat de mrfuri expediate (exprimate, de pild, n tone), iar cu unvolum dat de mrfuri care se aduc n decursul unei anumite perioade n portul

.

S admitem c se cunosc i distanele i dintre porturi (exprimate, de pild, n kilometri). Acesteporturi pot fi notate sub forma unei matrice

S notm cu

volumul efectiv de mrfuri care urmeaz s fie transportate din portul

n portul, iar cu capacitatea de ncrcare a vaselor care circul din portul n portul.Mrimile i (pentru ) se pot nota, de asemenea, sub forma unor matrice:

Necunoscutele din problem snt mrimile , adic capacitatea dencrcare a navelor ce vor fi trimise din portul n portul.

Funcia obiectiv va stabili mrimea ,,transporturilor goale, adic mrimea tonajuluineutilizat al navelor. Mrimea tonajului neutilizat pe traseul dintre portul i portul vareprezenta ; ca atare, mrimea capacitii de transport neutilizate pe toate traseele (ntone-kilometri) va reprezenta: .

... ... . ...

... ... .

...

... ... .

...


41/388

41

Problema examinat const n a face ca .

Condiiile auxiliare pe care trebuie s le satisfac necunoscutele pot fi notate subforma urmtoarelor ecuaii:(2.5) i

(2.6) .Ecuaia (2.5) ne arat c tonajul total al navelor trimise dintr-un port oarecare n toate

celelalte porturi trebuie s fie egal cu

. n mod analog, ecuaia (2.6) arat c tonajul total al

navelor sosite ntr-un port oarecaredin toate celelalte porturi trebuie s fie egal cu .Trebuie s menionm c ntocmai ca n problema de repartiie ( 4)dintre cele ecuaii de echilibru (2.5) i (2.6), numai ecuaii snt independente. Aceasta se explic

prin faptul c , adic tonajul total al navelor care pleac din toate porturile este egalcu tonajul total al navelor care sosesc n toate porturile. ntruct problema are ,necunoscute ,13 dar exist ecuaii de echilibru independente,numrul gradelor de libertate reprezint

.

n afar de relaiile de echilibru exist de asemenea condiii de nenegativitate ce pot fi

notate sub forma urmtoare:

(2.7) ,n care condiia nseamn c tonajul vaselor care pleac din portul spre portultrebuie s fie mai mare sau egal cu cantitatea de mrfuri care urmeaz a fi transportat pe acest

traseu.

Aceasta este formularea matematic a modelului lui Koopmans. Din aceast formulare se

vede c modelul lui Koopmans este o problem de programare liniar, deoarece att funcia

obiectiv , ct i ecuaiile de echilibru (2.5) i (2.6) snt relaii liniare n raport cu necunoscutele . Dar aceast problem poate fi uor transformat ntr-un model de programare neliniar dac,de pild, n locul distanei ntre porturi, introducem cheltuielile de transport cu meniunea caceste cheltuieli nu cresc direct proporional, ci mai lent dect distanele. Aceast problem poate

13Numrul de necunoscute

n cazul general este egal cu

, ns

este egal cu zero, dac

, adic dac mrimile se afl pe diagonala matricei tonajului navelor.


42/388

42

fi uor nlocuit printr-o problem dual, lund ca funcie obiectiv rentabilitatea total a tuturor

transporturilor pe plan mondial. n acest caz, problema de minimizare a tonajului neutilizat al

navelor ar fi nlocuit printr-o problem de maximizare a rentabilitii totale a transporturilor.

2.4. PROBLEME DE REPARTIIE

Problema de transport intr n clasa vast a problemelor de programare, care se numesc

probleme de repartiie. Vom elucida caracterul general al acestor probleme lund ca exemplu

repartizarea unor maini-unelte n vederea executrii unor anumite operaii elementare de

prelucrare a unor piese.

S presupunem c avem la dispoziie maini-unelte pentru achiereametalelor care potexecuta operaii diferite (strunjire, gurire, lefuire etc.) i c cu ajutorul acestor maini -uneltetrebuie s prelucrm o serie de piese (de pild, s executm anumite piese de maini). Problema

const n a repartiza aceste piese la diferite maini-unelte n aa fel nct efectul total al

prelucrrii s fie maxim.

S notm productivitatea mainii-unelte pentru executarea operaieicu . Aceastproductivitate trebuie ntr-un fel msurat, de pild n uniti bneti i atunci

reprezint

mrimea, n expresie bneasc, a efectului funcionrii mainii-unelte pentru executareaoperaiei, de pild n decursul unei ore. Mrimile pot fiprezentate sub forma unei matrice a productivitii ... ...

.....................................

...

Necunoscute n aceast problem snt mrimile , carestabilesc ct timp trebuie s execute maina-unealt operaia. Aceste necunoscute, al crornumr se ridic la mn pot fi prezentate sub forma matricei repartizrii pe operaii: ... ...

.....................................

...

Mrimea efectului funcionrii mainii-unelte la executarea operaieieste determinatde produsul dintre timpul de funcionare al acestei maini-unelte i productivitatea ei: .


43/388

43

Prin urmare, mrimea total a efectului funcionrii tuturor mainilor-unelte va reprezenta . Problema const tocmai n a face maxim funcia obiectiv astfel determinat: .S precizm condiiile auxiliare ale problemei. Vom meniona n primul rnd faptul c

fiecare main-unealt , n decursul perioadei n care examinm ntregulproces (o zi, o sptmn .a.m.d.) are un anumit timp maxim de funcionare . De aceea, timpultotal de funcionare al mainii-unelte, pentru executarea unei operaii oarecare , trebuie s reprezinte . n felul acesta vom obine primele ecuaii de echilibru ale

problemei

(2.8) .Ecuaia de echilibru (2.8) poate fi nlocuit cu inegalitatea de forma

(2.8) ,dac admitem posibilitatea utilizrii incomplete a timpului maxim de funcionare a mainilor-unelte.

Un alt grup de condiii auxiliare se noteaz sub forma ecuaiei de echilibru

(2.9) ,care arat c fiecare operaieipoate fi executat la oricare dintre mainile-unelte, ns dup unanumit timp, dinainte stabilit, egal cu

.

Aadar, funcia obiectiv trebuie s fie maximizat cu respectarea condiiilor (2.8) i(2.9), care n total snt n numr de . Este lesne s constatm c, i n acest caz, numrulecuaiilor de echilibru independente este mai mic cu o unitate i reprezint . ntr-adevr, din condiiile problemei rezult c timpul total de funcionare a tuturor mainilor-unelte,

pentru executarea tuturor operaiilor, trebuie s fie egal cu:

1) suma timpului maxim de funcionare a tuturor mainilor-unelte, adic i

2)

suma timpului necesar pentru executarea tuturor operaiilor, adic .Din ultimile dou ecuaii rezult c .Aadar, dac se dau ecuaii de echilibru (2.8) i (2.9), atunci din ele se poate

determina i ecuaia de echilibru .ntruct n problema examinat exist necunoscute i ecuaii de echilibru

independente, problema are

grade de libertate.

Condiiile de extrem ale acestei probleme arat c necunoscutele care caracterizeaz

repartiia operaiilor nu pot fi negative:


44/388

44

(2.10) .Schema prezentat a repartiiei mainilor-unelte pentru executarea diferitelor operaii

poate fi aplicat n mod analog i n alte probleme de teorie a programrii, de pild la

repartizarea suprafeelor cu o fertilitate diferit pentru diferite culturi (gru, sfecl, cartofi etc.)

sau n problema repartizrii lucrtorilor de calificare diferit (i implicit cu o productivitate amuncii diferit) la executarea diferitelor lucrri.

n problema de repartiie a terenurilor ntre diferite culturi, necunoscutele vorreprezenta numrul de hectare destinate pentru cultura .Mrimile vor reprezenta suprafaa total de teren , iar planul de nsmnri cu cultura.i n acest caz, producia la hectar a culturii pe terenultrebuie exprimat n uniti bneti,

pentru ca ele s poat fi comparabile i pentru ca s se poat construi funcia obiectiv, care n

cazul de fa va fi venitul total maxim de pe terenurile respective.

i aici se poate elabora un program dual, presupunnd, de pild, c venitul de pe

terenurile respective este dinainte determinat i este constant, dup ce am cercetat ca suprafee

trebuie s afectm pentru diverse culturi, n aa fel nct cheltuielile pentru ntreinerea acestor

culturi s fie minime.

n problema de repartiie a lucrtori pentru executarea a lucrri diferite,necunoscutele

vor arta ce numr de uniti de timp (de pild, ore) este ocupat lucrtorul

cu

efectuarea lucrrii. Productivitatea muncii va reprezenta efectul muncii lucrtorului (nexpresie bneasc), care execut lucrarea ntr-o unitate de timp. Problema const n aflareamrimii , adic a unei asemenea repartizri a lucrtorilor pediferite operaii nct valoarea lucrrii executate de ei s fie maxim.

Aici este deosebit de interesant cazul cnd , adic atunci cnd numrul diferitelorcategorii de lucrri este egal cu numrul de lucrtori. Aceast problem ar putea fi definit c u

ajutorul dictonului om potrivit la loc potrivit.

solutionarea matematica a probl economice

Documents