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.

2 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. 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.

3 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.

4 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.

5 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. For example, 23X2 and 4X16 arevalid decision variable terms, while 23X22, 4X163, and (4X1 * 2X1)are not.

6 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.

7 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. 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.

8 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.

9 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.

10 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. 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.