优化模型 下料问题.ppt

《优化模型 下料问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、下料问题下料问题生产中常会遇到通过切割、剪裁、冲压等手段，将原材料加工成所需大小这种工艺过程，称为原料下料（cuttingstock）问题。按照进一步的工艺要求，确定下料方案，使用料最省，或利润最大，是典型的优化问题。本节通过两个实例讨论用数学规划模型解决这类问题的方法。§5.3.1钢管下料问题例5.3某钢管零售商从钢管厂进货，将钢管按照顾客的要求切割后售出。从钢管厂进货时得到的原料钢管都是19米长。1)现有一客户需要50根4米长、20根6米长和15根8米长的钢管。应如何下料最节省？2)零售商如果采用的不同切割模式太多，将会导致生产过程的复杂化，从而增加生产和管理成本

2、，所以该零售商规定采用的不同切割模式不能超过3种。此外，该客户除需要1）中的三种钢管外，还需要10根5米长的钢管。应如何下料最节省？问题1）的求解问题分析首先，应当确定哪些切割模式是可行的。所谓一个切割模式，是指按照客户需要在原料钢管上安排切割的一种组合。例如，我们可以将19米长的钢管切割成3根4米长的钢管，余料为7米显然，可行的切割模式是很多的。其次，应当确定哪些切割模式是合理的。通常假设一个合理的切割模式的余料不应该大于或等于客户需要的钢管的最小尺寸。在这种合理性假设下，切割模式一共有7种，如表5-3所示。表5-3钢管下料的合理切割模式4米钢管根数6米钢管根数8米

3、钢管根数余料（米）模式14003模式23101模式32013模式41203模式51111模式60301模式70023问题化为在满足客户需要的条件下，按照哪些种合理的模式，切割多少根原料钢管，最为节省。而所谓节省，可以有两种标准，一是切割后剩余的总余料量最小，二是切割原料钢管的总根数最少。下面将对这两个目标分别讨论。模型建立决策变量用xi表示按照第i种模式（i=1,2,…,7）切割的原料钢管的根数，显然它们应当是非负整数。决策目标以切割后剩余的总余料量最小为目标，则由表1可得(32)以切割原料钢管的总根数最少为目标，则有(33)下面分别在这两种目标下求解。约束条件为满足

4、客户的需求，按照表1应有模型求解1.将（32），（34）~（36）构成的整数线性规划模型（加上整数约束）输入LINDO如下：Title钢管下料-最小化余量Min3x1+x2+3x3+3x4+x5+x6+3x7s.t.4x1+3x2+2x3+x4+x5>=50x2+2x4+x5+3x6>=20x3+x5+2x7>=15endgin7求解可以得到最优解如下：OBJECTIVEFUNCTIONVALUE1)27.00000VARIABLEVALUEREDUCEDCOSTX10.0000003.000000X212.0000001.000000X30.0000003.0000

5、00X40.0000003.000000X515.0000001.000000X60.0000001.000000X70.0000003.000000即按照模式2切割12根原料钢管，按照模式5切割15根原料钢管，共27根，总余料量为27米。显然，在总余料量最小的目标下，最优解将是使用余料尽可能小的切割模式（模式2和5的余料为1米），这会导致切割原料钢管的总根数较多。2.将（33）~（36）构成的整数线性规划模型（加上整数约束）输入LINDO：Title钢管下料-最小化钢管根数Minx1+x2+x3+x4+x5+x6+x7s.t.4x1+3x2+2x3+x4+x5>=5

6、0x2+2x4+x5+3x6>=20x3+x5+2x7>=15endgin7求解，可以得到最优解如下：OBJECTIVEFUNCTIONVALUE1)25.00000VARIABLEVALUEREDUCEDCOSTX10.0000001.000000X215.0000001.000000X30.0000001.000000X40.0000001.000000X55.0000001.000000X60.0000001.000000X75.0000001.000000即按照模式2切割15根原料钢管，按模式5切割5根，按模式7切割5根，共27根，可算出总余料量为35米。与上

7、面得到的结果相比，总余料量增加了8米，但是所用的原料钢管的总根数减少了2根。在余料没有什么用途的情况下，通常选择总根数最少为目标。问题2）的求解问题分析按照解问题1）的思路，可以通过枚举法首先确定哪些切割模式是可行的。但由于需求的钢管规格增加到4种，所以枚举法的工作量较大。下面介绍的整数非线性规划模型，可以同时确定切割模式和切割计划，是带有普遍性的方法。同1）类似，一个合理的切割模式的余料不应该大于或等于客户需要的钢管的最小尺寸（本题中为4米），切割计划中只使用合理的切割模式，而由于本题中参数都是整数，所以合理的切割模式的余量不能大于3米。此外，这里