第2章 对偶理论和灵敏度分析-第5,6节(运筹学-东北大学,钟磊钢)

运筹学(第三版)《运筹学》教材编写组 编

第2章 对偶理论 和灵敏度 分析第5节 对偶问题 的经济解 释——影 子价格

第6节对偶单纯 形法清华大学出版社钱颂迪制作

第2章 对偶理论和灵敏度分析第5节 对偶问题的经济解释 ——影子价格

在单纯形法的每步迭代中，目标函数取值 z=CBB-1b,和检验数CN-CBB-1N中都有乘子 Y=CBB-1,那么Y的经济意义是什么?

设B是{max z=CX|AX≤b,X≥0}的最优基， 由-Yb= -CB B-1b (2-12)式可知 z*=CBB-1b=Y*b 。 对z求偏导数，得

z 1 * CB B Y b*

由上式可知，变量yi*的经济意义是在其他条件 不变的情况下，单位资源变化所引起的目标函的 最优值的变化。

cjCB XB b

2 x1

3 x2

0 x3

0 x4

0 x5

θ

20 3

x1x5 x2 -z

44 2 -14

10 0 0

00 1 0

0-2 1/2

1/41/2 -1/8

01 0 0

-3/2 -1/8

y1*=1.5,y2*=0.125,y3*=0。 这说明是其他条件不变的情况下，若设备增加一台时， 该厂按最优计划安排生产可多获利1.5元；原材料A增 加1kg,可多获利0.125元；原材料B增加1kg,对获利 无影响。 从图2-1可看到，设备增加一台时，代表该约束条件 的直线由①移至①′,相应的最优解由(4,2)变为(4, 2.5),目标函数z=2×4+3×2.5=15.5,即比原来的增 大1.5。又若原材料A增加1kg时，代表该约束方程的 直 线 由 ② 移 至 ② ′ , 相 应 的 最 优 解 从 (4 , 2) 变 为 (4.25 , 1.875) , 目 标 函 数 z= 2 ×4.25+3×1.875=14.125。比原来的增加0.125。原 材料B增加1kg时，该约束方程的直线由③移至③′, 这时的最优解不变。

图2-1

yi*的值代表对第i种资源的估价-影子价格。 这种估价是针对具体工厂的具体产品而存在的一种特 殊价格，称它为“影子价格”。在该厂现有资源和现 有生产方案的条件下，设备的每小时租费为1.5元， 1kg原材料A的出让费为除成本外再附加0.125元，1kg 原材料B可按原成本出让，这时该厂的收入与自己组织 生产时获利相等。影子价格随具体情况而异，在完全 市场经济的条件下，当某种资源的市场价低于影子价 格时，企业应买进该资源用于扩大生产；而当某种资 源的市场价高于企业影子价格时，则企业的决策者应 把已有资源卖掉。可见影子价格对市场有调节作用。

第6节

偶单纯形法

前节讲到原问题与对偶问题的解之间的对应关 系时指出：在单纯形表中进行迭代时，在b列 中得到的是原问题的基可行解，而在检验数行 得到的是对偶问题的基解。 通过逐步迭代，当在检验数行得到对偶问题的 解也是基可行解时，根据性质(2)、(3)可知，已 得到最优解。即原问题与对偶问题都是最优解。

根据对偶问题的对称性 可以这样考虑：若保

持对偶问题的解是 基可行解，即cj-CBB-1Pj≤0,而原问题在 非可行解的基础上，通过逐步迭代达到 基可行解，这样也得到了最优解。 其优点是原问题的初始解不一定是基可 行解，可从非基可行解开始迭代。 方法如下：

设原问题max z=CX AX=b X≥0

又设B是一个基。 不失一般性，令B=(P1 ,P2 ,…,Pm),它对应 的变量为 XB=(x1,x2,…,xm) 当非基变量都为零时，可以得到XB=B-1b。若 在B-1b中至少有一个负分量，设(B-1b)i<0,并 且在单纯形表的检验数行中的检验数都为非正， 即对偶问题保持可行解，它的各分量是

(1) 对应基变量x1,x2,…,xm的检验数是 σ i=ci-zi=ci-CBB-1Pj=0,i=1,2,…,m (2) 对应非基变量xm+1,…,xn的检验数是 σ j=cj-zj=cj-CBB-1Pj≤0,j=m+1,…,n

每次迭代是将基变量中的负分量xl 取出， 去替换非基变量中的xk ,经基变换，所 有检验数仍保持非正。从原问题来看， 经过每次迭代，原问题由非可行解往可 行解靠近。当原问题得到可行解时，便 得到了最优解。

对偶单纯形法的计算步骤如下： (1) 根据线性规划问题，列出初始单纯形 表。 检查b列的数字，若都为非负，检验 数都为非正，则已得到最优解。停止计 算。 若检查b列的数字时，至少还有一个 负分量，检验数保持非正，那么进行以 下计算。

(2) 确定换出变量

按min{(B-1b)i|(B-1b)i<0=(B-1b)l对应的基变量 xi为换出变量 (3) 确定换入变量 在单纯形表中检查xl所在行的各系数α lj(j=1,2,…, n)。若所有α lj≥0,则无可行解，停止 计算。

若存在α lj<0 (j=1,2,…,n), 计算

cj zj ck z k min alj 0 j alj alk 按θ 规则所对应的列的非基变量xk为换入变量， 这样才能保持得到的对偶问题解仍为可行解。

(4) 以α lk为主元素，按原单纯形法在表 中进行迭代运算，得到新的计算表。 重复步骤(1)~(4)。