The Muddy River Chemical Corporation must produce exactly 1,000 pounds of a special mixture of phosphate and potassium for a customer. Phosphate costs $5 per pound and potassium costs $6 per pound. No more than 300 pounds of phosphate can be used, and at least 150 pounds of potassium must be used. The problem is to determine the least-cost blend of the two ingredients.

This problem may be restated mathematically as

where

Note that there are three constraints, not counting the nonnegativity constraints: the first is an equality, the second is a less-than-or-equal-to constraint, and the third is a greater-than-or-equal-to constraint.

To have a better understanding of the problem, a brief graphical analysis may prove useful. There are only two decision variables, $X_1$ and $X_2,$ so we are able to plot the constraints and feasible region. Because the first constraint, $X_1+X_2=1,000,$ is an equality, the solution must lie somewhere on the line ABC (see Figure M7.3). It must also lie between points A and B because of the constraint $X_1\le 300.$ The third constraint, $X_2\ge 150,$ is actually redundant and nonbinding, since $X_2$ will automatically be greater than 150 pounds if the first two constraints are observed. Hence, the feasible region consists of all points on the line segment AB. As you recall from Chapter 7, however, an optimal solution will always lie at a corner point of the feasible ­region (even if the region is only a straight line). The solution must therefore be at either point A or point B. A quick analysis reveals that the least-cost solution lies at corner B—namely, $X_1=300$ pounds of phosphate and $X_2=700$ pounds of potassium. The total cost is $5,700.

You don’t need the simplex method to solve the Muddy River Chemical problem, of course. But we can guarantee you that few problems will be this simple. In general, you can expect to see several variables and many constraints. The purpose of this section is to illustrate the straightforward application of the simplex method to minimization problems. When the simplex procedure is used to solve this, it will methodically move from corner point to corner point until the optimal solution is reached. In Figure M7.3, the simplex method will begin at point E, then move to point F, then to point G, and finally to point B, which is the optimal solution.

The first step is to apply what we learned in the preceding section to convert the constraints and objective function into the proper form for the simplex method. The equality constraint, $X_1+X_2=1,000,$ just involves adding an artificial variable, $A_1:$

Table M7.7 Initial Simplex Tableau for the Muddy River Chemical Corporation Problem

The second constraint, $X_1\le 300,$ requires the insertion of a slack variable—let’s call it $S_1:$

The last constraint is $X_2\ge 150,$ which is converted to an equality by subtracting a surplus variable, $S_2,$ and adding an artificial variable, $A_2:$

Finally, the objective function, $\text{cost}=\$5X_1+\$6X_2,$ is rewritten as

The complete set of constraints can now be expressed as follows:

Minimization problems are quite similar to the maximization problems tackled earlier in this module. The significant difference involves the $C_j-Z_j$ row. Our objective is to minimize cost, and a negative $C_j-Z_j$ value indicates that the total cost will decrease if that variable is selected to enter the solution. Thus, the new variable to enter the solution in each tableau (the pivot column variable) will be the one with a negative $C_j-Z_j$ that gives the largest improvement. We choose the variable that decreases costs the most. In minimization problems, an optimal solution is reached when all the numbers in the $C_j-Z_j$ row are 0 or positive—just the opposite from the maximization case.4 All other simplex stpng, as seen in the following, remain the same.

Now we solve Muddy River Chemical Corporation’s LP formulation using the simplex method. The initial tableau is set up just as in the earlier maximization example. Its first three rows are shown in the accompanying table. We note the presence of the $M costs associated with artificial variables $A_1$ and $A_2,$ but we treat them as if they were any large number. As noted earlier, they have the effect of forcing the artificial variables out of the solution quickly because of their large costs.

The numbers in the $Z_j$ row are computed by multiplying the $C_j$ column on the far left of the tableau times the corresponding numbers in the other columns. They are then entered in Table M7.7:

The $C_j-Z_j$ entries are determined as follows:

This initial solution was obtained by letting each of the variables $X_1, X_2,$ and $S_2$ assume a value of 0. The current basic variables are $A_1=1,000, S_1=300,$ and $A_2=150.$ This complete solution could be expressed in vector, or column, form as

An extremely high cost, $1,150M from Table M7.7, is associated with this answer. We know that this can be reduced significantly and now move on to the solution procedures.

In the $C_j-Z_j$ row of Table M7.7, we see that there are two entries with negative values, $X_1$ and $X_2.$ In the simplex rules for minimization problems, this means that an optimal solution does not yet exist. The pivot column is the one with the negative entry in the $C_j-Z_j$ row that indicates the largest improvement—shown in Table M7.7 as the $X_2$ column, which means that $X_2$ will enter the solution next.

Which variable will leave the solution to make room for the new variable, $X_2?$ To find out, we divide the elements of the quantity column by the respective pivot column substitution rates:

Hence, the pivot row is the $A_2$ row, and the pivot number (circled) is at the intersection of the $X_2$ column and the $A_2$ row.

The entering row for the next simplex tableau is found by dividing each element in the pivot row by the pivot number, 1. This leaves the old pivot row unchanged, except that it now represents the solution variable $X_2.$ The other two rows are altered one at a time by again applying the formula shown earlier in step 4:

The $Z_j$ and $C_j-Z_j$ rows are computed next:

All of these computational results are presented in Table M7.8.

Table M7.8 Second Simplex Tableau for the Muddy River Chemical Corporation Problem

The solution at the end of the second tableau (point F in Figure M7.3) is $A_1=850,$ $S_1=300,$ and $X_2=150.$ $X_1,$ $S_2,$ and $A_2$ are currently the nonbasic variables and have zero value. The cost at this point is still quite high, $\$850M+\$900.$ This answer is not optimal ­because not every number in the $C_j-Z_j$ row is zero or positive.

The new pivot column is the $X_1$ column. To determine which variable will leave the basis to make room for $X_1,$ we check the quantity column–to–pivot column ratios again:

Hence, variable $S_1$ will be replaced by $X_1.$5 The pivot number, row, and column are labeled in Table M7.8.

To replace the pivot row, we divide each number in the $S_1$ row by 1 (the circled pivot number), leaving the row unchanged. The new $X_1$ row is shown in Table M7.9. The other computations for this third simplex tableau follow:

Table M7.9 Third Simplex Tableau for the Muddy River Chemical Corporation Problem

The $Z_j$ and $C_j-Z_j$ rows are computed next:

The solution at the end of the three iterations (point G in Figure M7.3) is still not optimal because the $S_2$ column contains a $C_j-Z_j$ value that is negative. Note that the current total cost is nonetheless lower than at the end of the second tableau, which in turn is lower than the initial solution cost. We are headed in the right direction but have one more tableau to go!

Fourth Tableau for the Muddy River Chemical Corporation Problem

The pivot column is now the $S_2$ column. The ratios that determine the row and variable to be replaced are computed as follows:

$$\begin{array}{ccc}\text{For} \text{the} A_1 \text{row}:& \frac{550}{1}=550& (\text{row} \text{to} \text{be} \text{replaced})\hfill \\ \text{For} \text{the} X_1 \text{row: }& \frac{300}{0}\hfill & \left(\text{undefined}\right)\hfill \\ \text{For} \text{the} X_2 \text{row:}& \frac{150}{\mathrm{-}1}\hfill & (\text{not} \text{considered} \text{because} \text{it} \text{is} \text{negative})\end{array}$$

Each number in the pivot row is divided by the pivot number (again 1, by coincidence). The other two rows are computed as follows and are shown in Table M7.10:

7.1-15 Full Alternative Text

	COLUMN
	X1	X2	S1	S2	A1	A2
$C_j$ for column	$5	$6	$0	$0	$M	$M
$Z_j$ for column	$5	$6	$\mathrm{-}\$1$	$0	$6	$0
$C_j-Z_j$ for column	$0	$0	$1	$0	$M $\mathrm{\$M}-6$	$M

Table M7.10 Fourth and Optimal Solution to the Muddy River Chemical Corporation Problem

Table M7.10 Full Alternative Text

On examining the $C_j-Z_j$ row in Table M7.10, only positive or 0 values are found. The fourth tableau therefore contains the optimum solution. That solution is $X_1=300,$ $X_2=700,$ and $S_2=550.$ The artificial variables are both equal to 0, as is $S_1.$ Translated into management terms, the chemical company’s decision should be to blend 300 pounds of phosphate $\left(X_1\right)$ with 700 pounds of potassium $\left(X_2\right).$ This provides a surplus $\left(S_2\right)$ of 550 pounds of potassium more than required by the constraint $X_2\ge 150.$ The cost of this solution is $5,700. If you look back to Figure M7.3, you can see that this is identical to the answer found by the graphical approach.

Although small problems such as this can be solved graphically, more realistic product blending problems demand use of the simplex method, usually in computerized form.

In Chapter 7, we addressed some special cases that may arise when solving LP problems graphically (see Section 7.6). Here we describe these cases again, this time as they refer to the simplex method.

Infeasibility

Infeasibility, you may recall, comes about when there is no solution that satisfies all of the problem’s constraints. In the simplex method, an infeasible solution is indicated by looking at the final tableau. In it, all $C_j-Z_j$ row entries will be of the proper sign to imply optimality, but an artificial variable $\left(A_1\right)$ will still be in the solution mix.

Table M7.11 illustrates the final simplex tableau for a hypothetical minimization type of LP problem. The table provides an example of an improperly formulated problem, probably containing conflicting constraints. No feasible solution is possible because an artificial variable, $A_2,$ remains in the solution mix, even though all $C_j-Z_j$ entries are positive or 0 (the criterion for an optimal solution in a minimization case).

Table M7.11 Illustration of Infeasibility

Table M7.11 Full Alternative Text

Unbounded Solutions

Unboundedness describes linear programs that do not have finite solutions. It occurs in maximization problems, for example, when a solution variable can be made infinitely large without violating a constraint. In the simplex method, the condition of unboundedness will be discovered prior to reaching the final tableau. We will note the problem when trying to decide which variable to remove from the solution mix. As seen earlier in this module, the procedure is to divide each quantity column number by the corresponding pivot column number. The row with the smallest positive ratio is replaced. But if all the ratios turn out to be negative or undefined, it indicates that the problem is unbounded.

Table M7.12 illustrates the second tableau calculated for a particular LP maximization problem by the simplex method. It also points to the condition of unboundedness. The solution is not optimal because not all $C_j-Z_j$ entries are 0 or negative, as required in a maximization problem. The next variable to enter the solution should be $X_1.$ To determine which variable will leave the solution, we examine the ratios of the quantity column numbers to their corresponding numbers in the $X_1,$ or pivot, column:

7.1-18 Full Alternative Text

Since both pivot column numbers are negative, an unbounded solution is indicated.

Table M7.12 Problem with an Unbounded Solution

Table M7.12 Full Alternative Text

Degeneracy

Degeneracy is another situation that can occur when solving an LP problem using the simplex method. It develops when three (or more) constraints pass through a single point. For example, suppose a problem has only these three constraints $X_1\le 10, X_2\le 10,$ and $X_1+X_2<20.$ All three constraint lines will pass through the point $\left(10, 10\right).$ Degeneracy is first recognized when the ratio calculations are made. If there is a tie for the smallest ratio, this is a signal that degeneracy ­exists. As a result of this, when the next tableau is developed, one of the variables in the solution mix will have a value of zero.

Table M7.13 provides an example of a degenerate problem. At this iteration of the given maximization LP problem, the next variable to enter the solution will be $X_1,$ since it has the only positive $C_j-Z_j$ number. The ratios are computed as follows:

Theoretically, degeneracy could lead to a situation known as cycling, in which the simplex ­algorithm alternates back and forth between the same nonoptimal solutions; that is, it puts a new variable in, then takes it out in the next tableau, then puts it back in, and so on. One simple way of dealing with the issue is to select either row ($S_2$ or $S_3$, in this case) arbitrarily. If we are unlucky and cycling does occur, we simply go back and select the other row.

Table M7.13 Problem Illustrating Degeneracy

Table M7.13 Full Alternative Text

More Than One Optimal Solution

Multiple, or alternate, optimal solutions can be spotted when the simplex method is being used by looking at the final tableau. If the $C_j-Z_j$ value is equal to 0 for a variable that is not in the solution mix, more than one optimal solution exists.

Let’s take Table M7.14 as an example. Here is the last tableau of a maximization problem; each entry in the $C_j-Z_j$ row is 0 or negative, indicating that an optimal solution has been reached. That solution is read as $X_2=6, S_2=3,$ and $\text{profit}=\$12.$ Note, however, that variable $X_1$ can be brought into the solution mix without increasing or decreasing profit. The new solution, with $X_1$ in the basis, would become X₁ = 3 and $X_2=1.5,$ with profit still at $12. Can you modify Table M7.14 to prove this?

Table M7.14 Problem with Alternate Optimal Solutions

Table M7.14 Full Alternative Text

In Chapter 7, we introduce the topic of sensitivity analysis as it applies to LP problems that we have solved graphically. This valuable concept shows how the optimal solution and the value of its objective function change given changes in various inputs to the problem. Graphical analysis is useful in understanding intuitively and visually how feasible regions and the slopes of ­objective functions can change as model coefficients change. Computer programs handling LP problems of all sizes provide sensitivity analysis as an important output feature. Those programs use the information provided in the final simplex tableau to compute ranges for the objective function coefficients and ranges for the RHS values. They also provide shadow prices, a concept that we introduce in this section.

High Note Sound Company Revisited

In Chapter 7, we use the High Note Sound Company to illustrate sensitivity analysis graphically. High Note is a firm that makes quality speakers (called $X_1$) and stereo receivers (called $X_2$). Its LP formulation is repeated here:

$$\begin{array}{c}\text{Maximize} \text{profit}=\$50X_1+\$120X_2\hfill \\ \hfill \text{subject} \text{to}2X_1+4X_2\le 80\left(\text{hours} \text{of} \text{electricians'} time available\right)\\ \hfill 3X_1+1X_2\le 60\left(\text{hours} \text{of} \text{audio} \text{technicians' }time available\right)\end{array}$$

High Note’s graphical solution is repeated in Figure M7.4.

Figure M7.4 Full Alternative Text

Changes in the Objective Function Coefficients

In Chapter 7, we saw how to use graphical LP to examine the objective function coefficients.

A second way of illustrating the sensitivity analysis of objective function coefficients is to consider the problem’s final simplex tableau. For the High Note Sound Company, this tableau is shown in Table M7.15. The optimal solution is seen to be as follows:

7.1-22 Full Alternative Text

Basic variables (those in the solution mix) and nonbasic variables (those set equal to 0) must be handled differently using sensitivity analysis. Let us first consider the case of a nonbasic variable.

Table M7.15 Optimal Solution by the Simplex Method

Table M7.15 Full Alternative Text

Nonbasic Objective Function Coefficient

Our goal here is to find out how sensitive the problem’s optimal solution is to changes in the contribution rates of variables not currently in the basis ($X_1$ and $S_1$). Just how much would the objective function coefficients have to change before $X_1$ or $S_1$ would enter the solution mix and replace one of the basic variables?

The answer lies in the $C_j-Z_j$ row of the final simplex tableau (as in Table M7.15). Since this is a maximization problem, the basis will not change unless the $C_j-Z_j$ value of one of the nonbasic variables becomes positive. That is, the current solution will be optimal as long as all numbers in the bottom row are less than or equal to 0. It will not be optimal if $X_1$’s $C_j-Z_j$ value is positive or if $S_1$’s $C_j-Z_j$ value is greater than 0. Therefore, the values of $C_j$ for $X_1$ and $S_1$ that do not bring about any change in the optimal solution are given by

$$C_j-Z_j\le 0$$

This is the same as writing

$$C_j\le Z_j$$

Since $X_1$’s $C_j$ value is $50 and its $Z_j$ value is $60, the current solution is optimal as long as the profit per speaker does not exceed $60 or, correspondingly, does not increase by more than $10. Similarly, the contribution rate per unit of $S_1$ (or per hour of electrician’s time) may ­increase from $0 up to $30 without changing the current solution mix.

In both cases, when you are maximizing an objective function, you may increase the value of $C_j$ up to the value of $Z_j.$ You may also decrease the value of $C_j$ for a nonbasic variable to negative infinity $\left(\mathrm{-}\infty \right)$ without affecting the solution. This range of $C_j$ values is called the range of insignificance for nonbasic variables.

$$\begin{array}{l}\text{− }\infty \le C_j\left(\text{for }{X}_{\text{1}}\right)\le \text{ \$ 60}\\ \text{− }\infty \le C_j\left(\text{for }{S}_1\right)\le \text{ \$ 30}\end{array}$$

Basic Objective Function Coefficient

Sensitivity analysis on objective function coefficients of variables that are in the basis or solution mix is slightly more complex. We saw that a change in the objective function coefficient for a nonbasic variable affects only the $C_j-Z_j$ value for that variable. But a change in the profit or cost of a basic variable can affect the $C_j-Z_j$ values of all nonbasic variables because this $C_j$ is not only in the $C_j$ row but also in the $C_j$ column. This then impacts the $Z_j$ row.

Let us consider changing the profit contribution of stereo receivers in the High Note Sound Company problem. Currently, the objective function coefficient is $120. The change in this value can be denoted by the Greek capital letter delta $\left(\Delta \right).$ We rework the final simplex tableau (first shown in Table M7.15) and see our results in Table M7.16.

Table M7.16 Change in the Profit Contribution of Stereo Receivers

Table M7.16 Full Alternative Text

Notice the new $C_j-Z_j$ values for nonbasic variables $X_1$ and $S_1.$ These were determined in exactly the same way as we did earlier in this module. But wherever the $C_j$ value for $X_2$ of $120 was seen in Table M7.15, a new value of $\$120+\Delta$ is used in Table M7.16.

Once again, we recognize that the current optimal solution will change only if one or more of the $C_j-Z_j$ row values becomes greater than 0. The question is, how may the value of $\Delta$ vary so that all $C_j-Z_j$ entries remain negative? To find out, we solve for $\Delta$ in each column.

From the $X_1$ column:

$$\begin{array}{l}-\text{10}-\text{0}\text{.5}\Delta \le \text{0}\\ -\text{10}\text{=}\text{0}\text{.5}\Delta \\ -\text{20}\text{=}\Delta \text{ or }\Delta \ge -\text{20}\end{array}$$

This inequality means that the optimal solution will not change unless $X_2$’s profit coefficient decreases by at least $20, which is a change of $\Delta =\mathrm{-}\$20.$ Hence, variable $X_1$ will not enter the basis unless the profit per stereo receiver drops from $120 to $100 or less. This, interestingly, is exactly what we noticed graphically in Chapter 7. When the profit per stereo receiver dropped to $80, the optimal solution changed from corner point a to corner point b.

Now we examine the $S_1$ column:

$$\begin{array}{l}-3\text{0}-\text{0}\text{.25}\Delta \le \text{0}\\ -3\text{0}\le \text{0}\text{.25}\Delta \\ -1\text{20}\le \Delta \text{ or }\Delta \ge -1\text{20}\end{array}$$

This inequality implies that $S_1$ is less sensitive to change than $X_1. S_1$ will not enter the basis unless the profit per unit of $X_2$ drops from $120 all the way down to $0.

Since the first inequality is more binding, we can say that the range of optimality for $X_2$’s profit coefficient is

$$\$100\le C_j\left(\text{for} X_2\right)\le \infty$$

As long as the profit per stereo receiver is greater than or equal to $100, the current production mix of $X_2=20$ receivers and $X_1=0$ speakers will be optimal.

In analyzing larger problems, we would use this procedure to test for the range of optimality of every real decision variable in the final solution mix. The procedure helps us avoid the time-consuming process of reformulating and resolving the entire LP problem each time a small change occurs. Within the bounds set, changes in profit coefficients would not force a firm to alter its product mix decision or change the number of units produced. Overall profits, of course, will change if a profit coefficient increases or decreases, but such computations are quick and easy to perform.

Changes in Resources or RHS Values

Making changes in the RHS values (the resources of electricians’ and audio technicians’ time) results in changes in the feasible region and often the optimal solution.

Shadow Prices

This leads us to the important subject of shadow prices. Exactly how much should a firm be willing to pay to make additional resources available? Is one more hour of machine time worth $1 or $5 or $20? Is it worthwhile to pay workers an overtime rate to stay one extra hour each night to increase production output? Valuable management information could be provided if the worth of additional resources were known.

Fortunately, this information is available to us by looking at the final simplex tableau of an LP problem. An important property of the ${\text{C}}_{\text{j}}-{\text{Z}}_{\text{j}}$ row is that the negatives of the numbers in its slack variable $\left({\text{S}}_{\text{i}}\right)$ columns provide us with what we call shadow prices. A shadow price is the change in value of the objective function from an increase of one unit of a scarce resource (e.g., when one more hour of machine time or labor time or other resource is made available).

The final simplex tableau for the High Note Sound Company problem is repeated as Table M7.17 (it was first shown as Table M7.15). The tableau indicates that the optimal solution is $X_1=0, X_2=20, S_1=0, \text{and} S_2=40$ and that profit$=\$2,400.$ Recall that $S_1$ represents slack availability of the electricians’ resource and $S_2$ the unused time in the audio technicians’ department.

Table M7.17 Final Tableau for the High Note Sound Company

Table M7.17 Full Alternative Text

The firm is considering hiring an extra electrician on a part-time basis. Let’s say that it will cost $22 per hour in wages and benefits to bring the part-timer on board. Should the firm do this? The answer is yes: the shadow price of the electrician time resource is $30. Thus, the firm will net $\$8 \left(=\$30-\$22\right)$ for every hour the new worker helps in the production process.

Should High Note also hire a part-time audio technician at a rate of $14 per hour? The answer is no: the shadow price is $0, implying no increase in the objective function by making more of this second resource available. Why? Because not all of the resource is currently being used—40 hours are still available. It would hardly pay to buy more of the resource.

Right-Hand-Side Ranging

Obviously, we can’t add an unlimited number of units of ­resource without eventually violating one of the problem’s constraints. When we understand and compute the shadow price for an additional hour of electricians’ time ($30), we will want to ­determine how many hours we can actually use to increase profits. Should the new resource be added 1 hour, 2 hours, or 200 hours per week? In LP terms, this process involves finding the range over which shadow prices will stay valid. Right-hand-side ranging tells us the number of hours High Note can add or remove from the electrician department and still have a shadow price of $30.

Ranging is simple in that it resembles the simplex process we used earlier in this module to find the minimum ratio for a new variable. The $S_1$ column and quantity column from Table M7.17 are repeated in the following table; the ratios, both positive and negative, are also shown:

Quantity	S1	Ratio
20	0.25	$20/0.25=80$
40	$\mathrm{-}0.25$	$40/\mathrm{-}0.25=2160$

The smallest positive ratio (80, in this example) tells us by how many hours the electricians’ time resource can be reduced without altering the current solution mix. Hence, we can decrease the RHS resource by as much as 80 hours—basically from the current 80 hours all the way down to 0 hours—without causing a basic variable to be pivoted out of the solution.

The smallest negative ratio $\left(\mathrm{-}160\right)$ tells us the number of hours that can be added to the resource before the solution mix changes. In this case, we can increase electricians’ time by 160 hours, up to $240 \left(=80 \text{currently}+160 \text{may} \text{be} \text{added}\right)$ hours. We have now established the range of electricians’ time over which the shadow price of $30 is valid. That range is from 0 to 240 hours.

The audio technician resource is slightly different in that all 60 hours of time originally available have not been used. (Note that $S_2=40$ hours in Table M7.17.) If we apply the ratio test, we see that we can reduce the number of audio technicians’ hours by only 40 (the smallest positive ratio $=40/1$) before a shortage occurs. But since we are not using all the hours currently available, we can increase them indefinitely without altering the problem’s solution. Note that there are no negative substitution rates in the $S_2$ column, so there are no negative ­ratios. Hence, the valid range for this shadow price would be from $20\left(=60-40\right)$ hours to an ­unbounded upper limit.

The substitution rates in the slack variable column can also be used to determine the actual values of the solution mix variables if the right-hand side of a constraint is changed. The following relationship is used to find these values:

$$\text{New} \text{quantity}=\text{Original} \text{quantity}+\left(\text{Substution} \text{rate}\right)\left(\text{Change} \text{in} \text{right}–\text{hand} \text{side}\right)$$

For example, if 12 more electrician hours were made available, the new values in the quantity column of the simplex tableau are found as follows:

Original Quantity	S1	New Quantity
20	0.25	$20+\left(0.25\right)\left(12\right)=23$
40	$\mathrm{-}0.25$	$40+\left(\mathrm{-}0.25\right)\left(12\right)=37$

Thus, if 12 hours are added, $X_2=23$ and $S_2=37.$ All other variables are nonbasic and remain zero. This yields a total profit of $50\left(0\right)+120\left(23\right)=\$2,760,$ which is an increase of $360 (or the shadow price of $30 per hour for 12 hours of electrician time). A similar analysis with the other constraint and the $S_2$ column would show that if any additional audio technician hours were added, only the slack for that constraint would increase.

Every LP problem has another LP problem associated with it, which is called its dual. The first way of stating a linear problem is called the primal of the problem; we can view all of the problems formulated thus far as primals. The second way of stating the same problem is called the dual. The optimal solutions for the primal and the dual are equivalent, but they are derived through alternative procedures.

The dual contains economic information useful to management, and it may also be easier to solve, in terms of less computation, than the primal problem. Generally, if the LP primal involves maximizing a profit function subject to less-than-or-equal-to resource constraints, the dual will involve minimizing total opportunity costs subject to greater-than-or-equal-to product profit constraints. Formulating the dual problem from a given primal is not terribly complex, and once it is formulated, the solution procedure is exactly the same as for any LP problem.

Let’s illustrate the primal–dual relationship with the High Note Sound Company data. As you recall, the primal problem is to determine the best production mix of Speakers $\left(X_1\right)$ and stereo receivers $\left(X_2\right)$ to maximize profit:

The dual of this problem has the objective of minimizing the opportunity cost of not using the resources in an optimal manner. Let’s call the variables that it will attempt to solve for $U_1$ and $U_2. U_1$ represents the potential hourly contribution or worth of electrician time—in other words, the dual value of 1 hour of the electrician’ resource. $U_2$ stands for the imputed worth of the ­audio technicians’ time, or the dual technician resource. Thus, each constraint in the primal problem will have a corresponding variable in the dual problem. Also, each decision variable in the primal problem will have a corresponding constraint in the dual problem.

The RHS quantities of the primal constraints become the dual’s objective function coefficients. The total opportunity cost that is to be minimized will be represented by the function $80U_1+60U_2$—that is,

The corresponding dual constraints are formed from the transpose6 of the primal constraints’ coefficients. Note that if the primal constraints are $\le ,$ the dual constraints are $\ge :$

Let’s look at the meaning of these dual constraints. In the first inequality, the RHS constant ($50) is the income from one speaker. The coefficients of $U_1$ and $U_2$ are the amounts of each scarce resource (electrician time and audio technician time) that are required to produce a speaker. That is, 2 hours of electricians’ time and 3 hours of audio technicians’ time are used up in making one speaker. Each speaker produced yields $50 of revenue to High Note Sound Company. This inequality states that the total imputed value or potential worth of the scarce resources needed to produce a speaker must be at least equal to the profit derived from the product. The second constraint makes an analogous statement for the stereo receiver product.

Solving the Dual of the High Note Sound Company Problem

The simplex algorithm is applied to solve the preceding dual problem. With appropriate surplus and artificial variables, it can be restated as follows:

$$\begin{array}{ll}\text{Minimize}\hfill & \text{opportunity cost = 80}{U}_{\text{1}}\text{ + 60}{U}_{\text{2}}\text{ + 0}{S}_1\text{ + 0}{S}_{\text{2}}\text{ + }M{A}_{\text{1}}\text{ + }M{A}_{\text{2}}\hfill \\ \text{subject to}\hfill & \text{2}U\text{1 + 3}U\text{2 - 1}S\text{1 + 1}A\text{1 = 50}\hfill \\ \hfill & \text{4}U\text{1 + 1}U\text{2 - 1}S\text{2 + 1}A\text{2 = 120}\hfill \end{array}$$

The first and second tableaus are shown in Table M7.18. The third tableau—containing the optimal solution of $U_1=30, U_2=0, S_1=10, S_2=0,$ and opportunity cost $=\$2,400$—appears in Figure M7.5, along with the final tableau of the primal problem.

Table M7.18 First and Second Tableaus of the High Note Dual Problem

Table M7.18 Full Alternative Text

Figure M7.5 Full Alternative Text

We mentioned earlier that the primal and dual lead to the same solution even though they are formulated differently. How can this be?

It turns out that in the final simplex tableau of a primal problem, the absolute values of the numbers in the $C_j-Z_j$ row under the slack variables represent the solutions to the dual problem—that is, the optimal $U_i\text{s}$ (see Figure M7.5). In the earlier section on sensitivity analysis, we termed these numbers in the columns of the slack variables shadow prices. Thus, the solution to the dual problem presents the marginal profits of each additional unit of resource.

It also happens that the absolute value of the $C_j-Z_j$ values of the slack variables in the ­optimal dual solution represent the optimal values of the primal $X_1$ and $X_2$ variables. The minimum opportunity cost derived in the dual must always equal the maximum profit derived in the primal.

Also note the other relationships between the primal and the dual that are indicated in ­ Figure M7.5 by arrows. Columns $A_1$ and $A_2$ in the optimal dual tableau may be ignored because, as you recall, artificial variables have no physical meaning.

The biggest change to take place in the field of LP solution techniques in four decades was the 1984 arrival of an alternative to the simplex algorithm. Developed by Narendra Karmarkar, the new method, called Karmarkar’s algorithm, often takes significantly less computer time to solve very large-scale LP problems.8

As we saw, the simplex algorithm finds a solution by moving from one adjacent corner point to the next, following the outside edges of the feasible region. In contrast, Karmarkar’s method follows a path of points on the inside of the feasible region. Karmarkar’s method is also unique in its ability to handle an extremely large number of constraints and variables, thereby giving LP users the capacity to solve previously unsolvable problems.

Although it is likely that the simplex method will continue to be used for many LP problems, a new generation of LP software built around Karmarkar’s algorithm is already becoming popular. Delta Air Lines became the first commercial airline to use the Karmarkar program, called KORBX, which was developed and is sold by AT&T. Delta found that the program streamlined the monthly scheduling of 7,000 pilots who fly more than 400 airplanes to 166 cities worldwide. With increased efficiency in allocating limited resources, Delta saves millions of dollars in crew time and related costs.