The Simplex Method and Duality

How can we find the optimal solution efficiently, and interpret how valuable our limited resources are? In Chapter 02 we found the optimum by comparing the corner points of the feasible region. With two variables you can check this on a graph, but real problems have hundreds of products and thousands of constraints, so you cannot check every corner point one by one.

The simplex method is an algorithm that finds the optimal solution by moving systematically from one corner point of the feasible region to another, improving the objective value as it goes. Instead of blindly comparing every feasible solution, it only moves from the current corner to a neighboring corner that is better.

In Figure 1 the simplex method starts at (0, 0), first increases y, which has the larger unit profit, to arrive at (0, 4), and then increases x to reach (8/3, 8/3). It visited only three of the four corners, and as the problem grows, the share of corners that are never visited becomes much larger.

To apply the simplex method, we turn the inequality constraints into equations. If x + 2y of the 8 hours available in process 1 are actually used, we let s₁ be the hours left unused and write:

At the start x = y = 0, so s₁ = s₂ = 8. The variables whose values are determined this way are called basic variables, and the simplex method arranges these equations in a simplex tableau and swaps the basic variables one at a time. The Z row records how much profit falls when each variable is increased by one unit (a negative number means profit rises).

Step 0: (x, y) = (0, 0), Z = 0 · −100 is the smallest entry in the Z row, so y enters

As y increases, process 1 can hold out until 8/2 = 4 and process 2 until 8/1 = 8. Process 1 runs out first, so its slack variable s₁ leaves the basis (the minimum ratio test).

Step 1: (x, y) = (0, 4), Z = 400 · −10 remains in the Z row, so x enters

This time we increase x. The y row gives 4 ÷ (1/2) = 8 and the s₂ row gives 4 ÷ (3/2) = 8/3, so s₂ leaves.

Step 2: (x, y) = (8/3, 8/3), Z = 1280/3 · no negative entries in the Z row, so this is optimal

With no negative entries left in the Z row, increasing any variable no longer raises profit. The optimal solution is x = y = 8/3, Z = 1280/3. The 140/3 and 20/3 in the slack-variable columns of the final Z row are the same values as the shadow prices we will see in Section 6.

If the simplex method is a way of computing the optimal solution, duality is a way of interpreting the same problem from a different point of view.

Let the dual variables u and v be the values assigned to one unit of time in each of the two processes. Each process has 8 hours, so the total value of the resources is 8u + 8v. Product A uses 1 hour in process 1 and 2 hours in process 2, so the combined value of those resources must be at least A's profit of $60, and the same goes for B.

Flipping (transposing) the primal's constraint coefficient matrix gives the dual problem. The primal's right-hand side (8, 8) becomes the dual's objective coefficients, and the primal's objective coefficients (60, 100) become the dual's right-hand side.

When both the primal and the dual have optimal solutions, strong duality says the two optimal values are equal. Setting the dual's two constraints as equations and solving gives u = 140/3, v = 20/3, and

The two optimal values match. u and v are the shadow prices of one unit of time in each process. They tell you how much the optimal profit rises if you secure one more hour of that resource while everything else stays the same.

In Figure 3, raising process 1's time from 8 to 9 hours lifts the maximum profit from 1280/3 to $473.33, an increase of exactly 140/3. So in this model, securing extra time in process 1 is worth far more in marginal profit than extra time in process 2. If an extra hour of process 1 costs less than $46.67, adding it pays off. This interpretation, however, holds only in the 4–16 hour range. Beyond 16 hours process 2 becomes the bottleneck, and adding more process 1 time no longer raises profit.

By weak duality, the profit of any feasible primal solution can never exceed the resource value of any feasible dual solution.

If a feasible primal solution earns $400 in profit and a feasible dual solution gives a resource value of $440, the optimal profit lies between $400 and $440. In this way the dual provides an upper bound on the optimal value (for a maximization problem), and the moment the two values become equal, both are proven optimal. This is also the principle behind the "optimality gap" that large-scale optimization software reports.

Using the two ideas together lets you read an optimization result not as a bare number but as real decision information: "if we add this resource, how much more do we make?"

• Simplex method: finds the optimum by moving along the corners only in directions that improve the objective.
• Slack variables and the tableau: turn inequalities into equations; once the Z row has no negative entries, you are at the optimum.
• Dual problem: uses the value of one unit of each resource as variables and finds the minimum resource value that accounts for each product's profit.
• Strong · weak duality: Z ≤ W for feasible solutions and Z* = W* at the optimum, so optimality can be verified.
• Shadow price: the increase in optimal profit from one more unit of a resource, within its valid range.

Next is 04 Integer programming. It covers problems where decisions must be whole numbers, such as product quantities, numbers of staff, or numbers of vehicles.