ELEMENTE DE PROGRAMARE LINIARA

1 Formularea problemei

Programarea liniara se ocupa cu rezolvarea problemelor de optimizare a functiilor liniare de gradul intai in raport cu variabilele independente, in general supuse la restrictii care sunt, de asemenea, relatii de gradul intai.

Componentele principale ale unei probleme de programare liniara sunt:

a)      o functie-obiectiv sau functie scop - functie de gradul intai, in doua sau mai multe variabile independente;

b)      restrictii (structurale), constand intr-un sistem de inegalitati de gradul intai;

c)      conditii de pozitivitate (anumite marimi fizice cum ar fi: consumuri de materiale, numere de obiecte sau persoane pot fi reprezentate numai prin cantitati pozitive).

Functia-obiectiv poate fi un cost (care se minimizeaza) sau un consum de materiale (care trebuie, de asemenea, minimizat), sau un profit (care se maximizeaza) etc. O problema de maximum poate fi redusa intotdeauna la o problema de minimum si invers, printr-o schema simpla de tipul:

max f(x) = - (min (- f(x))).

Restrictiile structurale (inegalitati) sunt legate de mijloacele limitate de care dispunem: materiale, spatiu, timp etc.

Rezolvarea problemei de optimizare incepe cu stabilirea domeniului de admisibilitate, in care solutia este posibila sau realizabila. Acesta este un domeniu in spatiul variabilelor independente si este dat de restrictiile structurale si de pozitivitate. Daca domeniul de admisibilitate este vid, solutia nu exista (nu avem optim). Altfel, solutia exista putand fi unica sau multipla. Optimul se cauta in varfurile domeniului de admisibilitate.

2 Optimizarea functiilor de doua variabile. Exemple

Vom incepe cu cazul in care avem numai doua variabile independente. In acest caz se poate determina si o solutie grafica a problemei de optimizare.

Problema 1 Sa presupunem ca dorim sa maximizam volumul vanzarilor saptamanale intr-o intreprindere care produce obiectele de consum P₁ si P ₂, avand preturile de preturile de vanzare de 10 UM si respectiv 25 UM. Producerea lui P ₁ necesita 0.5 ore de manopera si 2.5 kg de material, iar producerea lui P ₂ necesita 1.5 ore manopera si 1 kg material. Se dispune de 6 lucratori care lucreaza 40 ore / saptamana si de 400 kg de material. Care este cantitatea optima care trebuie produsa din P ₁ si P ₂ ?

Rezolvare

Fie x₁ si x₂ cantitatile produse din cele doua obiecte de consum. Functia obiectiv care trebuie maximizata este valoarea produsa saptamanal:

V = 10x₁ +25x₂ , V = V_max . (2)

Restrictiile structurale sunt legate de timp si de cantitatea de material:

0.5x₁ + 1.5x₂ 6 40 = 240 ore ;

2.5x₁ + x₂ 400 kg material. (3)

La aceste restrictii se adauga conditiile de pozitivitate:

x 0; x₂ 0. (4)

Conditiile (3) se scriu cu ajutorul a doua drepte prin taieturi:

(D₁)

(D₂)

Fig. 1 Domeniul de admisibilitate

Domeniul de admisibilitate este , limitat de axele x₁ = 0, x₂ = 0 si de dreptele D₁ si D₂. S-a observat ca originea O satisface inegalitatile (3), deci apartine domeniului, (v. fig. 1).

Punctele de maxim se gasesc printre varfurile V₁, V₂, V₃ ale domeniului . Avem: V₁ (160;0), V₂ (1440/13;1600/13), V₃ (0;160). Rezulta:

V(V₁) = 1600 UM ; V(V₂) = 4184.62 UM ; V(V₃) = 4000 UM .

Prin urmare, maximul corespunde varfului V₂ al domeniului de admisibilitate. Solutia este unica si are o interpretare geometrica simpla: o paralela prin V₂ la dreapta V = 10x₁ + 25x₂ = constant = k, are valoarea cea mai mare pentru k cand x₁ = 1440/13, x₂ = 1600/13, fata de orice alt punct din . Pentru comparatie, in Fig.1, s-a reprezentat dreapta V in cazul k=2000.

Daca valorile trebuie sa fie nr. intregi, vom lua x₁ = 177 110, si x₂ = 123.08 123. Rezulta, cu aceste valori intregi, V_max =4175 UM. In acest fel, s-a optimizat volumul vanzarilor (V = 4184,62 UM). Se pun insa si alte probleme, cum ar fi: folosirea integrala a materialelor si a timpului de lucru. Se observa ca solutia optima (V₂) utilizeaza integral resursele, in timp ce varful V₃ realizeaza un volum de vanzari apropiat de maximum, dar lasa material la dispozitie. Este deci de vazut daca materialul economisit compenseaza venitul mai mic realizat.

2.1 Utilizarea variabilelor de compensare (ecart).

Putem transforma inegalitatile structurale (3) in egalitati prin introducerea unor variabile auxiliare S₁, S₂, numite variabile de compensare (variabile ecart).

Astfel, in loc de (3) vom scrie:

0.5x₁ + 1.5x₂ + S₁ = 240; S₁ 0; (5-a)

2.5x₁ + x₂ + S₂ = 400; S₂ 0. (5-b)

Celelalte relatii raman neschimbate. Eliminand din (5 a,b) x₁ si x₂ in functie de S₁, S₂, se obtine:

; x₁ 0; (6-a)

; x₂ 0. (6-b)

Introducand (6 a,b) in valoarea produsa saptamanal, se obtine:

(7)

V_max = 4184,62 se obtine, evident, pentru S₁ = S₂ = 0.

Din (6 a,b), pentru S₁ = 0 si S₂ = 0, se obtin coordonatele punctului V₂.

Din (7) mai obtinem:

(8)

adica alocarea de timp suplimentar pentru manopera (S₁ < 0) este de 21 ori mai eficienta decat repartizarea unei cantitati suplimentare de material. Costul pe unitatea de resursa alocata in plus se numeste cost de oportunitate si se calculeaza cu ajutorul derivatelor partiale: si

Problema 2

Cu datele din problema 1, se impune conditia ca numarul de obiecte produse sa fie minim 250, adica:

x + x₂ 250. (9)

Rezolvare.

Inegalitatea suplimentara (9) se transforma in egalitate prin introducerea variabilei ecart S₃, astfel incat se poate scrie:

x + x₂ - S₃ = 250; S₃ 0; (10)

Din (10) si (6 a,b), calculam:

S = x₁ + x₂ - 250 =

Deoarece S₁ 0, S₂ 0 din (11) rezulta S₃ < 0, ceea ce contrazice (10) care impune S₃ 0. Prin urmare, problema de optim (2) nu are solutie. Se poate verifica si grafic ca semiplanul x₁ + x₂ 250 este in afara domeniului de admisibilitate.

Problema 3

Pentru transportul de marfuri si pasageri intre doua localitati se pot folosi trenul si vaporul. Cu trenul, se pot transporta 600 calatori sau 60 tone marfa la o cursa, iar cu vaporul 300 calatori si 100 tone marfa la o cursa. Care este numarul de curse de tren si vapor care asigura costul minim, stiind ca o cursa de tren costa 1260 UM, una de vapor 700 UM, iar numarul minim de calatori de transportat este 3300, in timp ce marfa de transportat este de minim 680 tone.

Rezolvare

Fie x₁ numarul de curse de tren si x₂ numarul de curse de vapor. Costul total trebuie minimizat, adica avem de gasit :

min C = 1260x₁ + 700x₂, (12)

cu restrictiile:

600x₁ + 300x₂ 3300 ; (13-a)

60x₁ + 100x₂ 680 ; (13-b) x₁ 0; x₂ 0 ; (14)

Dreptele (D₁) , de ecuatie 600x₁ + 300x₂ = 3300 si (D₂) de ecuatie 60x₁ + 100x₂ = 680, se taie in punctul V₂ (3,5). Acest punct reprezinta minimul pentru costul C (fig. 2):

A

A

Fig. 2

= 1260 5 = 7280 UM.

Celelalte varfuri dau, respectiv:

= 1260 34/3 = 14280 UM; 11 = 7700 UM.

Domeniul de admisibilitate, , este deschis (fig. 2). Solutia este unica, iar transportul asigurat este de 3300 calatori si 680 tone marfa. In cazul cand se introduc variabile ecart, in loc de ineglitatile (13 a,b) se scrie:

600 x₁ + 300 x₂ - S₁ = 3300; S₁ 0; (15-a)

60 x₁ + 100 x₂ - S₂ = 680; S₂ 0, (15-b)

de unde se obtine:

(16)

si costul:

C = 7280 + 2S₁ + S₂; S₁ 0; S₂ 0; (17)

Din (17), este evident C_min = 7280 UM, pentru S₁ = S₂ = 0. Deoarece , rezulta ca este de doua ori mai putin eficienta cresterea/reducerea cantitatii de marfa/tona, in raport cu cresterea/reducerea numarului de pasageri transportati (cost de oportunitate).

Problema 4

Sa se minimizeze costurile de transport in conditiile problemei (3), daca va creste costul cursei de vapor de la 700 UM la 735 UM, iar pentru cursa de tren la 1470 UM.

Rezolvare

In acest caz avem de minimizat functia:

C = 1470x₁ + 735x₂ , (18)

cu aceleasi restrictii (13) si (14). Expresia functiei obiectiv C devine, in variabilele de compensare S₁, S₂:

C = 8085 + 2S₁; S₁ 0; S₂ 0, (19)

si admite minimul C_min = 8085, indiferent de S₂, adica problema admite o infinitate de solutii, situate pe segmentul (fig. 2) al dreptei (D₁). In particular, se pot face numai curse cu vaporul (11 la numar).

Observatie: Modul grafic de rezolvare sau prin eliminarea unor variabile este adecvat optimizarii functiilor obicetiv care depind de un numar mic de variabile (maximum trei). Pentru cazurile mai complicate exista programe pe calculator, bazate pe diversi algoritmi cum ar fi: algoritmul simplex primal, metoda penalizarii, algoritmul simplex dual.

3 Algoritmul simplex primal (Dantzig 1948).

3.1. Forma standard.

Acest algoritm se aplica problemei de programare liniara scrisa sub forma de mai jos, denumita forma standard:

optim F = (20-a)

(20-b)

x_j 0, (20-c)

Functia-obiectiv care se optimizeaza (maxim sau minim) contine k variabile supuse la m conditii. De obicei, ecuatiile (20-b) provin din inegalitati, care se transforma in egalitati prin adaugarea unor variabile suplimentare (auxiliare), astfel ca numarul de variabile creste fata de forma nonstandard. De asemenea, numarul de variabile din functia obiectiv se poate modifica, daca variabilele initiale care apar in aceasta functie nu satisfac conditia de pozitivitate.

Daca o variabila este oarecare (poate lua valori pozitive si negative), ea se poate inlocui prin diferenta a doua variabile arbitrare pozitive, deci numarul de variabile va creste cu o unitate.

Avand in vedere consideratiile de mai sus, se poate admite fara a reduce generalitatea ca m < n.

Problema 5

Sa se aduca la forma standard modelul de mai jos:

max F = 3x₁ - 4x₂ + 2x₃ (21-a)

2x₁ - x₂ + x₃ 4 (21-b)

-3x₁ + 2x₂ -2 (21-c)

3x₂ - 5x₃ (21-d)

, x₂ oarecare, x₃ 0. (21-e)

Rezolvare. Deoarece x₃ 0, se face substitutia x₃ = -x₄; x₄ > 0, variabila x₂ fiind oarecare se inlocuieste cu diferenta a doua variabile pozitive:

x₂ = x₅ - x₆; x₅ 0, x₆ 0.

Mai departe, se introduc variabilele auxiliare x₇, x₈ pentru a transforma cele doua inegalitati (21-b,c). Ca urmare, modelul standard arata dupa cum urmeaza:

max F = 3x₁ - 2x₄ - 4x₅ + 4x₆ (22-a)

2x₁ - x₄ - x₅ + x₆ - x₇ (22-b)

-3x₁ + 2x₅ - 2x₆ + x₈ = -2 (22-c)

5x₄ + 3x₅ - 3x₆ = -5 (22-d)

x_i 0, i (22-e)

Dupa cum se vede, in cazul de fata avem k = 6 (cu coeficientii c₂ = c₃ = 0, in relatia 20-a), m = 3, iar n = 6.

Mai departe, aplicarea algoritmului simplex primal cere ca in forma standard; a) toti termenii liberi sa fie pozitivi: b_i 0 ; b) in matricea sistemului (20-b) sa existe m coloane din matricea unitate. Conditia a) se poate realiza intotdeauna; conditia b) este mai restrictiva si poate cere introducerea unor variabile artificiale (metoda penalizarii).

3.2. Solutie admisibila a problemei de programare liniara este un set de numere (x_j), j care satisface conditiile (20-b,c). O solutie care are cel putin (n - m) componente nule se numeste solutie admisibila de baza. Daca solutia de baza are exact (n - m) componente nule, se spune ca este nedegenerata. Solutia care realizeaza optimul functiei obiectiv se numeste solutie optimala sau, simplu, optim. Optimul poate fi unic sau multiplu. Optimul poate fi si infinit. In cazul cand optimul nu exista, algoritmul poate sa cicleze.

Testarea optimului se face dupa semnul coeficientiilor variabilelor din expresia functiei obiectiv, dupa cum se doreste maxim sau minim. In cazul maximului, toti coeficientii trebuie sa devina, in final, negativi. Problema de minim se poate transforma in problema de maximum dupa regula: min f(x) = - max(-f(x)).

Sa revenim la forma standard (20 a,b,c) a problemei de programare liniara si sa scriem matricea A si variabila-vector X, punand in evidenta variabilele de baza (B) si variabilele secundare (S):

A ; X = (23)

unde B este o matrice inversabila de dimensiuni m x m, iar S o matrice de dimensiuni m(n - m). Sistemul restrictiilor, Ax = b, devine:

BX^B + SX^S = b; X^B = B^-1b - B^-1SX^S, (24)

iar functia-obiectiv ia forma:

F = CX = (25)

F = C^BB^-1b + (C^S−C^BB^-1S)X^S, (26)

unde C = (C₁, C₂, ., C_n) este vectorul (linie) coeficientilor din functia obiectiv.

Deoarece in algoritmul simplex primal matricea B este matricea unitate (B = I_m), relatiile de mai sus se simplifica. Mai mult, in fiecare etapa, se alege solutia cu variabilele secundare nule; astfel din (24) rezulta: X^B = b; (X^S = 0),

iar relatia (26) se mai scrie (B^-1= I_m):

F = C^BX^B + (C^{S _} C^BS)X^S. (27)

Pentru X^S = 0, din (27), se obtine F = F₀ = C^BX^B. Trebuie insa stabilit daca valoarea F₀ = C^BX^B este intr-adevar optima. In acest scop se face un test de optimalitate. Deoarece in general X^S are componente pozitive, se testeaza semnul componentelor vectorului-test, , dat de relatia :

, i (28)

i_B, i_S fiind multimile de indici ale variabilelor de baza si secundare, respectiv.

Observatie: Daca extindem (28) pentru , se obtine:

,i, (28-a) intrucat elementele fac parte din matricea I_m.

S-a convenit sa se ia semnul "+" (+) pentru cazul problemei de maxim si semnul "−"(− pentru cazul problemei de minim. In acest fel, daca (+)< 0, conform relatiei (27) s-a atins un maximum global unic, F = C^BX^B; daca (−) < 0, s-a atins un minim global unic. Daca unul din coeficienti τ_k = 0, k fixat, optimumul este multiplu, intrucat componenta x_k poate lua orice valoare (pozitiva). Conditiile de optim global formulate mai sus sunt suficiente (nu neaparat si necesare).

Daca nu s-a atins optimumul, se procedeaza la schimbarea bazei. In acest scop, variabilele din baza sunt inlocuite succesiv cu variabile secundare, dupa criteriile care urmeaza.

Criteriu de optim infinit

Daca exista k astfel incat (+ _k) > 0, in cazul maximului, respectiv (- _k) > 0 in cazul cautarii minimului si coeficientii a_ik 0, i, atunci exista un optimum infinit (+ ∞ pentru maxim, - ∞ pentru minim).

3.3. Criteriu de intrare in baza.

Daca semnul variabilei _j nu corespunde problemei de maxim sau de minim, se determina indicele k astfel incat:

(29)

Intra in baza variabila . Daca exista mai multe valori ale lui k dat de (29) se foloseste o metoda de perturbatii, care introduce un criteriu suplimentar. Altfel, se alege una din valorile obtinute.

3.4. Criteriu de iesire din baza.

Variabila care va fi inlocuita de x_k, precizata mai sus, se alege dupa criteriul raportului minim r, definit de:

, a_ik > 0, i = i_min . (30)

Aceasta alegere implica ramanerea in X^B a componentei cu ponderea cea mai mare. Iese din baza variabila . Daca mai multi indici satisfac (30), se foloseste o metoda de perturbatii sau se alege unul dintre ei.

Problemele care se apropie cel mai mult de conditiile cerute de aplicarea algoritmului simplex dual sunt cele cu restrictii de tip "", care introduc variabile suplimentare cu semnul (+), astfel incat apar coloane din matricea unitate. Restrictiile "", care limiteaza superior sunt adecvate, in general, problemelor de maxim. De aceea vom incepe prin prezentarea unui astfel de exemplu.

3.5. Exemple.

Problema 6

Sa revenim la problema 1, adaugand un al treilea produs, P₃, care se produce in cantitatea x₃ si are pretul unitar de vanzare de 15 UM/produs, iar timpul necesar manoperei si cantitatea de material ceruta sunt, respectiv, 1 ora si 2 kg. Se mai adauga restrictia ca numarul total de bucati produse din cele trei obiecte de consum sa nu depaseasca 200.

Problema de programare liniara va avea trei variabile si se formuleaza astfel:

maxV = 10x₁ + 25x₂ + 15x₃ (31-a)

0.5x₁ + 1.5x₂ + x₃ 240 ore (31-b)

2.5x₁ + x₂ + 2x₃ 400 kg (31-c) x₁ + x₂ + x₃ 200 bucati, x_i 0, . (31-d) Pentru transformarea inegalitatilor in egalitati se introduc variabilele suplimentare x₄, x₅, x₆, nenegative, ajungandu-se la formularea standard:

maxV = 10x₁ + 25x₂ + 15x₃ (32)

0.5x₁ + 1.5x₂ + x₃ + x₄ = 240 ; (33-a)

2.5x₁ + x₂ + 2x₃ + x₅ = 400 (33-b)

x₁ + x₂ + x₃ + x₆ = 200, x_i 0, . (33-c)

Rezultatele sunt trecute in Tabelul 1. S-a notat cu suma:

, i1,m; (34) Se obtine, in etapa a III-a:

. (35)

Valoarea maxima, maxV = 4100, rezulta pentru x₁ = 60 bucati, x₂ = 140

bucati si x₃ = 0. Pentru acesta repartitie, volumul de manopera se consuma in

intregime (x₄ = 0) si se realizeaza maximul impus de 200 bucati (x₆ = 0).

Raman neutilizate x₅ = 110 kg material.

Tabelul 1

Maxim. Problema 6

3.6. Verificari.

Din etapa I in etapa a III-a, matricea initiala A a fost supusa unor transformari ca urmare a eliminarilor facute operand cu liniile matricei in vederea introducerii si scoaterii de variabile din baza. Fie T matricea Dupa cum se vede din Tabelul 1, in etapa I, avem deci k=2, conform cu relatia (29). Intra deci in baza varibila , avand ponderea cea mai mare. Mai departe avem, conform (30), =160,valoare care corespunde variabilei din baza care iese prin urmare din baza, avand ponderea cea mai mica. Se transforma apoi coloana coeficientilor in coloana unitate, folosind multiplicatori dupa modelul elminarii gaussiene, aplicata intregii matrici.Pentru simplificarea calculelor, se observa ca, pentru variabilele care raman in baza ,se pastreaza coloanele unitate (nu trebuie recalculate). Se trece apoi la calculul sumelor si al coeficientilor numai pentru variabilele secundare din etapa respectiva ( pentru vriabilele din baza avem (), si nu este necesar calculul acestor transformari. Putem determina pe T observand ce a devenit matricea unitate care initial corespundea coloanelor vectorilor x₄, x₅, x₆. Rezulta:

. (36)

Aceeasi matrice a fost aplicata si coloanelor vectorilor x₂, x₅, x₁, care au ramas in final in baza, adica:

; .

Se verifica direct ca cele doua matrice T din (36) si T^-1 din (37) sunt intr-adevar matrice inverse.

De asemenea, mai putem verifica faptul ca, in final, avem:

. (38)

Din expresia (35) se deduc si costurile de oportunitate ("umbra"):

, , , (39)

adica cea mai mare eficacitate o are marirea numarului de ore alocate manoperei (de sase ori mai mare decat cresterea unitara obtinuta prin marirea numarului de bucati din produsul P₃, sau decat cresterea unitara corespunzatoare marimii numarului total de piese executate).

Pe ansamblu, se constata ca desi al treilea produs nu se recomanda a fi introdus (x₃ = 0), a actionat restrictia privind numarul total de produse. De asemenea, am obtinut o informatie privind costul de oportunitate corespunzator .

4 Metoda bazei artificiale (metoda penalizarii).

In cazul in care matricea A a restrictiilor nu contine o matrice unitate I_m (celelalte conditii pentru aplicarea algoritmului simplex primal fiind indeplinite) se pune problema de a crea o astfel de matrice. In acest sens, solutia preferabila nu este de a construi o matrice inversa de baza B^-1 (aceasta ar necesita un volum de calcul destul de mare si ar putea afecta termenii liberi b_i 0, i1,m), ci de a introduce variabile suplimentare pozitive, denumite si variabile artificiale. Aceste variabile pe care le vom nota cu y_i, i m, vor trebui in final sa dispara (y_i = 0). Ca urmare se modifica si functia obiectiv in maniera precizata mai jos. In consecinta, modelul standard anterior se extinde sub forma:

opt f(X, Y) = ; (40-a)

AX + I_mY = b; x_j 0, y_je 0; j; j_e, (40-b)

> 0 fiind un coeficient de penalizare care poate fi oricat de mare (). In (40-a), semnul (-) corespunde maximului, iar semnul (+), minimului.

Problema 7

In conditiile problemei 3 creste numarul de pasageri la 4000 minimum si se studiaza minimizarea costului, legat de necesitatea de a introduce si transport auto, pe langa cel naval si pe calea ferata. Cu mijloacele auto disponibile se pot transporta 120 calatori sau 30 tone marfuri, la un cost de 900 UM pe cursa. Numarul de curse auto trebuie sa fie de minimum 5.

Rezolvare

Fie x₃ numarul de curse auto. Problema se formuleaza astfel:

min C = 1260x₁ + 700x₂ +900x₃ ; (41-a)

600x₁ + 300x₂ + 120x₃ 4000 calatori; (41-b)

60x₁ + 100x₂ + 30x₃ 680 tone ; (41-c)

x₃ 5 curse; x_j 0, j. (41-d)

Introducand variabilele suplimentare x₄, x₅, x₆ si variabilele artificiale y₁, y₂, y₃, se obtine sistemul in forma standard:

minC = 1260x₁ + 700x₂ +900x₃ + (42-a)

Ax + I₃y = b, x 0, y 0 (42-b)

cu matricea A si vectorul b avand expresiile:

; . (42-c)

Rezultatele calculului sunt date in Tabelul 2. Se obtine:

C = 11830 + 2x₄ + x₅ + 630 x₆; min C = 11830 UM . (43)

Minimul a fost atins in momentul in care coeficientii variabilelor secundare x₄, x₅, x₆ au devenit pozitivi (-τ_j < 0). Coeficientii: - τ₇ = 2 - λ; - τ₈ = 1 - λ; - τ₉ = 630 - λ, corespunzatori variabilelor fictive, se considera negativi intrucat λ > 0 poate fi ales oricat de mare (λ > 630).

Tabelul 2

Metoda bazei artificiale. Problema 7

Se constata o influenta dubla asupra costului a reducerii numarului de pasageri, fata de reducerea costului pe tona . Reducerea unei curse auto, aduce o scadere a costului cu 630 UM, fata de 900 UM costul/cursa auto. Variabilele ramase in final in baza au valorile: x₁ = = 4.31; x₂ = = 2.71; x₃ = 5. Cum numarul de curse este intreg, solutia se plaseaza in jurul minimului, spre exemplu, se poate lua x₁ = 4; x₂ = 3; x₃ = 5, pentru care rezulta: C = 11640 UM, 3900 pasageri transportati si 690 tone marfa. Marind cursele auto la = 6, se transporta 4020 calatori, 720 tone marfa cu un cost C^' = 12540 UM. Se verifica produsul matricelor variabilelor de baza finale (x₁, x₂, x₃) si initiale:

. (44)

5 Analiza de senzitivitate.

Este interesant de studiat comportarea functiei-obiectiv fata de variatiile: 1) coeficientilor b_i, din restrictii; 2) coeficientilor c_j, ai functiei-obiectiv; 3) coeficientilor a_ij, , ai matricei A. De asemenea, se poate face un studiu legat de numarul (m) al restrictiilor, de numarul (n) de variabile s.a.m.d. O intrebare importanta este in ce masura functia-obiectiv, desi modificata, pastreaza proprietatea de a fi optima (se deplaseaza spre alte puncte de optim). Functia-obiectiv se poate dovedi mai sensibila la variatia unor coeficienti, restrictii etc. si mai putin sensibila la variatia altor parametri. Studiul unor astfel de probleme face obiectul analizei de senzitivitate.

5.1 Comportarea functiei-obiectiv la variatia coeficientilor b_i, din

restrictii. Exemple.

Variatia unui coeficient b_S, s fixat, poate fi pusa in legatura cu variabila auxiliara x_k, introdusa pentru a realiza egalitatea in restrictie. Coeficientul lui x_k este (+1) pentru cazul "" si zero pentru "=". In mod corespunzator, avem la trecerea variatiei in stanga o necunoscuta modificata, care se pastreaza in toate etapele pentru variabila suplimentara x_k:

(45)

in cazul in care x_k are coeficientul zero (egalitate) variatia nu poate fi repartizata unei singure variabile.

Prin urmare, daca variabila x_k este variabila secundara, ea va ramane cu valoarea zero la optim ( x_k = 0, k i_S Relatia (45) este doar o regula de inlocuire pentru a evita refacerea calculelor.

Se schimba doar valorile variabilelor din baza, ramanand insa nenegative.

Domeniul de admisibilitate pentru , pentru a ne plasa intr-o stare de optimum, plecand de la un optim deja calculat, se poate face cu ajutorul coeficientilor din tabelul furnizat de aplicarea algoritmului simplex primal, impunand conditia ca baza care a realizat optimumul sa aiba aceleasi variabile, nenegative (b_i 0, ); de asemenea, trebuie sa se pastreze semnul coeficientilor , pentru variabilele secundare in functia-obiectiv.

Notand cu coeficientul b_i in etapa finala, distingem doua cazuri:

a) x_k este variabila secundara si are coeficientii , i1, m, in matricea finala. Atunci apare inlocuirea:

, k fixat,  (46-a)

unde semnele corespund restrictiei "", respectiv "" din problema.

Inegalitatile (46-a) dau un interval de variatie pentru b_S, in functie de coeficientii < 0 da limita superioara a lui b_S, iar > 0, limita inferioara). Variabilele de baza iau valorile:

(46-b)

iar variatia functiei-obiectiv, f = va fi:

Δf = (46-c)

a)      daca x_k este variabila de baza, atunci ki_B, iar i = i_k este indicele liniei care ii corespunde lui x_k (din Tabel). Avem , a_ik = 0, din (45-c) se obtine:

Δf = ; Δx_k = Δb_S Δx_k Δb_S 0. (46-d)

In (46-d) primul semn (+) corespunde, ca de obicei, restrictiei "", mai frecventa in problemele de maximum, iar al doilea semn (-) restrictiei "", mai frecventa in problemele de minim.

Problema 8

Folosind datele din Tabelul 1 (referitor la problema (6)) sa se stabileasca domeniul de variatie pentru care se obtine un maximum al functiei-obiectiv V: a) pentru numarul de ore de lucru (in problema egal cu 240 ore); b) pentru cantitatea de material (in problema (6) egala cu 400 kg). In ambele cazuri, sa se discute valorile optime ale functiei-obiectiv.

Rezolvare.

a)      Numarul de ore alocat pentru manopera este legat de coeficientulb₁ (relatia 31-b) si de variabila auxiliara x₄, care, in final, (etapa a II-a, finala, Tabelul 1) este variabila secundara. Avem deci s = 1, k = 4.

Impartind coloana termenilor liberi (b_i) din etapa finala, cu coloana lui x₄ (a_i4, i1,3) se obtin valorile extreme:

, , ( 47)

care sunt plasate in jurul valorii initiale b₁ = 240 ore. Rezulta in final:

. (48)

Corespunzator lui , variabilele de baza din etapa finala au urmatoarele variatii (vezi coeficientii a_i4):

; ; . (49)

Variabilele secundare au variatii nule:

. (50)

Variatia functiei-obiectiv este (dupa forma initiala sau dupa 10-46-c):

V = 10x₁ + 25x₂ = b₁(25 x 1 + 0 x 3/2 + 10 x (-1)) = 15b₁ (51)

fata de valoarea maxV = 4100. Prin urmare, tinand cont de (47), se obtine:

-1100 900; 3000 max V 5000. (52)

In concluzie, venitul ramane maxim in conditiile maririi manoperei cu maximum 60 ore si a reducerii cu maximum 220/3 ore. In aceste conditii valoarea optima realizata variaza intre 3000 si 5000 UM.

b)      Cantitatea de material (coef. ) este legata de variabila x₅ care, in final, conform Tabelului 1, apare ca variabila principala, avand coeficientul 1 si valoarea 110 kg. Avem deci s = 2, k = 5. Conditia de nenegativitate conduce la (vezi 46-d, k = 5, i_k = 2, b_ik = 110, Tabel 1):

-110; = 0; (c₅ = 0). (53)

Prin urmare, cantitatea de material poate fi redusa cu maximum 110 kg si crescuta oricat fata de valoarea b₂ = 400. Rezulta:

290 (54)

In aceste conditii, deoarece variabila x₅ intra cu coeficientul c₅ = 0 in functia-obiectiv, max V = 4100 UM nu se schimba. In fond, 110 kg de material au ramas nefolosite, asa incat reducerea cu aceasta cantitate nu modifica venitul V. Marirea cantitatii de material nu schimba, de asemenea, nimic, deoarece orice cantitate adaugata peste 290 kg ramane neutilizata.

5.2 Senzitivitatea la schimbarea coeficientilor c_j, ai functiei-obiectiv. Exemple.

Am vazut ca, in final, optimul se realizeaza prin aducerea la acelasi semn pentru cazul maximului, pentru minim, a coeficientilor . Intrucat forma finala este echivalenta celei initiale, se poate discuta influenta parametrilor c_j, in ultima etapa. Avem (conform relatiei 28) , si:

, i (28)

Conditia de optimalitate se pastreaza atat timp cat semnul coeficientilor obtinut in final este mentinut.

Pe baza relatiei (28), putem distinge doua situatii:

a)      coeficientul c_k modificat se refera la variabilele secundare, deci ki_S. Atunci, din (28), se obtine:

, k i_S (55)

Prin urmare se modifica doar coeficientul variabilei x_k:

(56)

Rezulta ca este limitat superior de un numar pozitiv (-) in cazul maximului si limitat inferior de un numar negativ (-), in cazul minimului.

Deoarece x_k este variabila secundara, variatia functiei-obiectiv este nula:

(x_k = 0, ki_S), (56-a)

iar optimul se pastreaza, daca inegalitatile (56) sunt respectate;

b)      coeficientul c_k modificat se refera la variabila x_k din baza. In acest caz ki_B, caruia ii corespunde i = i_k = k. Rezulta:

ji_S, (57)

adica se modifica toti coeficientii care inmultesc variabilele secundare. Rezulta:

(58)

Din (58) rezulta un set de (m - n) inegalitati care trebuie satisfacute simultan de . Aceste inegalitati odata satisfacute, variatia functiei-obiectiv in jurul optimului este:

(58-a)

Problema 9

Folosind datele din Tabelul 2 (referitor la problema 7) sa se studieze senzitivitatea conditiilor de optimalitate la variatia: a) coeficientului c₄; b) coeficientului c₂ al functiei-obiectiv.

Se va studia si comportarea functiei-obiectiv (minim).

Rezolvare

a)          In acest caz variabila x₄, corespunzatoare lui c₄ = 0, este secundara. Folosim relatia (56) pentru k = 4, cazul fiind de minim.

Rezulta (k = 4) din (56) pentru minim:

(59)

Functia-obiectiv, conform cu (56-a) are variatia nula:

(x₄ = 0). (60)

deci valoarea minima, min F = 11 830, se pastreaza cu conditia c₄

b)          Coeficientul c₂ = 700 corespunde variabilei x₂ din baza (etapa finala, Tabelul 2). Aplicam inegalitatile (57) pentru cazul de minim, k = 2. Se obtine din (57), cazul de minim, i_k = 2:

a_2j c₂ < , j (61-a)

adica:

630; (61-b)

- 1; - 630; (61-c)

Deoarece , inegalitatile (61-c) pot fi indeplinite simultan intotdeauna, prin urmare studiul se reduce la inegalitatile (61-b). Se obtine, in continuare:

c₂ 2450; - 70 c₂ 630 c₂ 2100 . (62)

Variatia functiei-obiectiv este, conform (58-a):

Δf = x₂ Δc₂ = Δc₂; - 190 Δf 3800, (63-a)

adica min C se mentine intre limitele 11 830 + C

11 640 min C 15 630. (63-b)

CAPITOLUL 11

METODA DRUMULUI CRITIC

Metoda drumului critic a aparut in timpul celui de-al doilea razboi mondial, fiind dezvoltata la inceputul anilor '50 in Marea Britanie si SUA. In marea Britanie metoda a fost introdusa la inceput de companiile de electricitate conducand la reducerea duratei medii a reviziilor generale a unor centrale electrice cu pana la 30 %. In SUA, marina a dezvoltat o metoda denumita PERT (Programme Evaluation and Review Technique); independent, compania Du Pont a elaborat o metoda denumita chiar metoda drumului critic, realizand economii insemnate. Toate cele trei metode sunt similare, fiind extinse si in alte domenii, cum ar fi: constructii, contabilitate, studiul organizatiilor etc.

In general metoda realizeaza o schema de optimizare a desfasurarii in timp a activitatilor unui proiect, avand in vedere momentele de incepere si de finalizare a activitatilor corelate intre ele, evitand intarzierile si neconcordantele. Pentru a fi eficienta, metoda drumului critic cere o definire clara a obiectivelor si o estimare corecta a duratelor activitatilor componente, in raport cu resursele disponibile. Pe ansamblu, se urmareste folosirea cat mai eficienta a resurselor materiale si umane si reducerea duratei totale a proiectului.

11.1 Definitii si notatii. Drum critic. Exemple.

Se numeste activitate o componenta a proiectului, distincta de celelalte prin continut, moment initial si final, precum si prin competente si resurse. Activitatea se prezinta printr-o sageata "  " care incepe intr-un nod si se termina in alt nod. Nodurile se noteaza cu cercuri: "O". Totalitatea nodurilor si sagetilor formeaza o retea in care apar mai multe drumuri (trasee). Uneori, pentru completarea diferitelor trasee, se pot introduce activitati fictive, notate printr-o sageata intrerupta: " ". O activitate fictiva introdusa face reteaua mai usor de interpretat; timpul si resursele alocate unei astfel de activitati sunt nule.

La construirea unei retele de drumuri intre noduri, sunt respectate anumite reguli pe care le vom ilustra si in exemplele date. Astfel, se evita drumurile duble (multiple): doua noduri se leaga printr-o singura sageata; de asemenea, se evita existenta mai multor noduri terminus, de la care nu mai incepe nici o activitate (in afara celei care reprezinta sfarsitul proiectului).

Se noteaza cu TmS si TMS timpul minim, respectiv timpul maxim, pentru startul unei activitati. Aceste momente se inscriu in fiecare nod, sub forma de mai jos:

TmS se determina plecand din momentul inceperii proiectului, considerat moment zero (TmS = 0) si adaugand durata fiecarei activitati in parte, in sensul sagetilor. TMS se determina plecand de la nodul terminus al proiectului, in sens invers, spre nodul initial (TmS = 0, TMS = 0), scazand duratele activitatilor. Se respecta urmatoarele reguli:

a)         daca la un nod se ajunge pe doua trasee diferite, se ia pentru TmS valoarea cea mai mare, iar pentru TMS valoarea cea mai mica;

b)        pentru activitatile fictive, durata (adaugata la TmS sau scazuta din TMS) este zero;

c)         drumul critic este traseul format cu nodurile consecutive avand TmS = TMS.

Problema 11.1

In vederea testarii pietei pentru lansarea unui nou produs, activitatile identificate sunt cele prezentate in Tabelul 11.1, impreuna cu succesiunea si duratele lor. Se cere sa se stabileasca durata totala a proiectului si drumul critic pentru cele doua cazuri 1 si 2 in care duratele activitatilor C, E si G sunt modificate.

Tabelul 11.1

Problema 11.1

Rezolvare

a)      Reteaua de noduri in cazul 1 este prezentata in fig. 11.1. S-au completat la inceput timpii inferiori de start (TmS), luand valorile maxime. Spre exemplu, la nodul 2 se ajunge plecand din nodul 1 cu activitatea A durand o zi. Activitatea care incepe din nodul 2 fiind precedata de A, dar si de B (adoptarea strategiei), s-a introdus activitatea fictiva AF1 de durata zero, dar care transfera momentul inferior 2 din nodul 3 in nodul 2, durata activitatii B fiind mai mare decat durata activitatii A (activitatile si duratele lor sunt indicate pe fiecare sageata dintre noduri). La fel, in nodul 7, momentul inferior TmS este de 8 zile, egal cu suma duratelor activitatilor C si F. In acest fel, se ajunge in nodul 9 cu TmS = 14 zile (fata de startul proiectului in nodul 1). In acest stadiu, se completeaza TMS = 14 zile pentru nodul terminus 9 (TmS 9 = TMS 9, pentru nodul 9): sfarsitul unui proiect poate reprezenta startul unui proiect nou. La fel, in nodul 1 avem TmS 1 = TMS 1 = 0, prin definitia startului. Din nodul 9 plecam in sens invers, scazand duratele activitatilor; astfel, ajungem in nodul 8 cu TMS 8 = 14 - 3 = 11, iar in nodul 5 cu TMS 5 = 14 - 4 = 10 zile. Tot in nodul 5 ajungem insa si pe traseul nodurilor 8, 7, 6 cu TMS 5 = 11 - 3 - 0 - 3 = 5 < Prin urmare, luam valoarea cea mai mica TMS 5 = 5 zile. Valoarea TMS 1 = 0 in nodul 1 de start se regaseste pe traseul 9 - 8 - 7 - 4 - 1. Acest traseu are TmS i = TMS i, i = 9, 8, 7, 4, 1 si constituie drumul critic, intrucat starturile din punctele care il formeaza nu lasa loc nici unei intarzieri peste limita inferioara de start. Prin urmare, durata totala (optima) a proiectului este de 14 zile.

Fig. 11.1 Cazul 1 din Tabelul 11.1

O remarca asupra activitatii care nu precede nici o alta activitate din proiect: daca atribuiam acestei activitati un nod separat (diferit de cel terminus cu TmS = 4 + 4 = 8), pentru a determina momentul limita superior, era necesara o activitate fictiva, AF4, care ne ducea spre nodul 9, dupa schema de mai jos (Fig. 11.2):

Fig. 11.2 Drum alternativ intre nodurile 5, 9

Nodul 5' nu ne aduce informatii suplimentare: stim ca activitatea E incepe in ziua a 4-a si dureaza 4 zile. Nodurile din varful sagetilor nu contin intotdeauna informatii precise cu privire la sfarsitul activitatilor, ci ne spun doar daca aceste activitati s-ar putea prelungi fara a stopa proiectul, desi ar aduce unele cheltuieli suplimentare. Activitati de tipul E, care nu preced alte etape au un caracter mai general si se presupune ca au un efect pozitiv, chiar daca proiectul nu aduce rezultatele scontate.

b)      In cazul 2, reteaua apare ca in Fig. 11.3. Urmand regulile precizate mai sus, se calculeaza TmS si TMS pentru fiecare nod. Modificarea duratei activitatilor C (doua zile in loc de trei) si G (patru zile in loc de trei) lasa neschimbata durata totala a proiectului, dar modifica drumul critic care urmeaza acum traseul nodurilor 1, 3, 2, 5, 6, 7, 8, 9. In noul traseu apar si trei activitati fictive: AF1, AF2 si AF3.

Fig. 11.3 Cazul 2 din Tabelul 11.1

Corectitudinea drumului critic se poate testa prin calculul diferentei dintre timpul maxim la dispozitie si durata fiecarei activitati componente denumita rezerva totala (RT) de timp. Astfel pentru o activitate intre nodurile i, j de durata d_ij vom scrie:

RT_ij = TMS (j) - TmS (i) - d_ij.

Pentru fiecare traseu ij al drumului critic trebuie sa avem RT_ij = 0. Spre exemplu in Fig. 11.1, pentru nodurile 4, 7 avem:

RT 47 = TMS (7) - TmS (4) - d₄₇ = 8 - 3 - 5 = 0. (11.2)

Pentru nodurile 5, 6, care nu apartin drumului critic, avem:

RT 56 = TMS (6) - TmS (5) - d₅₆ = 8 - 4 - 3 = 1 zi. (11.3)

In afara rezervei totale de timp (RT), mai putem defini:

rezerva libera de timp pentru doua noduri i, j consecutive, notata RL_ij:

RL_ij = TmS (j) - TmS (i) - d_ij (11.4)

care reprezinta durata cu care activitatea ar putea fi amanata, fara a afecta activitatile care urmeaza;

rezerva independenta de timp, RI:

RI_ij = TmS (j) - TMS (i) - d_ij (11.5)

Pentru activitatea E dintre nodurile 5, 9 (Fig.11.3) avem:

RT 59 = TMS 9 - TmS 5 - d₅₉ = 14 - 4 - 3 = 7 zile. (11.6)

RL 59 = TmS 9 - TmS 5 - d₅₉ = 14 - 4 - 3 = 7 zile. (11.7)

RI 59 = TmS 9 - TMS 5 - d₅₉ = 14 - 4 - 3 = 7 zile.

Din (11.6) se vede ca traseul 59 nu apartine drumului critic, desi are noduri cu TmS = TMS.

11.2 Diagrame (grafice) Gantt. Exemplu.

Sunt diagrame care urmaresc modul de asigurare al suportului administrativ pentru activitatile programului. Unele dintre aceste activitati pot cere mai multe persoane calificate pentru urmarire si control, altele mai putine. Pe de alta parte numarul persoanelor cu o astfel de calificare inalta - eventual membrii ai corpului administrativ - este limitat si s-ar putea impune o modificare a TmS si TMS pentru a nu angaja persoane suplimentar. In acest scop, pot fi utilizate rezervele de timp: RT, RL, RI pe baza intocmirii unor diagrame de urmarire a fluxului activitatilor. Acestea se numesc diagrame Gantt, si sunt prezentate, in continuare, pentru cazul 1 analizat anterior. Diagrama Gantt apare in Fig. 11.4. In partea superioara sunt trecute activitatile, incepand cu cele incluse in drumul critic ( activitatile C, F, H , I), pentru care nu avem rezerve de timp. In partea de jos a diagramei este trecut personalul necesar conform tabelului 11.1. Cu linie intrerupta este indicat personalul necesar in varianta modificata in care activitaea E este deplasata in E'. Astfel numarul maxim de persoane necesare este redus de la 4 la 3.

Fig. 11.4 Diagrama Gantt. Cazul 1

varianta 1

varianta cu E'

drumul critic

CAPITOLUL 12

MATEMATICI FINANCIARE

12.1 Dobanzi simple si dobanzi compuse.

Dobanda reprezinta o suma adaugata unei sume initiale, S₀, depuse la o banca, dupa trecerea unui anumit interval de timp. O notatie adecvata pentru dobanda este D(S₀, t), unde t reprezinta timpul (durata depunerii). Prin urmare, valoarea (suma) finala, sau suma (valoarea) revenita celui care a plasat suma S₀ este:

S(S₀, t) = S₀ + D(S₀ , t). (12.1)

Dobanda are urmatoarele proprietati:

1) D(S₀ , t) 0 ;

2) D(0, t) = D(S₀ , 0)

12.1.1. Dobanda simpla. Exemple.

In cazul dobanzii simple, avem relatia:

D(S₀, t) = S₀ , d(t) = , (12.2)

unde d(t) este dobanda simpla unitara (pe unitate monetara UM), o functie pozitiva, exprimata de obicei in procente. Functia d(t) se construieste cu ajutorul ratei anuale a dobanzii, r, exprimata de asemenea in procente pe o durata specificata. De regula, rata anuala a dobanzii este constanta. Daca durata este egala cu unitatea (ex. 1an), d(t) si r sunt numeric egale.

Poate exista clauza ca dobanda fixata sa se adauge la sfarsitul perioadei. Daca suma se modifica in interval, spre exemplu, la jumatatea perioadei, atunci se modifica r (practic se scade), adica dobanda simpla unitara devine:

d(t) = r[t_ani] + r_C (t-[t_ani]); r_C r, (12.3)

unde partea intreaga a numarului t s-a notat cu [ ], iar cu r_C o dobanda in cont curent (adica pe perioada nedelimitata). Prin urmare, valoarea finala este:

S = S₀ (12.4)

Cazul depunerii in cont curent se obtine pentru r = r_C , d_C (t) = r_C t.

Exemplul 12.1

Sa se calculeze valoarea finala (revenita) pentru o depunere S₀ = 2000 UM, in regim de dobanda simpla, cu o rata de 12 % pe an in urmatoarele situatii: a) t = 1 an, b) t = 4 ani, c) t = 2.5 ani. Se prevede ca, la reducerea perioadei sub un an dobanda se reduce la 6 %.

Raspuns

a) Pentru t = 1 an si r = 12 %, r_C = 6 %, avem (S₀ = 2000 UM):

S₀ = 2000(1 + 0.12) = 2240 UM.

b) Pentru t= 4 ani, rezulta:

S₀ = 2000(1 + 0.48) = 2960 UM.

c) Pentru t = 2.5 ani, rezulta:

S₀ = 2000(1 + 0.27) = 2540 UM.

Daca depunerea se face in cont curent, dobanda dupa t = 2.5 ani ar fi:

D = 300 UM, in loc de 540 UM.

In cazul cand rata r a dobanzii se schimba pe parcursul intervalului de depunere, formula (12.4) se aplica pe subintervale. Putem scrie d(t) sub forma:

d(t) , , n = 1, 2, 3, . ,

(12.5)

n fiind numarul total de subintervale la sfarsitul carora se schimba ratele anuale r_i si r_Ci. Pentru n=1 si = 1 an, dobanda unitara este numeric egala cu rata (d(t)=r.1 an).