案例七：两辆铁路平板车的装货问题

运筹学案例：案例七：两辆铁路平板车的装货问题第1页共8页案例七：两辆铁路平板车的装货问题案例概述：有7种规格的包装箱要装到两辆铁路平板车上去。包装箱的宽和高是一样的，但厚度（t，以厘米计）及重量（ω，以kg计）是不同的。下表给出了每种包装箱的厚度、重量以及数量。每辆平板车有10.2m长的地方可用来装包装箱（象面包片那样），载重为40t。由于当地货运的限制，对765,,CCC类的包装箱的总数有一个特别的限制：这类箱子所占的空间（厚度）不能超过302.7cm。试把包装箱上平板车而使浪费的空间最小。1C2C3C4C5C6C7C件数8796648()cmt48．752.061.372.048.752.064.0()kgω200030001000500400020001000运筹学案例：案例七：两辆铁路平板车的装货问题第2页共8页案例分析与求解：一、问题重述有7种规格的包装箱要装到两辆铁路平板车上去。包装箱的宽和高是一样的，但厚度（t，以厘米计）及重量（ω，以kg计）是不同的。下表给出了每种包装箱的厚度、重量以及数量。每辆平板车有10.2m长的地方可用来装包装箱（象面包片那样），载重为40t。由于当地货运的限制，对765,,CCC类的包装箱的总数有一个特别的限制：这类箱子所占的空间（厚度）不能超过302.7cm。试把包装箱上平板车而使浪费的空间最小。1C2C3C4C5C6C7C件数8796648()cmt48．752.061.372.048.752.064.0()kgω200030001000500400020001000二、问题假设1、包装箱之间的空隙不计；2、铁路平板车只能放置一列包装箱；三、符号说明ic第i种包装箱ijx第i辆平板车上第j种规格包装箱的数目；jw第j种规格包装箱的重量；jt第j种规格包装箱的厚度；js第j种规格包装箱的总数目；其中，2,1=i运筹学案例：案例七：两辆铁路平板车的装货问题第3页共8页7,6,5,4,3,2,1=j四、模型的建立及求解定理一最优解中第七种包装箱的装货量必然为0。证：根据七种包装箱的厚度和件数，我们可以发现前四种包装箱的厚度总数为1737.3cm，后三种包装箱所占的空间不能超过302.7cm，总占用空间为2040cm。所以最优解必须使前四种包装箱与后三种包装箱分别最大。前四种包装箱全部装上平板车时总数达到最大值。我们对后三种包装箱所占空间求最大值，利用线性规划求解：∑=×=75miniiitcZ⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥=≤≤×∑=)7,6,5(0)7,6,57.30275icisctciiiiii（求得最优解为Z=302.1。此时，0,3,3765===ccc。所以在最优解中第七种包装箱的装货量必然为0。证毕。1、问题分析铁路装货过程中主要解决的是减少空间浪费的问题。存在的限制条件包括铁路平板车的长度、载重量、包装箱自身的件数以及包装箱765,,ccc的厚度；还应考虑包装箱长度的一些特殊性：1c与5c，2c与6c厚度相同，这样可能会导致有多个解；同时两辆平板车之间又存在相互的制约关系，在考虑一辆平板车时，必须同时考虑第二辆平板车运筹学案例：案例七：两辆铁路平板车的装货问题第4页共8页的装货。2、建立模型我们综合问题分析中的限制条件，建立一个整数规划模型：∑∑==−=21712040minijijixtZ⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎧……==≥≤……=≤≤≤≤≤∑∑∑∑∑∑∑=======)7,,2,1;2,1(07.302)7,,2,1(400004000010201020.217121712711712711jixxtjsxxwxwxtxttsijijijjjiijjjjjjjjjjjjj利用计算机求得两辆平板车上七种规格包装箱数目分布如下表（共30组最优解）：表一第一辆第二辆11x12x13x14x15x16x17x21x22x23x24x25x26x27x05640208232310069003081063000764000803233006640108132320144333073530001543320725301016433107153020244323063531002505330629100025432206253110运筹学案例：案例七：两辆铁路平板车的装货问题第5页共8页2643210615312027432006053130309132057050103191310560502032913005505030344313053532003505230529110035431205253210360522051911103643110515322037052105091120374310050532304053330474300040912204705110419121046051204153320464301042533104543020429120045051304353300444303007900208006310最优值Z=0.6五、模型的评价与改进本模型求解出的30组答案达到题目提出的要求，使总的浪费空间最少，均为0.6cm。我们认为铁路部门在考虑空间浪费最少的情况下，也同时要求载重量、占用空间相差尽可能小，将模型进一步改进。1、对载重量要求两辆平板车的载重量差别不应该太大，否则会引发一些安全问题。我们从表一得到的符合题目要求的最优解计算出两辆平板车之间的载重量差值如下（单位：吨）：表二第一辆平板车载重量第二辆平板车载重量总载重量两平板车载重量差值12740671323334671运筹学案例：案例七：两辆铁路平板车的装货问题第6页共8页32839671142938679537.529.5678638.528.56710739.527.56712835.531.5674939.527.567121037.529.56781138.528.567101231.535.56741332.534.56721433.533.56701533.533.56701637.529.56781737.529.56781834.532.56721938.528.567102035.531.56742139.527.567122236.530.56762332.534.56722429.537.56782530.536.56762633.533.56702734.532.56722831.535.56742935.531.5674303433671由表二可知，在要求载重量相差最小的情况下应采用14，15，26号方案，即：两辆平板车装载包装箱ic（i=1，2，……，7）分别为319131056050203291300550503041533204643010此时为最优方案。2、对浪费空间的要求考虑到平板车之间占用空间也不应该相差太大，分别计算满足表一最优解时，两辆平板车的占用空间及它们之间的差值如下表：(单运筹学案例：案例七：两辆铁路平板车的装货问题第7页共8页位：cm)表三第一辆平板车占用空间第二辆平板车占用空间两辆平板车剩余空间二辆平板车占用空间差值11019.81019.60.60.221019.71019.70.6031019.81019.60.60.241019.81019.60.60.2510201019.40.60.6610201019.40.60.6710201019.40.60.6810201019.40.60.691019.51019.90.60.41010201019.40.60.61110201019.40.60.61210201019.40.60.6131019.91019.50.60.4141019.91019.50.60.4151019.91019.50.60.41610201019.40.60.6171019.51019.90.60.41810201019.40.60.6191019.51019.90.60.42010201019.40.60.6211019.51019.90.60.42210201019.40.60.6231019.410200.60.6241019.91019.50.60.4251019.91019.50.60.4261019.410200.60.6271019.410200.60.6281019.91019.50.60.4291019.410200.60.6301019.71019.70.60从表三中可以得到方案2，30满足两辆平板车占用空间差值最小的要求，此时最优解为0690030810630007900208006310参考文献：运筹学案例：案例七：两辆铁路平板车的装货问题第8页共8页【1】李火林等编,《数学模型及方法》,江西高校出版社,南昌,1997【2】洪毅等编,《经济数学模型》,华南理工大学出版社,广州,2002【3】吴江等编,《运筹学模型与方法教程》,清华大学出版社,北京,2000