Operational Research

It is not possible to register for the course U63C5101 if the student is concurrently registered for or has previously completed the course 32BC-P-OPVY-01 (mutually exclusive courses).

The requirement for course U63C5101 can be fulfilled by substitution with the course 32BC-P-OPVY-01.

Garant předmětu:

Lecturer:

Tutor:

Supervisor:

Institute of Economic Studies

Synopsis:

Operations research is the branch of science dealing with formulation, modelling and solution of various decision-making situations in which we select the best of the acceptable solutions.

Requirements:

calculator, MS Excel

Syllabus of lectures:

1. Introduction to the subject Linear programming. Constructing mathematical models. General rules for constructing mathematical models. The base type of the job-cutting plan Production program, the mixing problem, the investment problem. Building models in practice.

2. Basic concepts of linear programming. Array notation systems of equations. Basic solution of systems of equations. Canonical form of linear programming tasks. Modifying the restrictive conditions of the equations and inequalities with a negative right side. Admissible basic solution of linear programming tasks.

3. Graphical solution of linear programming tasks. The basic principles of graphic solutions, process graphic solution.

4. Simplex method of the solution of linear programming tasks - solution by using the simplex algorithm. The array to write the simplex table.

5. Duality. Compilation of dual task, finding a solution to the dual tasks of the simplex table primary tasks. The theorem of complementarity. Weak and strong duality theorem.

6. Economic interpretation of the dual-coupled problems. Dual simplex algorithm.

7. Sensitivity analysis. Sensitivity analysis of the right side of the restrictive conditions. Sensitivity analysis of the coefficients of the special features.

8. Integer programming. Cutting-plane method. Gomory algorithm I and II. Integer request to all the structural variables. Integer request to selected structural variables.

9. The transport job. The formulation of transport tasks. Finding the default basic transport task solution - Northwest corner method, Flash card method and the VAM (Vogel approximation method). Dantzig optimization method.

10. An assignment problem. Minimize or maximize the formulation of problems. The Hungarian method of the solution of assignment problem. Finding the optimal permutation.

11. Graph theory. The basic concepts of graph theory. Representations of graphs. The skeleton, trees, paths in graphs. An isomorphism of graphs.

12. Scan oriented and non-oriented graphs. Graph algorithms. The maximum search path. Determination of maximum flow in the network throughput. Floyd's algorithm.

13. Network analysis and method of CPM - critical path method. The PERT Method. Determination of the time reserve.

14. Introduction to the inventory theory.

Syllabus of tutorials:

1. Constructing mathematical models. Practicing of basic types of tasks LP - Production program, cutting plan, mixing problem, investment problem.

2. Examples for converting LP tasks to canonical form of linear programming task.

3. Graphical solution of the linear programming task.

4. Simplex method of solving the problem of linear programming - solution using simplex algorithm.

5. Simplex method of solving the problem of linear programming - solution using matrix writing of a simplex table.

6. Compilation of dual task, find a solution of a dual task from a simplex table of the primary task. Applying a complementary sentence to finding a solution to a dual task from the primary task.

7. Examples of Dual Simplex Algorithm.

8. Sensitivity analysis I. Analysis of right sensitivity of limiting conditions.

9. Sensitivity analysis II. Sensitivity analysis of the target function coefficients.

10. Integer programming. Cutting Supplement Method. Gomorihy algorimus I. and II. The integer requirement for all structural variables. Request an integer only for selected structural variables.

11. Transport task. Formulation of the transport task. Finding the initial basic transport solution solution - Northwest corner method, Index method and VAM method (Vogel approximation method). Dantzig's optimization method.

12. Assignment problem. Minimization or maximization task formulation. Hungarian method of solving the assignment problem. Search for optimal permutation.

13. Theory of graphs. Representation of graphs. Skeletons, trees, paths in charts. Isomorphism of graphs

14. Network Analysis. Determination of the critical path. Build a network chart.

Study Objective:

The aim will be to teach students to create and solve mathematical models of real-world (primarily economic) systems with the emphasis on finding optimal decisions according to selected criteria. Students will be acquainted with the areas of linear programming and addressing general or integer linear programming algorithm of dual simplex/simplex algorithm. They will also be familiar with the problems of transport tasks in order to minimize the transport costs and the assignment problem with the application of the Hungarian method to find the optimal assignment.

It will also be the aim to acquaint students with the basic concepts of graph theory, in particular representations of graphs, charts, skeletons search paths or throughput in the chart, graph algorithms in task-oriented and non-oriented charts. The issue will also be part of the network analysis, in particular the application of CPM and PERT method.

At the end, students will be introduced to an introduction to inventory theory, respectively inventory management models.

Study materials:

JABLONSKÝ, J. Programy pro matematické modelování. Praha: Oeconomica, 2011. 258 s. ISBN 978-80-245-1810-7.

JABLONSKÝ, J. Operační výzkum. 3.vyd. Praha: Professional Publishing, 2007. ISBN 978-80-8694-644-3.

VOLEK, J., LINDA, B. Teorie grafů - aplikace v dopravě a veřejné správě. Pardubice: Univerzita Pardubice, 2012. ISBN 978-80-7395-225-9.

BRÁZDOVÁ, M. Řešené úlohy lineárního programování. Pardubice: Univerzita Pardubice, 2011. ISBN 978-80-7395-361-4.

Note:

Further information:

http://moodle-vyuka.cvut.cz

No time-table has been prepared for this course

The course is a part of the following study plans:

• B-EK-prez.forma od 15/16 (compulsory course)
• B-PM-prez.forma od 15/16 (compulsory elective course)
• B-EK-prez.forma od 16/17 (compulsory course)
• B-EK-prez.forma od 17/18 (compulsory course)
• B-EM-P prezenční studium od 18/19 (compulsory course)
• B-EM-P prezenční studium od 19/20 (compulsory course)
• B-EM-P prezenční studium od 20/21 (compulsory course)
• B-EM-P prezenční studium od 21/22 (compulsory course)
• B-EM-P prezenční studium od 22/23 (compulsory course)