Capitolele 1 și 2 ale cursului de Cercet ări Operaționale din anul I II au ca supo rt Notele de curs ale Domnului Profesor Vasile Nica și lucr area “… [607866]

CAPIT OLUL I
PROGRAMARE ÎN NUMERE ÎNTREGI

Capitolele 1 și 2 ale cursului de Cercet ări Operaționale din anul I II au ca supo rt Notele de curs ale
Domnului Profesor Vasile Nica și lucr area “ Capitole Speciale al e Cerc etărilor Operaționale” a a celuiași
autor, editat ă de Centrul d e Învățământ Econom ic Deschis la Dist anță din Academ ia de Studii Econom ice
București.

1.1 Definirea unei probleme de programare liniar ă în numere întregi

Să se determ ine x1, x2, …, xn care m aximizează funcția:

f = c1x1 + c2x2 + … + cnxn (1)

cu satisfacerea res tricțiilor:



=+…++=+…++=+…++
m n mn 2 m2 1 m12 n 2n 2 22 1211 n 1n 2 12 111
b xa xa xa…b xa xa xab xa xa xa
(2)

a restricțiilor de nenegativitate:

xj ≥ 0 , oricare ar fi j = 1,…, n (3)

și a condițiilor de integritate:

xj , într egi j = 1, …, n , (4)

În (1) și (2) coef icienții b1 ,…, bn și a11, a12, … , amn se vor presupune în m od constant
întreg i. Cerința nu es te deloc r estrictivă pentru că, în m od obișnuit, datele, oricar e ar fi prob lema,
sunt num ere raționale.
Problem ele (1)–(4) = (Integer Linear Programm ing) se prezint ă în f orma standard .
Considerarea apro ape în exclu sivitate a aceste i form e nu constituie o restrângere a generalit ății
noastre pentru c ă oricare ar fi inecua ția (cu coeficien ți întregi!), e a poate fi transf ormată în eg alitate
prin introducerea unei va riabile de abatere în m aniera binecunoscut ă din program area liniar ă. Este
evident că și variab ilele de abatere v or satisface restric țiile de nenegativitate.
Ignorând condiția de integritate, prim ele trei condi ții formeaz ă o problem ă standard de
program are liniară denum ită în continuare (LP).

1

Pentru com oditatea scrierii adapt ăm notațiile m atriciale u zuale:

(m ax)f = c⋅x (m ax)f = c⋅x
( ILP ) A⋅x = b ( LP ) A⋅x = b
x ≥ 0 x ≥ 0
x ÎNTREG

Să punem în eviden ță mulțimea de Solu ții Adm isibile ale celor dou ă problem e:

AILP = { x ∈ R n ú A⋅x = b , x ≥ 0 , x întreg}
ALP = { x ∈ R n ú A⋅x = b , x ≥ 0 } ⇒ A ILP ⊂ ALP

De aici rezult ă că (LP) es te o RELAXARE a lui (I LP).
Să presupunem pentru m oment că am bele problem e au Soluții Optime finite. În m od
constant vom nota cu x0 soluția optimă a program ului ILP (Solu ție Optimă Întreagă), în timp ce
soluția optimă a programului LP este x* (Soluție Optimă Neîntreag ă – Fracționară).

avem f ( x0 ) ≤ f ( x*)

Este posibil ca x* să aibă toate com ponentele întregi ⇒ x* = x0. Condiția de integ ritate (4)
complică enorm rezolvarea programului (ILP). Vom sublinia aces t lucru printr-o paralel ă între
trăsăturile cele mai importan te ale Mul țimilor de Solu ții Adm isibile ale celor dou ă problem e: (LP) și
(ILP).

Exemplu numeric:

(m ax) f = 3×1 – x2 ( max) f = 3×1 – x2
3 x1 – 2×2 ≤ 3 3 x1 – 2×2 ≤ 3
5 x1 + 4×2 ≥ 10 5 x1 + 4×2 ≥ 10
(ILP) 2 x1 + x2 ≤ 5 (LP) 2 x1 + x2 ≤ 5
x1,2 ≥ Ø relaxata x1,2 ≥ Ø
x1,2 ∈ Z

Figura 1 pune în evidență mulțimea soluțiilor adm isibile ALP ca fiind poligonul convex
ABC D. Soluția op timă x* se află într-un pu nct ex trem al acestu i poligon. Rep rezentând g rafic
curbele de n ivel ale func ției obiectiv se deduce c ă: x* ≡ A adică , f (x*) = 30 / 7. 



==
7/97/13
*
2*
1
xx

2

x1 x2
B O P

N

C

2 D
M ≡ x0 = [1, 2]
A ≡ x*
1 f = 0 (3)
(2) (1)
Figura 1

Prin insp ectarea d irectă se conclude c ă AILP este for mată din punctele M(1,2), N(0,3), P(0,4),
D(0,5), O(1,3). Valoarea cea m ai mare a funcției obiectiv se atinge în (1, 2) ⇒ x0 ≡ M avem x0
1=1,
x0
2 = 2 cu func ția ob iectiv f(x0) = 1.

Observație:
Simpla rotunjire a com ponentelor optim ului fracționar nu conduce în mod obligatoriu la
optim ul întreg. În cazu l de față prin rotun jire se obține punctul x(2,1) care nu este o so luție
admisibilă.
3

Figura 1 pune în evidență și un a lt aspect inte rensant. Să considerăm cea mai mic ă mulțime
convexă care conține so luții admisibile întregi ale prob lemei ILP . Nu es te greu de văzut că această
mulțime este reprezentat ă de poligonul MNDO. Vârfurile a cestui poligon sunt, prin construc ție,
soluții admisibile întregi și dacă maximizăm pe f pe aceas tă mulțime regăsim optimul întreg x0 !
Prin urm are putem rezolva o problem ă de program are liniar ă întreagă ca o problem ă de
program are lin iară obișnuită cu condi ția să știm să descriem în limbaj ecuațional
ÎNFĂȘURĂTOAREA CONVE XĂ a mulțimii soluțiilor sale întregi!
Reîntorcându-ne la cazul general dar insp irându-ne to t tim pul din acest exem plu notăm
următoarele:
1) În tim p ce ALP formează o m ulțime convex ă și închisă în Rn (n = numărul variabile lor
problem ei), mulțimea AILP este doar o m uțime discretă putând avea chiar un num ăr finit d e
elem ente. ILP poate s ă nu aibă soluții adm isibile (întregi) chiar dac ă LP are!

Exem plu:

1

2
1 2

Figura 2 ALP

2) Trebuie explicat de la bun înce put d e ce acord ăm importan ță programării în num ere
întregi. Es te evid ent f aptul că pentru foarte m ulte problem e variabilele sunt supuse
restricțiilor de integ ritate. Un m od destul de realist de abordare a acestor problem e constă în
a rezo lva p roblem a fără a ține seam a de condi țiile d e integ ritate d upă care ro tunjes c
componentele frac ționare ale solu țiilor optim e de așa manier ă încâ t restricțiile să fie
respectate. Aceast ă modalitate este frecvent f olosită în p ractică și este perfect justificat ă în
situația în c are va lorile perm isibile ale va riabilelor sun t suficien t de m ari astfel c ă efectul
rotunjir ii es te neglijab il. Există însă problem e de program are liniar ă în num ere întreg i
deosebit de im portante în care variabilele iau v alori întregi destul de m ici adesea 0 sau 1.
Pentru asem enea problem e “distanța” dintre optimul frac ționar și cel într eg s-ar pute a să fie
atât d e mare încât rotun jirea să nu ducă la o soluție accep tabilă.

3) Teoretic, orice problem ă de program are liniar ă în num ere întreg i este echivalent ă cu o
problemă de program are liniară uzuală adică în variab ile continue dac ă mulțimea soluțiilor
întregi se înlocuiește cu înfășurătoarea sa convex ă. Dificultatea abord ării problem ei din acest
unghi rezid ă în enorm a greutate de a descrie ecua țional înfășurătoarea convex ă.

4) Presupunem c ă într-o problem ă de program are liniară în numere în tregi apare restric ția:

1/2 x1 + 2/3 x2 + 3/4×3 ≤ 17/5
Transform ăm într-o inegalitate cu coeficien ți ÎNTREGI prin înm ulțirea cu c.m .m.m.c. al
numitorilor care este 60 ⇒ 30×1 + 40 x2 +45×3 ≤ 204 ⇒ forma STAS:
4

30×1 + 40 x2 +45×3 + y = 204
x1,2,3 ∈ Z ⇒ y ∈ Z (ca diferen ță de num ere întregi).

1.2 Exemp le

1. Problema croirii

Un număr de repere uni sau bidim ensiona le treb uie ex ecutate în cantit ăți date. Aceste repere
se obțin prin decupare din ni ște suporți (bare sau foi). Acoperirea unui suport cu diferite repere se
poate face în m ai multe m oduri (bineîn țeles că este exclus ă orice suprapunere total ă sau parțială a
reperel or).
O modalitate de acoperire a unui suport poartă num ele de RE ȚETĂ DE C ROIRE. După
decuparea reperului din suport conform unei rețete rămâne un REST ce nu m ai poate fi utilizat.
Problem a constă în a alege acele re țete de cro ire prin care să se obțină reperele în cantit ățile
dorite cu MINIMUL POSIBIL de rest .

FORMALIZAREA MATEMATIC Ă

Să încep em prin a d escrie modelul UNIDIME NSIONAL de croire. Reperele vor fi
identificate prin ni ște num ere întregi reprezentând l ungim ea lor într-o unitate de m asură adecvată.
Fie m = numărul de repere dis tincte care trebu ie tăiate și
• l1, l2,…, lm = lungim ile lor;
• L = lungim ea suportului din care se taie reperele.
O rețetă de croir e se ide ntifică printr-un vector m dimensional cu com ponente în tregi (a1, a2,
…, am), unde ai = numărul de rep ere i (deci cu lu ngim ea li) ce rezu ltă prin tăierea con form rețetei.
Evident: a1l1 + a2l2 + … + amlm ≤ L , iar L – (a1l1 + a2l2 + … + amlm) = res tul rețetei = ri.

• ρ1, ρ2, …, ρn = rețetele posibile de croire a reperelor din suportul dat.
a1j
ρj = a2j
…
amj

• b1, b2, …, bm = cantitățile în care rep erele trebuie executa te.
• r1, r2,…, rn = restu rile inutilizab ile ce rezu ltă din aplica rea O DAT Ă a rețetelor ρ1, ρ2,
…, ρn.
În activitatea de producere a cantităților nece sare de repe re fieca re rețetă va fi aplicat ă de un
număr de ori, posibil zero.

• xj = numărul de aplic ări ale rețetei ρj = MULTIPLICITATEA re țetei ρj.

Restul to tal rezult at din aplicarea re țetelo r ρ1,…, ρn cu m ultiplic itățile x1,…, xn este dat de
expresia:
f = r1x1 + r2x2 + … + rnxn (5)

Condiția de realizare a cantit ăților ce rute de repe re se tr anscrie astf el:

5

( 6)



=+…++=+…++=+…++
m n mn 2 m2 1 m12 n 2n 2 22 1211 n 1n 2 12 111
b xa xa xa…b xa xa xab xa xa xa

având în vedere sem nificația lor, va riabile le x1, …, xn satisfac:

xj ≥ 0 , j = 1, …, n (7)
xj = ÎNTREGI , j = 1, …, n (8)

Problem a croirii unidimensionale constă în dete rminarea m ultiplicităților xj care satisfac (6),
(7) și (8) și care minimizează obiectivul (5).
Adunând (5) și (6) membru cu membru obținem :

( Σ ai1 + r1 )x1 + ( Σ ai2 + r2 )x2 + … + ( Σain + rn ) xm = Σ bi + f

L L L

sau (9) L( x1 + x2 + … + xn ) = Σ bi + f

Fie funcția g = x1 + x2 + … + xn (10)
care indic ă numărul total de supor ți tăiați. Relația (9) devin e:
f = g @ L – Σ bi ⇔ g = 1/L(Σbi + f ) ⇒ (min)f = (m in)g. (11)

Relația (11) arat ă că dacă în lo cul minimizării res tului total se u rmărește m inimizarea
numărului de supor ți tăiați, se obține o problem ă echiv alentă în sensul c ă cele dou ă problem e au
aceeași soluție optimă.
Problem a croirii bidim ensionale este form al identică cu cea unidim ensională. Particularitatea
problem ei croirii rezid ă în numărul extrao rdina r de m are al rețetelor posibile de croire – presupuse
cunoscute în for malizarea m atematică. În realitate, chiar și în cazul unidim ensional m ai simplu,
rețetele de croire asociate unui set dat de repere și unui anum it suport din care se croiesc acestea, nu
sunt cunoscute . Generarea aces tor rețete este o p roblemă combinato rială delicată.

2. O problem ă de repartiz are a investi țiilor

O firmă are n proiecte p e care ar dori s ă le realizeze într-un r ăstimp de m ani, dar din cauza
bugetului s ău lim itat num ai o parte pot fi alese. Proiectul j aduce firm ei un câștig es timat la cj $ și
necesită investiții anuale în valoare de aij $, cu i = 1,…, m .
Capitalul disponibil pentru anul i este bi. Se pune problem a de a alege a cele pro iecte care s ă
aducă firm ei un câștig total (m axim) cu condi ția nedepășirii capitalului disponibil anual.

6

FORMALIZAREA MATEMATIC Ă

Introducem variabilele binare xj = 1 , dac ă proiectul j este admi s;
0 , altfel.

Obținem o problem ă de program are binară:

(m ax)f = Σ cjxj
aij xj ≤ bi , i = 1, …, m ∑
=n
j1
xj ∈ [0,1]

3. Problema ordonan țării reperelor pe ma șini

Ipoteze: n repere ce trebuie prelucrate pe m mașini.

Fiecare reper neces ită cel mult o opera ție pe fiec are m așină. Fie pik timpul necesar prelucr ării
reperu lui i pe mașina k. Variabilele de decizie ale problem ei vor fi:
xik = m omentul d e începere a prelucr ării reperulu i i pe mașina k. Se presupune c ă
program area începe de la m omentul 0.

Condiții:

1. Nu se pot program a două repere p entru a fi prelucrate pe acela și utilaj; aceas ta îns eamnă
că pentru oricare ar fi reperele i, j și utilajul k: xik – xjk ≥ pjk sau xjk – xik ≥ pik, i, j =1,…, n, i ≠ j, k =
1,…, m. (12)

2. Pentru fiecare reper o perațiile treb uie execu tate într-o anu mită ordine:

fie rijk = 1 dac ă a j-a preluc rare a reperu lui i se face pe utilaju l k
0 în caz con trar.

Atunci m omentul de începere al opera ției j la reperul i este: Σrijkxik .

Rezultă restricția Σrijk(xik + pik) ≤ Σri,j+1,k⋅xik, j =1,…, m-1. (13)

Există diverse func ții obiectiv. Cea obi șnuită constă în (m in) sum ei momentelor de începere
a ultim ei operații la fiecare job adic ă:

(min)f = ΣΣrimk⋅xik . (14)

Bineîn țeles dihotom ia (12) se înlocuie ște cu restricții STAS prin folosirea de variabile bivalente.
7

Problem a (12), (13), (14) este o problemă de un tip nou: ea con ține atât variab ile continue cât și
variabile bivalente. Spunem că este o problem ă de program are MIXT Ă.

1.3 Generalit ăți privind metode de rez olvare a problemelor de programare
liniară întreagă

A) Metode de tip plan de sec țiune;
B) Metode bazate pe enum erarea im plicită a soluțiilor în tregi;
C) Metode specifice create pentru rezolv area uno r clase de p rograme specifice.

Înainte de a expune bazele te oretice ale acestor m etode să exam inăm următorul exem plu:

(max)f = 3×1 – x2
3×1- 2×2 ≤ 3
(ILP) 5 x1 + 4×2 ≥ 10 (LP)
2×1 + x2 ≤ 5
x1,2 ≥ 0
x1,2 întreg i

Ignor ăm condiția de integ ritate și rezolvăm cu ajutorul sim plex-ului problem a relaxată (LP).
Adăugăm variab ilele de abatere și artificiale necesare ob ținând:

3 x1- 2×2 + y1 =3
5 x1 + 4×2 -y2 +z =10
(FBLP) 2 x1+ x2 +y3 =5
(m ax)f =3×1 – x2 – M⋅z, toate variabilele ≥ 0

B CB VVB x1 x 2 y 1 y 2 y 3 z
y1
z
y3 0
-M
0 3
10
5 3 -2 1 0 0 0
5 4 0 -1 0 1
2 1 0 0 1 0
f -10M -3-5M 1-4M * M * *
x1
z
y3 3
-M
0 1
5
3 1 -2/3 1/3 0 0 0
0 22/3 -5/3 -1 0 1
0 7/3 -2/3 0 1 0
f -5M+3 * -22/3M-1 5M/3+1 M * *
x1
x2
y3 3
-1
0 16/11
15/22
31/22 1 0 2/11 -1/11 0
0 1 -5/22 -3/22 0
0 0 -3/22 7/22 1
F 81/22 * * 17/22 -3/22 *
x1
x2
y2 3
-1
0 13/7
9/7
31/7 1 0 1/7 0 2/7
0 1 -2/7 0 3/7
0 0 -3/7 1 22/7
f 30/7 * * 5/7 * 3/7

x1 +1/7y 1 +2/7y 3 = 13/7
x 2-2/7 y1 +3/7y 3 = 9/7
-3/7y 1+ y 2 +22/7y 3=31/7

8

x1 + 1/7y 1 + 2/7y 3 = 1 + 6/7 ⇒ 1/7y 1 + 2/7y 3 – 6/7 = 1- x 1

1-x 1 ∈ Ζ (în orice x între g) ⇒ 1/7y 1+2/7y3-6/7 ∈ Ζ

Dacă 1-x 1 < 0 ⇒ 1- x 1 ≤ -1 ⇒ 1/7y1 + 2/7y 3 – 6/7 ≤ -1 ⇒ 1/7y 1+2/7y 3 ≤ -1/7 care
contrazice ipoteza c ă y1,3 ≥ 0. Deci 1-x1 ≥ 0 adică 1/7y 1+2/7y 3-6/7 ≥ 0.
Soluția optimă fracționară curentă nu verific ă această restricție; prin construc ție oricare
soluție întreagă o verifică.

A) Ideea metodei p lanului de sec țiune const ă în a adăuga aceas tă rest ricție la p roblem a
curentă și de a reoptim iza. Prin adăugare m ulțimea solu țiilor problem ei rela xate LP se micșorează în
timp ce m ulțimea soluțiilor întregi r ămâne aceeași. Este posibil c a prin adăugarea de asemenea
restricții care taie succesiv por țiuni din poliedrul convex al solu țiilor adm isibile a le prob lemei
relax ate, ALP, dar nu altereaz ă mulțimea soluțiilor întregi, optimul întreg s ă devină vârf al
poliedrului pe care se face reoptimiz area curent ă. În aceast ă situație acest optim întreg va f i sigur
detectat de m etoda Si mplex ca fiind solu ția optimă a probl emei de reoptim izare cu rente. Teoria ne
asigură că este întotdeau na așa!
Deci, în principiu, m etoda planului de sec țiune reduce rezolvarea unei (PLI) la o suit ă de
procese de reoptim izare liniar ă prin adăugare s uccesivă de noi restric ții, neverificate de optimul
fracționar curent, dar verificate de orice solu ție adm isibilă întreagă.
Pentru a vedea efectul introducerii restric ției
1/7y 1+2/7y3-6/7 ≥ 0
asupra m ulțimii soluțiilor adm isibile ale prob lemei (LP), obs ervăm că ea este echivalent ă cu :
1-x 1 ≥ 0 ⇔ x1 ≤ 1 restricția (4)
Prin adăugarea ei, poligonul ABCD se reduce la EFCD.

B A

9

Să procedăm la reoptimizare pentru determ inarea solu ției op time:

y4 = 1/7y 1 + 2/7 y 3 – 6/7 ⇔ -1/7y 1 – 2/7 y 3 + y 4 = -6/7

După reoptim izare se ob ține op timul fracționar F = [x 1 = 1, x 2 = 5/4], cu f = 7/4

În continuare din ecuațiile dedus e din tabelul Simple x optim alegem pe cea al c ărei termen
liber are p artea fracționară maximă.

3 -1 0 0 0 0
7/4= 1/4y 2+y3-3/4y 4
1+3/4=1/4y 2+y3-y4+1/4y 4⇒
1/4y 2+1/4y 4-3/4 = 1-y 3+y4

1/4y 2+1/4y 4-3/4 ≥ 0

1-y 3+y4 ≥ 0 ⇒
1+2x 1+2x 2= 5+1-x 1 ≥ 0 ⇒

x 1+x2≥ 3

Reoptim izăm:
y5 = 1/4y 2+1/4y 4-3/4 ⇒
-1/4y 2-1/4y 4+y5= -3/4

Adăugăm această restricție
la tabe lul simplex optim și aplicăm
simplexul dual

Într-o singur ă iterație s-a
obținut optimul întreg, punctul
M = [x 1 = 1, x 2 = 2], cu f = 1.

B CB VVB x1 x 2 y 1 y 2 y 3 y 4
x1
x2
y2
y4 3
-1
0
0 13/7
9/7
31/7
-6/7 1 0 1/7 0 2/7 0
0 1 -2/7 0 3/7 0
0 0 -3/7 1 22/7 0
0 0 -1/7 0 -2/7 1
f 30/7 * * 5/7 * 3/7 *
x1
x2
y2
y3 3
-1
0
0 1
0
-5
3 1 0 0 0 0 1
0 1 -1/2 0 0 3/2
0 0 -2 1 0 11
0 0 1/2 0 1 -7/2
f 3 * * 1/2 * * 3/2
x1
x2
y1
y2 3
-1
0
0 1
5/4
5/2
7/4 1 0 0 0 0 1
0 1 0 -1/4 0 -5/4
0 0 1 -1/2 0 -1/2
0 0 0 1/4 1 -3/4
f 7/4 * * * 1/4 * 17/4
y5 -3/4 -1/4 -1/4
x1
x2
y1
y3
y2 3
-1
0
0
0 1
2
4
1
3
f 1

1.4 Algoritm de tip plan de sec țiune pentru rez olvarea problemelor de
programare liniar ă în numere întregi (GOMORY, 1958)

Consider ăm problem a:
A⋅x = b A⋅x = b
(ILP) x ≥ 0 , x ÎNTREG (LP) x ≥ 0
(max) f = c⋅x (max)f = c⋅x

10

coeficienții lui A și ai lui b sunt întregi.
Fie AILP ⊂ A LP mulțimile de soluții adm isibile ale c elor două problem e. Vom presupune c ă
(LP) ar e optim finit x*. Dacă x* are toate com ponentele în tregi atun ci x* este și soluție optimă a lui
(ILP). În caz contrar, x0 – dacă există – NU se num ără printre vârfurile (punctele extrem e) ale
poliedrului ALP și deci nu va putea fi detect at de algoritm ul Sim plex!

Ideea algoritmului este:

Presupunem că x* nu are toate com ponentel e întregi. Se construie ște o rest ricție neverificată
de optim ul fracționar x* dar verificat ă de orice solu ție adm isibilă într eagă. Se adaug ă aceas tă
restricție problemei originale r enotată LP 0 și se r eoptim iozea ză.
Fie x** soluția optimă a problem ei augm entată notată LP 1. Datorită modului în care a fost
definită restricția suplimentar ă avem

AILP ⊂ ALP1 ⊂ ALP0 = ALP

Dacă nici x** nu are toate com ponentele întreg i se repetă procedeul: se construie ște o nouă
restricție neverificat ă de x** dar verificat ă de soluțiile adm isibile în tregi. Se adaug ă restricția la L P1
obținând o problem ă de program are liniară, LP 2. Prin construc ție:

AILP ⊂ ALP2 ⊂ ALP1 ⊂ ALP0 = ALP

Prin reoptim izare se decide dacă LP 2 are sau nu soluție optimă. Teoria ne asigur ă că în
anumite condi ții, într-un număr finit de pași se ajunge la o problem ă de program are liniară, LP k-1 a
cărei soluție optimă xk(*) are toate compone ntele întregi și deci rep rezintă soluția optimă a lui (ILP).
Din punct de vedere geom etric fiecare nouă restricție îndepărtează o porțiune din mulțimea
soluțiilor admisibile ale problem ei pr eceden te de unde den umirea de TĂIETURI acordat ă aces tor
restricții sup limentare.
Să vedem acum modul în care se genereaz ă aceste tăietur i:

Se aplică problem ei de program are liniar ă (LP) = (LP 0) algoritm ul Simplex. Fie B baza
optim ală în raport cu care avem :

I ⊂ {1, 2, …, n}= m ulțimea indicilo r variab ilelor bazice;
J = {1, 2, …, n} – I = m ulțimea indicilor variabilelor nebazice.

Prin înmulțirea s istem ului A⋅x = b la stâng a cu B-1 explicităm variabilele bazice ( xi), i ∈ I în
funcție de cele secundare ( xj), j ∈ J

xi + ∑
∈Jjaij xj = bi (15)

Term enii liberi (bi), i ∈ I for mează coloana VVB a tabelu lui Sim plex optim iar coef icienții
(aij), i ∈ I formeaz ă coloana A j a acelu iași tabe l.
Valorile xi* = bi, i∈I, reunite cu x j* = 0, j ∈ J form ează soluția optimă x* a problem ei
LP=LP 0.
11

Să presupunem că cel puțin una din m ărimile bi este fracționară (altm interi x* = x0 = sol uția
optimă a program ului (ILP)). Fie aceasta br .
Se știe că orice num ăr real a poate fi pus în form a a = [a] + {a}, unde:
[a] = partea întreag ă a lui a = ce l mai mare număr într eg ≤ a;
{a}= partea frac ționară a lui a adică a – [a] ⇒ 0 ≤ {a} < 1

Exem plu:

• a = 2,781 ⇒ [a] = 2 , {a}= 0,781
• a = -2,3 ⇒ [a]= -3, {a}= 0,7

În general, a∈Z dacă {a}= 0.

Aplicăm coeficien ților re stricției de rang r

br = x r + ∑
∈Jjarj xj (16)

descom pune rea de m ai sus:

[br] + {br}= x r + ∑
∈Jj ([arj] + {arj})⋅xj (17)

Ipoteza făcută asupra lui br implică 0 < {b r}< 1 (18)

[br] – [∑
∈Jjarj]⋅xj – xr = ∑
∈Jj{arj}⋅xj – {br} (19)

Fie x) o soluție adm isibilă între agă a problem ei ILP. Atunci m embrul stâng al rela ției (19)
calcu lat în x) este un num ăr întreg

[br] – [∑
∈Jjarj] x)
j – x)
r ∈ Z (20)

În consecin ță, și membrul drept al acestei eg alități calculat în aceea și soluție este un num ăr
întreg:

{∑
∈Jjarj}x)
j -{br}∈ Z (21)

Practic demonstr ăm că

{∑
∈Jjarj}x)
j – {br} ≥ 0 (22)

12

Demonstra ție:

Presupunem prin absurd contrariul:

{∑
∈Jjarj}x)
j-{br} < 0 (23)
atunci din (19) rezult ă:

[br] – [∑
∈Jjarj] x)
j – x)
r < 0
și din (20) deducem :

[br] – [∑
∈Jjarj] x)
j – x)
r ≤ -1

Folosind din nou (19) deducem : ∑
∈Jj{arj}x)
j -{br} ≤ -1, adică ∑
∈Jj{arj}x)
j ≤ {br} – 1
Deoarece {arj}≥ 0, oricare ar fi j ∈ J membrul stâng este ≥ 0 în tim p ce mem brul drept este
< 0 deoarece { bi}< 1.
Contradic ția obținută demonstreaz ă inegalitatea (22).
Deoarece x a fost ales arbitrar urm ează că restri cția

{∑
∈Jjarj}xj ≥ {br} (24)
este verificat ă de orice soluție ad misibilă întreagă.
P.d.a.p. în soluția optimă neîn treagă x* avem x*j = 0, j∈J valori care introdus e în (22) duc la
{br} ≤ 0 în contradic ție cu ipoteza (18) potrivit c ăreia {br} > 0!
În consecin ță, inegalitatea (24) nu este verificat ă de optim ul fracționar x*.
Vom adăuga restric ția (24) la problem a LP obținând problem a augm entată – cu m+1 restric ții
– notată LP 1. Pentru reoptim izare transform ăm (24) în eg alitate introducând o variabil ă de ab atere
xn+1:
– Σ{arj}xj+ x n+1 = -{br}
adăugăm această restricție la tabe lul Sim plex curent:

B CB VVB A r A j(j∈J) An+1

xr
…

xn+1

Cr
…

0

br
……

-{br} . .
. .
1 arj
………………………………………………
. .
……… 0 ……… -{ arj} ……………

……
f f … * …… ∆j ………………… *

13

x i = bi, i∈I
x j = 0, j∈J
x n+1 = {-br} constitu ie o soluție de bază Dual admisibil ă pentru LP 1.

Utilizând Simplexul dual, dup ă una sau m ai multe ite rații se ajunge la solu ția optimă x** a
acestei prob leme după care se reia p rocedeul des cris an terior.

Restricția de rang r (16) din care am derivat t ăietura (24) se num ește RES TRICȚIE
GENERATOARE. Ea se caracterizeaz ă prin faptul c ă term enul ei lib er es te fracționar. În caz c ă mai
multe r estricții din (15) au term en liber frac ționar, restric ția generatoare va fi aleas ă astfel în cât
partea frac ționară {br} să fie cât m ai mare. Ceea ce es te curios este c ă cu aceas tă regulă care s -a
dovedit foarte util ă în p ractică, nu s-a putut dovedi convergen ța algoritmului. Pentru convergen ță
este necesar ă aducerea problem ei LP la o anum e for mă și aplica rea altei regu li privind restric ția
generatoare. Aceste transform ări destul de tehnice dar care nu m icșorează generalitatea
considera țiilor pot fi ignorate în exemplel e ilustrative care sunt de regul ă mici ca dimensiune.

Comentariu

Ideea algoritmului și demonstra ția convergen ței sunt datorate lui Ralph E. Gom ory (1958 –
1960). El a propus doi algoritm i pent ru rezolvarea problem elor cu to ate variabilele întregi, unul
denum it DISCRET cel ălalt CICLIC. Anterior am expus algoritm ul CICLIC. Tot Gomory a propus și
un algoritm pentru rezolvarea probl emelor MIXTE în care num ai o parte din variab ile sunt supuse
restricțiilor de integ ritate.
Experiența num erică acum ulată până în prezent degaj ă un sentim ent de incoerență în ceea
ce priv ește eficacitatea algor itmilor pe o problem ă sau alta. Într-o excelent ă monografie ap ărută în
1962 se semnala faptul c ă o problem ă cu 90 de variab ile a fo st rezo lvată foarte rap id în tim p ce alta
cu num ai 12 variabile nu a putut fi rezolvat ă nici după câtev a sute de itera ții.
S-a conturat din ce în ce m ai mult ideea c ă – spre deosebire de problem ele de program are
liniară în care metoda simplex s-a dovedit universal ă – problemele interne au fiecare structu ra lor
internă pentru care trebu ie creat un algoritm particular sau cel pu țin specializat unul general.
De asem enea, au fost dezvoltate puternic pro cedeele care, f ără a conduce la solu ția optimă,
conduc la solu ții suboptim ale acceptabile.

Exemplu numeric:

2×1 +x2 -x3 ≤4
4×1 -3x 2 ≤2
(ILP) -3x 1+2x 2+x3 ≤3
x1,2,3 ≥ 0, ÎNTREGI
(max)f= x 1-3x 2+3x 3

Rezolvare:

Aduce m (ILP) la form a bună în vederea aplic ării sim plex-ului:

14

2x 1 +x2 -x3 +x 4 = 4
4x 1 -3x 2 +x 5 = 2
(FSILP) = (FBILP): -3x 1+2x 2+x3 +x 6 = 3
x 1…6 ≥ 0, ÎNTREGI
(m ax)f = x 1-3x 2+3x 3

15

(min) [3/2 / 1/4 = 6, 5/2 / 1/4 = 10] = 6
B CB VVB x1 x 2 x 3 x 4 x 5 x 6
x4
x5
x6 0
0
0 4
2
3 2 1 -1 1 0 0
4 -3 0 0 1 0
-3 2 1 0 0 1
f 0 -1 3 -3 * * *
x4
x5
x3 0
0
3 7
2
3 -1 3 0 1 0 1
4 -3 0 0 1 0
-3 2 1 0 0 1
f 9 -10 9 * * * 3 x 7
x4
x1
x3 0
1
3 15/2
1/2
9/2 0 9/4 0 1 1/4 1
1 -3/4 0 0 1/4 0
0 -1/4 1 0 3/4 1
f 14 * 3/2 * * 5/2 3
x7 0 -1/2 0 -1/4 0 0 -1/4 0 1
Restricția generatoare:
9/4 x 2 + x 4 + 1/4x 5 + x 6 = 15/2
(2+1/4)x 2 + x 4 + 1/4x 5 = 7+1/2
1/4x 2 + 1/4x 5 -1/2 = 7 – 2 x2 – x4 – x6
⇒ tăietura 1/4×2 + 1/4x 5 -1/2 ≥ 0 (aducem la form a STAS utilizând x 7)

Notăm x 7 = 1/4x 2 + 1/4x 5 -1/2 ⇒ -1/4x 2 – 1/4x 5 + x 7 = -1/2.
Reoptim izând se ob ține:

B CB VVB
x4
x1
x3
x2 0
1
3
-3 3
2
5
2
f 11

Soluția cure ntă are toate com ponent ele întregi: x0
1 = 2, x0
2 = 2, x0
3 = 5, fmax = 11.