IE案例分析(五)课件.pptx

《IE案例分析(五)课件.pptx》由会员分享，可在线阅读，更多相关《IE案例分析(五)课件.pptx（72页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、IE案例分析案例分析案例九：一维下料问题案例九：一维下料问题 n线材合理下料问题线材合理下料问题n有一批原料钢材(如钢管、钢筋、角钢、钢梁等)，每根长7.4m。现需做100套钢架，每套需要长2.9 m、2.1 m、1.5m的钢材各一根，问如何下料使所用的原料最省?n如果现有原料钢管每根19米，客户需求4米的钢管50根，6米的钢管20根，以及8米的15根，又该如何下料最节省？如何尽可能满足顾客需求？案例九：一维下料问题案例九：一维下料问题 n问题分析问题分析n一维下料是生产实践中常见的问题，优化下料要求最大限度地节约原材料，提高原材料的利用率。对于优化下料问题，属于整数规划问题，要想求出下料方案

2、的最优解，从计算复杂性理论分析，该问题属于NP-hard问题，可用一定数量的运算去解决多项式时间内可解决的问题。虽然整数规划问题是NP-hard问题，但是线性问题却存在有效算法。所以可以考虑不先求解整数规划问题而先来求解其相应的线性问题。采用线性规划来建立数学模型，分析求最优解。案例九：一维下料问题案例九：一维下料问题 n问题分析问题分析n例如，著名的推销员旅行问题（Travel Saleman Problem or TSP）：假设一个推销员需要从香港出发，经过广州，北京，上海，等 n 个城市，最后返回香港。任意两个城市之间都有飞机直达，但票价不等。现在假设公司只给报销 C 元钱，问是否存在一

3、个行程安排，使得他能遍历所有城市，而且总的路费小于 C？案例九：一维下料问题案例九：一维下料问题 n问题分析问题分析n推销员旅行问题显然是 NP 的。因为如果你任意给出一个行程安排，可以很容易算出旅行总开销。但是，要想知道一条总路费小于 C 的行程是否存在，在最坏情况下，必须检查所有可能的旅行安排！这将是个天文数字。案例九：一维下料问题案例九：一维下料问题 n问题分析问题分析n旅行推销员问题是数图论中最著名的问题之一，即“已给一个n个点的完全图，每条边都有一个长度，求总长度最短的经过每个顶点正好一次的封闭回路”。Edmonds，Cook和Karp等人发现，这批难题有一个值得注意的性质，对其中一

4、个问题存在有效算法时，每个问题都会有有效算法。案例九：一维下料问题案例九：一维下料问题 nNP难题难题nNP（non-deterministic polynomial 缩写）非确定性多项式。n迄今为止，这类问题中没有一个找到有效算法。目前倾向于接受NP完全问题（NP-Complet 或NPC）和NP难题（NP-Hard或NPH）不存在有效算法这一猜想，认为这类问题的大型实例不能用精确算法求解，必须寻求这类问题的有效的近似算法。n这类问题属于整数规划，求解十分复杂。其原因是可行的下料方式数目可能很大，从而造成要求解的整数规划的维数很高。n我们应该知道：首先，一个好的下料方案应该是原材料利用率最大

5、，从而减少损失，降低成本，提高经济效益。案例九：一维下料问题案例九：一维下料问题 n其次，要求所采用的下料方式尽可能少，即希望用最少的下料方式来完成任务。因为在生产中转换下料方式需要费用和时间，导致成本上升，效率下降。因此下料问题的目标是在生产能力容许的条件下，以最少数量的原材料，尽可能按时完成需求任务，同时下料方式数也尽量地少。案例九：一维下料问题案例九：一维下料问题 n根据该问题的特点，我们先从最基本的单目标决策问题入手，以材料损耗最少为目标，通过不同的数学原理建立最优化模型，得出最初的结果。然后逐步增加其约束条件最小的下料方式数，并根据该约束条件进一步完善我们的最优化模型，得到损耗最少，

6、下料方式数又小的结果。案例九：一维下料问题案例九：一维下料问题 n接下来检验在所得下料方式的排列中，是否存在可以满足时间条件限制的排列方式。若存在，则该结果即为最优解；若不存在，则这个结果就不符合题意，必须重新构建多目标决策的最优化模型。案例九：一维下料问题案例九：一维下料问题 n在新模型中以客户时间需求为第一 目标，材料损耗最少，下料方式最少为第二 目标。因此，在下料时就应该优先生产那些有时间限制要求的零件，并且求出在需求的时间段内下料方式和损耗的最优结果。案例九：一维下料问题案例九：一维下料问题 n案例一n为了建立模型方便，我们把下料后余下的小于最短用料的钢材称为废料头，把下料得到的长2.

7、9 m、2.1 m、1.5 m的钢材称为规格钢，把 7.4 m长的原料钢材简称原钢。n因此，所用的原钢可分解成三部分：成套利用的规格钢、剩余的规格钢、废料头。确定套裁方案，可利用穷举法，得如下方案(见表 1)：案例九：一维下料问题案例九：一维下料问题 n案例一方案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案例九：一维下料问题案例九：一维下料问题 n设决策变量：采取第 i种下料方式的有xi根原钢，i=1，2，8。n另外设辅助变

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

9、 Programming案例九：一维下料问题案例九：一维下料问题 n填入变量及约束的系数案例九：一维下料问题案例九：一维下料问题 n求解得案例九：一维下料问题案例九：一维下料问题 n根据计算得到：nX1=30 ，X2=10 ，X3=0 ，X4=50，Y1=Y2=Y3=0n也就是说采用第一种下料方式裁切30根，采用第二种方式裁剪10根采用第四种方式裁剪50根，其他的方式不采用。这个时候的废料最少为16米。而且没有多余的规格钢。这是比较好的一个解。案例九：一维下料问题案例九：一维下料问题 n利用WinSQB求解：Linear and Integer Programmingn不简化不简化案例九：一维

10、下料问题案例九：一维下料问题 案例九：一维下料问题案例九：一维下料问题 n填入变量及约束的系数n求解得案例九：一维下料问题案例九：一维下料问题 nX1=30 ，X2=10 ，X3=0 ，X4=50，Y1=Y2=Y3=0n计算得到的结果与简化后的一样。n是否所有的问题简化与不简化都一样？案例九：一维下料问题案例九：一维下料问题 n讨论讨论n许多书籍在介绍套裁方案时，跟我们一样为了简单通常会将其中的料头较大的方案去掉，如在本例中去掉方案6、方案7、方案8，从而建立只有4种方案的模型。事实上，这种仅仅根据料头的多少来确定套裁方案的解题方法存在较大的不足，首先是不能判定到底选几种方案作为建模时的方案，

11、这本身没有一个标准，选4种方案可以，那5种方案又如何?实在难以确定。案例九：一维下料问题案例九：一维下料问题 n讨论讨论n再就是通过料头大小来放弃一些方案，这种方式并不能与现实中完全吻合，假设我们放弃方案5，但在现实生活中，如果我们对于2.9m这种规格的材料需求特别大，而对于其它两种规格的材料需求量却较小，那么当2.9m规格材料满足需求时，其它两种规格的材料就已经超过了需求，从而使多余的部分成为料头弃掉，而未能实现真正的用料最省。案例九：一维下料问题案例九：一维下料问题 n如果现有原料钢管每根19米，客户需求4米的钢管50根，6米的钢管20根，以及8米的15根，又该如何下料最节省？如何尽可能满

12、足顾客需求？n合理切割模式：余料应小于客户需要钢管的最小尺寸案例九：一维下料问题案例九：一维下料问题 n可行切割模式如下：模式4米钢管根数6米钢管根数8米钢管根数余料（米）14003231013201341203511116030370023案例九：一维下料问题案例九：一维下料问题 n为满足客户需要，按照哪种模式，每种模式切割多少根原料钢管，最为节省？n标准1：原料钢管剩余总余量最少n标准2：所用原料钢管总根数最少案例九：一维下料问题案例九：一维下料问题 n标准1：原料钢管剩余总余量最少n决策变量nxi按第i种模式切割的原料钢管根数（i=1，27）n目标:min z=3x1+x2+3x3+3x

13、4+x5+x6+3x7案例九：一维下料问题案例九：一维下料问题 n采用软件计算：POM Software Library案例九：一维下料问题案例九：一维下料问题 n选择：Linear Programming案例九：一维下料问题案例九：一维下料问题 n选择：Linear Programming案例九：一维下料问题案例九：一维下料问题 n标准1：原料钢管剩余总余量最少n最优解：x2=12,x5=15,其余为0；最优值：27。按模式2切割12根,按模式5切割15根，余料=12*1+15*1=27米 案例九：一维下料问题案例九：一维下料问题 n标准2：所用原料钢管总根数最少n当余料没有用处时，通常以总

14、根数最少为目标 n目标:min z=x1+x2+x3+x4+x5+x6+x7 案例九：一维下料问题案例九：一维下料问题 n利用WinSQB求解：Linear and Integer Programmingn求解得案例九：一维下料问题案例九：一维下料问题 n最优解：x2=15,x5=5,x7=5,其余为0；最优值：25根。n按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料=15*1+5*1+5*3=35米 切割根数余料（米）目标12727目标22535n当余料没有用处时，通常以总根数最少为目标 案例九：一维下料问题案例九：一维下料问题 n标准2：所用原料钢管总根数最少n考虑

15、多余的规格钢也为废料时 n目标:min z=x1+x2+x3+x4+x5+x6+x7+4y1+6y2+8y3 案例九：一维下料问题案例九：一维下料问题 n标准2：所用原料钢管总根数最少案例九：一维下料问题案例九：一维下料问题 n标准2：所用原料钢管总根数最少案例九：一维下料问题案例九：一维下料问题 案例九：一维下料问题案例九：一维下料问题 n标准2：所用原料钢管总根数最少案例九：一维下料问题案例九：一维下料问题 案例九：一维下料问题案例九：一维下料问题 n小结n一维下料问题的求解，答案比较活泛。尽管在所需原材料总根数上答案一致，但在施工方案上却可以大相径庭。通常，在求解小规模问题时利用手工演算

16、，也可以找到全部解，而通常实际问题只需找到一个解即可。案例九：一维下料问题案例九：一维下料问题 n问题的提出问题的提出n某地有三个有色金属矿A1,A2,A3,生产同一种金属矿石,A1矿的年产量为100万吨,A2矿为80万吨,A3矿为50万吨。矿石全部供应四个冶炼厂:B1厂的全部需求量为50万吨,B2厂为70万吨,B3厂为80万吨,B4厂为30万吨。总产量恰好等于总需求量，运价已知，如表所示。问：如何安排运输，使各矿山的矿石运到各冶炼厂满足各厂的需要，且总运输费用最小。案例十：产销平衡问题案例十：产销平衡问题n问题的提出问题的提出案例十：产销平衡问题案例十：产销平衡问题冶冶炼炼厂厂矿矿山山B1B

17、2B3B4A11.520.33A270.81.42A31.20.322.5n最小元素法求解最小元素法求解案例十：产销平衡问题案例十：产销平衡问题销销地地产产地地B1B2B3B4产产量量A11.520.33100A270.81.4280A31.20.322.550需求需求量量50708030230n表中最小元素是C13=0.3,C32=0.3,令x13=mina1,b3=min80,100=80,将80填在C13的下方,表示A1供应80万吨到B3,在x23,x33的位置上分别打“”,表示B3已满足需要。案例十：产销平衡问题案例十：产销平衡问题销销地地产产地地B1B2B3B4产产量量A11.520

18、20.3803100A27300.8201.423080A31.20.35022.550需求量需求量50708030230n计算所有所有非基变量的检验数案例十：产销平衡问题案例十：产销平衡问题销地产地B1B2B3B4产量A11.52020.3803100A27300.8201.423080A31.20.35022.550需求量50708030230n =2-0.8+7-1.5=6.7 n若所有非基变量的检验数全部大于零时，说明不能增加任何非基变量的值，即不能将基变量变量换入成为基变量，否则总运费增加，这时的基本可行解就是最优解，其费用最小。当某个非基变量的检验数ij0时，说明可以增加xij的值

19、，使总运费下降，即将xij由非基变量换入成基变量，这时的基本可行解也就不是最优解，需要对运输方案进行调整。案例十：产销平衡问题案例十：产销平衡问题n这里的检验数有负数，所以当前调运方案费不是最优，须调整改进。案例十：产销平衡问题案例十：产销平衡问题销销地地产产地地B1B2B3B4产产量量A11.52020.3803100A270.8501.423080A31.2300.32022.550需求需求量量50708030230案例十：产销平衡问题案例十：产销平衡问题n再次计算所有所有非基变量的检验数n非基变量的检验数ij全部为非负，故当前调运方案为最优。nZ=1.520+0.380+0.850+23

20、0+1.230+0.320=196。n利用WinSQB求解：Network Modeling 案例十：产销平衡问题案例十：产销平衡问题n填入变量及约束的系数案例十：产销平衡问题案例十：产销平衡问题案例十：产销平衡问题案例十：产销平衡问题n求解，点击菜单栏Solve and Analyze,下拉菜单有四个选择求解方法：nSolve the problem（只求出最优解）、nSolve the Display Steps-Network(网络图求解并显示迭代步骤)、nSolve the Display Steps-Tableau(表格求解并显示迭代步骤)、nSelect Initial Solut

21、ion Method(选择求初始解方法)。n这里选择Select Initial Solution Method。案例十：产销平衡问题案例十：产销平衡问题n求初始解有八种方法，选择其中的Matrix Minimum(MM)矩阵最小元素法，即最小元素法。案例十：产销平衡问题案例十：产销平衡问题n点击菜单栏ResultsGraphic Solution,系统以网络流的形式显示最优调运方案。案例十：产销平衡问题案例十：产销平衡问题n点击菜单栏Solve the Display Steps-Tableau(表格求解并显示迭代步骤)。案例十：产销平衡问题案例十：产销平衡问题n点击菜单栏Next Iter

22、ation,显示下一迭代步骤。案例十：产销平衡问题案例十：产销平衡问题 不平衡运输问题n当总产量与总销量不相等时，称为不平衡运输问题，这类运输问题在实际中常常碰到，其求解方法是将不平衡问题化为平衡问题求解。案例十：产销平衡问题案例十：产销平衡问题 不平衡运输问题n某物资有三个产地Ai（i1，2，3），供应量分别为10，30，20；有三个销地Bj（j1，2，3），其销量分别为25，15，35；从Ai地向Bj地调运物资的单价Cij如下表，试用表上作业法求解。案例十：产销平衡问题案例十：产销平衡问题 调运物资的单价表 运价运价Cij B1B2B3B4aiA1357615A2615325A324393

23、0bj2010530 7065 案例十：产销平衡问题案例十：产销平衡问题 供大于求的问题需要虚设一个产地B5。运价运价Cij B1B2B3B4aiA1357615A2615325A3243930bj2010530 7065 案例十：产销平衡问题案例十：产销平衡问题 供大于求的问题需要虚设一个产地B5。运价运价CijB1B2B3B4B5aiA13576150015A261105315025A322043590530bj2010530（5）7065 案例十：产销平衡问题案例十：产销平衡问题 用最小元素法求初始解。n计算所有所有非基变量的检验数n只有当所有检验数都大于零，运送方案才为最优n利用Win

24、SQB求解：n（1）启动程序。点击开始程序 WinSQB Network Modeling。n（2）建立新问题。在图1中分别选择Transportation Problem、Minimization、Spreadsheet,案例十：产销平衡问题案例十：产销平衡问题n输入标题、产地数为3和销地数为5 案例十：产销平衡问题案例十：产销平衡问题n输入数据 案例十：产销平衡问题案例十：产销平衡问题n求解 案例十：产销平衡问题案例十：产销平衡问题n求解 案例十：产销平衡问题案例十：产销平衡问题1、有时候读书是一种巧妙地避开思考的方法。3月-233月-23Tuesday,March 28,20232、阅读

25、一切好书如同和过去最杰出的人谈话。18:08:4618:08:4618:083/28/2023 6:08:46 PM3、越是没有本领的就越加自命不凡。3月-2318:08:4618:08Mar-2328-Mar-234、越是无能的人，越喜欢挑剔别人的错儿。18:08:4618:08:4618:08Tuesday,March 28,20235、知人者智，自知者明。胜人者有力，自胜者强。3月-233月-2318:08:4618:08:46March 28,20236、意志坚强的人能把世界放在手中像泥块一样任意揉捏。28 三月 20236:08:46 下午18:08:463月-237、最具挑战性的挑

26、战莫过于提升自我。三月 236:08 下午3月-2318:08March 28,20238、业余生活要有意义，不要越轨。2023/3/28 18:08:4618:08:4628 March 20239、一个人即使已登上顶峰，也仍要自强不息。6:08:46 下午6:08 下午18:08:463月-2310、你要做多大的事情，就该承受多大的压力。3/28/2023 6:08:46 PM18:08:4628-3月-2311、自己要先看得起自己，别人才会看得起你。3/28/2023 6:08 PM3/28/2023 6:08 PM3月-233月-2312、这一秒不放弃，下一秒就会有希望。28-Mar-2328 March 20233月-2313、无论才能知识多么卓著，如果缺乏热情，则无异纸上画饼充饥，无补于事。Tuesday,March 28,202328-Mar-233月-2314、我只是自己不放过自己而已，现在我不会再逼自己眷恋了。3月-2318:08:4628 March 202318:08谢谢大家谢谢大家