X hits on this document





2 / 63


Module A

The Simplex Solution Method

he simplex method is a general mathematical solution technique for solving linear pro- gramming problems. In the simplex method, the model is put into the form of a table, and then a number of mathematical steps are performed on the table. These mathematical steps in effect replicate the process in graphical analysis of moving from one extreme point on the solution boundary to another. However, unlike the graphical method, in which we could simply search through all the solution points to find the best one, the sim- plex method moves from one better solution to another until the best one is found, and then it stops. T

The manual solution of a linear programming model using the simplex method can be a lengthy and tedious process.Years ago, manual application of the simplex method was the only means for solving a linear programming problem. Now computer solution is certainly preferred. However, knowledge of the simplex method can greatly enhance one’s understanding of linear programming. Computer software programs like QM for Windows or Excel spreadsheets provide solutions to linear programming problems, but they do not convey an in-depth understanding of how those solutions are derived. To a certain extent, graphical analysis provides an understanding of the solution process, and knowledge of the simplex method further expands on that understanding. In fact, computer solutions are usually derived using the simplex method. As a result, much of the terminology and notation used in computer software comes from the simplex method. Thus, for those students of management science who desire a more in-depth knowledge of linear programming, it is beneficial to study the simplex solution method as provided here.

Converting the Model into Standard Form

The first step in solving a linear programming model manually with the simplex method is to convert the model into standard form. At the Beaver Creek Pottery Company Native American artisans produce bowls (x1) and mugs (x2) from labor and clay. The linear pro- gramming model is formulated as

maximize Z = $40x1 + 50x2 (profit)

subject to

( l a b o r , h r . ) ( c l a y , l b . ) x 1 , x 2 Ú 0 4 x 1 + 3 x 2 1 2 0 x 1 + 2 x 2 4 0

We convert this model into standard form by adding slack variables to each constraint as follows:

maximize Z = 40x1 + 50x2 + 0s1 + 0s


subject to

x 1 , x 2 , s 1 , s 2 Ú 0 4 x 1 + 3 x 2 + s 2 = 1 2 0 x 1 + 2 x 2 + s 1 = 4 0

Document info
Document views288
Page views288
Page last viewedThu Oct 27 01:30:21 UTC 2016