max Z ' 4 x1 x 2 3 x 3 0 x 4 0 x 5 x1 x 2 x 3 x 4 5 st . x1 x 2 4 x 3 x 5 3 x ,x ,x ,x ,x 0 1 2 3 4 5
运筹学教程
CB =（C2，C1） =（30，50）
运筹学教程
线性规划的对偶理论

影子价格 王老板的家具生产模型的图解： x2 2x1+ x2 = 50
（P）max Z = 50x1+30x2 s.t. 4x1+ 3x2 ≤ 120 2x1+ x2 ≤ 50 x1，x2 ≥ 0 Z*=1350 Y*=(5,15)
j 1
若 a ij x j bi , 有 y i 0
j 1
n
运筹学教程
特点5、从影子价格考察单纯形表的计算。

j
c j C B B Pj c j
1
a
i 1
m
ij
yi
Cj代表第j种产品的产值，
a
i 1
m
ij
yi
是生产该种产品所消耗各项资源的影子价格的总和，即产品的 隐含成本。
j
a rj
cs zs 0 a rs
（最小比值原则） ，则选 x s 为换入变量，相
应的列为主元列，主元行和主元列交叉处的
元素 a rs 为主元素。
运筹学教程
(c j z j ) (c j z j )
'
a rj a rs
(c s z s )
a rj [
运筹学教程
线性规划的对偶理论

影子价格的特点：
特点2、影子价格是一种边际价值，其与经济学中的边际成本的概念相同。因 而，在经济管理有中十分重要的应用价值。企业管理者可以根据资源在企业 内部的影子价格的大小决定企业的经营策略。影子价格yi相当于在资源得到 最优利用的生产条件下，资源bi每增加一个单位，目标函数z 的增量。 特点3、影子价格的大小客观地反映资源在系统内的稀缺程度。如果某种资 源在系统内供大于求，尽管它有实实在在的市场价格，但它在系统内的影子 价格却为零，而影子价格越高，资源在系统内越稀缺。
运筹学教程
所有检验数≤0意味着
CN CBB
1
N 0Y AC
T
，
说明原问题的最优基也是对偶问题的可行基。 换言之，当原问题的基B既是原可行基又是 对偶可行基时，B成为最优基。 补充定理 B是线性规划的最优基的充要条 件是，B是可行基，同时也是对偶可行基。
运筹学教程
单纯形法的求解过程就是： 在保持原问题可行的前提下（b列保持≥0）， 通过逐步迭代实现对偶可行（检验数行≤0） 。 2、 对偶单纯形法思想： 换个角度考虑LP求解过程：保持对偶可行 的前提下（检验数行保持≤0） ，通过逐步迭 代实现原问题可行（b列≥0，从非可行解变 成可行解）。
基变换：
先确定换出变量——bi中的负元素（一般 选最小的负元素）对应的基变量出基； 即
i
b r min b i b i 0 , 则选 x r出基，
Hale Waihona Puke 相应的行为主元行。
运筹学教程
然后确定换入变量——原则是：在保持对偶 可行的前提下，减少原问题的不可行性。 如果
cj z min j a rj
1355=50x1+30x2
2x1+ x2 = 51
P
1365=50x1+30x2
4x1+3x2 = 121 x1 4x1+3x2 = 120
可行域
L0： 50x1+30x2
运筹学教程
线性规划的对偶理论

影子价格的特点：
影子价格是对偶解的一个十分形象的名称，它既表明对 偶解是对系统内部资源在当前的最优利用配置下的一种客观估 价，又表明它是一种虚拟的价格（或价值的影象）而不是真实 的价格。 特点1、影子价格是对系统资源的一种内部最优估价，只 有当系统 达到最优状态时才可能赋予资源这种价值。 系统资源的一种动态价格体系，影子价格的大小与系统 的价值取向有关，并受系统状态变化的影响。系统环境的任何 变化都可能会引起影子价格的变化。
当影子价格高于市场价格，应该买进资源； 当影子价格低于市场价格，应该卖出资源；
设备A:y1=0 设备B:y2=0.25 调试C:y3=0.5
运筹学教程
特点4、表明生产过程中该种资源的影子价格不等于0，表明 生产过程中资源得到充分利用。 如果某种资源未得到充分利用，该种资源的影子价格=0；
n
若 y i 0 , 有 a ij x j b i
1 2 3 2 3 4 1 2 3 5 1 5
4
0 y5

Cj CB 0 0 基 b y4 -2 y5 -1 Cj-Zj
-15 y1 0 -5 -15 0 -5 -15 -5/4 15/2 -15/2
-24 y2 [-6] -2 -24 1 0 0 1 0 0
-5 y3 -1 -1 -5
0 y4 1 0 0
5/2 -3/2
0 x4
-1/2 -1/2
0 x5
1/2 -1/2
基
x2 x1
x1
0 1
Cj-zj
0
0
-13/2 -5/2
-3/2
X=(4,1,0)T,最优值z=17
运筹学教程


小结 1.影子价格 2.对偶单纯形法
作业: 2.9(1)

0 y5 0 1 0 0 1 0 1/4 -3/2 -3/2
-24 y2 1/3 0 y5 -1/3 Cj-Zj -24 y2 1/4 -5 y3 1/2 Cj-Zj
1/6 -1/ 6 [-2/3] -1/3 -1 -4 0 1 0 -1/ 4 1/2 -7/2
运筹学教程
对偶单纯形法求解线性规划问题时，当使用 约束条件为“大于等于”，不必引进人工变 量，计算简化。
运筹学教程
二、对偶单纯形法的计算步骤： ①建立初始单纯形表，计算检验数行。
bi≥0——已得最优解； 检验数全部≤0 （非基变量检验数<0）
bi至少一个元素<0,转下步;
bi≥0——原始单纯形法； 至少一个检验数>0 bi至少一个元素<0,另外处理； (原问题、对偶问题均无可行解 ，引进人工变量)
运筹学教程
（15，20）
P
1350=50x1+30x2
可行域
4x1+3x2 = 120 x1
L0： 50x1+30x2
运筹学教程
线性规划的对偶理论

影子价格的直观含义： x2 2x1+ x2 = 50
（P）max Z = 50x1+30x2 s.t. 4x1+3x2 ≤ 120 2x1+ x2 ≤ 50 x1，x2 ≥ 0 Z*=1350 Y*=(5,15)
运筹学教程
3、对偶单纯形法的实施
（1）使用条件： ①检验数全部≤0；
②解答列bi至少一个元素 < 0； （2 ）实施对偶单纯形法的基本原则：
在保持对偶可行的前提下进行基变换——每一次 迭代过程中取出基变量中的一个负分量作为换 出变量去替换某个非基变量（作为换入变量）， 使原问题的非可行解向可行解靠近。
当产品产值大于隐含成本时，表明生产该产品有利。 当产品产值小于隐含成本时，表明用资源生产别的产品有利。
运筹学教程
第四节 对偶单纯形法
一、对偶单纯形法的基本思路 对偶单纯形法是应用对偶原理求解线性 规划的一种方法——在原问题的单纯形表 上进行对偶处理。
注意：不是解对偶问题的单纯形法！
运筹学教程
1、 单纯形法求解 初始可行基（对应一个初始基可行解） →迭代→另一个可行基（对应另一个基可行 解），直至所有检验数≤0为止。
化为 6 y2 y3 2 5 y 1 2 y 2 y 3 1 标准型 s .t . y1 , y 2 y 3 0
将2个等式约束 MaxZ 15 y 24 y 5 y 0 y 两边分别乘以-1， 6 y y y 2 然后列表求解如 5 y 2 y y y 1 s .t . 下： y , , y 0
Cj CB 基 b
-4 x1
-1 x2
-3 x3
0 x4
0 x5
0
0
x4
x5 Cj-zj
-5
-3
-1
-1 -4
-1
1 -1 1
-1
4 -3 1
1
0 0 -1
0
1 0 0
-1
x2
5
1
0
x5
Cj-zj
-8
-2
-3
0
0
3
-2
1
-1
1
0
运筹学教程
Cj CB
-4 -1
-4 b
1 4
-1 x2
1 0
-3 x3
cj zj a rj

cs zs a rs
] a rj [ min ] 0
分析： a rj
cj zj cs zs 0， 0； a rs 0 主元素， 0 a rj a rs cj zj a rj 0， min cs zs a rs 0
a rj 0，
运筹学教程
按主元素进行换基迭代，将主元素变成 1，主元列变成单位向量，得到新的单纯形表。 继续以上步骤，直至求出最优解。
运筹学教程
举例——用对偶单纯形法求解LP：
MinW 15 y 1 24 y 2 5 y 3