运筹学课件对偶问题的经济解释-影子价格

§5对偶问题的经济解释—影子价格

(P)的最终单纯形表中松弛变量的检验数对应(D)的最优解。当某约束条件的右端常数增加一个单位时（假设原问题的最优基不变），原问题的目标函数最优值增加的数量。Z*=CX*=Y*b=(y1*,y2*,…,ym*)b1b2﹕﹒bm=y1*b1+y2*b2+…+ym*bm当某个右端常数bibi+1时bi+1yi*+yi*(bi+1)=Y*b+yi*=Z*+yi*第I种资源的影子价格是第i个约束条件的右端常数增加一个单位时，目标函数增加的数量甲乙可用量机械设备

128原材料A4016原材料B

0412

X(3)=(4，2，0，0,4)T，z3=14cj23000CBXBbx1x2x3x4x5203x1x5x2442100001-2½-3/2½-1/81/8010-1400-3/2-1/80经济意义：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。影子价格

产品资源ⅠⅡ现有资源数钢材12100（吨）煤22180（吨）机时16240（小时）利润（万元）13x1x2x3x4x5-zXB-13500-3/40-1/4x130103/20-1/2x45000-5/211/2x23501-1/401/4X*=(30,35,0,50,0)T,Z*=135y1*=3/4y2*=0,y3*=1/4影子价格经济意义：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。§6对偶单纯形法保持对偶可行性，逐步改进主可行性，求解主问题。当b有负分量，A中有一明显初始对偶可行基(检验数均非正)，因而易得一初始解时，可用对偶单纯形法求解。

设B为一个基基本解X（0）为基本可行解的条件？B-1b≥0X（0）为最优解的条件？原原始可行性条件原始最优性条件令Y=CBB-1，代入原始最优性条件，→YA≥C对偶可行性条件例用对偶单纯形法求解单纯形法大M法剩余变量、人工变量用（-1）乘不等式两边，再引入松弛变量。cj

-1-40-300CBXBb

x1

x2

x3

x4

x5

x600x5x6-3-2-1-21-11021-4-1010-1-40-300先选出基变量后选进基变量原问题，符合原始最优性条件，但不可行cj

-1-40-300CBXBb

x1

x2

x3

x4

x5

x6-10x1x63-812-11-100-3-2-32130-2-1-2-10cj

-1-40-300CBXBb

x1

x2

x3

x4

x5

x6-10x1x63-812-11-100-3-2-32130-2-1-2-10-10x1x37417/205/2-2-1/203/213/2-1-1/270-1/20-1/2-2-1/2最优解X*=（7，0，4，0）TZ*=-7例6用对偶单纯形法求解（P）1-4/3---10-5/21/21-1/221-1/23/20-1/20-4-10-1-8/5--22/501-1/5-2/51/511/5107/5-1/5-2/500-3/5-8/5-1/5[][]§7灵敏度分析

系数bi、cj、aij

变化，最优解的最优性、可行性是否变化？

系数在什么范围内变化，最优解或最优性不变？如何求新的最优解？本节重点7.1灵敏度分析的原理是最优解，则可行性条件最优性条件正则性

bi非基变量cj基变量cB增加新变量一个非基变量系数aij的变化，要视aij对应的变量是基变量或非基变量而定。7.2br变化的分析影响解的可行性，只要B-1(b+△b)≥0，解的可行性不变，最优性也不变。

(B-1)r

是B-1的第r列，解上述不等式，求得保持可行性不变的△br的范围。≥0例:求第一章例1中的第二个约束条件b2（=16）的变化范围b2时，计算可得

b2

-4/0.25=-16

b2

-4/0.5=-8

b2

2/0.125=16所以，b2的变化范围是[-8，16]；b2的变化范围是[8，32]。

例:第一章例1中，若设备增加4台时，求新的最优生产计划。计算:得表：用对偶单纯形法得：

X*=(4，3，2，0，0)，z*=177.3cr

变化的灵敏度分析cr

cr

+cr不影响解的可行性，影响最优性。(1)cr

为非基变量的系数(2)cr

为基变量的系数例：第一章例1中c2变化c2，问c2在什么范围内变化时最优解不变。解：对所有的非基变量当给定c2，要求新的最优解时，先求新的检验数，再用单纯形法迭代。

解得：

-3

c2

1

7.4

aij变化的灵敏度分析(1).

aij

为非基变量的系数只影响xj的检验数，从而影响最优性。

例:第一章例1，增加一种新产品Ⅲ，它的技术系数是(2，6，3)T，利润系数是5。问该厂是否应生产该产品和生产多少？

解：设新产品Ⅲ的产量为x3(对于原最优解来说是非基变量)。因

故应生产产品Ⅲ。

x3进基在最终表中的系数是：

原最终表成为：

用单纯形法求解得：(2).aij为基变量系数基变化，影响最优性、可行性。例:第一章例1，若生产产品Ⅰ的工艺结构有改进，其技术系数变为（2，5，2)T，利润系数为4，试分析对生产计划