2025年Wolsey "强整数规划“ 建模的+Leapms实践——无产能批量问题

大家好，我是讯享网，很高兴认识大家。

Wolsey "强整数规划“ 建模的+Leapms实践——无产能批量问题

《整数规划》^[1]一书作者L. A. Wolsey对批量问题（Lot-sizing Problem)做了不少“强”整数规划建模^[2-5]，不是management science就是operations research，大师呀。

一个“弱”整数规划模型可以通过添加约束使之变“强” (Strong)。由于所添加的约束是线性不等式约束，就是空间上的平面并且把空间分成两半，一半留在可行解空间里，一半排除出可行解空间，于是这种约束就被叫成“割平面”(cutting plane)。

本帖记录用+Leapms对模型强化过程的实践，几乎是一个可以跟随的教程贴。如果没有+Leapms在手上，用其他建模语言和求解器也一样可以做，不过就是麻烦些。

本帖是本博客原创，本博客不转贴他人贴（除非今后说明）。

无产能批量问题（Uncapacited Lot-sizing Problem)

考虑在未来T个周期的生产-存贮问题，t (t=1,...,T) 周期的产品需求为d[t], 单位生产费用为p[t], 单位存贮费用为h[t], 生产的固定性费用为 f[t]。要求制定生产t周期的生产量 x[t]，使得总费用最少。

这里的矛盾是：如果生产过于频繁，则要付出更多的固定性费用；如果一次生产过多，则需要付出更多存贮费，且各个周期的生产费用是不同的，应该尽量避免在高生产费用的周期生产。

各个符号有英文涵义：d[t] -- demand at time t; p[t] -- production cost at time t; h[t] -- holding cost at time t; f[t] - fixed cost at time t。

假设产能是无限的，即x[t]可以取到所有d[t]的和，因此叫做无产能批量问题。

这个例子在Wolsey书的223-227页。

设$s_t$是t时间的库存，Wolse 是这样描述模型的：

讯享网

上面的第一行是说要极小化总费用；第二行是约束。熟悉+Leapms的同学知道上面的$x_t$就是x[t]了。

上面的第二行包括两个约束式，第一个是说阶段t-1的库存加上t阶段的生产等于t阶段的需求加上t阶段的库存，显然符合逻辑。就是这个：

第二个是说如果在t时间内生产，则0-1变量$y_t$必须是1。这个$y_t$表示t阶段是否有生产，它要在目标里面乘上$f$, 即$fy$。

对这样的描述写成+Leapms只需要一分钟。但是写之前最好能弄些d,p,h,f的数据，否则是无本之木，没法实践。还好Wolsey给出了数据，在224页第五段：

但是，Wolsey忘记给 p[t]了！发邮件给他被退回，好像老先生已经退休了。似乎实践要泡汤了。

不过思考一下没事的，因为p在研究强模型时候并不重要，只不过我们没法精准复现Wolsey的数据了，但是只要能复现模型由弱变强的性质就好。

首先我们要把“弱”模型写出来，就是这个：

min sum{t=1,...,T}(h[t]s[t]+f[t]y[t]) subject to s[t-1]+x[t]=d[t]+s[t] | t=1,...,T x[t]<=M*y[t]|t=1,...,T s[0]=0 where T,M are numbers d,h,f are sets s[t] is a variable of nonnegative number|t=0,...,T x[t] is a variable of nonnegative number|t=1,...,T y[t] is a variable of binary|t=1,...,T data_relation M=sum{t=1,...,T}d[t] data T=6 //阶段数 d={ 
 
   
 6 7 4 6 3 8}//需求 h={ 
 
   
 1 1 3 1 1 2}//单位存贮费用 f={ 
 
   
 8 12 8 6 10 23} //时间t内的生产固定费用

讯享网

2025年Wolsey "强整数规划“ 建模的+Leapms实践——无产能批量问题

Wolsey "强整数规划“ 建模的+Leapms实践——无产能批量问题

无产能批量问题（Uncapacited Lot-sizing Problem)

相关推荐