问题 (两辆铁路 板车的装载问题) (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 对 的特殊要求