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

I. Date generale
Codul	Disciplina	
MMA0006	Optimizare liniară	

Semestrul	Ore: C+S+L	Categoria	Statutul	
5	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.	Conf.	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 optimizarea liniara  in Rn, incluzand fundamentarea ei teoretica (proprietati
ale poliedrelor si consecintele acestor proprietati  pentru problemele de optimizare liniara),  algoritmi
numerici pentru rezolvarea problemelor de optimizare liniara, elemente de teoria jocurilor matriceale.	

IV. Conţinutul disciplinei
1.	Introducere in tematica optimizarii liniare; modele matematice; formularea generala a problemei de optimizare in Rn, cazul particular al problemei de optimizare liniara in Rn. 
2.	Elemente de analiza convexa in spatiul euclidian n-dimensional (multimi convexe; conuri;  poliedre; puncte extremale ale multimilor convexe; puncte extremale si fete ale poliedrelor).
3.	Teoreme de alternativa pentru sisteme de ecuatii si inecuatii liniare  in Rn.
4.	Studiul problemelor de optimizare liniara in Rn (proprietati ale multimii solutiilor; caracterizarea solutiilor; probleme de optimizare liniara in forma canonica si probleme de optimizare liniara in forma standard).
5.	Metode numerice pentru rezolvarea problemelor de optimizare liniara (metoda grafica pentru rezolvarea problemelor de optimizare liniara in  R2; algoritmul simplex pentru rezolvarea problemelor de optimizare liniara in forma canonica si algoritmul simplex pentru rezolvarea problemelor de optimizare liniara in forma standard; metoda celor doua faze pentru probleme de optimizare liniara in forma standard).
6.	Dualitatea problemelor de optimizare liniara (interpretari economice; teoremele de dualitate). 
7.	Aplicatii ale optimizarii liniare la studiul jocurilor matriceale. 	

V. Bibliografie
1. BORGWARDT, K. H.: Optimierung, Operations Research, Spieltheorie. Birkhäuser, 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", Facultatea 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.
9. VANDERBEI, R. J.: Linear Programming. Foundations and extensions. International Series in Operations Research&Management Science 37, Kluwer Academic Publishers, Boston, 2001.

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 optimizarii liniare (prezentarea optimizarii liniare ca si un capitol fundamental al cercetarii operationale; modele matematice: exemple de probleme concrete  aparute din practica ce conduc la probleme de optimizare liniara; recapitularea unor notiuni si notatii de baza legate de spatiul euclidian Rn).
2.	Introducere in tematica optimizarii liniare  (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 in legatura cu optimizarea liniara (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 in legatura cu optimizarea liniara (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.	Sisteme de ecuatii si inecuatii liniare (teoremele de alternativa ale lui Farkas, Motzkin, Gordan si Gale). Probleme de optimizare liniara in forma canonica (definitie; caracterizarea solutiei).
6.	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.	Probleme de optimizare liniara in forma canonica (numarul de iteratii in algoritmul simplex pentru rezolvarea problemelor de optimizare liniara in forma canonica; prezentarea unor metode pentru evitarea ciclarii; scurt istoric al algoritmului simplex si consideratii cu privire la polinomialitatea sa).
8.	Dualitatea problemelor de optimizare liniara (modul de determinare a dualei unei probleme de optimizare liniara; interpretari economice; duala unei probleme de optimizare liniara in forma canonica; teorema slaba de dualitate si teorema tare de dualitate).
9.	Probleme de optimizare liniara in forma standard  (definitie; aducerea unei probleme de optimizare liniara la 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).
10.	Metoda celor doua faze pentru  problemele de optimizare liniara in forma standard. 
11.	Elemente de teoria jocurilor (notiuni introductive; jocuri matriceale: conceptul de joc matriceal, principiul dominarii, valoarea inferioara si valoarea superioara a unui joc matriceal; clasificarea jocurilor matriceale).
12.	Strategii in jocuri matriceale (strategii maximin si strategii minimax; legatura ce exista intre aceste strategii si solutiile anumitor probleme de optimizare liniara; notiunile de solutie a unui joc matriceal respectiv de valoare a unui joc matriceal). Rezolvarea jocurilor matriceale (rezolvarea jocurilor matriceale cu punct sa).
13.	Rezolvarea jocurilor matriceale (rezolvarea jocurilor matriceale fara punct sa prin reducere la probleme de optimizare liniara: considerarea celor doua cazuri, anume cand valoarea inferioara a jocului este strict pozitiva, respectiv cand nu este strict pozitiva; prezentarea etapelor ce trebuie parcurse pentru a rezolva un joc matriceal). 
14.	Recapitularea 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. Prezentarea unor directii actuale de cercetare in cadrul optimizarii liniare; optimizarea liniara ca si punct de plecare pentru optimizarea neliniara

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 exercitii/probleme legate de metoda grafica pentru rezolvarea problemelor de optimizare liniara in R2 precum si legate de poliedre.
3.	Rezolvare de exercitii/probleme legate de multimi convexe  precum si de caracterizarea existentei/inexistentei solutiei unei probleme de optimizare liniara.
4.	Rezolvare de exercitii/probleme legate de notiunea de punct extremal al multimilor convexe (in particular al poliedrelor).
5.	Rezolvare de exercitii/probleme legate de de teoremele de alternativa ale lui Farkas, Motzkin, Gordan si Gale precum si legate de caracterizarea solutiei unei probleme de optimizare liniara in forma canonica. 
6.	Algoritmul simplex pentru rezolvarea problemelor de optimizare liniara in forma canonica (punerea sa in practica: tabelele simplex, determinarea solutiei; rezolvare de probleme cu ajutorul acestui algoritm).
7.	Algoritmul simplex pentru rezolvarea problemelor de optimizare liniara in forma canonica (citirea solutiei problemei din ultimul tabel simplex in cazul in care fie baza canonica, fie opusul acesteia este o baza admisibila a problemei; rezolvari de probleme).
8.	Determinarea dualei unei probleme de optimizare liniara; rezolvare de probleme legate de teoremele de dualitate; determinarea solutiei dualei unei probleme de optimizare liniara in forma canonica folosind datele din ultimul tabel simplex; rezolvarea unor probleme de optimizare liniara in care intervine un parametru.  
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).
10.	Probleme de optimizare liniara in forma standard (determinarea solutiei dualei unei probleme de optimizare liniara in forma standard folosind datele din ultimul tabel simplex). Exersarea metodei celor doua faze pentru problemele de optimizare liniara in forma standard.
11.	Exersarea metodei celor doua faze pentru problemele de optimizare liniara in forma standard. Se rezolva exercitii/probleme legate de jocuri matriceale (stabilirea matricei de plati in cazul unor jocuri concrete; determinarea faptului daca un joc este sau nu cu punct sa). 
12.	Se rezolva exercitii/probleme legate de jocuri matriceale (stabilirea functiei care exprima castigul mediu al primului jucator in cazul unor jocuri matriceale concrete; aplicarea rezultatelor de la curs cu privire la strategii in jocuri matriceale; rezolvarea unor jocuri matriceale cu punct sa).
13.	Se rezolva jocuri matriceale fara punct sa utilizand cei doi algoritmi simplex invatati.
14.	Se rezolva jocuri matriceale in care in matricea de plati intervine un parametru.	

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

VIII. Evaluare
Examenul final este scris si oral, cel scris fiind obligatoriu, iar cel oral optional. In cazul in care se opteaza si pentru examenul oral, nota obtinuta la examen este media aritmetica a notelor obtinute la proba scrisa si la cea orala. La examen se evalueaza in principal capacitatea studentilor de a aplica teoria predata la curs/seminar prin 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 individual, realizat prin documentarea efectiva intr-o unitate economica. Proiectul trebuie sa contina descrierea unei probleme concrete de optimizare (liniara) 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%, iar ponderea examenului final este de 80%.	

IX. Bibliografie suplimentară
1.BLAGA L., LUPSA L.: Elemente de programare liniara. Ed. Risoprint, Cluj-Napoca, 2003
      2. BRECKNER, B.E.,  POPOVICI, N.: Convexity and Optimization. An Introduction. EFES, 
          Cluj- Napoca, 2006.
       3. Webster, R.: Convexity. Oxford University Press, New York, 1994.	

Decan,							 Sef de catedra,
Prof. dr. Tambulea  Leon                                          Prof. dr. Cobzaş Stefan

Data,						               Titular curs,
4.03.2009						   Conf. dr.  BRECKNER Brigitte Erika