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

第三章 线性规划的对偶理论;线性规划问题具有对偶性，即任何一个求极大值的线性规划问题，都有一个求极小值的线性规划问题与之对应，反之亦然． 原问题、对偶问题、一对对偶问题 对偶理论（Duality Theory） [ dju(:)’?liti ] 研究对偶问题之间的关系及其解的性质 根据对偶理论，在解原问题的同时，也可以得到对偶问题的解，并且还可以提供影子价格等有价值的信息，在经济管理中有着广泛的应用．;为什么研究对偶理论？;;§1 对偶问题的一般概念;1.1 对偶问题的提出;例1;;问题;解决;;1.2 对偶问题的形式;1. 对称型对偶问题;;矩阵形式;对偶规则;例3;;;2. 非对称型对偶问题;;;;例4;;对偶规则;;原问题第k个约束为等式，对偶问题第k个变量是自由变量。 原问题第k个变量是自由变量，则对偶问题第k个约束为等式约束。;;;3. 混合型对偶问题;;;;对偶约束;例5;;例3;;;用矩阵理论讨论对偶问题;因为;原问题与对偶问题的对应关系;§2 对偶问题的基本性质;产品A，B产量X1，X2，Z为利润;X=(8,24)T Z =184;3y1+3y2 ?5 y1 +4y2? 6; 48 120 0 0 M M y1 y2 y3 y4 y5 y6 yB 11M 48-4M 120-7M M M 0 0 M y5 5 3 3 -1 0 1 0 M y6 6 1 4 0 -1 0 1 yB 180+1/2M 18-9/4M 0 M 30-3/4M 0 -30+7/4M M y5 1/2 9/4 0 -1 3/4 1 -3/4 120 y2 3/2 1/4 1 0 -1/4 0 1/4 yB 184 0 0 8 24 M-8 M-24 48 y1 2/9 1 0 -4/9 1/3 4/9 -1/3 120 y2 13/9 0 1 1/9 -1/3 -1/9 1/3;观察结论:;;对称性;弱对偶性;推论1;无界性;推论3;例1;;;例2;;例3;最优性;;强对偶性;根据弱对偶性定理，有;根据最优性判别定理，Y*也是最优解;推论4;一对对偶问题的关系;互补松弛性;;;互补松弛条件;互补松??条件;互补松弛关系（松紧关系）;松约束与紧约束;结论;推论5;松紧关系的实际意义;w1 wi wm wm+1 wm+j wn+m ;max z=3x1+4x2-x3 s.t. 4x1+2x2+5x3≤38 -x1+3x2- x3≥18 2x1- x2+3x3≤26 3x1+ x2- 2x3 ≥10 x1, x2, x3≥0;例4;;;先松后紧！！！;;非对称对偶问题的互补松弛条件;对于非对称形式的对偶问题，因为此时 Y*无正负限制，所以只有一个成立 ;混合型对偶问题;例5;;;;结论;解的对应性;推论;;;;单纯形乘子定理;§3 对偶问题的解;利用原问题的最优单纯形表求对偶最优解;;;例1