下料问题概述

下料问题生产中通过切割、剪裁、冲压等手段，将原材料加工成规定大小的成材.

优化问题按照工艺要求，确定下料方案，使所用材料最省，或利润最大.

钢管切割问题（一维）

题目1

如何下料最省？

分析

1、下料最省的标准（也就是最后的目标函数）

• 原料钢管剩余总余量最小;
• 所用原料钢管总根数最少.

2、由于采用不同切割模式太多, 会增加生产和管理成本,所以要规定切割模式不能超过几种，即切割模式自己设定为固定的几种。

3、按照客户需要在一根原料钢管上安排切割的某种排列组合，合理切割模式的余料应小于客户需要钢管的最小尺寸。

4、约束条件：

• 需求约束
• 原料约束
• 整数约束

求解

为满足客户需要，按照哪些种合理模式切割，每种模式切割多少根原料钢管，最为节省？
因此要设出来，最后找其中的约束关系，利用lingo求解。

思路1——总余量最少

解：设xi是 按第i种模式切割的原料钢管根数(i=1,…,7)

目标函数：

约束条件：

• 需求约束
  
• 整数约束
  xi均为整数

Lingo代码

model:
sets:
schema/1..7/:x,f;pipe/1..3/:b;link(pipe,schema):A;
endsets
data:
f=3,1,3,3,1,1,3;b=50,20,15;
A=4,3,2,1,1,0,0
0,1,0,2,1,3,0
0,0,1,0,1,1,2;
enddata
min=@sum(schema(i):(f(i)*x(i)));
@for(pipe(i):(@sum(schema(j):A(i,j)*x(j)))>=b(i));
@for(schema(i):@gin(x(i)));
end

思路2——总根数最少

解：设xi是 按第i种模式切割的原料钢管根数(i=1,…,7)

目标函数：

约束条件同上

题目2

增加1种需求：10根5m ；切割模式不超过3种；即现有4种需求：50根4m, 10根5m, 20根6m,15根8m；
若用枚举法确定合理切割模式，过于复杂。因此，对大规模问题, 用模型的约束条件界定合理模式。（直接设）设出每一种模式的切割方式，及按照每种模式切割的数量。但是注意，模式不要设置太多，可以自己固定模式数量的上限，否则不仅自己求解困难，在实际生产中管理也过为复杂。

求解

解:设xi是按第i 种模式切割的原料钢管根数(i=1,2,3);
r1i, r2i, r3i, r4i是第i 种切割模式下, 每根原料钢管生产4m、5m、6m和8m长的钢管的数量.

目标函数：（总根数最少）min=x1+x2+x3;

约束条件：

• 需求约束
  

• 原料约束（切割模式合理）
  

• 缩小可行域约束（根据第一问的规律得出）
  

• 整数约束
  xi,rij均为整数

Lingo代码

model:
sets:
schema/1..3/:x;pipe/1..4/:b,c;link(pipe,schema):r;
endsets
data:
b=50,10,20,15;c=4,5,6,8;
enddata
min=@sum(schema(i):x(i));
@for(pipe(i):(@sum(schema(j):r(i,j)*x(j)))>=b(i));
@for(schema(j):(@sum(pipe(i):r(i,j)*c(i)))<19);
@for(schema(j):(@sum(pipe(i):r(i,j)*c(i)))>=16);
@for(schema(i):@gin(x(i)));
@for(schema(j):@for(pipe(i):@gin(r(i,j))));
x(1)>=x(2);
x(2)>=x(3);
end

易拉罐下料（二维）

分析

目标:易拉罐利润扣除原料余料损失后的净利润最大
注意:不能装配的罐身、上下底也是余料
约束：工作时间；原料数量；配套组装

求解

解：设决策变量如下：
xi ~ 按照第i 种模式的生产张数(i=1,2,3,4)；
y1 ~ 一周生产的易拉罐个数；
y2 ~ 不配套的罐身个数；
y3 ~ 不配套的底、盖个数.

每只易拉罐利润0.10元，余料损失0.001元/ cm2，罐身面积PIdh=157.1 cm2；底盖面积PIdd/4=19.6 cm2

目标函数：
max=0.1y1-0.001(222.6x1+183.3x2+261.8x3+169.5y2)

约束：

• 时间约束
  
• 原料约束
  
• 配套约束
  
  
  

总结

一维问题若模式不多，可枚举出来，则列举出所有情况，设出采用每种模式切割的个数，找到合适的约束条件，建立整数线性规划模型。
若模式枚举不过来，则构造整数非线性规划模型, 将各种模式设出来（每种模式如何切割），同时设出采用每种模式切割的数量，然后多找约束条件（如：满足需求、切割模式合理等），列出多个不等式。可用缩小可行域的方法进行化简, 但要保证最优解的存在。
二维、三维问题类似。

切割模式相关软件

CutMaster

CutLogic 2D

附三维问题：

快递包装问题

某企业为下游快递公司生产包装纸箱。该企业生产的原始瓦楞纸有四种型号，皆为正方形，其边长分别为2.5m，2.0m，1.8m, 1.5m, 三层瓦楞板成本分别为10.0，6.5，4.8，4.0元。瓦楞纸边角料可以以每平米1.4元在其企业内部回收利用。五层瓦楞板成本为对应三层板的1.3倍。
问题1.　请利用下表中的数据给出合理的假设，确定该企业1天的生产计划，使其利润最大。
问题2.　如果实际中，提供给下游快递公司的纸箱在容积误差30%之内可以以大纸箱代替小纸箱供货，那么新的最优生产计划是什么？
问题3.　哪一种快递纸箱的需求变化对生产计划最为敏感？

可以展开如下图后参照二维模型进行求解

一、概念

下料：有若干规格的原材料，要切割成一批若干规格的零件，确定一种切割方式，使得原材料用料最少、产生的废料最少。

一维下料：上面提到的规格，可以包含很多属性，比如：长度、宽度、厚度等等。所谓一维下料，只关注其中一种属性，而其它属性被认为全部相同，这样便大大降低了下料问题的处理难度。本文研究的一维下料，以长度作为优化目标。

二、术语定义

原料：用于切割的原材料，长度不定。

零件：从原料中切割下来的短料。

废料：一根原料被使用后，剩余长度无法再用于生产任意零件。一般定义为阈值。

余料：一个原料被使用后，剩余材料仍然可以在后续生产中进行零件切割。

三、问题描述

现有N段长度不等的原料（当然，也可以全部长度相等或者其中一部分长度相等），现需要切割为M段长度不等的零件，生成一种切割方案，使产生的废料最少（阈值）、若必须要产生余料应使余料大于指定长度（阈值）以便余料再利用。

四、解决方案

1）穷举法

当原料和零件数量很小时，穷举法可以对所有切割方案进行穷举遍历，寻找最优解。但是如果原料和零件数量达到一定量后，穷举法时间复杂度成指数级增长，计算机无法算出结果。这里给一些定量的概念，比如从零件的角度穷举，M=20时，穷举数量级为1,048,576，M=30时，穷举数量级为1,073,741,824。即时间复杂度为O(2^M)，隐藏零件数量到达20以上时，就变成了无法完成的任务。

2）遗传算法

百度搜索“一维下料 遗传算法”，会得到非常多的相关论文搜索结果。遗传算法以进化论为依据，当种群进化若干代后，便会得到一个相对精英的种群。将一维下料问题转化为遗传算法模型如下：

a）染色体：a1,a2,a3......am，表示第m个零件在第am根原料上截取；

b）种群初始化：初始化x个可行染色体种群

c）交叉算子：按交叉概率，对染色体进行两两交叉，注意不要交叉出无效染色体

d）变异算子：按变异概率，对染色体中的基因进行剔除并变异，注意不要变异出无效染色体

e）选择算子：采用锦标赛算法或轮盘赌算法，对优秀染色体进行选择

f）适应度函数：根据优化目标设计适应度函数，一般从利用率、废料率角度设计

遗传算法能对下料方案有一定程度的优化，但是优化不明显，或许是哪个算子设计不合理、或者参数没有调到合适的值。（注：相关的论文中，结果数据非常优秀，但本人无法调出那么优秀的方案，所以对有些论文报怀疑态度）。

3）动态规划

一维下料的核心，其实可以对接背包问题，而动态规划实际上是一种解背包问题的其中一种算法。看了几个论文资料，算法没看太懂，暂没时间做实验，不做评价。

4）自研算法

涉及到商业上的问题，不便多说，但整体思路是模拟人工的操作。一般一个工人，拿到一组原料和一组零件规格后，只要给足够的时间，总能设计出一些比较优秀的方案，而此算法正是模拟这个过程。

五、总结

算法的东西，需要深入研究，但是不能一味的陷进去，有时候换个思路，可能得到意想不到的效果。大道至简才是精髓。

最后，放上一个测试链接，有兴趣的欢迎交流：http://106.53.17.139:8088/demo/

下面贴一组数据：

方案1：
余    0，排样规则：2234=2234
余   37，排样规则：2676=2639
余   12，排样规则：2777=2765
余   38，排样规则：2964=2926
余    1，排样规则：3062=1518+1543
余   16，排样规则：3134=3118
余    2，排样规则：3472=3470
余    8，排样规则：3513=3505
余    7，排样规则：3574=1690+1877
余   14，排样规则：3577=1947+1616
余    8，排样规则：3972=1747+2217
余    8，排样规则：3996=3988
余    3，排样规则：4064=2028+2033
余    3，排样规则：4212=2567+1642
余    0，排样规则：4496=2759+1737
余    2，排样规则：4541=2183+2356
余    0，排样规则：4550=2632+1918
余    0，排样规则：4765=2918+1847
余    1，排样规则：4850=4849
余    6，排样规则：4902=2714+2182
余    5，排样规则：5869=3076+2788
余    3，排样规则：5972=3654+2315
余    1，排样规则：6135=3249+2885
余    0，排样规则：6209=3794+2415
余    0，排样规则：7807=3170+2390+2247
余    2，排样规则：8567=4698+3867
余    1，排样规则：8904=5174+3729
余    1，排样规则：9975=2390+2552+2751+2281
余    0，排样规则：10729=3757+3195+3777
余    1，排样规则：11176=4688+4019+2468
余    0，排样规则：11338=5213+3756+2369
余    2，排样规则：11561=3520+4546+3493
余    0，排样规则：11571=2290+4000+5281
余    2，排样规则：12140=3862+4399+2084+1793
余    0，排样规则：12613=5157+5391+2065
余    1，排样规则：13086=4737+5052+3296
余    0，排样规则：13423=4653+4372+4398
余    2，排样规则：13461=4713+4271+4475
余    2，排样规则：14717=3222+4870+4678+1945
余    0，排样规则：14836=4096+5550+5190
余    0，排样规则：15015=5023+2527+5312+2153
余    0，排样规则：15155=3852+5336+3706+2261
余    0，排样规则：15196=5079+2919+4830+2368
余    0，排样规则：15330=4031+2751+5726+2822
余    1，排样规则：15440=3417+5634+3687+2701
余    1，排样规则：15480=2890+4757+5090+2742
余    0，排样规则：15688=4129+4214+3227+4118
余    1，排样规则：15733=3609+5587+3739+2797
余    1，排样规则：15825=4925+5485+5414
余    0，排样规则：16118=5373+5581+5164
余    2，排样规则：16525=3363+4639+5489+3032
余    1，排样规则：16676=5686+5425+5564
余    2，排样规则：16719=5783+3481+4413+3040
余    7，排样规则：16736=3907+5722+3463+3637
余    3，排样规则：16764=5686+5473+5602
余 3854，排样规则：16793=4223+4454+4262
余 3506，排样规则：20185=5451+5705+5523

方案2：
余    0，排样规则：2234=2234
余   37，排样规则：2676=2639
余   12，排样规则：2777=2765
余   38，排样规则：2964=2926
余    1，排样规则：3062=1543+1518
余   16，排样规则：3134=3118
余    2，排样规则：3472=3470
余    8，排样规则：3513=3505
余    7，排样规则：3574=1877+1690
余   14，排样规则：3577=1947+1616
余    8，排样规则：3972=2217+1747
余    8，排样规则：3996=3988
余    3，排样规则：4064=2033+2028
余    3，排样规则：4212=2567+1642
余    0，排样规则：4496=2759+1737
余    2，排样规则：4541=2356+2183
余    0，排样规则：4550=2632+1918
余    0，排样规则：4765=1847+2918
余    1，排样规则：4850=4849
余    7，排样规则：4902=2742+2153
余    0，排样规则：5869=3687+2182
余    0，排样规则：5972=3907+2065
余    1，排样规则：6135=3249+2885
余    0，排样规则：6209=3794+2415
余    0，排样规则：7807=2822+3040+1945
余    2，排样规则：8567=5489+3076
余    1，排样规则：8904=2701+4118+2084
余    0，排样规则：9975=3296+4398+2281
余    1，排样规则：10729=5164+5564
余    0，排样规则：11176=3739+5190+2247
余    3，排样规则：11338=5312+2369+3654
余    0，排样规则：11561=3757+5336+2468
余    0，排样规则：11571=5550+2315+3706
余    0，排样规则：12140=4096+5783+2261
余    1，排样规则：12613=2890+5722+4000
余    1，排样规则：13086=3170+3195+3493+3227
余    0，排样规则：13423=4546+3862+1793+3222
余    2，排样规则：13461=2390+3756+5023+2290
余    0，排样规则：14717=4757+4475+5485
余    0，排样规则：14836=5686+5373+3777
余    1，排样规则：15015=4372+5523+2368+2751
余    1，排样规则：15155=4870+3481+4413+2390
余    0，排样规则：15196=5414+2527+4223+3032
余    0，排样规则：15330=5634+5425+4271
余    0，排样规则：15440=3609+3867+5213+2751
余    1，排样规则：15480=4688+2788+5451+2552
余    0，排样规则：15688=4214+3520+5157+2797
余    3，排样规则：15733=5726+4830+5174
余    0，排样规则：15825=3463+4262+4737+3363
余    2，排样规则：16118=2714+4713+5052+3637
余    9，排样规则：16525=3729+4019+4639+4129
余    1，排样规则：16676=5686+3417+4653+2919
余   36，排样规则：16719=5587+5705+5391
余    0，排样规则：16736=4399+3852+4454+4031
余 3565，排样规则：17866=4678+4698+4925
余 3508，排样规则：18958=5281+5090+5079
余 3529，排样规则：20185=5473+5602+5581

方案3：
余    0，排样规则：2234=2234
余   37，排样规则：2676=2639
余   12，排样规则：2777=2765
余   38，排样规则：2964=2926
余    1，排样规则：3062=1543+1518
余   16，排样规则：3134=3118
余    2，排样规则：3472=3470
余    8，排样规则：3513=3505
余    7，排样规则：3574=1690+1877
余   14，排样规则：3577=1947+1616
余    8，排样规则：3972=2217+1747
余    8，排样规则：3996=3988
余    3，排样规则：4064=2028+2033
余    3，排样规则：4212=2567+1642
余    0，排样规则：4496=2759+1737
余    2，排样规则：4541=2183+2356
余    0，排样规则：4550=2632+1918
余    0，排样规则：4765=2918+1847
余    1，排样规则：4850=4849
余    6，排样规则：4902=2714+2182
余    5，排样规则：5869=3076+2788
余    0，排样规则：5972=3907+2065
余    2，排样规则：6135=2281+3852
余    0，排样规则：6209=3794+2415
余    1，排样规则：7807=5722+2084
余    3，排样规则：8567=4372+2247+1945
余    2，排样规则：8904=4688+4214
余    0，排样规则：9975=5336+4639
余    0，排样规则：10729=5473+3463+1793
余    0，排样规则：11176=3654+2390+2390+2742
余    0，排样规则：11338=2797+2751+3637+2153
余    1，排样规则：11561=4653+3040+3867
余    0，排样规则：11571=4413+3296+3862
余    0，排样规则：12140=4096+5783+2261
余    0，排样规则：12613=2701+4129+3493+2290
余    0，排样规则：13086=5581+5190+2315
余    0，排样规则：13423=5425+2919+5079
余    0，排样规则：13461=4925+4830+3706
余    0，排样规则：14717=2527+5164+3417+3609
余    0，排样规则：14836=5414+4031+5391
余    0，排样规则：15015=4000+3777+4870+2368
余    0，排样规则：15155=2890+5634+4262+2369
余    0，排样规则：15196=5489+3729+3227+2751
余    0，排样规则：15330=5686+5373+4271
余    0，排样规则：15440=5213+3249+3756+3222
余    2，排样规则：15480=5281+5174+5023
余    3，排样规则：15688=3363+3757+4019+4546
余    0，排样规则：15733=5485+4698+5550
余    1，排样规则：15825=2552+3195+4223+3032+2822
余    1，排样规则：16118=5564+2468+4398+3687
余    0，排样规则：16525=3520+5157+4678+3170
余    3，排样规则：16676=3739+5312+4737+2885
余    7，排样规则：16719=5523+5602+5587
余   25，排样规则：16736=3481+4713+4399+4118
余   32，排样规则：16914=5705+5451+5726
余 3549，排样规则：17235=4454+4475+4757
余 3664，排样规则：19492=5052+5090+5686

方案4：
余    0，排样规则：2234=2234
余   37，排样规则：2676=2639
余   12，排样规则：2777=2765
余   38，排样规则：2964=2926
余    1，排样规则：3062=1518+1543
余   16，排样规则：3134=3118
余    2，排样规则：3472=3470
余    8，排样规则：3513=3505
余    7，排样规则：3574=1877+1690
余   14，排样规则：3577=1947+1616
余    8，排样规则：3972=2217+1747
余    8，排样规则：3996=3988
余    3，排样规则：4064=2033+2028
余    3，排样规则：4212=2567+1642
余    0，排样规则：4496=2759+1737
余    2，排样规则：4541=2183+2356
余    0，排样规则：4550=2632+1918
余    0，排样规则：4765=2918+1847
余    1，排样规则：4850=4849
余    7，排样规则：4902=2742+2153
余    7，排样规则：5869=3493+2369
余    0，排样规则：5972=3907+2065
余    1，排样规则：6135=3249+2885
余    2，排样规则：6209=4262+1945
余    1，排样规则：7807=5722+2084
余    0，排样规则：8567=2714+3463+2390
余    0，排样规则：8904=4830+2281+1793
余    1，排样规则：9975=5079+2527+2368
余    1，排样规则：10729=3032+5281+2415
余    0，排样规则：11176=4475+4454+2247
余    0，排样规则：11338=4678+4399+2261
余    0，排样规则：11561=4223+4870+2468
余    0，排样规则：11571=3867+5414+2290
余    0，排样规则：12140=4096+2822+2182+3040
余    0，排样规则：12613=4688+5373+2552
余    0，排样规则：13086=5190+5581+2315
余    2，排样规则：13423=4757+4546+4118
余    0，排样规则：13461=5023+2890+2797+2751
余    0，排样规则：14717=4653+3520+3756+2788
余    0，排样规则：14836=3363+3170+5602+2701
余    0，排样规则：15015=3739+3729+5157+2390
余    0，排样规则：15155=3227+5523+3654+2751
余    1，排样规则：15196=4019+4129+3852+3195
余    2，排样规则：15330=5052+3417+3637+3222
余    0，排样规则：15440=5312+4737+5391
余    1，排样规则：15480=5634+4372+5473
余    0，排样规则：15688=4639+3706+3481+3862
余    0，排样规则：15733=2919+4031+5174+3609
余    1，排样规则：15825=4925+5213+5686
余    5，排样规则：16118=3296+3687+5336+3794
余    4，排样规则：16525=5705+5090+5726
余    0，排样规则：16676=5425+3076+4398+3777
余    0，排样规则：16719=5783+5485+5451
余   10，排样规则：16736=4698+3757+4271+4000
余    2，排样规则：16764=5489+5686+5587
余 3574，排样规则：16914=4413+4214+4713
余 3513，排样规则：19791=5550+5564+5164

方案5：
余    0，排样规则：2234=2234
余   37，排样规则：2676=2639
余   12，排样规则：2777=2765
余   38，排样规则：2964=2926
余    1，排样规则：3062=1518+1543
余   16，排样规则：3134=3118
余    2，排样规则：3472=3470
余    8，排样规则：3513=3505
余    7，排样规则：3574=1877+1690
余   14，排样规则：3577=1947+1616
余    8，排样规则：3972=2217+1747
余    8，排样规则：3996=3988
余    3，排样规则：4064=2033+2028
余    3，排样规则：4212=2567+1642
余    0，排样规则：4496=2759+1737
余    4，排样规则：4541=2290+2247
余    0，排样规则：4550=2632+1918
余    0，排样规则：4765=1847+2918
余    1，排样规则：4850=4849
余    5，排样规则：4902=2714+2183
余    7，排样规则：5869=3493+2369
余    0，排样规则：5972=3907+2065
余    1，排样规则：6135=3249+2885
余    0，排样规则：6209=2415+3794
余    0，排样规则：7807=5451+2356
余    3，排样规则：8567=3729+2751+2084
余    0，排样规则：8904=4000+2751+2153
余    1，排样规则：9975=4372+5602
余    0，排样规则：10729=4223+4713+1793
余    0，排样规则：11176=3687+5174+2315
余    0，排样规则：11338=3227+5079+3032
余    1，排样规则：11561=2919+2182+2822+3637
余    0，排样规则：11571=2261+2281+4639+2390
余    0，排样规则：12140=5373+4399+2368
余    2，排样规则：12613=3481+3739+5391
余    1，排样规则：13086=4262+3076+2552+3195
余    2，排样规则：13423=4737+4031+4653
余    0，排样规则：13461=4925+4830+3706
余    0，排样规则：14717=3862+5686+2468+2701
余    0，排样规则：14836=3363+3756+5190+2527
余    0，排样规则：15015=5634+4019+3417+1945
余    0，排样规则：15155=4698+3654+4413+2390
余    0，排样规则：15196=3463+5425+3520+2788
余    0，排样规则：15330=4678+3040+4870+2742
余    0，排样规则：15440=5023+4398+3222+2797
余    4，排样规则：15480=3852+2890+5564+3170
余    6，排样规则：15688=4454+5705+5523
余    0，排样规则：15733=4096+4271+3609+3757
余    1，排样规则：15825=5722+5414+4688
余    0，排样规则：16118=5485+5581+5052
余    6，排样规则：16525=3867+3777+4757+4118
余    3，排样规则：16676=5164+5726+5783
余   10，排样规则：16719=5550+5473+5686
余    7，排样规则：16736=4214+3296+5090+4129
余 3537，排样规则：17715=5157+4475+4546
余 3509，排样规则：19492=5281+5213+5489
余 3533，排样规则：19768=5336+5312+5587

方案6：
余    0，排样规则：2234=2234
余   37，排样规则：2676=2639
余   12，排样规则：2777=2765
余   38，排样规则：2964=2926
余    1，排样规则：3062=1518+1543
余   16，排样规则：3134=3118
余    2，排样规则：3472=3470
余    8，排样规则：3513=3505
余    7，排样规则：3574=1877+1690
余   14，排样规则：3577=1947+1616
余    8，排样规则：3972=2217+1747
余    8，排样规则：3996=3988
余    3，排样规则：4064=2033+2028
余    3，排样规则：4212=2567+1642
余    0，排样规则：4496=2759+1737
余    2，排样规则：4541=2183+2356
余    0，排样规则：4550=2632+1918
余    0，排样规则：4765=2918+1847
余    1，排样规则：4850=4849
余    6，排样规则：4902=2369+2527
余    0，排样规则：5869=3687+2182
余    0，排样规则：5972=3907+2065
余    1，排样规则：6135=3249+2885
余    0，排样规则：6209=3794+2415
余    1，排样规则：7807=5722+2084
余    0，排样规则：8567=3227+2552+2788
余    1，排样规则：8904=5174+3729
余    1，排样规则：9975=3417+3481+3076
余    0，排样规则：10729=4688+4096+1945
余    0，排样规则：11176=2797+5157+3222
余    0，排样规则：11338=5485+2390+3463
余    1，排样规则：11561=4118+5052+2390
余    0，排样规则：11571=2290+4737+2751+1793
余    0，排样规则：12140=3852+5587+2701
余    0，排样规则：12613=5391+2822+2247+2153
余    0，排样规则：13086=4454+3609+5023
余    0，排样规则：13423=3637+5373+4413
余    0，排样规则：13461=5213+3706+2281+2261
余    0，排样规则：14717=2890+3654+5705+2468
余    0，排样规则：14836=2919+4129+5473+2315
余    1，排样规则：15015=4372+2751+5523+2368
余    1，排样规则：15155=5489+5451+4214
余    1，排样规则：15196=3862+4271+3195+3867
余    0，排样规则：15330=4698+3520+4398+2714
余    2，排样规则：15440=4031+5079+3296+3032
余    3，排样规则：15480=4653+5634+5190
余    1，排样规则：15688=4475+3757+4713+2742
余    1，排样规则：15733=4870+5550+5312
余    2，排样规则：15825=5564+4678+5581
余    0，排样规则：16118=5602+4830+5686
余    0，排样规则：16525=3756+5090+4639+3040
余    2，排样规则：16676=4000+5281+4223+3170
余    5，排样规则：16719=4019+5425+3777+3493
余   36，排样规则：16736=3739+5336+4262+3363
余   91，排样规则：16764=5726+5164+5783
余 3533，排样规则：17235=4546+4399+4757
余 3548，排样规则：19573=4925+5414+5686

今天是开学的第三周周末，一整个上午都在上机，感受颇丰.

“思想上的巨人，代码上的小矮人”，用来形容我倒不为过.（思想上的巨人有些夸大了哈哈哈）.
今天深感无力，碰到一个问题，最令我头疼的还是代码.用什么样的算法解决？如何解决？又如何去改进与优化？这是我们每个人在面对（数学）问题时应仔细考虑的问题.
有时在编写代码前在纸上需要将基本可行方法及步骤写出来，有些东西也确实需要反复推敲方才可能放在软件里面去跑出相对更优的结果.

感慨至此，奔入主题.

实验一：钢管下料问题（LP问题）

要求：已知原料钢管总长度为19米，要求在任意输入l1、l2、l3（客户需求长度）以及对应的需求根数n1、n2、n3时，应用穷举法生成所有可能的合理的切割模式，建立线性规划模型并求解.
解：
（1）穷举法生成所有合理的切割模式.简便起见，我们先假定客户需求为4、6、8米长度（如书中）的钢管.代码请见附录一：（使用matlab）

附录一：

totlen = 19; len1 = 8; len2 = 6; len3 = 4; vector = [];               %规定钢管总长度，与客户需求长度
for num8 = 0:2               %从长度较大者开始切割算起
     restlen = totlen - num8 * len1;               %剩下的用来“分配”另外两种长度的钢管
     if restlen >= 6               %剩下长度能切割的前提是长度足够
         maxnum6 = fix(res tlen / len2);               %剩下钢管分配给中等长度钢管可以切割的最大数量
         for num6 = 0:maxnum6               %从最大数量依次减少（即分情况）
             restlen = restlen - num6 * len2;               %再剩下的用于最小长度钢管的切割
             if restlen >= 4               %剩下长度能切割的前提是长度足够
                 num4 = fix(restlen / len3);
                 remain = restlen - num4 * len3;
                 vector =[vector,num8,num6,num4,remain];
             else
                 num4 = 0;
                 remain = restlen;
                 vector = [vector,num8,num6,num4,remain];
             end
             restlen = totlen - num8 * len1;               %重新给切割完最大长度钢管后的钢管长度赋值
         end
     else
         num6 = 0;
         if restlen >= 4
             num4 = fix(restlen / len3);
         else
             num4 = 0;
             remain = totlen - num8 * len1;
         end
         vector = [vector,num8,num6,num4,remain];               %每一组模式有四个数，我们直接规定成一个向量，最后再整理就可
     end
end
vector
(reshape(vector,4,[]))'               %将得到的模式的原有数据整理成矩阵（表格）显示

（2）建立线性规划模型并求解,代码见附录二：（使用lingo17.0）
为简便起见，先规定客户对于8米、6米、4米钢管的需求根数分别为15、20、50根.建立如下线性规划模型：

Subject to：

Target function：

求解如下：（以余料最小为优化目标）

附录二：

//木材分割中的lingo求解（以余料为优化目标）
model:
sets:
num/1..7/:s,w,t,x,obj;
endsets
data:
s=-4,-3,-2,-1,-1,0,0;
w=0,-1,0,-2,-1,-3,0;
t=0,0,-1,0,-1,0,-2;
obj=3,1,3,3,1,1,3;
enddata
min=@sum(num(i):obj(i)*x(i));
@sum(num(i):s(i)*x(i))<=-50;
@sum(num(i):w(i)*x(i))<=-20;
@sum(num(i):t(i)*x(i))<=-15;
@for(num(i):@GIN(x(i)));
end

原创，转载前请联系邮箱liuan2307511895@foxmail.com 谢谢.*
最近同时在学习python相关内容，有时间就会发博客，随缘.