运筹学对偶原理上课讲义.ppt

《运筹学对偶原理上课讲义.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运筹学对偶原理目标函数Maxz=3x1+5x2约束条件x18s.t.2x2123x1+2x236x1，x20设有，y1,y2,y3分别为出售A，B，C工时所得利润（百元/工时），w为总盈利额（百元）对偶的定义线性规划问题在形式上，可以形成一对对称问题，对任何线性规划求最大值问题，都有一个与之对称的求最小值问题，这两个有关的约束条件的系数矩阵，具有相同的数据，仅形式互为转置，并且目标函数与约束右端项互换，其目标函数的最优值也是彼此相等的，我们把线性规划的这个对称问题称为对偶问题。原始问题maxz=CTXs.t.AX≤bX≥0对

2、偶问题minw=bTYs.t.ATY≥CY≥0≤maxbACTCATbT≥minmnmn原始问题Primalproblem对偶问题DualproblemP1D13.1.2对偶关系关系1规范对偶关系对称对偶关系2标准性LP问题的对偶关系非对称对偶自由Y关系3一般对偶关系原问题（或对偶问题）对偶问题（或原问题）目标函数MaxZ目标函数MinW约束条件数：m个第i个约束条件类型为“≤”第i个约束条件类型为“≥”第i个约束条件类型为“=”对偶变量数：m个第i个变量≥0第i个变量≤0第i个变量是自由变量决策变量数：n个第j个变量≥0第j个变量

3、≤0第j个变量是自由变量约束条件数：n第i个约束条件类型为“≥”第i个约束条件类型为“≤”第i个约束条件类型为“=”关系3一般对偶关系minz=CTXs.t.AX≤bX≥0maxw=bTYs.t.ATY≤CY≤0几种形式的对偶关系maxz=CTXs.t.AX≤bX≥0minw=bTYs.t.ATY≥CY≥0maxz=CTXs.t.AX=bX≥0minw=bTYs.t.ATY≥CY：自由求对偶问题例题maxω=7y1+4y2-2y3minZ=3x1+2x2-6x3+x52y1+y2-y3≤32x1+x2-4x3+x4+3x5≥7y1+

4、3y3≤2x1+2x3-x4≤4-4y1+2y2≤-6-x1+3x2-x4+x5=-2y1-y2-y3≥0x1，x2，x3≥0;3y1+y3=1x4≤0;x5无限制y1≥0y2≤0y3无约束3.2对偶问题的基本性质1对称性：对偶问题的对偶问题是原问题对偶的对偶就是原始问题minz’=-CTXs.t.-AX≥-bX≥0maxw`=-bTYs.t.-ATY≤-CY≥0minw=bTYs.t.ATY≥CY≥0maxz=CTXs.t.AX≤bX≥0对偶的定义对偶的定义2弱对偶性：极大化原问题的任一可行解的目标函数值，不大于其对偶问题任意可行

5、解的目标函数值3最优性：X°、Y°分别为原问题与对偶问题的可行解，且CX°=Y°b，则两者均为最优解。P774对偶定理：LP问题的P和D问题1）若一个问题有最优解，则另一问题也有最优解，且目标函数值相等。2）原问题无界，对偶问题无可行解。5兼容性原始问题的检验矢给出对偶问题的一个基本解6、原始问题和对偶问题最优解之间的互补松弛关系minz=CTXs.t.AX≥bX≥0maxy=bTYs.t.ATY≤CY≥0minz=CTXs.t.AX-XS=bX,XS≥0maxy=bTYs.t.ATY+YS=CY,YS≥0XTYS=0YTXS=0对

6、偶引进松弛变量Y，YsX，Xs引进松弛变量互补松弛关系y1yiymym+1ym+jyn+mx1xjxnxn+1xn+ixn+m对偶问题的变量对偶问题的松弛变量原始问题的变量原始问题的松弛变量xjym+j=0yixn+i=0(i=1,2,…,m;j=1,2,…,n)在一对变量中，其中一个大于0，另一个一定等于0[例4]求解下列LP问题，并给出对偶问题的最优解MaxZ=x1+2x22x1+2x2≤80x1+2x2≤4x1,x2≥0对偶问题为:Minw=8y1+4y22y1+0y2≥12y1+2y2≥2y1,y2≥0最优解为:x1=2,x

7、2=2,x3=0,x4=0y1=1/2,y2=1/2,y3=0,y4=0Cj1200CbxBbx1x2x3x40x30x400201221084y3y4y1y24/2=2/8/2=44/2=2Min20101/2-100102x3x22101/2-1/220101/2001/21/2-1-2004201-1x1x2y3y4y1y212y3y4y1y2463.3对偶的经济解释原始问题是利润最大化的生产计划问题单位产品的利润（元/件）产品产量（件）总利润（元）资源限量（吨）单位产品消耗的资源（吨/件）剩余的资源（吨）消耗的资源（吨）W=

8、yb=(y1…ym)b1bm…=b1y1+b2y2+…+bmymbi：第i种资源的数量yi：对偶解bi增加bi,其它资源数量不变时,目标函数的增量Z=biyi3.3对偶的经济解释Zbi=yi对偶解y：b的单位改变量所引起的目标函数