## Using the Dual Solution to Solve the Primal

The dual solution does not indicate optimal amounts of X and Y. It does, however, provide all the information necessary to determine the optimum output mix. The dual solution shows that input C does not impose a binding constraint on output of X and Y. Further, it demonstrates that n = n* = \$108 at the optimum output of X and Y. The dual solution also offers evidence on the value of primal constraint slack variables. To see this, recall the three constraints in the primal problem:

Constraint on A: 4QX + 2QY + SA = 32 Constraint on B: 1QX + 1QY + SB = 10 Constraint on C: 3QY + SC = 21

The dual solution indicates that the constraints on A and B are binding, because both inputs have positive shadow prices, and only resources that are fully utilized have a nonzero marginal value. Accordingly, the slack variables SA and SB equal zero, and the binding primal constraints can be rewritten as

With two equations and only two unknowns, this system can be solved for QX and QY. Multiplying the second constraint by two and subtracting from the first provides

These values of QX and QY, found after learning from the dual which constraints were binding, are identical to the values found by solving the primal problem directly. Having obtained the value for QY, it is possible to substitute value for QY in constraint C and solve for the amount of slack in that resource:

MANAGERIAL APPLICATION 9.4

It's a RIOT on the Internet!

Here's an idea for you. How would you like access to a Remote Interactive Optimization Testbed (RIOT) on the Internet? It's a simple concept, as in simply amazing.

RIOT creates an interface between the Web and linear programming solver programs that allows anyone with access to the Web to submit a linear program and have it solved. There has been a proliferation of linear programming solver software since 1980, like Cplex, Lingo, Minos, and so on. However, each of these solver programs implements different algorithms, like the simplex method, and offers different solution options, like sensitivity analysis. Depending on the problem to be solved, some solvers can be more or less efficient than others in terms of speed, accuracy, number of iterations, and available options.

LP applications on RIOT range from the serious, like a planar robot simulator with obstacle avoidance and open-pit mining problems, to the whimsical, like major league baseball and basketball elimination problems. Over time, continuing improvements promise users the opportunity to find the optimal value (maximum or minimum) for any linear function of a certain number of variables given a set of m linear constraints on these variables (equalities or inequalities).

Like everything on the Web, RIOT is still relatively new and bound to evolve rapidly over time. At this point, it is a free offering designed to achieve four main objectives:.

• Educational. RIOT provides educational information via HTML and interactive problems presented through an easy-to-use interface.

• Research. RIOT showcases state-of-the-art algorithms developed locally by UC Berkeley engineering faculty and others.

• Comparative research. RIOT provides efficiency information for different algorithms that solve similar problems.

• Showcase applications. RIOT provides a forum to showcase new and innovative applications of linear programming techniques.

RIOT is an enormously practical tool. It's on the Internet. It's free. What a RIOT!

See: Home page for RIOT can be found on the Internet (http://riot.ieor.berkeley.edu/riot/index.html).

These relations, which allow one to solve either the primal or the dual specification of a linear programming problem and then quickly obtain the solution to the other, can be generalized by the two following expressions:

Primal Objective Variablei X Dual Slack Variablei = 0 Primal Slack Variable^ X Dual Objective Variable^ = 0

Equation 9.15 states that if an ordinary variable in the primal problem takes on a nonzero value in the optimal solution to that problem, its related dual slack variable must be zero. Only if a particular Qi is zero valued in the solution to the primal can its related dual slack variable, L, take on a nonzero value. A similar relation exists between the slack variables in the primal problem and their related ordinary variables in the dual, as indicated by Equation 9.16. If the primal slack variable is nonzero valued, then the related dual variable will be zero valued, and vice versa.