Operations Research: Using the Simplex Method to solve ...

1 James E. Reeb, Extension forest products manufac-turing specialist; and Scott Leavengood, Extensionagent, Klamath County; Oregon State the Simplex Method to solve LinearProgramming maximization ProblemsJ. Reeb and S. Leavengood EM 8720-EOctober 1998$ key problem faced by managers is how to allocate scarce resourcesamong activities or projects. linear programming , or LP, is a Method ofallocating resources in an optimal way. It is one of the most widely usedoperations research (OR) tools. It has been used successfully as a decision-making aid in almost all industries, and in financial and service refers to mathematical programming . In this context, itrefers to a planning process that allocates resources labor, materials,machines, and capital in the best possible (optimal) way so that costs areminimized or profits are maximized. In LP, these resources are known asdecision variables. The crite-rion for selecting the bestvalues of the decision vari-ables ( , to maximize profitsor minimize costs) is known asthe objective function.

2 Thelimitations on resource avail-ability form what is known asa constraint example, let s say afurniture manufacturer pro-duces wooden tables andchairs. Unit profit for tables is$6, and unit profit for chairs is$8. To simplify our discussion,let s assume the only tworesources the company uses toproduce tables and chairs are wood (board feet) and labor (hours). It takes30 bf and 5 hours to make a table, and 20 bf and 10 hours to make a EXCELLENCEIN THE WOOD PRODUCTS INDUSTRYA bout this seriesAccording to the Operations Research Society ofAmerica, Operations research [OR] is concerned withscientifically deciding how to best design and operateman-machine systems, usually under conditionsrequiring the allocation of scarce resources. This publication, part of a series, should be usefulfor supervisors, lead people, middle managers, andanyone who has planning responsibility for either asingle manufacturing facility or for corporate planningover multiple facilities.

3 Although managers andplanners in other industries can learn about ORtechniques through this series, practical examples aregeared toward the wood products RESEARCHD ecision variables.. The resourcesavailable. Constraint set.. The limitations onresource availability. Objective function.. The criterion forselecting the bestvalues of the decisionvariables. There are 300 bf of wood available and 110 hours of labor avail-able. The company wishes to maximize profit, so profit maximiza-tion becomes the objective function. The resources (wood andlabor) are the decision variables. The limitations on resourceavailability (300 bf of wood and 110 hours of labor) form theconstraint set, or operating rules that govern the process. Using LP,management can decide how to allocate the limited resources tomaximize linear part of the name refers to the following: The objective function ( , maximization or minimization) canbe described by a linear function of the decision variables, thatis, a mathematical function involving only the first powers of thevariables with no cross products.

4 For example, 23X2 and 4X16 arevalid decision variable terms, while 23X22, 4X163, and (4X1 * 2X1)are not. The entire problem can be expressed as straight lines,planes, or similar geometrical figures. The constraint set can be expressed as a set of linear addition to the linear requirements, nonnegativity conditionsstate that the variables cannot assume negative values. It is notpossible to have negative resources. Without these conditions, itwould be mathematically possible to use more resources than EM 8719, Using the Graphical Method to solve LinearPrograms, we use the graphical Method to solve an LP probleminvolving resource allocation and profit maximization for a furni-ture manufacturer. In that example, there were only two variables(wood and labor), which made it possible to solve the with three variables also can be graphed, but three-dimensional graphs quickly become cumbersome. Problems withmore than three variables cannot be graphed.

5 Most real-worldproblems contain numerous objective criteria and resources, sothey re too complicated to represent with only two or three vari-ables. Thus, for all practical purposes, the graphical Method forsolving LP problems is used only to help students better under-stand how other LP solution procedures publication will build on the example of the furniturecompany by introducing a way to solve a more complex LP prob-lem. The Method we will use is the Simplex METHODO verview of the Simplex methodThe Simplex Method is the most common way to solve large LPproblems. Simplex is a mathematical term. In one dimension, asimplex is a line segment connecting two points. In two dimen-sions, a Simplex is a triangle formed by joining the points. A three-dimensional Simplex is a four-sided pyramid having four underlying concepts are geometrical, but the solution algo-rithm, developed by George Dantzig in 1947, is an with the graphical Method , the Simplex Method finds themost attractive corner of the feasible region to solve the LP prob-lem.

6 Remember, any LP problem having a solution must have anoptimal solution that corresponds to a corner, although there maybe multiple or alternative optimal usually starts at the corner that represents doing noth-ing. It moves to the neighboring corner that best improves thesolution. It does this over and over again, making the greatestpossible improvement each time. When no more improvementscan be made, the most attractive corner corresponding to theoptimal solution has been moderately sized LP with 10 products and 10 resource con-straints would involve nearly 200,000 corners. An LP problem10 times this size would have more than a trillion corners. Fortu-nately, the search procedure for the Simplex Method is efficientenough that only about 20 of the 200,000 corners are searched tofind the optimal the real world, computer software is used to solve LP prob-lems Using the Simplex Method , but you will better understand theresults if you understand how the Simplex Method works.

7 Theexample in this publication will help you do of the graphical methodFirst, let s quickly review the graphical procedure for solving anLP problem, which is presented in EM 8719, Using the GraphicalMethod to solve linear Programs. Let s say a furniture manufac-turer wishes to maximize profit. Information about availableresources (board feet of wood and hours of labor) and the objec-tive criterion is presented in Table 1. For a complete, step-by-stepreview of the graphical Method , see EM 8719 or one of the text-books listed in the For more information RESEARCHTip ..In our example,X1 refers to tables,X2 refers to chairs, andZ refers to 1. Information for the wooden tables and chairs linear (X1)Chair (X2)AvailableWood (bf)3020300 Labor (hr)510110 Unit profit$6$8 Maximize: Z = 6X1 + 8X2(objective function)Subject to: 30X1 + 20X2 < 300 (wood constraint: 300 bf available)5X1 + 10X2 < 110 (labor constraint: 110 hours available)X1, X2 > 0(nonnegativity conditions)Based on the above information, graphically solve the LP(Figure 1).

8 Graph the two constraint equation lines. Then plot twoobjective function lines by arbitrarily setting Z = 48 and Z = 72 tofind the direction to move to determine the most attractive coordinates for the most attractive corner (where the wood andlabor constraint equations intersect) can be found by simulta-neously solving the constraint equations with two 1. Determining the most attractive corner corresponding to the METHODTo simultaneously solve the two constraint equations, firstmultiply the labor equation by -2, and add it to the wood equation: 30X1 + 20X2= 300 (wood)-2(5X1 + 10X2= 110) (labor) 20X1 + 0 = 80 X1= 4 tablesNext, substitute into either of the constraint equations to find thenumber of chairs. We can substitute into both equations to illustratethat the same value is constraintLabor constraint30(4) + 20X2= 3005(4) + 10X2= 110120 + 20X2= 30020 + 10X2= 11020X2= 300 - 12010X2= 110 - 2020X2= 18010X2= 90 X2= 180/20 X2= 90/10 X2= 9 chairs X2= 9 chairsNow, determine the value of the objective function for theoptimal solution.

9 Substitute into the equation the number of tablesand chairs, and solve for = $6(4) + $8(9) = $96 The optimal solution is to manufacture four tables and ninechairs for a profit of $ RESEARCHU sing the Simplex methodBy introducing the idea of slack variables (unused resources) tothe tables and chairs problem, we can add two more variables tothe problem. With four variables, we can t solve the LP problemgraphically. We ll need to use the Simplex Method to solve thismore complex ll briefly present the steps involved in Using the simplexmethod before working through an example. Table 2 shows anexample of a Simplex tableau. Although these steps will give you ageneral overview of the procedure, you ll probably find that theybecome much more understandable as you work through list of shortcuts is found on page 23. You can refer to the sixsteps and shortcuts while working through the 1. Formulate the LP and construct a Simplex tableau.

10 Addslack variables to represent unused resources, thus eliminatinginequality constraints. Construct the Simplex tableau a table thatallows you to evaluate various combinations of resources todetermine which mix will most improve your solution. Use theslack variables in the starting basic variable 2. Find the sacrifice and improvement rows. Values in thesacrifice row indicate what will be lost in per-unit profit by makinga change in the resource allocation mix. Values in the improvementrow indicate what will be gained in per-unit profit by making 2. Example of a Simplex 00 Basic mixX1X2 SWSLS olution0SW3020103000SL510 0 1 110 Sacrifice00000 Current profitImprovement6800 7 Simplex METHODStep 3. Apply the entry criteria. Find the entering variable andmark the top of its column with an arrow pointing down. Theentering variable is defined as the current non-basic variable thatwill most improve the objective if its value is increased from 0.