数学建模之下料问题

三次作业

下料问题 摘要

本文是针对如何对钢管进行下料问题，根据题目要求以及下料时有关问题进行建立切割费用最少以及切割总根数最少两个目标函数通过结果分析需要使用何种切割模式。

生产方式所花费的成本价格或多或少有所不同，如何选取合理的生产方式以节约成本成为了很多厂家的急需解决的问题。这不仅仅关系到厂家的利益，也影响到一个国家甚至整个人类星球的可利用资源，人们的生活水平不断提高对物资的需求量也不断上升，制定有效合理的生产方式不仅可以为生产者节约成本也可以为社会节约资源，以达到资源利用最大化。本文以用于切割钢管花费最省及切割总根数最少为优化目标，通过构建多元函数和建立线性整数规划模型，利用数学及相关方面的知识对钢管的切割方式进行优化求解最佳方案。 本文最大的特色在于通过求解出切割钢管花费最省及切割总根数最少时分别得出两种目标函数取最小值时的切割模式。通过结果发现两种目标函数取最小值时所需切割根数都一样。于是选择切割钢管花费最省为目标函数，此时的切割模式达到最少，这样既满足了总根数最小有满足了切割费用最小。

关键词：切割模式 LINGO软件 线性整数

一、问题的提出

某钢管零售商从钢管厂进货，将钢管按照顾客的要求切割后出售。从钢管厂进货时得到的原料钢管的长度都是1850mm。现有一客户需要15根290mm、28根315mm、21根350mm和30根455mm的钢管。为了简化生产过程，规定所使用的切割模式的种类不能超过4种，使用频率最高的一种切割模式按照一根原料钢管价值的1/10增加费用，使用频率次之的切割模式按照一根原料钢管价值的2/10增加费用，依次类推，且每种切割模式下的切割次数不能太多（一根钢管最多生产5根产品）。此外，为了减少余料浪费，每种切割模式下的余料不能超过100mm。为了使总费用最小，应如何下料？

二、基本假设

1、假设所研究的每根钢管的长度均为1850mm的钢管。 2、假设每次切割都准确无误。

3、假设切割费用短时间内不会波动为固定值。 5、假设钢管余料价值为0.

6、假设一切运作基本正常不会产生意外事件。

7、每一根钢管的费用都一样，为一常值。

三、符号说明

符号 意义 表示按照第i 种切割模式（i1,2,3,4）切割的原料钢管的根数 xi r1i r2i r3i 第i种切割模式下每根原料钢管生产290mm钢管的数量 第i种切割模式下每根原料钢管生产315mm钢管的数量 第i种切割模式下每根原料钢管生产350mm钢管的数量 第i种切割模式下每根原料钢管生产455mm钢管的数量 生产钢管过程所需要增加的总费用 所需钢管的总根数

r4i P N 四、问题分析和模型的建立与求解

4.1、问题分析和模型的建立与求解 4.1.1问题的分析

结合题意，首先我们要确定应该选取哪些切割模式，生产15根290mm、28根315mm、21根350mm和30根455mm的钢管，每一

种切割模式都要符合客户的需求在原料钢管上安排切割的一种组合，而且必须满足一根原料刚管只能生产5根钢管。例如，我们可以将1850mm的钢管切割成5根长350mm的钢管，余料为100mm；或者将长1850mm的钢管切割成长315mm、355mm和455mm的钢管2根、2根、1根，余料为65mm。显然，可行的切割模式是很多的。于是问题化为在满足客户需要的条件下，按照哪几种合理的模式进行切割，每种模式切割多少根原料钢管最为节省。而由于需求的钢管规格为4种，所以枚举法的工作量较大。可以用xi表示按照第i种模式（i=1,2,3，4）切割的原料钢管的根数。又设使用第i种切割模式下每根原料钢管生产长290mm、315mm、355mm和455mm的钢管数量分别为r1i，r2i，r3i，r4i。

而所谓节省，这里有两种标准，一种切割后剩余的总余料量最小，二是切割原料钢管的总根数最少。 4.1.2模型的建立

根据情况，我们忽略每根钢管的成本价，直接计算增加的总费用，即：

min P=0.1x1+0.2x2+0.3x3+0.4x4

总根数最少：

min N=x1+x2+x3+x4

假设条件 x1>=x2>=x3>=x4 (4-1) 满足客户需求的约束条件为:

r11x1+r12x2+r13x3+r14x4 ≥ 15 (4-2)

r21x1+r22x2+r23x3+r24x4 ≥ 28 (4-3) r31x1+r32x2+r33x3+r34x4 ≥ 21 (4-4) r41x1+r42x2+r43x3+r44x4 ≥ 30 (4-5) 每一种切割模式必须可行、合理，所以每根原料钢管的成品量不能超过1850mm，也不能少于1750mm（余料不能大于100mm），于是 1750≤15r11+28r21+21r31+30r41 ≤1850 (4-6) 1750≤15r12+28r22+21r32+30r42 ≤1850 (4-7) 1750≤15r13+28r23+21r33+30r43 ≤1850 (4-8) 1750≤15r14+28r24+21r34+30r44 ≤1850 (4-9) 最后，加上非负整数约束：

xi，rji ∈ Z+ ， i=1,2,3,4 j=1,2,3,4 (4-10) 于是，问题归结为在在约束条件（4-2）～（4-10）下，求xi和r1i，r2i，r3i，r4i（i=1,2,3）使目标（4-1）达到最小。显然这是线性整数规划模型。 4.1.3模型的求解

非线性整数规划模型（4-1）～（4-9）虽然用LINGO软件可以直接求解，但为了减少运行时间，可以增加一些显然的约束条件，从而缩小可行解的搜索范围。

例如，由于4种切割模式的排列顺序是无关要紧的，所以不妨增加以下约束：

x1≥x2≥x3≥x4 （4-11）

又如，注意到所需原料钢管的总根数有明显的上界和下界。首先，原

料钢管的根数不可能少于

1529028315213503045519 1850 (4-12)

（根）。其次，考虑一种非常特殊的生产计划：第一种切割模式下只生产290mm钢管，一根原料钢管切割成6根290mm钢管，为满足15根290mm钢管的需求，需要3根原料钢管；第二种切割模式下只生产315mm钢管，一根原料钢管切割成5根315mm钢管为满足28根315mm的需求，需要6根原料钢管；第三种切割模式下只生产350mm钢管，一根原料钢管切割成5根350mm钢管，为满足21根350mm钢管的需求，需要5根原料钢管；第四种切割模式下只生产455mm钢管，一根原料钢管切割成4根455mm钢管，为满足30根455mm钢管的需求，需要8根原料钢管。于是满足要求的这种生产计划共需要3+6+5+8=22根原料钢管，这就得到了最优解的一个上界，所以可增加以下约束：

19≤x1+x2+x3+x4≤22 (4-13)

将式（4-1）～（4-13）构成的模型输入LINGO如下： model:

min=0.1*x1+0.2*x2+0.3*x3+0.4*x4;

r11*x1+r12*x2+r13*x3+r14*x4>=15; r21*x1+r22*x2+r23*x3+r24*x4>=28; r31*x1+r32*x2+r33*x3+r34*x4>=21; r41*x1+r42*x2+r43*x3+r44*x4>=30; 290*r11+315*r21+350*r31+455*r41<=1850;

290*r12+315*r22+350*r32+455*r42<=1850; 290*r13+315*r23+350*r33+455*r43<=1850; 290*r14+315*r24+350*r34+455*r44<=1850; 290*r11+315*r21+350*r31+455*r41>=1750; 290*r12+315*r22+350*r32+455*r42>=1750; 290*r13+315*r23+350*r33+455*r43>=1750; 290*r14+315*r24+350*r34+455*r44>=1750; x1+x2+x3+x4>=19; x1+x2+x3+x4<=22; x1>=x2; x2>=x3; x3>=x4;

@gin(x1)；@gin(x2)；@gin(x3)；@gin(x4); @gin(r11)；@gin(r12)；@gin(r13)；@gin(r14); @gin(r21)；@gin(r22)；@gin(r23)；@gin(r24); @gin(r31)；@gin(r32)；@gin(r33)；@gin(r34); @gin(r41)；@gin(r42)；@gin(r43)；@gin(r44); End

当花费P最少时，得到结果为:总共需要19根原料钢管。分别为: 模式一：一根原料可以切割成315mm钢管2根，350mm钢管2根，455mm钢管1根，总共8根。

模式二：一根原料可以切割成290mm钢管1根，315mm钢管2根，

455mm钢管2根 总共6根。

模式三：一根原料可以切割成290mm钢管2根，350mm钢管1根，

455mm钢管2根，总共5根。

当总根数最少时，得到结果为:总共需要19根原料钢管。分别为： 模式一：一根原料可以切割成290mm钢管1根，315mm钢管2根， 455mm钢管2根，总共7根。

模式二：一根原料可以切割成315mm钢管1根，350mm钢管3根，

455mm钢管1根 总共5根。

模式三：一根原料可以切割成290mm钢管2根，315mm钢管1根，455mm钢管2根，总共4根。

模式四：一根原料可以切割成315mm钢管2根，350mm钢管2根，455mm钢管1根，总共3根。

综合两种情况，当两个目标函数取最小值时，所需的总根数都为19。如果选择总根数最小为目标函数，则切割模式增加一种，那么切割费用有所增加。为此选择切割费用最小为目标函数，这样既满足了总根数最小有满足了切割费用最小。

五、评价与改进

在本文中，对于如何下料是根据客户的需要建立了两个目标函

数，通过求解模型发现，总根数最小为目标函数及切割费用最小为目标函数都取最小值时，所需原料都一样。那么本文的优点就是通过结果比较，再结合客户需求选取切割费用最少为目标函数。此时的切割模式达到最少，这样既满足了总根数最小有满足了切割费用最小。

六、参考文献

【1】姜启源等，《数学模型》(第三版)，高等教育出版社，2003

七、附录

7.1 附录正文 附录一：

Lingo求解代码：

min=x1+x2+x3+x4;

r11*x1+r12*x2+r13*x3+r14*x4>=15; r21*x1+r22*x2+r23*x3+r24*x4>=28; r31*x1+r32*x2+r33*x3+r34*x4>=21; r41*x1+r42*x2+r43*x3+r44*x4>=30;

290*r11+315*r21+350*r31+455*r41<=1850; 290*r12+315*r22+350*r32+455*r42<=1850; 290*r13+315*r23+350*r33+455*r43<=1850; 290*r14+315*r24+350*r34+455*r44<=1850; 290*r11+315*r21+350*r31+455*r41>=1750; 290*r12+315*r22+350*r32+455*r42>=1750; 290*r13+315*r23+350*r33+455*r43>=1750; 290*r14+315*r24+350*r34+455*r44>=1750; x1+x2+x3+x4>=19; x1+x2+x3+x4<=22; x1>=x2; x2>=x3; x3>=x4;

@gin(x1);@gin(x2);@gin(x3);@gin(x4);

@gin(r11);@gin(r12);@gin(r13);@gin(r14); @gin(r21);@gin(r22);@gin(r23);@gin(r24); @gin(r31);@gin(r32);@gin(r33);@gin(r34); @gin(r41);@gin(r42);@gin(r43);@gin(r44); End

附录二：

Local optimal solution found at iteration: 43721 Objective value: 19.00000

Variable Value Reduced Cost X1 8.000000 0.000000 X2 6.000000 0.000000 X3 5.000000 0.000000 X4 0.000000 0.000000 R11 0.000000 0.000000 R12 1.000000 0.000000 R13 2.000000 0.000000 R14 0.000000 0.000000 R21 2.000000 0.000000 R22 2.000000 0.000000 R23 0.000000 0.000000 R24 0.000000 0.000000 R31 2.000000 0.000000 R32 0.000000 0.000000 R33 1.000000 0.000000 R34 0.000000 0.000000 R41 1.000000 0.000000 R42 2.000000 0.000000 R43 2.000000 0.000000 R44 4.000000 0.000000

Row Slack or Surplus Dual Price 1 19.00000 -1.000000 2 1.000000 0.000000 3 0.000000 0.000000 4 0.000000 0.000000 5 0.000000 0.000000 6 65.00000 0.000000 7 20.00000 0.000000 8 10.00000 0.000000 9 30.00000 0.000000 10 35.00000 0.000000 11 80.00000 0.000000 12 90.00000 0.000000 13 70.00000 0.000000

14 0.000000 -1.000000 15 3.000000 0.000000 16 2.000000 0.000000 17 1.000000 0.000000 18 5.000000 0.000000

附录三：

Local optimal solution found at iteration: 12509 Objective value: 19.00000

Variable Value Reduced Cost X1 7.000000 0.000000 X2 5.000000 0.000000 X3 4.000000 0.000000 X4 3.000000 0.000000 R11 1.000000 0.000000 R12 0.000000 0.000000 R13 2.000000 0.000000 R14 0.000000 0.000000 R21 2.000000 0.000000 R22 1.000000 0.000000 R23 1.000000 0.000000 R24 2.000000 0.000000 R31 0.000000 0.000000 R32 3.000000 0.000000 R33 0.000000 0.000000 R34 2.000000 0.000000 R41 2.000000 0.000000 R42 1.000000 0.000000 R43 2.000000 0.000000 R44 1.000000 0.000000

Row Slack or Surplus Dual Price 1 19.00000 -1.000000 2 0.000000 0.000000 3 1.000000 0.000000 4 -0.4975089E-07 0.000000 5 0.000000 0.000000 6 20.00000 0.000000 7 30.00000 0.000000 8 45.00000 0.000000 9 65.00000 0.000000 10 80.00000 0.000000 11 70.00000 0.000000 12 55.00000 0.000000

13 35.00000 0.000000 14 0.000000 -1.000000 15 3.000000 0.000000 16 2.000000 0.000000 17 1.000000 0.000000 18 1.000000 0.000000