INTRODUCERE

Domeniul programării liniare în numere întregi ocupă un loc deosebit în

teoria optimizării atât prin caracterul problemelor cercetate, cît şi prin complexitatea

problemelor, a algoritmilor de soluţionare. Numeroase probleme cu caracter

aplicativ pot fi formulate ca probleme de programare liniară în numere întregi. Una

dintre aceste probleme este problema rucsacului. Problema rucsacului este o

problemă NP-complexă şi este utilizată pe larg la cercetarea complexităţii a

numeroase alte probleme.

Lucrarea dată examinează problema rucsacului atât în contextul general al

programării liniare în numere întregi, cît şi în cadrul metodelor specifice de

rezolvare, a aplicaţiilor mai importante.

Lucrarea constă din cinci capitole.

Capitolul I "Probleme de programare liniară în numere întregi. Problema

rucsacului" conţine două paragrafe.

În §1.1 sunt expuse câteva formulări ale problemei rucsacului: problema 0/1 a

rucsacului, problema rucsacului în numere întregi, problema rucsacului cu

inegalităţi (atunci când restricţia ia forma inegalităţii) şi este demonstrat că toate trei

forme ale problemei rucsacului sunt echivalente.În §1.2 este cercetată complexitatea problemei rucsacului. Se demonstrează, că

problema 0/1 a rucsacului este NP-complexă. La demonstrarea NP-complexităţii

problemei rucsacului în numere întregi reformulăm problema 0/1 a rucsacului în

problema rucsacului în numere întregi.

Capitolul II "Metode de rezolvare a problemelor de programare liniară în

numere întregi", constă din trei paragrafe, în care sunt descrise următoarele metode

de soluţionare a problemelor liniare în numere întregi: Metoda Gomory, Metoda

Branch and Bound, Metoda programării dinamice.

În capitolul III, propunem un algoritm GRASP (Greedy Randomized Adaptive

Search Procedure) pentru a genera o aproximare bună a setului optimal în sensul

1

PARETO (eficient) în probleme de optimizare combinatorie multi-obiectiv .

Algoritmul este aplicat la rezolvarea problemei rucsacului 0/1 cu r-funcţii

obiectiv. Această problemă este formulată asemenea problemei clasice 0/1 a

rucsacului cu r funcţii obiectiv, cu n-elemente (articole), fiecare cu costul şi greutatea

respective, care trebuie introduse în r rucsacuri cu diferite capacităţi pentru a

maximiza costurile totale. Algoritmul se bazează pe o funcţie scalară ponderată

(combinaţia liniară a funcţiilor obiectiv).

La fiecare iteraţie a algoritmului, este determinat un vector prioritar, şi este

alcătuită o soluţie luând în consideraţie preferinţele fiecărui caz. Soluţia găsită este

înlocuită (verificată) printr-o căutare locală, încercându-se îmbunătăţirea funcţiei

scalare ponderate.

Pentru a găsi o mulţime de soluţii eficiente vom folosi diferiţi vectori de

preferinţă, care sunt distribuiţi uniform pe frontiera PARETO.

Algoritmul propus a fost testat pe problemele cu r=2,3,4, şi numărul de

elemente n=250,500,750. Calitatea soluţiilor aproximative este evaluată fiind

comparată cu soluţiile date de 2 algoritmi genetici luaţi din literatura de specialitate.

În capitolul IV numit “Optimizarea globală prin metoda GRASP continuă”

prezentăm o metodă de optimizare globală neobişnuită, numită continuă (C-GRASP),

care este o extensie realizată de Feo şi Resende's a algoritmului GRASP din domeniul

de optimizare discretă la optimizarea globală continuă. Această metodă de căutare

locală este simplu de implementat, este aplicată pe larg, şi nu se foloseşte de

informaţia derivată, astfel creând un suport convenabil pentru rezolvarea problemelor

de optimizare globală. Noi ilustrăm eficacitatea procedurii pe un set de probleme

standarde.

Capitolul V “Aplicaţii” constă din două paragrafe.

În §5.1 este analizată şi rezolvată o problemă de tip rucsac: problema

investiţiilor capitale în care funcţia obiectiv este separabilă şi neliniară.

În §5.2 este expusă nemijlocit problema rucsacului, metoda de rezolvare a

căreia ne-o imaginăm ca un proces din n etape, fiecare etapă constând din umplerea

2

optimă a rucsacului cu obiecte de tip întreg. Tot în acest paragraf e rezolvat un

exemplu particular, în care se determină costul maxim al rucsacului.

3

CAPITOLUL I

PROBLEME DE PROGRAMARE LINIARĂ ÎN NUMERE ÎNTREGI.

PROBLEMA RUCSACULUI

1.1. FORMULĂRI ŞI PROPRIETĂŢI

Prin problema de programare liniară în numere întregi se înţelege o

problemă de programare liniară în care pentru o parte din variabile sau pentru toate se

impune condiţia să ia numai valori întregi. Astfel de restricţii apar, ca de obicei,

atunci cînd variabilele respective desemnează cantităţi indivizibile.

Problema programării liniare în numere întregi are forma:

c1x1+c2x2+...+cnxn max, (1)

(2)

unde N este mulţimea numerelor naturale. De regulă se presupune, că atît

coeficienţii problemei (l)-(2), cît şi termenii liberi sînt numere întregi.

Dacă M = {1,2,...,n }, atunci avem cazul problemei de programare liniară total

în numere întregi, pe scurt PLT.

Dacă M {l,2,...,n}, atunci avem cazul problemei de programare liniară mixtă,

abreviat PLM.

Viaţa cotidiană ne oferă un număr enorm de probleme, care, ori pot fi

formulate ca probleme de tipul (l)-(2), ori pot fi reduse la (l)-(2) printr-o

consecutivitate de transformări elementare. E de ajuns să cerem în problema de

repartizare eficientă a resurselor limitate ca necunoscutele să fie numere întregi (la

producţia garniturilor de mobilă, de exemplu, necunoscutele nu pot fi fracţionare

deoarece e absurd să se producă o jumătate de masă, o treime de scaun etc.) şi

4

obţinem o problemă de programare liniară în numere întregi. Dacă în problema de

transport se examinează ca marfă de livrat de la producători la beneficiari ori

aparate TV, ori automobile, ori calculatoare etc., atunci obţinem alte exemple de

probleme de tipul (l)-(2). Chiar şi în problema dietei unele dintre necunoscute,

corespunzătoare produselor alimentare vândute în recipiente indivizibile, trebuie să fie

întregi. În sfârşit, un număr mare de probleme de tipul (l)-(2) apar în

optimizarea combinatorie, teoria grafelor, logica matematică şi în general, în

cercetarea operaţională.

Un caz particular al problemei de programare liniară în numere întregi este

problema rucsacului.

Din n obiecte cu greutăţile a1, a2,..., an şi costurile c1, c2,..., cn trebuie selectate

într-un rucsac acele din ele, care au în sumă o greutate nu mai mare decât b şi un cost

total maxim posibil.

Dacă obiectele nu pot fi tăiate, atunci avem problema discretă sau problema 0/1

a rucsacului, în care variabilele pot lua doar valorile 0 şi 1. Dacă pentru orice obiect

putem să luăm doar o parte din el X J [0,1], atunci spunem că avem problema

continuă a rucsacului.

Notînd xj=

obţinem următorul model matematic al problemei discrete:

(3)

Variabilele xj care pot avea numai valorile 0 şi 1 mai sunt numite şi

booleene, iar problema de mai sus - problemă de programare booleana sau

problema de programare 0/1. Evident că o problemă de programare 0/1 poate avea

mai multe restricţii, ceea ce ar corespunde în problema rucsacului restricţiilor de

volum, de completare etc.

Dacă raportăm costurile obiectelor la greutăţile lor, obţinem costurile pe unitate

5

de greutate. La rezolvarea problemei continue, o ordonare a obiectelor în funcţie de

creşterea acestor raporturi ne dă posibilitatea să obţinem soluţia optimă, încărcând

obiectele, pe cît e posibil în întregime şi anume în această ordine, pînă cînd rucsacul se

umple. Componentele xj vor lua pe rînd valorile xj=1, pînă cînd greutatea rămasă

disponibilă, notată bd, nu mai permite să se pună un obiect întreg. Ultimul obiect se

taie şi se ia din el numai o parte xj=bd/aj.

Problema discretă cu părere de rău e mult mai complicată şi pentru n suficient

de mare nu mai poate fi rezolvată efectiv. Mai mult, din cele de mai sus reiese că

problema rucsacului în numere întregi nu poate fi rezolvată, în general, prin

aproximarea soluţiei optime a problemei continue corespunzătoare pînă la cea mai

apropiată soluţie optimă întreagă, de aceea ultima poate să încalce ori restricţiile

problemei de programare în numere întregi, ori condiţia de optimalitate. Ca rezultat

survine concluzia, că problemele de programare liniară în numere întregi cer, în

general, alte metode de rezolvare, special adaptate la specificul lor, ceea ce nu exclude

posibilitatea, că la rezolvarea unor probleme particulare să se utilizeze metode ale

programării liniare sau neliniare.

O altă formă de scriere a problemei rucsacului este problema rucsacului în

numere întregi:

c1x1+c2x2+...+cnxn max,

(4)

Un caz particular al problemei rucsacului este atunci cînd restricţia ia

forma inegalităţii:

(5)

obţinînd în acest mod, problema rucsacului cu inegalităţi.

6

Afirmaţie. Toate trei formulări ale problemei rucsacului, şi anume problema 0/1 a

rucsacului, problema rucsacului în numere întregi, problema rucsacului cu

inegalităţi, sunt echivalente.

Uşor se demonstrează, că problema rucsacului cu inegalităţi, se reduce la

problema rucsacului în numere întregi, adică sunt echivalente. Dacă în restricţia din

problema (4) adăugăm variabila , atunci echivalenţa acestor două probleme

este evidentă.

E mai complicat de demonstrat că problema rucsacului cu inegalităţi este

echivalentă şi cu problema 0/1 a rucsacului. Pentru a demonstra că ele sunt totuşi

echivalente, adăugăm în inegalitatea (5) expresia y (y- număr întreg ), unde

, iar

Înlocuind y în problema (3) obţinem:

demonstrînd astfel echivalenţa acestor două probleme.

1.2. COMPLEXITATEA PROBLEMEI

Ne interesează clasificarea problemelor de recunoaştere a proprietăţilor după

complexitatea lor. Vom nota prin P clasa problemelor de recunoaştere, care pot fi

rezolvate cu ajutorul unui algoritm polinomial. Clasa P poate fi determinată exact cu

ajutorul oricărui algoritm formal de determinare, cum ar fi maşina Turing. Dar, se

vede, că toate modelele de calcul posedă proprietatea, că dacă problema poate fi

soluţionată într-un timp polinomial cu ajutorul unui model, atunci ea poate fi

rezolvată într-un timp polinomial cu orice alt model. Astfel, clasa P este stabilă în

raport cu diverse schimbări în cadrul supoziţiilor iniţiale. De aceea, vom determina

clasa P neformal ca o clasă a problemelor de recunoaştere, pentru care sunt

7

cunoscuţi algoritmi polinomiali de soluţionare. Cu alte cuvinte, P este clasa

problemelor simple de recunoaştere, pentru care există algoritmi eficienţi.

Introducem clasa NP [6], o clasă mai extinsă de probleme de recunoaştere. Ca

o problemă să aparţină clasei NP, nu cerem ca răspunsul fiecărei probleme individuale

să fie primit într-o perioadă polinomială de timp cu ajutorul unui oarecare algoritm.

Cerem, pur şi simplu, ca în cazul, cînd pentru problema individuală x obţinem

răspunsul da, să existe o recunoaştere scurtă pentru x, adevărul căreia poate fi

verificat polinomial.

Definiţie. Vom spune, că problema de recunoaştere x intră în clasa NP, dacă

există polinomul p(n) şi algoritmul A (algoritmul de recunoaştere), astfel încît se

îndeplineşte următoarea condiţie: şirul de caractere x este problema individuală a

problemei A cu răspunsul da numai în cazul cînd există şirul c(x) şi |c(x)| < p(|x|), şi

algoritmul A, primind la intrare xSc(x), ajunge la răspunsul da după nu mai mult de

p(|x|) paşi.

Trebuie de menţionat, că pentru a determina apartenenţa unei probleme la clasa

de probleme NP, nu trebuie de explicat cum mai efectiv de recunoscut şirul c(x) la

intrarea lui x. Este necesar, pur şi simplu, de arătat existenţa cel puţin a unui singur şir

de caractere pentru fiecare x.. Menţionăm, că clasa P este submulţime a clasei NP. Cu

alte cuvinte, pentru orice problemă ce se rezolvă efectiv putem construi

recunoaşteri scurte. Pentru a înţelege aceasta, presupunem, că pentru problema A

există algoritmul polinomial AA. Dacă x este o problemă individuală a problemei A

cu răspunsul da, atunci algoritmul AA, folosit pentru x, peste un număr polinomial de

paşi oferă răspunsul da. Înscrierea rezultatului funcţionării algoritmului AA pentru

intrarea x este o confirmare convenabilă c(x).Într-adevăr, pentru a controla c(x), este

de ajuns să verificăm corectitudinea îndeplinirii algoritmului AA..

Dar, de ce NP - clasa problemelor de recunoaştere ne interesează?

Teoremă. Problema 0/1 a rucsacului este NP-complexă.

8

Demonstraţie. Evident, această problemă intră în NP; în afară de aceasta

putem arăta, că problema acoperirea exactă 3-M se exprimă polinomial în

problema 0/1 a rucsacului. Din familia F={Si,...Sn}, formată din n 3-M, vom

construi aşa numere întregi c1,c2,...,cn şi K, iar din c1,c2,...,cn putem forma o submulţime

cu suma K, atunci şi numai atunci, cînd în F există familia ce formează acoperirea

optimă a mulţimii S={u1, u2 ,..., u3m }.

Ne putem imagina toate mulţimile din F ca vectori binari de lungime 3m, de

exemplu: {u1, u5, u6 } şi {u2, u4 , u6 } iau forma 100011 şi 010101. Vom interpreta

aceşti vectori binari ca numere întregi, scrise în baza (n +1). Cu alte cuvinte, mulţimii

S, îi corespunde numărul întreg . În afară de aceasta fie K-număr întreg,

ce-i corespunde

Afirmăm, că în F există subfamilii, ce acoperă exact {u1,u2,...,u3m} numai în cazul,

dacă printre cj există submulţimi cu suma K.Demonstrăm suficienţa. Presupunem că există mulţimea , că

, calculînd această sumă în sistemul de numeraţie cu baza n+1 observăm,

că în termenii sumei se întâlnesc numai numerele 0 şi 1 şi în afară de aceasta

numărul termenilor este mai mic decît baza n+1. Drept urmare, la aşa înmulţire nu sînt

transferuri. De aceea dacă aceasta înseamnă, că în fiecare din 3m poziţii

există exact o unitate sau, cu alte cuvinte, subfamilia

C={Sj, j S } exact acoperă {u1, u2 ,..., u3m }.

Demonstrăm necesitatea. Dacă C este acoperire exactă a mulţimii {u1, u2 ,...,

u3m }, atunci rezultă că . Putem demonstra de asemenea că problema 0/1 a

rucsacului este NP-complexă chiar şi atunci, cînd K se alege egal cu .

9

CAPITOLUL II

METODE DE REZOLVARE A PROBLEMELOR DE PROGRAMARE

LINIARĂ ÎN NUMERE ÎNTREGI

2.1. METODA GOMORY

Se consideră problema:

( 1 )

(2)

unde rang(A) = m.

dintre ele avînd O metodă incipientă de soluţionare a acestei probleme

porneşte cu soluţionarea problemei relaxate [3], care nu ţine cont de integritatea

variabilelor.

1°. Dacă soluţia optimă x* a problemei relaxate are toate componentele întregi,

atunci (l)-(2) este rezolvată.

2°. Dacă problema relaxată nu are soluţii admisibile, atunci şi (l)-(2) nu are soluţii

admisibile.

3°. Dacă soluţia optimă z* are cel puţin o componentă neîntreagă, atunci se

alcătuieşte o restricţie liniară suplimentară, verificată de orice soluţie întreagă a

problemei (1)-(2) şi neverificată de soluţia optimă neîntreagă x* a problemei relaxate.

Ea se alătură sistemului de restricţii al problemei. Se rezolvă problema extinsă şi se

verifică iarăşi condiţiile l°-3°.

Lesne se înţelege că pasul 3° va genera iterativ o consecutivitate de probleme,

fiecare, în comparaţie cu problema precedentă, cu o restricţie mai

10

mult. Dacă procedeul de alcătuire a restricţiei adiţionale este pus la punct, după un număr

finit de iteraţii ori se determină soluţia problemei (l)-(2), ori se determină că (l)-(2) nu

are soluţie. Dacă procedeul de alcătuire a restricţiei adiţionale e inadecvat, paşii l°-3° se

pot repeta la nesfirşit, generîndu-se probleme cu un număr de restricţii oricît de mare.

Ideea unei asemenea metode îi aparţine lui Dantzig. Meritul de a indica o

procedură riguroasă şi bine pusă la punct de formare a restricţiilor adiţionale îi aparţine

lui Gomory.

Algoritmul lui Gomory de soluţionare a problemei de programare liniară în

numere întregi

La expunerea algoritmului vom avea nevoie de următoarele notaţii:

[x] — partea întreagă a lui x R — cel mai mare număr întreg, mai mic decît x;

{x}= x-[x]— partea fracţionară a lui x R.

Sunt evidente proprietăţile:

[x] x , 0<{x}< 1.

Exemple :

[0,1]=0; {0,1} = 0,1.

[1,1]=1; {1,1} = 0,1.

[-0,2]= -1; {0,2} = 0,8.

Oricărei soluţii admisibile de bază optime x' a problemei relaxate (l)-(2) îi

corespunde un sistem (echivalent sistemului (2)):

(3)

(J este- mulţimea indicilor componentelor nebazice), la care s-a ajuns printr-o

consecutivitate de pivotări ale algoritmului simplex. Sistemul (3), în notaţiile de mai

sus, se scrie sub forma:

(4)

11

Teorema 1. Dacă soluţia optimă admisibilă, de bază x' a problemei relaxate

(1)-(2) are componenta x j k = k neîntreagă ({ }>0), atunci:

I. orice soluţie întreagă a sistemului (2) satisface inecuaţia:

(5)

II. soluţia optimă admisibilă de baza (neîntreagă) x1 a problemei relaxate ( l ) -

(2) nu satisface inecuaţia (5).

Demonstraţie . I. Fie x* o careva soluţie întreagă a sistemului (2). Rezultă că

x* este soluţie şi a sistemului (3), şi a sistemului (4). Din (4) rezultă că:

este de asemenea întreagă, existînd două posibilităţi:

echivalent cu

(6) şi (7)

Să arătăm că (6) nu este verificată de nici o soluţie admisibilă a problemei (1)-(2).

Într-adevăr, (6) este echivalentă cu

,

care contrazice nenegativităţii componentelor ,{ kj}, , j J. Ca rezultat, deoarece

(6) şi (7) definesc două semispaţii reciproc complementare faţă de Rn, rezultă că orice

soluţie întreagă a sistemului (3), nesatisfacînd (6), va satisface (7) (echivalent cu (5)).

II. Soluţia x', fiind soluţie admisibilă de bază a sistemului (3), are nule toate

componentele nebazice .Înlocuind aceste valori în (5), obţinem 0 >{ }, ce

contrazice supoziţiei teoremei: .

12

Corolarul 1. Dacă soluţia optimă x' a problemei relaxate nu este întreagă ( )

şi toate componentele , ale tabelului simplex sunt întregi, atunci (5) defineşte

o inegalitate contradictorie, ceea ce înseamnă că (l)-(2) nu are soluţii întregi.

Teorema 1 şi corolarul 1 ne permit să concretizăm ideea lui Dantzig, expusă în

preambulul acestui subcapitol, prin următorul algoritm:

0°. Se rezolvă problema relaxată (l)-(2) şi se determină soluţia optimă x*.

1°. Dacă x* are toate componentele întregi, atunci (l)-(2) este rezolvată.

2°. Dacă problema relaxată nu are soluţii admisibile, atunci şi (l)-(2) nu are soluţii

admisibile.

3°. Se formează restricţia adiţională (5).

Dacă (5) este contradictorie (vezi corolarul (1)), atunci (l)-(2) nu are soluţii

întregi.

Dacă (5) nu este contradictorie, atunci problema curentă se extinde cu restricţia (5).

Se determină soluţia optimă x* a problemei extinse relaxate şi se trece la pasul 1o.

Remarca 1. Restricţia adiţională (5) taie efectiv mulţimea de soluţii admisibile X a

problemei relaxate (1)-(2), înlăturînd o parte a ei. Restricţia adiţională (5) se scrie sub

forma de ecuaţie introducînd variabile ecart xn+1>0, care se scade din membrul stîng.

Adăugarea la sistemul (2) a acestei restricţii conduce la problema extinsă relaxată:

(8)

(9)

Dacă (8)-(9) are soluţie întreagă, algoritmul ia sfîrşit. În cazul în care problema

are soluţie întreagă, algoritmul continuă cu formarea altei restricţii adiţionale şi

extinderea cu ea a problemei curente.

13

Remarca 2. Problema (8)-(9) poate fi soluţionată sau prin algoritmul simplex

primal, sau prin algoritmul simplex dual.

Algoritmul simplex primal se realizează ori prin metoda celor două faze, ori prin

metoda coeficienţilor de penalizare. În ultimul caz (8)-(9), în urma introducerii variabilei

artificiale xn+2 0 se aduce la forma:

unde M este coeficientul de penalizare.

Algoritmul simplex dual, la etapa de iniţiere, cere înmulţirea ultimei ecuaţii

cu -1. Ca rezultat, termenul liber devine negativ, iar variabila x n+1 se trasformă în

variabilă de bază.

Corolarul 2. Atît restricţia adiţională, cît şi coloana variabilei ecart, ce-i

corespunde în tabelul simplex, pot fi suprimate concomitent, îndată ce

variabila ecart respectivă intră în bază, obţinînd valoarea pozitivă.

Demonstraţie . Restricţia adiţională (5) este introdusă cu scopul de a tăia

efectiv o parte din mulţimea de soluţii admisibile. Atît timp cît ea este activă e

satisfăcută ca egalitate (din (9) reiese de asemenea că (5)

are rost).

Îndată ce restricţia adiţională (5) este satisfăcută ca inegalitate strictă

(5) devine inutilă şi poate fi suprimată atît ea, cît şi variabila

ecart xn+1.

La lansarea algoritmului simplex, xn+1 are sau valoare nulă (în cazul

algoritmului primal), sau valoare negativă (în cazul algoritmului dual), ceea ce

înseamnă că nu este satisfăcută restricţia adiţională. Dacă variabila ecart xn+1, nu este

14

bazică, atunci ecuaţia xn+1=0 corespunde unuia dintre cele n hiperplane ce definesc

soluţia admisibilă de bază respectivă. Dacă variabila xn+1 ia valoare pozitivă,

atunci ea devine nesemnificativă pentru variabilele problemei iniţiale (1)- (2) şi atît

ea, cît şi restricţia adiţională pot fi suprimate.

Deoarece în conformitate cu corolarul 2 toate variabilele suplimentare,

îndată ce intră în bază, sunt suprimate împreună cu restricţia corespunzătoare,

problemele extinse nu au mai mult decît n restricţii şi respectiv n-m variabile

suplimentare.

Remarca 3. Orice problemă extinsă conţine nu mai mult decît 2n-m

variabile şi nu mai mult decît n restricţii, în cazul în care algoritmul lui Gomory

se completează cu un procedeu de suprimare a variabilelor ecart bazice şi a

restricţiilor adiţionale corespunzătoare.

2.2. METODA BRANCH and BOUND

Metodele de tip Branch and Bound sunt suficient de flexibile pentru a conduce la

rezolvarea problemelor practice din diverse domenii.

Metoda Branch and Bound se bazează pe ideea enumerării raţionale a tuturor

punctelor posibile în problema de optimizare combinatorie. Pentru a face o descriere

mai exactă a metodei putem spune, că s-a făcut o încercare de a construi o

demonstraţie a optimalităţii unei soluţii pe baza descompunerii consecutive a

spaţiului soluţiilor. Vom desfăşura această metodă pentru problema de programare

liniară în numere întregi.

Vom analiza următoarea problemă de programare liniară în numere întregi

z =c'x= c(x),

Problema 0. Ax b, (1)

x 0 întreg.

Dacă rezolvăm problema liniară, care este problema relaxată a problemei

date, primim soluţia x°, care nu va lua valori întregi. Însă costul c(x°) al acestei 15

soluţii este limita de jos a costului optim c ( x ) (unde x este soluţia optimă a

problemei 0), şi dacă x0 ar lua valoare întreagă, atunci problema ar fi rezolvată. În

algoritmul secţiunii am putea adăuga acum restricţia în problema relaxată, ceea ce

nu exclude soluţiile problemei (1). Dar în loc de aceasta acum vom descompune

problema în două subprobleme, adăugînd două relaţii ce se contrazic reciproc şi

epuizează toate variantele posibile. Fie, de exemplu, componenta x o1 în x° nu ia

valori întregi. Atunci cele două probleme corespunzătoare au forma:

min z = c'x = c(x),

Ax b,

Problema 1. x 0 întreg , (2)

x

min z = c'x = C(X),

Ax b,

Problema 2. x 0 întreg , (3)

x

Soluţia problemei iniţiale trebuie să fie în unul din domeniile admisibile ale celor

două probleme, deoarece una din inegalităţile de mai jos trebuie să fie adevărată:

x

x

Alegem una din cele două subprobleme, de exemplu problema 1, şi s-o

rezolvăm ca pe o problemă liniară. Soluţia ei x 1 , nu va fi un număr întreg, şi problema

1 o putem descompune în două probleme, la fel cum am descompus problema 0,

obţinem în rezultat problemele 3 şi 4. Acest continuu proces î1 putem închipui ca pe o

16

continuitate de descompuneri a domeniului admisibil. Fiecare submulţime din această

descompunere prezintă o careva subproblemă i cu soluţia relaxată xi şi limita de jos

zi=c(x') pentru costul problemei iniţiale în domeniul dat de descompunere.

Acest proces poate fi prezentat sub forma unui arbore. Rădăcina acestui arbore

reprezintă domeniul admisibil iniţial, iar fiecare vîrf prezintă o subproblemă.

Descompunerea zonei admisibile a unui vîrf cu ajutorul adăugării inegalităţilor se

prezintă ca o ramificare a vîrfului în doi feciori ai lui.

Dacă domeniul admisibil al problemei liniare în numere întregi iniţiale e mărginit,

atunci acest proces nu poate fi continuat la nesfîrşit, deoarece inegalitatea de la unul

din vîrfurile arborelui ramificat va duce la obţinerea unei soluţii întregi a problemei de

programare liniară, care este soluţia optimă a problemei de programare liniară în

numere întregi iniţială. Procesul ramificării la un careva vîrf poate fi încălcat numai în

una din cauze:

1. soluţia problemei de programare liniară ia valoare întreagă, sau

2. problema de programare liniară poate fi inadmisibilă.

Totul ce este descris mai sus, conţine în sine numai procesul de ramificare al

metodei Branch and Bound. Dacă continuăm procesul ramificării pînă în momentul,

cînd toate vîrfurile vor fi extremităţile arborelui şi vor corespunde, fie soluţiilor întregi,

fie problemelor de programare liniară inadmisibile, atunci extremitatea cu cel mai mic

cost trebuie să fie soluţia optimă a problemei iniţiale de programare liniară în numere

întregi. Ajungem la un moment important al acestei metode. Şi anume, să considerăm

că soluţia complet întreagă optimă, găsită la acest moment, are costul zm şi noi

continuăm ramificarea vîrfului cu limita de jos zr=c(xr) mai mare sau egală cu zm.

Aceasta înseamnă că orice soluţie x, care poate fi primită în calitate de urmaş al

problemei xr, va avea costul c (x) zr zm, şi, drept urmare, nu va fi nevoie să continuăm

ramificarea din xr. În aşa caz vom spune, că vîrful xr e mort şi subproblema o vom numi

moartă. Celelalte vîrf uri, din care ramificarea o vom continua, le vom numi vii.

În acest algoritm lipsesc două detalii importante de care trebuie să ţinem cont:

trebuie să hotărîm, cum să alegem la fiecare pas, din care vîrf să continuăm ramificarea şi

al doilea moment este cum să alegem care variabilă aleatoare să determine restricţiile 17

suplimentare.

Metoda Branch and Bound se aplică nu numai la problemele de programare

liniară în numere întregi, ci şi la orice problemă combinatorică.

2.3. METODA PROGRAMĂRII DINAMICE

Pe parcursul a mai multor ani de activitate s-a observat că există numeroase

activităţi interesante şi semnificative care pot fi clasificate ca procese de decizie în mai

multe etape. Problemele matematice apărute în studierea acestor activităţi depăşesc

hotarele convenţionale ale analizei. De aceea se iveşte necesitatea elaborării noilor

metode care pot fi aplicate la studierea unor subiecte mai complexe, mai reale.

Metodele clasice ale calculului diferenţial şi calculul variaţiilor s-au dovedit a fi

utile în aceste noi domenii, dar limitate în ceea ce priveşte sfera şi varietatea aplicaţiiilor.

Numeroasele încercări de a obţine răspunsuri numerice, aplicând metodele deja

cunoscute, au rămas nejustificate şi nesatisfacătoare.

Examinarea atentă şi amănunţită a greutăţilor întîlnite au constituit o motivare

suficientă pentru crearea unor noi metode şi teorii matematice.

Conceptul de programare dinamică a fost introdus în anii cincizeci de către Richard

Bellman.

Termenul de "programare dinamică" are sens larg şi polivalent, el defineşte o

tehnică de calcul ce poate fi folosită la rezolvarea unor anumite tipuri de probleme de

optim, în particular, şi a unor probleme de programare matematică.

Natura ce ne înconjoară este abundentă în probleme de optimizare, care sunt

rezolvate prin nenumărate experienţe în decurs de milioane de ani.

Omul pentru a realiza optimul foloseşte capacităţile sale intelectuale, operînd cu

careva modele: machet, model matematic, desen.... Deci, problemele de optimizare

pot fi tratate şi ca modele matematice ale unor probleme reale ce apar în diferite domenii:

economie, ştiinţă s.a.

Conceptul de programare dinamică are mai multe semnificaţii. În primul rînd

18

este un model matematic general al proceselor de luare a deciziilor, ce se dezvoltă pe

etape în timp discret sau continuu, cu orizont limitat sau nelimitat. În al doilea rînd,

programarea dinamică reprezintă o clasă specifică de probleme de optimizare, care nu

pot fi rezolvate efectiv nici prin metodele tradiţionale ale analizei matematice, nici prin

metodele calculului variaţional.

În fine programarea dinamică este o metodă de studiu bazată pe folosirea ecuaţiilor

funcţionale şi pe principiul de optimalitate, avînd în vedere potenţialul maşinilor numerice

de calcul.

Dezvoltarea acestei metode a impus anumite sarcini. Una dintre ele fiind

examinarea unei varietăţi de activităţi în domeniul construcţiei de maşini, economic,

militar, industrial cu scopul de a vedea care dintre ele pot fi formulate în termenii

programării dinamice şi la ce nivel de complexitate.

Programarea dinamică nu reprezintă un şablon de rezolvare a problemelor.

Rezolvînd mai multe probleme de optimizare din diverse domenii au fost aplicate

metodele în mod diferit. Programarea dinamica poate fi folosită la rezolvarea unui şir

întreg de probleme care reprezintă interes şi importanţă în aplicaţii.

Avantajul deţinerii unei metode raţionale la rezolvarea cîtorva clase de probleme

din domeniile matematicii este multiplu. În primul rînd avem mijlocul de a obţine soluţia

problemei pe căi mai simple şi mai rapide.

După cum am menţionat mai înainte metoda programării dinamice se bazează

pe principiul optimalităţii. Mai jos vor fi expuse laconic aceste idei, bazîndu-ne pe

unele cazuri particulare semnificatoare.

Principiul optimalităţii

Presupunem dacă o problemă de decizie [5], care cere optimizarea unei

anumite funcţii prin alegerea convenabilă a valorilor variabile x1,x2,...,xn puse unui

sistem de restricţii.

Valorile optime ale variabilelor de control x1,x2,...,xn precum şi valoarea

optimă a funcţiei date, vor depinde de un sistem de parametri, numiţi parametrii de

19

stare, care descriu starea sistemului, adică determină sistemul de restricţii la care

sunt supuse variabilele.

Procedeele programării dinamice se aplică acelor probleme ce pot fi formulate

ca procese de decizie cu mai multe stadii, fiecăruia dintre acestea fiindu-i proprii una sau

mai multe variabile de control.

Totodată este necesar ca problemele de decizie corespunzătoare diferitor stadii să

aibă o structură asemănătoare.

Procedeele programării dinamice sunt dominate de principiul optimalităţii [5]

potrivit căruia: oricare ar fi decizia xk-1 luată în etapa k-1 corespunzător stării ξk rezultată din

aceasta ( ) trebuie să fie optimă pentru etapele rămase.

În programarea dinamică ne vom opri asupra problemei:

(R)

în care L >l1 >12 > ... > lm sunt întregi pozitivi.În secţiunea precedentă, (R) a apărut ca subproblemă în rezolvarea relaxatei

problemei de croire unidimensionale prin metoda generării de coloane. Este clar că

eficacitatea metodei amintite depinde de performanţele algoritmilor utilizaţi pentru

rezolvarea problemei (R).

(R) este un progam liniar în numere întregi foarte simplu, având o singură

restricţie, j în literatura de specialitate este cunoscută sub numele de problema

rucsacului datorită următoarei interpretări: ai este numărul pieselor de echipament de

greutate li şi utilitate ; care trebuie luate într-o excursie într-un rucsac ce suportă o

greutate maximă L. Întrebare: ce piese de echipament trebuie alese şi în câte exemplare

vor fi acestea introduse în rucsac astfel încât utilitatea încărcăturii să fie maximă?

Fireşte, (R) poate fi rezolvată prin metodele specifice programării în numere

întregi (plane de secţiune, Branch & Bound etc). Faptul că (R) are o singură restricţie

permite abordarea ei prin programare dinamică. Mai precis, pentru fiecare k = şi

fiecare întreg considerăm problema:

20

Rk( )

al carei optim îl notăm cu . Este clar că R=Rm ( ) şi că maximul funcţiei obiectiv din

R este .

Observăm că, pentru k fixat este o funcţie de o singură variabilă ale cărei

valori admisibile sunt O, l,... ,L.

Funcţiile , ,..., , pot fi determinate astfel:

(2.1)

Pentru k>1 avem formula de recurenţă:

=max (2.2)

Pentru k=m este suficient să găsim numai valoarea funcţiei în L

(L)=max

Relaţia (2.2) arată că funcţiile ,..., , rezultă nişte procese de optimizare

unidimensionale.

Să presupunem cunoscute funcţiile , ,..., , şi valoarea (L) şi să notăm cu

a ( ) valoarea variabilei ak care – pentru dat – realizează maximul din formula de

recurenţă (2.2). Pentru k=1 avem a ( )

Atunci, o soluţie optimă a problemei (R) se găseşte astfel: . Pentru

k=m-1,...,2,1: = (L-Sk) unde: Sk = lk+1a +...+lma

Observaţii

1. În termenii problemei rucsacului k( ) este valoarea maximă a unei încărcări a

rucsacului ce nu depăşeşte în greutate plafonul şi care este formată numai din

primele k tipuri de echipament.

21

2. Prin programarea dinamică rezolvarea problemei de optimizare

multidimensională (R) este înlocuită cu o secvenţă de optimizări unidmensionale

bazate pe formula de recurenţă (2.2)

3. Ecuaţia funcţională (2.2), prin care funcţiile , ,..., , , se deduc una din

alta formalizează - în cazul problemei (R) - principiul central al programării

dinamice datorat lui R. BELLMAN: O strategie optimă are proprietatea că oricare

ar fi starea iniţială şi decizia iniţială, deciziile rămase constituie strategie optimă în

raport cu starea care rezultă din prima decizie.

22

Capitolul III

UN ALGORITM GRASP PENTRU PROBLEMA RUCSACULUI

MULTI–OBIECTIV

3.1. Introducere

Multe probleme optimizare cu aspect practic implică, în general, minimizarea

(maximizarea) simultană a câtorva criterii de decizie care sunt contradictorii. De

exemplu, în design-ul unui sistem complex hard/soft, deseori costul sistemului trebuie

minimizat, în timp ce se doreşte o performanţă maximă. Există o contradicţie între aceste

două criterii. Deci, persoana care ia decizie, trebuie să aleagă soluţia cea mai bună, luând

în consideraţie preferinţele după anumite criterii.

Scopul optimizării combinatorii cu mai multe criterii (OCMMC) este de a

optimiza simultan r>1 criterii sau funcţii obiectiv. Aceste probleme au un set de soluţii

optimale (în locul unei singure soluţii optimale) în sensul că mulţimea de soluţii optimale

constă din puncte echivalente, când toate criteriile sunt luate în consideraţie. Elementele

mulţimii sunt cunoscute sub numele de soluţii optimale în sensul Pareto sau soluţii

eficiente.

Rezolvarea problemelor OCMMC este destul de diferită de rezolvarea

problemelor cu un singur criteriu (r=1), unde se caută o soluţie optimă. Dificultatea se

datorează nu numai complexităţii, ca în cazurile unei singure funţcii-obiectiv, dar de

asemenea, şi datorită căutării tuturor elementelor setului eficient, a cărui cardinalitate

creşte odată cu numărul criteriilor.

În literatura de specialitate, sunt propuse metode exacte de rezolvare a

problemelor de tip OCMMC. Aceste metode sunt în general valide pentru problemele bi-

criterilae, şi nu pot fi uşor adaptate pentru un număr de mai mare de criterii. De

asemenea, metodele exacte sunt ineficiente pentru rezolvarea problemelor de o scară

largă şi a problemelor OCMMC de NP–dificile.Ca şi în cazurile cu un singur criteriu,

23

folosirea tehnicilor euristice pare a fi cea mai bună abordare a problemelor OCMMC

datorită eficienţei, generalităţii şi simplităţii relative a implementării lor. Aceste tehnici

generează soluţii bine aproximate, într-un timp computaţional scurt. Au fost propuse mai

multe proceduri euristice pentru a rezolva probleme OCMMC, dar totuşi literatura este

cam săracă în ce priveşte aceste probleme. Metodele propuse de Ulungu, Teghem(1995)

şi Visee (1998) sunt bazate pe algoritmi exacţi, Ben (1999), Jasskiewicz (2002) şi Zitzler

şi Thiele (1999) folosesc algoritmi genetici, metodele lui Gandibleux şi Frevile (2000) şi

Hansen (1997) sunt bazate pe căutarea tabu, iar metodele propuse de Czyzak şi

Jaskiewicz (1998), Teghem (2000) şi Ulungu (1998) se bazează pe analiza simulată.

Un scurt sumar a metodelor metaeuristice multi-obiectiv, publicat de Jones ş.a.

(2002), arată că 70% din articole utilizează algoritmi genetici ca metaeuristică primară,

24% – analiza simulată şi 6% – căutarea tabu. Jones ş.a. (2002) spune că, nu este nici un

semn în literatură care este îmbogăţită cu cele mai noi tehnici euristice, de prezenţă a

algoritmului GRASP aplicat în cazurile multi-obiectv. Mai recent, Festa şi Resende

(2004) publică o bibliografie adnotată a metaeuristicii GRASP şi acolo nu există referinţe

la aplicarea algoritmului GRASP la rezolvarea problemelor OCMMC.

În cadrul acestei lucrări se consideră algoritmul GRASP pentru rezolvarea

problemelor OCMMC, generând un set de soluţii aproximative eficiente. Algoritmul este

testat rezolvând problema 0/1 cu mai multe criterii. Performanţa algoritmului propus este

comparată cu performanţele a doi algoritmi genetici: MOGLS propus de Jaskiewicz

(2002) şi SPEA2 (Zitzler 2002) care e o versiune îmbunătăţită a algoritmului SPEA

propus de Zitzler şi Thiele (1999). În continuare se prezintă formularea unei probleme de

tip OCMMC, se prezintă conceptele de utilizare şi definiţia formală a problemei

rucsacului multi-obiectiv. Sa discută în detaliu algoritmul GRASP propus. Se prezintă

rezultatele obţinute la calculator. În sfârşit, se prezintă şi concluziile.

24

3.2. Optimizarea multi-obiectiv

3.2.1. Alcătuirea problemei şi definiţiile de bază

Fiind dată o funcţie–vector din r componente f=(f1,…,fr) definită pe un set finit

, se consideră următoarea problemă multi-obiectiv de optimizare combinatorie.

Se cere maximizarea concomitentă a componentelor vectorului f(x)=(f1(x)=z1,

…,fr(x)=zr), pentru x . Imaginea soluţieix este punctul z=f(x) în spaţiul funcţiilor

obiectiv. Un punct z domină punctul z/ dacă pentru orice j: zj=fj(x) z =fj(x/) şi are

loc zj>z pentru cel puţin un j.

O soluţie x domină soluţia x/ dacă imaginea lui x domină imaginea lui x/. O

soluţie x* este “Pareto optimală” (sau eficientă), dacă nu există nici un x , astfel

încât z=f(x) să domine z*=f(x*).

O soluţie x* este nedominantă dacă nu există nici un x , astfel încât

z=f(x) să domine z*=f(x*).

3.2.2. Problema rucsacului multi-obiectiv (PRMO)

În literatură sunt studiate diferite versiuni a PRMO 0/1. În continuare vom folosi

aceeaşi formulare a problemei analizată de Zitzler, Thiele şi Jaskiewicz în experimentele

lor, care consideră problema multi-obiectiv prin cercetarea a r rucsacuri cu diferite

capacităţi. Această problemă poate fi formulată astfel:

fj(x)= j şi , j=1,....,r şi x {0,1}, i=1,…,n.

unde w este greutatea elementului i a rucsacului j, W -capacitatea rucsacului j şi x=(x ,

…,x ) vectorul de variabile liniare astfel încît xi=1, dacă elementul irucsacului şi

x =0 -în caz contrar.

25

3.3. Algoritmul GRASP euristic multi-obiectiv

GRASP este o metaeuristică multi-start, în care fiecare iteraţie constă din două

etape: construirea şi căutarea locală. Faza de construcţie constă în aflarea unei soluţii

posibile folosind algoritmul GRASP, a cărei vecinătate este studiată până când un minim

(sau maxim) local este găsit în cadrul fazei de căutare locală. Cea mai bună soluţie

generală este considerată ca răspuns.

3.3.1. Construcţia “greedy-randomized”

Pentru a genera un set iniţial de sluţii dominante, se foloseşte o euristică de tip

“greedy” pentru a maximiza o combinaţie liniară a funcţiilor obiectiv:

F(x)= (x) , unde =1 şi 0 1.

Vectorul preferinţă , în general, determină o direcţie de căutare pe frontiera

mulţimii optimale în sensul Pareto. Cu scopul generării unei soluţii, mai întâi, este definit

un vector de preferinţă . Pentru acest vector este generată o soluţie x, a cărei funcţie

ponderată f(x) este maximizată.

Murata ş.a. (2001) introduce un mod de generare a vectorului de preferinţă

distribuite uniform pe frontiera Pareto. Aceşti vectori sunt generaţi prin combinarea a r

numere întregi nenegative cu suma lui s:

w =s, unde w {0,1,2,…,s}.

De exemplu dacă r=2 funcţii-obiectiv şi s=5 avem vectorii:

(5,0),(4,1),(3,2),(2,3),(1,4),(0,5).

Pentru r=3 şi s=3, avem 10 vectori:

(3,0,0),(2,1,0),(1,2,0),(1,1,1),(0,2,1),(0,3,0),(1,0,2),(0,1,2),(0,0,3).

Cu scopul de a obţine preferinţe normalizate ( avem

Numărul vectorilor generaţi pentru r funcţii-obiectiv şi pentru o valoare a lui s, 26

Nr(s), se calculează astfel:

Procedura SoluţiaConstruită(x, lPareto)

La intrare:

x-soluţia ce trebuie alcătuită ;

-procentajul folosit la definirea candidaţiilor listei restrictive (CLR);

-vectorul preferinţelor;

lPareto-lista soluţiilor dominante care vor fi modificate cu x.

La ieşire:

x-soluţia construită.

Început

01 Introdu fiecare element x în lista candidaţiilor (LC)

sortată (descrescător) după condiţia;

;

02 Fie CLR e o listă cu % a primelor elemente a LC

03 Alege la întîmplare un element x din CLR.

04 Cît timp x nu încalcă w , pentru j=1,...,r do (fă)

05 Început

06 X

07 Elimină elementul x din CLR;

08 Alege la întîmplare un element x din CLR;

09 Sfîrşit_while

10 Pentru i=1 pînă la LC do (fă)

11 Început (Begin)

12 X al i-lea element al LC;

27

13 Dacă x nu întrece w , pentru j=1,...,r, atunci

14 Început

15 x

16 Sfîrşit_if

17 Sfîrşit_for

18 Verifică înserarea lui x în lPareto;

19 Întoarce x;

Sfîrşit_SoluţiaConstruită

Figura 1. Algoritmul de construcţie

Figura 1 reprezintă algoritmul de construcţie implementat, care primeşte ca

parametri de intrare soluţia x ce trebuie construită, procentajul folosit la selecţia

următorului element care va fi introdus în x, vectorul preferinţelor şi lista Pareto unde

sunt situate soluţiile.

La ieşire, algoritmul întoarce soluţia x.

În linia 1, este definită lista candidaţilor (LC). În această listă sunt introduse

toate elementele cu x =0. Lista LC este sortată (în ordine descrescătoare) conform

următorului raport:

(1)

Cum este arătat în linia a 3-a, lista restrictivă a candidaţilor (LRC) este compusă

din LC – primul element din lista LC.

Ciclul din liniile 4-9 este responsabil de alegerea aleatoare din algoritm. Un

element e este ales la întâmplare din LRC şi introdus în x. Acest proces este repetat atâta

timp cît introducerea lui nu încalcă nici o restricţie a problemei. Ciclul din liniile 10-17

completează soluţia x. Această etapă este lista CL. La linia 18 se verifică dacă soluţia x

este o soluţie primară, şi în final, soluţia x este returnată în linia 19.

3.3.2. Căutarea locală

28

Procedure LocalSearch(x, lPareto)

Început

x-soluţia ce trebuie găsită;

-procentajul folosit pentru recalcularea soluţiei x;

-vector ales;

lPareto-lista soluţiilor principale care vor fi adăugate la soluţiile găsite.

Output

x-soluţia recalculată.

Begin

01 For i=1 to n do

02 Marked[i] false;

03 While există un element e astfel încît Marked[e]=false do

04 Begin

05 y x

06 Înlătură elementul nemarcat y care reprezintă cea mai mică valoare a

raportului (1). Repetă acest proces pînă cînd orice element y va putea fi

ales pentru a fi inserat;

07 y BuildSolution(y, lPareto);

08 If f(y)<f(x) then

09 Begin

10 x

11 For i=1 to n do

12 Marked[i] false;

13 Else

14 Fie că x este elementul nemarcat a lui x care reprezintă cea mai mică valoare a

raportului (1);

15 Marked[e] true;

16 End_if

29

17 End_while

18 Return x;

End_LocalSearch

Figura 2. Algoritmul căutării locale.

Algoritmul de căutare locală este prezentat în figura 2. Programul primeşte drept

parametri de intrare: soluţia x ce trebuie recalculată, procentajul care este folosit la

etapa de recalculare a soluţiei, un vector oarecare şi lista Pareto, unde sunt introduse

soluţiile principale. Ca date de ieşire algoritmul returnează soluţia finală x. Ciclul din

liniile 1-2 iniţializează toate poziţiile şirului marcat cu valoarea fals. Un element e poate

fi mutat din rucsac doar dacă Marked[e]=false. Acest şir este foarte important pentru

finalul algoritmului. La linia 5, soluţia x este atribuită soluţiei auxiliare y. La linia 6 din

y sunt înlăturate elementele ce reprezintă cea mai mică valoare a raportului (1). Acest

proces se repetă atîta timp cît există un element ce nu aparţine rucsacului şi poate fi

introdus fără a încălca orice restricţie a problemei. La linia 7 procedura BuilSolution

este efectuată pînă cînd se găseşte y. Dacă noua soluţie y este mai bună ca x, atunci se

calculează soluţia x în linia 10 şi şirul Marked este reiniţializat la linia 11-12. Astfel,

procesul este repetat având o nouă soluţie x. Dacă y nu este mai bun ca x atunci la linia

15 este marcat primul element care este înlăturat din y în timpul etapei descrise la linia 6.

La linia 18, soluţia recalculată x este returnată. Numărul de iteraţii a algoritmului de

căutare locală depinde de valoarea soluţiei x ce este primită ca parametru.

30

3.3.3. Grasp multi-euristic

Procedure Grasp-multi euristic(N_iter, )

Input

N_iter-numărul de iteraţii Grasp

-procentajul (parametrul ) folosit la etapa de calculare;

-procentajul folosit la etape căutării locale

Output

lPareto-lista soluţiilor principale;

Begin

01 lPareto 0;

02 For i=1 to N_iter do

03 Begin

04 x

05 Definim vectorul pentru iteraţia i potrivit metodei descrise la paragraful 1.3.1

06 x BuildSoution (x, ,lPareto);

07 x LocalSearch(x, lPareto);

08 End_for

09 Return lPareto;

End_Grasp_Multi

Figura 3. Implementarea algoritmului Grasp

Figura 3 reprezintă algoritmul Grasp implementat care are ca parametri de

intrare: numărul de iteraţii (N_iter), parametrul folosit la etapa de căutare locală. Ca

date de ieşire, algoritmul returnează lista Pareto, unde sunt introduse soluţiile principale.

La linia 1, lista Pareto este iniţializată. Ciclul din liniile 2-8 efectuează iteraţiile Grasp

N_iter. La linia 4, soluţia x este iniţializată. La linia 5, vectorul ales este definit după

metoda descrisă anterior. Soluţia x este calculată la linia 6 şi recalculată la linia 7. În

sfârşit, lista Pareto este returnată.

31

3.4. Execuţia algoritmilor la calculator

Toate compilările algoritmilor au fost efectuate pe un calculator Pentium 4 de

2 GHz şi cu un Gbyte de memorie RAM. Algoritmul Grasp-multi a fost implementat în

C, versiunea 6.0 a compilatorului Miccrosoft Visual C.

3.4.1. Exemple

În acest program am folosit aceleaşi date pe care le-au folosit Zitzler şi Thiele

(1999). Ei au introdus date ce conţin 250, 500 şi 750 elemente şi 2, 3, şi 4 obiective.

Profiturile şi cantităţile care nu se potrivesc (nu sunt egale ) au fost generate la

întâmplare în interiorul [10:100]. Capacităţile rucsacului au fost fixate la jumătate din

greutatea totală potrivit rucsacului: w .

3.4.2. Evaluarea rezultatelor obţinute la calculator pentru optimizarea

multi-obiectv

Rezultatul soluţionării unei probleme de minimizare cu un singur criteriu este

evaluat printr-o metodă simplă drept diferenţa dintre valoarea funcţiei obiectiv a acestei

soluţii şi valoarea unei soluţii optime. În optimizarea multi-obiectiv, totuşi, nu există o

măsură unică naturală care să poată să conţină valoarea unei mulţimi de aproximaţii M la

mulţimea optimă Pareto sau mulţimea dată R.

Măsurăm rezultatele mulţimii de elemente secundare H generate de metoda

euristică, relativ la mulţimea dată R folosind două măsuri:

măsuri cardinale: NRS=H (numărul soluţiilor găsite prin metoda euristică )

măsuri de distanţă: (propus de Czyzak şi Jaskievicz(1998) şi Ulungu (1998):

D şi D

32

unde d este definit ca d(z { z

z=(z şi este un şir de funcţii obiectiv f .

De notat că D este distanţa medie de la punctul z R la cel mai apropiat

punct din H, în timp ce D reprezintă distanţa maximă de la punctul z R la orice

punct din H.

Cînd mulţimea de valori optime Pareto nu este cunoscută, iar H este mulţimea

punctelor secundare generate de o altă euristică, definim mulţimea de date R drept puncte

secundare a (H H ) şi folosim aceleaşi măsuri menţionate mai sus pentru a obţine

aproximaţiile lui H şi H relativ la R.

3.4.3. Compararea rezultatelor

S-au executat N_iter=1000 GRASP iteraţii pentru fiecare etapă descrisă în

tabelul 1. În acest tabel sunt descrise, pentru fiecare etapă numărul r de funcţii-obiectiv şi

numărul n de elemente. Timpul de compilare, măsurat în secunde, a algoritmului multi-

GRASP este scris în ultima coloană.

Valorile parametrilor (folosind la etapa de calculare ) şi (folosit la etapa

căutării locale) au fost 10 % şi 50 % respectiv, reprezentând cele mai bune rezultate.

S-a observat că este mul mai eficient de folosit > deoarece ne permite că la etapa

căutării locale, un număr mai mare de elemente să poată fi introduse în locul soluţiei

analizate.

Mai întâi, algoritmul propus este comparat cu algoritmul generic MOGLS

(Jaskiewiez 2002).

Tabelul 2 prezintă rezultatele comparate dintre algoritmul multi-GRASP şi

algoritmul MOGLS. În a -a coloană este prezentat nr

de soluţii. În următoarea coloană sunt prezentate pentru fiecare

algoritm şi fiecare etapă, numărul total de soluţii obţinute (TNS), numărul de soluţii

(NRS), şi distanţa medie (D ).

33

Iteraţie Timpul

consumatNume Obiective Elemente

Kn250_2 2 250 10

Kn250_3 3 250 94

Kn250_4 4 250 467

Kn500_2 2 500 67

Kn500_3 3 500 542

Kn500_4 4 500 1960

Kn750_2 2 750 204

Kn750_3 3 750 1259

Kn750_4 4 750 4120

Tabelul 1. Timpul consumat pentru fiecare iteraţie.

Etapa MOGLS GRASP-MULTI

TNS NRS D TNS NRS D

Kn250_2 209 178 0 1.22e-02 209 209 0

Kn250_3 5485 1464 1078 1.75e-02 4279 4242 4.40e-05

Kn250_4 22674 3952 3299 2.87e-02 19190 19099 1.23e-04

Kn500_2 357 249 0 1.68e-02 357 357 0

Kn500_3 13314 2360 1460 2.70e-02 11806 11803 3.54e-07

Kn500_4 46489 5699 4204 4.00e-02 42157 42157 6.47e-06

Kn750_2 555 356 3 1.75e-02 552 552 3.14e-06

Kn750_3 20286 2910 1073 2.97e-02 18561 18561 1.64e-07

Kn750_4 64796 6971 5178 4.53e-02 59515 59515 8.20e-06

Tabelul 2. Compararea algoritmilor MOGLS şi GRASP-MULTI (e-k=*10 ).

Rezultatele arată că algoritmul multi-GRASP obţine un număr mai mare de

soluţii de referinţă şi că acest algoritm este mai bun ca MOGLS în ceea ce priveşte

calcularea distanţei.

34

Algoritmul propus de asemenea este comparat cu algoritmul genetic Spea2

(Zitzler 2002) pentru etape cu n=750 elemente.

Etape SPEA2 GRASP-MULTI

TNS NRS D TNS NRS D

Kn750_2 552 250 0 1.51e-01 552 552 0

Kn750_3 18670 300 109 2.46e-01 18561 18561 0

Kn750_4 59636 350 121 3.58e-01 59515 59515 0

Tabelul 3. Compararea algoritmilor SPEA2 şi GRASP-MULTI (e-k=*10 )

Tabelul 3 arată numărul de soluţii de referinţă generate de SPEA2 şi multi-

GRASP. În acest tabel de asemenea este arătat, pentru fiecare algoritm şi fiecare etapă,

numărul total de soluţii obţinute, numărul soluţiilor de referinţă (NRS) şi distanţa medie

(D ).

Rezultatele arată că algoritmul multi-GRASP este mai eficient ca algoritmul

SPEA2 pentru probleme cu n=750 elemente.

3.5. Concluzii

Algoritmul GRASP generează o aproximaţie bună a unei mulţimi de soluţii

optime Pareto, a problemei combinatorii de optimizare multi-obiectiv. Algoritmul este

folosit pentru a rezolva problema rucsacului cu r funcţii-obiectiv şi este comparat cu

algoritmul MOGLS şi SPEA2. Rezultatele de la calculator arată că metoda propusă,

multi-GRASP, a obţinut pentru toate etapele efectuate, un număr de soluţii de referinţă

mult mai mare ca cele ale altor algoritmi euristici. Este de asemenea cea mai eficientă

metodă în ceea ce priveşte rezultatul soluţiilor obţinute (măsurate după distanţa dintre

soluţiile –D ). Bazându-ne pe rezultatele obţinute, putem conchide că algoritmul meta-

euristic GRASP poate fi folosit eficient pentru a rezolva probleme combinatorii de

optimizare multi-obiectiv.

35

CAPITOLUL IV

OPTIMIZAREA GLOBALĂ PRIN METODA GRASP CONTINUĂ

4.1. Introducere

Problemele de optimizare apar în cadre numeroase, incluzând decizii, inginerie,

şi ştiinţă. În multe situaţii, convexitatea funcţiei obiectiv (sau domeniul realizabil) nu

poate fi uşor verificată, şi este rezonabil pentru a presupune că problema este de

optimizare globală multiextremală. Optimizarea globală se ocupă de problemele de

optimizare cu multiple soluţii de extrem. Optimizarea în problemele globale poate fi

discretă sau continuă. Din punctul de vedere matematic, minimizarea globală

(optimizarea) caută o soluţie x*S Rn astfel ca f (x*)f(x), xS, unde S este un

domeniu din Rn şi funcţia obiectiv f este definită cu f :S R.. Aşa o soluţie x* se numeşte

soluţie minimă globală. O soluţie x' este minimă locală dacă într-o vecinătate locală

S0S, se verifică f (x1) f(x), xS0. Optimizarea globală abundă apare în multe

domenii, incluzând: biologia, chimia, genetica, ştiinţa militară, energetica, robotica,

ştiinţa de transportare etc.

În continuare prezentăm o metodă neobişnuită de optimizare globală, numită

Continuous-GRASP (C-GRASP), care extinde procedura de căutare GRASP de Feo şi

Resend din domeniul de optimizare discretă la aceea de optimizare globală continuă.

Euristici pentru optimizarea globală nu prea sunt în literatura de specialitate. Scopul

nostru este de a analiza o metodă locală de căutare aleatorie care este simplă pentru a o

pune în aplicare, poate fi aplicată pe un domeniu larg de probleme, şi care nu se

foloseşte de informaţii derivate, astfel creând un acces convenabil pentru rezolvarea

problemelor de optimizare globală. Se ilustrează eficacitatea procedurii pe un set de

probleme standard precum şi pe două probleme dificile de optimizare globală.

36

Procedure C-GRASP

(n,l,u,f(.),MaxIters,MaxNumIterNoImpro,NumTimesToRun,MaxDirToTry,)

1 f*;

2 for j=1,..., NumTimesToRun do

3 xUnifRand(l,u);h;NumIterNoImprov0;

4 for Iter=1,..., MaxIters do

5 xConstructGreedyRandomized(x, f(.),n,h,l,u, );

6 xLocalSearch(x, f(.),n,h,l,u,MaxDirToTry);

7 if f(x)<f* then

8 x*x; f*f(x); NumIterNoImprov0;

9 else

10 NumIterNoImprov NumIterNoImprov+1;

11 end if

if NumIterNoImprov MaxNumIterNoImpro then

hh/2; NumIterNoImprov0;

14 end if

15 end for

16 end for

17 return(x*);

end C-GRASP;

Figura 1. Pseudo-cod pentru C-GRASP

4.2. Metoda GRASP continuă

Feo şi Resende descriu euristica GRASP ca multi-pornire locală, unde

procedura GRASP a fiecărei iteraţii se compune din două faze, o faza de construire şi o

fază de căutare locală. Construirea combină procedeul greedz şi aranjarea aleatorie. Se

produce un set de pornire ca apoi să se pornească căutarea locală. Soluţia cea mai bună

peste toate iteraţiile este păstrată ca soluţie finală. GRASP a fost aplicat anterior la

numeroase probleme discrete de optimizare combinatorie. Aici ne oprim la optimizare 37

continuă globală.

Se prezintă euristica C-GRASP  pentru rezolvarea problemelor de optimizare

globală continuă. Fără a pierde din generalitate, noi luăm domeniul S ca un hiper

dreptunghi

S = {x =( x1,.. xn)Rn: l x u},

unde lRn şi uRn încît ui li,, pentru i=1,...,n.

Se consideră problema:

x* = argmin{f(x) | l x u }, unde f: RnR, şi l,x,uRn.

Pseudo-codul  pentru C-GRASP  este prezentat în Figură. Procedura ia

dimensiunea n de intrare a problemei, marginea inferioară şi superioară a vectorilor l şi u,

funcţia obiectiv f(.), precum şi parametrii MaxIter, MaxNumIterNoImprov,

MaxDirToTry, NumTimesToRun, şi .

În linia 1 din pseudo-cod, valoarea funcţiei obiectiv a celei mai bune soluţii

găsite (f*) este setată la infinit.

C-GRASP  este o procedură multi-start. Este repetat timpul NumTimesToRun în

ciclul de la linia 2 la linia 16. La fiecare iteratie, în linie 3, o soluţie iniţială x este punct

de pornire aleator distribuit în mod uniform peste Rn definit cu l şi u.

Procedure ConstructGredyRandomiyed (x, f(.),n,h,l,u,)

S{1,...,n};

While S0 do

Min+; max-;

for i=1,...,n do

if iS then

ziLineSerch(x,h,i,n, f(.),l,u);

gif(zi);

if min>gi then mingi;

if max<gi then maxgi;

end if

end for

38

RCL0;

for i=1,...,n do

if iS and gi(1-)*min+*max then

RCLRCL{i};

End if

end for

JRandomlySelectElement(RCL);

xjzj;SS\{j};

end while

return(x);

end ConstructGreedyRandomized;

Figura 2. Pseudo-codul pentru C-GRASP  faza de construire.

Parametrul h care controlează spaţiul de căutare discret, este readus la 1.

Găsirea soluţiei noi după căutarea locală este comparată cu cea mai bună soluţie

curentă în linia 7. Dacă soluţia nouă are o valoare obiectiv mai mică decît cea mai bună

soluţie curentă, atunci, în linia 8, cea mai bună soluţie curentă este actualizată cu soluţia

nouă, şi variabila NumIterNoImprov, care controlează grila densităţii de căutare, este

reiniţializat la 0. Altfel, în linia 10, NumIterNoImprov este sporită cu una. Dacă

NumIterNoImprov devine mai mare decît MaxNumIterNoImprov, grila densităţii este

sporită în linia 13, unde h este înjumătăţit şi NumIterNoImprov este reiniţializată la 0.

Aceasta permite ca C-GRASP  să înceapă cu o discretizare şi o sporire a densităţii

adaptabile după dorinţă, în felul acesta intensificînd căutarea într-o mai densă discretizare

cînd o soluţie bună are să fie găsită. Soluţia cea mai bună găsită, peste toate iteraţiile

NumTimesToRun, este reintoarsă.

Procedurile ConstructGreedyRandomized şi LocalSearch numite din C-GRASP 

sunt descrise în pseudo-coduri. Faza de construire (vedeţi pseudo-codul  în Figura 2) ia o

soluţie de intrare x. Începem să permitem a schimba toate coordonatele de x. Pe rînd, în

linia 6 a pseudo-codului  o linie caută sa fie executată în fiecare direcţie de coordonate

despărţită i de x cu alte n-1 coordonate ocupate de x la valorile lor curente. Valoarea z i

39

pentru i-th  coordonează minimizarea funcţiei obiectiv salvată, de asemenea ca valoarea

funcţiei obiectiv gi în liniile 6 şi 7 de pseudo-cod.

Procedure LocalSearch(x, f(.),n,h,l,u,MaxDirToTry)

1 Improvedtrue;D0;

2 x*x; f*f(x);

3 NumDirToTrymin{3n-1,NumDirToTry};

4 while Improved do

5 Improvedfalse;

6 while D NumDirToTry and not Improved do

7 Generate rUnifRand(1,3n-1)D;

8 DD{r};

9 dTernary1(r);xx*+h*d;

10 if lxu then

11 if f(x)<f* then

12 x*x; f*f(x);

13 D0;

14 Improvedtrue;

15 end if

16 end if

17 end while

18 end while

19 return(x*);

end LocalSerch;

Figura 3. Pseudo-codul  pentru C-GRASP  faza de căutare locală.

Alegerea coordonatei în acest mod garantează caracterul aleatoriu în faza de

construire. Noi continuăm procedura de mai sus pînă ce toate n coordonate au fost fixate. 40

La acea etapă, x este returnat de la faza de construire.

Faza căutării locale cu pseudo-cod este arătată în figura 3. Nu folosim

gradientele în C-GRASP deoarece gradientul nu este eficient calculabil pentru toate

funcţiie. De la o intrare, un punct dat xRn, algoritmul de căutare locală generează un set

de instrucţiuni şi determină direcţia, în cazul cînd, valoarea funcţiei de optimizare se

îmbunătăţeşte.

Pentru o problemă în două dimensiuni (şi cu uşurinţă generalizată la n

dimensiuni), şi pentru un punct dat x, obţinem direcţiile posibile pentru a fi analizate în

algoritmul de căutării locale. Ele sunt următoarele {(1,0),(0,1),(-1,0),(0,-1),(1,1),(-1,1),

(1,-1),(-1,-1)}. În general în spaţiul Rn, fiecare direcţie va fi un vector de lungimea n,

fiecare componentă fiind egală cu una dintre valorile {-1,0,1}. Este uşor de văzut că sunt

în total 3n-1 direcţii posibile ( noi excludem cazul când toate direcţiile vectorului sunt

nule).

Tabelul 1. Tripletele (n=2)

i Ternary(i) Ternary1(i) i Ternary(i) Ternary1(i)

1 01 {0,1}

3 10 {1,0}

5 12 {1,-1}

7 21 {-1,1}

2 02 {0,-1}

4 11 {1,1}

6 20 {-1,0}

8 22 {-1,-1}

Tabelul 2. C-GRASP – valoarea parametrilor

Parametri Valoarea Parametri Valoarea

0.4

MaxDirToTry 30

MaxNumIterNoImprov 20

h(valoarea start) 1

MaxIters 200

NumTimesToRun 20

Pornind la punct x*, în ciclul de la linia 6 la linia 17, noi construim ascendent

direcţiile distincte aleatorii. În linia 9, direcţia d este construită, şi punctul de test x =

x*+h*d este calculat, unde h este parametrul definit mai devreme care controlează

densitatea de discretizare. Dacă punctul de test x este realizabil şi este mai bun decat x*,

41

atunci x* este aşezat la x şi se restartează procesul cu x* ca pornire a soluţiei. Este

important de notat că alegerea setului de direcţie poate schimba de fiecare dată acest

proces , precum şi ordinea în care aceste direcţii sunt luate în consideraţie. Cînd noi

găsim un punct x* cu f( x*) f(x*+h*d) pentru fiecare din NumDirToTry sunt alese

direcţiile d, noi declarăm x* să fie optim local şi returnat.

4.3. Concluzii

În acest capitol, noi am prezentat o nouă euristică numită GRASP continuă, sau

C-GRASP,  pentru optimizarea globală continuă. După cum se vede în Secţiunea 2,

algoritmul este uşor de descris şi implementat. În plus, nu se foloseşte de nici o derivată,

de nici o informaţie suplimentară, fiind o metodă de rezolvare ideală pentru probleme de

tipul cutiei negre. Poate fi arătat că pentru un set de funcţii testate standard, C-GRASP

euristic aproape întotdeauna se concentrează la optimul global în foarte scurt timp.

42

CAPITOLUL V

APLICAŢII

5.1. Repartizarea investiţiilor capitale

Programarea dinamică este şi o metodă de calcul pentru rezolvarea

problemelor de optimizare de o anumită structură. Problema dată cu n variabile se

prezintă ca un proces cu mai mulţi paşi de luare a deciziilor. La fiecare pas se

determină extremul funcţiei de o singură variabilă.

Cunoaşterea metodei programării dinamice e cel mai bine de început cu

analiza problemei neliniare de repartizare a resurselor la întreprinderile unei

asociaţii sau ramurii. Putem considera că e vorba de repartizarea investiţiilor

capitale.

Fie că sunt indicate n puncte unde trebuiesc construite sau reconstruite

întreprinderile aceleiaşi ramuri, pentru aceasta fiind alocată suma de b lei. Vom

nota prin f j ( x j ) creşterea capacităţii sau venitul la întreprinderea cu numărul j,

dacă ea va primi x j lei din investiţiile capitale. Trebuie găsit aşa un mod de

repartizare a investiţiilor capitale (x1, ,x2,...,xn) la întreprinderi, care maximizează

suma veniturilor:

z = f(x1) + f(x2) + ... + f(xn),

păstrează suma investiţiilor capitale

x1+x2+...+xn=b

şi vom considera că variabilele xj pot lua doar valori întregi

xj .

Funcţiile fj (xj) le considerăm date, dar observăm că determinarea lor este o problemă economică complicată.

Vom folosi metoda programării dinamice la rezolvarea acestei probleme.

Introducem parametrul stării şi determinăm funcţia stării. Pentru parametrul stării ξ

primim suma de lei, alocată pentru cîteva întreprinderi, iar funcţia stării Fk(ξ) o 43

determinăm ca venitul maximal al primelor k întreprinderi, dacă ele împreună

primesc suma de ξ lei. Parametrul ξ poate lua valori de la 0 la b. Dacă din ξ lei

întreprinderea k primeşte xk lei, atunci restul ξ - xk trebuie să fie repartizaţi

întreprinderilor de la prima pînă la (k-1), aşa încît să primească venitul maximal Fk-1 (ξ -

xk). Atunci venitul a k întreprinderi va fi egal cu

f k ( x k ) + F k - 1(ξ-x k)

Trebuie de ales pentru xk o valoare între 0 şi ξ încît suma aceasta să fie maximă şi

ajungem la forma recurentă

pentru k = 2,3, ... ,n.. Dacă k = 1 atunci F1(ξ) = f1 (ξ)

Să analizăm un exemplu concret. Presupunem că asociaţia constă din patru

întreprinderi (n = 4). Suma investiţiilor capitale constituie 700 mii lei (b = 700),

repartizate întreprinderilor le împărţim la 100 mii lei. Valorile funcţiei fj (xj) sunt

indicate tab.l unde, de exemplu, numărul 88 arată că dacă întreprinderea a treia a

asociaţiei , primeşte 600 mii lei din investiţiile capitale atunci venitul va constitui 88 mii

lei.

TAB.1

xj 0 100 200 300 400 500 600 700

f1(x1)=F1(x1) 0 20 34 46 53 55 60 60

f2(x2)=F2(x2) 0 18 29 45 62 78 90 98

f3(x3)=F3(x3) 0 25 41 52 74 82 88 90

f4(x4)=F4(x4) 0 30 52 76 90 104 116 125

44

Mai întîi completăm tabelul 2. Adunăm valoarea f 2(x2) cu valoarea

F1(ξ – x2) = f1(ξ – x2) şi pe fiecare diagonală găsim cel mai mare număr, pe care îl

notăm cu steluţă şi îi indicăm valoarea x2(ξ). Completăm tab.3.

Continuăm procesul prin tabelarea funcţiilor F3(ξ), x 3(ξ) ş. a. m. d.

TAB. 2

ξ – x2 0 100 200 300 400 500 600 700

X2 F1(ξ – x2)

f2(x2)

0 20 34 46 53 55 60 60

0 0 0 20* 34 46 53 55 60 60

100 18 18 38* 52* 64 71 73 78

200 29 29 49 63 75 82 84

300 45 45 65* 79 91 98

400 62 62 82* 96 108

500 78 78 98* 112*

600 90 78 110

700 98 98

TAB. 3

ξ 0 100 200 300 400 500 600 700

F2(ξ) 0 20 38 52 65 82 98 112

0 0 100 100 300 400 500 500

45

TAB. 4

ξ – x3 0 100 200 300 400 500 600 700

X3 F2(ξ – x3)

f3(x3)

0 20 34 46 53 55 60 60

0 0 0 20 38 52 65 82 98 112

100 25 25* 45* 63* 77 90 107 123

200 41 41 61 79* 93 106 123

300 52 52 72 94* 112 126*

400 74 74 94* 112* 126*

500 82 82 102 120

600 88 88 106

700 90 90

TAB. 5

ξ 0 100 200 300 400 500 600 700

F3(ξ) 0 25 45 63 79 94 112 126

0 100 100 100 200 400 400 400

În tabelul 6 completăm numai diagonala pentru ξ = 700. Cel mai mare

număr pe această diagonală :

Zmax= 155 mii lei,

însă întreprinderii a patra trebuie să i se repartizeze

x = (7OO) = 3OO mii lei.

Celorlalte trei întreprinderi le rămîn 400 lei. Din tabelul 5 se observă că

celei de-a treia întreprinderi îi sunt repartizate

x = (7OO- x )= (400) = 200 mii lei.

Continuăm procesul invers şi observăm că46

x = (700- x -x ) = (200) = 100 mii lei.

Şi primei întreprinderi îi revine suma

x = 700- x - x - x = 100 mii lei.

Deci cea mai binevenită repartizare a capitalului la întreprinderi ar fi

următoarea : x = 100; x = 100; x =200; x =300.

Această repartizare va asigura asociaţiei cel mai mare venit posibil : 155 mii lei.

TAB. 6

ξ – x4 0 100 200 300 400 500 600 700

X4 F3(ξ – x4)

f4(x4)

0

0

20

25

38

45

52

63

65

79

82

94

98

112

112

126

0 0 126

100 30 142

200 52 146

300 76 155*

400 90 153

500 104 149

600 116 141

700 125 125

47

5.2. Problema rucsacului

Se consideră problema:

unde b, aj N, j=1,...,n, N- mulţimea numerelor naturale. Pentru m N vom

utiliza următoarea notaţie:

N(m) = {0, l,2,...,m}.

Metoda de rezolvare a acestei probleme

Metoda de rezolvare a acestei probleme ne vom imagina-o ca un proces din

n etape, fiecare etapă k, k = 1,... , n , constînd din umplerea optimă a rucsacului [3]

numai cu obiectele de tipul 1,2,...,k.

La prima etapă problema se rezolva elementar. Daca b se divide cu a1 fără

rest, atunci costul rucsacului va fi egal cu:

f1(b)=

În caz contrar - se încalcă condiţia de integritate a obiectelor cu care se

încarcă rucsacul şi problema de încărcare cu obiecte numai de tipul 1 nu are soluţie

în numere întregi, convenţional notînd în acest caz f1(b) = -∞.

Aşadar, în prima etapă se utilizează funcţia:

unde

48

La etapa a doua se rezolva ecuaţia

funcţională:

Clar că o soluţionare efectivă necesită valorile funcţiei f 1(τ) în

, însăşi metoda constînd din tabelarea funcţiei c2x2+fi (b-a2x2)

corespunzător lui x2 N( ) şi alegerea variantei pentru care c2x2+fj(b-a2x2) este

maximă. Evident că ecuaţia are soluţie numai în cazul în care există cel

puţin o valoare x2 N( )pentru care are loc f1(b-a2x2)≠-∞. Dacă pentru o

careva valoare x2 N( ) are loc f1(b-a2x2)= -∞, atunci perechea x1 = b-a2x2,

x2 nu satisface restricţia problemei rucsacului.

La etapa a treia se consideră ecuaţia funcţională:

rezolvarea căreea necesită valorile funcţiei f 2(τ) în Metoda de

rezolvare ramîne aceiaşi: tabelarea în x3 N a funcţiei c3x3+f2(b-a3 x3),

urmată de alegerea maxime a funcţiei c3x3+f2(b-a3 x3), urmată de alegerea maximei.

mod analogic, la etapa k, k > 3, se consideră ecuaţia funcţională

recurentă.

Avem ecuaţia recursivă :

49

Ea se rezolvă prin tabelarea funcţiei în corespundere cu xk

N( ) şi prin alegerea în fine a maximei.

Deoarece la etapa k+1 se utilizează valorile funcţiei fk(τ) e

rezonabil ca la etapa k să se tabeleze nu numai funcţia ci şi

funcţia fk(τ). Excepţie fac numai: etapa 1, în care se tabelează doar funcţia

f1(τ), corespunzător lui şi etapa n, în care se tabelează doar funcţia

pentru xn N( ) .Sumînd cele expuse, putem trage concluzia

că algoritmul de soluţionate a problemei rucsacului se reduce la o consecutivitate de

n paşi, pasul k, k=l,n, constînd din construirea unui tabel din patru coloniţe, ultimele

două, la trecerea la pasul k+1, fiind înlocuite cu valorile pentru care au soluţii

ecuaţiile funcţionale:

τ=0,b

Aşadar, în etapa (pasu1 10) k soluţiile ecuaţiilor funcţionale se determină

din tabelul:

Τ fk(τ) Xk

τ =0 fk(0) 0 fk-1(0)

50

τ =1 fk(1) 0 fk-1(1)

… … … …

τ =b fk(b) 0

1

2

...

fk-1(b)

…

Cînd se trece la etapa(pasul) k+l, tabelul de mai sus se salvează sub forma:

Τ fk(τ)

τ=0 fk(0) 0

τ=l fk(1)

… … …

τ=b fk(b)

unde este soluţia ecuaţiei funcţionale corespunzătoare lui τ .

La ultima etapă, e suficient să se determine pentru funcţia fn(τ) numai

valoarea fn(b)

În concluzie, problema rucsacului se rezolvă în baza relaţiilor:f1(τ)= , dacă

k=1 şi τ se divide cu a1 f1(τ)=-∞, dacă k=1 şi τ se divide cu a1

τ=0,b, dacă k>1

51

Exemplu particular

Să se soluţioneze problema rucsacului:

z=3x1+2x2+5x3+x4+4x5 → max

2x1+2x2+3x3+x4+2x5=8

xj N

Rezolvare. Conform celor expuse, la pasul 1 alcătuim tabelul:

La pasul 2 avem ecuaţiile recurente:

τ=0,8

În baza lor alcătuim tabelul:

Τ f1(τ)

0 0 0

1 -∞

2 3 1

3 -∞

4 6 2

5 -∞

6 9 3

7 -∞

8 12 4

52

T f1 (τ) X2 2x2+f1(τ-2xk) T f1 (τ) X2 2x2+f1(τ-2xk)

0 0 0 0+f1(0) 6 9 0

1

2

3

0+f1(6)= 9

2+f1(4)= 8

4+f1(2)= 7

6+f1(0)= 61 0 0+f1(1)= -∞ 7 0

i

1

2

3

0+f1(7)= -∞

2+f1(5)= -∞

4+f1(3)= -∞

6+f1(1)= -∞

2 3 0

1

0+f1(2)= 3

2+f1(0)=2

8 12 0

1

2

3

4

0+f1(8)=12

2+f1(6)=11

4+f1(4)= 10

6+f1(2)=9

8+f1(0)=0

3 0 0+f1(3)= -∞

2+f1(1)= -∞

4 6 0

1

0+f1(4)= 6

2+f1(2)=5

4+f1(0)=4

5 0

1

2

0+f1(5)= -∞

2+f1(3)= -∞

4+f1(1)= -∞

Să menţionăm că în coloana a doua se înscriu valorile maxime

(corespunzătoare valorii τ ) din coloana a patra, adică înscrierile în coloana a doua

se efectuează numai după efectuarea înscrierilor de rigoare în coloana a patra.

Trecînd la pasul următor, tabelul obţinut îl salvăm sub forma:

53

Τ f2(τ)

0 0+f1(0)=0 0

1 -∞ 0

2 2*0+f1(2)= 3 0

3 -∞ 0

4 2*0+f1(4)=6 0

τ f2(τ)5 -∞ 06 2*0+f1(6)=9 07 -∞ 08 2*0+f1(8)=12 0

La pasul trei se rezolvă ecuaţiile:

f3(τ) = max {5x3-f2(τ-3x3)}, τ= 0,

În mod analogic se construieşte tabelul pasului trei, care la trecere la

pasul patru se memorizează sub forma:

τ f3(τ) τ f3(τ)

0 5*0+f2(0)=0 0 5 5*1+f2(2)=8 11 -∞ 0 6 5*2+f2(0)=10 22 5*0+f2(2)=3 0 7 5*1-f2(4) =11 13 5*1+f2(0)=5 1 8 5*2+f2(2)=13 24 5*0+f2(4)=6 0

La pasul patru se rezolvă:

f4 (τ) = max {x4+f3(τ-x4)},τ= 0,8

care au soluţiile:

τ f4(τ) τ f4(τ)

0 0 0 5 0+f3(5)=8 01 1+f3(0)=1 1 6 0+f3(6)=10 12 0+f3(2)=3 0 7 1+f3(6)=11 03 0+f3(3)=5 0 8 0+f3(8)=13 04 1+f3(3)=6 1

La ultimul pas ne putem limita la rezolvarea doar a ecuaţiei funcţionale:

f5 (τ) = max {4x5+f4(τ-2x5)},τ= 0,8

vom obţine soluţiile chiar a 9 probleme, corespunzător valorilor

τ f5(τ) τ f5(τ)

0 0 0 5 4*2+f4(1)=9 21 0+f4(1)=1 1 6 4*3+f4(0)=12 32 4*1+f4(0)=4 1 7 4*3+f4(1)=13 33 4*1+f4(1)=5 1 8 4*4+f4(0)=16 44 4*2+f4(0)=8 2

Din ultimul tabel aflăm că maxima funcţiei obiectiv a problemei date este egală cu

=16. Soluţia problemei pentru o careva valoare τ se determina prin parcurgerea în ordine

inversă a tabelelor paşilor 4,3,2,1, în care se selectează valorile componentelor optime

corespunzătoare.

De exemplu, pentru τ =7, f5(7) = =4*3+f4(1) = 13, x5*=3. Valoarea variabilei x4 o

determinăm din tabelul pasului patru - din linia corespunzătoare lui f4(1)=1+f3(0). Din ea

reiese ca =1. Valoarea x3*=0 se determină din linia corespunzătoare lui f3(0). În

continuare aflăm ca =0 şi =0

Exact prin acelaşi procedeu se determină soluţia corespunzătoare lui

f5(8)=4*4+f4(0) = I6, care este egală cu x=(0,0,0,04)T.

Răspuns: Costul maxim zmax= 16 rucsacul îl are dacă e incarcat cu patru obiecte de tipul

cinci. Deci x*=(0.0,0,0,4).T

Anexă

Listingul programului

#include<stdio.h>

#include <stdlib.h>

#include<conio.h>

int i,par,min,k,j,s,x[100],xmin[100],a[100],c[100];

int b,n;

int f(int x[100], int c[100]);

{

int i,s=0;

for(i=0;i<n;i++)

s+=c[i]*x[i];

return s;

}

void generate()

{

int i;

for(i=0;i<n;i++)

{

x[i]=random(b/a[i]);

printf("x=%i ",x[i]);

}

printf("\n");

}

void localsearch()

{

par=-1;

for(i=0;i<n;i++)

{

x[i]+=1-random(3);

if(x[i]b/a[i]) x[i]=b/a[i];

if(x[i]<0) x[i]=0;

printf("x=%i ",x[i]);

}

printf("\n");

}

void suma()

{

s=0;

for(i=0;i<n;i++)

s+=a[i]*x[i];

}

void comparare_f()

{

par=1;

printf("F=%i",f(x,c));

if(minf(x,c))

{

min=f(x,c);

for(i=0;i<n;i++)

xmin[i]=x[i];

}

}

void rezultate(FILE *out)

{

fprintf(out,"\n Problema rucsacului este");

fprintf(out,"%s%i\n ","pentru n=",n);

fprintf(out,"%i \n ",min);

printf("\n\nmin=%i\n\n",min);

for(i=0;i<n;i++)

{

printf("x=%i ",xmin[i]);

fprintf(out,"%i ",xmin[i]);

}

printf("\nValorile c sunt\n");

for(i=0;i<n;i++)

printf("%4d",c[i]);

printf("\nValorile a sunt\n");

for(i=0;i<n;i++)

printf("%4d",a[i]);

printf("\nCu valoarea lui b=%d\n",b);

fprintf(out,"\n\nValorile c sunt\n");

for(i=0;i<n;i++)

fprintf(out,"%4d",c[i]);

fprintf(out,"\nValorile a sunt\n");

for(i=0;i<n;i++)

fprintf(out,"%4d",a[i]);

fprintf(out,"\nCu valoarea lui b=%d\n",b);

}

void main()

{

FILE *in, *out;

if ((out = fopen("d:\\Rezultat.txt", "wt"))== NULL)

{

printf("Cannot open output file.\n");

}

if ((in = fopen("c:\\Date.txt", "rt"))== NULL)

{

printf("Cannot open input file.\n");

}

int i;int ty;

for (ty=0;ty<8;ty++)

{

par=1;min=5000;

fscanf(in,"%d",&n);

for (i=0;i<n;i++)

fscanf(in,"%d",&c[i]);

for (i=0;i<n;i++)

fscanf(in,"%d",&a[i]);

fscanf(in,"%d",&b);

randomize(); int o=0;

acolo:clrscr();

for(j=0;j<1000;j++)

{

if(par==1)

generate();

suma();

if(s==b)

comparare_f();

else localsearch();

}

if (min==5000)

rezultate(out);

getch();

}

fclose(out);

fclose(in);

}

Rezultatele testării programului

Problema rucsacului pentru n=1:min=14x=7Valorile c sunt 2Valorile a sunt 3Cu valoarea lui b=21

Problema rucsacului pentru n=2:min=6x=6 x=0Valorile c sunt 1 2Valorile a sunt 2 3Cu valoarea lui b=12

Problema rucsacului pentru n=3:min=8x=2 x=0 x=2Valorile c sunt 1 2 3Valorile a sunt 3 3 4Cu valoarea lui b=14

Problema rucsacului pentru n=4:min=45x=1 x=4 x=6 x=6Valorile c sunt 1 2 3 3Valorile a sunt 4 3 2 1Cu valoarea lui b=34

Problema rucsacului pentru n=5:min=31x=2 x=1 x=2 x=4 x=1Valorile c sunt 1 2 3 4 5Valorile a sunt 8 7 5 1 7Cu valoarea lui b=44

Problema rucsacului pentru n=6:min=34x=0 x=8 x=2 x=0 x=0 x=2Valorile c sunt 4 2 6 4 2 3Valorile a sunt 6 2 1 6 3 1Cu valoarea lui b=20

Problema rucsacului pentru n=7:min=41x=0 x=1 x=0 x=1 x=9 x=2 x=0Valorile c sunt 1 5 2 1 3 4 1Valorile a sunt 5 2 4 7 1 2 1Cu valoarea lui b=22

Problema rucsacului pentru n=8:min=9x=0 x=0 x=0 x=4 x=1 x=0 x=1 x=0Valorile c sunt 7 2 5 1 4 6 1 8Valorile a sunt 8 2 5 1 7 3 6 2Cu valoarea lui b=17

BIBLIOGRAFIA

1. Valeriu Ungureanu. Programarea matematică, Chişinău, 2001.

2. Emil Boroş, Dumitru Opriş. Introducere în optimizarea liniară şi aplicaţii,

Timişoara, Facla, 1979.

3. Vasile Nica, Capitole speciale ale cercetărilor operaţionale. Tipografia ASE Bucureşti,

2004.

4. C. H. Mihoc, A. Ştefanescu. Progamarea matematică, Bucureşti, 1973.

5. Р.Беллман. Динамическое програмирование, Москва, 1960.

6. X. Пападимитриу, К. Стайглиц. Комбинаторная оптимизация, Москва, Мир, 1985.

7. Б. Алексеев, Б. Тихомиров, K. Фомин. Оптимальное управление, Москва, Наука,

1979.