窗含西岭千秋雪，门泊东吴万里船 对偶是一种普遍现象 第四章　对偶原理 窗含西岭千秋雪，门泊东吴万里船 对偶是一种普遍现象

甲　乙　丙　丁 材料 产品 ３　２　１　１ ４　１　３　２ ２　２　３　４ A B C 每台 收益 2000 4000 3000 限额 600 400 200 300 x1 x2 x3 y1　y2　y3　y4 假设工厂考虑不进行生产而把全部可利用的资源都让给其他企业，工厂希望给这些资源定出一个合理的价格，即使别的单位愿意购买，又使本工厂能得到生产这些产品所能获得的最大收益。

二、对偶问题的表达 （1）对称LP问题的定义 第一类对称形式 第二类对称形式 （2）对称LP问题的对偶问题 (D) (L)

例1：写出下列LP问题的对偶问题 对偶

（3）对偶问题的对偶 推导过程 (D) 变形

对偶 变形 (DD) 结论：对偶问题的对偶为原问题。

例2： 写出下列LP问题的对偶问题：

写出对称形式的对偶规划的要点： (1) min变成max (2) 价值系数与右端向量互换 (3) 系数矩阵转置 (4) ≥ 变 ≤ (2) 价值系数与右端向量互换 (3) 系数矩阵转置 (4) ≥ 变 ≤ 原问题中约束条件的个数=对偶问题中变量的个数 原问题中变量的个数=对偶问题中约束条件的个数

非对称形式的对偶 写成对称形式 对偶问题为：

例 min 5x1+4x2+3x3 s.t. x1+x2+x3=4 3x1+2x2+x3 =5 x1 ≥ 0, x2 ≥0, x3 ≥0 对偶问题为 max 4w1+5w2 s.t. w1+3w2≤5 w1+2w2 ≤ 4 w1+w2 ≤ 3

一般情形LP问题的对偶问题 min cx s.t. A1x ≥b1 A1 为m1×n , b1为m1×1 引入松弛变量 s.t. A1x –xs =b1 xs为m1×1 A2x =b2 A3x +xt = b3 xt为m3×1 x, xs , xt ≥0

min cx s.t. A1x –xs =b1 xs为m1×1 A2x =b2 A3x +xt = b3 xt为m3×1 x, xs , xt ≥0 对偶问题为 max w1b1+ w2b2 + w3b3 s.t. w1A1+ w2A2 + w3A3 ≤c – w1Is ≤0 w3It ≤0 w1 ≥ 0, w3 ≤0

min max 变 ≥0 ≤ 约 量 ≤0 ≥ 束 无限制 = 方 程 约 ≥ ≥0 束 ≤ ≤0 变 方 = 无限制 量

直接写出LP问题的对偶问题 例3

第二节 对偶问题的基本性质 原问题(L) 对偶问题(D) min cx max wb s.t. Ax ≥ b s.t. wA ≤ c x ≥ 0 w ≥ 0

定理1：弱对偶定理

例： （LP） 1）原问题任一可行解 x=(1, 1)T 目标值 =40 40是DLP问题最优目标值的上界. 2）对偶问题任一可行解 w=（1 1 1 1） 目标值 =10 10是LP问题最优目标值的下界.

推论1： 若LP(或DLP)问题有无界解，则其对偶问题(或原问题)无可行解； 若LP (或DLP)问题无可行解，则对偶问题(或原问题)或者无可行解,或者目标函数值趋于无穷。 推论2： 极大化问题的任何一个可行解所对应的目标 函数值都是其对偶问题的目标函数值的下界。 推论3： 极小化问题的任何一个可行解所对应的目标 函数值都是其对偶问题的目标函数值的上界。

定理2：最优性准则 证明：

例5

若(L),(D)均有可行解,则(L),(D)均有最 优解,且(L),(D)的最优目标函数值相等. 定理3：强对偶定理 若(L),(D)均有可行解,则(L),(D)均有最 优解,且(L),(D)的最优目标函数值相等. 证明：

(L) 引入剩余变量，把(L)化为标准形．

推论： 在用单纯形法求解LP问题（L）的最优单纯 形表中松弛变量的检验数的相反数(单纯形 乘子w=cBB-1)就是其对偶问题（D）的最优解

方法 由于(L) 化成标准形式时,松弛变量xn+j对应的列为-ej，它在目标函数中的价格系数＝０，所以， 判别数＝cBB-1(-ej)-0=-wj 则松弛变量对应的判别数均乘以(-1)，变得到单纯形乘子w=(w1,…,wm). 当原问题达最优时,单纯形乘子即为对偶问题的最优解.

例5 求下列问题对偶问题的最优解 解：化为标准型

x1 x2 x3 x4 x5 1 2 1 0 0 4 0 0 1 0 0 4 0 0 1 -2 -3 0 0 0 x3 x4 x5 8 16 12 4 1 0 1 0 -1/2 4 0 0 1 0 0 1 0 0 1/4 -2 0 0 0 3/4 x3 x4 x2 2 16 3 9 1

x1 x2 x3 x4 x5 1 0 1 0 -1/2 0 0 -4 1 2 0 1 0 0 1/4 0 0 2 0 -1/4 x1 x4 x2 2 8 3 13 2 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 0 x1 x5 x2 4 2 14 此时达到最优解。x*=(4,2), MaxZ=14。

(L) (DL)

小结 原问题(min) 对应关系 对偶问题(max) 有最优解 有最优解 不可行 无界解 无界解 不可行

x1 x2 l1 l2 （无可行解） w1 w2 l2 l1 （无可行解）

l2 x1 x2 l1 z （无界解） y1 y2 l1 l2 （无可行解）

定理4：互补松驰定理

证明：（必要性）

证明：（充分性）　

定理4’：互补松驰定理(非对称形式）

例6 考虑下面问题

解: 则， 好

考虑在最优解处,右端项bi的微小变动对目标函数值的影响. 对偶问题的经济学解释：影子价格 1、定义 2、含义 考虑在最优解处,右端项bi的微小变动对目标函数值的影响.

若把原问题的约束条件看成是广义的资源约束,则右端项的值表示每种资源的可用量. 对偶解的经济含义:资源的单位改变量引起目标函数值的增加量. 通常称对偶解为影子价格. 影子价格的大小客观地反映了资源在系统内的稀缺程度.资源的影子价格越高,说明资源在系统内越稀缺,而增加该资源的供应量对系统目标函数值贡献越大.

0 0 2 24 1440 木门 木窗 木工 4小时 3小时 120小时/日 油漆工 2小时 1小时 50小时/日 收入 56 30 木门 木窗 木工 4小时 3小时 120小时/日 油漆工 2小时 1小时 50小时/日 收入 56 30 解：设该车间每日安排 x1 x2 x3 x4 生产木门x1扇，木窗x2。 x3 4 3 1 0 120 max z=56 x1 +30 x2 x4 2 1 0 1 50 s.t. 4 x1 +3 x2≤120 -56 -30 0 0 0 2 x1 + x2 ≤50 x3 0 1 1 -2 20 x1 x2 ≥0 x1 1 1/2 0 1/2 25 0 -2 0 28 1400 x2 0 1 1 -2 20 x1 0 0 -1/2 -1/2 15 0 0 2 24 1440 对偶问题的解为: w*=(2, 24)

3、影子价格的作用 （1）告诉管理者增加何种资源对企业更有利 （2）告诉管理者花多大代价购买进资源或卖出资源是合适的 （3）为新产品定价提供依据

对偶单纯形法 定义：设x(0)是(L)的一个基本解（不一定是可行解），它对应的矩阵为B，记w=cBB-1，若w是(L)的对偶问题的可行解，即对任意的j, wPj-cj ≤0，则称x(0)为原问题的对偶可行的基本解。 结论：当对偶可行的基本解是原问题的可行解时，由于判别数≤0，因此，它就是原问题的最优解。

基本思想： 从原问题的一个对偶可行的基本解出发； 求改进的对偶可行的基本解：每个对偶可行的基本解x=(xBT,0)T对应一个对偶问题的可行解w=cBB-1，相应的对偶问题的目标函数值为wb=cBB-1b，所谓改进的对偶可行的基本解，是指对于原问题的这个基本解，相应的对偶问题的目标函数值wb有改进（选择离基变量和进基变量，进行主元消去）； 当得到的对偶可行的基本解是原问题的可行解时，就达到最优解。

与原单纯形法的区别： 原单纯形法保持原问题的可行性，对偶单纯形法保持所有检验数wPj-cj ≤0，即保持对偶问题的可行性。 特点：先选择出基变量，再选择进基变 量。

步骤： 1. 化标准型,建立初始单纯形表 3、换基迭代 (若所有yrj≥0,则该LP无可行解） 4、回到第2步

x1 x2 x3 x4 x5 -3 -1 -1 1 0 1 -4 -1 0 1 -1 -1 -1 0 0 x4 x5 -1 -2 -4 -13/4 0 -3/4 1 -1/4 -1/4 1 1/4 0 -1/4 -5/4 0 -3/4 0 -1/4 x4 x2 -1/2 1/2 -13/4 1 0 3/13 -4/13 1/13 0 1 4/13 -1/13 -3/13 0 0 -6/13 -5/13 -2/13 x1 x2 2/13 7/13 9/13

用对偶单纯形法求解下列LP问题 解：原问题变形为

x1 x2 x3 x4 x5 x6 -1 1 -1 1 0 0 1 1 2 0 1 0 0 -1 1 0 0 1 x4 x5 x6 -1 -2 -3 0 0 0 -4 8 -2 -1 1 -1 1 -1 0 0 0 2 1 1 1 0 0 -1 1 0 0 1 x1 x5 x6 0 -3 -2 -1 0 0 4 -2 -1 1 0 0 -1 0 -1 0 0 3 1 1 2 0 1 -1 0 0 -1 x1 x5 x2 0 0 -5 -1 0 -3 6 2 10

关于初始对偶可行的基本解 min cx s.t. Ax=b x ≥0 若初始对偶可行的基本解不易直接得到，则解一个扩充问题，通过这个问题的求解，给出原问题的解答。

方法 附加人工约束

x1 x2 x3 x4 x5 x1 x2 x3 1 0 0 1 -2 0 1 0 -3 1 0 0 1 -1 -1 0 0 0 2 -4 2 3 -2 显然， （2，3，-2，0，0） 不是对偶可行解， 所以加一个约束

方法一 x1 x2 x3 x4 x5 x6 x1 x2 x3 x6 1 0 0 1 -2 0 0 1 0 -3 1 0 0 0 1 -1 -1 0 0 0 0 1 1 1 0 0 0 2 -4 0 2 3 -2 M 1 1 0 0 0 -3 -1 0 1 0 0 4 3 0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 -6 -2 x1 x2 x3 x4 2-M 3+3M M-2 M -2M -1 最优解为 (0,9,0,2,0) 最优值=-4 -2 0 0 0 0 0 -4 -1 0 0 0 3 1 3 1 0 0 -5 0 1 0 1 0 -3 0 1 0 0 1 -2 0 x6 x2 x3 x4 M-2 9 2

x1 x2 x3 x4 x5 x6 方法二 x1 x2 x3 x6 x1 x2 x3 x4 x5 x2 x3 x4 1 0 0 1 -2 0 2 3 -2 M 0 1 0 -3 1 0 0 0 1 -1 -1 0 0 0 0 1 1 1 1 0 0 0 2 -4 0 x1 x2 x3 x4 1 0 0 0 -3 -1 -3 2-M 3+3M M-2 M 0 1 0 0 4 3 0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 -6 -2 -2M x5 x2 x3 x4 -1/3 0 0 0 1 1/3 (M-2)/3 17/3+5M/3 M-2 2/3+2M/3 -4/3 1 0 0 0 5/3 0 0 1 0 0 1 1/3 0 0 1 6 2/3 -2 0 0 0 0 0 -4

扩充问题有最优解 最优值=-4 原问题最优解为 原问题最优值=-4 最优值=-4

用对偶单纯形法解下列问题

最优表为: 扩充问题的最优解是:

原始-对偶算法 基本思想： 从对偶问题的一个可行解开始，同时计算原问题和对偶问题，试图求出原问题的满足互补松弛条件的可行解。

原问题： 对偶问题：

限定原始问题 Restricted primal problem 人工变量

限定原始问题的对偶问题

由于对偶问题无上界，所以原问题无可行解。

计算步骤

限定原始问题目标函数值 对偶问题函数值f=wb 对偶问题可行解为w时所有的wpj-cj

用原始-对偶算法解下列问题 解：对偶问题为

限定原始问题为：

△

4 2 3 1 8 5 - y x △ 1

4 2 3 1 -2 -1 - y x △

△ １ △