第三章对偶理论和灵敏度分析

1、第三章 对偶理论和灵敏度分析第三章 对偶理论和灵敏度分析第1节 线性规划的对偶问题第2节 对偶问题的基本性质第3节 影子价格第4节 对偶单纯形法第5节 灵敏度分析第1节 线性规划的对偶问题一、对偶的含义对同一事物（问题）从不同的角度（立场）观察，有两种对立的表述。例如：“平面中矩形的面积与周长的关系”有两种表述：周长一定，面积最大的矩形是正方形；面积一定，周长最短的矩形是正方形。第1节 线性规划的对偶问题例1：某工厂在计划期内要安排生产、两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如下表所示。该工厂每生产一件产品可获利2元，每生产一件产品可获利3元，问应如何安排计划使该工

2、厂获利最多？产品资源产品产品现有条件设备1台时/件2台时/件8台时原材料A4kg/件016kg原材料B04kg/件12kg另一个角度灵敏度分析第1节 线性规划的对偶问题例1：解：设计划期内产品、的产量分别为x1、x2 max z =2x1+3x2 x1+2x28 4x116 4x212 x1，x20求解对偶问题图解法确定影子价格第1节 线性规划的对偶问题从另一个角度考虑例1。假设该工厂的决策者决定不生产产品、 ，而将其所有资源（设备和原材料）出租或外售，问应给每种资源如何定价，使该工厂的收入最合理？第1节 线性规划的对偶问题解：设出租单位设备台时的租金为y1，出让单位原材料A，B的售价为y2，

3、y3 min=8y1+16y2+12y3 y1+4y22 2y1+4y33 y1，y2 ，y30第1节 线性规划的对偶问题max z =2x1+3x2 min=8y1+16y2+12y3 x1+2x28 y1+4y22 4x116 2y1+4y33 4x212 y1，y2，y30 x1，x20第1节 线性规划的对偶问题对于一般产品组合问题的线性规划问题，从另一角度提出问题：假定有另一公司欲将该公司所拥有的资源收买过来，至少应付出多少代价，才能使该公司愿意放弃生产活动，出让资源？第1节 线性规划的对偶问题11221112121112122222112212min,0mmmmmmnnmnmnmb

4、yb yb ya ya ya yca ya yayca ya yaycy yy解：设用yi代表收买该公司一单位i种资源时付给的代价第1节 线性规划的对偶问题1 12211 11221121 1222221 12212max,0nnnnnnmmmnnmnzc xc xc xa xa xa xba xa xa xba xaxaxbx xx11221112121112122222112212min,0mmmmmmnnmnmnmb yb yb ya ya ya yca ya yayca ya yaycy yy企业决策者做生产规划 最大利润为目标 最小资源消耗为目标第1节 线性规划的对偶问题二、对偶问题

5、含义：每一线性规划问题（称为原问题）都有一个与之对应的线性规划问题，称其为对偶问题。第1节 线性规划的对偶问题特点：原问题与对偶问题从不同角度对一个实际问题提出并进行描述，组成一对互为对偶的线性规划问题。（1）同一组数据参数（2）不同数据位置（3）同一个问题从两种不同角度描述第1节 线性规划的对偶问题原问题： max z =CX AXb X0对偶问题： min=Yb YAC Y0三、原问题与对偶问题的转化第1节 线性规划的对偶问题原（对偶）问题对偶（原）问题目标函数z求最大化目标函数求最小化n个变量变量 0变量 0变量取值无约束n个（函数）约束条件（函数）约束条件取（函数）约束条件取（函数）约

6、束条件取m个（函数）约束条件（函数）约束条件为（函数）约束条件为（函数）约束条件为m个变量变量 0变量 0变量取值无约束（函数）约束条件右端项目标函数变量的系数目标函数变量的系数（函数）约束条件右端项原问题与对偶问题的转化规则第1节 线性规划的对偶问题要求：求下列线性规划原问题的对偶问题。例2： max z =2x1+x2 5x215 6x1+2x224 x1+x25 x1，x20第1节 线性规划的对偶问题例2：解： min=15y1+24y2+5y3 6y2+y32 5y1+2y2+y31 y1，y2，y30第1节 线性规划的对偶问题例3： min z =2x1+3x2 -5x3+x4 x1

7、+x2-3x3+x45 2x1+2x3+x44 x2+x3+x4=6 x10，x2，x30，x4无约束第1节 线性规划的对偶问题例3：解： max=5y1+4y2 +6y3 y1+2y22 y1+y33 -3y1+2y2+y3-5 y1+y2+y3=1 y10，y20，y3取值无约束第1节 线性规划的对偶问题例4： min z =7x1+4x2 -3x3 -4x1+2x2-6x324 -3x1-6x2-4x315 5x2+3x3=30 x10，x2无约束，x30第1节 线性规划的对偶问题例4：解： max=24y1+15y2 +30y3 -4y1-3y27 2y1-6y2+5y3=4 -6y2

8、-4y2+3y3-3 y10，y20，y3无约束第1节 线性规划的对偶问题例5： max z =3x1-7x2 -5x3+8x4+8x5 x2-x3+3x4-4x5=-16 2x1+3x2-3x3-2x42 -x1+2x3-2x4-5 -2x110 5x225 x3，x40，x5无约束第1节 线性规划的对偶问题例5：解：min=-16y1+2y2 -5y3+10y4-2y5+25y6+5y7 2y2-y3+y4+y5=3 y1+3y2+y6+y7-7 -y1-3y2+2y3-5 3y1-2y2-2y38 -4y1=8 y1无约束，y20，y30，y40，y50，y60，y70第1节 线性规划的

9、对偶问题例6：min z =2x1+x2 x1+3x210 x12 x2-3第1节 线性规划的对偶问题例6： 解： max=10y1+2y2-3y3 y1+y22 3y1+y31 y10，y20，y30第1节 线性规划的对偶问题小结在写对偶问题时，需要注意的是原问题是最大化形式还是最小化形式，这对对偶问题的变量与约束条件的对应关系影响很大。作业3-1作业3-1：试求下列线性规划原问题的对偶问题。1、 min z =-x1+3x2 -5x3 -2x1+6x2-x330 x1+4x2-3x320 x1-x2+x3=-4 x10，x20，x3无约束2、 max z =x1+x2+2x3+x4 2x1

10、+3x2+x3-x45 x1-x2+6x3+x47 x1+x2=-4 x1，x30 ，x20，x4无约束第2节 对偶问题的基本性质11max0njjjnijjijjzc xa xbx假定线性规划原问题为：110miiimijijiib ya ycy其对偶问题为：min第2节 对偶问题的基本性质1、对称性：对偶问题的对偶是原问题。i112ynmjjiijic xb yj、弱对偶性：若x 是原问题的可行解，是其对偶问题的可行解，则有。i11i3y=ynmjjiijic xb yjj、最优性：若x 是原问题的可行解，是其对偶问题的可行解，且有，则x 是原问题的最优解， 是其对偶问题的最优解。第2节

11、对偶问题的基本性质4、强对偶性（对偶定理）：若原问题有最优解，则其对偶问题也一定有最优解，且目标函数值相同。5、无界性：若原问题（对偶问题）具有无界解，则对偶问题（原问题）无可行解。无界性的应用：当原问题（对偶问题）无可行解时，其对偶问题（原问题）或无可行解或具有无界解。第2节 对偶问题的基本性质即：若对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之若约束条件取严格不等式，则其对应的对偶变量值为零。nniijjijjij=1j=1ya xa xy =iibb6、互补松弛性：在线性规划的最优解中，若0，则；若，则0。mmjijijji=1i=1xaaxjjccii类似可得：若0，

12、则y；若y，则0。第2节 对偶问题的基本性质7、变量对应关系：用单纯形表求解线性规划问题时，迭代的每一步在得到原问题的一个基可行解的同时，其检验数行的相反数是其对偶问题的一个基解。若原问题单纯形表达到最优，则对偶问题的最优解为原问题松弛变量对应的检验数的相反数。第2节 对偶问题的基本性质例8：已知线性规划问题 max z =x1+x2 -x1+x2+x32 -2x1+x2-x31 x1，x2，x30试应用对偶理论证明上述线性规划问题无最优解。第2节 对偶问题的基本性质例8：解：对偶问题 min=2y1+y2 -y1-2y21 y1+y21 y1-y20 y1，y20无界性第2节 对偶问题的基本

13、性质例9：已知线性规划问题 min=2x1+3x2+5x3+2x4+3x5 x1+x2+2x3+x4+3x54 2x1-x2+3x3+x4+x53 x1，x2，x3，x4，x50已知其对偶问题的最优解为y1=0.8，y2=0.6，z=5，试根据对偶理论，直接求出出原问题的最优解。第2节 对偶问题的基本性质例9：解：对偶问题 max z=4y1+3y2 y1+2y22 y1-y23 2y1+3y25 y1+y22 3y1+y23 y1，y20互补松弛性第2节 对偶问题的基本性质例10：已知线性规划问题 max z =x1+2x2+3x3+4x4 x1+2x2+2x3+3x420 2x1+x2+3

14、x3+2x420 x1，x2，x3，x40其对偶问题最优解为y1=1.2，y2=0.2，试根据对偶理论，直接求出原问题最优解。第2节 对偶问题的基本性质例10：解：对偶问题 min=20y1+20y2 y1+2y21 2y1+y22 2y1+3y23 3y1+2y24 y1，y20第2节 对偶问题的基本性质例11：已知线性规划问题 max z =4x1+3x2 x16 2x28 2x1+3x218 x1，x20其最优单纯形表如右所示：试确定对偶问题的最优解。 4 3 0 0 0CBxBb x1 x2 x3 x4 x5403x1x4x2642 1 0 1 0 0 0 0 4/3 1 -2/3 0

15、 1 -2/3 0 1/3 0 0 -2 0 -1jc j单纯形表中解的对应关系第2节 对偶问题的基本性质例12：求解下述线性规划问题。 max z =3x1-2x2+4x3+2x4 4x1+2x2+3x3+x415 3x1-2x2+x3-4x44 x1，x2，x3，x40第2节 对偶问题的基本性质例12：解：对偶问题 min=15y1+4y2 4y1+3y23 2y1-2y2-2 3y1+y24 y1-4y22 y10 ，y20第2节 对偶问题的基本性质小结（1）在求解线性规划问题时，只需求解其中一个问题，就可从最优解的单纯形表中同时得到另一个问题的最优解。（2）求解一个m个约束条件n个变量

16、的线性规划问题，可以转化为求解一个n个约束条件m个变量的对偶问题（3）当m=2时，对偶问题可以用图解法求解，简化求解过程作业3-2作业3-2：已知线性规划问题 max z =2x1+4x2+x3+x4 x1+3x2+x48 2x1+x26 x1+x2+x39 x2+x3+x46 x1，x2 ，x3 ，x40已知原问题最优解为（2，2，4，0），试根据对偶理论，直接求出对偶问题的最优解。第3节 影子价格例13：试确定例1对偶问题的最优解。max z =2x1+3x2 x1+2x28 4x116 4x212 x1，x20第3节 影子价格解：方法一：写出对偶问题并求解max z =2x1+3x2 m

17、in=8y1+16y2+12y3 x1+2x28 y1+4y22 4x116 2y1+4y33 4x212 y1，y2，y30 x1，x20第3节 影子价格方法二：单纯形法转化为标准型 max z =2x1+3x2 x1+2x2+x3=8 4x1+x4=16 4x2+x5=12 x150最优单纯形表如右所示： 2 3 0 0 0CBxBb x1 x2 x3 x4 x5203x1x5x2442 1 0 0 1/4 0 0 0 -2 1/2 1 0 1 1/2 -1/8 0 0 0 -3/2 -1/8 0jc j第3节 影子价格一、影子价格的定义根据第i种资源在生产中做出的贡献而作的估价，称为影子

18、价格。数量上等于对偶问题的最优解yi*，量纲上是对一个单位的第i种资源的估价（或对目标函数的利润贡献）。第3节 影子价格二、影子价格的计算第i种资源的影子价格是第i种资源的边际价格，表示在给定的生产条件下，每增加一个单位的第i种资源时目标函数z*的增量（z*）。=iiziyzb第 种资源的影子价格第3节 影子价格例14：试确定例1中三种资源各自的影子价格。解：图解法图示如下：第3节 影子价格例15：已知线性规划问题 max z =4x1+3x2 x16 2x28 2x1+3x218 x1，x20其最优单纯形表如右所示：试确定三种资源的影子价格，并说明其含义。 4 3 0 0 0CBxBb x1

19、 x2 x3 x4 x5403x1x4x2642 1 0 1 0 0 0 0 4/3 1 -2/3 0 1 -2/3 0 1/3 0 0 -2 0 -1jc j第3节 影子价格小结（1）对于只有两个决策变量的线性规划问题可以用图解法确定第i种资源的影子价格（即为最优目标函数值的改变量）（2）对于两个及两个以上决策变量的线性规划问题可以用单纯形法确定第i种资源的影子价格（即为对偶问题的最优解）第3节 影子价格三、影子价格的经济意义影子价格是第i种资源的机会成本。在现有资源量的基础上，若增加一个单位的第i种资源，企业获利将增加yi* （即z*），反之若减少一个单位的第i种资源，企业获利将减少yi*

20、（即z*） 。生产决策者可以根据第i种资源的市场价格来决策是否调整原来的生产规模。第i种资源的市场价格是已知数，而第i种资源的影子价格取决于该资源的利用情况，是未知数，即是一种动态价格。第i种资源市场价格低于其影子价格，企业应从市场上买进该资源若干单位（获利更大），扩大生产规模。第i种资源市场价格高于其影子价格，企业应把已有该资源卖掉（获利更大），减少生产规模。第i种资源市场价格等于其影子价格，企业既不用买入该资源，也不用卖出该资源。作业3-3作业3-3：有一标准型的线性规划问题：maxZ=CX，AX=b，X0，其最优单纯形表如下表所示。其中：x4，x5是对应于初始单位矩阵的松弛变量。试求：（

21、1）利用最优单纯形表求c1，c2，c3，c4，c5。（2）求约束条件影子价格。 c1 c2 c3 c4 c5CBxBb x1 x2 x3 x4 x5c1c2x1x212 1 0 -1 3 -1 0 1 2 -1 1 0 0 -3 -3 -1jc j第4节 对偶单纯形法例16：求解下述线性规划问题。 min z =15x1+24x2+5x3 6x2+x32 5x1+2x2+x31 x1，x2，x30第4节 对偶单纯形法例16：解：方法一：对偶理论对偶问题 max=2y1+y2 5y215 6y1+2y224 y1+y25 y1，y20第4节 对偶单纯形法方法二：人工变量法 max z=-15x1

22、-24x2-5x3-Mx6-Mx7 6x2+x3-x4+x6=2 5x1+2x2+x3-x5+x7=1 xj0（j=1，2，7）第4节 对偶单纯形法一、对偶单纯形法的含义将单纯形法应用于对偶问题的一种计算方法。第4节 对偶单纯形法二、对偶单纯形法的解题思路在单纯形表中进行迭代时，保持对偶问题的解是基可行解（即所有检验数都为非负），而原问题在非可行解的基础上（即b列数字中有负数），通过逐步迭代达到基可行解，进而得到最优解。第4节 对偶单纯形法三、对偶单纯形法的解题步骤第一，将问题转化为标准型，列初始单纯形表。若表中b列数字都为非负，所有检验数都为非正，则已得最优解，停止计算；否则若b列数字中至少

23、有一个负分量，且所有检验数非正，则转入第二。第二，确定换出变量。 对应的基变量xi为换出变量xl。第三，确定换入变量。在初始单纯形表中检查xl所在行的各系数alj（j=1，2，n）,若所有alj0，则无可行解，停止计算；否则 若存在alj0,则有 ，对应的xk（非基变量）为换入变量。第四，以alk为主元素进行迭代，得到新的单纯形表，重复第一第四，直至终止。111min () ()()iilB bB bB b minjkljljlkaaa 对偶单纯形法求解例16第4节 对偶单纯形法方法三：对偶单纯形法解：标准型转化另一种形式1232312345max1524562521jzxxxxxxxxxxx

24、 0（j=1，2， ，5）1232312345max1524562521jzxxxxxxxxxxx 0（j=1，2， ，5）第4节 对偶单纯形法单纯形法与对偶单纯形法的对应关系单纯形法对偶单纯形法前提条件所有bi0所有j0最优性检验所有j0 ？所有bi0？j0 ？换入、换出变量的确定先确定换入变量后确定换出变量先确定换出变量后确定换入变量原始基解的变化可行最优非可行可行（最优）第4节 对偶单纯形法小结（1）对于初始解是非基可行解，检验数都是负数的情况，不必添加人工变量，直接应用对偶单纯形法计算（2）对于变量多于约束条件的线性规划问题，直接应用对偶单纯形法计算可以减少计算工作量（若约束条件仅有两

25、个，可先将它变换为对偶问题，然后用图解法求解）；对于变量较少，约束条件很多的线性规划问题，可先将它变换成对偶问题，然后用对偶单纯形法求解（3）对偶单纯形法应用的局限性：很难找到一个初始可行基，使初始解是非基可行解，检验数都是负数作业3-4 作业3-4：用对偶单纯形法求解下述线性规划问题。 min z =3x1+2x2+x3+4x4 2x1+4x2+5x3+x40 3x1-x2+7x3-2x42 5x1+2x2+x3+6x415 x1，x2，x3，x40第5节 灵敏度分析一、灵敏度分析的含义系统或事物对因周围条件变化而显示出来的敏感程度的分析。第5节 灵敏度分析目标系数cj：成本、运输、广告、产

26、品的接受程度、竞争者的数量等因素引起cj的变化约束系数aij：生产条件的改变引起aij的变化右端项bi：资源投入量的改变引起bi的变化决策变量：新产品的开发引起的增加约束条件：增加新的资源限制引起约束条件的增加11max(min)( , ),1,2,0,1,2,njjjnijjijjzc xa xb imxjn 第5节 灵敏度分析二、灵敏度分析的内容当模型中约束系数aij、右端项bi和目标系数cj有一个或几个发生变化时，已求得的线性规划问题的最优解会有什么变化模型中约束系数aij、右端项bi和目标系数cj在什么范围内变化时，线性规划问题的最优解（或最优基）不变若已求得的线性规划问题的最优解发生

27、变化，如何求出新的最优解第5节 灵敏度分析灵敏度分析的具体解决问题：右端项bi的变化分析目标系数cj的变化分析约束系数aij的变化分析增加变量的变化分析增加约束条件的变化分析说明：灵敏度分析的具体解决问题以例1为例讨论变化过程第5节 灵敏度分析线性规划问题 其最优单纯形表如下所示： max z =2x1+3x2 x1+2x28 4x116 4x212 x1，x20 2 3 0 0 0CBxBb x1 x2 x3 x4 x5203x1x5x2442 1 0 0 1/4 0 0 0 -2 1/2 1 0 1 1/2 -1/8 0 0 0 -3/2 -1/8 0jc j右端项b2变化目标系数c2变化

28、约束系数a1j变化增加变量x变化第5节 灵敏度分析三、灵敏度分析的步骤1、将参数的改变计算反映到最终单纯形表上来2、用高斯消去法把单纯形表格变成恰当的形式，即基变量在所在方程中的系数为1，而在其他方程中的系数为0，得到一个基解3、可行性检验，检验单纯形表中b列数字是否都为非负4、最优性检验，检验单纯形表中所有非基变量检验数是否都为非正5、只要可行性检验和最优性检验有一个未通过，就以此单纯形表作为初始单纯形表进行迭代第5节 灵敏度分析继续迭代的具体处理方法：若可行性和最优性同时满足，则最优解不变若满足可行性而不满足最优性，则用单纯形法继续迭代求最优解若满足最优性而不满足可行性，则用对偶单纯形法继

29、续迭代求最优解若可行性和最优性同时不满足，则引入人工变量，编制新的单纯形表，求最优解可行性检验最优性检验结论或继续迭代的处理方法所有bi0所有j 0最优解不变所有bi0所有j 0用单纯形法继续迭代求最优解所有bi 0所有j 0用对偶单纯形法继续迭代求最优解所有bi 0所有j 0引入人工变量，编制新的单纯形表求最优解第5节 灵敏度分析灵敏度分析之一：右端项bi的变化分析内容：右端项bi发生变化时（原线性规划问题中其他系数不变），最优基B是否改变；或者为使最优基不变，右端项bi的允许变化范围。方法：右端项bi的变化反映到最终单纯形表上，只引起b列数字的变化（满足最优性）：若满足可行性，则最优解不变

30、；若不满足可行性，则用对偶单纯形法继续迭代求最优解第5节 灵敏度分析例17：在例1中，（1）右端项b2在什么范围内变化时，最优解不变；（2）右端项b2由8变为12，最优解有什么变化？第5节 灵敏度分析灵敏度分析之二：目标系数cj的变化分析非基变量目标系数cj的变化当最优单纯形表中非基变量的目标系数变化时，只影响该非基变量检验数的变化，而不影响其他检验数。基变量目标系数cj的变化当最优单纯形表中基变量的目标系数变化时，最优解中CB相应的发生变化，则影响各非基变量检验数。第5节 灵敏度分析例18：线性规划问题 max z =6x1+30 x2+13x3 0.5x1+4x2+x324 x1+4x2+

31、4x360 x1，x2，x30其最优单纯形表如下所示。（1）目标系数c2在什么范围内变化时，最优解不变；（2）目标系数c2由60变为50，最优解有什么变化？ 6 30 13 0 0CBxBb x1 x2 x3 x4 x5613x1x3366 1 12 1 3 -1 0 -2 0 -1 1/2 0 -16 0 -11 -1/2jc j非基变量第5节 灵敏度分析例19：在例1中，（1）目标系数c2在什么范围内变化时，最优解不变；（2）目标系数c2由3变为5，最优解有什么变化？基变量第5节 灵敏度分析灵敏度分析之三：约束系数aij的变化分析非基变量约束系数aij的变化当最优单纯形表中非基变量的约束系

32、数变化时，只影响该非基变量检验数的变化，而不影响其他检验数。基变量约束系数aij的变化当最优单纯形表中基变量的约束系数变化时，影响最优单纯形表中几乎所有的位置。第5节 灵敏度分析例20：已知线性规划问题 max z =2x1+5x2+x3+4x4 4x1+3x2+0.5x3+2x48 8x1+4x2+7x3+4x412 7x1+4x2+9x3+3x410 x1-40的最优单纯形表如下所示。 2 5 1 4 0 0 0CBxBb x1 x2 x3 x4 x5 x6 x7045x5x4 x2121-1 0 27/4 0 1 1/4 -1 1 0 -2 1 0 1 -1 1 1 15/4 0 0 -3/4 1-7 0 -39/4 0 0 -1/4 -1jc j非基变量487 487 362 （1）x1的约束系数 在什么范围内变化时，最优解不变；（2） x1的约束系数由 变为 ，最优解有什么变化？增加约束条件的变化第5节 灵敏度分析例21：在例1中，基变量11124502144502xx （1） 的约束系数由变为时，最优解有什么变化？（2） 的约束系数由变为时，最优解有什么变化？第5节 灵敏度分析灵敏度分析之四：增加变量的变化分析方法：在原问题的最优单纯形表中增加一列，计算检验数，若检验数0，则原问题最优解不变，否则，以该增加变量为换入变量，用单纯形法继续迭代求最