《线性规划建模举例》由会员分享，可在线阅读，更多相关《线性规划建模举例（34页珍藏版）》请在金锄头文库上搜索。
1、vv 线性规划模型举例线性规划模型举例继续继续返回返回线性规划应用举例线性规划应用举例上页上页下页下页返回返回一、使用线性规划方法处理实际问题一、使用线性规划方法处理实际问题必须具备的条件必须具备的条件( (建模条件建模条件) )：n优化条件-问题的目标有极大化或极问题的目标有极大化或极 小化的要求小化的要求, ,而且能用决策变量的线性而且能用决策变量的线性函数来表示。函数来表示。 n选择条件-有多种可供选择的可行方有多种可供选择的可行方案，以便从中选取最优方案。案，以便从中选取最优方案。上页上页下页下页返回返回3）限制条件-达到目标的条件是有一定限制的（比如，资源的供应量有限度等） ，而且这
2、些限制可以用决策变量的线性 等式或线性不等式表示出来。此外，描述问题的决策变量相互之描述问题的决策变量相互之间应有一定的联系，有可能建立数学关间应有一定的联系，有可能建立数学关 系，即这些系，即这些变量之间是内部相关变量之间是内部相关的。的。上页上页下页下页返回返回二、建模步骤二、建模步骤： 第一步：设置要求解的决策变量第一步：设置要求解的决策变量。决策变决策变量选取得当，不仅能顺利地建立模型而且能量选取得当，不仅能顺利地建立模型而且能 方便地求解方便地求解，否则很可能事倍功半。，否则很可能事倍功半。 第二步：找出所有的限制第二步：找出所有的限制，即约束条件，即约束条件，并并用决策变量的线性方
3、程或线性不等式来表示用决策变量的线性方程或线性不等式来表示 。当限制条件多，背景比较复杂时，可以。当限制条件多，背景比较复杂时，可以采采 用图示或表格形式列出所有的已知数据和信用图示或表格形式列出所有的已知数据和信 息，以避免息，以避免“ “遗漏遗漏” ”或或“ “重复重复” ”所造成的错误。所造成的错误。 上页上页下页下页返回返回 第三步：明确目标要求，并用决策变量第三步：明确目标要求，并用决策变量的线性函数来表示，确定对函数是取极大的线性函数来表示，确定对函数是取极大 还是取极小的要求。还是取极小的要求。决策变量的非负要求可以根据问题的决策变量的非负要求可以根据问题的实际意义加以确定。实际
4、意义加以确定。上页上页下页下页返回返回线性规划模型举例(一) 运输问题 (二) 布局问题 (三) 分派问题 (四) 生产计划问题 (五) 合理下料问题上页上页下页下页返回返回(一) 运输问题设某种物资有m个产地，A1，A2，Am；联 合供应n个销地：B1，B2，Bn。各产地产量（单位：吨），各销地销量（单 位：吨），各产地至各销地单位运价（单位：元 吨）如下表所示。 应如何调运， 才使总运费最 少？上页上页下页下页返回返回表中：表中：a ai i表示产地表示产地A Ai i的产量的产量(i=1(i=1，2 2， ，m)m)；b bj j表示销地表示销地B Bj j的销量的销量(j=1(j=1，
5、2 2， ，n)n)；c cij ij表示表示A Ai iB Bj j间的单位运价（元吨）间的单位运价（元吨）(i=1(i=1，2 2， ，m; m; j=1 j=1，2 2， ，n)n)；单价（元吨）销地产地产量(吨) B1 B2 BnA1A2 Am销量（吨）C11 C12 C1nC21 C22 C2n Cm1 Cm2 Cmnb1 b2 bna1a2 am上页上页下页下页返回返回设设x xij ij表示由产地表示由产地A Ai i运往销地运往销地B Bj j的物资的物资 数数(i=1,2, (i=1,2, ,m;j=1,2, ,n),m;j=1,2, ,n)。那么，上述运输问题的数学模型为：
6、那么，上述运输问题的数学模型为：求一组变量求一组变量x xij ij(i (i=1,2, =1,2, ,m;j=1,2, ,n),m;j=1,2, ,n)的值的值, , 使它满足使它满足即(一) 运输问题()产销平衡 ()产销平衡 ()产销不平衡 上页上页下页下页返回返回约束条件产地Ai发到各销地的发量 总和应等于ai的产量各产地发到销地Bj的发量 总和应等于bj的销量调运量不能为负数0()()产销平衡的模型产销平衡的模型上页上页下页下页返回返回约束条件产地Ai发到各销地的发量 总和应等于Ai的产量各产地发到销地Bj的发量 总和应等于Bj的销量调运量不能为负数0()()产销平衡的模型产销平衡的
7、模型上页上页下页下页返回返回约束条件()()产销平衡的模型产销平衡的模型上页上页下页下页返回返回这一问题的数学模型应为： 求一组变量 的值,使它满足()产销不平衡产大于销(一) 运输问题1、物资供大于求 2、生产的物资没有全 部销售出去，因此： 产地产生库存 凡参加运输的物资均可以销售出去上页上页下页下页返回返回约束条件产地Ai发到各销地的发量 总和不超过Ai的产量各产地发到销地Bj的发量 总和应等于Bi的销量调运量不能为负数()()产销不平衡产销不平衡产大于销的模型产大于销的模型上页上页下页下页返回返回（二）布局问题作物布局在n块地上种植m种作物，已知各块土地亩数、各种作物计划播种面积及各种
8、作物在各块的单产（每亩的产量）如表 （与运输问题相似）， 问：如何合理安排种植计划，才使总 产量最多。 上页上页下页下页返回返回（二）布局问题单价（元吨）销地产地产量（吨 ）B1 B2 BnA1A2 Am销量（吨）C11 C12 C1nC21 C22 C2n Cm1 Cm2 Cmnb1 b2 bna1a2 amn n块土地块土地m m种种农作物农作物总产量最多总产量最多方法与运输方法与运输 问题类似问题类似每亩的产量每亩的产量上页上页下页下页返回返回(三）生产组织与计划问题总的加工成本最低上页上页下页下页返回返回某工厂用机床 加工种零件。在一个生产周期， 各机床只能工作的机时、工厂必须完成各
9、零件加工数、各机床加工每个零件的时间 （单位：机时个）和加工每个零件的成 本（单位：元个）如表1及表2所示。 问：在这个生产周期，怎样安排各机床的 生产任务，才能既完成加工任务，又使总 的加工成本最低。(三）生产组织与计划问题上页上页下页下页返回返回加工每个零件的时间零件机床在一周期能 工作机时B1 B2 BnA1A2 Am必须加工零件数C11 C12 C1nC21 C22 C2n Cm1 Cm2 Cmnb1 b2 bna1a2 am表1 ：加工每个零件的时间(三）生产组织与计划问题上页上页下页下页返回返回表 2：加工每个零件的成本加工每个零件的成本零件机床B1 B2 BnA1A2 Amd11
10、 d12 d1nd21 d22 d2n dm1 dm2 dmn(三）生产组织与计划问题上页上页下页下页返回返回求一组变量 的值,使它满足 解：设 为机床 在下一生产周期加工零件 的个数 。这一问题的数学模型为： (三）生产组织与计划问题上页上页下页下页返回返回约束条件(加工零件个数不能为负数、分数）(机床 加工各零件总机时不 能超过 能工作机时）(各机床加工零件 的总数不能少于需要数）(三）生产组织与计划问题总的加工成本最低的模型上页上页下页下页返回返回约束条件(三）生产组织与计划问题总的加工成本最低的模型目标函数上页上页下页下页返回返回设用某原材料(条材或板材)下零件 的毛坯.根据过去经验
11、在一件原材料上有 种不同 的下料方式,每种下料方式可得各种毛 坯个数及每种零件需要量如下表所示。 问：应怎样安排下料方式，使得既能满足需要，用的原材料又最少。(四)合理下料问题上页上页下页下页返回返回例1-9 某厂接受了一批加工定货 ，客户要求加工100套钢架，每套由长 2.9米、2.1米和1.5米的圆钢各一根组 成。现在仅有一批长7.4米的棒料毛坯，问应如何下料，使所用的棒料根数 最少？上页上页下页下页返回返回解决这类问题一般有两个步骤： z步骤一、按照一定的思路设法列出所有的排 料方案（也称下料方案或排料图），当方案 很多，甚至无法一一列出时，通常应先确定 一些筛选原则，把明显不合理的方案
12、删除， 仅仅考虑剩余的为数不太多的方案；z步骤二、设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米料头。这是最好的办
13、法吗？合理套裁肯定会有更好的效果。先设法列出所有的下料方案，思路如图。上页上页下页下页返回返回排列下料方案思路图上页上页下页下页返回返回设设x xi i为按第为按第i i种种方案下料的棒料根数方案下料的棒料根数， 建立LP模型如下：上页上页下页下页返回返回(五）分派问题设有n件工作 分派给n人 去做， 每人只做一件工作且每件工作只分 派一人去做。设Ai完成Bj的工时为。 问：应如何分派才使完成全部工作 的总工时最少。上页上页下页下页返回返回解：设 为Bj分派给人Ai情况：Bj分派给Ai时， ； 不分派给Ai时， 。那末这一问题的数学模型为：求一组变量 的值，使目标函数 的值最小。(完成全部工作的总工时最少）(五）分派问题上页上页下页下页返回返回约束条件每件工作只分派一人去做每人只做一件工作每人对每件工作只有做与不做两种情况分派问题的模型目标函数上页上页下页下页返回返回线性规划模型
