《平板车的装载》PPT课件.ppt
平板车的装载平板车的装载MCM88B题题两量铁路平板车的装载问题两量铁路平板车的装载问题有有7种规格的包装箱要装到两辆铁路平板车上去。包装箱的宽和高种规格的包装箱要装到两辆铁路平板车上去。包装箱的宽和高是一样的，但厚度（是一样的，但厚度（t厘米）及重量（厘米）及重量（w公斤）是不同的。见下表：公斤）是不同的。见下表：c1 c2 c3 c4 c5 c6 c7t(厘米）厘米）48.7 52.0 61.3 72.0 48.7 52.0 64.0w(公斤公斤)2000 3000 1000 500 4000 2000 1000件数件数 8 7 9 6 6 4 8每辆平板车有每辆平板车有10.2米长的地方可用来装包装箱米长的地方可用来装包装箱(像面包片那样像面包片那样),载重载重40吨。由于当地货运的限制，对吨。由于当地货运的限制，对c5，c6，c7类的包装箱的类的包装箱的总数有一个特别的限制：这类箱子所占的空间（厚度）不能超过总数有一个特别的限制：这类箱子所占的空间（厚度）不能超过302.7厘米。试把包装箱装到平板车上使浪费的空间最小。厘米。试把包装箱装到平板车上使浪费的空间最小。平板车的装载平板车的装载问题重述在尺寸大小和载重量的约束下，两节车厢上装载各种规格的板条在尺寸大小和载重量的约束下，两节车厢上装载各种规格的板条箱。每种板条箱有特定的厚度和重量，但其宽和高是统一的。向箱。每种板条箱有特定的厚度和重量，但其宽和高是统一的。向量量N，WW和和T T分别表示各种板条箱的数量（单位个）、重量（单分别表示各种板条箱的数量（单位个）、重量（单位吨位吨T T）和厚度（单位）和厚度（单位cmcm）：）：板条箱号板条箱号（个）（个）ni厚度厚度ti cm重量重量T 吨吨 1 2 3 4 5 6 7 8 7 9 6 6 4 848.7 52.0 61.3 72.2 48.7 52.0 64.0 2 3 1 0.5 4 2 1变量引入变量引入X和Y分别表示平板车的实际载货向量，既xi表示第一辆平板车上的第i种板条箱的数量，yi意义相同平板车的装载平板车的装载约束条件约束条件C1；每种板条箱的装载数量不会超过其可用量xi+yi ni 1 i7C2；每节车厢上的箱子厚度不超过1020cmXT1020YT1020“”表示点积C3；每节车厢上的箱子重量不超过40吨XW40YW40C4；卡车约束，既第5,6,7种板条箱的总厚度不超过302.7cm。题目没有讲清总厚度的意义,我们分两种情况定义向量:T使得ti=0,1I4;ti=ti5I7XT+YT302.7(1)XT302.7;YT302.7(2)也就是说：也就是说：X，YNN，（X+Y)T=2039.4X+Y)T=2039.4利用反证法利用反证法;设设X,Y N,(X+Y)T2039.4,N,(X+Y)T2039.4,往证往证(X+Y)T=2039.4(X+Y)T=2039.4首先证明首先证明 xi+yi=ni,i=1,2,3,4.反设存在反设存在i1,2,3,4使得使得 xi+yi302.7说明m5254所以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.0 x2+61.3x3+72x4+48.7x5+52x6+64x7+48.7x8+52.0 x9+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.0 x2+61.3x3+72x4+48.7x5+52x6+64x7=1020 48.7x8+52.0 x9+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 14OBJECTIVE FUNCTION VALUE 1)2039.400VARIABLE 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.000000ROW 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.000000 0.000000 9)0.000000 0.000000 10)0.599998 0.000000 11)2.500000 0.000000 12)10.500000 0.000000 13)0.599998 0.000000
