Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licenţă
Domeniul: Matematică
Programul de studii: Matematică informatică - linia de studiu română
Limba de predare: Română

SYLLABUS

I. Date generale
Codul	Disciplina	
MMA0008	Cercetare operaţională	

Semestrul	Ore: C+S+L	Categoria	Statutul	
6	2+2+0	specialitate	obligatorie	

II. Cadre didactice cu norma de bază în Universitate
Numele şi	Titlul	Gradul	Catedra	Tipul activităţii	
prenumele	ştiinţific	didactic		C	S	L	
BRECKNER Brigitte Erika	Dr.	Lect.	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
Se ofera o introducere  in problematica cercetarii operationale, punand accentul pe studiul  problemelor de optimizare (liniara si neliniara)	

IV. Conţinutul disciplinei
1.	Introducere in tematica cercetarii operationale; modele matematice. 
2.	Optimizare liniara in Rn (poliedre; conceptul de problema de optimizare liniara; metoda grafica pentru rezolvarea problemelor de optimizare liniara in  R2; teoreme de alternativa pentru sisteme de ecuatii si inecuatii liniare; probleme de optimizare liniara in forma canonica si probleme de optimizare liniara in forma standard; algoritmul simplex pentru rezolvarea problemelor de optimizare liniara in forma canonica si cel pentru problemele in forma standard; dualitatea problemelor de optimizare liniara; elemente de teoria jocurilor) 
3.	Elemente de analiza convexa in spatiul euclidian n-dimensional (multimi convexe; conuri; puncte extremale ale multimilor convexe; puncte extremale si fete ale poliedrelor; separarea multimilor convexe prin hiperplane; functii convexe; proprietati ale functiilor convexe; clase  speciale de functii convexe)
4.	Optimizare neliniara in Rn (puncte de minim ale functiilor convexe; problema celei mai bune aproximari; conditii necesare si conditii suficiente pentru problemele de optimizare neliniara cu restrictii; dualitatea problemelor de optimizare neliniara cu restrictii)	

V. Bibliografie
1. BORGWARDT, K. H.: Optimierung, Operations Research, Spieltheorie. Birkhaeuser, Basel, 2001.
2. BRECKNER, B.E.: De la poliedre la jocuri matriceale. O introducere in optimizarea liniara. EFES, Cluj-Napoca, 2007.
3. BRECKNER, B.E., POPOVICI, N.: Probleme de analiza convexa in Rn. Casa Cartii de Stiinta, Cluj-Napoca, 2003.
4.  BRECKNER, B.E.,  POPOVICI, N.: Probleme de cercetare operationala. EFES, Cluj-Napoca, 2006.
5. BRECKNER, W.W.: Cercetare operationala. Universitatea "Babes-Bolyai", Fac. de Matematica, Cluj-Napoca, 1981.
6. BRECKNER, W.W., DUCA, D.: Culegere de probleme de cercetare operationala. Universitatea "Babes-Bolyai, Fac. de Matematica, Cluj-Napoca, 1983.
7. DOMSCHKE, W., DREXL, A.: Einfuehrung in Operations Research.  Springer-Verlag, Berlin, 2005..
8. DOMSCHKE, W., DREXL, A., KLEIN, R., SCHOLL, A., VOSS, S.: Uebungen und Fallbeispiele zum Operations Research. Springer-Verlag, Berlin, 2005.

VI. Tematica activităţilor didactice pe săptămâni
Cursuri: Ca si bibliografie se utilizeaza in principal [2] si [5].

1.	Introducere in tematica cercetarii operationale (notiuni de baza in cercetarea operationala; ilustrarea etapelor unui proces de planificare ce utilizeaza cercetarea operationala; modele matematice: exemple de probleme concrete  aparute din practica ce conduc la probleme de optimizare; prezentarea principalelor capitole ale cercetarii operationale)
2.	Optimizare liniara in Rn (definitia problemei de optimizare  in Rn; hiperplane, semispatii si poliedre in Rn; definitia problemei de optimizare  liniara in Rn; metoda grafica pentru rezolvarea problemelor de optimizare liniara in  R2)
3.	Elemente de analiza convexa in spatiul euclidian n-dimensional (multimi convexe; invelitoare convexa; conuri; invelitoare conica; conul de recesie al unei multimi; enuntul teoremei de reprezentare a poliedrelor si consecintele ei pentru studiul problemelor de optimizare liniara: caracterizarea existentei/inexistentei solutiilor unei probleme de optimizare liniara)
4.	Elemente de analiza convexa in spatiul euclidian n-dimensional (puncte extremale ale unei multimi convexe si caracterizari ale acestora;  caracterizarea punctelor extremale ale poliedrelor; caracterizarea poliedrelor ascutite; notiunea de fata a unui poliedru; descrierea multimii solutiilor unei probleme de optimizare liniara; existenta unei solutii a unei probleme de optimizare liniara, solutie ce simultan este si un punct extremal al multimii punctelor admisibile ale problemei)   
5.	Optimizare liniara in Rn (sisteme de ecuatii si inecuatii liniare: teoremele de alternativa ale lui Farkas, Motzkin, Gordan si Gale)
6.	Optimizare liniara in Rn (definitia problemei de optimizare liniara in forma canonica;  caracterizarea solutiei unei probleme de optimizare liniara in forma canonica; baza teoretica a algoritmului simplex pentru rezolvarea problemelor de optimizare liniara in forma canonica: conditia de optim, conditia de nemarginire a functiei de scop, justificarea pasului de iteratie in algoritmul simplex; prezentarea instructiunilor algoritmului simplex)
7.	Optimizare liniara in Rn (consideratii cu privire la finitudinea algoritmului simplex pentru rezolvarea problemelor de optimizare liniara in forma canonica; scurt istoric al algoritmului simplex; dualitatea problemelor de optimizare liniara: modul de determinare a dualei unei probleme de optimizare liniara, duala unei probleme de optimizare liniara in forma canonica) 
8.	Optimizare liniara in  Rn (dualitatea problemelor de optimizare liniara: teorema slaba de dualitate si teorema tare de dualitate; definitia problemei de optimizare liniara in forma standard: aducerea unei probleme de optimizare liniara la forma standard)
9.	Optimizare liniara in  Rn (probleme de optimizare liniara in forma standard: caracterizarea solutiei unei probleme de optimizare liniara in forma standard, puncte extremale ale poliedrului punctelor admisibile ale unei probleme de optimizare liniara in forma standard,  prezentarea instructiunilor algoritmului simplex pentru rezolvarea unei probleme de optimizare liniara in forma standard). Elemente de analiza convexa in spatiul euclidian n-dimensional (separarea multimilor convexe prin hiperplane)
10.	 Optimizare neliniara in  Rn (functii convexe: definitie, exemple, proprietati imediate, inegalitatea lui Jensen, continuitatea si diferentiabilitatea functiilor convexe)
11.	Optimizare neliniara in  Rn (functii convexe: caracterizarea functiilor convexe cu ajutorul unor inegalitati diferentiale ; clase speciale de functii convexe: functii strict convexe si functii afine)  
12.	 Optimizare neliniara in  Rn (puncte de minim ale functiilor convexe: proprietati si caracterizari ale acestor puncte; problema celei mai bune aproximari privita ca si o problema de optimizare neliniara: conditii suficiente pentru existenta si unicitatea punctului de cea mai buna aproximare, caracterizarea punctelor de cea mai buna aprtoximare) 
13.	 Optimizare neliniara in  Rn (probleme de optimizare cu restrictii: definitie, stabilirea unor  conditii necesare si a unor conditii suficiente pentru solutiile unor astfel de probleme cu ajutorul conditiilor de tip Karush-Kuhn-Tucker)
14.	 Optimizare neliniara in  Rn (dualitatea problemelor de optimizare cu functii de scop diferentiabile si cu restrictii diferentiabile). O scurta recapitulare a materiei predate la aceasta disciplina cu scopul de a oferi o privire de ansamblu asupra ei si de a  sublinia legaturile existente intre diferitele aspecte tratate

Seminarii: Continutul lor este legat de materia predata la curs si vizeaza aprofundarea acesteia prin rezolvare de exercitii si probleme (acestea sunt alese in principal din [4] si [6])

      1.  Exersarea realizarii modelelor matematice.
2.	Se rezolva probleme legata de metoda grafica pentru rezolvarea problemelor de optimizare liniara in R2 precum si legate de poliedre.
3.	Rezolvare de probleme legate de multimi convexe  precum si de caracterizarea existentei/inexistentei solutiilor unei probleme de optimizare liniara.
4.	Rezolvare de probleme legate de notiunea de punct extremal al unei multimi convexe (in particular al poliedrelor)
5.	Rezolvare de exercitii si probleme legate de proprietatile multimii solutiilor unei probleme de optimizare liniara precum si legate de teoremele de alternativa ale lui Farkas, Motzkin, Gordan si Gale
6.	Algoritmul simplex pentru rezolvarea problemelor de optimizare liniara in forma canonica (punerea sa in practica: tabelele simplex, rezolvare de probleme cu ajutorul acestui algoritm)
7.	Algoritmul simplex pentru rezolvarea problemelor de optimizare liniara in forma canonica (citirea solutiei din ultimul tabel simplex, rezolvare de probleme)
8.	Algoritmul simplex pentru rezolvarea problemelor de optimizare liniara in forma canonica si dualitatea problemelor de optimizare liniara (rezolvarea dualei unei probleme de optimizare liniara in forma canonica folosind datele din ultimul tabel simplex)
9.	Probleme de optimizare liniara in forma standard (punerea in practica a algoritmului simplex pentru rezolvarea acestor probleme: tabelele simplex corespunzatoare, rezolvare de probleme cu acest algoritm, citirea solutiei dualei din ultimul tabel simplex)
10.	 Se incepe cu predarea unor elemente de teoria jocurilor (notiuni introductive, conceptul de joc matriceal); se rezolva exercitii/probleme legate de: stabilirea matricei de plati in cazul unor jocuri concrete; se mai exerseaza algoritmul simplex pentru rezolvarea problemelor de optimizare liniara in forma standard
11.	 Se predau: elemente de teoria jocurilor (principiul dominarii, clasificarea jocurilor matriceale); se rezolva exercitii/probleme legate de jocuri matriceale precum si de functii convexe
12.	 Se predau: elemente de teoria jocurilor (strategii in jocuri matriceale);  se rezolva exercitii/probleme legate de punctele de minim ale functiilor convexe si de problema celei mai bune aproximari
13.	 Se predau: elemente de teoria jocurilor (rezolvarea jocurilor matriceale prin reducere la probleme de optimizare liniara; se considera cazul in care valoarea inferioara a jocului este strict pozitiva); se rezolva jocuri matriceale prin utilizarea celor doi algoritmi simplex prezentati in seminariile anterioare
14.	 Se predau: elemente de teoria jocurilor (rezolvarea jocurilor matriceale prin reducere la probleme de optimizare liniara; se considera cazul in care valoarea inferioara a jocului nu este strict pozitiva, se prezinta etapele ce trebuie parcurse pentru a rezolva un joc matriceal); se rezolva jocuri matriceale utilizand cei doi algoritmi simplex prezentati in seminariile anterioare; se rezolva probleme de optimizare neliniara cu restrictii utilizand conditii de tip Karush-Kuhn-Tucker	

VII. Metode didactice folosite
Expunere, prezentare, proiecte, exerciţii, studiu individual, lucru in echipa	

VIII. Evaluare
Examenul final este scris si oral. La examen se evalueaza in principal capacitatea studentilor de a aplica teoria predata la curs/seminar la rezolvarea de probleme (avand atat o natura calculatorie in care trebuie aplicati algoritmii prezentati, cat si una teoretica).  La sfarsitul semestrului, fiecare student va trebui sa predea un proiect scris, realizat prin documentarea efectiva in unitati economice. Continul acestui proiect este o problema concreta de optimizare care apare in activitatea unitatii economice la care s-a facut documentarea, precum si modelul matematic aferent acestei probleme.

Ponderea acestui proiect in nota finala este de 20%, ponderea examenului final este de 80%.	

IX. Bibliografie suplimentară
1. BOYD, S., VANDENBERGHE, L.: Convex optimization. Cambridge University Press, Cambridge, 2004. 
2. BRECKNER, B.E.,  POPOVICI, N.: Convexity and Optimization. An Introduction. EFES, Cluj-Napoca, 2006.
3. VANDERBEI, R. J.: Linear Programming. Foundations and extensions. International Series in Operations Research&Management Science 37, Kluwer Academic Publishers, Boston, 2001.
4. Webster, R.: Convexity. Oxford University Press, New York, 1994.	

	Data,							Titular curs,
27 aprilie 2007				Lect. dr. BRECKNER Brigitte Erika