资源描述：
《运筹学对偶单纯形法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第三章对偶模型•线性规划的对偶关系•线性规划的对偶性质•对偶单纯形法3.1.1对偶问题例1：资源分配模型某装备厂拟生产甲、乙两种新产品，每件利润分别为300元和200元。甲、乙产品的部件分别在A、B两个车间生产，每件甲、乙产品的部件分别消耗A、B车间1,2小时。两种产品的部件最后都要在C车间装配，装配每件甲、乙产品分别消耗2小时和3小时。已知A、B、C车间每周可用于这两种产品的最大生产能力分别为6小时、8小时、18小时。该工厂应如何安排生产才能使得工厂获利最大？工时利润产品单耗（工时/件）最大生产能力（百元/工时）车间甲乙（工时/天）yA1061yB0282yC23183单位利润32ω（百元
2、/件）由于原拟用于生产每件甲产品的1个A工时和2个c工时能创造3百元利润，所以出租上述数量的各资源的盈利起码应不低于3百元。w=6y+8y+18y1231y+0y+2y≥3①1230y+2y+3y≥2②123y，y，y≥0③123minw=6y1+8y2+18y3y1+2y3≥3s.t.2y2+3y3≥2y1,y2,y3≥0Y*=(5/3,0,2/3)Tw*=22maxz=3x1+2x2z*=22x1≤62x2≤8s.t.2x1+3x2≤18x1，x2≥0X*=(6,2)T3.1.2对偶关系关系1：规范对偶关系(P1):maxz=CTXAX≤bs.t.X≥0(D1):minw=bTYATY≥
3、Cs.t.Y≥0我们称LP问题(P1)与(D1)为规范原始、对偶问题，并称二者之间的对应关系为规范对偶关系。max型x1≥0x2≥0min型y1≥010≤6y2≥002≤8y3≥023≤18≥≥w32zminw=6y+8y+18y1231y+0y+2y≥3①123s.t.0y+2y+3y≥2②123y，y，y≥0③123关系2：标准形LP问题的对偶关系(P2):maxz=CTXAX=bs.t.X≥0(D2):minw=bTYATY≥Cs.t.Y自由例1maxz=3x1-1x2-2x33x1+2x2-3x3=6y1s.t.1x1-2x2+1x3=4y2x1,x2,x3≥0minw=6y1+4y
4、23y1+1y2≥32y1-2y2≥-1s.t.-3y1+1y2≥-2y1,y2自由关系3：一般对偶关系对偶问题(P)(D)目标要求maxmin规范不等式≤≥约束的式号系数阵(aij)m×n(aji)n×m第k个约束第k个变量函数约束个数变量个数约束第k个右端常数第k个价值系数与(非)规范不等式约束非负(正)变量变量等式约束自由变量例2minω=3x1+2x2-1x32x1+1x2+3x3≥2s.t.3x1-5x2≤51x1+1x2+1x3=1x1≤0,x3≥0解maxz=2y1+5y2+1y32y1+3y2+1y3≥3s.t.1y1-5y2+1y3=23y1+1y3≤-1y1≥0,y2≤0
5、,y3自由例3minω=2x1+x2+3x3+4x41x1+3x2+2x3+x4=5s.t.2x1-2x2+3x3≤13x1+1x2-2x3≥2x1≥0,x2≤0,x4≥0解maxz=5y1+1y2+2y31y1+2y2+3y3≤2s.t.3y1-2y2+1y3≥12y1+3y2+1y3=3y≤41yy3≥0y1自由,2≤0,3.2线性规划的对偶性质性质1对称性规范原始、对偶问题(P1)与(D1)互相对偶。性质2弱对偶性设X,Y分别为(P1)与(D1)的任意可行解，则CTX≤bTY性质3最优性设X,Y分别为(P1)与(D1)的可行解，则当CTX=bTY时，X,Y分别是(P1)与(D1)的最优
6、解。性质4线性规划的对偶定理对(P1)与(D1)而言：(1)若其中一个问题有最优解，则另一个问题也有最优解，且二者最优值相等。（强对偶性）(2)若其中一个问题的解无界，则另一个问题无可行解。（无界性）注意：(2)之逆命题不成立。因为一个问题无可行解时，另一个问题可能解无界，也可能无可行解。性质5互补性原始问题与对偶问题的变量或基本解之间具有互补性。决策变量vs松弛变量基变量vs非基变量T(P1):maxz=CTX(D1):minw=bYATY≥Cs.t.AX≤bs.t.X≥0Y≥0T(Ps):maxz=CTX(Ds):minw=bYATY-Ys=Cs.t.AX+Xs=bs.t.X,Xs≥0Y
7、,Ys≥0XvsYsxjvsym+jYvsXsyivsxn+jy=σi=1,2,…,min+iy=σj=1,2,…,nm+jj性质6兼容性原始问题的检验矢给出对偶问题的一个基本解。c32000jxxxxx比值基解123453x16101000x44004/31-2/32x201-2/301/3222005/302/3yyyyy45123σσσσσ12345X*=(6,2,0,4,0)T,z*=22互补基本解Y
