LORENA TUFAN

CULEGERE DE PROBLEME DE OPTIMIZARE CONVEX

Editura Fundaiei Romnia de Mine, 2001ISBN 973-582-433-7

Bun de tipar: 18.VII.2001; Coli tipar: 12,75 Format: 16/6186 Editura i Tipografia Fundaiei Romnia de Mine Splaiul Independenei nr.313, Bucureti, sector 6, Oficiul Potal 78 Telefon: 410 43 80; Fax. 411 33 84 www. SpiruHaret.ro

UNIVERSITATEA SPIRU HARETFACULTATEA DE MATEMATIC-INFORMATIC

LORENA TUFAN

CULEGERE DE PROBLEME DE OPTIMIZARE CONVEX

EDITURA FUNDAIEI ROMNIA DE MINE Bucureti, 2001

CUPRINS

I. PROGRAMARE LINIAR I. 1. Sisteme de ecuaii i inecuaii liniare ............................ I. 2. Algoritmul simplex primal .......................................... I. 3. Metoda celor dou faze ................................................ I.4. Determinarea tuturor soluiilor optime ........................... I.5. Degenerare i ciclare .................................................... I.6. Algoritmul simplex revizuit .......................................... I.7. Algoritmul simplex dual ............................................... I.8. Reoptimizare ................................................................ I.9. Parametrizare ............................................................. I. 10 Programare liniar n numere ntregi ........................ I.10.1. Algoritmul ciclic al lui Gomory ...................... I.10.2. Algoritmul mixt al lui Gomory ........................ I.11. Probleme de transport ................................................. I.12. Probleme recapitulative ........................................... II. PROGRAMARE NELINIAR II.1. Funcii convexe i generalizat convexe ......................... II.2. Condiii necesare sau suficiente de optimizare .............. II.3. Dualitate ..................................................................... II.4. Metode de optimizare fr restricii ............................. II.4.1. Metoda celei mai rapide descreteri .................... II.4.2. Metoda direciilor conjugate ............................. II.4.3. Metoda Quasi-Newton ....................................... 124 130 145 153 153 160 1675

9 19 29 41 46 52 57 66 74 84 84 95 101 110

6

PREFA

Prezenta lucrare este un manual auxiliar pentru cursul de optimizare convex din programa de nvmnt a facultilor de matematic - informatic, dar poate fi folosit cu succes i de studenii facultilor cu profil economic. Lucrarea este structurat n dou capitole ce cuprind probleme rezolvate i probleme propuse de programare liniar i programare neliniar, probleme judicios selecionate pentru consolidarea cunotinelor studenilor asupra principalelor metode de optimizare convex. Urez succes tuturor cititorilor acestei cri! Autoarea

7

8

I. PROGRAMARE LINIAR

I.1. Sisteme de ecuaii i inecuaii liniare I. 1.A. Sisteme de ecuaii liniare n acest capitol ne vom ocupa de sistemele de ecuaii algebrice de gradul nti cu mai multe necunoscute, sau, aa cum li se mai spune de obicei, sisteme de ecuaii liniare. Fie dat un sistem de m ecuaii cu n necunoscute. Convenim s notm necunoscutele prin: x1, x2, ..., xn, coeficientul cu care apare necunoscuta xj din ecuaia a i-a prin: aij, iar membrul al doilea (numit termenul liber) din ecuaia a i-a prin bi. Cu aceste notaii sistemul de ecuaii liniare se scrie sub forma general:

(1)

a 11x 1 + a 12 x 2 + K + a 1n x n = b 1 a 21x 1 + a 22 x 2 + K + a 2n x n = b 2 ............................................. a m1x1 + a m2 x 2 + K + a mn x n = b m x j = bi , 1 i m

Sistemul (1) mai poate fi scris condensat sub forma:

aj=1

n

ij

Coeficienii necunoscutelor formeaz o matrice cu m linii i n coloane:

a 11 a 21 A= K a m1

a 12 a 22 K a m2

K a 1n K a 2n K K K a mn

9

numit matricea coeficienilor sistemului sau, simplu, matricea sistemului. Matricea cu m linii i n+1 coloane

a 11 a 21 A= K a m1

a 12 a 22 K a m2

K a 1n K a 2n K K K a mn

b1 b2 K bm

care se obine adugnd la coloanele matricei A coloana termenilor liberi b1, b2, ..., bm se numete matricea extins a sistemului. Un sistem de numere 1, 2, ..., n se numete soluie a sistemului (1) dac nlocuind necunoscutele x1, x2, ..., xn respectiv prin aceste numere, toate ecuaiile acestui sistem sunt verificate, adic:

a ij j = b i , 1 i mj=1

n

Un sistem de ecuaii care are soluii se numete incompatibil. Aa este de exemplu sistemul:

3x 1 + 5x 2 = 2 3x 1 + 5x 2 = 9

Un sistem de ecuaii care are cel puin o soluie se numete compatibil. Un sistem compatibil se numete determinat dac are o singur soluie i se numete nedeterminat dac are mai mult dect o soluie. Exemplu: 1) Sistemul:

x1 + 3x 2 = 7 x1 + x 2 = 5

este determinat, deoarece are soluia x1 = 4, x2 = 1 i aceasta este singura soluie a sistemului. 2) Sistemul:

2x1 x 2 = 1 4x1 2x 2 = 2

este nedeterminat deoarece are mai multe soluii (chiar o mulime infinit de soluii) x1 = k, x2 = 2k 1, k fiind un numr arbritar.10

Observm c soluiile de mai sus ne dau ntreaga mulime de soluii a sistemului. n legtur cu sistemele de ecuaii liniare ne punem problema stabilirii unor metode care s ne permit s decidem dac un sistem de ecuaii dat este compatibil sau nu, iar n cazul n care este compatibil, s putem spune dac este determinat sau nu, i s dm procedee de gsire a tuturor soluiilor sale. I.1.A.1. Teorem (Regula lui Cramer). Fie sistemul (1). Fie d = det A determinantul sistemului i dj, 1 j n, determinantul care se obine din d prin nlocuirea coloanei j prin coloana b. Dac d este nenul, atunci sistemul are o soluie unic, anume:

x1 =

d1 d d , x 2 = 2 ,K, x n = n d d d

I.1.A.2. Exerciiu rezolvat. S rezolvm sistemul de ecuaii liniare:

2 x 1 x 2 + x 3 x 4 = 1 2 x x + 3x 4 = 2 1 2 x 3 + x 4 = 3 3x 1 2 x 1 + 2 x 2 2 x 3 + 5 x 4 = 6 Determinantul

2 1 1 1 2 1 0 3 = 9 d= 3 0 1 1 2 2 2 5al acestui sistem fiind nenul, soluia este dat de formulele lui Cramer. Valorile necunoscutelor vor avea la numrtor urmtorii determinani:11

1 1 1 1 2 1 0 3 = 0, d1 = 3 0 1 1 6 2 2 5 2 1 1 1 2 1 2 3 = 15, d3 = 3 0 3 1 2 2 6 5Astfel x1 = 0, x 2 = 2, x 3 =

2 1 1 1 2 2 0 3 d1 = = 18 3 3 1 1 2 6 2 5 2 1 1 1 2 1 0 2 d4 = = 12 3 0 1 3 2 2 2 6

nostru. Mai mult, aceasta este unica soluie.

5 4 , x 4 = este soluia sistemului 3 5

I.1.A.2. Teorem (Kronecker - Capelli). Un sistem de ecuaii liniare (1) este compatibil dac i numai dac rangul matricei sistemului, A, este egal cu rangul matricei extinse A . I.A.1.3. Definiie. 1) Se numete minor principal al sistemului (1) orice minor nenul al matricii A astfel nct toi minorii, care conin pe d s fie nuli. 2) Se numete minor caracteristic al sistemului (1) orice minor de ordin r + 1, unde r este numrul de linii i coloane al lui d, obinut prin bordarea unui minor principal cu elemente corespunztoare ale coloanei termenilor liberi, precum i ale uneia dintre liniile rmase. I.A.1.4. Teorem (Rouch). Un sistem de ecuaii (1) este compatibil dac i numai dac toi minorii caracteristici sunt nuli.

I.A.1.5. Exerciiu rezolvat. S rezolvm sistemul:

12

4x1 + 2x 2 3x 3 x 4 = 4 x + x x = 3 1 2 3 + x4 = 1 3x1 + 3x 2 x1 7x 2 + 3x 3 = 3 Calculm determinantul sistemului i obinem:

4 1

2 3 1 1 1 3 0 3 0 1 0

3

=0

1 7

Cu toate c numrul de ecuaii este egal cu numrul de necunoscute, nu se pot folosi direct formula lui Cramer, deoarece determinantul sistemului este nul. Matricea coeficienilor este de rang 3 un minor principal fiind de exemplu:

2 3 1 1 1 0 = 2 0 3 0 1Exist un singur minor caracteristic:

2 3 1 4 1 1 3 0 3 0 1 0

31

=0

7

3

care fiind nul, sistemul este compatibil. Considerm primele trei ecuaii cu necunoscutele principale x2, x3, x4. Dac x1 = fiind necunoscut secundar, gsim: x2 = 3 + , x3 = 6 + 2, x4 = 8. I.A.1.6. Exerciiu rezolvat. S rezolvm sistemul:13

x + y + z = 1 x + y + z = 1 x + y + z = 1 Calculm determinantul sistemului i obinem:

1 1 1 1 1 1=0 1 1 1Matricea coeficienilor este de rang 1 i un minor principal este de exemplu 1 0. Exist doi determinani caracteristici:

1 1 1 1

= 0 i

1 1 1 1

=0

care, fiind nuli, sistemul este compatibil. Considerm prima ecuaie cu necunoscuta principal x1. Dac x2 = i x3 = necunoscute secundare, gsim: x1 = 1 . I.1.B. Sisteme de ecuaii liniare I.1.B.1. Lema Farca Mincowski. Fie A Mmn(R) i b Mn,1(R). Considerm sistemele de inecuaii: (1)

Ax = b x0

(2)

A T u 0T b 0 2 3 1 u 1 0, u 2 0, u 3 arbitrar 5u1 + 4 u 2 u 3 0 7u1 + u3 = 0 b) u + 2u 0 1 2 3u + 10 u u > 0 1 2 3 u1 0, u 2 arbitrar, u 3 0 17

Cum sistemul este compatibil, din teorema Farca Mincowski rezult c urmtorul sistem este incompatibil:

5x 1 + 7x 2 + x 3 3 4 x 1 2x 3 = 10 = 1 x1 x 2 x 1 0, x 2 arbitrar, x 3 0 Exerciii propuse spre rezolvare I.1.E.1. Rezolvai sistemele de ecuaii liniare.

x 2y + z + t = 1 a) x y + z t = 1 x 2y + z + 5t = 6

4x + 2y 3z + t = 4 x+ y z = 3 b) +t= 1 3x + 3y x 7y + 3z = 3

x 3y = 2 x + 2y = 3 c) Discuie dup i . (, parametrii reali) 3x y = 2x + y =

x + y + 2z = 1 d) x + 2y + z = 1 , R, parametrii. Discuie dup i . x+ y z= x + y + z 2t = 5 e) 2x + y + 2z + t = 1 2x 3y + z + 2t = 3 x + y + z = 1 f) x + y + z = 1 x + y + z = 1

R, parametru. Discuie dup .18

x 2y + z t = 0 2x y + 3z 3t = 0 g) R, parametru. Discuie dup . y+ z+ t = 0 x+ 2x + ( 1) y + 2z + t = 0 I.1.E.2. tiind c urmtorul sistem are soluie, aplicai lema Farca Mincowski pentru acest sistem:

6 u 1 + u 2 + u 4 5 x1 2x 2 x 3 2 1 2u 1 + u 2 + u 3 = 3 x1 3x 3 = 0 3 a) b) 0 2 3u 1 + u 5 x1 2x 2 x1 0, x 2 0, x 3 0 u 0, u arbitrar, u 0 1 2 3I.2. Algoritmul simplex primal

S considerm o problem de programare liniar sub forma standard:

inf c T x (I.2.1.) Ax = b x0

{ }

Se poate presupune c liniile matricei A sunt liniar independente, deoarece n caz contrar o parte din ecuaii se deduc din celelalte i n acest caz pot fi eliminate. Vom mai presupune c matricea A este de dimensiuni m n, atunci b Rm, iar rang A = m. Vom nota cu i liniile matricii A (i {1, 2, ..., m}) i cu aj coloanele (j {1, 2, ..., n}). Definiiile ce urmeaz au sens numai pentru o problem sub forma standard. Spunem c o soluie x a problemei (I.2.1.) este soluie de baz dac vectorii aj corespunztori componentelor nenule ale acestei soluii sunt liniari independeni. Deoarece rang A = m, nu pot exista mai mult de m vectori aj liniar independeni, deci o soluie de baz are cel mult m componente diferite de zero. Dac o soluie de baz are cel mult m componente19

nenule, atunci soluia respectiv se numete nedegerat. Dac ns o soluie de baz are mai puin de m elemente nenule, ea se numete soluie de baz degenerat. Fie B matricea format de coloanele aj ale unei soluii de baz nedegenerate. Matricea B este o matrice ptratic (de ordin m), nesingular. Vom numi baz orice matrice ptratic, nesingular de ordin m, extras din matricea A. Dac B este o baz, atunci

x= x , x

(

B

R

) , unde x

B

= B1b , x = 0 constituie o soluie de baz aB

R

problemei I.2.1. Baza B se numete admisibil dac soluia corespunztoare ei este soluie, a problemei I.2.1. deci x = B1 b 0 . Descrierea algoritmului simplex primal Pas 0: Se aduce problema la forma standard, adic la forma I.2.1. Se determin o baz admisibil B i se calculeaz mrimile

x = B1b ; yj = B-1aj i z B c j = cB B1a j c j , unde cB este coloana jdin funcia obiectiv corespunztoare elementelor din baz, precum i

B

(

)

z = cB x .Se alctuiete urmtorul tabel: V.B V.V.B. x1

B

B

x i1 x i2M x in

x2

...

xn

x z

B

B y1

yB 2 z B c2 2...

yB n zB cn n

B

B z1 c1

Pas 1: Criteriul de optim finit Dac B este primal admisibil i z B c j 0 pentru oricare j j {1, 2, ..., n} atunci B este optim i problema are soluie.

20

Pas 2: Criteriul de optim infinit Dac B este primal admisibil i exist k {1, 2, ..., n} astfel nct z B c k > 0 i y B 0 , atunci problema are optim infinit. k k Pas 3: Criteriul de intrare n baz Determinm k {1, 2, ..., n} astfel nct:

z B c k = max z B c j k jj{1, 2,K,n }

(

)

Variabila xk va intra n baz. Pas 4: Criteriul de ieire din baz Determinm r { i1, i2, ..., in} astfel nct:B xB i xr = min B y B i yB >0 y ik ik rk

Variabila xr va iei din baz. Pas 5: Calculul urmtorului tabel simplex. y B se numete privot. Noul tabel simplex se calculeaz dup rk urmtoarele reguli: - linia pivotului se transform prin mprire la pivot; - coloana pivotului, mai puin pivotul, devine zero; - noua valoare a unui element nesituat pe linia sau coloana pivotului se obine scznd din vechea valoare produsul elementelor de pe diagonala dreptunghiului format, mprite la pivot (regula dreptunghiului). Exerciiu rezolvat Rezolvai problema de programare liniar:

inf {2x x } 1 2 x1 x 2 4 3x 1 x 2 18 x + 2x 2 6 1 x1 , x 2 0 Rezolvare. Pas 0. Aducem problema la forma standard:21

inf {2x x } 1 2 x1 x 2 + x 3 = 4 3x 1 x 2 + x4 = 18 x + 2x 2 + x5 = 6 1 x1 , x 2 , x 3 , x 4 , x 5 0 Considerm matricea sistemului:

1 1 1 0 0 A = 3 1 0 1 0 1 2 0 0 1 4 Considerm matricea termenilor liberi: b = 18 i matricea 6funciei obiectiv c = (-2, -1, 0, 0, 0). Determinm rangul matricei A; rangul este 3, iar matricea care d rangul matricii A este:

1 0 0 B = 0 1 0 0 0 1Deci B = I3, iar B-1 = I3, Calculm x , y B , z B c j i z . j jB B

1 0 0 4 4 x = B b = 0 1 0 18 = 18 0 0 1 6 6 B 1

Cum x 0 , rezult c B este primal admisibil. Aadar, se poate aplica algoritmul simplex primal.22

B

1 B y 1 = B1a 1 = I 3a 1 = a 1 = 3 1 1 B 1 y 2 = B a 2 = I 3a 2 = a 2 = 1 2 1 y B = B1a 3 = I 3a 3 = a 3 = 0 3 0 0 B 1 y 4 = B a 4 = I 3a 4 = a 4 = 1 0 0 y B = B1a 5 = I 3a 5 = a 5 = 0 5 1 1 B B B z1 c1 = c y 1 c1 = ( 0,0,0) 3 ( 2) = 2 1 1 B z B c2 = cB y 2 c2 = ( 0,0,0) 1 ( 1) = 1 2 2 1 B B B z 3 c3 = c y 3 c3 = ( 0,0,0) 0 0 = 0 0

23

0 z B c 4 = cB y B c 4 = ( 0,0,0) 1 0 = 0 4 4 0 0 B B B z 5 c5 = c y 5 c5 = ( 0,0,0) 0 0 = 0 1 4 18 B B B z = c x = ( 0,0,0) = 0 6 Tabelul simplex asociat este:Tabelul nr. 1

V.B. x3 x4 x5

V.V.B. 4 18 6 0

x1 1 3 -1 2

x2 -1 -1 2 1

x3 1 0 0 0

x4 0 1 0 0

x5 0 0 1 0

Pas 1: Criteriul de optim finit Dac B este primal admisibil i z B c j 0 pentru oricare j j {1, 2, 3, 4, 5} atunci B este optim i problema are soluie. n cazul nostru acest criteriu nu se aplic. Pas 2: Criteriul de optim infinit Dac B este primal admisibil i exist k {1, 2, 3, 4, 5} astfel nct z B c k > 0 i y B 0 , atunci problema are optim infinit. k k n cazul nostru acest criteriu nu se aplic.

24

Pas 3: Criteriul de intrare n bazj{1, 2, 3, 4, 5}

max

(z

B j

B c j = max{2,1,0,0,0} = 2 = z1 c1

)

Variabila x1 va intra n baz. Pas 4: Criteriul de ieire din bazB x iB x3 4 18 min B = min , = 4 = B i y iB > 0 y y 31 1 3 1 i1

Variabila x3 iese din baz. Pas 5: Calculul urmtorului tabel simplex y B este pivot. (cel ncercuit n tabelul anterior) 31Tabelul nr. 2

V.B. x1 x4 x5

V.V.B. 4 6 10 -8

x1 1 0 0 0

x2 -1 2 1 3

x3 1 -3 1 -2

x4 0 1 0 0

x5 0 0 1 0

Pas 1: Criteriul de optim finit Dac B este primal admisibil i z B c j 0 pentru oricare j j {1, 2, 3, 4, 5}, atunci B este optim i problema are soluie. n cazul nostru acest criteriu nu se aplic. Pas 2: Criteriul de optim infinit Dac B este primal admisibil i exist k {1, 2, 3, 4, 5} astfel nct z B c k > 0 i y B 0 , atunci problema are optim infinit. k k n cazul nostru acest criteriu nu se aplic. Pas 3: Criteriul de intrare n bazj{1, 2, 3, 4 , 5}

max

(z

B j

c j = max{0,3,2,0,0} = 3 = z B c2 2

)

Variabila x2 va intra n baz. Pas 4: Criteriul de ieire din baz25

B x B 6 10 i x4 min B = , = 3 = B y 42 i yB >0 y i i2 2 2 1

Variabila x4 iese din baz. Pas 5: Calculul urmtorului tabel simplex y B este pivot. (cel ncercuit n tabelul anterior) 42Tabelul nr. 3

V.B. x1 x2 x5

V.V.B. 7 3 7 -17

x1 1 0 0 0

x2 0 1 0 0

x3 -1/2 -3/2 5/2 5/2

x4 1/2 1/2 -1/2 -3/2

x5 0 0 1 0

Pas 1: Criteriul de optim finit Dac B este primal admisibil i z B c j 0 pentru oricare j j {1, 2, 3, 4, 5}, atunci B este optim i problema are soluie. n cazul nostru acest criteriu nu se aplic. Pas 2: Criteriul de optim infinit Dac B este primal admisibil i exist k {1, 2, 3, 4, 5} astfel nct z B c k > 0 i y B 0 , atunci problema are optim infinit. k k n cazul nostru acest criteriu nu se aplic. Pas 3: Criteriul de intrare n baz

5 3 5 B max 0,0, , ,0 = = z 3 c3 j{1, 2, 3, 4 , 5} 2 2 2Variabila x3 va intra n baz. Pas 4: Criteriul de ieire din baz26

x B 7 14 x B i 4 min B = = = B B 5 5 y 53 i yi3 >0 y i 3 2Variabila x5 iese din baz. Pas 5: Calculul urmtorului tabel simplex y B este pivot. (elementul ncercuit din tabelul anterior) 53Tabelul nr. 4

V.B. x1 x2 x3

V.V.B.

42 5 36 5 14 5-24

x1 1 0 0 0

x2 0 1 0 0

x3 0 0 1 0

x4 2/5 1/2 -2/5 -1

x5 1/5 3/5 2/5 -1

Pas 1: Criteriul de optim finit Dac B este primal admisibil i z B c j 0 pentru oricare j j {1, 2, 3, 4, 5}, atunci B este optim i problema are soluie. n cazul nostru acest criteriu se aplic, iar valoarea minim a funciei obiectiv este z* = -24 i se obine pentru* x1 =

42 * 36 * 14 ,x = ,x = i x * = x * = 0 . 4 5 5 2 5 3 5

Observaii 1) Dac matricea A conine vectori unitari, atunci, cu ajutorul algoritmului simplex, se poate determina inversa unei baze.

27

1 1 0 De exemplu pentru B = 3 1 0 , format cu coloanele a1, a2 1 2 1i a5 ale matricii A, din tabelul 3 n care variabile de baz au fost x1, x2, x5 obinem

1 / 2 1 / 2 0 B1 = 3 / 2 1 / 2 0 5 / 2 1 / 2 1 2) Forma secundar a unei probleme de programare liniar relativ la o baz. Pentru baza B = {x1, x4, x5} forma secundar a problemei de programare liniar rezolvat anterior se obine din tabelul 2 i este:

inf {2x x } 1 2 x1 = 4 + x 2 x 3 x 4 = 6 2x 2 + 3x 3 x = 10 x 2 x 3 5 x1 , x 2 , x 3 , x 4 , x 5 0 Exerciii propuse spre rezolvare

inf {3x + 4x + x } 1 2 3 x1 + 2x 2 + 3x 3 10 1) x 1 x 2 5 x + 2x 3 6 1 x1 , x 2 , x 3 0

28

inf {107x x 2x } 4 5 6 14 1 1 7 x1 + x4 + x5 x6 = 3 3 3 3 1 2) x2 + 16x 4 + x 5 2x 6 = 5 2 x 3 + 3x 4 =0 x1 , x 2 , x 3 , x 4 , x 5 0 inf {x + 2x + 2x 3x } 1 2 3 4 x1 x 2 + x 3 + x 4 = 1 3) 3 x2 x3 x3 + x4 2 x1 , x 2 , x 3 , x 4 0 inf {x + 2x + 2x + x } 1 2 3 4 1 x x3 + x4 = 1 4) 1 2 x2 x3 x4 = 1 x1 , x 2 , x 3 , x 4 0I.3. Metoda celor dou faze n cele ce urmeaz vom prezenta o metod cunoscut sub numele de metoda celor dou faze sau metoda bazei artificiale care se ntrebuineaz atunci cnd este greu de gsit o baz primal admisibil pentru problema iniial. I.3.1. Descrierea metodei celor dou faze Pas 0: Se aduce problema la forma standard:

29

inf c T x (I.3.2) Ax = b x 0

{ }

unde A este o matrice cu m linii i n coloane, iar b 0 (n caz contrar se nmulesc cu -1 ecuaiile corespunztoare componentelor negative ale lui b). Pas 1. Asociem problemei (I.3.1) urmtoarea problem de programare liniar:

inf {x + x +L+x } n +1 n+2 n+ m a (I.3.3) Ax + x = b a x 0, x 0

unde xn+i, 1 i m, sunt numite variabile artificiale, iar xa este xa = (xn+1, xn+2, ..., xn+m)T. Faza 1. Se rezolv problema (I.3.2) folosind algoritmul simplex primal. Avem dou cazuri: (i) inf(xn+1 + xn+2 + ... + xn+m) > 0, atunci problema (I.3.1) nu are soluie; (ii) inf(xn+1 + xn+2 + ... + xn+m) = 0. n acest sens caz avem o baz optim pentru problema (I.3.2) care este baz iniial pentru problema (I.3.1). Putem avea dou situaii: ii1) Nu exist variabile atificiale n baza optim obinut. Atunci se trece la rezolvarea problemei (I.3.1) folosind baza obinut. ii2) Exist variabile atificiale n baz. Atunci avem: ) Variabilele atificiale din baz pot fi eliminate, lund pivot orice element nenul de pe linia corespunztoare acelei variabile atificiale din tabelul optim i ajunge la cazul II1). ) Nu pot fi eliminate din baz variabile atificiale. Atunci se suprim liniile din tabel corespunztoare acestor variabile atificiale i se obine un tabel care conduce la ii1).30

Observaie Faza I se ncheie cnd gsim o baz optim pentru problema (I.3.2) care nu conine variabile atificiale i pentru care inf(xn+1 + xn+2 + ... + xn+m) = 0. FAZA II. Rezolvm problema (I.3.1) cu baza primal admisibil gsit la FAZA I. Eexerciiul rezolvat Rezolvai problema de programare liniar

inf {2x + 3x } 1 2 x1 x 2 + x 3 = 1 x + x x = 1 2 4 (1) 1 x1 2x 2 = 1 2x + x x = 2 3 4 1 x1 , x 2 , x 3 , x 4 0

Rezolvare: Vom utiliza metoda celor dou faze. Vom introduce variabilele artificiale x5, x6, x7 i x8. (n general se introduc attea variabile artificiale cte ecuaii sunt). Obinem astfel problema:

inf {x + x + x + x } 5 6 7 8 x1 x 2 + x 3 + x 5 = 1 x + x x + x = 1 2 4 6 (2) 1 + x7 = 1 x1 2x 2 2x + x x + x = 2 3 4 8 1 x1 , x 2 , x 3 , x 4 , x 5 , x 6 , x 7 , x 8 0

pe care o vom rezolva folosind algoritmul simplex primal. Problema este scris deja sub forma standard, deci vom trece direct la pasul 1. Matricea sistemului este:31

1 1 1 1 A= 1 2 2 0

1 0 0 1 0 0 1 1

1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1

1 1 b = , iar matricea funciei obiectiv este c = (0, 0, 0, 0, 1, 1, 1, 1). 1 2Rangul matricii A este 4 i este dat de matricea

Matricea termenilor liberi este:

1 0 B= 0 0

0 1 0 0

0 0 1 0

0 0 0 1

Atunci: cB = (1, 1, 1, 1), x B = B1 b = I 1 b = b , y B = B 1a j = 4 j = I 4 1a j = a j , oricare j {1, 2, ..., 8}, z B = c T y B = c T a j , deci j B j B

B B z1 = 5 , z B = -2, z B =2, zB = -2, zB = 1, zB = 1, zB = 1, z 8 = 1 , iar 2 3 4 5 6 7

z B = c T x B = c T b = 5 . n acest caz tabelul simplex asociat problemei B Beste: V.B. x5 x6 x7 x8 V.V.B. 1 1 1 2 5 x1 1 1 1 2 5 x2 -1 1 -2 0 -2 x3 1 0 0 1 2 x4 0 -1 0 -1 -2 x5 1 0 0 0 0 x6 0 1 0 0 0 x7 0 0 1 0 0 x8 0 0 0 1 0

Pas 1: Criteriul de optim finit nu se verific. Pas 2: Criteriul de optim infinit nu se verific. Pas 3: Criteriul de intrare n baz32

max{5, -2, 2, -2, 0, 0, 0, 0} =5 Deci variabila x1 intr n baz. Pas 4: Criteriul de ieire din baz

1 1 1 2 min , , , = 1 1 1 1 2

Deci, de exemplu, variabila x8 iese din baz. Observaie: Deoarece pentru toate variabilele x5, x6, x7 i x8 se obine aceeai valoare de minim, orice variabil dintre cele menionate mai sus putea iei din baz. Pas 5: Alctuirea noului tabel simplex. V.B. x5 x6 x7 x1 V.V.B. 0 0 0 1 0 x1 0 0 0 1 0 x2 -1 1 -2 0 -2 x3 1/2 1/2 1/2 1/2 1/2 x4 1/2 1/2 1/2 1/2 1/2 x5 1 0 0 0 0 x6 0 1 0 0 0 x7 0 0 1 0 0 x8 -1/2 -1/2 -1/2 1/2 -5/2

Se observ c n acest tabel z B = 0, deci, conform FAZA I ii, {x5, x6, x7, x1} este baz optim pentru problema (2). ntotdeauna dup determinarea unei baze optime pentru problema (2) vom alctui un tabel n care variabilele artificiale precum i ultima linie a tabelului anterior nu mai apar. Obinem astfel urmtorul tabel: V.B. x5 x6 x7 x1 V.V.B. 0 0 0 1 x1 0 0 0 1 x2 -1 1 -2 0 x3 1/2 1/2 1/2 1/2 x4 1/2 1/2 1/2 1/233

n continuare va trebui ca din variabilele bazice ale acestui tabel, alegnd diveri pivoi, care pot fi eventual i negativi, s eliminm variabilele artificiale. Astfel, alegnd pivot pe -1 obinem urmtorul tabel: x4 1/2 x6 0 0 0 0 x7 0 0 0 1/2 x1 1 1 0 1/2 Se observ c pe linia variabilei artificiale x6 avem numai valoarea 0, astfel variabila x6 poate fi eliminat din tabel. Obinem astfel tabelul: V.B. x2 V.V.B. 0 x1 0 V.B. x2 x7 x1 V.V.B. 0 0 1 x1 0 0 1 x2 1 0 0 x3 1/2 3/2 1/2 x4 1/2 1/2 1/2 x2 1 x3 1/2 0 3/2 1/2

Alegnd pivot pe x3 i obinem tabelul: V.B. x2 x3 x1 V.V.B. 0 0 1

3 variabila x7 poate fi nlocuit cu variabila 2x1 0 0 1 x2 1 0 0 x3 0 1 0 x4 -1/3 1/3 -2/3

34

n acest moment printre variabilele bazice nu se mai afl nici o variabil artificial. Astfel prima faz a fost ncheiat i am obinut c { x2, x3, x1} este baz pentru problema (1). Trecere la FAZA II, adic la rezolvarea problemei (1) cu ajutorul algoritmului simplex primal. Tabelul asociat acestei probleme se obine din tabelul anterior la care se adaug o linie ce conine pe z B i z B c j , j {1, 2, 3, 4}, valori ce se vor calcula cu ajutorul j definiiei. Pentru problema (1) valoarea funciei obiectiv este c = (2, 3, 0, 0), iar cB = (3, 0, 2). Astfel:

0 T z B = cB x B = ( 3,0,2) 0 = 2 1 0 z c1 = c y c1 = ( 3,0,2) 0 2 = 0 1 1 T z B c2 = cB y B c2 = ( 3,0,2) 0 3 = 0 2 2 0 0 B T B z 3 c3 = cB y 3 c3 = ( 3,0,2) 1 0 = 0 0 1 / 3 7 T z B c4 = cB y B c4 = ( 3,0,2) 1 / 3 0 = 4 4 3 2 / 3B 1 T B B 1

Tabelul simplex asociat este: V.B. x2 V.V.B. 0 x1 0 x2 1 x3 0 x4 1/335

x3 x1

0 1 2

0 1 0

0 0 0

1 0 0

1/3 2/3 7/3

Continum algoritmul simplex pentru acest tabel. Pas 1: Criteriul de optim finit se aplic, deci z * = 2 este valoare optim a funciei obiectiv asociat problemei (1), obinut pentru soluia optim x = 0, x = 0, x = 1, x = 0. 2 3 1 4 I.3.4. Determinarea inversei unei baze folosind metoda celor dou faze Exerciiu rezolvat: Rezolvai urmtoarea problem de programare liniar specificnd la fiecare pas inversa bazei B:

inf {3x + 2x 4x } 1 2 3 x1 + 3x 2 + 2x 3 = 3 3x1 + 3x 2 + x 3 = 4 x , x , x 0 1 2 3

Rezolvare: Vom utiliza metoda celor dou faze. Vom introduce variabilele artificiale x4 i x5. Obinem astfel problema

inf {x + x } 4 5 x1 + 3x 2 + 2x 3 + x 4 = 3 3x1 + 3x 2 + x 3 + x 5 = 4 x 0, i = 1,5 i

pe care o vom rezolva folosind algoritmul simplex primal. Matricea sistemului este:

1 3 2 1 0 A= , 3 3 1 0 1

36

matricea termenilor liberi este b = , iar matricea funciei obiectiv

3 4

este c = (0, 0). Rangul matricii A este 2 i este dat de matricea

1 0 B= 0 1

Calculm cu ajutorul formulelor x B , z B i y B , z B c j pentru toi j j

j = 1,5 i obinem urmtorul tabel simplex:V.V.B. x1 x2 x3 x4 x5 3 1 3 2 1 0 4 3 3 1 0 1 7 4 6 3 0 0 Deoarece x4 i x5 sunt n variabilele bazei n acest tabel, inversa bazei format cu coloanele 4 i 5 ale matricii A este matricea format din coloanele x4 i x5 corespunztoare tabelului. Aadar inversa bazei V.B. x4 x5

1 0 1 0 1 B= este B = 0 1 0 1

Continum aplicarea algoritmului simplex primal pentru tabelul alctuit. Pas 1: Criteriul de optim finit nu se verific Pas 2: Criteriul de optim infinit nu se verific Pas 3: Criteriul de intrare n baz max{4, 6, 3, 0, 0} = 6 Deci variabila x2 intr n baz Pas 4: Criteriul de ieire din baz min , = 1 Deci variabila x4 iese din baz. Pas 5: Alctuirea noului tabel simplex: V.B. V.V.B. x1 x2 x3 x4 x537

3 4 3 3

x2 x5

1 1 1

1/3 2 2

1 0 0

2/3 -1 -1

1/3 -1 -1

0 1 0

Deoarece x2 i x5 sunt variabilele bazei n acest tabel, iar x4 i x5 au fost variabilele bazei iniiale, inversa bazei format cu coloanele 2 i 5 ale matricii A, este format din coloanele 4 i 5 corespunztoare tabelului. Aadar inversa bazei

3 0 1 3 0 B= este B1 = 3 1 1 1 Continum aplicarea algoritmului simplex primal pentru tabelul alctuit. Pas 1: Criteriul de optim finit nu se aplic Pas 2: Criteriul de optim infinit nu se aplic Pas 3: Criteriul de intrare n baz max{2, 0, -1, -1, 0} = 2 Deci variabila x1 intr n baz Pas 4: Criteriul de ieire din baz

1 1 1 min , = 1 2 2 3

Deci variabila x5 iese din baz. Pas 5: Alctuirea noului tabel simplex: V.B. x2 x1 V.V.B. 5/6 1/2 0 x1 0 1 0 x2 1 0 0 x3 5/6 -1/2 0 x4 1/2 -1/2 -1 x5 -1/6 1/2 -1

Deoarece x2 i x1 sunt variabilele bazei n acest tabel, iar x4 i x5 au fost variabilele bazei iniiale, inversa bazei format cu coloanele 238

i 1 ale matricii A, este format din coloanele 4 i 5 corespunztoare tabelului. Aadar inversa bazei

3 1 1 2 1 6 B= este B1 = 3 3 1 2 1 2 Observm c n ultimul tabel obinut, printre variabilele bazice nu se mai afl nici o variabil secundar. Astfel prima faz a fost ncheiat i am obinut c {x2, x1} este baz pentru problema iniial. Trecem la FAZA II, adic la rezolvarea problemei iniiale cu ajutorul algoritmului simplex primal. Tabelul asociat acestei probleme se obine din tabelul anterior la care se adaug o linie ce conine pe z B i z B c j , j {1, 2, 3}, valori ce se vor calcula cu ajutorul j definiiei. Pentru problema iniial valoarea funciei obiectiv este c = (-3, 2, -4), iar cB = (2, -3). Astfel:

5 6 1 T z B = cB x B = ( 2,3) = 1 6 6 0 B T B z1 c1 = cB y1 c1 = ( 2,3) ( 3) = 0 1 1 B T B z2 c2 = cB y 2 c2 = ( 2,3) 2 = 0 0 5 6 43 T zB c3 = cB y B c3 = ( 2,3) ( 4 ) = 3 3 6 1 2

Tabelul simplex asociat este: V.B. x2 x1 V.V.B. 5/6 1/2 1/6 x1 0 1 0 x2 1 0 0 x3 5/6 -1/2 43/6 B-1 1/2 -1/2 -1/6 1/2

Pas 1: Criteriul de optim finit nu se aplic39

Pas 2: Criteriul de optim infinit nu se aplic Pas 3: Criteriul de intrare n baz max 0,0,

43 43 = 6 6

Deci variabila x3 intr n baz Pas 4: Criteriul de ieire din baz

5 6 5 min = 1 3 2

Deci variabila x2 iese din baz. Pas 5: Calculul noului tabel simplex: V.B. x3 x1 V.V.B. 1 1 -7 x1 0 1 0 x2 6/5 3/5 -43/5 x3 1 0 0 B-1 3/5 1/5

1/5 2/5

Observaie: Partea de tabel corespunztoare lui B-1 se calculeaz dup aceleai reguli ca ntregul tabel. Deoarece x3 i x1 sunt variabile bazei n acest tabel, inversa bazei format cu coloanele 3 i 1 ale matricii A, este matricea B-1 din tabel. Aadar inversa matricii

2 1 3 5 1 5 B= este B1 = 1 3 1 2 2 5 Continum aplicarea algoritmului simplex. Pas 1: Criteriu de optim finit se aplic. Deci valoarea optim a problemei este z* = -7 obinut pentru x = 1, x = 0, x = 1 1 2 340

Eexerciii propuse spre rezolvare

1)

inf {x 1 + 2x 2 + x 4 + x 5 5x 6 } 6x + 2x + x x + x + 2x = 4 2 3 4 5 6 1 1 1 2 x 1 x 2 x 3 + x 4 + x 5 = 3 3 2 3x 1 x 2 + 2 x 3 + 4x 4 + 1 x 5 + x 6 = 2 2 x i 0, i = 1,6 min{5x x 2x } 1 2 3 x1 + x 2 + 2x 3 10 2x x + x 8 2 3 1 2x1 + x 2 4x 3 4 x x 6 x 6 2 3 1 x1 , x 2 , x 3 0

2)

3)

min{x 2x + x } 1 2 3 x1 + 2x 2 x 3 2 6x1 + 3x 2 + 2x 3 = 4 3x x 2 4x 3 = 10 1 x1 , x 2 , x 3 0

41

4)

min{2x + 3x + x x + x } 1 2 3 4 5 5x1 x 2 + x 3 x 4 + x 5 = 9 x1 x 2 + 3x 3 x 4 5 2x + x 2 4x 3 + 3x 4 = 0 1 x i 0, i = 1,5 I.4 Determinarea tuturor soluiilor optime

n problemele practice este util s tim dac exist un singur program optim sau dac sunt mai multe. n al doilea caz este n general interesant s cunoatem toate programele optime n scopul de a selecta dintre ele. S considerm problema de programare liniar n forma standard

inf ( c T x) (I.4.1) Ax = b x 0

unde A este o matrice cu m linii, n coloane i rangA = m < n. Fie P* = x R n Ax = b, x 0 mulimea soluiilor problemei (I.4.1) i fie

{

}

mulimea soluiilor optime ale problemei (I.4.1.), unde

P A = P I H( c, z *)

z* = inf { c T x x P}

iar H(c z*) este hiperplanul

H(c, z *) = x R n c T x = z *

{

}

n cele ce urmeaz vom presupune c P* . Sunt posibile urmtoarele dou situaii: a) Problema (I.4.1) are soluie optim unic, adic P* este constituit dintr-un singur element. Acesta este exact soluia optim determinat cu ajutorul algoritmului simplex.

42

b) Problema (I.4.1) nu are soluie optim unic. n acest caz P* este o mulime mrginit inferior, iar algoritmul simplex furnizeaz unul dintre elementele mulimii P*. Rezultatele care urmeaz ofer informaii suplimentare privind posibilitatea de obinere a lui P* cu ajutorul algoritmului simplex. I.4.2. Definiie. Fie B o baz primal admisibil pentru problema (I.4.1). B se numete nedegenerat dac x > 0 . B se numete degenerat dac exist i B astfel nct x i = 0 . I.4.3. Propoziie. Fie B o baz primal admisibil pentru problema (I.4.1.) cu proprietatea c z B c j 0 , oricare j R. O j condiie necesar i sufient ca x P s fie program optim este caB B

x j z B c j = 0 , oricare j R. jI.4.4. Propoziie. Fie B o baz primal admisibil pentru problema (I.4.1.). Condiia necesar i suficient ca soluia de baz nedegenerat x s fie unica soluie optim este ca: z B c j < 0 , oricare j R. j I.4.5. Exerciiu rezolvat. Determinai toate soluiile optime ale problemei de programare liniar:B

(

)

inf {7x + x + x } 1 3 4 2x 1 + x 2 + x 3 =0 + x4 = 3 3x 1 + x 2 x i 0, i = 1,4

Rezolvare. Vom rezolva problema folosind algoritmul simplex primal. Matricea A a sistemului este A =

2 1 1 0 , matricea 3 1 0 1

termenilor liberi este b = , iar matricea funciei obiectiv este c =

0 3

(7, 0, 1, 1). Rangul matricii A este 2 i este dat de matricea43

1 0 B= = I 2 . Folosind formulele din capitolul (I.2.) obinem 0 1urmtorul tabel simplex: V.B. x3 x4 V.V.B. 0 3 3 x1 2 3 -2 x2 -1 1 0 x3 1 0 0 x4 0 1 0

PAS 1. Criteriul de optim finit se verofic. Rezult c am obinut * soluia optim x1 = 0, x * = 0, x * = 0, x * = 3 , valoarea optim a 2 3 4 funciei obiectiv fiind z* = 3. Observm ns c exist j R pentru care avem z B c j = 0 . j ntr-adevr z2 - c2 = 0 i deci programul obinut nu este unicul program optim. Pentru a obine alt soluie optim introducem n baz pe x2, vectorul care prsete baza fiind ales dup criteriul obinuit:

3 min = 3 1

deci x4 iese din baz. Efectund transformarea tabelului simplex precedent cu pivotul y42 = 1 obinem un nou tabel simplex optim: V.B. x3 x2 Am V.V.B. 3 3 3 astfel x1 -1 3 -2 o x2 0 1 0 nou x3 1 0 0 soluie x4 1 1 0 optim de baz:

obinut

= 3. Avem acum z4 - c4 = 0 i deci x4 poate fi introdus n baz. Vectorul care prsete baza este ales dup criteriul obinuit:

* x1 = 0, x * = 3, x * = 4, x * = 0 , iar valoarea funciei obiectiv este z* 2 3 4

3 3 min , = 1. 1 1

44

Aadar i x3 i x2 pot iei din baz. ns dac x2 prsete baza obinem soluia optim precedent. Deci cel care va prsi baza este x3. Efectund transformarea tabelului simplex precedent cu pivotul y41 = 1 obinem un nou tabel simplex optim: V.B. x4 x2 V.V.B. 3 0 3 x1 -1 4 -2 x2 0 1 0 x3 1 -1 0 x4 1 0 0

Am obinut astfel soluia de baz * x1 = 0, x * = 0, x * = 0, x * = 3, iar valoarea funciei obiectiv 2 3 4 este z* = 3. Aceast soluie optim a mai fost ns obinut. Acum avem z B c 3 = 0 i deci x3 poate fi introdus n baz. 3 Vectorul care prsete baza este ales dup criteriul obinuit:

3 min = 3 1

Aadar x4 poate iei din baz. ns dac x4 prsete baza vom obine o soluie optim ce a mai fost obinut anterior. Aadar, am obinut dou soluii optime i anume:

0 0 0 3 * * x 1 = i x 1 = 0 3 3 0n ambele cazuri valoarea funciei obiectiv fiind z* = 3. Deci, mulimea tuturor soluiilor optime este:

45

0 0 3 0 P* = + ( 1 ) [ 0,1] 3 0 3 0 Exerciii propuse spre rezolvare Determinai mulimea tuturor soluiilor optime ale problemei:

inf {3x + x } 1 2 3x 1 + x 2 + x 3 = 6 3x 1 + x 2 + x 4 = 3 x i 0, i = 1,4 I. 5. Degenerare i ciclare S considerm problema de programare liniar n forma standard:

inf ( c T x) I.5.1. Ax = b x 0

unde rang (A) = m < n. Prin trecerea de la o baz al alta n cursul aplicrii algoritmului simplex, valoarea funciei obiectiv se poate micora sau poate rmne aceeai. Dac valoarea funciei obiectiv scade strict la fiecare iteraie, atunci nici o baz nu se poate repeta, deoarece fiecrei baze i corespunde un program cu o anumit valoare a funciei obiectiv. n acest caz rezult c, ntr-un numr finit de iteraii (numrul bazelor fiind finit), se ajunge la un program optim sau se pune n eviden faptul c problema are optim finit. Spunem n acest caz c algoritmul simplex este convergent ntr-un numr finit de pai.46

Dac valoarea funciei obiectiv nu se modific n cursul ctorva iteraii succesive, e posibil s revenim la una din bazele deja utilizate i atunci aplicarea n continuare a algoritmului simplex se continu indefinit, fr a se ajunge la o soluie. n acest caz spunem c algoritmul simplex cicleaz. Pentru a evita ciclarea procedm astfel: Determinm mai nti mulimeaB B + = i B y ik > 0

{

}

Dac mulimea B+ este nevid, trecem la determinarea mulimiiB B B B B 0 = i B + min x i / y ik = x i y ik iB +

(

)

Dac B0 este format dintr-un singur element, acesta este indicele cutat r. n caz contrar definimB B B1 = i B 0 min y iB / y ik = y iB y ik 1 1 iB0

(

)

Din nou, dac B1 este format dintr-un singur element, acesta este indicele cutat r. n caz contrar se merge mai departe, constituind succesiv mulimile B2, B3, ... date de relaiaB B B B B t = i B t 1 min y it / y ik = y it y ik iB t 1

(

)

pentru 1 t m, pn se obine o mulime format dintr-un singur element, care este indicele cutat r. n concluzie, pentru evitarea ciclrii, rezult urmtoarea regul practic: a) se determin o baz primal admisibil iniial B0 pentru problema I.5.1 format cu primele m coloane ale matricii A, eventual reindexnd variabilele. b) se determin mulimile B0, B1, B2, ... pn se obine o mulime format dintr-un singur element r Bt care este indicele coloanei ar ce prsete baza. I.5.2. Exerciiu rezolvat. Determinai toate soluiile optime ale problemei de programare liniar:47

3 1 inf x 4 + 20x 5 x 6 + 6x 7 2 4 1 x + x 8x x + 9x = 0 5 6 7 1 4 4 x 2 + 1 x 4 12x 5 1 x 6 + 3x 7 = 0 4 2 x3 + x6 = 1 x i 0, i = 1,7 Rezolvare Matricea asociat sistemului este

1 9 1 0 0 1/ 4 8 A = 0 1 0 1 / 4 12 1 / 2 3 0 0 1 0 0 1 1 matricea termenilor liberi este b = (o, o, 1), iar matricea funciei

6 . 1 matricei A este 3 i este dat de matricea B = 0 0obiectiv este c = 0, 0, 0,

3 1 , 20, , 4 2

Se observ c rangul

0 0 1 0 = I 3. Folosind 0 1x6 -1 -1/2 1 1/2 x7 9 3 0 6

formulele din capitolul I.2 obinem urmtorul tabel simplex: V.B. x1 x2 x3 V.V.B. 0 0 1 0 x1 1 0 0 0 x2 0 1 0 0 x3 0 0 1 0 x4 1/4 1/2 0 3/4 x5 -8 -12 0 -20

Observm c criteriile de optim finit i infinit nu se aplic, x4 intr n baz, iar x1 iese din baz. Urmtorul tabel simplex este: V.B48

V.V.B.

x1

x2

x3

x4

x5

x6

x7

. x4 x2 x3

0 0 1 0

4 -2 0 -3

0 1 0 0

0 0 1 0

1 0 0 0

-32 4 0 4

-4 3/2 1 7/2

36 -15 0 -33

Observm c criteriile de optim finit i infinit nu se aplic, x5 intr n baz, iar x2 iese din baz. Urmtorul tabel simplex este: V.B . x4 x5 x3 V.V.B. x1 x2 x3 x4 x5 x6 x7

0 -12 8 0 1 0 -84 8 0 -1/2 1/4 0 0 1 3/8 -15/4 1 0 0 1 0 0 1 0 0 -1 -1 0 0 0 2 -18 Observm c criteriile de optim finit i infinit nu se aplic, x6 intr n baz, iar x4 iese din baz. Urmtorul tabel simplex este: V.B. x6 x5 x3 V.V.B. 0 0 1 0 x1 -3/2 1/16 3/2 2 x2 1 -1/8 -1 -3 x3 0 0 1 0 x4 1/8 -3/64 -1/8 -1/4 x5 0 1 0 0 x6 1 0 0 0 x7 21/2 3/16 21/2 3

Observm c criteriile de optim finit i infinit nu se aplic, x7 intr n baz, iar x5 iese din baz. Urmtorul tabel simplex este: V.B. x6 x7 x3 V.V.B. 0 0 1 0 x1 2 1/3 -2 1 x2 -6 -2/3 6 -1 x3 0 0 1 0 x4 -5/2 -1/4 5/2 1/2 x5 56 16/3 -56 -16 x6 1 0 0 0 x7 0 1 0 0

Observm c criteriile de optim finit i infinit nu se aplic, x1 intr n baz, iar x6 iese din baz. Urmtorul tabel simplex este:49

V.B. x1 x7 x3

V.V.B. 0 0 1 0

x1 1 0 0 0

x2 -3 1/3 0 2

x3 0 0 1 0

x4 -5/4 1/6 0 7/4

x5 28 -4 0 -44

x6 1/2 -1/6 1 -1/2

x7 0 1 0 0

Observm c criteriile de optim finit i infinit nu se aplic, x2 intr n baz, iar x7 iese din baz. Urmtorul tabel simplex este: V.V.B. x1 x2 x3 x4 x5 x6 x7 0 1 0 0 1/4 -8 -1 9 0 0 1 0 1/2 -12 -12 3 1 0 0 1 0 0 1 0 0 0 0 0 3/4 -20 1/2 -6 Observm c dup ase iteraii simplex am revenit la baza iniial. Cu alte cuvinte, algoritmul simplex cicleaz pentru problema considerat. Pentru evitarea ciclrii vom aplica urmtorul algoritm. Evident x4 este coloana care urmeaz s intre n baz. Pentru a determina indicele coloanei care urmeaz s prseasc baza vom determina mai nti mulimeaB B + = i B y ik > 0

V.B. x1 x2 x3

{

}

baz,

n cazul nostru deoarece x4 este coloana care urmeaz s ias din

B + = i B y iB4 > 0

{

}

Deci B+ = {1, 2} Cum B , vom determina mulimea

x iB xr B 0 = r B + B = min B B y ik > 0 y y rk ik 0 0 n cazul nostru min , = 0 . Rezult B0 = {1, 2}. 1 1 4 250

Deoarece B0 nu este constituit dintr-un singur element, vom determina mulimea:

yB yB i i r B0 min B1 = B1 B1 = iB0 y y ik ik 1 0 n cazul nostru min , = 0 . Rezult B1 ={2}. Cum B1 este 1 1 4 21 obinem noul tabel simplex: 2V.V.B. 0 0 1 0 x1 1 0 0 0 x2 -1/2 2 0 -3/2 x3 0 0 1 0

constituit dintr-un singur element, rezult c indicele cutat este r = 2. Aadar, x2 iese din baz. Efectund transformarea cu pivotul

y 24 =V.B. x1 x4 x3

x4 0 1 0 0

x5 -2 -24 0 -2

x6 -3/4 -1 1 5/4

x7 15/2 6 0 -21/2

Observm c criteriile de optim finit i infinit nu se aplic, x6 intr n baz, iar x3 iese din baz. Urmtorul tabel simplex este: V.B. x1 x4 x6 V.V.B. 3/4 1 1 -5/4 x1 1 0 0 0 x2 -1/2 2 0 -3/2 x3 3/4 1 1 -5/4 x4 0 1 0 0 x5 -2 -24 0 -2 x6 0 0 1 0 x7 15/2 6 0 -21/2

3 , x = 0, x = 0, x = 1, x = 0, x = 1, x = 0, 3 4 5 6 7 4 2 5 iar valoarea funciei obiectiv este z = . 4 x1 =

Observm c se poate aplica criteriul de optim finit, iar soluia optim a problemei este:

51

Exerciii propuse spre rezolvare Rezolvai urmtoarele probleme de programe liniar:

inf { 2 x 1 x 2 + x 3 + x 4 } x 1 x 2 + 2x 3 x 4 + x 5 = 2 2) 2x + x 3x + x 6 1 2 3 4 x 1 + x 2 + x 3 + x 4 7 x i 0, i = 1,5 I.6. Algoritmul simplex revizuit Algoritmul simplex revizuit funcioneaz dup acelai principiu ca i algoritmul simplex, ns pentru fiecare baz utilizat B nu trebuie s cunoatem dect numerele z B c j , j R, i vectorii x i y B , unde j k k R este indicele determinat cu ajutorul criteriului de intrare n baz. Considerm problema de prograre liniar:B

inf {x + 2x + 2x 3x } 1 2 3 4 x1 x 2 + x 3 + x 4 = 1 1) x 2 x 3 3 x + x 4 2 3 x i 0, i = 1,4

inf { c T x} Ax = b x 0

unde A este matricea sistemului, b este coloana termenilor liberi, iar c este matricea funciei obiectiv. Construim matricea

52

T ~ 1 c A= 0 A

Fie B matricea care d rangul matricii A. Construim matriceaT ) 1 cB B= 0 B

Alctuim tabelul simplex)revizuit ) V.B. B1 B1 b T B x0 1 cB B1 z 0 B xB B-1 M x 0 Exerciiu rezolvat. Considerm problema de programare liniar:

inf {2x x 3x } 1 2 3 2x 1 + 3x 2 + x4 = 1 =3 x1 x 2 + x 3 x i 0, i = 1,4

Rezolvai problema cu ajutorul algoritmului simplex revizuit. Rezolvare. Matricea asociat sistemului este

2 3 0 1 A= 1 2 1 0

matricea termenilor liberi este b = , iar matricea funciei obiectiv

1 3

este c = (2, -1, -3, 0). Rangul matricii A este doi, iar matricea care d rangul matricii A este

1 0 B= = I 2 . Observm c 0 1 1 B B T B T T T x = B1b = b, z = cB x = ( 0,3) = 9 , iar cB B1 = cB I 2 = cB . 353

Astfel obinem matricile:

1 2 1 3 0 1 0 3 $ ~ A = 0 2 3 0 1 i B = 0 1 0 0 1 1 1 0 0 0 1Tabelul simplex revizuit asociat este: V.B. x0 x4 x3

) B11 0 0 0 1 0 3 0 1

) B1 b9 1 3

Pas 1: Criteriul de optim finit. Pentru a putea aplica criteriul de optim finit trebuie s calculm mai nti z B c j , pentru oricare j R. j n general,

coloana z c j = ( prima linie din tabel) j $ din A B j

2 B Astfel: z1 c1 = ( 1 0 3) 2 = 1 1 1 z B c2 = ( 1 0 3) 3 = 2 2 1Observm c nu se poate aplica criteriul de optim finit. Pas 2: Criteriul de intrare n baz54

max z B c j = max{1,2} = 1 jjR

{

}

Rezult c x1 intr n baz.

B $ 1a 1 = z1 c1 Pas 3: Calculm B B y1 1 0 3 2 1 $ B1a 1 = 0 1 0 2 = 2 0 0 0 1 1Tabelul simplex revizuit asociat este: V.B. x0 x4 x3 1 0 0 0 1 0

) B13 0 1

) B1 b9 1 3

) B1 a1

1 2 1

Pas 4: Criteriul de optim infinit.

B B Observm c z1 c1 = 1, iar y 1 = , aadar criteriul de

2 1

optim infinit nu se aplic. Pas 5: Criteriul de ieire din baz.

1 3 1 min , = 2 1 2Rezult c x4 iese din baz Pas 6: Tabelul simplex revizuit asociat: V.B. x0 x1

) B11 0 -1/2 1 3 0

) B1 b17/2 155

x3

0

-1/2

1

5/2

Pas 1: Criteriul de optim finit. Pentru a putea aplica criteriul de optim finit trebuie s calculm mai nti z B c j , pentru oricare j R. j

1 7 1 3 3 = z B c2 = 1 2 2 2 1 0 1 1 B 3 1 = z 4 c 4 = 1 2 2 0Observm c criteriul de optim finit se aplic. Aadar o soluie optim a sistemului este:

1 5 * x 1 = , x * = 0, x * = , x * = 0 , iar valoarea optim a funciei 2 3 2 2 4 17 obiectiv este z* = . 2Exerciii propuse spre rezolvare Rezolvai urmtoarele probleme de programare liniar folosind algoritmul simplex revizuit.

inf {x + 2x + 3x x } 1 2 3 4 x 1 + 2x 2 + 3x 3 = 15 1) 2x 1 + x 2 + 5x 3 = 20 x + 2x 2 + x 3 + x 4 = 10 1 x i 0, i = 1,4

56

inf {2x + x } 1 2 3x 1 + x 2 3 2) 4x 1 + 3x 2 6 x + 2x 2 2 1 x i 0, i = 1,2

57

I.7. Algoritmul simplex dual S considerm o problem de programare liniar n forma general:T T inf c1 x 1 + c T x 2 + c 3 x 3 2 A 11 x 1 + A 12 x 2 + A 13 x 3 b1 (I.7.1) A 21 x 1 + A 22 x 2 + A 23 x 3 = b 2 A 31 x 1 + A 32 x 2 + A 33 x 3 b1 x 1 0, x 2 arbitrar, x 3 0

{

}

Numim problem dual asociat problemei (I.7.1) urmtoarea problem de programare liniar:T T inf b1 u 1 + b T u 2 + b 3 u 3 2 A T u + A T u + A T u c 21 2 31 3 1 11 1 T T (I.7.2) A 12 u 1 + A T u 2 + A 32 x 3 b 2 22 T T A 13 u 1 + A T u 2 + A 33 u 3 c 3 23 u 1 0, u 2 arbitrar, u 3 0

{

}

Problema (I.7.1) se va numi problema primal. Este uor de vzut c duala problemei duale este chiar problema primal. Din acest motiv vom spune c problemele (I.7.1) i (I.7.2) formeaz un cuplu de probleme duale. Problema dual se obine din problema primal astfel: - termenii liberi din problema primal devin coeficieni ai funciei obiectiv n dual; - coeficienii funciei obiectiv din primal devin termeni liberi n dual; - o problem de minimizare se transform prin dualitate ntr-o problem de maximizare (i reciproc);57

- coeficienii variabilelor din problema dual se obin transpunnd matricea coeficienilor din problema primal; - variabilele duale corespunztoare unor restricii primale concordante sunt pozitive, iar cele corespunztoare unor restricii neconcordante sunt negative; - variabilele corespunztoare unor restricii egaliti pot fi att pozitive ct i negative; - n problema dual unor variabile primale pozitive le corespund inegaliti concordante, iar unor variabile negative le corespund inegaliti neconcordante; - unor variabile primale fr restricii de semn le corespund n problema dual restricii sub form de egaliti. I.7.3. Exerciiu rezolvat. S se scrie duala urmtoarei probleme de programale liniar:

inf {3x 6x + x } 1 3 4 2x 1 + 5x 2 x 3 + 2x 4 3 x 1 + 2x 2 + x 3 = 5 2x x 2 + x 4 2 1 x1 , x 2 0, x 3arbitrar, x 4 0

Rezolvare: Problema dual este:

inf {3u 1 + 5u 2 2u 3 } 2 u 1 u 2 + 2 u 3 3 5u 1 + 2u 2 u 3 0 u 1 + u 2 = 6 2 u 1 + u 3 1 u 1 0, u 2 arbitrar, u 3 0 58

Exerciii propuse spre rezolvare S se scrie dualele urmtoarelor probleme de programare liniar:

inf {2x + 2x + 4x } 1 2 3 2x 1 + 3x 2 + 5x 3 2 1) 3x 1 + x 2 + 7x 3 3 x + 4x 2 + 6x 3 5 1 x i 0, i = 1,2,3 sup{6x + 4x + x + 7x + 5x } 1 2 3 4 5 3x 1 + 7x 2 + 8x 3 + 5x 4 + x 5 = 2 2) 2x 1 + x 2 + 3x 3 + 2x 4 + 9x 5 = 6 x 0, i = 1,5 i

sup{x + 2x + 6x + x x } 1 2 3 4 5 2x + 3x 2 + 4x 3 + 7x 4 = 21 3) 1 3x1 + 17x 2 + 8x 3 + 2x 4 48 x , x , x 0, x , x oarecare 1 2 5 3 4

I.7.4. Enunul algoritmului simplex dual Considerm problema de programare liniar

inf { cT x} (I.7.5) Ax = b , A Mm,n(R), c Rn, b Rm. x 0

Definiie. B se numete baz dual admisibil pentru problema (I.7.5) dac z B c j 0 , pentru oricare j {1, 2, ...,n}. j59

Descrierea algoritmului simplex dual Pas 0: Se aduce problema la forma standard (vezi I.2.1) i se determin o baz iniial dual admisibil. Se calculeaz z B c j , x B , y B . j j Pas 1: Criteriul de optim finit Dac x iB 0 pentru toi i B, baza actual este optim, iar x B este soluia optim. Pas 2: Criteriul de inexisten a soluiei Dac exist r B astfel nct x rB < 0 i y B 0 pentru oricare rj j {1, 2, ...,n} atunci problema nu are soluii. Pas 3: Criteriul de ieire din baz Notm B = i B xiB < o

x r = min{ xiB

{

B i

} . Variabila x prsete baza.r

}

Pas 4: Criteriul de intrare n baz Fie k R astfel nct

zB c j z B ck j k = min B B B y rk y rj j y rj < 0

variabila xk intr n baz. Pas 5: Se calculeaz noul tabel simplex asociat. Exerciiu rezolvat. Considerm problema de programare liniar:

inf {x + x + x } 1 2 3 1 x 1 + x 2 x 3 2 2 x x + x 1 3 1 2 x1 , x 2 , x 3 0

S se rezolve problema cu ajutorul algoritmului simplex dual: Rezolvare: Pas 0. Aducem problema la forma standard60

inf {x + x + x } 1 2 3 x 1 + x 2 1 x 3 + x 4 = 2 2 x x + x + x = 1 2 3 5 1 x i 0, i = 1,5 1 1 1 / 2 1 0 A= 1 0 1 1 1 2 matricea termenilor liberi este b = , iar matricea asociat funciei 1 1 0 B B B B B= . Calculm cu ajutorul formulelor x , z i y j , z j c j 0 1 pentru toi j = 1,5 i obinem urmtorul tabel simplex:V.B. x4 x5 V.V.B. -2 1 0 x1 -1 -1 -1 x2 1 -1 -1 x3 -1/2 1 -1 x4 1 0 0 x5 0 1 0 obiectiv este c=(1, 1, 1, o, o). Matricea care d rangul matricii A este Matricea asociat acestei probleme este

B Pas 1: Criteriul de optim finit nu se aplic (deoarece x 4 < 0 ). Pas 2: Criteriul de inexisten a soluiei nu se aplic. Pas 3: Criteriul de ieire din baz

min{ x iB } = min{2} = 2iB

Deci x4 iese din baz. Pas 4: Criteriul de intrare n baz

61

zB cj 1 1 j =1 min B = min , B y4j i y 4 j< 0 1 1 2Deci x1 intr n baz. Pas 5: Calculul noului tabel simplex V.B. x1 x5 V.V.B. 2 3 2 x1 1 0 0 x2 -1 -2 -2 x3 1/2 3/2 -1/2 x4 -1 -1 -1 x5 0 1 0

Pas 1: Criteriul de optim finit se aplic Aadar, am obinut soluia z* = 2 pentru x = 2, x = x = x = 0, x = 3 1 2 3 4 5 Exerciii propuse spre rezolvare S se rezolve cu ajutorul problemei duale urmtoarele probleme de programare liniar:

inf {3x + 6x + x } 1 2 3 x1 2x 2 + x 3 7 x + x 10 2 1 x 2 + 4 x 3 5 1) x1 x 2 + x 3 1 x + 2x 2 3 2 x1 + x 3 4 x i 0, i = 1,2,3

62

inf {x + x + x } 3 4 5 x 1 x 3 + x 4 1 x 5 = 2 2) 2 x x x + x = 1 3 4 5 2 x i 0, i = 1,5

inf { x 3x 2x } 1 2 3 2x1 + x 2 4 x + 2x 5 2 3) 1 7x1 + 8x 2 3x 3 20 5x + 4x + 3x 28 2 3 1 x1 , x 2 , x 3 0 I.7.6. Determinarea unei soluii optime pentru problema dual n cazul n care matricea asociat problemei conine vectori unitari i cunoatem o soluie de baz optim pentru problema primal i tabelul simplex asociat Considerm problema de programare liniar n forma general:

inf { c T x} (I.7.7) Ax = b , A Mmn(R), b Rm, c Rn, m n x 0

Fie A = (a1, a2, ..., an). Presupunem c matricea B care d rangul matricii A este B = (l1, l2, ..., lm), unde l1, l2, ..., lm Rm sunt vectori i i i unitari i a 1 = l1 , a 2 = l 2 ,K, a m = l m . Atunci soluia problemei duale asociate problemei (I.7.7) este:

u = z B c1 + c1 ,K, z Bm cm + c m i1 i

(

)

63

Exerciiu rezolvat. Considerm problema de programare liniar:

inf {2x 3x + x } 1 2 3 x 2 + x 3 = 2 x1 + 3x 2 = 5 x , x , x 0 1 2 3

0 1 1 2 A= , matricea termenilor liberi este b = , iar matricea 1 3 0 5finciei obiectiv este c = (2, -3, 1). Matricea care d rangul matricii A este B =

Rezolvare:

Matricea

asociat

acestei

probleme

este

1 0 B B B . Calculnd cu ajutorul formulelor x , z i y j , 0 1

z B c j pentru toi j {1, 2, 3} obinem urmtorul tabel simplex: jV.B. x3 x1 V.V.B. 2 5 12 x1 0 1 0 x2 1 3 10 x3 1 0 0

Vom rezolva aceast problem cu ajutorul algoritmului simplex primal. Pas 1: Criteriul de optim finit nu se aplic. Pas 2: Criteriul de optim infinit nu se aplic. Pas 3: Criteriul de intrare n baz max{10} = 10 Deci x2 intr n baz. Pas 4: Criteriul de ieire din baz

2 5 5 min , = 1 3 3Deci x1 iese din baz. Pas 5: Calculul noului tabel simplex asociat:64

V.B. x3 x2

V.V.B. 1/3 5/3 -14/3

x1 -1/3 -1/3 -10/3

x2 0 1 0

x3 1 0 0

Pas 1: Criterul de optim finit se aplic. Aadar soluie a problemei considerate este z =

1 x = . 3 3

5 14 obinut pentru x = 0, x = , 1 2 3 3

Problema dual asociat problemei considerate este:

sup{2u + 5u } 1 2 u2 2 u1 + 3u 2 3 u 1 1 u1 , u 2 arbitrare

O soluie a acestei probleme se poate obine din rezolvarea problemei primale, astfel:

z = 1

14 3

(u ,u ) = (z 2

B 3

10 B c 3 + c 3 , z1 c1 + c1 ) = 0 + 1, + 2 = 3

4 = 1, 3Aadar, pentru aceast problem soluia este z = pentru u = 1 i u = . 1 265

4 3

14 obinut 3

I.8. Reoptimizare Se consider o problem de programare liniar

inf { c T x} A 0 x = b 0 x 0

pentru care am determinat o soluie optim. Fie B baza optim, x B soluia optim i B = i a i B

{

}

I.8.1. Modificarea vectorului b S reoptimizm voluia pentru cazul A0x = b, cu b = b0 + b1, b1 Rm. Prin aceast modificare B rmne dual admisibil. n ultimul tabel simplex apare B-1. Dac

~B = B1b = B1 ( b + b ) = x B + B1b 0 x 0 1 1 ~B este soluia optim. n caz contrar o putem reoptimiza atunci x inf {3x + 2x 4x } 1 2 3 x1 + 3x 2 + 2x 3 = 3 3x 1 + 3x 2 + x 3 = 4 x , x , x 0 1 2 3

aplicnd algoritmul simplex dual. ) Exerciiu rezolvat. S se rezolve problema de programare liniar

i s se reoptimizeze soluia pentru b = (1,4)T. Rezolvare. Aplicnd metoda celor dou faze obinem soluia optim a problemei iniiale (vezi I.3.4). Ultimul tabel simplex este:Tabelul 1

V.B. x366

V.V.B. 1

x1 0

x2 6/5

x3 1

B-1 3/5 -1/5

x1

1 -7

1 0

3/5 -43/5

0 0

-1/5

2/5

Am obinut deci B = {3,1}, B = (a3,a1), B1 = modifica doar coloana V.V.B. dup cum urmeaz:

35

1 5 1 5 2 5

x B = (1, 0, 1) i z B = -7. Vom construi un nou tabel n care se va~B = B1~ = 3 5 1 5 1 = 1 5 x b 1 5 2 5 4 7 5 ~B = c T ~B = ( 4,3) 1 5 = 17 z Bx 5 7 5Aadar noul tabel este: V.B. x3 x1 V.V.B. -1/5 7/5 -17/5 x1 0 1 0 x2 6/5 3/5 -43/5 x3 1 0 0

n continuare problema se va rezolva cu ajutorul algoritmului simplex dual.

6 1 x3 Cum ~B = < 0 i y 3 = 0, ,1 0 , se poate aplica criteriul 5 5

de existen a soluiilor (Pas 2), deci problema considerat nu are soluii. I.8.2. Modificarea funciei obiectiv c S reoptimizm soluia pentru funcia obiectiv min{cTx} cu c = c0 + c1, c1 Rm. Prin aceast modificare B rmne primal admisibil, dar poate s nu mai fie dual admisibil.67

Dac B rmne dual admisibil (adic z jB c j ( ) 0 ) atunci

x B rmne optim.n caz contrar reoptimizm soluia aplicnd algoritmul simplex primal. ) Exerciiu rezolvat. S se rezolve problema de programare liniar de la exerciiul ) i s se reoptimizeze soluia pentru c = (-1, -1, 1)T. Rezolvare. Pornind de la tabelul 1 se va construi un nou tabel n care se va modifica doar ultima linie, dup cum urmeaz:

~ B = c T x B = ( 1,1)1 = 0 z B 1

~ B c = c T y B c = ( 1,1) 0 ( 1) = 1 + 1 = 0 z1 1 1 B 1 1 ~ B c = c T y B c = ( 1,1) 6 5 ( 1) = 8 z2 2 2 B 2 5 3 5 ~ B c = c T y B c = ( 1,1) 1 1 = 0 z3 3 B 3 3 0Aadar, noul tabel este: V.B. x3 x1 V.V.B. 1 1 0 x1 0 1 0 x2 6/5 3/5 8/5 x3 1 0 0

n continuare problema se va rezolva cu ajutorul algoritmului simplex primal. I.8.3. Modificarea unui vector ar, r B S se reoptimizeze soluia pentru cazul Ax = b0, cu r r a = a 0 + a 1 , r B. Prin aceast modificare B rmne primal admisibil. Evalumr

68

putem reoptimiza aplicnd algoritmul simplex primal. ) Exerciiu rezolvat. S se rezolve problema de programare liniar de la exerciiul ) i s se reoptimizeze soluia pentru a2= (-3, -3)T. Rezolvare. Pornind de la tabelul 1 se va construi un nou tabel n care se va modifica toat coloana corespunztoare variabilei x2, dup cum urmaz:

~ B c = c T B 1a r c = z B c + c T B 1a r zr r B r r r B 1 ~ B c ( ) 0, x B rmne soluia optim. n caz contrar o Dac z r r

3 5 1 5 3 6 5 y B = B 1 a 2 = = 2 1 5 2 5 3 3 5

6 5 23 T z B c2 = cB y B c2 = ( 4,3) 2 = 2 2 5 3 5 Aadar noul tabel este: V.B. x3 x1 V.V.B. 1 1 -7 x1 0 1 0 x2 -6/5 -3/5 23/5 x3 1 0 0

n continuare problema se va rezolva cu ajutorul algoritmului simplex primal. Cum z B c2 = 2

6 5 23 > 0 , iar y B = < 0 , se poate aplica 2 5 3 5

criteriul de optim infinit i deci problema n acest caz are optim infinit. I.8.4. Modificarea unui vector ar, cu r Br r Se reoptimizeaz soluia pentru cazul Ax = b0 cu a r = a 0 + a 1 , r B. Prin aceast transformare pot fi afectate att primal ct i dual admisibilitatea. Fie B* noua baz. Fie i linia i baz din B-1.

69

r B*este nesingular dac r a 1 1. Dac B* este singular atunci B nu poate fi folosit pentru reoptimizarea soluiei i problema se rezolv independent (se reiau r calculele de la o iteraie anterioar intrrii n baz a lui a 0 ). Dac B* este nesingular, se calculeaz (B*)-1. (B*)-1= Ir(ar)B-1, cu Ir(ar) = (e1, ..., er-1, r, er+1, ...,em)

iar r =

1r rr

,L,1

1 ,L, mr . rr rr b0

Se calculeaz

x B = B

( )

z B c 0 j = c T B j B

( )

1

j a 0 c 0 j , j B.

Dac x B 0, z jB c0 j ( 0) , B* este optim. Dac B* este primal admisibil, dar nu i dual, atunci x B se reoptimizeaz aplicnd simplexul primal. Dac B* este dual admisibil, dar nu i primal, atunci x B se reoptimizeaz aplicnd simplexul dual. Dac B* nu este nici primal nici dual admisibil, fie se rezolv problema relund-o de la o iteraie anterioar intrrii lui a 0 n baz, fie r se aduce problema la una n care modificarea este introducerea unei noi coloane n matricea A. ) Exerciiul rezolvat. S se rezolve problema de programare liniar de la exerciiul ) i s se reoptimizeze soluia pentru a1= (-1, 1)T.

~ 2 1 . Se 1 1 1 3 1 3 ~ ~ observ c B este matrice ireversibil cu B1 = . ntregul 1 3 2 3Rezolvare. n acest caz matricea B devine B = tabel se recalculeaz astfel:

70

~B = B1b = 1 3 1 3 3 = 7 3 x 1 3 2 3 4 5 3 1 3 1 3 1 0 ~ B y 1 = B1a 1 = = 1 3 2 3 1 1 1 3 1 3 3 2 ~ y B = B1a 2 = = 2 1 3 2 3 3 1 1 3 1 3 2 1 ~ y B = B1a 3 = = 3 1 3 2 3 1 0 0 B T B z1 c1 = cB y 1 c1 = ( 4,3) ( 3) = 0 1 2 T z B c2 = cB y B c2 = ( 4,3) 2 = 13 2 2 1 1 T z B c3 = cB y B c3 = ( 4,3) ( 4) = 0 3 3 0 7 3 43 T z B = cB x B = ( 4,3) = 3 5 3Tabelul asociat este: V.V.B. 7/3 5/3 -43/3 n continuare problema se simplex primal sau simplex dual. V.B. x3 x1 x1 x2 x3 0 2 1 1 1 0 0 -13 0 rezolv cu ajutorul algoritmului

I.8.5. Adugarea unei noi coloane matricii A S reoptimizm soluia pentru cazul A0x + an+1 xn+1 = b071

Prin aceast modificare B rmne primal admisibil. B Se calculeaz z n+1 cn+1 . Dac B rmne i dual admisibil, x B este optim. n caz contrar, soluia se reoptimizeaz folosind algoritmul simplex primal. ) Exerciiu rezolvat. S se rezolve problema de programare liniar de la exerciiul ) i s s reoptimizeze soluia pentru a4 = (-2, 1), c4 = 0. Rezolvare. Problema ce trebuie rezolvat acum este:

inf {3x + 2x 4x + 0 x } 1 2 3 4 x1 + 3x 2 + 2x 3 2x 4 = 3 3x 1 + 3x 2 + x 3 + x 4 = 4 x 0, i = 1,4 iPornind de la tabelul 1 se va construi un nou tabel n care se va introduce o nou coloan, coloana lui x4.

3 5 1 5 2 7 5 y B = B1a 4 = = 4 1 5 2 5 1 4 5 7 5 16 T z B c 4 = cB y B c 4 = ( 4,3) 0 = 4 4 5 4 5Aadar noul tabel este: V.B. x3 x1 V.V.B. 1 1 -7 x1 0 1 0 x2 6/5 3/5 -43/5 x3 1 0 0 x4 -7/5 4/5 16/5

Problema se rezolv cu ajutorul algoritmului simplex primal.72

Exerciii propuse spre rezolvare 1) Considerm problema

inf {3x 2x x } 1 2 3 5x 1 x 2 + 2x 3 13 3x 1 + 2x 2 x 3 4 x x2 + x3 6 1 x i 0, i = 1,3

a) S se rezolve problema; b) S se reoptimizeze soluia pentru c = (1, -1, 3)T; c) S se reoptimizeze soluia pentru b = (1, 1, 0)T; d) S se reoptimizeze soluia pentru a2 = (0, -1, 2)T; e) S se reoptimizeze soluia pentru a1 = (6, 1, 1)T; f) S se reoptimizeze soluia pentru cazul cnd se adaug variabila x7, cu a7 = (-1, -1, -5)T, c7 = 0. 2) Considerm problema:

inf {2x x + x + x } 1 2 3 4 x1 x 2 + 2x 3 x 4 2 2x 1 + x 2 3x 3 + x 4 6 x + x2 + x3 + x4 7 1 x i 0, i = 1,4

a) S se rezolve problema dat; b) S se reoptimizeze soluia pentru c = (-1, 2, 0, -1)T; c) S se reoptimizeze soluia pentru b = (2, 2, 2)T; d) S se reoptimizeze soluia pentru a4 = (1, 0, -1)T; e) S se reoptimizeze soluia pentru a3 = (2, 2, -1)T; f) S se reoptimizeze soluia pentru cazul cnd se adaug variabila x8, cu a8 = (1, 2, 3)T. I.9. Parametrizare73

S considerm o problem de programare liniar:

inf { c x} 0 A 0 x = b 0 x 0pentru care am determinat o soluie optim. Fie B baza optim,

x B soluia optim i B = i a i B .I.9.1. Parametrizarea vectorului b Considerm problema

{

}

inf { c x} 0 A 0 x = b 0 + b 1 , pentru R. x 0

Prin aceast modificare, cnd variaz, B rmne dual admisibil. Se procedeaz astfel: 1. Se gsete intervalul de variaie a lui pentru care B rmne primal admisibil (adic optim), punnd condiia x B = B-1b0 + B-1b1 0. 2. n afara acestui interval se reoptimizeaz soluia aplicnd algoritmul simplex dual. ) Exerciiu rezolvat. S se rezolve problema de programare liniar:

inf {3x + 2x 4x } 1 2 3 x1 + 3x 2 + 2x 3 = 3 3x1 + 3x 2 + x 3 = 4 x , x , x 0 1 2 3

i s se parametrizeze soluia pentru b( ) = 74

3+ . 4

Rezolvare. Aplicnd metoda celor dou faze obinem soluia optim a problemei iniiale (vezi I.3.4).Ultimul tabel simplex este:Tabelul 1

V.B. x3 x1

V.V.B. 1 1 -7

x1 0 1 0

x2 6/5 3/5 -43/5

x3 1 0 0

B-1 3/5 -1/5 -1/5 2/5

Am obinut aadar B={3, 1}, B = (a3, a1), B1 = modifica doar coloana V.V.B. dup cum urmeaz:

35

x B = ( 1,0,1) i z B = 7. Vom construi un nou tabel n care se va 5 + 4 3 5 1 5 3 + 5 ~B = B1 b( ) = x = 1 5 2 5 4 5 3 5 ~B = c T x B = ( 4,3) 3 + = 35 7 ~ z B 5 4 Aadar noul tabel simplex asociat este: x2 V.B. V.V.B. x1 x3 0 6/5 5 + 4 x1 x3 1 0 0

1 5 , 1 5 2 5

5 5 3 5 35 7 5

1 0

3/5 -43/5

n continuare problema se va rezolva cu ajutorul algoritmului simplex dual.75

Pas 1: Criteriul de optim finit Dac xiB 0 pentru toi i B, baza actual este optim, iar x B este soluia optim.B x3 0 B x 0 pentru toi i B nseamn: , adic x1 0 5 + 4 5 5 0 5 + 4 0 4 5 5 , . 4 3 5 3 0 5 5 3 0 5 3

B i

5 5 , , problema are soluie optim 4 3 5 + 4 5 3 35 7 z = obinut pentru x1 = , x 2 = 0, x = . 3 5 5 5Deci, dac Pas 2: Criteriul de inexisten a soluiei Dac exist r B astfel nct x rB < 0 i y B 0 pentru oricare rj j {1, 2, ...,n} atunci problema nu are soluii.

76

n cazul nostru, dac

sau > , problema nu are soluie. Aadar:

5 3

5 + 4 5 3 5 < 0 sau < 0 , adic < 5 5 4

pentru - , problema are soluie optim 4 3 pentru -,- ,+ problema nu are soluii I.9.2. Modificarea funciei obiectiv c Considerm problemaT inf ( c0 + c1 ) x A 0 x = b 0 , pentru R x 0

5 5

5 5 4 3

{

}

Prin aceast modificare, cnd variaz, B rmne primal admisibil. Se procedeaz astfel: 1. Se stabilete intervalul de variaie al lui pentru care B rmne i dual admisibil, adic optim punnd condiia:B z B c j = z 0 c0 + ( c1 ) y j c1 ( ) 0 j j j j T

[

]

2. n afara acestui interval se reoptimizeaz soluia aplicnd algoritmul simplex primal. ) Exerciiul rezolvat. S se rezolve problema de programare liniar de la exerciiul ) i s se parametrizeze soluia pentru c() = (-3, 2 + , -4). Rezolvare. Pornind de la tabelul 1 se va construi un nou tabel n care se va modifica doar ultima linie dup cum urmeaz:

77

~B = c T ( ) x B = ( 4,3)1 = 7 z B 1 ~B c ( ) = cT ( ) y B c ( ) = ( 4,3) 0 ( 3) = 0 z1 B 1 1 1 1 ~ B c ( ) = c T ( )y B c ( ) = ( 4,3) 6 5 (2 + ) = z2 2 B 2 2 3 5 = 43 5 5

~ B c ( ) = c T ( )y B c ( ) = ( 4,3) 1 ( 4) = 0 z3 3 B 3 3 0 Aadar, noul tabel este: V.B. x3 x1 V.V.B. 1 1 -7 x1 0 1 0 x2 6/5 3/5 x3 1 0 0

43 5 5

n continuare problema se va rezolva cu ajutorul algoritmului simplex primal. Pas 1: Criteriul de optim finit z Dac ~jB c j ( ) 0 pentru toi j R atunci problema are optim finit.

~B c ( ) 0 pentru toi j R nseamn 43 5 0, deci zj j 5 43 . 5

78

43 problema are soluia optim z* = -7 5 43 continum obinut pentru x = 1, x = 0, x = 1. Dac < 1 2 3 5Deci, dac algoritmul simplex primal. Pas 2: Criteriul de optim infinit z Dac exist j R astfel nct ~jB c j ( ) > 0 i y B 0 atunci j problema are optim infinit. Se observ c n cazul nostru, pentru j R, adic j = 2, y B > 0 . j Aadar criteriul de optim infinit nu se aplic. Pas 3: Criteriul de intrare n baz Evident x2 intr n baz. Pas 4: Criteriul de ieire din baz

1 1 5 min , = 6 3 6 5 5Deci x3 iese din baz. Pas 5: Tabelul simplex asociat V.B. x2 x1 V.V.B. 5/6 1/2 x1 0 1 0 x2 1 0 0 x3 5/6 -1/2

1 + 5 6

43 + 5 6

Pas 1: Criteriul de optim finit79

Deoarece

+ , deci + > > 0. Deci vom calcula: 5 5 5 5 5Pentru >

Pas 4: Criteriul de ieire din baz

1 1 min . = 3 + 3 + 5 5 Aadar x1 iese din baz. Pas 5: Tabelul simplex asociat V.B.82

V.V.B.

x1

x2

x3

x3 x2

10 3 5 + 3 5 3 + 5 22 40 5 + 3

5 6 5 + 3 5 5 + 3 5 + 43 5 + 3

0 1 0

1 0 0

Pas 1: Criteriul de optim finit

43 -5 + 43 , < 0 , deci criteriul de 5 5 + 3 22 40 optim finit se aplic, iar problema are soluia z = obinut 5 + 3 10 3 5 pentru x = 0, x = , x = . 1 2 3 5 + 3 3 + 5Se observ c pentru > Exerciii propuse spre rezolvare S se rezolve urmtoarele probleme:T inf ( c0 + c1 ) x a) Ax 0 x 0

{

}

cu

2 1 8 T T A = 3 2 , b = 24 , R, x R 2 , c 0 = (4,3) , c1 = (0,2) 1 3 18

inf { cT x} b) Ax b 0 + b 1 cu A acelai ca la a) x 083

8 1 b 0 = 24 , b1 = 0 , R , c = (4,3)T 18 1 inf { cT x} A( ) x b x 0 2 8 1 A( ) = 3 2, b = 24 , R , 1 + 2 3 18

c)

cu

c aceeai ca la b). I.10. Programarea liniar n numere ntregi I.10.1. Algoritmul ciclic al lui Gomory Fie problema de programare liniar n numere ntregi

inf { cT x} Ax = b (I.10.1.1.) x 0 x Z n unde A Mmn(Z), rang A = m, b Zm, c Zn. Algoritmul ciclic const n urmtoarele: Pas 1. Se rezolv mai nti problema de programare liniar (I.10.1.1). Dac soluia optim obinut x = x1 ,K, x n (dac exist) aparine lui Zn, atunci algoritmul s-a terminat. Altfel se trece la pasul 2. Pas 2. Fie indicele i astfel ca: i = min {1 j nxj variabil de baz, x j nentreag} n tabelul simplex corespunztor soluiei de baz x punem n eviden prile fracionare ale componentelor liniei variabilei de baz xi. Fie fi = x i , fi (0, 1), partea fracionar a componentei x i , iar fij84

(

)

{ }

= {yij}, fij [0, 1), partea fracionar a elementului yij care se gsete n tabelul simplex corespunztor soluiei de baz x . Se scrie ecuaia:

n fij x j + x n+1 = fi (I.10.1.2.) j=1 x 0, x Z n+1 n +1

( )

Restricia (I.10.1.2) se poate aduga tabelului simplex corespunztor soluiei de baz x . Se alctuiete un nou tabel i se trece la pasul 3. Pas 3. Baza asociat tabelului simplex obinut prin adugarea liniei coeficienilor corespunztoare restriciei I.10.1.2. i a unei coloane pentru xn+1, este dual admisibil. Astfel se va elimina din baz variabila xi. Aplicnd algoritmul simplex dual pe acest tabel simplex completat, putem avea dou cazuri. Cazul 1. Nu pot fi eliminate toate componentele negative din soluie, care apar n cursul aplicrii algoritmului simplex dual. n acest caz problema nu are soluii. Cazul 2. Se pot elimina toate componentele negative din soluie. n acest caz ne este furnizat o soluie x 1 cu n + 1 componente. Dac x 1 are toate componentele ntregi, atunci aceasta va fi soluia cutat. Dac nu, se trece la pasul 2, adic se introduce nc o ecuaie i o necunoscut. Exerciiul rezolvat. S se rezolve problema:

inf {9x 5x } 1 2 75 3x 1 + 2x 2 2 () 7x + 3x 68 2 1 x1 , x 2 0, x 1 , x 2 Z

Rezolvare. Aducem problema la forma standard. Pentru aceasta nmulim prima ecuaie cu 2, dup care introducem variabilele auxiliare x3 i x4. Obinem:

85

inf {9x 5x } 1 2 6x1 + 4x 2 + x 3 = 75 7x1 + 3x 2 + x 4 68 x ,x ,x ,x 0 1 2 3 4 x1 , x 2 , x 3 , x 4 Z Pas 1. Rezolvm problema cu ajutorul algoritmului simplex primal. Obinem urmtorul tabel simplex: V.B. x3 x4 V.V.B. 75 68 0 x1 6 7 9 x2 4 3 5 x3 1 0 0 x4 0 1 0

Se observ c x1 intr n baz, iar x4 iese din baz. Se obine urmtorul tabel simplex: V.B. x3 x1 V.V.B.

117 7 68 7 612 7

x1 0 1 0

10 7 3 7 8 7

x2

x3 1 0 0

6 7 1 7 9 7

x4

Se observ c x2 intr n baz, iar x3 iese din baz. Se obine urmtorul tabel simplex: V.B. x2 V.V.B.

117 10

x1 0

x2 1

7 10

x3

x4

3 5

86

x1

47 10 504 5

1 0

0 0

3 10 8 10

2 5 3 5

Se observ c se poate aplica criteriul de optim finit. Am obinut soluia x =

47 117 504 , pentru baza {x2, x1}. Cum , ,0,0 i z = 10 10 5

x Z trecem la pasul 2.Pas 2. Fie i = min{1 j 4xj variabil de baz, x j nentreag}. Astfel i = min{1, 2} = 1. Fie fi = x i f1 =

47 = 0,7 10 3 f13 = {y 13 } f13 = = 1 0,3 = 0,7 10

{ }

2 f14 = {y 14 } f14 = = 0,4 5 f11 = {y 11 } f11 = {1} = 0 f12 = {y 12 } f12 = {0} = 0Noua restricie este:

( fij ) x j + x 4+1 = f14 j=1

adic: - 0,7x3 - 0,4x4 + x5 = - 0,7. Obinem noua problem:

87

inf {9x 4x } 1 2 6x 1 + 4x 2 + x 3 = 75 7x 1 + 3x 2 + x 4 = 68 0,7x 0,4x + x = 0,7 1 4 5

{x , x , x } :2 1 5

Construim tabelul simplex pentru noua problem pentru baza

V.B. x2 x1 x5

V.V.B.

117 10 47 10 7 10 504 5

x1 0 1 0 0

x2 1 0 0 0

7 10 3 10 7 10 4 5

x3

3 5 2 5 4 10 3 5

x4

x5 0 0 1 0

n continuare trecem la PASUL 3 adic la rezolvarea problemei cu ajutorul algoritmului simplex dual. Pas 1: Criteriul de optim finit nu se verific. Pas 2: Criteriul de inexisten a soluiei nu se verific. Pas 3: Criteriul de ieire din baz min{- 0,7} = - 0,7 Deci x5 iese din baz. Pas 4: Criteriul de intrare n baz

4 3 8 min 5 , 5 = 0,7 0,4 5

Deci x3 intr n baz.88

Pas 5: Noul tabel simplx asociat V.B. x2 x1 x3 V.V.B. 11 5 1 -100 x1 0 1 0 0 x2 1 0 0 0 x3 0 0 1 0 x4 -1 x5 1

4 7 4 7 1 7

3 7 10 7 8 7

Pas 1: Criteriul de optim finit se verific. Obinem soluia x = (5, 11, 1, 0, 0) i z = -100. Cum x Z rezult c aceasta este soluie a problemei considerate. Aadar soluie pentru problema iniial () este x1 = 5, x 2 = 11 i z = 100 . Exerciiu rezolvat. S se rezolve problema

inf {15x 4x 37x } 3 4 5 1 11 8 17 x1 + x 3 + x 4 + x 5 = 8 6 7 6 3 5 13 7 x 2 + x 3 + x 4 + x 5 = 8 2 8 2 () 1 4 5 13 x3 + x4 + x5 + x6 = 3 2 3 2 x i 0, i = 1,6 x i Z, i = 1,6Pas 1: Rezolvm problema cu ajutorul algoritmului simplex primal. Variabilele x1, x2, x3 constituie o baz admisibil. Se poate construi astfel urmtorul tabel simplex:89

V.B. x1 x2 x3

V.V.B.

17 6 7 2 26 3-130

x1 1 0 0 0

x2 0 1 0 0

x3 0 0 1 0

11 6 5 2 8 3-36

x4

7 8 13 85 -38

x5

x6 0 0 2 -30

obinut pentru:

1 0 0 1 0 0 1 B = 0 1 0 i B = 0 1 0 . 1 0 0 0 0 2 2 17 7 26 x = , , ,0,0,0 i z = -130 pentru baza {x1, x2, x3}. 6 2 3 Cum x* Z trecem la PASUL 2. Pas 2: Fie i = min {1 j 6xj variabil de baz, x j nentreag} Astfel fie i = min {1, 2, 3} = 1B Fie f1 = x1 f1 =

Pas 1: Criteriul de optim finit se aplic. Am obinut soluia

{ }

17 5 = 6 6

90

f11 = {y 11 } f11 = {1} = 0

f12 = {y 12 } f12 = {0} = 0 f13 = {y 13 } f13 = {0} = 0 11 5 f14 = {y 14 } f14 = = 6 6 7 7 f15 = {y 15 } f15 = = 8 8 f16 = {y 16 } f16 = {0} = 0Noua restricie este:

( f )x6 j=1 1j

j

+ x 6+1 = f 1 5 6

adic: x 4 x 5 + x 7 =

5 6

7 8

Obinem noua problem:

inf {15x 3 4x 4 37x 5 } 1 11 8 17 x1 + x 3 + x 4 + x 5 = 8 6 7 6 3 5 13 7 () x 2 + x 3 + x 4 + x5 = 8 2 8 2 4 5 13 1 x3 + x4 + x5 + x6 = 2 3 2 3 5 7 5 x 4 x 5 + x 7 = 6 8 6

91

Construim tabelul simplex pentru noua problem pentru baza {x1, x2, x3, x7}. V.B. x1 x2 x3 x7 V.V.B.

17 6 7 2 26 3 5 6-130

x1 1 0 0 0 0

x2 0 1 0 0 0

x3 0 0 1 0 0

11 6 5 2 8 3 5 6-36

x4

7 8 13 85

x5

x6 0 0 2 0 -30

x7 0 0 0 1 0

7 8

-38

n continuare trecem la PASUL 3, adic rezolvm problema cu ajutorul algoritmului simplex dual. Pas 1: Criteriul de optim finit nu se verific. Pas 2: Criteriul de inexisten a soluiei nu se verific. Pas 3: Criteriul de ieire din baz

5 5 min = 6 6Deci x7 iese din baz. Pas 4: Criteriul de intrare n baz

36 38 216 304 216 = min = min , , 5 7 5 7 5 6 8

Deci x4 intr n baz.

92

Pas 5: Tabelul simplex asociat: V.B. x1 x2 x3 x4 V.V.B. 1 1 6 1 - 94 x1 1 0 0 0 0 x2 0 1 0 0 0 x3 0 0 1 0 0 x4 0 0 0 1 0 x5

21 20-1

x6 0 0 2 0 -30

x7

11 53

11 5 21 20 1 5

16 5 6 5 216 5

Pas 1: Criteriul de optim finit se aplic. Aadar o soluie a acestei probleme este: x = (1, 1, 6, 1, 0,0) i z = - 94 Cum x Z, algoritmul se ncheie aici. Observaii: 1) Dac soluia final x obinut dup aplicarea algoritmului simplex dual ar fi avut i componente fracionare, adic x Zn, atunci am fi introdus la problema () nc o ecuaie (a cincea) i nc o necunoscut (x8) (vezi PASUL 2) obinnd astfel o nou problem, dup care am fi alctuit un tabel simplex pentru noua problem ce ar fi avut ca baz { x1, x2, x3, x4, x8}. Apoi am fi rezolvat aceast nou problem cu algoritmul simplex dual. 2) Dac soluia final x ar fi avut componente negative atunci problema iniial () nu ar fi avut soluii.

Exerciii propuse spre rezolvare93

Rezolvai problemele de programare liniar:

inf { 4x + 3x + 6x } 1 2 3 43x 1 + 40x 2 + 48x 3 500 1) x 1 + x 2 + x 3 12 x ,x ,x 0 1 2 3 x1 , x 2 , x 3 Z inf {5x + 4x } 1 2 3x1 + x 2 9 x + 2x 7 2 2) 1 5x1 + 3x 2 21 x , x 0 1 2 x1 , x 2 Zinf { x 1 x 2 + x 3 } 1 2 x1 + x 2 + x 3 = 1 3 3 3) 3x + 3x + x = 4 1 2 3 x i 0, i = 1,3 x i Z, i = 1,3

I.10.2. Algoritmul mixt al lui Gomory Fie problema de programare liniar:94

inf { c T x} Ax = b x 0 x Z, j J( ) j

unde A, b, c sunt matrici cu elemente numere raionale, iar J , J {1, 2, ..., n}. Algoritmul mixt const n urmtoarele: Pas 1: Mai nti se rezolv problema de programare liniar. Dac soluia optim obinut x = x1 ,K, x n (dac exist) ndeplinete condiia (), adic x j Z pentru oricare j J, atunci algoritmul s-a ncheiat. Astfel se trece la Pasul 2. Pas 2: Fie xl variabila de baz n tabelul simplex de la PASUL 1, cu l J, a crei valoare nu este ntreag. Notm cu R mulimea indicilor variabilelor secundare care apar n tabelul simplex de la PASUL 1. Determinm mulimile:

(

)

R = R R J

R = j R y lj > 0 + R lj

{ = {j R y

} < 0}{ }

Pentru j R J calculm prile fracionare flj = {ylj}. De asemenea se calculeaz fl = x lB . Mai determinm mulimile:

R 1 = j R J f lj < f l R2lj

{ = {j R J flj j

} 0 R = j {3} y 1j > 0 = + + R lj 1j

{ = {j R y

} { < 0} R = { j {3} y{ }

} < 0} = {3}

R J = { 4} 2 2 47 7 B = = . De asemenea calculm f 1 = x 1 = = . 5 5 10 10Mai determinm mulimile: Pentru j R J, adic pentru j = 4, calculm f14 = {y14} =

R 1 = j R J f 1 j < f 1 R 1 = {j {4}f14 < f 1 } = {4} R21j 1 2 14

{ = {j R J f

} > f } R = {j {4}f

> f1 } =

PAS 3: Definim g1j astfel

97

y 1j , j R + f1 y , j R 1 f1 1j g1j = f1j , j R1 f 1 1 f1j , j R 2 1 f1

(

)

Cum R = R 2 = , iar R = {3} i R1= {4}, obinem: +

f1 y 13 , j = 3 g1j = 1 f1 f , j = 4 14

7 5, j = 3 Aadar, g1j = 2, j = 4 5Astfel adugm restricia suplimentar:

2 7 7 x4 x3 + x5 = 5 5 10

Obinem noua problem:

inf {9x 5x } 1 2 6x 1 + 4x 2 + 2x 3 = 75 7x + 3x + x = 68 2 4 1 7 x 2 x + x = 7 5 5 3 5 4 10

Construim tabelul simplex pentru noua problem pentru baza {x2, x1, x5}:98

V.B. x2 x1 x5

V.V.B.

117 10 47 10 7 10 504 5

x1 0 1 0 0

x2 1 0 0 0

7 5 3 5 7 5 8 5

x3

3 10 2 5 4 10 3 5

x4

x5 0 0 1 0

Rezolvm cu ajutorul algoritmului simplex dual. Pas 1: Criteriul de optim finit nu se aplic. Pas 2: Criteriul de inexisten a soluiei nu se aplic Pas 3: Criteriul de ieire din baz

7 7 min = 10 10 Deci x5 iese din baz. Pas 4: Criteriul de intrare n baz

8 3 8 min 5 , 5 = 7 4 7 5 10

Deci x3 intr n baz.

Pas 5: Calculul noului tabel asociat V.B. V.V.B. x1 x2 x3 x4 x599

x2 x1 x3

11 5

0 1 0 0

1 0 0 0

0 0 1 0

1 2-100

7 10 4 7 2 7 1 7

1

3 7 5 7 8 7

Pas 1: Criteriul de optim finit se aplic. Aadar am obinut soluia x = 5,11, ,0 i z*= - 100. Cum

1 2

x , x , x Z rezult c algoritmul mixt al lui Gomory s-a ncheiat. 1 2 4Exerciii propuse spre rezolvare Rezolvai urmtoarele probleme de programare liniar:

inf {10x 7x + 2x x } 1 2 3 4 3x 1 2x 2 x 3 = 1 x + 2x + x = 12 1 3 4 1) 2x 2 + x 3 + 3x 4 = 16 x 0, i = 1,4 i x 2 Z

100

inf {2x + x } 1 2 x1 x 2 4 3x x 18 2 2) 1 x 1 + 2x 2 6 x , x 0 1 2 x1 ZI.11. Probleme de transport Considerm problemam n min cijx ij i=1 j=1 n x = ( ) a , 1 i m i j=1 ij m x ij = ( ) b j , 1 j n i=1 x ij 0, 1 i m, 1 j n m n unde a i = ( ) b j , a i 0, b j 0 i=1 j=1

Matricial problema se va scrie sub forma:

min{ c T x} Ax = b x 0

unde A Mm+n,mn (R), rang A = m + n - 1, xRmn, b = (a1, ..., am, b1, ..., bn)T Rm+n,, c = (c1, ..., cmn)T Rmn. Aceast problem de programare liniar se rezolv cu ajutorul problemei duale.101

Determinarea unei soluii iniiale de baz prin metoda colului de nord-vest 1. Se ntocmete tabelul corespunztor problemei de transport: c11 c21 cm1 b1M

x11

c12 c22 cm2 b2

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

c1n c2n cmn bn

a1 a2 am

2. Se alege ca prim variabil de baz x11 (variabila din colul de N.V.) creia i se atribuie x11 = min{a1, b1}. Aceast valoare se trece n prima celul, sub diagonal. 3) Dac x11 = a1, atunci x12 =K= x1n = 0 (variabile secundare) i se nlocuiete a1 cu a1 - x11 , iar b1 cu b1 - x11 . Dac x11 = b1, atunci x 21 =K = x m1 = 0 (variabile secundare) i de asemenea, se nlocuiete a1 cu a1 - x11 , b1 cu b1 - x11 . n continuare se consider ca variabil de baz urmtoarea variabil din colul de N.V. al tabelului rmas i se procedeaz analog. Exemplu. S se determine o soliie iniial de baz folosind metoda colului de N.V. pentru problema: 7 2 6 5 8 4 3 9 5 5 1 9 3 9 2 7 11 11 8

Rezolvare102

7 5 2 6 5 0

8 6 4 3 3 9 3 0 1 5

5 8 2 1 9 1 0

3 9 7 7 0

11 11 8

6 8 7

0 0 0

x11 = min{5, 11} = 5 x12 = min{9, 6} = 6 x22 = min{3, 11} = 3 x23 = min{9, 8} = 8 x33 = min{1, 8} = 1 x34 = min{7, 7} = 0 Am obinut astfel urmtoarea soluie iniial de baz: 7 5 2 6 4 3 3 1 1 8 6 5 8 2 7 5 3 9

Algoritmul de transport 1. Se ntocmete tabelul corespunztor problemei de transport. 2. Se determin o soluie iniial de baz ale crei valori se trec n tabel n celulele corespunztoare, sub diagonal. 3. Fie B = {(i, j)xij variabil de baz}. Se rezolv sistemul ui + vj = cij, (i, j) B, fixndu-se arbitrar (i, j) valoarea unei variabile (de exemplu u1 = 0). Fie ui, vj, B, soluiile acestui sistem. Se nscriu valorile ui i vj pe marginile tabelului (ui la vest i vj la nord). 4. Se calculeaz cantitile ij = ui + vj - cij pentru (i, j) B i se nscriu n colul din dreapta jos al celulelor respective.103

5. Test de optimalitate. Dac ij 0 pentru oricare (i, j) B, soluia este optim. Dac exist (i, j) B cu ij > 0, atunci soluia se poate mbunti. 6. mbuntirea soluiei. a) Calculm kl = max ij . xkl va intra n baz.( i , j ) B

b) Se determin ciclul format de celula (k, l) cu celelalte celule corespunztoare variabilelor de baz. Se calculeaz: x ps = min { x tr (t, r) celul de rang par n ciclul anterior determinat} xps va iei din baz. c) Se determin noile valori ale variabilelorde baz:

x tr - x ps , dac (t,r) este celul de rang par n ciclu x tr = x tr + x ps , dac (t,r) este celul de rang impar n cicluObservm c aceast operaie poate da unor variabile de baz o valoare nul. Aceste variabile nule vor fi considerate ca fcnd parte din noua soluie de baz, care este acum degenerat. 7. Se reia algoritmul pentru noua soluie de baz. Exerciiul rezolvat. S se rezolve problema de transport dat de urmtorul tabel: 8 3 5 2 10 4 1 6 7 15 1 9 4 3 25 5 10 20 15 Rezolvare. Determinm mai nti o soluie iniial de baz cu ajutorul metodei colului N.V. 8 3 5 2 10 5 0 5 5104

4 1 5 0

1 5 9 10 5 0

6 10 4 10 20 10 0 3

7 15 15 0

15 25

10 15

0 0

Am obinut astfel urmtoarea soluie iniial de baz: 8 3 8 7 8 3 5 2 0 5 5 3 5 4 1 6 7 -2 2 5 10 -2 1 9 4 3 -4 3 -10 10 15 Obinem B = {(1, 1), (1, 2), (2, 2), (2, 3), (3, 3), (3, 4)}. Construim sistemul: ui + vj = cij, pentru (i, j) B. Obinem:

u1 + v1 = 8 u1 + v 2 = 3 u2 + v2 = 1 u2 + v3 = 6 u + v3 = 4 3 u3 + v 4 = 3 u = 0 1

Obinem soluiile: u1 = 0 v1 = 8 u2 = -2 v2 = 3 u3 = -4 v3 = 8 v4 = 7105

Calculm ij pentru (i, j) B, ij = ui + vj - cij Astfel: 13 = 0 + 8 - 5 = 3 14 = 5 21 = 2 24 = -2 31 = 3 32 = -10 Soluia nu este optim deoarece exist ij > 0. n continuare vom ncerca mbuntirea soluiei. Pentru aceasta calculm max {ij(i, j) B} = max {3, 5, 2, -2, 3, -10} = 5 = 14. Deci x14 intr n baz. Considerm ciclul pornit din celula (1, 4). C = {(1, 4), (3, 4), (3, 3), (2, 3), (2, 2), (1, 2), (1, 4)} Calculm

min x tr ( t, r ) {( 3,4) , ( 2,3) , ( 1,2)} = x12 = 5

{

}

Deci x12 iese din baz. Noile variabile de baz vor avea deci urmtoarele valori: x 11 = 5 (neschimbat), x 14 = 5, x 34 = 15 - 5 = 10, x 33 = 10 + 5 = 15, x 23 = 10 5 = 5, x 22 = 5 + 5 = 10. Obinem urmtorul tabel: 8 -2 3 2 8 3 5 2 0 5 -5 -2 5 4 1 6 7 3 7 10 5 -2 1 9 4 3 1 8 -10 15 10 Obinem B = {(1, 1), (1, 4), (2, 2), (2, 3), (3, 3), (3, 4)} Construim sistemul ui + vj = cij, pentru (i, j) B. Obinem:

106

u1 + v1 = 8 u1 + v 4 = 2 u2 + v2 = 1 u2 + v3 = 6 u + v3 = 4 3 u3 + v 4 = 3 u = 0 1Obinem soluiile: u1 = 0 v1 = 8 u2 = 3 v2 = -2 u 3 = 1 v3 = 3 v4 = 2 Calculm ij pentru (i, j) B, ij = ui + vj - cij. Astfel: 12 = -5; 13 = -2; 21 = 7; 24 = -2; 31 = 8; 32 = -10. Soluia nu este optim deoarece exist ij > 0. n continuare vom ncerca mbuntirea soluiei. Pentru aceasta calculm max {ij(i, j) B} = max {-5, -2, 7, -2, 8, -10} = 8 = 31 Deci x31 intr n baz. Considerm ciclul pornit din celula (3. 1) C = {(3, 1), (1, 1), (1, 4), (3, 4), (3, 1)} Calculm

min{x tr (t , r ) {(1,1), (3,4 )}} = x 11 = 5

Deci x11 iese din baz. Obinem urmtorul tabel: 0 -2 3 2107

0 3 1

8 -8 4 -1 1 5

3 -5 1 10 9 -10

5 -2 6 5 4 15

2 10 7 -2 3 5

Obinem B = {(1, 4), (2, 2), (2, 3), (3, 1), (3, 3), (3, 4)}. Construim sistemul ui + vj = cij, pentru (i, j) B. Obinem:

u1 + v 4 = 2 u2 + v2 = 1 u2 + v3 = 6 u 3 + v1 = 1 u + v3 = 4 3 u3 + v4 = 3 u = 0 1

Obinem soluiile: u1 = 0 v1 = 0 u2 = 3 v2 = -2 u 3 = 1 v3 = 3 v4 = 2 Calculm ij pentru (i, j) B, ij = ui + vj - cij. Astfel: 11 = -8; 12 = -5; 13 = -2; 21 = -1; 24 = -2; 32 = -10. Cum ij 0 pentru oricare (i, j) B rezult c n acest moment am obinut soluia optim. Aceasta este: x 14 = 10; x 22 = 10; x 23 =5; x 31 = 5; x 33 = 15; x 34 = 5. Valoarea minim a costului de transport este 125. Exerciii propuse spre rezolvare S se rezolve problemele de transport date de urmtoarele tabele: 1)108

1 7 4 2 20 2) 3 8 1 15 3) 3 1 3 50 4) 2 3 3 8 5) 6 1 2 11

3 6 9 10 5 5 4 6 12 2 2 5 25 4 6 5 15 5 3 4 7

2 5 11 8 7 9 5 2 8 2 3 2 15 6 9 7 2 4 2 1 8

7 4 1 6 8 2 4 7 25 4 4 1 10 8 1 9 1 11 5 6 10

9 3 10 1 10 18 22 20

15 10 13 12

70 10 20

13 6 7

6 1 9 4

9 4 7 3

20 18 5

I.12. Probleme recapitulative I.12.1. Exerciiu rezolvat. Se consider problema de programare liniar109

inf { c T x} (1) Ax = b x 0unde A M3,6(R). Ultimele trei coloane ale lui A sunt vectori unitari e1, e2, i e3. n cursul rezolvrii problemei (1) cu algoritmul simplex se obine tabelul simplex urmtor: V.B. x4 x2 x6 V.V.B. 10 3 5 -45 x1 5/2 -1/2 -5/2 5/2 x2 0 1 0 0 x3 2 0 3 2 x4 1 0 0 0 x5 1/4 1/4 -3/4 -15/4 x6 0 0 0 1

0 -15 0

Se cere: a) Determinai inversa B-1 a bazei B corespunztoare acestui tabel simplex. b) Scriei sistemul de ecuaii Ax = b n forma explicit n raport cu baza B. c) Gsii problema (1). d) Determinai mulimea soluiilor optime pentru problema (1). e) Scriei duala problemei (1). f) Determinai o soluie optim a dualei. g) nlocuind n (1) vectorul c prin c() = (5 - , -15 + 2, -2 - 2, , 0, 2)T unde este parametru real, rezolvai problema de programare liniar parametric obinut n acest mod. Rezolvare. a) Deoarece ultimele trei coloane ale matricii A sunt vectirii e1, e2, e3 atunci inversa B-1 a bazei B corespunztoare acestui tabel simplex este:

1 1 4 0 B = 0 1 4 0 0 3 4 1 1

110

b) Sistemul de ecuaii Ax = b n form explicit n raport cu baza B este:

inf {x 0 } 5 15 x 0 = 45 + ( x 1 ) + 2( x 3 ) ( x 5 ) 2 4 5 1 x 4 = 10 + ( x 1 ) + 2( x 3 ) + ( x 5 ) 2 4 1 1 x 2 = 3 ( x 1 ) + ( x 5 ) 2 4 5 3 x 6 = 5 ( x 1 ) + 3( x 3 ) ( x 5 ) 2 4

1 1 4 0 1 1 0 Cum B1 = 0 1 4 0 , obinem c B = 0 4 0 0 3 4 1 0 3 1 tim c x B = B-1b. nmulind cu B la dreapta aceast relaie obinem c b = B x B , deci: 1 1 0 10 7 7 b = 0 4 0 3 = 12 b = 12 0 3 1 5 14 14 B -1 tim c y j = B aj, pentru oricare j {1, 2, ..., 6}. nmulind cu B la dreapta aceast relaie, obinem aj = B y B , pentru oricare jj {1, 2, ..., 6}. Deci:1

c) Pentru a putea scrie problema (1), trebuie s determinm pe b, A i c. Pentru aceasta trebuie s gsim mai nti matricea B.

1 1 0 5 2 3 pentru j = 1: a = By = 0 4 0 1 2 = 1 2 0 3 1 5 2 4 B 1

111

1 1 pentru j = 2: a 2 = By B = 0 4 2 0 3 1 1 3 B pentru j = 3: a = By 3 = 0 4 0 34

0 0 1 0 1 = 4 1 0 3 0 2 2 0 0 = 0 1 3 3

Pentru j = 4, j = 5 i j = 6 nu mai calculm aj deoarece tim deja c a = e1, a5 = e2, a6 = e3. Aadar avem:

3 1 2 1 0 0 A = 1 2 4 0 0 1 0 3 3 0 0 1 4

T tim c z B c j = cB y B c j , pentru oricare j {1, 2, ..., 6}, dar j j din ipoteza problemei tim c c4 = 0, c2 = -15 i c6 = 0 i T cB = (0, -15, 0). Deci: pentru j = 1:

B T B z1 c1 = cB y1 c1 5 15 B = c1 c1 = 5 . z1 c1 = 5 2 2 2 52 15 T B cB y 1 = ( 0,15,0) 1 2 = 2 5 2

pentru j = 3:

112

B T B z 3 c3 = cB y 3 c3 2 = 0 c 3 c 3 = 2 . z B c3 = 2 3 2 T B cB y 3 = ( 0,15,0) 0 = 0 3 pentru j = 5:

B T B z 5 c5 = cB y 5 c5 15 15 15 z B c5 = = c5 c5 = 0 5 4 4 4 14 15 T B cB y 5 = ( 0,15,0) 1 4 = 4 3 4 . Aadar: cT = (5, -15, -2, 0, 0,0)

113

Deci problema iniial este:

x 1 x 2 x inf (5,15,2,0,0,0 ) 3 x 4 x 5 x 6 x1 x 1 2 1 0 0 2 7 3 x3 1 2 4 0 0 1 0 = 12 x 4 3 3 0 0 1 4 14 x 5 x 6 x1 , x 2 , x 3 , x 4 , x 5 , x 6 0adic:

inf {5x 1 15x 2 2 x 3 } 3x 1 x 2 + 2 x 3 + x 4 = 7 1 2 x 1 + 4x 2 + x 5 = 12 4 x 1 + 3x 2 + 3x 3 + x 6 = 14 x 1 , x 2 , x 3 , x 4 , x 5 , x 6 0

d) Rezolvm problema cu ajutorul algoritmului simplex primal. Pas 1: Criteriul de optim finit nu se aplic. Pas 2: Criteriul de optim infinit nu se aplic. Pas 3: Criteriul de intrare n baz

5 15 5 max ,0,2, = x 1 intr n baz. 4 2 2

114

Pas 4: Criteriul de ieire din baz

10 min = 4 x 4 iese din baz. 5 2Tabelul (*)

Pas 5: Calculul noului tabel simplex V.B. x1 x2 x6 V.V.B. 4 5 15 -55 x1 1 0 0 0 x2 0 1 0 0 x3 4/5 2/5 5 0 x4 2/5 1/5 1 -1 x5 1/10 3/10 -1/2 -4 x6 0 0 1 0

Pas 1: Criteriul de optim finit se aplic. O soluie a problemei este z* = -55 obinut pentru * x1 = 4, x * = 5, x * = 0, x * = 0, x * = 0, x * = 15 . 2 3 4 5 6 Problema nu are soluie unic deoarece z B c j nu este strict jB mai mic d