Anex la cursul 2 Algoritmul lui Ralph Gomory.

Exemplu numeric:

S se determine soluia optim a urmtoarei probleme de programare n numere ntregi:

(PI)

1 2

1 2

1 2

1 2 1 2

max 2

3 10 20

7 6 56

, 0, ,

f x x

x x

x x

x x x x Z

= +

+

+

S se scrie ecuaiile dreptelor de tietur Gomory n varibilele originare ale problemei i s se reprezinte grafic aceste drepte. REZOLVARE: Rezolvnd cu algoritmul simplex problema relaxat (P), se obine urmtorul table simplex final: max

jc 1 2 0 0

Bc B B

X 1a 2a 3a

4a

2 2a 7/2 0 1 7/88 3/88 1 1a 5 1 0 -3/44 5/44

f 12 0 0 1/11 2/11

2 3 4

2 3 4

2 3 4

2 2

7 / 88 3 / 88 7 / 2

7 / 88 3 / 88 3 1/ 2

3 7 / 88 3 / 88 1/ 2 1/ 2

3 ,PI

x x x

x x x

x x x

Deoarece x A x

+ + =

+ + = +

= +

rezult din relaia de mai sus c 2 3 0x .

Ecuaia hiperplanului de seciune Gomory este: (T1): 2 3x = , hiperplanul fiind n acest caz o dreapt paralel cu axa absciselor. Intersecia

mulimii de soluii admisibile PA cu semiplanul nchis 2 3 0x , mrginit de dreapta (T1)

este o mulime inclus strict n PA care nu conine optimul fracionar al problemei (P), * (5,7 / 2)x =

Pe de alt parte,are loc, de asemenea inegalitatea: i.e.

3 47 / 88 3 / 88 1/ 2x x , a crei aducere la forma standard conduce la ecuaia:

3 4 57 / 88 3 / 88 1/ 2x x x + = , unde variabila de ecart 5 0x .

Adugarea acestei noi restricii la restriciile originare ale problemei relaxate (P) i reoptimizarea utiliznd algoritmul simplex dual ne conduc la:

3 47 / 88 3 / 88 1/ 2 0x x +

Iteraia 1: max

jc 1 2 0 0 0

Bc B B

X 1a 2a 3a

4a 5a

2 2a 7/2 0 1 7/88 3/88 0 1 1a 5 1 0 -3/44 5/44 0

0 5a -1/2 0 0 -7/88 -3/88 1 f 12 0 0 1/11 2/11 0 2 2a 3 0 1 0 0 1

1 1a 38/7 1 0 0 1/7 -6/7 0 3a 44/7 0 0 1 3/7 -88/7

f 80/7 0 0 0 1/7 8/7 Se constat c soluia optim nu aparine mulimii de soluii admisibile asociate problemei (PI). n acest caz, se continu aplicarea algoritmului Gomory n cadrul unei noi iteraii: Componentele fracionare ale soluiei optime sunt:

*1 38 / 7 5 3 / 7x = = + i *3 44 / 7 6 2 / 7x = = + .

Alegem restricia generatoare dup partea fracionar cea mai mare a termenului liber. Calculele care conduc la scrierea noii restricii n form explicit n raport cu baza

( )2 1 3 6, , ,B a a a a = sunt urmtoarele:

1 4 5

1 4 5 5

1 5 4 5

1/ 7 6 / 7 5 3 / 7

1 / 7 1 / 7 5 3 / 7

5 1/ 7 1 / 7 3 / 7

x x x

x x x x

x x x x

+ = +

+ + = +

= +

Deoarece 1 5,x x Z i 4 5, 0x x , deducem c

1 5 5 3 / 7x x adic 1 5 5 0x x . Aceast relaie poate fi exprimat numai n variabilele

decizionale ale problemei (PI), dac inem seama c:

3 4 57 / 88 3 / 88 1/ 2x x x + = i c

2 3 47 / 88 3 / 88 7 / 2x x x+ + = . Din ultimele dou relaii rezult c 2 5 3x x+ = , deci:

1 2 8x x+ . Ecuaia dreptei de seciune Gomory este (T2): 1 2 8x x+ = . Observm din nou

faptul c intersecia semiplanului nchis 1 2 8x x+ cu mulimea de soluii admisibile 1PA ale

problemei (P1) nu conine optimul fracionar al acesteia * (38 / 7,3)x = Pe de alt parte,

4 5

4 5

4 5 6 6

1/ 7 1 / 7 3 / 7 0

1/ 7 1 / 7 3 / 7

1/ 7 1 / 7 3 / 7, 0

x x

x x

x x x x

+

+ =

Aplicarea algoritmului simplex dual conduce la urmtoarele calcule: Iteraiile 1 i 2:

max jc 1 2 0 0 0 0

Bc B B

X 1a 2a 3a

4a 5a 6a

2 2a 7/2 0 1 7/88 3/88 0 1 1a 5 1 0 -3/44 5/44 0

0 5a -1/2 0 0 -7/88 -3/88 1 f 12 0 0 1/11 2/11 0 2 2a 3 0 1 0 0 1 0

1 1a 38/7 1 0 0 1/7 -6/7 0 0 3a 44/7 0 0 1 3/7 -88/7 0

0 6a -3/7 0 0 0 -1/7 -1/7 1 f 80/7 0 0 0 1/7 8/7 0 2 2a 3 1 0 0 0 1 0 1 1a 5 0 1 0 0 -1 1

0 3a 5 0 0 1 0 -13 3 0 4a 3 0 0 0 1 1 -7

f 11 0 0 0 0 1 1 Algoritmul identific la acest iteraie soluia optim ntreag a problemei (PI)

* *(5,3) 11x f= =