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