Matrix methods, sensitivity and geometry¶
Part 4 of the course, volume 4 of the lecture notes. The revised primal and dual simplex, the primal-dual method, sensitivity analysis, the geometry of linear programming (faces, vertices and basic solutions). Examples worked out step by step and exercises with complete solutions at the end of each chapter.
-
11. Revised simplex algorithm
Pivoting operations with two systems of linear equations · Pseudo-code of the revised simplex algorithm
-
12. Revised dual simplex algorithm
Pivoting operations with two systems of linear equations · Updating the reduced costs · Pseudo-code of the revised dual simplex algorithm · Execution of the revised dual simplex algorithm
-
13. The primal-dual method
The reference pair of primal and dual problems · The restricted primal problem · The dual step · Pseudo-code of the primal-dual method · …
-
14. Sensitivity analysis
Optimal bases and their two conditions · Changes in the objective-function vector · Changes in the right-hand-side vector · Adding a new variable · …
-
15. The geometry of Linear Programming
The dimension of a polyhedron · Faces, facets and vertices · Basic feasible solutions and vertices · The Fundamental Theorem, geometrically · …