运筹学第二章电子讲稿1.ppt

第二章 对偶理论与灵敏度分析 §1.单纯形表的矩阵描述 max Ζ=CX s.t. AX=b X0 A=[B,N] ,C=(CB,CN),X= 则有 max Ζ=CBXB+CNXN x.t. BXB+NXN=b XB,XN≥0 XB=B-1b-B-1NXN Ζ=CB(B-1b-B-1NXN)+CNXN =CBB-1b+(CN-CBB-1N)XN 由于b列中有负数，故用对偶单纯形法求新的最优解 XB b x1 x2 x3 x4 x5 x6 x2 31/5 * 1 0 0 * * x3 33/5 * 0 1 0 * * x6 8 –2 0 0 1 –20 -2 -9/5 0 0 0 –92/5 –8/5 7.2.目标函数中价值系数cj的变化分析 (1)cj是非基变量xj的系数 根据单纯形表的矩阵表示 B-1b I B-1N –CBB-1b 0 CN-CBB-1N 由于CB没有改变，故影响的仅是检验数 ?j=cj-CBB-1Pj 若cj变化Δcj,要保证最优解不变只须其检验数仍小于或等于零，即 ? j’=cj’-CBB-1Pj=cj+Δcj-CBB-1Pj≤0 或 Δcj≤-(cj-CBB-1Pj)=-?j (2)cr是基变量xr的系数 在cr没有变化时, ?r=cr-CBB-1Pr=0 若cr变化Δcr,则 CB’=CB+(0,…,0, Δcr,0,…,0) CB’B-1=CBB-1+(0,…,0, Δcr,0,…，0)B-1 ?’=C’-CB’B-1A =C’-CBB-1A-(0,…,0, Δcr,0,…,0)B-1A =C’-CBB-1A-Δcr(ar1,ar2,…,arn) ?j’=cj-CBB-1Pj-Δcrarj (j≠r) = ?j-Δcrarj ?r’=cr+Δcr-CBB-1Pj-Δcrarr =0 若要保持原最优解不变则必须?j’≤0,即 ?j’-Δcrarj≤0 即Δcr≤ ?j/arj (若arj0) Δcr≥ ?j/arj (若arj0) arj 为xr所在行的各系数(j=1,…,n) 即Δcr的变化范围为 max {?j/arj arj0 }≤Δcr≤min{?j/arj air0} 若Δcr超出此范围，则将修改后的检验数代入，继续迭代. 例. 一线性规划模型为 max Ζ=9x1+8x2+50x3+19x4 s.t. 3x1+2x2+10x3+4x4≤18 2x3+1/2x4≤3 xj?0, j=1,2,3,4 最后单纯形表为 b x1 x2 x3 x4 x5 x6 2 2 4/3 0 1 2/3 –10/3 1 –1/2 –1/3 1 0 –1/6 4/3 - 4 –2/3 0 0 –13/3 –10/3 问保持现行解为最优的条件下