平板车的装载.ppt

平板车的装载 MCM88B题 平板车的装载 平板车的装载 约束条件 平板车的装载 最优解 模型2的结论 定理2: 存在{X,Y}满足c1~c3和(2)使得它正好装满两节车厢. X=(6,2,6,0,0,0,4),Y=(0,5,2,5,2,1,2) * 两量铁路平板车的装载问题 有7种规格的包装箱要装到两辆铁路平板车上去。包装箱的宽和高是一样的，但厚度（t厘米）及重量（w公斤）是不同的。见下表： 件数 8 7 9 6 6 4 8 w(公斤) 2000 3000 1000 500 4000 2000 1000 t(厘米） 48.7 52.0 61.3 72.0 48.7 52.0 64.0 c1 c2 c3 c4 c5 c6 c7 每辆平板车有10.2米长的地方可用来装包装箱(像面包片那样),载重40吨。由于当地货运的限制，对c5，c6，c7类的包装箱的总数有一个特别的限制：这类箱子所占的空间（厚度）不能超过302.7厘米。试把包装箱装到平板车上使浪费的空间最小。 问题重述 在尺寸大小和载重量的约束下，两节车厢上装载各种规格的板条箱。每种板条箱有特定的厚度和重量，但其宽和高是统一的。向量N，W和T分别表示各种板条箱的数量（单位个）、重量（单位吨T）和厚度（单位cm）： 1 2 3 4 5 6 7 8 7 9 6 6 4 8 48.7 52.0 61.3 72.2 48.7 52.0 64.0 2 3 1 0.5 4 2 1 板条箱号 （个）ni 厚度ti cm 重量T 吨 变量引入 X和Y分别表示平板车的实际载货向量，既xi表示第一辆平板车上的第i种板条箱的数量，yi意义相同 C1；每种板条箱的装载数量不会超过其可用量 xi + yi ≤ ni 1 ≤i≤7 C2；每节车厢上的箱子厚度不超过1020cm X?·T ≤ 1020 Y?·T ≤ 1020 “·” 表示点积 C3；每节车厢上的箱子重量不超过40吨 X·W ≤ 40 Y·W ≤ 40 C4；卡车约束，既第5,6,7种板条箱的总厚度不超过302.7cm。 题目没有讲清总厚度的意义,我们分两种情况 定义向量:T`使得t`i=0, 1 ≤ I ≤ 4; t`i=ti 5 ≤ I ≤ 7 X·T`+Y·T`≤ 302.7 (1) X·T`≤ 302.7 ;YT` ≤302.7 (2) 求两车厢的具有最少剩余空间的载货量等价于求 (X+Y)·T 的极大值对应的X和Y. 定理1: 设N是由满足c1~C3和(1)的无序对{X,Y}为元素构成的集合,则存在{X,Y}∈N使得其总使用空间为2039.4cm,这是所能装载的最大数量(既只有0.6cm的剩余). 证明: 考虑X=(4,7,4,3,0,0,0)和Y=(4,0,5,3,3,3,0) 容易验证属于N. 1. X+Y=(8,7,9,6,3,3,0)≤N=(8,7,9,6,6,4,8) 2. X·W=35.5≤40 Y·W=33.5≤40 3. X·T=1020≤1020 Y·T=1019.4≤1020 4. X·T`+Y·T=302.1≤302.7 也就是说：{X，Y}∈N， （X+Y)·T=2039.4 利用反证法; 设{X`,Y`} }∈N, (X`+Y`) ·T≥2039.4,往证 (X`+Y`) ·T=2039.4 首先证明 x`i+y`i=ni, i=1,2,3,4. 反设存在i`∈{1,2,3,4}使得 x`i`+y`i`ni` 则 (X`+Y`)·T= 说明{X`，Y`}至少有48.7cm的剩余空间，矛盾，故x`i+y`i=ni。i=1，2，3，4 然后由上述结论只需证 不成立 便可得结论：{X，Y}是最优解。