问题一 (两辆铁路平板车的装载问题 )
(88年 MCM之 B题 )
要把七种规格的包装箱装到两辆铁路平板车上,
包装箱的宽和高都是相同的,但厚度 (t,以厘米计 )
及重量 (w,以吨计 )却不同,下表给出了它们的厚度、重量及数量
C1 C2 C3 C4 C5 C6 C7
t(厘米 ) 48.7 52.0 61.3 72.0 48.7 52.0 64.0
w(吨 ) 2 3 1 0.5 4 2 1
箱数 8 7 9 6 6 4 8
每辆平板车有 10.2米的地方可以用来装箱 (像面包片那样 ),载重为 40吨,由于当地货运的限制,对 C5,
C6,C7三类包装箱的总数有如下特殊约束,它们所占的空间 (厚度 )不得超过 302.7厘米,试把这些包装箱装到平板车上,而浪费的空间最小,
1 问题分析题中所有包装箱共重 89吨,总厚度达到
2749.5cm,而两辆平板车只能载 2× 40=80
吨,2040cm,因此不能全装下,究竟在两辆车上装哪些种各多少个箱子才合适,必须有评价的标准,这标准是遵守题中说明的重量、厚度方面的约束条件,并且体现出尽可能多装,
由题意,只考虑像面包片重叠那样的装法,
把问题简化为,两辆车上装箱总厚度之和尽可能大,这是一个典型的规划问题,
2 模型构建
)7,6,5,4,3,2,1;2,1(
.
ji
Cix jij 箱的数量辆平板车装表示在第设
)2(82111 xx箱数约束
)3(72212 xx
)8(8
)7(4
)6(6
)5(6
)4(9
2717
2616
2515
2414
2313
xx
xx
xx
xx
xx
)1(.0 Zx ij自然条件
)10(40245.032
)9(40245.032
27262524232221
17161514131211
xxxxxxx
xxxxxxx重量约束
)11(10 2064527.48
723.61527.48
171615
14131211
xxx
xxxx厚度约束
)12( 1 02 064527.48
723.61527.48
272625
24232221
xxx
xxxx
( 13 ) 7.30264527.4864527.48
C7C 6,C 5,
272625171615 xxxxxx
的特殊要求对两辆平板车装箱总厚度之和
]64527.48
723.61527.48[S
765
2
1
4321
iii
i
iiii
xxx
xxxx
此问题的数学模型为,
).1(
),13()2(
..,
]640.0520.0487.0
720.0613.0520.0487.0[max S
765
2
1
4321
ts
xxx
xxxx
iii
i
iiii
这是整数线性规划模型我们运用 LINDO软件求解,可以得到该问题的一个最优解为
c1 c2 c3 c4 c5 C6 c7 总重 总厚度一 3 2 9 1 3 0 0 37.5 1019.9
二 5 5 0 5 0 3 0 29.5 1019.5
最优值为 2039.4.从运行的结果报告来看,LINDO
求解时用到了 分支定界法,
一些技巧与改进
1.由于两辆平板车的对称性,我们只要对某个变量进行限制,例如 x13≤4,这样计算量就减少了,
2.从最优解我们发现,前四种货物箱全部装载完,
事实上,如果我们仔细计算早就可以发现,在限定所载后三种货物箱的厚度和不超过 302.7cm时,装载前四种货物箱的厚度大于或等于 2040-302.7
=1737.3,而 前四种货物箱的总厚度正好为 1737.3
cm,且总重量为 49t.由于后三种货物箱总厚度不超过 302.7cm的最大值我们很容易发现为 302.1
cm,就是 C5三箱,C6三箱,C7不装 (因为它们的厚度分别为 48.7,52,64,换动任何一个都将改动超过
0.6cm.)而此时总重为 67t.手工就可以派出一个最优解,基于这些分析后,我们很容易通过编程算出所有的最优解 (前四种箱数约束事实上可以用等式,第五,六种各三个,第七种为零 ).
我们今后会看到,即使我们利用计算机处理一些问题,进行必要的数学处理和具体问题的分析对我们解决问题往往很有帮助,特别是参加数学建模竞赛时更是如此,
探索题：如果你多运行几次,观察结果有什么不同?
问题二 投资效益问题及分支定界法
1.问题的提出项目 1 2 3 4 5 6
投资 (亿元 ) 5 2 6 4 6 8
收益 (亿元 ) 0.5 0.4 0.6 0.5 0.9 1
一个公司有 22亿元资金可用来投资,现有六个项目可供选择,各项目投资额和预计受益如下表,
应选那几个项目投资收益最大?
2.模型的建立引入表征是否对的 i 个项目投资的变量 xi,
.,0
,,1
个项目不投资若对的个项目投资若对的
i
ix
i
,864625 654321 xxxxxxI
因此投资总额为因而预见的年收入为
,9.05.06.04.05.0 654321 xxxxxxP
从而模型 (ILP)为
1,0,22864625,.
,9.05.06.04.05.0 m a x
654321
654321
ixxxxxxxts
xxxxxxP
3.模型的求解方法 1.穷举法,由于现在只有 6个项目,每个项目都有投资和不投资两种可能的选择,因此共有 64 种投资方案,我们可以将这 64个方案一一验证是否可行,并对可行的方案计算收益,进行比较,选出最优方案,此方法简便易行,但是,计算量较大,而且随着可选项目的增多,不太具有推广性,
方法 2,分支定界法,
分支定界法的思想是,先求解 LP:即放宽变量的取值范围,改成 0≤ xi ≤1.此时得到的最优解若是整数,则它就是 ILP的最优解 ;否则,我们在此解附近来找到一个可行解,即整数解,
项目 1 2 3 4 5 6
投资 (亿元 ) 5 2 6 4 6 8
收益 0.5 0.4 0.6 0.5 0.9 1
收益率 0.1 0.2 0.1 0.125 0.15 0.125
可以看出,投资优先次序是,2,5,4(6),1(3).因此我们很容易得到两个最优解,
本例比较简单,我们不用软件可直接求解 LP.为此,我们算出每个项目的投资收益率,即单位投资的收益,列表,
).1,1,1,0,1,
5
2
(),,,,,(
),1,1,1,
3
1
,1,0(),,,,,(
654321
654321
xxxxxx
xxxxxx
我们仍允许其他变量为分支变量称的约束或我们增加的约束或满足取值不由于在图上称为结点
,,
10,10
3
1.1),1,1,1,
3
1
,1,0(
3
33
3
x
xx
x
为此,我们必须进一步处理,先看第一个最优解易算出它们的年收益都是 P=3.0.由于我们放宽了 xi的取值范围,上述最优收益超过了实际的最优收益,因为上述两组最优解都包含了非 0,1的值,它是不满足约束条件,实际上不是可行解,
取介于 0,1之间的实数值,根据优先选取收益率高的原则,又可以取得两组最优解,
x3=0 时的最优解为 (2/5,1,0,1,1,1),收益为 3.0;
x3=1 时的一最优解为 (0,1,1,0,1,1) (原则二,在同等收益的解中,优先取使得不满足约束的解分量尽量少,因此 (0,1,1,1,1,0.5) 舍去 ),收益为 2.9,此解已经满足变量取值为 0,1的约束,因此是原问题的一个可行解,
它的年收益可以作为原问题最优解的一个候选者,
即年收益少于 2.9的解肯定不会是最优解,这就是定界,
而对应于 x3=0的最优解恰为我们第一步得到且至今还为处理的解,这一步图解如下,
图 1 (0,1,1/3,1,1,1),3.0
(2/5,1,0,1,1,1),3.0 (0,1,1,0,1,1),2.9
13?x
由于 x3=0 的解中 x1=2/5,我们进一步增加约束 x1=0
或 x1=1 来考察,即将变量取 0,1的值的约束改为 x3=0,
x1=0 或 x3=0,x1=1 来求解,
对于约束 x3=0,x1=0,满足投资总额不超过 22的解为
(0,1,0,1,1,1),对应的年收益为 2.8,虽然它是原问题的一个可行解,但是由于其年收益不到 2.9,不可能为最优解,
对于约束 x3=0,x1=1,有两组最优解 (1,1,0,1,1,5/8)和
(1,1,0,1/4,1,1),对应的年收益都是 2.925,
03?x
图 2 (0,1,1/3,1,1,1),3.0
(2/5,1,0,1,1,1),3.0 (0,1,1,0,1,1),2.9
(0,1,0,1,1,1) 2.8 (1,1,0,1/4,1,1) 2.925 或
× (1,1,0,1,1,5/8) 2.925
再在 (1,1,0,1/4,1,1) 的基础上分别增加 x4=0 和 x4=1 的约束,此时求得的最优解分别为
03?x
13?x
01?x 11?x
我们再一一考察它们,过程我们用图 2表示,
定界年收益为 2.925,前者虽为可行解,但是年收益不足 2.9,
因此舍去,后者即为上一步未曾处理的解,图解为
(0,1,1/3,1,1,1),3.0
(2/5,1,0,1,1,1),3.0 (0,1,1,0,1,1),2.9
(0,1,0,1,1,1) 2.8 (1,1,0,1/4,1,1) 2.925
×
(1,1,0,0,1,1) 2.8 (1,1,0,1,1,5/8) 2.925
×
继续在 (1,1,0,1,1,5/8) 的基础上,对 x6 增加约束,
13?x
01?x
03?x
11?x
04?x
14?x
(1,1,0,0,1,1),年收益为 2.8,以及 (1,1,0,1,1,5/8),
03?x 13?x
01?x 11?x
04?x 14?x
06?x 1
6?x
(0,1,1/3,1,1,1),3.0
(2/5,1,0,1,1,1),3.0 (0,1,1,0,1,1),2.9
(0,1,0,1,1,1) 2.8 (1,1,0,1/4,1,1) 2.925
×
(1,1,0,0,1,1) 2.8 × (1,1,0,1,1,5/8) 2.925
(1,1,0,1,1,0) 2.3 (1,1,0,1,1/2,1) 2.85
× ×结论,(0,1,1,0,1,1)为最优解,最大收益为 2.9亿元,
评注,
分支定界法本质上就是穷举法,不过它是一种改进的穷举法,它在算法实现上有很大的灵活性,往往取决于对问题的处理方式,分支变量的选择顺序对工作量影响极大,因此,要根据问题本身的理解,优先考虑关键的分支,尽早得到一个较好的目标值,从而使得许多分支提前终止,
LINDO软件中也用到了分支定界法,我们来看看上次讲的平板车的例子,本来,简单的穷举法要检验、计算 45× 36× 55× 28× 28× 15× 45=4.7E+10,
就算我们限定,xi7=0,我们也至少要算约 1.0E+9次,但是我们实际上一般迭代几万次,分支在 4到 15千之间,
(88年 MCM之 B题 )
要把七种规格的包装箱装到两辆铁路平板车上,
包装箱的宽和高都是相同的,但厚度 (t,以厘米计 )
及重量 (w,以吨计 )却不同,下表给出了它们的厚度、重量及数量
C1 C2 C3 C4 C5 C6 C7
t(厘米 ) 48.7 52.0 61.3 72.0 48.7 52.0 64.0
w(吨 ) 2 3 1 0.5 4 2 1
箱数 8 7 9 6 6 4 8
每辆平板车有 10.2米的地方可以用来装箱 (像面包片那样 ),载重为 40吨,由于当地货运的限制,对 C5,
C6,C7三类包装箱的总数有如下特殊约束,它们所占的空间 (厚度 )不得超过 302.7厘米,试把这些包装箱装到平板车上,而浪费的空间最小,
1 问题分析题中所有包装箱共重 89吨,总厚度达到
2749.5cm,而两辆平板车只能载 2× 40=80
吨,2040cm,因此不能全装下,究竟在两辆车上装哪些种各多少个箱子才合适,必须有评价的标准,这标准是遵守题中说明的重量、厚度方面的约束条件,并且体现出尽可能多装,
由题意,只考虑像面包片重叠那样的装法,
把问题简化为,两辆车上装箱总厚度之和尽可能大,这是一个典型的规划问题,
2 模型构建
)7,6,5,4,3,2,1;2,1(
.
ji
Cix jij 箱的数量辆平板车装表示在第设
)2(82111 xx箱数约束
)3(72212 xx
)8(8
)7(4
)6(6
)5(6
)4(9
2717
2616
2515
2414
2313
xx
xx
xx
xx
xx
)1(.0 Zx ij自然条件
)10(40245.032
)9(40245.032
27262524232221
17161514131211
xxxxxxx
xxxxxxx重量约束
)11(10 2064527.48
723.61527.48
171615
14131211
xxx
xxxx厚度约束
)12( 1 02 064527.48
723.61527.48
272625
24232221
xxx
xxxx
( 13 ) 7.30264527.4864527.48
C7C 6,C 5,
272625171615 xxxxxx
的特殊要求对两辆平板车装箱总厚度之和
]64527.48
723.61527.48[S
765
2
1
4321
iii
i
iiii
xxx
xxxx
此问题的数学模型为,
).1(
),13()2(
..,
]640.0520.0487.0
720.0613.0520.0487.0[max S
765
2
1
4321
ts
xxx
xxxx
iii
i
iiii
这是整数线性规划模型我们运用 LINDO软件求解,可以得到该问题的一个最优解为
c1 c2 c3 c4 c5 C6 c7 总重 总厚度一 3 2 9 1 3 0 0 37.5 1019.9
二 5 5 0 5 0 3 0 29.5 1019.5
最优值为 2039.4.从运行的结果报告来看,LINDO
求解时用到了 分支定界法,
一些技巧与改进
1.由于两辆平板车的对称性,我们只要对某个变量进行限制,例如 x13≤4,这样计算量就减少了,
2.从最优解我们发现,前四种货物箱全部装载完,
事实上,如果我们仔细计算早就可以发现,在限定所载后三种货物箱的厚度和不超过 302.7cm时,装载前四种货物箱的厚度大于或等于 2040-302.7
=1737.3,而 前四种货物箱的总厚度正好为 1737.3
cm,且总重量为 49t.由于后三种货物箱总厚度不超过 302.7cm的最大值我们很容易发现为 302.1
cm,就是 C5三箱,C6三箱,C7不装 (因为它们的厚度分别为 48.7,52,64,换动任何一个都将改动超过
0.6cm.)而此时总重为 67t.手工就可以派出一个最优解,基于这些分析后,我们很容易通过编程算出所有的最优解 (前四种箱数约束事实上可以用等式,第五,六种各三个,第七种为零 ).
我们今后会看到,即使我们利用计算机处理一些问题,进行必要的数学处理和具体问题的分析对我们解决问题往往很有帮助,特别是参加数学建模竞赛时更是如此,
探索题：如果你多运行几次,观察结果有什么不同?
问题二 投资效益问题及分支定界法
1.问题的提出项目 1 2 3 4 5 6
投资 (亿元 ) 5 2 6 4 6 8
收益 (亿元 ) 0.5 0.4 0.6 0.5 0.9 1
一个公司有 22亿元资金可用来投资,现有六个项目可供选择,各项目投资额和预计受益如下表,
应选那几个项目投资收益最大?
2.模型的建立引入表征是否对的 i 个项目投资的变量 xi,
.,0
,,1
个项目不投资若对的个项目投资若对的
i
ix
i
,864625 654321 xxxxxxI
因此投资总额为因而预见的年收入为
,9.05.06.04.05.0 654321 xxxxxxP
从而模型 (ILP)为
1,0,22864625,.
,9.05.06.04.05.0 m a x
654321
654321
ixxxxxxxts
xxxxxxP
3.模型的求解方法 1.穷举法,由于现在只有 6个项目,每个项目都有投资和不投资两种可能的选择,因此共有 64 种投资方案,我们可以将这 64个方案一一验证是否可行,并对可行的方案计算收益,进行比较,选出最优方案,此方法简便易行,但是,计算量较大,而且随着可选项目的增多,不太具有推广性,
方法 2,分支定界法,
分支定界法的思想是,先求解 LP:即放宽变量的取值范围,改成 0≤ xi ≤1.此时得到的最优解若是整数,则它就是 ILP的最优解 ;否则,我们在此解附近来找到一个可行解,即整数解,
项目 1 2 3 4 5 6
投资 (亿元 ) 5 2 6 4 6 8
收益 0.5 0.4 0.6 0.5 0.9 1
收益率 0.1 0.2 0.1 0.125 0.15 0.125
可以看出,投资优先次序是,2,5,4(6),1(3).因此我们很容易得到两个最优解,
本例比较简单,我们不用软件可直接求解 LP.为此,我们算出每个项目的投资收益率,即单位投资的收益,列表,
).1,1,1,0,1,
5
2
(),,,,,(
),1,1,1,
3
1
,1,0(),,,,,(
654321
654321
xxxxxx
xxxxxx
我们仍允许其他变量为分支变量称的约束或我们增加的约束或满足取值不由于在图上称为结点
,,
10,10
3
1.1),1,1,1,
3
1
,1,0(
3
33
3
x
xx
x
为此,我们必须进一步处理,先看第一个最优解易算出它们的年收益都是 P=3.0.由于我们放宽了 xi的取值范围,上述最优收益超过了实际的最优收益,因为上述两组最优解都包含了非 0,1的值,它是不满足约束条件,实际上不是可行解,
取介于 0,1之间的实数值,根据优先选取收益率高的原则,又可以取得两组最优解,
x3=0 时的最优解为 (2/5,1,0,1,1,1),收益为 3.0;
x3=1 时的一最优解为 (0,1,1,0,1,1) (原则二,在同等收益的解中,优先取使得不满足约束的解分量尽量少,因此 (0,1,1,1,1,0.5) 舍去 ),收益为 2.9,此解已经满足变量取值为 0,1的约束,因此是原问题的一个可行解,
它的年收益可以作为原问题最优解的一个候选者,
即年收益少于 2.9的解肯定不会是最优解,这就是定界,
而对应于 x3=0的最优解恰为我们第一步得到且至今还为处理的解,这一步图解如下,
图 1 (0,1,1/3,1,1,1),3.0
(2/5,1,0,1,1,1),3.0 (0,1,1,0,1,1),2.9
13?x
由于 x3=0 的解中 x1=2/5,我们进一步增加约束 x1=0
或 x1=1 来考察,即将变量取 0,1的值的约束改为 x3=0,
x1=0 或 x3=0,x1=1 来求解,
对于约束 x3=0,x1=0,满足投资总额不超过 22的解为
(0,1,0,1,1,1),对应的年收益为 2.8,虽然它是原问题的一个可行解,但是由于其年收益不到 2.9,不可能为最优解,
对于约束 x3=0,x1=1,有两组最优解 (1,1,0,1,1,5/8)和
(1,1,0,1/4,1,1),对应的年收益都是 2.925,
03?x
图 2 (0,1,1/3,1,1,1),3.0
(2/5,1,0,1,1,1),3.0 (0,1,1,0,1,1),2.9
(0,1,0,1,1,1) 2.8 (1,1,0,1/4,1,1) 2.925 或
× (1,1,0,1,1,5/8) 2.925
再在 (1,1,0,1/4,1,1) 的基础上分别增加 x4=0 和 x4=1 的约束,此时求得的最优解分别为
03?x
13?x
01?x 11?x
我们再一一考察它们,过程我们用图 2表示,
定界年收益为 2.925,前者虽为可行解,但是年收益不足 2.9,
因此舍去,后者即为上一步未曾处理的解,图解为
(0,1,1/3,1,1,1),3.0
(2/5,1,0,1,1,1),3.0 (0,1,1,0,1,1),2.9
(0,1,0,1,1,1) 2.8 (1,1,0,1/4,1,1) 2.925
×
(1,1,0,0,1,1) 2.8 (1,1,0,1,1,5/8) 2.925
×
继续在 (1,1,0,1,1,5/8) 的基础上,对 x6 增加约束,
13?x
01?x
03?x
11?x
04?x
14?x
(1,1,0,0,1,1),年收益为 2.8,以及 (1,1,0,1,1,5/8),
03?x 13?x
01?x 11?x
04?x 14?x
06?x 1
6?x
(0,1,1/3,1,1,1),3.0
(2/5,1,0,1,1,1),3.0 (0,1,1,0,1,1),2.9
(0,1,0,1,1,1) 2.8 (1,1,0,1/4,1,1) 2.925
×
(1,1,0,0,1,1) 2.8 × (1,1,0,1,1,5/8) 2.925
(1,1,0,1,1,0) 2.3 (1,1,0,1,1/2,1) 2.85
× ×结论,(0,1,1,0,1,1)为最优解,最大收益为 2.9亿元,
评注,
分支定界法本质上就是穷举法,不过它是一种改进的穷举法,它在算法实现上有很大的灵活性,往往取决于对问题的处理方式,分支变量的选择顺序对工作量影响极大,因此,要根据问题本身的理解,优先考虑关键的分支,尽早得到一个较好的目标值,从而使得许多分支提前终止,
LINDO软件中也用到了分支定界法,我们来看看上次讲的平板车的例子,本来,简单的穷举法要检验、计算 45× 36× 55× 28× 28× 15× 45=4.7E+10,
就算我们限定,xi7=0,我们也至少要算约 1.0E+9次,但是我们实际上一般迭代几万次,分支在 4到 15千之间,
