Objectives, Decision Variables, Constraints, and Feasibility › Example: Allocating Two Products Across Two Resources

We now solve the packaging problem completely by hand, then repeat the exercise with whole pallets, and finally measure the gap between the two. Hand-solving is not busywork: it gives us a reference value against which every solver call in the next section can be audited.

The first step is to find the feasible set, because without it we have no candidates to score. Each resource inequality becomes an equality on its boundary line. The machine constraint $2x_1 + x_2 \leq 8$ has boundary $x_2 = 8 - 2x_1$, which meets the $x_1$-axis at $x_1 = 4$ and the $x_2$-axis at $x_2 = 8$. The labour constraint $x_1 + 2x_2 \leq 8$ has boundary $x_2 = 4 - x_1/2$, meeting the axes at $x_1 = 8$ and $x_2 = 4$. The non-negativity domains cut everything to the first quadrant, so the feasible region is the quadrilateral with corners

$$(0,0), \qquad (4,0), \qquad (8/3,\, 8/3), \qquad (0,4).$$

The corner $(4,0)$ comes from the first line at $x_2 = 0$; the corner $(0,4)$ comes from the second line at $x_1 = 0$; the corner $(8,0)$ implied by the second line is cut off by the first line and is therefore not feasible. To find the intersection we solve the two equalities. Doubling the first gives $4x_1 + 2x_2 = 16$. Subtracting the second, $x_1 + 2x_2 = 8$, yields $3x_1 = 8$, so $x_1 = 8/3$, and substituting back gives $x_2 = 8 - 2(8/3) = 8/3$. Both are positive, so this point is in the feasible set.

Evaluating the objective at each corner:

The largest value is $560/3 \approx 186.67$ at corner C, where both resources are exactly exhausted. Checking the algebra: $40 \cdot \tfrac{8}{3} = \tfrac{320}{3}$ and $30 \cdot \tfrac{8}{3} = \tfrac{240}{3}$, and the sum is $\tfrac{320}{3} + \tfrac{240}{3} = \tfrac{560}{3}$. Because the objective is linear and the feasible set is a polygon, the maximum must occur at a corner, so we have solved the continuous problem exactly without any software. The slack columns are worth reading alongside the profit: at C both are zero, which is the geometric signature of a vertex formed by two binding constraints.

Now suppose pallets cannot be split. We enumerate every lattice point with $0 \leq x_1 \leq 4$ and $0 \leq x_2 \leq 4$ and keep those satisfying both inequalities $2x_1 + x_2 \leq 8$ and $x_1 + 2x_2 \leq 8$. The feasible lattice points are exactly those whose coordinates satisfy both resource limits, because nonnegativity and the resource limits rule out any coordinate above 4, independently of the objective. The top candidates, ranked by profit $40x_1 + 30x_2$, are:

The best integer plan is $x_1 = 3$, $x_2 = 2$ with profit $40 \cdot 3 + 30 \cdot 2 = 180$, leaving one labour-hour idle ($8 - (3 + 2\cdot 2) = 1$) and no machine-hours idle ($8 - (2\cdot 3 + 2) = 0$). Note how close the top candidates are: $(2,3)$ earns 170 and $(3,2)$ earns 180, a ten-unit difference produced by swapping which resource is left slack. Rounding the continuous optimum $2.667, 2.667$ to $(3,3)$ would have been a mistake, since $2 \cdot 3 + 3 = 9 > 8$ violates the machine constraint; rounding down to $(2,2)$ loses 40 units of profit. Rounding is a heuristic with no general feasibility or optimality guarantee; this example shows infeasibility when rounding up and lost profit when rounding down.

Finally we quantify how much the integer restriction costs. In minimization form the integer optimum is $z_{\text{inc}} = -180$ and the LP relaxation bound is $z_{\text{LB}} = -560/3$; using profit values directly gives the same relative gap,

$$\begin{aligned} \text{gap} &= \frac{z_{\text{inc}} - z_{\text{LB}}}{\lvert z_{\text{inc}} \rvert} && \text{(relative gap definition)} \\ &= \frac{(-180) - (-560/3)}{\lvert -180 \rvert} && \text{(substitute incumbent and bound)} \\ &= \frac{20/3}{180} = \frac{1}{27} && \text{(simplify numerator and denominator)} \\ &\approx 0.0370. && \text{(evaluate)} \end{aligned}$$

The gap relative to the integer profit is $1/27\approx3.70\%$. This quantifies the initial LP bound's looseness. Enumeration has already established that 180 is the exact integer optimum for this tiny model. A MILP solver that certifies that optimum can tighten its search bound to 180 and report a zero final gap.