C A P I T O L U L III

PROBLEME DE OPTIMIZARE DE DIMENSIUNI MARI

§1. Problema dimensiunii în rezolvarea efectivă a problemelor de optimizare practice

Principala cauză generatoare de dificultăţi în rezolvarea problemelor de optimizare reale este dimensiunea: o asemenea problemă este pur şi simplu "prea mare". În programarea matematică, mărimea unei probleme este o chestiune relativă, depinzând de mulţi parametri cum ar fi:

· numărul de variabile şi numărul de restricţii;

· complexitatea expresiilor funcţiei obiectiv şi a restricţiilor;

· performanţele echipamentului de calcul: hardware şi software.

Utilizarea modelelor matematice în studiul unor situaţii reale - în special din domeniul economic - a condus la programe matematice care suprasolicită şi cele mai puternice calculatoare.Din fericire, marea majoritate a problemelor de optimizare "mari" au o "structură specială" care, în programarea liniară de exemplu, înseamnă:

· densitate mică a constantelor numerice nenule;

· gruparea elementelor nenule în blocuri aşezate "pe diagonală";

· număr foarte mare de variabile şi relativ puţine restricţii sau invers, multe restricţii şi puţine variabile.

Trebuie spus că dacă un program liniar mare nu are o structură specială, sarcina colectării datelor este practic aproape imposibil de realizat; astfel pentru un program cu 10⁴ restricţii şi 10⁶ variabile, matricea coeficienţilor ar avea 10¹⁰ intrări şi în cazul unei densităţi de 100% ar necesita 10¹⁰ date numerice de adunat, sortat şi prelucrat!!

Pentru programele neliniare, complexitatea şi structura specială se caracterizează mult mai greu.

§2. Clasificarea metodelor de rezolvare a programelor liniare mari

În principiu metodele de rezolvare a programelor mari se împart în două categorii:

· metode directe: acestea specializează o procedură generală adaptând-o la specificul unei anumite clase de probleme de optimizare.

Exemplul tipic îl constituie algoritmul simplex; este ştiut că principala problemă de calcul care apare în aplicarea lui o constituie modul de manipulare a inversei bazei curente. În cazul unei "structuri speciale" este posibil ca dimensiunea acestei matrici să se reducă semnificativ.

Să considerăm cazul unui program liniar cu variabile superior mărginite:

Abordarea "clasică" presupunea transformarea condiţiilor de limitare superioară în egalităţi:

Rezulta un program cu m+n restricţii şi 2n variabile, ale cărui baze erau matrici de ordinul m+n.

Totuşi forma particulară a restricţiilor de limitare superioară a putut fi exploatată eficient într-o specializare a algoritmului simplex în care inversa bazei curente are dimensiunea egală cu numărul m al restricţiilor propriu zise.

· metode indirecte, bazate pe descompunerea problemei mari în subprobleme mai mici, interconectate. Subproblemele pot fi rezolvate independent (şi dacă este posibil chiar simultan) dar faptul că ele interacţionează implică existenţa unui mecanism (problemă) de coordonare. Astfel, rezolvarea problemei originale mari se face "la două nivele":

· la primul nivel - inferior - se rezolvă subproblemele; rezultatele sunt "comunicate":

· la al doilea nivel - superior - care "analizează" aceste rezultate şi transmite nivelului inferior noi parametri.

La nivelul unu are loc o reluare a calculelor (reoptimizare); noile rezultate sunt trimise nivelului superior care le analizează ş.a.m.d.

Important este faptul că acest proces iterativ este convergent în sensul că într-un număr finit de paşi (º dialoguri între cele două nivele), nivelul coordonator "anunţă" găsirea soluţiei optime.

§3. Descompunere în programarea liniară. Principiu

Considerăm un program liniar în formă standard:

în care:

T º matrice m´n;

x º coloana celor n variabile;

t º coloana celor m termeni liberi;

c º linia celor n coeficienţi din funcţia obiectiv.

Pentru moment, nu vom face nici o ipoteză asupra "mărimii" programului (P) sau asupra structurii sale. Ştim că (P) poate fi rezolvat "dintr-o dată" cu ajutorul algoritmului simplex. Ne propunem să arătăm cum poate fi rezolvat (P) prin descompunerea sa în mai multe subprobleme mai mici, intercorelate.

Vom împărţi sistemul Tx=t al restricţiilor în două blocuri (partiţionarea este deocamdată arbitrară):

· blocul Ax=b cu m₁ < m restricţii;

· blocul Mx=d cu m₂ =m - m₁ restricţii

Considerăm mulţimea soluţiilor admisibile ale sistemului liniar Ax=b:

A ={x Î Rⁿ | Ax = b , x ³ 0}

Este bine cunoscut faptul că A este o mulţime convexă şi chiar poliedrală (adică o intersecţie finită de semispaţii din Rⁿ). Ea are un număr finit de vârfuri v¹,v²,...,v^s care se identifică cu soluţiile admisibile de bază ale sistemului Ax = b.

Pentru simplitatea expunerii, vom presupune în continuare că mulţimea A este mărginită (această ipoteză este îndeplinită în mai toate cazurile practice).

Un rezultat clasic al analizei convexe arată că orice punct al mulţimii poliedrale şi mărginite A se scrie ca o combinaţie convexă a vârfurilor ei:

unde:

şi

Înlocuind în blocul Mx = d şi în funcţia obiectiv f = cx obţinem:

Cu notaţiile:

programul (P) se scrie echivalent:

în care variabilele sunt scalarii

Dacă este o soluţie optimă a programului (PM) atunci este o soluţie optimă a programului original (P).

Programul (PM) se numeşte program coordonator (master program) şi are următoarele proprietăţi:

· are mai puţine restricţii decât (P): doar 1+m₂ faţă de m₁ + m₂ ;

· are în general un număr foarte mare de variabile, câte una pentru fiecare vârf al mulţimii A şi, după cum se ştie numărul acestor vârfuri estte de obicei "impresionant";

· rezolvarea programului (PM) necesită - cel puţin la prima vedere - cunoaşterea vârfurilor v¹,v²,...,v^s fără de care nu se pot evalua colanele Q^k şi scalarii . Or, cunoaşterea apriorică a vârfurilor v¹,v²,...,v^s este o sarcină extrem de grea şi practic imposibil de făcut în mai toate cazurile!

Din fericire, rezolvarea programului (PM) nu necesită cunoaşterea apriorică a vârfurilor v¹,v²,...,v^s. După cum vom vedea în secţiunea 5, pe parcursul aplicării algoritmului simplex acestui program, vârfurile mulţimii A absolut necesare în optimizare vor fi generate (calculate) "la cerere" prin rezolvarea unor programe liniare de forma:

în care u este un vector linie ale cărui componente se stabilesc şi se modifică în funcţie de stadiul rezolvării programului (PM).

În esenţă, rezolvarea programului original (P) s-a redus la:

· rezolvarea programului coordonator (PM);

şi la:

· rezolvarea mai multor probleme de forma P(u)

toate de dimensiuni mai mici decât cele ale programului (P); vezi figura 3.1

Figura 3.1

Cele de mai sus constituie esenţa principiului de descompunere Dantzig - Wolfe. El poate fi folosit atunci când programul (P) are un număr foarte mare de restricţii. Descompunerea devine şi mai atractivă în cazul în care submatricea A are o structură diagonală

Figura 3.2

în care A¹,A²,...,A^p sunt matrici de diferite dimensiuni.Pentru simplificarea expunerii să presupunem că A are doar două blocuri A¹ şi A². Elementele constitutive ale programului (P) pot fi partiţionate astfel:

A b

M

Figura 3.3

Programul (P) are deci forma:

Û

Se observă uşor că în această situaţie, problema P(u) “se sparge” în două subprobleme independente (care pot fi rezolvate simultan!):

Schema de rezolvare “la două nivele” a programului (P) din figura 3.1 devine:

Nivel 2

Nivel 1

Figura 3.4

§4. O interpretare economică a principiului de descompunere

Să considerăm o economie cu mai mulţi agenţi. Fiecare agent operează un număr de activităţi de pe urma cărora obţine un venit. Operarea activităţilor implică utilizarea unor resurse disponibile în cantităţi limitate. Fireşte, obiectivul fiecărui agent este maximizarea venitului propriu.

Este clar că dacă fiecare agent ar deţine controlul asupra tuturor resurselor necesare lui atunci maximizarea venitului la scara întregii economii s-ar reduce la maximizarea venitului fiecărui agent în parte.

În realitate lucrurile stau altfel.

Fiecare agent deţine controlul asupra anumitor resurse: capacităţi proprii de producţie, forţa de muncă angajată, resurse financiare proprii, unele materii prime utilizate în exclusivitate.Acestea vor fi numite resurse specifice.

Pe lângă resursele specifice, fiecare agent utilizează şi alte resurse care nu sunt la dispoziţia sa exclusivă; aceste resurse sunt procurate de pe piaţă, la concurenţă cu ceilalţi agenţi, datorită faptului că sunt disponibile în cantităţi limitate. Acestea vor fi denumite resurse comune.

În acest context, problema principială care se pune este de a stabili cum vor fi repartizate resursele comune între agenţi astfel încât, la scara întregii economii, venitul să fie maxim.

Într-o economie centralizată, repartizarea resurselor comune este făcută de stat care indică fiecărui agent ce şi cât să producă.

Ne propunem să arătăm cum se face repartizarea comune într-o economie descentralizată în care autoritatea centrală nu mai deţine controlul asupra acţiunilor agenţilor.

Ne vom situa în cazul ideal al unei economii liniare, caracterizate prin următoarele ipoteze:

· pentru fiecare activitate, consumurile de resurse şi venitul sunt direct proporţionale cu nivelul la care este operată activitatea;

· nivelul de operare al unei activităţi poate fi reprezentat de orice număr real nenegativ;

· veniturile agenţilor nu se condiţionează reciproc şi sunt egale cu suma veniturilor activităţilor fiecăruia. Venitul la scara întregii economii este suma veniturilor agenţilor.

Pentru simplitatea expunerii vom presupune că în economia studiată există numai doi agenţi.

Introducem notaţiile:

x¹, x² º vectorii (coloană) nivelelor de operare ale activităţilor celor doi agenţi;

b¹ , b² º vectorii (coloană) cantităţîlor disponibile din resursele specifice;

A¹, A² º matricile consumurlor unitare de resurse specifice;

M¹, M² º matricile consumurilor unitare din resursele comune;

d º vectorul (coloană) cantităţilor disponibile de resurse comune;

c¹, c² º vectorii (linie) veniturilor unitare corespunzătoare celor doi agenţi.

Evident, nivelele de operare ale activităţilor agenţilor sunt condiţionate de disponibilele de resurse specifice:

A¹x¹ £ b¹ A²x² £ b² (4.1)

şi în plus:

x¹ ³ 0 x² ³ 0 (4.2)

Vectorii x¹, x² care satisfac relaţiile 4.1 - 4.2 se vor numi programe posibile de activitate.

Un cuplu de programe posibile (x¹, x²) devine realizabil numai dacă necesarul de resurse comune se încadrează în disponibilul dat adică:

M¹x¹ + M²x² £ d (4.3)

Venitul total pe economie are expresia:

f = c¹x¹ +c²x² (4.4)

Reunind (4.1 - 4.4) obţinem programul liniar:

(4.5)

care modelează problema repartizării resurselor comune în vederea maximizării venitului pe întreaga economie.

Observăm că matricea programului (4.5) are structura bloc diagonală cu restricţii de cuplare, identică cu structura pe care s-a prezentat, în secţiunea precedentă, principiul de descompunere Dantzig - Wolfe.

Din punct de vedere formal, problema repartizării resurselor comune într-o economie descentralizată înseamnă rezolvarea programului (P) în condiţiile în care nici agenţii nici autoritatea centrală nu au informaţii complete asupra acestuia. Astfel:

agentul 1 controlează (cunoaşte) b¹, A¹, M¹, c¹;

agentul 2 controlează (cunoaşte) b², A², M², c²;

autoritatea centrală controlează (cunoaşte) d.

Maximizarea venitului fiecărui agent, ţinând seama numai de resursele sale specifice, revine formal la rezolvarea programelor:

dar nu rezolvă problema repartizării resurselor comune deoarece, dacă şi sunt soluţiile optime ale programelor din (4.6), este posibil ca:

£ d

În continuare vom arăta - în principiu - cum poate fi rezolvat programul (P) din (4.5) în situaţia în care nici autoritatea centrală şi nici agenţii nu deţin informaţii complete asupra programului!

Vom presupune că:

· între autoritatea centrală şi agenţi există o cooperare în sensul unui schimb de informaţii privind "intenţiile"de acţiune;

· autoritatea centrală îşi asumă rolul de arbitru în următorul sens: ea "anunţă" un sistem de preţuri pe resursele comune iar agenţii iau aceste peţuri ca date şi îşi diminuează veniturile cu valoarea resurselor comune solicitate.Fie u vectorul (linie) al acestor preţuri.Atunci:

· agentul 1, pentru susţinerea unui program posibil x¹ (posibil º A¹x¹ £ b¹, x¹ ³ 0),va trebui să "plătească" valoarea uM¹x¹ astfel că venitul său "net" va fi:

· analog, venitul agentului 2, rezultat din programul posibil x² (A²x² £ b², x² ³ 0), va fi:

Maximizarea acestor venituri nete înseamnă rezolvarea programelor modificate:

Agenţii comunică autorităţii centrale propunerile optimale şi . În principiu,autoritatea centrala analizează oportunitatea luării în considerare a acestor propuneri pentru maximizarea venitului pe economie şi poate decide modificarea sistemului de preţuri, mărind preţurile resurselor comune "intens" solicitate.

Noile preţuri sunt comunicate agenţilor; aceştia vor căuta noi soluţii care să le maximizeze veniturile nete "corectate". Evident, prin creşterea preţurilor la anumite resurse comune, cererile "excesive" din aceste resurse vor fi "temperate". Formal, cele spuse înseamnă reluarea programelor P₁(u), P₂(u) cu u modificat!

Important este că într-un număr finit de asemenea "dialoguri º schimburi de informaţii" între agenţi şi autoritatea centrală, vor rezulta soluţiile şi care maximizează venitul total pe economie. În general, şi nu coincid cu una sau alta dintre propunerile agenţilor ( propuneri făcute în cadrul dialogului sus amintit) ci sunt combinaţii convexe ale acestora. Tot odată va rezulta şi un sistem u^* de preţuri pe resursele comune în raport cu care şi maximizează veniturile nete individuale ale agenţilor! Spuunem că tripletul (,,u^*) reprezintă un echilibru pentru economia (liniară) considerată.

Dialogul dintre autoritatea centrală şi agenţi poate fi reprezentat astfel:

Nivel 2

Propuneri de programe

de activitate

Nivel 1

Figura 4.1

Comparând această schemă cu cea din figura 3.4 se constată că cele spuse mai sus constituie o interpretare economică a principiului de descompunere Dantzig - Wolfe.

§5. Algoritmul de descompunere Dantzig - Wolfe

În această secţiune vom arăta cum se rezolvă efectiv programul principal (PM) din secţiunea 3.

Să admitem pentru moment că am cunoaşte toate constantele programului (PM). Vom aplica acestui program versiunea revizuită a algoritmului simplex.

Să presupunem cunoscută o bază admisibilă B; în raport cu această bază partiţionăm vectorul l al variabilelor:

unde l^B este vectorul variabilelor bazice iar l^S al celor nebazice.

Soluţia asociată bazei B va avea forma:

B fiind presupusă admisibilă, . Fie:

vectorul multiplicatorilor simplex asociaţi bazei B (g^B este vectorul format din coeficienţii g_k ai variabilelor bazice l_k din l^B)

Valoarea funcţiei obiectiv f în soluţia de bază este:

Elementele numerice B^-1, şi p sunt reunite în următorul tabel simplex redus:

l^B		B^-1
f		p

Tabelul 5.1

Din necesităţi care vor deveni evidente imediat, partiţionăm p astfel: p = (p₀,u)

p₀ fiind prima componentă din p iar u reunind pe celelalte.

Testarea optimalităţii soluţiei necesită calcularea costurilor reduse:

După cum este bine ştiut, dacă atunci este o soluţie optimă a programului (PM). Pentru a vedea dacă se întâmplă acest lucru evaluăm:

Se observă că este valoarea maximă a funcţiei liniare pe vârfurile mulţimii poliedrale mărginite A .

Conform teoremei centrale a programării liniare [9] , evaluarea acestui maxim nu necesită cunoaştera apriorică a vârfurilor v¹,...,v^s; este suficient să se rezolve programul liniar:

Fie v^* o soluţie optimă a programului P(u) şi valoarea funcţiei obiectiv în v^*. v^* este unul din vârfurile mulţimii A şi putem scrie:

astfel că:

Dacă ( în fapt !) atunci soluţia este optimă.

Dacă se calculează Q^* = Mv^* , şi se introduce în baza curentă coloana .

După evaluarea coloanei se determină coloana care părăseşte baza actuală şi se pivotează tabelul simplex redus curent, intrându-se într-o nouă iteraţie.

Din descrierea făcută rezultă clar că ameliorarea soluţiei admisibile de bază - presupusă dată - nu a necesitat cunoaşterea de la început a tuturor vârfurilor mulţimii A ; vârful necesar în procesul de optimizare s-a obţinut rezolvând un program liniar de forma P(u) cu un vector u adecvat.

În ceeace priveşte obţinerea unei soluţii de bază iniţiale pentru programul (PM), aceasta se poate obţine în maniera uzuală. Se pleacă de la o bază unitară ale cărei coloane corespund:

· (unele) unor (eventuale) variabile de abatere existente în blocul Mx = d;

· (altele) unor variabile artificiale introduse în anumite ecuaţii ale blocului Mx = d şi/sau în ecuaţia de convexitate .

În cazul în care au fost efectiv folosite variabile artificiale, într-o primă fază se va minimiza suma w a acestora. Coloanele care vor intra în bază se vor genera după schema generală de mai sus, funcţia f fiind înlocuită cu funcţia w care se minimizează!!

Exemplu 5.1 Se consideră o economie liniară descentralizată cu doi agenţi, fiecare oprând câte o activitate. Fie x₁ şi x₂ nivelele de operare ale celor două activităţi. Resursele specifice controlate de către cei doi agenţi limitează nivelele activităţilor după cum urmează:

x₁ £ 4 , x₂ £ 3

Susţinerea activităţilor necesită două resurse comune R₁ şi R₂ al căror disponibil este limitat şi controlat de o "autoritate centrală". La un nivel de operare egal cu unitatea, vectorii consumurilor din resursele R₁ şi R₂ sunt: pentru prima activitate şi pentru a doua. Vectorul cantităţilor disponibile din resursele R₁ şi R₂ este . În fine, veniturile unitare sunt de 7 u.m. (unităţi monetare) în prima activitate şi de 6 u.m. în a doua.

Fiecare agent caută să obţină un venit cât mai mare, dar ei nu deţin controlul asupra resurselor comune. Pe de altă parte, economia fiind descentralizată, autoritatea centrală nu poate impune agenţilor nivelele la care să opereze activităţile proprii.

Obiectivul urmărit este maximizarea venitului total pe economie.

Formal, problema constă în rezolvarea programului liniar:

în situaţia încare nici agenţii, nici autoritatea centrală nu deţin "informaţii complete" asupra programului (P).

După cum am văzut, rezolvarea este posibilă prin cooperarea dintre agenţi şi autoritatea centrală, pe baza algoritmului de descompunere Dantzig - Wolfe.

Partiţionăm sistemul restricţiilor în două blocuri:

Principiul de descompunere propune rezolvarea programului:

în care:

unde v¹,...,v^s sunt vârfurile mulţimii poliedrale:

A =

Este evidentă mărginirea mulţimii A .

O dată obţinută soluţia optimă a programului propus, soluţia optimă a programului original (P) va rezulta din formula:

Aplicăm algoritmul simplex revizuit formei standard:

Variabilele de abatere y₁ , y₂ arată ce cantităţi din resursele comune R₁ , R₂ rămân nefolosite.

Programul (PM) are trei restricţii şi se vede uşor că matricea sa conţine coloanele unitare şi corespunzătoare variabilelor y₁ , y₂. Pentru o bază unitară de start ne-ar trebui şi coloana care nu este tot aşa de "vizibilă". Am putea introduce o variabilă artificială în restricţia de convexitate , dar putem proceda, mai simplu, şi astfel:

Se observă că vectorul nul este unul din vârfurile v¹,...,v^s ale mulţimii A (nu întotdeauna este aşa!); putem presupune că v¹ =.Atunci Q¹ = Mv¹ = şi .

În concluzie, matricea programului (PM) conţine coloana unitară .

Astfel, pentru (PM) dispunem de baza unitară corespunzătoare varibilelor l₁, y₁ şi y₂. Toate aceste variabile au coeficienţi nuli în funcţia obiectiv aşa că :

. În consecinţă, vectorul multiplicatorilor simplex asociaţi bazei unitare indicate este:

din care rezultă p₀ = 0 , u = [0,0]. Vectorul valorilor variabilelor bazice are componentele:

Valoarea funcţiei obiectiv este:

Toate aceste elemente formează tabelul simplex redus de start:

	l1	1	1	0	0
(T1)	y1	9	0	1	0
	y2	7	0	0	1
	f	0	0	0	0

Tabelul 5.2

Considerarea vârfului v¹ = sugerează că, la iniţierea dialogului între agenţi şi autoritatea centrală, se pleacă de la situaţia în care cele două activităţi nu sunt operate: x₁ = 0 , x₂ = 0.

y₁ = 9 , y₂ = 7 arată că resursele R₁ şi R₂ nu sunt deocamdată solicitate.

Am văzut în secţiunea 4 că vectorul u are semnificaţia de sistem de preţuri pe resursele comune.Aceste preţuri sunt “anunţate” de către autoritatea centrală agenţilor, care la rândul lor, îşi vor maximiza veniturile “plătind” pentru resursele comune solicitate. “Propunerile” de programe de activitate sunt “comunicate” de agenţi autorităţii centrale. Aceasta preia propunerile şi încearcă, pe baza lor şi a propunerilor “mai vechi”, să construiască o “mixtură” care să se încadreze în disponibilul limitat de resurse comune şi să conducă la un venit total cât mai mare.

Iteraţia 1 Autoritatea centrală anunţă sistemul de preţuri u = (0,0) , altfel spus “oferă” resursele comune “pe gratis”.

Agenţii rezolvă programul:

cu soluţia optimă evidentă:

pe care o trimit “ca propunere de program de activitate” autorităţii centrale. Deoarece:

soluţia din tabelul (T₁) nu este optimă; baza curentă trebuie schimbată prin introducerea unei noi coloane din matricea programului (PM). Această coloană se generează astfel:

Vectorul - notat în teoria premergătoare cu v^* - este un alt vârf al mulţimii A , să zicem v². Calculăm:

Coloana care intră în bază va fi: .

Calculele uzuale ale unei iteraţii din algoritmul simplex revizuit sunt indicate mai jos

Tabelul 5.3

Iteraţia 2 Autoritatea centrală anunţă noul sistem de preţuri: u = (46/17 , 0).

După cum se vede, resursa R₂ este încă oferită “pe gratis”, deoarece y₂ = 20/17 arată că “mixtura”:

nu utilizează integral această resursă.

Calculăm vectorul veniturilor unitare “nete”:

Agenţii vor avea de rezolvat programul:

a cărui soluţie optimă este:

( La “preţurile actuale” agentul 1 are un venit net pozitiv; el îşi poate permite să procure resursele R₁ şi R₂ în cantităţile necesare pentru operarea activităţii sale la nivelul maxim posibil 4. Pentru agentul 2, resursa R₁ este "prea scumpă": oricât de mic ar fi nivelul de operare al activităţii proprii, “costul” resurselor R₁ şi R₂ depăşeşte venitul său “brut” astfel că, pentru agentul 2, decizia va fi “să nu facă nimic”.)

Deoarece :

soluţia din tabelul (T₂) adică “mixtura” descrisă mai sus, nu este optimă.

Noua propunere a agenţilor este un alt vârf, să zicem v³, al mulţimii A , vârf care va produce coloana ce “îmbunătăţeşte” baza curentă:

Intră în bază coloana:

Pivotăm tabelul curent (T₂):

Tabelul 5.4

Iteraţia 3 Noul sistem de preţuri pe resursele comune anunţat de autoritatea centrală va fi:

u = (5/4 , 9/4)

Veniturile unitare “nete” ale agenţilor devin:

Astfel, funcţia obiectiv a programului P(u = (5/4 , 9/4)) este constantă: şi în consecinţă valoarea ei maximă va fi . Deoarece soluţia din tabelul (T₃) este soluţia optimă a programului (PM). Soluţia optimă a programului original (P) este “mixtura convexă” a celor trei “propuneri” v¹,v²,v³:

iar venitul maxim total are valoarea (max)f = 27.

§ 6. Metoda generării de coloane pentru problema croirii

După cum am văzut, principiul de descompunere Dantzig - Wolfe rezolvă un program liniar cu multe restricţii înlocuindu-l cu un altul - numit program principal - cu mai puţine restricţii dar cu foarte multe coloane (variabile) care nu sunt disponibile de la început! În orice fază a rezolvării programului principal, un număr relativ mic de coloane sunt cunoscute, coloanele necesare îmbunătăţirii soluţiilor intermediare fiind generate la "cerere".

Scopul acestei secţiuni este acela de a arăta cum se aplică tehnica generării de coloane în rezolvarea altor probleme de optimizare similare cum este de exemplu problema croirii introdusă în capitolul II, §2. În continuare vom vedea că această tehnică necesită luarea în considerare a unei probleme de optimizare foarte simple ca structură dar deosebit de importantă în optimizarea combinatorială - problema rucsacului. Pentru această subproblemă, în secţiunea următoare, va fi prezentată o metodă specifică de rezolvare bazată pe programarea dinamică.

6.1 Problema croirii unidimensionale. Enunţ şi model matematic

Un număr de m repere cu lungimile l₁,l₂,...,l_m trebuiesc croite din suporţi cu lungimea comună L în cantităţile b₁,b₂,...,b_m .Obiectivul constă în satisfacerea cererilor cu un consum minim de suporţi.

Presupunem că L şi l₁ ,l₂ ,..., l_m sunt exprimate prin numere întregi , pozitive şi că L > l₁ >l₂ >..>l_m. Am numit reţetă de croire o modalitate de tăiere a unui suport în repere cu lungimile cerute. Formal, o reţetă de croire se identifică cu un vector a = (a₁,a₂,...,a_m) cu componente numere întregi nenegative în care a_i reprezintă numărul reperelor cu lungimea l_i rezultate din tăierea suportului. Suma lungimilor reperelor astfel obţinute nu depăşeşte lungimea suportului, astfel că:

Numărul acestor reţete este finit şi ordonându-le într-un fel oarecare, de exemplu lexicografic,obţinem lista:

(pentru nevoi ulterioare reţetele vor fi scrise în coloană). Dacă notăm cu x_j numărul de suporţi tăiaţi după reţeta a^j ( x^j se mai numeşte şi multiplicitatea reţetei a^j) modelul matematic al problemei de croire este:

Deoarece pritre reţetele a¹,a²,...,aⁿ se numără şi reţetele unitare:

(1,0,0,...,0) , (0,1,0,...,0) , ..., (0,0,0,...,1)

problema (P) are soluţii admisibile (cu componente) întregi şi chiar soluţie optimă.

În cazul - frecvent întâlnit în practică - în care ne limităm la utilizarea numai a aşa numitelor reţete maximale - adică a acelor reţete a = (a₁,a₂,...,a_m) pentru care restul:

este mai mic decât lungimea celui mai mic reper - problema de croire se formalizează astfel:

unde A¹ , A² , ..., A^N este (sub)lista reţetelor maximale, iar y₁,y₂,...,y_N sunt multiplicităţile acestora.

Observaţie: Dacă în modelul (P) toate restricţiile erau egalităţi (aceasta însemnând croirea reperelor "exact" în cantităţile cerute) în noul model (P') nu mai putem impune aceeaşi condiţie deoarece,prin restrângerea modalităţilor de croire a unui suport, este posibil ca sistemul să nu aibe soluţii întregi nenegative! Iată de ce, pentru a asigura compatibilitatea noului model suntem nevoiţi să admitem că anumite repere pot fi croite "în exces".

Programele întregi (P) şi (P') sunt în esenţă echivalente în sensul că au acelaşi optim întreg iar soluţia optimă a programului (P) utilizează cu prioritate reţete maximale; în conssecinţă, în cele ce urmează vom studia programul "mai general" (P).

Exemplul 6.1 Considerăm cazul croirii a trei repere cu lungimile l₁ = 11, l₂ =7 , l₃ =4 din suporţi cu lungimea L = 19. În următorul tabel sunt indicate toate reţetele de croire şi sunt puse în evidenţă reţetele maximale.

Reţeta	a^1º A^1	a^2 º A^2	a^3	a^4	a^5 º A^3	a^6	a^7 º A^4	a^8	a^9	a^10	a^11ºA^5	a^12	a^13	a^14
l1 = 11	1	1	1	1	0	0	0	0	0	0	0	0	0	0
l2 = 7	1	0	0	0	2	2	1	1	1	1	0	0	0	0
l3 = 4	0	2	1	0	1	0	3	2	1	0	4	3	2	1
Rest	1	0	4	8	1	5	0	4	8	12	3	7	11	15

Tabelul 6.1

Pentru cererile b₁ =12 , b₂ =18 , b₃ =30 :

· luarea în considerare a tuturor reţetelor de croire - maximale şi nemaximale - conduce la modelul:

· având în vedere numai reţetele maximale obţinem modelul:

Ca orice problemă de programare în numere întregi ,(P) este foarte greu de rezolvat. În marea majoritate a aplicaţiilor practice vom fi fericiţi să obţinem - în timp util şi cu un efort computaţional rezonabil - o soluţie "bună" nu neapărat optimală. Aşa cum s-a indicat în capitolul I,§1,o asemenea soluţie s-ar putea obţine rotunjind convenabil soluţia optimă a problemei relaxate (PL) dedusă din (P) prin eliminarea cerinţei ca variabilele să ia numai valori întregi. Această tactică conduce la rezultate foarte bune în special în cazurile în care cererile b₁,b₂,...,b_m sunt mari; într-adevăr în aceste cazuri, componentele soluţiei optime fracţionare vor fi suficient de mari astfel că pierderile datorate rotunjirii vor fi mici şi nesemnificative.

În continuare ne vom ocupa de rezolvarea relaxatei (PL) a problemei de croire (P):

Dificultatea rezolvării acestei probleme rezidă în numărul foarte mare de coloane (reţete) pe care le poate avea (mai cu seamă în situaţile reale) şi care - în cazul rezolvării "obişnuite" - ar trebui mai întâi generate. Vom vedea în continuare cum se poate evita acest impediment.

6.2 Teoria metodei generării de coloane

Vom aplica problemei (PL) versiunea revizuită a algoritmului simplex.. La start, se poate pleca cu baza formată din cele m reţete unitare:

cu tabelul redus:

e^1	b1	1
e^2	b2		1
^M	^M			O
e^m	bm				1
f	Sbi	1	1	K	1

Tabelul 6.2

Cel mai bine este să se plece cu baza formată din cele m reţete unicat:

în care:

, , … ,

şi cu tabelul simplex redus:

K^1	b1/r1	1/r1
K^2	b2/r2		1/r2
^M	^M			O
K^m	bm/rm				1/rm
f	Sbi/ri	1/r1	1/r2		1/rm

Tabelul 6.3

Fie B baza admisibilă curentă, soluţia asociată bazei B. Presupunem disponibil tabelul simplex corespunzător; vezi tabelul 6.4

Reamintim că:

După cum se ştie, soluţia va fi optimă dacă, pentru toate coloanele avem:

Pentru a testa îndeplinirea condiţiei de mai sus este suficient să calculăm:

şi cum fiecare a^j este o soluţie cu componente întregi nenegative a inecuaţiei va fi suficient să rezolvăm programul auxiliar:

Dacă maximul funcţiei obiectiv din R(p) este £ 1 este clar că pentru toţi j = 1,…,n şi soluţia asociată bazei B este optimă.

Dacă maximul din R(p) este > 1 atunci soluţia optimă a^* a programului R(p) este o reţetă, fie ea a^k , din lista a tuturor reţetelor, cu proprietatea:

.

Introducem în baza curentă coloana a^k urmând instrucţiunile algoritmului simplex revzuit. Obţinem o nouă bază admisibilă B’, o nouă soluţie a problemei (PL) în general mai bună decât soluţia veche şi un nou tabel simplex redus în care aopare un nou vector p’ de multiplicatori simplex.Pentru a testa optimalitatea noii soliuţii rezolvăm programul R(p’) etc.

Procesul iterativ se încheie într-un număr finit de paşi cu găsirea soluţiei optime a problemei (PL).

Tabelul 6.4

6.3 Rezumatul procedurii Generare de Coloane pentru rezolvarea relaxatei problemei de croire

Start Se pleacă cu baza formată din reţetele unicat(6.1) şi cu tabelul simplex redus 6.3. Fie B baza curentă şi p = c^B× B^-1 vectorul multiplicatorilor simplex corespunzători.

Conţinutul unei iteraţii:

Pasul 1 Se rezolvă problema auxiliară:

(vezi secţiunea următoare în ceeace priveşte modul algoritmic de rezolvare al problemei R(p) .

Pasul 2 Dacă maximul funcţiei obiectiv din R(p) este £ 1 stop: soluţia curentă a problemei (PL) este optimă. Altminteri:

Pasul 3 Fie a^* soluţia optimă a problemei R(p) . Se introduce în baza curentă B coloana a^* (reindexată eventual cu numărul de ordine al iteraţiei) urmând instrucţiunile algoritmului simplex revizuit. Se revine la pasul 1 în cadrul unei noi iteraţii.

Exemplul 6.2 Vom rezolva relaxata (PL) a problemei de croire (P) din exemplul 6.1 (sfătuim cititorul să ignore faptul că am generat deja toate reţetele de croire ale problemei...De altfel, diferitele reţete folosite de algoritm vor avea o notare diferită de cea din tabelul 6.1)

Start. Plecăm cu baza formată din reţetele unicat:

este o matrice diagonală a cărei inversă este :. Soluţia asociată bazei B = [K¹,K²,K³]:

(celelalte reţete - pe cqre de fapt nu le ştim - nu se folosesc).

Multiplicatorii simplex asociaţi bazei [K¹,K²,K³]sunt:

Valoarea funcţiei obiectiv în soluţia construită este: `f =p×b = 1×12 + ×18 + ×30 = 28×

Tabelul simplex redus de start:

K^1	12	1	0	0
K^2	9	0	1/2	0
K^3	15/2	0	0	1/4
f	57/2	1	1/2	1/4

Tabelul 6.5

Iteraţia 1 Se rezolvă problema :

Prin simplă inspecţie (în cazul de faţă) sau aplicând un algoritm adecvat dacă numărul reperelor este mare (vezi secţiunea următoare) se găseşte (max)r = 3/2 > 1 şi soluţia optimă a^* = (1,1,0) care este o reţetă maximală. Renotăm a^* : A¹ = (1,1,0)^T şi introducem A¹ în baza curentă:

A^1	®	1	1	0
K^1	12	1	0	0	1	º pivot		A^1	12	1	0	0
K^2	9	0	1/2	0	1/2		Þ	K^2	3	-1/2	1/2	0
K^3	15/2	0	0	1/4	0			K^3	15/2	0	0	1/4
f	57/2	1	1/2	1/4	1/2	=(max)r-1		f	45/2	1/2	1/2	1/4

Tabelul6.6a Tabelul 6.6b

Iteraţia 2 Rezolvăm problema:

al cărei optim , (max)r = 5/4 > 1 , se atinge pe reţeta maximală a^* = (0,2,1)^T ,renotată A². Introducem A² în baza curentă:

A^2

®

0

2

1

A^1

12

1

0

0

0

A^1

12

1

0

0

K^2

3

-1/2

1/2

0

1

º pivot

Þ

A^2

3

-1/2

1/2

0

K^3

15/2

0

0

1/4

1/4

K^3

27/4

1/8

-1/8

1/4

f

45/2

1/2

1/2

1/4

1/4

=(max)r-1

f

87/4

5/8

3/8

1/4

Tabelul6.7a Tabelul 6.7b

Iteraţia 3 Acum se rezolvă problema:

Se găseşte (max)r = 9/8 > 1 şi soluţia optimă a^* = (1,0,2)^T ,renotată A³. Introducem A³ în baza curentă:

A^3

®

1

0

2

A^1

12

1

0

0

1

A^1

6/5

4/5

1/5

-2/5

A^2

3

-1/2

1/2

0

-1/2

Þ

A^2

42/5

-2/5

2/5

1/5

K^3

27/4

1/8

-1/8

1/4

5/8

º pivot

A^3

54/5

1/5

-1/5

2/5

f

87/8

5/8

3/8

1/4

1/8

=(max)r-1

f

102/5

3/5

2/5

1/5

Tabelul6.8a Tabelul 6.8b

Iteraţia 4 Rezolvăm problema:

De această dată (max)r = 1 astfel că soluţia curentă,înscrisă în tabelul 6. , este optimă.

În concluzie, soluţia optimă fracţionară a problemei de croire date utilizează:

· reţeta maximală A¹ = (1,1,0)^T cu multiplicitatea ;

· reţeta maximală A² = (0,2,1)^T cu multiplicitatea ;

· reţeta maximală A³ = (1,0,2)^T cu multiplicitatea .

Numărul suporţilor "consumaţi" este : .

Observaţie: Reîntorcându-ne la problema de croire generală (P) şi la relaxata acesteia se constată imediat că optimul întreg este cel puţin egal cu rotunjirea superioară a optimului fracţionar!

În cazul de faţă rezultă că soluţia optimă întreagă va utiliza cel puţin suporţi.

Să vedem acum cum se determină o soluţie "bună" pentru problema de croire studiată.

Etapa 1 Se rotunjesc inferior multiplicităţile reţetelor din soluţia optimă a problemei relaxate (PL):

Etapa 2 Se determină cantităţile de repere ce pot fi croite cu reţetele din soluţia optimă fracţionară dar cu multiplicităţile rotunjite inferior:

Etapa 3 Se determină cantităţile de repere care mai sunt de croit:

Etapa 4 Pentru "cererea reziduală" b' se aplică următoarea euristică, numită FFD (First Fit Decreasing):

· se determină prima reţetă în sens lexicografic care "încape" în b';

· se actualizează b' prin extragerea reţetei găsite şi se reia pasul precedent.

În cazul nostru prima reţetă cuprinsă în b' este (1,1,0)^T = A¹.Actualizăm cererea reziduală:

Au mai rămas două repere cu lungimea l₃ = 4 a căror croire necesită consumarea unui suport .

Recapitulând, o soluţie "bună" pentru croirea cantităţilor de repere cerute ar fi următoarea:

· se foloseşte reţeta A¹ = (1,1,0) de 1 + 1 = 2 ori;

· se foloseşte reţeta A² = (0,2,1) de 8 ori;

· se foloseşte reţeta A³ = (1,0,2) de 10 ori;

· se mai taie dintr-un suport două repere cu lungimea l₃ = 4 adică se foloseşte reţa nemaximală (0,0,2) .

În total se consumă 2 + 8 + 10 + 1 =21 suporţi şi în baza unei observaţii anterioare soluţia construită este chiar optimă!

Concluzii finale

1. În soluţia optimă a problemei relaxate se utilizează numai reţete maximale;

2. După aplicarea euristicii FFD asupra cererii reziduale, pot apare şi câteva reţete nemaximale - de regulă una singură;

3. Numeroasele experimente numerice au arătat că optimul întreg al problemei de croire unidimensionale este de regulă egal cu rotunjirea întreagă superioară a optimului fracţionar şi numai în rare cazuri este mai mare decât aceasta cu exact o unitate!

§7 Programare dinamică

În această secţiune ne vom opri asupra problemei :

în care sunt întregi pozitivi.

În secţiunea precedentă, (R) a apărut ca subproblemă în rezolvarea relaxatei problemei de croire unidimensionale prin metoda generaă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. În literatura de specialitate este cunoscută sub numele de problema rucsacului datorită următoarei interpretări:

a_i este numărul pieselor de echipament de greutate l_i şi utilitate p_i 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 = 1,…,m şi fiecare întreg l =0,1,…,L considerăm problema:

al cărei optim îl notăm cu r_k(l). Este clar că R = R_m(l) şi căaximul funcţiei obiectiv din R este r_m(L).

Observăm că, pentru k fixat r_k este o funcţie de o singură variabilă ale cărei valori admisibile sunt 0,1,…,L.

Funcţiile r₁ , r₂ , … , r_m-1 , r_m pot fi determinate astfel:

· = l = 0,1,…,L (7.1)

· pentru k > 1 avem formula de recurenţă:

ê (7.2)

· pentru k = m este suficient să găsim numai valoarea funcţiei r_m în L:

ê

Relaţia (7.2) arată că funcţiile r₂,…,r_m-1,r_m rezultă din nişte procese de optimizare unidimensionale.

Să presupunem cunoscute funcţiile r₁ , r₂ , … , r_m-1 şi valoarea r_m(L) şi să notăm cu valoarea variabilei a_k care – pentru l dat – realizează maximul din formula de recurenţă (7.2). Pentru k = 1 avem . Atunci, o soluţie optimă a problemei (R) se găseşte astfel:

Observaţii: 1) În termenii problemei rucsacului r_k(l) este valoarea maximă a unei încărcări a rucsacului ce nu depăşeşte în greutate plafonul l şi care este formată numai din primele k tipuri de echipament.

2) Prin programarea dinamică rezolvarea problemei de optimizare multidimensională (R) este înlocuită cu o secvenţă de optimizări unidimensionale bazate pe formula de recurenţă (7.2).

3) Ecuaţia funcţională (7.2), prin care funcţiile r₁ , r₂ , … , r_m-1 , r_m se deduc una din alta formalizează – în cazul problemei (R) – principiul central al programării dinamice datorat lui R. BELLMAN : O strategie (secvenţială) optimă are proprietatea că oricare ar fi starea iniţială şi decizia iniţială, deciziile rămase constituie o strategie optimă în raport cu starea care rezultă din prima decizie.

Demonstraţia formulei (7.2)

Fie o valoare întreagă , , dată variabilei a_k . Fie o soluţie optimă a problemei . Prin urmare:

Deoarece rezultă că este o soluţie admisibilă a problemei care dă funcţiei obiectiv valoarea:

În consecinţă:

şi cum a fost arbitrar aleasă (între 0 şi ) urmează că:

ê

Pe de altă parte fie o soluţie optimă a problemei .Prin urmare:

Din rezultă că este o soluţie admisibilă a problemei şi deci:

Să arătăm că în ultima relaţie avem egalitate. Presupunând prin absurd contrariul fie o soluţie optimă a problemei . În consecinţă vom avea:

Prin urmare este o soluţie admisibilă a problemei şi deoarece

tragem concluzia că nu este soluţie optimă a problemei contrar ipotezei.

În definitiv:

astfel că:

ê

Egalitatea (7.2) este demonstrată.

Exemplul 7.1 Vom aplica procedura descrisă problemei:

Iteraţia 1 Determinăm valorile funcţiei pentru l = 0,1,...,11

Ele sunt înscrise în tabelul 7.1

l	0	1	2	3	4	5	6	7	8	9	10	11
r1(l)	0	0	0	0	0	16	16	16	16	16	32	32
	0	0	0	0	0	1	1	1	1	1	2	2

Tabelul 7.1

Iteraţia 2 În continuare calculăm valorile funcţiei

ê}=

ê} unde l = 0,1,...,11

Astfel, pentru l = 0,1,2,3 r₂(l) = r₁(l) ; pentru l = 4,5,6,7 vom avea:

ê}=

iar pentru l =8,9,10,11

ê}=

Rezultatele sunt afişate în tabelul 7.2

l	0	1	2	3	4	5	6	7	8	9	10	11
r2(l)	0	0	0	0	12	16	16	16	24	28	32	32
	0	0	0	0	1	0	0	0	2	1	0	0

Tabelul 7.2

Iteraţia 3 În final vom evalua numai:

ê=

Determinarea soluţiei optime ("de la sfârşit către început")

Pasul 1 ;

Pasul 2 ;

Pasul 3

.

Soluţia optimă a problemei date este:

§ 8. Întrebări şi probleme

1.Este cunoscut faptul că problemele practice de optimizare de dimensiuni "mari" au o structură "specială". Ce înseamnă această structură specială în programarea liniară?

2.Ce caracteristici are programul principal (P^m) rezultat din aplicarea metodei de descompunere Dantzig - Wolfe? Ce metodă se utilizează pentru rezolvarea lui?

3.Se consideră un program liniar în formă canonică de maximizare a cărui mulţime de restricţii a fost partiţionată în două blocuri:

în notaţiile matriciale ale secţiunii 3.

Să presupunem că şi sunt doi vectori nenegativi de dimensiuni convenabile astfel încât:

· este soluţia optimă a programului

·

·

Să se arate că este soluţia optimă a programului (P).

.4. [3] Utilizaţi algoritmul de descompunere Dantzig - Wolfe la rezolvarea următoarelor programe liniare custructură bloc - diagonală şi restricţii de cuplare:

În rezolvarea subproblemelor de la nivelul 1 se poate folosi metoda grafică.

5. Pentru instalaţia de apă a unui imobil în construcţie sunt necesare 80 de ţevi de 2m, 40 de ţevi de 2,50m şi 30 de ţevi cu lungimea de 3,50m. Aceste bucăţi se taie din ţevi cu lungimea de 9m.

a) Alcătuiţi lista reţetelor maximale de croire;

b) Scrieţi un program liniar în numere întregi pentru minimizarea numărului de ţevi de 9m ce vor fi tăiate;

c) Rezolvaţi programul relaxat prin metoda generării de coloane;

d) Plecând de la soluţia optimă fracţionară construiţi o soluţie "bună" a problemei date;ar putea fi optimă soluţia construită de dvs.?

6.Problema rucsacului. Formulare şi model matematic.Descrieţi algoritmul de ezolvare al problemei rucsacului prin programare dinamică.

7. Rezolvaţi problemele de tip rucsac: