筹学PPT第二章线性规.ppt
2023/9/28,第二章 线性规划（Linear Programming）,第一节 线性规划的模型与图解法 第二节 单纯形法 第三节 对偶问题与灵敏度分析 第四节 运输问题 第五节 线性整数规划,2023/9/28,运筹学,第一节 线性规划的模型与图解法一、线性规划问题及其数学模型,在生产管理和经营活动中经常需要解决：如何合理地利用有限的资源，以得到最大的效益。,2023/9/28,运筹学,例1 某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源。现将有关数据列表如下：试拟订使总收入最大的生产方案。,2023/9/28,运筹学,线性规划模型的三要素,3.约束条件：为实现优化目标需受到的限制，用决策变量的等式或不 等式表示；,1.决策变量：需决策的量，即待求的未知数；,2.目标函数：需优化的量，即欲达的目标，用决 策变量的表达式表示；,2023/9/28,运筹学,目标函数：总收入，记为z,则z=7x1+12x2，为体现对其 追求极大化，在z 的前面冠以极大号Max；,决策变量：甲、乙产品的计划产量，记为；,在本例中,约束条件：分别来自资源煤、电、油限量的约束，和产 量非负的约束，表示为,2023/9/28,运筹学,解：设安排甲、乙产量分别 为,总收入为，则模型为：,2023/9/28,运筹学,例2 某市今年要兴建大量住宅,已知有三种住宅体系可以大量兴建，各体系资源用量及今年供应量见下表：要求在充分利用各种资源条件下使建造住宅的总面积为最大(即求安排各住宅多少m2)，求建造方案。,2023/9/28,运筹学,解:设今年计划修建砖混、壁板、大模住宅各为 x1,x2,x3 m2,z为总面积,则本问题的数学模型为:,前苏联的尼古拉也夫斯克城住宅兴建计划采用了上述模型，共用了12个变量，10个约束条件。,2023/9/28,运筹学,练习：某畜牧厂每日要为牲畜购买饲料以使其获取A、B、C、D四种养分。市场上可选择的饲料有M、N两种。有关数据如下：试决定买M与N二种饲料各多少公斤而使支出的总费用为最少？,饲料,2023/9/28,运筹学,解：设购买M、N饲料各为，则,2023/9/28,运筹学,线性规划模型的一般形式：（以MAX型、约束为例）,决策变量：目标函数：约束条件：,2023/9/28,运筹学,则模型可表示为,模型一般式的矩阵形式,记,LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1)428.0000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 24.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)84.000000 0.000000 3)0.000000 1.360000 4)0.000000 0.520000 NO.ITERATIONS=2,2023/9/28,运筹学,2023/9/28,运筹学,回顾例1的模型,其中 表示决策变量的向量；表示产品的价格向量；表示资源限制向量；表示产品对资源的单耗系数矩阵。,2023/9/28,运筹学,一般地 称为决策变量向量，称为价格系数向量,称为技术系数矩阵,称为资源限制向量。,2023/9/28,运筹学,线性规划应用举例,例1（下料问题）某工厂要做100套钢架，每套用长为2.9 m,2.1 m,1.5 m的圆钢各一根。已知原料每根长7.4 m，问：应如何下料，可使所用原料最省？,2023/9/28,运筹学,例1（下料问题）某工厂要做100套钢架，每套用长为2.9 m,2.1 m,1.5 m的圆钢各一根。已知原料每根长7.4 m，问：应如何下料，可使所用原料最省？,2,0,1,0.1,1,2,0,0.3,1,1,1,0.9,1,0,3,0,0,3,0,1.1,0,2,2,0.2,0,1,3,0.8,0,0,4,1.4,2023/9/28,运筹学,2x1+x2+x3+x4=100 2x2+x3+3x5+2x6+x7=100 x1+x3+3x4+2x6+3x7+4x8=100 x1,x2,x3,x4,x5,x6,x7,x8 0,设 x1,x2,x3,x4,x5,x6,x7,x8 分别为上述8种方案下料的原材料根数，建立如下的LP模型：,最优解为：x1=10,x2=50,x3=0,x4=30,x5=0,x6=0,x7=0,x8=0,min Z=x1+x2+x3+x4+x5+x6+x7+x8,s.t.,2023/9/28,运筹学,案例1 超级食品公司的广告混合问题,分析：（1）决策变量的设置,令x1、x2、x3分别为三种媒介的广告数量；,（2）目标函数：广告总受众量（千人）最大,（3）约束条件,最优解：X=(0,20,10)T,2023/9/28,运筹学,案例2 控制大气污染,分析：（1）决策变量的设置,令x11、x12、x13分别为鼓风炉的各种将污方法所实施的比例；x21、x22、x23分别为反射炉的各种将污方法所实施的比例；,（2）目标函数：总成本最低,（3）约束条件,最优解：,2023/9/28,运筹学,二、线性规划模型的图解法,图解法是用画图的方式求解线性规划的一种方法。它虽然只能用于解二维（两个变量）的问题，但其主要作用并不在于求解，而是在于能够直观地说明线性规划解的一些重要性质。,2023/9/28,运筹学,1.图解法的步骤,（1）做约束的图形 先做非负约束的图形；再做资源约束的图形。,以例1为例，其约束为,2023/9/28,运筹学,问题：不等式的几何意义是什么？怎样做图？,2023/9/28,运筹学,（1）做约束的图形 先做非负约束的图形；再做资源约束的图形。以例1为例，其约束为,各约束的公共部分即模型的约束，称可行域。,1.图解法的步骤,2023/9/28,运筹学,（2）做目标的图形,对于目标函数任给 二不同的值，便可做出相应的二直线，用虚线表示。以例1为例，其目标为，分别令，做出相应的二直线，便可看出 增大的方向。,2023/9/28,运筹学,（3）求出最优解 将目标直线向使目标 优化的方向移，直至可行域的边界为止，这时其与可行域的“切”点 即最优解。如在例1中，是可行域的一个角点，经求解交出 的二约束直线联立的方程可解得,2023/9/28,运筹学,由图解法的结果得到例1的最优解，还可将其代入目标函数求得相应的最优目标值。说明当甲产量安排 20 个单位，乙产量安排 24 个单位时，可获得最大的收入 428。,2023/9/28,运筹学,练习：用图解法求解下面的线性规划。,2023/9/28,运筹学,问题：在上两例中,多边形，而且是“凸”形的多边形。,最优解在什么位置获得？,在边界，而且是在某个顶点获得。,线性规划的可行域是一个什么形状？,2023/9/28,运筹学,2.由图解法得到线性规划解的一些特性,（1）线性规划的约束集（即可行域）是一个凸多 面体。,凸多面体是凸集的一种。所谓凸集是指：集中任两点的连线仍属此集。试判断下面的图形是否凸集：,凸集中的“极点”，又称顶点或角点，是指它属于凸集，但不能表示成集中某二点连线的内点。如多边形的顶点。,2023/9/28,运筹学,（2）线性规划的最优解（若存在的话）必能在可行域的角点获得。,因为，由图解法可知，只有当目标直线平移到边界时，才能使目标 z 达到最大限度的优化。,问题：本性质有何重要意义？,它使得在可行域中寻优的工作由“无限”上升为“有 限”，从而为线性规划的算法设计提供了重要基础。,2023/9/28,运筹学,（3）线性规划解的几种情形,唯一最优解,多重最优解,无解,无有限最优解（无界解）,
