运筹学第二章对偶问题ppt课件.ppt

《运筹学第二章对偶问题ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章对偶问题与灵敏度分析2.1对偶问题的提出例1-1线性规划模型:Maxz=2x1+3x2St.x1+2x284x1164x212x1，x20y1+4y222y1+4y33=8y1+16y2+12y3y1，y2，y30对偶问题y1元/小时y2元/kgy3元/kg资源出租出让价格MinIII设备128台时原材料A4016kg原材料B0412kg单位利润23例2-1求解此对偶问题，模型为y1+4y2y4+y5=22y1+4y3y6+y7=3Min=8y1+16y2+12y3+0y4+My5+0y6+My7y1,y2,y3,y4,

2、y5,y6,y70402by74101320183MM0M001XBCBMy5y1y2y3y4y5y6y7816120M0MM100164M124Mi3/4[]102by341013/41/201/42-MM03M－301/4XBCBMy5y1y2y3y4y5y6y7816120M0M1210016-4M0i1/2－[4]402by74101320183MM0M001XBCBMy5y1y2y3y4y5y6y7816120M0MM100164M124Mi3/4[]101/2by311/401/43/41/201/

3、424M43M301/4XBCB16y2y1y2y3y4y5y6y7816120M0M121/40000i23/2[]102by341013/41/201/42-MM03M－301/4XBCBMy5y1y2y3y4y5y6y7816120M0M1210016-4M0i1/2－[4]21/21/8by111/41/803/2101/204M42M201/2XBCB16y2y1y2y3y4y5y6y7816120M0M81/41/8004101/2by311/401/43/41/201/424M43M301/4XBC

4、B16y2y1y2y3y4y5y6y7816120M0M121/40000i23/2[]最优解为：Y=（y1,y2,y3,y4,y6)=（3/2，1/8，0，0，0）y14比较原问题和对偶问题的最优单纯形表，得x1x2x3x4x523000XBCBb203x1x5x24001/4014001/22011/21/80z14003/21/802121/21/8by111/41/803/2101/204M42M201/2XBCB16y2y1y2y3y4y5y6y7816120M0M81/41/8004y142.2对偶问

5、题的一般形式Maxz=c1x1+c2x2+……+cnxnSt.a11x1+a12x2+……+a1nxnb1a21x1+a22x2+……+a2nxnb2……am1x1+am2x2+……+amnxnbmx1,x2,……xn0对偶问题Min=b1y1+b2y2+……+bmymSt.a11y1+a21y2+……+am1ymc1a12y1+a22y2+……+am2ymc2a1ny1+a2ny2+……+amnymcny1,y2,……ym0对于其他形式的对偶问题，可以先转化为上述形式，再求对偶问题例2-2：求下面线性规划问题的对偶问题Maxz=

6、3x1+4x2+6x3St.2x1+3x2+6x34406x14x2x31005x13x2+x3=200x1，x2，x30两边乘以“1”5x13x2+x32005x13x2+x3200Maxz=3x1+4x2+6x3St.2x1+3x2+6x34406x1+4x2+x31005x13x2+x32005x1+3x2x3200x1，x2，x30对偶Minw=440y1100y2+200y4200y52y16y2+5y45y533y1+4y23y4+3y546y1+y2+y4y56y1,y2,

7、y4,y50Minw=440y1100y2+200y4200y52y16y2+5y45y533y1+4y2+3y43y546y1+y2+y4y56y1,y2,y4,y50Minw=440y1100y2+200（y4y5）2y16y2+5(y4y5)33y1+4y2+3(y4y5)46y1+y2+(y4y5)6y1,y2,y4,y50令y3=y4y5Minw=440y1100y2+200y32y16y2+5y333y1+4y2+3y346y1+y2+y36y1,y20,y3：unr当原问题的第i

8、个约束条件为“=”时，其对偶问题的第i个变量没有符号约束Maxz=3x1+4x2+6x3St.2x1+3x2+6x344