第三章-线性规划的对偶理论和灵敏度分析

1、第三章第三章 线性规划的对偶理论和灵敏度分析线性规划的对偶理论和灵敏度分析 求解线性规划问题的方法一般分为三步求解线性规划问题的方法一般分为三步: 第一步第一步:对实际问题进行细致分析, 建立适当的线性规划模型; 第二步第二步:求解这个线性规划模型, 得到最优解和最优值; 第三步第三步:对最优解进行分析. 对决策者来说, 进行第三步工作极为重要。通过灵敏度分析研究系数的变化对最优解 的影响。 3.1.对偶问题的提出对偶问题的提出 问题问题 3.1.2. 3.1.2. 四海机械厂为扩大生产规模, 想租借常山机械厂的设备资源. 问: 常山厂愿意以每小时什么价格出租设备呢? 问题建模问题建模. 设常

2、山厂每小时出租C D E , 三种设备的价格分别是123,y yy对常山厂来说, 出租设备所带来的利润应不小于自己生产所带来的利润, 故有约束 和12242yy13255yy对四海厂来说, 一方面租金越少越好; 另一方面, 对租来的设备使用率越高越好, 故目标函数应为123min 121615yyy因此, 可建立如下线性规划模型: 由于模型(3.1.2)是通过模型(3.1.1)引申出来的, 故称模型(3.1.1)为原始模型原始模型, 称对应的实际问题为原始问题原始问题; 称模型(3.1.2)为对偶模型对偶模型, 称对应的问题为对偶问题对偶问题. 从(3.1.3)式可以看出:1. 原始模型是极大

3、化极大化问题, 对偶模型是极小化极小化问题;2. 对偶模型中决策变量的个数决策变量的个数是原始模型中不等式不等式约束的个数约束的个数;3. 对偶模型中不等式约束不等式约束的个数是原始模型中决决策变量策变量的个数;4. 对偶模型中的约束矩阵是原始模型中约束矩阵的转置转置;5. 原始模型是小于等于小于等于的不等式约束, 对偶模型是大于等于大于等于的不等式约束;6. 原始模型的常向量常向量是对偶模型的价值向量价值向量. 对偶模型的常向量常向量是原始模型的价值向量价值向量. 对一般的线性规划模型, 我们也可根据这六条规律, 写出另一个线性规划模型, 这时, 称第一个线性规划模型为原始模型原始模型, 第

4、二个线性规划模型为对偶模型对偶模型. 例例 3.1.3. 3.1.3. 写出下述线性规划模型的对偶模型及对偶模型的对偶模型: 123123123123123max 563 . . 235, -53, 4738, ,0.xxxst xxxxxxxxxx x x结论：结论：模型(3.1.8)等价于原始模型(3.1.4), 这说明原始模型(3.1.4)和其对偶模型(3.1.6)互为对偶模型. 对一般的线性规划问题, 我们也有此规律, 即原始模型和对偶模型互为对偶模型。原始模型和对偶模型互为对偶模型。 3.2 3.2 对偶问题的基本性质 任意一个线性规划问题都存在着与其对应的对偶问题, 且互为对偶,

5、那么原始问题和对偶问题的最优解之间有什么关系呢? 对偶问题共有四个基本性质,分别是弱对偶性、弱对偶性、最优性、强对偶性和互补松弛性最优性、强对偶性和互补松弛性. 如果一点关系都没有, 我们在讨论原始问题时就没必要考虑其对偶问题了; 如果有关系, 有什么样的关系呢? 设原始问题 max: ,0Tc xAxb x的可行域为 : ,0nDxRAxb x, 对偶问题 min:, 0TTb y A yc y的可行域为 1: ,0mTDyRA yc y性质一性质一. (弱对偶性弱对偶性) 原始问题的目标函数值不超过对偶问题的目标函数值, 即 1, ,TTc xb yxDyD 证明证明. 任取 xD, 考虑

6、原始问题max : , 0Tc xAxb x的第 i 个约束: 1 11, 1,nijjiinnija xa xa xbim任取1yD, 考虑对偶问题min : , 0TTb yA yc y的第 j 个约束: 111, 1,mijijmjmjia ya ya ycjn显然,0 x y 且 1111111111(),().nnmmnTjjijijijjijjiijmmnmnTiiijjiijjiiijijc xc xa y xa x yb yb ya xya x y 因此有TTc xb y性质二性质二. (最优性) 设1,xD yD使得TTc xb y, 即对应的目标函数值相等, 则 x是原始问

7、题的最优解，y是对偶问题的最优解.证明证明. 设 *x是原始问题的最优解, *y是对偶问题的最优解, 则 *, TTTTc xc xb yb y由性质一知*TTTTTc xc xb yb yc x. 故*TTc xc x和* TTb yb y这说明x是原始问题的最优解，y是对偶问题的最优解.性质三性质三. (强对偶性) 若原始问题max:, 0Tc x Axb x有最优解, min:,0TTb y A yc y一定有最优解, 证明证明. 不妨设常向量0b . 通过引入松弛变量, 可将原始问题化成标准形式:1max . . , 1, 0, 0,1, .Tnijjiijic xsta xxbimx

8、xim则对偶问题且对应的最优值相同. 设 *n mxR是标准形式的最优解且对应的基为B，则1*,0B bx10B b且10,1,TjjBjcc Bpjmn对松弛变量来说, 有110TTTBmBcc B Ic B 松松, 从而10TBc B令*1()TTByc B则*myR且*0.y 对非松弛变量来说, 有1*()0TTTTxBcc B AcyA进而有*TA yc因此,*y是对偶问题的可行解.由1*0B bx可推出*1*()TTTTBc xc B bybb y由性质二知,*y是对偶问题的最优解.性质四性质四. (互补松弛性) 设x是原始问题 max:, 0Tc x Axb x的最优解,y是对偶问题min:, 0TTb y A yc y的最优解. 0iy (1) 若, 则1nijjija xb(2) 若1nijjija xb, 则0iy 证明证明. 显然1,xD yD. 由性质一的证明, 知1111nmnmTTjj