线性规划建模举例

线性规划模型举例继续返回线性规划应用举例上页下页返回一、使用线性规划方法处理实际问题必须具备的条件(建模条件)：1)优化条件---问题的目标有极大化或极小化的要求,而且能用决策变量的线性函数来表示。2)选择条件---有多种可供选择的可行方案，以便从中选取最优方案。上页下页返回3）限制条件---达到目标的条件是有一定限制的（比如，资源的供应量有限度等），而且这些限制可以用决策变量的线性等式或线性不等式表示出来。此外，描述问题的决策变量相互之间应有一定的联系，有可能建立数学关系，即这些变量之间是内部相关的。上页下页返回二、建模步骤：第一步：设置要求解的决策变量。决策变量选取得当，不仅能顺利地建立模型而且能方便地求解，否则很可能事倍功半。第二步：找出所有的限制，即约束条件，并用决策变量的线性方程或线性不等式来表示。当限制条件多，背景比较复杂时，可以采用图示或表格形式列出所有的已知数据和信息，以避免“遗漏”或“重复”所造成的错误。上页下页返回第三步：明确目标要求，并用决策变量的线性函数来表示，确定对函数是取极大还是取极小的要求。决策变量的非负要求可以根据问题的实际意义加以确定。上页下页返回线性规划模型举例(一)运输问题(二)布局问题(三)分派问题(四)生产计划问题(五)合理下料问题上页下页返回(一)运输问题设某种物资有m个产地，A1，A2，…，Am；联合供应n个销地：B1，B2，…，Bn。各产地产量（单位：吨），各销地销量（单位：吨），各产地至各销地单位运价（单位：元／吨）如下表所示。应如何调运，才使总运费最少？上页下页返回表中：ai表示产地Ai的产量(i=1，2，…，m)；bj表示销地Bj的销量(j=1，2，…，n)；cij表示AiBj间的单位运价（元／吨）(i=1，2，…，m;j=1，2，…，n)；销地产地产量(吨)B1B2…BnA1A2┇Am销量（吨）C11C12…C1nC21C22…C2n┇┇…┇Cm1Cm2…Cmnb1b2…bna1a2┇am上页下页返回设xij表示由产地Ai运往销地Bj的物资数(i=1,2,…,m;j=1,2,…,n)。那么，上述运输问题的数学模型为：求一组变量xij(i=1,2,…,m;j=1,2,…,n)的值,使它满足minjjiba11即(一)运输问题(Ⅰ)产销平衡(Ⅰ)产销平衡(Ⅱ)产销不平衡上页下页返回约束条件产地Ai发到各销地的发量总和应等于ai的产量各产地发到销地Bj的发量总和应等于bj的销量调运量不能为负数0(Ⅰ)产销平衡的模型上页下页返回约束条件产地Ai发到各销地的发量总和应等于Ai的产量各产地发到销地Bj的发量总和应等于Bj的销量调运量不能为负数0(Ⅰ)产销平衡的模型njmixnjbxmiaxijijiijmijnj,,1;,,2,10,,2,1,,2,111上页下页返回约束条件njmixnjbxmiaxijijiijmijnj,,1;,,2,10,,2,1,,2,111njmiijijxcs11min。的值最小目标函数(Ⅰ)产销平衡的模型上页下页返回m11injjiba即这一问题的数学模型应为：求一组变量的值,使它满足njmixij,,2,1;,,2,1(Ⅱ)产销不平衡—产大于销(一)运输问题1、物资供大于求2、生产的物资没有全部销售出去，因此：产地产生库存凡参加运输的物资均可以销售出去上页下页返回约束条件njmixnjbxmiaxijjijiijminj,,2,1;,,2,10,,2,1,,2,111产地Ai发到各销地的发量总和不超过Ai的产量各产地发到销地Bj的发量总和应等于Bi的销量调运量不能为负数njmiijijxcs11min目标函数(Ⅱ)产销不平衡—产大于销的模型上页下页返回（二）布局问题•作物布局在n块地上种植m种作物，已知各块土地亩数、各种作物计划播种面积及各种作物在各块的单产（每亩的产量）如表—（与运输问题相似），问：如何合理安排种植计划，才使总产量最多。上页下页返回（二）布局问题销地产地产量（吨）B1B2…BnA1A2┇Am销量（吨）C11C12…C1nC21C22…C2n┇┇…┇Cm1Cm2…Cmnb1b2…bna1a2┇amn块土地m种农作物总产量最多方法与运输问题类似每亩的产量上页下页返回(三）生产组织与计划问题总的加工成本最低上页下页返回某工厂用机床加工种零件。在一个生产周期，各机床只能工作的机时、工厂必须完成各零件加工数、各机床加工每个零件的时间（单位：机时／个）和加工每个零件的成本（单位：元／个）如表1及表2所示。问：在这个生产周期，怎样安排各机床的生产任务，才能既完成加工任务，又使总的加工成本最低。mAAA,,,21nBBB,,,21(三）生产组织与计划问题上页下页返回零件机床在一周期能工作机时B1B2…BnA1A2┇Am必须加工零件数C11C12…C1nC21C22…C2n┇┇…┇Cm1Cm2…Cmnb1b2…bna1a2┇am表1：加工每个零件的时间(三）生产组织与计划问题上页下页返回表2：加工每个零件的成本零件机床B1B2…BnA1A2┇Amd11d12…d1nd21d22…d2n┇┇…┇dm1dm2…dmn(三）生产组织与计划问题上页下页返回求一组变量的值,使它满足njmixij,,2,1;,,2,1解：设为机床在下一生产周期加工零件的个数。这一问题的数学模型为：njmi,,2,1;,,2,1ijxiAjBnjmiijijxds11的值最小。目标函数(三）生产组织与计划问题上页下页返回约束条件njmixnjbxmiaxcijijiijijmijnj,,2,1,,,2,1,0,,2,1,,2,111整数(加工零件个数不能为负数、分数）(机床加工各零件总机时不能超过能工作机时）iAiA(各机床加工零件的总数不能少于需要数）jBjB(三）生产组织与计划问题总的加工成本最低的模型上页下页返回约束条件njmixnjbxmiaxcijiijiijijninj,,2,1,,,2,1,0,,2,1,,2,111整数(三）生产组织与计划问题总的加工成本最低的模型njmiijijxds11min目标函数上页下页返回设用某原材料(条材或板材)下零件的毛坯.根据过去经验在一件原材料上有种不同的下料方式,每种下料方式可得各种毛坯个数及每种零件需要量如下表所示。问：应怎样安排下料方式，使得既能满足需要，用的原材料又最少。mAAA,,,21nBBB,,,21(四)合理下料问题上页下页返回例1-9某厂接受了一批加工定货，客户要求加工100套钢架，每套由长2.9米、2.1米和1.5米的圆钢各一根组成。现在仅有一批长7.4米的棒料毛坯，问应如何下料，使所用的棒料根数最少？上页下页返回解决这类问题一般有两个步骤：步骤一、按照一定的思路设法列出所有的排料方案（也称下料方案或排料图），当方案很多，甚至无法一一列出时，通常应先确定一些筛选原则，把明显不合理的方案删除，仅仅考虑剩余的为数不太多的方案；步骤二、设xi表示按第ｉ种方案下料的棒料根数（或板材块数）i=1,2,…,n，按照问题的要求建立LP模型。上页下页返回例1-9某厂接受了一批加工定货，客户要求加工100套钢架，每套由长2.9米、2.1米和1.5米的圆钢各一根组成。现在仅有一批长7.4米的棒料毛坯，问应如何下料，使所用的棒料根数最少？上页下页返回最简单的处理方法：从一根棒料上截取2.9米、2.1米和1.5米的棒料各一根，正好配成一套钢架，100套钢架总共需要100根棒料毛坯。每根棒料毛坯剩下0.9米的料头,100根毛坯总共剩90米料头。——这是最好的办法吗？合理套裁肯定会有更好的效果。先设法列出所有的下料方案，思路如图。上页下页返回排列下料方案思路图原料（7.4米长棒料）1.截规格1(2.9米)2.截规格2(2.1米)截规格3(1.5米)最多截取根数n1=2n1=1最多截取根数n2=3n2=2n2=1最多截取根数n3=45.8余料1.6用料2.9余料4.5用料6.3余料1.1用料4.2余料3.2用料2.1余料5.3用料6.0余料1.4余料余料N够截规格2吗?N够截规格3吗?(2.1米)(1.5米)YYn2=2用料4.2余料0.3n2=1用料2.1余料2.4n2=0余料4.5n3=2用料3.0余料0.2n3=3用料4.5余料0.8余料N够截规格3吗?(1.5米)Yn3=1用料1.5余料0.1n3=0用料0余料0.3n3=1用料1.5余料0.9n3=3用料4.5余料0方案I截201余料0.1方案II(120)余料0.3方案Ⅲ(111)余料0.9方案Ⅳ(103)余料0方案Ⅴ(030)余料1.1方案Ⅵ(022)余料0.2方案Ⅶ(013)余料0.8方案Ⅷ(004)余料1.4上页下页返回设xi为按第i种方案下料的棒料根数，建立LP模型如下：0,,,100432031011000123012010000001112..82187654321876543218765432181xxxxxxxxxxxxxxxxxxxxxxxxxxxtsxMinZii上页下页返回(五）分派问题设有n件工作分派给n人去做，每人只做一件工作且每件工作只分派一人去做。设Ai完成Bj的工时为。问：应如何分派才使完成全部工作的总工时最少。nBBB,,,21nAAA,,,21njicij,,2,1,上页下页返回解：设为Bj分派给人Ai情况：Bj分派给Ai时，；不分派给Ai时，。那末这一问题的数学模型为：ijxnjiXij,,2,1,0njixij,,2,1,求一组变量的值，使目标函数的值最小。nimjijijxcs11(完成全部工作的总工时最少）(五）分派问题1jiX上页下页返回约束条件njixnixnjxijijijnjni,,2,1,10,,2,11,,2,1111或每件工作只分派一人去做每人只做一件工作每人对每件工作只有做与不做两种情况分派问题的模型nimjijijxcs11min目标函数上页下页返回线性规划模型