Parametrizare

Sunt cazuri în care coeficienţii unei probleme nu sunt cunoscuţi, sau nu pot fi estimaţi cu exactitate, sau nu sunt constanţi, ei variind în funcţie de unul sau mai mulţi parametrii, după o lege cunoscută, care este mai mult sau mai puţin complicată, putând lua valori într-o mulţime oarecare, finită sau infinită, discretă sau continuă, mărginită sau nemărginită. Ne-ar interesa să cunoaştem, pentru fiecare valoare posibilă a coeficienţilor, care este soluţia optimă a problemei, sau invers, pentru fiecare soluţie, care este mulţimea parametrilor pentru care aceasta rămâne optimă.

Este evident că problema este atât de complicată încât nu se poate da o unică rezolvare, aplicabilă pentru orice mulţime a parametrilor şi oricare ar fi legile de dependenţă a coeficienţilor de parametrii.

Ne propunem să facem rezolvarea doar pentru cazurile în care termenii liberi ai restricţiilor sau coeficienţii funcţiei obiectiv variază liniar în funcţie de un singur parametru.

Cazul 1 Parametrizarea termenilor liberi ai restricţiilor

Aşadar termenii liberi ai restricţiilor au forma:

b(l) = b⁰ + b¹×l Û b_i(l) =

unde l Î R este parametrul considerat iar b⁰, b¹ Î R^m sunt doi vectori cu componentele constante reale. Pentru rezolvarea problemei pentru orice l, vom parcurge următorii paşi:

Pasul 1. Se rezolvă problema pentru un l₀ iniţial; presupunem că există cel puţin un l pentru care problema are soluţie (altfel am avea un caz neinteresant) şi în plus putem presupune că el este egal chiar cu 0, acest lucru putând fi aranjat eventual prin schimbarea de variabilă:

l = l₀ + m

şi scrierea lui b sub forma:

b(m) = (b⁰ + b¹×l₀) + b¹×m.

Vom găsi o soluţie x₀ şi baza corespunzătoare B₀.

Pasul 2. Se calculează soluţiile de bază x_B(l), corespunzătoare bazei găsite la pasul 1, pentru l variabil:

x_B(l) =

Deoarece valorile D_j = nu depind de l, ele sunt pozitive pentru orice l, nu doar pentru l₀ şi deci soluţia x_B(l) va fi optimă atâta timp cât are toate componentele pozitive. Acei l pentru care x_B(l) ³ 0 reprezintă mulţimea valorilor parametrului pentru care baza B₀ dă soluţia optimă.

Pasul 3. Se rezolvă sistemul de inecuaţii x_B(l) ³ 0, a cărui soluţie va fi, ţinând cont că toate inecuaţiile sunt liniare, un interval , unde poate fi şi -¥ iar poate fi şi +¥ (în general, pentru orice bază, mulţimea pe care soluţia este pozitivă are această formă şi deci şi mulţimea pe care nu există nici o bază cu soluţia pozitivă va fi o reuniune de astfel de intervale, însă deschise şi, cum există un număr finit de baze, mulţimea numerelor reale va fi împărţită într-un număr finit de intervale, ca mai sus, pentru fiecare corespunzând o bază optimă sau nici una. Se poate demonstra că intervalele pe care nu există soluţie sunt neapărat de forma (-¥,a) sau (a,+¥)). Deoarece B^-1 este inversabilă, cel puţin unul dintre şi este finit. Fie acesta.

Pentru l > , cel puţin una din componentele soluţiei de bază corespunzătoare bazei B₀ va fi strict negativă. Este clar că, pentru l > , trebuie căutată altă bază optimă, dacă aceasta există.

Pasul 4. Reluăm algoritmul, pentru o valoare a lui l aflată în imediata vecinătate a luişi l > , astfel încât să ne situăm în intervalul imediat următor intervalului . Pentru găsirea bazei corespunzătoare acestuia (sau pentru aflarea faptului că nu există nici o soluţie pentru l >) se aplică în continuare algoritmul simplex dual (deoarece toţi D_j ³ 0).

Se obţine o succesiune de valori <<<…<= +¥ şi o succesiune de baze şi soluţii optime asociate fiecărui interval.

Pasul 5. Reluăm algoritmul pentru o valoare a lui l aflată în imediata vecinătate a lui şi l <, astfel încât să ne situăm în intervalul imediat anterior lui. Pentru găsirea bazei corespunzătoare acestuia (sau pentru aflarea faptului că nu există nici o soluţie pentru l <) se aplică în continuare algoritmul simplex dual (deoarece toţi D_j ³ 0).

Se obţine o succesiune de valori >>>…>= -¥ şi o succesiune de baze şi soluţii optime asociate fiecărui interval.

În acest moment, cunoaştem, pentru fiecare valoare posibilă a parametrului l, soluţia optimă a problemei sau invers, pentru fiecare bază, care este mulţimea parametrilor pentru care aceasta este optimă şi algoritmul este terminat.

Exemplu O întreprindere are gama sortimentală formată din 6 produse {P_j / j = 1,6} pentru fabricarea cărora foloseşte 3 materii prime {M_i / i = 1,3}. Se cunosc:

a) disponibilurile din fiecare materie primă {b_i(l) / i = 1,3}, care sunt dependente liniar de un parametru l.

b) profiturile/1000 unităţi vândute din fiecare produs {c_j / j = 1,6}.

c) coeficienţii tehnologici {a_i,j / i = 1,3; j = 1,6} (a_i,j = cantitatea din materia primă i necesară fabricării a 1000 produse de tipul j)

toate date în tabelul de mai jos:

produse mat. prime	P1	P2	P3	P4	P5	P6	Disponibil
M1	3	5	7	2	1	2	20 + 3l
M2	5	6	9	3	4	5	40 + 2l
M3	7	8	10	3	2	8	60 + l
profit/1000 prod.	2	3	4	1	1	2

Se doreşte găsirea acelor cantităţi {x_j / j = 1,6} ce trebuie fabricate din fiecare produs, astfel încât să se obţină profitul total maxim.

Rezolvare Avem de rezolvat o problemă de parametrizare a termenului liber, deci vom aplica algoritmul de mai sus.

Se scrie problema de programare asociată şi se aduce la forma standard:

		F.S.
max (2x1 + 3x2 + 4x3 + x4 + x5 + 2x6) x1, x2, x3, x4, x5, x6 ³ 0	Û	max (2x1 + 3x2 + 4x3 + x4 + x5 + 2x6) x1, x2, x3, x4, x5, x6 ³ 0

Pasul 1. Rezolvăm problema pentru l = 0 şi obţinem baza optimă:

B = (a₅,a₆,a₂) =

soluţia optimă x_B = , inversa bazei B^-1 = şi ultimul tabel simplex:

			2	3	4	1	1	2	0	0	0
cB	xB	xB	x1	x2	x3	x4	x5	x6	s1	s2	s3
1	x5			0			1	0
2	x6			0			0	1
3	x2			1			0	0
				0			0	0

Pasul 2. Se calculează soluţia de bază corespunzătoare bazei optime pentru l oarecare:

x_B(l) = B^-1×b(l) = ×=

Pasul 3. Se rezolvă sistemul de inecuaţii x_B ³ 0:

x_B ³ 0 Û Þ l Î Þ = şi =

Pasul 4. Se observă că pentru l aflat în imediata vecinătate a luişi l > vom avea o singură variabilă negativă şi anume x₆. Pentru un astfel de l, soluţia corespunzătoare bazei B este dual admisibilă şi, aplicând algoritmul simplex dual, aceasta va fi scoasă din bază şi înlocuită cu x₃. Se obţin:

- noua bază B = (a₅, a₃, a₂) = şi B^-1 =

- noua soluţie:

x_B(l) = B^-1×b(l) = ×=

- noul tabel simplex corespunzător noii baze:

			2	3	4	1	1	2	0	0	0
cB	xB	xB	x1	x2	x3	x4	x5	x6	s1	s2	s3
1	x5			0	0		1
4	x3			0	1		0
3	x2			1	0		0
				0	0		0

- noul interval pe care este optimă noua bază:

Þ l Î Þ = şi =

Reluând algoritmul vom obţine succesiv intervalele şi soluţiile următoare:

1. l Î B = (a₇, a₃, a₂) x_B =

2. l Î B = (a₇, a₃, a₅) x_B =

Pasul 5. Începând înapoi de la = obţinem:

1. l Î B = (a₅, a₆, a₉) x_B =

2. l Î B = (a₅, a₈, a₉) x_B =

3. l Î - sistemul nu are soluţii admisibile.

La marginile intervalelor problema va avea cel puţin două soluţii de bază şi, deci, o infinitate de soluţii optime (toate combinaţiile convexe dintre acestea).

În concluzie, dacă:

- l Î disponibilul din M₁ ar fi negativ, caz fără sens economic.

- l Î întreprinderea va fabrica doar produse de tipul P₅

- l Î întreprinderea va fabrica doar produse de tipul P₅ şi P₆

- l Î întreprinderea va fabrica doar produse de tipul P₅, P₆ şi P₂

- l Î întreprinderea va fabrica doar produse de tipul P₅, P₃ şi P₂

- l Î întreprinderea va fabrica doar produse de tipul P₃ şi P₂

- l Î întreprinderea va fabrica doar produse de tipul P₃ şi P₅

Cazul 2 Parametrizarea coeficienţilor funcţiei obiectiv

Aşadar, coeficienţii funcţiei obiectiv au forma:

c(l) = c⁰ + c¹×l Û c_j(l) =

unde l Î R este parametrul considerat iar c⁰, c¹ ÎRⁿ sunt doi vectori cu componentele constante reale. Pentru rezolvarea problemei pentru orice l, vom parcurge următorii paşi:

Pasul1. Se rezolvă problema pentru un l₀ iniţial; presupunem că există cel puţin un l pentru care problema are soluţie (altfel am avea un caz neinteresant) şi în plus putem presupune că el este egal chiar cu 0, acest lucru putând fi aranjat eventual prin schimbarea de variabilă:

l = l₀ + m

şi scrierea lui b sub forma:

c(m) = (c⁰ + c¹×l₀) + c¹×m.

Vom găsi o soluţie x₀ şi baza corespunzătoare B₀.

Pasul2. Se calculează D_j(l) corespunzători bazei găsite la pasul 1, pentru l variabil:

D_j(l) = × – c(l)

Deoarece componentele soluţiei de bază corespunzătoare x_B = nu depind de l, ele sunt pozitive pentru orice l, nu doar pentru l₀ şi soluţia x_B va fi optimă atâta timp cât toţi D_j(l) ³ 0. Acei l pentru care D_j(l) ³ 0 reprezintă mulţimea valorilor parametrului pentru care baza B₀ dă soluţia optimă.

Pasul3. Se rezolvă sistemul de inecuaţii D_j(l) ³ 0, a cărui soluţie va fi, ţinând cont că toate inecuaţiile sunt liniare, un interval , unde poate fi şi -¥ iar poate fi şi +¥ (în general, pentru orice bază, mulţimea pe care D_j(l) ³ 0 are această formă şi, deci, şi mulţimea pe care nu există soluţie optimă va fi o reuniune de astfel de intervale, însă deschise şi, cum există un număr finit de baze, mulţimea numerelor reale va fi împărţită într-un număr finit de intervale, pentru fiecare corespunzând o bază optimă sau nici una. Se poate demonstra că intervalele pe care nu există soluţie optimă sunt neapărat de forma (-¥,a) sau (a,+¥)). Deoarece B^-1 este inversabilă, cel puţin unul dintre şi este finit. Fie acesta.

Pentru l > cel puţin unul dintre D_j(l) corespunzători bazei B₀ va fi strict negativ. Este clar că pentru l > trebuie căutată altă bază optimă, dacă aceasta există.

Pasul4. Reluăm algoritmul pentru o valoare a lui l aflată în imediata vecinătate a luişi l > , astfel încât să ne situăm în intervalul imediat următor intervalului. Pentru găsirea bazei corespunzătoare acestuia (sau pentru aflarea faptului că nu există nici o soluţie optimă pentru l >) se aplică în continuare algoritmul simplex primal (deoarece x_B ³ 0).

Se obţine o succesiune de valori <<<…<= +¥ şi o succesiune de baze şi soluţii optime asociate fiecărui interval.

Pasul5. Reluăm algoritmul pentru o valoare a lui l aflată în imediata vecinătate a lui şi l <, astfel încât să ne situăm în intervalul imediat anterior lui. Pentru găsirea bazei corespunzătoare acestuia (sau pentru aflarea faptului că nu există nici o soluţie optimă pentru l < ) se aplică în continuare algoritmul simplex primal (deoarece x_B ³ 0).

Se obţine o succesiune de valori >>>…>= -¥ şi o succesiune de baze şi soluţii optime asociate fiecărui interval.

În acest moment, cunoaştem, pentru fiecare valoare posibilă a parametrului l, soluţia optimă a problemei sau invers, pentru fiecare bază, care este mulţimea parametrilor pentru care aceasta este optimă şi algoritmul este terminat.

Exemplu Analizăm cazul aceleiaşi întreprinderi în cazul în care disponibilul din fiecare materie primă rămâne constant dar profiturile variază în funcţie de un parametru m, acestea fiind date în tabelul de mai jos:

produse mat. prime	P1	P2	P3	P4	P5	P6	Disponibil
M1	3	5	7	2	1	2	20
M2	5	6	9	3	4	5	40
M3	7	8	10	3	2	8	60
profit/1000 prod.	2 + 4m	3 + 3m	4 + 2m	1 + 4m	1 + 2m	2 + 3m

Rezolvare. Avem de rezolvat o problemă de parametrizare a coeficienţilor funcţiei obiectiv, deci vom aplica algoritmul de mai sus.

Se scrie problema de programare asociată şi se aduce la forma standard:

		F.S.
max [(2+4m)x1 + (3+3m)x2 + (4+2m)x3 + (1+4m)x4 + (1+2m)x5 + (2+3m)x6] x1, x2, x3, x4, x5, x6 ³ 0	Û	max [(2+4m)x1 + (3+3m)x2 + (4+2m)x3 + (1+4m)x4 + (1+2m)x5 + (2+3m)x6] x1, x2, x3, x4, x5, x6 ³ 0

Pasul 1. Rezolvăm problema pentru m = 0 şi obţinem baza optimă:

B = (a₅,a₆,a₂) =

soluţia optimă x_B = , inversa bazei B^-1 = şi ultimul tabel simplex:

			2 + 4m	3 + 3m	4 + 2m	1 + 4m	1 + 2m	2 + 3m	0	0	0
cB	xB	xB	x1	x2	x3	x4	x5	x6	s1	s2	s3
1 + 2m	x5			0			1	0
2 + 3m	x6			0			0	1
3 + 3m	x2			1			0	0
				0			0	0

Pasul 2. Se calculează D_j corespunzători bazei optime, pentru m oarecare:

D(l) = × – c(m) =

=

Pasul 3. Se rezolvă sistemul de inecuaţii x_B ³ 0:

D(m) ³ 0 Û Þ m Î Þ = şi =

Pasul 4. Se observă că pentru m aflat în imediata vecinătate a lui şi m > vom avea un singur D_j negativ şi anume D₄. Pentru un astfel de m, soluţia corespunzătoare bazei B este primal admisibilă şi, aplicând algoritmul simplex primal, x₄ va fi introdusă în bază şi înlocuită cu x₅. Se obţin:

- noua bază B = (a₄, a₆, a₂) = şi B^-1 =

- noua soluţie:

x_B = B^-1×b = ×=

- noul tabel simplex corespunzător noii baze:

			2 + 4m	3 + 3m	4 + 2m	1 + 4m	1 + 2m	2 + 3m	0	0	0
cB	xB	xB	x1	x2	x3	x4	x5	x6	s1	s2	s3
1 + 4m	x4			0		1		0
2 + 3m	x6			0		0		1
3 + 3m	x2			1		0		0
				0		0		0

- noul interval pe care este optimă noua bază:

Þ m Î Þ = şi =

Reluând algoritmul vom obţine succesiv intervalele şi soluţiile următoare:

1. m Î B = (a₄, a₆, a₉) x_B =

2. m Î B = (a₄, a₅, a₉) x_B =

Pasul 5. Începând înapoi de la = obţinem:

3. l Î B = (a₃, a₆, a₂) x_B =

4. l Î B = (a₃, a₆, a₉) x_B =

5. l Î B = (a₃, a₈, a₉) x_B =

6. l Î B = (a₇, a₈, a₉) x_B =

La marginile intervalelor, problema va avea cel puţin două soluţii de bază şi, deci, o infinitate de soluţii optime (toate combinaţiile convexe dintre acestea).

În concluzie, dacă:

- l Î disponibilul din M₁ ar fi negativ, caz fără sens economic.

- l Î întreprinderea va fabrica doar produse de tipul P₅.

- l Î întreprinderea va fabrica doar produse de tipul P₅ şi P₆.

- l Î întreprinderea va fabrica doar produse de tipul P₅, P₆ şi P₂.

- l Î întreprinderea va fabrica doar produse de tipul P₅, P₃ şi P₂.

- l Î întreprinderea va fabrica doar produse de tipul P₃ şi P₂.

- l Î întreprinderea va fabrica doar produse de tipul P₃ şi P₅.