9414数学空间站--打造中国数学学科航母

资讯无限
您现在的位置： 9414数学空间 >> 资讯无限 >> 高等数学竞赛 >> 数学理论 >> 数学家传记 >> 正文
找找看:

AMCM平板车装货问题

作者：佚名    文章来源：本站原创    点击数：    更新时间：2006-12-25

 

 

9.1    案例2：（ACM88B）两辆铁路平板车的装货问题

要把七种规格的包装箱装到两辆铁路平板车上去。包装箱的宽和高都是相同的，但厚度（t，以厘米计）及重量（w，以千克计）却不同。下表给出了它们的厚度、重量及数量。

 

 

C1

C2

C3

C4

C5

C6

C7

厚度t（厘米）

48.7

52.0

61.3

72.0

48.7

52.0

64.0

重量w（千克）

2000

3000

1000

500

4000

2000

1000

箱数

8

7

9

6

6

4

8

 

每辆平板车有10.2米长的地方可以用来装箱（象面包片那样），载重为40吨。由于当地货运的限制，对三类包装箱（C5、C6、C7）的总数有如下特殊约束：它们所占的空间（厚度）不得超过302.7厘米。试把这些包装箱装到平板车上去，而浪费的空间最小。


 

 

 

 

9.1.1    问题分析：

      很明显，这是一个最优化问题。而优化问题的关键是确定决策变量、最优化目标、约束条件。分析数据可知，所有包装箱的总重量为89吨，因此这些包装箱不可能全部装到这两个平板车上。

分析题目不难看出，装配车的约束有：

平板车载重约束（即不能超重）；

平板车空间约束（即厚度不超过302.7厘米）。

 

优化目标：

优化目标是什么呢？

是包装箱个数装得最多？

还是让两辆平板车总装箱厚度之和最大？

 

由于题目中，装箱方法就像叠面包一样，应该以两辆平板车总装箱厚度之和尽可能大为目标（即让平板车空间利用率最大为目标）。

 

建立模型考虑：

那么根据题目要求，需要完成的决策就是确定各规格的包装箱在分别在两辆平板车上的装箱数目。这些数目都是整数，因此，所求问题，可以归结为一个整数线性规划问题。

9.1.2      定义变量

              ：表示第i辆平板车上装Ci的个数

（i =1，2；j =1，2，3，4，5，6，7）

9.1.3    模型建立

（一）约束条件：

（1）包装箱个数约束：

，i＝1，2。（1）

（2）重量约束：

（3）厚度约束：

      （4）对C5，C6，C7的特殊约束：

      （二）目标函数，

使两辆车的总装箱厚度之和尽可能大，如下：

      因此，原问题可以归结为如下的数学模型：

        

9.1.4        模型求解：

采用Lindo软件求解；

max 0.487 x11 + 0.520 x12 + 0.613 x13 + 0.720 x14 + 0.487 x15 + 0.520 x16 + 0.640 x17 +

    0.487 x21 + 0.520 x22 + 0.613 x23 + 0.720 x24 + 0.487 x25 + 0.520 x26 + 0.640 x27

st

   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

   0.487 x11 + 0.520 x12 + 0.613 x13 + 0.720 x14 + 0.487 x15 + 0.520 x16 + 0.640 x17 <= 10.2

   0.487 x21 + 0.520 x22 + 0.613 x23 + 0.720 x24 + 0.487 x25 + 0.520 x26 + 0.640 x27 <= 10.2

   0.487 x15 + 0.520 x16 + 0.640 x17 <= 3.027

   0.487 x25 + 0.520 x26 + 0.640 x27 <= 3.027

   x11 + x21 <= 8

   x12 + x22 <= 7

   x13 + x23 <= 9

   x14 + x24 <= 6

   x15 + x25 <= 6

   x16 + x26 <= 4

   x17 + x27 <= 8

 

 

   x11 <= 8

 x21 <= 8

 x12<=7

x22<=7

x13<=9

x23<=9

x14<＝6

x24<=6

x15<=6

x25<=6

x16<=4

x26<=4

x17<=8

x27<=8

  

end

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    

运行结果提示出现错误；以下为部分结果；

（原因是：用了gin后，输入的模型中一般不能出现小数）

 

        OBJECTIVE FUNCTION VALUE

 

        1)      20.33300

 

  VARIABLE        VALUE          REDUCED COST

       X11         0.000000         -0.487000

       X12         7.000000         -0.520000

       X13         9.000000         -0.613000

       X14         0.000000         -0.720000

       X15         0.000000         -0.487000

       X16         2.000000         -0.520000

       X17         0.000000         -0.640000

       X21         7.000000         -0.487000

       X22         0.000000         -0.520000

       X23         0.000000         -0.613000

       X24         6.000000         -0.720000

       X25         1.000000         -0.487000

       X26         0.000000         -0.520000

       X27         3.000000         -0.640000

错误原因不明，因此去掉整数约束，得到结果如下，

 LP OPTIMUM FOUND AT STEP      7

 

        OBJECTIVE FUNCTION VALUE

 

        1)      20.40000

 

  VARIABLE        VALUE          REDUCED COST

       X11         0.000000          0.000000

       X12         7.000000          0.000000

       X13         9.000000          0.000000

       X14         1.448611          0.000000

       X15         0.000000          0.000000

       X16         0.000000          0.000000

       X17         0.000001          0.000000

       X21         8.000000          0.000000

       X22         0.000000          0.000000

       X23         0.000000          0.000000

       X24         4.551389          0.000000

       X25         0.000000          0.000000

       X26         0.000000          0.000000

       X27         4.729687          0.000000

 

 

Matlab(Linprogdis函数)求解

如果去掉整数约束，得到结果如下：

Optimization terminated successfully.

 

x =

 

    3.4909

    2.9745

    3.6745

    2.6174

    1.8472

    1.4654

    1.8041

    3.4909

    2.9745

    3.6745

    2.6174

    1.8472

    1.4654

    1.8041

 

 

fval =

 

  -20.4000

 

结果目标函数与Lindo结果一样，但是决策变量的值不同。

 

  采用Linprogdis程序求解，源程序如下：

（略）

注：Linprogdis是关于求解混合整数规划的Matlab函数（由zy采用分支定届法实现）

9.2    思考题：

请问能否分别以两辆车各建立一个优化模型？

 

 


在本站查看更多关于建模的文章

CUMCM奖杯
出乎意料的竞赛结果
没有相关文章
栏目导航
数学家传记文章排行榜
最近更新的文章