第章 对偶模型ppt课件.pptVIP

第3章对偶模型 2 3 1线性规划的对偶关系 3 3 1 1对偶问题 例3 1 考虑范例 这是一个分配三种有限资源 即A B C三个车间每周最大生产能力6 8 18个工时 于两项生产活动 即生产甲 乙两种产品 的资源分配或经营规划问题 假如该厂因故不能投产甲 乙两种新产品 而已调拨完毕的资源闲置不用是一种浪费 因此 现拟将原用于生产这两种产品的三种有限资源 即各车间的工时 全都承揽对外加工 则应如何考定这三种工时的价格 4 3 1 1对偶问题 解 由于价格等于成本加利润 而这三个车间的生产成本在不长一段时间内相对稳定 可视为常数 故只需考定这三种工时的利润 为此 将A B C三个车间承揽对外加工每个工时可获得的利润设为y1 y2 y3 元 工时 将这三个车间的生产能力6 8 18个工时全用于对外加工所获总利润为w 元 周 见表3 1 5 3 1 1对偶问题 将式 0 作为目标函数 将式 作为约束条件 初步 构成一个LP模型 只不过目标要求尚待确定 Max Min 6 3 1 1对偶问题 本例与范例反映了同一个实际经济问题的两个侧面 或同一问题的两种对偶提法 称范例为原本问题或原问题 称本例为范例这个原问题的对偶问题 称式 3 1 为原本模型 称 3 2 为对偶模型 也可称LP模型 3 1 3 2 为原本 对偶问题 实际上这二者互为对偶 将LP模型 3 2 的变量y1 y2 y3称为对偶变量 它们构成的向量记为 Y y1 y2 y3 T称为对偶变矢 其维数等于原本模型的阶数m 本例即为m 3 由前已知 对偶问题和原问题的最优值恰好相等 w 22 z 这不是偶然 7 3 1 2对偶关系 8 3 1 2对偶关系 这两个相互对偶的LP问题 P1 D1 具有相同的三类参数A b C 因此知道其中任一问题 则另一问题可由上述关系1中的模型结构唯一确定 9 3 1 2对偶关系 在表3 3中 将第 行和式号 列遮住 余下就是对偶模型 D1 而将第 列和式号 行遮住 余下就是原本模型 P1 不难由已知模型确定另一模型 写出下列线性规划的对偶问题 解 课堂练习1 11 3 1 2对偶关系 12 例3 2 写出下列LP问题的对偶模型 在表3 4中 将第 行和式号 遮住 余下就是对偶问题 据此 不难写出对偶模型 D2 对比关系1与关系2的问题 P 与 D 不难看出 1 P 与 D 的目标要求大小相反 max min2 P 与 D 的系数阵互为转置阵 aij m n aji n m3 P 与 D 的变量与约束相互对应关系如下 13 3 1 2对偶关系 与模型自身目标相反者为规范 相同者为非规范 综上 可以归纳得出更一般的对偶关系 14 15 写出LP模型的一般步骤 1 按 0 由已知模型的目标要求推定对偶模型的目标要求 2 按 由已知模型的约数个数推定对偶模型的变量个数 3 按 由已知模型的右端常数推定对偶模型的目标函数 4 按 a b c 由已知模型的变量数据推定对偶模型的约束数据 5 按 d 由已知模型的变量形式推定对偶模型的约束形式 6 按 由已知模型的约束形式推定对偶模型的变量形式 16 例3 3 试写出下列Lp模型的对偶问题 写出下列线性规划的对偶问题 解 y1 0 y2 0 y3无约束 课堂练习2 18 3 2线性规划的对偶性质 线性规划的对偶关系具有良好的性质及其经济意义 学习对偶性质有助于加深了解线性规划的基本性质 19 3 2 1基本性质 20 3 2 1基本性质 其思路是 现将 D1 等价化成 P1 的形式 然后推导出其对偶模型恰是 P1 于是 可按 P1 D1 的规则 由 PD 推导出 DP 再将 DP 化成等价的 P1 21 3 2 1基本性质 22 3 2 1基本性质 23 3 2 1基本性质 24 3 2 1基本性质 z 22 w 问题 P1 D1 的决策变量的个数分别为2和3 二者不相等 标准化后 问题 Ps Ds 的变量个数就相等了 均为5个 即变矢X Y的维数相同 其中蕴含着一种互补性 3 2 1基本性质 更一般的规范原本 对偶问题及其标准型 26 3 2 1基本性质 27 3 2 1基本性质 28 3 2 1基本性质 因此 若要求解原本 对偶问题 则可采用单纯形法 只需任解其一 便能得到二者的解 这恰是单纯形法的独特属性 原本 对偶兼容性 所具高超成效与实用价值的体现 综上 可将原本 对偶问题互补基本解的不同情况加以分类 见表3 11 30 3 2 1基本性质 两式意味着 原变量与其补变量 一个 0 松弛 一个 0 拘紧 二者具有松紧性 也可谓互补松弛性 由于这是基本解互补变量的松紧性 故简称基本松紧性 以区别后述最优解的类似性质 32 3 2 1基本性质 33 3 2 1基本性质 由于这是最优解互补变量的松紧性 故简称最优松紧性 其内涵与性质7类同 3 2 2经济属性 影子价值和影子利润是韩大卫提出的 35 3 2 2经济属性 影子价值的概念 在按线性规划的最优经营方案经营n项活动时 当前已投入的bi个单位第i种资源中 每一个单位资源i为n项经营活动所创造的总价值z所做贡献 韩大卫提出影子价值有些怪异 忘记了 边际 范建平 36 影子价格 37 影子价格 38 39 3 2 2经济属性 3 2 2经济属性 3 2 2经济属性 42 3 2 2经济属性 43 44 3 2 2经济属性 45 46 47 3 3对偶单纯形法 48 基于互补基本解均为可行必然均为最优这一重要结论 单纯形法的思路 始终保持原基本解可行 将对偶基本解由不可行化为可行 相应的检验数全为非负 则二者同时最优 对偶单纯形的思路 始终保持对偶可行 将原本基本解由不可行化为可行 也能使二者最优 若初始单纯形表满足表3 12所列对偶单纯形法的前提条件 对偶可行 0 则称为符合规范 相应的方法称为规范对偶单纯形法 49 3 3 1规范对偶单纯形法 3 3 1规范对偶单纯形法 这表明对偶单纯形法确定的主元为负数 与原本单纯形法确定的主元取值符号相反 10 27 51 例3 4 试用对偶单纯形法 求解范例原LP问题的对偶问题 解 由前表3 7得范例的标准形对偶问题 a b c 表3 13c给出的一对最优互补基本解 同表3 8 3 9结果一致 3 3 2人工对偶单纯形法 例3 5 求解下列LP问题 据以建立单纯形表 但应注意 按式 2 4a 计算当前目标值z0时 目标函数中的常数项3M应加给z0 如表3 14 a 所示 所有检验数已非负 符合规范 依法接续运行 a b c 原问题有两个极点最优解 56 原本 对偶单纯形法的相同点 基准相同 都基于互补基本解均为可行必然均为最优这一准则 进化规程相同 都须在关注对象的可行域内 找出并始于一个起点 寻沿 棱线 进化到另一极点 基本步骤相同 都有6步 且每一步的主旨相同 核心内容大致类同 基本算法相同 换基运算 工具相同 单纯形表 结果相同 都得到相同的一对最优互补基本解 或判明问题无解 57 58 3 3 3交替单纯形法 交替单纯形法 是指在求解一个LP问题的过程中 交替使用原本 对偶单纯形法两种方法 而无须顾及二法的前提 现用哪一种方法并无一定之规 可酌情而定 一般可先用对偶单纯形法 将单纯形表化为原本可行 然后用原本单纯形表接续运行 注意 由于交替单纯形法一开始并未满足所用二法前提 所以对问题无解的判定必须慎重 必须满足所用方法的前提 才能依法判断 作出无解结论 59 例3 6 求解下列LP问题 建立单纯形表求解 见表3 16 60 例3 6 求解下列LP问题 a b c 61 例3 7 求解下列LP问题 建立单纯形表求解 见表3 17 62 例3 7 求解下列LP问题