Page 248 -

228 CHAPTER 5 LINEAR PROGRAMMING: THE SIMPLEX METHOD

Interpreting the Optimal Solution
Using the final simplex tableau, we find the optimal solution to the HighTech
problem consists of the basic variables x 1 , x 2 and s 2 and nonbasic variables s 1 and
s 3 with:
x 1 ¼ 30
x 2 ¼ 12
s 1 ¼ 0
s 2 ¼ 8
s 3 ¼ 0

The value of the objective function is E1980. If management wants to maximize the
total profit contribution, HighTech should produce 30 units of the Deskpro and 12
units of the UltraPortable. When s 2 ¼ 8, management should note that there will be
eight unused UltraPortable display units. Moreover, because s 1 ¼ 0 and s 3 ¼ 0, no
slack is associated with the assembly time constraint and the warehouse capacity
constraint; in other words, these constraints are both binding. Consequently, if it is
possible to obtain additional assembly time and/or additional warehouse space,
The first computer-based management should consider doing so.
simplex application was Figure 5.3 shows the computer solution to the HighTech problem using Excel.
in 1951 when the US Air The optimal solution with x 1 ¼ 30 and x 2 ¼ 12 is showntohave anobjective
Force looked at the
deployment and support function value of E1980. The values of the slack variables complete the optimal
of aircraft. The problem solution with s 1 ¼ 0, s 2 ¼ 8and s 3 ¼ 0. The values in the Reduced Costs column
had 71 variables and 48
are from the net evaluation row of the final simplex tableau. Note that the c j – z j
constraints. There were
73 simplex iterations values in columns corresponding to x 1 and x 2 are both 0. The shadow prices are
needed to find the the z j values for the three slack variables in the final simplex tableau. Referring
optimal solution and this to the final tableau, we see that the shadow price for constraint 1 is the z j value
took the computer 18 corresponding to s 1 ¼ 2.8. Similarly, the shadow price for constraint 2 is 0, and
hours.
the dual price for constraint 3 ¼ 5.2. The use of the Simplex method to calculate
shadow (dual) prices will be discussed further when we cover sensitivity analysis
in Chapter 6.

Summary of the Simplex Method
Let us now summarize the steps followed to solve a linear programme using the
Simplex method. We assume that the problem has all less-than-or-equal-to con-
straints and involves maximization.
Step 1. Formulate a linear programming model of the problem.
Step 2. Add slack variables to each constraint to obtain standard form.
Step 3. Set up the initial simplex tableau.
Step 4. Choose the nonbasic variable with the largest entry in the net evaluation
row to bring into the basis. This variable identifies the pivot column: the
column associated with the incoming variable.
Step 5. Choose as the pivot row that row with the smallest ratio of b i /a ij for a ij > 0
where j is the pivot column. This pivot row is the row of the variables
leaving the basis when variable j enters.
Step 6. Perform the necessary elementary row operations.
a. Divide each element of the pivot row by the pivot element (the
element in the pivot row and pivot column).

Copyright 2014 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has
deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.