运筹学对偶理论与敏感性分析PPT学习教案

1、会计学1 运筹学对偶理论与敏感性分析运筹学对偶理论与敏感性分析 2 第1页/共85页 3 产品甲产品乙设备能力（ h） 设备A3265 设备B2140 设备C0375 利润（元/件）15002500 设变量xi为第i种（甲、乙）产品的生产 件数（i1,2） 第2页/共85页 4 若该工厂的设备都用于出租，工厂收取出租 费。试问：设备A、B、C每工时各如何收 费才最有竞争力？ 第3页/共85页 5 minw=65y1+40y2+75y3 s.t.3y1+2y21500（不少于甲产品的利 润） 2y1+y2+3y32500（不少于乙产品的利润 ） y1,y2,y30 第4页/共85页 6 y1,

2、y2, y3 0 第5页/共85页 7 第6页/共85页 8 s.t. Ax b s.t. Ax + Ixs = b x 0 x, xs 0 第7页/共85页 9 cB cN 0 cB xB b xB xN xS 0 xS b B N I 检验数行 cB cN 0 cB cN 0 cB xB b xB xN xS cB xB B-1b I B-1N B-1 检验数行 0 cN -cBB-1N - cBB-1 经过若干次迭代 （标准化）原问题的初始单纯形表 第8页/共85页 10 当单纯形表为最优表时，检验数行为： (cB,cN,0)-cBB-1(B,N,I)= (0,cN-cBB-1N,-cB

3、B-1)0 令y=cBB-1,易看出 yAc y0 又因为 w =yb =cBB-1b =z 根据后面的强对偶理论知cBB-1为对偶问题的 最优解。而cBB-1就是最优单纯形表中对应于松弛 变量的检验数的负值。 第9页/共85页 11 例2.2： maxz=50 x1+100 x2 s.t.x1+x2300 2x1+x2400 x2250 x1,x20 加松弛变量得标准形式： maxz=50 x1+100 x2 s.t.x1+x2+x3=300 2x1+x2+x4=400 x2+x5=250 x1,x2,x3,x4,x50 第10页/共85页 12 50 100 0 0 0 CB XB x1

4、x2 x3 x4 x5 i 0 x3 300 1 1 1 0 0 300 0 x4 400 2 1 0 1 0 400 0 x5 250 0 (1) 0 0 1 250 z 0 50 100* 0 0 0 0 x3 50 (1) 0 1 0 -1 50 0 x4 150 2 0 0 1 -1 75 100 x2 250 0 1 0 0 1 z -25000 50* 0 0 0 -100 50 x1 50 1 0 1 0 -1 0 x4 50 0 0 -2 1 1 100 x2 250 0 1 0 0 1 z -27500 0 0 50 0 50 cBB-1 I B=(P1,P4, P2) B-

5、1 最优解：x1=50,x2=250,x4=50 对偶最优解：y1=50,y2=0,y3=50 B-1对应的检验数 T = cBB-1。 第11页/共85页 13 原问题（对偶问题）原问题（对偶问题）对偶问题（原问题）对偶问题（原问题） max z = cxmin w = yb n 个变量n 个约束 xj 0a1jy1 + a2jy2 + + a2jym cj xj 0a1jy1 + a2jy2 + + a2jym cj xj 无约束a1jy1 + a2jy2 + + a2jym = cj m 个约束m 个变量 ai1x1 + ai2x2 + + ainxn biyi 0 ai1x1 + ai

6、2x2 + + ainxn biyi 0 ai1x1 + ai2x2 + + ainxn = bi yi 无约束 非对称形式的对偶规划 第12页/共85页 14 第13页/共85页 15 这样，原规划模型可以写成 mjx bxaxa bxaxa bxaxa ts xcxcz j mnmnm nn nn nn , 2 , 1, 0 . max 11 11111 11111 11 第14页/共85页 16 111122 11111121211 12112122222 111122 112 min . . ,0 mm mm mm nnnmnmn m wb yb yb yb y a ya yayayc

7、 ayayayayc s t ayayayayc yyyy 这里，把y1看作是 y1=y1-y1，于是 y1没有非负限制。 第15页/共85页 17 例例2.12.1 写出右写出右 边线性规划问边线性规划问 题的对偶问题题的对偶问题 。 0, 3 22 252 min 21 321 321 321 321 xx xxx xxx xxx xxxz 0, 12 12 1 3225 max 21 321 321 321 321 yy yyy yyy yyy yyyw 最小化问题：最小化问题： 最小化问题的对偶问题：最小化问题的对偶问题： 变成目标函变成目标函 数的系数数的系数 系数变成约束系数变成约

8、束 条件右侧值条件右侧值 变成第一个变成第一个 约束条件的约束条件的 系数系数 反过来，由下反过来，由下 往上也是一样往上也是一样 的。的。 第16页/共85页 18 (LP)Maxz=j=1,2,n cj xj s.t.j=1,2,n aij xjbi,i =1,2,m xj 0,j =1,2,n (DP)Minw=i=1,2,m bi yi s.t.i=1,2,m aij yicj,j =1,2,n yi0,i =1,2,m 第17页/共85页 19 对偶规划的性质和原理对偶规划的性质和原理 定理2.0(对称性） 对偶规划的对偶规划是原规划 定理2.1(弱对偶定理） 若x,y分别为(LP)

9、和(DP)的可行解，则 cxyb 第18页/共85页 20 第19页/共85页 21 定理2.3(强对偶定理) 若(LP)和(DP)均可行，那么(LP)和(DP)均有最优解，且最优值相等。 定理2.4(互补松弛定理) 若X*,Y*为最优解，Xs,Ys为原问题和对偶问题的松弛变量，则有YsX*=0,Y*Xs=0 也即，在(LP)和(DP)的最优解中： (1)如果对应某一约束的对偶变量取值非零，则该约束取严格等式； (2)如果某一约束取严格不等式，则其对应的对偶变量必取零。 第20页/共85页 22 定理2.5 原问题单纯型表的检验数行对应对偶问题的一个基解 cB cN 0 cB xB b xB

10、xN xS cB xB B-1b I B-1N B-1 检验数行 0 cN -cBB-1N - cBB-1 第21页/共85页 23 例2.3：已知线性规划 maxz=50 x1+100 x2 s.t.x1+x2300 2x1+x2400 x2250 x1,x20 的最优解为x1*=50,x2*=250，求出 该线性规划对偶问题的最优解。 第22页/共85页 24 解：x1*+x2*=300y1*0, 2x1*+x2*0y1*+2y2*=50, x2*0y1*+y2*+y3*= 100. 所以， y1*=50,y2*=0,y3*=50. 第23页/共85页 25 例：已知线性规划 maxz=x

11、1+x2 s.t.-x1+x2+x32 -2x1+x2-x31 x1,x2x30 试用对偶理论证明该线性规划无最优 解。 第24页/共85页 26 解：minw=2y1+y2 s.t.-y1-2y22 y1+y21 y1-y20 y1,y20 对偶问题无可行解 第25页/共85页 27 课堂练习： 已知原问题最优解为（2,2,4,0），根据对偶理论，写出对偶问题的最优解 第26页/共85页 28 4. 对偶单纯形法对偶单纯形法 w 基本思想 w 算法过程 w 算例 第27页/共85页 29 cB cN 0 cB xB b xB xN xS cB xB B-1b I B-1N B-1 检验数行

12、0 cN -cBB-1N -cBB-1 第28页/共85页 30 cB cN 0 cB xB b xB xN xS cB xB B-1b0 I B-1N B-1 检验数行 0 cN - cBB-1N - cBB-1 0 第29页/共85页 31 cB cN 0 cB xB b xB xN xS cB xB B-1b0 I B-1N B-1 检验数行 0 cN - cBB-1N - cBB-1 0 第30页/共85页 32 对偶单纯形法在什么情况下使用？ 应用前提：有一个基，其对应的基满足: 单纯形表的检验数行全部为负（即 对偶可行）； 基变量取值有负数（非可行解）。 注：通过矩阵行变换运算，使

13、所有相应 基变量取值均为非负数即得到最优 单纯形表。 第31页/共85页 33 对偶单纯形法求解线性规划问题过程：对偶单纯形法求解线性规划问题过程： 第32页/共85页 34 标准化：标准化： maxz=-2x1-3x2-4x3 s.t.-x1-2x2-x3+x4=-3 -2x1+x2-3x3+x5=-4 x1,x2,x3,x4,x50 minw=2x1+3x2+4x3 s.t.x1+2x2+x33 2x1-x2+x34 x1,x2,x30 第33页/共85页 35 cj -2 -3 -4 0 0 cB xB b x1 x2 x3 x4 x5 0 x4 -3 -1 -2 -1 1 0 0 x5

14、 -4 -2 1 -3 0 1 j 0 -2 -3 -4 0 0 0 x4 -1 0 -5/2 1/2 1 -1/2 -2 x1 2 1 -1/2 3/2 0 -1/2 j 4 0 -4 -1 0 -1 -3 x2 2/5 0 1 -1/5 -2/5 1/5 -2 x1 11/5 1 0 7/5 -1/5 -2/5 j 28/5 0 0 -9/5 -8/5 -1/5 第34页/共85页 36 是 是 是是 否否 否否 所有所有 得到 最优解 计算计算 原规划的基解是 可行的 对偶问题的基解是 可行的 所有所有 计算计算 以旋转元素进行迭代以旋转元素进行迭代 停 无 界 解 无 可 行 解 单纯

15、形法对偶单纯形法 0 j 0 i b max0 kjj 0min iie bbb 0 ik a0 lj a ek e ik ik i a b a a b 0min min0 ik ej ejek a aa 第35页/共85页 37 第36页/共85页 3. 对偶变量的经济解释对偶变量的经济解释 影子价格影子价格 Shadow price 第37页/共85页 39 maxz=2x1+x2 s.t.5x215 6x1+2x225 x1+x25 x1 , x2 0 b2：2425 z* ：8.58.75 z/b2=0.25 第38页/共85页 40 若B是最优基，y*T = cBB-1 为影子价格向

16、量。 第39页/共85页 扩大生产；否则不宜买进。 第40页/共85页 * 22 * 11 * mmy bybybwz 第41页/共85页 43 miy b z i i ,2,1, * * miy i ,2,1, * 第42页/共85页 第43页/共85页 45 变化。 3 x1+x25 3 x1+x26 b2：2425 z/b20.25 第44页/共85页 第45页/共85页 47 0,1818,3030,+) x1*(b2-6)/6(b2-10)/45 x2*3(30-b2)/40 z*1+b2/35/2+b2/410 y2*=z/b21/31/4 b2 0 第46页/共85页 48 5.

17、 灵敏度分析灵敏度分析 Sensitivity Analysis 第47页/共85页 49 第48页/共85页 50 原问题对偶问题结论或继续计算的 步骤 可行解可行解最优基不变 可行解非可行解用单纯形法继续迭 代 非可行解可行解用对偶单纯形法继 续迭代 非可行解非可行解引入人工变量，编 制新的单纯形表重 新计算 第49页/共85页 问题问题1 1：ci,bi,aij发生变化，问题的最 优解如何变化？或者这些参数在多大 的范围内变化，最优解仍然不变？ 问题2：增加一约束或变量，最优解如 何变化？ 第50页/共85页 52 1.c是非基变量的系数： 2. c是基变量的系数：是基变量的系数： 第5

18、1页/共85页 1.若ck是非基变量的系数： 设 ck 变化为 ck + ck k=ck +ck-ci aik=k+ck 只要k0,即 ck-k， 则最优解不变； 否则，将最优单纯形表中的检验数k 用k取代，继续单纯形法的表格计算 。 第52页/共85页 第53页/共85页 c -2 -3 -4 0 0 cB xB b x1 x2 x3 x4 x5 -3 x2 2/5 0 1 -1/5 -2/5 1/5 -2 x1 11/5 1 0 7/5 -1/5 -2/5 j 28/5 0 0 -9/5 -8/5 -1/5 c -2 -3 -4+c3 0 0 cB xB b x1 x2 x3 x4 x5

19、-3 x2 2/5 0 1 -1/5 -2/5 1/5 -2 x1 11/5 1 0 7/5 -1/5 -2/5 j 28/5 0 0 -9/5+c3 -8/5 -1/5 从表中看到3=c3+c3-(c2a13+c1a23) 可得到c39/5 时，原最优解不变。 第54页/共85页 2. 若若 cs 是基变量的系数：是基变量的系数： 设cs变化为cs +cs，那么 j=cj-i sciaij-(cs+cs)asj =j-csasj， 只要对所有非基变量，有j0，即 jcsasj， 则最优解不变；否则，将最优单纯形 表中的检验数j用j取代，继续单纯 形法的表格计算。 第55页/共85页 57 I

20、II可用资源 设备128台时 原材料A4016kg 原材料B0412kg 已知生产1件I可以获利2元，生产1件II可获利3元， 问应当如何安排计划使该工厂获利最多？ 第56页/共85页 例2.6：线性规划 maxz=2x1+3x2+0 x3+0 x4+0 x5 s.t.x1+2x2+x3=8 4x1+x4=16 4x2+x5=12 x1,x2,x3,x4,x50 有最优解的单纯形表： 考虑基变量系数c2发生变化 c 2 3 0 0 0 cB xB b x1 x2 x3 x4 x5 2 x1 4 1 0 0 1/4 0 0 x5 4 0 0 -2 1/2 1 3 x2 2 0 1 1/2 -1/

21、8 0 j -14 0 0 -1.5 -1/8 0 第57页/共85页 c 2 3 0 0 0 cB xB b x1 x2 x3 x4 x5 2 x1 4 1 0 0 1/4 0 0 x5 4 0 0 -2 1/2 1 3 x2 2 0 1 1/2 -1/8 0 j -14 0 0 -1.5 -1/8 0 c 2 3+c2 0 0 0 cB xB b x1 x2 x3 x4 x5 2 x1 4 1 0 0 1/4 0 0 x5 4 0 0 -2 1/2 1 3+c2 x2 2 0 1 1/2 -1/8 0 j -14-2c2 0 0 -1.5 -c2/2 -1/8+c2/8 0 第58页/共8

22、5页 111 00 0 00 rr B bBbbBb 第59页/共85页 1 c 2 3 0 0 0 cB xB b x1 x2 x3 x4 x5 2 x1 4 1 0 0 1/4 0 0 x5 4 0 0 -2 1/2 1 3 x2 2 0 1 1/2 -1/8 0 j -14 0 0 -1.5 -1/8 0 第60页/共85页 各列分别对应 b1,b2,b3的单一变化。 因此，设b1增加4，则x1,x5,x2分别变 为： 4+04=4,4+(-2)4=-418时表时表2-17(1)仍然是最优表仍然是最优表,最优解是参数的函数 最优解是参数的函数 X（8，9+0.5，0）,目标值目标值Z 67+1.5