Prerequisite:
MT182. Students may
not take both MT262 and CS349.
Teaching: 33hr lectures
Assessment: Two hour written examination
·
To show how a
wide range of problems may be formulated as linear programming (LP) problems;
·
To show how
two-variable problems may be solved using graphical methods;
·
To show how the
general LP problem can be solved using the simplex algorithm;
·
To show how
duality in LP fits into a more general framework using Lagrange multipliers;
·
To show how the
transportation and allocation problems may be solved using special algorithms;
·
To show how the
integer constraint may be taken into account.
On
completion of the course the students should be able to:
·
formulate
problems as LP problems;
·
solve
two-variable problems by graphical means;
·
use the simplex
algorithm to solve small LP and transportation problems;
·
use the Hungarian
algorithm to solve assignment problems;
·
solve integer programming problems using the branch and
bound method.
Linear programmes: Examples
of formulation of problems as LPs. Examples with solutions by diagram. Unbounded and infeasible
LPs. General LPs: feasible and
basic feasible solutions.
Simplex method: How
you solve with the simplex method, with the emphasis on elementary row
operations. The
formula for the dj. Getting started: the
two-phase method, infeasibility.
Proof of termination, cycling. Brief mention of complexity.
Illustration using a package.
Duality: Its meaning;
dual of the dual is the primal; the dual solution; the duality theorem; the
simplex tableau displays the dual solution.
Complementary slackness and testing for optimality. Dual simplex method. Duality in a wider context: graphical description of Lagrange multipliers
in a constrained optimization; the dual variables as Lagrange multipliers.
Sensitivity analysis: Examples
of different types.
Transportation problem: Loops
and basic feasible solutions; setting out the algorithm; formulation of problems
as transportation problems.
Assignment problems: Why
the transportation method is inefficient.
Hungarian algorithm, proof of convergence.
Integer programming: Formulation
of problems using binary variables; capital budget problems, fixed charge problems. Solution methods: branch and bound, Gomory’s method.
Elementary
Linear Programming with Applications – B Kolman and R
E Beck (Academic Press). Library
Ref. 519.41 KOL