Linear Programming

Recommended Prerequisites

Knowledge acquired on the Linear Algebra curricular unit.

Teaching Methods

Theoretical and practical lessons where the professor exposes more theoretical subjects and where students solve exercises and use software for a better understanding of algorithms.

Learning Outcomes

Students will be provided with theoretical and practical knowledge of the solution of optimization problems with functions and linear restrictions. We will also study some of the best known network optimization problems, such as the minimum-cost flow problem, transport, affectation, shortest path and maximum flow.

Generic competences:

Knowledge of mathematical results;

Capacity for formulating and solving problems;

Conception or use of mathematical models in real situations;

Rigorous and clear written and spoken expressions;

Competence in using computational tools;

Individual initiative;

Capacity for autonomous learning;

Critical thinking;

Capacity for teamwork;

Imagination and creativity.

Work Placement(s)

No

Syllabus

1. Linear Programming Formulations;

2. Normal Form and Admissible Basic Solutions;

3. Convex Sets and Extreme Points;

4. Linear Duality;

5. Primal Methods and Dual Simplex;

6. Existence and Unicity of the Optimal Solution for a Linear Program;

7. Complexity, Degeneracy and Implementation;

8. Treatment of Variables with Upper and Lower Limits;

9. Sensitivity Analysis and Post-Optimization;

10. Graph Theory Concepts Review;

11. Minimum-Cost Flow Linear Problem;

12. Transport Problem;

13. Affectation Problem;

14. Shortest Path and Maximum Flow Problems. 

Assessment Methods

Assessment
Resolution Problems: 15.0%
Exam: 85.0%

Bibliography

JÚDICE, J.; MARTINS, P.; PASCOAL, M.; SANTOS, J.. Programação Linear.

 

JÚDICE, J.; MARTINS, P.; PASCOAL, M.; SANTOS, J.. Optimização em Redes.

 

BAZARAA, M.S.; JARVIS, J.J. & SHERALI, H. D. (1990).  Linear Programming and Network Flows. 2nd Edition. New York: Wiley & Sons.

 

NASH, S. G. & SOFER, A. (1996). Linear and Nonlinear Programming. New York: McGraw-Hill.