运筹学—2对偶原理.ppt

定理2-4 主对偶定理 若原始问题和对偶问题两者均可行，则两者均有最优解，且此时目标函数值相同。 证明要点： 第一部分——证明两者均有最优解。 由于原始问题和对偶问题均可行，根据弱对偶定理知两者均有界，于是均有最优解。 第二部分——证明在达到最优时，两个问题的目标函数值相等。 证明思路：利用单纯形法的特征，就非对称形式的对偶问题给出 第一步：给出原始问题形式和对偶问题形式； (D) (L) 设原始问题有对应于最优基B的最优基本可行解X=（XB，0）T, 则有XB=B-1b。 第二步：利用单纯形法的矩阵描述，由单纯形法最优性判别定理得出重要结论 ,并引出“单纯形乘子”的定义 ； 令 A=（B,N），所以对应于最优基B的检验数满足 （最优单纯形乘子） 定义 第四步：进一步证明 是对偶问题的最优解，并验证两个问题的目标函数值相等。 第三步：证明最优单纯形乘子就是对偶问题的可行解； 所以， 是对偶问题的可行解。 又 根据最优性准则定理，这时的 正是对偶问题的最优解。 定理2-4 互补松弛定理：如果X和Y分别是原问题和对偶问题的可行解，它们同时为最优解的充要条件是（C-YA)X=0和Y(b-AX)=0 设原问题和对偶问题的标准型是 原问题 对偶问题 max z = CX A X + XS = b X, XS ≥0 min S= Yb YA - YS = C Y , Y S ≥0 z = ( YA - YS ) X S= Y( A X + XS ) 根据定理3 最优性准则，X，Y要为最优解，则Z，S必须相等。即： ( YA - YS ) X = Y( A X + XS) YS X + YXS=0 根据非负条件，X≥0， Y≥0， XS≥0， YS≥0，显然有 YS X =0， YXS=0，即（C-YA)X=0，Y(b-AX)=0 必要性证明： 互补松弛定理：如果X和Y分别是原问题和对偶问题的可行解，它们同时为最优解的充要条件是（C-YA)X=0和Y(b-AX)=0 设原问题和对偶问题的标准型是 原问题 对偶问题 max z = CX A X + XS = b X, XS ≥0 min S= Yb YA - YS = C Y , Y S ≥0 z = ( YA - YS ) X = YA X - YS X =YAX+(C-YA)X S= Y( A X + XS ) = Y A X + YX S =YAY+Y(b-AX) 根据定理3 最优性准则得出X，Y分别为原问题与对偶问题的最优解 充分性证明： 互补松弛定理：如果X和Y分别是原问题和对偶问题的可行解，它们同时为最优解的充要条件是（C-YA)X=0和Y(b-AX)=0 （1）如果原问题的某一约束为紧约束（松弛变量为零），则约束对应的对偶变量应大于或等于零。 （2）如果原问题的某一变量为松约束（松弛变量大于零），则对应的对偶变量比为零。 （3）如果原问题的某一变量大于零，该变量对应的对偶约束必为紧约束。 （4）如果原问题的某一变量等于零，该变量对应的对偶约束可能为紧约束，也可能为松约束。 例；已知线性规划问题 Z 已知其对偶问题的最优解为 试用对偶理论找出原问题的最优解。 S Z S * * 2.1单纯形法的矩阵描述 一、为什麽要研究单纯形法的矩阵描述？ 进一步讨论修正单纯形法 便于理论推导（如对偶定理的证明） 二、怎样进行矩阵描述？ 关键——写出两个基本的表达式。 第二章? 线性规划的进一步研究 1、准备工作： （1）标准型的矩阵形式—— （2）将式中矩阵写成分块矩阵形式 2、将分块形式代入矩阵形式标准型，得出两个基本表达式： （1）由约束条件 可得 用非基变量表示基变量的表达式： （2-1） （2）将式（2-1）代入目标函数的表达式，可得： 用非基变量表示目标函数的表达式： （3）借助一个恒等式推出用非基变量表示目标函数的另一个等价表达式： 代入式（2-2），并令 （2-4） 单纯形乘子 三、单纯形表格的矩阵形式： cj ? CB ? XB xj b CB CN ? ? 0 ? 一、对偶问题的提出 1、? 对偶思想举例 周长一定的矩形中，以正方形面积最大；面积一定的矩形中，以正方形周长最小； 2．2 对偶原理 2、? 换个角度审视生产计划问题 例2