Some Simplex Method Examples

Example 1: (from class) Maximize:P= 3x+ 4ysubject to: x≥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 with our 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 it. We need to write our initial simplex tableau. Since we have two constraints, we need to introduce the two slack variablesuandv. This gives us the equalities x+y+u= 4

2x+y= 5

We rewrite our objective function as-3x-4y+P= 0 and from here obtain the system of equations: ?x+y+u= 4

2x+y= 5

-3x-4y+P= 0

This gives us our initial simplex tableau:

x y u v P1 1 1 0 04

2 1 0 1 05

-3 -4 0 0 10 To find the column, locate the most negative entry to the left of the vertical line (here this is-4). To find the pivot row, divide each entry in the constant column by the entry in the corresponding in the pivot column. In this case, we"ll get 41
as the ratio for the first row and 51
for the ratio in the second row. The pivot row is the row corresponding to the smallest ratio, in this case 4. So our pivot element is the in the second column, first row, hence is 1. Now we perform the following row operations to get convert the pivot column to a unit column: R

2→R2-R1

3→R3+ 4R1

Our simplex tableau has transformed into:

x y u v P1 1 1 0 04

1 0 -1 1 01

1 0 4 0 116

Notice that all of the entries to the left of the vertical line in the last row are non- negative. We must stop here! To read off the solution from the table, first find the unit columns in the table. The variables above the unit columns are assigned the value in the constant column in the row where the 1 is in the unit column. Every variable above a non-unit column is set to 0. So herey= 4,v= 1,P= 16,x= 0, andu= 0. Thus, our maximum occurs whenx= 0,y= 4 and the maximum value is 16. Example 2 (from class) Minimize:C=-2x+ysubject to: x≥0,y≥0 Classify the problem. Clearly, this is a minimization problem...but it"s not the standard problem since our constraints involve linear expressions with the variables less than or equal to a constant. We use the trick that minimizing this functionCis the same as maximizing the functionP=-C. This problem is then equivalent to:

MaximizeP= 2x-ysubject to:??

x≥0,y≥0 Introducing the slack variableuandv, our initial simplex tableau is: x y u v P1 2 1 0 06

3 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 row operations to convert this column into a unit column: R

2→13

R1 R

1→R1-R2

3→R3+ 2R2

We have the tableau:

x y u v P0 4 /3 1 -1 /3 02

1 2 /3 0 1 /3 04

0 5 /3 0 1 /3 18

Since the last row has all positive entries to the left of the vertical line, we are done. Our maximum ofPoccurs atx= 4,y= 0 and the maximum value ofPis 8. Since

P=-Cour minimum forCis-8.

ThusC=-8 is the minimum forCandCis minimized at (4,0). Example 3 (from class) MinimizeC= 2x+ 5ysubject to ?x+ 2y≥4

3x+ 2y≥3

x≥0,y≥0 This problem is a standard minimization problem. We call this problem theprimal problem. To solve it, we first write the tableau x y1 24 3 23 2 5 Now take this tableau and interchange its columns and rows, labeling the first two columnsu,v: u v1 32 2 25 4 3 From here we get the tableau of thedual problemby negating the last row of this table and then inserting unit columns andx,y, andPbetween thevthe constant column: u v x y P

1 3 1 0 02

2 2 0 1 05

-4 -3 0 0 10 Now we use the simplex algorithm to get a solution to the dual problem. The pivot element is the 1 in the first column, first row. We do the following sequence of row operations to reduce this column to a unit column: R

2→R2-2R1

3→R3+ 4R1

and arrive at the final tableau: u v x y P1 3 1 0 02

0 -4 -2 1 01

0 9 4 0 18

The solution for the primal problem appears underneath the slack variables (in this casexandy) in the last row of of the final tableau. The maximum of the dual problem is the same as the minimum for the primal problem so the minimum forCis 8 and this value occurs atx= 4,y= 0. Note that the dual problem has a maximum atu= 2 andv= 0. Example 4: Suppose when I solve a simplex problem I find that my slack variableutakes on a positive value. Did I do something wrong? Explain. Answer.No. Basically, when one of the slack variables takes on a positive value it means that in maximizing our objective function we stayed "below" one of our constraints. For example, ifuis the slack variable corresponding to a constraint on labor hours used and the value ofuis 12 in our optimal solution, it means we have 12 remaining labor hours available. Example 5: What do I conclude if the last row to the left of the vertical line in my simplex tableau contains all zeros? Answer.There are infinitely many solutions to the optimization problem.quotesdbs_dbs12.pdfusesText_18

[PDF] Some Simplex Method Examples

94 THE SIMPLEX METHOD: MINIMIZATION