Исследование операций

Бакалавриат 2020/2021

Статус: Курс по выбору (Программная инженерия)

Направление: 09.03.04. Программная инженерия

Кто читает: Департамент программной инженерии

Где читается: Факультет компьютерных наук

Когда читается: 4-й курс, 1-3 модуль

Формат изучения: без онлайн-курса

Преподаватели: Жукова Галина Николаевна

Язык: английский

Кредиты: 8

Контактные часы: 60

Full Syllabus Ask Question

Abstract

Operations research is a section of applied mathematics related to the optimization of human activity, the work of various mechanisms and devices, logistics, traffic and much more. This course contains the following topics: linear programming (simplex method, duality, sensitivity analysis), integer linear programming, nonlinear programming, transportation problem, traveling salesman problem, dynamic programming, queueing theory and game theory. The lectures present theoretical material and methods for solving problems. In the practical classes, students learn to solve problems on the topic of a lecture given just before the lesson, at the end of the lesson they have to independently solve a problem on the topic. At the end of the course, students take an exam where they have to answer two theoretical questions and solve six problems. The course Operations Research is designed, to develop the skills to solve practical problems related to optimization and decision making.

Learning Objectives

The discipline goal is to introduce basic methods of Operations Research to students
to learn various techniques of solving Linear programming problems (including Integer programming), Nonlinear programming problems, Transportation problem, Traveling salesman problem and some other problems of Operations Research
to practice the use of software for solving Linear programming problems
to obtain skills in developing mathematical models for practical optimization task and in sensitivity analysis

Course Contents

Linear Programming
A linear programming problem formulation, basic concepts of the linear programming method. Graphical method for solving the linear programming problems. The canonical form of a linear programming problem. Slack and surplus variables. Basic and nonbasic variables. Simplex table. The dual linear programming problem. Dual variables in the simplex table. Dual prices. Sensitivity analysis. Integer linear programming. Gomory method. Branch and Bound method.
Non-linear programming
Lagrange multipliers method. Lagrange function. Necessary and sufficient conditions of Lagrange functions extremum. Gradient method for solving non-linear programming problems. The case of convex feasible space with linear boundaries.
Transportation problem
Northwest corner method and minimum cost method for finding a feasible solution. Multipliers method for optimum solution. Closed loops construction. Simplex method explanation of the method of multipliers.
Travelling salesman problem
Matrix representation of the problem. The nearest-neighbor heuristic algorithm for a feasible solution. Branch and Bound method for the optimum solution.
Dynamic programming
Formulation of the dynamic programming problem. Decomposing the multivariate problem into stages (single-variable subproblems). The recursive nature of the computations of dynamic programming. Forward and backward recursion. The principle of optimality. Bellman equations. Investment distribution. Sensitivity analysis.
Queueing theory
The basic concepts of queueing theory. Classification of queueing systems. Markov random process. Event streams. Kolmogorov equations. The process of birth and death.
Game theory
The concept of the game model. Saddle point. Solving matrix games in mixed strategies. A graphical solution of matrix games. Reduction of a matrix game to a linear programming problem. Multi-objective optimization. Wald, Hurwicz, Savage and Laplace criteria. Pareto optimality.

Assessment Elements

Контрольная работа (С1)
Контрольная работа (С2)
Контрольная работа (С3)
Контрольная работа (С4)
Контрольная работа (С5)
Контрольная работа (С6)
Контрольная работа (С7)
Контрольная работа (С8)
Контрольная работа (С9)
Контрольная работа (С10)
Контрольная работа (С11)
Контрольная работа (С12)
Экзамен (Экз)
Экзамен проводится по заранее разосланным заданиям. Студенты заполняют гугл-форму с ответами.

Interim Assessment

Interim assessment (3 module)
All marks are evaluated using 10 grade scale. Current control Оcurrent is evaluated as an average mark of tests. The final control is evaluated as follows Оfinal = Оtheor.1+ Оtheor.2+Оtask, where О theor.1,2 = {0,1,2}, Оtask = {0,1} for each of 6 tasks. О theor.1,2 =2 if the theoretical answer is complete and correct, О theor.1,2 =1 if the theoretical answer is incomplete but correct О theor.1,2 =0 if the theoretical answer is incorrect or absent If a student answered 2 theoretical questions of 2 and solved correctly 6 problems of 6 he/she obtains 10 marks (using the 10 grade scale). The resulting mark (for the bachelor diploma) is evaluated according to the following formula using the 10 grade scale: Оresult = 0,5· Оcurrent + 0,5· Оfinal The rounding system is the same for all the marks and is a simple mathematical one: 4.49 = 4, 4.50 = 5, etc. The lecturer can exclude the final control for those students who obtained Оcurrent=8,9,10 which means excellent work was done during the seminar classes. Those students obtain Оresult = Оcurrent.

Bibliography

Recommended Core Bibliography

Болотский А. В., Кочеткова О. А. - Исследование операций и методы оптимизации - Издательство "Лань" - 2020 - 116с. - ISBN: 978-5-8114-4568-4 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/136175

Recommended Additional Bibliography

Горлач Б.А. - Исследование операций - Издательство "Лань" - 2013 - 448с. - ISBN: 978-5-8114-1430-7 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/4865

Course Syllabus