问题 (两辆铁路 板车的装载问题) (88年MCM之B题)
问题一 (两辆铁路平 板车的装载问题) (88年MCM之 B题)
要把七种规格的包装箱装到两辆铁路平板车上, 包装箱的宽和高都是相同的,但厚度(t,以厘米计) 及重量(w,以吨计却不同下表给出了它们的厚 度、重量及数量 C1 C4C5C6C7 t(厘米)48752061372048.752 20 64.0 W(吨)23 054 2 1 箱数8796648 每辆平板车有102米的地方可以用来装箱(像面 包片那样载重为40吨由于当地货运的限制对C5, C6,C7三类包装箱的总数有如下特殊约束:它们所占 的空间(厚度)不得超过3027厘米试把这些包装箱装 到平板车上,而浪费的空间最小
要把七种规格的包装箱装到两辆铁路平板车上, 包装箱的宽和高都是相同的,但厚度(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吨,总厚度达到 27495cm,而两辆平板车只能载2×40=80 吨,2040cm,因此不能全装下,究竞在两辆车上 装哪些种各多少个箱子才合适必须有评价的 标准这标准是遵守题中说明的重量、厚度方 面的约束条件,并且体现出尽可能多装 由题意,只考虑像面包片重叠那样的装法, 把问题简化为:两辆车上装箱总厚度之和尽可 花大,这是一个典型的规划问题
1 问题分析 题中所有包装箱共重89吨,总厚度达到 2749.5cm,而两辆平板车只能载2×40=80 吨,2040cm,因此不能全装下,究竟在两辆车上 装哪些种各多少个箱子才合适,必须有评价的 标准.这标准是遵守题中说明的重量、厚度方 面的约束条件,并且体现出尽可能多装. 由题意,只考虑像面包片重叠那样的装法, 把问题简化为:两辆车上装箱总厚度之和尽可 能大,这是一个典型的规划问题
2模型构建 设x表示在第辆平板车装C箱的数量 (i=1,2;j=1,2,3,4,5,6,7) 自然条件0≤x∈Z 箱数约束x1+x21≤8 x1+x2≤7 (3) X1,+x<9 < 14 24 (5) x15 25 ≤6 x16+x26≤4 17 27 8 (8)
2 模型构建 ( 1,2; 1,2,3,4,5,6,7) . i = j = 设xi j表示在第i辆平板车装Cj箱的数量 8 (2) 箱数约束 x11 + x21 7 (3) x12 + x22 8 (8) 4 (7) 6 (6) 6 (5) 9 (4) 1 7 2 7 1 6 2 6 1 5 2 5 1 4 2 4 1 3 2 3 + + + + + x x x x x x x x x x 0 x Z. (1) 自然条件 ij
重量约束2x1+3x12+x13+0.5x14+4x15+2x6+x1740(9) 2x2+3x22+x23+0.5x24+4x23+2x26+x2≤40(10) 厚度约束487x1+52x12+613x13+72x14 +48.7x15+52x16+64x1≤1020(11) 48.7x21+52x22+613x23+72x24 +48.7x25+52x26+64x27≤1020(12) 对C5,C6,C7的特殊要求 48.7x5+52x+64x1+48.7x25+52x26+64x27≤3027(13)
2 3 0.5 4 2 4 0 (1 0) 2 3 0.5 4 2 4 0 (9) 2 1 2 2 2 3 2 4 2 5 2 6 2 7 1 1 1 2 1 3 1 4 1 5 1 6 1 7 + + + + + + + + + + + + x x x x x x x 重量约束 x x x x x x x 48.7 52 64 1020 (11) 48.7 52 61.3 72 1 5 1 6 1 7 1 1 1 2 1 3 1 4 + + + + + + x x x 厚度约束 x x x x 48.7 52 64 1020 (12) 48.7 52 61.3 72 2 5 2 6 2 7 2 1 2 2 2 3 2 4 + + + + + + x x x x x x x 48.7 52 64 48.7 52 64 302.7 (13) C5,C6,C7 x1 5 + x1 6 + x1 7 + x2 5 + x2 6 + x2 7 对 的特殊要求
两辆平板车装箱总厚度之和 S=∑[487X1+52x12+613x+72x;4 +487x;+52x6+64x;7 此问题的数学模型为: maxs=∑0487x1+0.520x2+0.613x;3+0.720x4 +0.487x;s+0.520x6+0.640x7 s,n/(2)-(13) 这是整数线性规划模型
两辆平板车装箱总厚度之和 48.7 52 64 ] S [48.7 52 61.3 72 5 6 7 2 1 1 2 3 4 i i i i i i i i x x x x x x x + + + = + + + = 此问题的数学模型为: − + + + = + + + = (1). (2) (1 3), ., . 0.487 0.520 0.640 ] maxS [0.487 0.520 0.613 0.720 5 6 7 2 1 1 2 3 4 s t x x x x x x x i i i i i i i i 这是整数线性规划模型
我们运用 LINDO软件求解,可以得到该问题的 个最优解为 c1c2c3c4c5c6c7总重总厚度 329130037.510199 550503029.510195 最优值为20394从运行的结果报告来看, LINDO 求解时用到了分支定界法 些技巧与改进 由于两辆平板车的对称性,我们只要对某个
我们运用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.由于两辆平板车的对称性,我们只要对某个
变量进行限制例如x13s4这样计算量就减少了 2从最优解我们发现,前四种货物箱全部装载完 事实上,如果我们仔细计算早就可以发现在限定 所载后三种货物箱的厚度和不超过3027cm时,装 载前四种货物箱的厚度大于或等于2040-3027 =17373,而前四种货物箱的总厚度正好为17373 cm,且总重量为49由于后三种货物箱总厚度不 超过3027cm的最大值我们很容易发现为3021 cm,就是C5三箱,C6三箱C7不装因为它们的厚 度分别为487,52,64换动任何一个都将改动超过 06cm)而此时总重为67手工就可以派出一个最 优解基于这些分析后我们很容易通过
变量进行限制,例如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.问题的提出 个公司有22亿元资金可用来投资现有六 个项目可供选择各项目投资额和预计受益 如下表: 项目 123456 投资(亿元526468 收益(亿元)0.504060.5091 应选那几个项目投资收益最大?
问题二 投资效益问题及分支定界法 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亿元资金可用来投资,现有六 个项目可供选择,各项目投资额和预计受益 如下表: 应选那几个项目投资收益最大?