资源描述：
《第2章 对偶理论和灵敏度分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第二章对偶理论与灵敏度分析§1单纯形法的矩阵描述设maxz=CXAX=bX≥0A为m×n阶矩阵RankA=m,取B为可行基,N为非基，123求解步骤：432利润12kg40材料B16kg04材料A8台时21设备台时限制ⅡⅠ§2对偶问题的提出[eg.1]制定生产计划M1:maxz=2x1+3x21x1+2x2≤84x1≤164x2≤12x1，x2≥05现在出租，设y1为设备单位台时的租金y2,y3为材料A、B转让附加费(kg-1)则M2为M1的对偶问题，反之亦然。M2:minw=8y1+16y2+12y3y1+4y2≥22y1+4y3≥3y1,y2,y3≥
2、032利润12kg40材料B16kg04材料A8台时21设备台时限制ⅡⅠ6一般的，原问题：maxz=CXAX≤bX≥0对偶问题：minw=YbYA≥CY≥0比较：maxzminw决策变量为n个约束条件为n个约束条件为m个决策变量为m个“≤”“≥”7§3对偶问题的化法1、典型情况[eg.2]maxz=x1+2x2+x32x1+x2≤62x2+x3≤8x1,x2,x3≥0对偶：minw=6y1+8y22y1≥1y1+2y2≥2y2≥1y1,y2≥082、含等式的情况[eg.3]maxz=x1+2x2+4x32x1+x2+3x3=3x1+2x2+5x3≤4x1
3、,x2,x3≥0对偶：minw=3y1’-3y1”+4y22y1’-2y1”+y2≥1y1’-y1”+2y2≥23y1’-3y1”+5y2≥4y1’,y1”,y2≥0令y1=y1’-y1”,则：minw=3y1+4y22y1+y2≥1y1+2y2≥23y1+5y2≥4y2≥0，y1无约束一般，原问题第i个约束取等式，对偶问题第i个变量无约束。2x1+x2+3x3≤3-2x1-x2-3x3≤-393、含“≥”的max问题[eg.4]maxz=x1+2x2+4x32x1+x2+3x3≥3x1+2x2+5x3≤4x1,x2,x3≥0对偶：minw=-3y1’+
4、4y2-2y1’+y2≥1-y1’+2y2≥2-3y1’+5y2≥4y1’,y2≥0令y1=-y1’，则：minw=3y1+4y22y1+y2≥1y1+2y2≥23y1+5y2≥4y1≤0,y2≥0-2x1-x2-3x3≤-310一般:①max问题第i个约束取“≥”，则min问题第i个变量≤0；②min问题第i个约束取“≤”，则max问题第i个变量≤0；③原问题第i个约束取等式，对偶问题第i个变量无约束；④max问题第j个变量≤0,则min问题第j个约束取“≤”；⑤min问题第j个变量≤0，则max问题第j个约束取“≥”；⑥原问题第j个变量无约束，对偶问
5、题第j个约束取等式。约束条件符号判断：max->min相同，min->max相反决策变量符号判断：max->min相反，min->max相同11[eg.5]minz=2x1+3x2-5x3+x4x1+x2-3x3+x4≥52x1+2x3-x4≤4x2+x3+x4=6x1≤0,x2,x3≥0,x4无约束对偶：maxw=5y1+4y2+6y3y1+y2≥2y1+y3≤3-3y1+2y2+y3≤-5y1-y2+y3=1y1≥0,y2≤0,y3无约束12对偶问题的基本性质一、单纯形法计算的矩阵描述MaxZ=CXAX≤bX≥0其中X＝(x1,x2……xn)TMax
6、Z=CX+0XsAX+IXs=bX,Xs≥0其中Xs＝(xn+1,xn+2……xn+m)TI为m×m的单位矩阵13项目非基变量基变量XBXNXs0XsbBNIcj-zjCBCN0……项目基变量非基变量XBXNXsCBXBB-1bIB-1NB-1cj-zj0CN-CBB-1N-CBB-1对应初始单纯形表中的单位矩阵I，迭代后的单纯形表中为B-1；初始单纯形表中基变量Xs=b，迭代后的表中为XB=B-1b；约束矩阵（A，I）＝（B，N，I），迭代后为（B-1B，B-1N，B-1I）＝（I，B-1N，B-1)；初始单纯形表中xj的系数向量为Pj，迭代后为Pj’
7、，且Pj’=B-1Pj。14maxZ=4.5x1+5x2s.t.3x1+2x2≤244x1+5x2≤40x1,x2≥0minw=24y1+40y2s.t.3y1+4y2≥4.52y1+5x2≥5y1,y2≥0y1y2x1x2maxZ=4.5x1+5x2s.t.3x1+2x2+x3=244x1+5x2+x4=40x1,x2,x3,x4,≥0minw=24y1+40y2s.t.3y1+4y2-y3=4.52y1+5x2-y4=5y1,y2,y3,y4≥0y1y2x1x215cj4.5500θCBXBbx1x2x3x40x3243210120x44045018
8、cj-zj4.55000x387/501-2/540/75x284/5101/5
