运筹学04对偶问题和灵敏度分析

1、唯一最优解唯一最优解 N NN YYY添加松弛变量添加松弛变量、人工变人工变量量, 列出初始单纯形表列出初始单纯形表计算非基变量计算非基变量对应的检验数对应的检验数 j所有所有 j 0基 变 量基 变 量中中有 非 零有 非 零的的人 工 变人 工 变量量某非基变某非基变量检验数量检验数为零为零无可行解无可行解无穷多最优解无穷多最优解对某对某 j 0有有aij0无界解无界解令令 k=max j对所有对所有ai k0计算计算 i=bi/aik令令 s=min ixs为换出变量为换出变量ask为主元素为主元素 迭代运算迭代运算. 用非基变量用非基变量xk替换基变量替换基变量xs; . 对主元素行对

2、主元素行(第第s行行)，令，令 bs/askbs;asj/askasj. 对主元素列对主元素列(第第k列列)，令，令1ask；0其它元素其它元素 表中其它行列元素表中其它行列元素 令令 aij-asj/askaikaij bi-bs/askaikbiYN复习上次内容：人工变量法基变量非基变量等式右端XB XN1XS系数矩阵IB-1N1B-1B-1b检验数0CN1-CBB-1N1-CBB-1-CBB-1b11111()()min()0()()iskiikkisB bB bBPBPBP单纯形表的矩阵表达形式 1:N系数矩阵中对应于非基变量中决策变量的子矩阵3 线性规划的对偶问题的提出 矩阵形式 0

3、.maxXbAXt.sCXz实际问题提出： 某厂生产甲、乙两种产品，产量、利润、设备台时如下模型所示0,124 16 482 . .32max21212121xxxxxxtsxxz甲产品：获利2元乙产品：获利3元 从另一个角度讨论这个问题：工厂决定转让设备并出让原材料收取租金，如何确定租价？ 设y1为出租单位出租单位设备台时的租价，设备台时的租价， y2，y3分别出让单位原材料、的出让单位原材料、的附加额附加额。0,34 22 4 . .12168 min3213121321yyyyyyytsyyyII生产每件产品 的设备台时和原材料出让的所有收入生产每件产品 的利润！ 为什么目标取最小？租金

4、定的越高就不会有人来租，问题就没有实际意义，工厂和接受者都愿意的条件为上述规划问题的解。 其中Y=（y1，y2，y3） 每个线性规划都有另一个线性规划每个线性规划都有另一个线性规划(对偶问题对偶问题)与它密切相与它密切相关，对偶理论揭示了原问题与对偶问题的内在联系。关，对偶理论揭示了原问题与对偶问题的内在联系。0,124 16 482 . .32max21212121xxxxxxtsxxz0,34 22 4 . .12168 min3213121321yyyyyyytsyyy 理论上11BCNBCCBBN与检验数为优解线性规划问题有获得最时并且当0011BCNBCCBBN，称为单纯形乘子令1B

5、CYB0,.0.maxmaxXbIXAXtsXbAXtsCXZCXZsXs因为Yb的上界为无限大,所以b只能有最小值。zbBCYbBCYCYAABCCYBCBBBB ) 3( 0 )2(0 0 ) 1 (11110. .minYCYAtsYb4 线性规划的对偶理论原问题与对偶问题的数学模型原问题与对偶问题的数学模型原问题标准形式：对偶问题标准形式： 标准对偶问题标准对偶问题nmijTnaAxxxXXbAXtsCXz)(,),(0. . max21),(0.min21myyyYYCYAtsYb标准形式下原问题与对偶问题的对应关系根据下表写出原问题与对偶问题的表达式 xjyjx1x2by1y2y3

6230. .max XybAXybAXtsCXZ0. .min yyCAAyytsbbyy0,)(. .)(min yyCAyytsbyy由自 . .minYCYAtsYb 如果原问题约束条件是等式约束0. .maxXbAXtsCXZ原问题中的价值向量与对偶问题中的资源向量对换（上下对换）原问题: X在C和A的右边; 对偶问题:Y在b和A的左边（左右对换）对偶问题的基本性质和基本定理1. 对称性定理：对偶问题的对偶是原问题证明：2. 弱对偶性定理 若X（0）和Y（0）分别是原问题和对偶问题的可行解，则有CX（0）Y（0）b3. 若原问题（对偶问题）为无界解，则其对偶问题

7、（原问题）无可行解。 (逆命题未必成立) 由弱对偶定理可证得 证明: 因为X（0）是原问题的可行解，故有 AX（0）b。 又因为Y(0)是对偶问题的可行解，则有 Y（0）AX（0）Y（0）b, 及Y（0）AC故 C X（0）Y（0）A X（0）Y（0）b亦即 C X（0）Y（0）b 证毕4.最优性定理若X（0）和Y（0）分别是原问题和对偶问题的可行解，且有 C X（0）=Y（0）b , 则X（0）和Y（0）分别是原问题和对偶问题的最优解。 证明： 设 X 是原问题任一可行解，Y（0）是对偶问题的可行解，根据弱对偶性定理，有C XY（0）b 因为C X（0）=Y（0）b，故CXC X（0），即X

8、（0）是原问题的最优解。 设Y为对偶问题的任一可行解，同理有Yb Y（0）b 即Y（0）是对偶问题的最优解。5.对偶定理 有一对对偶的线性规划问题，若其中有一个有最优解，则另一个也有最优解，且相应的目标函数值相等。 证明：设X（0）是原问题的最优解，对应的基矩阵为B, 非基变量的检验数为CN- CBB-1N0 全体检验数 C- CBB-1A0，即CCBB-1A 令Y（0）= CBB-1 0，则有Y（0）AC 即Y（0）是对偶问题的可行解。 由于z=C X（0）= CBXB（0）= CBB-1b= Y（0）b（目标值相等）由最优性定理可知Y（0）为对偶问题的最优解。综上，一对对偶问题的解必然下列

9、情况之一：综上，一对对偶问题的解必然下列情况之一：1、原问题和对偶问题都有解，且目标函数值相等，原问题的 最优解是其对偶问题的最优解。2、一个问题具有无界解，另一个问题无可行解3、一个问题无可行解,另一个问题或具有无界解或无可行解 6 .互补松弛定理 若X（0）和Y（0）分别是原问题和对偶问题的可行解，则X（0）和Y（0）都是最优解的充要条件是 Y（0）Xs=Ys X（0）=0。其中Xs=(xs1,xs2,xsm)T，xs1,xs2,xsm 是原问题的松弛变量，松弛变量， Ys=(ys1,ys2,ysn)T ，ys1,ys2,ysn是对偶问题的剩余变量剩余变量。 如果有某个原始最优解X(0)

10、Ys X（0）=0：对某个下标j满足X(0)j0，那么与之对应的对偶约束在最优的情况下为等式，即ysj=0(不需要松弛变量)； Y（0）Xs=0：如果原始约束在最优情况下对某个下标i满足x(0)si0(原问题约束是严格不等式，需要松弛变量才能化为等式)，那么对偶问题最优解中与之对应的y(0)i=0。证明: 原问题 对偶问题 max z =CX min =Yb AX+ Xs =b YA-Ys=C X, Xs 0 Y, Ys0 z =(YA-Ys)X=YAX-YsX =Y(AX+Xs)=YAX+YXs 若Y(0)Xs=0和YsX(0) =0, 则Y(0)b=Y(0)AX(0)=CX(0)，根据性质

11、4知: X(0),Y(0)为最优解。 反之, X(0),Y(0)为最优解,则根据性质4: CX(0)=Y(0)b。两组最优解分别代入目标函数: CX(0)=Y(0)AX(0)-YsX(0) Y(0)AX(0) Y(0) b=Y(0)AX(0)+Y(0)Ys Y(0)AX(0) 可知必有Y(0)Xs=YsX(0) =0。 证毕7. 原问题的检验数对应对偶问题的一个基本解设B是原问题的一个可行基,有A=(B,N)max z=CBXB+CNXN min =YbBXB+NXN+XS=b YB-Ys1=CBXB, XN，Xs0 YN-Ys2=CN Y, Ys1，Ys20 YS=（YS1，YS2）证明:

12、原问题 对偶问题 max z =CX min =Yb AX+ Xs =b YA-Ys=C X, Xs 0 Y, Ys0Ys1对应原问题当中基变量XB的剩余变量，Ys2对应原问题当中非基变量XN的剩余变量 当原问题有解XB=B-1b，XN=0时,检验数为：CN-CBB-1N，-CBB-1 令Y=CBB-1，代入对偶问题的约束条件得： Ys1=0， -Ys2= CN-CBB-1N 则（Y，Ys1，Ys2）为对偶问题的基本解 证毕检验数性质：原问题检验数行对应其对偶问题的一个 基解, 关系如下: XB XN Xs 0 CN-CBB-1N -CBB-1 Ys1 - Ys2 -Y例4 已知线性规划问题

13、max z = x1 + x2 -x1 + x2 + x3 2 -2x1 + x2 - x3 1 x1 , x2 , x30试用对偶理论证明上述线性规划问题无最优解。 证: 首先看到该问题存在可行解，例如X = (0,0,0) 而上述问题的对偶问题为 min = 2y1 + y2 -y1 - 2y2 1 y1 + y2 1 y1 - y2 0 y1 ,y2 0 由第一约束条件可知对偶问题无可行解，因而无最优解。由此原问题也无最优解。例5 已知线性规划问题 min = 2x1 + 3x2 + 5x3 + 2x4 + 3x5 x1 + x2 + 2x3 + x4 + 3x5 4 2x1 - x2

14、+ 3x3 + x4 + x5 3 xj 0,j = 1,2,3,4,5 已知其对偶问题的最优解为y1* = 4/5, y2* = 3/5；z = 5。试用对偶理论找出原问题的最优解.解: 先写出它的对偶问题 max z = 4y1 + 3y2 y1 + 2y2 2 y1 - y2 3 (2) 2y1 + 3y2 5 (3) y1 + y2 2(4) 3y1 + y2 3 y1 ,y2 0将y1*, y2*的值代入上述约束条件，得(2),(3),(4)为严格不等式；由互补松弛性得x2* = x3* = x4* = 0 因y1 ,y2 = 0，原问题的两个约束条件应取等式，故有 x1* + 3x

15、5* = 4 2x1* + x5* = 3 求解后得x1* = 1，x5* = 1故原问题的最优解为 X* = (1,0,0,0,1)T最优值为 * = 55 对偶问题的经济解释（影子价格）由对偶定理知，当达到最优解时有： z=CX（0）=Y（0）b=y1（0）b1+ y2（0）b2+ ym（0）bm在最优解处，常数项bi 的微小改变对目标函数值的影响（在不改变最优基情况下）有mmbzybzybzy)0(2)0(21)0(1,这说明若原问题的bi增加一个单位，则由此引起的最优目标函数值增加量等于该约束条件对应的对偶变量yi的最优值。因此，最优对偶变量yi的值，就相当于对单位变化的第i种资源在实

16、现最大利润时的一种价格估计，这种估计被称之为影子价格影子价格。原问题：可以理解为资源的合理利用使总利润最大对偶问题：估计资源的价值问题（但并不是第种资源的实际成本，而是根据企业制造产品的收益估计资源的单位价值，既资源在最优产品组合时具有的潜在价值）影子价格：不同于市场价格，是企业内部估计或核算价格例：某厂生产、种产品要消耗钢、煤、机械加工时间，现有资源数和利润表如下，试制定一个最优生产计划。单位消耗现有资源数钢煤机时100180240利润1212121212max3. .2100221806240,0 xxstxxxxxxx x解得：(30,35)135xz123123123123m10018

17、0240. .212263,0inyyystyyyyyyy yy对偶问题:由互补松弛条件：(3/4,0,1/4)y解得：0362010*3*1*3*1*2yyyyy所以： 钢增加一吨，收入增加3/4万 煤增加一吨，收入增加0 机时增加一个，收入增加1/4万 煤本身没有用完，再增加量，收入也不会增加，而另两种资源已经用完，再增加资源才会增加收益。影子价格在经济管理中的作用影子价格在经济管理中的作用:(1) 指示企业内部挖潜的方向： yi高,对目标增益贡献大,应重 视此资源的组织、采购； (2)指导企业的购销决策： yi*是新增资源的价值，在最优产 品不变的情况下，购入资源价格 大于yi*时，企业

18、亏损，若企业有 市价高于影子价格的资源，应设 法将其转让；(3)用影子价格分析工艺改变后对资源节约的收益:(4)指导企业间的分工协作: 企业接受外协加工时，制定收费标准可依据影子价格，以使双方都有利润，可以促进协作；当外协单位支付的报酬不低于影子价格时，企业可以接受，合作可以促进产品更新换代，以发挥各自优势。例：A、B、C三厂生产车床、刨床，若只生产一种产品，效率表如右图。车、刨床需求比例为1：2，试制定最优分工协作计划，使总的套数最多。解：A、B、C三厂编号为1，2，3 车、刨床的编号为1，2效率车床 刨床ABC1 45 22 3ijx为第i厂生产第j种产品的时间比例则：11213152xxx122232423xxx车床总数：刨床总数：1121311222325214232xxxxxx11213112223221044230 xxxxxx展开得：)2 , 1, 3 , 2 , 1(0111323122211211jixxxxxxxij112131122232212221223132112131122232max5242311.1210442300(1,2,3,1,2)i