对偶性及对偶单纯形法

1、2-4 2-4 对偶性及对偶单纯形法对偶性及对偶单纯形法 序号食 品 名称热 量（千卡）蛋 白 质（克）钙（毫克）价格（元）1猪肉100050400142鸡蛋8006020063大米9002030034白菜200105002线性规划的原问题与对偶问题的变换规则表： 原问题与对偶问题解的对应关系原问题与对偶问题解的对应关系对对对对偶偶偶偶问问问问题题题题问问问问题题题题与与与与解解解解的的的的状状状状态态态态有有最最优优解解 无无 界界 无无可可行行解解有有最最优优解解一一定定不不可可能能不不可可能能无无 界界不不可可能能不不可可能能可可能能原原问问题题无无可可行行解解不不可可能能可可能能可可能

2、能 对偶单纯形法计算步骤如下： 步骤步骤1 确定原问题（L）的初始基B，使所有检验数 ，即Y=CBB-1是对偶可行解，建立初始单纯形表。 步骤步骤2 检查基变量的取值，若XB=B-1b0，则已得最优解，计算停；否则求 min(B-1b)i(B-1b)i0=(B-1b)确定单纯形表第L行对应的基变量为旋出变量。 步骤步骤3 3 若所有aj0,则原问题无可行解，计算停；否则，计算 =minj / aj aj 0 =k/ak确定对应的xk为旋入变量。 步骤步骤4 以ak为主元作（L，K）旋转变换，得新的单纯形表，转步骤2。 可以证明，按上述方法进行迭代，所得解始终是对偶可行解。 0PBC-Cj1Bj

3、jCj -1 -4 0 -3 0 0 CB XB x1 x2 x3 x4 x5 x6 b 0 x5 -1 -2 1 -1 1 0 -3 0 x6 2 1 -4 -1 0 1 -2 -1 -4 0 -3 0 0 0 x5C j -1 -4 0 -3 0 0 CB XB x1 x2 x3 x4 x5 x6 b 0 x5 -1 -2 1 -1 1 0 -3 0 x6 2 1 -4 -1 0 1 -2 -1 -4 0 -3 0 0 0 x5x1，Cj -1 -4 0 -3 0 0 CB XB x1 x2 x3 x4 x5 x6 b 0 x5 -1 -2 1 -1 1 0 -3 0 x6 2 1 -4

4、-1 0 1 -2 -1 -4 0 -3 0 0 0 C j -1 -4 0 -3 0 0 CB XB x1 x2 x3 x4 x5 x6 b 0 x5 1 2 -1 1 -1 0 3 0 x6 2 1 -4 -1 0 1 -2 -1 -4 0 -3 0 0 0 C j -1 -4 0 -3 0 0 CB XB x1 x2 x3 x4 x5 x6 b -1 X1 1 2 -1 1 -1 0 3 0 x6 0 -3 -2 -3 2 1 -8 Cj -1 -4 0 -3 0 0 CB XB x1 x2 x3 x4 x5 x6 b -1 X1 1 2 -1 1 -1 0 3 0 x6 0 -3 -2

5、 -3 2 1 -8 0 -2 -1 -2 -1 0 -3 C j -1 -4 0 -3 0 0 CB XB x1 x2 x3 x4 x5 x6 b -1 x1 1 2 -1 1 -1 0 3 0 x6 0 -3 -2 -3 2 1 -8 0 -2 -1 -2 -1 0 -3 C j -1 -4 0 -3 0 0 CB XB x1 x2 x3 x4 x5 x6 b -1 X1 1 2 -1 1 -1 0 3 0 x6 0 -3 -2 -3 2 1 -8 0 -2 -1 -2 -1 0 -3 C j -1 -4 0 -3 0 0 CB XB x1 x2 x3 x4 x5 x6 b -1 X1 1

6、 2 -1 1 -1 0 3 0 x6 0 3/2 1 3/2 -1 -1/2 4 Cj -1 -4 0 -3 0 0 CB XB x1 x2 x3 x4 x5 x6 b -1 X1 1 7/2 0 5/2 -2 -1/2 7 0 X3 0 3/2 1 3/2 -1 -1/2 4 Cj -1 -4 0 -3 0 0 CB XB x1 x2 x3 x4 x5 x6 b -1 X1 1 7/2 0 5/2 -2 -1/2 7 0 X3 0 3/2 1 3/2 -1 -1/2 4 0 -1/2 0 -1/2 -2 -1/2 -7 C j -1 -2 0 0 0 CB XB x1 x2 x3 x4 x

7、5 b 0 X4 1 -2 1 1 0 -1 0 X5 1 2 -1 0 1 -6 -1 -2 0 0 0 0 Cj -1 -2 0 0 0 CB XB x1 x2 x3 x4 x5 b 0 X4 1 -2 1 1 0 -1 0 X5 1 2 -1 0 1 -6 -1 -2 0 0 0 0 Cj -1 -2 0 0 0 CB XB x1 x2 x3 x4 x5 b 0 X4 1 -2 1 1 0 -1 0 X5 1 2 -1 0 1 -6 -1 -2 0 0 0 0 Cj -1 -2 0 0 0 CB XB x1 x2 x3 x4 x5 b 0 X4 -1/2 1 -1/2 -1/2 0 1/

8、2 0 X5 1 2 -1 0 1 -6 -1 -2 0 0 0 0 Cj -1 -2 0 0 0 CB XB x1 x2 x3 x4 x5 b 0 X4 -1/2 1 -1/2 -1/2 0 1/2 0 X5 2 0 0 1 1 -7 Cj -1 -2 0 0 0 CB XB x1 x2 x3 x4 x5 b -2 X2 -1/2 1 -1/2 -1/2 0 1/2 0 X5 2 0 0 1 1 -7 -2 0 -1 -1 0 -1 例2-11 用对偶单纯形法求解下述问题 minZ=12x1+8x2+16x3 +12x4 2x1+ x2 +4x3 2 2x1+2x2+4x4 x1,x2,x3

9、,x40 解：令 =-Z，则问题可变为 max =-12x1-8x2-16x3-12x4 - 2x1- x2 -4x3 +x5 =-2 -2x1-2x2 -4x4 x6=- x1,x2,x3,x4,x5,x60 取B=（P5,P6）为初始基，易见所有检验数j0，从而可建立单纯形表，计算结果如下： ZZC -12 -8 -16 -12 0 0CBXBB-1b X1 X2 X3 X4 X5 X600X5X6-2-3 -2 -1 -4 0 1 0 -2 -2 0 -4 0 1 -12 -8 -16 -12 0 00-12X5X4-23/4 -2 -1 -4 0 1 0 1/2 1/2 0 1 0 -

10、1/4 -6 -2 -16 0 0 -3-8-12X2X42-1/4 2 1 4 0 -1 0-1/2 0 -2 1 1/2 -1/4 -2 0 -8 0 -2 -3-8-12X2X111/2 0 1 -4 4 1 -1 1 0 4 -2 -1 1/2 0 0 0 -4 -4 -2L=2，K=4L=1，K=2L=2，K=1最优解：X1=1/2，X2=1，X3=X4=0,minZ=14 本例如果用单纯形法计算，确定初始基可行解时需引入两个人工变量，计算量要多于对偶单纯形法。一般情况下，如果问题能够用对偶单纯形法计算，计算量会少于单纯形法。但是，对偶单纯形法并不是一种普遍算法，它有一定的局限性，不

11、是任何线性规划问题都能用对偶单纯形法计算的。当线性规划问题具备下面条件时，可以用对偶单纯形法求解： 问题标准化后，价值系数全非正； 所有约束全是不等式。原始数据表原始数据表肥肥肥肥料料料料数数数数量量量量成成成成分分分分甲甲甲甲乙乙乙乙丙丙丙丙丁丁丁丁需需需需要要要要量量量量（公公公公斤斤斤斤氮氮0 0. .0 03 3 0 0. .3 30 00 0. .1 15 53 33 3磷磷0 0. .0 05 50 00 0. .2 20 0. .1 12 24 4钾钾0 0. .1 14 40 00 00 0. .0 07 74 42 2每每每每公公公公斤斤斤斤价价价价格格格格（元元元元）4 4

12、1 15 51 10 01 13 3Cj -4 -15 -10 -13 0 0 0 CB XB x1 x2 x3 x4 x5 x6 x 7 b 0 x 5 -0.03 -0.3 0 -0.15 1 0 0 -33 0 x 6 -0.05 0 -0.2 -0.10 0 1 0 -24 0 x 7 -0.14 0 0 -0.07 0 0 1 -42 -4 -15 -10 -13 0 0 0 0 Cj -4 -15 -10 -13 0 0 0 CB XB x1 x2 x3 x4 x5 x6 x 7 b 0 x 5 -0.03 -0.3 0 -0.15 1 0 0 -33 0 x 6 -0.05 0

13、-0.2 -0.10 0 1 0 -24 0 x 7 1 0 0 0.5 0 0 -7.14 300 -4 -15 -10 -13 0 0 0 0 Cj -4 -15 -10 -13 0 0 0 CB XB x1 x2 x3 x4 x5 x6 x 7 b 0 x 5 0 -0.3 0 -0.135 1 0 -0.21 -24 0 x 6 -0.05 0 -0.2 -0.10 0 1 0 -24 0 x 7 1 0 0 0.5 0 0 -7.14 300 -4 -15 -10 -13 0 0 0 0 Cj -4 -15 -10 -13 0 0 0 CB XB x1 x2 x3 x4 x5 x6

14、x 7 b 0 x 5 0 -0.3 0 -0.135 1 0 -0.21 -24 0 x 6 0 0 -0.2 -0.075 0 1 -0.36 -9 -4 x 1 1 0 0 0.5 0 0 -7.14 300 -1200 Cj -4 -15 -10 -13 0 0 0 CB XB x1 x2 x3 x4 x5 x6 x 7 b 0 x 5 0 -0.3 0 -0.135 1 0 -0.21 -24 0 x 6 0 0 -0.2 -0.075 0 1 -0.36 -9 -4 x 1 1 0 0 0.5 0 0 -7.14 300 0 -15 -10 -11 0 0 -29.56 -1200

15、 Cj -4 -15 -10 -13 0 0 0 CB XB x1 x2 x3 x4 x5 x6 x 7 b -15 x 2 0 1 0 0.45 -3.33 0 0.7 80 0 x 6 0 0 -0.2 -0.075 0 1 -0.36 -9 -4 x 1 1 0 0 0.5 0 0 -7.14 300 0 0 -10 -11 0 0 -29.56 -2400 Cj -4 -15 -10 -13 0 0 0 CB XB x1 x2 x3 x4 x5 x6 x 7 b -15 x 2 0 1 0 0.45 -3.33 0 0.7 80 0 x 6 0 0 -0.2 -0.075 0 1 -0

16、.36 -9 -4 x 1 1 0 0 0.5 0 0 -7.14 300 0 0 -10 -11 0 0 -29.56 -2400 Cj -4 -15 -10 -13 0 0 0 CB XB x1 x2 x3 x4 x5 x6 x 7 b -15 x 2 0 1 0 0.45 -3.33 0 0.7 80 -10 x 3 0 0 1 0.375 0 -0.5 0.17 45 -4 x 1 1 0 0 0.5 0 0 -7.14 300 -2850 Cj -4 -15 -10 -13 0 0 0 CB XB x1 x2 x3 x4 x5 x6 x 7 b -15 x 2 0 1 0 0.45

17、-3.33 0 0.7 80 -10 x 3 0 0 1 0.375 0 -0.5 0.17 45 -4 x 1 1 0 0 0.5 0 0 -7.14 300 0 0 0 -0.5 -16.5 0 -17.36 -2850 对偶问题的经济意义影子价格 在单纯形算法中，设在单纯形算法中，设X XB B=B=B-1-1b b，X XN N=0=0是最优解；最优值是最优解；最优值 Z=C CB BB B-1-1b b，取取Y= C CB BB B-1-1= =（y y1 1,y,y2 2, , ,y ym m）,则则Y是对偶最优解。是对偶最优解。 下面我们讨论下面我们讨论yi（i=1,2, ,m）

18、的经济含义。的经济含义。 设设b bi i有单位增量有单位增量 b bi i =1，其它参数不变，则，其它参数不变，则 Z+Z=C CB BB B-1-1(b+(0,(b+(0, ,b bi i, ,0),0)T T） =Z+Z+yib bi i 即即Z= yib bi i = yi。所以所以yi表示在原问题已取得最优解表示在原问题已取得最优解的情况下，第的情况下，第i i种资源改变一个单位时总收益的变化值，也种资源改变一个单位时总收益的变化值，也可以说可以说yi是对第是对第i种资源的一种价格估计。这种价格估计并种资源的一种价格估计。这种价格估计并不是第不是第i种资源的实际价值或成本，而是由该企业在制产品种资源的实际价值或成本，而是由该企业在制产品的收益来估计所用资源的单位价值，称为的收益来估计所用资源的单位价值，称为影子价格。资源的影子价格是与具体的企业及产品有关的，同一种资源，在不同企业，或生产不同产品时对应的影子价格并不相同。 从对偶问题引出的实例中，可以看出，影子价格也是企业出让资源的