1. 
Name of the discipline 
OPERATIONS RESEARCH 
2. 
Study course, specialty 
4, Mathematics (scientific and pedagogical activity) 
3. 
Semester of study 
7 
4. 
Amount of credits 
3 
5. 
Lecturer’s S.N.P. 
Romashchenko Galina Stanislavovna 
6. 
Aims of the study 
Study of the principal methods of solution of extremal problems of graph theory and game theory. The improvement of professional competence level in optimization problems solution. Further formation of student’s abstract mathematical thinking experience and skills of its application in concrete problems solution along with mathematical culture increase. As a result student has to be able to: apply the graph theory and game theory in practical problems solution; compile net models; exploit the dynamical programming methods. 
7. 
Prerequisites 
Mathematical analysis (calculus) Algebra and number theory Optimization methods Functional analysis 
8. 
Contents of the discipline 
History of extremal problems in graph theory. Problem of the minimal weight spanning tree (skeleton) finding. Prim algorithm and its correctness. Kruskal algorithm and its correctness. Oriented graphs. Problem of finding the shortest path between the two given vertexes. Dijkstra algorithm. Problem of finding of all the shortest paths in graph. Floyd algorithm. Negative length cycles finding. Networks, flows, sections. Ford – Fulkerson theorem (maximal flow criterion). Problem of finding of an admissible flow of the maximal capacity. Ford – Fulkerson algorithm. Problem of construction of the minimal price flow. BusakerGowen algorithm of construction of the minimal price flow among the flows of a given capacity. Traveling salesman problem. Hamilton cycles. Little’s algorithm. Branch and bound method. Scheduling planning. Network model construction, ranging, the critical paths finding. Jobs schedule graph construction, labor resources schedule graph construction. Schedule graph optimization. Game theory objects. Matrix and bimatrix games. Strategies, outcomes, gain function, games in the normal form, two person games, zero sum games. Preference relations and optimums. Dominating and undominatable strategies, and their existence. Pareto optimums. Two person games with zero sum. Lower and upper price of a game. Game price. Saddle points and game price. Von Neumann theorem on minmax. Canonical decision rules and Nash equilibriums. Mixed extensions of finite games. Price and saddle point existence in the mixed extensions of matrix games. Nash equilibriums existence in the mixed extensions of bimatrix games. 
9. 
Recommended literature 
1. Bakhtin V.I., Kovalenok A.P., Lebedev A.V., Lysenko Ju. V. Operations research. – Minsk, BGU, 2003 (in Russian). 2. Minieka E. Optimization algorithms for networks and Graphs. 1981. 3. Busaker R.G., Saaty T.L. Finite graphs and networks, 1974. 
10. 
Methods of teaching 
Lectures, laboratory practice, SSI (students scientific investigation) 
11. 
Language of teaching 
Russian 
12. 
Knowledge control and requirements 
Tests 
13. 
Certification form 
credit
