cercetari operationale

MELNIC LUCIA ZGAN REMUS CHIRCOR MIHAEL

CERCETRI OPERAIONALE

FUNDAMENTAREA DECIZIILOR N MANAGEMENTUL SISTEMELOR DE PRODUCIE

2004

2

CUPRINS

1. INTRODUCERE

1.1. Scurt istoric al evoluiei tiinei Cercetare Operaional 1.2. Teoria Deciziei i Cercetare Operaional 1.3. Modelarea matematic n Cercetarea Operaional

2. PROGRAMARE LINIAR 2.1. Probleme de programare liniar 2.1.1. Formularea problemei de programare liniar 2.1.2. Forme ale problemei de programare liniar 2.1.3. Modelul matematic al problemei de programare liniar 2.2. Consideraii generale privind problemele de programare liniar 2.2.1. Soluii i fundamente ale problemei de programare liniar 2.2.2. Baze ale problemei de programare liniar 2.2.3. Interpretarea geometric a problemei de programare liniar 2.3. Metoda Simplex

2.3.1. Fundamente teoretice n aplicarea metodei Simplex

2.3.2. Algoritmul simplex primal

2.3.3. Metode de determinare a unei soluii de baz iniiale 2.3.4. Interpretarea economic a algoritmului simplex primal 2.4. Dualitatea n programarea liniar 2.4.1. Problema dual. Fundamente teoretice 2.4.2. Algoritmul simplex dual

2.4.3. Interpretarea economic a dualitii

3. PROGRAMAREA LINIAR DE TIP TRANSPORT 3.1. Formularea unei probleme de transport

3.2. Exemple de probleme de tip transport

3.3. Determinarea unei soluii de baza iniiale a problemei de transport 3.4. Metoda de determinare a soluiei optime pentru probleme de transport.

Metoda potenialelor.

3

4

5

7

7

7

9

12

16

16

20

22

26

26

28

35

39

41

41

45

49

53

53

55

57

59

Cercetri operaionale- Fundamentarea deciziilor n managementul sistemelor de producie

3

4. ELEMENTE DE TEORIA GRAFURILOR

4.1. Fundamente n teoria grafurilor

4.1.1. Noiunea de graf 4.1.2. Orientare i neorientare n graf

4.1.3. Drumuri i circuite n graf 4.1.4. Lanuri i circuite n graf 4.2. Matrici ataate grafurilor 4.2.1. Matricea arcelor (conexiunilor directe)

4.2.2. Matricea drumurilor (conexiunilor totale)

4.2.3. Descompunerea grafului n componente tari conexe

4.3. Drumuri hamiltoniene n graf

4.4. Drumuri de valoare optim n graf 4.5. Cuplaje. Probleme de repartiie (afectare)

5. TEHNICA DIAGRAMELOR DE TIP REEA 5.1. Generaliti privind modelarea prin reele

5.2. Metoda drumului critic (Critical Path Method - C.P.M.)

5.3. Metoda potenialelor (Metro Potential Method - M.P.M.) 5.4. Metoda PERT (Program Evaluation and Review Technique)

5.5. Tehnica GERT (Graphical Evaluation and Review Technique)

6. ELEMENTE DE TEORIA DECIZIEI

6.1. Procesul i sistemul decizional al ntreprinderii 6.2. Utiliti decizionale 6.3. Optimizarea deciziilor n condiii de certitudine 6.3.1. Metoda utilitilor globale 6.3.2. Metoda Electre

6.3.3. Metoda Ledear-ului

6.4. Optimizarea deciziilor n condiii de risc

BIBLIOGRAFIE

64

64

64

69

70

71

71

73

75

78

87

93

97

97

99

106

108

111

114

114

117

121

121

121

122

123

131

Cercetri Operaionale- Fundamentarea deciziilor n managementul sistemelor de producie

3

CAPITOLUL 1 INTRODUCERE

1.1. Scurt istoric al evoluiei tiinei Cercetare Operaional Cercetarea operaional ca tiin a aprut ctre sfritul primei jumti a secolului

nostru i s-a dezvoltat spectaculos n special n ultimii ani, n strns legtur cu tiina organizrii i conducerii, teoria sistemelor, cibernetica, informatica i analiza sistemelor.

coala clasic are marele merit al abordrii unui domeniu nou, considerndu-se pionier a organizrii tiinifice (F.W. Taylor-1900, H.L.Gantt-1901, A.Fayol-1915) i aceasta pune pentru prima dat problema abordrii raionale a mecanismului funcionrii unei ntreprinderi.

n perioada urmtoare se lrgete considerabil problematica organizrii i conducerii, iar aspectele informaional-decizionale (pn atunci ignorate) i aspectele relaiilor umane dau un alt sens abordrii mecanismului funcionrii ntreprinderii.

Cercetare operaional exista naintea declanrii celui de al doilea rzboi mondial prin lucrrile elaborate de Erlang (1917) firele de ateptare, Harrris (1915) gestiunea tiinific a stocurilor, Vorra (1931) rennoirea echipamentelor.

Utilizarea cercetrii operaionale n practic era dificil de realizat deoarece din punct de vedere intelectual exista o anumit aversiune fat de modele i de caracterul descriptiv al tiinei, iar din punct de vedere material datorit complexitii mici a organizailor i talia relativ modest a ntreprinderilor din aceea perioad, investiiile n mijloace de calcul eficace, respectiv a ordinatoarelor nu era justificat.

n ceea ce privete procesele de decizie, pentru prima oar se pune n mod riguros i pe scar larg problema gsirii unor soluii optime sau apropiate de cele optime, n marea diversitate de probleme organizatorice i de conducere.

Prima aplicaie a cercetrii operaionale moderne la scar larg o constituie aplicarea regulilor definite de Sir Blackett n timpul celui de al doilea rzboi mondial cu deosebit succes n Anglia i care a debutat n 1937.

Termenul de Cercetare Operaional (Operational Research)a fost utilizat pentru prima dat n 1939, fiind legat de contribuia oamenilor de tiin la utilizarea eficient a radiolocatoarelor n sistemul aprrii antiaeriene al Angliei.

n S.U.A. ptrunderea tiinei cercetrii operaionale (Management Science) n dezvoltarea problemelor de conducere a industriei se datoreaz celei de-a doua revoluii industriale i posibilitilor de comercializare a calculatoarelor electronice.

n prezent, mai mult de jumtate din firmele americane au sau folosesc specialiti n cercetarea operaional.

n 1953 s-a format Societatea American de Cercetri Operaionale, iar n 1957 s-a constituit Federaia Internaional a Societilor de Cercetri Operaionale. Au aprut reviste i s-au introdus cursuri i seminarii de cercetare operaional att n S.U.A. ct i n alte ri ale lumii.

n practic, ntreprinderea poate fi privit ca un sistem ale crui elemente componente (oameni, capital, materiale, informaie) sunt intercorelate prin fluxuri materiale, informaionale i energetice ce au un comportament orientat spre atingerea unor obiective precise.

Cercetrile operaionale au consacrat n domeniul optimizrii deciziei, un mod de abordare tiinific asupra problemelor ce intervin n cadrul unei ntreprinderi industriale i totodat nu se concepe conducerea i gestionarea ntreprinderii, fr a face apel la metodele cercetrii operaionale, mpreun cu celelalte tehnici moderne ca informatica, cibernetica, teoria sistemelor, statistica.

Obiectul cercetrii operaionale l constituie sistemele i ele i propun elaborarea unor metode de analiza a operaiilor ndreptate spre un anumit scop, precum i estimarea obiectiv

Introducere

4

a deciziilor ce pot fi adoptate. Cercetarea operaional este un ansamblu de metode care i propune, n vederea

pregtirii deciziilor, s determine n mod raional soluiile cele mai eficiente.

1.2. Teoria Deciziei i Cercetare Operaional Creterea productivitii i obinerea rentabilitii ntreprinderii industriale pe termen

lung, ntr-un mediu dinamic i ntr-o continu schimbare, depinde, ntr-o mare msur de capacitatea managementului ntreprinderii de a anticipa schimbarea i de a adapta decizia noilor situaii ntr-un mod planificat.

Accelerarea evoluiei tehnologice n industrie, influeneaz i comportamentul consumatorilor, care se va orienta spre noi concepte i produse, mai inovate, mai atractive i adaptate modului i ritmului lor de via.

Utilizarea raional a celor patru tipuri de resurse conduc la flexibilitatea organizaiei i astfel activitatea poate fi planificat n prognoze pentru a releva anumite aspecte semnificative ale viitorului. n aceste condiii, managerul trebuie s adopte decizii, fundamentate tiinific i performant.

Decizia reprezint soluia aleas, din mai multe variante posibile cu scopul atingerii unui obiectiv prestabilit n condiii de eficien maxim. Este actul deliberat al unui individ sau al unui grup de oameni investii cu puterea de a alege varianta de concepere/realizare a unui scop i de a declana aciuni.

Procesul de decizie pornete de la un anumit rezultat care trebuie s fie obinut, iar decidentul trebuie ca prin prelucrarea diferitelor informaii s aleag cea mai bun variant pentru atingerea acestuia (fig. 1.1).

Rezultat dorit Obiective Variante Criterii DECIZIE Actiune

Control

Rezultat dorit

Fig.1.1.

Cercetare operaional alturi de Teoria deciziei a absorbit noile dezvoltri n domeniul activitii de management industrial i al sistemelor economice.

Necesitatea modelrii n managementul produciei industriale rezult din faptul c efectuarea unor experimente asupra organizaiilor este foarte greu de realizat, dar experimente de acest fel (de exemplu modificarea parametrilor funcionali) se pot face uor n condiiile folosirii unui model.

Utilizarea modelelor este impus i de complexitatea sistemelor industriale, care necesit existena unei activiti desfurat astfel nct deciziile s fie n concordan cu evoluia eficient a acestora.

Operaia de investigarea a sistemelor reale prin reprezentri convenionale se numete modelare. Ea reprezint mulimea activitilor care se extind de la simpla prezentare a problemei la proceduri abstracte i raionale. Ele produc n final premisele cantitative formale ale dinamicii procesului.

Modelul este o reprezentare izomorfa a realitii ce ofer o imagine intuitiv dar riguroas n sensul structurii logice a fenomenului studiat.

Modelarea ca metod de fundamentare a deciziilor n activitatea economic ofer urmtoarele avantaje: - reprezint riguros fenomenele i legturile lor la nivelul sistemului; - permite verificarea prin analogie a teoriei cu practica;


5

- nlesnete descoperirea unor corelaii ntre fenomene i predeterminarea performanelor firmei, necesare pentru adoptarea unor decizii raionale; - reflect teorii ale proceselor cuantificabile i necuantificabile; - urmrete obinerea unor soluii optime.

Modelarea utilizeaz un suport material fizic (de exemplu simulatoarele), o reprezentare grafic (de exemplu un grafic reea), un model abstractizat sub forma unui model matematic. Din impactul ntre modelele fizice cu dispozitive logice de calcul i cele matematice au rezultat modelele de simulare.

n managementul produciei industrial se aplic toate aceste tipuri de modele, de exemplu: modelele fizice se pot folosi pentru studiul privind planul general al firmei, modelele grafice la analiza relaiilor om main, modelele matematice pentru alocarea resurselor sau analiza proceselor aleatoare.

Corelaia teorie-model-realitate reprezint un aspect logic - privind corespondena dintre teorie i model i un aspect gnoseologic urmrind corespondena dintre model i realitate. Modelul intervine ntre teorie i obiectul real i trebuie testat n raport cu realitatea exprimat ca obiect.

n funcie de modul n care se ajunge la soluia optim exist dou direcii principale de lucru:

atingerea obiectivului prin deducerea soluiei optime; atingerea aceluiai obiectiv prin practici oferite de teoria deciziei

Deducerea soluiei se caracterizeaz prin certitudinea rezultatului obinut pe baza unor informaii obiective i complete. Dificultatea const n formularea problemei ntr-un limbaj matematic adecvat i n volumul mare al calculelor.

Metoda a doua solicit decidentului s estimeze consecinele posibile ale aciunilor sale pe baza unor informaii obiective, dar incomplete, introducndu-se n rezolvarea problemei elemente subiective.

Prima direcie a condus la dezvoltarea unui ansamblu de discipline n cadrul CERCETRII OPERAIONALE.

A doua direcie de lucru a condus la constituirea unei discipline aparte TEORIA DECIZIEI. ntre cele dou direcii exist raporturi strnse, biunivoce, ceea ce a condus la apariia unei tiine multidisciplinare: TEORIA DECIZIEI i CERCETARE OPERAIONAL

Teoria deciziei este legat intrinsec de cercetarea operaional care poate fi considerat pregtirea tiinific a deciziilor.

1.3. Modelarea matematic n cercetarea operaional Condiiile n care se desfoar activitatea analizat din cadrul ntreprinderii, conduc la

un sistem de relaii tip ecuaii i inecuaii ce cuprind variabilele problemei i coeficienii tehnico economici ce o caracterizeaz. Aceste relaii reprezint restriciile problemei matematice.

Obiectivul studiului l constituie optimizarea unui anumit rezultat dependent de aceleai variabile ce figureaz n restricii. Obiectivul este sub forma unei funcii ale crei valori maxime sau minime le cutm i care se numete funcia obiectiv (scop, eficien).

Restriciile problemei i funcia obiectiv formeaz modelul matematic al problemei. Modelele matematice se prefer pentru capacitatea lor de condensare riguroas a

esenialului. Modelele cercetrii operaionale se caracterizeaz prin cutarea unei soluii optime sau apropiate de optim pentru operaia studiat.

Modelele cercetrii operaionale se bazeaz pe o mare diversitate de procedee matematice i au aplicaii la nivel macro, dar n special la nivel microeconomic. Ele reprezint principalul instrument pentru optimizarea deciziilor n analiza de sistem.

Introducere

6

Decizia obinut cu ajutorul modelului nu poate fi recomandat nemijlocit pentru realizare, deoarece modelul face abstracie de o serie de aspecte ale fenomenului studiat. Principalele faze ale elaborrii unui model matematic ntr-o problema de organizare conducere sunt urmtoarele: Prima faz a modelrii este cunoaterea realitii n organismul studiat, n scopul mbuntirii mecanismului informaional decizional i descrierea logicii proceselor decizionale, aceast faz avnd un caracter pregtitor;

A doua faz a modelrii constituirea propriu - zis a modeluluiacesta cu ajutorul unui instrument clasic de modelare.

Elaborarea unui model matematic realmente original reclam, pe lng profunda cunoatere a realitii care urmeaz a fi modelat, o foarte solid cultur matematic, imaginaie i talent.

Modelelor clasice ale cercetrii operaionale, sunt diverse funcie de structura matematica i logic, i variaz de la modele simple cum sunt cele ale programrii liniare, la modele combinatorice, n probleme de teoria grafelor, analiza drumului critic i programarea operativ a produciei i pn la modele complexe cum sunt cele ale utilitii sau deciziilor de grup.

A treia faz a modelrii este confruntarea modelului cu realitatea prin implementarea rezultatului obinut i eventual experimentarea sa. Exist o gam larg de probleme tehnico economice care se preteaz a fi modelate matematic cu ajutorul procedeelor cercetrii operaionale, dintre care putem meniona: programarea operativ a produciei; repartizarea raional a resurselor; gestiunea stocurilor; ealonarea n timp a activitilor unei investiii. In contextul celor artate mai sus trebuie subliniat importana metodelor cercetrii operaionale n fundamentarea i elaborarea deciziilor. Sarcina cercetrii operaionale este de a pregti decizia i nu de a o adopta . Conducerea executiv care va lua decizia final trebuie s in seama pe lng recomandrile cercetrii operaionale i de o serie de factori ce nu pot fi formalizai.

Una din principalele caracteristici ale tuturor metodelor cercetrii operaionale este faptul c problemele cercetrii operaionale sunt privite, din perspectiv pur teoretic, ca probleme de matematic pur.

n cele ce urmeaz vom privi metodele cercetrii operaionale strns legate de problemele practice.

n prezent nu se mai poate concepe conducerea unei activiti tehnico-economice importante fr a face apel la metodele cercetrii operaionale, bineneles mpreun cu celelalte tehnici moderne cum ar fi informatica, analiza de sistem .a..


7

CAPITOLUL 2 PROGRAMAREA LINIAR

2.1. Probleme de programare liniar

Orice activitate industrial se desfoar n condiiile existenei unor resurse limitate

de materii prime i materiale, de resurse umane, iar folosirea eficient, a acestora, conduce la rezultate optime att din punct de vedere tehnic ct i economic.

Modelele de programare matematic i mai ales modelele de programare liniar, constituie o clas special, att n teorie ct i n practica industrial.

Pentru decizii referitoare la structura optim de producie, la cantitatea ce urmeaz a se produce, la sortimente, abordarea acestora cu modele ale programrii matematice conduce la rezultate optime.

Programarea matematic reprezint un instrument deosebit de util fundamentrii deciziilor n practica industrial. 2.1.1. Formularea problemei de programare liniar

Principala problem cu caracter decizional, cu care se confrunt producia o constituie determinarea structurii optime de producie pe termen mediu i scurt printr-o folosire eficient a resurselor.

Condiiile n care se desfoar activitatea de producie analizat, conduc la un sistem de relaii tip ecuaii i inecuaii ce cuprind variabilele problemei i coeficienii tehnico economici ce o caracterizeaz .

Modelul matematic de programare liniar se constituie din mulimea de activiti (operaii){A1, A2, ..Aj,.. An}, (j=1,...,n) pentru producerea unei uniti din produsul Pj (ca rezultat al activitii Aj), mulimea de resurse disponibile materiale, financiare, de capaciti de producie {b1, b2, ... bm}, (i = 1,...,m) precum i din relaiile tehnico-economice dintre acestea.

n practica industrial, legtura dintre activiti (operaii) i resurse este determinat de procesul tehnologic de fabricaie corespunztor realizrii produsului.

Elementele aij, (i = 1,...,m; j = 1,...,n) se numesc coeficieni tehnico-economici, acetia fiind constani ntr-un interval de timp determinat i arat ce cantitate din resursa bi (i = 1,...,m) se consum pentru producerea unei uniti din produsul Pj.

Toate aceste legturi (restricii) definite de vectorii coloan a(j) se pot organiza ntr-o matrice A cu m linii i n coloane (2.1); fiecare linie se refer la o resurs bi i fiecare coloan se refer la o activitate aj.

AMm.n; A= ( ai,j ), i = 1,..,m, j= 1,...,n; A =

mn1m

n111

a..........a

a.........a (2.1)

b m

R , b =

m

2

1

b

bb

. (2.2)

Notnd cu xj (j = 1,...,n) (2.3) programul activitii aj ntr-o perioad dat i cu bi

cantitile disponibile din resursele bi, se pot scrie matematic restriciile tehnico-economice. Aceste restricii reprezint restriciile problemei de programare liniar (2.4).

Programare liniar

8

x R n , x =

nx

xx

.2

1

(2.3)

mnmn2m21m1

2n2n222121

1n1n212111

bxa...xaxa

bxa...xaxabxa...xaxa

+++

++++++

(2.4)

Fiecare restricie (inecuaie de tipul ) cuprinde afirmaia prin care cantitatea

consumat dintr-o resurs nu poate depi volumul disponibil din resursa respectiv. Obiectivul studiului l constituie optimizarea unui anumit rezultat dependent de

aceleai variabile ce figureaz n restricii. Obiectivul este sub forma unei funcii ale crei valori maxime sau minime le cutam i

care se numete funcia obiectiv (scop, eficien). n practica industrial, ea reprezint criteriul de performan urmrit: maximizarea

beneficiului, maximizarea produciei marf, minimizarea costului produciei, maximizarea gradului de ncrcare al utilajelor sau minimizarea timpului de staionare al acestora, maximizarea veniturilor etc.

Variaia funciei obiectiv arat evoluia volumului activitilor, prin intermediul coeficienilor jc , ce pot fi costuri unitare n cazul problemelor de minim, sau profituri unitare pentru probleme de maxim (2.5).

Rc j , c Rn c =

n

2

1

c

cc

. ; )......( nj21

T ccccc = (2.5)

Decizia cu scopul unei eficiene maxime presupune minimizarea efortului i

maximizarea rezultatului, Conceptul de optim se definete, n acest caz, ca un program (soluie) x Rn care

minimizeaz sau maximizeaz o funcie obiectiv i, n acelai timp, satisface toate restriciile tehnico-economice.

Presupunnd c fiecare coeficient .cj msoar eficiena unei uniti din rezultatul activitii Aj, atunci se poate introduce funcia obiectiv liniar (2.6) :

z = c1x1 + c2x2 + ... + cnxn (2.6)

Sintetiznd toate datele de mai sus, obinem urmtorul model (2.7, 2.8, 2.9)de

programare liniar. Relaiile (2.7), (2.8) i (2.9) constituie mpreun modelul matematic al unei probleme

de programare liniar, avnd fiecare un rol specific: 1. relaia (2.7), denumit funcia obiectiv a problemei, evalueaz eficiena/performana

fiecrei soluii (program) x;


9

+

=

=

=

=

nj10x

li1kbxa

ki1bxa

xcz

j

n

1jijij

n

1jijij

n

1jjj

xmin(max)

2. relaiile (2.8) de tipul =

n

1jijij bxa reprezint restricii ce coreleaz volumul consumului

activitilor cu cel al disponibilului pentru fiecare resurs; iar restriciile de tipul =

n

1jijij bxa impun un consum peste limitele minimale, sunt restricii tehnico-economice

de tip calitativ; 3. relaia (2.9) xj 0 j = 1,...,n, numit condiia de nenegativitate a variabilelor, asigur

obinerea unei soluii realizabile n practica industrial. Decizia obinut cu ajutorul modelului nu poate fi recomandat nemijlocit pentru

realizare, deoarece modelul face abstracie de o serie de aspecte ale fenomenului studiat, cele ce au la baz o serie de factori ce nu pot fi formalizai.

n practica industrial programarea liniar ofer soluii care pot motiva tiinific luarea unor decizii de natur strategic, tactic sau a unor decizii cu coninut tehnico organizatoric. 2.1.2. Forme ale problemei de programare liniar

O problem de programare liniar este, un caz particular al problemelor de programare matematic i, innd cont de forma oricrei funcii liniare, se poate defini forma general a problemei de programare liniar.

Funcia liniar (2.10), notat cu z reprezint funcia obiectiv a problemei. Relaiile (2.11) reprezint sistemul de restricii ale problemei, iar membrul stng al

fiecrei relaii aste o funcie liniar n variabilele x1, x2,,xn, la fel ca i funcia obiectiv. Problema de programare liniar const n optimizarea unei funcii liniare cu restricii

liniare.

Forma general a problemei de programare liniar

( )( )( )( )

( )( )

=++

=++=+++++=

mnmn22m11m

2n222121

1nn1212111

nn2211

bxaxaxa

bx2axaxabxaxaxaxcxcxcz

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

......

...min(max)

unde: ),(),,,,(),,( m1iRbn1jm1iRan1jRc iijj ==== Din analiza mai multor probleme de programare liniara deducem c ntr-o astfel de problema pot apare restricii scrise sub forma de inegaliti sau egaliti, iar criteriul de optimizare ales impune n unele cazuri maximizarea iar n alte cazuri minimizarea funciei obiectiv.

(2.7)

(2.8)

(2.9)

(2.10)

(2.11)

Programare liniar

10

Rezolvarea problemei de programare liniar presupune determinarea valorilor variabilelor xi, care satisfac restriciile i optimizeaz funcia obiectiv a problemei. Forma standard a problemei de programare liniar O problema de programare liniar este dat sub form standard dac toate restriciile sale sunt date sub form de ecuaii (egaliti) i tuturor variabilelor li se impun condiii de nenegativitate. Problema de programare liniar dat n form standard se scrie n mod explicit (2.12):

=

=

=

=

njx

mibxa

xcz

j

n

jijij

n

jij

101

max(min)

1

1 (2.12)

Problema de programare liniar n form standard poate fi scris i sub form matricial (2.13) :

=

0xbAx

xcTmin(max), unde

mnm

n

RbRMARxc

,)(,

(2.13)

unde cT reprezint componentele matricei c transpus. Sistemul de restricii liniare ( Ax=b ) poate fi un sistem compatibil, compatibil unic determinat sau nedeterminat de m ecuaii i n necunoscute. Pentru ca problema de optimizare s aib sens, numrul de ecuaii trebuie s fie mai mic dect numrul de necunoscute (m


11

0x

bAxxcT

)(min(max)

unde

mnm

n

RbMA

RxC

,

, (2.15)

Orice problem de programare liniar n form general poate fi adus la forma standard sau canonic cu ajutorul unor transformri elementare efectuate asupra operatorului aplicat funciei obiectiv restriciilor i variabilelor: a) o problem de minimizare n form matricial se poate transforma ntr-o problem de

maximizare i invers, schimbnd semnul coeficienilor din funcia obiectiv, astfel:

max c xcx TT )min(= ; min c xcx TT )max(= (2.16)

b) o variabil x arbitrar (variabil creia nu i se impune restricie de semn) se poate nlocui cu dou variabile nenegative 2,1 xx , prin relaia :

0xxundexxx 2121 = ,, (2.17)

c) o variabil x supus condiiei de nepozitivitate ( 0x ) se transform ntr-o variabil

nenegativ prin substituia

0xundexx 11 = , (2.18)

d) Restriciile de tip inecuaie se transform n restricii de tip ecuaii innd cont de urmtoarele :

=

0yxbyxa

0xbxa TT

,i

=+

0yxbyxa

0xbxa TT

, (2.19)

unde y se numete variabil ecart. Variabilele ecart nu apar n funcia obiectiv sau astfel spus apar n funcia obiectiv dar cu coeficieni nuli: 0=ejc (unde =

ejc coeficieni ai variabilelor ecart).

e) sensul unei inegaliti se schimb prin nmulirea cu 1. n aplicaiile practice apar frecvent situaii n care modelul conine simultan restricii de toate tipurile (concordante, neconcordante, egaliti), problema fiind dat n form general, iar rezolvarea ei poate fi abordat fr a restrnge generalitate. Exemplul 2.1 S se scrie formele echivalente ale problemei de programare liniar:

Problema dat este n forma general. Pe baza transformrilor echivalente vom construi formele echivalente ale problemei iniiale. Deoarece variabila x3 nu are restricii de semn, o vom nlocui, cu diferena a dou variabile

Programare liniar

12

( )

+

++

=

+

oarecarex0xx0x2x3x2

2x4x3x2x5x

4xx3x2xx3

321

321

31

321

21

321

,,,,

,,

,max

)()()()(

4321

pozitive: x3 = x4 x5. Pentru ca problema s aib forma standard, toate restriciile trebuie s fie egaliti, de aceea n restriciile (2), (3) i (4) vom introduce variabilele de egalizare x6, x7, x8. Forma standard va fi:

( )

=+++

=+

=+

=

+

0xxx0xxxx3x2

2xx4x4x3xx2x2x5x

4xx3x2x2xx3

821

85421

7541

65421

21

5421

,...,,,

,,

,max

Forma canonic se obine transformnd restricia (1) n dou inegaliti i toate

inegalitile le transformm n inegaliti deoarece problema este dat de maximizare. Astfel, x3 trebuie nlocuit cu diferena x4 x5.

Se obine astfel forma canonic

( )

.

,,,,

,,

,,

max

+++

+++

+

0xxxx0xxx3x2

2x4x4x3x2x2x5x

4xx34xx3

x2x2xx3

5421

5421

541

5421

21

21

5421

2.1.3. Modelul matematic al problemei de programare liniar Pentru a nelege modelul matematic al problemelor de programare liniar sub forma general, vom analiza cteva exemple din practica industrial:

Alocarea optim a resurselor n producia industrial O firm urmeaz s produc n tipuri de produse Pj , nj ,1= , folosind m tipuri de

resurse Ri mi ,1= . Se cunosc coeficienii tehnologici aij ; cantitile disponibile bi din resursele Ri ;

profitul unitar cj pentru fiecare produs Pj. S se ntocmeasc planul optim de producie al firmei astfel nct profitul total realizat

s fie maxim.


13

Elaborare modelului matematic al problemei Condiii generale de desfurare a activitii analizate :

- restriciile problemei apar din urmtoarea condiie: cantitatea totala din resursa i folosit pentru producerea celor n produse nu poate fi mai mare dect cantitatea disponibila:

mibxa ijn

jij ,1,

1=

=

(2.20)

- condiiile de nenegativitate asigur obinerea unei soluii realizabile din punctul de

vedere al logicii practice industriale.

xj 0 , nj ,1= (2.21)

Sistemul de inecuaii (2.20) i (2.21) poate avea o infinitate de soluii, deci putem organiza procesul de producie pentru realizarea produsului P ntr-o infinitate de moduri dar respectnd condiiile anterioare .

Acest fapt face evident imposibilitatea practic a managerului de a compara toate variantele de plan posibile deci este necesar introducerea unui alt criteriu.

Adoptarea unei variante de plan (n fapt fundamentarea deciziei) se face, preferabil, pe baza unui criteriu economic (cel mai uzual maximizarea profitului sau n alte cazuri minimizarea costurilor). Aplicarea acestui criteriu economic, presupune cunoaterea profitului total.

Deci : jjn

jxc

=1reprezint profitul total pentru produsele Pj

Funcia obiectiv (scop, eficien) va fi :

max jn

jj xcf

=

=

1 (2.22)

Deci, modelul de programare liniar ce urmeaz a fi rezolvat pentru determinarea

planului optim de producie astfel nct profitul total realizat s fie maxim este:

==

0x

bxa

xcf

j

ijij

n

1jjjmax

(2.23)

Problema de transport

Un produs omogen P este stocat n m depozite Di, n cantitile ai , mi ,1= i este cerut de spre a fi transportat la n centre de consum Cj ,n cantitile bj, nj ,1= . Se cunosc costurile cij pe unitatea de produs transportat de la centrul Di la centrul Cj . Se cere determinarea unui plan de transport astfel nct costul total de transport s fie minim.

Programare liniar

14

Elaborarea modelului matematic al problemei Notaii : ai = cantitatea din produs care se afl n depozitul i; bj = cantitatea cerut de consumatorul j ( 1


15

Problem de repartizare a sarcinilor de producie ntr-un atelier de montaj echipele njE j ,1, = , pot monta cu randamente diferite,

produsele m1iPi ,, = . Activitatea atelierului este caracterizat de urmtoarele date cunoscute: ija - timpul necesar pentru montajul unei cantiti de produs Pi de ctre echipa

;jE ijc - cheltuielile necesare pentru montajul unei uniti de produs Pi de ctre echipa ;jE ib - cantitatea planificat din produsul Pi , mi ,1= ; jt - timpul de lucru disponibil al echipei

njE j ,1, = . S se stabileasc o repartizare a produselor, echipelor, din atelierul de montaj astfel

nct cheltuielile totale necesare s fie minime. Elaborarea modelului matematic al problemei: Variabilele de decizie (necunoscutele) se noteaz cu ijx i reprezint cantitatea din produsul Pi ce trebuie realizat de echipa Ej. Funcia obiectiv este o funcie de cost, respectiv, cheltuielile celor n echipe, necesare pentru montajul cantitilor repartizate din cele m produse; funcia trebuie minimizat:

== =

m

1i

n

1jijij xcfmin (2.30)

Cantitatea de produse de fiecare tip planificat trebuie realizat:

mibx in

jij ,1,

1==

=

(2.31)

Oricare echip poate executa produse n limita fondului de timp disponibil:

=

=m

ijijij njtxa

1,1, (2.32)

Variabilele ijx se supun condiiei de nenegativitate:

njmixij ,1,,1,0 == (2.33) Deci, modelul matematic al problemei este:

==

=

==

=

=

=

= =

n1jm1i0x

n1jtxa

m1ibx

xcf

ij

m

1ijijij

in

1jij

m

1i

n

1jijij

,,,,

,,

,,

min

(2.34)

Problem de utilizare a capacitii utilajelor

Programare liniar

16

O firm produce n tipuri de produse care pot fi fabricate pe m utilaje care au capaciti de producie limitate pe o anumit perioad. Se cunosc: procentul ija din capacitatea utilajului i necesar pentru producerea unei uniti din produsul j; profitul unitar cj al produsului nj ,1= .

S se stabileasc un program de fabricaie care s permit utilizarea optim a capacitii disponibile a celor m utilaje.

Elaborarea modelului matematic al problemei:

Variabilele problemei sunt cantitile de produse fabricate n perioada considerat. Se noteaz cu xj, numrul de produse de tipul nj ,1= .

Funcia obiectiv este profitul total obinut de firm pentru cele n tipuri produse; funcia trebuie maximizat:

==

n

1jjj xcfmax (2.35)

Restriciile de capacitate ale celor m utilaje se exprim sub forma:

=

=m

jijij mixa

1,1,1 (2.36)

Variabilele xj se supun condiiei de nenegativitate:

njx j ,1,0 = (2.37)

Atunci, modelul matematic al problemei este:

=

=

=

=

=

n1j0x

m1i1xa

xcf

j

m

1jijij

n

1jjj

,,

,,

max

(2.38)

2.2. Consideraii generale privind problemele de programarea liniar

2.2.1. Soluii i fundamente ale problemei de programare liniar Fie problema de programare liniar dat n form standard matricial:

=

0xbAx

xcTmin(max), unde

mnm

n

RbMA

RxC

,

, (2.39)

Sistemul de ecuaii Ax=b are o infinitate de soluii, deci trebuie s se gseasc n mulimea soluiilor o soluie ce realizeaz valoarea optim (minim sau maxim ) a funciei obiectiv.


17

Soluie admisibil Un vector x = ( ) nn Rxxx ...21 care satisface restriciile si condiia de nenegativitate se numete soluie admisibil sau posibil a problemei de programare liniar. Mulimea soluiilor admisibile, S, este:

}{ 0xbAxRxS n == ,/ (2.40) Sistemul de ecuaii, avnd m ecuaii i n necunoscute, cu m

Programare liniar

18

x = ( x1 , x2 , x3 , xp , 0, 0 ,0)T (2.42)

Dac p = 0, atunci x = 0 deci afirmaia teoremei este evident. Dac p > 0, atunci exist dou posibiliti:

- dac vectorii a1 , a2 , ..ap A corespunztori celor p componente nenule ale lui x sunt liniari independeni, atunci x este program de baz.

- dac vectorii a1 , a2 , ..ap A corespunztori celor p componente nenule ale lui x sunt liniari dependeni atunci exist numerele reale: y1, y2,.. yp nu toate nule astfel nct s fie satisfcut relaia:

a1y1 + a2y2 +..+apyp = 0 (2.43)

Relaia (2.43) se poate scrie sub urmtoarea form echivalent : Ay = 0 cu y 0. Notm cu y vectorul cu primele p componente nenule i urmtoarele componente n-p

nule: y = (y1, y2 , yp, 0, 0 .0 )T. Atunci, obinem: A( x + y ) = Ax + Ay = b, ( ) R Deci, x + y este soluia sistemului Ax=b astfel putem determina valori ale lui

pentru care x + y este program pentru problema (2.41), deci este ndeplinit i condiia: x + y > 0

Notm: I1 = mulimea indicilor i , 1< i < p , yi > 0; I2 = mulimea indicilor i , 1< i


19

() [ 0,1] , atunci [ x, y] M . Deci se poate spune c mulimea M din V este convex, dac odat cu doi vectori x, y

M conine i segmentul determinat de aceti vectori. Definiia 2.3: Vectorul X M se numete vrf sau punct extrem al mulimii M dac nu

exist vectorii x, y M astfel nct { }10,)1( += yxX . n caz contrar X se numete punct interior mulimii M .

Definiia 2.4 : Prin combinaie liniar convex a vectorilor x1 ,x2 ,xm M se

nelege o expresie de forma 1x1 + 2x2 + + mxm cu [ 0,1 ] i 1 + 2 + + m = 1 Concluzie: Orice punct interior X al unei mulimi convexe M se poate exprima ca o

combinaie liniar convex de un numr finit de puncte extreme. Teorema 2.2: Mulimea soluiilor admisibile ale unei probleme de programare liniar

este o mulime convex . Demonstraie : Fie mulimea soluiilor admisibile dat de relaia (2.40). Fie dou soluii: x1 , x2 S. Atunci pentru [0,1] avem

x = x1 +(1- )x2 0 (2.45) nlocuind relaia (2.45) n relaia (2.40) obinem : Ax= A[x1 +( 1- )x2]=Ax1 + (1- ) Ax2 = b + (1- )b = b+ b - b = b, deci mulimea soluiilor problemei de programare liniar este o mulime convex. Teorema 2.3: Orice soluie admisibil de baz a unei probleme de programare liniar

este vrf sau punct de extrem al mulimii soluiilor admisibile. Demonstraie.

Presupunem c soluia admisibil de baz x are forma x=(x1 x2 xm 0 0T.

Aceasta nseamn c 0ix (i = 1, m), vectorii p1, p2, ,pm sunt liniar independeni i x satisface sistemul de restricii, deci

x1P1 + x2P2 + + xmpm +0pm+1 + + 0pn = p0 (2.46) Trebuie artat c x este vrf al mulimii S a soluiilor admisibile. Presupunem prin absurd c x nu este vrf, ci punct interior, adic exist doi vectori

Sxx '',' astfel nct: ( ) ''1' xxx += , ( )1,0 Scris pe componente:

( ) '1'11 1 xxx += , ( ) ''2'22 1 xxx += ,., ( ) ''' 1 mmm xxx += ,.., ( ) ''' 10 nn xx +=

ns ( )1,0 , deci 01 > , iar 0' ix ( )ni ,1= i 0'' ix ( )ni ,1= deoarece Sxx '',' , astfel c, din cele n m relaii se obin:

00 '' 1 ==+ nm xx ; 00''''

1 ==+ nm xx i deci vectorii '',' xx au formele:

Programare liniar

20

( )Tmxxxx 00' ''2'1 = , ( )Tmxxxx 00'' ''''2''1 = (2.47)

Exprimm faptul c Sxx '',' verific restriciile

0mm2211 ppxpxpx =+++'''

(2.48)

0mm2211 ppxpxpx =+++''''''

(2.49) ns vectorii pi ,,pm sunt liniari independeni. Rezult:

'''''2

'2

''1

'1 ,, mm xxxxxx === adic ''' xx = (2.50)

Aceasta nseamn c nu exist vectorii Sxx '',' astfel ca ( ) ( )1,0''1' += xxx

prin urmare x este vrf sau punct de extrem n S. Teorema 2.4: Funcia obiectiv a unei probleme de programare liniar ia valoare

optim ntr-un punct extrem a mulimii convexe M a tuturor soluiilor admisibile ale problemei de programare liniar.

Demonstraie: Presupunem c se cere ca funcia obiectiv s fie minimizat. Notam cu M~ = { xi , i I } mulimea punctelor extremale ale lui M i fie x1 punct

extrem pentru care 1T xc = }{min i

T

Iixc

= z1

Presupunem prin absurd c aceast afirmaie nu este adevrat, atunci exist x0 { }MM ~ astfel nct : 0T xc = z0 < z1, deoarece x0 nu este punct extrem atunci :

x0 = i

Iii x

, I 0 , Ii

i = 1 (2.51)

Dar z0 = 0

T xc = iT

Iii xc

'

> 1T

Iii xc

= cT x1 = z1, ceea ce este o contradicie. Deci x1 este un program minimal pentru problema de programare liniar.

Consecin : Dac funcia obiectiv ia aceeai valoare optim n mai multe puncte extremale, atunci

orice combinaie liniar convex a acestora este soluie optim a problemei de programare liniar.

2.2.2. Baze ale problemei de programare liniar

Fie problema de programare liniar n forma standard (2.13), n care matricea A are m

linii i n coloane, iar rang A = m < n. Ecuaiile ce compun sistemul liniar Ax = b sunt liniar independente, iar sistemul are o infinitate de soluii.

Astfel, n matricea A exist cel puin un grup de m coloane liniar independente, care formeaz o baz a spaiului Rm.

Definiiile ce urmeaz reprezint fundamente ce stau la baza rezolvrii modelelor de programare liniar. Definiia 2.5 Se numete baz a problemei de programare liniar n form standard un grup de m coloane liniar independente.


21

Problema (2.13) are un numr finit de baze i anume mnC . Fie B o baz format cu m coloane, ale matricei A. Matricea A se poate scrie

partiionat sub forma:

[ ]SBA ,= , cu ( )[ ] IiiaB = , ( )[ ] JjjaS = (2.52)

unde prin I i J s-au notat mulimile de indici corespunztori coloanelor din baza B i, respectiv, a celorlalte coloane:

( ){ }

{ } InJBaniI i

/,...,2,1,1

=

== (2.53)

Partiionarea vectorului x al variabilelor problemei este urmtoarea:

= S

B

xxx , cu [ ] IiiB xx = , [ ] JjjS xx = (2.54)

iar partiionarea vectorul c al coeficienilor funciei obiectiv este:

= S

B

cc

c , cu [ ] IiiB cc = , [ ] JjjS cc = (2.55) n raport cu baza B aleas, variabilele ( )Iixi se vor numi variabile de baz, iar

( )Jjx j variabile secundare. Sistemul de ecuaii Ax = b se poate scrie dup partiionare sub forma:

[ ] bSxBxbxx

SB SBSB

=+=

, (2.56)

Matricea B fiind o baz a spaiului Rm este inversabil. Astfel prin nmulirea relaiei

(2.56) la stnga cu B-1 se obine forma explicit a sistemului de ecuaii:

SB SxBbBx 11 = (2.57)

Notm cu:

bBxB 1= (2.58)

( ) njaBy jBj ,1,1 == (2.59)

nlocuind relaiile (2.58) i (2.59) n relaia (2.57) obinem:

=

Jj

Bj

Bj

BB xyxx (2.60)

Scris pe componente relaia (2.60) devine:

Programare liniar

22

IixyxxJj

Bj

Bij

Bi

Bi =

, (2.61) Definiia 2.6. Soluia de baz corespunztoare bazei B este:

nB

B Rxx

=

0 (2.62)

O soluie de baz este o soluie admisibil (program) a unei probleme de programare

liniar dac 0Bx . Definiia 2.7 Baza B care satisface condiia

01 bB (2.63)

se numete baz primal admisibil. innd seama de relaiile (2.54) i (2.55), funcia obiectiv a problemei de programare

liniar, xcz T= , poate fi exprimat prin:

[ ] ( ) STSS11TBSTSBTBSBSB xcSxBbBcxcxcxxccz +=+=

=

'

( ) STS1TB1TB xcSBcbBcz '' = (2.64) Notm cu:

BTB

Bxcz = (2.65)

n1jycz BjTB

Bj ,, == (2.66)

nlocuind relaiile (2.65) i (2.66) n relaia (2.64) obinem:

( )

=

Jj

Bjj

Bi

Bxczzz (2.67)

Definiia 2.7. Constanta Bz din relaia (2.67) reprezint valoarea funciei obiectiv n soluia asociat bazei B.

Diferentele jBj cz ( )Jj se mai numesc costuri reduse i au rolul esenial n

caracterizarea optimalitii unei soluii admisibile de baz a unei probleme de programare liniar.

2.2.3. Interpretarea geometric a problemei de programare liniar O interpretare geometric a unei probleme de programare liniara se poate obine

simplu n cazul cnd problema are dou variabile (spaiu R2) i se prezint sub forma canonic.


23

Fie modelul de programare liniar (2.11) exprimat n funcie de dou variabile de decizie x1 i x2.

1) Restriciile unui astfel de model pot fi exprimate prin a) egaliti : 1212111 bxaxa =+

b) inegaliti : sau 2222121

2222112bxaxabxaxa

++

(2.68)

2) Condiii de nenegativitate : 0,0 21 xx (2.69)

3) Funcia obiectiv (2.10) poate fi: 2211 xcxcz +=min(max) (2.70)

Realiznd o analiz din punct de vedere grafic putem observ urmtoarele : egalitatea 1212111 bxaxa =+ , reprezint o dreapta. Mulimea soluiilor ( )21 xx , aparine

acestei drepte (d), iar aceast dreapt (curb de nivel), mparte planul ( )210 xx n dou semiplane.

inegalitatea 1212111 bxaxa

Programare liniar

24

Coordonatele acestor puncte se afl uor astfel:

0

d2

x1

D(0,2)

x2

d1

A(2,0)

B(4,1)

C(1,4)

d3

(D)

Fig.2.1

( ) ( )

=+

=

5

22

21

2132 xx

xxddB ( )1,4B

( ) ( )

=+

=

5

222

21

2131 xx

xxddC ( )4,1C

Aflarea soluiei optime se bazeaz pe faptul c funcia obiectiv, avnd dou variabile se

poate reprezenta printr-o dreapt (D).

(D): c1x1 + c2x2 = z

Adus la forma y = mx + n unde m este panta, iar n ordonata la origine, rezult:

(D): 1

12

12 c

zxccx +=

care reprezint o mulime de drepte paralele ntre ele, avnd panta constant2

1ccm =

i ordonata la origine variabil, 1czn = .

n problemele de maxim vom alege poziia care are ordonata la origine astfel ca ea s furnizeze valoarea maxim pentru z.

Analog pentru problemele de minim. Pentru exemplul de mai sus rezult: (D) : x2 = -2x1 + z ; se alege acea dreapt ce trece prin unul din vrfuri, ce are m = -2

i ordonata n = z = max Ea este figurat punctat n figura 2.1. Ordonata la origine maxim corespunde punctului

B deci

x1 = 4 i x2 = 1 z = 2*4 +1*1 = 9 = max

Deoarece panta dreptei (D) este m = -2 = tg , rezult c unghiul = 116,560.


25

Exemplul 2.3. Pentru fabricarea a dou produse P1 i P2, o firm dispune de patru tipuri de resurse Ri ( )4,1 . Cantitile de resurse Ri folosite pentru fabricarea fiecrei uniti din produsele P1 i P2,

n uniti convenionale (tone etc) sunt date n tabelul 2.1. Se mai cunosc cantitile disponibile ale firmei din fiecare resurs Ri ( )4,1=i i

beneficiile pentru fiecare unitate din cele dou produse. S se determine planul de producie astfel ca beneficiul total s fie maxim. Tabelul 2.1

Introducnd variabilele de decizie: x1 = numrul de uniti din produsul P1 i x2 =

numrul de uniti din produsul P2 , rezult urmtorul model matematic de P.L.:

++

124164

821222

2

1

21

21

xx

xxxx

max,, =+= 2121 x3x2z0x0x

Soluia grafic (2.2) se obine determinnd domeniul admisibil: ( )( )( )( )

=

=

=+

=+

12x4d16x4d

8x2xd12x2x2d

24

13

212

211

(D) 2x1 + 3x2 = z Se observ c dreptele ( )1d , ( )2d i ( )3d sunt concurente n punctul B(4,2), iar

( ) ( )32 ddC are coordonatele C(2,3).

0

d2

x1

D(0,3)

x2

d1

A(4,0)

B(4,2)

C(2,3)

(D)

d3

d4

Fig.2.2

Resurse R1 R1 Disponibil R1 2 2 12 R2 1 2 8 R3 4 0 16 R4 0 4 12 Beneficiu 2 um 3 um

Programare liniar

26

Soluia optim a problemei este:

x1 = 4; x2 = 2 f(x) = 14 = max Verificm soluia n restriciile problemei.

Rezult c resursele R1, R2 i R3 sunt resurse rare, utilizate n ntregime n timp ce resursa R4 nu a fost n ntregime utilizat.

Cantitatea din resursa R4, ce rmne disponibil poate fi determinat i ulterior folosit cunoscnd preul umbr (dual).

Aceast analiz urmeaz a fi detaliat n subcapitolul 2.4.

2.3. Metoda Simplex

Metoda Simplex sau metoda mbuntirilor succesive evit cercetarea exhaustiv a tuturor soluiilor de baz ale unei probleme de programare liniar, construind succesiv soluii realizabile de baz din ce n ce mai bune ale modelului pn cnd este obinut o soluie de baz optim. Prin soluie mai bun nelegnd soluia ce d funciei de eficien (obiectiv) o valoare mai mic, respectiv mai mare dect cele precedente dup cum funcia de eficien este de minim sau de maxim.

Deci acest algoritm este o metod de examinare sistematic a programelor de baz ce d funciei de eficien o valoare optim.

Aceast metod pune n eviden cazul n care problema admite un optim infinit sau mulimea programelor este vid. 2.3.1. Fundamente teoretice n aplicarea metodei Simplex

Prezentarea metodei simplex se realizeaz pe un model de programare liniar dat n form standard i n care funcia obiectiv este o funcie de minimizare.

=

0xbAxxcTmin

, unde

mnm

n

RbMA

RxC

,

, (2.71)

Fie B o baz primal admisibil extras din matricea A i bBBx 1= o soluie de baz iniial a problemei de programare liniar.

Pentru ordonarea i facilitarea calculelor se utilizeaz n aplicarea practic a algoritmului tabele ce poart denumirea de tabele simplex.

Aceste tabele sunt tabele simple ce au m+1 linii i n+1 coloane i cuprind coeficienii numerici al problemei (2.71) corespunztori bazei primal admisibile B (tab 2.2). Tabelul conine n prima coloan, variabilele de baz (V.B.), n coloana a doua valoarea variabilelor de baz (V.V.B), iar n urmtoarele n coloane vectorii n1jy Bj ,, = .

Pe ultima linie a tabelului se trece valoarea funciei obiectiv pentru baza B notat cu Bz i diferenele n1jcz jBj ,, = .

Acestui tabel se ataeaz o linie deasupra variabilelor jx i o coloan la stnga coloanei V.B cu coeficienii corespunztori funciei obiectiv n1jc j ,, = .


27

Tabelul 2.2

Bix

Blx

Bmx

cl ck cj cn... ... ...

xl ... xk ... xj ... xnV.V.BV.B.CB

c1

ci

cl

cm

...

...

...

...

...

...

......

z ... ... ...

yB11

yBi1

yBl1

yBm1

yB1k

yBik

yBlk

yBmk

yB1j

yBij

yBlj

yBmj

yB1n

yBin

yBln

yBmn

x1Bx1B

xiB

xlB

xmB

z B1 - c 1 zBk - c k z

Bj - c j z

Bn - cn

...

...

...

...

B

Tabelul simplex se ataeaz fiecrei baze B din algoritm i are ca fundamente rezultatele teoretice ce sunt prezentate n continuare. Teorema 2.5 Criteriu de optimalitate Fie B o baz primal admisibil pentru probleme de programare liniar (2.71). Dac

0 jczBj , oricare ar fi j J , atunci programul de baz asociat bazei B, bBBx 1= este o

soluie optim a problemei de programare liniar considerat. Teorema 2.6 Criteriu de infinitudine a soluiilor Fie B o baz primal admisibil pentru probleme de programare liniar (2.71). Dac exist indicele k J astfel nct 0 kcz Bk i 0Biky , oricare ar fi Ii atunci problema are un optim infinit. Teorema 2.7 Criteriu de mbuntire a soluiilor Fie B o baz primal admisibil pentru probleme de programare liniar 2.71. Fie k J astfel nct 0> kcz Bk (2.72) i { } >=+ 0/ BikyIiI . Pentru indicele + Ii determinat cu relaia:

Blk

Bl

Bik

B

y

x

yix

Ii=

+

min (2.73)

se obine un nou program de baz Bx~

cel puin la fel de bun ca Bx , corespunztor unei noi baze B~ care are aceleai coloane ca i B, cu excepia coloanei )(la ce se nlocuiete cu coloana )(ka . Observaii: Baza B~ este primal admisibil i verific toate teoremele anterioare. Relaia (2.73) reprezint criteriul de ieire din baz i ne arat indicele + Il , al

coloanei )(la ce urmeaz s prseasc baza B.

Programare liniar

28

n cazul n care exist mai muli indici k J pentru care se ndeplinesc (2.72) i (2.73) atunci se pot construi mai multe baze primal admisibile i fiecare dintre acestea modific valoarea funciei obiectiv.

Pentru a obine mai repede optimul cutat este indicat a alege acel indice pentru care se verific relaia.

)())((max kczyx

yx

jcBjz

BkB

lk

Bl

Blk

Bl

Jj=

(2.74)

n practic utilizndu-se pentru evitarea calculelor urmtorul criteriu:

kcBkzjc

BjzJj

=

)(max (2.75)

Relaia 2.75 reprezint criteriul de intrare n baz i ne arat indicele

Jk al coloanei )(ka ce urmeaz s intre n baza B. Elementul lky din tabelul simplex poart denumirea de pivot.

Pentru calculul elementelor tabelului simplex asociat bazei B~ n raport cu elementele tabelului simplex asociat bazei B se utilizeaz formulele de schimbare a bazei n cadrul unei operaii numit pivotare gaussin. n practic formulele de schimbare a bazei se echivaleaz cu urmtoarele reguli de transformare a tabelelor simplex :

Elementele situate pe linia pivotului se mpart la valoarea pivotului ; Elementele situate pe coloana pivotului devin zero cu excepia

pivotului ce va avea valoarea unu ; Celelalte elemente ale tabelului simplex se transform dup regula

dreptunghiului. Se consider dreptunghiul imaginar a crui diagonal este determinat de elementul Bijy i pivotul Bijy (fig. 2.3) ; noua valoare Bijy

~se obine mprind la pivot diferena

dintre produsul BlkBij yy i BikBlj yy dup formula :

Blk

Bik

Blj

Blk

BijB

ij yyyyy

y

=

~ (2.76)

Bijy

Bijy

Biky

Biky

elementul detransformat

pivotul Fig.2.3 2.3.2. Algoritmul simplex primal. Rezultatele teoretice obinute anterior permit enunarea algoritmului simplex. Acest algoritm pentru rezolvarea problemelor de programare liniar date n form standard (2.13) este diferit n raport cu tipul funciei obiectiv, respectiv, probleme de minimizare sau maximizare.


29

Algoritmul simplex primal pentru probleme de minimizare Pasul 1 : Se determin o baza B primal admisibil. Pasul 2 : Se determin urmtoarele elemente : BjyjcBjz

BzBx ,,,

Pasul 3 : Se analizeaz toate diferenele jcz Bj :

Dac toate diferenele jcz Bj 0 , nj ,1= atunci programul Bx este optim.

Dac exist cel puin un indice j + J , { }0/ >=+ jBj czJjJ astfel nct jcz

Bj > 0 se trece la pasul 4.

Pasul 4 Se determin indicele k + J cu criteriul de intrare n baz = kcz

Bk )(max jcz

Bj

Jj

+

Dac 0Bky atunci problema are un optim infinit. Dac + Jk)( pentru care 0>Bky se trece la pasul 5.

Pasul 5: Se determin indicele l I cu criteriul de ieire din baz:

Blk

Bl

Bij

Bi

Biky

Ii yx

yx

=

>

min

0

Pasul 6 : Se nlocuiete n baza iniial B vectorul )(la cu vectorul )(ka , obinndu-se astfel o nou baz B~ , iar pivotul corespunztor este lky . Mrimile tabelului simplex corespunztor noii baze B~ , se vor determina cu ajutorul unei reguli denumit regula dreptunghiului (pivotare n jurul elementului lky ), dup care se trece la Pasul 2. Algoritmul simplex primal pentru probleme de maximizare Acest algoritm are paii 1,2,5,6 identici cu algoritmul pentru probleme de minimizare. Pasul 3 : Se analizeaz toate diferenele jcz Bj :

Dac toate diferenele jcz Bj 0 , nj ,1= atunci programul Bx este optim.

Dac exist cel puin un indice j

J , { }0/ Bky se trece la Pasul 5. Algoritmul simplex poate fi exprimat sintetic sub urmtoarea schem logic ( fig.2.4).

Programare liniar

30

START

Construiestetabel simplex initial

Exista valori pozitive (negative) pe linia diferentelor?

Indica solutia optima STOP

Nu

Da

Determina coloana pivotului

Exista valori pozitive in coloana pivotului?

Nu Indica solutia optima STOP

Da

Determina linia pivotului

Calculeaza un nou tabel simplex

Fig.2.4

Exemplul 2.4 . S se rezolve urmtoarea problem de programare liniar:

( )

+

+

.2max0,

,62,183

,4

21

21

21

21

21

xxxx

xxxx

xx

Pentru a aplica algoritmul simplex, vom aduce mai nti problema la forma standard. n acest scop introducem variabilele ecart x3, x4 i x5:

( )

+

=++

=+

=+

.2max0,...,,

,62,183

,4

21

621

521

421

321

xxxxx

xxxxxx

xxx

Iteraia 1 Pasul 1 Fie B o baz admisibil a problemei format din coloanele matricii A i anume a3, a4 i a5:

( )

==

100010001

aaaB 543 ,,

Pasul 2 Baza B este matricea unitate, astfel vom calcula urmtoarele elemente: IBB ==1 i [ ]61841 === bbBxB ;


31

1= By Bj jj aa = , elementele matricii A.

( ) )00012(0001' ==== jjjjjBjBj ccacaBccz .01 == bBcz BB

Cunoscnd toate aceste date, putem forma tabelul simplex iniial ( tab.2.3). Pasul 3. Deoarece exist j

J , { }0/

min

0

= 14

318,1

4min =

,

deci indicele l = 3. Variabila x3 va prsi baza B. Pivotul este y31= 1 Pasul 6: Se nlocuiete n baza iniial B variabila x3 cu variabila x1 obinndu-se astfel o noua baza B~ ceea ce nsemn c se vor transforma toate mrimile urmtorului tabel simplex cu regula dreptunghiului. Interaia 2 Se realizeaz un pivotaj n jurul elementului y42 (tab.2.3).

Interaia 3. Se realizeaz un pivotaj n jurul elementului y53 (tab.2.3).

Interaia 4 Deoarece 0 jj cz pentru toi j, baza actual este optim. Deci programul optim al problemei noastre este

542

1 =x , 536

2 =x , 514

3 =x , 04 =x , 05 =x ( 4x i 5x au valoarea 0, deoarece sunt variabile secundare). Interpretare geometric.

Pentru problema examinat mai sus se poate da o interpretare geometric simpl n spaiu R2.

n planul x1Ox2, mulimea punctelor (x1, x2) care satisfac restricia 421 xx constituie unul din semiplanele determinate de dreapta 4xxd 211 =:)( , i anume semiplanul care conine originea.

Celelalte dou restricii determin analog alte dou semiplane. Mulimea programelor problemei va fi format din mulimea punctelor din primul

cadran ( )0,0 21 xx care se afl la intersecia celor trei semiplane. Aceast mulime este poligonul OABCD (fig. 2.5). Funcia obiectiv este max(2x1 +x2). Ecuaia 2x1 +x2 = z reprezint o familie de drepte

paralele ntre ele. n figura 2.4 sunt reprezentate punctat cteva din aceste drepte. Pentru z=z2, funcia

obiectiv ia valori mai mari dect pentru z = z1, iar pentru z = z3 valori i mai mari.

Programare liniar

32

Tabelul 2.3

2

V.V.BV.B.CB x2 x3 x4 x5

1 0 0 0

x3

x4

x5

0

0

0

xl

4

186

13

-1

-1-12

0 -2 -1 0 0 0

1 0 00 1 0

0 0 1

CB V.B. V.V.B x2 x3 x4 x5xl

x2 x3 x4 x5xl

x2 x3 x4 x5xl

2 1 0 0 0

2 1 0 0 0

2 1 0 0 0

2

0

0

x1

x4

x5

x1

x2

x5

x3

2

1

0

2

1

0

CB V.B. V.V.B

CB V.B. V.V.B

4

6

10

1

0

0

-1

2

1

1

-3

1

0

0

0

01

1

8 0 -3 2 0 0

7

3

7

17

1

0

0

1

0

0

-1/2

-3/2

5/2

1/2

1/2

-1/2

0

0

10 0 -5/2 -3/2 0

42/5

36/5

14/5

24

1

0

0

1

0

0

0

0

1

2/5

1/5

-2/5

1/5

3/5

2/5

0 0 0 1 1

x1

x2

536,

542C

B(7,3)

A(4,0)O (0,0)

D (0,3)

x2

x1

(d2)

(d1)

Fig.2.5

ns, dup cum se vede din figur, nu exist nici un program care s dea funciei

obiectiv valoarea z3 (dreapta 2x1 +x2 =z3 nu intersecteaz poligonul OABCD domeniul soluiilor).

Cea mai mare valoare pe care o poate lua z pentru punctele din poligonul OABCD se obine atunci cnd dreapta 2x1 +x2 = z trece prin punctul C. Valoarea lui z n acest caz este 2. 42/5 + 36/5 = 24.


33

Cnd am aplicat algoritmul simplex, drept baz iniial am luat baza B = (a3, a4, a5). Variabilele x1 i x2 sunt variabile secundare, deci au valoarea 0; reiese c ne-am gsit n vrful O (0,0) al poligonului OABCD, iar valoarea funciei obiectiv era z = 0. n continuare, variabila x1 intr n baz i am obinut programul x1 = 4, x2 = 0.

Geometric aceasta nseamn c din vrful O ne-am deplasat pn n vrful A (4,0) de-a lungul muchiei OA. n continuare, din vrful A am ajuns n vrful B, mergnd pe muchia AB (variabila x3 a pstrat tot valoarea 0, deci ne gseam pe dreapta d1). De aici am ajuns n vrful optim C, urmnd muchia BC.

Valoarea funciei obiectiv a crescut de la 0 la 8, apoi la 17 (n vrful B) i, n sfrit, la valoarea maxim 24.

Acest lucru este valabil i n cazul general: fiecrei baze admisibile a problemei adus la forma standard i corespunde un vrf al domeniului soluiilor.

Concluzie: Fiecare iteraie simplex reprezint o deplasare de la un vrf al domeniului soluiilor, pe o muchie, pn la un vrf, care confer funciei obiectiv o valoare mai bun. Exemplul 2.5.

O companie produce trei tipuri de produse A, B, C. Fiecare dintre aceste produse trebuie prelucrate tehnologic aceeai main unealt, timp de 2 ore, 3 ore respectiv 1 or. Maina unealt este disponibil pentru perioada analizat, 400 ore.

Pentru produsele A i C se folosesc componente speciale, cte o bucat pentru fiecare produs, firma avnd un stoc disponibil pe perioada analizat de 150 de uniti din aceste componente. Tot pentru produsele A i C se utilizeaz un aliaj special: pentru o unitate din produsul A se utilizeaz 2 kg de aliaj special, iar pentru o unitate din produsul C, 4 kg. Stocul disponibil este de 200 kg din acest aliaj special.

Studiul de pia pentru produsul B arat c se pot vinde pe perioada analizat cel mult 50 de uniti din acest produs.

Beneficiul unitar al produselor A, B i C este respectiv: 8 um (uniti monetare), 5 um, 10 um.

Compania dorete s stabileasc planul de producie care maximizeaz beneficiul total pe perioada analizat. Elaborarea modelului matematic

Notm x1 = numrul de produse A x2 = numrul de produse B x3 = numrul de produse C

unde x1, x2, x3 pentru modelul analizat reprezint variabilele de decizie.

+

+++

5020042

15040032

2

31

31

321

xxx

xxxxx

01 x , 02 x , 03 x )1058max( 321 xxxz ++=

Se observ c problema nu are form standard. Introducem variabilele de compensare x4, x5, x6, x7 i nlocuim max(z)=min(-z),

dorind s aplicm algoritmul simplex pentru probleme de minim. Calculele efectuate sunt grupate n tabelele simplex reunite n tabelul 2.4. Soluia optim este: x = (100, 50, 0, 50, 50, 0, 0), iar funcia obiectiv este min (f)= -

1050, deci max(z) = 1050 Interpretarea soluiei:

Variabilele de decizie au valorile : x1 = 100, x2 = 50, x3 = 0

Programare liniar

34

=+

=++

=++

=+++

5020042

15040032

72

631

531

4321

xxxxx

xxxxxxx

0ix )7,1( =i )1058min( 321 xxxf =

Matricea coeficienilor tehnico - economici este:

=

1000010010040200101010001132

A

Se vor fabrica 100 uniti din produsul A, 50 uniti din produsul B, zero uniti din produsul C.

Se va obine beneficiul maxim, egal cu 1050 uniti monetare. Semnificaia variabilelor de compensare rezult din modul cum au fost introduse.

Verificnd restriciile iniiale ale problemei cu soluia optim x1 = 100, x2 = 50, x3 = 0 i comparnd cu sistemul de restricii n care s-au introdus variabilele de compensare, rezult:

- orele de lucru pe main nu s-au folosit integral, rmnnd disponibile x4 = 50 ore; - componentele nu s-au folosit integral, rmnnd x5 = 50 uniti. - stocul de aliaj dup efectuarea prelucrrilor este nul x6 = 0 - este satisfcut condiia de vnzare pentru B, x7 = 0.

Tabelul 2.4

CB

CB

CB

CB

-8

V.V.BV.B. x2 x3 x4 x5

-5 -10 0 0

x4

x6

x5

0

0

0

xl

400

150200

2

1

2

3

0

0

0 8 5 10 0 0

1 1 01 0 14 0 0

V.B. V.V.B x2 x3 x4 x5xl

x2 x3 x4 x5xl

x2 x3 x4 x5xl

-8 -5 -10 0 0

0

0

0

x3

x4x5

00

-8

V.B. V.V.B

V.B. V.V.B

35010050

3/21/2

3

0

0

0

0

1

1

0

0100

-500 3 5 0 0 0

200

10050

-750

3/2

1/20

0

0

0

0

10

0

0

10

3 0 0 0 0

-1050

0

0

100

0

-3

-12

10

0

0

10

0 0 -6 0 0

x6 x7

0 0

0 0

0 0

0 0

01

0 0

-1/4

1/4

00-1/40

5/2 0

-1/41/41/4

-3

0

0

5/2 -5

-1-1/21/2

-3

0

0

-4 -5

0 x7 0 1 0 0 0 0 150

-5 -10 0 0 0 0-8x6 x7

x7

-1050

1/20 1 0 0 0 0 1

x6 x7

0

0

-5-10 x3

x4x5

x2 50

1/21

0 1 0 0 0 0 1

-5 -10 0 0 0 0-8x6 x7

x1

x4x5

x2-5

50

50

50100

0 1 0 0 0 0 1


35

2.3.3. Metode de determinarea unei soluii de baz iniiale Algoritmul simplex necesit, pentru pornire, ca problema s fie dat n forma standard

i s aib o soluie admisibil de baz. Prima dintre condiii se realizeaz folosind transformri utilizate n programarea

liniar. Pentru cea de-a doua condiie alegerea la ntmplare a unei baze format din m vectori

ai matricei A, conduce la soluii de baz nerealizabile cu care algoritmul simplex nu poate ncepe.

Gsirea unei baze pur i simplu prin ncercri repetate nu este indicat, aceast cutare putnd dura foarte mult.

Rezolvarea problemei pleac de la observaia c singura baz pentru care calculul de mai sus se poate face imediat este matricea unitate, caz n care soluia de baz corespunztoare este chiar vectorul termenilor liberi.

Aceasta presupune ca problema s aib toi termenii liberi mai mari sau egali cu 0 i n matricea A s existe toate coloanele matricei unitate.

n acest sens plecm de la observaia c existena unui vector din matricea unitate este echivalent cu existena unei variabile care apare doar n ecuaia corespunztoare lui 1 din acel vector, cu coeficientul 1. Acest lucru poate fi obinut n dou moduri:

1) Alegem o nou funcie obiectiv care s-i ating extremul printre soluiile pozitive chiar pentru y = 0 i n momentul cnd am obinut soluia respectiv pornim cu aceasta ca soluie iniial algoritmul simplex pentru fosta problem (Metoda celor dou faze). 2) Adugm la vechea funcie obiectiv noi variabile y cu coeficieni alei astfel nct aportul variabilelor la valoarea funciei s fie contrar scopului dorit (infinit pozitiv ntr-o problem de minim i infinit negativ ntr-o problem de maxim) (Metoda coeficienilor de penalizare)

Vom detalia n continuare cele dou metode: Metoda celor dou faze Fie dat problema de programare liniar la forma standard de maxim:

=

0xb xA

xcT'max (2.77)

n care am aranjat deja ca toi termenii liberi s fie pozitivi . Faza 1

Const n rezolvarea unei probleme de programare liniar auxiliar, asociat problemei iniiale. Astfel construim problema:

=+

+++= +++

0x,xbxIAx

xxxxf

a

am

anm

a2m

a1m

a )...min()( (2.78)

unde xa sunt variabilele artificiale ce se introduc n restriciile problemei att ct sunt

necesare n scopul formrii bazei unitare; Im matricea unitate de ordin m. Rezolvm cu algoritmul simplex aceast problem, pornind rezolvarea de la baza

matrice unitate, putem ajunge la dou situaii:

Programare liniar

36

1. minimul funciei f este strict pozitiv, aceasta fiind echivalent cu faptul c egalitatea Ax + Imxa = b se poate obine doar pentru Imxa > 0 sau altfel spus Ax > b pentru orice x 0, deci sistemul Ax = b nu are soluii admisibile i n concluzie problema iniial nu are soluie. 2. minimul funciei f este 0, n acest caz, soluia optim obinut verific Ax = b, fiind n concluzie o soluie admisibil de baz a primei probleme.

Faza 2

ncepnd de la soluia gsit la Faza 1 se rezolv problema iniial cu algoritmul simplex. Se ndeprteaz din tabelul simplex toate elementele corespunztoare variabilelor artificiale (cu excepia celor care rmn n baz), introducnd coeficienii funciei obiectiv din problema iniial.

Dezavantajul metodei const n faptul c tabelul simplex final de la faza 1 trebuie modificat pentru a se obine tabelul simplex iniial de la faza 2, eliminndu-se coloanele corespunztoare lui y i totodat nu vom avea n tabelele simplex ale problemei iniiale inversa bazei (se gsea n dreptul coloanelor matricei unitate din prima faz) necesar n anumite variante ale algoritmului simplex.

Metoda coeficienilor de penalizare

Fie problema de programare liniar la forma standard de minimizare:

=

0xbxAxcTmin

(2.79)

n care toi termenii liberi sunt pozitivi i matricea A nu conine nici un vector coloan unitar.

Construim problema:

=+

=

0yx,byxAMy)xcf Tmax(

(2.80)

n care M este o constant presupus foarte mare (mai mare dect orice constant care

ar putea apare n rezolvarea problemei). Rezolvm problema cu algoritmul simplex pornind rezolvarea de la baza matrice

unitate, putnd ajunge la trei situaii: 1) problema are optim infinit, n acest caz, problema iniial are optim infinit ( nu prezint interes din punct de vedere tehnico-economic). 2) problema are optim finit i n soluia de baz avem cel puin o variabil din vectorul y. n acest caz problema iniial nu are soluii admisibile. 3) problema are optim finit i n soluia de baz nu avem nici o variabil din vectorul y. n acest caz problema iniial are optim finit, soluia optim i maximul funciei fiind aceleai cu cele ale problemei modificate. Se remarc faptul c variabilele y nu au aceeai semnificaie economic ca celelalte

variabile, ele fiind introduse doar ca un artificiu de calcul pentru a putea porni algoritmul simplex.

Observaii : Dac matricea restriciilor conine vectori unitari, atunci numrul variabilelor artificiale introduse este egal cu m, numrul vectorilor unitari, indiferent de tipul funciei obiectiv.


37

Dac la aplicarea algoritmului simplex, o variabil artificial iese din baz ea nu va mai intra niciodat, ceea ce arat eliminarea din calculele ulterioare.

Exemplu 2.6 Un atelier de prelucrri mecanice fabric dou produse P1 i P2. Din structura de dezagregarea produselor se deduce c pentru realizarea produsului P1

sunt necesare 3 componente de tip A i un component de tip B, iar pentru realizarea produsului P2 sunt necesare 1 component de tip A i 4 componente de tip B.

Atelierul dispune n stoc de 10 componente de tip A. Contractele cu furnizorii pentru componentele de tip B, arat c se poate realiza aprovizionarea cu acesta n cantitate de cel puin dou componente B.

Beneficiul unitar pentru produsele P1 i P2 sunt de 2 um, respectiv de 3um. Se dorete s se stabileasc planul de producie care s maximizeze beneficiul total. Modelul matematic este urmtorul:

+++=

0xx2x4x

10xx3x3x2f

21

21

21

21

,

)max(

unde 21 xx , , reprezint numrul de produse de tip P1 respectiv P2. Forma standard a problemei va fi:

( )

=+

=+++=

0xxxx2xx4x

10xxx3x3x2fmax

4321

421

321

21

,,,

n matricea A vom introduce variabila x5 cu coeficientul 1 n a doua ecuaie i

mpreun cu coeficienii variabilei x3 n final vom avea de rezolvat problema prin cele dou metode:

Metoda celor dou faze Metoda coeficienilor de penalizare

=++

=++

0xxxxx2xxx4x

10xxx3x

54321

5421

321

5

,,,,

)min(

=++

=+++

0xxxxx2xxx4x

10xxx3Mxx3x2

54321

5421

321

521

,,,,

)max(

Aplicnd Metoda celor dou faze vom obine succesiv tabele:

0 0 0 0 1 cB xB xB x1 x2 x3 x4 x5 0 x3 10 3 1 1 0 0 1 x5 2 1 4 0 -1 1 2 1 4 0 -1 0 0 0 0 0 1 cB xB xB x1 x2 x3 x4 x5 0 x3 19/2 11/4 0 1 1/4 -1/4 0 x2 1/2 1/4 1 0 -1/4 1/4 0 0 0 0 0 -1

Programare liniar

38

Am obinut optimul egal cu 0 n soluia de baz (x3,x2) care va fi soluia iniial pentru algoritmul simplex aplicat problemei iniiale n a doua faz.

Eliminm din tabel coloana lui x5, nlocuim valorile coeficienilor funciei obiectiv i deci i valoarea acesteia, valorile jBj cz i rezolvm problema n continuare, plecnd de la baza primal admisibil determinat, cu algoritmul simplex primal, obinnd tabelele de mai jos:

2 3 0 0 cB xB xB x1 x2 x3 x4 0 x3 19/2 11/4 0 1 1/4 3 x2 1/2 1/4 1 0 -1/4 3/2 -5/4 0 0 -3/4 2 3 0 0 cB xB xB x1 x2 x3 x4 0 x3 4 0 -11 1 3 2 x1 2 1 4 0 -1 4 0 5 0 -2 2 3 0 0 cB xB xB x1 x2 x3 x4 0 x4 4/3 0 -11/3 1/3 1 2 x1 10/3 1 1/3 1/3 0 20/3 0 -7/3 2/3 0 2 3 0 0 cB xB xB x1 x2 x3 x4 0 x4 38 11 0 4 1 3 x2 10 3 1 1 0 30 7 0 3 0

Soluia optim a primei probleme este deci x1 = 0 i x2 = 10 care d un maxim al funciei

egal cu 30. Aplicnd Metoda coeficienilor de penalizare vom obine succesiv urmtoarele tabele:

2 3 0 0 -M

cB xB xB x1 x2 x3 X4 x5 0 x3 10 3 1 1 0 0

-M x5 2 1 4 0 -1 1 -2M -M -4M 0 M -M -M-2 -4M-3 0 M 0 2 3 0 0 -M

cB xB xB x1 x2 x3 x4 x5 0 x3 19/2 11/4 0 1 -1/4 3 x2 1/2 1/4 1 0 -1/4 1/4 3/2 -5/4 0 0 -3/4 M+3/4 2 3 0 0 -M

cB xB xB x1 x2 x3 x4 x5 0 x3 4 0 -11 1 3 -3 2 x1 2 1 4 0 -1 1 4 0 5 0 -2 2+M 2 3 0 0 -M

cB xB xB x1 x2 x3 x4 x5 0 x4 4/3 0 -11/3 1/3 1 -1 2 x1 10/3 10/3 1 1/3 0 0 20/3 0 -7/3 2/3 0 M 2 3 0 0 -M

cB xB xB x1 x2 x3 x4 x5 0 x4 38 11 0 4 1 -1 3 x2 10 3 1 1 0 0 30 7 0 3 0 M


39

2.3.4. Interpretarea a algoritmului simplex primal

Se consider problema de optimizare a activitii unei firme productoare. Aceasta realizeaz n produse , cu un profit unitar cj , n,j 1= . Firma utilizeaz mai multe resurse prime Ri , m,i 1= , disponibile n cantitile limitate bi. Consumurile specifice de resurse pentru fiecare produs sunt aij , m,i 1= , n,j 1= .

Obiectivul firmei este obinerea unui profit total maxim, cu restriciile ce provin din consumul integral al resurselor disponibile . Modelul de optimizare a activitii firmei este reprezentat de problema de programare liniar n forma standard :

=

=

0xbAx

xcz T(max) (2.81)

n care xj , nj ,1= , este cantitatea din produsul j ce urmeaz a fi fabricat.

Consumarea (utilizarea) integral a resurselor nu este strict, deoarece n lista operaiilor productive se poate include un numr de operaii fictive (corespunztoare variabilelor ecart) ale cror valori s reprezinte cantitatea din resurse neconsumat. n soluia de baz a algoritmului simplex numrul componentelor nenule nu depete numrul restriciilor.

De aceea, n orice soluie optim a problemei, numrul produselor ce urmeaz a fi fabricate nu depete numrul resurselor folosite . Coloanele a(j) din baza B ce corespund operaiilor j le vom numi operaii de baz, celelalte fiind operaii secundare.

Programul optim prevede obinerea, numai prin operaiile de baz, a produselor, astfel nct s fie consumate integral resursele disponibile.

O posibilitate de a obine un program mai bun const n identificarea unor operaii secundare care s nlocuiasc o parte din operaiile de baz curente. Pentru acesta este necesar un criteriu de comparare a operaiilor secundare cu cele de baz . n ipoteza c baza B=[a(1), a(2), ..,a(m)], din relaia (2.59)

yBj=B-1a(j) , nj ,1= (2.82) deducem :

A(j)= ByBj , nj ,1= (2.83) care se poate scrie

)()()()( ... mBmj2B

j21B

j1j AyAyAyA +++= (2.84)

Relaia de mai sus are urmtoarea semnificaie din punct de vedere tehnico-economic,

fabricarea unei uniti de produs j este echivalent cu fabricarea cantitilor BmjBj2B j1 yyy ,...,,, din produsele operaiilor de baz. Ca urmare, pentru fabricarea unei uniti din produsul j este necesar a diminua producia operaiilor de baz cu cantitile BmjBj2Bj1 yyy ,...,, .

Programare liniar

40

Aportul produsului j la creterea profitului firmei poate fi comparat cu aportul valoric al cantitilor BmjBj2B j1 yyy ,...,,, .

n consecin, dac:

0cycycyccz jBmjm

Bj22

Bj11j

Bj +++= ... (2.85)

fabricarea produsului j nu este rentabil ntruct nu conduce la o majorarea valorii (profitului) produciei curente. Dac pentru toate operaiile secundare avem

n,j,cz j

Bj 10 = (2.86)

atunci programul de fabricaie curent este optim. Acesta este, criteriul de optimalitate al algoritmului simplex. Dac 0

= (2.89)

Presupunem c valoarea 0 se obine pentru indicele 1. Atunci:

00 ===BlkB

lk

BlB

lBlk

Bll y

yxxyxx (2.90)

Ca urmare, operaia l nu va mai fi folosit, iar n locul ei se va utiliza operaia k, care asigur creterea maxim a valorii curente a produciei i, implicit, maximizeaz profitului firmei.


41

Aceasta este interpretarea a criteriului de ieire din baz al algoritmului simplex. Cazul optimului infinit, ca soluie a problemei de programare liniar, nu este semnificativ din punct de vedere economic.

2.4. Dualitatea n programarea liniar 2.4.1. Problema dual. Fundamente teoretice. Problema dual Dualitatea n programarea liniar ocup un rol important att din punct de vedere teoretic ct i din punct de vedere practic. Pe teoremele de dualitatea se bazeaz muli algoritmi de rezolvare a problemelor de programare liniar.

Fie problema de programare liniara dat sub forma general numit problema primal :

( )

++

++=++

++

332211321

333323213123312221211313212111

00xcxcxcmin

x;arbitrarx;xbxaxaxabxaxaxabxaxaxa

problema primal (2.91)

Numim problem dual a problemei de programare liniara urmtoarea problema de

programare liniara: ( )

++=

++++++

00 321333322311323322221121331221111

332211

u;arbitraru;ucuauauacuauauacuauaua

ubububmax

problema dual (2.92)

Observm c duala problemei dualei este chiar problema primal. Datorit legturii

strnse ce se stabilete ntre aceste probleme care sunt duale una celeilalte, vom spune ca problema (2.91) i problema (2.92) formeaz un cuplu de probleme duale.

Problema dual se obine din problema primal folosind urmtoarele transformri :

- Termenii liberi din problema primal devin coeficieni ai funciei obiectiv din problema dual.

- Coeficienii funciei obiectiv din problema primal devin termeni liberi n problema dual.

- O problem de maximizare primal devine problem de minimizare dual. - Matricea coeficienilor din problema dual este transpusa matricei coeficienilor

din problema primal - Variabilele duale corespunztoare unor restricii concordante din problema primal

sunt nenegative, iar cele corespunztoare unor restricii primale neconcordante sunt nepozitive.

- Variabilele primale negative le corespund n problema dual restricii concordante, iar variabilelor primale pozitive le corespund n problema dual restricii neconcordante.

Programare liniar

42

- Variabilele duale corespunztoare restriciilor primale care sunt ecuaii, pot fi de semn oarecare. - Variabilelor primale oarecare le corespund restricii duale care sunt ecuaii.

Exemplul 2.7 Determinai duala problemei de programare liniar:

f = max(2x1 5x2 + 4x3)

++=+

+

85232

63574

213

31

312

321

xxxxx

xxxxxx

x1 0, x2 oarecare, x3 0

Conform regulilor de mai sus vom avea: duala este de minim deoarece primala este de maxim; variabilele dualei vor fi:

u1 corespunztoare restriciei: x1 x2 + 4x3 7 u2 corespunztoare restriciei: x2 5x1 + 3x3 = 6 u3 corespunztoare restriciei: x1 + 2x3 3 u4 corespunztoare restriciei: x3 + 2x1 - 5x2 8

funcia obiectiv a dualei va fi produsul dintre termenii liberi ai restriciilor primalei cu

variabilele corespunztoare din dual: g = 7u1 + 6u2 + 3u3 + 8u4

duala va avea 3 restricii, cte variabile are primala, ele obinndu-se astfel: Prima restricie (asociat variabilei x1) - termenul stng al restriciei se obine nmulind coeficienii variabilei x1 din cele 4 restricii ale primalei cu variabilele corespunztoare acestora din dual: u1 5u2 + u3 + 2u4 - termenul liber al restriciei va fi coeficientul lui x1 din funcia obiectiv a primalei, adic b1 = c1 = 2 - deoarece variabila corespunztoare acestei restricii, x1, este negativ, restricia va fi neconcordant i deoarece duala este problem de minim rezult c va fi cu . n concluzie, prima restricie va fi: u1 5u2 + u3 + 2u4 2 Analog se vor determina i celelalte dou restricii:

-u1 + u2 - 5u4 = -5 4u1 + 3u2 + 2u3 - u4 4

restriciile de semn ale variabilelor dualei vor fi: u1 0, deoarece restricia corespunztoare este neconcordant; u2 oarecare, deoarece restricia corespunztoare este egalitate; u3 0, deoarece restricia corespunztoare este concordant; u4 0, deoarece restricia corespunztoare este neconcordant.

n final, problema dual este: (min) 7u1 + 6u2 + 3u3 + 8u4

++=+

++

423455

425

4321421

4321

uuuuuuu

uuuu

u1 0, u2 oarecare, u3 0, u4 0


43

Exemplul 2.8 S se scrie duala problemei de programare liniar dat n form canonic:

( )

+

+++++

0,...,10252

153523max

41

432

431

4321

4321

xxxxxxxx

xxxxxxxx

Se construiete tabelul cu datele problemei iniiale:

Aadar, problema dual este:

( )

+

++

++

0,,1

5232

310515min

321

321

321

31

21

321

xuuuuu

uuuuu

uuuuu

Fundamente teoretice

Fr a restrnge din generalitate ne vom ocupa n continuare de cuplul de probleme duale (2.91) - (2.92), prima fiind considerat problema primal, iar cea de-a doua, problema dual.

Se noteaz { }0, == xbAxRxP n (2.93)

{ }0, = ucuARuD Tm 2.94) Mulimile soluiilor admisibile (sau programelor) ale problemei primale (2.91),

respectiv, duale (2.92). Teorema 2.8. Dac Px i Du , atunci ubxc TT . Teorema 2.9. Fie Px * , Du * i ** ubxc TT . Atunci x* nu este soluie optim a problemei primale, iar u* este soluie optim a problemei duale Propoziia 2.1. Dac L este o matrice antisimetric (LT = -L), atunci sistemul de inegaliti liniare

maxmin 3 2 15

15

10

u1u2u3

1 -1 3 1-1 -1

-12 00 1 2

5

x1 x2 x3 x4

Programare liniar

44

0

0t

tl (2.95)

are cel puin o soluie t astfel nct

0> tL (2.96) Teorema 2.10. (Teorema fundamental a dualitii) Fie cuplul de probleme duale (2.91) - (2.92). Atunci una i numai una din urmtoarele situaii este posibil :

a) Ambele probleme au soluii admisibile. n acest caz, ambele probleme au soluii optime i valori optime ale funciilor obiectiv sunt egale.

b) Una din probleme are soluii admisibile, iar cealalt nu are (este incompatibil). n acest caz, problema compatibil are optim infinit.

c) Nici una dintre probleme nu are soluii admisibile. Teorema 2.11. (Teorema ecarturilor complementare). Fie cuplul de probleme duale canonice (2.91) - (2.92). Atunci Px i Du sunt soluii optime pentru cele dou probleme dac i numai dac:

( )( )

=

=

0

0

uAcu

bxAuTT

T

(2.97)

Exemplul 2.9

ntr-un atelier mecanic se produc dou de tipuri de piese P1, P2. Timpii unitari de prelucrarea celor dou piese pe cele dou maini unelte M1, M2,

profitul unitar i disponibilul de timp al mainilor unelte sunt date n tabelul de mai jos:

P1 P2 Disponibil resur

cercetari operationale

Documents

Transcript of cercetari operationale