第二章线性规划ppt课件

3 运筹学的主要内容,线性规划 非线性规划 整数规划 多目标规划 动态规划 图与网络模型 存储论,排队论 对策论 决策分析 排序与统筹方法 随机规划 模糊规划 预测,1.2 运筹学的数学模型,模型的定义: 模型是一件实际事物或情况的代表或抽象。实际事物是A，若B能够真实地描述A，则称B为A的模型。,数学模型就是用字母、数字和运算符号将系统或过程的某些特征及相互关系表达出来，他试图定量地表示系统的各种关系，以便对系统和问题进行量化分析。,第2章 线性规划,线性规划问题 可行区域与基本可行解 单纯形方法 初始解 对偶性及对偶单纯形方法 灵敏度分析,2.1 线性规划问题,线性规划问题举例 线性规划模型,1 线性规划问题举例,生产计划问题 运输问题 营养配餐问题 资金使用问题,1 线性规划问题举例（一）,某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。已知条件如下表所示：,问题：工厂应如何安排生产可获得最大的总利润？,1 线性规划问题举例（一）,解：设生产两种产品的数量分别为x1,x2，总利润为z.,目标函数,约束条件,1 线性规划问题举例（二）,设要从甲地调出物资2000吨，从乙地调出物资600吨，从丙地调出物资500吨，分别供应给A地1700吨、B地1100吨、C地200吨、D地100吨。已知每吨运费如下表所示。,假定运费与运量成正比例，问怎样才能找到一个总运费最省的调拨计划？,2,3,2,1,3,4,1,600,500,1700,1100,200,100,2000,供应量,供应地,运价,需求量,需求地,21,25,7,15,51,51,37,15,43,38,26,17,1 线性规划问题举例（二）,1 线性规划问题举例（二）,用 (i=1,2,3; j=1,2,3,4)分别表示从甲乙丙三个产地运往A,B,C,D四个销地的物资数量。,1 线性规划问题举例（二）,1 线性规划问题举例（二）,简化表达式,1 线性规划问题举例（三）,假定一个成年人每天需要从食物中获得3000千卡的热量、55克蛋白质和800毫克的钙。市场情况见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小？,1 线性规划问题举例（三）,解：设xj为第j种食品每天的购入量，则配餐问题的线性规划模型为： min z=30x1+9x2 +6x3+3x4 s.t. 1000x1+800x2 +900x3+200x4 3000 50x1+ 60x2 + 20x3+ 10x4 55 400x1+200x2 +300x3+500x4 800 x1，x2 ， x3 ， x4 0,1 线性规划问题举例（四）,设有400万元资金，要求4年内使用完，若在一年内使用资金 万元，则可得到效益 万元，（效益不能再次使用），当年未使用的资金可存入银行，年利率为10%，试制定出资金的使用计划，以使4年资金效益之和最大。,1 线性规划问题举例（四）,1 线性规划问题举例（四）,线性规划问题的结构特征,都有一组决策变量； 都有一组约束条件，它们是线性等式或不等式； 都有一个确定的目标，这个目标可以表示成决策变量的线性函数，根据问题不同，有的要求实现极大化，有的要求实现极小化。,线性规划问题的本质：研究在一组线性约束下，一个线性函数的极值问题。,2 线性规划模型,一般形式 标准形式 形式转换,2 线性规划模型（一般形式）,目标函数,约束条件,2 线性规划模型（标准形式）,min z = c1 x1 + c2 x2 + + cn xn s.t. a11 x1 + a12 x2 + + a1n xn = b1 a21 x1 + a22 x2 + + a2n xn = b2 am1 x1 + am2 x2 + + amn xn = bm x1 ，x2 ， ，xn 0,目标函数,约束条件,2 线性规划模型（标准形式）,2 线性规划模型（标准形式）,用向量表示,用矩阵表示,2 线性规划模型（标准形式）,2 线性规划模型（标准形式）,标准形式的特点：,目标函数极小化,约束条件全部是等式,所有的变量都是非负的,2 线性规划模型（形式转换）,令xj= xj- xj，对模型中的进行变量代换。,目标函数为 max z=c1x1+c2x2+cnxn,令z=-z ,变为 min z= -c1x1- c2x2- -cnxn,约束条件为 a11x1+a12x2+a1nxnb1,加入非负变量xn+1，称为松弛变量，有 a11x1+a12x2+a1nxn+xn+1=b1,约束条件为 a11x1+a12x2+a1nxnb1,减去非负变量xn+1，称为剩余变量，有 a11x1+a12x2+a1nxn - xn+1=b1,变量xj无约束。,2 线性规划模型（形式转换）,例：将如下线性规划问题化成标准形式：,2.2 可行区域与基本可行解,基本概念 图解法求解两个变量的线性规划问题 可行区域的几何结构 基本可行解及线性规划的基本定理,1 基本概念,1 基本概念,对于标准的LP问题来说,2 图解法求解两个变量线性规划问题（1）,max z=x1+3x2 s.t. x1+x26 -x1+2x28 x1, x20,可行域,目标函数等值线,最优解,6,4,-8,6,0,x1,x2,最优解为x=(4/3,14/3)T,最优值z=4/3+14=46/3,2 图解法求解两个变量线性规划问题（2）,max z=3x1+3x2 s.t. x1+ x26 -x1+2x28 x1, x20,可行域,目标函数等值线,6,4,-8,6,0,x1,x2,最优解?,最优值?,2 图解法求解两个变量线性规划问题（3）,max z=3x1+3x2 s.t. -x1+2x28 x1, x20,可行域,目标函数等值线,4,-8,0,x1,x2,最优解?,最优值?,min z=3x1+3x2?,2 图解法求解两个变量线性规划问题（4）,max z=3x1+3x2 s.t. -x1+2x28 x1-2x2-9 x1, x20,可行域?,2 图解法求解两个变量线性规划问题,在边界，而且是在某个顶点获得。,多边形，而且是“凸”形的多边形。,线性规划的可行域是一个什么形状？,最优解(如果存在)在什么位置获得？,两变量线性规划问题解的性质,2 图解法求解两个变量线性规划问题,1）唯一解,2）多重最优解,3）无有限最优解,4）无可行解,求解线性规划问题可能出现哪些情况？,3 可行区域的几何结构,基本假设 凸集 可行域的凸性 问题,3 可行区域的几何结构（基本假设）,3 可行区域的几何结构（凸集）,3 可行区域的几何结构（凸集）,3 可行区域的几何结构（凸集）,3 可行区域的几何结构（凸集）,3 可行区域的几何结构（可行域的凸性）,定理2.2.2 任意多个凸集的交集还是凸集。,3 可行区域的几何结构（可行域的凸性）,3 可行区域的几何结构（问题）,4 基本可行解及线性规划的基本定理,定义 基本定理 结论 问题,4基本可行解及线性规划的基本定理（定义）,基(基阵)：设B是秩为m的约束矩阵ARmn中的一个m阶满秩子方阵，则称B为一个基（基阵）。,基向量：B中m个线性无关的列向量称为基向量。,基变量：变量x中与基向量对应的m个分量称为基变量.其余的分量称为非基变量。,基本解：令所有的非基变量取值为零得到的解。,基本可行解：既是基本解又是可行解。,可行基：基本可行解对应的基B。,目标函数,约束条件,基矩阵,右边常数,基变量,4基本可行解及线性规划的基本定理（定义）,基本解,基本可行解,可行基,4基本可行解及线性规划的基本定理（定义）,例：考虑如下线性规划问题，用图解法求解，并把它化成标准形式，且指出基、基解：,4基本可行解及线性规划的基本定理（定义）,0,x1,x2,4基本可行解及线性规划的基本定理（定义）,4基本可行解及线性规划的基本定理（定义）,0,x1,x2,（0，0）,（4，0）,（4，2）,（0，4）,（8，0）,4基本可行解及线性规划的基本定理（定理）,4基本可行解及线性规划的基本定理（结论）,线性规划问题的可行域是凸集。 基本可行解与可行域的顶点对应，可行域有有限多个顶点(基本可行解)。 最优解一定可以在某个顶点上(基本可行解)得到。,非可行解,可行解,基可行解,基解,最优解？,4基本可行解及线性规划的基本定理 （结论与问题）,4基本可行解及线性规划的基本定理（总结）,求解LP的基本思路,1、构造初始可行基； 2、求出一个基可行解（顶点）； 3、最优性检验：判断是否最优解； 4、基变换，转2。要保证目标函数值比原来更优。,2.3 单纯形方法,1947年由Dantzig提出，被称为20世纪最好的十个算法之一，是迄今为止解决线性规划问题的最成熟的方法。,2.3 单纯形方法,典式 基本定理 单纯形方法 单纯形表（单纯形方法的实现）,1 典式(定义),1 典式（定义）,1 典式（定义）,典式的特点：1、约束条件中含有一个单位矩阵； 2、目标函数中不含基变量。,1 典式（定义）,1 典式（例）,1 典式（定义）,问题：如何判断一个基本可行解是否为最优解呢？,典则形式的LP问题中，目标函数中的变量系数的符号，对于判断某一个基本可行解是不是最优解非常重要。,本例中 是什么？,典则形式的LP问题中，目标函数系数向量的负向量。,称为检验数向量.,2 基本定理,定理2.3.1,例如：,2 基本定理,例如：,2 基本定理,例如：,2 基本定理,定理2.3.4,对于任何非退化的线性规划问题，从任何基本可行解开始，经过有限多次迭代，或者得到一个基本可行解，或者作出该线性规划问题无界的判断。,3 单纯形方法,Step 1 将线性规划问题化成典式,求出各个非基变量的检验数。 Step 2 判断所有非基变量的检验数是否非正,若是,则结束；否则转step 3。 Step 3 选取一个检验数大于零的非基变量为进基变量； Step 4 若进基变量所对应的约束条件系数全为非正数,则原问题无界,结束；否则,按最小比值原则确定出基变量； Step 5 进行迭代(用方程组的初等行变换法确定新的基对应的典式及检验数),转step 2。,4 单纯形表,例1 求解LP问题,x1 x2 x3 x4 x5,RHS,x1 x2 x3 x4 x5,RHS,检验数,转轴元, 最优解：x*=(6.5, 2.5, 0.5, 0, 0)T,最优值：z*= -1.5,例2：,解LP问题,4 单纯形表,x1 x2 x3 x4 x5, 此问题无界,RHS,例3：,解LP问题,4 单纯形表,x1 x2 x3 x4 x5, 此问题有多解。,RHS,2.4 初始解（两阶段法）,问题：线性规划 问题化为标准型时， 若约束条件的系数 矩阵中不存在单位 矩阵，如何构造 初始可行基？,2.4 初始解（两阶段法）,第一阶段：加入人工变量,构造初始可行基.,用单纯形法求解,若g=0, 进入第二阶段,否则,原问 题无可行解。 第二阶段：去掉人工变量，还原目标函数系数，做 出初始单纯形表。,例：求解下列线性规划问题,将原问题化成标准型：,解:,用两阶段方法来求解。,第一阶段的线性规划问题为,x1 x2 x3 x4 x5 x6 x7,RHS,x1 x2 x3 x4 x5 x6 x7 RHS,x1 x2 x3 x4 x5 x6 x7 RHS,得原问题的基可行解X=(1,3,0,0,0,)T。,第二阶段：将上表中的人工变量去除，目标函数换成原问题的目标函数从上表的最后一个单纯形表出发，继续计算。,x1 x2 x3 x4 x5 RHS,x1 x2 x3 x4 x5 RHS,得原标准线性规划问题的最优解X=（0，5/2，3/2，0，0）T，最优值是-3/2。 所以最初的线性规划问题的最优解X=（0，5/2，3/2）T，最优值是3/2。,例：求解下列线性规划问题,将原问题化成标准型：,解:,用两阶段方法来求解。,第一阶段的线性规划问题为,x1 x2 x3 x4 x5 x6 RHS,x1 x2 x3 x4 x5 x6 RHS,x1 x2 x3 x4 x5 x6 RHS,x1 x2 x3 x4 x5 x6 RHS,第二阶段：将上表中的人工变量去除，目标函数换成原问题的目标函数从上表的最后一个单纯形表出发，继续计算。,x1 x2 x3 x4 RHS,所以最初的线性规划问题的最优解X=(3/5，6/5)T， 最优值是18/5。,例：求解下列线性规划问题,将原问题化成标准型：,解:,用两阶段方法来求解。,第一阶段的线性规划问题为,x1 x2 x3 x4 x5 x6 RHS,x1 x2 x3 x4 x5 x6 RHS,原问题无解。,两阶段方法总结,第一阶段结束时，辅助问题目标函数值大于0，原问题无解； 第一阶段结束时，辅助问题目标函数值等于0，且人工变量都是非基变量，那末，所得基本可行解为原问题初始基本可行解，去掉人工变量，目标函数行换为原问题目标函数，继续求解。 第一阶段结束时，辅助问题目标函数值等于0，但是人工变量不都是非基变量，那么令其强行出基，然后继续求解。,小 结,线性规划问题,图解法,只有两个变量,约束矩阵A中含有一个m阶的单位矩阵,右端向量非负,单纯形方法,约束矩阵A中没有一个m阶的单位矩阵,两阶段法,2.5 对偶性及对偶单纯形方法,对偶问题的提出 原问题与对偶问题的数学模型 原问题与对偶问题的关系 对偶单纯形法,1 对偶问题的提出,例：某家电厂生产两种产品，有关数据如下表：,如何安排生产， 使获利最多？,厂 家,1 对偶问题的提出,收 购,付出代价 最小，且对方 能接受。,出让代价应不低于 用同等数量的资源 自己生产的收益。,1 对偶问题的提出,收 购,厂 家,一对对偶问题,2 原问题与对偶问题的数学模型,其它形式 的对偶 ?,2 原问题与对偶问题的数学模型,原问题（P）,对偶问题（D）,例 写出线性规划问题的对偶问题：,2 原问题与对偶问题的数学模型,3 原问题与对偶问题的关系,收 购,厂 家,一对对偶问题,3 原问题与对偶问题的关系,3 原问题与对偶问题的关系,原问题与对偶问题在某种意义上来说，实质上是一样 的，因为第二个问题仅仅在第一个问题的另一种表达 而已。,理论证明： 原问题与对偶问题解的关系,3 原问题与对偶问题的关系,定理2.5.2 对偶的对偶为原始问题。（对称性）,3 原问题与对偶问题的关系,定理,弱对偶定理（弱对偶性）：设 和 分别是问题（P）和（D）的可行解，则必有,3 原问题与对偶问题的关系,定理2.5.1 如果一个LP问题有最优解，则它的对偶问题也有最优解，且它们的最优值相等。（强对偶定理）,推论（最优性判别定理）原始问题和对偶问题的可行解x, w分别是最优解的充要条件是cTx=wTb。,3 原问题与对偶问题的关系,3 原问题与对偶问题的关系,显然，这两个问题都无可行解。,综上所述，一对对偶问题的关系，只能有下面三种情况之一出现： 都有最优解，分别设为X* 和 Y*，则必有CTX* =bTY*； 一个问题无界，则另一个问题无可行解； 两个都无可行解。,3 原问题与对偶问题的关系,定理2.5.3 原始LP与其对偶必为下面三种情况之一出现,3 原问题与对偶问题的关系,定理2.5.4 设x和w分别是原始问题和对偶问题的可行解，则它们是原始问题和对偶问题的最优解的充要条件是对一切i=1,2,m和一切的j=1,2,n有,3 原问题与对偶问题的关系,4 对偶单纯形方法,基本思路 对偶单纯形方法计算步骤,4 对偶单纯形方法（基本思路）,对偶单纯形法是求解线性规划的另一种基本方法。它是根据对偶原理和单纯形法的原理而设计出来的，因此称为对偶单纯形法。不要简单理解为是求解对偶问题的单纯形法。,4 对偶单纯形方法（计算步骤）,例：,解：将原问题化成标准形：,0 -6 -1 1 0 -2,-15 -24 -5 0 0,4 对偶单纯形方法（计算步骤）,2,-5 -2 -1 0 1 -1,x4,x5,x1 x2 x3 x4 x5 RHS,4 对偶单纯形方法（计算步骤）,0 1 1/6 -1/6 0 1/3,-5 0 -2/3 -1/3 1 -1/3,x2,-15 0 -1 -4 0 10,x1 x2 x3 x4 x5 RHS,4 对偶单纯形方法（计算步骤）,x1 x2 x3 x4 x5 RHS,2.6 灵敏度分析,灵敏度分析概念 如何进行灵敏度分析 价值向量的灵敏度分析 右端向量的灵敏度分析,Cj 市