基于Excel的木板下料优化：约束建模与无VBA实现咨询

二维下料问题约束数学建模 #

前置符号定义

• 两类基材板：规格1尺寸为L1 × l1，单块面积$S_1 = L1 \times l1$，总使用量为$n_1$；规格2尺寸为L2 × l2，单块面积$S_2 = L2 \times l2$，总使用量为$n_2$
• 待生产成品共$m$种，第$i$种成品尺寸为$a_i × b_i$，需求数量为$k_i$，单块面积$s_i = a_i \times b_i$
• 0-1决策变量$x_{ijp}$：取值为1代表第$i$种成品的第$j$个副本，裁切自第$p$块基材板；为0则反之
• 0-1决策变量$y_{pq}$：取值为1代表第$p$块基材板采用规格$q$（$q=1$对应L1×l1，$q=2$对应L2×l2），每块基材仅能选一种规格，因此对任意$p$满足$y_{p1} + y_{p2} = 1$
• 连续变量$u_{ijp}$、$v_{ijp}$：分别为第$i$种成品的第$j$个副本，在所属第$p$块基材板上的左下角横、纵坐标（以基材板左下角为坐标原点）

核心约束表达式

1. 单块成品完整归属约束（你需要的不可拆分拼接约束）
   对任意第$i$种成品的任意第$j$个副本，有且仅有一块基材板承接它：
   $$\sum_{p} x_{ijp} = 1 \quad \forall i \in [1,m], \forall j \in [1,k_i]$$

2. 成品尺寸适配约束
   成品放置不能超出所属基材的物理边界：
   $$x_{ijp} \times (u_{ijp} + a_i) \leq y_{p1} \times L1 + y_{p2} \times L2 \quad \forall i,j,p$$
   $$x_{ijp} \times (v_{ijp} + b_i) \leq y_{p1} \times l1 + y_{p2} \times l2 \quad \forall i,j,p$$
   如果允许成品旋转90度裁切，仅需将上式中的$a_i、b_i$替换为可互换的两个维度即可

3. 同基材成品不重叠约束
   对任意两块放在同一块基材上的不同成品，必须满足横向/纵向至少一个方向完全错开：
   $$u_{ijp} + a_i \leq u_{i'j'p} + M \times (1 - z_{ii'jj'p})$$
   $$u_{i'j'p} + a_{i'} \leq u_{ijp} + M \times z_{ii'jj'p}$$
   $$v_{ijp} + b_i \leq v_{i'j'p} + M \times (1 - w_{ii'jj'p})$$
   $$v_{i'j'p} + b_{i'} \leq v_{ijp} + M \times w_{ii'jj'p}$$
   其中$z_{ii'jj'p}、w_{ii'jj'p}$为0-1变量，$M$为足够大的常数（可取两类基材最大边长的2倍即可）

仅用基础Excel功能实现的可行性 #

• 如果你的成品种类≤5种、单批次总需求数量≤20块，且仅2种基材规格，可以用内置的「规划求解」功能实现：按照上述变量定义在单元格中写入约束，选择「演化求解」方法即可得到近似最优解
• 如果成品种类、总需求更大，普通版本Excel的规划求解有决策变量数量上限（最高支持200个左右变量），且演化求解耗时会指数级上升，大概率无法得到可行解，该场景建议使用专门的下料优化工具计算。

内容的提问来源于stack exchange，提问作者AlexJJ