数学建模：线性规划问题(超全).ppt

线性规划问题的提出 线性规划的基本概念 线性规划的数学模型 线性规划问题的标准形式,第一节 线性规划问题 及其数学模型,问题的提出,例: 生产计划问题,决策变量（Decision variables） 目标函数（Objective function） 约束条件（Constraint conditions） 可行域（Feasible region) 最优解（Optimal solution),基本概念,问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。,它是决策变量的函数,指决策变量取值时受到的各种资源条件的限制，通常表达为含决策变量的等式或不等式。,满足约束条件的决策变量的取值范围,可行域中使目标函数达到最优的决策变量的值,是问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。,第1步 -确定决策变量,设 I的产量 II的产量 利润,第2步 -定义目标函数,Max Z = x1 + x2,Max Z = 2 x1 + 3 x2,第2步 -定义目标函数,第3步 -表示约束条件,x1 + 2 x2 8 4 x1 16 4 x2 12 x1、 x2 0,该计划的数学模型,目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,x1,x2,线性规划问题的共同特征,一组决策变量X表示一个方案,一般X大于等于零。 约束条件是线性等式或不等式。 目标函数是线性的。 求目标函数最大化或最小化,线性规划模型的一般形式,线性规划问题的标准形式,标准形式为:,目标函数最大 约束条件等式 决策变量非负,简写为,用矩阵表示,C价值向量 b资源向量 X决策变量向量,min Z=CX 等价于 max Z = -CX “” 约束：加入非负松驰变量,一般线性规划问题的标准化,例：,目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,min Z=CX 等价于 max Z = -CX “” 约束：加入非负松驰变量,一般线性规划问题的标准形化,例：,“” 约束： 减去非负剩余变量；,Max,例 ：,可正可负（即无约束）；,解 ：标准形为,线性规划模型举例,(一) 运输问题 (二) 布局问题 (三) 分派问题 (四) 生产计划问题 (五) 合理下料问题,线性规划模型的条件,（1）要求解问题的目标函数能用数值指标来反映，且为线性函数； （2）存在着多种方案； （3）要求达到的目标是在一定约束条件下实现的，这些约束条件可用线性等式或不等式来描述。,(一) 运输问题,设某种物资有m个产地，A1，A2，A m；联合供应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)；,设xij表示由产地Ai运往销地Bj的物资 数(i=1,2, ,m;j=1,2, ,n)。 那么，上述运输问题的数学模型为： 求一组变量xij(i=1,2, ,m;j=1,2, ,n) 的值, 使它满足,即,(一) 运输问题,()产销平衡,约束条件,产地Ai发到各销地的发量 总和应等于Ai的产量,各产地发到销地Bj的发量 总和应等于Bj的销量,调运量不能为负数0,()产销平衡的模型,约束条件,产地Ai发到各销地的发量 总和应等于Ai的产量,各产地发到销地Bj的发量 总和应等于Bj的销量,调运量不能为负数0,()产销平衡的模型,()产销平衡的模型,约束条件,()产销平衡的模型,()产销不平衡产大于销,(一) 运输问题,调运量不能为负数,()产销不平衡产大于销的模型,产地Ai发到各销地的发量 总和不超过Ai的产量,各产地发到销地Bj的发量 总和应等于Bi的销量,（二）布局问题,作物布局 在n块地上种植m种作物，已知各块土地 亩数、各种作物计划播种面积及各种作 物在各块的单产（每亩的产量）如表 （与运输问题相似）， 问：如何合理安排种植计划，才使总产量最多。,产量（吨）,B1 B2 Bn,A1 A2 Am 销量（吨）,C11 C12 C1n C21 C22 C2n Cm1 Cm2 Cmn b1 b2 bn,a1 a2 am,（二）布局问题,n块土地,每亩的产量,m种农作物,总产量最多,方法与运输问题类似,(三）分派问题,(完成全部工作的总工时最少）,(三）分派问题,分派问题的模型,每件工作只分派一人去做,每人只做一件工作,每人对每件工作只有 做与不做两种情况,(四）生产组织与计划问题,某工厂用机床 加工 种零件。在一个生产周期， 各机床只能工作的机时、工厂必须完成各零件加工数、各机床加工每个零件的时间（单位：机时个）和加工每个零件的成本（单位：元个）如表1及表2所示。 问：在这个生产周期，怎样安排各机床的生产任务，才能既完成加工任务，又使总的加工成本最低。,() 总的加工成本最低,(四）生产组织与计划问题,表1 ：加工每个零件的时间,() 总的加工成本最低,(四）生产组织与计划问题,表 2：加工每个零件的成本,() 总的加工成本最低,(四）生产组织与计划问题,求一组变量 的值,使它满足,() 总的加工成本最低,(四）生产组织与计划问题,(加工零件个数不能为负数、分数）,(机床 加工各零件总机时不能超过 能工作机时）,(各机床加工零件 的总数不能少于 需要数）,() 总加工成本最低的模型,(四）生产组织与计划问题,() 总加工成本最低的模型,(四）生产组织与计划问题,(四）生产组织与计划问题,() 生产存储问题,一是各个月的正常和加班的允许工时； 二是满足交货要求。,(四）生产组织与计划问题,() 生产存储问题,该生产存储问题的线性规划模型为,目标函数,盈利总额=生产的 5 种产品销售价 成本和库存费用,(四）生产组织与计划问题,一是各个月的正常和加班的允许工时； 二是满足交货要求。,设用某原材料(条材或板材)下零件 的毛坯.根据过去经验 在一件原材料上有 种不同 的下料方式,每种下料方式可得各种毛 坯个数及每种零件需要量如下表所示。 问：应怎样安排下料方式，使得既 能满足需要，用的原材料又最少。,(五)合理下料问题,下 料 方 式,零件 名称,各方式下的零件个数,B1 B2 Bn,A1 A2 Am,C11 C12 C1n C21 C22 C2n Cm1 Cm2 Cmn,零件 需要量,a1 a2 am,(五)合理下料问题,解： 设用 种方式下料的原材料数 为 （j=1,2,n)， 则这一问题的数学模型为：,(五)合理下料问题,所用原材料数量最少,（所下的 Ai 零件总数不能少于 ）,（各种方式下料的原材料数不能是负数、分数）,约束条件,目标函数,(五)合理下料问题,