运筹学课件第2章 线性规划的对偶理论

1、5-4 单纯形法计算的向量矩阵描述,线性规划的标准形式,初始 单纯 形表,关系：,CB,最终单纯形表,s.t.,例1 用单纯形法求解线性规划问题,解：,将上述问题化为标准形式, , ,B,N,B-1,B-1N,B-1b,NY1 + BY2 + Y3 = b,B-1NY1 + Y2 + B-1Y3 = B-1b,-CBB-1,I,I, , ,5-4 单纯形法计算的向量矩阵描述,线性规划的标准形式,初始 单纯 形表,关系：,CB,最终单纯形表,线性规划问题具有对偶性,即任何一个线性规划问题,都存在另一个线性规划问题与之对应.如果把其中一个问题叫做原问题,则另外一个就叫做它的对偶问题.并称这两个相互

2、联系的问题为一对对偶问题.研究对偶问题之间的关系及其性质,就是线性规划的对偶理论(DualityTheory).,第2章 线性规划的对偶理论,1 对偶问题的提出 2 原问题与对偶问题 3 对偶问题的基本性质 4 影子价格 5 对偶单纯形法 6 灵敏度分析 7 参数线性规划,常山机器厂用A、B、C三种设备生产I、II两种产品。问该企业应如何安排生产使总的利润收入为最大。,例1 生产计划问题,2-1 对偶问题的提出,模型,s.t.,现有四海机器厂, 为扩大生产想租常山机器厂的设备, 问常山机器厂分别以每小时什么价格才愿意出租自己的设备呢?,设设备A, B, C每小时的出租价格分别为y1, y2,和

3、y3元,出租条件: 租金收入生产的获利。,四海机器厂接受条件: 租金要低,LP1,LP2,s.t.,LP2,模型,LP1,矩阵形式见P54-P55,原始问题 Max z=CX s.t.AX b X 0,对偶问题 Min w =bT Y s.t. AT Y CT Y 0,max,b,A,C,CT,AT,bT,max,m,n,m,n,对偶的定义,规范对偶问题,2-2 原问题与对偶问题,对应关系：,(1),(2),变量的个数,约束条件个数,=,(3),(原)约束条件,(4),右端项,目标函数的系数,(对偶)约束条件,原问题,对偶问题,一般形式,矩阵形式,【例】写出下列线性规划的对偶问题,【解】这是一

4、个规范形式的线性规划，设Y=（y1，y2），则有,线性规划的对偶模型 Dual model of LP,从而对偶问题为,对偶变量yi也可写成xi的形式。,线性规划的对偶模型 Dual model of LP,【例】 写出下列线性规划的对偶问题,【解】这是一个规范形式的线性规划，它的对偶问题求最小值，有三个变量且非负，有两个“ ”约束，即,线性规划的对偶模型 Dual model of LP,若给出的线性规划不是规范形式，可以先化成规范形式再写对偶 问题。也可直接按表2-2中的对应关系写出非规范形式的对偶问题。,将上述原问题与对偶问题的对应关系列于表2-2,例如，原问题是求最小值，按表2-2有下

5、列关系：,1. 第i个约束是“ ”约束时，第i个对偶变量yj0,2第i个约束是“ = ”约束时，第i个对偶变量yi无约束；,3当xj0时，第j个对偶约束为“ ”约束，当xj无约束时，第j个对偶约束为“ = ”约束。,线性规划的对偶模型 Dual model of LP,线性规划的对偶模型 Dual model of LP,对偶问题 原问题,原问题 对偶问题,一般形式,矩阵形式,2-2 原问题与对偶问题,对应关系：,(1),(2),变量的个数,约束条件个数,=,(3),(原)约束条件,(4),右端项,目标函数的系数,(对偶)约束条件,(4),目标函数的系数,(4),(4),系数矩阵AT,(5),

6、系数矩阵A,线性规划的对偶模型 Dual model of LP,写出下列线性规划的对偶问题,2-3 对偶问题的基本性质,弱对偶性；强对偶性； 最优性; 无界性; 互补松弛性,掌握原问题和其对偶问题解之间的关系,对偶问题是（记为DP）：,这里A是mn矩阵, X是n1列向量，Y是m1列向量。假设Xs与Ys分别是（LP）与（DP）的松驰变量。,设原问题是（记为LP）：,2.3对偶性质 Dual property,在下面的讨论中, 假定线性规划原问题和对偶问题分别如下,【证】因为X0、Y0是可行解，故有AX0b, X00及AY 0C，Y00,将不等式 AX0b,弱对偶性 设X0、Y0分别为LP(ma

7、x)与DP(min)的可行解，则,两边左乘Y0，得Y0 AX0Y0b,再将不等式Y0AC两边右乘X0，得C X0Y0AX0,故 C X0Y0AX0Y0b,这一性质说明了两个线性规划互为对偶时，求最大值的线性规划的任意目标值都不会大于求最小值的线性规划的任一目标值，不能理解为原问题的目标值不超过对偶问题的目标值。,2.2 对偶性质 Dual property,最优性,问题的可行解，且有,若,是原问题的可行解，,提示,则,是原问题的最优解，,是其对偶问题的最优解。,设,是原问题的最优解，,是其对偶问题的最优解。,是其对偶,无界性,若原问题(对偶问题)具有无界解, 则其对偶问题(原问题)无可行解.,

8、说明,逆命题不成立。,即原问题(对偶问题)无可行解，则其对偶问题(原问题)或无可行解或具有无界解,反证法结合弱对偶性,线性规划的标准形式,初始单纯形表,关系：,CB,线性规划的标准形式,CB,恰好是对偶问题的基解.,原问题检验数的相反数,对偶问题的基解为原问题检验数的相反数, 原问题的松弛变量-对偶问题的变量, 原问题的变量-对偶问题的松弛变量.,由单纯形表所得到的原问题和对偶问题的基解 对应目标函数相等即z=w,互补的基解,线性规划的原问题及其对偶问题之间 存在一对互补的基解, 其中原问题的松弛变量对应对偶问题的变量, 对偶问题的剩余变量对应原问题的变量； 这些互相对应的变量如果在一个问题的

9、解中是基变量, 则在另一问题的解中是非基变量； 将这对互补的基解分别代入原问题和对偶问题的目标函数有z=w.,说明：,原问题检验数的相反数yj,恰好是对偶问题的基解.,例.,s.t.,原问题,对偶问题,标准形式,最终单纯形表,原问题变量,原问题松弛变量,对偶问题变量,对偶问题剩余变量,y1 y2 y3,y4 y5,对偶问题剩余变量,原问题变量,对偶问题变量,原问题松弛变量, , ,说明：,1) 从原问题的最优解的单纯形表中同时得到对偶问题的最优解,因此只需求解其中一个问题即可.,2)单纯形法迭代的每一步中, 原问题及对偶问题解的关系,可行解,非可行解,可行解,非可行解,最优,z zmax,z

10、zmax,=,由单纯形表得到原问题的 一个最优解的同时, 也得到了其对偶问题的一个最优解,解的结果为 原问题检验数的相反数,原问题的松弛变量对应 对偶问题的变量,原问题的变量对应对偶问题 的松弛变量.,由最优性得 为对偶问题的最优解 .,强对偶性,最终单纯形表,由原问题的最优解得到对偶问题的可行解,且它们对应的目标函数值相等,强对偶性(对偶定理),若原问题有最优解, 则其对偶问题,且有,证明：,将原问题化成标准形式,用单纯形法求得最优解，则有,即,即,故,是对偶问题的可行解,又因,由性质2即可证得。,也一定有最优解,互补松弛定理 设X0、Y0分别为（LP）与（DP）的可行解，XS和YS是它的松

11、弛变量的可行解，则X0和Y0是最优解当且仅当,YSX0=0和Y0XS=0,【证】设X和Y是最优解,由强对偶性得，C X0= bY0，由于XS和YS是松弛变量，则有,A X0XSb Y0AYS=C,将第一式左乘Y0，第二式右乘X0得,Y0A X0Y0XSY0b Y0A X0YS X0=C X0,2.3 对偶性质 Dual property,显然有,Y0XS=YS X0,又因为Y、Xs、Ys、X0，所以有,Y0XS =0和YS X0=0,成立。,反之， 当Y0XS=0和YS X=0时，有,Y0A X0Y0 b Y0A X0=C X0,显然有Y0 b=C X0,由最优性知Y0与X0是（LP）与（DP

12、）的最优解。证毕。,2.3对偶性质 Dual property,互补松弛关系,max z=CTX s.t. AX+u=b X, u0,min w=bTY s.t. ATY-v=C Y, v0,max z=CX s.t. AX b X 0,min w=bTY s.t. ATy C y0,互补松弛关系,max z=CX s.t.AX+u=b X, u 0,min w=bTy s.t. ATY-v=CT Y, v 0,XTv=0 YTu=0,m,n,=,Y,v,AT,-I,CT,n,=,A,u,I,b,n,m,m,X,y1 yi ym vm+1 vm+j vm+n,x1 xj xn un+1 un+

13、i un+m,对偶问题的变量 对偶问题的松弛变量,xjvm+j=0yiun+i=0(i=1,2,m; j=1,2,n) 在一对变量中，其中一个大于0，另一个一定等于0,【例2】 已知线性规划,的最优解是 求对偶问题的最优解。,2.2 对偶性质 Dual property,【解】对偶问题是,因为X10，X20，所以对偶问题的第一、二个约束的松弛变量等于零，即,解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为Y=（1，1），最优值w=26。,2.2 对偶性质 Dual property,2-4 已知线性规划问题：,对偶问题,要求: (a)写出其对偶问题； (b)已知原问题最优解为 根据对

14、偶理论, 直接求出对偶问题的最优解.,由互补松弛性得,由目标函数相等得,线性规划的标准形式,初始单纯形表,关系：,CB,线性规划的标准形式,CB,恰好是对偶问题的基解.,原问题检验数的相反数,对偶问题的基解为原问题检验数的相反数, 原问题的松弛变量-对偶问题的变量, 原问题的变量-对偶问题的松弛变量.,由单纯形表所得到的原问题和对偶问题的基解 对应目标函数相等即z=w,1) 从原问题的最优解的单纯形表中同时得到对偶问题的最优解,因此只需求解其中一个问题即可.,2)单纯形法迭代的每一步中, 原问题及对偶问题解的关系,可行解,非可行解,可行解,非可行解,最优,z zmax,z zmax,=,2-5

15、 对偶单纯形法,单纯形法计算的基本思想：,保持原问题为可行解的基础上, 通过迭代增大目标函数, 当对偶问题的解也为可行解时, 就达到了目标函数的最优解.,即,从满足,的基解入手，,寻找满足,的基解。,对偶单纯形法的基本思想：,保持对偶问题为可行解的基础上, 通过迭代减小目标函数, 当原问题的解也为可行解时, 就达到了目标函数的最优解.,的条件下寻找满足,的基解。,从满足,的基解入手，,即,在保持,的条件下,在保持其不变,cj -zj,cj zj,cn -zn,对偶单纯形法的初始单纯形表：,在上表中必须有,cj zj 0 ( j= 1,n ),但,的值不一定为正.,对偶单纯形法的计算步骤：,(1

16、) 确定出基变量.,对应的变量xr作为出基变量.,(2) 确定入基变量.,xs作为入基变量.,ars称为主元素,(3) 用入基变量替换出基变量得到新基, 进行初等变换, 再检验是否 , 若是, 则找到了问题的最优解, 否则, 回到第一步再重复计算.,说明：,原问题无可行解, 对偶问题的目标函数值无界.,原问题无可行解的判别方法：,例4：用对偶单纯形法求解线性规划问题,解：,化成标准形式,列出单纯形表, 并用对偶单纯形法求解, , ,说明：,1) 在利用对偶单纯形法时, 要保证初始单纯形表中对偶问题应是基可行解, 这一点对大多数线性规划很难实现, 因此对偶单纯形法一般不单独使用.,2) 使用对偶

17、单纯形法的条件,概况 改变价值向量 改变右端向量 增加变量 增加约束条件,2-6 灵敏度分析,1. 灵敏度分析的含义,概况,是指对系统或事物因周围条件变化显示出来的敏感度的分析.,2. 灵敏度分析研究的问题,当一个或多个参数发生变化时, 最优解会有什么变化; 或这些参数在一个多大范围内变化时, 问题的最优解不变.,3. 如何解决,1) 用单纯形法从头计算(此法既麻烦又没有必要),2) 把参数的变化直接反映到最终单纯形表中，再继续处理。,灵敏度分析的步骤,1) 将参数的改变计算反映在最终单纯形表上,2) 检查原问题是否仍为可行解,4) 按右表所列情况得出结论和决定继续计算的步骤,3) 检查对偶问

18、题是否仍为可行解,6-1 价值系数cj发生变化(仅影响检验数),单纯形表,s.t.,例 已知下述线性规划的最终单纯形表为,(1) 若c由(2, 3)变成(3, 2), 最优解是否发生变化?,(2) 若目标函数为,问 分别在什么范围内变化时，问题的最优解不变？,当 在什么范围内变化时，问题的最优解不变？,例 已知下述线性规划的最终单纯形表为,(1) 若c由(2, 3)变成(3, 2), 最优解是否发生变化?,解：,将c的变化反映到最终单纯形表中,3 2,3,2,- 3/2, ,最优解是(4,2,0,0,5), 最优值16,1/ 5,(2) 若目标函数为,问 分别在什么范围内变化时, 问题的最优解

19、不变？,解：,当,即,最优解不变.,时,类似可讨论，当,最优解不变.,(3) 若目标函数为,问 在什么范围内变化时, 问题的最优解不变？,解：,当,即,最优解不变.,时,o,6-2 分析bi的变化范围,bi的变化引起基变 量的取值发生变化， 有可能发生1、3 两种情况,s.t.,例 已知下述线性规划的最终单纯形表为,(1) 若b由(12,16,15)变成(15,12,20), 最优基是否发生变化?,(2) 若b变成 ，分别分析 在什么范围内变化时, 问题的最优基不变。,(3) 当 在什么范围内变化时, 问题的最优基不变。,解：,(1) 若b由(12,16,15)变成(15,12,20), 最优

20、基是否发生变化?,则新规划的最初单纯形表为, ,最优基发生变化，,最优值为18,最优解为,解：,当,问题的最优基不变,(2) 若 ，分别分析 在什么范围内变化时, 问题的最优基不变。,即,类似可求得当,问题的最优基不变,解：,当,即,问题的最优基不变,(3) 若 ，分析 在什么范围内变化时, 问题的最优基不变。,6-3 增加新变量(增加新产品),分析步骤：,(1)计算,(2)计算,(3)若,，只需将,原最优解不变,的值反映到最终单纯形表中，,和,，则按单纯形法继续迭代计算。,若,s.t.,例 已知下述线性规划的最终单纯形表为,若增加一个变量x6 , 有c6=4, P6=(2,4,5)T, 分析

21、问题最优解的变化.,解：,构造新表, ,利用单纯形法继续迭代,6-4 增加约束条件(增加工序),分析步骤：,先将原问题的最优解代入新增的约束条件， 若满足，说明新增约束未起到限制作用，原最优解不变. 否则，将新增约束直接反映到最终表中，再进行分析.,s.t.,例 已知下述线性规划的最终单纯形表为,若增加一个约束条件 , 分析问题最优解的变化.,解：,原问题的最优解为(3,3,0,4,0)，而33+2 3=1514,构造新表,将新增的约束条件加上松弛变量后的方程 直接反映到最终单纯形表中，得,取P1、P4、P2、P6列组成单位阵,对上表进行初等行变化得到对应的单纯形表,对偶单纯形法, ,最优解,

22、最优值,x1=8/3, x2=3,z*=43/3,s.t.,练习 已知下述线性规划的最终单纯形表为,(1)若增加一个约束条件 , 分析问题最优解的变化.,(2)若增加一个约束条件 , 分析问题最优解的变化.,s.t.,练习 已知下述线性规划的最终单纯形表为,(1)若增加约束条件 , 分析问题最优解的变化.,解：,原问题的最优解为(3,3,0,4,0)，,故(3,3,0,4,0)还是新规划的最优解,而33+2 3=1514,对上表进行初等行变化得到对应的单纯形表,s.t.,练习 已知下述线性规划的最终单纯形表为,(2)若增加一个约束条件 , 分析问题最优解的变化.,解：,原问题的最优解为(3,3

23、,0,4,0)，而33+2 3=1516,将新增的约束条件减去剩余变量后的方程 直接反映到最终单纯形表中,构造新表,取P1、P4、P2、P6列组成单位阵,构造初始单纯形表,对偶单纯形法, ,2-7 参数线性规划,灵敏度分析：,研究使问题的最优解或最优基保持不变时的参数值变化范围.,参数线性规划：,研究当参数值连续变化时, 问题的最优解如何随参数值的变化而变化.,例 求解下述参数线性规划问题,s.t.,解：,当=0求解得最终单纯表为,将参数的变化反映到最终单纯形表中，得,当,即,最优解为（3，3）,当-1时, 30， 50利用单纯形法继续迭代, , ,当1时, 50， 30利用单纯形法继续迭代, ,例 求解下述参数线性规划问题,s.t.,解：,当=0求解得最终单纯表为,将参数的变化反映到最终单纯形表中,当,即,时，最优基不变, , ,2-4 影子价格,在单纯形法的每步迭代中有目标函数,表示第i种资源的拥有量,表示对第i种资源一个单位的估价, 非市场价格.,影子价格,说明：,1)供求关系影响市场价格; 资源的利用影响影子价格.,2) 影子价格是一种边际价