平板车的装货问题

  • 格式:doc
  • 大小:114.00 KB
  • 文档页数:7

两辆平板车的装货问题

摘要

本文根据平板车装货问题的条件和要求,将原问题抽象、简化为整形规划数学模型,考虑具体问题的细节,则进一步简化为一个0-1规划模型,通过利用LINGO软件求解模型,完整地解决了问题。

由已知条件,可得两辆车的装货的三个约束条件:重量约束、厚度约束、特别限制条件,由于第三个约束条件不太明确,由原问题可建立两个模型,对模型一、二求解得结果为:模型一总使用空间为2039.4cm,浪费0.6cm空间;对模型二求解得总是用空间为2040cm,浪费空间为0cm。

最后,根据本问题的特殊性,将原模型进行简化、优化,最终得到该问题的最优解为总使用空间为2039.4cm。

关键字: 整数规划 LINGO软件 最优解 1 两辆平板车的装货问题

一.问题重述

将7种规格的包装箱要装到两辆平板车上去,包装箱的宽和高是一样的,但厚度(t,以厘米计)及重量(w,以千克计)是不同的。如下表所示给出了每种包装箱的厚度、重量及数量。每辆平板车有10.2m长的地方可用来装包装箱(像面包片那样),载重量为40吨。由于当地货运的限制,对C5、C6、C7类的包装箱的总数有一个特殊的限制,这类箱子所占的空间(厚度)不能超过302.7m,把包装箱装到平板车上去使得浪费的空间最小。

C1 C2 C3 C4 C5 C6 C7

t 48.7 52.0 61.3 72.0 48.7 52.0 64

w 2000 3000 1000 500 4000 2000 1000

件数 8 7 9 6 6 4 8

二.模型假设

(1)这7种规格的包装箱不会因挤压因素等发生变形。

(2)这7种规格的包装箱之间紧密排列,不留空隙。

三、符号说明

符号 代表的意义

i 平板车的7种规格,可以取1,2,3,4,5,6,7

ic 平板车上第i类箱子

ix 第一辆车上的ic类箱子个数

iy 第二辆车上的ic类箱子

in 两辆车上的ic类箱子之和

2 四、问题分析

这是一个典型的整数规划问题,问题的目标是把包装箱装到平板车上去,使得浪费的空间最小,要做的决策是平板车上装的各种箱子的个数,也就是两辆平板车上装的箱子所占的空间最大。经计算,所有箱子公重89吨,共厚2749.5cm而两两辆车得最大载重为80吨,最大载货空间为2040cm,因此不能全部装下。根据要求,要在限制条件下选择装载,使浪费地空间最小,约束条件分为三类:

(1) 重量约束:每辆车载重不超过40吨;

(2) 厚度约束:每辆车上载货厚度不超过1020cm;

(3) 特别限制:C5,C6,C7类包装箱总厚度不能超过302.7cm。

第三个条件不太明确,字面上看不出是两辆车上C5,C6,C7总共不超过302.7cm还是每辆车不超过302.7cm,为此将条件分为两种情况:

A:C5,C6,C7在两辆车上的总厚度不超过302.7cm;

B:C5,C6,C7在每一辆车上的总厚度不超过302.7cm。

按题目所给,将决策变量、目标函数、约束条件用数学符号及式子表示出来,就可得到模型一和二,借助数学软件LINGO进行求解。

五、模型建立

设装在第一辆车上的iC类箱子为ix箱,装在第二辆车上的iC类箱子为iy箱,i=1,2,3,4,5,6,7.

引入向量t,w,n,

0.64,0.52,7.48,0.72,3.61,2.52,7.48,,,,,,7654321tttttttt

1,2,4,5.0,1,3,2,,,,,,7654321wwwwwwww

8,4,6,6,9,7,8,,,,,,7654321nnnnnnnn

令 7654321,,,,,,xxxxxxxx

7654321,,,,,,yyyyyyyy

则在A条件下装货的数学模型为

模型A 71maxiiiiyxt 3 s.t

7,6,5,4,3,2,1,,0,07.3021020102040;407;,6,5,4,3,2,1,7571717171iyxyxyxtytxtywxwinyxiiiiiiiiiiiiiiiiiiiiiii为整数,

在B条件下,得到的数学模型为

模型B 71maxiiiiyxt

s.t

7,6,5,4,3,2,1,,0,07.3027.3021020102040;407;,6,5,4,3,2,1,757571717171iyxyxyxtyxtytxtywxwinyxiiiiiiiiiiiiiiiiiiiiiiiiiii为整数,

六、模型求解

本模型的求解可用整数规划中的分枝定界法、割平面法及0-1规划中的隐枚举发。这里采用LINGO软件求解。由目标函数和约束条件构成的线性规划模型输入LINGO求解,可得如下结果(源程序见附录1):

模型A的最优解为0,0,0,3,4,7,4x,0,3,3,3,5,0,4y,此时总使用空间为2039.4cm,浪费0.6cm.

模型B的最优解为4,0,0,0,6,2,6x,2,1,2,5,2,5,0y,此时总使用空间为2040cm,浪费0cm. 4 七、模型优化

从模型本身可以看出,将两辆车看成是一辆装载空间、载重都大一半的车,构成一合并车厢,求出其近似最有解后,再给两节车箱重新分配并使之平衡,将会简化模型的求解。例如对模型A可先求解如下辅助模型

模型A1 71maxjijjzt

s.t

7,6,5,4,3,2,1,07.302;802040757171jzznzztzwztjjjjjjjjjjjjj为整数,

可以证明,如果模型A1的最有解能被两车平衡,则该解也是模型A的最有解。

八、参考文献

【1】数学模型 姜启源等 高等教育出版社 2003年

【2】数学建模原理与方法 冯杰等 科学出版社 2007年

附件:

采用LINGO编写的代码及运行结果如下:

max=48.7*x11+52.0*x12+61.3*x13+72.0*x14+48.7*x15+52.0*x16+64*x17+48.7*x21+52.0*x22+61.3*x23+72.0*x24+48.7*x25+52.0*x26+64*x27;

x11+x21<=8;

x12+x22<=7;

x13+x23<=9;

x14+x24<=6;

x15+x25<=6;

x16+x26<=4;

x17+x27<=8;

2*x11+3*x12+1*x13+0.5*x14+4*x15+2*x16+1*x17<=40;

2*x21+3*x22+1*x23+0.5*x24+4*x25+2*x26+1*x27<=40; 5 48.7*x15+52.0*x16+64*x17+48.7*x25+52.0*x26+64*x27<=302.7;

48.7*x11+52.0*x12+61.3*x13+72.0*x14+48.7*x15+52.0*x16+64*x17<=1020;

48.7*x21+52.0*x22+61.3*x23+72.0*x24+48.7*x25+52.0*x26+64*x27<=1020;

@GIN( x11);

@GIN( x12);

@GIN( x13);

@GIN( x14);

@GIN( x15);

@GIN( x16);

@GIN( x17);

@GIN( x21);

@GIN( x22);

@GIN( x23);

@GIN( x24);

@GIN( x25);

@GIN( x26);

@GIN( x27);

在LINGO上运行得到如下结果:

Global optimal solution found at step: 222235

Objective value: 2039.400

Branch count: 101516

Variable Value Reduced Cost

X11 5.000000 -48.70000

X12 1.000000 -52.00000

X13 9.000000 -61.30000

X14 1.000000 -72.00000

X15 1.000000 -48.70000

X16 1.000000 -52.00000

X17 0.0000000 -64.00000

X21 3.000000 -48.70000

X22 6.000000 -52.00000

X23 0.0000000 -61.30000

X24 5.000000 -72.00000

X25 2.000000 -48.70000

X26 2.000000 -52.00000

X27 0.0000000 -64.00000

Row Slack or Surplus Dual Price 6 1 2039.400 0.0000000