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

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

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

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

4、模型, 这时, 称第一个线性规 划模型为原始模型原始模型, 第二个线性规划模型为对偶模型对偶模型. 例例 3.1.3. 3.1.3. 写出下述线性规划模型的对偶模型及对 偶模型的对偶模型: 123 123 123 123 123 max 563 . . 235, -53, 4738, ,0. xxx st xxx xxx xxx x x x 结论：结论：模型(3.1.8)等价于原始模型(3.1.4), 这说 明原始模型(3.1.4)和其对偶模型(3.1.6)互为对偶 模型. 对一般的线性规划问题, 我们也有此规律, 即原始模型和对偶模型互为对偶模型。原始模型和对偶模型互为对偶模型。 3.2 3

5、.2 对偶问题的基本性质 任意一个线性规划问题都存在着与其对应的对偶 问题, 且互为对偶, 那么原始问题和对偶问题的最优 解之间有什么关系呢? 对偶问题共有四个基本性质,分别是弱对偶性、弱对偶性、 最优性、强对偶性和互补松弛性最优性、强对偶性和互补松弛性. 如果一点关系都没有, 我们在讨论原始问题时 就没必要考虑其对偶问题了; 如果有关系, 有什么 样的关系呢? 设原始问题 max : ,0 T c xAxb x的可行域为 : ,0 n DxRAxb x, 对偶问题 min:, 0 TT b y A yc y 的可行域为 1 : ,0 mT DyRA yc y 性质一性质一. (弱对偶性弱对偶

6、性) 原始问题的目标函数值不超过对偶问题的目 标函数值, 即 1 , , TT c xb yxDyD 证明证明. 任取 xD , 考虑原始问题max : , 0 T c xAxb x 的第 i 个约束: 1 1 1 , 1, n ijjiinni j a xa xa xbim 任取1 yD, 考虑对偶问题min : , 0 TT b yA yc y 的第 j 个约束: 11 1 , 1, m ijijmjmj i a ya ya ycjn 显然,0 x y 且 11111 11111 (), (). nnmmn T jjijijijji jjiij mmnmn T iiijjiijji iij

7、ij c xc xa y xa x y b yb ya xya x y 因此有 TT c xb y 性质二性质二. (最优性) 设1 ,xD yD 使得 TT c xb y, 即对应的目标函数值 相等, 则 x 是原始问题的最优解， y 是对偶问题的最优解. 证明证明. 设 * x是原始问题的最优解, * y是对偶问题的 最优解, 则 * , TTTT c xc xb yb y 由性质一知 *TTTTT c xc xb yb yc x. 故 *TT c xc x和 * TT b yb y 这说明x 是原始问题的最优解， y 是对偶问题的最优解. 性质三性质三. (强对偶性) 若原始问题 max

8、:, 0 T c x Axb x有最优解, min:,0 TT b y A yc y 一定有最优解, 证明证明. 不妨设常向量 0b . 通过引入松弛变量, 可将原始问题化成标准形式: 1 max . . , 1, 0, 0,1, . T n ijjii j i c x sta xxbim x xim 则对偶问题 且对应的最优值相同. 设 *n m xR 是标准形式的最优解且对应的基为B，则 1 * , 0 B b x 1 0B b 且 1 0,1, T jjBj cc Bpjmn 对松弛变量来说, 有 11 0 TTT BmB cc B Ic B 松松 , 从而 1 0 T B c B 令

9、*1 ()T T B yc B 则 *m yR且 * 0.y 对非松弛变量来说, 有 1* ()0 TTTT xB cc B AcyA 进而有 *T A yc 因此, * y是对偶问题的可行解. 由 1 * 0 B b x 可推出 *1* () TTTT B c xc B bybb y 由性质二知, * y是对偶问题的最优解. 性质四性质四. (互补松弛性) 设x是原始问题 max:, 0 T c x Axb x 的最优解, y 是对偶问题 min:, 0 TT b y A yc y 的最优解. 0 i y (1) 若, 则 1 n ijji j a xb (2) 若 1 n ijji j a xb , 则0 i y 证明证明. 显然 1 ,xD yD . 由性质一的证明, 知 1111 nmnm TT jjijjiii jiji c