Anexă la cursul 2 Algoritmul lui Ralph Gomory. Exemplu numeric: Să se determine soluția optimă a următoarei probleme de programare în numere întregi: max f = x1 + 2 x2 (PI) −3 x1 + 10 x2 ≤ 20 7 x1 + 6 x2 ≤ 56
x1 , x2 ≥ 0, x1 , x2 ∈ Z Să se scrie ecuațiile dreptelor de tăietură Gomory în varibilele originare ale problemei și să se reprezinte grafic aceste drepte.
REZOLVARE: Rezolvând cu algoritmul simplex problema relaxată (P), se obține următorul table simplex final: max cB cj X 7/2 5 12
B
1 a1 2 a2 0
0 a4 B a2 a1 f
a3
7/88 -3/44 1/11
2 1
0 1 0
1 0 0
3/88 5/44 2/11
x2 + 7 / 88 x3 + 3 / 88 x4 = 7 / 2 x2 + 7 / 88 x3 + 3 / 88 x4 = 3 + 1 / 2 x2 − 3 = −7 / 88 x3 − 3 / 88 x4 + 1 / 2 ≤ 1 / 2 Deoarece x2 ∈ API ⇒ x2 − 3 ∈ Ζ,
rezultă din relația de mai sus că x2 − 3 ≤ 0 . Ecuația hiperplanului de secțiune Gomory este: (T1): x2 = 3 , hiperplanul fiind în acest caz o dreaptă paralelă cu axa absciselor. Intersecția mulțimii de soluții admisibile AP cu semiplanul închis x2 − 3 ≤ 0 , mărginit de dreapta (T1) este o mulțime inclusă strict în AP care nu conține optimul fracționar al problemei (P), x* = (5, 7 / 2) Pe de altă parte,are loc, de asemenea inegalitatea:
−7 / 88 x3 − 3 / 88 x4 + 1/ 2 ≤ 0 i.e.
−7 / 88 x3 − 3 / 88 x4 ≤ −1 / 2 , a cărei aducere la forma standard conduce la ecuația: −7 / 88 x3 − 3 / 88 x4 + x5 = −1 / 2 , unde variabila de ecart x5 ≥ 0 . Adăugarea acestei noi restricții la restricțiile originare ale problemei relaxate (P) și reoptimizarea utilizând algoritmul simplex dual ne conduc la:
Iterația 1: max cB cj X 7/2 5 -1/2 12 3 38/7 44/7 80/7
B
1 a1 2 a2 0
0 a4 0 a5 B a2 a1 a5 f a2 a1 a3 f
a3
7/88 -3/44 -7/88 1/11 0 0 1 0
2 1 0 2 1 0
0 1 0 0 0 1 0 0
1 0 0 0 1 0 0 0
3/88 5/44 -3/88 2/11 0 1/7 3/7 1/7
0 0 1 0 1 -6/7 -88/7 8/7
Se constată că soluția optimă nu aparține mulțimii de soluții admisibile asociate problemei (PI). În acest caz, se continuă aplicarea algoritmului Gomory în cadrul unei noi iterații: Componentele fracționare ale soluției optime sunt: * x1 = 38 / 7 = 5 + 3 / 7 și
* x3 = 44 / 7 = 6 + 2 / 7 . Alegem restricția generatoare după partea fracționară cea mai mare a termenului liber. Calculele care conduc la scrierea noii restricții în formă explicită în raport cu baza B′ = ( a 2 , a1 , a 3 , a 6 ) sunt următoarele:
x1 + 1 / 7 x4 − 6 / 7 x5 = 5 + 3 / 7 x1 + 1 / 7 x4 − x5 + 1 / 7 x5 = 5 + 3 / 7 x1 − x5 − 5 = −1 / 7 x4 − 1 / 7 x5 + 3 / 7 Deoarece x1 , x5 ∈ Z și x4 , x5 ≥ 0 , deducem că x1 − x5 − 5 ≤ 3 / 7 adică x1 − x5 − 5 ≤ 0 . Această relație poate fi exprimată numai în variabilele decizionale ale problemei (PI), dacă ținem seama că: −7 / 88 x3 − 3 / 88 x4 + x5 = −1 / 2 și că x2 + 7 / 88 x3 + 3 / 88 x4 = 7 / 2 . Din ultimele două relații rezultă că x2 + x5 = 3 , deci: x1 + x2 ≤ 8 . Ecuația dreptei de secțiune Gomory este (T2): x1 + x2 = 8 . Observăm din nou faptul că intersecția semiplanului închis x1 + x2 ≤ 8 cu mulțimea de soluții admisibile AP1 ale problemei (P1) nu conține optimul fracționar al acesteia x* = (38 / 7,3) Pe de altă parte, −1 / 7 x4 − 1 / 7 x5 + 3 / 7 ≤ 0 −1 / 7 x4 − 1 / 7 x5 ≤ −3 / 7 −1 / 7 x4 − 1 / 7 x5 + x6 = −3 / 7, x6 ≥ 0 Aplicarea algoritmului simplex dual conduce la următoarele calcule:
Iterațiile 1 și 2:
max cB 2 1 0 2 1 0 0 2 1 0 0 B a2 a1 a5 f a2 a1 a3 a6 f a2 a1 a3 a4 f
cj X 7/2 5 -1/2 12 3 38/7 44/7 -3/7 80/7 3 5 5 3 11
B
1 a1 0 1 0 0 0 1 0 0 0 1 0 0 0 0
2 a2 1 0 0 0 1 0 0 0 0 0 1 0 0 0
0
0 a4 3/88 5/44 -3/88 2/11 0 1/7 3/7 -1/7 1/7 0 0 0 1 0
0 a5 0 0 1 0 1 -6/7 -88/7 -1/7 8/7 1 -1 -13 1 1
0 a6
a3
7/88 -3/44 -7/88 1/11 0 0 1 0 0 0 0 1 0 0
0 0 0 1 0 0 1 3 -7 1
Algoritmul identifică la acestă iterație soluția optimă întreagă a problemei (PI) x* = (5,3) f * = 11 