《数模下料问题与计算》由会员分享，可在线阅读，更多相关《数模下料问题与计算（15页珍藏版）》请在金锄头文库上搜索。
1、华中师范大学数学与统计学学院赵东方dfzhaotom.co1下料问题与计算在工业生产中，经常会遇到切割下料问题，即，如何最佳的切割按固定尺寸供应的材料，使得既符合所需要求又尽可能减少浪费。10.一维下料问题例10-1有10米长的钢管，切割成3米长的80根，4米长的70根，问：怎样下料最省料？解：首先讨论切割方法切割方法133米+04米+废料1米切割方法22米1米废料0米切割方法303米+24米+废料2米设用切割方法i切割ix根钢管目标函数1：总根数最少321m in xxxf +=目标函数2：总废料最少321*0m in xxxf +=约束条件 +整数,0 7032210 8030213.jx
2、 xxx xxxts对第一个目标函数求解，得到结果如下：153,402,01,55m in = xxxf对第二个目标函数求解，得到结果如下：03,702,01,0m in = xxxf此时总根数为70根，总废料为0。注意，两个目标函数构成的线性规划问题不等价。例10-2长500Cm的钢管，切割成98Cm、78Cm的小钢管，要求98Cm的1万根，78Cm的2万根。怎样切割材料最省？解：首先讨论切割方法切割方法1098cm +678cm +废料32cm切割方法21m 5m废料12cm切割方法3298cm +378cm +废料70cm切割方法43m 2m废料50cm切割方法5498cm +178cm
3、 +废料30cm切割方法65m 0m废料10cm华中师范大学数学与统计学学院赵东方dfzhaotom.co2设用切割方法i切割ix根钢管目标函数1：总根数最少654321m in xxxxxxf +=目标函数2：总废料最少654321 103050701232m in xxxxxxf +=约束条件 +整数,0 200006054232516 1000065544332210.jx xxxxxx xxxxxxts对第一个目标函数求解，得到结果如下：12006,05,04,03,40002,01,5200m in = xxxxxxf对第二个目标函数求解，得到结果如下：12006,05,04,03,
4、40002,01,60000m in = xxxxxxf总根数都是5200根，总废料为60000cm。注意，此例中两个目标函数构成的线性规划问题等价。10.2二维下料问题用mm125的钢板切割m31的小钢板60块、mm42的小钢板49块、m75的小钢板12块，如何生产用料最省？解：（一）首先讨论3种小钢板最多各能切割多少块。钢板总面积60m2，m31的小钢板面积3m2，mm42的小钢板面积8m2，mm75的小钢板面积35m2，分别最多切割m ax、m axb、m axc块，则1,7,20m axm axm ax cb。另外，我们注意到，下料的边长都是整数，于是，废料的边长不会超过3，即，废料的
5、面积最多是224m 2。设一次切割13的a块、24的b块、57的c块，则剩余废料满足：( )43583600 + cba。依据这种理由，废料的面积可能是0，1，2，3，4m 2，我们寻找可能的下料方法，在Mathem atica软件包中编程如下：DooDooIf3a+8b+35c=60-k,Print“(,a,”,b,”,c,”),a,0,20,b,0,7,c,0,1,k,0，4其中变量k的取值代表废料的面积。执行后得到20组可能的解：H20,0,0L见下面：切割方法2华中师范大学数学与统计学学院赵东方dfzhaotom.co3H12,3,0L见下面：切割方法9H4,6,0L见下面：切割方法6
6、H3,2,1LH17,1,0L见下面：切割方法1H9,4,0L见下面：切割方法8H1,7,0L8,0,1H0,3,1LH14,2,0L见下面：切割方法10H6,5,0L见下面：切割方法7H5,1,1L见下面：切割方法4H19,0,0L11,3,0H3,6,0LH2,2,1L见下面：切割方法5（3，2，1）H16,1,0L8,4,0H0,7,0LH7,0,1L见下面：切割方法3（8，0，1）另外，根据需求量的面积计算，5333.16.60/)12*3549*860*3( =+，可知最少需要17块钢板用于这次订单的下料。（二）假设（1）由于施工条件所限，切割尽量走直线，最好一刀切到底（便于施工）；
7、（2）切割不计损耗；讨论切割方法如下（约定切割余料统称为废料）：切割方法1对应于（17，1，0）17块1m3m+1块2m4m+块5m7m+废料1m1m13华中师范大学数学与统计学学院赵东方dfzhaotom.co4313124其中阴影部分代表废料，余下同。切割方法2对应于（20，0，0）20块1m3m+0块2m4m+块5m7m+废料0m0m切割方法3对应于（7，0，1）7块1m3m+0块2m4m+块5m7m+废料2m2m57 22切割方法4对应于（5，1，1）5块1m3m+1块2m4m+块5m7m+废料1m2m华中师范大学数学与统计学学院赵东方dfzhaotom.co557 24 21切割方法
8、5对应于（2，2，1）2块1m3m+2块2m4m+块5m7m+废料（1m2m+1m1m）57 242413切割方法6对应于（4，6，0）4块1m3m+6块2m4m+块5m7m+废料0m0m1324切割方法7对应于（6，5，0）6块1m3m+5块2m4m+块5m7m+废料1m2m华中师范大学数学与统计学学院赵东方dfzhaotom.co61324 42313112切割方法8对应于（9，4，0）9块1m3m+4块2m4m+1块5m7m+废料1m1m31切割方法9对应于（12，3，0）12块1m3m+3块2m4m+块5m7m+废料0m0m2442切割方法10对应于（14，2，0）14块1m3m+2块
9、2m4m+1块5m7m+废料1m2m华中师范大学数学与统计学学院赵东方dfzhaotom.co724 12设用切割方法i切割ix块钢板目标函数1：总量最少10987654321m in xxxxxxxxxxf +=目标函数2：总废料的面积最少10987654321 20203240m in xxxxxxxxxxf +=约束条件+ + +整数,012543 4910293847565241 601014912897664524537220117. jx xxx xxxxxxxx xxxxxxxxxxts在Mathem atica软件包中编程求解，两个线性规划都得不到整数解，所以改在Lindo软件
10、包中编程求解。对第一个目标函数总量最少求解：m inx1+x2+x3+x4+x5+x6+x7+x8+x9+x10st17x1+20x2+7x3+5x4+2x5+4x6+6x7+9x8+12x9+14x1060x1+x4+2x5+6x6+5x7+4x8+3x9+2x1049x3+x512endgin10执行后得到结果：OBJECTIVEFUNCTIONVALUE1)18.00000VARIBLEVALUE REDUCEDCOSTX1 0.0000001.0000002X3 0.0000001.000000华中师范大学数学与统计学学院赵东方dfzhaotom.co8X4 6.0000001.000
11、0005X6 6.0000001.0000007 0.000000X8 1.0000009 0.000000X10 1.000000即，总钢板用量18m in=f块，最优解为，010,09,08,07,66,65,64,03,02,01 = xxxxxxxxxx对第二个目标函数总废料的面积最少求解：m inx1+0*x2+4*x3+2*x4+3*x5+0*x6+2*x7+x8+0*x9+2*x10st17x1+20x2+7x3+5x4+2x5+4x6+6x7+9x8+12x9+14x1060x1+x4+2x5+6x6+5x7+4x8+3x9+2x1049x3+x512endgin10执行后得到
12、结果：OBJECTIVEFUNCTIONVALUE1)24.00000VARIBLEVALUE REDUCEDCOSTX1 0.0000004.0000003X4 12.0000002.0000005 0.0000003.000000X7 2.0000008 0.0000001.000000X10 2.0000002 0.0000000.000000X6 7.0000009 0.0000000.000000即，总废料24m in=f2m，最优解为，010,09,08,07,76,05,124,03,02,01 = xxxxxxxxxx注意，两个不同的目标函数构成的线性规划问题不同构。（三）假设
13、（1）切割机器是高智能化的，可以任意编程切割；（2）切割不计损耗；讨论切割方法如下：华中师范大学数学与统计学学院赵东方dfzhaotom.co9切割方法1对应于（17，1，0）17块1m3m+1块2m4m+块5m7m+废料1m1m13313124切割方法2对应于（20，0，0）20块1m3m+0块2m4m+块5m7m+废料0m0m切割方法3将（7，0，1）7块1m3m+0块2m4m+1块5m7m+废料2m2m57 22改变为（8，0，1）8块1m3m+块2m4m+1块5m7m+废料1m1m华中师范大学数学与统计学学院赵东方dfzhaotom.co1057切割方法4对应于（5，1，1）5块1m3
14、m+1块2m4m+块5m7m+废料1m2m57 24 21切割方法5将（2，2，1）2块1m3m+块2m4m+1块5m7m+废料（1m2m+1m1m）57 242413改为（3，2，1）3块1m3m+2块2m4m+1块5m7m+废料0m0m华中师范大学数学与统计学学院赵东方dfzhaotom.co157 4242切割方法6对应于（4，6，0）4块1m3m+6块2m4m+块5m7m+废料0m0m1324切割方法7对应于（6，5，0）6块1m3m+5块2m4m+块5m7m+废料1m2m1324 42313112切割方法8对应于（9，4，0）9块1m3m+4块2m4m+1块5m7m+废料1m1m华中
15、师范大学数学与统计学学院赵东方dfzhaotom.co1231切割方法9对应于（12，3，0）12块1m3m+3块2m4m+块5m7m+废料0m0m2442切割方法10对应于（14，2，0）14块1m3m+2块2m4m+1块5m7m+废料1m2m2412设用切割方法i切割ix块钢板目标函数1：总量最少华中师范大学数学与统计学学院赵东方dfzhaotom.co1310987654321m in xxxxxxxxxxf +=目标函数2：总废料的面积最少10987654321 20203240m in xxxxxxxxxxf +=约束条件+ + +整数,012543 4910293847565241 601014912897664534538220117. jx xxx xxxxxxxx xxxxxxxxxxts在Mathem atica软件包中编程求解，
