对偶问题及对偶单纯形法完整课件-002

第四章线性规划的对偶理论DualityTheory线性规划的对偶问题对偶问题的基本性质对偶问题的经济解释-一影子价格对偶单纯形法灵敏度分析第1页、对偶问题的提出对同一问题从不同角度考虑,有两种对立的描述例1、应如何安排生产计划,使一天的总利润最大?某企业生产甲、乙两种产品,要用A、B、C三种不同的原料。每生产1吨甲产品,需耗用三种原料分别为1,1,0单位;生产1吨乙产品,需耗用三种原料分别为1,2,1单位。每天原料供应的能力分别为6,8,3单位。又知道每生产1吨甲产品企业利润为300元,每生产1吨乙产品企业利润为400元原料单位利润产品BC01(百元)供应量116128第2假设该企业决策者决定不生产甲、乙产品,而是将厂里的现有资源外售。决策者应怎样制定每种资源的收?费标准才合理?原料单位利润产品BC(百元)甲乙24供应量68设x,表示第j种产品每天的产量maxz=3x1+4x2st.x1+x2≤6x1+2x2≤8x<30,x,≥0第3页分析问题:1、出让每种资源的收入不能低于自己生产时的可获利润;、定价不能太高,要使对方能够接受原料单位利润产品BC(百元)甲乙128013供应量6设y表示第j种原料的收费单价把生产一吨甲产品所用的原料出让,所得净收入应不低于生产甲产品的利润:y+y223mIn6y+8y,+34s.t:w=6y1+8y2+3y+2y2+y3≥4只能在满足>所有产品的y,y2,y3≥0利润的条件下,其总收入尽可能少,才能成交原问题与对偶问题的对应关系Pmaxz=3x+4Dminw=6y,+8y,+3yt.(x+x2≤6yy1+2y2+y3≥4x2y1,y2,y3≥0x1,x2≥0y表示对第j种资源的估价矩阵形式:maxz,=(34minw=(683)y2st.11y33Xz0maxz=CXminw=b/stAX≤bst[ATY≥CrX>0(一)对称型对偶问题变景maxz=CX且约束条minw=h7大时均取s.t(AX<h极小时s.t(AY>C/Y>0maxx=cr1+Cxx2+…+Cxnminw=b1y1+b2y2+.+bmyst(a1rx1+a12x2+…+a1xn≤bs.t.(a1P1+a21y2+.+amPm2CIritart,xxn≤b2(P)D)r?aV,tax≥0(=1,2,…,n)≥0(i其中y≥0(i=1,2,…,m)称为对偶变量第7页二)非对称型对偶问题max<=Cr+C2e2tcyts.t(a1r1+a1xx2+aixr3sba3x1+a32+a3xr3≥b3x1≥0,x20,x3无约束分析:化为对称形式。令2=-x2x=x3-x3(x3≥0,x3≥0)maxZ=C-r-C2x2+C3r3-c3x3s.t(q1--a1252+a13-a13x2s621-a2xa2r+a22x2-a23-3+a23x3s-b2I+a3252-a33x+a3rrs-bax≥0二)非对称型对偶问题max=Ci-5-C2x2tC3r3-C3r3对偶变量a1x1-12x2+a133-a33≤by1a2r-5-a2252+a2352-a2sb2x3+a2x3≤-b23+a22-a3x3+a3≤-bx2,x3,xy20对偶问题:minw=by+by-by-b,yt(a11+a212-a2122-a31y32Cy3y3-an331-a3y2+a3y2+a33y32-Cay1,y2,y2,y3≥0二)非对称型对偶问题令y2=y2y2minw=by,+,y?-b,y?,y3minw=by,+b,y,+by.t(a151+a2122-a2122-a31332Gst(1121+a2132+a3y32Ca2y3≤C2a13y1+a23y2-a23y2-a3y3≥C3a13y+a23y2+a3y32C3a13y-a2y2+a23y2+a3y32a13y+a2y2+a3y3≤C3y,y2,y2,y320y1≥0,y2无约束,y≤0m