The Geometry of Linear ProgramsData for the GTC ProblemFormulating the GTC ProblemReformulationFinding an optimal solutionGraphing the Feasible RegionSlide 7Slide 8Slide 9Slide 10How do we find an optimal solution?Slide 12PowerPoint PresentationSlide 14Slide 15Optimal Solution StructureSlide 17Finding an optimal solution in two dimensions: SummaryPreview of the Simplex AlgorithmPreview of the Simplex MethodPreview of Sensitivity AnalysisSlide 22Shifting a ConstraintSlide 24Finding the New Optimum SolutionSome Questions on Shadow PricesBounds on RHS coefficients in Sensitivity AnalysisSlide 28Changing the RHS coefficientSlide 30Slide 31Summary for changes in RHS coefficientsBounds on Cost coefficients in Sensitivity AnalysisShifting a Cost CoefficientDetermining Bounds on Cost CoefficientsSlide 36Summary: 2D Geometry helps guide the intuitionMIT and James Orlin © 20031The Geometry of Linear Programs–the geometry of LPs illustrated on GTCMIT and James Orlin © 20032Data for the GTC Problem Want to determine the number of wrenches and pliers to produce given the available raw materials, machine hours and demand. Wrenches Pliers Available Steel 1.5 1.0 15,000 pounds Molding Machine 1.0 1.0 12,000 hrs Assembly Machine .4 .5 5,000 hrs Demand Limit 8,000 10,000 Contribution ($ per unit) $.40 $.30MIT and James Orlin © 20033Formulating the GTC ProblemP = number of pliers manufactured W = number of wrenches manufacturedMaximize Profit = Steel:Molding:Assembly:Pliers Demand:Wrench Demand: P,W  0Non-negativity:1.5 W + P  15,000 W + P  12,0000.4 W + 0.5 P  5,000 P  10,000 W  8,000.4 W + .3 PMIT and James Orlin © 20034ReformulationP = number of 1000s of pliers manufactured W = number of 1000s of wrenches manufacturedMaximize Profit = Steel:Molding:Assembly:Pliers Demand:Wrench Demand: P,W  0Non-negativity:1.5 W + P  15 W + P  120.4 W + 0.5 P  5 P  10 W  8400 W + 300 PMIT and James Orlin © 20035Finding an optimal solutionIntroduce yourself to your partnerTry to find an optimal solution to the linear program, without looking ahead.Graphing the Feasible Region2WP4 6 8 10 12 142468101214We will construct and shade the feasible region one or two constraints at a time. 6Graphing the Feasible RegionWP2 4 6 8 10 12 142468101214Graph the Constraint:1.5 W + P  157Graphing the Feasible RegionWP2 4 6 8 10 12 1424681012148Graph the Constraint: W + P  12Graphing the Feasible RegionWP2 4 6 8 10 12 1424681012149Graph the Constraint:0.4 W + 0.5 P  5What happened to the constraint :W + P  12?Graphing the Feasible RegionWP2 4 6 8 10 12 14246810121410Graph the Constraints:W  8 P  10How do we find an optimal solution?WP2 4 6 8 10 12 142468101214Maximize z = 400W + 300PIt is the largest value of q such that 400W + 300P = q has a feasible solution 11How do we find an optimal solution?WP2 4 6 8 10 12 142468101214Maximize z = 400W + 300PIs there a feasible solution with z = 400W + 300P = 1200? 12z=1200WP2 4 6 8 10 12 142468101214How do we find an optimal solution?Maximize z = 400W + 300PIs there a feasible solution with z = 2400? Is there a feasible solution with z = 3600? 13z =2400z=3600WP2 4 6 8 10 12 142468101214Can you see what the optimal solution will be? z = 2400z = 3600How do we find an optimal solution?Maximize z = 400W + 300P14WP2 4 6 8 10 12 142468101214What characterizes the optimal solution? What is the optimal solution vector? W = ? P = ? What is its solution value? z = ? How do we find an optimal solution?Maximize z = 400W + 300P15Optimal Solution StructureWP2 4 6 8 10 12 142468101214Maximize z = 400W + 300P1.5 W + P  15.4W + .5P  5plus other constraintsA constraint is said to be binding if it holds with equality at the optimum solution.Other constraints are non-bindingBinding constraints16How do we find an optimal solution?WP2 4 6 8 10 12 142468101214Maximize z = 400W + 300P1.5W + P = 15.4W + .5P = 5 Solution:.7W = 5, W = 50/7P = 15 - 75/7 = 30/7z = 29,000/7 = 4,142 6/7Optimal solutions occur at corner points. In two dimensions, this is the intersection of 2 lines.17MIT and James Orlin © 200318Finding an optimal solution in two dimensions: SummaryThe optimal solution (if one exists) occurs at a “corner point” of the feasible region.In two dimensions with all inequality constraints, a corner point is a solution at which two (or more) constraints are binding.There is always an optimal solution that is a corner point solution (if a feasible solution exists). More than one solution may be optimal in some situationsMIT and James Orlin © 200319Preview of the Simplex AlgorithmIn n dimensions, one cannot evaluate the solution value of every extreme point efficiently. (There are too many.)The simplex method finds the best solution by a neighborhood search technique. Two feasible corner points are said to be “adjacent” if they have one binding constraint in common.Preview of the Simplex MethodWP2 4 6 8 10 12 142468101214Start at any feasible extreme point.Move to an adjacent extreme point with better objective value. Continue until no adjacent extreme point has a better objective value.Maximize z = 400W + 300P20Preview of Sensitivity AnalysisWP2 4 6 8 10 12 142468101214Suppose the pliers demand is decreased to 10 - . What is the impact on the optimal solution value?The shadow price of a constraint is the unit increase in the optimal objective value per unit increase in the RHS of the constraint.21Changing the RHS of a non-binding constraint by a small amount has no impact. The shadow price of the constraint is 0.Preview of Sensitivity AnalysisWP2 4 6 8 10 12 142468101214Suppose slightly more steel is available? 1.5W + P  15 +  What is the impact on the optimal solution value?22Shifting a Constraint6 87345WPSteel is increased to 15 + .What happens to the optimal solution?What happens to the optimal solution value?23Shifting a Constraint6 87345WPSteel is increased to 15 +.What happens to the optimal solution?What happens to the optimal solution value?24MIT and James Orlin © 200325Finding the New Optimum SolutionMaximize z = 400W + 300PBinding Constraints:Solution:Thus the shadow price of steel is 1,600/7 = 228 4/7.Conclusion: If the amount of steel increases by  units (for sufficiently