Geometric interpretation of linear programming dual

Let's take a look at example 6 from section 9.3 of Linear Algebra and Its Applications.

A manufacturer of mixed nuts sells two different products. Box1 contains 1 pound of cashews and 1 pound of peanuts. Box2 contains 1 pound of filberts and 2 pounds of peanuts. The manufacture is trying to determine how many boxes of each type to make, given the input stock they have available. Box1 sells for \$2. Box2 sells for \$3. Their input stock is 30 pounds of cashews, 20 pounds of filberts, and 54 pounds of peanuts.

Primary problem

Find a vector $x$

that maximizes $c^T x = \begin{bmatrix}2 & 3\end{bmatrix} x$

subject to $\begin{bmatrix}1 & 0\\0 & 1\\1 & 2\end{bmatrix}x \le \begin{bmatrix}30\\20\\54\end{bmatrix} = b$

and $x \ge 0$

Dual problem

Find a vector $y$

that minimizes $b^T y$

subject to $A^T y = \begin{bmatrix}1 & 0 & 1\\0 & 1 & 2\end{bmatrix} y \ge c$

and $y \ge 0$

Primal graph

First, let's recognize the complications of putting both of these problems in the same graph. $x$ is a column vector of how many box1s and box2s should be produced. $y$ is a column vector of the marginal revenue product for each of the inputs. MRP is the additional revenue the manufacture can earn per unit of input, by producing and selling additional outputs with those inputs. So the units of $x$ and $y$ are not even close to matching. $x$ has two rows, and the units are numbers of boxes. $y$ has three rows, and the units are dollars per pound.

The below two dimensional graph is for the primal problem. The horizontal axis shows the number of box1s produced. The vertical axis shows the number of box2s produced. The shaded polygon in the middle shows which combinations are feasible in the primal problem. The objective vector is shown, and its level set lines are shown as gray dashed lines. To reduce the noise in the graph, for the extreme points, the level set lines shown as a dashed line segments instead of full lines. Point C is the maximum feasible solution.

primal graph
geogebra

Dual graph

The graph of the dual problem is three dimensional. The vertical axis shows the price of peanuts. The left axis shows the price of cashews, and the right axis shows the cost of filberts. The blue plane shows the constraint from box1 (the price per unit of input must be greater than or equal to the output price if they were combined into box1s). The purple plane shows the constraint from box2. Two level sets are shown in orange. dual graph
geogebra

Points A, B, C, and D are feasible for the primal problem. While points C, F, and G are feasible for the dual problem. Point E is infeasible on both. The only feasible point they share is C, which is the optimal point for both. On the dual graph, the dual problem is trying to find the feasible point with the lowest level (a point closer to the origin).

On the primal graph, the dual problem is also trying to find the point with the lowest level (closer to the origin). For the dual, points A, B, and D actually have lower levels than the optimal value of C, as shown on both graphs. However, A, B, and D are infeasible for the dual. So out of the feasible points for the dual (points C, F, and G), C is the one with the lowest level.

The feasiblity of the dual problem's points can also be seen on the 2d graph with the dashed level set segments through those points. When the level set line intersects the primal's feasible region at that point, then the point is infeasible for the dual problem. Notice how the dashed line through points A, B, and D intersect with the primal's feasible region. For point A, this indicates that more revenue can be made by producing more box2s (the objective is higher when the filberts line is followed out from A). That is why point A is under the box2 plane in the dual graph. At point D, more revenue can be earned by producing more box1s, which is why it is under the box1 plane in the dual graph. Point B is ruled out in the dual because its MRP for filberts is negative. That is, if the filberts constraint were tighter, the new B' at the intersection of the new filberts constraint and the existing peanuts constraint would make more revenue than the existing B. Point E is also infeasible in the dual, because if the primal's feasible region was extended to point E (if the filberts constraint were removed), then the level set line would intersect the primary's feasible region.

MRP in primal graph

Notice how the MRP at each point (value shown at points in the dual graph) is non-zero precisely for the edges that constrain the primary problem. Point B is at the intersection of the filberts and peanuts lines and has value $(0, -1, 2)$. Its MRP is 0 for the cashews line. That's because the cashews are not a limiting factor for the amount of box1s and box2s produced at point B.

The MRPs can somewhat be seen in the primal graph. Each point on the below graph has 1 or 2 additional points close to it. The additional points were calculated by relaxing the constraints one-by-one, each by 1 unit. The units for the MRPs are dollars per additional manufacturing input. So comparing one of the existing points against a relaxed by 1 point takes care of the "per additional manufacturing input" part of the units. To handle the dollars part, use the level set to convert the additional boxes into dollars. For example, point A' is one box1 higher than A. Each box1 is worth \$3, as indicated by the level set lines (its hard to read because the difference is small). Point A is only bordered by the filberts constraint. So the MRP for point A is $(0,3,0)$.

primal graph with MRP
geogebra