大学论文电气工程与自动化专业数学建模方法与应用课程论文基于最优理论的钢管下料问题.docx
《大学论文电气工程与自动化专业数学建模方法与应用课程论文基于最优理论的钢管下料问题.docx》由会员分享，可在线阅读，更多相关《大学论文电气工程与自动化专业数学建模方法与应用课程论文基于最优理论的钢管下料问题.docx（19页珍藏版）》请在冰点文库上搜索。
大学论文电气工程与自动化专业数学建模方法与应用课程论文基于最优理论的钢管下料问题
XX大学
本科生课程论文
论文题目：
基于最优理论的钢管下料问题
学院：
珠海学院
学系：
电气自动化研究所
专业：
电气工程及其自动化
课程名称：
数学建模方法及应用
学生姓名：
学号：
指导教师：
2010年6月23日
基于最优化理论的钢管下料问题
[摘要]
本题求解的是钢管下料问题，是一个整数线性规划的优化模型。
问题
（1）求解如何下料最为节省，对于如何为最节省，给出两个目标，一个是剩余总余料最省，另一个是切割原料钢管总根数最少。
对于总余料的定义为：
每根钢管切割后不能再切割出产品的部分及生产出来而没有卖掉的产品。
两个目标虽然不同，但是最优解中所用的切割模式和切割钢管根数是一样的，因此两个模型具有等价性。
问题
（2）求解的是如何下了是总费用最少。
总费用包括两个方面的费用：
一是用于购买原料钢管的费用，这部分费用由购买原料钢管总根数决定；二是切割原料钢管的增加费用。
由于切割每根原料钢管的增加费用与原料钢管的价值成正比关系，可以目标函数转化为钢管根数的函数。
根据事实依据增加一些适当的约束条件，使软件快速和有效地求解。
[关键字]：
钢管下料优化模型整数规划
1.问题重述
某钢管零售商从钢管厂进货,将钢管按照顾客的要求切割后售出.从钢管厂进货时得到的原料钢管长度都是1850mm.现有一客户需要15根290mm、28根315mm、21根350mm和30根455mm的钢管.一根原料钢管最多生产5根产品.此外,为了减少余料浪费,每种切割模式下的余料浪费不能超过100mm.
（1）应如何下料最节省？
（2）为了简化生产过程,规定所使用的切割模式的种类不能超过4种,使用频率最高的一种切割模式按照每切割一根原料钢管价值的1/10增加费用,使用频率次之的切割模式按照一根原料钢管价值的2/10增加费用,依此类推。
为了使总费用最小,应如何下料?
2、问题分析
2.1问题
（1）
要确定如何下了最为节省，首先要确定哪些切割模式是可行的。
所谓一个切割模式，是指按照客户的需要在原料钢管上安排切割的一种组合。
显然，可行的切割模式是很多的。
然而，哪些切割模式是可行的呢？
例如如果我们将一根1850mm的原料钢管切下5根290mm规格的钢管，余料为400mm，还可以切割出一根299mm、315mm或着350mm规格的钢管，但是产品根数为6根，不符合题目中的条件，如果余料不再切割，那就造成了很大的浪费。
按照题目的要求，即每根原料钢管生产的产品不能超过五根，并且每种切割模式的余料不能超过100mm，合理可行的切割模式一共有11种，如表2-1所示，
表2-1
290mm钢管数
315mm钢管数
350mm钢管数
455mm钢管数
余料（mm）
模式1
3
0
0
2
70
模式2
2
1
0
2
45
模式3
2
0
1
2
10
模式4
1
2
0
2
20
模式5
1
1
2
1
90
模式6
1
0
3
1
55
模式7
0
3
1
1
100
模式8
0
2
2
1
65
模式9
0
1
3
1
30
模式10
0
0
5
0
100
模式11
0
0
0
4
30
问题化为在满足客户需要的条件下，按照哪几种合理的模式切割多少根原料钢管，最为节省。
而所谓节省，给定两种标准：
一是切割后剩余的总余料量最小，而是切割原料钢管的总根数最少。
2.2问题
（2）
总费用包括两方面的费用，一是用于购买原料钢管的费用，这部分费用由购买原料钢管总根数决定，由于假定购买的原料钢管都用于切割，所以切割的原料钢管总根数越少，费用越少。
二是切割原料钢管的增加费用。
由于切割每根原料钢管的增加费用与原料钢管的价值成正比关系，可以目标函数转化为钢管根数的函数。
例如，设每根钢管的价值为一个单位，则按照使用频率最高的模式切割一根钢管的费用为1/10单位，按照次之使用频率的模式切割一根钢管的费用为2/10单位，以此类推，由此可以给出总费用的目标函数。
按照问题
（1）的思路，可以通过枚举法首先确定那些切割模式是可行的。
但是，由于按每种使用频率不同的模式切割单位钢管的增加费用是不同的，所以还要考虑各种模式使用频率的排列情况，枚举法的工作量就非常大了。
因此必须寻找另外的方法。
另外，由于存在着切割原料钢管的增加费用，所以，切割原料钢管最少的方案不一定使总费用最少。
3、模型假设
1.料钢管的费用及切割原料钢管的增加费用之和，不涉及其它的费用如工人工资、设备损耗费、原料钢管及产品的存储费用，或者认为这些费用已经包含在切割原料钢管的增加费用之中了。
2.钢管切割的损耗忽略不计。
3.所有被切割的原料钢管都能成功地被切割出期待的产品。
4.所有购买的钢管都能被用于生产。
5.如果生产出来的产品数超过客户的需求，超出的部分的产品认为是被浪费了。
4、符号说明
1.：
切割后剩余的总余料量。
2.：
按照第种模式切割原料钢管的增加费用。
3.
：
按照第
种模式（
=1，2，3，4，…，）切割的原料钢管根数，显然它们应当是非负整数。
4.
：
按照第
种切割模式下每根原料钢管生产290mm钢管数量。
5.
：
按照第
种切割模式下每根原料钢管生产315mm钢管数量。
6.
：
按照第
种切割模式下每根原料钢管生产350mm钢管数量。
7.
：
按照第
种切割模式下每根原料钢管生产455mm钢管数量。
5、模型建立与求解求解
5.1问题
（1）
模型建立
决策变量用
表示按照第种模式（=1，2，3，4，…，）切割的原料钢管根数，显然它们应当是非负整数。
决策目标
目标一：
以切割后剩余的总余料量最小为目标，则由表2-1有Min=70x1+45x2+10x3+20x4+90x5+55x6+100x7+65x8+30x9+100x10+30x11
目标二：
以切割原料钢管的总根数最少为目标，则有
Min=x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11
约束条件
它们的约束条件相同，按照表2-1，约束条件如下：
3x1+2x2+2x3+x4+x5+x6≥15
x2+2x4+x5+3x7+2x8+x9≥28
x3+2x5+3x6+x7+2x8+3x9+5x10≥21
2x1+2x2+2x3+2x4+x5+x6+x7+x8+x9+4x11≥30
模型求解
1.将目标一和约束条件构成的整数线性规划模型输入lingo求解，得到最优解如下：
Objectivevalue:
430.0000
Extendedsolversteps:
0
Totalsolveriterations:
6
VariableValueReducedCost
X10.00000070.00000
X20.00000045.00000
X33.00000010.00000
X411.0000020.00000
X50.00000090.00000
X60.00000055.00000
X70.000000100.0000
X80.00000065.00000
X96.00000030.00000
X100.000000100.0000
X110.00000030.00000
按照模式3切割3根原料钢管，按照模式4切割11根原料钢管，按照模式9切割6根原料钢管，总共切割20根，总余料最少，为430mm.
2.将目标二和约束条件构成的整数线性规划模型输入lingo求解，得到最优解如下：
Objectivevalue:
19.00000
Extendedsolversteps:
0
Totalsolveriterations:
7
VariableValueReducedCost
X10.0000001.000000
X20.0000001.000000
X31.0000001.000000
X413.000001.000000
X50.0000001.000000
X60.0000001.000000
X70.0000001.000000
X80.0000001.000000
X92.0000001.000000
X103.0000001.000000
X110.0000001.000000
按照模式割1根原料钢管，按模式4切割13原料钢管，按照模式9切割2原料钢管，按照模式10切割3根原料钢管，可是切割原料钢管总根数最少，为19根
分别以总余料最小和切割原料钢管总根数最少为目标的线性规划得出的结果存在相差，两者之中必定只有一种是最为节省的方案。
通过观察约束条件，可以发现，每种规格的钢管的生产数量没有设定上界，即每种规格钢管的实际生产数量都有可能超过客户的需求，那么，超出客户需求的产品也应该认为是余料。
因此，目标一的目标应该改写为：
Min=x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+290（3x1+2x2+2x3+x4+x5+x6
-15）+315（x2+2x4+x5+3x7+2x8+x9-28）+350（x3+2x5+3x6+x7+2x8+3x9+5x10-21）
+455（2x1+2x2+2x3+2x4+x5+x6+x7+x8+x9+4x11-30）
将修改后目标一和约束条件构成的整数线性规划模型输入lingo求解，得到最优解如下：
Objectivevalue:
980.0000
Extendedsolversteps:
0
Totalsolveriterations:
7
VariableValueReducedCost
X10.0000001850.000
X20.0000001850.000
X31.0000001850.000
X413.000001850.000
X50.0000001850.000
X60.0000001850.000
X70.0000001850.000
X80.0000001850.000
X92.0000001850.000
X103.0000001850.000
X110.0000001850.000
修改目标一后最优解为按照模式割1根原料钢管，按模式4切割13原料钢管，按照模式9切割2原料钢管，按照模式10切割3根原料钢管，实际总余料料最小（包括多生产的产品），为980mm，切割原料钢管总数为19根。
通过对比修改后的目标一和目标二最优解的方案，可以发现它们是一样的。
事实上，这两种方法在本质上是一致的，因为目标二中，切割的原料钢管最少，剩下的是余料，客户需求量是固定的，实际的总余料也就最少。
5.2问题
（2）
模型建立
由于切割模式的种类不能超过4种，可以用
表示按照第
种模式（
=1，2，3，4）切割的原料钢管根数，它们是非负整数。
设所使用的第
种切割模式下每根原料钢管生产290mm，315mm，350mm和455mm钢管数量分别为
，
，
，
，它们为非负整数。
决策目标
总费用最少，假设x1>x2>x3,这对问题没有影响目标为
min=1.1x1+1.2x2+1.3x3+1.4x4
约束条件
为满足客户的条件，应有
r11x1+r12x2+r1x3+r14x≥15
r21x1+r22x2+r23x3+r24x4≥28
r31x1+r32x2+r33x3+r34x4≥21
r41x1+r42x2+r43x3+r44x4≥30
每一种切割模式必须可行、合理，所以每根原料钢管的成品量不超过1850mm，也不能少于1750mm（余料不大于100mm），于是
1750≤290r11+315r21+350r31+455r41≤1850
1750≤290r12+315r22+350r32+455r42≤1850
1750≤290r13+315r23+350r33+455r43≤1850
1750≤290r14+315r24+350r34+455r44≤1850
每种切割模式下每根原料钢管生产的产品数不能超过5根，于是
r11+r21+r31+r41≤5
r12+r22+r32+r42≤5
r13+r23+r33+r43≤5
r14+r24+r34+r44≤5
并且
x1>x2>x3
模型求解
实际上，上边的约束条件确定的范围是很大的，用LINGO求解要很长的时间，因此需要加上一些显然的约束条件，从而缩小可行解的范围。
由于原料钢管不可能少于[（290×15+315×28+350×21+455×30）/1850]=18.5根，于是得到了钢管根数的下界。
可以增加约束条件
x1+x2+x3≥19
将目标函数和约束条件构成的整数线性规划模型输入lingo求解，得到最优解如下：
Objectivevalue:
21.50000
Extendedsolversteps:
267
Totalsolveriterations:
16069
VariableValueReducedCost
X114.00000-0.1000000
X24.0000000.000000
X31.0000000.1000000
X40.0000000.2000000
R111.0000000.000000
R120.0000000.000000
R132.0000000.000000
R144.0000000.000000
R212.0000000.000000
R220.0000000.000000
R230.0000000.000000
R240.0000000.000000
R310.0000000.000000
R325.0000000.000000
R331.0000000.000000
R340.0000000.000000
R412.0000000.000000
R420.0000000.000000
R432.0000000.000000
R441.0000000.000000
即按照模式1，2，3分别切割14，4，1根原料钢管，使用原料钢管总根数19根
第一种切割模式下一根原料钢管切割成1根290mm规格钢管、2根315mm规格钢管和2根455mm规格钢管；第二种切割模式下一根原料钢管切割成5根350mm规格钢管；第三种切割模式下一根原料钢管切割成2根290mm钢管、1根350mm规格钢管和2根455mm规格钢管。
这样的方案使总费用最少，为21.5根钢管的价值。
6、模型检验及评价。
问题
（1）需要求的是如何下料最省，从两个不同的目标出发，建立不同的模型，最后求出最优解，从最优解中可知两者切割模式和计划是相同的，由此得出两者虽然目标不同，本质上是相同的，并且说明了模型的正确性。
问题
（2）需要求的是如何下料使总费用最少，模型通过把目标函数转化为切割原料钢管总根数函数，方便了求解。
同时，为了不使因为求解范围过大而使求解时间过长或无法求解，从一些明显的事实中，增加了一些适当的约束条件，从而是求解的时间大大缩短，快速地求出结果。
运用lingo软件，使得解决模型简单，明了。
参考文献
[1]赵静，但琦主编.数学建模与数学实验[J]：
第三版.北京：
高等教育出版社，2008，37-112
[2]杜宇.优化数学模型及LINGO软件求解[J].黔西南民族师范高等专科学校学报，2008（3）：
111-114
[3]韩中庚，姜启源，陈中月.奶制品加工计划的设计模型[J].信息工程大学学报,2002,3
（1）:
40-42
[4]谢金星，薛毅.优化模型与LINDO/LINGO软件[M].北京：
清华大学出版社，2005.166-190
[5]张杰.建立数学模型解决钢管下料问题[M].山西建能，2009，35（35）：
146-147
附录一
问题
（1）模型
目标一
min=70*x1+45*x2+10*x3+20*x4+90*x5+55*x6+100*x7+65*x8+30*x9+100*x10+30*x11+290*（3*x1+2*x2+2*x3+x4+x5+x6-15）+315*（x2+2*x4+x5+3*x7+2*x8+x9-28）+350*（x3+2*x5+3*x6+x7+2*x8+3*x9+5*x10-21）+455*（2*x1+2*x2+2*x3+2*x4+x5+x6+x7+x8+x9+4*x11-30）;
3*x1+2*x2+2*x3+x4+x5+x6>=15;
x2+2*x4+x5+3*x7+2*x8+x9>=28;
x3+2*x5+3*x6+x7+2*x8+3*x9+5*x10>=21;
2*x1+2*x2+2*x3+2*x4+x5+x6+x7+x8+x9+4*x11>=30;
@gin（x1）;
@gin（x2）;
@gin（x3）;
@gin（x4）;
@gin（x5）;
@gin（x6）;
@gin（x7）;
@gin（x8）;
@gin（x9）;
@gin（x10）;
@gin（x11）;
最优解
Globaloptimalsolutionfound.
Objectivevalue:
980.0000
Extendedsolversteps:
0
Totalsolveriterations:
7
VariableValueReducedCost
X10.0000001850.000
X20.0000001850.000
X31.0000001850.000
X413.000001850.000
X50.0000001850.000
X60.0000001850.000
X70.0000001850.000
X80.0000001850.000
X92.0000001850.000
X103.0000001850.000
X110.0000001850.000
RowSlackorSurplusDualPrice
1980.0000-1.000000
20.0000000.000000
30.0000000.000000
41.0000000.000000
50.0000000.000000
目标二
min=x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11;
3*x1+2*x2+2*x3+x4+x5+x6>=15;
x2+2*x4+x5+3*x7+2*x8+x9>=28;
x3+2*x5+3*x6+x7+2*x8+3*x9+5*x10>=21;
2*x1+2*x2+2*x3+2*x4+x5+x6+x7+x8+x9+4*x11>=30;
@gin（x1）;
@gin（x2）;
@gin（x3）;
@gin（x4）;
@gin（x5）;
@gin（x6）;
@gin（x7）;
@gin（x8）;
@gin（x9）;
@gin（x10）;
@gin（x11）;
最优解
Globaloptimalsolutionfound.
Objectivevalue:
19.00000
Extendedsolversteps:
0
Totalsolveriterations:
7
VariableValueReducedCost
X10.0000001.000000
X20.0000001.000000
X31.0000001.000000
X413.000001.000000
X50.0000001.000000
X60.0000001.000000
X70.0000001.000000
X80.0000001.000000
X92.0000001.000000
X103.0000001.000000
X110.0000001.000000
RowSlackorSurplusDualPrice
119.00000-1.000000
20.0000000.000000
30.0000000.000000
41.0000000.000000
50.0000000.000000
附录二
问题
（2）模型
min=1.1*x1+1.2*x2+1.3*x3+1.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;
x2>x3;
x3>x4;
r11+r21+r31+r41<=5;
r12+r22+r32+r42<=5;
r13+r23+r33+r43<=5;
r14+r24+r34+r44<=5;
@gin（x1）;
@gin（x2）;
@gin（x3）;
@gin（x4）;
@gin（r11）;
@gin（r21）;
@gin（r31）;
@gin（r41）;
@gin（r12）;
@gin（r22）;
@gin（r32）;
@gin（r42）;
@gin（r13）;
@gin（r23）;
@gin（r33）;
@gin（r43）;
@gin（r14）;
@gin（r24）;
@gin（r34）;
@gin（r44）;
最优解
Localoptimalsolutionfound.
Objectivevalue:
21.50000
Extendedsolversteps:
280
Totalsolveriterations:
13285
VariableValueReducedCost
X114.00000-0.1000000
X24.0000000.000000
X31.0000000.1000000
升级会员 