Transcription of Some Simplex Method Examples
1 Name:February 27, 2008 Some Simplex Method ExamplesExample 1: (from class) Maximize:P= 3x+ 4ysubject to: x+y 42x+y 5x 0,y 0 Our first step is to classify the problem. Clearly, we are going to maximize our objec-tive function, all are variables are nonnegative, and our constraints are written withour variable combinations less than or equal to a constant. So this is astandard max-imization problemand we know how to use the Simplex Method to solve need to write our initial Simplex tableau. Since we have two constraints, we needto introduce the two slack variablesuandv. This gives us the equalitiesx+y+u= 42x+y= 5We rewrite our objective function as 3x 4y+P= 0 and from here obtain the systemof equations: x+y+u= 42x+y= 5 3x 4y+P= 0 This gives us our initial Simplex tableau:x y u v P1 1 1 0 042 1 0 1 05-3 -4 0 0 10To find the column, locate the most negative entry to the left of the vertical line (herethis is 4).
2 To find the pivot row, divide each entry in the constant column by theentry in the corresponding in the pivot column. In this case, we ll get41as the ratiofor the first row and51for the ratio in the second row. The pivot row is the rowcorresponding to the smallest ratio, in this case 4. So our pivot element is the in thesecond column, first row, hence is we perform the following row operations to get convert the pivot column to a unitcolumn:R2 R2 R1R3 R3+ 4R1 Our Simplex tableau has transformed into:x y u v P1 1 1 0 041 0 -1 1 011 0 4 0 116 Notice that all of the entries to the left of the vertical line in the last row are non-negative.
3 We must stop here!To read off the solution from the table, first find the unit columns in the table. Thevariables above the unit columns are assigned the value in the constant column in therow where the 1 is in the unit column. Every variable above a non-unit column is setto 0. So herey= 4,v= 1,P= 16,x= 0, andu= , our maximum occurs whenx= 0,y= 4 and the maximum value is 2 (from class) Minimize:C= 2x+ysubject to: x+ 2y 63x+ 2y 12x 0,y 0 Classify the problem. Clearly, this is a minimization it s not the standardproblem since our constraints involve linear expressions with the variables less than orequal to a constant.
4 We use the trick that minimizing this functionCis the same asmaximizing the functionP= C. This problem is then equivalent to:MaximizeP= 2x ysubject to: x+ 2y 63x+ 2y 12x 0,y 0 Introducing the slack variableuandv, our initial Simplex tableau is:x y u v P1 2 1 0 063 2 0 1 012-2 1 0 0 10 Our pivot element is the 3 in row 2 column 1. We do the following sequence of rowoperations to convert this column into a unit column:R2 13R1R1 R1 R2R3 R3+ 2R2We have the tableau:x y u v P0 4 /3 1 -1 /3 021 2 /3 0 1 /3 040 5 /3 0 1 /3 18 Since the last row has all positive entries to the left of the vertical line, we are maximum ofPoccurs atx= 4,y= 0 and the maximum value ofPis 8.
5 SinceP= Cour minimum forCis 8 is the minimum forCandCis minimized at (4,0).Example 3 (from class) MinimizeC= 2x+ 5ysubject to x+ 2y 43x+ 2y 3x 0,y 0 This problem is a standard minimization problem. We call this problem theprimalproblem. To solve it, we first write the tableaux y1 243 232 5 Now take this tableau and interchange its columns and rows, labeling the first twocolumnsu,v:u v1 322 254 3 From here we get the tableau of thedual problemby negating the last row of this tableand then inserting unit columns andx,y, andPbetween thevthe constant column:u v x y P1 3 1 0 022 2 0 1 05-4 -3 0 0 10 Now we use the Simplex algorithm to get a solution to the dual problem.
6 The pivotelement is the 1 in the first column, first row. We do the following sequence of rowoperations to reduce this column to a unit column:R2 R2 2R1R3 R3+ 4R1and arrive at the final tableau:u v x y P1 3 1 0 020 -4 -2 1 010 9 4 0 18 The solution for the primal problem appears underneath the slack variables (in thiscasexandy) in the last row of of the final tableau. The maximum of the dual problemis the same as the minimum for the primal problem so the minimum forCis 8 andthis value occurs atx= 4,y= 0. Note that the dual problem has a maximum atu= 2andv= 4: Suppose when I solve a Simplex problem I find that my slack variableutakes on apositive value.
7 Did I do something wrong? Basically, when one of the slack variables takes on a positive valueit means that in maximizing our objective function we stayed below one of ourconstraints. For example, ifuis the slack variable corresponding to a constraint onlabor hours used and the value ofuis 12 in our optimal solution, it means we have 12remaining labor hours 5: What do I conclude if the last row to the left of the vertical line in my Simplex tableaucontains all zeros? are infinitely many solutions to the optimization problem.
