Bachelor 2020/2021

Operations Research

Type: Elective course (Software Engineering)

Area of studies: Software Engineering

Delivered by: School of Software Engineering

Where: Faculty of Computer Science

When: 4 year, 1-3 module

Mode of studies: offline

Instructors: Galina Zhukova

Language: English

ECTS credits: 8

Contact hours: 60

Course Syllabus

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