IE案例分析(五)讲课教案.ppt

《IE案例分析(五)讲课教案.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、IE案例分析(五)案例九：一维下料问题问题分析一维下料是生产实践中常见的问题，优化下料要求最大限度地节约原材料，提高原材料的利用率。对于优化下料问题，属于整数规划问题，要想求出下料方案的最优解，从计算复杂性理论分析，该问题属于NP-hard问题，可用一定数量的运算去解决多项式时间内可解决的问题。虽然整数规划问题是NP-hard问题，但是线性问题却存在有效算法。所以可以考虑不先求解整数规划问题而先来求解其相应的线性问题。采用线性规划来建立数学模型，分析求最优解。案例九：一维下料问题问题分析例如，著名

2、的推销员旅行问题（TravelSalemanProblemorTSP）：假设一个推销员需要从香港出发，经过广州，北京，上海，…，等n个城市，最后返回香港。任意两个城市之间都有飞机直达，但票价不等。现在假设公司只给报销C元钱，问是否存在一个行程安排，使得他能遍历所有城市，而且总的路费小于C？案例九：一维下料问题问题分析推销员旅行问题显然是NP的。因为如果你任意给出一个行程安排，可以很容易算出旅行总开销。但是，要想知道一条总路费小于C的行程是否存在，在最坏情况下，必须检查所有可能的旅行安排！这将是个天

3、文数字。案例九：一维下料问题问题分析旅行推销员问题是数图论中最著名的问题之一，即“已给一个n个点的完全图，每条边都有一个长度，求总长度最短的经过每个顶点正好一次的封闭回路”。Edmonds，Cook和Karp等人发现，这批难题有一个值得注意的性质，对其中一个问题存在有效算法时，每个问题都会有有效算法。案例九：一维下料问题NP难题NP（non-deterministicpolynomial缩写）非确定性多项式。迄今为止，这类问题中没有一个找到有效算法。目前倾向于接受NP完全问题（NP-Complet

4、或NPC）和NP难题（NP-Hard或NPH）不存在有效算法这一猜想，认为这类问题的大型实例不能用精确算法求解，必须寻求这类问题的有效的近似算法。这类问题属于整数规划，求解十分复杂。其原因是可行的下料方式数目可能很大，从而造成要求解的整数规划的维数很高。我们应该知道：首先，一个好的下料方案应该是原材料利用率最大，从而减少损失，降低成本，提高经济效益。案例九：一维下料问题其次，要求所采用的下料方式尽可能少，即希望用最少的下料方式来完成任务。因为在生产中转换下料方式需要费用和时间，导致成本上升，效率下

5、降。因此下料问题的目标是在生产能力容许的条件下，以最少数量的原材料，尽可能按时完成需求任务，同时下料方式数也尽量地少。案例九：一维下料问题根据该问题的特点，我们先从最基本的单目标决策问题入手，以材料损耗最少为目标，通过不同的数学原理建立最优化模型，得出最初的结果。然后逐步增加其约束条件——最小的下料方式数，并根据该约束条件进一步完善我们的最优化模型，得到损耗最少，下料方式数又小的结果。案例九：一维下料问题接下来检验在所得下料方式的排列中，是否存在可以满足时间条件限制的排列方式。若存在，则该结果即为

6、最优解；若不存在，则这个结果就不符合题意，必须重新构建多目标决策的最优化模型。案例九：一维下料问题在新模型中以客户时间需求为第一目标，材料损耗最少，下料方式最少为第二目标。因此，在下料时就应该优先生产那些有时间限制要求的零件，并且求出在需求的时间段内下料方式和损耗的最优结果。案例九：一维下料问题案例一为了建立模型方便，我们把下料后余下的小于最短用料的钢材称为废料头，把下料得到的长2.9m、2.1m、1.5m的钢材称为规格钢，把7.4m长的原料钢材简称原钢。因此，所用的原钢可分解成三部分：成套利用的

7、规格钢、剩余的规格钢、废料头。确定套裁方案，可利用穷举法，得如下方案(见表1)：案例九：一维下料问题案例一方案1方案2方案3方案4方案5方案6方案7方案82.9m120101002.1m002211301.5m31203104合计7.47.37.27.16.66.56.36废料头00.10.20.30.80.91.11.4案例九：一维下料问题设决策变量：采取第i种下料方式的有xi根原钢，i=1，2，…，8。另外设辅助变量：剩余的2.9m规格钢为y1根，剩余的2.1m规格钢为y2根，剩余的1.5m规

8、格钢为y3根。案例九：一维下料问题将剩余的规格钢当作废料的情况minz=0x1+0.1x2+0.2x3+0.3x4+0.8x5+0.9x6+1.1x7+1.4x8+2.9y1+2.1y2+1.5y3案例九：一维下料问题考虑实际生产情况简化模型（去掉料头较大的方案）minz=0x1+0.1x2+0.2x3+0.3x4+2.9y1+2.1y2+1.5y3案例九：一维下料问题利用WinSQB求解：LinearandIntegerProgramming案例九：一维下料问题填入变量及约束的系