SM/0132 - OPERATIONS RESEARCH
Academic Year 2019/2020
Free text for the University
ENRICO GORGONE (Tit.)
- Teaching style
- Lingua Insegnamento
|[60/65] MATHEMATICS||[65/20 - Ord. 2012] Applicativo||9||72|
The course, consistent with the objectives of the Degree Program, has as main objectives those of
- provide students with the tools for knowledge and understanding of operational research/decison science, particularly in decision-making processes and related implementations and codifications.
- introduce students to the use of conceptual tools and operative techniques useful for understanding, representing and dealing with mathematical / informatics problems, especially through optimization mathematical models.
- provide advanced calculation tools for decision analysis in order to acquire the indispensable application skills in different operational contexts.
In particular, according to the Dublin Descriptors
- Knowledge and understanding: provide students with the tools to develop original ideas derived from the knowledge acquired and the ability to understand.
- applying knowledge and understanding: provide students with the tools to mathematically formalize problems coming from the real world.
- making judgments: provide students with the tools for critical analysis of the problem to be analyzed.
- Communication skills: providing students with the tools to communicate the knowledge elaborated and applied in different contexts.
- Learning skills: provide students with the tools to study independently managing the time spent studying.
Basic knowledge of convex analysis and algebra, geometry, (mandatory) theory and study of data structures (useful).
-Introduction to Operations Research/Decisions Science
Definition, characterization, representation and structured organization of an algorithm: standardization of the structural maps. From the theorems to computational tools. The modeling process: from the physical problem to the sensitivity analysis.
The decision-making process: Description of the physical problem, the construction of the mathematical model, identifying the level of approximation (adherence), identification of the solution technique (algorithm), algorithm implementation, validation of the results .. Model concept: Physical models, conceptual and formal models, mathematical models, simulation models. The interdisciplinary approach in process modeling. Classification and construction of mathematical models: for decision making.
- Linear Programming Problems (LP):
Linear Algebra, Covex Analysis and Polyhedral. LP models, modeling techniques. Classical LP problems: transportation, diet, knapsac, production, resources management. Geometric solution, the requirement space.
- The Simplex method:
extreme points and optimality; basic feasible solution; key of the simplex method; algebra of the simplex method; termination criteria, block variable.
-Starting solution and convergence:
initial basic feasible solution; two-phase method.
Special simplex implementation:
the simplex method for bounded variables, network simplex; algebraic and graph structures. starting solution in network simplex by graph structures.
- The Karush-Kuhn-Tucker theorem and optimality conditions:
complementary slackness conditions, dual problem.
formulation of the dual problem; primal-dual ralationships; economic interpretation of the dual.
_ Decomposition method:
the Dantzig-Wolfe decomposition method.
- Notes on Heuristic and enumerative algorithm:
Problems with Boolean and integer variables, specialized algorithms, Branch & Bound algorithms, Problems of Vehicle Routing Problem. Use in logistics problems.
Notes on the genetic algorithm and tabu search.
The course consists of 72 hours of lectures of which 54 are devoted to lectures and 18 to resume foundamental concepts . During these appropriate calculation tools are provided and how to use them. The class is organized in working groups that are followed individually for the preparation of a final project. Application cases from the real world are analyzed and treated.
Verification of learning
The evaluation is performed during the preparation of the project by working groups, with the assistance of the teacher and the tutor, and the oral examination.
The evaluation is performed on the basis of the following criteria:
- Clarity in the exposition and synthesis of the final project by the members of the group;
- Ability to identify the topic of the question during the oral examination and to learn to highlight the fundamental theoretical and applied aspects.
The first criterion allows to
- verify the ability to apply modeling and algorithmic methodologies to a real or realistic case; - verify the ability to construct mathematical models of optimization starting from the physical description of the problem;
- verify the ability to use the software tools illustrated during the tutorials
- verify the ability to work in a group.
The second criterion allows to
- verify the level of acquisition of the knowledge of the subject;
- verify the ability to illustrate and argue the methodologies justifying the theoretical statements;
- verify the learning ability in the single study.
The process of quantification of the evaluation of the test takes place with the contribution of all the aspects and criteria mentioned and can not be coded in a formula or in tables.
Matteo Fischetti. Lezioni di Ricerca Operativa. ISBN: 978-1980835011
with reference to the adopted textbook:
THE FIRST 2 CHAPTERS CONTAIN RESPECTIVELY:
INTRODUCTION TO THE ISSUE AND NOTES ON BASIC KNOWLEDGE AND LINEAR PROGRAMMING MODELS
CHAP 1 INTRODUCTION,
CHAP 2 LINEAR ALGEBRA, CONVEX ANANLYSIS AND POLYHEDRAL SETS, PAGG 45-90
CAP 3 THE SIMPLEX METHOD
SECTIONS 3.1, 3.2, 3.3, 3.6,3.7, 3.8
PAGES FROM 91 TO 104
PAGES FROM 114 TO 130
CHAP. 4 STARTING SOLUTION AND CONVERGENCE
SECTIONS 4.1, 4.2
PAGES FROM 151 TO 156 (no 152)
CHAP.5 SPECIAL SIMPLEX IMPLEM……
SECTIONS 5.1, 5.2
PAGES FROM 201 TO 206; FROM 220 TO 234
PAGES da 237 a 243
CHAP. 6 DUALITY AND SENSITIVITY
SECTIONS 6.1, 6.2, 6.3
PAGES FROM 259 TO 273
CHAP.7 THE DECOMPOSITION PRINCIPLE
SECTIONS 7.1, 7.2
PAGES FROM 339 TO 353
- NOTES TAKEN DURING LESSONS AND TUTORIALS ARE AN USEFUL SUPPORT TO THE STUDY PROCESS.