IE案例分析(五)

IE案例分析王晓光武汉理工大学机电工程学院案例九：一维下料问题线材合理下料问题有一批原料钢材(如钢管、钢筋、角钢、钢梁等)，每根长7.4m。现需做100套钢架，每套需要长2.9m、2.1m、1.5m的钢材各一根，问如何下料使所用的原料最省?如果现有原料钢管每根19米，客户需求4米的钢管50根，6米的钢管20根，以及8米的15根，又该如何下料最节省？如何尽可能满足顾客需求？案例九：一维下料问题问题分析一维下料是生产实践中常见的问题，优化下料要求最大限度地节约原材料，提高原材料的利用率。对于优化下料问题，属于整数规划问题，要想求出下料方案的最优解，从计算复杂性理论分析，该问题属于NP-hard问题，可用一定数量的运算去解决多项式时间内可解决的问题。虽然整数规划问题是NP-hard问题，但是线性问题却存在有效算法。所以可以考虑不先求解整数规划问题而先来求解其相应的线性问题。采用线性规划来建立数学模型，分析求最优解。案例九：一维下料问题问题分析例如，著名的推销员旅行问题（TravelSalemanProblemorTSP）：假设一个推销员需要从香港出发，经过广州，北京，上海，…，等n个城市，最后返回香港。任意两个城市之间都有飞机直达，但票价不等。现在假设公司只给报销C元钱，问是否存在一个行程安排，使得他能遍历所有城市，而且总的路费小于C？案例九：一维下料问题问题分析推销员旅行问题显然是NP的。因为如果你任意给出一个行程安排，可以很容易算出旅行总开销。但是，要想知道一条总路费小于C的行程是否存在，在最坏情况下，必须检查所有可能的旅行安排！这将是个天文数字。案例九：一维下料问题问题分析旅行推销员问题是数图论中最著名的问题之一，即“已给一个n个点的完全图，每条边都有一个长度，求总长度最短的经过每个顶点正好一次的封闭回路”。Edmonds，Cook和Karp等人发现，这批难题有一个值得注意的性质，对其中一个问题存在有效算法时，每个问题都会有有效算法。案例九：一维下料问题NP难题NP（non-deterministicpolynomial缩写）非确定性多项式。迄今为止，这类问题中没有一个找到有效算法。目前倾向于接受NP完全问题（NP-Complet或NPC）和NP难题（NP-Hard或NPH）不存在有效算法这一猜想，认为这类问题的大型实例不能用精确算法求解，必须寻求这类问题的有效的近似算法。这类问题属于整数规划，求解十分复杂。其原因是可行的下料方式数目可能很大，从而造成要求解的整数规划的维数很高。我们应该知道：首先，一个好的下料方案应该是原材料利用率最大，从而减少损失，降低成本，提高经济效益。案例九：一维下料问题其次，要求所采用的下料方式尽可能少，即希望用最少的下料方式来完成任务。因为在生产中转换下料方式需要费用和时间，导致成本上升，效率下降。因此下料问题的目标是在生产能力容许的条件下，以最少数量的原材料，尽可能按时完成需求任务，同时下料方式数也尽量地少。案例九：一维下料问题根据该问题的特点，我们先从最基本的单目标决策问题入手，以材料损耗最少为目标，通过不同的数学原理建立最优化模型，得出最初的结果。然后逐步增加其约束条件——最小的下料方式数，并根据该约束条件进一步完善我们的最优化模型，得到损耗最少，下料方式数又小的结果。案例九：一维下料问题接下来检验在所得下料方式的排列中，是否存在可以满足时间条件限制的排列方式。若存在，则该结果即为最优解；若不存在，则这个结果就不符合题意，必须重新构建多目标决策的最优化模型。案例九：一维下料问题在新模型中以客户时间需求为第一目标，材料损耗最少，下料方式最少为第二目标。因此，在下料时就应该优先生产那些有时间限制要求的零件，并且求出在需求的时间段内下料方式和损耗的最优结果。案例九：一维下料问题案例一为了建立模型方便，我们把下料后余下的小于最短用料的钢材称为废料头，把下料得到的长2.9m、2.1m、1.5m的钢材称为规格钢，把7.4m长的原料钢材简称原钢。因此，所用的原钢可分解成三部分：成套利用的规格钢、剩余的规格钢、废料头。确定套裁方案，可利用穷举法，得如下方案(见表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规格钢为y3根。案例九：一维下料问题将剩余的规格钢当作废料的情况minz=0x1+0.1x2+0.2x3+0.3x4+0.8x5+0.9x6+1.1x7+1.4x8+2.9y1+2.1y2+1.5y33,2,1,8,....,2,1,,0,0100384706153403221131002807361514232201010018070615041302211jiyjxiyxxxxxxxxyxxxxxxxxyxxxxxxxx为整数案例九：一维下料问题考虑实际生产情况简化模型（去掉料头较大的方案）minz=0x1+0.1x2+0.2x3+0.3x4+2.9y1+2.1y2+1.5y33,2,1,8,....,2,1,,0,0100340322113100242322010100141302211jiyjxiyxxxxyxxxxyxxxx为整数案例九：一维下料问题利用WinSQB求解：LinearandIntegerProgramming案例九：一维下料问题填入变量及约束的系数案例九：一维下料问题求解得案例九：一维下料问题根据计算得到：X1=30，X2=10，X3=0，X4=50，Y1=Y2=Y3=0也就是说采用第一种下料方式裁切30根，采用第二种方式裁剪10根采用第四种方式裁剪50根，其他的方式不采用。这个时候的废料最少为16米。而且没有多余的规格钢。这是比较好的一个解。案例九：一维下料问题利用WinSQB求解：LinearandIntegerProgramming不简化案例九：一维下料问题案例九：一维下料问题填入变量及约束的系数求解得案例九：一维下料问题X1=30，X2=10，X3=0，X4=50，Y1=Y2=Y3=0计算得到的结果与简化后的一样。是否所有的问题简化与不简化都一样？案例九：一维下料问题讨论许多书籍在介绍套裁方案时，跟我们一样为了简单通常会将其中的料头较大的方案去掉，如在本例中去掉方案6、方案7、方案8，从而建立只有4种方案的模型。事实上，这种仅仅根据料头的多少来确定套裁方案的解题方法存在较大的不足，首先是不能判定到底选几种方案作为建模时的方案，这本身没有一个标准，选4种方案可以，那5种方案又如何?实在难以确定。案例九：一维下料问题讨论再就是通过料头大小来放弃一些方案，这种方式并不能与现实中完全吻合，假设我们放弃方案5，但在现实生活中，如果我们对于2.9m这种规格的材料需求特别大，而对于其它两种规格的材料需求量却较小，那么当2.9m规格材料满足需求时，其它两种规格的材料就已经超过了需求，从而使多余的部分成为料头弃掉，而未能实现真正的用料最省。案例九：一维下料问题如果现有原料钢管每根19米，客户需求4米的钢管50根，6米的钢管20根，以及8米的15根，又该如何下料最节省？如何尽可能满足顾客需求？合理切割模式：余料应小于客户需要钢管的最小尺寸案例九：一维下料问题可行切割模式如下：模式4米钢管根数6米钢管根数8米钢管根数余料（米）14003231013201341203511116030370023案例九：一维下料问题为满足客户需要，按照哪种模式，每种模式切割多少根原料钢管，最为节省？标准1：原料钢管剩余总余量最少标准2：所用原料钢管总根数最少案例九：一维下料问题标准1：原料钢管剩余总余量最少决策变量xi～按第i种模式切割的原料钢管根数（i=1，2…7）目标:minz=3x1+x2+3x3+3x4+x5+x6+3x7为整数xixxxxxxxxxxxx157253206354225054322314案例九：一维下料问题采用软件计算：POMSoftwareLibrary案例九：一维下料问题选择：LinearProgramming案例九：一维下料问题选择：LinearProgramming案例九：一维下料问题标准1：原料钢管剩余总余量最少最优解：x2=12,x5=15,其余为0；最优值：27。按模式2切割12根,按模式5切割15根，余料=12*1+15*1=27米案例九：一维下料问题标准2：所用原料钢管总根数最少当余料没有用处时，通常以总根数最少为目标目标:minz=x1+x2+x3+x4+x5+x6+x7为整数xixxxxxxxxxxxx157253206354225054322314案例九：一维下料问题利用WinSQB求解：LinearandIntegerProgramming求解得案例九：一维下料问题最优解：x2=15,x5=5,x7=5,其余为0；最优值：25根。按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料=15*1+5*1+5*3=35米切割根数余料（米）目标12727目标22535当余料没有用处时，通常以总根数最少为目标案例九：一维下料问题标准2：所用原料钢管总根数最少考虑多余的规格钢也为废料时目标:minz=x1+x2+x3+x4+x5+x6+x7+4y1+6y2+8y3为整数xiyxxxyxxxxyxxxxx153725320263542250154322314案例九：一维下料问题标准2：所用原料钢管总根数最少案例九：一维下料问题标准2：所用原料钢管总根数最少案例九：一维下料问题案例九：一维下料问题标准2：所用原料钢管总根数最少案例九：一维下料问题案例九：一维下料问题小结一维下料问题的求解，答案比较活泛。尽管在所需原材料总根数上答案一致，但在施工方案上却可以大相径庭。通常，在求解小规模问题时利用手工演算，也可以找到全部解，而通常实际问题只需找到一个解即可。案例九：一维下料问题问题的提出某地有三个有色金属矿A1,A2,A3,生产同一种金属矿石,A1矿的年产量为100万吨,A2矿为80万吨,A3矿为50万吨。矿石全部供应四个冶炼厂:B1厂的全部需求量为50万吨,B2厂为70万吨,B3厂为80万吨,B4厂为30万吨。总产量恰好等于总需求量，运价已知，如表所示。问：如何安排运输，使各矿山的矿石运到各冶炼厂满足各厂的需要，且总运输费用最小。案例十：产销平衡问题问题的提出案例十：产销平衡问题冶炼厂矿山B1B2B3B4A11.520.33A270.81.42A31.20.322.5最小元素法求解案例十：产销平衡问题销地产地B1B2B3B4产量A11.520.33100A270.81.4280A31.20.322.550需求量50708030230表中最小元素是C13=0.3,C32=0.3,令x13=min{a1,b3}=min{80,100}=80,将80填在C13的下方,表示A1供应80万吨到B3,在x23,x33的位置上分别打“×”,表示B3已满足需要。案例十：产销平衡问题销地产地B1B2B3B4产量A11.5[20]2[×]0.3[80]3[×]100A27[30]0.8[20]1.4[×]2[30]80A31.2[×]0.3[50]2[×]2.5[×]50需求量50708