资源描述：
《对偶问题.ppt.convertor》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第2章线性规划的对偶理论Duality对偶DualProblem对偶问题DualLinearProgramming对偶线性规划DualTheory对偶理论2.1问题的提出例：某企业计划生产甲、乙两种产品，该两种产品均需要A、B、C、D四种不同的材料，按工艺资料规定，生产一单位甲乙产品需要各种材料数量及单位产品利润如表中所示。问:如何安排产品的生产计划,才能使企业获利最大?1.最大生产利润模型设企业生产甲产品为X1件，乙产品为X2件，则maxz=2X1+3X2s.t2X1+2X2£12X1+2X2£84X1£164X2£12X
2、1³0,X2³02.资源最低售价模型(原问题)<========>(对偶问题)设第i种资源价格为yi,（i=1,2,3,4,）则有minw=12y1+8y2+16y3+12y4s.t2y1+y2+4y3+0y4³22y1+2y2+0y3+4y4³3yi³0,(i=1,2,3,4)y1y2y3y42.2原问题与对偶问题的关系一般表示式：原问题：maxz=c1X1+c2X2+┈+cnXns.t a11X1+a12X2+┈+a1nXn£b1a21X1+a22X2+┈+a2nXn£b2 ····················
3、···am1X1+am2X2+┈+amnXn£bmxj³0，j=1,2,┈,n对偶问题：minw=b1y1+b2y2+┈+bmym s.t a11y1+a21y2+┈+am1ym³c1a12y1+a22y2+┈+am2ym³c2 ·························a1ny1+a2ny2+┈+amnym³cnyi³0，(i=1,2,···,m)典式模型对应对偶结构矩阵表示（1）maxz=CXs.tAX£bX³0minw=Ybs.tYA³CY³0对偶问题原问题对偶模型其他结构关系（2）若模型为maxz=CX
4、s.tAX³bX³0maxz=CXs.t-AX£-bX³0变形minw=Ybs.tYA³CY£0Minw=Y´(-b)st.Y´(-A)³CY´³0令Y=-Y´对偶问题对偶变量Y¢（3）maxz=CXs.tAX£bX£0变形设X=-X´max=-CX´st.-AX´£bX´³0minw=Ybs.tYA£CY³0则有minw=Ybs.t-YA³-CY³0对偶问题典式：用矩阵形式表示：（1）maxz=CXminw=Ybs.tAX£b<========>s.tYA³CX³0Y³0（2）maxz=CXminw=Ybs.tAX³b<=
5、=======>s.tYA³CX³0Y£0（3）maxz=CXminw=Ybs.tAX£b<========>s.tYA£CX£0Y³0原问题（或对偶问题）对偶问题（或原问题）目标函数MaxZ目标函数MinW约束条件数：m个第i个约束条件类型为“≤”第i对偶变量数：m个第i个变量≥0第i个变量≤0第i个约束条件类型为“≥”第i个约束条件类型为“=”个变量是自由变量决策变量数：n个第j个变量≥0第j个变量≤0第j个变量是自由变量约束条件数：n第i个约束条件类型为“≥”第i个约束条件类型为“≤”第i个约束条件类型为“=”例2-3
6、写出下面线性规划的对偶问题：课堂练习：写出下面线性规划的对偶规划：下面的答案哪一个是正确的？为什麽？（原问题是极小化问题，因此应从原始对偶表的右边往左边查！）例题2minZ=3x1+2x2-6x3+x52x1+x2-4x3+x4+3x5≥7x1+2x3-x4≤4-x1+3x2-x4+x5=-2x1，x2，x3≥0;x4≤0;x5无限制maxω=7y1+4y2-2y32y1+y2-y3≤3y1+3y3≤2-4y1+2y2≤-6y1-y2-y3≥03y1+y3=1y1≥0y2≤0y3无约束2.3对偶问题的基本性质Maxz=CXM
7、inw=Ybst.AX£bst.YA³CX³0Y³0(1)弱对偶性：若X0——原问题可行解，Y0——对偶问题可行解则CX0£Y0b证明：∵Y0³0，AX0£b，∴Y0AX0£Y0b，而Y0A³C，∴CX0£Y0AX0，∴CX0£Y0AX0£Y0b（2）最优性：若X0——原问题可行解，Y0——对偶问题可行解，且CX0=Y0b则X0——原问题最优解，Y0——对偶问题最优解证明：设X*——原问题最优解，Y*——对偶问题最优解则CX0£CX*£Y*b£Y0b但CX0=Y0b，∴CX0=CX*=Y*b=Y0b∴X0=X*，Y0=Y*即
8、X0——原问题最优解，Y0——对偶问题最优解证毕。（3）无界性若原问题最优解无界，则对偶问题无可行解证：有性质1，CX0£Y0b，当CX0®∞时，则不可能存在Y0，使得CX0£Y0b。注：逆定理不成立，即如果原问题（对偶问题）无可行解，那么对偶问题（或原问题）“解无界”不成立。（4）强对偶
