LINGO：生产计划问题

模型：有瓶颈设备的多级生产计划问题

某工厂的主要任务是通过组装生产产品 A ，用于满足外部市场需求。产品 A 的构成与组装过程见下图，即 D , E , F , G 是从外部采购的零件，先将零件 D , E 组装成部件 B ，零件 F , G 组装成部件 C ，然后将部件 B , C 组装成产品 A 出售。图中连接线上的数字表示的是组装时部件（或产品）中包含的零件（或部件）的数量（可以称为消耗系数），例如 DB 上数字“ 9 ”表示组装 1 个部件 B 需要用到 9 个零件 D ； BA 上的数字“5 ”表示组装 1 件产品 A 需要用到 5 个部件 B ；以此类推。

假设该工厂每次生产计划的计划期为 6 周（即每次制定未来 6 周的生产计划），只有最终产品 A 有外部需求，目前收到的订单的需求件数按周的分布如表 1 第 2 行所示。部件 B , C 是在该工厂最关键的设备（可以称为瓶颈设备）上组装出来的，瓶颈设备的生产能力非常紧张，具体可供能力如表 1 第 3 行所示（第 2 周设备检修，不能使用）。 B , C的能力消耗系数分别为 5 和 8 ，即生产 1 件 B 需要占用 5 个单位的能力，生产 1 件 C 需要占用 8 个单位的能力。

对于每种零部件或产品，如果工厂在某一周订购或者生产该零部件或产品，工厂需要一个与订购或生产数量无关的固定成本（称为生产准备费用）；如果某一周结束时该零部件或产品有库存存在，则工厂必须付出一定的库存费用（与库存数量成正比）。这些数据在表 1 第 5 、 6 行给出。

表1 生产计划

周次	1	2	3	4	5	6
A的外部需求	40	0	100	0	90	10
瓶颈能力	10000	0	5000	5000	1000	1000
零件编号	A	B	C	D	E	F	G
生产准备费用	400	500	1000	300	200	400	100
单位库存费用	12	0.6	1.0	0.04	0.03	0.04	0.04

按照工厂的信誉要求，目前接收的所有订单到期必须全部交货，不能有缺货；此外，不妨简单地假设目前该企业没有任何零部件或产品库存，也不希望第 6 周结束后留下任何零部件或产品库存。最后，假设不考虑生产提前期，即假设当周采购的零件马上就可用于组装，组装出来的部件也可以马上用于当周组装成品 A 。在上述假设和所给数据下，如何制定未来 6 周的生产计划。

表2 符号说明

$N$	生产项目总数
$T$	计划期长度
$K$	瓶颈资源种类数
$M$	一个充分大的正数，在模型中起到使模型线性化的作用
$d_{i,t}$	项目 i 在 t 时段的外部需求
$X_{i,t}$	项目 i 在 t 时段的生产批量
$I_{i,t}$	项目 i 在 t 时段的库存量
$Y_{i,t}$	项目 i 在 t 时段是否生产的标志（ 0 ：不生产， 1 ：生产)
$S(i)$	产品结构中项目 i 的直接后继项目集合
$r_{i,j}$	产品结构中项目 j 对项目 i 的消耗系数
$s_{i,t}$	项目 i 在 t 时段生产时的生产准备费用
$h_{i,t}$	项目 i 在 t 时段的单件库存费用
$C_{k,t}$	资源 k 在 t 时段的能力上限
$a_{k,i,t}$	项目 i 在 t 时段生产时，生产单个项目占用资源 k 的能力

对题目而言，生产项目总数 N = 7 （分别用 1 ～ 7 表示项目 A , B , C , D , E , F , G ），计划期长度T = 6 （周），瓶颈资源种类数 K = 1 。只有 A 有外部需求，所以 $d_{i,t}$ 中只有 $d_{1,t}$ 可以取非零需求，即表 1 中的第 2 行的数据，其它 $d_{i,t}$ 全部为零。参数 $s_{i,t}$ ， $h_{i,t}$ 只与项目 i 有关，而不随时段 t 变化，所以可以略去下标 t ，其数值就是表 1 中的最后两行数据。由于只有一种资源，参数 $C_{k,t}$ 可以略去下标 k ，其数值就是表 1 中的第 3 行的数据；而 $a_{k,i,t}$ 只与项目 i 有关，而不随时段 t 变化，所以可以同时略去下标 k 和 t ，即 $a_{2}$ = 5， $a_{3}$ = 8 。从图 1 中容易得到项目 i 的直接后继项目集合 S( i) 和消耗系数 $r_{i,j}$ 。已知 A 的外部总需求为 240 ，所以任何项目的产量不会超过240× 7 ×15 = 25000 （从图 1 可以知道，这里7 ×15已经是每件产品 A 对任意一个项目的最大的消耗系数了），所以取 M = 25000 足够大。

示例代码：

MODEL: 
TITLE 瓶颈设备的多级生产计划; 
SETS: 
! 定义项目集合PART，包括生产准备费Setup、单件库存成本Hold、对瓶颈资源的消耗系数A; 
PART/A B C D E F G/:Setup,Hold,A; 
! 定义计划期集合TIME，包括瓶颈设备的能力Capacity; 
TIME/1..6/:Capacity; 
! 定义项目结构关系USES，以及项目之间的消耗系数Req; 
USES(PART,PART):Req; 
! 定义项目与时间的派生集合PXT，包括外部需求Demand、产量X（批量）、0/1变量Y、库存Inv; 
PXT(PART,TIME):Demand,X,Y,Inv; 
ENDSETS 
! 目标函数定义：最小化总生产准备费和总单件库存成本; 
[OBJ]Min=@sum(PXT(i,t):setup(i)*Y(i,t)+hold(i)*Inv(i,t)); 
! 物流平衡方程; 
@FOR(PXT(i,t)|t #eq# 1:[Ba0]X(i,t)-Inv(i,t)= 
Demand(i,t)+@SUM(USES(i,j):Req(i,j)*X(j,t))); 
@FOR(PXT(i,t)|t #NE# 1:[Bal]Inv(i,t-1)+X(i,t)-Inv(i,t)= 
Demand(i,t)+@SUM(USES(i,j):Req(i,j)*X(j,t))); 
! 能力约束：确保每个计划期内瓶颈设备的总消耗不超过其能力; 
@FOR(TIME(t):[Cap]@SUM(PART(i):A(i)*X(i,t))<Capacity(t)); 
! 其它约束; 
M = 25000; 
@FOR(PXT(i,t):X(i,t)<=M*Y(i,t)); 
@FOR(PXT:@BIN(Y)); 
DATA: 
Demand=0;Req =0; 
Capacity=10000 0 5000 5000 1000 1000; 
Setup=400 500 1000 300 200 400 100; 
Hold=12 0.6 1.0 0.04 0.03 0.04 0.04; 
A=0 5 8 0 0 0 0; 
ENDDATA 
CALC: 
demand(1,1)=40;demand(1,3)=100; 
demand(1,5)=90;demand(1,6)=10; 
req(2,1)=5;req(3,1)=7;req(4,2)=9; 
req(5,2)=11;req(6,3)=13;req(7,3)=15; 
ENDCALC 
END

运行结果：

可得：

周次	1	2	3	4	5	6
A的产量	40		100		100
B的产量	200		1000
C的产量	1055			625
D的产量	1800		9000
E的产量	2200		11000
F的产量	13715			8125
G的产量	15825			9375

优化：

用 i = 1,2,...,7 依次表示项目 A, B,C, D, E, F,G ；

t = 1,2,...， 6 分别表示第 1 周，第 2 周，…，第 6 周；

$x_{i,t}$ ：项目 i 在 t 时刻的生产批量

$y_{i,t}$ ：其为1表示项目 i 在在 t 时刻生产，其为0表示项目 i 在 t 时刻不生产

$z_{i,t}$ ：项目 i 在 t 时刻的库存量

$r_{i,j}$ ：项目 j 对项目 i 的消耗系数

$s_{i}$ ：项目 i 的准备费用

$h_{i}$ ：项目 i 的单件库存费用

$c_{t}$ ：t 时刻资源的能力上限

$a_{i}$ ：生产单件项目 i 占用资源的能力

$d_{t}$ ： t 时刻项目 A 的外部需求

$N(i)$ ：项目 i 的直接后继项目集合

优化代码：

MODEL: 
SETS: 
PART/A B C D E F G/:s,h,a; 
TIME/1..6/:c,d; 
link1(PART,PART):r; 
link2(PART,TIME):x,y,z; 
ENDSETS 
[OBJ]Min=@sum(link2(i,t):s(i)*y(i,t)+h(i)*z(i,t)); 
! 物流平衡方程; 
[ACON0] x(1,1)-z(1,1)=d(1); 
@FOR(time(t)|t #gt# 1:[ACON] z(1,t-1)+x(1,t)-z(1,t)=d(t)); 
@FOR(PART(i)|i#ne#1: 
[NONA0]x(i,1)-z(i,1)=@SUM(part(j):r(i,j)*x(j,1))); 
@FOR(link2(i,t)|i#ne#1 #and# t #ne# 1: 
[NONA] z(i,t-1)+x(i,t)-z(i,t)=@SUM(part(j):r(i,j)*x(j,t))); 
! 能力约束; 
@FOR(TIME(t):[Cap]@SUM(PART(i):a(i)*x(i,t))<c(t)); 
! 其它约束; 
M = 250000; 
@FOR(link2:x<=M*y); @FOR(link2:@BIN(y)); 
DATA: 
r=0; 
d=40 0 100 0 90 10; 
c=10000 0 5000 5000 1000 1000; 
s=400 500 1000 300 200 400 100; 
h=12 0.6 1.0 0.04 0.03 0.04 0.04; 
a=0 5 8 0 0 0 0; 
ENDDATA 
CALC: 
r(2,1)=5;r(3,1)=7;r(4,2)=9;r(5,2)=11;r(6,3)=13;r(7,3)=15; 
ENDCALC 
END

运行结果：