CS 472-3
Linear Programming
Catalog Description
(Same as Mathematics 472.) Nature and purpose of the linear programming model. Development of the simplex method. Application of the model to various problems. Duality theory. Transportation. Assignment problem. Postoptimality analysis.
Prerequisite:
Mathematics 221.
Objectives
To introduce the students to the theory and application of linear programming.
Course Outline
| Lectures | ||
| 1. | Background
Definition and description of the model. Objective function, constraints, feasibility restrictions. Solution, feasible solution, optimal feasible solution. Examples and applications. Graphical examples and solutions. Topology of the constraint set. Convexity, inequalities, intersections of inequalities, extreme points, convex combination. Simultaneous linear equations. Statement of the problem, Gaussian reduction, Cramer's rule, rank, linear independence, spanning set, basic solutions, basic variables, degeneracy. |
6 |
| 2. | The Simplex Method
Revised form of a linear programming problem. Slack and surplus variables, matrix form, activity vectors, requirements vector, cost vector, rank. Examples. Reduction of a feasible solution to a basic feasible solution. Linear dependence, eliminating a dependent vector, requirements of feasibility, examples. Vector notation. A,b, aj, B, yj, XB, CB, z, zj, examples. Improving a basic feasible solution. Graphical display. Computational development, choosing a vector to leave and maintaining feasibility, choosing a vector to enter and improving the objective function, transformation formulas. Examples. Optimality conditions and proof of optimality. Special problems. Unbounded solutions, alternative optima, degeneracy, minimization instead of maximization. Initial basic feasible solution. Special cases, artificial vectors and variables, Charnes' - M method, conditions at optimality. The Simplex Tableau. Form, conversions, termination, examples. Two-Phase Method. Cost vector for each phase, conditions at optimality for phase 1, precautions during phase 2 under certain phase 1 conditions. Examples. Unrestricted variables. Substitution, costs, activity vectors. Examples. |
10 |
| 3. | Duality Theory
General. Form of primal and dual, example, economic interpretation, alternate forms. Fundamental properties. Dual of the dual, relation of objective functions, equality of objective functions, existence of optimal solutions, unbounded solutions. Complementary slackness. Statement of conditions, proof, alternate forms. |
8 |
| 4. | Revised Simplex and Sensitivity
Postoptimality problems, changing the price vector, changing the requirements vector, adding variables, adding constraints, parametric programming. |
9 |
| 5. | Transportation Problems
Statement of the problem. Origins and destinations, shipping costs, objective function, form of the LP problem, examples. The LP problem. Matrix form, vector notation, properties of the matrix, inappropriateness of the simplex method. The Stepping-Stone Algorithm. Initial basic feasible solution, north west corner rule. Tableau format, computation of zij - cij. Improving a basic feasible solution, vector to enter, vector to leave, transformation of tableau, optimality. Degeneracy. Inequalities in the constraints. |
7 |
| Total | 40 | |