1.       

Name of the discipline  

OPERATIONS RESEARCH

2.       

Study course,

specialty

4,  Computer mathematics and systems analysis

3.       

Semester of study

7

4.       

Amount of credits                     

2

5.       

Lecturer’s S.N.P.

Romashchenko Galina Stanislavovna

6.       

Aims of the study

A study of the basic methods for solving extremal problems in graph theory and game theory. Increase the level of professional competence in solving optimization problems. Further development of students’ skills in abstract mathematical thinking and the ability to apply it in specific tasks, increase their mathematical culture.

As a result of the study, the student should be able to:

be able to:

To apply graph theory and game theory to solve practical problems;

compile network models;

use the methods of dynamic programming

7.       

Prerequisites

Mathematical analysis

Algebra and Number Theory

Optimization methods

Functional Analysis

8.       

Contents of the discipline

The history of the occurrence of extremal problems in graph theory. The problem of constructing a spanning tree of minimal weight. Prima algorithm, its correctness. Kraskal’s algorithm and its correctness. Oriented graphs. Algorithms of Dijkstra and Floyd.

The problem of finding the shortest path between two given vertices. Dijkstra’s algorithm. The problem of finding all shortest paths in a graph. Floyd’s algorithm. Finding cycles of negative length. Networks, flows, sections. The Ford-Falkerson theorem (the criterion for the maximality of a flow). The problem of finding the permissible flux of maximum power. Algorithm of Ford-Falkerson. The problem of constructing a minimum cost stream. The Basaker-Gowen algorithm for constructing a minimum-cost stream among flows of a given power. The traveling salesman’s problem. Little’s algorithm. Hamiltonian cycles. Method of branches and boundaries. Scheduling. Statement of the problem, the main stages of the solution. Building a network model, ranking, finding critical paths. Construction of a calendar schedule of work and distribution of labor resources. Optimization of the calendar schedule.

Elementary concepts of game theory. Matrix and bimatrix games. Strategies, outcomes, winning functions, normal-form games, two-person games, zero-sum games. Attitudes of preferences and optima. Dominant and non-dominant strategies, their existence. Pareto optimality and the existence of Pareto optima. The game of two persons with zero sum. The lower and upper price of the game, the connection between them. The price of the game. The relationship between games that have a price, and inessential games. Saddle points and the price of the game. Von Neumann’s theorem on minimax. Canonical rules of decision-making and Nash equilibrium.

Mixed expansion of the ultimate games.

The existence of a saddle point and a price in a mixed matrix game expansion. The existence of Nash equilibria in the mixed extension of the bimatrix game.

9.       

Recommended literature

1. Bakhtin VI, Kovalan ok AP, Lebedev AV, Lysenko Yu.V. Operations research. – Minsk, BSU, 2003

2. Minika E. Optimization algorithms on networks and graphs. 1977.

3. Basaker P., Saati T. 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