Product Mix Problem

The product mix problem is the decision of how much of each product to produce in a single-period horizon (typically a week or a month). Given unit contribution margins $c_i$, per-product resource consumption coefficients $a_{r,i}$ (machine hours/unit, raw material kg/unit, labour hours/unit), resource capacities $b_r$, and per-product demand ceilings $d_i$, the decision variables are quantities $x_i$. The linear model is max $\sum_i c_i x_i$ subject to $\sum_i a_{r,i} x_i \le b_r$, $x_i \le d_i$, $x_i \ge 0$, and it is the canonical first industrial application of **linear programming (LP)**. After George B. Dantzig's 1947 simplex algorithm, it spread first across oil refineries in the 1950s (gasoline/diesel/asphalt mix from refinery output for maximum profit), then across all manufacturing and food industry. Standard solution is simplex or interior-point in seconds; the output gives the optimum mix, **shadow prices** (marginal value of one additional hour of bottleneck capacity) and slacks. Integer quantities are handled by MIP; demand uncertainty by two-stage stochastic LP or robust LP (Bertsimas and Sim 2004). Eliyahu Goldratt's (1984) **theory of constraints** complements this with the intuitive rule: prioritize the product with the highest **contribution per bottleneck-resource hour**, not the one with the highest unit price.