优化建模生产与服务运作管理中的优化问题优化建模与 LINDO/LINGO软件第 5章优化建模内容提要
§ 5.1 生产与销售计划问题
§ 5.2 有瓶颈设备的多级生产计划问题
§ 5.3 下料问题
§ 5.4 面试顺序与消防车调度问题
§ 5.5 飞机定位和飞行计划问题优化建模
§ 5.1 生产与销售计划问题优化建模
§ 5.1.1问题实例
例 5.1某公司用两种原油（ A和 B）混合加工成两种汽油（甲和乙）。甲、乙两种汽油含原油 A的最低比例分别为 50%和 60%，每吨售价分别为 4800元和
5600元。该公司现有原油 A和 B的库存量分别为 500
吨和 1000吨，还可以从市场上买到不超过 1500吨的原油 A。原油 A的市场价为：购买量不超过 500吨时的单价为 10000元 /吨；购买量超过 500吨但不超过 1000吨时，超过 500吨的部分 8000元 /吨；购买量超过 1000吨时，超过 1000吨的部分 6000元 /吨。
该公司应如何安排原油的采购和加工。
优化建模
§ 5.1.2建立模型问题分析安排原油采购、加工的目标是利润最大，题目中给出的是两种汽油的售价和原油 A的采购价，利润为销售汽油的收入与购买原油 A的支出之差。这里的难点在于原油 A的采购价与购买量的关系比较复杂，
是分段函数关系，能否及如何用线性规划、整数规划模型加以处理是关键所在。
优化建模模型建立设原油 A的购买量为 x（吨），根据题目所给数据，
采购的支出 c(x)可表为如下的分段线性函数（以下价格以千元 /吨为单位）：
5 0 0 )1( 1 0 0 0 63 0 0 0
1 0 0 0 )( 5 0 0 81 0 0 0
5 0 0 )(0 10
)(
xx
xx
xx
xc
(1)
设原油 A用于生产甲、乙两种汽油的数量分别为 x11和 x12（吨），
原油 B用于生产甲、乙两种汽油的数量分别为 x21和 x22（吨），
则总的收入为 4.8(x11+x21)+5.6(x12+x22)（千元）。
于是本例的目标函数（利润）为
)()(6.5)(8.4 22122111 xcxxxxzM ax (2)
优化建模约束条件包括加工两种汽油用的原油 A、原油 B库存量的限制，
和原油 A购买量的限制，以及两种汽油含原油 A的比例限制，
它们表示为
xxx 5 0 01211 （ 3）
1 0 0 02221 xx （ 4）
1500?x （ 5）
5.0
2111
11?
xx
x
（ 6）
6.0
2212
12?
xx
x
（ 7）
0,,,,22211211?xxxxx （ 8）
由于（ 1）式中的 c(x)不是线性函数，（ 1） ~（ 8）给出的是一个非线性规划。而且，对于这样用分段函数定义的 c(x)，
一般的非线性规划软件也难以输入和求解。能不能想办法将该模型化简，从而用现成的软件求解呢？
优化建模
§ 5.1.3 求解模型 3种解法第 1种解法 将原油 A的采购量 x分解为三个量，即用 x1，
x2,x3分别表示以价格 10,8,6千元 /吨采购的原油 A的吨数，总支出为 c(x) = 10x1+8x2+6x3，且
321 xxxx
(9)
这时目标函数（ 2）变为线性函数：
)6810()(6.5)(8.4 32122122111 xxxxxxxzM a x (10)
应该注意到，只有当以 10千元 /吨的价格购买
x1=500（吨）时，才能以 8千元 /吨的价格购买 x2
（ >0），这个条件可以表示为
0)500( 21 xx (11)
优化建模同理，只有当以 8千元 /吨的价格购买 x2=500（吨）时，
才能以 6千元 /吨的价格购买 x3（ >0），于是
0)5 0 0( 32 xx (12)
此外,x1,x2,x3的取值范围是
5 0 0,,0 321 xxx (13)
优化建模由于有非线性约束 (11),(12),(3)~(13)构成非线性规划模型。 LINGO程序：
Model:
Max= 4.8*x11 + 4.8*x21 + 5.6*x12 + 5.6*x22 - 10*x1 - 8*x2 - 6*x3;
x11+x12 < x + 500;
x21+x22 < 1000;
0.5*x11 - 0.5*x21 > 0;
0.4*x12 - 0.6*x22 > 0;
x=x1+x2+x3;
(x1 - 500) * x2=0;
(x2 - 500) * x3=0;
@bnd(0,x1,500);
@bnd(0,x2,500);
@bnd(0,x3,500);
end
优化建模将文件存储并命名为 exam0501a.lg4，
执行菜单命令,LINGO|Solve”,运行该程序得到：
Local optimal solution found.
Objective value,4800.000
Total solver iterations,26
Variable Value Reduced Cost
X11 500.0000 0.000000
X21 500.0000 0.000000
X12 0.000000 0.000000
X22 0.000000 0.000000
X1 0.000000 0.000000
X2 0.000000 0.000000
X3 0.000000 0.000000
X 0.000000 0.000000
优化建模最优解,用库存的 500吨原油 A,500吨原油 B生产 1000
吨汽油甲，不购买新的原油 A，利润为 4800（千元）
但是此时 LINGO得到的结果只是一个 局部最优解可以用菜单命令,LINGO|Options” 在,Global
Solver” 选项卡上启动全局优化（ Use Global
Solver）选项，然后重新执行菜单命令
,LINGO|Solve”,得到：
Global optimal solution found.
Objective value,5000.002
Extended solver steps,3
Total solver iterations,187
优化建模
Variable Value Reduced Cost
X11 0.000000 0.000000
X21 0.000000 0.000000
X12 1500.000 0.000000
X22 1000.000 0.000000
X1 500.0000 0.000000
X2 499.9990 0.000000
X3 0.9536707E-03 0.000000
X 1000.000 0.000000
此时 LINGO得到的结果是一个 全局最优解
（ Global optimal solution）：购买 1000吨原油 A，
与库存的 500吨原油 A和 1000吨原油 B一起，共生产
2500吨汽油乙，利润为 5000（千元），高于刚刚得到的局部最优解对应的利润 4800（千元）。
优化建模第 2种解法,
引入 0-1变量将（ 11）和（ 12）转化为线性约束令 y1=1,y2=1,y3=1分别表示以 10千元 /吨,8千元
/吨,6千元 /吨的价格采购原油 A，则约束（ 11）
和（ 12）可以替换为
112 500500 yxy
223 5 0 05 0 0 yxy
33 5 0 0 yx?
(14)
(15)
(16)
y1,y2,y3 =0或 1 (17)
优化建模
（ 3） ~（ 10），（ 13） ~（ 17）构成混合整数线性规划模型，将它输入 LINDO软件：
优化建模
Max 4.8x11+4.8x21+5.6x12+5.6x22-10x1-8x2-6x3
st
x-x1-x2-x3=0
x11+x12-x<500
x21+x22<1000
0.5x11-0.5x21>0
0.4x12-0.6x22>0
x1-500y1<0
x2-500y2<0
x3-500y3<0
x1-500y2>0
x2-500y3>0
end
int y1
int y2
int y3
优化建模运行该程序得到,
OBJECTIVE FUNCTION VALUE
1) 5000.000
VARIABLE VALUE REDUCED COST
Y1 1.000000 0.000000
Y2 1.000000 2200.000000
Y3 1.000000 1200.000000
X11 0.000000 0.800000
X21 0.000000 0.800000
X12 1500.000000 0.000000
X22 1000.000000 0.000000
X1 500.000000 0.000000
X2 500.000000 0.000000
X3 0.000000 0.400000
X 1000.000000 0.000000
这个结果与前面非线性规划模型用全局优化得到的结果相同。
优化建模第 3种解法 直接处理分段线性函数 c(x)。
（ 1）式表示的函数 c(x)如图 5-1。
c(x)
x
12000
9000
5000
0 500 1000 1500
图 5-1 分段线性函数 c(x)图形优化建模记 x轴上的分点为 b1=0,b2=500,b3=1000,b4=1500。当 x在第 1个小区间 [b1,b2]时，记 x= z1b1+z2b2,z1+z2=1,z1,z2≥0,因为 c(x)在 [b1,
b2]是线性的，所以 c(x)= z1c(b1)+z2c(b2)。同样，当 x在第 2个小区间 [b2,b3]时,x= z2b2+z3b3,z2+z3=1,z2,z3≥0,c(x)=
z2c(b2)+z3c(b3)。当 x在第 3个小区间 [b3,b4]时,x= z3b3+z4b4，
z3+z4=1,z3,z4≥ 0,c(x)= z3c(b3)+z4c(b4)。为了表示 x在哪个小区间，
引入 0-1变量 yk(k=1,2,3)，当 x在第 k个小区间时,yk=1，否则，
yk=0。这样,z1,z2,z3,z4,y1,y2,y3应满足
3432321211,,,yzyyzyyzyz
)4,3,2,1(0,14321 kzzzzz k
10,,,1 321321 或 yyyyyy
(18)
(19)
(20)
优化建模此时 x和 c(x)可以统一地表示为
43244332211 1 5 0 01 0 0 05 0 0 zzzbzbzbzbzx
（ 2） ~（ 10），（ 18） ~（ 22）也构成一个混合整数线性规划模型，可以用 LINDO求解。不过，我们还是将它输入
LINGO软件，因为其扩展性更好（即当分段函数的分段数更多时，只需要对下面程序作很小的改动）。输入的
LINGO模型如下：
43244332211 1 2 0 0 09 0 0 05 0 0 0)()()()()( zzzbczbczbczbczxc
(22)
优化建模输入的 LINGO模型如下：
Model:
SETS:
Points/1..4/,b,c,y,z;! 端点数为 4，即分段数为 3;
ENDSETS
DATA:
b=0 500 1000 1500;
c=0 5000 9000 12000;
y=,,,0; ! 增加的虚拟变量 y(4)=0;
ENDDATA
优化建模
Max= 4.8*x11 + 4.8*x21 + 5.6*x12 + 5.6*x22 -
@sum(Points,c*z);
x11+x12 < x + 500;
x21+x22 < 1000;
0.5*x11 - 0.5*x21 > 0;
0.4*x12 - 0.6*x22 > 0;
@sum(Points,b*z)=x;
@for(Points(i)|i#eq#1,z(i) <= y(i));
@for(Points(i)|i#ne#1,z(i) <= y(i-1)+y(i));
@sum(Points,y)=1;
@sum(Points,z)=1;
@for(Points,@bin(y));
end
优化建模求解，得到的结果如下（略去已知参数 b和 c的显示结果）：
Global optimal solution found.
Objective value,5000.000
Extended solver steps,0
Total solver iterations,28
优化建模
Variable Value Reduced Cost
X11 0.000000 0.000000
X21 0.000000 1.600000
X12 1500.000 0.000000
X22 1000.000 0.000000
X 1000.000 0.000000
Y( 1) 0.000000 -4600.000
Y( 2) 0.000000 -1200.000
Y( 3) 1.000000 0.000000
Y( 4) 0.000000 0.000000
Z( 1) 0.000000 0.000000
Z( 2) 0.000000 0.000000
Z( 3) 1.000000 0.000000
Z( 4) 0.000000 200.0000
优化建模可见，得到的最优解和最优值与第 2种解法相同。
备注 这个问题的关键是处理分段线性函数，我们推荐化为整数线性规划模型的第 2,3种解法，第 3种解法更具一般性，其做法如下。
设一个 n段线性函数 f(x)的分点为
11 nn bbb?
引入 zk 将 x和 f(x)表示为
1
1
n
k
kk bzx
1
1
)()(
n
k
kk bfzxf
(23)
(24)
优化建模
zk 和 0-1变量 yk满足
nnnnn yzyyzyyzyz 1121211,,,,?
10,121 或 kn yyyy?
)1,,2,1(01121 nkzzzz kn,
(25)
(26)
(27)
优化建模
§ 5.2 有瓶颈设备的多级生产计划问题优化建模
§ 5.2.1 问题实例在给定的外部需求和生产能力等限制条件下，按照生产总费用最小编制未来若干个生产周期的最优生产计划，这种问题在文献上一般称为批量问题
（ Lotsizing Problems）。
我们通过下面的具体例子来说明这种多级生产计划问题的优化模型。这里“多级”的意思是需要考虑产品是通过多个生产阶段（工艺过程）生产出来的。
优化建模例 5.2 某工厂的主要任务是通过组装生产产品 A，
用于满足外部市场需求。
A产品的产品构成与组装过程见图 5-2：即 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；
依此类推。
优化建模瓶颈设备加工
A
B C
D E F G
5 7
9 11 13 15
图 5-2 产品构成与组装过程图优化建模表 5-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周（即每次制定未来 6
周的生产计划），只有最终产品 A有外部需求，目前收到的订单的需求件数按周的分布如表 5-1第 2行所示。部件 B,C
是在该工厂最关键的设备（可以称为瓶颈设备）上组装出来的，瓶颈设备的生产能力非常紧张，具体可供能力如表 5-1
第 3行所示（第 2周设备检修，不能使用）。 B,C的能力消耗系数分别为 5和 8，即生产 1件 B需要占用 5个单位的能力，
即生产 1件 C需要占用 8个单位的能力。
对于每种零部件或产品，如果工厂在某一周订购或者生产该零部件或产品，工厂需要付出一个与订购或生产数量无关的固定成本（称为生产准备费用）；如果某一周结束时该零部件或产品有库存存在，则工厂必须付出一定的库存费用（与库存数量成正比）。这些数据在表 5-1第 5,6行给出。
优化建模按照工厂的信誉要求，目前接收的所有订单到期必须全部交货，不能有缺货发生；此外，不妨简单地假设目前该企业没有任何零部件或产品库存，也不希望第 6周结束后留下没有任何零部件或产品库存。最后，假设不考虑生产提前期，
即假设当周采购的零件马上就可用于组装，组装出来的部件也可以马上用于当周组装成品 A。
在上述假设和所给数据下，如何制定未来 6周的生产计划？
优化建模
§ 5.2.2 建立模型问题分析 这个例子考虑的是在有限的计划期内,给定产品结构、生产能力和相关费用及零部件或成品（以下统称为生产项目）在离散的时间段上（这里是周，也可以是天、月等）的外部需求之后,确定每一生产项目在每一时间段上的生产量 (即批量 ),使总费用最小,由于每一生产项目在每一时间段上生产时必须经过生产准备
(Setup),所以通常的讨论中总费用至少应考虑生产准备费用和库存费用,
其实，细心的读者一定会问：是否需要考虑生产的直接成本（如原材料成本、人力成本、电力成本等）？
优化建模符号说明为了建立这类问题的一般模型，我们定义如下数学符号：
N -------- 生产项目总数（本例中 N=7） ;
T -------- 计划期长度（本例中 T=6） ;
K -------- 瓶颈资源种类数（本例中 K=1） ;
M -------- 一个充分大的正数，在模型中起到使模型线性化的作用 ;
优化建模
dit,
----- 项目 i在 t时段的外部需求
（本例中只有产品 A有外部需求） ;
Xit,----- 项目 i在 t时段的生产批量 ;
Iit,----- 项目 i在 t时段的库存量 ;
Yit,
----- 项目 i在 t时段是否生产的标志
(0：不生产,1：生产 );
rij,----- 产品结构中项目 j对项目 i的消耗系数 ;
S(i) ----- 产品结构中项目 i的直接后继项目集合 ;
优化建模
sit,----- 项目 i在 t时段生产时的生产准备费用 ;
hit,----- 项目 i在 t时段的单件库存费用 ;
Ckt,----- 资源 k在 t时段的能力上限 ;
akit,,
--- 项目 i在 t时段生产时,生产单个产品占用资源 k
的能力 ;
δ(x) ---- 这个函数当且仅当 x>0时取值 1,否则取值 0.
在上述数学符号中，只有 Xit,Iit,Yit,为决策变量 ;
其余均为已知的计划参数。
优化建模其实，真正的生产计划只是要求确定 X
i t,
就可以了，因为知道
X i t,以后 I i t,,Y i t,也就自然确定了。另外，在我们的具体例子中参数 s
i t,
,h
i t,
,a
k i t,,
其实只与项目 i 有关，而不随时段 t 变化，
我们这里加上下标 t 只是为了使模型能够更一般化。
优化建模目标函数这个问题的目标是使生产准备费用和库存费用的总和最小。因此，目标函数应该是每个项目在每个时段上的生产准备费用和库存费用的总和，即
N
i
T
t
titititi IhYs
1 1
,,,,)(
(28)
约束条件这个问题中的约束有这么几类：每个项目的物流应该守恒、资源能力限制应该满足、每时段生产某项目前必须经过生产准备和非负约束
（对 Yi,j是 0-1约束）。
优化建模
TtNiXrdIXI
iSj tjjititititi
,,1,,,1
)(,,,,,1,
(29)
资源能力限制比较容易理解，即
TtKkCXa
N
i
tktitik,,1,,,1
1
,,,,
(30)
所谓物流守恒（假设 Ii,0 =0）
优化建模
(31)
TtNiIYMYX titititi,,1,,,10,},1,0{,0,,,,
每时段生产某项目前必须经过生产准备，也就是说当
Xit=0时 Yit=0； Xit>0时 Yit=1。这本来是一个非线性约束，
但是通过引入参数 M（很大的正数，表示每个项目每个时段的最大产量）可以化成线性约束，即：
总结,这个问题的优化模型就是在约束（ 29）（ 30）
（ 31）下使目标函数（ 28）达到最小。
优化建模
§ 5.2.3 求解模型本例生产项目总数 N=7(A,B,C,D,E,F,G),计划期长度 T=6（周），瓶颈资源种类数 K=1。只有 A
有外部需求，所以 di,t中只有 d1,t可以取非零需求，即表 5-1中的第 2行的数据，其他全部为零。 参数 si,t、
hi,t只与项目 i有关，而不随时段 t变化，所以可以略去下标 t，其数值就是表 5-1中的最后两行数据。
由于只有一种资源，参数 Ck,t可以略去下标 k，其数值就是表 5-1中的第 3行的数据；而 ak,I,t只与项目 i有关，
而不随时段 t变化，所以可以同时略去下标 k和 t，即
a2=5,a3=8（其他 ai为 0）。从图 6-2中容易得到项目 i的直接后继项目集合 S(i)和消耗系数。
优化建模准备以下的数据文件（文本文件 exam0502.LDT，可以看到其中也可以含有注释语句）：
! 项目集合 ;
A B C D E F G~
! 计划期集合 ;
1 2 3 4 5 6~
! 需求 ;
40 0 100 0 90 10
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0~
优化建模
! 能力 ;
100000 5000 5000 1000 1000~
! 生产准备费 ;
400 500 1000 300 200 400 100~
! 库存费 ;
12 0.6 1.0 0.04 0.03 0.04 0.04~
! 对能力的消耗系数；
0 5 8 0 0 0 0~
优化建模
! 项目间的消耗系数,req(i,j)表示 j用到多少 i;
0 0 0 0 0 0 0
5 0 0 0 0 0 0
7 0 0 0 0 0 0
0 9 0 0 0 0 0
0 11 0 0 0 0 0
0 0 13 0 0 0 0
0 0 15 0 0 0 0
! 数据结束 ;
优化建模对本例,A的外部总需求为 240，所以任何项目的产量不会超过 240× 7× 15<25000（从图 6-2
可以知道，这里 7× 15已经是每件产品 A对任意一个项目的最大的消耗系数了），所以取
M=25000就已经足够了。
本例中的具体模型可以如下输入 LINGO软件：
MODEL:
TITLE 瓶颈设备的多级生产计划 ;
! 从文本文件 exam0502.LDT中读取数据 ;
优化建模
SETS:
! PART = 项目集合,Setup = 生产准备费,Hold = 单件库存成本，
A = 对瓶颈资源的消耗系数 ;
PART/ @FILE( 'exam0502.LDT')/,Setup,Hold,
A;
! TIME = 计划期集合,Capacity = 瓶颈设备的能力 ;
TIME / @FILE( 'exam0502.LDT')/,Capacity;
! USES = 项目结构关系,Req = 项目之间的消耗系数 ;
USES( PART,PART),Req;
! PXT = 项目与时间的派生集合,Demand = 外部需求,
X = 产量（批量）,Y = 0/1变量,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 #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( 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( 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 = @FILE( 'exam0502.LDT');
Capacity = @FILE( 'exam0502.LDT');
Setup = @FILE( 'exam0502.LDT');
Hold = @FILE( 'exam0502.LDT');
A = @FILE( 'exam0502.LDT');
Req = @FILE( 'exam0502.LDT');
ENDDATA
END 注意：由于本例有 42个 0-1变量，
LINGO演示版是无法求解的优化建模表 5-2 生产计划的最后结果周次 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
LINDO求解,得到最优目标函数值为 9245,结果如下：
优化建模
§ 5.3 下料问题优化建模
§ 5.3 下料问题生产中常会遇到通过切割、剪裁、冲压等手段，
将原材料加工成所需大小这种工艺过程，称为原料下料（ cutting stock）问题。按照进一步的工艺要求，确定下料方案，使用料最省，或利润最大，
是典型的优化问题。本节通过两个实例讨论用数学规划模型解决这类问题的方法。
优化建模
§ 5.3.1钢管下料问题例 5.3 某钢管零售商从钢管厂进货，将钢管按照顾客的要求切割后售出。从钢管厂进货时得到的原料钢管都是 19米长。
1) 现有一客户需要 50根 4米长,20根 6米长和 15根 8米长的钢管。应如何下料最节省？
2) 零售商如果采用的不同切割模式太多，将会导致生产过程的复杂化，从而增加生产和管理成本，所以该零售商规定采用的不同切割模式不能超过 3种。
此外，该客户除需要 1）中的三种钢管外，还需要
10根 5米长的钢管。应如何下料最节省？
优化建模问题 1）的求解问题分析 首先，应当确定哪些切割模式是可行的。
所谓一个切割模式，是指按照客户需要在原料钢管上安排切割的一种组合。例如，我们可以将 19米长的钢管切割成 3根 4米长的钢管，余料为 7米显然，可行的切割模式是很多的。
其次，应当确定哪些切割模式是合理的。通常假设一个合理的切割模式的余料不应该大于或等于客户需要的钢管的最小尺寸。在这种合理性假设下，切割模式一共有 7种，如表 5-3所示。
优化建模表 5-3 钢管下料的合理切割模式
4米钢管根数 6米钢管根数 8米钢管根数 余料（米）
模式 1 4 0 0 3
模式 2 3 1 0 1
模式 3 2 0 1 3
模式 4 1 2 0 3
模式 5 1 1 1 1
模式 6 0 3 0 1
模式 7 0 0 2 3
优化建模问题化为在满足客户需要的条件下，按照哪些种合理的模式，切割多少根原料钢管，最为节省。而所谓节省，可以有两种标准，一是切割后剩余的总余料量最小，二是切割原料钢管的总根数最少。
下面将对这两个目标分别讨论。
优化建模模型建立决策变量 用 xi 表示按照第 i种模式（ i=1,2,…,7 ）
切割的原料钢管的根数，显然它们应当是非负整数。
决策目标 以切割后剩余的总余料量最小为目标，
则由表 1可得
76543211 3333 xxxxxxxZM i n (32)
以切割原料钢管的总根数最少为目标，则有
76543212 xxxxxxxZM i n (33)
下面分别在这两种目标下求解。
优化建模约束条件 为满足客户的需求，按照表 1应有
50234 54321 xxxxx
2032 6542 xxxx
152 753 xxx
优化建模模型求解
1,将（ 32），（ 34） ~（ 36）构成的整数线性规划模型
（加上整数约束）输入 LINDO如下：
Title 钢管下料 - 最小化余量
Min 3x1 + x2 + 3x3 + 3x4 + x5 + x6 + 3x7
s.t.
4x1 + 3x2 + 2x3 + x4 + x5 >= 50
x2 + 2x4 + x5 + 3x6 >= 20
x3 + x5 + 2x7 >= 15
end
gin 7
优化建模求解可以得到最优解如下：
OBJECTIVE FUNCTION VALUE
1) 27.00000
VARIABLE VALUE REDUCED COST
X1 0.000000 3.000000
X2 12.000000 1.000000
X3 0.000000 3.000000
X4 0.000000 3.000000
X5 15.000000 1.000000
X6 0.000000 1.000000
X7 0.000000 3.000000
优化建模即按照模式 2切割 12根原料钢管，按照模式 5切割 15根原料钢管，共 27根，总余料量为 27米。
显然，在总余料量最小的目标下，最优解将是使用余料尽可能小的切割模式（模式 2和 5的余料为 1米），这会导致切割原料钢管的总根数较多。
优化建模
2,将（ 33） ~（ 36）构成的整数线性规划模型
（加上整数约束）输入 LINDO：
Title 钢管下料 - 最小化钢管根数
Min x1 + x2 + x3 + x4 + x5 + x6 + x7
s.t.
4x1 + 3x2 + 2x3 + x4 + x5 >= 50
x2 + 2x4 + x5 + 3x6 >= 20
x3 + x5 + 2x7 >= 15
end
gin 7
优化建模求解，可以得到最优解如下：
OBJECTIVE FUNCTION VALUE
1) 25.00000
VARIABLE VALUE REDUCED COST
X1 0.000000 1.000000
X2 15.000000 1.000000
X3 0.000000 1.000000
X4 0.000000 1.000000
X5 5.000000 1.000000
X6 0.000000 1.000000
X7 5.000000 1.000000
优化建模即按照模式 2切割 15根原料钢管，按模式 5切割 5根，按模式 7切割 5根，共 27根，可算出总余料量为 35米。与上面得到的结果相比，总余料量增加了 8米，但是所用的原料钢管的总根数减少了 2根。在余料没有什么用途的情况下，
通常选择总根数最少为目标。
优化建模问题 2）的求解问题分析 按照解问题 1）的思路，可以通过枚举法首先确定哪些切割模式是可行的。但由于需求的钢管规格增加到
4种，所以枚举法的工作量较大。下面介绍的整数非线性规划模型，可以同时确定切割模式和切割计划，是带有普遍性的方法。
同 1）类似，一个合理的切割模式的余料不应该大于或等于客户需要的钢管的最小尺寸（本题中为 4米），切割计划中只使用合理的切割模式，而由于本题中参数都是整数，
所以合理的切割模式的余量不能大于 3米。此外，这里我们仅选择总根数最少为目标进行求解。
优化建模模型建立决策变量 由于不同切割模式不能超过 3种，可以用 xi 表示按照第 i种模式（ i=1,2,3）切割的原料钢管的根数，
显然它们应当是非负整数。 设 所使用的第 i种切割模式下每根原料钢管生产 4米长,5米长,6米长和 8米长的钢管数量分别为 r1i,r2i,r3i,r4i（ 非负整数 ）。
决策目标 以切割原料钢管的总根数最少为目标，即目标为
321 xxxM i n
（ 37）
优化建模约束条件 为满足客户的需求，应有
50313212111 xrxrxr (38)
10323222121 xrxrxr
20333232131 xrxrxr
15343242141 xrxrxr
(39)
(40)
(41)
优化建模每一种切割模式必须可行、合理，所以每根原料钢管的成品量不能超过 19米，也不能少于 16米（余量不能大于 3
米），于是
19865416 41312111 rrrr (42)
19865416 42322212 rrrr (43)
19865416 43332313 rrrr (44)
优化建模模型求解
（ 37） ~（ 44）构成这个问题的优化模型。由于在（ 38） ~
（ 41）式中出现了决策变量的乘积，所以这是一个整数非线性规划模型，虽然用 LINGO软件可以直接求解，但我们发现在较低版本的 LINGO软件中需要运行很长时间也难以得到最优解。为了减少运行时间，可以增加一些显然的约束条件，从而缩小可行解的搜索范围。
例如，由于 3种切割模式的排列顺序是无关紧要的，所以不妨增加以下约束：
321 xxx
（ 45）
优化建模又例如，我们注意到所需原料钢管的总根数有着明显的上界和下界。首先，无论如何，原料钢管的总根数不可能少于
2619 158206105504 （根）
其次，考虑一种非常特殊的生产计划：第一种切割模式下只生产 4米钢管，一根原料钢管切割成 4根 4米钢管，为满足 50根 4米钢管的需求，需要 13根原料钢管；第二种切割模式下只生产 5米,6米钢管，一根原料钢管切割成 1根 5
米钢管和 2根 6米钢管，为满足 10根 5米和 20根 6米钢管的需求，需要 10根原料钢管；
优化建模第三种切割模式下只生产 8米钢管，一根原料钢管切割成 2
根 8米钢管，为满足 15根 8米钢管的需求，需要 8根原料钢管。于是满足要求的这种生产计划共需 13+10+8=31根原料钢管，这就得到了最优解的一个上界。所以可增加以下约束：
3126 321 xxx (46)
将（ 37） ~（ 46）构成的模型输入 LINGO如下：
优化建模将（ 37） ~（ 46）构成的模型输入 LINGO如下：
model:
Title 钢管下料 - 最小化钢管根数的 LINGO模型 ;
min=x1+x2+x3;
x1*r11+x2*r12+x3*r13 >=50;
x1*r21+x2*r22+x3*r23 >=10;
x1*r31+x2*r32+x3*r33 >=20;
x1*r41+x2*r42+x3*r43 >=15;
4*r11+5*r21+6*r31+8*r41 <=19;
4*r12+5*r22+6*r32+8*r42 <=19;
4*r13+5*r23+6*r33+8*r43 <=19;
4*r11+5*r21+6*r31+8*r41 >=16;
4*r12+5*r22+6*r32+8*r42 >=16;
4*r13+5*r23+6*r33+8*r43 >=16;
x1+x2+x3 >= 26;
x1+x2+x3 <= 31;
x1>=x2;
x2>=x3;
@gin(x1); @gin(x2); @gin(x3);
@gin(r11);@gin(r12);@gin(r13);
@gin(r21);@gin(r22);@gin(r23);
@gin(r31);@gin(r32);@gin(r33);
@gin(r41);@gin(r42);@gin(r43);
end
优化建模经过 LINGO求解，得到输出如下：
Local optimal solution found.
Objective value,28.00000
Extended solver steps,72
Total solver iterations,3404
Model Title,钢管下料 -最小化钢管根数的 LINGO模型优化建模
Variable Value Reduced Cost
X1 10.00000 1.000000
X2 10.00000 1.000000
X3 8.000000 1.000000
R11 2.000000 0.000000
R12 3.000000 0.000000
R13 0.000000 0.000000
R21 1.000000 0.000000
R22 0.000000 0.000000
R23 0.000000 0.000000
R31 1.000000 0.000000
R32 1.000000 0.000000
R33 0.000000 0.000000
R41 0.000000 0.000000
R42 0.000000 0.000000
R43 2.000000 0.000000
优化建模即按照模式 1,2,3分别切割 10,10,8根原料钢管，使用原料钢管总根数为 28根。第一种切割模式下一根原料钢管切割成 3根 4米钢管和 1根 6米钢管；第二种切割模式下一根原料钢管切割成 2根 4米钢管,1根 5米钢管和 1根 6米钢管；
第三种切割模式下一根原料钢管切割成 2根 8米钢管。
如果充分利用 LINGO建模语言的能力，使用集合和属性的概念，可以编写以下 LINGO程序，这种方法更具有一般的通用性，并有利于输入更大规模的下料问题的优化模型：
优化建模
model:
Title 钢管下料 - 最小化钢管根数的 LINGO模型 ;
SETS,
NEEDS/1..4/:LENGTH,NUM;
! 定义基本集合 NEEDS及其属性 LENGTH,NUM;
CUTS/1..3/:X;
! 定义基本集合 CUTS及其属性 X;
PATTERNS(NEEDS,CUTS):R;
! 定义派生集合 PATTERNS（这是一个稠密集合）及其属性 R;
ENDSETS
DATA:
LENGTH=4 5 6 8;
NUM=50 10 20 15;
CAPACITY=19;
ENDDATA
min=@SUM(CUTS(I),X(I) );
优化建模
!目标函数 ;
@FOR(NEEDS(I),@SUM(CUTS(J),X(J)*R(I,J) ) >NUM(I) );
!满足需求约束 ;
@FOR(CUTS(J),@SUM(NEEDS(I),LENGTH(I)*R(I,J) ) <CAPACITY );
!合理切割模式约束 ;
@FOR(CUTS(J),@SUM(NEEDS(I),LENGTH(I)*R(I,J) ) >CAPACITY
-@MIN(NEEDS(I):LENGTH(I)) );
!合理切割模式约束 ;
@SUM(CUTS(I),X(I) ) >26; @SUM(CUTS(I),X(I) ) <31;
!人为增加约束 ;
@FOR(CUTS(I)|I#LT#@SIZE(CUTS):X(I)>X(I+1) );
!人为增加约束 ;
@FOR(CUTS(J),@GIN(X(J)) ) ;
@FOR(PATTERNS(I,J),@GIN(R(I,J)) );
end
求解这个模型，得到的结果与前面的结果完全相同。
优化建模
§ 5.3.2易拉罐下料问题例 5.4 某公司采用一套冲压设备生产一种罐装饮料的易拉罐，这种易拉罐是用镀锡板冲压制成的（参见图 5-3）。易拉罐为圆柱形，包括罐身、上盖和下底，
罐身高 10厘米，上盖和下底的直径均为 5厘米。该公司使用两种不同规格的镀锡板原料，规格 1的镀锡板为正方形，边长 24厘米；规格 2的镀锡板为长方形，
长、宽分别为 32和 28厘米。由于生产设备和生产工艺的限制，对于规格 1的镀镀锡板原料，只可以按照图 2
中的模式 1,2或 3进行冲压；对于规格 2的镀锡板原料只能按照模式 4进行冲压。使用模式 1,2,3,4进行每次冲压所需要的时间分别为 1.5,2,1,3（秒）。
优化建模模式 1 模式 2 模式 3
模式 4
上盖下底罐身图 5-3 易拉罐下料模式优化建模该工厂每周工作 40小时，每周可供使用的规格 1,2的镀锡板原料分别为 5万张和 2万张。目前每只易拉罐的利润为 0.10元，
原料余料损失为 0.001元 / 厘米 2（如果周末有罐身、上盖或下底不能配套组装成易拉罐出售，也看作是原料余料损失）。
工厂应如何安排每周的生产？
已知上盖和下底的直径 d=5厘米，可得其面积为
4/2ds? 19.6厘米
2周长为 dL 15,7 厘米；已知罐身高 h = 1 0 厘米,
可得其面积为 hLS 157.1 厘米
2
。
于是模式 1 下的余料损失为 9.2 221024 2 Ss 厘米
2
。
同理计算其它模式下的余料损失,
并可将 4 种冲压模式的特征归纳如表 5 - 4 。
优化建模表 5-4 4种冲压模式的特征罐身个数 底、盖个数 余料损失
（厘米 2）
冲压时间
（秒）
模式 1 1 10 222.6 1.5
模式 2 2 4 183.3 2
模式 3 0 16 261.8 1
模式 4 4 5 169.5 3
问题的目标显然应是易拉罐的利润扣除原料余料损失后的净利润最大，约束条件除每周工作时间和原料数量外，还要考虑罐身和底、
盖的配套组装。
优化建模模型建立决策变量 用 xi 表示按照第 i种模式的冲压次数（ i=1,2,3,4）,y1表示一周生产的易拉罐个数。为计算不能配套组装的罐身和底、盖造成的原料损失，用 y2表示不配套的罐身个数,y3表示不配套的底、盖个数。
虽然实际上 xi和 y1,y2,y3应该是整数。但是由于生产量相当大，可以把它们看成是实数，从而用线性规划模型处理。
决策目标 假设每周生产的易拉罐能够全部售出，公司每周的销售利润是 0.1y1。原料余料损失包括两部分,4种冲压模式下的余料损失，和不配套的罐身和底、盖造成的原料损失。按照前面的计算及表 2的结果，总损失为 0.001(222.6x1 + 183.3x2 +
261.8x3 + 169.5x4 + 157.1y2 +19.6y3)。
优化建模于是，决策目标为
)6.191.1575.1698.2613.1836.222(001.01.0 3243211 yyxxxxyM a x
(47)
约束条件时间约束：每周工作时间不超过 40小时 =144000（秒），由表 2最后一列得
144000325.1 4321 xxxx (48)
原料约束：
每周可供使用的规格 1,2的镀锡板原料分别为 50000张和 20000张，即
5 0 0 0 0321 xxx (49)
2 0 0 0 04?x (50)
优化建模配套约束,由表 2一周生产的罐身个数为 x1 + 2x2 + 4x4,一周生产的底、盖个数为 10x1 + 4x2 + 16x3+ 5x4，因为应尽可能将它们配套组装成易拉罐销售。所以 y1满足
}2/)516410(,42m i n { 43214211 xxxxxxxy (51)
这时不配套的罐身个数 y2，和不配套的底、盖个数 y3应为
14212 42 yxxxy
(52)
143213 2516410 yxxxxy
(53)
优化建模
（ 47） ~（ 53）就是我们得到的模型，其中（ 51）是一个非线性关系，
不易直接处理，
但是它可以等价为以下两个线性不等式：
4211 42 xxxy
(54)
2/)516410( 43211 xxxxy (55)
模型求解将模型（ 47） ~（ 50）和（ 52） ~（ 55）直接输入 LINDO（输入
LINGO也可以），求解时 LINDO发出警告信息（程序和警告信息参见图 5-4）。 图中错误编号,66”的含义（参见第 4章的错误代码表）是：模型中数据不平衡，所以发出警告信息（注意，只是警告信息，所以仍然可以继续求解）。求解结果是：
优化建模
OBJECTIVE FUNCTION VALUE
1) 4298.337
VARIABLE VALUE REDUCED COST
Y1 160250.000000 0.000000
X1 0.000000 0.000050
X2 40125.000000 0.000000
X3 3750.000000 0.000000
X4 20000.000000 0.000000
Y2 0.000000 0.223331
Y3 0.000000 0.036484
优化建模图 5-4 模型中数据不平衡的警告信息优化建模这个结果可靠吗？由于 LINDO警告模型中数据之间的数量级差别太大，所以我们可以进行预处理，缩小数据之间的差别。实际上，约束（ 48） ~（ 50）中右端项的数值过大（与左端的系数相比较）,LINDO在计算中容易产生比较大的误差，所以出现此警告信息。
为了解决这一问题，可以将所有决策变量扩大 10000倍
（相当于 xi以万次为单位,yi以万件为单位）。此时，目标（ 47）可以保持不变（记住得到的结果单位为万元就可以了），而约束（ 48） ~（ 50）改为
4.14325.1 4321 xxxx (56)
5321 xxx (57)
24?x (58)
优化建模将模型（ 47）和（ 52） ~（ 58）输入 LINDO:
! 易拉罐下料：均衡数据
Max 0.100y1 - 0.2226x1 - 0.1833x2 - 0.2618x3 - 0.1695 x4 - 0.1571y2 - 0.0196y3
s.t.
1.5x1 + 2.0x2 + 1.0x3 +3.0x4 <= 14.4
x1 + x2 + x3 <= 5
x4 <= 2
x1 + 2x2 + 4x4 - y1 >=0
10x1 + 4x2 + 16x3+ 5x4 - 2y1 >=0
x1 + 2x2 + 4x4 - y1 - y2 =0
10x1 + 4x2 + 16x3+ 5x4 - 2y1 - y3=0
end
优化建模求解得到,
OBJECTIVE FUNCTION VALUE
1) 0.4298337
VARIABLE VALUE REDUCED COST
Y1 16.025000 0.000000
X1 0.000000 0.000050
X2 4.012500 0.000000
X3 0.375000 0.000000
X4 2.000000 0.000000
Y2 0.000000 0.223331
Y3 0.000000 0.036484
即模式 1不使用，模式 2使用 40125次，模式 3使用 3750次，模式 4使用 20000次，可生产易拉罐 160250个，罐身和底、盖均无剩余，净利润为 4298元。
优化建模
5.4 面试顺序与消防车调度问题优化建模面试顺序问题例 5.5 有 4名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先找公司秘书初试，
然后到部门主管处复试，最后到经理处参加面试，并且不允许插队（即在任何一个阶段 4名同学的顺序是一样的）。由于 4名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如表 5-5所示（单位：
分钟）。这 4名同学约定他们全部面试完以后一起离开公司。假定现在时间是早晨 8,00，请问他们最早何时能离开公司？
优化建模表 5-5 面试时间要求秘书初试 主管复试 经理面试同学甲 13 15 20
同学乙 10 20 18
同学丙 20 10 10
同学丁 8 10 15
优化建模建立模型实际上，这个问题就是要安排 4名同学的面试顺序，使完成全部面试所花费的时间最少。
记 tij为第 i名同学参加第 j阶段面试需要的时间 (已知 )，令 xij表示第 i名同学参加第 j阶段面试的开始时刻
(不妨记早上 8,00面试开始为 0时刻 )(i=1,2,3,4； j=1,
2,3),T为完成全部面试所花费的最少时间。
优化目标为
33M a xM in iii txT
优化建模
a,时间先后次序约束 (每人只有参加完前一个阶段的面试后才能进入下一个阶段 )：
xij+ tij?xi,j+1 (i=1,2,3,4； j=1,2)
b.每个阶段 j同一时间只能面试 1名同学：用 0-1变量 yik表示第 k名同学是否排在第 i名同学前面 (1表示是，
0表示否 )，则
xij+ tij–xkj?Tyik (i,k=1,2,3,4; j=1,2,3; i<k)
xkj+ tkj–xij?T(1–yik) (i,k=1,2,3,4; j=1,2,3; i<k)
约束条件：
优化建模可以将非线性的优化目标改写为如下线性优化目标：
Min T
s.t,T? x13+ t13
T? x23+ t23
T? x33+ t33
T? x43+ t43
优化建模
Min T
s.t,xij+ tij?xi,j+1 (i=1,2,3,4； j=1,2)
xij+ tij–xkj?Tyik (i,k=1,2,3,4; j=1,2,3; i<k)
xkj+ tkj–xij?T(1–yik) (i,k=1,2,3,4; j=1,2,3; i<k)
xi3+ ti3?T (i=1,2,3,4)
这个问题的 0-1非线性规划模型 (当然所有变量还有非负约束，变量 yik还有 0-1约束 ),
优化建模
Model:
min =T;
T >= x13+ t13;
T >= x23+ t23;
T >= x33+ t33;
T >= x43+ t43;
x11+ t11 <= x12;
x12+ t12 <= x13;
x21+ t21 <= x22;
x22+ t22 <= x23;
x31+ t31 <= x32;
x32+ t32 <= x33;
x41+ t41 <= x42;
x42+ t42 <= x43;
求解模型这个模型可以如下输入 LINGO：
优化建模
x11+ t11 - x21<= T*y12;
x21+ t21 - x11<= T*(1-y12);
x12+ t12 - x22<= T*y12;
x22+ t22 - x12<= T*(1-y12);
x13+ t13 - x23<= T*y12;
x23+ t23 - x13<= T*(1-y12);
x11+ t11 - x31<= T*y13;
x31+ t31 - x11<= T*(1-y13);
x12+ t12 - x32<= T*y12;
x32+ t32 - x12<= T*(1-y13);
x13+ t13 - x33<= T*y13;
x33+ t33 - x13<= T*(1-y13);
x11+ t11 - x41<= T*y14;
x41+ t41 - x11<= T*(1-y14);
x12+ t12 - x42<= T*y14;
x42+ t42 - x12<= T*(1-y14);
优化建模
x13+ t13 - x43<= T*y14;
x43+ t43 - x13<= T*(1-y14);
x21+ t21 - x31<= T*y23;
x31+ t31 - x21<= T*(1-y23);
x22+ t22 - x32<= T*y23;
x32+ t32 - x32<= T*(1-y23);
x23+ t23 - x33<= T*y23;
x33+ t33 - x23<= T*(1-y23);
x21+ t21 - x41<= T*y24;
x41+ t41 - x21<= T*(1-y24);
x22+ t22 - x42<= T*y24;
x42+ t42 - x22<= T*(1-y24);
x23+ t23 - x43<= T*y24;
x43+ t43 - x23<= T*(1-y24);
x31+ t31 - x41<= T*y34;
x41+ t41 - x31<= T*(1-y34);
优化建模
x32+ t32 - x42<= T*y34;
x42+ t42 - x32<= T*(1-y34);
x33+ t33 - x43<= T*y34;
x43+ t43 - x33<= T*(1-y34);
t11=13;
t12=15;
t13=20;
t21=10;
t22=20;
t23=18;
t31=20;
t32=16;
t33=10;
t41=8;
t42=10;
t43=15;
优化建模
@bin(y12);
@bin(y13);
@bin(y14);
@bin(y23);
@bin(y24);
@bin(y34);
End
优化建模用 LINGO求解得到,
Local optimal solution found at iteration,4357
Objective value,84.00000
Variable Value Reduced Cost
T 84.00000 0.000000
X13 36.00000 0.000000
T13 20.00000 0.000000
X23 56.00000 0.000000
T23 18.00000 0.000000
X33 74.00000 0.000000
T33 10.00000 0.000000
X43 21.00000 0.000000
T43 15.00000 0.000000
X11 8.000000 0.000000
T11 13.00000 0.000000
X12 21.00000 0.000000
T12 15.00000 0.000000
优化建模
Variable Value Reduced Cost
X21 21.00000 0.000000
T21 10.00000 0.000000
X22 36.00000 0.000000
T22 20.00000 0.000000
X31 37.50000 0.000000
T31 20.00000 0.000000
X32 57.75000 0.000000
T32 16.00000 0.000000
X41 0.000000 0.9999970
T41 8.000000 0.000000
X42 11.00000 0.000000
T42 10.00000 0.000000
Y12 0.000000 -83.99950
Y13 0.000000 0.000000
Y14 1.000000 83.99950
Y23 0.000000 -83.99950
Y24 1.000000 0.000000
Y34 1.000000 0.000000
即所有面试完成至少需要 84分钟，面试顺序为 4-1-2-3
(即丁 -甲 -乙 -丙 )。
早上 8:00面试开始，
最早 9:24面试可以全部结束。
优化建模同样，如果利用 LINGO的建模语言，可以编写一个更一般的 LINGO模型。先准备一个数据文件 (文本文件 exam0505.txt)，其中的内容如下：
! 被面试者集合 ;
1 2 3 4~
! 面试阶段的集合 ;
1 2 3~ !
已知的面试所需要的时间 ;
13 15 20
10 20 18
20 16 10
8 10 15
! 数据结束 ;
优化建模
LINGO模型如下：
Model:
Title 面试问题 ;
SETS:
! Person = 被面试者集合,Stage = 面试阶段的集合 ;
Person/@FILE(exam0505.txt)/;
Stage/@FILE(exam0505.txt)/;
! T = 已知的面试所需要的时间,X = 面试开始时间 ;
PXS(Person,Stage),T,X;
! Y(i,k) = 1,k排在 i前,0：否则 ;
PXP(Person,Person)|&1 #LT# &2,Y;
ENDSETS
DATA,
T=@FILE(exam0505.txt);
ENDDATA
优化建模
[obj] min =MAXT;
! MAXT是面试的最后结束时间 ;
MAXT >= @max(PXS(i,j)|j#EQ#@size(stage),x(i,j)+t(i,j));
!只有参加完前一个阶段的面试后才能进入下一个阶段 ;
@for(PXS(i,j)|j#LT#@size(stage):[ORDER]x(i,j)+t(i,j)<x(i,j+1));
! 同一时间只能面试 1名同学 ;
@for(Stage(j):
@for(PXP(i,k):[SORT1]x(i,j)+t(i,j)-x(k,j)<MAXT*Y(i,k) );
@for(PXP(i,k):[SORT2]x(k,j)+t(k,j)-x(i,j)<MAXT*(1-Y(i,k)) );
);
@for(PXP,@bin(y));
End
优化建模求解这个模型，得到的结果与前面的完全相同。
可以很清楚地看到，使用 LINGO建模语言的集合和属性概念，得到的模型具有非常好的结构性，反映了相应的优化模型的本质，目标、决策变量、约束一清二楚，容易阅读和理解，而且还可以让数据与程序完全分离，这种优越性是 LINDO软件无法与之相比的。
优化建模消防车调度问题例 5.6 某市消防中心同时接到了三处火警报告。
根据当前的火势，三处火警地点分别需要 2辆,2辆和
3辆消防车前往灭火。三处火警地点的损失将依赖于消防车到达的及时程度：记 tij为第 j辆消防车到达火警地点 i的时间 (分钟 )，则三处火警地点的损失分别为,
6t11+4t12,7t21+3t22,9t31+8t32+5t33。
目前可供消防中心调度的消防车正好有 7辆，分别属于三个消防站 (可用消防车数量分别为 3辆,2辆、
2辆 )。消防车从三个消防站到三个火警地点所需要的时间如表 5-6所示。该公司应如何调度消防车，才能使总损失最小？
优化建模如果三处火警地点的损失分别为,
4t11+6t12,3t21+7t22,5t31+8t32+9t33，
调度方案是否需要改变？
消防站到三个火警地点所需要的时间时间 (分钟 ) 火警地点 1 火警地点 2 火警地点 3
消防站 1 6 7 9
消防站 2 5 8 11
消防站 3 6 9 10
优化建模问题分析本题考虑的是为每个火警地点分配消防车的问题，初步看来与线性规划中经典的运输问题有些类似。
本题的问题可以看成是指派问题和运输问题的一种变形，我们下面首先把它变成一个运输问题建模求解。
决策变量为了用运输问题建模求解，很自然地把 3个消防站看成供应点。如果直接把 3个火警地点看成需求点，
我们却不能很方便地描述消防车到达的先后次序，因此难以确定损失的大小。下面我们把 7辆车的需求分别看成 7个需求点 (分别对应于到达时间 t11,t12,t21,t22,
t31,t32,t33)。用 xi j表示消防站 i是否向第 j个需求点派车
(1表示派车,0表示不派车 )，则共有 21个 0-1变量。
优化建模决策目标题目中给出的损失函数都是消防车到达时间的线性函数，所以由所给数据进行简单的计算可知，如果消防站 1向第 6个需求点派车 (即消防站 1向火警地点 3
派车但该消防车是到达火警地点 3的第二辆车 )，则由此引起的损失为 8*9=72。同理计算，可以得到损失矩阵 (元素分别记为 ci j)。
ci j 火警地点 1 火警地点 2 火警地点 3j=1 j=2 j=3 j=4 j=5 j=6 j=7
消防站 i=1 36 24 49 21 81 72 45
消防站 i=2 30 20 56 24 99 88 55
消防站 i=3 36 24 63 27 90 80 50
优化建模于是，使总损失最小的决策目标为
7
1
3
1
M i n
j
ij
i
ij xcZ
约束条件 约束条件有两类：一类是消防站拥有的消防车的数量限制，另一类是各需求点对消防车的需求量限制。
消防站拥有的消防车的数量限制可以表示为
x11+x12+x13+x14+x15+x16+x17=3
x21+x22+x23+x24+x25+x26+x27 =2
x31+x32+x33+x34+x35+x36+x37=2
各需求点对消防车的需求量限制可以表示为
.7,6,5,4,3,2,1,13
1
jx
i ij
优化建模模型求解将如上构成的线性规划模型输入 LINDO：
! 消防车问题
Min 36x11+24x12+49x13+21x14+81x15+72x16+45x17
+30x21+20x22+56x23+24x24+99x25+88x26+55x27
+36x31+24x32+63x33+27x34+90x35+80x36+50x37
SUBJECT TO x11+x12+x13+x14+x15+x16+x17 = 3
x21+x22+x23+x24+x25+x26+x27 = 2
x31+x32+x33+x34+x35+x36+x37 = 2
x11+x21+x31 =1
x12+x22+x32 =1
x13+x23+x33 = 1
x14+x24+x34 =1
x15+x25+x35 =1
x16+x26+x36 = 1
x17+x27+x37 = 1
END
优化建模求解得到如下结果：
OBJECTIVE FUNCTION VALUE 1) 329.0000
VARIABLE VALUE REDUCED COST
X11 0.000000 10.000000
X12 0.000000 8.000000
X13 1.000000 0.000000
X14 0.000000 2.000000
X15 1.000000 0.000000
X16 1.000000 0.000000
X17 0.000000 3.000000
X21 1.000000 0.000000
X22 1.000000 0.000000
X23 0.000000 3.000000
X24 0.000000 1.000000
X25 0.000000 14.000000
X26 0.000000 12.000000
X27 0.000000 9.000000
优化建模
VARIABLE VALUE REDUCED COST
X31 0.000000 2.000000
X32 0.000000 0.000000
X33 0.000000 6.000000
X34 1.000000 0.000000
X35 0.000000 1.000000
X36 0.000000 0.000000
X37 1.000000 0.000000
也就是说，消防站 1应向火警地点 2派 1辆车，向火警地点 3派 2辆车；消防站 2应向火警地点 1派 2辆车；
消防站 3应向火警地点 2,3各派 1辆车。最小总损失为
329。
优化建模讨论
1) 这个问题本质上仍然和经典的运输问题类似，
可以把每辆车到达火场看作需求点，消防站可作供应点。在上面模型中，我们虽然假设 xij为 0-1变量，但求解时是采用线性规划求解的，也就是说没有加上 xij
为 0-1变量或整数变量的限制条件，但求解得到的结果中 xij正好是 0-1变量。这一结果不是偶然的，而是运输问题特有的一种性质。
优化建模
2) 在上面模型中，我们没有考虑消防车到达各火警地点的先后次序约束，但得到的结果正好满足所有的先后次序约束。这一结果却并不总是必然的，而只是巧合。
如对例题后半部分的情形，结果就不是这样了。
显然，此时只需要修改损失矩阵 (元素仍然分别记为 cij)
ci j 火警地点 1 火警地点 2 火警地点 3j=1 j=2 j=3 j=4 j=5 j=6 j=7
消防站 i=1 24 36 21 49 45 72 81
消防站 i=2 20 30 24 56 55 88 99
消防站 i=3 24 36 27 63 50 80 90
优化建模此时将重新构成的线性规划模型输入 LINDO求解,可以得到新的最优解,
x14=x16=x17=x21=x22=x33=x35=1
其他变量为 0(最小总损失仍为 329)。实际上,损失矩阵中只是 1,2列交换了位置,3,4列交换了位置,5,7
列交换了位置，因此不用重新求解就可以直接看出以上新的最优解。
但是，以上新的最优解却是不符合实际情况的。
例如,x14=x33=1表明火警地点 2的第一辆消防车来自消防站 3，第二辆消防车来自消防站 1，但这是不合理的，因为火警地点 2与消防站 3有 9分钟的距离，大于与消防站 1的 7分钟的距离。分配给火警地点 3的消防车也有类似的不合理问题。
优化建模为了解决这一问题，我们必须考虑消防车到达各火警地点的先后次序约束，也就是说必须在简单的运输问题模型中增加一些新的约束，以保证以上的不合理问题不再出现。
首先考虑火警地点 2。由于消防站 1的消防车到达所需时间 (7分钟 )小于消防站 2的消防车到达所需时间 (8分钟 )，并都小于消防站 3的消防车到达所需时间
(9分钟 )，因此火警地点 2的第 2辆消防车如果来自消防站 1，则火警地点 2的第 1辆消防车也一定来自消防站 1；
火警地点 2的第 2辆消防车如果来自消防站 2，则火警地点 2的第 1辆消防车一定来自消防站 1或 2。因此，必须增加以下约束,x
14?x13
x24?x13 +x23
优化建模
x16?x15
x17?x16
x36?x15+x35
2x37?x15+x16+x35+x36
同理，对火警地点 1，必须增加以下约束：
x22?x21
对火警地点 3，必须增加以下约束：
优化建模此时将重新构成的线性规划模型输入 LINDO软件如下：
! 消防车调度
Min 36x12+24x11+49x14+21x13+81x17+72x16+45x15
+30x22+20x21+56x24+24x23+99x27+88x26+55x25
+36x32+24x31+63x34+27x33+90x37+80x36+50x35
SUBJECT TO x11+x12+x13+x14+x15+x16+x17 = 3
x21+x22+x23+x24+x25+x26+x27 = 2
x31+x32+x33+x34+x35+x36+x37 = 2
x11+x21+x31 = 1
x12+x22+x32 = 1
x13+x23+x33 = 1
x14+x24+x34 = 1
x15+x25+x35 = 1
x16+x26+x36 = 1
x17+x27+x37 = 1
优化建模
X22 - X21 <= 0
X14 - X13 <=0
X24 - X23 - X13 <=0
X16 - X15 <= 0
X17 - X16 <=0
X36 - X15 - X35 <=0
2X37 -X15 -X16 -X35 -X36 <=0
END
! INT 21
优化建模求解，可以得到新的解为：
OBJECTIVE FUNCTION VALUE 1) 32.6667
VARIABLE VALUE REDUCED COST
X12 0.000000 9.333333
X11 0.000000 7.333333
X14 1.000000 0.000000
X13 1.000000 0.000000
X17 0.333333 0.000000
X16 0.333333 0.000000
X15 0.333333 0.000000
X22 1.000000 0.000000
X21 1.000000 0.000000
X24 0.000000 2.333333
X23 0.000000 1.000000
优化建模
VARIABLE VALUE REDUCED COST
X27 0.000000 13.000000
X26 0.000000 12.000000
X25 0.000000 9.000000
X32 0.000000 2.000000
X31 0.000000 0.000000
X34 0.000000 5.333333
X33 0.000000 0.000000
X37 0.666667 0.000000
X36 0.666667 0.000000
X35 0.666667 0.000000
优化建模但是我们发现此时的解中 xij并不都是 0–1变量或整数变量，因此还是不符合题意。这是因为此时的模型已经不再是“标准”的运输模型，所以得到的解不一定自然地为正数解的缘故。所以我们还必须显式地加上 xij为 0–1变量的约束。
加上 xij为 0-1变量的约束后求解可以得到：
x13=x14=x15=x21=x22=x36=x37=1，
其他变量为 0(最小总损失仍为 335)。也就是说，消防站 1应向火警地点 2派 2辆车，向火警地点 3派 1辆车；
消防站 2应向火警地点 1派 2辆车；消防站 3应向火警地点 3派 2辆车。经过检验可以发现，此时的派车方案是合理的。
优化建模
5.5 飞机定位和飞行计划问题优化建模
5.5.1飞机的精确定位问题例 5.7 飞机在飞行过程中，能够收到地面上各个监控台发来的关于飞机当前位置的信息，根据这些信息可以比较精确地确定飞机的位置 。如图所示，
VOR是高频多向导航设备的英文缩写，它能够得到飞机与该设备连线的角度信息； DME是距离测量装置的英文缩写，它能够得到飞机与该设备的距离信息。
图中飞机接收到来自 3个 VOR给出的角度和 1个 DME
给出的距离 (括号内是测量误差限 )，并已知这 4种设备的 x,y坐标 (假设飞机和这些设备在同一平面上 )。
如何根据这些信息精确地确定当前飞机的位置？
优化建模
0
y
x
VOR2
x=629,
y=375 309.00 (1.30)
864.3(2.0) 飞机
x=?,y=?
VOR1
x=764,
y=1393
161.20 (0.80)
VOR3
x=1571,
y=259
45.10 (0.60)
北
DME
x=155,
y=987
图 飞机与监控台优化建模问题分析记 4种设备 VOR1,VOR2,VOR3,DME的坐标为 (xi,yi)(以 km为单位 ),i=1,2,3,4； VOR1,VOR2、
VOR3测量得到的角度为?i (从图中可以看出，按照航空飞行管理的惯例，该角度是从北开始，沿顺时针方向的角度，取值在 00~3600之间 )，角度的误差限为?i，
i=1,2,3； DME测量得到的距离为 d4 (km)，距离的误差限为?4。设飞机当前位置的坐标为 (x,y)，则问题就是由下表的已知数据计算 (x,y)。
xi yi 原始的?i (或 d4)?i
VOR1 746 1393 161.20(2.81347弧度 ) 0.80(0.0140弧度 )
VOR2 629 375 45.10(0.78714弧度 ) 0.60(0.0105弧度 )
VOR3 1571 259 309.00(5.39307弧度 ) 1.30(0.0227弧度 )
DME 155 987 864.3 (km) 2.0 (km)
优化建模模型 1及求解图中角度?i是点 (xi,yi)和点 (x,y)的连线与 y 轴的夹角 (以 y 轴正向为基准，顺时针方向夹角为正，而不考虑逆时针方向的夹角 )，于是角度?i的正切
i
i
i yy
xx
t a n i=1,2,3,
对 DME测量得到的距离，显然有
24244 )()( yyxxd
直接利用上面得到的 4个等式确定飞机的坐标 x,y，
这时是一个求解超定 (非线性 )方程组的问题，在最小二乘准则下使计算值与测量值的误差平方和最小 (越接近 0越好 )。
优化建模
3
1
2]t an)/()([),( M in
i iii
yyxxyxJ?
224244 ])()([ yyxxd
这是一个非线性 (无约束 )最小二乘拟合问题。
则需要求解优化建模
MODEL:
SETS:
VOR/1..3/,x,y,cita,sigma;
ENDSETS
DATA:
x,y,cita,sigma =
746 1393 2.81347 0.0140
629 375 0.78714 0.0105
1571 259 5.39307 0.0227;
x4 y4 d4 sigma4 = 155 987 864.3 2.0;
ENDDATA
! XX,YY表示飞机坐标 ;
min = @sum(VOR,@sqr((xx-x)/(yy-y) - @tan(cita)) )
+ @sqr(d4 - @sqrt(@sqr(xx-x4)+@sqr(yy-y4)) );
END
很容易写出其 LINGO程序如下：
优化建模求解该模型得到的解为 (只列出部分结果 )：
Local optimal solution found.
Objective value,128.0226
Variable Value Reduced Cost
XX 243.4204 0.1315903E-08
YY 126.3734 0.000000
显然，这个解的目标函数值很大 (128.0226),因此我们怀疑是一个局部最小点。用,LINGO|OPTIONS”
菜单命令启动,Global Solver”选项卡上的,Use
Global Solver”选项，然后求解，可以得到全局最优解如下：Global optimal solution found.
Objective value,0.7050440E-03
Variable Value Reduced Cost
XX 980.6926 0.000000
YY 731.5666 0.000000
优化建模这个解的目标函数值很小 (0.000705)，飞机坐标为
(980.6926,731.5666)。
优化建模模型 2及求解注意到这个问题中角度和距离的单位是不一致的
(角度为弧度，距离为公里 )，因此将这 4个误差平方和同等对待 (相加 )不是很合适。并且,4种设备测量的精度 (误差限 )不同，而上面的方法根本没有考虑测量误差问题。如何利用测量设备的精度信息？这就需要看你对例中给出的设备精度如何理解。
一种可能的理解是：设备的测量误差是均匀分布的。以 VOR1为例，目前测得的角度为 161.20，测量精度为 0.80，所以实际的角度应该位于区间 [161.20-
0.80,161.20+0.80]内。对其他设备也可以类似理解。
由于很小，即测量精度很高，所以在相应区间内正切函数 tan的单调性成立。
优化建模于是可以得到一组不等式：
)t a n ()t a n ( ii
i
i
ii yy
xx
44242444 )()( dyyxxd
(i=1,2,3)
也就是说，飞机坐标应该位于上述不等式组成的区域内。例如，模型 1中得到的目标函数值很小，显然满足测量精度要求，因此坐标 (980.6926,731.5666)
肯定位于这个可行区域内。
优化建模由于这里假设设备的测量误差是均匀分布的，所以飞机坐标在这个区域内的每个点上的可能性应该也是一样的，我们最好应该给出这个区域的 x和 y坐标的最大值和最小值。于是我们可以分别以 min x,max x、
min y,max y、为目标，以上面的区域限制条件为约束，求出 x和 y坐标的最大值和最小值。
以 min x为例，相应的 LINGO程序为：
MODEL:
Title 飞机定位模型 2;
SETS:
VOR/1..3/,x,y,cita,sigma;
ENDSETS
优化建模
DATA:
x,y,cita,sigma =
746 1393 2.81347 0.0140
629 375 0.78714 0.0105
1571 259 5.39307 0.0227;
x4 y4 d4 sigma4 = 155 987 864.3 2.0;
ENDDATA
! XX,YY表示飞机坐标 ;
min=xx;
@for(VOR,(xx-x)/(yy-y) > @tan(cita - sigma) );
@for(VOR,(xx-x)/(yy-y) < @tan(cita + sigma) );
d4 - sigma4 < @sqrt(@sqr(xx-x4)+@sqr(yy-y4)) ;
d4 + sigma4 > @sqrt(@sqr(xx-x4)+@sqr(yy-y4)) ;
END
优化建模用 LINGO求解上述模型,LINGO系统返回的信息是这个模型没有可行解。其实这显然是一个不正确的信息，可能只是由于求解空间太大,LINGO没有找到可行解。其实，我们可以想象这个问题的可行解大致就该在模型 1中得到的最优解附近，因此可以把这个解作为初始值告诉 LINGO。例如，在上面程序中增加以下三行：
INIT:
xx,yy = 980.6926,731.5666;
ENDINIT
优化建模此时求解，马上就得到 XX的最小值为 974.8424。
类似地（只需要换换目标函数就可以了），可得到
XX的最大值为 982.2129,YY的最小值为 717.1587，
YY的最大值为 733.1944。
因此，最后得到的解是一个比较大的矩形区域，
大致为 [975,982]× [717,733]。
优化建模模型 3及求解模型 2得到的只是一个很大的矩形区域，仍不能令人满意。实际上，模型 2中假设设备的测量误差是均匀分布的，这是很不合理的。一般来说，在多次测量中，应该假设设备的测量误差是正态分布的，而且均值为 0。本例中给出的精度?i可以认为是测量误差的标准差 (也可以是与标准差成比例的一个量，如标准差的 3倍或 6倍等 )。
在这种理解下，用各自的误差限?i对测量误差进行无量纲化 (也可以看成是一种加权法 )处理是合理的，
即求解如下的无约束优化问题更合理：
优化建模
2
4
2
4
2
44
23
1
)()(),( M i n
yyxxdαyxE
i i
ii
其中
i
i
i yy
xx
t a n i=1,2,3,
由于目标函数是平方和的形式，因此这是一个非线性最小二乘拟合问题。相应的 LINGO程序为 (仍然将迭代初值告诉 LINGO)：
优化建模
MODEL:
TITLE 飞机定位模型 3;
SETS:
VOR/1..3/,x,y,cita,sigma;
ENDSETS
DATA:
x,y,cita,sigma =
746 1393 2.81347 0.0140
629 375 0.78714 0.0105
1571 259 5.39307 0.0227;
x4 y4 d4 sigma4 = 155 987 864.3 2.0;
ENDDATA
INIT:
xx,yy = 980.6926,731.5666;
ENDINIT
优化建模
! XX,YY表示飞机坐标 ;
!min = @sum(VOR,@sqr(((xx-x)/(yy-y) - @tan(cita))/sigma) )
+ @sqr((d4 - @sqrt(@sqr(xx-x4)+@sqr(yy-y4)))/sigma4 );
min = @sum(VOR,(((xx-x)/(yy-y) - @tan(cita))/sigma)^2 )
+ ((d4 - ((xx-x4)^2+(yy-y4)^2)^.5 )/sigma4 )^2;
END
Global optimal solution found.
Objective value,2.600539
Model Title,飞机定位模型 3
Variable Value Reduced Cost
XX 980.2106 0.000000
YY 727.3056 0.000000
计算结果为：
即飞机坐标为 (980.21,727.31)，这个解对应的目标函数值大约为 2.6。
优化建模这个误差为什么比模型 1的大很多？这是因为模型 1中使用的是绝对误差，而这里使用的是相对于精度?i的误差。分母?i很小，所以相对误差比绝对误差大，这是可以理解的。其实，可以认为此时的目标函数是四个标准正态分布的误差平方和，只要在 4以内都是合理的。
优化建模
5.5.2飞行计划问题例 5.8 这个问题是以第二次世界大战中的一个实际问题为背景，经过简化而提出来的。在甲乙双方的一场战争中，一部分甲方部队被乙方部队包围长达 4
个月。 由于乙方封锁了所有水陆交通通道，被包围的甲方部队只能依靠空中交通维持供给。运送 4个月的供给分别需要 2,3,3,4次飞行，每次飞行编队由 50架飞机组成 (每架飞机需要 3名飞行员 )，可以运送 10万吨物资。每架飞机每个月只能飞行一次，每名飞行员每个月也只能飞行一次。在执行完运输任务后的返回途中有 20%的飞机会被乙方部队击落，相应的飞行员也因此牺牲或失踪。
优化建模在第 1个月开始时，甲方拥有 110架飞机和 330名熟练的飞行员。在每个月开始时，甲方可以招聘新飞行员和购买新飞机。新飞机必须经过一个月的检查后才可以投入使用，新飞行员必须在熟练飞行员的指导下经过一个月的训练才能投入飞行。每名熟练飞行员可以作为教练每个月指导 20名飞行员 (包括他自己在内 )进行训练。每名飞行员在完成一个月的飞行任务后，必须有一个月的带薪假期，假期结束后才能再投入飞行。已知各项费用 (单位略去 )如下表所示，请你为甲方安排一个飞行计划。
优化建模如果每名熟练飞行员可以作为教练每个月指导不超过 20名飞行员 (包括他自己在内 )进行训练，模型和结果有哪些改变？
第 1个月 第 2个月 第 3个月 第 4个月新飞机价格 200.0 195.0 190.0 185.0
闲置的熟练飞行员报酬 7.0 6.9 6.8 6.7
教练和新飞行员报酬 (包括培训费用 ) 10.0 9.9 9.8 9.7
执行飞行任务的熟练飞行员报酬 9.0 8.9 9.8 9.7
休假期间的熟练飞行员报酬 5.0 4.9 4.8 4.7
优化建模问题分析这个问题看起来很复杂，但只要理解了这个例子中所描述的事实，其实建立优化模型并不困难。首先可以看出，执行飞行任务以及执行飞行任务后休假的熟练飞行员数量是常数，所以这部分费用 (报酬 )是固定的，在优化目标中可以不考虑。
决策变量设 4个月开始时甲方新购买的飞机数量分别为 x1,
x2,x3,x4架,闲置的飞机数量分别为 y1,y2,y3,y4架。 4个月中,飞行员中教练和新飞行员数量分别为 u1,u2,u3,
u4人,闲置的的熟练飞行员数量分别为 v1,v2,v3,v4人。
优化建模目标函数优化目标是,
Min 200x1+195x2 +190x3+185x4+10u1+9.9u2
+9.8u3+9.7u4+7v1+6.9v2+6.8v3+6.7v4
约束条件需要考虑的约束包括：
1） 飞机数量限制,4个月中执行飞行任务的飞机分别为 100,150,150,200架，但只有 80,120,120,160
架能够返回供下个月使用。
第 1个月,100+y1=110
第 2个月,150+y2=80+ y1+ x1
第 3个月,150+y3=120+ y2+ x2
第 4个月,200+y4=120+ y3+ x3
优化建模
2） 飞行员数量限制,4个月中执行飞行任务的熟练飞行员分别为 300,450,450,600人，但只有 240,360，
360,480人能够返回 (下个月一定休假 )。
第 1个月,300 +0.05 u1+ v1=330
第 2个月,450 +0.05 u2+ v2= u1+ v1
第 3个月,450 +0.05 u3+ v3= u2+ v2+240
第 4个月,600 +0.05 u4+ v4= u3+ v3+360
最后，自然要求 x1,x2,x3,x4,y1,y2,y3,y4,u1,u2,
u3,u4,v1,v2,v3,v4?0 且为整数。
优化建模于是，这个优化模型很容易输入 LINDO：
MIN 200x1+195x2 +190x3+185x4+10u1+9.9u2
+9.8u3+9.7u4+7v1+6.9v2+6.8v3+6.7v4
s.t,y1=10
y1+ x1 - y2 =70
y2+ x2 - y3 =30
y3+ x3 - y4=80
0.05 u1+ v1=30
u1 + v1 - 0.05 u2 - v2 = 450
u2 + v2 - 0.05 u3 - v3 = 210
u3 + v3 - 0.05 u4 - v4 = 240
end
GIN 16
优化建模用 LINDO求解得到：
OBJECTIVE FUNCTION VALUE 1) 42324.40
VARIABLE VALUE REDUCED COST
X1 60.000000 200.000000
X2 30.000000 195.000000
X3 80.000000 190.000000
X4 0.0000000 185.000000
U1 460.00000 10.000000
U2 220.00000 9.900000
U3 240.00000 9.800000
U4 0.0000000 9.700000
V1 7.0000000 7.000000
V2 6.0000000 6.900000
V3 4.0000000 6.800000
V4 4.0000000 6.700000
优化建模
VARIABLE VALUE REDUCED COST
Y1 10.000000 0.000000
Y2 0.000000 0.000000
Y3 0.000000 0.000000
Y4 0.000000 0.000000
即最优解为 x1=60,x2=30,x3=80,x4=0,y1=10,y2= y3= y4
=0,u1=460,u2=220,u3=240,u4=0,v1=7,v2=6,v3=4,
v4=4; 目标函数值为 42324.40。
优化建模问题讨论如果每名熟练飞行员可以作为教练每个月指导不超过 20名飞行员 (包括他自己在内 )进行训练，则应将教练与新飞行员分开：
设 4个月飞行员中教练为 u1,u2,u3,u4人，新飞行员数量分别为 w1,w2,w3,w4人。其它符号不变。飞行员的数量限制约束为第 1个月,300+u1+v1=330
第 2个月,450+u2+v2= u1+v1+w1,w1?20u1
第 3个月,450+u3+v3= u2+v2+240+w2,w2?20u2
第 4个月,600+u4+v4= u3+v3+360+w3,w3?20u3
优化建模优化模型作相应修改，输入 LINDO如下：
MIN 200x1+195x2 +190x3+185x4+10u1+9.9u2+9.8u3+9.7u4
+7v1+6.9v2+6.8v3+6.7v4+10w1+9.9w2+9.8w3+9.7w4
s.t,y1=10
y1+ x1 - y2 =70
y2+ x2 - y3 =30
y3+ x3 - y4=80
u1+ v1=30
u1 + v1 + w1 - u2 - v2 = 450
u2 + v2 + w2 - u3 - v3 = 210
u3 + v3 + w3 - u4 - v4 = 240
w1 - 20u1 <=0
w2 - 20u2 <=0
w3 - 20u3 <=0
end
gin 20
优化建模用 LINDO求解得到：
OBJECTIVE FUNCTION VALUE 1) 42185.80
VARIABLE VALUE REDUCED COST
X1 60.000000 200.000000
X2 30.000000 195.000000
X3 80.000000 190.000000
X4 0.000000 185.000000
U1 22.000000 10.000000
U2 11.000000 9.900000
U3 12.000000 9.800000
U4 0.000000 9.700000
V1 8.000000 7.000000
V2 0.000000 6.900000
V3 0.000000 6.800000
V4 0.000000 6.700000
优化建模
VARIABLE VALUE REDUCED COST
W1 431.000000 10.000000
W2 211.000000 9.900000
W3 228.000000 9.800000
W4 0.000000 9.700000
Y1 10.000000 0.000000
Y2 0.000000 0.000000
Y3 0.000000 0.000000
Y4 0.000000 0.000000
即最优解为 u1=22,u2=11,u3=12,u4=0,v1=8,v2=v3=v4
=0,w1=431,w2=211,w3=228,w4=0 (x1~x4,y1~y4不变 )；
目标函数值为 42185.80。
优化建模自己练习，或课上布置布置作业内容
Thank you very much!
§ 5.1 生产与销售计划问题
§ 5.2 有瓶颈设备的多级生产计划问题
§ 5.3 下料问题
§ 5.4 面试顺序与消防车调度问题
§ 5.5 飞机定位和飞行计划问题优化建模
§ 5.1 生产与销售计划问题优化建模
§ 5.1.1问题实例
例 5.1某公司用两种原油（ A和 B）混合加工成两种汽油（甲和乙）。甲、乙两种汽油含原油 A的最低比例分别为 50%和 60%，每吨售价分别为 4800元和
5600元。该公司现有原油 A和 B的库存量分别为 500
吨和 1000吨，还可以从市场上买到不超过 1500吨的原油 A。原油 A的市场价为：购买量不超过 500吨时的单价为 10000元 /吨；购买量超过 500吨但不超过 1000吨时，超过 500吨的部分 8000元 /吨；购买量超过 1000吨时，超过 1000吨的部分 6000元 /吨。
该公司应如何安排原油的采购和加工。
优化建模
§ 5.1.2建立模型问题分析安排原油采购、加工的目标是利润最大，题目中给出的是两种汽油的售价和原油 A的采购价，利润为销售汽油的收入与购买原油 A的支出之差。这里的难点在于原油 A的采购价与购买量的关系比较复杂，
是分段函数关系，能否及如何用线性规划、整数规划模型加以处理是关键所在。
优化建模模型建立设原油 A的购买量为 x（吨），根据题目所给数据，
采购的支出 c(x)可表为如下的分段线性函数（以下价格以千元 /吨为单位）：
5 0 0 )1( 1 0 0 0 63 0 0 0
1 0 0 0 )( 5 0 0 81 0 0 0
5 0 0 )(0 10
)(
xx
xx
xx
xc
(1)
设原油 A用于生产甲、乙两种汽油的数量分别为 x11和 x12（吨），
原油 B用于生产甲、乙两种汽油的数量分别为 x21和 x22（吨），
则总的收入为 4.8(x11+x21)+5.6(x12+x22)（千元）。
于是本例的目标函数（利润）为
)()(6.5)(8.4 22122111 xcxxxxzM ax (2)
优化建模约束条件包括加工两种汽油用的原油 A、原油 B库存量的限制，
和原油 A购买量的限制，以及两种汽油含原油 A的比例限制，
它们表示为
xxx 5 0 01211 （ 3）
1 0 0 02221 xx （ 4）
1500?x （ 5）
5.0
2111
11?
xx
x
（ 6）
6.0
2212
12?
xx
x
（ 7）
0,,,,22211211?xxxxx （ 8）
由于（ 1）式中的 c(x)不是线性函数，（ 1） ~（ 8）给出的是一个非线性规划。而且，对于这样用分段函数定义的 c(x)，
一般的非线性规划软件也难以输入和求解。能不能想办法将该模型化简，从而用现成的软件求解呢？
优化建模
§ 5.1.3 求解模型 3种解法第 1种解法 将原油 A的采购量 x分解为三个量，即用 x1，
x2,x3分别表示以价格 10,8,6千元 /吨采购的原油 A的吨数，总支出为 c(x) = 10x1+8x2+6x3，且
321 xxxx
(9)
这时目标函数（ 2）变为线性函数：
)6810()(6.5)(8.4 32122122111 xxxxxxxzM a x (10)
应该注意到，只有当以 10千元 /吨的价格购买
x1=500（吨）时，才能以 8千元 /吨的价格购买 x2
（ >0），这个条件可以表示为
0)500( 21 xx (11)
优化建模同理，只有当以 8千元 /吨的价格购买 x2=500（吨）时，
才能以 6千元 /吨的价格购买 x3（ >0），于是
0)5 0 0( 32 xx (12)
此外,x1,x2,x3的取值范围是
5 0 0,,0 321 xxx (13)
优化建模由于有非线性约束 (11),(12),(3)~(13)构成非线性规划模型。 LINGO程序：
Model:
Max= 4.8*x11 + 4.8*x21 + 5.6*x12 + 5.6*x22 - 10*x1 - 8*x2 - 6*x3;
x11+x12 < x + 500;
x21+x22 < 1000;
0.5*x11 - 0.5*x21 > 0;
0.4*x12 - 0.6*x22 > 0;
x=x1+x2+x3;
(x1 - 500) * x2=0;
(x2 - 500) * x3=0;
@bnd(0,x1,500);
@bnd(0,x2,500);
@bnd(0,x3,500);
end
优化建模将文件存储并命名为 exam0501a.lg4，
执行菜单命令,LINGO|Solve”,运行该程序得到：
Local optimal solution found.
Objective value,4800.000
Total solver iterations,26
Variable Value Reduced Cost
X11 500.0000 0.000000
X21 500.0000 0.000000
X12 0.000000 0.000000
X22 0.000000 0.000000
X1 0.000000 0.000000
X2 0.000000 0.000000
X3 0.000000 0.000000
X 0.000000 0.000000
优化建模最优解,用库存的 500吨原油 A,500吨原油 B生产 1000
吨汽油甲，不购买新的原油 A，利润为 4800（千元）
但是此时 LINGO得到的结果只是一个 局部最优解可以用菜单命令,LINGO|Options” 在,Global
Solver” 选项卡上启动全局优化（ Use Global
Solver）选项，然后重新执行菜单命令
,LINGO|Solve”,得到：
Global optimal solution found.
Objective value,5000.002
Extended solver steps,3
Total solver iterations,187
优化建模
Variable Value Reduced Cost
X11 0.000000 0.000000
X21 0.000000 0.000000
X12 1500.000 0.000000
X22 1000.000 0.000000
X1 500.0000 0.000000
X2 499.9990 0.000000
X3 0.9536707E-03 0.000000
X 1000.000 0.000000
此时 LINGO得到的结果是一个 全局最优解
（ Global optimal solution）：购买 1000吨原油 A，
与库存的 500吨原油 A和 1000吨原油 B一起，共生产
2500吨汽油乙，利润为 5000（千元），高于刚刚得到的局部最优解对应的利润 4800（千元）。
优化建模第 2种解法,
引入 0-1变量将（ 11）和（ 12）转化为线性约束令 y1=1,y2=1,y3=1分别表示以 10千元 /吨,8千元
/吨,6千元 /吨的价格采购原油 A，则约束（ 11）
和（ 12）可以替换为
112 500500 yxy
223 5 0 05 0 0 yxy
33 5 0 0 yx?
(14)
(15)
(16)
y1,y2,y3 =0或 1 (17)
优化建模
（ 3） ~（ 10），（ 13） ~（ 17）构成混合整数线性规划模型，将它输入 LINDO软件：
优化建模
Max 4.8x11+4.8x21+5.6x12+5.6x22-10x1-8x2-6x3
st
x-x1-x2-x3=0
x11+x12-x<500
x21+x22<1000
0.5x11-0.5x21>0
0.4x12-0.6x22>0
x1-500y1<0
x2-500y2<0
x3-500y3<0
x1-500y2>0
x2-500y3>0
end
int y1
int y2
int y3
优化建模运行该程序得到,
OBJECTIVE FUNCTION VALUE
1) 5000.000
VARIABLE VALUE REDUCED COST
Y1 1.000000 0.000000
Y2 1.000000 2200.000000
Y3 1.000000 1200.000000
X11 0.000000 0.800000
X21 0.000000 0.800000
X12 1500.000000 0.000000
X22 1000.000000 0.000000
X1 500.000000 0.000000
X2 500.000000 0.000000
X3 0.000000 0.400000
X 1000.000000 0.000000
这个结果与前面非线性规划模型用全局优化得到的结果相同。
优化建模第 3种解法 直接处理分段线性函数 c(x)。
（ 1）式表示的函数 c(x)如图 5-1。
c(x)
x
12000
9000
5000
0 500 1000 1500
图 5-1 分段线性函数 c(x)图形优化建模记 x轴上的分点为 b1=0,b2=500,b3=1000,b4=1500。当 x在第 1个小区间 [b1,b2]时，记 x= z1b1+z2b2,z1+z2=1,z1,z2≥0,因为 c(x)在 [b1,
b2]是线性的，所以 c(x)= z1c(b1)+z2c(b2)。同样，当 x在第 2个小区间 [b2,b3]时,x= z2b2+z3b3,z2+z3=1,z2,z3≥0,c(x)=
z2c(b2)+z3c(b3)。当 x在第 3个小区间 [b3,b4]时,x= z3b3+z4b4，
z3+z4=1,z3,z4≥ 0,c(x)= z3c(b3)+z4c(b4)。为了表示 x在哪个小区间，
引入 0-1变量 yk(k=1,2,3)，当 x在第 k个小区间时,yk=1，否则，
yk=0。这样,z1,z2,z3,z4,y1,y2,y3应满足
3432321211,,,yzyyzyyzyz
)4,3,2,1(0,14321 kzzzzz k
10,,,1 321321 或 yyyyyy
(18)
(19)
(20)
优化建模此时 x和 c(x)可以统一地表示为
43244332211 1 5 0 01 0 0 05 0 0 zzzbzbzbzbzx
（ 2） ~（ 10），（ 18） ~（ 22）也构成一个混合整数线性规划模型，可以用 LINDO求解。不过，我们还是将它输入
LINGO软件，因为其扩展性更好（即当分段函数的分段数更多时，只需要对下面程序作很小的改动）。输入的
LINGO模型如下：
43244332211 1 2 0 0 09 0 0 05 0 0 0)()()()()( zzzbczbczbczbczxc
(22)
优化建模输入的 LINGO模型如下：
Model:
SETS:
Points/1..4/,b,c,y,z;! 端点数为 4，即分段数为 3;
ENDSETS
DATA:
b=0 500 1000 1500;
c=0 5000 9000 12000;
y=,,,0; ! 增加的虚拟变量 y(4)=0;
ENDDATA
优化建模
Max= 4.8*x11 + 4.8*x21 + 5.6*x12 + 5.6*x22 -
@sum(Points,c*z);
x11+x12 < x + 500;
x21+x22 < 1000;
0.5*x11 - 0.5*x21 > 0;
0.4*x12 - 0.6*x22 > 0;
@sum(Points,b*z)=x;
@for(Points(i)|i#eq#1,z(i) <= y(i));
@for(Points(i)|i#ne#1,z(i) <= y(i-1)+y(i));
@sum(Points,y)=1;
@sum(Points,z)=1;
@for(Points,@bin(y));
end
优化建模求解，得到的结果如下（略去已知参数 b和 c的显示结果）：
Global optimal solution found.
Objective value,5000.000
Extended solver steps,0
Total solver iterations,28
优化建模
Variable Value Reduced Cost
X11 0.000000 0.000000
X21 0.000000 1.600000
X12 1500.000 0.000000
X22 1000.000 0.000000
X 1000.000 0.000000
Y( 1) 0.000000 -4600.000
Y( 2) 0.000000 -1200.000
Y( 3) 1.000000 0.000000
Y( 4) 0.000000 0.000000
Z( 1) 0.000000 0.000000
Z( 2) 0.000000 0.000000
Z( 3) 1.000000 0.000000
Z( 4) 0.000000 200.0000
优化建模可见，得到的最优解和最优值与第 2种解法相同。
备注 这个问题的关键是处理分段线性函数，我们推荐化为整数线性规划模型的第 2,3种解法，第 3种解法更具一般性，其做法如下。
设一个 n段线性函数 f(x)的分点为
11 nn bbb?
引入 zk 将 x和 f(x)表示为
1
1
n
k
kk bzx
1
1
)()(
n
k
kk bfzxf
(23)
(24)
优化建模
zk 和 0-1变量 yk满足
nnnnn yzyyzyyzyz 1121211,,,,?
10,121 或 kn yyyy?
)1,,2,1(01121 nkzzzz kn,
(25)
(26)
(27)
优化建模
§ 5.2 有瓶颈设备的多级生产计划问题优化建模
§ 5.2.1 问题实例在给定的外部需求和生产能力等限制条件下，按照生产总费用最小编制未来若干个生产周期的最优生产计划，这种问题在文献上一般称为批量问题
（ Lotsizing Problems）。
我们通过下面的具体例子来说明这种多级生产计划问题的优化模型。这里“多级”的意思是需要考虑产品是通过多个生产阶段（工艺过程）生产出来的。
优化建模例 5.2 某工厂的主要任务是通过组装生产产品 A，
用于满足外部市场需求。
A产品的产品构成与组装过程见图 5-2：即 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；
依此类推。
优化建模瓶颈设备加工
A
B C
D E F G
5 7
9 11 13 15
图 5-2 产品构成与组装过程图优化建模表 5-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周（即每次制定未来 6
周的生产计划），只有最终产品 A有外部需求，目前收到的订单的需求件数按周的分布如表 5-1第 2行所示。部件 B,C
是在该工厂最关键的设备（可以称为瓶颈设备）上组装出来的，瓶颈设备的生产能力非常紧张，具体可供能力如表 5-1
第 3行所示（第 2周设备检修，不能使用）。 B,C的能力消耗系数分别为 5和 8，即生产 1件 B需要占用 5个单位的能力，
即生产 1件 C需要占用 8个单位的能力。
对于每种零部件或产品，如果工厂在某一周订购或者生产该零部件或产品，工厂需要付出一个与订购或生产数量无关的固定成本（称为生产准备费用）；如果某一周结束时该零部件或产品有库存存在，则工厂必须付出一定的库存费用（与库存数量成正比）。这些数据在表 5-1第 5,6行给出。
优化建模按照工厂的信誉要求，目前接收的所有订单到期必须全部交货，不能有缺货发生；此外，不妨简单地假设目前该企业没有任何零部件或产品库存，也不希望第 6周结束后留下没有任何零部件或产品库存。最后，假设不考虑生产提前期，
即假设当周采购的零件马上就可用于组装，组装出来的部件也可以马上用于当周组装成品 A。
在上述假设和所给数据下，如何制定未来 6周的生产计划？
优化建模
§ 5.2.2 建立模型问题分析 这个例子考虑的是在有限的计划期内,给定产品结构、生产能力和相关费用及零部件或成品（以下统称为生产项目）在离散的时间段上（这里是周，也可以是天、月等）的外部需求之后,确定每一生产项目在每一时间段上的生产量 (即批量 ),使总费用最小,由于每一生产项目在每一时间段上生产时必须经过生产准备
(Setup),所以通常的讨论中总费用至少应考虑生产准备费用和库存费用,
其实，细心的读者一定会问：是否需要考虑生产的直接成本（如原材料成本、人力成本、电力成本等）？
优化建模符号说明为了建立这类问题的一般模型，我们定义如下数学符号：
N -------- 生产项目总数（本例中 N=7） ;
T -------- 计划期长度（本例中 T=6） ;
K -------- 瓶颈资源种类数（本例中 K=1） ;
M -------- 一个充分大的正数，在模型中起到使模型线性化的作用 ;
优化建模
dit,
----- 项目 i在 t时段的外部需求
（本例中只有产品 A有外部需求） ;
Xit,----- 项目 i在 t时段的生产批量 ;
Iit,----- 项目 i在 t时段的库存量 ;
Yit,
----- 项目 i在 t时段是否生产的标志
(0：不生产,1：生产 );
rij,----- 产品结构中项目 j对项目 i的消耗系数 ;
S(i) ----- 产品结构中项目 i的直接后继项目集合 ;
优化建模
sit,----- 项目 i在 t时段生产时的生产准备费用 ;
hit,----- 项目 i在 t时段的单件库存费用 ;
Ckt,----- 资源 k在 t时段的能力上限 ;
akit,,
--- 项目 i在 t时段生产时,生产单个产品占用资源 k
的能力 ;
δ(x) ---- 这个函数当且仅当 x>0时取值 1,否则取值 0.
在上述数学符号中，只有 Xit,Iit,Yit,为决策变量 ;
其余均为已知的计划参数。
优化建模其实，真正的生产计划只是要求确定 X
i t,
就可以了，因为知道
X i t,以后 I i t,,Y i t,也就自然确定了。另外，在我们的具体例子中参数 s
i t,
,h
i t,
,a
k i t,,
其实只与项目 i 有关，而不随时段 t 变化，
我们这里加上下标 t 只是为了使模型能够更一般化。
优化建模目标函数这个问题的目标是使生产准备费用和库存费用的总和最小。因此，目标函数应该是每个项目在每个时段上的生产准备费用和库存费用的总和，即
N
i
T
t
titititi IhYs
1 1
,,,,)(
(28)
约束条件这个问题中的约束有这么几类：每个项目的物流应该守恒、资源能力限制应该满足、每时段生产某项目前必须经过生产准备和非负约束
（对 Yi,j是 0-1约束）。
优化建模
TtNiXrdIXI
iSj tjjititititi
,,1,,,1
)(,,,,,1,
(29)
资源能力限制比较容易理解，即
TtKkCXa
N
i
tktitik,,1,,,1
1
,,,,
(30)
所谓物流守恒（假设 Ii,0 =0）
优化建模
(31)
TtNiIYMYX titititi,,1,,,10,},1,0{,0,,,,
每时段生产某项目前必须经过生产准备，也就是说当
Xit=0时 Yit=0； Xit>0时 Yit=1。这本来是一个非线性约束，
但是通过引入参数 M（很大的正数，表示每个项目每个时段的最大产量）可以化成线性约束，即：
总结,这个问题的优化模型就是在约束（ 29）（ 30）
（ 31）下使目标函数（ 28）达到最小。
优化建模
§ 5.2.3 求解模型本例生产项目总数 N=7(A,B,C,D,E,F,G),计划期长度 T=6（周），瓶颈资源种类数 K=1。只有 A
有外部需求，所以 di,t中只有 d1,t可以取非零需求，即表 5-1中的第 2行的数据，其他全部为零。 参数 si,t、
hi,t只与项目 i有关，而不随时段 t变化，所以可以略去下标 t，其数值就是表 5-1中的最后两行数据。
由于只有一种资源，参数 Ck,t可以略去下标 k，其数值就是表 5-1中的第 3行的数据；而 ak,I,t只与项目 i有关，
而不随时段 t变化，所以可以同时略去下标 k和 t，即
a2=5,a3=8（其他 ai为 0）。从图 6-2中容易得到项目 i的直接后继项目集合 S(i)和消耗系数。
优化建模准备以下的数据文件（文本文件 exam0502.LDT，可以看到其中也可以含有注释语句）：
! 项目集合 ;
A B C D E F G~
! 计划期集合 ;
1 2 3 4 5 6~
! 需求 ;
40 0 100 0 90 10
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0~
优化建模
! 能力 ;
100000 5000 5000 1000 1000~
! 生产准备费 ;
400 500 1000 300 200 400 100~
! 库存费 ;
12 0.6 1.0 0.04 0.03 0.04 0.04~
! 对能力的消耗系数；
0 5 8 0 0 0 0~
优化建模
! 项目间的消耗系数,req(i,j)表示 j用到多少 i;
0 0 0 0 0 0 0
5 0 0 0 0 0 0
7 0 0 0 0 0 0
0 9 0 0 0 0 0
0 11 0 0 0 0 0
0 0 13 0 0 0 0
0 0 15 0 0 0 0
! 数据结束 ;
优化建模对本例,A的外部总需求为 240，所以任何项目的产量不会超过 240× 7× 15<25000（从图 6-2
可以知道，这里 7× 15已经是每件产品 A对任意一个项目的最大的消耗系数了），所以取
M=25000就已经足够了。
本例中的具体模型可以如下输入 LINGO软件：
MODEL:
TITLE 瓶颈设备的多级生产计划 ;
! 从文本文件 exam0502.LDT中读取数据 ;
优化建模
SETS:
! PART = 项目集合,Setup = 生产准备费,Hold = 单件库存成本，
A = 对瓶颈资源的消耗系数 ;
PART/ @FILE( 'exam0502.LDT')/,Setup,Hold,
A;
! TIME = 计划期集合,Capacity = 瓶颈设备的能力 ;
TIME / @FILE( 'exam0502.LDT')/,Capacity;
! USES = 项目结构关系,Req = 项目之间的消耗系数 ;
USES( PART,PART),Req;
! PXT = 项目与时间的派生集合,Demand = 外部需求,
X = 产量（批量）,Y = 0/1变量,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 #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( 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( 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 = @FILE( 'exam0502.LDT');
Capacity = @FILE( 'exam0502.LDT');
Setup = @FILE( 'exam0502.LDT');
Hold = @FILE( 'exam0502.LDT');
A = @FILE( 'exam0502.LDT');
Req = @FILE( 'exam0502.LDT');
ENDDATA
END 注意：由于本例有 42个 0-1变量，
LINGO演示版是无法求解的优化建模表 5-2 生产计划的最后结果周次 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
LINDO求解,得到最优目标函数值为 9245,结果如下：
优化建模
§ 5.3 下料问题优化建模
§ 5.3 下料问题生产中常会遇到通过切割、剪裁、冲压等手段，
将原材料加工成所需大小这种工艺过程，称为原料下料（ cutting stock）问题。按照进一步的工艺要求，确定下料方案，使用料最省，或利润最大，
是典型的优化问题。本节通过两个实例讨论用数学规划模型解决这类问题的方法。
优化建模
§ 5.3.1钢管下料问题例 5.3 某钢管零售商从钢管厂进货，将钢管按照顾客的要求切割后售出。从钢管厂进货时得到的原料钢管都是 19米长。
1) 现有一客户需要 50根 4米长,20根 6米长和 15根 8米长的钢管。应如何下料最节省？
2) 零售商如果采用的不同切割模式太多，将会导致生产过程的复杂化，从而增加生产和管理成本，所以该零售商规定采用的不同切割模式不能超过 3种。
此外，该客户除需要 1）中的三种钢管外，还需要
10根 5米长的钢管。应如何下料最节省？
优化建模问题 1）的求解问题分析 首先，应当确定哪些切割模式是可行的。
所谓一个切割模式，是指按照客户需要在原料钢管上安排切割的一种组合。例如，我们可以将 19米长的钢管切割成 3根 4米长的钢管，余料为 7米显然，可行的切割模式是很多的。
其次，应当确定哪些切割模式是合理的。通常假设一个合理的切割模式的余料不应该大于或等于客户需要的钢管的最小尺寸。在这种合理性假设下，切割模式一共有 7种，如表 5-3所示。
优化建模表 5-3 钢管下料的合理切割模式
4米钢管根数 6米钢管根数 8米钢管根数 余料（米）
模式 1 4 0 0 3
模式 2 3 1 0 1
模式 3 2 0 1 3
模式 4 1 2 0 3
模式 5 1 1 1 1
模式 6 0 3 0 1
模式 7 0 0 2 3
优化建模问题化为在满足客户需要的条件下，按照哪些种合理的模式，切割多少根原料钢管，最为节省。而所谓节省，可以有两种标准，一是切割后剩余的总余料量最小，二是切割原料钢管的总根数最少。
下面将对这两个目标分别讨论。
优化建模模型建立决策变量 用 xi 表示按照第 i种模式（ i=1,2,…,7 ）
切割的原料钢管的根数，显然它们应当是非负整数。
决策目标 以切割后剩余的总余料量最小为目标，
则由表 1可得
76543211 3333 xxxxxxxZM i n (32)
以切割原料钢管的总根数最少为目标，则有
76543212 xxxxxxxZM i n (33)
下面分别在这两种目标下求解。
优化建模约束条件 为满足客户的需求，按照表 1应有
50234 54321 xxxxx
2032 6542 xxxx
152 753 xxx
优化建模模型求解
1,将（ 32），（ 34） ~（ 36）构成的整数线性规划模型
（加上整数约束）输入 LINDO如下：
Title 钢管下料 - 最小化余量
Min 3x1 + x2 + 3x3 + 3x4 + x5 + x6 + 3x7
s.t.
4x1 + 3x2 + 2x3 + x4 + x5 >= 50
x2 + 2x4 + x5 + 3x6 >= 20
x3 + x5 + 2x7 >= 15
end
gin 7
优化建模求解可以得到最优解如下：
OBJECTIVE FUNCTION VALUE
1) 27.00000
VARIABLE VALUE REDUCED COST
X1 0.000000 3.000000
X2 12.000000 1.000000
X3 0.000000 3.000000
X4 0.000000 3.000000
X5 15.000000 1.000000
X6 0.000000 1.000000
X7 0.000000 3.000000
优化建模即按照模式 2切割 12根原料钢管，按照模式 5切割 15根原料钢管，共 27根，总余料量为 27米。
显然，在总余料量最小的目标下，最优解将是使用余料尽可能小的切割模式（模式 2和 5的余料为 1米），这会导致切割原料钢管的总根数较多。
优化建模
2,将（ 33） ~（ 36）构成的整数线性规划模型
（加上整数约束）输入 LINDO：
Title 钢管下料 - 最小化钢管根数
Min x1 + x2 + x3 + x4 + x5 + x6 + x7
s.t.
4x1 + 3x2 + 2x3 + x4 + x5 >= 50
x2 + 2x4 + x5 + 3x6 >= 20
x3 + x5 + 2x7 >= 15
end
gin 7
优化建模求解，可以得到最优解如下：
OBJECTIVE FUNCTION VALUE
1) 25.00000
VARIABLE VALUE REDUCED COST
X1 0.000000 1.000000
X2 15.000000 1.000000
X3 0.000000 1.000000
X4 0.000000 1.000000
X5 5.000000 1.000000
X6 0.000000 1.000000
X7 5.000000 1.000000
优化建模即按照模式 2切割 15根原料钢管，按模式 5切割 5根，按模式 7切割 5根，共 27根，可算出总余料量为 35米。与上面得到的结果相比，总余料量增加了 8米，但是所用的原料钢管的总根数减少了 2根。在余料没有什么用途的情况下，
通常选择总根数最少为目标。
优化建模问题 2）的求解问题分析 按照解问题 1）的思路，可以通过枚举法首先确定哪些切割模式是可行的。但由于需求的钢管规格增加到
4种，所以枚举法的工作量较大。下面介绍的整数非线性规划模型，可以同时确定切割模式和切割计划，是带有普遍性的方法。
同 1）类似，一个合理的切割模式的余料不应该大于或等于客户需要的钢管的最小尺寸（本题中为 4米），切割计划中只使用合理的切割模式，而由于本题中参数都是整数，
所以合理的切割模式的余量不能大于 3米。此外，这里我们仅选择总根数最少为目标进行求解。
优化建模模型建立决策变量 由于不同切割模式不能超过 3种，可以用 xi 表示按照第 i种模式（ i=1,2,3）切割的原料钢管的根数，
显然它们应当是非负整数。 设 所使用的第 i种切割模式下每根原料钢管生产 4米长,5米长,6米长和 8米长的钢管数量分别为 r1i,r2i,r3i,r4i（ 非负整数 ）。
决策目标 以切割原料钢管的总根数最少为目标，即目标为
321 xxxM i n
（ 37）
优化建模约束条件 为满足客户的需求，应有
50313212111 xrxrxr (38)
10323222121 xrxrxr
20333232131 xrxrxr
15343242141 xrxrxr
(39)
(40)
(41)
优化建模每一种切割模式必须可行、合理，所以每根原料钢管的成品量不能超过 19米，也不能少于 16米（余量不能大于 3
米），于是
19865416 41312111 rrrr (42)
19865416 42322212 rrrr (43)
19865416 43332313 rrrr (44)
优化建模模型求解
（ 37） ~（ 44）构成这个问题的优化模型。由于在（ 38） ~
（ 41）式中出现了决策变量的乘积，所以这是一个整数非线性规划模型，虽然用 LINGO软件可以直接求解，但我们发现在较低版本的 LINGO软件中需要运行很长时间也难以得到最优解。为了减少运行时间，可以增加一些显然的约束条件，从而缩小可行解的搜索范围。
例如，由于 3种切割模式的排列顺序是无关紧要的，所以不妨增加以下约束：
321 xxx
（ 45）
优化建模又例如，我们注意到所需原料钢管的总根数有着明显的上界和下界。首先，无论如何，原料钢管的总根数不可能少于
2619 158206105504 （根）
其次，考虑一种非常特殊的生产计划：第一种切割模式下只生产 4米钢管，一根原料钢管切割成 4根 4米钢管，为满足 50根 4米钢管的需求，需要 13根原料钢管；第二种切割模式下只生产 5米,6米钢管，一根原料钢管切割成 1根 5
米钢管和 2根 6米钢管，为满足 10根 5米和 20根 6米钢管的需求，需要 10根原料钢管；
优化建模第三种切割模式下只生产 8米钢管，一根原料钢管切割成 2
根 8米钢管，为满足 15根 8米钢管的需求，需要 8根原料钢管。于是满足要求的这种生产计划共需 13+10+8=31根原料钢管，这就得到了最优解的一个上界。所以可增加以下约束：
3126 321 xxx (46)
将（ 37） ~（ 46）构成的模型输入 LINGO如下：
优化建模将（ 37） ~（ 46）构成的模型输入 LINGO如下：
model:
Title 钢管下料 - 最小化钢管根数的 LINGO模型 ;
min=x1+x2+x3;
x1*r11+x2*r12+x3*r13 >=50;
x1*r21+x2*r22+x3*r23 >=10;
x1*r31+x2*r32+x3*r33 >=20;
x1*r41+x2*r42+x3*r43 >=15;
4*r11+5*r21+6*r31+8*r41 <=19;
4*r12+5*r22+6*r32+8*r42 <=19;
4*r13+5*r23+6*r33+8*r43 <=19;
4*r11+5*r21+6*r31+8*r41 >=16;
4*r12+5*r22+6*r32+8*r42 >=16;
4*r13+5*r23+6*r33+8*r43 >=16;
x1+x2+x3 >= 26;
x1+x2+x3 <= 31;
x1>=x2;
x2>=x3;
@gin(x1); @gin(x2); @gin(x3);
@gin(r11);@gin(r12);@gin(r13);
@gin(r21);@gin(r22);@gin(r23);
@gin(r31);@gin(r32);@gin(r33);
@gin(r41);@gin(r42);@gin(r43);
end
优化建模经过 LINGO求解，得到输出如下：
Local optimal solution found.
Objective value,28.00000
Extended solver steps,72
Total solver iterations,3404
Model Title,钢管下料 -最小化钢管根数的 LINGO模型优化建模
Variable Value Reduced Cost
X1 10.00000 1.000000
X2 10.00000 1.000000
X3 8.000000 1.000000
R11 2.000000 0.000000
R12 3.000000 0.000000
R13 0.000000 0.000000
R21 1.000000 0.000000
R22 0.000000 0.000000
R23 0.000000 0.000000
R31 1.000000 0.000000
R32 1.000000 0.000000
R33 0.000000 0.000000
R41 0.000000 0.000000
R42 0.000000 0.000000
R43 2.000000 0.000000
优化建模即按照模式 1,2,3分别切割 10,10,8根原料钢管，使用原料钢管总根数为 28根。第一种切割模式下一根原料钢管切割成 3根 4米钢管和 1根 6米钢管；第二种切割模式下一根原料钢管切割成 2根 4米钢管,1根 5米钢管和 1根 6米钢管；
第三种切割模式下一根原料钢管切割成 2根 8米钢管。
如果充分利用 LINGO建模语言的能力，使用集合和属性的概念，可以编写以下 LINGO程序，这种方法更具有一般的通用性，并有利于输入更大规模的下料问题的优化模型：
优化建模
model:
Title 钢管下料 - 最小化钢管根数的 LINGO模型 ;
SETS,
NEEDS/1..4/:LENGTH,NUM;
! 定义基本集合 NEEDS及其属性 LENGTH,NUM;
CUTS/1..3/:X;
! 定义基本集合 CUTS及其属性 X;
PATTERNS(NEEDS,CUTS):R;
! 定义派生集合 PATTERNS（这是一个稠密集合）及其属性 R;
ENDSETS
DATA:
LENGTH=4 5 6 8;
NUM=50 10 20 15;
CAPACITY=19;
ENDDATA
min=@SUM(CUTS(I),X(I) );
优化建模
!目标函数 ;
@FOR(NEEDS(I),@SUM(CUTS(J),X(J)*R(I,J) ) >NUM(I) );
!满足需求约束 ;
@FOR(CUTS(J),@SUM(NEEDS(I),LENGTH(I)*R(I,J) ) <CAPACITY );
!合理切割模式约束 ;
@FOR(CUTS(J),@SUM(NEEDS(I),LENGTH(I)*R(I,J) ) >CAPACITY
-@MIN(NEEDS(I):LENGTH(I)) );
!合理切割模式约束 ;
@SUM(CUTS(I),X(I) ) >26; @SUM(CUTS(I),X(I) ) <31;
!人为增加约束 ;
@FOR(CUTS(I)|I#LT#@SIZE(CUTS):X(I)>X(I+1) );
!人为增加约束 ;
@FOR(CUTS(J),@GIN(X(J)) ) ;
@FOR(PATTERNS(I,J),@GIN(R(I,J)) );
end
求解这个模型，得到的结果与前面的结果完全相同。
优化建模
§ 5.3.2易拉罐下料问题例 5.4 某公司采用一套冲压设备生产一种罐装饮料的易拉罐，这种易拉罐是用镀锡板冲压制成的（参见图 5-3）。易拉罐为圆柱形，包括罐身、上盖和下底，
罐身高 10厘米，上盖和下底的直径均为 5厘米。该公司使用两种不同规格的镀锡板原料，规格 1的镀锡板为正方形，边长 24厘米；规格 2的镀锡板为长方形，
长、宽分别为 32和 28厘米。由于生产设备和生产工艺的限制，对于规格 1的镀镀锡板原料，只可以按照图 2
中的模式 1,2或 3进行冲压；对于规格 2的镀锡板原料只能按照模式 4进行冲压。使用模式 1,2,3,4进行每次冲压所需要的时间分别为 1.5,2,1,3（秒）。
优化建模模式 1 模式 2 模式 3
模式 4
上盖下底罐身图 5-3 易拉罐下料模式优化建模该工厂每周工作 40小时，每周可供使用的规格 1,2的镀锡板原料分别为 5万张和 2万张。目前每只易拉罐的利润为 0.10元，
原料余料损失为 0.001元 / 厘米 2（如果周末有罐身、上盖或下底不能配套组装成易拉罐出售，也看作是原料余料损失）。
工厂应如何安排每周的生产？
已知上盖和下底的直径 d=5厘米，可得其面积为
4/2ds? 19.6厘米
2周长为 dL 15,7 厘米；已知罐身高 h = 1 0 厘米,
可得其面积为 hLS 157.1 厘米
2
。
于是模式 1 下的余料损失为 9.2 221024 2 Ss 厘米
2
。
同理计算其它模式下的余料损失,
并可将 4 种冲压模式的特征归纳如表 5 - 4 。
优化建模表 5-4 4种冲压模式的特征罐身个数 底、盖个数 余料损失
（厘米 2）
冲压时间
（秒）
模式 1 1 10 222.6 1.5
模式 2 2 4 183.3 2
模式 3 0 16 261.8 1
模式 4 4 5 169.5 3
问题的目标显然应是易拉罐的利润扣除原料余料损失后的净利润最大，约束条件除每周工作时间和原料数量外，还要考虑罐身和底、
盖的配套组装。
优化建模模型建立决策变量 用 xi 表示按照第 i种模式的冲压次数（ i=1,2,3,4）,y1表示一周生产的易拉罐个数。为计算不能配套组装的罐身和底、盖造成的原料损失，用 y2表示不配套的罐身个数,y3表示不配套的底、盖个数。
虽然实际上 xi和 y1,y2,y3应该是整数。但是由于生产量相当大，可以把它们看成是实数，从而用线性规划模型处理。
决策目标 假设每周生产的易拉罐能够全部售出，公司每周的销售利润是 0.1y1。原料余料损失包括两部分,4种冲压模式下的余料损失，和不配套的罐身和底、盖造成的原料损失。按照前面的计算及表 2的结果，总损失为 0.001(222.6x1 + 183.3x2 +
261.8x3 + 169.5x4 + 157.1y2 +19.6y3)。
优化建模于是，决策目标为
)6.191.1575.1698.2613.1836.222(001.01.0 3243211 yyxxxxyM a x
(47)
约束条件时间约束：每周工作时间不超过 40小时 =144000（秒），由表 2最后一列得
144000325.1 4321 xxxx (48)
原料约束：
每周可供使用的规格 1,2的镀锡板原料分别为 50000张和 20000张，即
5 0 0 0 0321 xxx (49)
2 0 0 0 04?x (50)
优化建模配套约束,由表 2一周生产的罐身个数为 x1 + 2x2 + 4x4,一周生产的底、盖个数为 10x1 + 4x2 + 16x3+ 5x4，因为应尽可能将它们配套组装成易拉罐销售。所以 y1满足
}2/)516410(,42m i n { 43214211 xxxxxxxy (51)
这时不配套的罐身个数 y2，和不配套的底、盖个数 y3应为
14212 42 yxxxy
(52)
143213 2516410 yxxxxy
(53)
优化建模
（ 47） ~（ 53）就是我们得到的模型，其中（ 51）是一个非线性关系，
不易直接处理，
但是它可以等价为以下两个线性不等式：
4211 42 xxxy
(54)
2/)516410( 43211 xxxxy (55)
模型求解将模型（ 47） ~（ 50）和（ 52） ~（ 55）直接输入 LINDO（输入
LINGO也可以），求解时 LINDO发出警告信息（程序和警告信息参见图 5-4）。 图中错误编号,66”的含义（参见第 4章的错误代码表）是：模型中数据不平衡，所以发出警告信息（注意，只是警告信息，所以仍然可以继续求解）。求解结果是：
优化建模
OBJECTIVE FUNCTION VALUE
1) 4298.337
VARIABLE VALUE REDUCED COST
Y1 160250.000000 0.000000
X1 0.000000 0.000050
X2 40125.000000 0.000000
X3 3750.000000 0.000000
X4 20000.000000 0.000000
Y2 0.000000 0.223331
Y3 0.000000 0.036484
优化建模图 5-4 模型中数据不平衡的警告信息优化建模这个结果可靠吗？由于 LINDO警告模型中数据之间的数量级差别太大，所以我们可以进行预处理，缩小数据之间的差别。实际上，约束（ 48） ~（ 50）中右端项的数值过大（与左端的系数相比较）,LINDO在计算中容易产生比较大的误差，所以出现此警告信息。
为了解决这一问题，可以将所有决策变量扩大 10000倍
（相当于 xi以万次为单位,yi以万件为单位）。此时，目标（ 47）可以保持不变（记住得到的结果单位为万元就可以了），而约束（ 48） ~（ 50）改为
4.14325.1 4321 xxxx (56)
5321 xxx (57)
24?x (58)
优化建模将模型（ 47）和（ 52） ~（ 58）输入 LINDO:
! 易拉罐下料：均衡数据
Max 0.100y1 - 0.2226x1 - 0.1833x2 - 0.2618x3 - 0.1695 x4 - 0.1571y2 - 0.0196y3
s.t.
1.5x1 + 2.0x2 + 1.0x3 +3.0x4 <= 14.4
x1 + x2 + x3 <= 5
x4 <= 2
x1 + 2x2 + 4x4 - y1 >=0
10x1 + 4x2 + 16x3+ 5x4 - 2y1 >=0
x1 + 2x2 + 4x4 - y1 - y2 =0
10x1 + 4x2 + 16x3+ 5x4 - 2y1 - y3=0
end
优化建模求解得到,
OBJECTIVE FUNCTION VALUE
1) 0.4298337
VARIABLE VALUE REDUCED COST
Y1 16.025000 0.000000
X1 0.000000 0.000050
X2 4.012500 0.000000
X3 0.375000 0.000000
X4 2.000000 0.000000
Y2 0.000000 0.223331
Y3 0.000000 0.036484
即模式 1不使用，模式 2使用 40125次，模式 3使用 3750次，模式 4使用 20000次，可生产易拉罐 160250个，罐身和底、盖均无剩余，净利润为 4298元。
优化建模
5.4 面试顺序与消防车调度问题优化建模面试顺序问题例 5.5 有 4名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先找公司秘书初试，
然后到部门主管处复试，最后到经理处参加面试，并且不允许插队（即在任何一个阶段 4名同学的顺序是一样的）。由于 4名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如表 5-5所示（单位：
分钟）。这 4名同学约定他们全部面试完以后一起离开公司。假定现在时间是早晨 8,00，请问他们最早何时能离开公司？
优化建模表 5-5 面试时间要求秘书初试 主管复试 经理面试同学甲 13 15 20
同学乙 10 20 18
同学丙 20 10 10
同学丁 8 10 15
优化建模建立模型实际上，这个问题就是要安排 4名同学的面试顺序，使完成全部面试所花费的时间最少。
记 tij为第 i名同学参加第 j阶段面试需要的时间 (已知 )，令 xij表示第 i名同学参加第 j阶段面试的开始时刻
(不妨记早上 8,00面试开始为 0时刻 )(i=1,2,3,4； j=1,
2,3),T为完成全部面试所花费的最少时间。
优化目标为
33M a xM in iii txT
优化建模
a,时间先后次序约束 (每人只有参加完前一个阶段的面试后才能进入下一个阶段 )：
xij+ tij?xi,j+1 (i=1,2,3,4； j=1,2)
b.每个阶段 j同一时间只能面试 1名同学：用 0-1变量 yik表示第 k名同学是否排在第 i名同学前面 (1表示是，
0表示否 )，则
xij+ tij–xkj?Tyik (i,k=1,2,3,4; j=1,2,3; i<k)
xkj+ tkj–xij?T(1–yik) (i,k=1,2,3,4; j=1,2,3; i<k)
约束条件：
优化建模可以将非线性的优化目标改写为如下线性优化目标：
Min T
s.t,T? x13+ t13
T? x23+ t23
T? x33+ t33
T? x43+ t43
优化建模
Min T
s.t,xij+ tij?xi,j+1 (i=1,2,3,4； j=1,2)
xij+ tij–xkj?Tyik (i,k=1,2,3,4; j=1,2,3; i<k)
xkj+ tkj–xij?T(1–yik) (i,k=1,2,3,4; j=1,2,3; i<k)
xi3+ ti3?T (i=1,2,3,4)
这个问题的 0-1非线性规划模型 (当然所有变量还有非负约束，变量 yik还有 0-1约束 ),
优化建模
Model:
min =T;
T >= x13+ t13;
T >= x23+ t23;
T >= x33+ t33;
T >= x43+ t43;
x11+ t11 <= x12;
x12+ t12 <= x13;
x21+ t21 <= x22;
x22+ t22 <= x23;
x31+ t31 <= x32;
x32+ t32 <= x33;
x41+ t41 <= x42;
x42+ t42 <= x43;
求解模型这个模型可以如下输入 LINGO：
优化建模
x11+ t11 - x21<= T*y12;
x21+ t21 - x11<= T*(1-y12);
x12+ t12 - x22<= T*y12;
x22+ t22 - x12<= T*(1-y12);
x13+ t13 - x23<= T*y12;
x23+ t23 - x13<= T*(1-y12);
x11+ t11 - x31<= T*y13;
x31+ t31 - x11<= T*(1-y13);
x12+ t12 - x32<= T*y12;
x32+ t32 - x12<= T*(1-y13);
x13+ t13 - x33<= T*y13;
x33+ t33 - x13<= T*(1-y13);
x11+ t11 - x41<= T*y14;
x41+ t41 - x11<= T*(1-y14);
x12+ t12 - x42<= T*y14;
x42+ t42 - x12<= T*(1-y14);
优化建模
x13+ t13 - x43<= T*y14;
x43+ t43 - x13<= T*(1-y14);
x21+ t21 - x31<= T*y23;
x31+ t31 - x21<= T*(1-y23);
x22+ t22 - x32<= T*y23;
x32+ t32 - x32<= T*(1-y23);
x23+ t23 - x33<= T*y23;
x33+ t33 - x23<= T*(1-y23);
x21+ t21 - x41<= T*y24;
x41+ t41 - x21<= T*(1-y24);
x22+ t22 - x42<= T*y24;
x42+ t42 - x22<= T*(1-y24);
x23+ t23 - x43<= T*y24;
x43+ t43 - x23<= T*(1-y24);
x31+ t31 - x41<= T*y34;
x41+ t41 - x31<= T*(1-y34);
优化建模
x32+ t32 - x42<= T*y34;
x42+ t42 - x32<= T*(1-y34);
x33+ t33 - x43<= T*y34;
x43+ t43 - x33<= T*(1-y34);
t11=13;
t12=15;
t13=20;
t21=10;
t22=20;
t23=18;
t31=20;
t32=16;
t33=10;
t41=8;
t42=10;
t43=15;
优化建模
@bin(y12);
@bin(y13);
@bin(y14);
@bin(y23);
@bin(y24);
@bin(y34);
End
优化建模用 LINGO求解得到,
Local optimal solution found at iteration,4357
Objective value,84.00000
Variable Value Reduced Cost
T 84.00000 0.000000
X13 36.00000 0.000000
T13 20.00000 0.000000
X23 56.00000 0.000000
T23 18.00000 0.000000
X33 74.00000 0.000000
T33 10.00000 0.000000
X43 21.00000 0.000000
T43 15.00000 0.000000
X11 8.000000 0.000000
T11 13.00000 0.000000
X12 21.00000 0.000000
T12 15.00000 0.000000
优化建模
Variable Value Reduced Cost
X21 21.00000 0.000000
T21 10.00000 0.000000
X22 36.00000 0.000000
T22 20.00000 0.000000
X31 37.50000 0.000000
T31 20.00000 0.000000
X32 57.75000 0.000000
T32 16.00000 0.000000
X41 0.000000 0.9999970
T41 8.000000 0.000000
X42 11.00000 0.000000
T42 10.00000 0.000000
Y12 0.000000 -83.99950
Y13 0.000000 0.000000
Y14 1.000000 83.99950
Y23 0.000000 -83.99950
Y24 1.000000 0.000000
Y34 1.000000 0.000000
即所有面试完成至少需要 84分钟，面试顺序为 4-1-2-3
(即丁 -甲 -乙 -丙 )。
早上 8:00面试开始，
最早 9:24面试可以全部结束。
优化建模同样，如果利用 LINGO的建模语言，可以编写一个更一般的 LINGO模型。先准备一个数据文件 (文本文件 exam0505.txt)，其中的内容如下：
! 被面试者集合 ;
1 2 3 4~
! 面试阶段的集合 ;
1 2 3~ !
已知的面试所需要的时间 ;
13 15 20
10 20 18
20 16 10
8 10 15
! 数据结束 ;
优化建模
LINGO模型如下：
Model:
Title 面试问题 ;
SETS:
! Person = 被面试者集合,Stage = 面试阶段的集合 ;
Person/@FILE(exam0505.txt)/;
Stage/@FILE(exam0505.txt)/;
! T = 已知的面试所需要的时间,X = 面试开始时间 ;
PXS(Person,Stage),T,X;
! Y(i,k) = 1,k排在 i前,0：否则 ;
PXP(Person,Person)|&1 #LT# &2,Y;
ENDSETS
DATA,
T=@FILE(exam0505.txt);
ENDDATA
优化建模
[obj] min =MAXT;
! MAXT是面试的最后结束时间 ;
MAXT >= @max(PXS(i,j)|j#EQ#@size(stage),x(i,j)+t(i,j));
!只有参加完前一个阶段的面试后才能进入下一个阶段 ;
@for(PXS(i,j)|j#LT#@size(stage):[ORDER]x(i,j)+t(i,j)<x(i,j+1));
! 同一时间只能面试 1名同学 ;
@for(Stage(j):
@for(PXP(i,k):[SORT1]x(i,j)+t(i,j)-x(k,j)<MAXT*Y(i,k) );
@for(PXP(i,k):[SORT2]x(k,j)+t(k,j)-x(i,j)<MAXT*(1-Y(i,k)) );
);
@for(PXP,@bin(y));
End
优化建模求解这个模型，得到的结果与前面的完全相同。
可以很清楚地看到，使用 LINGO建模语言的集合和属性概念，得到的模型具有非常好的结构性，反映了相应的优化模型的本质，目标、决策变量、约束一清二楚，容易阅读和理解，而且还可以让数据与程序完全分离，这种优越性是 LINDO软件无法与之相比的。
优化建模消防车调度问题例 5.6 某市消防中心同时接到了三处火警报告。
根据当前的火势，三处火警地点分别需要 2辆,2辆和
3辆消防车前往灭火。三处火警地点的损失将依赖于消防车到达的及时程度：记 tij为第 j辆消防车到达火警地点 i的时间 (分钟 )，则三处火警地点的损失分别为,
6t11+4t12,7t21+3t22,9t31+8t32+5t33。
目前可供消防中心调度的消防车正好有 7辆，分别属于三个消防站 (可用消防车数量分别为 3辆,2辆、
2辆 )。消防车从三个消防站到三个火警地点所需要的时间如表 5-6所示。该公司应如何调度消防车，才能使总损失最小？
优化建模如果三处火警地点的损失分别为,
4t11+6t12,3t21+7t22,5t31+8t32+9t33，
调度方案是否需要改变？
消防站到三个火警地点所需要的时间时间 (分钟 ) 火警地点 1 火警地点 2 火警地点 3
消防站 1 6 7 9
消防站 2 5 8 11
消防站 3 6 9 10
优化建模问题分析本题考虑的是为每个火警地点分配消防车的问题，初步看来与线性规划中经典的运输问题有些类似。
本题的问题可以看成是指派问题和运输问题的一种变形，我们下面首先把它变成一个运输问题建模求解。
决策变量为了用运输问题建模求解，很自然地把 3个消防站看成供应点。如果直接把 3个火警地点看成需求点，
我们却不能很方便地描述消防车到达的先后次序，因此难以确定损失的大小。下面我们把 7辆车的需求分别看成 7个需求点 (分别对应于到达时间 t11,t12,t21,t22,
t31,t32,t33)。用 xi j表示消防站 i是否向第 j个需求点派车
(1表示派车,0表示不派车 )，则共有 21个 0-1变量。
优化建模决策目标题目中给出的损失函数都是消防车到达时间的线性函数，所以由所给数据进行简单的计算可知，如果消防站 1向第 6个需求点派车 (即消防站 1向火警地点 3
派车但该消防车是到达火警地点 3的第二辆车 )，则由此引起的损失为 8*9=72。同理计算，可以得到损失矩阵 (元素分别记为 ci j)。
ci j 火警地点 1 火警地点 2 火警地点 3j=1 j=2 j=3 j=4 j=5 j=6 j=7
消防站 i=1 36 24 49 21 81 72 45
消防站 i=2 30 20 56 24 99 88 55
消防站 i=3 36 24 63 27 90 80 50
优化建模于是，使总损失最小的决策目标为
7
1
3
1
M i n
j
ij
i
ij xcZ
约束条件 约束条件有两类：一类是消防站拥有的消防车的数量限制，另一类是各需求点对消防车的需求量限制。
消防站拥有的消防车的数量限制可以表示为
x11+x12+x13+x14+x15+x16+x17=3
x21+x22+x23+x24+x25+x26+x27 =2
x31+x32+x33+x34+x35+x36+x37=2
各需求点对消防车的需求量限制可以表示为
.7,6,5,4,3,2,1,13
1
jx
i ij
优化建模模型求解将如上构成的线性规划模型输入 LINDO：
! 消防车问题
Min 36x11+24x12+49x13+21x14+81x15+72x16+45x17
+30x21+20x22+56x23+24x24+99x25+88x26+55x27
+36x31+24x32+63x33+27x34+90x35+80x36+50x37
SUBJECT TO x11+x12+x13+x14+x15+x16+x17 = 3
x21+x22+x23+x24+x25+x26+x27 = 2
x31+x32+x33+x34+x35+x36+x37 = 2
x11+x21+x31 =1
x12+x22+x32 =1
x13+x23+x33 = 1
x14+x24+x34 =1
x15+x25+x35 =1
x16+x26+x36 = 1
x17+x27+x37 = 1
END
优化建模求解得到如下结果：
OBJECTIVE FUNCTION VALUE 1) 329.0000
VARIABLE VALUE REDUCED COST
X11 0.000000 10.000000
X12 0.000000 8.000000
X13 1.000000 0.000000
X14 0.000000 2.000000
X15 1.000000 0.000000
X16 1.000000 0.000000
X17 0.000000 3.000000
X21 1.000000 0.000000
X22 1.000000 0.000000
X23 0.000000 3.000000
X24 0.000000 1.000000
X25 0.000000 14.000000
X26 0.000000 12.000000
X27 0.000000 9.000000
优化建模
VARIABLE VALUE REDUCED COST
X31 0.000000 2.000000
X32 0.000000 0.000000
X33 0.000000 6.000000
X34 1.000000 0.000000
X35 0.000000 1.000000
X36 0.000000 0.000000
X37 1.000000 0.000000
也就是说，消防站 1应向火警地点 2派 1辆车，向火警地点 3派 2辆车；消防站 2应向火警地点 1派 2辆车；
消防站 3应向火警地点 2,3各派 1辆车。最小总损失为
329。
优化建模讨论
1) 这个问题本质上仍然和经典的运输问题类似，
可以把每辆车到达火场看作需求点，消防站可作供应点。在上面模型中，我们虽然假设 xij为 0-1变量，但求解时是采用线性规划求解的，也就是说没有加上 xij
为 0-1变量或整数变量的限制条件，但求解得到的结果中 xij正好是 0-1变量。这一结果不是偶然的，而是运输问题特有的一种性质。
优化建模
2) 在上面模型中，我们没有考虑消防车到达各火警地点的先后次序约束，但得到的结果正好满足所有的先后次序约束。这一结果却并不总是必然的，而只是巧合。
如对例题后半部分的情形，结果就不是这样了。
显然，此时只需要修改损失矩阵 (元素仍然分别记为 cij)
ci j 火警地点 1 火警地点 2 火警地点 3j=1 j=2 j=3 j=4 j=5 j=6 j=7
消防站 i=1 24 36 21 49 45 72 81
消防站 i=2 20 30 24 56 55 88 99
消防站 i=3 24 36 27 63 50 80 90
优化建模此时将重新构成的线性规划模型输入 LINDO求解,可以得到新的最优解,
x14=x16=x17=x21=x22=x33=x35=1
其他变量为 0(最小总损失仍为 329)。实际上,损失矩阵中只是 1,2列交换了位置,3,4列交换了位置,5,7
列交换了位置，因此不用重新求解就可以直接看出以上新的最优解。
但是，以上新的最优解却是不符合实际情况的。
例如,x14=x33=1表明火警地点 2的第一辆消防车来自消防站 3，第二辆消防车来自消防站 1，但这是不合理的，因为火警地点 2与消防站 3有 9分钟的距离，大于与消防站 1的 7分钟的距离。分配给火警地点 3的消防车也有类似的不合理问题。
优化建模为了解决这一问题，我们必须考虑消防车到达各火警地点的先后次序约束，也就是说必须在简单的运输问题模型中增加一些新的约束，以保证以上的不合理问题不再出现。
首先考虑火警地点 2。由于消防站 1的消防车到达所需时间 (7分钟 )小于消防站 2的消防车到达所需时间 (8分钟 )，并都小于消防站 3的消防车到达所需时间
(9分钟 )，因此火警地点 2的第 2辆消防车如果来自消防站 1，则火警地点 2的第 1辆消防车也一定来自消防站 1；
火警地点 2的第 2辆消防车如果来自消防站 2，则火警地点 2的第 1辆消防车一定来自消防站 1或 2。因此，必须增加以下约束,x
14?x13
x24?x13 +x23
优化建模
x16?x15
x17?x16
x36?x15+x35
2x37?x15+x16+x35+x36
同理，对火警地点 1，必须增加以下约束：
x22?x21
对火警地点 3，必须增加以下约束：
优化建模此时将重新构成的线性规划模型输入 LINDO软件如下：
! 消防车调度
Min 36x12+24x11+49x14+21x13+81x17+72x16+45x15
+30x22+20x21+56x24+24x23+99x27+88x26+55x25
+36x32+24x31+63x34+27x33+90x37+80x36+50x35
SUBJECT TO x11+x12+x13+x14+x15+x16+x17 = 3
x21+x22+x23+x24+x25+x26+x27 = 2
x31+x32+x33+x34+x35+x36+x37 = 2
x11+x21+x31 = 1
x12+x22+x32 = 1
x13+x23+x33 = 1
x14+x24+x34 = 1
x15+x25+x35 = 1
x16+x26+x36 = 1
x17+x27+x37 = 1
优化建模
X22 - X21 <= 0
X14 - X13 <=0
X24 - X23 - X13 <=0
X16 - X15 <= 0
X17 - X16 <=0
X36 - X15 - X35 <=0
2X37 -X15 -X16 -X35 -X36 <=0
END
! INT 21
优化建模求解，可以得到新的解为：
OBJECTIVE FUNCTION VALUE 1) 32.6667
VARIABLE VALUE REDUCED COST
X12 0.000000 9.333333
X11 0.000000 7.333333
X14 1.000000 0.000000
X13 1.000000 0.000000
X17 0.333333 0.000000
X16 0.333333 0.000000
X15 0.333333 0.000000
X22 1.000000 0.000000
X21 1.000000 0.000000
X24 0.000000 2.333333
X23 0.000000 1.000000
优化建模
VARIABLE VALUE REDUCED COST
X27 0.000000 13.000000
X26 0.000000 12.000000
X25 0.000000 9.000000
X32 0.000000 2.000000
X31 0.000000 0.000000
X34 0.000000 5.333333
X33 0.000000 0.000000
X37 0.666667 0.000000
X36 0.666667 0.000000
X35 0.666667 0.000000
优化建模但是我们发现此时的解中 xij并不都是 0–1变量或整数变量，因此还是不符合题意。这是因为此时的模型已经不再是“标准”的运输模型，所以得到的解不一定自然地为正数解的缘故。所以我们还必须显式地加上 xij为 0–1变量的约束。
加上 xij为 0-1变量的约束后求解可以得到：
x13=x14=x15=x21=x22=x36=x37=1，
其他变量为 0(最小总损失仍为 335)。也就是说，消防站 1应向火警地点 2派 2辆车，向火警地点 3派 1辆车；
消防站 2应向火警地点 1派 2辆车；消防站 3应向火警地点 3派 2辆车。经过检验可以发现，此时的派车方案是合理的。
优化建模
5.5 飞机定位和飞行计划问题优化建模
5.5.1飞机的精确定位问题例 5.7 飞机在飞行过程中，能够收到地面上各个监控台发来的关于飞机当前位置的信息，根据这些信息可以比较精确地确定飞机的位置 。如图所示，
VOR是高频多向导航设备的英文缩写，它能够得到飞机与该设备连线的角度信息； DME是距离测量装置的英文缩写，它能够得到飞机与该设备的距离信息。
图中飞机接收到来自 3个 VOR给出的角度和 1个 DME
给出的距离 (括号内是测量误差限 )，并已知这 4种设备的 x,y坐标 (假设飞机和这些设备在同一平面上 )。
如何根据这些信息精确地确定当前飞机的位置？
优化建模
0
y
x
VOR2
x=629,
y=375 309.00 (1.30)
864.3(2.0) 飞机
x=?,y=?
VOR1
x=764,
y=1393
161.20 (0.80)
VOR3
x=1571,
y=259
45.10 (0.60)
北
DME
x=155,
y=987
图 飞机与监控台优化建模问题分析记 4种设备 VOR1,VOR2,VOR3,DME的坐标为 (xi,yi)(以 km为单位 ),i=1,2,3,4； VOR1,VOR2、
VOR3测量得到的角度为?i (从图中可以看出，按照航空飞行管理的惯例，该角度是从北开始，沿顺时针方向的角度，取值在 00~3600之间 )，角度的误差限为?i，
i=1,2,3； DME测量得到的距离为 d4 (km)，距离的误差限为?4。设飞机当前位置的坐标为 (x,y)，则问题就是由下表的已知数据计算 (x,y)。
xi yi 原始的?i (或 d4)?i
VOR1 746 1393 161.20(2.81347弧度 ) 0.80(0.0140弧度 )
VOR2 629 375 45.10(0.78714弧度 ) 0.60(0.0105弧度 )
VOR3 1571 259 309.00(5.39307弧度 ) 1.30(0.0227弧度 )
DME 155 987 864.3 (km) 2.0 (km)
优化建模模型 1及求解图中角度?i是点 (xi,yi)和点 (x,y)的连线与 y 轴的夹角 (以 y 轴正向为基准，顺时针方向夹角为正，而不考虑逆时针方向的夹角 )，于是角度?i的正切
i
i
i yy
xx
t a n i=1,2,3,
对 DME测量得到的距离，显然有
24244 )()( yyxxd
直接利用上面得到的 4个等式确定飞机的坐标 x,y，
这时是一个求解超定 (非线性 )方程组的问题，在最小二乘准则下使计算值与测量值的误差平方和最小 (越接近 0越好 )。
优化建模
3
1
2]t an)/()([),( M in
i iii
yyxxyxJ?
224244 ])()([ yyxxd
这是一个非线性 (无约束 )最小二乘拟合问题。
则需要求解优化建模
MODEL:
SETS:
VOR/1..3/,x,y,cita,sigma;
ENDSETS
DATA:
x,y,cita,sigma =
746 1393 2.81347 0.0140
629 375 0.78714 0.0105
1571 259 5.39307 0.0227;
x4 y4 d4 sigma4 = 155 987 864.3 2.0;
ENDDATA
! XX,YY表示飞机坐标 ;
min = @sum(VOR,@sqr((xx-x)/(yy-y) - @tan(cita)) )
+ @sqr(d4 - @sqrt(@sqr(xx-x4)+@sqr(yy-y4)) );
END
很容易写出其 LINGO程序如下：
优化建模求解该模型得到的解为 (只列出部分结果 )：
Local optimal solution found.
Objective value,128.0226
Variable Value Reduced Cost
XX 243.4204 0.1315903E-08
YY 126.3734 0.000000
显然，这个解的目标函数值很大 (128.0226),因此我们怀疑是一个局部最小点。用,LINGO|OPTIONS”
菜单命令启动,Global Solver”选项卡上的,Use
Global Solver”选项，然后求解，可以得到全局最优解如下：Global optimal solution found.
Objective value,0.7050440E-03
Variable Value Reduced Cost
XX 980.6926 0.000000
YY 731.5666 0.000000
优化建模这个解的目标函数值很小 (0.000705)，飞机坐标为
(980.6926,731.5666)。
优化建模模型 2及求解注意到这个问题中角度和距离的单位是不一致的
(角度为弧度，距离为公里 )，因此将这 4个误差平方和同等对待 (相加 )不是很合适。并且,4种设备测量的精度 (误差限 )不同，而上面的方法根本没有考虑测量误差问题。如何利用测量设备的精度信息？这就需要看你对例中给出的设备精度如何理解。
一种可能的理解是：设备的测量误差是均匀分布的。以 VOR1为例，目前测得的角度为 161.20，测量精度为 0.80，所以实际的角度应该位于区间 [161.20-
0.80,161.20+0.80]内。对其他设备也可以类似理解。
由于很小，即测量精度很高，所以在相应区间内正切函数 tan的单调性成立。
优化建模于是可以得到一组不等式：
)t a n ()t a n ( ii
i
i
ii yy
xx
44242444 )()( dyyxxd
(i=1,2,3)
也就是说，飞机坐标应该位于上述不等式组成的区域内。例如，模型 1中得到的目标函数值很小，显然满足测量精度要求，因此坐标 (980.6926,731.5666)
肯定位于这个可行区域内。
优化建模由于这里假设设备的测量误差是均匀分布的，所以飞机坐标在这个区域内的每个点上的可能性应该也是一样的，我们最好应该给出这个区域的 x和 y坐标的最大值和最小值。于是我们可以分别以 min x,max x、
min y,max y、为目标，以上面的区域限制条件为约束，求出 x和 y坐标的最大值和最小值。
以 min x为例，相应的 LINGO程序为：
MODEL:
Title 飞机定位模型 2;
SETS:
VOR/1..3/,x,y,cita,sigma;
ENDSETS
优化建模
DATA:
x,y,cita,sigma =
746 1393 2.81347 0.0140
629 375 0.78714 0.0105
1571 259 5.39307 0.0227;
x4 y4 d4 sigma4 = 155 987 864.3 2.0;
ENDDATA
! XX,YY表示飞机坐标 ;
min=xx;
@for(VOR,(xx-x)/(yy-y) > @tan(cita - sigma) );
@for(VOR,(xx-x)/(yy-y) < @tan(cita + sigma) );
d4 - sigma4 < @sqrt(@sqr(xx-x4)+@sqr(yy-y4)) ;
d4 + sigma4 > @sqrt(@sqr(xx-x4)+@sqr(yy-y4)) ;
END
优化建模用 LINGO求解上述模型,LINGO系统返回的信息是这个模型没有可行解。其实这显然是一个不正确的信息，可能只是由于求解空间太大,LINGO没有找到可行解。其实，我们可以想象这个问题的可行解大致就该在模型 1中得到的最优解附近，因此可以把这个解作为初始值告诉 LINGO。例如，在上面程序中增加以下三行：
INIT:
xx,yy = 980.6926,731.5666;
ENDINIT
优化建模此时求解，马上就得到 XX的最小值为 974.8424。
类似地（只需要换换目标函数就可以了），可得到
XX的最大值为 982.2129,YY的最小值为 717.1587，
YY的最大值为 733.1944。
因此，最后得到的解是一个比较大的矩形区域，
大致为 [975,982]× [717,733]。
优化建模模型 3及求解模型 2得到的只是一个很大的矩形区域，仍不能令人满意。实际上，模型 2中假设设备的测量误差是均匀分布的，这是很不合理的。一般来说，在多次测量中，应该假设设备的测量误差是正态分布的，而且均值为 0。本例中给出的精度?i可以认为是测量误差的标准差 (也可以是与标准差成比例的一个量，如标准差的 3倍或 6倍等 )。
在这种理解下，用各自的误差限?i对测量误差进行无量纲化 (也可以看成是一种加权法 )处理是合理的，
即求解如下的无约束优化问题更合理：
优化建模
2
4
2
4
2
44
23
1
)()(),( M i n
yyxxdαyxE
i i
ii
其中
i
i
i yy
xx
t a n i=1,2,3,
由于目标函数是平方和的形式，因此这是一个非线性最小二乘拟合问题。相应的 LINGO程序为 (仍然将迭代初值告诉 LINGO)：
优化建模
MODEL:
TITLE 飞机定位模型 3;
SETS:
VOR/1..3/,x,y,cita,sigma;
ENDSETS
DATA:
x,y,cita,sigma =
746 1393 2.81347 0.0140
629 375 0.78714 0.0105
1571 259 5.39307 0.0227;
x4 y4 d4 sigma4 = 155 987 864.3 2.0;
ENDDATA
INIT:
xx,yy = 980.6926,731.5666;
ENDINIT
优化建模
! XX,YY表示飞机坐标 ;
!min = @sum(VOR,@sqr(((xx-x)/(yy-y) - @tan(cita))/sigma) )
+ @sqr((d4 - @sqrt(@sqr(xx-x4)+@sqr(yy-y4)))/sigma4 );
min = @sum(VOR,(((xx-x)/(yy-y) - @tan(cita))/sigma)^2 )
+ ((d4 - ((xx-x4)^2+(yy-y4)^2)^.5 )/sigma4 )^2;
END
Global optimal solution found.
Objective value,2.600539
Model Title,飞机定位模型 3
Variable Value Reduced Cost
XX 980.2106 0.000000
YY 727.3056 0.000000
计算结果为：
即飞机坐标为 (980.21,727.31)，这个解对应的目标函数值大约为 2.6。
优化建模这个误差为什么比模型 1的大很多？这是因为模型 1中使用的是绝对误差，而这里使用的是相对于精度?i的误差。分母?i很小，所以相对误差比绝对误差大，这是可以理解的。其实，可以认为此时的目标函数是四个标准正态分布的误差平方和，只要在 4以内都是合理的。
优化建模
5.5.2飞行计划问题例 5.8 这个问题是以第二次世界大战中的一个实际问题为背景，经过简化而提出来的。在甲乙双方的一场战争中，一部分甲方部队被乙方部队包围长达 4
个月。 由于乙方封锁了所有水陆交通通道，被包围的甲方部队只能依靠空中交通维持供给。运送 4个月的供给分别需要 2,3,3,4次飞行，每次飞行编队由 50架飞机组成 (每架飞机需要 3名飞行员 )，可以运送 10万吨物资。每架飞机每个月只能飞行一次，每名飞行员每个月也只能飞行一次。在执行完运输任务后的返回途中有 20%的飞机会被乙方部队击落，相应的飞行员也因此牺牲或失踪。
优化建模在第 1个月开始时，甲方拥有 110架飞机和 330名熟练的飞行员。在每个月开始时，甲方可以招聘新飞行员和购买新飞机。新飞机必须经过一个月的检查后才可以投入使用，新飞行员必须在熟练飞行员的指导下经过一个月的训练才能投入飞行。每名熟练飞行员可以作为教练每个月指导 20名飞行员 (包括他自己在内 )进行训练。每名飞行员在完成一个月的飞行任务后，必须有一个月的带薪假期，假期结束后才能再投入飞行。已知各项费用 (单位略去 )如下表所示，请你为甲方安排一个飞行计划。
优化建模如果每名熟练飞行员可以作为教练每个月指导不超过 20名飞行员 (包括他自己在内 )进行训练，模型和结果有哪些改变？
第 1个月 第 2个月 第 3个月 第 4个月新飞机价格 200.0 195.0 190.0 185.0
闲置的熟练飞行员报酬 7.0 6.9 6.8 6.7
教练和新飞行员报酬 (包括培训费用 ) 10.0 9.9 9.8 9.7
执行飞行任务的熟练飞行员报酬 9.0 8.9 9.8 9.7
休假期间的熟练飞行员报酬 5.0 4.9 4.8 4.7
优化建模问题分析这个问题看起来很复杂，但只要理解了这个例子中所描述的事实，其实建立优化模型并不困难。首先可以看出，执行飞行任务以及执行飞行任务后休假的熟练飞行员数量是常数，所以这部分费用 (报酬 )是固定的，在优化目标中可以不考虑。
决策变量设 4个月开始时甲方新购买的飞机数量分别为 x1,
x2,x3,x4架,闲置的飞机数量分别为 y1,y2,y3,y4架。 4个月中,飞行员中教练和新飞行员数量分别为 u1,u2,u3,
u4人,闲置的的熟练飞行员数量分别为 v1,v2,v3,v4人。
优化建模目标函数优化目标是,
Min 200x1+195x2 +190x3+185x4+10u1+9.9u2
+9.8u3+9.7u4+7v1+6.9v2+6.8v3+6.7v4
约束条件需要考虑的约束包括：
1） 飞机数量限制,4个月中执行飞行任务的飞机分别为 100,150,150,200架，但只有 80,120,120,160
架能够返回供下个月使用。
第 1个月,100+y1=110
第 2个月,150+y2=80+ y1+ x1
第 3个月,150+y3=120+ y2+ x2
第 4个月,200+y4=120+ y3+ x3
优化建模
2） 飞行员数量限制,4个月中执行飞行任务的熟练飞行员分别为 300,450,450,600人，但只有 240,360，
360,480人能够返回 (下个月一定休假 )。
第 1个月,300 +0.05 u1+ v1=330
第 2个月,450 +0.05 u2+ v2= u1+ v1
第 3个月,450 +0.05 u3+ v3= u2+ v2+240
第 4个月,600 +0.05 u4+ v4= u3+ v3+360
最后，自然要求 x1,x2,x3,x4,y1,y2,y3,y4,u1,u2,
u3,u4,v1,v2,v3,v4?0 且为整数。
优化建模于是，这个优化模型很容易输入 LINDO：
MIN 200x1+195x2 +190x3+185x4+10u1+9.9u2
+9.8u3+9.7u4+7v1+6.9v2+6.8v3+6.7v4
s.t,y1=10
y1+ x1 - y2 =70
y2+ x2 - y3 =30
y3+ x3 - y4=80
0.05 u1+ v1=30
u1 + v1 - 0.05 u2 - v2 = 450
u2 + v2 - 0.05 u3 - v3 = 210
u3 + v3 - 0.05 u4 - v4 = 240
end
GIN 16
优化建模用 LINDO求解得到：
OBJECTIVE FUNCTION VALUE 1) 42324.40
VARIABLE VALUE REDUCED COST
X1 60.000000 200.000000
X2 30.000000 195.000000
X3 80.000000 190.000000
X4 0.0000000 185.000000
U1 460.00000 10.000000
U2 220.00000 9.900000
U3 240.00000 9.800000
U4 0.0000000 9.700000
V1 7.0000000 7.000000
V2 6.0000000 6.900000
V3 4.0000000 6.800000
V4 4.0000000 6.700000
优化建模
VARIABLE VALUE REDUCED COST
Y1 10.000000 0.000000
Y2 0.000000 0.000000
Y3 0.000000 0.000000
Y4 0.000000 0.000000
即最优解为 x1=60,x2=30,x3=80,x4=0,y1=10,y2= y3= y4
=0,u1=460,u2=220,u3=240,u4=0,v1=7,v2=6,v3=4,
v4=4; 目标函数值为 42324.40。
优化建模问题讨论如果每名熟练飞行员可以作为教练每个月指导不超过 20名飞行员 (包括他自己在内 )进行训练，则应将教练与新飞行员分开：
设 4个月飞行员中教练为 u1,u2,u3,u4人，新飞行员数量分别为 w1,w2,w3,w4人。其它符号不变。飞行员的数量限制约束为第 1个月,300+u1+v1=330
第 2个月,450+u2+v2= u1+v1+w1,w1?20u1
第 3个月,450+u3+v3= u2+v2+240+w2,w2?20u2
第 4个月,600+u4+v4= u3+v3+360+w3,w3?20u3
优化建模优化模型作相应修改，输入 LINDO如下：
MIN 200x1+195x2 +190x3+185x4+10u1+9.9u2+9.8u3+9.7u4
+7v1+6.9v2+6.8v3+6.7v4+10w1+9.9w2+9.8w3+9.7w4
s.t,y1=10
y1+ x1 - y2 =70
y2+ x2 - y3 =30
y3+ x3 - y4=80
u1+ v1=30
u1 + v1 + w1 - u2 - v2 = 450
u2 + v2 + w2 - u3 - v3 = 210
u3 + v3 + w3 - u4 - v4 = 240
w1 - 20u1 <=0
w2 - 20u2 <=0
w3 - 20u3 <=0
end
gin 20
优化建模用 LINDO求解得到：
OBJECTIVE FUNCTION VALUE 1) 42185.80
VARIABLE VALUE REDUCED COST
X1 60.000000 200.000000
X2 30.000000 195.000000
X3 80.000000 190.000000
X4 0.000000 185.000000
U1 22.000000 10.000000
U2 11.000000 9.900000
U3 12.000000 9.800000
U4 0.000000 9.700000
V1 8.000000 7.000000
V2 0.000000 6.900000
V3 0.000000 6.800000
V4 0.000000 6.700000
优化建模
VARIABLE VALUE REDUCED COST
W1 431.000000 10.000000
W2 211.000000 9.900000
W3 228.000000 9.800000
W4 0.000000 9.700000
Y1 10.000000 0.000000
Y2 0.000000 0.000000
Y3 0.000000 0.000000
Y4 0.000000 0.000000
即最优解为 u1=22,u2=11,u3=12,u4=0,v1=8,v2=v3=v4
=0,w1=431,w2=211,w3=228,w4=0 (x1~x4,y1~y4不变 )；
目标函数值为 42185.80。
优化建模自己练习，或课上布置布置作业内容
Thank you very much!
