The Simplex Algorithm - Carnegie Mellon School of Computer ...

1 The Simplex AlgorithmSlides by Carl Kingsford1 Example Simplex Algorithm RunExample linear program:x1+x2 3 x1+3x2 1+x2 3x1+x2=zThe last line is theobjectivefunction we are trying assume:Iall the constraints are , andIall the values of the variables must be variablesWe re-write into a system of equations by introducing non-negativeslack variables:x1+x2+x3= 3 x1+3x2+x4= 1+x2+x5= 3x1+x2=zThere is an easy solution to this system of equations:x3= 3,x4= 1,x5= 3and all the rest of the variables= 0 This gives us an objective of now proceed with a series of transformations that seek toincrease the to put the non-zero values on the left-hand side:x3= 3 x1 x2x4= 1 +x1 3x2x5= 3 x2z= 0 +x1+x2 This is called atableau: Right-hand side variables are all 0, lefthand side may be right hand side variables are calledbasic variables are candidates for increasing to increasez?

2 Those with positive coefficients in the objective. Pick one: to put the non-zero values on the left-hand side:x3= 3 x1 x2x4= 1 +x1 3x2x5= 3 x2z= 0 +x1+x2 This is called atableau: Right-hand side variables are all 0, lefthand side may be right hand side variables are calledbasic variables are candidates for increasing to increasez?Those with positive coefficients in the objective. Pick one: variablex2is called theenteringvariable (we ll see why in a minute)How much can we increasex2by?So long as none of the basic variables become choose the amount to increase based on the strictest equation:3 x2 0 = x2 3(1)1 3x2 0 = x2 1/3(2)3 x2 0 = x2 3(3)Constraint (2) is the strictest, so we setx2= 1 variablex2is called theenteringvariable (we ll see why in a minute)How much can we increasex2by?

3 So long as none of the basic variables become choose the amount to increase based on the strictest equation:3 x2 0 = x2 3(1)1 3x2 0 = x2 1/3(2)3 x2 0 = x2 3(3)Constraint (2) is the strictest, so we setx2= 1 leaving variableLook at the strictest constraint now:x4= 1 +x1 3x2= x2= 1/3 + (1/3)x1 (1/3)x4If we increasex2= 1/3, thenx4becomes re-write constraint (2) to putx2on the left-hand side, andsubstitute in forx2in all the remaining equations:x3= 8/3 (4/3)x1+(1/3)x4x2= 1/3 +(1/3)x1 (1/3)x4x5= 8/3 (1/3)x1+(1/3)x4z= 1/3 +(4/3)x1 (1/3)x4 This system of equations is equivalent to what we started with, butnow if we set the rhs variables to 0, we get an objective value of1/3.

4 Progress!6 Pivotsx4was which variable can we increase?x1is the only variable with a non-negative coefficient in ourobjective. So, we selectx1as the entering variable, and see howmuch we can increase it:x1 (8/3)/(4/3) = 2(4)x1 (1/3)/( 1/3) = 1(5)x1 (8/3)/(1/3) = 8(6)Notice only those constraints wherex1has a negative coefficientprovide a constraint!Constraint (4) is the strictest. So we increasex1to 2 in the sameway as which variable can we increase?x1is the only variable with a non-negative coefficient in ourobjective. So, we selectx1as the entering variable, and see howmuch we can increase it:x1 (8/3)/(4/3) = 2(4)x1 (1/3)/( 1/3) = 1(5)x1 (8/3)/(1/3) = 8(6)Notice only those constraints wherex1has a negative coefficientprovide a constraint!

5 Constraint (4) is the strictest. So we increasex1to 2 in the sameway as 2 Look at the strictest constraint:x3= 8/3 (4/3)x1+ (1/3)x4= x1= 2 (3/4)x3 (1/4)x4 Rewrite that constraint in terms ofx1, and substitute in forx1everywhere:x1= 2 (3/4)x3+(1/4)x4x2= 1 (1/4)x3 (1/4)x4x5= 2 +(1/4)x3+(1/4)x4z= 3 x3 Now: all the coefficients in the objective function are 0, so we redone. The optimal value is 3 withx1= 2 andx2= that these values satisfy the original constraints!8 NoteINote that increasingx1alsoincreasedx2. This happenedwhen we substituted in forx1in the second Algorithm In General1.

6 Write LP with slack variables (slack vars = initial solution)2. Choose a variablevin the objective with a positive coefficientto increase3. Among the equations in whichvhas a negative coefficientqiv, choose the strictest oneThis is the one that minimizes pi/qivbecause theequations are all of the formxi=pi+ Re-write the strictest equation to putvon the left-hand side,and substitute forveverywhere If all the coefficients are 0 in objective, we re done;otherwise, jump back to step of a pivot+-+-++p1p2p3p4p5z =objxi =xj =Basic variablesvalues of basic variables in current solutionobjective value of current solutioncandidate entering variablecandidate leaving variables11 Special casesIWhat if no constraint provides an upper bound on enteringvariablev?

7 = problem is unbounded, and has an if the strictest upper bound is 0?= there is another feasible~xof equivalent may have to do a pivot that doesn t increase the objective(but doesn t decrease it either) in order to make if there are multiple choices for the enteringvariable?Choose according to some pivot rule:ILargest coefficient in the objective increases the objective asmuch as possible per unit of variable increase pick the one that increases the objective choose one at edge choose the variable to maximize:~cT(~xnew ~xold)||~xnew ~xold||IBland s rule choose the entering variable with the lowest index(and the corresponding leaving variable with the lowest index aswell).

8 [Important theoretically, but not used much in practice.]13 How do we know this process will terminate?In general, this process might not terminate!If you can always increase the objective function (non-zero upperbound on the entering variable), then it must eventually might be that you repeatedly have to choose an entering variablewith a 0 upper s rule ensures that you can t cycle do we know it s optimal?Consider a final objective equation, say (a different objective thanthe example above):z= 24 5x1 3x3 This expression is equivalent to whatever objective we started all the variables have to be 0, we must have the optimalz 24.

9 Since we ve achieved 24, we know it must be made one implicit assumption in the discussion above: thatinitially setting the non-slack variables to 0 would give us a is not the case if thebivalues are<0:x3= 3 x1 x2x4= 1 +x1 3x2x5= 3 x2z= 0+x1+x2 Here, we d get a solution withx4<0, which is not solve anauxiliaryLP problem to find the initial ProblemSuppose we have LP:maximizen j= j=1aijxj bii= 1,..,mxj 0j= 1,..,nIts auxiliary problem is:maximize j=1aijxj x0 bii= 1,..,mxj 0j= 0,..,nwherex0is a new variable we j=1aijxj x0 bii= 1.

10 ,mxj 0j= 0,..,nSettingxj= 0 forj 1 andx0really big will give us a feasible solution to original problem had a solution its auxiliary problem has an optimalsolution of objective = the tableau for this problem as usual (introducing slack variables) butit still won t be Tableau-x0z =w1 =w2 =w3 =w4 =w5 =+1x0+1x0+1x0+1x0+1x0 All +1 coeff. b/c original equations all had -1x0+A-B+C-D+EThe original b vector (which includes some negative entries)The slack variablesSuppose Bis the most negative entry. Rewrite that equation in terms ofx0:x0= +B+ terms involving variablesNow substitute the red part in forx0in every other will addBto every constant term = all the constant terms becomepositive (since Bwas the most negative).