《平板车的装》PPT课件.ppt

平板车的装载,MCM88B题,两量铁路平板车的装载问题,有7种规格的包装箱要装到两辆铁路平板车上去。包装箱的宽和高是一样的，但厚度（t厘米）及重量（w公斤）是不同的。见下表：,每辆平板车有10.2米长的地方可用来装包装箱(像面包片那样),载重40吨。由于当地货运的限制，对c5，c6，c7类的包装箱的总数有一个特别的限制：这类箱子所占的空间（厚度）不能超过302.7厘米。试把包装箱装到平板车上使浪费的空间最小。,平板车的装载,问题重述,在尺寸大小和载重量的约束下，两节车厢上装载各种规格的板条箱。每种板条箱有特定的厚度和重量，但其宽和高是统一的。向量N，W和T分别表示各种板条箱的数量（单位个）、重量（单位吨T）和厚度（单位cm）：,变量引入,X和Y分别表示平板车的实际载货向量，既xi表示第一辆平板车上的第i种板条箱的数量，yi意义相同,平板车的装载,约束条件,C1；每种板条箱的装载数量不会超过其可用量 xi + yi ni 1 i7,C2；每节车厢上的箱子厚度不超过1020cm X T 1020 Y T 1020 “” 表示点积,C3；每节车厢上的箱子重量不超过40吨 XW 40 YW 40,C4；卡车约束，既第5,6,7种板条箱的总厚度不超过302.7cm。,题目没有讲清总厚度的意义,我们分两种情况,定义向量:T使得ti=0, 1 I 4; ti=ti 5 I 7,XT+YT 302.7 (1),XT 302.7 ;YT 302.7 (2),平板车的装载,最优解,求两车厢的具有最少剩余空间的载货量等价于求 (X+Y)T 的极大值对应的X和Y.,定理1: 设N是由满足c1C3和(1)的无序对X,Y为元素构成的集合,则存在X,YN使得其总使用空间为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. XW=35.540 YW=33.540,3. XT=10201020 YT=1019.41020,4. XT+YT=302.1302.7,也就是说：X，YN， （X+Y)T=2039.4,利用反证法; 设X,Y N, (X+Y) T2039.4,往证,(X+Y) T=2039.4,首先证明 xi+yi=ni, i=1,2,3,4.,反设存在i1,2,3,4使得 xi+yini 则,(X+Y)T=,说明X，Y至少有48.7cm的剩余空间，矛盾，故xi+yi=ni。i=1，2，3，4,然后由上述结论只需证,不成立,便可得结论：X，Y是最优解。 证法如下,记 mi=xi + yi，i=5，6，7反设（3）成立，则由7t5=340.9302.7,说明m57，然后分别考虑,1。m5=0，由t6，t7是整数知 是整数，不能属于（302.1，302.7），（3）不成立,2. m5=1，由（3）得,因为4t7=256254所以m74,通过验证m7=0,1,2,3四种情况(3)不成立,6. m5=5. m6t6+m7t7=59, 不可能成立,7. m5=6 亦无解,这样我们就证明了(3)无解,那么2039.4是所能取的最大值,模型2的结论,定理2: 存在X,Y满足c1c3和(2)使得它正好装满两节车厢. X=(6,2,6,0,0,0,4),Y=(0,5,2,5,2,1,2),可以验证它们满足条件,定理证明同定理1. 证明略,max 48.7x1+52.0x2+61.3x3+72x4+48.7x5+52x6+64x7+48.7x8+52.0x9+61.3x10+72x11+48.7x12+52x13+64x14 st x1+x8=8 x2+x9=7 x3+x10=9 x4+x11=6 x5+x12=6 x6+x13=4 x7+x14=8 48.7x1+52.0x2+61.3x3+72x4+48.7x5+52x6+64x7=1020 48.7x8+52.0x9+61.3x10+72x11+48.7x12+52x13+64x14=1020 2x1+3x2+x3+0.5x4+4x5+2x6+x7=40 2x8+3x9+x10+0.5x11+4x12+2x13+x14=40 48.7x5+52x6+64x7+48.7x12+52x13+64x14=302.7 end gin 14,OBJECTIVE FUNCTION VALUE 1) 2039.400 VARIABLE VALUE REDUCED COST X1 1.000000 -48.700001 X2 4.000000 -52.000000 X3 4.000000 -61.299999 X4 3.000000 -72.000000 X5 3.000000 -48.700001 X6 3.000000 -52.000000 X7 0.000000 -64.000000 X8 7.000000 -48.700001 X9 3.000000 -52.000000 X10 5.000000 -61.299999 X11 3.000000 -72.000000 X12 0.000000 -48.700001 X13 0.000000 -52.000000 X14 0.000000 -64.000000,ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 0.000000 3) 0.000000 0.000000 4) 0.000000 0.000000 5) 0.000000 0.000000 6) 3.000000 0.000000 7) 1.000000 0.000000 8) 8.