435. Capacity-Constrained

435.1. Capacity-constrained multi-product newsvendor

Relax two dimensions from basic newsvendor: number of items > 1 and capacity is constrained. Each product has its own demand and cost structure, but they share a budget, warehouse space, or other resource.

Without the constraint, each product is its own newsvendor — ${𝑄}_{𝑖}^{\ast }={𝜇}_{𝑖}+{𝑧}_{𝑖}^{\ast }{𝜎}_{𝑖}$ at its own critical ratio ${\text{CR}}_{𝑖}={𝐶}_{𝑢}^{𝑖}/\left({𝐶}_{𝑢}^{𝑖}+{𝐶}_{𝑜}^{𝑖}\right)$. With a shared constraint, those individual optima may not all be achievable — the constraint forces trade-offs.

435.1.1. Setup

$𝑛$ products. For each $𝑖$:

• Demand ${𝐷}_{𝑖}\sim \mathrm{𝒩︀}\left({𝜇}_{𝑖},{𝜎}_{𝑖}^2\right)$
• Costs: ${𝑃}_{𝑖},{𝐶}_{𝑖},{𝑆}_{𝑖}$ → ${𝐶}_{𝑢}^{𝑖}={𝑃}_{𝑖}-{𝐶}_{𝑖}$, ${𝐶}_{𝑜}^{𝑖}={𝐶}_{𝑖}-{𝑆}_{𝑖}$
• Resource consumption: ${𝑣}_{𝑖}$ per unit of product $𝑖$ (e.g., $ if budget-constrained, ft³ if space-constrained)

Constraint:

If individual optima already satisfy the constraint, use them. The interesting case is when ${\sum }_{𝑖}{𝑣}_{𝑖}{𝑄}_{𝑖}^{\text{ind}}>𝑉$ — must shrink.

435.1.2. Lagrangian

Maximize total expected profit subject to the capacity constraint:

where $𝐸\left[{\mathrm{\Pi }}_{𝑖\left({𝑄}_{𝑖}\right)}\right]$ is the basic newsvendor expected profit for product $𝑖$.

Lagrangian (with multiplier $𝜆\ge 0$):

435.1.3. Modified critical ratio

Take $𝜕𝐿/𝜕{𝑄}_{𝑖}=0$ for each $𝑖$:

For continuous demand, $𝜕𝐸\left[{\mathrm{\Pi }}_{𝑖}\right]/𝜕{𝑄}_{𝑖}=\left(1-{𝐹}_{𝑖\left({𝑄}_{𝑖}\right)}\right){𝐶}_{𝑢}^{𝑖}-{𝐹}_{𝑖\left({𝑄}_{𝑖}\right)}{𝐶}_{𝑜}^{𝑖}$ (from the marginal-analysis derivation in basic newsvendor). Setting equal to $𝜆{𝑣}_{𝑖}$:

Compare to basic: ${𝐹}_{𝑖\left({𝑄}_{𝑖}^{\text{basic}}\right)}={𝐶}_{𝑢}^{𝑖}/\left({𝐶}_{𝑢}^{𝑖}+{𝐶}_{𝑜}^{𝑖}\right)$. The constraint reduces each product’s effective critical ratio by $𝜆{𝑣}_{𝑖}/\left({𝐶}_{𝑢}^{𝑖}+{𝐶}_{𝑜}^{𝑖}\right)$ — products that consume more capacity per unit get bigger CR cuts, ordering less.

Effective per-product CR:

When $𝜆{𝑣}_{𝑖}\ge {𝐶}_{𝑢}^{𝑖}$, the effective CR goes negative — that product is not worth ordering at all given the constraint.

435.1.4. Find $𝜆$

$𝜆$ is chosen so that ${\sum }_{𝑖}{𝑣}_{𝑖}{𝑄}_{𝑖}^{\ast }\left(𝜆\right)=𝑉$. One equation, one unknown — bisection works (the LHS is monotone decreasing in $𝜆$).

435.1.5. Algorithm

1. Compute unconstrained ${𝑄}_{𝑖}^{\text{basic}}={𝜇}_{𝑖}+{\mathrm{\Phi }}^{-1}\left({\text{CR}}_{𝑖}^{\text{basic}}\right){𝜎}_{𝑖}$.
2. Check ${\sum }_{𝑖}{𝑣}_{𝑖}{𝑄}_{𝑖}^{\text{basic}}\le 𝑉$. If yes, done.
3. Else, find $𝜆>0$ such that ${\sum }_{𝑖}{𝑣}_{𝑖}{𝑄}_{𝑖}^{\ast }\left(𝜆\right)=𝑉$ (bisection).
4. Each ${𝑄}_{𝑖}^{\ast }={𝜇}_{𝑖}+{\mathrm{\Phi }}^{-1}\left({\text{CR}}_{𝑖\left(𝜆\right)}\right){𝜎}_{𝑖}$.