Computer science | OPERATIONS RESEARCH

cod. 0512100012

OPERATIONS RESEARCH

	0512100012
	COMPUTER SCIENCE
	EQF6
	COMPUTER SCIENCE
	2021/2022

PERCORSO COMUNE

	OBBLIGATORIO
	YEAR OF COURSE 3
	YEAR OF DIDACTIC SYSTEM 2017
	SPRING SEMESTER

TEACHING UNITS

SSD	CFU	HOURS	ACTIVITY	TYPE OF ACTIVITY
MAT/09	4	32	LESSONS	BASIC COMPULSORY SUBJECTS
MAT/09	2	16	LAB	BASIC COMPULSORY SUBJECTS

	Objectives
	THE OPERATIONS RESEARCH COURSE AIMS TO PROVIDE THE KNOWLEDGE FOR SOLVING OPTIMIZATION PROBLEMS FORMULATED THROUGH MATHEMATICAL MODELS OF CONTINUOUS LINEAR PROGRAMMING (LP).

	Prerequisites
	THE COURSE REQUIRES A KNOWLEDGE OF THE BASIC NOTIONS OF LINEAR ALGEBRA AND ANALYTICAL GEOMETRY AND THE CAPACITY OF SOLVING SYSTEMS OF LINEAR EQUATIONS AND PERFORMING OPERATIONS ON VECTORS AND MATRICES.

	Contents
	1. LINEAR PROGRAMMING (PL) (LECTURES: 10H; EXERCISE 4H) - BASIC OPERATIONS ON MATRICES AND VECTORS, SYSTEM OF LINEAR EQUATIONS; - FORMULATION OF REAL PROBLEMS; - HYPERPLANES, HALF-SPACES, POLYHEDRA, EXTREME DIRECTIONS OF A POLYHEDRON, REPRESENTATION THEOREM. 2. THE SIMPLEX METHOD (LECTURES: 6H; EXERCISE 4H) - EXTREME POINTS OF A POLYHEDRON AND BASIC FEASIBLE SOLUTIONS, OPTIMALITY AND UNBOUNDEDNESS CONDITIONS, SIMPLEX METHOD ALGEBRA, DEGENERATE BASIC FEASIBLE SOLUTION AND CYCLING PHENOMENON, SIMPLEX CONVERGENCE; - STARTING BASIC FEASIBLE SOLUTION: TWO-PHASES METHOD AND BIG-M METHOD (ONLY PROBLEM DEFINITION). 3. THE DUALITY THEORY (LECTURES: 6H; EXERCISE 4H) - DUAL PROBLEM FORMULATION, THEOREM OF WEAK DUALITY, THEOREM OF STRONG DUALITY, COMPLEMENTARY SLACKNESS CONDITIONS, PRIMAL-DUAL RELATION; - ECONOMIC INTERPRETATION OF DUAL VARIABLES; - SENSITIVITY ANALYSIS: POST-OPTIMALITY ANALYSIS, OPTIMAL POINT VARIATION, OPTIMAL SOLUTION VALUE VARIATION BY CHANGING DATA; - USE OF THE EXCEL SOFTWARE TO SOLVE LINEAR PROGRAMMING PROBLEMS. 4. NETWORK OPTIMIZATION PROBLEMS (LECTURES: 10H; EXERCISE 4H) FORMULATIONS AND ALGORITHMS FOR THE FOLLOWING NETWORK OPTIMIZATION PROBLEMS: - MINIMUM COST FLOW; - TRANSPORTATION; - MAX FLOW; - SHORTEST PATH; - MINIMUM SPANNING TREE.

1. LINEAR PROGRAMMING (PL) (LECTURES: 10H; EXERCISE 4H)
- BASIC OPERATIONS ON MATRICES AND VECTORS, SYSTEM OF LINEAR EQUATIONS;
- FORMULATION OF REAL PROBLEMS;
- HYPERPLANES, HALF-SPACES, POLYHEDRA, EXTREME DIRECTIONS OF A POLYHEDRON, REPRESENTATION THEOREM.
2. THE SIMPLEX METHOD (LECTURES: 6H; EXERCISE 4H)
- EXTREME POINTS OF A POLYHEDRON AND BASIC FEASIBLE SOLUTIONS, OPTIMALITY AND UNBOUNDEDNESS CONDITIONS, SIMPLEX METHOD ALGEBRA, DEGENERATE BASIC FEASIBLE SOLUTION AND CYCLING PHENOMENON, SIMPLEX CONVERGENCE;
- STARTING BASIC FEASIBLE SOLUTION: TWO-PHASES METHOD AND BIG-M METHOD (ONLY PROBLEM DEFINITION).
3. THE DUALITY THEORY (LECTURES: 6H; EXERCISE 4H)
- DUAL PROBLEM FORMULATION, THEOREM OF WEAK DUALITY, THEOREM OF STRONG DUALITY, COMPLEMENTARY SLACKNESS CONDITIONS, PRIMAL-DUAL RELATION;
- ECONOMIC INTERPRETATION OF DUAL VARIABLES;
- SENSITIVITY ANALYSIS: POST-OPTIMALITY ANALYSIS, OPTIMAL POINT VARIATION, OPTIMAL SOLUTION VALUE VARIATION BY CHANGING DATA;
- USE OF THE EXCEL SOFTWARE TO SOLVE LINEAR PROGRAMMING PROBLEMS.
4. NETWORK OPTIMIZATION PROBLEMS (LECTURES: 10H; EXERCISE 4H)
FORMULATIONS AND ALGORITHMS FOR THE FOLLOWING NETWORK OPTIMIZATION PROBLEMS:
- MINIMUM COST FLOW;
- TRANSPORTATION;
- MAX FLOW;
- SHORTEST PATH;
- MINIMUM SPANNING TREE.

	Teaching Methods
	THE COURSE IS ORGANIZED IN 48 HOURS OF FRONTAL LESSONS (6 CFU), USING PROJECTED SLIDES. AT THE END OF EACH TOPIC, SOME EXAMPLES AND CLASSROOM EXERCISES ARE PRESENTED. DURING THE CLASSROOM EXERCISES, THE STUDENTS FACE SOME EXERCISES TO SOLVE BY USING THE TECHNIQUES PRESENTED IN THE THEORETICAL LECTURES. THE RESOLUTION OF THE EXERCISES, WHICH IS CARRIED OUT UNDER THE SUPERVISION OF THE TEACHER, SEEKS TO DEVELOP AND STRENGTHEN THE STUDENT’S CAPACITY OF IDENTIFYING THE MOST APPROPRIATE TECHNIQUES TO SOLVE THEM. METHODS TO PRODUCE A CLEAR AND ACCURATE PRESENTATION OF THE ACHIEVED RESULTS ARE ALSO PROPOSED.

Teaching Methods

THE COURSE IS ORGANIZED IN 48 HOURS OF FRONTAL LESSONS (6 CFU), USING PROJECTED SLIDES. AT THE END OF EACH TOPIC, SOME EXAMPLES AND CLASSROOM EXERCISES ARE PRESENTED. DURING THE CLASSROOM EXERCISES, THE STUDENTS FACE SOME EXERCISES TO SOLVE BY USING THE TECHNIQUES PRESENTED IN THE THEORETICAL LECTURES. THE RESOLUTION OF THE EXERCISES, WHICH IS CARRIED OUT UNDER THE SUPERVISION OF THE TEACHER, SEEKS TO DEVELOP AND STRENGTHEN THE STUDENT’S CAPACITY OF IDENTIFYING THE MOST APPROPRIATE TECHNIQUES TO SOLVE THEM. METHODS TO PRODUCE A CLEAR AND ACCURATE PRESENTATION OF THE ACHIEVED RESULTS ARE ALSO PROPOSED.

	Verification of learning
	THERE ARE NOT MIDTERM EXAMINATIONS FOR THIS COURSE. THE FINAL EXAM IS DESIGNED TO EVALUATE AS A WHOLE: THE KNOWLEDGE AND UNDERSTANDING OF THE CONCEPTS PRESENTED IN THE COURSE, AS WELL AS THE ABILITY TO APPLY SUCH KNOWLEDGE FOR THE RESOLUTION OF LINEAR PROGRAMMING PROBLEMS. THE EXAM CONSISTS OF A WRITTEN TEST AND AN ORAL INTERVIEW. - THE WRITTEN TEST IS DESIGNED TO ASSESS THE ABILITY TO SOLVE OPTIMIZATION PROBLEMS AND NORMALLY LASTS 120 MINUTES. IT CONSISTS OF 4 OR 5 EXERCISES, AND POSSIBLY OPEN-ENDED QUESTIONS, WHICH ARE GIVEN A SCORE. THE SUM OF THESE SCORES IS 30. TYPICAL TOPICS OF THE EXERCISES CONCERN: THE GRAPHICAL RESOLUTION OF PL PROBLEMS AND THE COMPUTATION OF THE EXTREME DIRECTIONS OF THE POLYHEDRON, THE FORMULATION OF OPTIMIZATION PROBLEMS, THE RESOLUTION OF A PL PROBLEM BY USING THE SIMPLEX METHOD, THE CONSTRUCTION OF THE DUAL PROBLEM, THE SENSITIVITY ANALYSIS AND THE RESOLUTION OF GRAPH PROBLEMS PRESENTED IN THE COURSE. THE SCORE OF THE WRITTEN EXAM IS EQUAL TO THE SUM OF THE SCORES ASSIGNED BY THE TEACHER TO THE EXERCISES SOLVED BY THE STUDENT. IS ADMITTED TO THE ORAL EXAMINATION THE STUDENT THAT GAINS A SCORE OF AT LEAST 18/30. - WITH THE ORAL INTERVIEW, ARE EVALUATED THE KNOWLEDGE ABOUT THE MODELLING AND SOLVING OF LINEAR PROGRAMMING PROBLEMS. THE INTERVIEW INCLUDES THE PRELIMINARY DISCUSSION OF THE WRITTEN TEST AND VARIOUS QUESTIONS REGARDING THE TOPICS OF THE COURSE PROGRAM. THE MINIMUM ASSESSMENT LEVEL (18) IS AWARDED WHEN THE STUDENT SHOWS A FRAGMENTARY KNOWLEDGE OF THEORETICAL CONTENTS AND A LIMITED ABILITY TO FORMULATE OPTIMIZATION PROBLEMS AND TO APPLY ALGORITHMS TO SOLVE THEM. THE MAXIMUM ASSESSMENT LEVEL (30) IS ATTRIBUTED WHEN THE STUDENT SHOWS A COMPLETE AND IN-DEPTH KNOWLEDGE OF THE COURSE TOPICS AND A REMARKABLE ABILITY TO IDENTIFY THE MOST APPROPRIATE METHODS TO SOLVE THE OPTIMIZATION PROBLEMS FACED. THE FINAL GRADE IS DEFINED BY THE TEACHER ACCORDING TO THE RESULTS OF THE TWO TESTS. IN ANY CASE, THE FINAL GRADE CANNOT EXCEED THE WRITTEN TEST GRADE BY MORE THAN 6 POINTS. IN THE EVENT THAT THE EXAM SHOULD TAKE PLACE REMOTELY DUE TO THE COVID-19 EMERGENCY, THE TEACHER CAN DECIDE (BY PROMPTLY INFORMING THE STUDENTS), TO ABOLISH THE WRITTEN TEST. IN THIS CASE, DURING THE ORAL EXAM STUDENTS WILL ALSO BE ASKED TO SOLVE ONE OR MORE EXERCISES OF THE TYPE PROPOSED IN THE WRITTEN TEST.

Verification of learning

THERE ARE NOT MIDTERM EXAMINATIONS FOR THIS COURSE.
THE FINAL EXAM IS DESIGNED TO EVALUATE AS A WHOLE: THE KNOWLEDGE AND UNDERSTANDING OF THE CONCEPTS PRESENTED IN THE COURSE, AS WELL AS THE ABILITY TO APPLY SUCH KNOWLEDGE FOR THE RESOLUTION OF LINEAR PROGRAMMING PROBLEMS.
THE EXAM CONSISTS OF A WRITTEN TEST AND AN ORAL INTERVIEW.
- THE WRITTEN TEST IS DESIGNED TO ASSESS THE ABILITY TO SOLVE OPTIMIZATION PROBLEMS AND NORMALLY LASTS 120 MINUTES. IT CONSISTS OF 4 OR 5 EXERCISES, AND POSSIBLY OPEN-ENDED QUESTIONS, WHICH ARE GIVEN A SCORE. THE SUM OF THESE SCORES IS 30. TYPICAL TOPICS OF THE EXERCISES CONCERN: THE GRAPHICAL RESOLUTION OF PL PROBLEMS AND THE COMPUTATION OF THE EXTREME DIRECTIONS OF THE POLYHEDRON, THE FORMULATION OF OPTIMIZATION PROBLEMS, THE RESOLUTION OF A PL PROBLEM BY USING THE SIMPLEX METHOD, THE CONSTRUCTION OF THE DUAL PROBLEM, THE SENSITIVITY ANALYSIS AND THE RESOLUTION OF GRAPH PROBLEMS PRESENTED IN THE COURSE. THE SCORE OF THE WRITTEN EXAM IS EQUAL TO THE SUM OF THE SCORES ASSIGNED BY THE TEACHER TO THE EXERCISES SOLVED BY THE STUDENT. IS ADMITTED TO THE ORAL EXAMINATION THE STUDENT THAT GAINS A SCORE OF AT LEAST 18/30.
- WITH THE ORAL INTERVIEW, ARE EVALUATED THE KNOWLEDGE ABOUT THE MODELLING AND SOLVING OF LINEAR PROGRAMMING PROBLEMS. THE INTERVIEW INCLUDES THE PRELIMINARY DISCUSSION OF THE WRITTEN TEST AND VARIOUS QUESTIONS REGARDING THE TOPICS OF THE COURSE PROGRAM. THE MINIMUM ASSESSMENT LEVEL (18) IS AWARDED WHEN THE STUDENT SHOWS A FRAGMENTARY KNOWLEDGE OF THEORETICAL CONTENTS AND A LIMITED ABILITY TO FORMULATE OPTIMIZATION PROBLEMS AND TO APPLY ALGORITHMS TO SOLVE THEM. THE MAXIMUM ASSESSMENT LEVEL (30) IS ATTRIBUTED WHEN THE STUDENT SHOWS A COMPLETE AND IN-DEPTH KNOWLEDGE OF THE COURSE TOPICS AND A REMARKABLE ABILITY TO IDENTIFY THE MOST APPROPRIATE METHODS TO SOLVE THE OPTIMIZATION PROBLEMS FACED.
THE FINAL GRADE IS DEFINED BY THE TEACHER ACCORDING TO THE RESULTS OF THE TWO TESTS. IN ANY CASE, THE FINAL GRADE CANNOT EXCEED THE WRITTEN TEST GRADE BY MORE THAN 6 POINTS.

IN THE EVENT THAT THE EXAM SHOULD TAKE PLACE REMOTELY DUE TO THE COVID-19 EMERGENCY, THE TEACHER CAN DECIDE (BY PROMPTLY INFORMING THE STUDENTS), TO ABOLISH THE WRITTEN TEST. IN THIS CASE, DURING THE ORAL EXAM STUDENTS WILL ALSO BE ASKED TO SOLVE ONE OR MORE EXERCISES OF THE TYPE PROPOSED IN THE WRITTEN TEST.

	Texts
	- M.S. BAZARAA, J.J. JARVIS & H.D. SHERALI, LINEAR PROGRAMMING AND NETWORK FLOWS, FOURTH EDITION, JOHN WILEY, 2010. - SLIDES AVAILABLE ON THE WEBPAGE OF THE TEACHER: HTTPS://DOCENTI.UNISA.IT/020511/RISORSE OTHER RESOURCES: HILLIER FREDERICK S., RICERCA OPERATIVA, MCGRAW-HILL EDUCATION, 2010.

	More Information
	- THE COURSE LANGUAGE IS ITALIAN. - THE ATTENDANCE OF THE LESSONS IS HIGHLY RECOMMENDED. - OTHER SUPPORTING MATERIAL IS AVAILABLE ON THE WEBPAGE: HTTPS://DOCENTI.UNISA.IT/001227/RISORSE - OFFICE HOURS FOR STUDENTS ARE AVAILABLE ON THE WEBPAGE: HTTPS://DOCENTI.UNISA.IT/001227/RISORSE

BETA VERSION Data source ESSE3 [Ultima Sincronizzazione: 2022-11-21]