Programarea liniar

Reoptimizare
Presupunem c am rezolvat o problem de programare liniar, cunoscnd pentru aceasta
soluia optim de baz x
B
=B
-1
b, inversa bazei B
-1
i tabelul simplex corespunztor soluiei optime.
e propunem s vedem, !n condiiile !n care se modi"ic unele din datele problemei, ce anume din
rezolvarea "ostei probleme mai poate "i "olosit la rezolvarea noii probleme, !n !ncercarea de a
rezolva noua problem !ntr-un timp mai scurt dect cel necesar rezolvrii acesteia de la zero, cu
algoritmul simplex. #cest deziderat corespunde ideii de a "olosi experiena anterioar. $e
asemenea, ne propunem s vedem ce in"luen au di"eritele tipuri de modi"icri ale datelor
problemei asupra soluiilor, att din punct de vedere matematic ct i economic.
$atele problemei sunt constituite din%
coe"icienii "unciei obiectiv = componentele vectorului c
termenii liberi ai restriciilor = componentele vectorului b
coe"icienii variabilelor din restricii = elementele matricii #
& modi"icare poate a"ecta toate cele trei grupe.
'om analiza e"ectele modi"icrilor !ncepnd de la cazurile cele mai simple%
(azul 1. Dac se modific doar elementele vectorului c c)
$eoarece matricea # i vectorul b rmn aceleai, avem acelai sistem de restricii i deci
aceeai mulime de soluii admisibile. *oluia optim a "ostei probleme, "iind !n particular soluie de
baz admisibil a sistemului de restricii, va "i soluie admisibil de baz i !n noua problem.
$ispunem deci de o soluie iniial admisibil de baz i, deci, putem aplica algoritmul simplex
primal direct de la "aza a doua. *e construiete tabelul simplex corespunztor soluiei, !n problema
modi"icat%
B
c
S
c
B
c
x
B
x
B
x
B
x
*
B
-1
b +
m B
-1
*
B
c
B
-1
b ,
j

care este de "apt "ostul tabel, !n care se recalculeaz

j

. #vem dou cazuri%

a- $ac toi
. 1 . . . .
c a B c c z
j B j j


,, soluia este optim/
b- $ac exist un
j

0 ,, se aplic !n continuare algoritmul simplex primal, pn la gsirea

soluiei optime.
Exemplu% Pentru problema%
1.*.
2max- f = 3x
1
4x
5
6 5x
3

'

+
+
+
7 5
3
8
3 5
3 5
5 1
x x
x x
x x
x
1
, x
5
, x
3
,

2max-f = 3x
1
4 x
5
65x
3
4 9a
1

'

+ +
+ +
+ +
7 5
3
8
3 3 5
1 5 3 5
1 5 1
s x x
a s x x
s x x
:
1
, x
5
, x
3
, s
1
, s
5
, a
1
,
;<
Programarea liniar
obinem !n "inal urmtorul tabel simplex%
3 -1 5 , , , -9
B
c x
B
x
B x
1
x
5
x
3
s
1
s
5
s
3
a
1
3 x
1
3 1 , , 1 1 5 -5
5 x
3
5 , , 1 , 1 1 -1
-1 x
5
1 , 1 , , -1 -5 5
15 , , , 3 ; 1, 9 - 1,
1. $ac noua "uncie obiectiv este f = x
1
4 5x
5
6 7x
3
atunci tabelul corespunztor va "i%
1 -5 7 , , , -9
B
c x
B
x
B x
1
x
5
x
3
s
1
s
5
s
3
a
1
1 x
1
3 1 , , 1 1 5 -5
7 x
3
5 , , 1 , 1 1 -1
-5 x
5
1 , 1 , , -1 -5 5
11 , , , 1 < 11 9 - 11
toi
j

,, ne a"lm !n cazul a- i soluia care ddea optimul "ostei probleme este soluia optim i
!n noua problem.
5. $ac noua "uncie obiectiv este f = x
1
6 3x
5
- 5x
3
atunci tabelul corespunztor va "i%
1 3 -5 , , , -9
B
c x
B
x
B x
1
x
5
x
3
s
1
s
5
s
3
a
1
1 x
1
3 1 , , 1 1 5 -5
-5 x
3
5 , , 1 , 1 1 -1
3 x
5
1 , 1 , , -1 -5 5
5 , , , 1 -8 -; 9 6 ;
exist
j

0 , 2de exemplu
8
5

s
-, ne a"lm !n cazul b- i soluia care ddea optimul "ostei
probleme nu este optim i !n noua problem, pentru gsirea celei optime 2dac exist=- trebuind s
aplicm !n continuare algoritmul simplex primal.
Cazul 2 $ac se modi"ic doar componentele vectorului b b
$eoarece matricea # rmne aceeai, "osta baz rmne baz i !n noua problem. *oluia
corespunztoare va "i% b B x
B

1
iar
j j j B j
c a B c
1
. >n concluzie, noua soluie ar putea
sau nu s aib toate componentele pozitive 2dup cum este noul b)-, dar sigur toi
?
rmn pozitivi
2"iind aceeai cu cei ai soluiei "ostei probleme, care era optim-, deci soluia este cel puin dual
admisibil de baz. 'om avea dou cazuri%
a- $ac
,
B
x
atunci soluia este i primal admisibil, deci este soluia optim a noii
probleme/
b- $ac
B
x
are cel puin o component negativ atunci soluia este doar dual admisibil de
baz i vom continua cu algoritmul simplex dual pentru gsirea celei optime 2dac ea
exist=-.
;@
Bazele cercetrii operaionale
Exemplu Pentru problema%
1.*.
2max- f = - 8x
1
4 x
5
6 5x
3

'

+ +
+
17 3 7
18 7 5
1A 5 8
3 5 1
3 5 1
3 5 1
x x x
x x x
x x x
x1, x5, x3 ,

2max- f = - 8x1 4 x5 6 5x3 49a1

'

+ + +
+ + +
+ +
17 3 7
18 7 5
1A 5 8
3 3 5 1
1 5 3 5 1
1 3 5 1
s x x x
a s x x x
s x x x
x1,x5, x3, s1, s5, s3,
a1 ,
obinem !n "inal urmtorul tabel simplex%
-8 -1 5 , , , -9
B
c x
B
x
B x
1
x
5
x
3
s
1
s
5
s
3
a
1
, s
1
55
3
11
3
11
, 1 ,
3
1
,
, s
5
11
3
11

3
55
, , 1
3
7
-1
5 x
3
7
3
1

3
7
1 , ,
3
1
,
1,
3
1,
3
13
, , ,
3
5
9
din care obinem inversa bazei B =

,
_

3 , ,
7 1 ,
1 , 1
ca "iind B
-1
=

,
_

3
1
, ,
3
7
1 ,
3
1
, 1
1. $ac noul vector al termenilor liberi, din problema la "orma standard, ar "i b) = 25, 7, ;-
B
atunci tabelul corespunztor ar "i%
-8 -1 5 , , , -9
B
c x
B
x
B x
1
x
5
x
3
s
1
s
5
s
3
a
1
, s
1
8
3
11
3
11
, 1 ,
3
1
,
, s
5
7
3
11

3
55
, , 1
3
7
-1
5 x
3
5
3
1

3
7
1 , ,
3
1
,
8
3
1,
3
13
, , ,
3
5
9
toate componentele soluiei ar "i pozitive, ne-am a"la !n cazul a- i soluia gsit ar "i soluia optim
!n noua problem.
5. $ac noul vector al termenilor liberi din problema la "orma standard ar "i b) = 27, ;, 3-
B
atunci tabelul corespunztor ar "i%
-8 -1 5 , , , -9
B
c x
B
x
B x
1
x
5
:
3
s
1
s
5
s
3
a
1
, s
1
;
3
11
3
11
, 1 ,
3
1
,
A,
Programarea liniar
, s
5
-1
3
11

3
55
, , 1
3
7
-1
5 x
3
1
3
1

3
7
1 , ,
3
1
,
5
3
1,
3
13
, , ,
3
5
9
ar exista componente ale soluiei strict negative 2de exemplu x
3
= -1-, ne-am a"la !n cazul b-, soluia
nu ar "i primal admisibil i, pentru gsirea celei optime, 2dac exist=- vom aplica !n continuare
algoritmul simplex dual.
Cazul 3. $ac apar C variabile suplimentare, cu coe"icienii corespunztori, !n "uncia
obiectiv i !n restricii.
#ceast modi"icare are ca e"ect adugarea a C coloane la matricea # i a C elemente la
vectorul c, numrul de restricii 2i deci de linii ale matricii # i de elemente ale vectorului b-
rmnnd acelai.
$eoarece, !n momentul a?ungerii la soluia optim, !n sistem se a"l doar restricii
independente !ntre ele, rangul matricii este egal cu numrul de linii 2care este mai mic dect
numrul de coloane- i, din acest motiv, adugarea orictor coloane nu !l va modi"ica. Baza "ostei
matrici rmne deci baz i !n noua matrice, soluia x
B
= B
-1
b , rmne soluie de baz a noului
sistem de restricii 2B i b "iind aceeai-, deci este i o soluie de baz primal admisibil a noii
probleme. Babelul corespunztor acestei baze, !n noua problem, este cel anterior, la care se adaug
C coloane ast"el%
pe linia variabilelor se adaug noile variabile/
pe linia coe"icienilor "unciei obiectiv se adaug coe"icienii corespunztori noilor
variabile/
!n interiorul tabelului, sub "iecare variabil nou introdus, se adaug coloana B
-1
a
C
,
unde a
C
este vectorul coloan "ormat din coe"icienii variabilei x
C
, nou introduse !n
restriciile problemei/

C
, corespunztori noilor variabile, se calculeaz cu "ormula cunoscut%
C
=
T
B
c B
-1
a
C
-
c
C
.
'om avea dou cazuri%
a- $ac toi
C
sunt pozitivi, soluia optim a "ostei probleme este soluie optim i pentru
noua problem/
b- $ac exist un indice C, pentru care
C
0 ,, atunci soluia este doar primal admisibil i
vom aplica !n continuare algoritmul simplex primal, pentru gsirea soluiei optime 2dac
ea exist=-
A1
Bazele cercetrii operaionale
Exemplu 1ie problema%
1.*.
2max- f = 3x
1
6 8x
5
4 5x
3

'

+
+
+
3
7
3; A 1,
3 5 1
5 1
3 5 1
x x x
x x
x x x
x1, x5, x3 ,

2max- f = 3x1 6 8x5 4 5x3 49a1

'

+ +
+ + +
+ +
3
7 7
3; A 1,
3 3 5 1
5 3 5 1
1 1 3 5 1
s x x x
s x x x
a s x x x
x1,x5, x3, s1, s5, s3, a1
,
pentru care obinem tabelul simplex "inal%
3 8 -5 , , , -9
B
c x
B
x
B x
1
x
5
x
3
s
1
s
5
s
3
a
1
8 x
5
8 , 1 ,
3
1
3
3
1
3
1

3 x
1
1 1 , ,
3
1

-5
3
1

3
1
-5 x
3
5 , , 1 , 1 -1 ,
17 , , ,
3
1
8 5 9
3
1

de unde gsim inversa bazei B =

,
_

1 1 1
, 1 1
1 1, A
ca "iind B
-1
=

,
_

1 1 ,
3
1
5
3
1
3
1
3
3
1
.
1. $ac introducem, !n plus, variabilele x
8
, x
7
i x
;
, obinnd problema la "orma standard%
2max- f = 3x1 6 8x5 4 5x3 65x8 4 5,x7 4x; 49a1

'

+ +
+ + + + +
+ + + +
3 5 5
7 5 3 5 7
3; 3 A 1,
3 ; 7 8 3 5 1
5 ; 7 8 3 5 1
1 1 ; 7 8 3 5 1
s x x x x x x
s x x x x x x
a s x x x x x x

x1, x5, x3, x8, x7, x;, s1, s5, s3, a1 ,
vom obine tabelul corespunztor bazei B, !n noua problem, prin%
adugarea variabilelor x
8
, x
7
, x
;
la linia variabilelor/
adugarea coe"icienilor 5, -5,, -1 corespunztori acestor variabile la linia coe"icienilor
"unciei obiectiv/
adugarea coloanelor%
a
8
=

,
_

1 1 ,
3
1
5
3
1
3
1
3
3
1

,
_

5
5
1
=

,
_

8
3
7
,
A5
Programarea liniar
a
7
=

,
_

1 1 ,
3
1
5
3
1
3
1
3
3
1

,
_

5
3
1
=

,
_

1
3
1@
3
5<
,
a
;
=

,
_

1 1 ,
3
1
5
3
1
3
1
3
3
1

,
_

5
5
1
=

,
_

8
3
7
.
adugm%

8
=
T
B
c B
-1
a
8
4 c
8
= 1

7
=
T
B
c B
-1
a
7
4 c
7
=
3
11

;
=
T
B
c B
-1
a
;
4 c
;
=
3
1A
i, "inal, obinem tabelul%
3 8 -5 5 -5, -1 , , , -9
B
c x
B
x
B x
1
x
5
x
3
x
8
x
7
x
;
s
1
s
5
s
3
a
1
8 x
5
8 , 1 , 7
3
5<

3
18
3
1
3
3
1
3
1

3 x
1
1 1 , , -3
3
1@
3
<

3
1

-5
3
1

3
1
-5 x
3
5 , , 1 8 -1 3 , 1 -1 ,
17 , , , 1
3
11
3
1A

3
1
8 5
9
3
1

*e observ c toi
?
sunt pozitivi, deci soluia este optim.
5. $ac, pentru aceeai modi"icare, alegem coe"icientul lui x
7
egal cu 41,, !n loc de 45,, !n
tabel se va modi"ica doar
7
, care va avea valoarea
3
1@

i ne vom a"la !n cazul b- 2deoarece

7
0
,-/ vom continua cutarea soluiei optime cu algoritmul simplex primal.
Cazul 4. $ac se adaug o restricie
D"ectul este adugarea unei linii la matricea # i a unui element la vectorul b.
*e veri"ic dac "osta soluie de optim veri"ic noua restricie. $ac o veri"ic, ea este
soluia de optim i a noii probleme. $ac nu o veri"ic, vom cuta !n continuare noua soluie de
optim 2dac ea exist=-.
$eoarece rangul matricii # era egal cu numrul de linii 2care era mai mic dect numrul de
coloane-, prin adugarea unei linii rangul noii matrici va "i cu 1 mai mare 2dac nu s-ar !ntmpla aa
ar rezulta c noua restricie este o combinaie a celor anterioare i, deci, nu are nici un e"ect asupra
mulimii soluiilor, putnd "i eliminat din sistem, noua problem "iind de "apt aceeai cu "osta
problem, care e de?a rezolvat-.
A3
Bazele cercetrii operaionale
>n acest caz, "osta baz nu mai este baz !n noua matrice, ci doar un minor cu determinantul
di"erit de zero, de dimensiune cu 1 mai mic dect rangul matricii. Pentru a obine baza noii
probleme vom borda "osta baz cu noua linie i o coloan.
$in ultimul tabel simplex al "ostei probleme, putem scrie "ostul sistem la "orma%
x
B
6B
-1
E*Ex
*
= B
-1
Eb = x
B
de unde scoatem variabilele principale !n "uncie de cele secundare, le !nlocuim !n noua restricie i
apoi aran?m ca termenul liber b
m61
obinut s "ie pozitiv 2!nmulind eventual restricia cu 41-.
#dugm noua restricie, sub "orma obinut, la sistemul iniial, scris sub "orma corespunztoare
ultimului tabel simplex. #vem trei cazuri%
a- $ac restricia este de tipul FG, introducem variabila de abatere s, care va avea
coe"icientul 61 i baza va "i "ormat din coloanele corespunztoare "ostelor variabile
principale, plus coloana variabilei s, obinnd matricea unitate. Babelul corespunztor !n
noua problem va "i "ostul tabel, la care se adaug%
o linie !n plus, pe care% c
s
= , !n coloana coe"icienilor din "uncia obiectiv ai
variabilelor din baza, s !n coloana variabilelor bazei, b
m61
!n coloana soluiei de baz,
coe"icienii noii restricii 2adus la ultima "orm- !n interiorul tabelului i 1 in
dreptul noii variabile s.
o coloan !n plus corespunztoare lui s, care va "i vector unitar.
>n acest caz, noii
?
vor "i "otii
?
2deoarece c
s
= ,-, la care se adaug cel corespunztor
lui s 2egal cu ,, deoarece s este din baz-. *oluia are toate componentele pozitive i toi

?
pozitivi, deci este soluia optim cutat.
b- $ac restricia este de tipul FG variabila de abatere va avea coe"icientul 41 i soluia
corespunztoare este doar dual admisibil 2deoarece s = -b
m61
0 ,-/ vom continua
cutarea soluiei optime cu algoritmul simplex dual.
c- $ac restricia este cu F=G, se introduce variabila arti"icial a, cu c
a
= -9, se construiete
tabelul asociat ca la cazul a- i se obine o soluie admisibil 2deoarece a = b
m61
,-, cu

?
depinznd de 9 2deoarece c
a
= -9-. *e continu cu algoritmul simplex primal.
Exemplu 1ie problema%
1.*.
2max- f = x
1
43x
5
6 5x
3

'

+ +
+ +
+
1< 8 3
1< 7
@ 5 8
3 5 1
3 5 1
3 5 1
x x x
x x x
x x x
x
1
, x
5
, x
3
,

2max- f = x
1
43x
5
6 5x
3

'

+ + +
+ + +
+ +
1< 8 3
1< 7
@ 5 8
3 3 5 1
1 5 3 5 1
1 3 5 1
s x x x
a s x x x
s x x x
x
1
, x
5
, x
3
, s
1
, s
5
, s
3
, a
1
,
pentru care obinem tabelul "inal%
A8
Programarea liniar
1 -3 5 , , , -9
c
B
x
B
x
B
x
1
x
5
x
3
s
1
s
5
s
3
a
1
, s
5
78 , 11 , 5 1 3 -1
5 x
3
@@ , 55 1 3 , 8 ,
1 x
1
5A 1 ; , 1 , 1 ,
557 , 73 , A , @ 9
din care putem scrie sistemul de restricii sub "orma%

'

+ + +
+ + +
+ + +
5A ;
@@ 8 3 55
78 5 11
3 1 5 1
3 1 5 3
3 1 5 5
s s x x
s s x x
s s x s

'

3 1 5 1
3 1 5 3
3 1 5 5
; 5A
8 3 55 @@
5 11 78
s s x x
s s x x
s s x s

1. $ac noua restricie ar "i 5x
1
6 x
5
4 x
3
A atunci soluia de optim 2x
1
= 5A, x
5
= ,, x
3
= @@-
ar veri"ica noua restricie i ar "i soluie de optim i pentru noua problem.
5. $ac noua restricie ar "i 3x
1
65x
5
6 x
3
< ea nu ar "i veri"icat de "osta soluie de optim.
>nlocuind !n aceast restricie s
5
, x
1
i x
3
, cu expresiile obinute !n sistemul de mai sus, rezult%
3E25A 4 ;x
5
4 s
1
4 s
3
- 6 5x
5
6 2@@ 4 55x
5
4 3s
1
4 8s
3
- <
-3<x
5
4 ;s
1
4 As
3
-1A5 3<x
5
6 ;s
1
6 As
3
1A5
3<x
5
6 ;s
1
6 As
3
4 s = 1A5
i sistemul%

'

+ +
+ + +
+ + +
+ + +
1A5 A ; 3<
5A ;
@@ 8 3 55
78 5 11
3 1 5
3 1 5 1
3 1 5 3
3 1 5 5
s s s x
s s x x
s s x x
s s x s
iar !n "inal, tabelul%
1 -3 5 , , , ,
c
B
x
B
x
B
x
1
x
5
x
3
s
1
s
5
s
3
s
, s
5
78 , 11 , 5 1 3 ,
5 x
3
@@ , 55 1 3 , 8 ,
1 x
1
5A 1 ; , 1 , 1 ,
, s -1A5 , 3< , ; , A 1
557 , 73 , A , @ ,
!n care soluia de baz este dual admisibil. *e continu rezolvarea problemei cu algoritmul simplex
dual.
3. $ac noua restricie ar "i x
1
6 x
5
6 x
3
= 1,, ea nu ar "i veri"icat de "osta soluie. Prin
!nlocuirea lui x
1
i x
3
obinem%
25A 4 ;x
5
4 s
1
4 s
3
- 6 x
5
6 2@@ 4 55x
5
4 3s
1
4 8s
3
- = 1,,
-5Ax
5
4 8s
1
4 7s
3
= -5; 5Ax
5
6 8s
1
6 7s
3
= 5;
5Ax
5
6 8s
1
6 7s
3
6 a = 5;
A7
Bazele cercetrii operaionale
rezult sistemul%

'

+ + +
+ + +
+ + +
+ + +
5; 7 8 5A
5A ;
@@ 8 3 55
78 5 11
3 1 5
3 1 5 1
3 1 5 3
3 1 5 5
a s s x
s s x x
s s x x
s s x s
iar !n "inal, tabelul%
1 -3 5 , , , -9
c
B
x
B
x
B
x
1
x
5
x
3
s
1
s
5
s
3
a
, s
5
78 , 11 , 5 1 3 ,
5 x
3
@@ , 55 1 3 , 8 ,
1 x
1
5A 1 ; , 1 , 1 ,
-9 a 5; , 5A , 8 , 7 1
-5;9 6 557 , -5A9 6 73 , -89 6 A , -79 6 @ ,
!n care soluia de baz este primal admisibil. *e continu rezolvarea problemei cu algoritmul
simplex primal.
Cazul 5. $ac se modi"ic coe"icienii unei variabile x
?
D"ectul este modi"icarea coloanei a
?
j
a
din # [Link] a coe"icientului c
?
j
c
din "uncia
obiectiv. #vem dou variante%
Cazul 5.1 (oloana a
?
nu "ace parte din B. >n acest caz "osta baz B rmne baz i !n noua
problem, soluia corespunztoare este aceeai% x
B
= B
-1
Eb i tabelul corespunztor este "ostul tabel,
!n care se modi"ic doar coloana corespunztoare variabile x
?
%

c
?
j
c
, B
-1
Ea
?
B
-1
E j
a
,
?

j j B j
c a B c
1
#vem dou cazuri%
$ac
,
j "osta soluie optim rmne optim i !n noua problem.
$ac j

0 , "osta soluie optim este doar primal admisibil i se va continua

rezolvarea problemei cu algoritmul simplex primal.
Exemplu 1ie problema%
1.*.
2max- f = 5x
1
63x
5
6 8x
3

'

+
+
+
7 7 8
17 8 7 ;
17 7 ;
3 5 1
3 5 1
3 5 1
x x x
x x x
x x x
x
1
, x
5
, x
3
,

2max- f = 5x
1
63x
5
6 8x
3

'

+ +
+ +
+ +
7 7 8
17 8 7 ;
17 7 ;
3 3 5 1
5 3 5 1
1 1 3 5 1
s x x x
s x x x
a s x x x
x
1
, x
5
, x
3
, s
1
, s
5
, s
3
, a
1
,
$up rezolvare, se obine tabelul simplex "inal de mai ?os, din care se gsete inversa bazei
B =

,
_

7 , 8
7 , ;
7 1 ;
ca "iind B
-1
=

,
_

7
3
7
5
,
; 7 1
5
1
5
1
,
A;
Programarea liniar
5 3 8 , , , -9
c
B
x
B
x
B
x
1
x
5
x
3
s
1
s
5
s
3
a
1
5 x
1
1, 1 ,
5
3
,
5
1
5
1
,
, s
1
@, , , 17 1 7 ; -1
3 x
5
@ , 1 1 ,
7
5
7
3
,
8A , , 5 ,
7
11
7
18
9
1. $ac se modi"ic coe"icienii variabilei x
3
, problema devenind%
1.*.
2max- f = 5x
1
63x
5
6 5x
3

'

+
+
+
7 3 7 8
17 3 7 ;
17 5 7 ;
3 5 1
3 5 1
3 5 1
x x x
x x x
x x x
x
1
, x
5
, x
3
,

2max- f = 5x
1
63x
5
6 5x
3

'

+ +
+ +
+ +
7 3 7 8
17 3 7 ;
17 5 7 ;
3 3 5 1
5 3 5 1
1 1 3 5 1
s x x x
s x x x
a s x x x
x
1
, x
5
, x
3
, s
1
, s
5
, s
3
, a
1
,
noua coloan corespunztoare lui x
3
va "i a
.
3
=

,
_

7
3
7
5
,
; 7 1
5
1
5
1
,
E

,
_

3
3
5
=

,
_

7
3
1
,
iar
.
3
=
7
1@

0 ,,
deci
ne a"lm !n cazul b- i vom continua rezolvarea problemei cu algoritmul simplex primal, de la
tabelul%
5 3 5 , , , -9
c
B
x
B
x
B
x
1
x
5
x
3
s
1
s
5
s
3
a
1
5 x
1
1, 1 , , ,
5
1
5
1
,
, s
1
@, , , -1 1 7 ; -1
3 x
5
@ , 1
7
3

,
7
5
7
3
,
8A , ,
7
1@

,
7
11
7
18
9
5. $ac se modi"ic coe"icienii variabilei x
3
, problema devenind%
1.*.
2max- f = 5x
1
63x
5
- 3x
3

'

+
+
+
7 5 7 8
17 7 7 ;
17 3 7 ;
3 5 1
3 5 1
3 5 1
x x x
x x x
x x x
x
1
, x
5
, x
3
,

2max- f = 5x
1
63x
5
4 3x
3

'

+ +
+ +
+ +
7 5 7 8
17 7 7 ;
17 3 7 ;
3 3 5 1
5 3 5 1
1 1 3 5 1
s x x x
s x x x
a s x x x
x
1
, x
5
, x
3
, s
1
, s
5
, s
3
, a
1
,
AA
Bazele cercetrii operaionale
noua coloan corespunztoare lui x
3
va "i a
.
3
=

,
_

7
3
7
5
,
; 7 1
5
1
5
1
,
E

,
_

5
7
3
=

,
_

7
8
1;
5
3
iar
.
3
=
7
85
0 ,, deci
ne a"lm !n cazul a- cu "osta soluie optim i pentru noua problem, tabelul "inal "iind%
5 3 -3 , , , -9
c
B
x
B
x
B
x
1
x
5
x
3
s
1
s
5
s
3
a
1
5 x
1
1, 1 ,
5
3
,
5
1
5
1
,
, s
1
@, , , 1; 1 7 ; -1
3 x
5
@ , 1
7
8
,
7
5
7
3
,
8A , ,
7
85
,
7
11
7
18
9
Cazul 5.2 (oloana a
?
"ace parte din baza B. >n acest caz "osta baz nu mai exist !n noua
matrice #. oul minor B), obinut prin !nlocuirea lui a
?
cu j
a
!n B, poate "i%
neinversabil 2det B) = ,- caz !n care trebuie cutat alt baz/
inversabil, soluia corespunztoare x
B)
= 2B)-
-1
Eb putndu-se !n urmtoarele situaii%
are toate componentele pozitive 2x
B)
,-, deci este primal admisibil i putem aplica !n
continuare algoritmul simplex primal/
are componente strict negative, dar are toi
?
pozitivi, deci este dual admisibil i
putem aplica !n continuare algoritmul simplex dual/
are componente strict negative i exist
?
strict negativi, deci nu este nici primal nici
dual admisibil i trebuie cutat alt baz.
*e observ c exist variante cnd trebuie cutate alte baze i, cHiar !n cazurile cnd putem
"olosi noua baz, avem de "cut calcule laborioase 2inversarea lui B), calculul produselor B
-1
Eb i B
-
1
E# i calculul noilor
?
-. $in acest motiv vom aplica urmtorul procedeu 2"r a mai veri"ica
posibilitatea existenei unui caz "avorabil de mai sus-%
pasul 1. *e scriu !n noua problem 2adus la "orma canonic- toi termenii cu variabila x
?
ca
o sum de doi termeni, unul avnd coe"icient "ostul coe"icient al variabilei x
?
iar cellalt di"erena
dintre acetia%
j
c
E x
?
= c
?
E x
?
6 2 j
c
- c
?
- E x
?
ij
a
E x
i?
= a
i?
E x
?
6 2 ij
a
- a
i?
- E x
?
pasul 2. *e !nlocuiete !n toi termenii de "orma 2 j
c
- c
?
- E x
?
i 2 ij
a
- a
i?
- E x
?
, variabila x
?
cu
o nou variabil I i se adaug la sistem restricia x
?
= I, obinndu-se o problem ecHivalent.
pasul 3. Pentru noua problem, se aplic procedeul de la cazul 4 pentru varianta c-,
obinndu-se o soluie de baz admisibil cu care se continu cu algoritmul simplex primal.
Exemplu $up rezolvarea problemei%
A<
Programarea liniar
1.*.
2max- f = 5x
1
63x
5
6 7x
3

'

+ +
+ +
+ +
; 5
< 3 5
1, 5 3
3 5 1
3 5 1
3 5 1
x x x
x x x
x x x
x
1
, x
5
, x
3
,

2max- f = 5x
1
63x
5
6 7x
3

'

+ + +
+ + +
+ + +
; 5
< 3 5
1, 5 3
3 3 5 1
5 3 5 1
1 3 5 1
s x x x
s x x x
s x x x
x
1
, x
5
, x
3
, s
1
, s
5
, s
3
,
se obine soluia optim i tabelul pentru baza corespunztoare variabilelor 2x
1
, x
3
, s
3
-, !n care 2x
1
=
5, x
3
= 5, s
3
= ,- i tabelul%
5 3 7 , , ,
c
B
x
B
x
B
x
1
x
5
x
3
s
1
s
5
s
3
5 x
1
5 1
A
1

,
A
3
A
5

,
7 x
3
5 ,
A
7
1
A
1

A
3
,
, s
3
, ,
A
8
,
A
7

A
1
1
18 ,
A
5
,
A
1
A
11
,
B i B
-1
"iind date mai ?os%
B =

,
_

1 1 5
, 3 1
, 5 3
B
-1
=

,
_

1
A
1
A
7
,
A
3
A
1
,
A
5
A
3
$ac presupunem c se modi"ic coe"icienii variabilei x
3
, noua problem "iind%
1.*.
2max- f = 5x
1
63x
5
6 5x
3

'

+ +
+ +
+ +
; 5
< 5
1, 3
3 5 1
3 5 1
3 5 1
x x x
x x x
x x x
x
1
, x
5
, x
3
,

2max- f = 5x
1
63x
5
6 5x
3

'

+ + +
+ + +
+ + +
; 5
< 5
1, 3
3 3 5 1
5 3 5 1
1 3 5 1
s x x x
s x x x
s x x x
x
1
, x
5
, x
3
, s
1
, s
5
, s
3
,
deoarece x
3
"ace parte din baz, vom "ace trans"ormarea%
1.*.
2max- f = 5x
1
63x
5
6 5x
3

'

+ + +
+ + +
+ + +
; 5
< 5
1, 3
3 3 5 1
5 3 5 1
1 3 5 1
s x x x
s x x x
s x x x
x
1
, x
5
, x
3
, s
1
, s
5
, s
3
,

2max- f = 5x
1
63x
5
6 7x
3
- 3I

'

+ + +
+ + +
+ + +
y x
s x x x
s y x x x
s y x x x
3
3 3 5 1
5 3 5 1
1 3 5 1
; 5
< 5 3 5
1, 5 3
x
1
, x
5
, x
3
, s
1
, s
5
, s
3
, I ,
A@
Bazele cercetrii operaionale
$in primele trei ecuaii scoatem variabilele "ostei baze 2x
1
, x
3
, s
3
- !n "uncie de celelalte,
!nmulind sistemul cu B
-1
. (oe"icienii "ostelor variabile se iau din ultimul tabel iar ai lui I se
calculeaz !nmulind coloana coe"icienilor lui cu B
-1
. #vem%
B
-1

E

,
_

,
5
1
=

,
_

1
A
1
A
7
,
A
3
A
1
,
A
5
A
3
E

,
_

,
5
1
=

,
_

A
3
A
7
A
1
deci sistemul va avea "orma%

'

+ + +
+ +
+ +
y x
s s s y x
s s y x x
s s y x x
3
3 5 1 5
5 1 3 5
5 1 5 1
,
A
1
A
7
A
3
A
8
5
A
3
A
1
A
7
A
7
5
A
5
A
3
A
1
A
1
$in primele trei ecuaii se scot variabilele bazei !n "uncie de celelalte%

'

+
+ +
+ +
5 1 5 3
5 1 5 3
5 1 5 1
A
1
A
7
A
3
A
8
A
3
A
1
A
7
A
7
5
A
5
A
3
A
1
A
1
5
s s y x s
s s y x x
s s y x x
apoi se !nlocuiesc !n ultima ecuaie%
y s s y x + +
5 1 5
A
3
A
1
A
7
A
7
5

5
A
3
A
1
A
5
A
7
5 1 5
+ + s s y x
!n
care se adaug variabila de abatere a i se adaug la sistem. *e obine !n "inal problema%
2max- f = 5x
1
63x
5
6 7x
3
- 3I

'

+ + +
+ + +
+ +
+ +
5
A
3
A
1
A
5
A
7
,
A
1
A
7
A
3
A
8
5
A
3
A
1
A
7
A
7
5
A
5
A
3
A
1
A
1
5 1 5
3 5 1 5
5 1 3 5
5 1 5 1
a s s y x
s s s y x
s s y x x
s s y x x
Babelul corespunztor va "i%
<,
Programarea liniar
5 3 7 -3 , , , -9
c
B
x
B
x
B
x
1
x
5
x
3
I s
1
s
5
s
3
a
5 x
1
5 1
A
1

,
A
1
A
3
A
5

, ,
7 x
3
5 ,
A
7
1
A
7

A
1

A
3
, ,
, s
3
, ,
A
8
,
A
7

A
7

A
1
1 ,
-9 a 5 ,
A
7
,
A
5
A
1

A
3
, 1
18-59 , A
5
-
A
7
9
,
A
5

A
5

9
A
1
6
A
1
9
A
11
-
A
3
9 , ,
!n care soluia de baz este admisibil i vom continua rezolvarea cu algoritmul simplex primal.
$in punct de vedere economic, situaiile de mai sus pot "i "oarte bine exempli"icate pe cazul
unei !ntreprinderi care "abric n produse "olosind m materii prime i dorete gsirea acelor cantiti
ce trebuie "abricate din "iecare produs ast"el !nct s obin pro"itul total maxim.
>n acest caz coe"icienii problemei vor "i%
c
?
= pro"iturile unitare obinute prin vnzarea celor n produse.
b
i
= disponibilurile din cele m materii prime.
a
i?
= coe"icienii teHnologici.
1. 9odi"icarea coe"icienilor "unciei obiectiv poate !nsemna "ie o reevaluare a pro"iturilor
unitare, "ie pur i simplu scHimbarea obiectivului propus 2de exemplu maximizarea
veniturilor sau minimizarea cHeltuielilor !n loc de maximizarea pro"itului, caz !n care c
i
ar avea alte semni"icaii 2venit unitar, cost unitar- i deci cu totul alte valori-.
5. 9odi"icarea termenilor liberi poate !nsemna modi"icarea posibilitilor de procurare a
materiilor prime prin pierderea unor "urnizori sau realizarea de contracte cu noi
"urnizori.
3. #pariia de coloane !n plus !nseamn lrgirea gamei de produse.
8. #pariia de noi restricii poate !nseamn existena unei resurse care nu "usese luat !n
considerare pn acum, deoarece limitele datorate acesteia erau su"icient de largi pentru
a nu in"luena soluia, !n urma modi"icrii acestor limite ele putnd modi"ica soluia.
7. 9odi"icarea coloanelor poate !nsemna "ie scHimbarea gamei sortimentale, "ie scHimba-
rea teHnologiei de "abricaie.
<1