运筹学课件1-7线性规划建模举例.ppt

《运筹学课件1-7线性规划建模举例.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线性规划模型举例继续返回线性规划应用举例一、使用线性规划方法处理实际问题必须具备的条件(建模条件)：优化条件---问题的目标有极大化或极小化的要求,而且能用决策变量的线性函数来表示。选择条件---有多种可供选择的可行方案，以便从中选取最优方案。3）限制条件---达到目标的条件是有一定限制的（比如，资源的供应量有限度等），而且这些限制可以用决策变量的线性等式或线性不等式表示出来。此外，描述问题的决策变量相互之间应有一定的联系，有可能建立数学关系，即这些变量之间是内部相关的。二、建模步骤：第一步：设置要求解的决策变量。决策变量选取得当，不仅能顺利地建立模型而且能方便地求解，否则很可能事倍功

2、半。第二步：找出所有的限制，即约束条件，并用决策变量的线性方程或线性不等式来表示。当限制条件多，背景比较复杂时，可以采用图示或表格形式列出所有的已知数据和信息，以避免“遗漏”或“重复”所造成的错误。第三步：明确目标要求，并用决策变量的线性函数来表示，确定对函数是取极大还是取极小的要求。决策变量的非负要求可以根据问题的实际意义加以确定。线性规划模型举例(一)运输问题(二)布局问题(三)分派问题(四)生产计划问题(五)合理下料问题(一)运输问题设某种物资有m个产地，A1，A2，…，Am；联合供应n个销地：B1，B2，…，Bn。各产地产量（单位：吨），各销地销量（单位：吨），各产地至各销地单

3、位运价（单位：元／吨）如下表所示。应如何调运，才使总运费最少？表中：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)的值,使它

4、满足即(一)运输问题(Ⅰ)产销平衡(Ⅰ)产销平衡(Ⅱ)产销不平衡约束条件产地Ai发到各销地的发量总和应等于ai的产量各产地发到销地Bj的发量总和应等于bj的销量调运量不能为负数0(Ⅰ)产销平衡的模型约束条件产地Ai发到各销地的发量总和应等于Ai的产量各产地发到销地Bj的发量总和应等于Bj的销量调运量不能为负数0(Ⅰ)产销平衡的模型约束条件(Ⅰ)产销平衡的模型这一问题的数学模型应为：求一组变量的值,使它满足(Ⅱ)产销不平衡—产大于销(一)运输问题约束条件产地Ai发到各销地的发量总和不超过Ai的产量各产地发到销地Bj的发量总和应等于Bi的销量调运量不能为负数(Ⅱ)产销不平衡—产大于销的模型产小

5、于销的模型呢？（二）布局问题作物布局在n块地上种植m种作物，已知各块土地亩数、各种作物计划播种面积及各种作物在各块的单产（每亩的产量）如表—（与运输问题相似），问：如何合理安排种植计划，才使总产量最多。（二）布局问题单价（元／吨）销地产地产量（吨）B1B2…BnA1A2┇Am销量（吨）C11C12…C1nC21C22…C2n┇┇…┇Cm1Cm2…Cmnb1b2…bna1a2┇amn块土地m种农作物总产量最多方法与运输问题类似每亩的产量(三）生产组织与计划问题总的加工成本最低某工厂用机床加工种零件。在一个生产周期，各机床只能工作的机时、工厂必须完成各零件加工数、各机床加工每个零件的时间（单位

6、：机时／个）和加工每个零件的成本（单位：元／个）如表1及表2所示。问：在这个生产周期，怎样安排各机床的生产任务，才能既完成加工任务，又使总的加工成本最低。(三）生产组织与计划问题加工每个零件的时间零件机床在一周期能工作机时B1B2…BnA1A2┇Am必须加工零件数C11C12…C1nC21C22…C2n┇┇…┇Cm1Cm2…Cmnb1b2…bna1a2┇am表1：加工每个零件的时间(三）生产组织与计划问题表2：加工每个零件的成本加工每个零件的成本零件机床B1B2…BnA1A2┇Amd11d12…d1nd21d22…d2n┇┇…┇dm1dm2…dmn(三）生产组织与计划问题求一组变量的值,使

7、它满足解：设为机床在下一生产周期加工零件的个数。这一问题的数学模型为：(三）生产组织与计划问题约束条件(加工零件个数不能为负数、分数）(机床加工各零件总机时不能超过能工作机时）(各机床加工零件的总数不能少于需要数）(三）生产组织与计划问题总的加工成本最低的模型约束条件(三）生产组织与计划问题总的加工成本最低的模型目标函数某厂接受了一批加工定货，客户要求加工100套钢架，每套由长2.9米、2.1米和1.5米的圆钢各一根组成