对偶理论和灵敏度分析.ppt

《对偶理论和灵敏度分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、对偶理论和灵敏度分析1.单纯形的矩阵描述用矩阵语言描述单纯形法的关键是写出两个基本的表达式,设线性规划的标准型为maxz=CXAX=bX≥0C=(CB,CN)，X=(XB,XN)’，A=(B,N)由约束条件AX=(B,N)(XB,XN)=BXB+NXN=b，可以得到用非基变量表示基变量的表达式:XB=B-1b-B-1NXN(1)将(1)式代入目标函数的表达式,可以得到用非基变量表示目标函数的表达式.Z=CX=(CB,CN)(XB,XN)’=CBXB+CNXN=CB(B-1-B-1NXN)+CNXN=CBB

2、-1b+(CN-CBB-1N)XN=CBB-1b+σNXN另非基变量等于零，则Z=CBB-1b注意XB检验数为零,实质上是CB-CBB-1B=0Y=CBB-1为单纯形乘子cxbCBCNθXBXNXBB-1bB-1BB-1N-z-CBB-1b0CN-CBB-1N注意:在初始单位矩阵的位置,在各运算表中就是B-1的所在位置BI……IB-12.改进单纯形法改进单纯形法又称为逆矩阵法或修正单纯形法,是在原来单纯形法基础上加以改进，关键在于求B-1,有了B-1,单纯形算法的各个表中的数字都可以利用线性规划中的原始数

3、据计算出来。3对偶理论某厂生产甲乙两种产品，各自的零部件分别在A、B车间生产，最后都需在C车间装配，相关数据如表所示：问如何安排甲、乙两产品的产量，使利润为最大。产品车间工时单耗甲乙生产能力ABC10023481236单位产品获利35maxZ=3x1+5x2x1≤82x2≤123x1+4x2≤36x1≥0,x2≥0S.t.若上例中该厂的产品平销，现有另一企业想租赁其设备。厂方为了在谈判时心中有数，需掌握设备台时费用的最低价码，以便衡量对方出价，对出租与否做出抉择。在这个问题上厂长面临着两种选择：自行

4、生产或出租设备。首先要弄清两个问题：①合理安排生产能取得多大利润?②为保持利润水平不降低，资源转让的最低价格是多少？问题①的最优解：x1=4，x2=6，Z*=42。假设出让A、B、C设备所得利润分别为y1、y2、y3原本用于生产甲产品的设备台时，如若出让，不应低于自行生产带来的利润，否则宁愿自己生产。于是有y1+0y2+3y3≥3同理，对乙产品而言，则有0y1+2y2+4y3≥5设备台时出让的收益（希望出让的收益最少值）min=8y1+12y2+36y3显然还有y1，y2，y3≥0min=8y1+12

5、y2+36y3y1+0y2+3y3≥30y1+2y2+4y3≥5y1，y2，y3≥0S.t.maxZ=3x1+5x2x1≤82x2≤123x1+4x2≤36x1,x2≥0S.t.例线性规划问题maxz=3x1+5x2stx1+3x2107x1+4x220xj0;j=1,2.对偶问题为：ming=10y1+20y2sty1+7y233y1+4y25yi0;i=1,2。3.1对偶变换的规则3.2对偶问题的基本性质为了便于讨论，下面不妨总是假设(1)对称性：对偶问题的对偶是原问题。(2)弱对偶性

6、：对偶问题(min)的任何可行解Y0，其目标函数值总是不小于原问题(max)任何可行解X0的目标函数值，即CX0≤Yb0。弱对偶定理推论：原问题的任何可行解目标函数值是其对偶问题目标函数值的下限；对偶问题的任何可行解目标函数值是原问题目标函数值的上限。(3)无界性若原(对偶)问题为无界解，则其对偶(原)问题无可行解当原问题(对偶问题)为无可行解,其对偶问题(原问题)或具有无界解或无可行解。如果原(对偶)问题有可行解，其对偶(原)问题无可行解，则原问题为无界解。(4)强对偶性可行解是最优解的性质(最优性准则

7、定理)若原问题的某个可行解X0的目标函数值与对偶问题某个可行解Y0的目标函数值相等，则X0,Y0分别是相应问题的最优解（5）主对偶定理若原问题和对偶问题两者皆可行,则两者均有最优解,且此时目标函数值相等。综上所述，一对对偶问题的解必然是下列三种情况之一:原问题和对偶问题都有最优解。一个问题具有无界解，另一个问题无可行解。原问题和对偶问题都无可行解。(6)互补松弛性设X0,Y0分别是原问题和对偶问题的可行解，Xs为原问题的松弛变量的值、Ys为对偶问题剩余变量的值。X0,Y0分别是原问题和对偶问题最优解的充分

8、必要条件是：Y0Xs=YsX0=0(7)原问题单纯形表检验数行与对偶问题解的关系原问题单纯形表检验数的相反数对应对偶问题的一个基解.显然,原问题最终单纯形表检验数的相反数对应对偶问题的一个基可行解XBXNXS0CN-CBB-1N-CBB-1YS1-YS2-Y例已知线性规划问题：试用对偶理论证明此线性规划问题无最优解。解：对偶问题为：由第一约束条件显见，对偶问题无可行解因为（0，0，0）为线性规划问题的可行解。而对偶问题无可行解