Welcome to Theories of Science


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.


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



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.



[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


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:

Deadline: 3 August 2015

Important information concerning PhD courses
We have over some time experienced problems with no-show for both project and general courses. It has now reached a point where we are forced to take action. Therefore, the Doctoral School has decided to introduce a no-show fee of DKK 5,000 for each course where the student does not show up. Cancellations are accepted no later than 2 weeks before start of the course. Registered illness is of course an acceptable reason for not showing up on those days. Furthermore, all courses open for registration approximately three months before start. This can hopefully also provide new students a chance to register for courses during the year. We look forward to your registrations.