1. SylabUZ
2. Faculty of Computer Science, Electrical Engineering and Automatics
3. winter term 2021/2022
4. Computer Science - Second-cycle Erasmus programme
5. Operational research

Generate PDF for this page

Operational research - course description

Aim of the course

• To provide basic skills in formulation of optimization tasks.
• To provide knowledge in elementary procedures of quantitative optimization.
• To give critical insight in the subject of reliability and efficiency of numerical process related to determination of the best solution.
• To derive essential skills of using optimization techniques in engineering applications.      

Prerequisites

Save changes

Mathematical analysis, Linear algebra and analytic geometry

Scope

Linear programming tasks (LPT). Standard formulation of LPT. Method of elementary solutions and simplex algorithm. Optimal choice for production assortment. Mixture problem. Technological process choice. Rational programming. Transportation and assignment problems. Two-person zero sum games and games with nature.

Network programming. Network models with determined logical structure. CPM and PERT methods. Time-cost analysis. CPM_COST and PERT-COST methods.

Non-linear programming tasks (NPT) – optimality conditions. Convex sets and  functions. Necessary and sufficient conditions for the solution existence in the case without constraints. Lagrange multiplayers method. Extrema of the function with equality and inequality constraints. Kuhn-Tucker conditions. Constraints regularity. Conditions of an equilibrium point existence. Least squares method. Quadratic programming.

Computational methods for solving NPT. Directional search methods: Fibonacci, golden search, Kiefer, Powell and Davidon. Method of basic search: Hooke-Jeeves and Nelder-Mead. Continuous and discrete gradient algorithm. Newton method. Gauss-Newton and Levenberg-Marquardt algorithms. Elementary methods of feasible direction: Gauss-Seidel, steepest decent, conjugate gradient of Fletcher-Reeves,   variable metric of Davidon-Fletcher-Powell. Searching for minimum in the case of constraints: internal, external and mixed penalty functions, projected gradient, sequential quadratic programming and admissible directions method. Elements of dynamic programming.

Practical issues. Simplification and elimination of constraints. Discontinuity elimination. Scaling. Numerical approximation of gradient. Usage of numerical packages. Presentation of methods implemented in popular environments for symbolic and numerical processing.

Teaching methods

Lecture;

Laboratory exercises.
 

Learning outcomes and methods of theirs verification

Outcome description	Outcome symbols	Methods of verification	The class form

Assignment conditions

Lecture –  the passing condition is to obtain positive mark from the exam;

Laboratory – the passing condition is to obtain positive marks from all laboratory exercises to be planned within the laboratory schedule.

Calculation of the final grade: lecture 50% + laboratory 50%

Recommended reading

1. Ferris M., Mangasarian O., Wright S.: Linear programming in MATLAB, Cambridge University Press, 2008.
2. Williams P.: Model Building in Mathematical Programming, 5th Edition, Wiley, 2013
3. Taha H. A.: Operations Research: An Introduction, 10th Edition, Pearson ,2016
4. Hillier F., Lieberman G.: Introduction to operations research, McGraw-Hill College, 1995.
5. Bertsekas D.: Nonlinear programming, 2nd edition, Athena Scientific, 2004
6. Boyd S., Vandenberghe L.: Convex optimization, Cambridge University Press, 2004.

Further reading

1. Winston W.: Operations Research Applications and Algorithms, Wadsworth Publishing Company, 1997.

2. Ravindran A., Philips D., Solberg J.: Operational research: Principles and Practice, Wiley, 1987.

Notes

Modified by dr hab. inż. Maciej Patan, prof. UZ (last modification: 15-07-2021 12:25)