平板车装货问题

两辆铁路平板车装货问题的讨论摘要本文将铁路平板车的装货问题抽象简化为整数线性规划问题，经过合理假设，建立了优化问题模型，然后利用matlab软件求出一组最优解，考虑到变量较多以及变量权值的特殊（如C2、C6长度相等）我们猜想可能存在多组解，我们再参考matlab求出的一组最优解，根据C语言编译程序求得所有符合条件的60组最优解，经过去重后最终得到30组最优解。本文鉴于题中给出的C5,C6,C7类的包装箱的总数的限制条件“这类箱子所占的空间厚度）不能超过302.7cm”存在两种理解方式，对该问题分两种情况讨论，分别建立模型得出最优方案。第一种理解认为对每辆平板车而言C5,C6,C7类的包装箱所占的空间（厚度）不能超过302.7cm。对此我们建立了整数线性规划模型一并用matlab求得最优解为C1,C2……C6,C7类包装箱的数量为得到了包装箱所浪费的最小空间为0.6cm,参考此最优解进而用C语言求出最终6组最优解（详见表一）。第二种理解认为两辆平板车C5,C6,C7类的包装箱所占的空间（厚度）累计不能超过302.7cm。对此我们建立了整数线性规划模型二并用matlab求得最优解为C1,C2……C6,C7类包装箱的数量为（3，5，0，5，2，3，0，5，2，9，1，1，0，0），得到了包装箱所浪费最小空间为0cm，参考此最优解进而用C语言求出最终30组最优解（详见表二）关键词：整数线性规划分类讨论最优解一、问题重述有七种规格的包装箱要装到两辆铁路平板车上去。包装箱的宽和高是一样的，但厚度（t，以厘米计）及重量（w，以公斤计）是不同的。下表给出了每种包装箱的厚度、重量以及数量。每辆平板车有1020cm的地方可用来装包装箱（像面包片那样），载重为40吨。由于当地货运的限制，对C5,C6,C7类的包装箱的总数有一个特别的限制：这类箱子所占的空间（厚度）不能超过302.7cm（分两辆车和一辆车两种情况讨论。试把包装箱装到平板车上去使得浪费的空间最小。C1C2C3C4C5C6C7t(cm)48.75261.372.048.752.064.0w(kg)2000300010005000400020001000x件数8796648问题分析对于本题目，由于包装箱的宽和高是一样，但厚度（t,cm）及重量（w,kg）是不同的，所以在解决此问题时暂时忽略包装箱的宽和高，而仅仅虑包装箱厚度、重量以及数量。题中对每辆平板车的容量（10.2m），载重量（40t）以及C5,C6,C7类的包装箱的总数有限制（厚度不能超过302.7cm）从而得出约束条件。并在此约束条件限制下使得浪费的空间最小即求目标函数的的最小值，并且平板车上装的包装箱件数为整数，所以本问题为线性规划中的整数规划问题。对题中C5,C6,C7类的包装箱的总数的限制“这类箱子所占的空间（厚度）不能超过302.7cm”，我们认为此处题目存在歧义可以有两种理解方式：（1）对每辆平板车而言C5,C6,C7类的包装箱所占的空间（厚度）不能超过302.7cm；（2）对一次货运而言，即两辆平板车C5,C6,C7类的包装箱所占的空间（厚度）累计不能超过302.7cm。所以对该问题我们分两种情况讨论，分别建立模型，并利用matlab软件求出最优解。考虑到变量较多以及变量权值的特殊（如C2、C6长度相等）我们猜想可能存在多组解。我们参考matlab求出的一组最优解，根据C语言编译程序求得所有符合条件的60组最优解，经过去重后最终得到30组最优解。三、模型假设假设包装箱之间空隙可忽略不计

假设铁路平板车只能放一排包装箱，不可叠加两辆平板车完全相同，不考虑平板车前后次序不考虑在同一平板车上相同规格包装箱排列次序四、符号系统f浪费的空间cijcij第i种包装箱装在第j辆平板车上数目ti第i种包装箱的厚度Wi第i种包装箱的质量第i种包装箱的数目五、模型建立与求解对本题中C5,C6,C7类的包装箱的总数的限制“这类箱子所占的空间（厚度）不能超过302.7cm,我们认为此处题目存在歧义可以有两种理解方式：对每辆平板车而言C5,C6,C7类的包装箱所占的空间（厚度）不能超过302.7cm；对一次货运而言，即两辆平板车C5,C6,C7类的包装箱所占的空间（厚度）累计不能超过302.7cm。对此我们分别建立了两种整数规划模型。5.1模型一的建立与求解假设包装箱之间空隙可忽略不计，铁路平板车只能放一排包装箱，不可叠加，且不考虑平板车前后次序和同一平板车上相同规格包装箱排列次序。此时，设第i种包装箱装在第j辆平板车上数目Ci,则平板车浪费的空间minf=2040-佥7Ct。ijijij=1i=1由于两辆平板车长度均为1020cm，每辆平板车上的包装箱总厚度不应超过1020cm,据此建立第一个约束条件：1020-工Ct>0j=1,2ijii=1由于当地货运的限制，对C5,C6,C7类的包装箱的总数有一个特别的限制：对每辆平板车而言C5,C6,C7类的包装箱所占的空间（厚度）不能超过302.7cm。据此建立第二个约束条件：工Ct<302.7j=1,2ijii=5由于两辆平板车载重均为40000Kg，每辆平板车上包装箱总重量不应超过40000kg，据此建立第三个约束条件：工CW<40000j=1,2ijii=1由于七种包装箱的数目在提供的包装箱件数xi的容许的范围内，并且包装箱在每辆平板车上的数目为非负整数，据此建立第四个约束条件0<£C..<x.j=1,2ijij=1根据以上分析可建立以下整数线性规划数学模型：

minf=2040-昱艺minf=2040-昱艺Cijxij=1i=11020-工Cx>0ijiji=1工C.W.<302.7ijis.t.<i=5工C.W.<40000jii=10<昱C..<x.iji.=15.1.2模型一的求解根据整数规划模型一，我们用matlab求得最优解为两辆车装运C1,C2,...,C7类包装箱的数量分别为（6，2，6，0，0，0，4；1，5，2，5，1，1，2），剩余厚度为0.6cm。考虑到matlab求解整数规划只能求出一组最优解的局限性，我们进而用C语言编程求出了所有符合条件的12组最优解。因为不考虑两车先后次序，我们又用对结果去重，最终得到6组最优解（详见下表）。表一：序号C11C21C31C41C51C61C71C12C22C32C42C52C62C721052521262600042152511262600043152511262600044242502262600045242512262600046232503262600045.2模型二的建立与求解5.2.1模型二的建立

模型二中，除了第二条约束条件变为两辆平板车C5,C6,C7类的包装箱所占的空间（厚度）累计不能超过302.7cm，其它均和模型一相同。约束条件二为：茫7Ct<302.7。ijij=1i=5可以建立如下整数线性规划模型：minf=minf=2040―》为Cijtij=1ij=1i=11020-工Ct>0ijii=1昱艺Ct<302.7ijis.t.<j=1i=1工C.W.<40000jii=10<》C..<x.ijij=1,2j=1,2i=1,2...,7j=15.2.2模型二的求解根据整数规划模型二，用matlab求得最优解为两辆车装运C1,C2,...,C7类包装箱的数量分别为（3,2,9,1,3,0,0;5,5,0,5,0,3,0）,剩余厚度为0.6cm。参考matlab求得的一组最优解，我们又用C语言编程求得所有符合条件的54组最优解，经过去重后最终得到20组最优解（详见下表）。表二：序号C11C21C31C41C51C61C71C12C22C32C42C52C62C72105640208232310206640108132320306900308106300407640008032330507900208006310

614433307353000715433207253010816433107153020924432306353100102505330629100011254322062531101226432106153120132743200605313014309132057050101531913105605020163291300550503017344313053532001835052305291100193543120525321020360522051911102136431105153220223705210509112023374310050532302440533304743000254091220470511026415332046430102741912104605120284253310454302029429120045051303043533004443030六、模型分析本文针对两辆铁路平板车装运包装箱的问题，在合理假设后建立装货建立整数规划模型，通过matlab分析得出一组最优分配方式，利用C语言编程得到第一种情况下所有满足最小浪费空间为0.6m的分配方式共6组、第二种情况下所有满足最小浪费空间为0m的分配方式共30组。（程序及数据输出见附录1、2）七、模型推广面考虑实际生活中货车的安全问题，实际生活中还有其他因素比如两辆货车在不同情况下的载重、浪费空间之差