Linear Programming: Chapter 2 The Simplex Method

← Back to document page

Linear Programming: Chapter 2The Simplex MethodRobert J. VanderbeiOctober 17, 2007Operations 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.

Simplex Method|First Iteration If x 2 increases, obj goes up. How much can x 2 increase? Until w 4 decreases to zero. Do it. End result: x 2 >0 whereas w 4 = 0. That is, x 2 must become basic and w 4 must become nonbasic. Algebraically rearrange equations to, in the words of Jean-Luc Picard, "Make it so." This is a pivot.

  Methods, Simplex method, Simplex