下载文档原格式
第三章线性规划对偶理论与灵敏度分析习题 一、思考题1．对偶问题和对偶变量的经济意义是什么？2．简述对偶单纯形法的计算步骤。
它与单纯形法的异同之处是什么？3．什么是资源的影子价格？它和相应的市场价格之间有什么区别？4．如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检 验数之间的关系？5．利用对偶单纯形法计算时，如何判断原问题有最优解或无可行解？6．在线性规划的最优单纯形表中，松弛变量（或剩余变量）0>+k n x ，其经济意 义是什么？7．在线性规划的最优单纯形表中，松弛变量k n x +的检验数0>+kn σ（标准形为求最小值），其经济意义是什么？8．将i j ji bc a ,,的变化直接反映到最优单纯形表中，表中原问题和对偶问题的解 将会出现什么变化？有多少种不同情况？如何去处理？ 二、判断下列说法是否正确1．任何线性规划问题都存在且有唯一的对偶问题。
2．对偶问题的对偶问题一定是原问题。
3．若线性规划的原问题和其对偶问题都有最优解，则最优解一定相等。
4．对于线性规划的原问题和其对偶问题，若其中一个有最优解，另一个也一定 有最优解。
5．若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷多个最优解。
6．已知在线性规划的对偶问题的最优解中，对偶变量0>*i y ，说明在最优生产计 划中，第i 种资源已经完全用尽。
7．已知在线性规划的对偶问题的最优解中，对偶变量0=*i y ，说明在最优生产计 划中，第i 种资源一定还有剩余。
8．对于i j ji bc a ,,来说，每一个都有有限的变化范围，当其改变超出了这个范围 之后，线性规划的最优解就会发生变化。
9．若某种资源的影子价格为u ，则在其它资源数量不变的情况下，该资源增加k 个单位，相应的目标函数值增加 u k 。
10．应用对偶单纯形法计算时，若单纯形表中某一基变量0<i x ，且i x 所在行的 所有元素都大于或等于零，则其对偶问题具有无界解。
第3章 对偶理论§3.1 线性规划的对偶理论3.1.1 对偶问题的表述对称形式的对偶：（L ） cx min (D) wb maxs.t. b Ax ≥ s.t. c wA ≤0≥x 0≥w其中c 为n 维行向量，A 为n m ⨯矩阵，b 为m 维列向量，x 表示n 维列向量，w 表示m 维行向量。
称(D)为线性规划(L)的对偶规划问题。
定理1 (L)与(D)互为对偶规划问题。
――（对合性）例 设原问题 对偶问题, 12 5 s.t.min 21212121≥≥-≥+-x x x x x x x x 0, 12 1s.t.5 max 21212121≥-≤-≤++w w w w w w w w 非对称形式的对偶：（LP ） cx min (DP) wb maxs.t. b Ax = s.t. c wA ≤ 0≥x例 设原问题 对偶问题,, 523 4 s.t.345min 321321321321≥=++=++++x x x x x x x x x x x x 342 53 s.t.54 max 21212121≤+≤+≤++w w w w w w w w 一般线性规划问题：可化为上述二者之一讨论其对偶问题，也可直接写出对偶问题，详细的对应法则见教材（陈宝林）124页。
直接写出对偶的弊端之一是对偶最优解不易确定，而对称形式和非对称形式对偶的最优解都可由原问题的单纯形乘子确定出来。
3.1.2 对偶定理(强对偶定理和弱对偶定理)定理2 (弱对偶定理)：设x 和w 分别是（L ） cx min 和 (D) wb maxs.t. b Ax ≥ s.t. c wA ≤0≥x 0≥w的可行解，则有下列不等式成立：b w xc ≥证明：由于b x A ≥和0≥w ，则有b w x A w ≥。
由于A w c ≥和0≥x ，则有x A w x c ≥。
因此有b w x c ≥推论 1 设x 和w 分别是(L)和(D)的可行解，且有b w x c =，则x 和w 分别是(L)和(D)的最优解。
推论2 如果(L)的目标函数在可行集上无下界，则对偶规划(D)无可行解。
推论3 如果(D)的目标函数在可行集上无上界，则原始规划(L)无可行解。
定理3 (强对偶定理)：如果互为对偶规划的两个问题之一有最优解，则另一个问题也有最优解，并且二者的目标值相等。
证明：设原问题（L ）存在最优解，引进松弛变量，写成等价形式：s.t. min ≥≥=-v x bv Ax cx（1）由于（1）存在最优解，因此可以用单纯形方法求出它的一个最优基本可行解，不妨设该最优解是⎥⎦⎤⎢⎣⎡=v x y ，相应的最优基是B 。
此时所有判别数均非正，即j c p w j j ∀≤- ,0 （2）1-=B c w B 为单纯形乘子。
考虑所有原来变量（不包括松弛变量）在基B 下的判别数，把它们所满足的条件（2）用矩阵形式写出：0≤-c A w 或 c A w ≤ （3）把所有松弛变量在基B 下的判别数所满足的条件（2）用矩阵形式写出：0)(≤-I w 或 0≥w （4）由（3）和（4）可知，w 是对偶问题（D ）的可行解。
由于非基变量的取值为0，以及目标函数中松弛变量的系数为0，因此有x c y c b B c b w B B B ===-1根据定理2的推论1，w 是对偶问题（D ）的最优解，且原问题和对偶问题目标函数最优值相等。
类似地可以证明，如果对偶问题存在最优解，则原问题也存在最优解，并且二者的目标值相等。
注：也可用凸集分离定理证明该结论。
但运用单纯形法证明该定理属于构造性证明，也适用于求解对偶问题。
3.1.3 互补松弛定理利用对偶定理可以证明原问题和对偶问题的最优解满足重要的互补松弛性质。
对于互为对偶的一对线性规划问题，已知一个问题的最优解时，可以利用互补松弛定理求出另一个问题的最优解。
定理4 (对称形式的互补松弛定理)：设x 和w 分别是(L)和(D)的可行解，则二者分别为最优解的充分必要条件是：0)( ,0)(=-=-x c A w b x A w用i A 表示矩阵A 的第i 行，用j p 表示矩阵A 的第j 列。
推论1 设x 和w 分别是(L)和(D)的可行解，则二者分别为最优解的充分必要条件是： (i) 对n j ,,1Λ=，若0>j x ，就有j j c p w =；若j j c p w <，就有0=j x 。
(ii) 对m i ,,1Λ=，若0>i w ，就有i i b x A =；若i i b x A >，就有0=i w 。
推论2 设x 是(L)的最优解，则w 是(D)的最优解的充要条件是：(i) 对n j ,,1Λ=，若0>j x ，就有j j c p w =；(ii) 对m i ,,1Λ=，若i i b x A >，就有0=i w 。
推论3 设w 是(D)的最优解，则x 是(L)的最优解的充要条件是：(i) 对n j ,,1Λ=，若j j c p w <，就有0=j x ;(ii) 对m i ,,1Λ=，若0>i w ，就有i i b x A =。
例： 设原问题 对偶问题,, 232 13 s.t.32 min 321321321321≥≥-+≥+-++x x x x x x x x x x x x 0, 13 32 2 3 s.t.2 max 2121212121≥≤-≤+-≤++w w w w w w w w w w 设用图解法求得对偶问题的最优解为 )711,71(),(21==w w w 则可用互补松弛定理求原问题的最优解。
由于在最优解w 处，对偶问题的第3个约束成立严格不等式，因此原问题第3个变量03=x 。
又由于w 的两个分量均大于0，因此在原问题中前两个约束在最优解处成立等式，即⎩⎨⎧=-+=+-23213321321x x x x x x 把03=x 代入上述方程组，可解得741=x ，752=x 。
原问题的最优解为T x x x x )0,75,74(),,(321==。
§3.2 非线性规划的对偶理论3.2.1 非线性规划的Lagrange 对偶问题的表述非线性规划的对偶理论不像线性规划的对偶理论简单漂亮。
可以通过多种不同的方式来构造非线性规划对偶问题，如基于Lagrange 函数，凸函数的共轭函数及K-T 最优性条件等。
不同构造方式基于的条件不同，所得结论亦有区别，从而应用场合不同。
此节以Lagrange 对偶为例，介绍非线性规划的对偶理论。
原问题：.,,1 ,0)( ,,1 ,0)( s.t.)(min D x l j x h m i x g x f j i ∈===≥ΛΛ (5) D 为n R 的子集，它的选择影响到计算和修正对偶目标函数的计算量。
令对偶目标函数（Lagrange 对偶函数）为：⎭⎬⎫⎩⎨⎧∈--=∑∑==D x x h v x g w x f v w lj j j m i i i |)()()(inf ),(11θ 对偶问题：0 s.t.),(max ≥w v w θ（6） 例：求下列问题的Lagrange 对偶问题。
2221min x x +,04 s.t.21≥-+x x.0,021≥≥x x将变量的非负限制作为集约束：⎭⎬⎫⎩⎨⎧≥≥⎥⎦⎤⎢⎣⎡=∈0,0|2121x x x x D x对偶函数：{}{}{}w x wx x x wx x x x x x w x x w 40|inf 0|inf 0,|)4(inf )(2222112121212221+≥-+≥-=≥-+-+=θ由上式可知，当0≥w 时，有w w w 421)(2+-=θ当0<w 时，由于0,21≥x x ，则有222121≥-≥-wx x wx x因此当021==x x 时，得到极小值 w w 4)(=θ综上分析，得到对偶函数：⎪⎩⎪⎨⎧<≥+-=0,40,421)(2w w w w w w θ 本例的对偶问题为s.t.421)(max 2≥+-=w w w w θ 问题的最优解和最优值为：8 ,)2 ,2(min ==f x T对偶问题的最优解和最优值为：8 ,4max ==θw问题：原问题与对偶问题解之间的关系？线性规划的弱对偶定理是否成立？线性规划的强对偶定理是否成立？原问题： .,0)( ,0)( s.t.)(min D x x h x g x f ∈=≥ 其中 ,))(,),(()(1T m x g x g x g Λ=T l x h x h x h ))(,),(()(1Λ=令T l T m v v v w w w ),,(,),,(11ΛΛ==对偶问题：s.t.),(max ≥w v w θ 其中，{}D x x h v x g w x f v w T T ∈--=|)()()(inf ),(θ原问题的可行集： {}D x x h x g R x S n ∈=≥∈= ,0)( ,0)(|对偶问题的可行集： {}0|),(≥∈=+w R v w SD l m3.2.2 对偶定理定理5（弱对偶定理）：原问题（inf ）在可行集上的目标值不小于对偶问题（sup ）在可行集上的目标值，即SD v w S x v w x f ∈∀∈∀≥),(, ),,()(θ推论1{}{};),(|),(sup |)(inf SD v w v w S x x f ∈≥∈θ 推论2 如果存在SD v w S x ∈∈),(,使得),()(v w x f θ≤ 则x 和),(v w 分别是原问题和对偶问题的最优解。
推论3如果{},|)(inf -∞=∈S x x f 则有SD v w v w ∈∀-∞=),( ,),(θ推论4如果{},),(|),(sup ∞=∈SD v w v w θ 则原问题不可行。
对偶间隙：由推论1知sup inf ϑ≥f ，若sup inf ϑ=f ，则原问题与对偶问题无对偶间隙；若sup inf ϑ>f ，则原问题与对偶问题有对偶间隙。
下面的强对偶定理表明：对凸规划，在适当的约束规格下，原问题与对偶问题不会出现对偶间隙。
定理6（强对偶定理）：设在（5）中下列条件满足：n R D ⊂ )i (非空凸，m i x g x f i ,,1 ),( ),(Λ=-是凸函数；l j x h j ,,1 ),(Λ=是线性函数。
}.|)(int{0 ,0)ˆ( ,0)ˆ( s.t. ˆ )ii (D x x h x h xg D x ∈∈=>∈∃ 则有下列结论成立：(i) {}{};),(|),(sup |)(inf SD v w v w S x x f ∈=∈θ (ii) 若{}S x x f ∈|)(inf 有限，则存在s.t. ,),(SD v w ∈{};),(|),(sup ),(SD v w v w v w ∈=θθ(iii) 若{}S x x f ∈|)(inf 有限，且存在{}S x x f x f S x ∈=∈|)(inf )( s.t. ,，则有0)(=x g w 。
