Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Masterat
Domeniul: Matematica
Programul de studii: Matematica
Limba de predare: Română

SYLLABUS

I. Date generale
Codul	Disciplina	
MMA1008	Metode numerice în optimizare	

Semestrul	Ore: C+S+L	Categoria	Statutul	
4	2+2+0	specialitate	opţională	

II. Cadre didactice cu norma de bază în Universitate
Numele şi	Titlul	Gradul	Catedra	Tipul activităţii	
prenumele	ştiinţific	didactic		C	S	L	
LUPSA Liana	Dr. 	Prof.	Analiză şi Optimizare	*			

Cadre didactice asociate
Numele şi	Titlul	Instituţia	Tipul	Tipul activităţii	
prenumele	ştiinţific		postului	C	S	L	

III. Obiectivele disciplinei
Prezentarea principiilor care stau la baza principalelor metode numerice de rezolvare a problemelor de optimizare liniară şi neliniară. La terminarea cursului studenţii vor fi capabili să aplice aceste metode pentru rezolvarea unor clase de probleme de optimizare.	

IV. Conţinutul disciplinei
Sunt incluse metode numerice pentru determinarea punctelor de optim (fără restricţii) ale funcţiilor reale de o variabilă reală (metoda lui Fibonacci, metoda secţiunii de aur, metoda bisecţiei, etc.), precum şi ale funcţiilor reale de mai multe variabile reale (metode care nu utilizează gradientul, metode de gradient, metode cu direcţii conjugate). Sunt prezentate principalele tehnici utilizate în construirea algoritmilor pentru rezolvarea problemelor de optimizare cu restricţii (tehnica reducerii la probleme de optimizare fără restricţii, tehnica tăieturilor, tehnica punctului interior, tehnica direcţiilor admisibile, tehnica branch and bound, principiul programării dinamice). Fiecare tehnică este exemplificată prin unul sau mai mulţi algoritmi (metode de penalizare interioară, metode de penalizare exterioară, metode ce utilizează funcţia lui Lagrange, metoda planelor secante, algoritmul discret şi continuu a lui Gomory, algoritmul lui Young, algoritmul lui Balas, algoritmul branch and bound pentru rezolvarea problemei de optimizare în variabile întregi, rezolvarea problemei rucsacului şi a problemei de alocare utilizând tehnica optimizării dinamice. 

V. Bibliografie
1) Andrei N.: Programarea matematică avansată. Teorie, metode computaţionale, aplicaţii. Bucureşti, Editura Tehnică, 1999.
2) Blaga L., Lupşa L.: Cercetare operaţională. Cluj-Napoca, Editura Argonaut, 2006.
3) Breckner W.W.: Cercetare operaţională. Cluj-Napoca, Universitatea Babeş-Bolzai, 1981
4) Ehrgot M.: Multicriteria Optimization. Berlin Heidelberg New York: Springer, 2005. 
5) Forgo F.: Nonconvex Programming, Budapest: Akademiai Kiado, 1988.
6), Jongen H. Th., Meer K., Triesch E.: Optimization Theory. Kluwer Academic Publishers, Boston, 2004.
7) Lupşa L.: Numerical optimization methods. Special issues in discrete optimization. Cluj-Napoca: Risoprint, 2005.
9) Snyman J. A.: Practical Mathematical Optimization. An Introduction to Basic Optimization Theory and Classical and New Gradient-Based Algorithms. Springer, 2005.
10) Wenzu Sun, Za-Xiang Zuan: Optimization Theory and Methods. Nonlinear Programming. Springer, 2006

VI. Tematica activităţilor didactice pe săptămâni
Curs 1.  Consideraţii generale privind problemele de optimizare şi metodele numerice de rezolvare a lor
-	Formularea problemei generale de optimizare, precizarea terminologiei ce urmează a fi utilizată: funcţie scop, funcţii ce generează restricţii, soluţie admisibilă, mulţime a soluţiilor admisibile, problemă de optimizare inconsistentă, punct de optim local, punct de optim local strict, punct de optim (global), mulţime a soluţiilor optime, problemă de optimizare care nu are soluţii optime, etc.
-	Formularea succintă a problemei de optimizare multicriterială, precizarea terminologiei: punct de optim Pareto (soluţie eficientă), punct de optim Slater (soluţie slab eficientă), alte tipuri de puncte de optim. Cazul optimizării lexicografice.
-	Clasificarea problemelor de optimizare 
- în funcţie de dimensiunea funcţiei scop: optimizarea unicriterială, optimizare multicriterială; 
- în funcţie de existenţa sau inexistenţa restricţiilor: optimizare fără restricţii şi optimizare cu restricţii; 
- în funcţie de forma restricţiilor: optimizare clasică, optimizare cu condiţii logice;
- în funcţie de natura funcţiei scop şi a funcţiilor care definesc restricţiile: optimizare liniară, optimizare pătratică, optimizare convexă etc.;
- în funcţie de natura mulţimii soluţiilor admisibile: optimizare continuă, întregă, semiîntregă, discretă, pseudobooleană etc;
- în funcţie de natura coeficienţilor ce intră în funcţia scop şi în funcţiile ce generază restricţiile: optimizare deterministă depinzând sau nu de unul sau mai mulţi parametri, optimizare nedeterministă (stohastică) .
-	Clasificarea metodelor de rezolvare
- în funcţie de acurateţea rezultatului: metode exacte şi metode aproximative;
- în funcţie de numărul de iteraţii: metode finite şi metode infinite.

Curs 2. Metode de determinare a punctelor de optim ale funcţiilor reale unimodale în raport cu o mulţime.
-definiţia funcţiilor unimodale în raport cu o mulţime;
-exemple de funcţii unimodale în raport cu o mulţime;
-proprietăţi , relative la punctele de optim, ale acestor funcţii;
-algoritmul general de determinare a punctelor de optim a funcţiilor unimodale în raport cu o mulţime.

Curs  3. Metode de determinare a punctelor de optim ale funcţiilor reale relativ la un interval al axei reale
- metode bazate pe interpolare, fără utilizarea derivatei: metoda lui Powell;
- metode bazate pe interpolare, cu utilizarea derivatei: metoda lui Newton, metoda secantei, metoda lui Davidon.

Curs 4. Direcţii de descreştere
- definiţia direcţiei de descreştere; exemple de direcţii de descreştere;
- algoritmul general al metodelor bazate de direcţii de descreştere în cazul funcţiilor diferenţiabile; convergenţa algoritmului;
- proprietăţi ale direcţiilor de descreştere.

Curs 5. Metode de determinare a punctelor de optim fără restricţii ale funcţiilor reale de mai multe variabile reale
1) Metode de gradient; alegerea paşilor în metodele de gradient:
- principiul minimizării de-a lungul razei (pasul Cauchy),
- principiul punctului staţionar (pasul Cury),
- principiul alegerii fixe a coeficienţilor,
- principiu relaxării.
2) Metode cu direcţii conjugate: algoritmul general al metodelor bazate pe direcţii conjugate, metoda lui Fletcher-Reeves, metoda lui Polak-Ribière şi metoda lui Daniel.

Curs 6. Metode de tip SUMT:
-	metode de penalizare interioară;
-	metode de penalizare exterioară.

Curs 7. Metode bazate pe direcţii admisibile: 
-	metoda paşilor mari; 
-	varinta I a algoritmului lui Zountendijk-Zuhoviţki.

Curs  8. Principiul tăieturilor: 
-	tăieturi interioare;
-	tăieturi exterioare.

Curs  9. Metode bazate pe principiul tăieturilor: 
-	metoda planelor secante;
-	metoda paşilor mici.

Curs  10. Metode de rezolvare a problemelor de optimizare întregă ce au la bază principiul tăieturilor: 
-	metoda continuă a lui Gomory pentru rezolvarea problemei de optimizare liniară în variabile întregi;
-	metodă bazată pe tăieturi pentru rezolvarea problemei de optimizare cu funcţia scop fractionară şi mulţimea soluţiilor admisibile poliedru convex.

Curs 11. Principiul metodei de tip branch and bound;
-	aplicaţii la rezolvarea problemelor continue neconvexe şi a problemelor de optimizare întregă.

Curs 12. Programarea dinamică şi aplicarea ei în rezolvarea unor probleme de optimizare:
- Modele de probleme de programare dinamica;
-: principiul lui Bellman;
- aplicatii ale acestuia (in varianta continua sau discreta) in economie
- aplicarea principiului lui Bellman la unele probleme de optimizare pe retele.

Curs  13. Principiul metodelor de punct interior.
- algoritmul lui Karmarkar.

Curs 14. Metode de rezolvare a problemelor de optimizare pseudobooleana:
-	metode enumerative;
-	metode enumerative cu restrictie filtru;
-	 metoda lui Hammer Rudeanu.

Seminar 1.  Exemple de situaţii din viaţa cotidiană a căror soluţionare conduce la rezolvarea unor probleme de  optimizare
-	Exemple de probleme de optimizare unicriteriale şi multicriteriale;
-	Exemple de probleme de optimizare cu restrcţii şi fără restricţii;
-	Exemple de probleme de optimizare cu condiţii logice;
-	Exemple de probleme de optimizare liniară, optimizare pătratică, optimizare convexă, optimizare hiperbolică;
-	Exemple de probleme de optimizare întregă, probleme de optimizare parţial-întregă, probleme de optimizare discretă, probleme de optimizare pseudobooleană;
-	Exemple de probleme de optimizare parametrică;
-	Exemple de probleme de optimizare stochastică.

Seminar 2. Metode de determinare a punctelor de optim ale funcţiilor reale, unimodale în raport cu o mulţime.
-	Particularizarea algoritmului general în cazul în care mulţimea este un interval compact; obţinerea algoritmului secţiunii de aur, a algoritmului lui Fibonacci şi a algoritmului împărţirii echidistante.
-	Particularizarea algoritmului în cazul în care mulţimea este finită (algoritmul bisecţiei);
-	Utilizarea algoritmului bisecţiei pentru obţinerea unui algoritm de tip aproximativ pentru determinarea punctelor de optim ale unei funcţii unimodale pe un interval compact.

Seminar 3. Metode de determinare a punctelor de optim ale funcţiilor reale relativ la un interval al axei reale
-	Rezolvarea unor probleme cu ajutorul algoritmului lui Powell şi a algoritmului lui Newton.
-	Prezentarea referatului: Metode euristice pentru determinarea punctelor de optim ale funcţiilor reale de o variabilă reală (algoritmul lui Armijo, algoritmul lui Wolfe-Powell, algoritmul lui Dennis şi Schnabel).

Seminar  4. Metode euristice de determinare a punctelor de optim ale funcţiilor reale de mai multe variabile reale
Se vor prezenta: algoritmul de optimizare ciclică pe axele de coordonate, algoritmul de optimizare ciclică pe axele de coordonate şi diagonală şi metoda lui Hooke şi Jeeves; se va da câte un exemplu de utilizare a lor;
-	Sub formă de referat va fi prezentată metoda lui Rosenbrock  şi algoritmul lui Powell.

Seminar  5. Metode de determinare a punctelor de optim fără restricţii ale funcţiilor reale de mai multe variabile reale
-	Determinarea punctelor de minim ale unor funcţii reale de două şi trei variabile reale utilizând metoda gradientului cu alegerea pasului Cauchy şi a pasului după princiul alegerii fixe. 
-	Prezentarea sub formă de referat a metodei lui Hestenes-Stiefel pentru determinarea punctelor de minim ale funcţiilor pătratice, uniform convexe.

Seminar 6. Metode de tip SUMT: 
- rezolvarea câte unei probleme cu metoda penalizare interioare şi cu metoda penalizării exterioare.
- prezentarea referatului “Metode secvenţiale de rezolvare a problemelor de optimizare cu restricţii utilizând funcţia lui Lagrange clasică”

Seminar 7. Metode bazate pe direcţii admisibile: 
- rezolvarea unor  probleme de optimizare utilizând metoda paşilor mari şi varinta I a algoritmului lui Zountendijk-Zuhoviţki;
- prezentarea sub formă de referat a “Variantei a II-a a algoritmului lui Zountendijk-Zuhoviţki”.

Seminar  8. Varianta Zuhoviţki a algoritmului simplex. .
- prezentarea algoritmului simplex primal şi dual în varianta lui Zuhoviţki;
- rezolvarea unor probleme de optimizare liniară cu ajutorul algoritmilor simplex prezentaţi.

Seminar 9. Metode bazate pe principiul tăieturilor:
-	rezolvarea unor  probleme de optimizare utilizând  metoda planelor secante.
-	Prezentarea sub formă de referat a metodei paşilor mici.

Seminar 10. Metode de rezolvare a problemelor de optimizare întregă ce au la bază principiul tăieturilor:
- rezolvarea cu ajutorul metodei continue a lui Gomory a unor probleme de optimizare liniară discretă. 
- prezentarea, sub formă de referat a algoritmului discret al lui Gomory şi a algoritmului lui Young. 
- pentru rezolvarea problemelor de optimizare fracţionară şi hiperbolică întregă.

Seminar 11. Principiul metode de tip branch and bound.
- aplicarea acestui principiu la rezolvarea unor problemelor de optimizare întregă.
- prezentarea sub formă de referat a algorit_____referatului.

Seminar 13. Optimizare dinamică:
Aplicarea metodei optimizării dinamice la rezolvarea unor probleme particulare de alocare.
Prezentarea sub form de referatului a algoritmului lui Little pentru determinarea unui drum Hamiltonian de lungime minimă într-un graf.

Seminar 12. Metode punct interior. 
- Rezolvarea unei probleme de optimizare liniară folosind algoritmul lui Karmakar.
- Prezentarea sub formă de referat a algoritmului lui Khachiyan.

Seminar 14. Metode de rezolvare a problemei de programare pătratică:
- Prezentarea, sub forma de referat, a algoritmului lui Beale pentru rezolvarea unei probleme de optimizare patratica.
- Prezentarea, sub forma de referat, a unui algoritm  pentru rezolvarea unei probleme de optimizare patratica pseudobooleana

VII. Metode didactice folosite
Prelegerea cu demonstraţii, dezbaterea, dialogul, conversaţii de sistematizare şi sinteză, conversaţii de aplicare, utilizarea situaţiilor problemă, studiu de caz	

VIII. Evaluare
Examen oral (Ne), susţinerea unui referat (Nr) şi elaborarea unui program (Np). 
Nota finală = 1/3 Ne + 1/3 Nr + 1/3 Np.
Examenul oral va acoperi materia predată la curs şi seminar.
În timpul semestrului, în cadrul seminarului, studenţii vor prezenta câte un referat, în care vor expune o metodă numerică de optimizare, cuprinsă într-un articol din literatura de specialitate.
Tot în timpul semestrului, studenţii vor elabora  programe scrise într-un limbaj de programare ales de student, utilizând eventual MATLAB-ul sau MAPEL-ul. În cazul în care studentul nu ştie bine nici un limbaj de programare, poate înlocui elaborarea unui program cu pregătirea a încă unui referat.

IX. Bibliografie suplimentară
Articolele de specialitate date fiecarui student pentru referat	

	Decan,							Sef de catedra,

	Data,							Titular curs,
    1 septembrie 2008					Prof. Dr.  LUPSA Liana