切割库存问题

下料问题（cutting stock problem）把标准长度、宽度或面积的原材料切成若干规格，以满足订单数量，并优化原材料用量、废料或成本。最简单的一维模型只计可相加的长度；切缝、边缘损耗、可回收余料及多种母材都需要单独加入条件。

现有长度十米的母材，要切出三根六米和两根四米成品。每根母材最多容纳一根六米；因此至少需要三根母材。用两根各切成六加四，第三根只切六，恰好满足需求，共用三十米，成品总长二十六米，余料四米。这个构造与下界一致，已给出最优原材料数量。

以切割模式为变量

设规格长度 ${\ell }_i>0$、订单数 $d_i\in {\mathbb{Z}}_{\ge 0}$，母材长 $L$。一种模式为非负整数向量 $a=(a_1,\dots ,a_m)$，表示该根母材切出每种规格的件数，须满足 $$\sum _i{\ell }_i{a}_i\le L.$$ 这里左边必须乘规格长度；只把件数相加不能检验能否放进原材料。主例的所有非空模式为 $(1,1),(1,0),(0,2),(0,1)$。

对每种模式 $a\in 𝒫$，令 $x_a$ 为使用次数。允许超额成品时，最少母材模型是 $$\begin{array}{cc}min& \sum _{a\in 𝒫}{x}_a,\\ \sum _{a\in 𝒫}{a}_i{x}_a& \ge d_i(i=1,\dots ,m),\\ x_a& \in {\mathbb{Z}}_{\ge 0}.\end{array}$$ 若严格禁止多切，需求行应改成等号。主例最优使用 $x_{(1,1)}=2$、$x_{(1,0)}=1$，其余为零，无论允许超额与否都可行且最优。

前两根没有余料，第三根的虚线段为四米余料。按规格汇总后的件数，与逐根切割结果完全对应。

用资源与规格分别给下界

总长度只给出 $\lceil 26/10\rceil =3$ 的下界。此例还可由六米规格每根最多一件得到下界三。这种规格下界有时比总长度更强：若需要三根六米而不需要四米，总长度下界仅二，但规格下界仍为三。

证明一般长度下界时，将所有需求行分别乘以 ${\ell }_i$ 后相加。因为每个模式至多使用 $L$ 米，任何可行方案满足 $$\sum _i{\ell }_i{d}_i\le \sum _a{x}_a\sum _i{\ell }_i{a}_i\le L\sum _a{x}_a.$$ 对非负整数母材次数取整，得到所述下界。若允许多切，最少母材数量与最少废料不一定等价：额外切出的产品不能未经约定就算作已完成的原订单，库存或处置代价也可能重要。

模式数量与列生成

即使规格数不多，全部可行模式也可能很多。枚举模式相当于把原材料内部的装法预先整理成列，然后由整数规划决定用多少次。列生成则先只选少数模式解连续松弛，再通过对偶价格寻找有改善作用的新模式。

删除整数要求后，变量可以是母材根数的分数，只是求下界的数学工具，不能直接交给切割设备执行。对连续最优次数逐项向上取整通常能满足“至少需求”的约束，却可能浪费原料；也不能保证已经生成了整数最优解需要的所有模式。

变式。 改成一根六米、三根四米。总长度十八米，下界两根；用模式六加四一次、四加四一次恰好两根，达到下界。若母材每刀有宽度损耗，应先说明切出 $k$ 件时需要多少刀以及是否切掉边料，再把相应损耗加入模式可行条件，不能仍用未经修正的长度和。

下料与装箱问题在忽略切缝、原材料同型且成品件数固定时可以互相转化：每件成品当作一个待装物品。但当允许超额生产、余料跨期复用或多种母材成本不同时，需要保留各自的业务条件。