Faculty of BSU

1. |
Name of the discipline |
OPERATIONS RESEARCH |

2. |
Study course, specialty |
3, Mathematics (research and production activities) |

3. |
Semester of study |
6 |

4. |
Amount of credits |
4 |

5. |
Lecturer’s S.N.P. |
Lebedev Andrey Vladimirovich |

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. Busaker-Gowen 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. The score on the exam is set taking into account the current academic performance (with a coefficient of 0.3) |

13. |
Certification form |
Exam |