-线性规划建模举例

1、1-7线性规划建模举例 导读：就爱阅读网友为您分享以下“1-7线性规划建模举例”资讯，希望对您有所帮助，感谢您对的支持!线性规划应用举例线性规划模型举例继续返回一、使用线性规划方法处理实际问题 必须具备的条件(建模条件) 必须具备的条件(建模条件)：1) 优化条件-问题的目标有极大化或极 优化条件 问题的目标有极大化或极小化的要求, 小化的要求,而且能用决策变量的线性 函数来表示。 函数来表示。2) 选择条件 有多种可供选择的可行方 选择条件-有多种可供选择的可行方案，以便从中选取最优方案。 以便从中选取最优方案。上页 下页 返回3）限制条件-达到目标的条件是有一定限 ）限制条件 达到目标的条

2、件是有一定限 制的（比如， 资源的供应量有限度等）， 制的 （ 比如 ， 资源的供应量有限度等） 而且这些限制可以用决策变量的线性等 式或线性不等式表示出来。 式或线性不等式表示出来。 此外， 描述问题的决策变量相互之 此外 ， 间应有一定的联系， 间应有一定的联系 ， 有可能建立数学关 即这些变量之间是内部相关 变量之间是内部相关的 系，即这些变量之间是内部相关的。上页 下页 返回二、建模步骤： 建模步骤：第一步：设置要求解的决策变量。决策变量 第一步：设置要求解的决策变量。 选取得当， 选取得当，不仅能顺利地建立模型而且能方便 地求解，否则很可能事倍功半。 地求解，否则很可能事倍功半。 第

3、二步：找出所有的限制，即约束条件， 第二步：找出所有的限制，即约束条件，并 用决策变量的线性方程或线性不等式来表示。 用决策变量的线性方程或线性不等式来表示。 当限制条件多，背景比较复杂时，可以采用图 当限制条件多，背景比较复杂时，可以采用图 示或表格形式列出所有的已知数据和信息， 示或表格形式列出所有的已知数据和信息，以 避免“遗漏” 重复”所造成的错误。 避免“遗漏”或“重复”所造成的错误。上页 下页 返回第三步：明确目标要求，并用决策变量 第三步：明确目标要求， 的线性函数来表示， 的线性函数来表示 ， 确定对函数是取极大 还是取极小的要求。 还是取极小的要求。 决策变量的非负要求可以根

4、据问题的 实际意义加以确定。 实际意义加以确定。上页下页返回线性规划模型举例(一)运输问题 (二)布局问题 (三)分派问题 (四)生产计划问题 (五)合理下料问题上页下页返回(一) 运输问题设某种物资有m个产地， 设某种物资有m个产地，A1，A2，Am；联 ， 合供应n个销地： 合供应n个销地：B1，B2，Bn。 ， 各产地产量（单位： ），各销地销量 各销地销量（ 各产地产量（单位：吨），各销地销量（单 ），各产地至各销地单位运价 单位： 各产地至各销地单位运价（ 位：吨），各产地至各销地单位运价（单位：元 如下表所示。 吨）如下表所示。应如何调运， 应如何调运， 才使总运费最 少？上页下页

5、返回产 地销 地B1 C11 C21 Cm1 b1B2 C12 C22 Cm2 b2 Bn C1n C2n Cmn bn产量（ 产量（吨） a1 a2 amA1 A2 Am 销量（ 销量（吨）表中： 表示产地A 的产量(i=1， m)； 表中：ai表示产地Ai的产量(i=1，2， ，m)； bj表示销地Bj的销量(j=1，2， ，n)； 表示销地B 的销量(j=1， n)； cij表示AiBj间的单位运价（元吨）(i=1，2， ，m; 表示A 间的单位运价（ (i=1， j=1， j=1，2， ，n)； n)；上页 下页 返回(一) 运输问题()产销平衡 ()产销平衡即()产销平衡 ()产销平

6、衡 ()产销不平衡 ()产销不平衡na i= 1mi= j bj= 1设xij表示由产地Ai运往销地Bj的物资 表示由产地A 运往销地B ,n)。 数(i=1,2, ,m;j=1,2, ,n)。 那么，上述运输问题的数学模型为： 那么，上述运输问题的数学模型为： 求一组变量x 求一组变量xij(i=1,2, ,m;j=1,2, ,n) 的值, 的值, 使它满足上页 下页 返回()产销平衡的模型 ()产销平衡的模型产地A 产地Ai发到各销地的发量 总和应等于ai的产量 总和应等于a 约束条件 各产地发到销地B 各产地发到销地Bj的发量 发到销地 总和应等于b 总和应等于bj的销量 调运量不能为负

7、数 调运量不能为负数0 量不能为负数上页下页返回()产销平衡的模型 ()产销平衡的模型产地A 产地Ai发到各销地的发量 总和应等于A 总和应等于Ai的产量ij ix = aj= 1 mn约束条件x = bij各产地发到销地B 各产地发到销地Bj的发量 发到销地 总和应等于B 总和应等于Bj的销量(i =1,2,L m) ,xij 0 (i =12,L m j =1L n) , , ; , ,调运量不能为负数 调运量不能为负数0 量不能为负数上页 下页 返回i= 1j( j =1,2,L n) ,()产销平衡的模型 ()产销平衡的模型n m目 函 mn s = ijxij 的 最 标 数 i c

8、 值 小x = aij inj= 1 m(i =1,2,L m) , ( j =1,2,L n) ,1 1 j= i=约束条件x = bijxij 0 (i =12,L m j =1L n) , , ; , ,上页 下页 返回i= 1j(一) 运输问题()产销不平衡 产大于销 ()产销不平衡产大于销 产销不平衡m n 即 a j i j=1 b i= 1 这一问题的数学模型应为： 求一组变量xij(i =12 L m j =12 L n) , , , ; , , , 的值,使它满足上页下页返回()产销不平衡 ()产销不平衡产大于销的模型 产销不平衡产地A 产地Ai发到各销地的发量 目 函 标

9、数 mn s = i cijxij 总和不超过A 总和不超过Ai的产量 j= i= 1 1 产小于 n xij 销的模各产地发到销地m的发量 ai 各产地=12,L Bj i 发到销地B , , 发到销地 型呢 j= 1 总和应等于B 总和应等于Bi的销量 m 约束条件nmi= 1？j()x = bij( j =1,2,L n) ,xij 0(i =1,2,L m; j =1,2,L n) , ,上页 下页 返回调运量不能为负数 调运量不能为负数（二）布局问题 作物布局在n块地上种植m种作物，已知各块土地 亩数、各种作物计划播种面积及各种作 物在各块的单产（每亩的产量）如表 （与运输问题相似）

10、，问：如何合理安排种植计划，才使总 产量最多。上页 下页 返回（二）布局问题产 地 销 地n块土地B1 B2 Bn C1n C2n Cmn bn C11 C12 方法与运输 C问题类似 C22 21 Cm1 b1 Cm2 b2 产量（ 产量（吨） a1 a2 am种 农 作 物m mA1 A2 Am销量（ 销量（吨）上页下页返回(三）生产组织与计划问题总的加工成本最低上页下页返回(三）生产组织与计划问题1 2 , m 某工厂用机床 A, A ,L A 加工 B1, B2,L Bn种零件。在一个生产周期， , 种零件。在一个生产周期， 各机床只能工作的机时、 各机床只能工作的机时、工厂必须完成各

11、 零件加工数、 零件加工数、各机床加工每个零件的时间 单位：机时 （单位：机时个）和加工每个零件的成 单位： 如表1及表2 本（单位：元个）如表1及表2所示。 在这个生产周期， 问：在这个生产周期，怎样安排各机床的 生产任务，才能既完成加工任务， 生产任务，才能既完成加工任务，又使总 的加工成本最低。 的加工成本最低。上页下页返回(三）生产组织与计划问题机 床零 件B1 C11 C21 Cm1 b1B2 C12 C22 Cm2 b2 Bn C1n C2n Cmn bn在一周期能 工作机时 a1 a2 amA1 A2 Am 必须加工零件数表1 ：加工每个零件的时间上页 下页 返回(三）生产组织与

12、计划问题零 机 床 件B1 d11 d21 dm1B2 d12 d22 dm2 Bn d1n d2n dmnA1 A2 Am表 2：加工每个零件的成本 ：上页 下页 返回(三）生产组织与计划问题解：设xij 为机床 A 在下一生产周期加工 零件B 的个数 (i =12,L m j =12,L n) 。 , , ; , ,ij这一问题的数学模型为： 这一问题的数学模型为： 求一组变量 xij(i =12,L m j =12,L n) , , ; , , 的值, 的值,使它满足目 函 s = ijxij 的 最 标 数 d 值 小j= i= 1 1nm上页下页返回(三）生产组织与计划问题总的加工成

13、本最低的模型c x aij ij in1 j=(i =1,2,L m) , ( j =1,2,L n) ,B的总数不能少于 j(机床 A加工各零件总机时不 机床 i 能超过 A能工作机时） i能工作机时）ij约束条件x b1 i=mjxij 0 , 整 (i =12,L m j =12,L n) 数 , , , , ,(加工零件个数不能为负数、分数） 加工零件个数不能为负数、分数） 加工零件个数不能为负数上页 下页 返回(各机床加工零件 各机床加工零件 B 需要数） j 需要数）(三）生产组织与计划问题总的加工成本最低的模型目标函数mn s = d xij i ijj= i= 1 1nmc x

14、 aij ij inj= 1 n(i =1,2,L m) , ( j =1,2,L n) ,约束条件x bij ixij 0 , 整 (i =12,L m j =12,L n) 数 , , , , ,上页 下页 返回i= 1(四)合理下料问题设用某原材料(条材或板材) 设用某原材料(条材或板材)下零件 A, A ,L A 的毛坯.根据过去经验 1 2 , m 的毛坯. 在一件原材料上有 B, B2,L B 种不同 1 , n 的下料方式,每种下料方式可得各种毛 的下料方式, 坯个数及每种零件需要量如下表所示。 坯个数及每种零件需要量如下表所示。问：应怎样安排下料方式，使得既 应怎样安排下料方式

15、， 能满足需要，用的原材料又最少。 能满足需要，用的原材料又最少。上页下页返回(四)合理下料问题下 料 方 式零件B1 C11 C21 Cm1 B2 C12 C22 Cm2 Bn C1n C2n Cmn零件 名称需要量a1 a2 amA1 A2 Am上页下页返回解决这类问题一般有两个步骤： 解决这类问题一般有两个步骤：步骤一、按照一定的思路设法列出所有的排料 步骤一、按照一定的思路设法列出所有的排料 方案（也称下料方案或排料图） 当方案很多， 方案（也称下料方案或排料图），当方案很多， 甚至无法一一列出时，通常应先确定一些筛选 甚至无法一一列出时，通常应先确定一些筛选 原则，把明显不合理的方案

16、删除， 原则，把明显不合理的方案删除，仅仅考虑剩 余的为数不太多的方案； 余的为数不太多的方案； 步骤二、 表示按第 步骤二、设xi表示按第种方案下料的棒料根 数 （ 或板材块数） i=1,2,n， 按照问题的要 或板材块数 ） ， 求建立LP模型 模型。 求建立 模型上页 下页 返回某厂接受了一批加工定货， 例1-9 某厂接受了一批加工定货， 客户要求加工100套钢架 ， 每套由长 套钢架， 客户要求加工 套钢架 2.9米 、 2.1米和 米的圆钢各一根组 米和1.5米的圆钢各一根组 米 米和 现在仅有一批长7.4米的棒料毛坯 米的棒料毛坯， 成。现在仅有一批长 米的棒料毛坯， 问应如何下料

17、， 问应如何下料 ， 使所用的棒料根数最 少？上页下页返回最简单的处理方法： 最简单的处理方法：从一根棒料上截 米和1.5米的棒料各一根 取2.9米、2.1米和 米的棒料各一根， 米 米和 米的棒料各一根， 正好配成一套钢架， 套钢架总共需要 正好配成一套钢架，100套钢架总共需要 100根棒料毛坯。每根棒料毛坯剩下 根棒料毛坯。 根棒料毛坯 每根棒料毛坯剩下0.9 米的料头,100根毛坯总共剩 米料头。 根毛坯总共剩90米料头 米的料头 根毛坯总共剩 米料头。 这是最好的办法吗？ 这是最好的办法吗？ 这是最好的办法吗 合理套裁肯定会有更好的效果。 合理套裁肯定会有更好的效果。 肯定会有更好的

18、效果 先设法列出所有的下料方案，思路如图。 先设法列出所有的下料方案，思路如图。上页 下页 返回排列下料方案思路图原 料 （ 7 .4 米 长 棒 料 ） 1 .截 规 格 1 (2 .9 米 ) 2 .截 规 格 2 (2 .1 米 ) 截 规 格 3 (1 .5 米 )最 多 截 取 根 数 n1=2 5 .8 余 料 1 .6 n1=1 用 料 2 .9 余 料 4 .5最 多 截 取 根 数 n2= 3 用 料 6 .3 余 料 1 .1 n2=2 用 料 4 .2 余 料 3 .2 n2=1 用 料 2 .1 余 料 5 .3最多截取 根 数 n3=4 用 料 6 .0 余 料 1

19、.4余 料 N 够 截 规 格 2 吗 ? ( 2 .1 米 ) Y N余 料 够 截 规 格 3 吗 ? (1 .5 米 ) Yn2=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 .1 方 案 I 截 201 余 料 0 .1n3=0 用 料 0 余 料 0 .3 方 案 II (1 2 0 ) 余 料 0 .3n3=1 用 料 1 .5 余 料 0 .9 方 案 (111 ) 余 料 0 .9n3=3 用 料 4 .5 余 料 0 方 案 (1 0 3 ) 余 料 0 方 案 (0 3 0 ) 余 料 1.1 方 案 (0 2 2 ) 余 料 0 .2 方 案 (0 1 3 ) 余 料 0.8 方 案 (0 0 4 )上页下页余 料 1 .4返回设xi为按第i种方案下料的棒料根数， 为按第i种方案下料的棒料根数， 建立LP模型如下 模型如下： 建立 模型如下：MinZ = xii =1 82x1 + 1x2 + 1x3 + 1x4 + 0x5