Simplex MethodSimplex MethodMath 364: Principles of Optimization, Lecture 7Haijun [email protected] of MathematicsWashington State UniversitySpring 2012Haijun Li Math 364: Principles of Optimization, Lecture 7 Spring 2012 1 / 20Simplex MethodStandard FormFigure:Haijun Li Math 364: Principles of Optimization, Lecture 7 Spring 2012 2 / 20Simplex MethodFigure: Two consecutive shifts and constraintsHaijun Li Math 364: Principles of Optimization, Lecture 7 Spring 2012 3 / 20Simplex MethodLP in Standard Form:Adding Slack/Excess Var iablesFigure:Haijun Li Math 364: Principles of Optimization, Lecture 7 Spring 2012 4 / 20Simplex MethodFarmer Jones LP: Standard FormFigure: Graphical SolutionHaijun Li Math 364: Principles of Optimization, Lecture 7 Spring 2012 5 / 20Simplex MethodSlack/Excess Variables ⇒ “Almost Identity” MatrixFigure: Graphical SolutionHaijun Li Math 364: Principles of Optimization, Lecture 7 Spring 2012 6 / 20Simplex MethodFigure: Graphical SolutionHaijun Li Math 364: Principles of Optimization, Lecture 7 Spring 2012 7 / 20Simplex MethodParametric Solution with Slack/Excess VariablesFigure:Haijun Li Math 364: Principles of Optimization, Lecture 7 Spring 2012 8 / 20Simplex MethodFigure:Haijun Li Math 364: Principles of Optimization, Lecture 7 Spring 2012 9 / 20Simplex MethodExample of Finding Basic SolutionsFigure:Haijun Li Math 364: Principles of Optimization, Lecture 7 Spring 2012 10 / 20Simplex MethodPay Attention to Non-negativity ConstraintsFigure:Haijun Li Math 364: Principles of Optimization, Lecture 7 Spring 2012 11 / 20Simplex MethodFigure:Haijun Li Math 364: Principles of Optimization, Lecture 7 Spring 2012 12 / 20Simplex Methodbfs ⇔ corner point of convex feasible regionFigure:Haijun Li Math 364: Principles of Optimization, Lecture 7 Spring 2012 13 / 20Simplex MethodFigure:Haijun Li Math 364: Principles of Optimization, Lecture 7 Spring 2012 14 / 20Simplex MethodFigure: Graphical SolutionHaijun Li Math 364: Principles of Optimization, Lecture 7 Spring 2012 15 / 20Simplex MethodFigure:Haijun Li Math 364: Principles of Optimization, Lecture 7 Spring 2012 16 / 20Simplex MethodFigure:Haijun Li Math 364: Principles of Optimization, Lecture 7 Spring 2012 17 / 20Simplex MethodFigure:Haijun Li Math 364: Principles of Optimization, Lecture 7 Spring 2012 18 / 20Simplex MethodFigure:Haijun Li Math 364: Principles of Optimization, Lecture 7 Spring 2012 19 / 20Simplex MethodFigure:Haijun Li Math 364: Principles of Optimization, Lecture 7 Spring 2012 20 /