Linear Programming: Simplex Method - Cabrillo …

1 CHAPTER5 Linear Programming: Simplex The Simplex Tableau; PivotingIn this section we will learn how to prepare a Linear pro-gramming problem in order to solve it by pivoting usinga matrix Method . TheSimplex Methodis matrix basedmethod used for solving Linear programming problems withany number of variables. The Simplex algorithm can beused to solve Linear programming problems that alreadyare, or can be converted to,standard maximum-typeproblems. An example of a standard maximum-type prob-lem isMaximizeP= 4x+ 4ysubject tox+ 3y 302x+y 20x 0;y 0197198 HELENE PAYNE, FINITE MATHEMATICSThe Standard Maximum-Type ProblemA Linear programming problem is astandard maximum-type problemif the following conditions are met: The objective function is Linear and is to bemaxi-mized. The variables are all nonnegative. The structural constraints are all of the formax+by+ c, wherec 176.

2 (i) Determine which of the constraints be-low are not on the form appropriate for a standard maximum-type problem. (ii) If the constraint is not on the appropriateform, rewrite it if possible, to put on that form.(a) 3x 2y 6(b) 6x+ 5y+z 3(c) 7x 4y 5(d)x y 11z 0(e) 5x 7y 2(f) 3x 5z 8(g) 2x The Simplex Tableau; Pivoting199 Exercise ones of the following Linear program-ming problems are standard maximum-type problems? Pleasemotivate your answer.(a)MaximizeP= 4x+ 4ysubject tox+ 3y 302x+y 20x 0;y 0(b)MinimizeC= 5x+ 3ysubject tox+y 66x+y 16x+ 6y 16x 0;y 0200 HELENE PAYNE, FINITE MATHEMATICSThe first step towards using the Simplex algorithm is toconvert the structural constraints into equalities by addingso calledslack variables. The following structural con-straints,x+ 2y 8,x y 4,turn into the following equalities orslack equationswhenslack variables,s1ands2are added to the first and secondconstraint, respectively:x+ 2y+s1= 8,x y+s2= slack variables will always be nonnegative (zero or pos-itive) when solving Linear programming problems.

3 In alinear programming problem with two variables, the slackvariables are always nonnegative in the corner points of thefeasible region. Should a slack variable turn negative, it in-dicates that a mistake has been made in the pivoting. Fora more in depth analysis of how the slack variables relateto the geometry of the feasible region, the reader shouldrefer to section in the textbook. The slack variables aremerely a tool to help us solve Linear programming prob-lems. When stating the solution of the problem, we willnot state the values of the slack variables, only the valuesof the variables given in the The Simplex Tableau; Pivoting201 The next step is to insert the slack equations into anaugmented y s1s2 1 2 1 081 1 0 14 At an stage in the pivoting process, after a pivot operationhas been completed, we can determine the values of all ourvariables (x,y,s1, ands2).

4 Before we begin pivoting, wenotice thatxandyare free variables which we can set toany value. In the Simplex algorithm we call our free vari-ablesnonbasic variablesand we set them equal to other variables, whose column contains exactly one 1and the rest of the elements are zero, are called thebasicvariables. Solving the two equations from the augmentedmatrix,x+ 2y+s1= 8,x y+s2= the basic variables,s1ands2, we obtain,s1= 8 x 2y,s2= 4 x+y,.202 HELENE PAYNE, FINITE MATHEMATICSand since we set the nonbasic variables equal to zero, thevalues of our variables before we begin pivoting are:x= 0y= 0s1= 8s2= Smallest-Quotient RuleFor any given pivot column, Divide each positive number in that column into thecorresponding number in the constants column ofthe matrix. Select as the pivot row, the row corresponding tothe smallestnonnegative quotientobtained.

5 If a zeroquotient is obtained, it is the smallest quotient. Pivot using the pivot element, making it equal to 1and all other elements in that column equal to zero. When pivoting is done, and we set the nonbasic vari-ables to zero, we obtain a solution called abasicfeasible solutionto the Linear programming the smallest quotient rule to choose the pivot ele-ment in a given matrix ensures that the slack variables re-main non-negative. In a Linear programming problem withtwo variables, the basic feasible solution corresponds to acorner point of the feasible The Simplex Tableau; Pivoting203 Exercise the given augmented matrix below, 1 2 1 081 1 0 14 (a) Use the smallest-quotient rule to find the pivot ele-ment in thexcolumn.(b) Perform the pivot operation, making the pivot ele-ment equal to 1, and all other elements in that col-umn equal to zero.

6 (c) Identify the nonbasic and the basic variables. Set thenonbasic variables equal to zero and find the basicfeasible PAYNE, FINITE The Simplex Method : Solving Maximum Prob-lems in Standard FormIn the previous section we learned to identify a standardmaximum-type Linear programming problem, how to addslack variables to the structural constraints, to set up theaugmented matrix, given a pivot column apply the small-est quotient rule to find the pivot element, and once thepivot operation has been completed, find the basic feasiblesolution. But where does the objective function come in?How do we know which column to choose as the pivot col-umn? How do we find the maximum value of the objectivefunction? We are now ready to learn all the steps in theSimplex Algorithm. All those questions will be The Simplex Method : Solving Maximum Problems in Standard Form205 Consider the following standard maximum-type linearprogramming 3x+ 4ysubject tox+ 3y 302x+y 20x 0.

7 Y 0 Step 1 in the Simplex Algorithm - Insert Slack Vari-ablesInsert a slack variable into each of the structural result is this system of slack equations:x+ 3y+s1= 30,2x+y+s2= 2 in the Simplex Algorithm - Rewrite the Ob-jective FunctionRewrite the objective function to match the format of theslack equations, and add the corresponding equation to thebottom of the slack equations:x+ 3y+s1= 30,2x+y+s2= 20, 3x 4y+P= PAYNE, FINITE MATHEMATICSStep 3 in the Simplex Algorithm - Write the InitialSimplex TableauThe augmented matrix is called theinitial Simplex number in the bottom row, to the left of the verticalbar is called y s1s2P 13 1 0 03021 0 1 020 3 4 0 0 10 Step 4 in the Simplex Algorithm - Find the PivotElementThe most negative indicator in the last row of the tableaudetermines the pivot column. We apply the smallest quo-tient rule for that column.

8 Find the pivot element of ourinitial Simplex tableau y s1s2P 13 1 0 03021 0 1 020 3 4 0 0 10 The Simplex Method : Solving Maximum Problems in Standard Form207 Step 5 in the Simplex Algorithm - Perform thePivot OperationPerform the pivot operation on the pivot element. After thepivot operation has been completed write down the basicfeasible y s1s2P 13 1 0 03021 0 1 020 3 4 0 0 10 x=,y=,s1=,s2=P=Step 6 in the Simplex AlgorithmIf a negative indicator is still present, repeat steps 4 and no negative indicators are present, the maximum of theobjective function has been y s1s2P 131130 010530 131 010 530430 140 208 HELENE PAYNE, FINITE MATHEMATICSWe had to repeat steps 4 and 5 since we still did havea negative indicator in the last matrix obtainedafter the last pivoting is listed below.

9 Are there any morenegative indicators? What is the basic feasible solutionafter the last pivoting?x y s1s2P 0 125 15081 0 1535060 0135150 x=,y=,s1=,s2=P=The solution to our Linear programming problem is:Preaches a maximum value of 50 forx= 6 andy= 8. No-tice that we do not even mention the slack variables. Theyare not part of the final solution, but just a tool to help ussolve the The Simplex Method : Solving Maximum Problems in Standard Form209 Insert slack variables and find slack equationsRewrite the objective function and put it below the slack equationsWrite the initial Simplex tableauFind the pivot element by finding the most negative indicator in last row and using the smallest quotient the initial Simplex tableauWrite the initial Simplex tableauPerform the pivot there any more negative indicators in the last row?

10 The maximum has been Simplex Algorithm Flowchart210 HELENE PAYNE, FINITE MATHEMATICSE xercise the Simplex Method to solve the fol-lowing Linear programming problem. After each pivot op-eration, list the basic feasible solution. You final answershould befmaxand thex- andy-values for whichfassumesits maximum 2x+ysubject tox+ 3y 142x+y 11x 0;y The Simplex Method : Solving Maximum Problems in Standard Form211 Exercise the Simplex Method to solve the fol-lowing Linear programming problem. After each pivot op-eration, list the basic feasible solution. You final answershould befmaxand thex-,y-, andz-values for whichfassumes its maximum 2x+y+ 3zsubject tox+ 2y+z 253x+ 2y+ 2z 30x 0;y 0;z 0212 HELENE PAYNE, FINITE MATHEMATICSE xercise the objective function and the con-straints, and then solve the problem by using the confectioner has 600 pounds of chocolate, 100 poundsof nuts, and 50 pounds of fruits in inventory with whichto make three types of candy: Sweet Tooth, Sugar Dandy,and Dandy Delite.