LP Graphical Method

Interactive visualizations for Chapter 2 of the Ricerca Operativa notes

The Furniture Workshop LP

We work with the same LP from the lecture notes:

\[ \begin{aligned} & \text{maximize} && 30\,x_1 + 50\,x_2 \\ & \text{subject to} && 2\,x_1 + 5\,x_2 \leq 40 && \text{(wood)} \\ & && 4\,x_1 + 2\,x_2 \leq 32 && \text{(labour)} \\ & && x_1, x_2 \geq 0. \end{aligned} \]

The optimal solution is at \((5, 6)\) with profit \(z^* = 450\).

Step 1: Constraint Boundaries

Each inequality constraint defines a half-plane. We first plot the boundary line of each constraint and shade the feasible side.

Each constraint divides the plane into two half-planes. The feasible side is the shaded region (the side containing the origin, since \(0 \leq 40\) and \(0 \leq 32\)).

Step 2: Feasible Region

The feasible region is the intersection of all half-planes (both resource constraints plus \(x_1, x_2 \geq 0\)).

The feasible region \(P\) is a convex polygon with four vertices: \((0,0)\), \((8,0)\), \((5,6)\), and \((0,8)\). Every point inside this polygon satisfies all constraints simultaneously.

Step 3: Objective Function Isolines

The objective \(z = 30x_1 + 50x_2\) defines a family of parallel lines (one per value of \(z\)). As \(z\) increases, the isoline shifts in the direction of the gradient \(\nabla z = (30, 50)\).

The isolines are parallel (all have slope \(-3/5\)). As we increase \(z\), we slide the line in the gradient direction \((30, 50)\). The last isoline touching the feasible region passes through the vertex \((5, 6)\) at \(z^* = 450\).

Step 4: Vertex Enumeration

Every vertex of the feasible region is the intersection of two constraint boundary lines. We enumerate all vertices and evaluate the objective at each one.

The Fundamental Theorem of LP guarantees that the optimal solution lies at a vertex. By evaluating the objective at all four vertices, we confirm that \((5, 6)\) achieves the maximum \(z^* = 450\).

Step 5: Complete Solution Summary

Putting it all together: the feasible region, the optimal isoline, and the optimal vertex.

Conclusion: The workshop should produce 5 chairs and 6 tables for a maximum profit of 450. Both the wood and labour constraints are tight at the optimum (all resources are fully used).

Bonus: Multiple Optimal Solutions

When the objective gradient is parallel to a binding constraint, the optimum is an entire edge rather than a single vertex.

Left: The original objective (\(30x_1 + 50x_2\)) has a unique vertex optimum. Right: When the objective is \(2x_1 + 5x_2\) (same coefficients as the wood constraint), the isoline coincides with the constraint boundary, and the entire edge from \((5,6)\) to \((0,8)\) is optimal.