Transcription of Linear Programming: Chapter 2 The Simplex Method
1 Linear Programming: Chapter 2 The Simplex MethodRobert J. VanderbeiOctober 17, 2007 Operations Research and Financial EngineeringPrinceton UniversityPrinceton, NJ 08544 rvdbSimplex MethodAn x1+ 3x2 3x3subject to3x1 x2 2x3 7 2x1 4x2+ 4x3 3x1 2x3 4 2x1+ 2x2+x3 83x1 5x1, x2, x3 with slack variablesmaximize = x1+ 3x2 3x3subject tow1= 7 3x1+x2+ 2x3w2= 3 + 2x1+ 4x2 4x3w3= 4 x1+ 2x3w4= 8 + 2x1 2x2 x3w5= 5 3x1x1, x2, x3, w1, w2, w3, w4, w5 : Thislayoutis called adictionary. Settingx1,x2, andx3to0, we can read off the values for the other variables:w1= 7,w2= 3, etc. Thisspecific solution is called adictionary solution. Dependent variables, on the left, are calledbasic variables. Independent variables, on the right, are callednonbasic Solution is Feasiblemaximize = x1+ 3x2 3x3subject tow1= 7 3x1+x2+ 2x3w2= 3 + 2x1+ 4x2 4x3w3= 4 x1+ 2x3w4= 8 + 2x1 2x2 x3w5= 5 3x1x1, x2, x3, w1, w2, w3w4w5 : All the variables in the current dictionary solution are nonnegative.
2 Such a solution is calledfeasible. The initial dictionary solution need not be feasible we were just lucky Method First Iteration Ifx2increases, obj goesup. How much canx2increase? Untilw4decreases to zero. Do it. End result:x2>0whereasw4= 0. That is,x2must becomebasicandw4must becomenonbasic. Algebraically rearrange equations to, in the words of Jean-Luc Picard, Make it so. This is Pivot:x2 w4becomesSimplex Method Second PivotHere s the dictionary after the first pivot: Now, letx1increase. Of the basic variables,w5hits zero first. So,x1entersandw5leavesthe basis. New dictionary Method Final Dictionary It s optimal (no pink)! Click here to practice the Simplex Method . For instructions, click Discussunboundedness;(today) Discuss initialization/infeasibility; , what if initial dictionary is not feasible.
3 (today) Discussdegeneracy.(next lecture)UnboundednessConsider the following dictionary: Could increase eitherx1orx3to increase obj. Consider increasingx1. Which basic variable decreases to zero first? Answer: none of them,x1can grow without bound, and obj along with it. This is how we detectunboundednesswith the Simplex the following problem:maximize 3x1+ 4x2subject to 4x1 2x2 8 2x1 23x1+ 2x2 10 x1+ 3x2 1 3x2 2x1, x2 Problem Modify problem by subtracting a new variable,x0, from each constraint and replacing objective function with x0 Phase-I Problemmaximize x0subject to x0 4x1 2x2 8 x0 2x1 2 x0+ 3x1+ 2x2 10 x0 x1+ 3x2 1 x0 3x2 2x0, x1, x2 0. Clearly feasible: pickx0large,x1= 0andx2= 0. If optimal solution has obj= 0, then original problem is feasible.
4 Final phase-I basis can be used as initialphase-IIbasis (ignoringx0thereafter). If optimal solution has obj<0, then original problem is First PivotApplet depiction shows both the Phase-I and the Phase-II objectives: Dictionary is infeasible even for Phase-I. One pivot needed to get feasible. Entering variable isx0. Leaving variable is one whose current value is most negative, After first Second PivotGoing into second pivot: Feasible! Focus on the yellow highlights. Letx1enter. Thenw5must leave. After second Third PivotGoing into third pivot: x2must enter. x0must leave. After third of Phase-ICurrent dictionary: Optimal for Phase-I (no yellow highlights). obj= 0, therefore original problem is dictionary:For Phase-II: Ignore column withx0in Phase-II.
5 Ignore Phase-I objective Solution Optimal! Click here to practice the Simplex Method on problems that may have infeasiblefirst dictionaries. For instructions, click here.
