Linear Programming

Academic year
Subject Area
Language of Instruction
Mode of Delivery
ECTS Credits
1st Cycle Studies

Recommended Prerequisites

Knowledge on Linear Algebra.

Teaching Methods

In class, the instructor exposes theoretical concepts, presents examples, encourages problem solving by students, punctually using appropriate software, and encourages discussion. During the semester, tutorial support is provided to students, outside of classes, both for the resolution of proposed exercises and in preparation for evaluation tests.

Learning Outcomes

The main objectives are the acquisition of knowledge about the theoretical analysis and practical resolution of linear programs, optimization problems in Rn defined exclusively by linear functions. After completing the curricular unit, the student should know the simplex and interior points algorithms, as well as master aspects related to the facial structure of polyhedra, fundamental for the subsequent analysis of optimization problems in discrete structures, and the specificity of large problems, by means of column generation or of network flow optimization type algorithms.

This curricular unit allows to develop the following skills: knowledge of mathematical results; ability to formulate and solve problems; design or use of mathematical models for real situations; rigorous and clear written and oral expressions; competence in the use of computational tools; individual initiative and teamwork; autonomous learning and critical thinking.

Work Placement(s)



1. Linear Programming Formulations;

2. Convex Sets and Extreme Points;

3. Linear Duality;

4. Primal and Dual Simplex Methods;

5. Sensitivity Analysis and Re-Optimization;

6. Large scale optimization (strategies);

7. Minimum-Cost Flow Linear Problem;

8. Interior Point Methods;

9. Facial structure of Polyhedra

10. Algebraic Modeling

Head Lecturer(s)

Marta Margarida Braz Pascoal

Assessment Methods

Continuous assessment
Resolution Problems: 10.0%
Laboratory work or Field work: 15.0%
Frequency: 75.0%

Final assessment
Exam: 100.0%


J. Júdice, P. Martins, M. Pascoal, J. Santos, Programação Linear, Departamento de Matemática da FCTUC, 2009.

J. Júdice, P. Martins, M. Pascoal, J. Santos, Otimização em Redes, Departamento de Matemática da FCTUC, 2009.

M.S. Bazaraa, J.J. Jarvis, H.D. Sherali, Linear Programming and Network Flows, segunda edição, Wiley & Sons, 1990.

D. Bertsimas, J.N. Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997.

Nash, S. G. & Sofer, A. Linear and Nonlinear Programming. New York: McGraw-Hill, 1996.