C A P I T O L U L I

PROGRAMARE ÎN NUMERE ÎNTREGI

§ 1. Specificul programării în numere întregi

Este binecunoscut faptul că modelarea prin programare liniară reprezintă un mijloc puternic şi eficace pentru studiul proceselor economice în vederea îmbunătăţirii performanţelor acestora.

O proprietate foarte importantă a variabilelor de decizie, dintr-un program liniar era aceea că, o dată cu două valori permise, puteau lua orice altă valoare intermediară; această proprietate „de a putea varia continuu” era esenţială în fundamentarea metodelor de determinare a soluţiilor optime.

Nu puţine sunt situaţiile practice, modelate cu ajutorul programării liniare în care unele variabile de decizie nu au sens economic decât dacă au numai valori întregi.

De exemplu, dacă outputul unei activităţi este măsurat în unităţi indivizibile este clar că valorile permise ale variabilei care indică nivelul activităţii respective trebuie să fie numere întregi. La fel, repartizarea personalului muncitor, al utilajelor sau al mijloacelor de transport pe diverse activităţi trebuie exprimată tot prin cantităţi întregi.

Exemplul 1.1 [4] Un fermier are nevoie de 107 funţi de îngrăşământ pe care îl poate procura fie în saci de 35 funţi la preţul de 14 $ sacul, fie în saci de 24 funţi a 12 $ fiecare. Obiectivul său este de a cumpăra cantitatea necesară de îngrăşământ la cel mai mic cost.

Notând cu x₁, x₂ numărul sacilor de 35 funţi, respectiv 24 funţi cumpăraţi de fermier, modelul situaţiei descrise arată astfel:

În modelul rezultat, condiţia „x₁, x₂ întregi” înseamnă pur şi simplu că fermierul nu poate cumpăra o jumătate sau o treime de sac; ori cumpără un sac întreg ori nu. Fără această condiţie avem de a face cu o problemă uzuală de programare liniară.

Poate mai importante sunt situaţiile în care trebuie luate decizii de tip „da sau nu” ca de exemplu:

• se poate aproba realizarea unui anumit proiect de dezvoltare ?

• se poate iniţia o activitate implicând un anumit cost fix de pregătire ?

• se poate amplasa o facilitate (unitate productivă, depozit, magazin) într-un anumit loc ?

Existând doar două posibilităţi, de a amplasa sau de a respinge, asemenea decizii pot fi reprezentate prin variabile cu numai două valori permise, 0 sau 1:

1, dacă decizia este afirmativă;

0, dacă decizia este negativă.

Exemplul 1.2 [7 ] În cadrul unui proiect mai general de extindere şi dezvoltare, conducerea unei firme studiază oportunitatea construirii unei noi fabrici fie în oraşul A, fie în oraşul B, poate chiar în amândouă şi a cel mult un depozit într-unul din cele două oraşe, alegerea amplasamentului fiind însă condiţionată de construirea unei fabrici în localitatea respectivă. În tabelul 1.1. sunt indicate: valoarea prezentă netă a diferitelor alternative, capitalul necesar acestor investiţii şi capitalul disponibil pentru întregul proiect de dezvoltare.

milioane $

Nr. crt.	Alternativa decizională	Variabila de decizie	Valoarea prezentă netă	Capitalul necesar
1	Construirea unei fabrici în A	x1	9	6
2	Construirea unei fabrici în B	x2	5	3
3	Construirea unui depozit în A	x3	6	5
4	Construirea unui depozit în B	x4	4	2
Capital disponibil				10

Tabelul 1.1.

Condiţiile specificate în proiectul de dezvoltare se formalizează astfel:

• cel mult un depozit poate fi construit: x₃ + x₄ ≤ 1

(deoarece x₃, x₄ nu pot lua decât valorile 0 sau 1, se elimină posibilitatea construirii a două depozite în ambele oraşe deoarece x₃ = 1, x₄ = 1 nu satisfac inegalitatea !)

• depozitul nu poate fi construit în lipsa unităţii productive: x₃ ≤ x₁, x₄ ≤ x₂

(este clar că x₁ = 0 implică cu necesitate x₃ = 0, etc.)

• încadrarea în capitalul disponibil: 6 x₁ + 3 x₂ + 5 x₃ + 2 x₄ ≤ 10

• maximizarea valorii prezente nete totale a obiectivelor care se vor realiza:

9 x₁ + 5 x₂ + 6 x₃ + 4 x₄ ® max

Rezultă următorul model matematic:

Observaţie: Dacă s-ar fi pus condiţia construirii unui singur depozit într-unul din cele două oraşe, atunci inegalitatea x₃ + x₄ ≤ 1 trebuie schimbată în x₃ + x₄ = 1.

Pentru cele ce urmează este necesar să precizăm câţiva termeni.

• variabilă continuă º variabilă care, o dată cu două valori permise poate lua orice altă valoare intermediară;

• variabilă întreagă º variabilă care nu poate lua decât valori numere întregi;

• variabilă bivalentă (booleană)ºvariabilă întreagă care nu poate lua decât valorile 0 sau 1;

• problemă de programare în numere întregi (pe scurt program întreg) º problemă de programare liniară care utilizează una sau mai multe variabile întregi. Problema se zice totală dacă toate variabilele sale sunt întregi şi mixtă dacă utilizează simultan şi variabile continue şi variabile întregi;

• problemă de programare bivalentă (sau program bivalent) – totală sau mixtă º problemă care utilizează variabile bivalente.

· Exemplul 1.2. arată că utilizarea variabilelor întregi aduce un plus de flexibilitate în modelarea unor situaţii practice. Această flexibilitate „costă” însă destul de mult, deoarece programele întregi sunt mult mai greu de rezolvat decât programele liniare uzuale (adică în variabile continue). Fără a intra deocamdată în amănunte este suficient să amintim că dacă în prezent a devenit o obişnuinţă rezolvarea unor programe liniare cu mii de variabile continue (fireşte utilizând programe comerciale de calculator), un program cu mai puţin de 100 variabile întregi poate cauza mari dificultăţi !

Pentru evitarea complicaţiilor se poate aplica următoarea schemă de rezolvare aproximativă a programelor întregi.

Se ignoră condiţia ca variabilele să ia numai valori întregi şi se rezolvă programul „relaxat” care este un program liniar uzual. Două situaţii sunt posibile:

• soluţia optimă a problemei relaxate are toate componentele întregi; aceasta va fi, evident şi soluţia optimă a programului întreg original;

• unele componente ale soluţiei optime a programului relaxat sunt fracţionare. În această situaţie componentele fracţionare vor fi rotunjite – inferior sau superior – la valori întregi, în ideea că soluţia optimă „întreagă” este situată „în apropierea soluţiei optime fracţionare”.

Operaţia de rotunjire trebuie astfel făcută încât rezultatul să fie o soluţie a problemei, adică să verifice restricţiile. este firesc să acceptăm soluţia continuă prin rotunjire, cel puţin ca soluţie suboptimală; în multe contexte practice acest lucru este justificat prin faptul că valorile permise variabilelor sunt suficient de mari astfel încât efectul rotunjirii să fie neglijabil.

Nu puţine sunt situaţiile în care strategia de rezolvare fie şi aproximativă prin rotunjirea soluţiei optime fracţionare nu este recomandabilă. Uneori se întâmplă ca numărul alternativelor de rotunjire să fie foarte mare implicând un volum apreciabil de calcule suplimentare pentru verificarea şi sortarea acestora. Pe de altă parte, pentru unele programe întregi în care variabilele iau valori destul de mici, ca de exemplu 0 sau 1, este posibil ca „distanţa” dintre optimul „întreg” şi cel „fracţionar” să fie atât de mare încât simpla rotunjire să nu ducă la o soluţie acceptabilă.

Exemplul 1.3 Pentru programul întreg din exemplul 1.1. soluţia optimă a programului relaxat:

are componentele:

Sunt evidente următoarele rotunjiri care conduc la soluţii admisibile:

A doua soluţie - mai bună – este totuşi „departe” de soluţia optimă întreagă:

§ 2. Domenii de aplicare ale programării în numere întregi. Exemple

Situaţiile practice a căror modelare necesită utilizarea variabilelor întregi sunt extrem de numeroase şi exemplele următoare nu acoperă nici pe departe această varietate. După cum vom vedea în următorul capitol, situaţiile combinatoriale pot fi modelate – cel puţin în principiu ca probleme de programări în numere întregi.

2.1. Problema monezilor Cum poate fi plătită o sumă de bani astfel încât:

• numărul tipurilor valorice de monezi utilizate la plată să nu depăşească o limită dată;

• numărul total al monezilor necesare plăţii să fie minim.

Pentru formalizare avem nevoie de următoarele notaţii:

S = suma de plată,

n = numărul total al tipurilor valorice de monezi disponibile pentru plată;

p = numărul maxim de tipuri valorice de monezi ce pot fi utilizate la plata sumei S;

a_j º valoarea monezii de tip j;

m_j º numărul monezilor de tip j disponibile în casă.

Introducem variabilele:

x_j = numărul monezilor de tip j utilizate la plata sumei S;

Rezultă următorul program întreg

0 ≤ x_j ≤ m_jy_j j=1, ...n

x_j ≥ 0 întregi; y_j Î {0, 1} j = 1, ...n

2.2. Alegerea proiectelor de investiţii O firmă este interesată în mai multe proiecte de investiţii pe care ar putea să le realizeze în câţiva ani dar, din cauza bugetului limitat, va trebui să se limiteze la o parte din ele. Proiectul j aduce firmei – în caz de finalizare – un profit estimat la c_j dolari j = 1, ... n şi necesită investiţii anuale în valoare de a_ij dolari i = 1, ... m. Capitalul disponibil pentru anul i este b_i. Se pune problema alegerii acelor proiecte care să aducă firmei un profit total maxim cu condiţia nedepăşirii capitalului disponibil anual.

Pentru formalizare introducem variabile bivalente

Obţinem programul bivalent:

x_j Î {0, 1} j = 1, ... n

Observaţie Utilizarea variabilelor bivalente ne permite să modelăm o serie de situaţii speciale. De exemplu:

· cel mult unul din primele trei proiecte poate fi acceptat: x₁ + x₂ + x₃ ≤ 1;

· numai unul din primele trei proiecte poate fi acceptat: x₁ + x₂ + x₃ = 1;

· nu poate fi acceptat proiectul 2 dacă proiectele 1 şi 4 sunt respinse: x₂ ≤ x₁ + x₄

etc.

2.3. Elaborarea programelor de producţie cu costuri de pregătire

Să considerăm programul liniar

x_j ≥ 0 j = 1, ... n

în care x₁, x₂, ... x_n reprezintă nivelul unor activităţi productive iar c₁, c₂, ...c_n sunt costurile unitare aferente. Ipoteza uzuală de liniaritate presupune proporţionalitatea directă între costul unei activităţi şi nivelul la care este operată activitatea respectivă. Există însă situaţii în care demararea unei activităţi necesită un cost de pregătire, independent de nivelul la care activitatea va fi operată. Costul activităţii j va avea forma:

Pentru a încorpora în modelul matematic anterior aceste elemente introducem următoarele bivalente

Rezultă programul mixt:

unde m_j reprezintă o limită superioară a nivelului x_j al activităţii j

x_j ≤ m_jy_j j = 1, ... n

x_j ≥ 0, y_j Î {0,1} j = 1, ... n

2.4 Stabilirea programului de zbor al avioanelor unei companii de transporturi aeriene

O companie de transporturi aeriene are în dotare mai multe avioane de diferite tipuri pe care îşi impune să le utilizeze cât mai bine pe rutele de transport utilizate de această companie.

Datele problemei:

m = numărul tipurilor de avioane;

n = numărul rutelor servite de companie;

c_i = capacitatea maximă de transport a unui avion de tipul i (nr. locurilor disponibile);

d_i = numărul avioanelor de tipul i disponibile;

b_j = numărul clienţilor potenţiali pe ruta j;

p_j = profitul companiei pe călător transportat pe ruta j;

a_ij = numărul de zboruri pe care un avion de tipul i îl poate face pe ruta j într-o perioadă (zi, decadă, lună);

q_ij = costul operării unui zbor al unui avion de tipul i pe ruta j

Obiectiv:

repartizarea avioanelor pe rute şi stabilirea numărului de zboruri ce trebuie efectuate la nivelul unei perioade astfel încât cererile de transport să fie raţional făcute la cel mai mic cost.

Variabile modelului:

x_ij = numărul avioanelor de tipul i rezultate pe ruta j;

y_ij = numărul de zboruri planificat a se realiza cu avioane de tipul i pe ruta j într-o perioadă.

Funcţia obiectiv. Avem două cazuri:

1) Se au în vedere numai costurile de operare ale diferitelor zboruri:

(2.1.)

2) La costurile de operare se adaugă şi costurile de „penalizare” pentru locurile „libere”. Pe ruta j numărul locurilor libere este dat de diferenţa astfel că expresia cheltuielilor de penalizare – identificat cu profitul pierdut – este:

Cheltuielile totale vor avea expresia:

astfel că funcţia obiectiv devine:

(2.2.)

expresia fiind o constantă ce nu afectează optimizarea.

Restricţii:

• încadrarea aparatelor repartizate în numărul disponibil de avioane

i = 1, ... m (2.3.)

• condiţia de realizare a zborurilor planificate în funcţie de numărul avioanelor repartizate

i = 1, ... m; j = 1, ...m (2.4.)

• satisfacerea cererilor de transport:

j = 1, ... m (2.5.)

Condiţii impuse explicit variabilelor:

x_ij ≥ 0, y_ij ≥ 0 întregi i = 1, ... m; j = 1, ... n (2.6.)

Ataşând condiţiilor 2.3. – 2.6. funcţiile obiectiv (2.1.) şi (2.2.) se obţin două programe întregi totale.

§ 3. Particularităţile mulţimii soluţiilor admisibile ale unui program întreg

Să considerăm următorul program întreg total (P) împreună cu programul relaxat (PL) – obţinut din (P) prin eliminarea cerinţei ca variabilele să ia numai valori întregi:

Programul întreg (P)

Programul relaxat (PL)

Ne propunem:

• să rezolvăm grafic cele două programe;

• să punem în evidenţă principalele proprietăţi ale mulţimilor de soluţii admisibile ale celor două programe. Analiza comparativă a acestor proprietăţi ne va permite degajarea – cel puţin la nivel de principiu – a unor metode de rezolvare (exactă) a programelor întregi.

Terminologie, notaţii:

• soluţie admisibilă º ansamblu de valori numerice (nu neapărat întregi) care verifică restricţiile şi condiţiile de nenegativitate;

• soluţie admisibilă întreagă º soluţie admisibilă cu toate componentele întregi;

• A_PL º mulţimea sluţiilor admisibile ale programului relaxat (PL);

• A_P º mulţimea soluţiilor admisibile întregi ale programului (P);

• soluţia optimă fracţionară ºsoluţia optimă a programului relaxat (PL), notată constant cu x*;

• optim fracţionar º valoarea f (x*) a funcţiei obiectiv în soluţia optimă fracţionară x*;

• soluţia optimă întreagă º soluţia optimă a programului întreg (P), notată constant cu x⁰;

• optim întreg º valoarea f (x⁰) a funcţiei obiectiv în soluţia optimă întreagă x⁰.

Vizualizăm mulţimile A_P şi A_PL

Reamintim că pentru reprezentarea grafică a mulţimii A_PL se fac următoarele operaţii:

· se reprezintă grafic dreptele: d₁ º 3 x₁ – 2 x₂ = 3

d₂ º 5 x₁ + 4 x₂ = 10

d₃ º 2 x₁ + x₂ = 5

şi se identifică semiplanele în care au loc cele trei restricţii şi cele două condiţii de nenegativitate.

A_PL va fi intersecţia celor cinci semiplane puse în evidenţă mai sus adică poligonul simplu haşurat DFGH

dreapta de nivel a funcţiei obiectiv

soluţia optimă ÎNTREAGĂ x⁰=(1,2)

optimul ÎNTREG f(x⁰)=1

soluţia optimă FRACŢIONARĂ

optimul FRACŢIONAR

Fig. 3.1.

Pentru a găsi soluţia optimă fracţionară se reprezintă grafic o dreaptă de nivel a funcţiei obiectiv şi se stabileşte direcţia de translatare a acesteia corespunzătoare maximizării. Rezultă º vârful F din desen optimul fracţionar având valoarea .

Prin simplă inspecţie se constată că mulţimea soluţiilor admisibile întregi ale programului (P) se compune din cinci puncte:

A_P = {A(1,2), B(0,3), C(0,4), D(0,5), E(1,3)}

Funcţia obiectiv f are valoarea maximă în A(1,2); prin urmare soluţia optimă întreagă este x⁰=(1,2) iar optimul întreg are valoarea f(x⁰) = 1.

Comparând mulţimile A_P şi A_PL se pot formula următoarele concluzii şi în cazul general:

1) A_PL este o mulţime în care fiecare punct este „înconjurat” de alte puncte din mulţimi oricât de apropiate. Ca urmare, teoria clasică a optimizării, bazată după cum se ştie pe posibilitatea efectuării unor deplasări infinitesimale în jurul unui punct, este direct aplicabilă.

Prin contrast, A_P este o mulţime rară, adică orice punct din ea posedă o vecinătate suficient de mică în care nu se mai află alte puncte din mulţime. Aplicarea teoriei amintite este în acest caz lipsită de sens.

2) A_PL este o mulţime convexă şi mai mult poliedrală având un număr finit de vârfuri. Aceste proprietăţi, plus liniaritatea funcţiei obiectiv, ne asigură că soluţia optimă fracţionară se găseşte într-unul din vârfuri (conform teoremei centrale a programării liniare). Cercetarea sistematică a mulţimii vârfurilor lui A_PL cu ajutorul algoritmului simplex conduce la optimul fracţionar într-un număr finit de paşi.

Cu rare excepţii, soluţia optimă întreagă – care este la urma urmei o soluţie admisibilă problemei relaxate – se găseşte în interiorul mulţimii A_PL şi ca urmare nu este nici măcar generată de către algoritmul simplex.

3) Să considerăm anvelopa convexă a mulţimii A_P, adică cea mai mică mulţime convexă care conţine A_P. În fig. 3.1. această anvelopă este reprezentată de poligonul dublu haşurat ABDE. Prin construcţie vârfurile anvelopei sunt soluţii admisibile întregi ale programului (P).

Dacă vom maximiza funcţia obiectiv f pe anvelopa convexă a soluţiilor admisibile întregi vom regăsi soluţia optimă întreagă x⁰.

În concluzie, putem rezolva o problemă de programare în numere întregi ca o problemă de programare liniară uzuală cu condiţia să ştim să descriem în limbaj de inecuaţii liniare anvelopa convexă a soluţiilor admisibile întregi.

În cazul studiat, această descriere este uşor de făcut: anvelopa ABDE se compune din soluţiile sistemului de inecuaţii

În cazul general descrierea este practic imposibil de făcut. Totuşi am putea recupera ceva din această idee: adăugând la problema relaxată PL un număr de restricţii suplimentare judicios alese, numite tăieturi, se pot îndepărta din A_PL o serie de porţiuni astfel încât soluţia optimă întreagă să devină vârf în mulţimea rămasă – vezi fig. 3.2.

Fig. 3.2

În acest fel soluţia optimă întreagă va putea fi detectată de către algoritmul simplex.

4) În cazul studiat A_P era o mulţime finită. Acest lucru se întâmplă şi în situaţii mai generale; de exemplu o problemă de programare cu n variabile bivalente nu poate avea mai mult de 2ⁿ soluţii admisibile întregi. Fără a influenţa generalitatea concluziilor, se poate presupune că orice program întreg are un număr finit de soluţii întregi.

Aceste constatări ne vor permite să înţelegem mai bune fundamentele, performanţele şi limitele metodelor de rezolvare a programelor întregi ce vor fi prezentate în următoarea secţiune.

§ 4. Metode de rezolvare ale programelor întregi

Următoarele consideraţii vizează programul întreg în formă standard cu m ecuaţii şi n variabile:

A x = b

x ≥ 0

x întreg (º cu componente întregi)

(max) f = cx

Û

(P)

x_j ≥ 0 j = 1,...n

x_j întregi

în care toate constantele a_ij, b_i, c_j sunt numere întregi.

Forma generală de mai sus acoperă şi cazul particular important al programelor bivalente prin introducerea restricţiilor x_j ≤ 1 , j = 1, ... n Ca şi până acum (PL) va desemna programul relaxat dedus din (P) prin eliminarea condiţiei de integritate impusă variabilelor.

Vom presupune în mod constant că mulţimea soluţiilor admisibile ale problemei (PL) este mărginită; în problemele practice această cerinţă poate fi întotdeauna asigurată. Rezultă imediat că (P) are un număr finit de soluţii admisibile întregi.

Deoarece coeficienţii funcţiei obiectiv sunt întregi şi optimul întreg va fi un număr întreg. Mai mult:

optimul întreg ≤ ë optimul fracţionarû

unde ë a û înseamnă rotunjirea întreagă inferioară a numărului real a.

Ne propunem în continuare să dăm o clasificare a metodelor şi algoritmilor de rezolvare a programului întreg general (P); observaţiile şi concluziile din secţiunea prezentată vor juca un rol esenţial.

1) O mare parte din aceste metode reduc rezolvarea programului întreg (P) la rezolvarea unei secvenţe finite şi programe liniare uzuale:

(PL₀ = PL), PL₁, PL₂, ... , PL_t

ultimul având drept soluţie optimă chiar soluţia optimă întreagă a programului original (P).

Pentru fiecare k = 1, 2, ... t programul (PL_k) se obţine din cel anterior prin adăugarea unei anumite restricţii suplimentare a cărei construcţie diferă de la metodă la metodă. Restricţiile suplimentare sunt astfel alese încât:

· să fie verificate de orice soluţie admisibilă întreagă a programului original (P);

· prin introducerea lor să îndepărteze porţiuni din mulţimea A_PL a tuturor soluţiilor admisibile ale relaxatei PL º PL₀ până când soluţia optimă întreagă devine vârf în mulţimea rămasă, putând fi astfel cunoscută de algoritmul simplex - vezi fig. 3.2.

Din acest motiv aceste restricţii suplimentare se mai numesc şi tăieturi sau plane de secţiune.

Din categoria algoritmilor bazaţi pe tăieturi fac parte algoritmii discret şi ciclic datoraţi lui Gomory (1960) şi algoritmul primal al lui Young şi Glover (1972).

2) Faptul că un program întreg are (sau poate fi făcut să aibă) un număr finit de soluţii sugerează un alt mod de rezolvare a programelor întregi bazate pe enumerarea totală sau parţială a acestor soluţii. Enumerarea totală este evocată doar ca posibilitate pentru că numărul soluţiilor admisibile întregi, deşi finit este de regulă foarte mare.

Schemele de enumerare parţială determină soluţia optimă întreagă generând efectiv doar o parte a mulţimii soluţiilor admisibile întregi, soluţiile negenerate fiind recunoscute implicit ca neoptimale.

Domeniul predilect de aplicare a metodelor de enumerare îl constituie programarea bivalentă. Un exemplu reprezentativ îl constituie algoritmul aditiv al lui Balaş (1965).

3) Punerea în evidenţă a soluţiei optime întregi x⁰ – situată de regulă în interiorul mulţimii soluţiilor admisibile ale problemei relaxate – se poate face şi în următorul mod (Dakin, Driebeck, 1964).

Să presupunem că am rezolvat problema relaxată PL, cu ajutorul algoritmului simplex obţinând soluţia optimă fracţionară x*. Dacă x* are toate componentele întregi, am terminat:

x* º x⁰ º soluţia optimă întreagă a programului original (P)

În caz contrar, una sau mai multe din componentele ale soluţiei x* nu sunt întregi; să presupunem de exemplu că este fracţionar. Este clar atunci că soluţia optimă întreagă căutată va verifica una din următoarele inegalităţi mutual exclusive:

(unde s-a notat cu ëaû º partea întreagă a numărului real a ).

Considerăm programele liniare obţinute prin extinderea relaxatei PL cu fiecare din cele două inegalităţi:

PL PL

PL₁ º PL₂ º

Vom spune că am ramificat problema (PL) după variabila x₁.

A_{PL 1}

A_{PL 2}

Fig. 4.1.

Este uşor de arătat că:

· Mulţimile de soluţii admisibile A_{PL 1} şi A_{PL 2} ale celor două programe noi sunt submulţimi stricte în A_PL.

· A₁ È A₂ = A_P şi A₁ Ç A₂ = Ø

unde A₁, A₂ sunt mulţimile de soluţii admisibile întregi ale programelor PL₁ şi PL₂. În particular soluţia optimă întreagă a programului original (P) se găseşte într-una (şi numai în una) din mulţimile mai mici A_{PL 1} sau A_{PL 2} vezi figura 4.1.

Rezolvăm în continuare PL₁; putem face acest lucru prin reoptimizare. Să presupunem că PL₁ este compatibilă; în soluţia sa optimă, notată x^{* 1} prima componentă va fi cu siguranţă întreagă: .

În ipoteza ca a doua componentă este fracţionară vom deriva alte două noi programe liniare după modelul de mai sus:

PL₁ PL₁

PL₁₁ º PL₁₂ º

Dacă soluţia optimă întreagă căutată este soluţie admisibilă pentru programul PL₁ atunci cu siguranţă ea se va găsi în una din mulţimile de soluţii admisibile ale celor două programe rezultate prin ramificare.

În principiu, reunificarea poate continua de la oricare din problemele PL₁₁, PL₁₂ sau PL₂, condiţiile de ramificare fiind acelea ca programul în cauză:

· să fie compatibil (adică să aibă soluţii admisibile);

· soluţia sa optimă să aibă cel puţin o componentă fracţionară.

De regulă, ramificarea se face după prima variabilă cu valoare fracţionară sau după variabila cu cea mai mare parte fracţionară.

Pentru înţelegerea metodei vom vizualiza procesul de ramificare printr-un graf arbore T ale cărui moduri sunt diferitele probleme rezultate din ramificare. Nodurile terminale (adică nodurile din care nu s-a mai efectuat ramificarea) sunt fie probleme incompatibile fie probleme cu soluţii optime întregi. Cu excepţia rădăcinii (PL) fiecare nod din T are un unic predecesor. Orice nod care nu este nod terminal are doi succesori.

Introducem următoarele variabile:

x_CMB (vector) care reţine cea mai bună soluţie admisibilă întreagă la un moment sau altul al derulării procesului de ramificare

z_CMB, care reţine valoarea funcţiei obiectiv în x_CMB.

La start: x_CMB = Ø z_CMB = - ¥

Figura 4.1

Fiecare nod PL_a al arborelui T – unde a este o succesiune de 1 şi 2 – va avea ataşată o margine superioară:

z_a º rotunjirea întreagă inferioară a optimului problemei PL_a în cazul în care aceasta este compatibilă.

Este clar că dacă soluţia optimă întreagă x⁰ se află printre soluţiile admisibile ale problemei PL_a atunci:

z_CMB ≤ f (x⁰) º optimul întreg ≤ z_a

Prin urmare, dacă pentru o problemă PL_a rezultată din ramificare, avem:

z_a ≤ z_CMB

nu mai are nici un rost să ramificăm PL_a, deoarece printre eventualele sale soluţii admisibil întregi nu există nici una mai bună decât actuala x_CMB !

Arborele T nu există de la început. La start el se reduce la rădăcina (PL) şi în continuare primeşte noi noduri şi arce de legătură în funcţie de problemele rezultate din ramificare şi efectiv rezolvate.

Metoda de rezolvare a unui program întreg succint expusă mai sus va fi explicată mai în detaliu pe următorul exemplu:

START

· Se iniţializează: z_CMB = - ¥ şi x_CMB = Ø (locaţia vidă)

· Se rezolvă cu algoritmul simplex relaxata problemei (P):

(max) f = 5 x₁ + 3 x₂

- x₁ + 2 x₂ ≥ 2

(PL) x₁ – x₂ ≤ 2

2 x₁ + 2 x₂ ≤ 7

x₁, x₂ ≥ 0

· Se găseşte soluţia optimă fracţionară:

· Se conchide că optimul întreg nu poate depăşi marginea superioară:

· Variabila după care se face ramificarea va fi alesă după criteriul „părţii fracţionare mai mari”; în cazul de faţă este vorba de variabila x₂.

Iteraţia 1 Se rezolvă cu algoritmul simplex programul liniar (PL₁) dedus din (PL) prin adăugarea restricţiei x₂ ≤ 1.

· Se găseşte soluţia întreagă x₁ = 0, x₂ = 1; f = 3 pe care o reţinem:

x_CMB = (0, 1) z_CMB = 3

Ştim acum că optimul întreg este cel puţin 3. Revenim la problema (PL).

Iteraţia 2 Se rezolvă cu algoritmul simplex programul liniar (PL₂) dedus din (PL) prin adăugarea restricţiei x₂ ≥ 2.

· Se găseşte soluţia fracţionară

· Se conchide că soluţiile admisibile întregi ale problemei (PL₂) care sunt şi soluţii ale problemei iniţiale (P) nu pot oferi funcţiei obiectiv o valoare mai mare decât marginea:

· Ramificăm după variabila x₁.

Iteraţia 3 Se rezolvă problema (PL₂₁) obţinută din PL₂ adăugând restricţia x₂ ≤ 1.

· Rezultă soluţia fracţionară

· Dacă soluţia optimă a programului (P) s-ar găsi printre soluţiile întregi ale problemei PL₂₁, optimul întreg n-ar depăşi marginea .

· Ramificăm după variabila x₂.

Iteraţia 4 adăugăm la (PL) restricţia x₂ ≤ 2, obţinând un nou program liniar PL₂₁₁. Rezolvarea lui conduce la soluţia întreagă x₁ = 1, x₂ = 2, f = 11 evident mai bună decât soluţia întreagă „depozitată” în x_CMB. În consecinţă actualizăm:

x_CMB = (1,2) z_CMB = 11

Conchidem că optimul întreg al problemei originale (P) este mai mare sau egal cu 11.Revenim la problema PL₂₁.

Iteraţia 5 De această dată adăugăm la PL₂₁ restricţia x₂ ≥ 3. Programul PL₂₁₂ rezultat are soluţia fracţionară

Să observăm că eventualele soluţii întregi ale acestei probleme nu pot oferi funcţiei obiectiv o valoare superioară marginii cum valoarea funcţiei obiectiv în cea mai bună soluţie întreagă găsită până acum este chiar 11, conchidem că ramificând PL₂₁₂ nu vom găsi soluţii întregi mai bune decât actuala x_CMB. În consecinţă ne întoarcem din nou la problema PL₂₁.

Recapitulând, studiul problemei PL₂₁ a produs o soluţia întreagă care a fost reţinută precum şi concluzia că PL₂₁ nu are soluţii întregi mai bune decât cea găsită. Ne întoarcem la problema PL₂ din care am derivat PL₂₁.

Iteraţia 6 Adăugăm acum la PL₂ restricţia x₁ ≥ 2. Noul program PL₂₂ se dovedeşte a fi incompatibil. Ne întoarcem din nou la problema PL₂ cu concluzia că actuala x_CMB este cea mai bună soluţie întreagă a sa. Mai departe, revenim la problema PL din care am derivat PL₂.

În acest moment putem spune că am examinat – direct sau indirect - toate soluţiile întregi ale problemei (P), deoarece acestea erau, fie soluţii întregi ale problemei PL₁ deja studiate, fie ale problemei PL₂ de asemeni examinate.

Soluţia întreagă reţinută în x_CMB este din cea mai bună soluţie întreagă adică este soluţia optimă a problemei originale (P).

Comentariile de mai sus sunt sintetizate în arborele T din fig. 4.2.

Ordinea de rezolvare a problemelor:

PL ® PL₁ ® PL₂ ® PL₂₁ ® PL₂₁₁ ® PL₂₁₂ ® PL₂₂

Soluţia optimă întreagă: x⁰ = x_CMB = (1, 2); Optimul întreg f (x⁰) = 11

Observaţii 1) Utilitarul QM ramifică o problemă după variabila cu cea mai mare parte fracţionară !

2) Utilitarul QM opreşte ramificarea unui nod PL_a numai dacă z_a < z_CMB în ideea găsirii tuturor soluţiilor admisibile întregi. În cazul de faţă şi nodul PL₂₁₂ a fost ramificat ! vezi fig.4.3

Un nod al arborelui T din care ramificarea poate continua se numeşte nod activ; altminteri el se va numi nod mort. Din denumire rezultă că algoritmul se opreşte în momentul în care rădăcina PL este declarată nod mort.

Fig 4.3

Principalele dezavantaje ale metodei descrise sunt:

·creşterea foarte rapidă, chiar explozivă a numărului problemelor de rezolvat şi de aici a volumului de calcule o dată cu creşterea dimensiunilor programului original şi mai cu seamă a numărului de variabile întregi;

·comportare impredictibilă pe probleme de dimensiuni apropiate: arborele problemelor rezolvate poate fi extrem de „stufos” pentru o problemă şi foarte simplu pentru o alta.

În practică, metoda se conbină cu alte procedee (cum ar fi metoda planelor de secţiune) care pot oferi rapid soluţii admisibile întregi suficient de bune micşorându-se astfel drastic numărul ramificărilor.

Algoritmul descris este o specializare a unei metode mai generale denumite branch & bound.

În principiu această metodă ramifică adică partiţionează mulţimea în care se caută un anumit element – numit element optimal – în părţi mai mici pe care le mărgineşte, aceasta însemnând optimizarea funcţiei obiectiv pe fiecare din părţile rezultate. Unele din aceste părţi sunt ramificate şi mărginite în continuare. Nu sunt ramificate acele părţi care nu conţin în mod sigur soluţia optimă căutată.

Ideea metodei B & B este de a găsi elementul optimal fără a inspecta toate elementele între care acesta se găseşte; de aceea se spune că B & B este o schemă de enumerare parţială.

§ 5. Întrebări şi probleme

1. Enumeraţi sursele de apariţie ale modelelor de programare în numere întregi.

2. Explicaţi termenii: relaxata unui program întreg, soluţie optimă fracţionară, soluţie optimă întreagă, optim fracţionar, optim întreg.

3. Explicaţi principiul metodelor de rezolvare a programelor întregi bazate pe tăieturi.

4. Explicaţi – eventual pe baza unui exemplu - metoda Branch & Bound.

5. În rezolvarea unui program liniar în numere întregi (P) în care funcţia obiectiv se maximizează s-a ajuns la următorul arbore al programelor liniare efectiv rezolvate:

Figura 5.1

a) Precizaţi soluţia optimă fracţionară x^* şi f(x^*) şi soluţia optimă întreagă x⁰ şi f(x⁰);

b) Indicaţi pe arcele arborelui restricţiile după care s-a făcut ramificarea;

c) În ce ordine au fost rezolvate cele cinci probleme?

d) De ce nu s-a continuat ramificarea din nodul (PL₂) ?

5. Se consideră programele întregi:

Pentru fiecare din ele:

a) reprezentaţi grafic mulţimea soluţiilor admisibile ale problemei relaxate;

b) puneţi în evidenţă soluţiile admisibile întregi şi acoperirea convexă a acestora;

determinaţi grafic soluţiile optime fracţionară şi întreagă precum şi optimele fracţionar şi întreg.

6. Din produsul B sunt necesare cel puţin b unităţi. Produsul se poate obţine pe două instalaţii I₁ şi I₂ dar numai în cicluri complete de fabricaţie ( şi aceasta datorită unei operaţii de coacere prevăzută în tehnologia de fabricaţie). Pe fiecare ciclu instalaţia I₁ produce p₁ unităţi din B iar I₂ produce p₂ unităţi din B. Un ciclu de fabricaţie durează a₁ ore pe I₁ şi a₂ ore pe I₂. Fondurile de timp disponibil ale celor două instalaţii sunt de F₁ ore respectiv F₂ ore. Costurile de fabricaţie se ridică la c₁ u.m. (unităţi monetare) pe I₁ şi c₂ u.m. pe I₂ pe fiecare ciclu. Scrieţi un program întreg pentru producerea cantităţii minimale B cu cheltuieli totale minime. Indicaţie: se vor lua ca variabile de decizie numărul ciclurilor de fabricaţie planificate a se realiza pe cele două instalaţii.

7. Un produs complex P se compune din 4 unităţi din componenta A şi 3 unităţi din componenta B. Componentele A şi B pot fi realizate prin trei procese de fabricaţie diferite în cadrul cărora se utilizează resursele R şi S disponibile în cantităţile de 100 unităţi respectiv 200 unităţi. Realizarea unui proces de fabricaţie necesită anumite cantităţi din resursele R şi S şi are ca rezultat producerea anumitor cantităţi din componentele A şi B conform datelor din următorul tabel:

Proces	Intrări (unităţi specifice)		Ieşiri (unităţi specifice)
	din R	din S	din A	din B
1	8	6	7	5
2	5	9	6	9
3	3	8	8	4

Tabelul 5.1

Să se scrie un program întreg pentru determinarea numărului maxim de produse complexe P ce pot fi realizate din resursele date. Indicaţie: se va nota cu x₁ , x₂ , x₃ numărul de procese 1,2 respectiv 3 necesare şi cu y numărul produselor complexe P rezultate.

8. Folosiţi utilitarul QM pentru rezolvarea programului întreg:

(Este vorba de modelul matematic al problemei precedente în care variabila y a fost renotată x₄) Interpretaţi soluţia obţinută.

9. Rezolvaţi prin metoda Branch & Bound programele întregi din ex.5. În rezolvarea programelor liniare generate de metodă se va folosi metoda grafică. Construiţi arborele T al programelor liniare efectiv rezolvate.

10. Descrieţi următoarele probleme:

· problema monezilor;

· problema alegerii proiectelor de investiţii;

· problema stabilirii programului de producţie cu costuri fixe de pregătire;

· problema stabilirii orarului de zbor al avioanelor.

Particularizaţi aceste modele pe date concrete plauzibile.