The Simplex Solution Method
The simplex method does not guarantee integer solutions.
An additional comment should be made regarding simplex solutions in general. Although this solution resulted in integer values for the variables (i.e., 24 and 8), it is possi- ble to get a fractional solution for decision variables even though the variables reflect items that should be integers, such as airplanes, television sets, bowls, and mugs. To apply the simplex method, one must accept this limitation.
Summary of the Simplex Method
The simplex method demonstrated in the previous section consists of the following steps:
a n d Transform the model constraint inequalities into equations. Set up the initial tableau for the basic feasible solution at the origin and compute the r o w v a l u e s . c o l u m n w Determine the pivot column (entering nonbasic solution variable) by selecting the i t h t h e h i g h e s t p o s i t i v e v a l u e i n t h e r o w . c j - z j c j - z j Determine the pivot row (leaving basic solution variable) by dividing the quantity column values by the pivot column values and selecting the row with the minimum nonnegative quotient. Compute the new pivot row values using the formula z j
old tableau pivot row values new tableau pivot row values = pivot number
Compute all other row values using the formula
new tableau row values
old tableau row values
corresponding coefficients in * pivot column
corresponding new tableau pivot row values
C o m p u t e t h e n e w a n d r o w s . D e t e r m i n e w h e t h e r t h e n e w s o l u t i o n i s o p t i m a l b y c h e c k i n g t h e r o w . I f a l l r o w v a l u e s a r e z e r o o r n e g a t i v e , t h e s o l u t i o n i s o p t i m a l . I f a p o s i t i v e v a l u e c j - z j c j - z j c j - z j exists, return to step 3 and repeat the simplex steps. z j
Simplex Solution of a Minimization Problem
In the previous section the simplex method for solving linear programming problems was demonstrated for a maximization problem. In general, the steps of the simplex method outlined at the end of this section are used for any type of linear programming problem. However, a minimization problem requires a few changes in the normal simplex process, which we will discuss in this section.
In addition, several exceptions to the typical linear programming problem will be presented later in this module. These include problems with mixed constraints (=, … , and Ú ); problems with more than one optimal solution, no feasible solution, or an unbounded solution; problems with a tie for the pivot column; problems with a tie for the pivot row; and problems with constraints with negative quantity values. None of these kinds of problems require changes in the simplex method. They are basically unusual results in individual simplex tableaus that the reader should know how to interpret and work with.