Reoptimizare

Presupunem că am rezolvat o problemă de programare liniară, cunoscând pentru aceasta soluţia optimă de bază x_B =B^-1×b, inversa bazei B^-1 şi tabelul simplex corespunzător soluţiei optime. Ne propunem să vedem, în condiţiile în care se modifică unele din datele problemei, ce anume din rezolvarea fostei probleme mai poate fi folosit la rezolvarea noii probleme, în încercarea de a rezolva noua problemă într-un timp mai scurt decât cel necesar rezolvării acesteia de la zero, cu algoritmul simplex. Acest deziderat corespunde ideii de a folosi experienţa anterioară. De asemenea, ne propunem să vedem ce influenţă au diferitele tipuri de modificări ale datelor problemei asupra soluţiilor, atât din punct de vedere matematic cât şi economic.

Datele problemei sunt constituite din:

- coeficienţii funcţiei obiectiv = componentele vectorului c

- termenii liberi ai restricţiilor = componentele vectorului b

- coeficienţii variabilelor din restricţii = elementele matricii A

O modificare poate afecta toate cele trei grupe.

Vom analiza efectele modificărilor începând de la cazurile cele mai simple:

Cazul 1. Dacă se modifică doar elementele vectorului c ® c’

Deoarece matricea A şi vectorul b rămân aceleaşi, avem acelaşi sistem de restricţii şi deci aceeaşi mulţime de soluţii admisibile. Soluţia optimă a fostei probleme, fiind în particular soluţie de bază admisibilă a sistemului de restricţii, va fi soluţie admisibilă de bază şi în noua problemă. Dispunem deci de o soluţie iniţială admisibilă de bază şi, deci, putem aplica algoritmul simplex primal direct de la faza a doua. Se construieşte tabelul simplex corespunzător soluţiei, în problema modificată:

	xB	xB	xB	xS
		B^-1×b	Im	B^-1×S
		× B^-1×b	0

care este de fapt fostul tabel, în care se recalculează . Avem două cazuri:

a) Dacă toţi ³ 0, soluţia este optimă;

b) Dacă există un < 0, se aplică în continuare algoritmul simplex primal, până la găsirea soluţiei optime.

Exemplu: Pentru problema:

		F.S.
(max) f = 3x1 –x2 + 2x3 x1, x2, x3 ³ 0	Û	(max)f = 3x1 – x2 +2x3 – Ma1 x1, x2, x3, s1, s2, a1 ³ 0

obţinem în final următorul tabel simplex:

			3	-1	2	0	0	0	-M
	xB	xB	x1	x2	x3	s1	s2	s3	a1
3	x1	3	1	0	0	1	1	2	-2
2	x3	2	0	0	1	0	1	1	-1
-1	x2	1	0	1	0	0	-1	-2	2
		12	0	0	0	3	6	10	M - 10

1. Dacă noua funcţie obiectiv este f’ = x₁ – 2x₂ + 5x₃ atunci tabelul corespunzător va fi:

			1	-2	5	0	0	0	-M
	xB	xB	x1	x2	x3	s1	s2	s3	a1
1	x1	3	1	0	0	1	1	2	-2
5	x3	2	0	0	1	0	1	1	-1
-2	x2	1	0	1	0	0	-1	-2	2
		11	0	0	0	1	8	11	M - 11

toţi ³ 0, ne aflăm în cazul a) şi soluţia care dădea optimul fostei probleme este soluţia optimă şi în noua problemă.

2. Dacă noua funcţie obiectiv este f” = x₁ + 3x₂ - 2x₃ atunci tabelul corespunzător va fi:

			1	3	-2	0	0	0	-M
	xB	xB	x1	x2	x3	s1	s2	s3	a1
1	x1	3	1	0	0	1	1	2	-2
-2	x3	2	0	0	1	0	1	1	-1
3	x2	1	0	1	0	0	-1	-2	2
		2	0	0	0	1	-4	-6	M + 6

există < 0 (de exemplu ), ne aflăm în cazul b) şi soluţia care dădea optimul fostei probleme nu este optimă şi în noua problemă, pentru găsirea celei optime (dacă există!) trebuind să aplicăm în continuare algoritmul simplex primal.

Cazul 2 Dacă se modifică doar componentele vectorului b ® b’

Deoarece matricea A rămâne aceeaşi, fosta bază rămâne bază şi în noua problemă. Soluţia corespunzătoare va fi: iar . În concluzie, noua soluţie ar putea sau nu să aibă toate componentele pozitive (după cum este noul b’), dar sigur toţi D_j rămân pozitivi (fiind aceeaşi cu cei ai soluţiei fostei probleme, care era optimă), deci soluţia este cel puţin dual admisibilă de bază. Vom avea două cazuri:

a) Dacă atunci soluţia este şi primal admisibilă, deci este soluţia optimă a noii probleme;

b) Dacă are cel puţin o componentă negativă atunci soluţia este doar dual admisibilă de bază şi vom continua cu algoritmul simplex dual pentru găsirea celei optime (dacă ea există!).

Exemplu Pentru problema:

		F.S.
(max) f = - 4x1 – x2 + 2x3 x1, x2, x3 ³ 0	Û	(max) f = - 4x1 – x2 + 2x3 –Ma1 x1,x2, x3, s1, s2, s3, a1 ³ 0

obţinem în final următorul tabel simplex:

			-4	-1	2	0	0	0	-M
	xB	xB	x1	x2	x3	s1	s2	s3	a1
0	s1	22			0	1	0		0
0	s2	11			0	0	1		-1
2	x3	5			1	0	0		0
		10			0	0	0		M

din care obţinem inversa bazei B = ca fiind B^-1 =

1. Dacă noul vector al termenilor liberi, din problema la forma standard, ar fi b’ = (2, 5, 6)^T atunci tabelul corespunzător ar fi:

			-4	-1	2	0	0	0	-M
	xB	x’B	x1	x2	x3	s1	s2	s3	a1
0	s1	4			0	1	0		0
0	s2	5			0	0	1		-1
2	x3	2			1	0	0		0
		4			0	0	0		M

toate componentele soluţiei ar fi pozitive, ne-am afla în cazul a) şi soluţia găsită ar fi soluţia optimă în noua problemă.

2. Dacă noul vector al termenilor liberi din problema la forma standard ar fi b’ = (5, 6, 3)^T atunci tabelul corespunzător ar fi:

			-4	-1	2	0	0	0	-M
	xB	x’B	x1	x2	x3	s1	s2	s3	a1
0	s1	6			0	1	0		0
0	s2	-1			0	0	1		-1
2	x3	1			1	0	0		0
		2			0	0	0		M

ar exista componente ale soluţiei strict negative (de exemplu x₃ = -1), ne-am afla în cazul b), soluţia nu ar fi primal admisibilă şi, pentru găsirea celei optime, (dacă există!) vom aplica în continuare algoritmul simplex dual.

Cazul 3. Dacă apar k variabile suplimentare, cu coeficienţii corespunzători, în funcţia obiectiv şi în restricţii.

Această modificare are ca efect adăugarea a k coloane la matricea A şi a k elemente la vectorul c, numărul de restricţii (şi deci de linii ale matricii A şi de elemente ale vectorului b) rămânând acelaşi.

Deoarece, în momentul ajungerii la soluţia optimă, în sistem se află doar restricţii independente între ele, rangul matricii este egal cu numărul de linii (care este mai mic decât numărul de coloane) şi, din acest motiv, adăugarea oricâtor coloane nu îl va modifica. Baza fostei matrici rămâne deci bază şi în noua matrice, soluţia x_B = B^-1×b ³ 0 rămâne soluţie de bază a noului sistem de restricţii (B şi b fiind aceeaşi), deci este şi o soluţie de bază primal admisibilă a noii probleme. Tabelul corespunzător acestei baze, în noua problemă, este cel anterior, la care se adaugă k coloane astfel:

- pe linia variabilelor se adaugă noile variabile;

- pe linia coeficienţilor funcţiei obiectiv se adaugă coeficienţii corespunzători noilor variabile;

- în interiorul tabelului, sub fiecare variabilă nou introdusă, se adaugă coloana B^-1×a_k, unde a_k este vectorul coloană format din coeficienţii variabilei x_k, nou introduse în restricţiile problemei;

- D_k, corespunzători noilor variabile, se calculează cu formula cunoscută: D_k = ×B^-1×a_k - c_k.

Vom avea două cazuri:

a) Dacă toţi D_k sunt pozitivi, soluţia optimă a fostei probleme este soluţie optimă şi pentru noua problemă;

b) Dacă există un indice k, pentru care D_k < 0, atunci soluţia este doar primal admisibilă şi vom aplica în continuare algoritmul simplex primal, pentru găsirea soluţiei optime (dacă ea există!)

Exemplu Fie problema:

		F.S.
(max) f = 3x1 + 4x2 – 2x3 x1, x2, x3 ³ 0	Û	(max) f = 3x1 + 4x2 – 2x3 –Ma1 x1,x2, x3, s1, s2, s3, a1 ³ 0

pentru care obţinem tabelul simplex final:

			3	4	-2	0	0	0	-M
	xB	xB	x1	x2	x3	s1	s2	s3	a1
4	x2	4	0	1	0		3
3	x1	1	1	0	0		-2
-2	x3	2	0	0	1	0	1	-1	0
		15	0	0	0		4	2	M

de unde găsim inversa bazei B = ca fiind B^-1 = .

1. Dacă introducem, în plus, variabilele x₄, x₅ şi x₆, obţinând problema la forma standard:

(max) f = 3x₁ + 4x₂ – 2x₃ +2x₄ – 20x₅ –x₆ –Ma₁

x₁, x₂, x₃, x₄, x₅, x₆, s₁, s₂, s₃, a₁ ³ 0

vom obţine tabelul corespunzător bazei B, în noua problemă, prin:

- adăugarea variabilelor x₄, x₅, x₆ la linia variabilelor;

- adăugarea coeficienţilor 2, -20, -1 corespunzători acestor variabile la linia coeficienţilor funcţiei obiectiv;

- adăugarea coloanelor:

a₄ = × = ,

a₅ = × = ,

a₆ = × = .

- adăugăm:

- D₄ = ×B^-1×a₄ – c₄ = 1

- D₅ = ×B^-1×a₅ – c₅ =

- D₆ = ×B^-1×a₆ – c₆ =

şi, final, obţinem tabelul:

			3	4	-2	2	-20	-1	0	0	0	-M
	xB	xB	x1	x2	x3	x4	x5	x6	s1	s2	s3	a1
4	x2	4	0	1	0	5				3
3	x1	1	1	0	0	-3				-2
-2	x3	2	0	0	1	4	-1	3	0	1	-1	0
		15	0	0	0	1				4	2	M

Se observă că toţi D_j sunt pozitivi, deci soluţia este optimă.

2. Dacă, pentru aceeaşi modificare, alegem coeficientul lui x₅ egal cu –10, în loc de –20, în tabel se va modifica doar D₅, care va avea valoarea şi ne vom afla în cazul b) (deoarece D₅ < 0); vom continua căutarea soluţiei optime cu algoritmul simplex primal.

Cazul 4. Dacă se adaugă o restricţie

Efectul este adăugarea unei linii la matricea A şi a unui element la vectorul b.

Se verifică dacă fosta soluţie de optim verifică noua restricţie. Dacă o verifică, ea este soluţia de optim şi a noii probleme. Dacă nu o verifică, vom căuta în continuare noua soluţie de optim (dacă ea există!).

Deoarece rangul matricii A era egal cu numărul de linii (care era mai mic decât numărul de coloane), prin adăugarea unei linii rangul noii matrici va fi cu 1 mai mare (dacă nu s-ar întâmpla aşa ar rezulta că noua restricţie este o combinaţie a celor anterioare şi, deci, nu are nici un efect asupra mulţimii soluţiilor, putând fi eliminată din sistem, noua problemă fiind de fapt aceeaşi cu fosta problemă, care e deja rezolvată).

În acest caz, fosta bază nu mai este bază în noua matrice, ci doar un minor cu determinantul diferit de zero, de dimensiune cu 1 mai mică decât rangul matricii. Pentru a obţine baza noii probleme vom borda fosta bază cu noua linie şi o coloană.

Din ultimul tabel simplex al fostei probleme, putem scrie fostul sistem la forma:

x_B +B^-1·S·x_S = B^-1·b = x_B

de unde scoatem variabilele principale în funcţie de cele secundare, le înlocuim în noua restricţie şi apoi aranjăm ca termenul liber b_m+1 obţinut să fie pozitiv (înmulţind eventual restricţia cu –1). Adăugăm noua restricţie, sub forma obţinută, la sistemul iniţial, scris sub forma corespunzătoare ultimului tabel simplex. Avem trei cazuri:

a) Dacă restricţia este de tipul “£”, introducem variabila de abatere s, care va avea coeficientul +1 şi baza va fi formată din coloanele corespunzătoare fostelor variabile principale, plus coloana variabilei s, obţinând matricea unitate. Tabelul corespunzător în noua problemă va fi fostul tabel, la care se adaugă:

- o linie în plus, pe care: c_s = 0 în coloana coeficienţilor din funcţia obiectiv ai variabilelor din baza, s în coloana variabilelor bazei, b_m+1 în coloana soluţiei de bază, coeficienţii noii restricţii (adusă la ultima formă) în interiorul tabelului şi 1 in dreptul noii variabile s.

- o coloană în plus corespunzătoare lui s, care va fi vector unitar.

În acest caz, noii D_j vor fi foştii D_j (deoarece c_s = 0), la care se adaugă cel corespunzător lui s (egal cu 0, deoarece s este din bază). Soluţia are toate componentele pozitive şi toţi D_j pozitivi, deci este soluţia optimă căutată.

b) Dacă restricţia este de tipul “³” variabila de abatere va avea coeficientul –1 şi soluţia corespunzătoare este doar dual admisibilă (deoarece s = -b_m+1 < 0); vom continua căutarea soluţiei optime cu algoritmul simplex dual.

c) Dacă restricţia este cu “=”, se introduce variabila artificială a, cu c_a = -M, se construieşte tabelul asociat ca la cazul a) şi se obţine o soluţie admisibilă (deoarece a = b_m+1 ³ 0), cu D_j depinzând de M (deoarece c_a = -M). Se continuă cu algoritmul simplex primal.

Exemplu Fie problema:

		F.S.
(max) f = x1 –3x2 + 2x3 x1, x2, x3 ³ 0	Û	(max) f = x1 –3x2 + 2x3 x1, x2, x3, s1, s2, s3, a1 ³ 0

pentru care obţinem tabelul final:

			1	-3	2	0	0	0	-M
cB	xB	xB	x1	x2	x3	s1	s2	s3	a1
0	s2	54	0	11	0	2	1	3	-1
2	x3	99	0	22	1	3	0	4	0
1	x1	27	1	6	0	1	0	1	0
		225	0	53	0	7	0	9	M

din care putem scrie sistemul de restricţii sub forma:

Þ

1. Dacă noua restricţie ar fi 2x₁ + x₂ – x₃ £ 7 atunci soluţia de optim (x₁ = 27, x₂ = 0, x₃ = 99) ar verifica noua restricţie şi ar fi soluţie de optim şi pentru noua problemă.

2. Dacă noua restricţie ar fi 3x₁ +2x₂ + x₃ £ 8 ea nu ar fi verificată de fosta soluţie de optim. Înlocuind în această restricţie s₂, x₁ şi x₃, cu expresiile obţinute în sistemul de mai sus, rezultă:

3·(27 – 6x₂ – s₁ – s₃) + 2x₂ + (99 – 22x₂ – 3s₁ – 4s₃) £ 8

Û -38x₂ – 6s₁ – 7s₃ £ -172 Û 38x₂ + 6s₁ + 7s₃ ³ 172

Û 38x₂ + 6s₁ + 7s₃ – s = 172

şi sistemul: iar în final, tabelul:

			1	-3	2	0	0	0	0
cB	xB	xB	x1	x2	x3	s1	s2	s3	s
0	s2	54	0	11	0	2	1	3	0
2	x3	99	0	22	1	3	0	4	0
1	x1	27	1	6	0	1	0	1	0
0	s	-172	0	38	0	6	0	7	1
		225	0	53	0	7	0	9	0

în care soluţia de bază este dual admisibilă. Se continuă rezolvarea problemei cu algoritmul simplex dual.

3. Dacă noua restricţie ar fi x₁ + x₂ + x₃ = 100 ea nu ar fi verificată de fosta soluţie. Prin înlocuirea lui x₁ şi x₃ obţinem:

(27 – 6x₂ – s₁ – s₃) + x₂ + (99 – 22x₂ – 3s₁ – 4s₃) = 100

Û -27x₂ – 4s₁ – 5s₃ = -26 Û 27x₂ + 4s₁ + 5s₃ = 26

Û 27x₂ + 4s₁ + 5s₃ + a = 26

rezultă sistemul: iar în final, tabelul:

			1	-3	2	0	0	0	-M
cB	xB	xB	x1	x2	x3	s1	s2	s3	a
0	s2	54	0	11	0	2	1	3	0
2	x3	99	0	22	1	3	0	4	0
1	x1	27	1	6	0	1	0	1	0
-M	a	26	0	27	0	4	0	5	1
		-26M + 225	0	-27M + 53	0	-4M + 7	0	-5M + 9	0

în care soluţia de bază este primal admisibilă. Se continuă rezolvarea problemei cu algoritmul simplex primal.

Cazul 5. Dacă se modifică coeficienţii unei variabile x_j

Efectul este modificarea coloanei a_j ® din A şi/sau a coeficientului c_j ® din funcţia obiectiv. Avem două variante:

Cazul 5.1 Coloana a_j nu face parte din B. În acest caz fosta bază B rămâne bază şi în noua problemă, soluţia corespunzătoare este aceeaşi: x_B = B^-1·b şi tabelul corespunzător este fostul tabel, în care se modifică doar coloana corespunzătoare variabile x_j:

c_j ® , B^-1·a_j ® B^-1·, D_j ®

Avem două cazuri:

- Dacă fosta soluţie optimă rămâne optimă şi în noua problemă.

- Dacă < 0 fosta soluţie optimă este doar primal admisibilă şi se va continua rezolvarea problemei cu algoritmul simplex primal.

Exemplu Fie problema:

		F.S.
(max) f = 2x1 +3x2 + 4x3 x1, x2, x3 ³ 0	Û	(max) f = 2x1 +3x2 + 4x3 x1, x2, x3, s1, s2, s3, a1 ³ 0

După rezolvare, se obţine tabelul simplex final de mai jos, din care se găseşte inversa bazei

B = ca fiind B^-1 =

			2	3	4	0	0	0	-M
cB	xB	xB	x1	x2	x3	s1	s2	s3	a1
2	x1	10	1	0		0			0
0	s1	90	0	0	15	1	5	6	-1
3	x2	9	0	1	1	0			0
		47	0	0	2	0			M

1. Dacă se modifică coeficienţii variabilei x₃, problema devenind:

		F.S.
(max) f = 2x1 +3x2 + 2x3 x1, x2, x3 ³ 0	Û	(max) f = 2x1 +3x2 + 2x3 x1, x2, x3, s1, s2, s3, a1 ³ 0

noua coloană corespunzătoare lui x₃ va fi a^/₃ = ·= iar D^/₃ = < 0, deci

ne aflăm în cazul b) şi vom continua rezolvarea problemei cu algoritmul simplex primal, de la tabelul:

			2	3	2	0	0	0	-M
cB	xB	xB	x1	x2	x3	s1	s2	s3	a1
2	x1	10	1	0	0	0			0
0	s1	90	0	0	-1	1	5	6	-1
3	x2	9	0	1		0			0
		47	0	0		0			M

2. Dacă se modifică coeficienţii variabilei x₃, problema devenind:

		F.S.
(max) f = 2x1 +3x2 - 3x3 x1, x2, x3 ³ 0	Û	(max) f = 2x1 +3x2 – 3x3 x1, x2, x3, s1, s2, s3, a1 ³ 0

noua coloană corespunzătoare lui x₃ va fi a^/₃ = ·= iar D^/₃ = < 0, deci ne aflăm în cazul a) cu fosta soluţie optimă şi pentru noua problemă, tabelul final fiind:

			2	3	-3	0	0	0	-M
cB	xB	xB	x1	x2	x3	s1	s2	s3	a1
2	x1	10	1	0		0			0
0	s1	90	0	0	16	1	5	6	-1
3	x2	9	0	1		0			0
		47	0	0		0			M

Cazul 5.2 Coloana a_j face parte din baza B. În acest caz fosta bază nu mai există în noua matrice A. Noul minor B’, obţinut prin înlocuirea lui a_j cu în B, poate fi:

- neinversabil (det B’ = 0) caz în care trebuie căutată altă bază;

- inversabil, soluţia corespunzătoare x_B’ = (B’)^-1·b putându-se în următoarele situaţii:

- are toate componentele pozitive (x_B’ ³ 0), deci este primal admisibilă şi putem aplica în continuare algoritmul simplex primal;

- are componente strict negative, dar are toţi D_j pozitivi, deci este dual admisibilă şi putem aplica în continuare algoritmul simplex dual;

- are componente strict negative şi există D_j strict negativi, deci nu este nici primal nici dual admisibilă şi trebuie căutată altă bază.

Se observă că există variante când trebuie căutate alte baze şi, chiar în cazurile când putem folosi noua bază, avem de făcut calcule laborioase (inversarea lui B’, calculul produselor B^-1·b şi B^-1·A şi calculul noilor D_j). Din acest motiv vom aplica următorul procedeu (fără a mai verifica posibilitatea existenţei unui caz favorabil de mai sus):

pasul 1. Se scriu în noua problemă (adusă la forma canonică) toţi termenii cu variabila x_j ca o sumă de doi termeni, unul având coeficient fostul coeficient al variabilei x_j iar celălalt diferenţa dintre aceştia:

· x_j = c_j · x_j + ( - c_j) · x_j

· x_ij = a_ij · x_j + ( - a_ij) · x_j

pasul 2. Se înlocuieşte în toţi termenii de forma ( - c_j) · x_j şi ( - a_ij) · x_j, variabila x_j cu o nouă variabilă y şi se adaugă la sistem restricţia x_j = y, obţinându-se o problemă echivalentă.

pasul 3. Pentru noua problemă, se aplică procedeul de la cazul 4 pentru varianta c), obţinându-se o soluţie de bază admisibilă cu care se continuă cu algoritmul simplex primal.

Exemplu După rezolvarea problemei:

		F.S.
(max) f = 2x1 +3x2 + 5x3 x1, x2, x3 ³ 0	Û	(max) f = 2x1 +3x2 + 5x3 x1, x2, x3, s1, s2, s3 ³ 0

se obţine soluţia optimă şi tabelul pentru baza corespunzătoare variabilelor (x₁, x₃, s₃), în care (x₁ = 2, x₃ = 2, s₃ = 0) şi tabelul:

			2	3	5	0	0	0
cB	xB	xB	x1	x2	x3	s1	s2	s3
2	x1	2	1		0			0
5	x3	2	0		1			0
0	s3	0	0		0			1
		14	0		0			0

B şi B^-1 fiind date mai jos:

B = B^-1 =

Dacă presupunem că se modifică coeficienţii variabilei x₃, noua problemă fiind:

		F.S.
(max) f = 2x1 +3x2 + 2x3 x1, x2, x3 ³ 0	Û	(max) f = 2x1 +3x2 + 2x3 x1, x2, x3, s1, s2, s3 ³ 0

deoarece x₃ face parte din bază, vom face transformarea:

		F.S.
(max) f = 2x1 +3x2 + 2x3 x1, x2, x3, s1, s2, s3 ³ 0	Û	(max) f = 2x1 +3x2 + 5x3 - 3y x1, x2, x3, s1, s2, s3, y ³ 0

Din primele trei ecuaţii scoatem variabilele fostei baze (x₁, x₃, s₃) în funcţie de celelalte, înmulţind sistemul cu B^-1. Coeficienţii fostelor variabile se iau din ultimul tabel iar ai lui y se calculează înmulţind coloana coeficienţilor lui cu B^-1. Avem:

B^-1 · = · =

deci sistemul va avea forma:

Din primele trei ecuaţii se scot variabilele bazei în funcţie de celelalte:

apoi se înlocuiesc în ultima ecuaţie: Û în care se adaugă variabila de abatere a şi se adaugă la sistem. Se obţine în final problema:

(max) f = 2x₁ +3x₂ + 5x₃ - 3y

Tabelul corespunzător va fi:

			2	3	5	-3	0	0	0	-M
cB	xB	xB	x1	x2	x3	y	s1	s2	s3	a
2	x1	2	1		0				0	0
5	x3	2	0		1				0	0
0	s3	0	0		0				1	0
-M	a	2	0		0				0	1
		14-2M	0	-M	0	M	+M	-M	0	0

în care soluţia de bază este admisibilă şi vom continua rezolvarea cu algoritmul simplex primal.

Din punct de vedere economic, situaţiile de mai sus pot fi foarte bine exemplificate pe cazul unei întreprinderi care fabrică n produse folosind m materii prime şi doreşte găsirea acelor cantităţi ce trebuie fabricate din fiecare produs astfel încât să obţină profitul total maxim.

În acest caz coeficienţii problemei vor fi:

- c_j = profiturile unitare obţinute prin vânzarea celor n produse.

- b_i = disponibilurile din cele m materii prime.

- a_ij = coeficienţii tehnologici.

1. Modificarea coeficienţilor funcţiei obiectiv poate însemna fie o reevaluare a profiturilor unitare, fie pur şi simplu schimbarea obiectivului propus (de exemplu maximizarea veniturilor sau minimizarea cheltuielilor în loc de maximizarea profitului, caz în care c_i ar avea alte semnificaţii (venit unitar, cost unitar) şi deci cu totul alte valori).

2. Modificarea termenilor liberi poate însemna modificarea posibilităţilor de procurare a materiilor prime prin pierderea unor furnizori sau realizarea de contracte cu noi furnizori.

3. Apariţia de coloane în plus înseamnă lărgirea gamei de produse.

4. Apariţia de noi restricţii poate înseamnă existenţa unei resurse care nu fusese luată în considerare până acum, deoarece limitele datorate acesteia erau suficient de largi pentru a nu influenţa soluţia, în urma modificării acestor limite ele putând modifica soluţia.

5. Modificarea coloanelor poate însemna fie schimbarea gamei sortimentale, fie schimbarea tehnologiei de fabricaţie.