1.       

Name of the discipline  

OPERATIONS RESEARCH

2.       

Study course,

specialty

3, Mathematics (economic activity)

3.       

Semester of study

6

4.       

Amount of credits                     

4

5.       

Lecturer’s S.N.P.

Lebedev Andrei 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, examination mark takes into account running tests marks (coefficient 0.3)

13.   

Certification form

Examination