运筹学02-对偶理论与敏感性分析.ppt

《运筹学02-对偶理论与敏感性分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1运筹学第二章对偶理论与及灵敏度分析DualTheoryandSensitivityAnalysis2线性规划的对偶问题概念、理论及经济意义线性规划的对偶单纯形法线性规划的灵敏度分析本章内容重点3§1.线性规划对偶问题对偶问题的提出例1.1:某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：4产品甲产品乙设备能力（h）设备A3265设备B2140设备C0375利润（元/件）15002500设变量xi为第i

2、种（甲、乙）产品的生产件数（i＝1,2）5maxz=1500x1+2500x2s.t.3x1+2x2≤652x1+x2≤403x2≤75x1,x2≥0若该工厂的设备都用于出租，工厂收取出租费。试问：设备A、B、C每工时各如何收费才最有竞争力？6设y1,y2,y3分别为每工时设备A、B、C的出租费。minw=65y1+40y2+75y3s.t.3y1+2y2≥1500（不少于甲产品的利润）2y1+y2+3y3≥2500（不少于乙产品的利润）y1,y2,y3≥07maxz=1500x1+2500x2s.t.3

3、x1+2x2≤652x1+x2≤40原问题3x2≤75x1,x2≥0minw=65y1+40y2+75y3s.t.3y1+2y2≥15002y1+y2+3y3≥2500对偶问题y1,y2,y3≥08对偶问题的定义对称形式：互为对偶(LP)maxz=cx(DP)minw=ybs.t.Ax≤bs.t.yA≥cx≥0y≥0注意：x为列向量,y为行向量。9原问题的最优单纯形表中关于对偶问题的最优解的信息：(LP)maxz=cx(DP)minw=ybs.t.Ax≤bs.t.yA≥cx≥0y≥0maxz=cx标准化m

4、axz=cx+0xss.t.Ax≤bs.t.Ax+Ixs=bx≥0x,xs≥010cBcN0cBxBbxBxNxS0xSbBNI检验数行cBcN0cBcN0cBxBbxBxNxScBxBB-1bIB-1NB-1检验数行0cN-cBB-1N-cBB-1经过若干次迭代（标准化）原问题的初始单纯形表11当单纯形表为最优表时，检验数行为：(cB,cN,0)-cBB-1(B,N,I)=(0,cN-cBB-1N,-cBB-1)≤0令y=cBB-1,易看出yA≥cy≥0又因为w=yb=cBB-1b=z根据后面的强对偶理

5、论知cBB-1为对偶问题的最优解。而cBB-1就是最优单纯形表中对应于松弛变量的检验数的负值。12例2.2：maxz=50x1+100x2s.t.x1+x2≤3002x1+x2≤400x2≤250x1,x2≥0加松弛变量得标准形式：maxz=50x1+100x2s.t.x1+x2+x3=3002x1+x2+x4=400x2+x5=250x1,x2,x3,x4,x5≥013cBB-1IB=(P1,P4,P2)０B-1最优解：x1=50,x2=250,x4=50对偶最优解：y1=50,y2=0,y3=50B-

6、1对应的检验数T=cBB-1。14原问题（对偶问题）对偶问题（原问题）maxz=cxminw=ybn个变量n个约束xj≥0a1jy1+a2jy2+…+a2jym≥cjxj≤0a1jy1+a2jy2+…+a2jym≤cjxj无约束a1jy1+a2jy2+…+a2jym=cjm个约束m个变量ai1x1+ai2x2+…+ainxn≤biyi≥0ai1x1+ai2x2+…+ainxn≥biyi≤0ai1x1+ai2x2+…+ainxn=biyi无约束非对称形式的对偶规划15举列说明：设原规划中第一个约束为等式：

7、a11x1+…+a1nxn=b1那么，这个等式与下面两个不等式等价a11x1+…+a1nxnb1a11x1+…+a1nxnb116这样，原规划模型可以写成17此时已转化为对称形式，直接写出对偶规划这里，把y1看作是y1=y1’-y1’’，于是y1没有非负限制。18例2.1写出右边线性规划问题的对偶问题。最小化问题：最小化问题的对偶问题：变成目标函数的系数系数变成约束条件右侧值变成第一个约束条件的系数反过来，由下往上也是一样的。19§2.对偶问题的基本性质(LP)Maxz=j=1,2,…,ncjxjs

8、.t.j=1,2,…,naijxjbi,i=1,2,…,mxj0,j=1,2,…,n(DP)Minw=i=1,2,…,mbiyis.t.i=1,2,…,maijyicj,j=1,2,…,nyi0,i=1,2,…,m20对偶规划的性质和原理定理2.0(对称性）对偶规划的对偶规划是原规划定理2.1(弱对偶定理）若x,y分别为(LP)和(DP)的可行解，则cx≤yb21推论(无界性)若(LP)具有无界解，则(DP)无可