原问题、对偶问题、一对对偶问题VIP免费

第三章线性规划的对偶理论•线性规划问题具有对偶性，即任何一个求极大值的线性规划问题，都有一个求极小值的线性规划问题与之对应，反之亦然．•原问题、对偶问题、一对对偶问题•对偶理论（DualityTheory）–[dju(:)’æliti]–研究对偶问题之间的关系及其解的性质•根据对偶理论，在解原问题的同时，也可以得到对偶问题的解，并且还可以提供影子价格等有价值的信息，在经济管理中有着广泛的应用．为什么研究对偶理论？–对偶问题可能比原问题容易求解–对偶问题还有很多理论和实际应用的意义§1对偶问题的一般概念§2对偶问题的基本性质§3对偶问题的解§4对偶问题的经济解释——影子价格§5对偶单纯形法§6原始——对偶单纯形法§1对偶问题的一般概念1.对偶问题的提出2.对偶问题的形式1.1对偶问题的提出•资源的合理利用问题，即充分利用资源生产两种产品•大规模定制生产时代，充分利用资源生成所需的产品•对外提供加工服务，收取加工费•存在一个矛盾–自己要赚钱，定价越高越好–定价太高，别人不找你•折中——保证不亏的前提下，对方的支出最少例1甲乙限额材料2332工时4523利润（元/件）1020235432322010max212121xxxxxxZ问题•假设不是安排生产，而是出售材料，出租工时，问如何定价，可使工厂获利不低于安排生产所获得的利益，且又能使这些定价具有竞争力解决•设出售材料的定价为每单位y1元•出租工时的定价为每工时y2元205310422332min212121yyyyyyW235432322010max212121xxxxxxZ205310422332min212121yyyyyyW1.2对偶问题的形式1.对称型对偶问题2.非对称型对偶问题3.混合型对偶问题1.对称型对偶问题•定义1矩阵形式•原问题•对偶问题增加内容对偶规则1.给每个原始约束条件定义一个非负对偶变量yi(i=1,2,…,m);2.使原问题的目标函数系数cj变为其对偶问题约束条件的右端常数；3.使原问题约束条件的右端常数bi变为其对偶问题目标函数的系数；4.将原问题约束条件的系数矩阵转置，得到其对偶问题约束条件的系数矩阵；5.改变约束条件不等号的方向，即将“=<”改为“>=”；6.原问题“max”型，对偶问题为“min”型．例32.非对称型对偶问题例4对偶规则原问题第k个约束为等式，对偶问题第k个变量是自由变量。原问题第k个变量是自由变量，则对偶问题第k个约束为等式约束。3.混合型对偶问题对偶约束•另外，我们把约束条件分为行约束（变量的线性组合的等式或不等式约束）和变量的符号约束两部分，而以原问题的行约束与对偶问题的变量一一对应，原问题的变量与对偶问题的行约束一一对应，并且将对应的一对约束称为一对对偶约束．例5例3用矩阵理论讨论对偶问题设原问题：01maxXbAXCXZ可用另一形式：0SSX,XbIXAXCXZmax00NBCCbINBXBXNXSbBCBCNBCCbBBNBIBBBN1111110XBXNXS4003020111BCNBCCBBCCBSBNNBBB表示线性规划问题已得到最优解.令,BCYB1则由(4)有0Y由(2)和(3),有,ABCCB01故有CYA因为,1YbbBCZB而Y的上限无限大,所以只存在最小值.由上讨论,可得另一个线性规划问题:05minYCYAYbW称为原线性规划问题的对偶规划问题。0X,bAXCXZmax原问题PrimeProblem对偶问题DualProblem原问题与对偶问题的对应关系原问题求极小------ZMAXZmin原问题约束方程有“≥”------两边同乘（-1），“≤”原问题约束方程有“=”------对偶问题？§2对偶问题的基本性质•对称性•弱对偶性•无界性•最优性•强对偶性•互补松弛性•解的对应性产品A，B产量X1，X2，Z为利润例1、3X1+X2+X3=483X1+4X2+X4=120X1…X40maxZ=5X1+6X23X1+X2483X1+4X2120X1,X20机器台时劳动工时X=(8,24)TZ=1845600X1X2X3X4XB056000X34831100X41203(4)011801/200-3/20X318(9/4)01-1/46X2303/4101/418400-2/9-13/95X18104/9-1/96X22401-1/31/33y1+3y25y1+4y26minW=48y1+120y23y1+3y2-y3+y5=5y1+4y2-y4+y6=6minW=48y1+120y2+My5+My64812000MMy1y2y3y4y5y6yB11...