对称形式的对应关系
原问题 max z n个决策变量 m个约束条件 约束条件“≤”型
决策变量≥0
对偶问题 min w n个约束条件 m个决策变量 决策变量≥0
约束条件“≥”型
对偶问题的对偶是原问题，即对偶关系是 相互对称的关系
非对称形式下的对偶关系
原问题（对偶问题） max z n个决策变量 m个约束条件 约束条件“≤”型 约束条件“≥”型 约束条件“=”型 决策变量≥0 决策变量≤0 决策变量无约束 对偶问题（原问题） min w n个约束条件 m个决策变量 决策变量≥0 决策变量≤0 决策变量无约束 约束条件“≥”型 约束条件“≤”型 约束条件“=”型
y4 2 y1 2 y2 3 y1 y2 y3 y4 4 y3 y 4 1 y4 0
第三节 影子价格
* ( j 1 , , n ) y 设 x* 和 j i (i 1, , n) 分别是原问题和 对偶问题的最优解，则由对偶性质，有
例 用对偶单纯形法求解如下的LP问题
min z 15x1 24x2 5 x3 6 x2 x3 2 5 x1 2 x2 x3 1 x1 , x2 , x3 0
化成标准形式
m ax w 15x1 24x2 5 x3 6 x2 x3 x4 2 5 x1 2 x2 x3 x5 1 x1 , x2 , x3 0
•最优性 若原问题一个可行解目标函数等于对偶问题的 某个可行解的目标函数,则这两个可行解分别 是原问题和对偶问题的最优解 •强对偶性 若原问题和对偶问题都有可行解,则它们都有 最优解,且最优解的目标函数值相等 •互补松弛性 在线性规划问题的最优解中,如果对应某一约 束条件的对偶变量值非零,则其对应的约束条 件取等式;反之若一个约束条件为严格的不等 式,则其对应的对偶变量为零
将各约束条件两端同乘“-1”得
m ax w 15x1 24x2 5 x3 6 x2 x3 x4 2 5 x1 2 x2 x3 x5 1 x1 , x2 , x3 0
用对偶单纯形法求解得
-15 Cb Xb 0 x4 0 x5 b -2 -1 x1 0 -5 -15 x2 -6 -2 -24
CN XN
N CN CN XN B-1N CN –CBB-1N
0 XS
I 0 0 XS B-1 –CBB-1
• 在初始单纯形表中单位矩阵经过迭代后变为基 矩阵B的逆 • 在初始单纯形表给出的解中基变量Xs=b,而在迭 代后的表给出的解中基变量 XB=B-1b • 系数矩阵的变化: [A, I]B-1[A, I] • 在初始单纯形表中变量xj的系数为Pj经过迭代 后变为Pj′,并且Pj′=B-1 Pj • 若迭代后的单纯形表为最终表则题的对称形式
• 变量：所有变量均具有非负约束 • 约束条件： 最大化问题 所有约束条件都是“≤” 型的 最小化问题 所有约束条件都是“≥” 型的
对称形式下的对偶关系
项目 A b C 目标函数 约束条件 决策变量 原问题 约束条件系数矩阵 约束条件右端项向量 目标函数系数向量 max z=CX AX≤b X≥0 对偶问题 约束条件系数矩阵转置 目标函数的系数向量 约束条件的右端项向量 min w=Yb’ A’Y ≥C’ Y ≥0
单纯形法的矩阵表示
m ax z CX
AX b X 0
XB X , A B X N C CB C N N ,
max z CX 0 X s
添加松 弛变量XS
AX IX S b X 0
BX B NX N IX S b X 0, X 0 N B
• 资源的影子价格随企业的生产任务、产品结构 的改变而改变 • 影子价格是资源的边际价格 • 资源的影子价格也可视为一种机会成本 • 在生产过程中若某种资源未得到充分利用则其 影子价格为零；只有在资源得到充分利用时， 其影子价格才可能非零 • 利用影子价格可以说明：单纯形法中的检验数 可以看成生产某种产品的产值与隐含成本的差 • 可以利用影子价格确定企业内部的核算价格， 以便控制有限资源的使用和考核下属企业经营 的好坏。
y4
y5
y1 y3
0 1
对偶 问题 最终 单纯 形表
对偶问题剩余变量
y2
y3
y1
y2 y3 1/4 1/2 -5/4 15/2
y2
1 0
y4
-1/4 1/2
y5
1/4 -3/2
σj
15/2
0
0
7/2
3/2
原问题松弛变量
原问题变量
x3
x4
x5
x1
x2
原本在对偶关系中，原问题的变量对应着对偶问题 的约束条件，原问题的约束条件对应着对偶变量。 但在分别添加了松弛变量和剩余变量后，也可以建 立原问题变量与对偶问题变量之间的对应关系
max z C B X B C N X N 0 X s
将XB的系数 矩阵化为单 位矩阵
原来 BX B NX N IX S b 1 1 1 IX B B NX N B X S B b
初 始 单 纯 形 表
迭 代 后 的 单 纯 形 表
CB XB
0 XS b B CB CB XB CB XB B-1b I 0
互补松弛性的另一种表述
在线性规划问题的最优解中,如果对应某一约 束条件的对偶变量值非零,则该约束条件中松 弛变量等于零;反之若一个约束条件中松弛变 量非零,则其对应的对偶变量为零。
例（p76.7） 原问题 max z 2 x1 4 x2 x3 x4 x1 3 x2 x4 8 2 x x 6 1 2 x2 x3 x4 6 x1 x2 x3 9 x 0, j 1,2,3,4 j
问题 美佳公司愿意以多大的代价出让自己所 拥有的生产资源？
设y1,y2和y3分别表示出让资源A，B和调试 工序的单价，则美佳公司同意出让的条件 将是 同意出让生产产品I的资源 6 y 2 y3 2 同意出让生产产品II的资源 5 y1 2 y2 y3 1
购买者希望用最少的代价获得这些资源， 因此
例1
6x1+2x2 =24
资源的变化： 设备B的可用 时间从增加 一小时
Max z=2x1+x2
s.t. 5x2≤15
6x1+2x2 ≤24
x1+x2 ≤5
可行域 x2=3 最优解
x1,x2≥0
最优目标 函数值的 变化：8.5 变到8.75， 增加1/4
x1+x2 =5
参考文献：
李慧：资源影子价格分析与经营管理决策， 系统工程理论与实践，2003年4月号，22-26
对偶问题基可行解 （检验数非正）
原问题基可行 解
• 保持对偶问题有基可行解,而原问题只是 基本解,通过迭代,使后者的负分量个数减 少，一旦成为基可行解,则原问题与对偶 问题同时实现最优解.
对偶单纯形法计算步骤
• 适应于求解这样的LP问题：标准化后不 含初始基变量，但将某些约束条件两端 乘以“-1”后，即可找出初始基变量。 • 要求：初始单纯形表中的检验数满足最 优性条件
对满足上述条件的LP问题，对偶单纯形法的 步骤是： •作出初始单纯形表（注意要求） •检查b列的数据是否非负，若是，表中已经 给出最优解；否则转下一步 •确定换出变量：取b列最小的数对应的变量 为换出变量 •确定换入变量：用检验数去除以换出变量行 的那些对应的负系数，在除得的商中选取其 中最小者对应的变量为换入变量 •旋转运算。然后回到第2步。
对偶问题 min w 8 y1 6 y2 6 y3 9 y4 y4 2 y1 2 y2 3 y1 y2 y3 y4 4 y3 y 4 1 y1 y3 1 y 0, i 1,2,3,4 i 将原问题最优解X*=(2,2,4,0)代入原问题约束条件中得 第一个约束条件：2+6=8，为等式 第二个约束条件：4+2=6，为等式 第三个约束条件：2+4=6，为等式 第四个约束条件：2+2+4<9，为不等式，故y4 = 0
* z* c j x * b y i i w* j j 1 i 1
n
m
式中bi是线性规划原问题约束条件的右端 项，它代表第i种资源的拥有量；对偶变 量yi的意义代表在资源最优利用的条件下 对第i种资源的估价。这种估价不是资源 的市场价格，而是根据资源在生产中作 出的贡献而作的估价，为区别起见，称 为影子价格。
min z 15y1 24y2 5 y3
这样得到一个新的线性规划问题
min w 15y1 24y2 5 y3 6 y 2 y3 2 5 y1 2 y2 y3 1 y1 , y2 , y3 0
称这一问题是原来的LP问题的对偶线性规 划问题或对偶问题，原来的LP问题也称为 原问题。
而由x1=2>0, 得 而由x2=2>0, 得 而由x3=4>0, 得 于是得到方程组
y1 2 y2 y4 2 3 y1 y2 y3 y4 4 y3 y4 1
4 3 得对偶问题最优解为 y1 , y2 , y3 1, y4 0 5 5
注：原问题与对偶问题最优目标函数值都是 z*=4+8+4=16
0 1 0
1/4 -1 1/2 -1 1/2
例1 原问 题最 终单 纯形 表
项目
原问题变量
原问题松弛变量
x1
x3 15/2 x1 7/2 x2 3/2 - σj 0 1 0 0
x2
0 0 1 0
x3
1 0 0 0