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

SYLLABUS

I. Allgemeine Daten
Kennnummer	Disziplin	
MMA0008	Operations Research	

Semester	Stunden: C+S+L	Kategorie	Status	
6	2+2+0	specialitate	obligatorie	

II. Lehrkräfte der Universität
Name und	Wiss.	Position	Lehrstuhl	Lehrveranstaltung	
Vorname	Grad			V	S	L	
BRECKNER Brigitte Erika	Dr.	Lect.	Analiză şi Optimizare	*	*		

Assozierte Lehrkräfte
Name und	Wiss.	Institution	Position	Lehrveranstaltung	
Vorname	 			V	S	L	

III. Ziele der Disziplin
Die Vorlesung bietet eine Einführung in Operations Research mit Schwerpunkt im Studium der (linearen und nichtlinearen) Optimierungsaufgaben 	

IV. Inhalte der Disziplin
1.	Grundbegriffe des Operations Research. Mathematische Modellbildung. 
2.	Lineare Optimierung in Rn (Polyeder; der Begriff der linearen Optimierungsaufgabe; die graphische Methode zur Lösung linearer Optimierungsaufgaben in  R2; Alternativsätze für lineare Gleichungs- und Ungleichungssysteme; lineare Optimierungsaufgaben in kanonischer bzw. in Standardform; der Simplex-Algorithmus zur Lösung der linearen Optimierungsaufgaben in kanonischer Form und der Simplex-Algorithmus zur Lösung der linearen Optimierungsaufgaben in Standardform; die Dualität der linearen Optimierungsaufgaben; Spieltheorie) 
3.	Konvexe Analysis im n-dimensionalen euklidischen Raum (konvexe Mengen; Kegel; Extremalpunkte konvexer Mengen; Extremalpunkte und Seiten von Polyedern; die Trennung der konvexen Mengen durch Hyperbenen; konvexe Funktionen; Eigenschaften konvexer Funktionen; spezielle Klassen von konvexen  Funktionen)
      4.   Nichtlineare Optimierung in Rn (Minimalpunkte konvexer Funktionen; das Problem der   Bestapproximation; notwendige und hinreichende Bedingungen für die Lösung nichtlinearer Optimierungsaufgaben mit Nebenbedingungen; Dualität der nichtlinearen Optimierungsaufgaben mit Nebenbedingungen)	

V. Pflichtliteratur
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. Thematik der wöchentlichen Lehrveranstaltungen
Vorlesungen: Als begleitende Literatur werden hauptsächlich [2] und [5] verwendet.

1.	Einführung in Operations Research. (Grundlegende Begriffe in Operations Research; die Etappen eines Planungsprozesses in Operations Research; mathematische Modelle:  Beispiele für konkrete Probleme aus der Praxis, die zu Optimierungsaufgaben führen;  die wichtigsten Kapitel des Operations Research)
2.	Lineare Optimierung in Rn (Definition der Optimierungsaufgaben in Rn; Hyperebenen, Halbräume und Polyeder in Rn; Definition der linearen Optimierungsaufgaben in Rn; die graphische Methode zur Lösung linearer Optimierungsaufgaben in R2)
3.	Konvexe Analysis im n-dimensionalen euklidischen Raum (konvexe Mengen; konvexe Hülle; Kegel; Rezessionskegel einer Menge; der Darstellungssatz für Polyeder und seine Folgerungen für das Studium linearer Optimierungsaufgaben: die Charakterisierung der Lösbarkeit/Unlösbarkeit  linearer Optimierungsaufgaben)
4.	Konvexe Analysis im n-dimensionalen euklidischen Raum (Extremalpunkte konvexer Mengen und deren Charakterisierung; Charakterisierung der Extremalpunkte der Polyeder;  Charakterisierung der spitzen Polyeder; Seiten der Polyeder, Beschreibung der Lösungsmenge einer linearen Optimierungsaufgabe;  Beweis der Existenz einer Lösung einer linearen Optimierungsaufgabe,  die gleichzeitig auch  ein Extremalpunkt des Zulässigkeitsbereiches der betreffenden Aufgabe ist)   
5.	Lineare Optimierung in Rn (lineare Gleichungs- und Ungleichungssysteme: die Alternativsätze von Farkas, Motzkin, Gordan und Gale)
6.	Lineare Optimierung in Rn (Definition der linearen Optimierungsaufgaben in kanonischer Form; Charakterisierung der Lösung einer linearen Optimierungsaufgabe in kanonischer Form; die theoretischen Grundlagen für den Simplex-Algorithmus zur Lösung  linearer Optimierungsaufgaben in kanonischer Form: die Optimalitätsbeding, die Unbeschränktsheitsbedingung, die Begründung des eigentlichen Iterationsschrittes im Simplex- Algorithmus; es werden die  einzelnen Iterationsschritte des  Simplex-Algorithmus aufgezählt)
7.	Lineare Optimierung in Rn (die Endlichkeit des Simplex-Algorithmus zur Lösung linearer Optimierungsaufgaben in kanonischer Form; ein kurzer geschichtlicher Überblick zum Simplex-Algorithmus; die Dualität der linearen Optimierungsaufgaben: das Bestimmen des Dualproblems einer linearen Optimierungsaufgabe; das Dualproblem einer linearen Optimierungsaufgabe in kanonischer Form) 
8.	Lineare Optimierung in  Rn (die Dualität der linearen Optimierungsaufgaben: der schwache und  der starke Dualitätssatz; Definition der linearen Optimierungsaufgaben in Standardform: das Bestimmen der Standardform einer linearen Optimierungsaufgabe)
9.	Lineare Optimierung in  Rn (lineare Optimierungsaufgaben in Standardform: die Charakterisierung der Lösung einer linearen Optimierungsaufgabe in Standardform, Extremalpunkte des Polyeders der zulässigen Punkte einer linearen Optimierungsaufgabe in Standardform;  der Simplex-Algorithmus zur Lösung linearer Optimierungsaufgaben in Standardform). Konvexe Analysis im n-dimensionalen euklidischen Raum (die Trennung der konvexen Mengen durch Hyperebenen) 
10.	Nichtlineare Optimierung in  Rn (konvexe Funktionen: Definition, Beispiele, Eigenschaften, die Ungleichung von Jensen, die Stetigkeit und die Differenzierbarkeit konvexer Funktionen)
11.	Nichtlineare Optimierung in  Rn (konvexe Funtionen: die Charakterisierung konvexer Funktionen  mit Hilfe von  Ungleichungen; spezielle Klassen von konvexen Funktionen: streng konvexe Funktionen und affine Funktionen)  
12.	 Nichtlineare Optimierung in  Rn (Minimalpunkte konvexer Funktionen: Eigenschaften und Charakterisierungen dieser Punkte; das Problem der Bestapproximation als nichtlineares Optimierungsproblem: hinreichende  Bedingungen für die Existenz und Eindeutigkeit der Bestapproximation, Charakterisierung der Bestapproximation) 
13.	 Nichtlineare Optimierung in  Rn (Optimierungsaufgaben mit Nebenbedingungen: Definition, notwendige und hinreichende Bedingungen vom Karush-Kuhn-Tucker  Typ für die Lösungen dieser Aufgaben)
14.	 Nichtlineare Optimierung in  Rn (die Dualität der Optimierungsaufgaben mit differenzierbarer Zielfunktion  und differenzierbaren Nebenbedingungen). Eine kurze Wiederholung des Stoffes, um einen Überblick zu ermöglichen sowie um Zusammenhänge zwischen den einzelnen Teilen zu betonen. 

Übungen: Inhaltlich sind die Übungen auf die Vorlesungen abgestimmt und bezwecken das Vertiefen des in der Vorlesung behandelten Stoffes durch das Lösen von Aufgaben in Gruppenübungen (die Aufgaben werden hauptsächlich aus [4] und [6] ausgesucht)

      1.  Bestimmen mathematischer Modelle.
2.	Aufgaben zu Polydern bzw. zur graphischen Methode zur Lösung linearer Optimierungsaufgaben in R2. 
3.	Lösen von Aufgaben zu konvexen Mengen, sowie zur Charakterisierung der Lösbarkeit linearer Optimierungsaufgaben.
4.	Lösen von Aufgaben zu Extremalpunkten der konvexen Mengen (und der Polyeder) 
5.	Lösen von Aufgaben zu den Eigenschaften der Lösungsmenge einer linearen Optimierungsaufgabe und zu den Alternativsätzen von Farkas, Motzkin, Gordan und Gale.
6.	Der Simplex-Algorithmus zur Lösung linearer Optimierungsaufgaben in kanonischer Form (Simplex-Tabellen, das Lösen von Aufgaben mit Hilfe dieses Verfahrens) 
7.	Der Simplex-Algorithmus zur Lösung linearer Optimierungsaufgaben in kanonischer Form (das Ablesen der Lösung aus der letzten Simplex-Tabelle,  Lösen von Aufgaben)
8.	Der Simplex-Algorithmus zur Lösung linearer Optimierungsaufgaben in kanonischer Form und die Dualität der linearen Optimierungsaufgaben (das Lösen der Dualen einer linearen Optimierungsaufgaben in kanonischer Form mit Hilfe der Eintragungen aus der letzten Simplex-Tabelle)
9.	Lineare Optimierungsaufgaben in Standardform (die entsprechenden  Simplex-Tabellen, das Ablesen der Lösung der Dualen aus der letzten Simplex-Tabelle)
10.	 Grundbegriffe der Spieltheorie (einführende Begriffe, Matrixspiele); das Bestimmen der Auszahlungsmatrix konkreter Matrixspiele; ausserdem wird auch noch der Simplex-Algorithmus zur Lösung linearer Optimierungsaufgaben in Standardform geübt
11.	 Matrixspiele (das Reduzierungsprinzip, die Klassifikation der Matrixspiele); es werden Aufgaben zu Matrixspielen sowie zu konvexen Funktionen gelöst
12.	 Strategien in Matrixspielen; es werden Aufgaben zu den Minimalpunkten konvexer Funktionen sowie zum Problem der Bestapproximation gelöst
13.	 Lösen der Matrixspiele durch Zurückführung auf lineare Optimierungsaufgaben (der Fall, wenn der untere Spielwert streng positiv ist); es werden  Matrixspiele unter Zuhilfenahme der Simplex-Algorithmen  gelöst
14.	 Lösen der Matrixspiele durch Zurückführung auf lineare Optimierungsaufgaben (der Fall, wenn der untere Spielwert nicht streng positiv ist; die Etappen zur Lösung eines Matrixspieles);
es werden sowohl Matrixspiele mit Hilfe der Simplex-Algorithmen, als auch nichtlineare Optimierungsaufgaben mit Nebenbedingungen mit Hilfe der Karush-Kuhn-Tucker Bedingungen  gelöst	

VII. Didaktische Methoden
Vortrag, Unterrichtsgespräch, Problematisierung, Projekte, Aufgabenlösen, Selbststudium, Gruppenübungen 	

VIII. Beurteilung der studentischen Leistungen
Die Endprüfung besteht aus einem schriftlichen und einem mündlichen Teil (wobei der letztere nicht verpflichtend ist). In diesen wird vor allem die Fertigkeit geprüft, die in den  Vorlesungen und  Übungen erworbenen Kenntnisse  für das Lösen von Aufgaben (sowohl theoretischer, als auch rechnerischer Natur)  einzusetzen. Ausserdem muss Ende des Semesters  jeder Student ein Projekt abgeben. Das Thema des Projektes ist die Beschreibung  einer konkreten Optimierungsaufgabe (und ihres mathematischen Modells), die man aufgrund einer Recherche in der Wirtschaft (z.B. bei einer Firma) ausfindig gemacht hat. 

Die Gesamtnote für diese Disziplin wird nach der Formel G := (4x+ y)/5 berechnet, wobei x die in der Prüfung und y die für das Projekt  erzielte Note bezeichnen.	

IX. Zusatzliteratur
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.	

	Datum,						Verantwortliche Lehrkraft,
27. April 2007					Lect. Dr. BRECKNER Brigitte Erika