第二章 线性规划的对偶理论与灵敏度分析
主要内容 讲授重点 讲授方式
对偶问题、对偶基本性质、对偶单纯形方法、灵敏度分析、参数规划 对偶基本性质、对偶单纯形方法、灵敏度分析 讲授式、启发式
本章知识结构图
对偶问题灵敏度分析对偶单纯形法参数线性规划基本性质影子价格解的关系 第一节 线性规划的对偶问题
一、对偶问题的提出
首先通过实际例子看对偶问题的经济意义。
例1 第一章例1中美佳公司利用该公司资源生产两种家电产品时，其线性规划问题为： (LP1) max z＝2xl+x2
现从另一角度提出问题。假定有另一公司想把美佳公司的资源收买过来，它至少应付出多大代价，才能使美佳公司愿意放弃生产活动，出让自己的资源。显然美佳公司愿出让自己资源的条件是，出让代价应不低于用同等数量资源由自己组织生产活动时获取的盈利。设分别用y1、y2、和y3代表单位时间(h)设备A、设备B和调试工序的出让代价。因美佳公司用6小时设备A和1小时调试可生产一件家电I，盈利2元；用5小时设备A，2小时设备B及1小时调试可生产一件家电Ⅱ，盈利1元。由此y1，y2，y3的取值应满足 6y2+y3≥2
5y1+2y2+y3≥1 (2.1) 又另一公司希望用最小代价把美佳公司的全部资源收买过来，故有
min z＝15y1+24y2+5y3 (2.2) 显然yi≥0(i＝l，2，3)，再综合(2.1)，(2.2)式有。
(LP 2) min ?＝15y1+24y2+5y3
?5x2?15?6x?2x?24?12??x1?x2?5??x1,x2?0
上述LP1和LP2是两个线性规划问题，通常称前者为原问题，后者是前者的对偶问题。 二、对称形式下对偶问题的一般形式
定义：满足下列条件的线性规划问题称为具有对称形式：其变量均具有非负约束，其约束条件当目标函数求极大时均取“≤”号，当目标函数求极小时均取“≥”号’。
对称形式下线性规划原问题的一般形式为：
?6y2?y3?2??5y1?2y2?1?y,y,y?0?123
max z=c1x1+c2x2+?+cnxn ?a11x1?a12x2?????a1nxn?b1??a21x1?a22x2?????a2nxn?b2??????ax?ax?????ax?bm22mnnm?m11??xj?0(j?1,?,n) (2.3)
用yi（i=1，?，m）代表第i种资源的估价，则其对偶问题的一般形式为:
min w=b1y1+b2y2+?+bmym
?a11y1?a12y2?????am1ym?c1?ay?ay?????ay?c211222m2m2??y???????????ay?ay?????ay?c2n2mnmn?1n1(i?1,???,m)??yi?0 (2.4)
用矩阵形式表示，对称形式的线形规划问题的原问题为：
max z=CX
?AX?b? ?X?0 (2.5)
其对偶问题为：
min w=Y’b
?A'Y?C?Y?0 ?
将上述对称形式下线性规划的原问题与对偶问题进行比较，可以列出如表2-1所示的对应关系。 表 2－1 原 问 题 对偶问题 A B C 目标函数 约束条件 决策变量 约束系数矩阵 约束条件的右端项向量 目标函数中的价格系数向量 max z=CX AX≤b X≥0 其约束系数矩阵的转置 目标函数中的价格系数向量 约束条件的右端项向量 min ?=Y?b A?Y≥C? Y≥0
上述对偶问题中令?= ??，可改写为
' max ?=-Y’b
'??A'Y??C'? ?Y?0
minz'??CX??AX??b?X?0 ?
'再令z??z则上式可改写为：
minz??CX如将其作为原问题，并按表2-1所列对应关系写出它的对偶问题则有
??AX??b? ?X?0
可见对偶问题的对偶即原问题。
三、非对称形式的原-对偶问题关系
因为并非所有线性规划问题具有对称形式，故下面讨论一般情况下线性规划问题如何写出其对偶问题。考虑下面的例子。
例2 写出下述线性规划问题的对偶问题
maxz?x1?4x2?3x3
?2x1?3x2?5x3?2?3x?x?6x?1?123??x1?x2?x3?4??x1?0,x22?0,x3无约束
思路是先将其转换成对称形式，再按表2-1的对应关系来写。
下面将对称或不对称线性规划原问题同对偶问题的对应关系，统一归纳为表2-2所示形式。 表2-2 原问题（对偶变量） 对偶问题（原问题） A b c 目标函数 约束系数矩阵 约束条件右端项向量 目标函数中的价格系数向量 约束条件系数矩阵的转置 目标函数中的价格系数向量 约束条件右端项向量 maxz??cjxjj?1n min???biyij?1n ?xj(j?1,?,n)??xj?0变量??xj?0?x无约束?j 有n个(j?1,?,n)??m?aijyi?cj??i?1?m?ay?c?ijij?i?1?m?ay?c?ijij?i?1?约束条件 原问题（对偶变量） 对偶问题（原问题） 有m个(j?1,?,m)??n?aijyj?ci??j?1?n?ay?c?ijji?j?1?n?aijyj?ci??j?1?约束条件 ?yi(j?1,?,m)?y?0?i变量??yi?0??xi无约束 第二节 对偶问题的基本性质
本节的讨论先假定原问题及对偶问题为对称形式线性规划问题，即原问题为：
maxz??cixjj?1n
其对偶问题为：
?m??aijxj?bi(i?1,?,m)?j?1?x?0(j?1,?,n)?j (2.9)
minw??bixii?1m (2.10) 然后说明对偶问题的基本性质在非对称形式时也适用。
为本节讨论及后面讲述的需要，这里先介绍有关单纯形法计算的矩阵描述。
一、单纯形法计算的矩阵描述
对称形式线性规划问题(2.9)的矩阵表达式加上松弛变量后为：
?m??aijxi?cj(i?1,?,m)?i?1?x?0(j?1,?,n)?jmaxz?Cx?0Xs?AX?IXs?b?X?0,Xs?0 ? (2.11)
上式中Xs为松弛变量，Xs=( xn+1,xn+2,?，xn+m)，I为m×m单位矩阵。
单纯形法计算时，总选取I为初始基，对应基变量为Xs。设迭代若干步后，基变量为XB，XB在初始单纯形表中的系数矩阵为B。将B在初始单纯形表中单独列出，而A中去掉后的若干列后剩下的列组成矩阵N，这样(2.11)的初始单纯形表可列成如表2-3的形式。
表 2-3 非基变量 XB XN B N 基 变 量 Xs I 0 Xs b cj-zj CB CN 0 当迭代若干步，基变量为XB时，则该步的单纯形表中由XB系数组成的矩阵为I。又因单纯形法的迭代是对约束增广矩阵进行的行的初等变换，对应Xs的系数矩阵在新表中应为
B。故当基变量为XB时，新的单纯形表具有表2-4形式。
表 2-4 -1
基 变 量 XB -1非基变量 XN Xs BN B -1-1-1-1 CB XB Bb I cj-zj 0 CN-CBN -CBB 从表2-3和表2-4看出，当迭代后基变量为XB时，其在初始单纯形表中的系数矩阵为B，则有：
(1)对应初始单纯形表中的单位矩阵I，迭代后的单纯形表中为B(2)初始单纯形表中基变量
?1；
Xs＝b,，迭代后的表中XB＝B?1b,，
?1?1?1?1?1(3)初始单纯形表中约束系数矩阵为[BA，BI]＝[BB，BN，BI]，迭代
?1?1?1?1?1?1?1后的表中约束系数矩阵为[BA，BI]＝[BB，BN，BI]＝[I，BN，B]。
(4)若初始矩阵中变量
xj 的系数向量为
Pj 迭代后为
Pj' ，则有
Pj'?B?1Pj （2.13）
（5）当B为最优解时，在表2-4中应有
?1C?CBN?0 NB （2.14）
?CBB?1?0 (2.15)
因 xB 的检验数可写为
CB?CB?I?0 (2.16)
故(2.14)～(2.16) 式可重写为
?1C?CBA?0 (2.17) B
?CBB?1?0 (2.18)
CBB?1称为单纯乘子，若令Y'?CBB?1 则(2.17)、(2.18)式可改写为
?A'Y?C'?Y?0 ? (2.19)
看出这时检验数行，若取其相反数恰好是其对偶问题的一个可行解。将这个解代入对偶问题的目标函数值，有
'?1??Yb?CBb?z (2.20) B
由(2.20)式看出，当原问题为最优解时，这时对偶问题为可行解，且两者具有相同的目
标函数值。根据下一节讲述的对偶问题的基本性质，将看到这时对偶问题的解也为最优解。
下面通过例子说明两个问题的变量及解之间的对应关系，见例3。
例3 本章例1中列出了两个互为对偶的线性规划问题，两者分别加上松弛和剩余变量后为：
maxz?2x1?x2?0x3?0x4?0x5