《平板车的装载》PPT课件

《《平板车的装载》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、平板车的装载MCM88B题两量铁路平板车的装载问题有7种规格的包装箱要装到两辆铁路平板车上去。包装箱的宽和高是一样的，但厚度（t厘米）及重量（w公斤）是不同的。见下表：c1c2c3c4c5c6c7t(厘米）48.752.061.372.048.752.064.0w(公斤)200030001000500400020001000件数8796648每辆平板车有10.2米长的地方可用来装包装箱(像面包片那样),载重40吨。由于当地货运的限制，对c5，c6，c7类的包装箱的总数有一个特别的限制：这类箱子所占的空间（厚度）不能

2、超过302.7厘米。试把包装箱装到平板车上使浪费的空间最小。平板车的装载问题重述在尺寸大小和载重量的约束下，两节车厢上装载各种规格的板条箱。每种板条箱有特定的厚度和重量，但其宽和高是统一的。向量N，W和T分别表示各种板条箱的数量（单位个）、重量（单位吨T）和厚度（单位cm）：板条箱号（个）ni厚度ticm重量T吨1234567879664848.752.061.372.248.752.064.02310.5421变量引入X和Y分别表示平板车的实际载货向量，既xi表示第一辆平板车上的第i种板条箱的数量，yi意义相同平

3、板车的装载约束条件C1；每种板条箱的装载数量不会超过其可用量xi+yi≤ni1≤i≤7C2；每节车厢上的箱子厚度不超过1020cmX·T≤1020Y·T≤1020“·”表示点积C3；每节车厢上的箱子重量不超过40吨X·W≤40Y·W≤40C4；卡车约束，既第5,6,7种板条箱的总厚度不超过302.7cm。题目没有讲清总厚度的意义,我们分两种情况定义向量:T`使得t`i=0,1≤I≤4;t`i=ti5≤I≤7X·T`+Y·T`≤302.7(1)X·T`≤302.7;YT`≤302.7(2)平板车的装载最优解求两车厢的

4、具有最少剩余空间的载货量等价于求(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≤40Y·W=33.5≤403.X·T=1020≤1020Y·T=1019.4

5、≤10204.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`

6、`i+y`i，i=5，6，7反设（3）成立，则由7t5=340.9>302.7说明m5<7，然后分别考虑1。m5=0，由t6，t7是整数知是整数，不能属于（302.1，302.7），（3）不成立2.m5=1，由（3）得因为4t7=256>254所以m7<4,通过验证m7=0,1,2,3四种情况(3)不成立6.m5=5.m6t6+m7t7=59,不可能成立7.m5=6亦无解这样我们就证明了(3)无解,那么2039.4是所能取的最大值模型2的结论定理2:存在{X,Y}满足c1~c3和(2)使得它正好装满两节车厢.X=(

7、6,2,6,0,0,0,4),Y=(0,5,2,5,2,1,2)可以验证它们满足条件定理证明同定理1.证明略max48.7x1+52.0x2+61.3x3+72x4+48.7x5+52x6+64x7+48.7x8+52.0x9+61.3x10+72x11+48.7x12+52x13+64x14stx1+x8<=8x2+x9<=7x3+x10<=9x4+x11<=6x5+x12<=6x6+x13<=4x7+x14<=848.7x1+52.0x2+61.3x3+72x4+48.7x5+52x6+64x7<=102048

8、.7x8+52.0x9+61.3x10+72x11+48.7x12+52x13+64x14<=10202x1+3x2+x3+0.5x4+4x5+2x6+x7<=402x8+3x9+x10+0.5x11+4x12+2x13+x14<=4048.7x5+52x6+64x7+48.7x12+52x13+64x14<=302.7endgin14OBJECTIVEFU