最优化方法第3章.ppt

第 三 章,线 性 规 划,概述,线性规划是最简单、理论最为成熟、应用最为广泛的一种数学规划方法。 线性规划问题的提出：最早是1939年由前苏联数学家康托洛维奇在研究铁路运输的组织问题、工业生产的管理问题时提出来的。 1947年，美国学者丹西格（G.B.Dantzig）提出了线性规划问题的单纯形方法，使线性规划的算法趋于成熟。,3.1 线性规划模型,一.问题的提出 例1:某工厂拥有A、B、C 三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示，问：工厂应如何安排生产可获得最大的总利润？,决策变量：设变量xi为第i种（甲、乙）产品的生产件数（i1，2）。 约束条件：根据题意，两种产品的生产受到设备能力（机时数）的限制。 对设备A，两种产品生产所占用的机时数不能超过65，于是可以得到不等式：3 x1 + 2 x2 65； 对设备B，两种产品生产所占用的机时数不能超过40，于是可以得到不等式：2 x1 + x2 40；,对设备C，两种产品生产所占用的机时数不能超过75，于是可以得到不等式：3x2 75 ； 产品数不可能为负，即 x1 ,x2 0。 目标函数：即获取最大利润。于是可写出目标函数z为相应的生产计划可以获得的总利润：z=1500x1+2500x2 。 综上所述，在加工时间以及利润与产品产量成线性关系的假设下，把目标函数和约束条件放在一起，可以建立如下的线性规划模型：,目标函数 Max z =1500x1+2500x2 约束条件 s.t. 3x1+2x2 65 2x1+x2 40 3x2 75 x1 ,x2 0,这是一个典型的利润最大化的生产计划问题。其中，“Max”是英文单词“Maximize”的缩写，含义为“最大化”；“s.t.”是“subject to”的缩写，表示“满足于”。因此，上述模型的含义是：在给定条件限制下，求使目标函数z达到最大的x1 ,x2 的取值。,二.一般形式 目标函数： Max(Min)z = c1x1 + c2x2 + + cnxn,约束条件： a11x1+a12x2+a1nxn( =, )b1 a21x1+a22x2+a2nxn( =, )b2 . . . am1x1+am2x2 +amnxn( =, )bm x1 ，x2 ， ，xn 0,三.线性规划模型的标准形式 目标函数： Max z = c1x1 + c2x2 + + cnxn,约束条件： a11x1 + a12x2 + + a1nxn = b1 a21x1 + a22x2 + + a2nxn = b2 . . . am1x1 + am2x2 + + amnxn = bm x1 ，x2 ， ，xn 0,线性规划的标准形式的特点：目标最大化、约束为等式、决策变量均非负、右端项非负。 对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:,1.极小化目标函数的问题 设目标函数为 Min f = c1x1 + c2x2 + + cnxn 则可以令z -f ，该极小化问 题与下面的极大化问题有相同的最优 解，即 Max z = -c1x1 - c2x2 - - cnxn 注：尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即 Min f - Max z,2.约束条件为“”时 aijxjbi aijxj + xn+i = bi xn+i 松弛变量(slack variable)； 3.约束条件为“”时 aijxj bi aijxj xn+i = bi xn+i 过剩变量(surplus variable)； 显然， xn+i具有非负约束，即xn+i 0 这样处理所得最优解不变； max z =x1+10x2 x1 + 2x2100 x1、x20,max z =x1+10x2 x1 + 2x2 + x3=100 x1、x2 、 0,4. 若xk为无符号限制 则令xk=xk1xk2，其中xk1、xk20 5. 若bi 0 举例: 化下列线性规划为标准形 max z=2x1+2x24x3 s.t. x1 + 3x23x3 30 x1 + 2x24x380 x1、x20，x3无限制,max z=2x1+2x24x3+4x3” s.t. x1 + 3x23x3+3x3” x4 = 30 x1 + 2x24x3+ 4x3” + x5 = 80 x1、x2 、x3、x3” 、x4、x5 0,四.矩阵形式 线性规划的一般形式： Max cTx (LP) s.t. Ax b x0 其中： c , x Rn b Rm A: mn 矩阵,线性规划的标准形式： Max cTx (LP) s.t. Ax = b x0 其中： c , x Rn b Rm A：mn 矩阵,3.2 线性规划的图解法,一、基本概念 可行解(Feasible Solution)任一满足约束条件的一组决策变量的数值； 可行域(Feasible Region)所有可行解组成的集合，也称为可行解集； 目标函数等值线(Objective function line)为于同一直线上的点，具有相同的目标函数值.,二、图解法步骤(Procedure) 画出线性规划问题的可行域R； 画出目标函数的梯度向量； 画出目标函数等值线族； 找最优点：沿梯度方向移动时，目标函数值不断增加，因此，当平移直线刚要离开R时的“最后交点”，即为最优。（即满足约束，又使目标函数值最大的点）,三、图解法举例,例1 max Z=50x1+100x2 x1 + x2300 2x1 + x2400 x2250 x1、x20,该问题有唯一最优解 x1=50；x2=250,例2 max Z=50x1+50x2 x1 + x2300 2x1 + x2400 x2250 x1、x20,B点和C点所代表的坐标同时为最优解，即该问题有无穷多最优解,例3 max z =x1+x2 x1x2 1 x1 + 2x20 x1、x20 问题有无界解 (unbounded) 例4 min z =x1+x2 x1x2 1 x1 + 2x20 x1、x20 有唯一最优解,例5 max z =x1+x2 x1 + 2x21 x1 + x22 x1、x20 问题无可行解 (no feasible solution),四.直观结论,可行域可以是个凸多边形，可能无界，也可能为空； 若线性规划问题的最优解存在，它一定可以在可行域的某一个顶点上得到； 若在两个顶点上同时得到最优解，则该两点连线上的所有点都是最优解，即LP有无穷多最优解； 若可行域非空有界，则一定有最优解。,五.图解法的优缺点,优点：当决策变量为两个时，可用图解法求 解，解法简单，可节省求解时间。 缺点：仅适用于两个决策变量的规划问题。,3.3 线性规划问题解的性质,一、线性规划问题的基本概念 对于标准形式的线性规划： max z=cTx s.t. AX=b X0 1. 可行解(feasible solution)满足约束条件的点X=（x1，x2，xn）T称为该LP的一个可行解； 2. 最优解(optimal solution)使目标函数值达到最大的可行解,3基、基变量、非基变量 (base, basic variable, nonbasic variable),设约束方程的系数矩阵A(R(A)=m)中，有m个线性无关的列向量， 且设B=（P1，P2，Pm）线性无关（A中任一非奇异阶子矩阵（B）0），则称B为该LP的一个基； 相应的 P1，P2，Pm为基向量； 与之对应的变量 x1，x2，xm基变量，记为：XB= （x1，x2，xm）T ； 其余的向量为非基向量，记为：N=（Pm+1，Pm+2，Pn）； 其余的变量为非基变量 ，记为：XN=（xm+1，xm+2，xn）T；,4基本解 (basic solution),将AX=b改写 （B，N）（XB，XN）T=b 有： BXB=bNXN 令 XN=0 得到 BXB=b 线性方程组。 由于B中各列向量线性无关，因此解此方程组有唯一解 即： XB= （x10，x20，xm0）T 于是得到AX=b的一个确定的解： X0=（XB，XN）T =（x10，x20，xm0，0，0，0）T 称X0为该线性规划对应与基B的一个基本解。 若一个可行解x又是基本解，则称x为基本可行解。,同样，在A中任选m个线性无关的列向量都可以组成一个基，基对应一个基本解。对于一个LP最多有多少呢？从n个中选m个进行组合，即： Cnm=n！，因此，基本解是有限的。 举例：找出下列LP所有的基及其对应的基本解 max z=6x1+4x2 s.t. 2x1 + 3x2100 4x1 + 2x2120 x1、x20 解：化为标准型 max z=6x1+4x2+0x3+0x4 s.t. 2x1 + 3x2 + x3 =100 4x1 + 2x2 +x4 =120 x1、x2，x3，x4 0,二、线性规划的基本定理,定理1 若线性规划存在可行域，则其可行域R=X|AX=b，X0是凸集。 定理2 线性规划问题的可行解X=（x1，x2，xn）T为基本可行解的充要条件是：X的非零分量所对应的系数列向量是线性无关的。 定理3 如果线性规划有可行解，则一定有基本可行解。 定理4 线性规划问题的基本可行解对应于可行域的顶点。 定理5 若线性规划问题的可行域非空有界，则线性规划问题的最优解一定可以在其可行域的某个顶点上得到；,3.4 单纯形法 (simplex method),基本思想：在有限的基本可行解中寻找最优解。即，从初始基本可行解出发，转换到另一个基本可行解，使目标值增大，直到达到最优解，或判断出无最优解为止。 一、引例 用单纯形方法求解下列线性规划 max z=6x1+4x2 2x1 + 3x2100 4x1 + 2x2120 x1、x20 解：化为标准型 max z=6x1+4x2+0x3+0x4 2x1 + 3x2 + x3 =100 4x1 + 2x2 +x4 =120 x1、x2，x3，x4 0,（1）找初始可行基：B1=（P3，P4）； 此时， XB=（x3，x4）T，XN=（x1，x2）T 用XN表示Z和XB有：（用非基变量表示目标函数和基变量） max z=6x1+4x2 x3 =1002x13x2 +x4 =1204x12x2 令 XN=(0,0)T 有 XB=(100,120)T 则有X（1）=（0，0，100，120）T为对应于基B1的基本可行解。 问： X（1）是否最优呢？否 因为x1和x2在目标函数中的系数为正，当x1，z；x2，z。,（2）寻找可行基B2，使其对应的基本可行解X（2）能使目标函数值增加。 选： x10 则有： X（2）=（x1，0，x3，x4）T 要使X（2）为基本可行解，x3，x4中必有一个为零，而另一个大等于零。 只要取 x1=min100/2，120/4=30 （由约束条件可知） 就有 x3=40，x4=0 这样 X（2）=（30，0，40，0）T 因为 P1，P3线性无关，因此，B2=（P1，P3）为一个基 而 X（2）为对应于B2的基可行解 此时 XB=（x1，x3）T，XN=（x2，x4）T 用XN表示Z和XB有： max z=180+2x2（3/2）x4 x1 = 30（1/2）x2（1/4）x4 x3 = 40 2 x2 +（1/2）x4 问： X（2）是否最优呢？否 因为： x2在目标函数中的系数为正，当x2，z。,（3）寻找可行基B3，使其对应的基可行解X（3）能使目标函数值增加。 选： x20 则有： X（3）=（x1，x2，x3，0）T 要使X（3）为基本可行解，x1，x3中必有一个为零，而另一个大等于零。 只要取 x2=min30/（1/2），40/2=20 就有 x1=20，x3=0 这样 X（3）=（20，20，0，0）T 因为 P1，P2线性无关，因此，B3=（P1，P2）为一个基 而 X（3）为对应于B3的基本可行解 此时 XB=（x1，x2）T，XN=（x3，x4）T 用XN表示Z和XB有： max z=2001/2）x3（5/4）x4 x1 =20 +（1/4）x3 （3/8）x4 x2 =20 （1/2）x3 +（1/4）x4 问： X（3）是否最优呢？是 求解过程：从引例可以总结出求解过程：（1）找出初始基及其基本可行解；（2）判断是否为最优解，是停止，否则转下一步；（3）转换可行基，并求出相应的基本可行解，使目标函数值有所改进，转（2）。,二、单纯形方法,设有标准形式的线性规划问题：max z=cTx；AX=b，X0； 设 B可行基； x可行解 则记 A=（B,N）；X=（ XB，XN ）T， C=（ CB，CN ）T 则,用非基变量表示目标函数,当 时,取XN=0, 则: Z最大. 所以, 为最优解.,检验数(evaluation index) 用非基变量表示目标函数后，非基变量在目标函数中的系数 判别定理：1）B为LP的一个基， 2） 则：对应于B的基本解 必为LP的最优解。,上述方程组的系数增广矩阵 称为对应于基B的单纯形表。,2最优性检验(optimality testing),判别定理1：设X为线性规划的一个基本可行解，且对于一切jJ（J为非基变量的下标集）有j0，则X为LP的最优解； 判别定理2：设X为线性规划的一个基本可行解，且对于一切jJ（J为非基变量的下标集）有j0，同时有某个非基变量的检验数k=0（kJ），则该LP有无穷多最优解； 判别定理3：设X为线性规划的一个基本可行解，若有k0（kJ），且Pk0，则该LP无最优解。,3 转轴运算,问题: 由一基出发，经过旋转可得到一个新可行基，也 可得到一新的不可行基，如何找到可行基，使可行基之间有 限次迭代达最优基.,4. 单纯形法计算步骤 基本思想：采用迭代法，先取一个顶点（即基本可行解），判断是否最优？若不是，则另换一个顶点且目标函数值有所增加，再判断是否为最优解。 第一阶段：找出一个可行基 第二阶段：由可行基出发（换基）找最优基 计算步骤：,保证其目标函数值不减,三、单纯形法解题举例,例2：用单纯形法求解 max z=6x1+2x2+10x3+8x4 5x1 + 6x24x34x420 3x13x2 +2x3 + 8x425 4x12x2 + x3 + 3x410 x1、x2、x3、x40 -7=340, p70,故该LP有无解解,上述单纯形法的基础是线性规划问题有初始基本可 行解。有些线性规划问题化为标准形式以后，就存 在初始可行基，如约束条件全部为“”的线性规划 问题。对于标准形式的线性规划问题，若约束方程 系数矩阵中不存在现成的初始可行基，则不能简单 的用上述单纯形法，而通常采用所谓的人工变量 法。人工变量法一般有两阶段法和大M法。,3.5、人工变量法(Artificial Variable Method),（二）大M法(Big M method) 对于标准形式的线性规划问题（问题A） max z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn= b1 a21x1+a22x2+a2nxn= b2 am1x1+am2x2+amnxn= bm x1，x2，xn0 若其约束方程的系数矩阵中不存在现成的初始可行基，则引入所谓的人工变量xn+1，xn+m构造如下形式的线性规划问题（问题B） max z=c1x1+c2x2+cnxnMxn+1Mxn+m a11x1+a12x2+a1nxn+xn+1 = b1 a21x1+a22x2+a2nxn +xn+2 = b2 am1x1+am2x2+amnxn +xn+m = bm x1，x2，xn，xn+1，xn+m0,问题B中M为任意大的正数。显然问题B存在现成 的单位基，且初始基本可行解中，以人工变量为 基变量。即：xj = 0 j=1, , n ; xn+i = bi i =1 , , m 是基本可行解。 结论： 若问题B得到的最优解满足 xn+i = 0 i =1 , , m则是原问题的最优解；否则，原问题无可行解。,例：用单纯形法（大M法）求解 max z=3x12x2x3 x1 2x2 + x3 11 4x1 + x2 +2x3 3 2x1 + x3 = 1 x1、x2、x30 解：化为标准形式，并引入人工变量，构造如下模型： max z=3x12x2x3Mx6Mx7 x12x2 + x3 + x4 = 11 4x1 + x2 +2x3 x5 + x6 = 3 2x1 + x3 +x7 = 1 x1、x2、x30,3.7 线性规划的对偶问题(Dual Problem),线性规划早期发展过程中的最为重要的理论成果之一就是线性规划的对偶问题及相关理论的提出。线性规划的对偶理论是解释资源的影子价格、线性规划问题的敏度分析等的理论基础。,主要内容 对偶问题定义 线性规划问题写出其对偶问题，要掌握在对称形式和非对称情况下由原问题写出对偶问题的方法。 对偶定理 只需了解原问题与对偶问题解的关系，证明从略。,例:某工厂拥有A、B、C 三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示。求获最大利润的方案。,Max z = 1500x1 + 2500x2 s.t. 3x1 + 2x2 65 2x1 + x2 40 原问题 3x2 75 x1 ,x2 0 同样是上述问题，提问：企业不安排生产，而转让三种设备，应如何给三种资源定价？,决策变量：y1、y2、y3分别代表A、B、C三种设备的价格（最低转让净收入）。 约束条件1：生产一件产品甲所耗资源数量转让所得净收入不能低于一 件产品甲所获利润，即： 3y1+2y2 1500 约束条件2：生产一件产品乙所耗资源数量转让所得净收入不能低于一 件产品乙所获利润，即： 2y1+y2+3y3 2500,Min f = 65y1+ 40y2 + 75y3 s.t. 3y1+2y2 1500 2y1+y2+3y3 2500 对偶问题 y1, y2 , y3 0,2、对偶定义 对称形式： 互为对偶 (LP) Max z = cT x (DP) Min f = bTy s.t. Ax b s.t. ATyc x 0 y 0 “Max - ” “Min-”,一对对称形式的对偶规划之间具有下面的对应关系。 (1)若一个模型为目标求“极大”，约束为“小于等于”的不等式，则它的对偶模型为目标求“极小”，约束是“大于等于”的不等式。即“max，”和“min，”相对应。,(2)从约束系数矩阵看：一个模型中为，另一个模型中为AT。一个模型是m个约束，n个变量，则它的对偶模型为n个约束，m个变量。 (3)从数据b、C的位置看：在两个规划模型中，b和C的位置对换。 (4)两个规划模型中的变量皆非负。,非对称形式的对偶规划 一般称不具有对称形式的一对线性规划为非对称形式的对偶规划。 对于非对称形式的规划，可以按照下面的对应关系直接给出其对偶规划。 （1）将模型统一为“max，”或“min，” 的形式，对于其中的等式约束按下面（2）、（3）中的方法处理；,（2）若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取值没有非负限制； （3）若原规划的某个变量的值没有非负限制，则在对偶问题中与此变量对应的那个约束为等式。,根据以上分析，线性规划原问题与对偶问题的数量关系可用下表描述。,例1 写出下列线性规划问题的对偶问题 max z=2x1+2x24x3 x1 + 3x2 + 3x3 30 4x1 + 2x2 + 4x380 x1、x2，x30,解：其对偶问题为 min w=30y1+ 80y2 y1 + 4y2 2 3y1 + 2y2 2 3y1 + 4y2 4 y1、y20,例2 写出下列线性规划问题的对偶问题 min z=2x1+8x24x3 x1 + 3x23x3 30 x1 + 5x2 + 4x3 = 80 4x1 + 2x24x350 x10、x20，x3无限制 解：其对偶问题为,max w=30y1+80 y2+50 y3 y1 y2 + 4 y3 2 3y1+5y2 + 2y3 8 3y1 + 4y24y3 =4 y10，y2无限制，y30,定理1(弱对偶定理) 设X(0)是原问题max z= cT X ，AXb，X0的可行解,Y(0)是其对偶问题min w= bT Y ， AT y C，Y0的可行解,则 cT X（0）Y（0）b。 原问题任一可行解对应的目标函数值不大于其对偶问题的任一可行解对应目标函数值。,二、对偶问题基本定理,定理2(最优性定理) 设X(0)是原问题max z= cT X ，AXb，X0的可行解，Y（0）是其对偶问题min w= bT Y， AT y C，Y0的可行,若 CX（0）= Y（0）b， 则 X（0）、Y（0）分别是它们的最优解。 定理3(对偶定理) 若原问题max z= cT X ，AXb，X0有最优解，则其对偶问题min w= bT Y ， AT y C，Y0 一定有最优解，且二者目标函数值相等。,资源的影子价格(Shadow Price) 如前所述，若X*为线性规划max z= cT X，AXb，X0的最优解，则z*=CX*；若Y*为其对偶问题的最优解，则有w*= bT Y*。根据对偶定理有 z*=w* 即 z*= bT Y* 因此 即 由此可以看出，对偶问题的最优解实际上是右端常数项的单位变化所引起的目标值的变化；,三. 对偶问题的经济意义,若原问题描述的是资源有限条件下最优生产决策问题，则其对偶问题的最优解yi*(i=1,，m)表示第i种资源在最优生产决策下的边际值，即若