### Linear and Integer Programming (2015)

Welcome to Theories of Science

Description:

2 Syllabus Sketch

2.1 Mathematical Preliminaries

Vector Addition, Multiplication of a Vector by a Scalar,Vector Multiplication, Norm of a Vector, Special Vector Types, Linear Dependence and Independence, Spanning Sets and Bases, Matrix Addition, Multiplication by a Scalar, Matrix Multiplication, Special Matrices, Determinants, The Inverse of a Matrix, The Rank of a Matrix, The Solution of Simultaneous Linear Equations, A Unique Solution of A _ x = b, An Infinite Number of Solutions to A _ x = b.

2.2 Overview

The Linear Decision Model, Applications of Linear Programming.

2.3 The Conventional Linear Programming Model

Models and Model Types, General Guidelines in Model Building, Definitions, Basic Steps in Linear Programming Model Formulation, The General Form of the Linear Programming Model, Assumptions of the Linear Programming Model, Examples of Linear Programming Model Formulation Model Validity.

2.4 Foundations of the Simplex Method

Converting a Linear Program into Standard Form, Graphical Solution of 2-dimensional Linear Programs, Convex Sets and Polyhedral Sets, Extreme Points, Extreme Directions, and Optimality, Basic Feasible Solutions and Extreme Points.

2.5 The Simplex Method: Tableau and Computation

Algebra of the Simplex Method, The Simplex Method in Tableau Form, Finding the initial Basic Feasible Solution, Unrestricted Variables and Variables with Negative Lower Bounds, Degeneracy and Cycling.

2.6 Special Simplex Implementations

The Revised Simplex Method, The Product Form of the Inverse, The Bounded Variables Simplex Method, Decomposition.

2.7 Duality

Formulation of the Linear Programming Dual, Relationships in Duality, Geometric Interpretation of Optimality Conditions, Farkas’ Lemma.

I would like to reiterate that this is a sketch of the topics that we will be covering. For various reasons, I may choose to drop a mentioned topic or cover a new topic. In such cases, advance notice will be given.

Assessment:

Quizzes (2) - Two quizzes will be conducted, one on August 7 and the second on August 14.

pass/fail

Learning outcomes

Upon successful completion of this course, students should :

(a) Understand how to model real-world problems using linear and integer programs.

(b) Understand the basics of linear algebra necessary for linear programming.

(c) Understand the mathematical underpinnings of the SImplex algorithm.

(d) Use the Simplex Method to solve linear programs.

References

[IC93] James P. Ignizio and Tom P. Cavalier. Linear Programming. Prentice Hall, 1993.

[Sch87] A. Schrijver. Theory of Linear and Integer Programming. John Wiley and Sons, New York, 1987.

Organizer: Professor Peter Axel Nielsen, e-mail: pan@cs.aau.dk

Lecturers: K. Subramani e-mail: k.subramani@mail.wvu.edu

ECTS: 3.0 ECTS

Time: (b) Meeting Times:

Tuesday 4. August: 13.00-15.00

Wednesday 5. August: 13.00-15.00

Friday 7. August: 13.00-15.00

Monday 10. August: 13.00-15.00

Thursday 13. August: 13.00-15.00

Friday 14. August: 13.00-15.00

Place: Room 0.2.90 Selmal Lagerlöfsvej 300, 9220 Aalborg.

Zip code: 9220

City: Aalborg

Number of seats: