原问题、对偶问题、一对对偶问题.ppt

《原问题、对偶问题、一对对偶问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章线性规划的对偶理论线性规划问题具有对偶性，即任何一个求极大值的线性规划问题，都有一个求极小值的线性规划问题与之对应，反之亦然．原问题、对偶问题、一对对偶问题对偶理论（DualityTheory）[dju(:)’æliti]研究对偶问题之间的关系及其解的性质根据对偶理论，在解原问题的同时，也可以得到对偶问题的解，并且还可以提供影子价格等有价值的信息，在经济管理中有着广泛的应用．为什么研究对偶理论？对偶问题可能比原问题容易求解对偶问题还有很多理论和实际应用的意义§1对偶问题的一般概念§2对偶问题的基本性质

2、§3对偶问题的解§4对偶问题的经济解释——影子价格§5对偶单纯形法§6原始——对偶单纯形法§1对偶问题的一般概念对偶问题的提出对偶问题的形式1.1对偶问题的提出资源的合理利用问题，即充分利用资源生产两种产品大规模定制生产时代，充分利用资源生成所需的产品对外提供加工服务，收取加工费存在一个矛盾自己要赚钱，定价越高越好定价太高，别人不找你折中——保证不亏的前提下，对方的支出最少例1甲乙限额材料2332工时4523利润（元/件）1020问题假设不是安排生产，而是出售材料，出租工时，问如何定价，可使工厂获利不低于安

3、排生产所获得的利益，且又能使这些定价具有竞争力解决设出售材料的定价为每单位y1元出租工时的定价为每工时y2元1.2对偶问题的形式对称型对偶问题非对称型对偶问题混合型对偶问题1.对称型对偶问题定义1矩阵形式原问题对偶问题增加内容对偶规则给每个原始约束条件定义一个非负对偶变量yi(i=1,2,…,m);使原问题的目标函数系数cj变为其对偶问题约束条件的右端常数；使原问题约束条件的右端常数bi变为其对偶问题目标函数的系数；将原问题约束条件的系数矩阵转置，得到其对偶问题约束条件的系数矩阵；改变约束条件不等号的方向，

4、即将“=<”改为“>=”；原问题“max”型，对偶问题为“min”型．例32.非对称型对偶问题例4对偶规则原问题第k个约束为等式，对偶问题第k个变量是自由变量。原问题第k个变量是自由变量，则对偶问题第k个约束为等式约束。3.混合型对偶问题对偶约束另外，我们把约束条件分为行约束（变量的线性组合的等式或不等式约束）和变量的符号约束两部分，而以原问题的行约束与对偶问题的变量一一对应，原问题的变量与对偶问题的行约束一一对应，并且将对应的一对约束称为一对对偶约束．例5例3用矩阵理论讨论对偶问题设原问题：可用另一形式：

5、XBXNXSXBXNXS表示线性规划问题已得到最优解.令则由(4)有由(2)和(3),有故有因为而Y的上限无限大,所以只存在最小值.由上讨论,可得另一个线性规划问题:称为原线性规划问题的对偶规划问题。原问题PrimeProblem对偶问题DualProblem原问题与对偶问题的对应关系原问题求极小------原问题约束方程有“≥”------两边同乘（-1），“≤”原问题约束方程有“=”------对偶问题？§2对偶问题的基本性质对称性弱对偶性无界性最优性强对偶性互补松弛性解的对应性产品A，B产量X1，X2

6、，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+120y2

7、3y1+3y2-y3+y5=5y1+4y2-y4+y6=6minW=48y1+120y2+My5+My64812000MMy1y2y3y4y5y6yB11M48-4M120-7MMM00My5533-1010My66140-101yB180+1/2M18-9/4M0M30-3/4M0-30+7/4MMy51/29/40-13/41-3/4120y23/21/410-1/401/4yB18400824M-8M-2448y12/910-4/91/34/9-1/3120y213/9011/9-1/3-1/91/3

8、y=(2/9,13/9),Z=184观察结论:①一对对偶问题都有最优解，且目标函数值相等。②最优表中有两个问题的最优解。对称性定理1（对称性定理）对偶问题的对偶是原问题。弱对偶性定理2（弱对偶性）证明推论1最大化问题的任一个可行解的目标函数值都是其对偶最小化问题目标函数的下界；最小化问题的任一个可行解的目标函数值都是其对偶最大化问题目标函数的上界。无界性推论2若原问题（对偶问题）为无界解，则其对偶问题（原问题）无