运筹学-用对偶分析原问题最优解(名校讲义)PPT课件

第三讲用对偶分析原问题最优解 1初步分析线性规划解的几种可能性 2线性规划解的求解方法之一 图解法 3对偶性质及平衡定理 4基础解及基础可行解 1初步分析线性规划解的几种可能性 1 已知线性规划的标准形式为AX b X O CTX min满足前2条的解为可行解 同时又满足第3条的为最优解 从解的性质看 线性规划有下述几种可能 1 不存在可行解或无解 例如规划x1 x1 0无可行解3x1 min 1初步分析线性规划解的几种可能性 2 2 存在可行解 但找不到最优解 例如规划x1 x2 0 x1 x2 0 2x1 min显然 令x1 x2 为任意非负值都是可行解 当 则目标函数 2x1 故找不出使目标函数取极小值的具体解X 1初步分析线性规划解的几种可能性 3 3 存在最优解 但不是唯一的 例如规划x1 x2 1x1 x2 ox1 x2 min显然两点连线上的所有点都是最优解 见图1 1 4 一般情况有无穷多可行解 但有唯一最优解 2线性规划解的求解方法之一 图解法 1 例1 3 求解下述线性规划2x1 x2 x3 4 1 xj 0j 1 2 3 2 3x1 5x2 min 3 将 1 式中的x3移至右边 常数4移至左边 得 2x1 x2 4 x3 0移项得 2x1 x2 4于是变为两维线性规划问题 其约束可行域可用直角坐标系表示 如图1 2 2线性规划解的求解方法之一 图解法 2 图1 2中 阴影部分为可行域 若要求出最优点 必须作出目标函数的等值线 然后令等值线向最小值方向 即最优方向 移动 直到离开可行域的瞬间为止 此时的交点即为最优点 图中直线L1 L2 L3即为目标值分别为12 9及6的等值线 L3与可行域的顶点B x1 2 x2 0 L3再向左下方移动 必离开可行域 于是该点即为线性规划之最优解 即 X x1 x2 x3 2 0 0 目标值为3x1 5x2 6 图解法简单易行 但只适于两维问题 本题虽是三维 但很容易变为两维 对于高维问题 只能采用其它的办法求解 很幸运 该法已经找到 这就是以后将要介绍的单纯形法 3对偶性质及平衡定理 1 1 弱对偶性 不等式性质 设原线性规划为AX b X 0 CTX min其对偶规划为YTA CT YTb max若X Y分别是原问题和对偶问题的可行解 则必存在关系式CTX YTb证明 因为X Y分别是原问题及对偶问题的可行解 因此YTAX YT AX YTb及YTAX YTA X CTX故CTX YTb这是一个很有用的性质 因为有时并不需要精确求出线性规划问题最优解 只需了解最优目标值的范围 那么采用求解对偶可行解就显得十分方便 3对偶性质及平衡定理 2 2 强对偶性 对偶最优性 若分别是原问题与对偶问题可行解 且 则必分别是原问题及对偶问题的最优解 证明 设X是原向题任一可行解 则从弱对偶性知 可见是原问题最优解 同理 设Y是对偶问题任一可行解 则 故是对偶问题最优解 3对偶性质及平衡定理 3 1 平衡定理设原问题为 4 xj 0 j 1 2 n 5 6 其对偶形式为 7 8 3对偶性质及平衡定理 4 则平衡定理阐述如下 若xj j 1 2 n 和yi i 1 2 m 分别是原问题和对偶问题之可行解 必存在下述关系 即弱对偶性 上式中两边相等的充分必要条件是 或xj 0或xj 0 但 3对偶性质及平衡定理 5 证明 根据 5 式和 7 式可得 9 3对偶性质及平衡定理 6 证明 若使 即表明 9 式左边为0 不等式变为等式 而该式是由n项和组成 每一项是两因子乘积 每个因子都 0 故每一项都 0 若使n项为0 势必使每一项为0 即 则其中至少有一个因子为0 于是得出 或xj 0 或xj 0 必使 3对偶性质及平衡定理 7 从强对偶性知 符合平衡定理第 条时的可行解X Y必是最优解 于是 平衡定理为寻找线性规划最优解提供了一种方法 亦即 在若干个问题的可行解X中 若是有一组解所对应的对偶可行解 使得Xj 0所对应的对偶约束条件为等式 则此时的解必为最优解 例1 4 应用平衡定理解下述规划 3对偶性质及平衡定理 8 其对偶形式为首先令原问题中任两个变量为0 因有2个约束条件 这样可求出唯一解 试探求出一组原问题可行解 例如 令x1 x4 0 则得 3对偶性质及平衡定理 9 故此时X 0 2 3 0 T是原问题可行解 为检验是否为最优解 令非零xj对应的对偶约束为等式 求平衡解Y 即令将y1 y2值代入式 12 及式 15 看是否满足 5 1 4 12 9 11 13全满足 可见Y是符合平衡定理的对偶解 因此 X 0 2 3 0 T及Y 1 1 T分别是原问题及对偶问题的最优解 此时目标函数值CTX YTb 16 3对偶性质及平衡定理 10 显然 一次成功是一咱巧合 最坏情况 本例需次才能找到 当维数增大 这种枚举法的计算量会呈现指数般急剧增长而变为不现实 以后将重点阐述有实用价值的单纯形法 4基础解及基础可行解 1 一 基础解定义令X满足 AX b 若X 0 则X必有非零分量x x 于是必存的方程式 1 其中a a 为与x x 对应的A阵列矢量 如果列矢量a a 之间线性独立 则称X为基础解 4基础解及基础可行解 2 线性独立的定义 或判断准则 为 若方程中的矢量系数 必须全为零才能使方程满足 则称矢量a a 之间线性独立 即 任何一个矢量都不能由其它矢量的线性组合所构成的一组矢量必线性独立 例如 中 则知a1 a2 a3之间线性相关 即线性不独立 因为任何一个矢量都可由其它两个矢量所组成 但是这三个矢量中 两两之间线性无关 独立 4基础解及基础可行解 3 若存在多个不同的非零基础解 则它们之间组合系数之和为1的线性组合也必是方程解 即方程必存在无穷多个解 二 基础可行解定义满足等式约束AX b及自变量限制X 0的解称为可行解 既是可行解又是基础解解的解称为基础可行解 即基础解与可行解之交集称为基础可行解 基础可行解是可行域的顶点 它是可行解的一部分 基础可行解在线性规划的求解中具有特殊重要性 下面将阐述并证明关于它的重要定理 4基础解及基础可行解 4 三 定理对于下述标准线性规划1 如果存在可行解 则必存在基础可行解 2 如果存在最优解 则必存在基础最优解 定理1证明 设 规划已有一个可行解X 且具有正分量x x 如果无正分量 则X本身即为落在原点的基础可行解 如果正分量x x 对应的A阵列矢量a a 线性独立 则X即为基础可行解 如果不独立 则在下述方程 4基础解及基础可行解 5 中 3 至少有一项 i 0 不失一般性 令 0且 0 否则等式两边乘以 1 设 4 其中 x x 0则用 4 式 3 式得 5 4基础解及基础可行解 6 如果 足够小 则仍可使 5 式左边系数 0 0 即仍可使新的X为可行解 选取于是新的