Syllabus
|
Course Code: MMATH21-415 Course Name: Elective VI) Linear Programming |
||
| MODULE NO / UNIT | COURSE SYLLABUS CONTENTS OF MODULE | NOTES |
|---|---|---|
| 1 | Simultaneous linear equations, Basic solutions, Linear transformations, Point sets, Lines and hyperplanes, Convex sets, Convex sets and hyperplanes, Convex cones, Restatement of the LP problem, Slack and surplus variables, Preliminary remarks on the theory of the simplex method, Reduction of any feasible solution to a basic feasible solution, Definitions and notations regarding LP problems. Improving a basic feasible solution, Unbounded solutions, Optimality conditions, Alternative optima, Extreme points and basic feasible solutions. The simplex method, Selection of the vector to enter the basis, Degeneracy and breaking ties, Further development of the transformation formulas, The initial basic feasible solution, artificial variables, Inconsistency and redundancy, Tableau format for simplex computations, Use of the tableau format, Conversion of a minimization problem to a maximization problem, Review of the simplex method. |
|
| 2 | The two-phase method for artificial variables, Phase I, Phase II, Numerical examples of the two-phase method, Requirements space, Solutions space, Determination of all optimal solutions, Unrestricted variables, Charnes’ perturbation method regarding the resolution of the degeneracy problem. Selection of the vector to be removed, Definition of b(€). Order of vectors in b(€), Use of perturbation technique with simplex tableau format, Geometrical interpretation of the perturbation method. The generalized linear programming problem, The generalized simplex method, Examples pertaining to degeneracy, An example of cycling. (Chapter 5, 6 of recommended book) |
|
| 3 | Revised simplex method: Standard Form I, Computational procedure for Standard Form I, Revised simplex method: Standard Form II, Computational procedure for Standard Form II, Initial identity matrix for Phase I, Comparison of the simplex and revised simplex methods, The product form of the inverse of a non-singular matrix. (Chapter 7 of recommended book) |
|
| 4 | Alternative formulations of linear programming problems, Dual linear programming problems, Fundamental properties of dual problems, Other formulations of dual problems, Complementary slackness, Unbounded solution in the primal, Dual simplex algorithm, Alternative derivation of the dual simplex algorithm, Initial solution for dual simplex algorithm, The dual simplex algorithm; an example, geometric interpretations of the dual linear programming problem and the dual simplex algorithm. A primal dual algorithm, Examples of the primal-dual algorithm. Transportation problem, properties of matrix A, the simplex method and transportation problem, simplification resulting from all the transportation problem tableau, bases in the transportation tableau, the stepping stone algorithm, an example. ( Chapter 8 & 9.1 to 9.8 of recommended book) |
|
