数学规划基础-9(全集).pdf

Tianjin University 4 4 求一个线性规划的对偶求一个线性规划的对偶 当求一个给定线性规划的对偶 我们称给定的线性 规划为原问题原问题 prime 如果原问题是最大化问 题 对偶将是最小化问题 反之亦然 为方便起 见 我们定义最大化问题的变量为 最小化问题的变量为 我们首先 介绍如何得到一个所有变量都为非负和所有约束 都是 的最大化问题 称为标准最大化问题标准最大化问题 的 对偶 一个标准最大化问题可以写为 Tianjin University 如式 16 所示标准最大化问题的对偶定义为 如式 17 所有约束都是 和所有变量都非负的最小化问题 称为标准最小化问题标准最小化问题 如果原问题是类似式 17 的标准 最小化问题 我们定义式 17 的对偶是式 16 Tianjin University 求一个标准最大或最小化问题的对偶求一个标准最大或最小化问题的对偶 Tianjin University 家具公司问题为 Tianjin University 求对偶的表格法很清楚地表明第i个对偶约束与第i个 原问题变量 相对应 例如 第一个对偶约束对 应于 课桌 因为约束的每个系数都来自于 原问题的 课桌 列 相似地 第二个对偶约 束相应于 饭桌 第三个对偶约束相应于 椅子 以一个相似的方式 对偶变量 与第i 个原问题约束相联系 例如 与第一个原问题 约束 木材约束 相联系 因为在对偶中 的每 个系数均来自于木材约束 或木材的可利用性 Tianjin University 我们现在求一个最小化问题的对偶 Tianjin University 求一个非标准线性规划的对偶求一个非标准线性规划的对偶 Tianjin University 为了将一个最大化问题转化为标准最大化形式 我们 进行如下操作 步骤步骤1 将每个 约束乘以 1 将它转化为一个 约束 例如 在式 18 将被转化为 步骤步骤2 以两个不等式约束 一个 约束和一个 约束 替换每个等式约束 然后将 约束转化为 约束 例如 在式 18 中 我们用两个不等式 和 替换 然后我们将 转 化为 步骤步骤3 如同在3 11节 用 替换每个无符号约 束变量 其中 和 在式 18 中 我们将 用 替换 Tianjin University 当这些转换完成后 式 18 已经被转化为如下 等 价 线性规划 Tianjin University 如果原问题不是一个标准最小化问题 我们可以通过下 面的步骤将其转化为标准最小化问题 步骤步骤1 通过乘以 1将每个 约束转化为 约束 例如 在式 19 中 将 转化为 步骤步骤2 用一个 约束和一个 约束替换每个等式约束 然后将 约束转化为一个 约束 例如 式 19 约束 等价于 和 将 转化为 我们发现可以用两个约束 和 替换约束 步骤步骤3 用 替换任意无符号约束变量 其中 和 对式 19 应用这些步骤得到如下标准最 小化问题 Tianjin University Tianjin University 我们可以使用下面的法则在不对非标准形式线性规划 使用前面介绍的转换的情况下得到它的对偶 求一个非标准最大化问题的对偶求一个非标准最大化问题的对偶 步骤步骤1 填写表9以使原问题可以横着读出 步骤步骤2 做完如下变换后 对偶可以像正常情况下竖向 读出 a 如果第i个原始约束是一个 约束 相 应的对偶变量 必定满足 b 如果第i个原始 约束是一个等式约束 对偶变量 现在为无符号约 束 c 如果第i个原始变量是无符号约束 第i个 对偶约束将是一个等式约束 Tianjin University 将这个方法应用于式 18 由表9得到表12 Tianjin University Tianjin University 求一个非标准最小化问题的对偶求一个非标准最小化问题的对偶 步骤步骤1 填写表9以使原问题可以竖着读出 步骤步骤2 做完如下变换后 对偶可以像正常情况下横 向读出 a 如果第i个原始约束是一个 约束 相应的对偶变量 必定满足 b 如果 第i个原始约束是一个等式约束 对偶变量现在为 无符号约束 c 如果第i个原始变量是无符号 约束 第i个对偶约束将是一个等式约束 Tianjin University Tianjin University Tianjin University 4 5 对偶问题的经济学解释对偶问题的经济学解释 一个最大化问题对偶的解释一个最大化问题对偶的解释 家具公司问题的对偶是 家具公司问题的相互关系见表16 Tianjin University 假设一个企业家想买走家具公司的所有资源 那么 企业家必须确定他 她 愿意支付给家具公司单 位资源的价格 在此条件下 我们定义 这些资源需要支付的总价格是 由于 购买资源的成本需要最小化 是该线性规划问题的目标函数 Tianjin University 在确定资源价格时 企业家面对什么样的约束 资 源价格必须被设置的足够高以促使家具公司出售 例如 企业家必须至少提供给家具公司60元来 购买8板英尺木材 4个油漆工时和2个木匠工时 的资源组合 因为如果家具公司愿意 它可以使 用这些资源生产一张课桌并以60元出售 由于企 业家为生产课桌的资源提供的价格是 他 她 必须选择 以满足 但这只是家具公司对偶的第一个 或课桌 约束 Tianjin University 相似的原因表明至少需要30元用来支付生产饭桌的 资源 6板英尺木材 2个油漆工时和1 5个木匠工 时 这意味着 必须满足 这是家具公司对偶的第二个 或饭桌 约束 相似地 第三个 或椅子 对偶约束是 将所有条件放在一起 我们看到家具公司问题对偶 的解得到木材 油漆工时和木匠工时的价格 前 面的讨论也表明第个对偶变量的确很自然地对应 于第个原始约束 Tianjin University 归纳起来 当原问题是一个标准最大化问题 对偶 变量与决策者可用的资源量有关 由于这个原因 对偶变量常称为资源影子价格资源影子价格 resource shadow prices 有关影子价格的更深入讨论见 4 7节 Tianjin University 一个最小化问题对偶的解释一个最小化问题对偶的解释 为了解释一个最小化问题的对偶 我们考虑2 4节食 谱问题的对偶 在4 4节 我们得到食谱问题的对 偶是 食谱问题的数据见表17 Tianjin University 假设约翰是一个 营养 售货员 他出售大卡 巧 克力 糖和脂肪 他希望人们通过购买大卡 糖 脂肪和巧克力来满足日常的营养需要 约翰必 须确定 Tianjin University 约翰希望从出售给顾客的日常营养需求搭配中获得 最大收入 由于他从顾客那里将得到 美分收入 约翰的目标函数是 在设置营养的价格时 约翰必须将价格设得足够低 以保证顾客有足够的兴趣从他那购买所有营养 例如 用50美分买了一块核仁巧克力饼 顾客可 以得到400大卡 3盎司巧克力 2盎司糖和2盎司 脂肪 因此约翰对这个营养组合的要价不能超过 50美分 这得到如下 核仁巧克力饼 约束 Tianjin University 相似地推理得到第二个对偶 冰激凌 约束 第 三个对偶 汽水 约束和第四个对偶 干酪饼 约束 Tianjin University 4 6 对偶法则和结果对偶法则和结果 本节 我们讨论线性规划中最重要的成果之一 对 偶理论 本质上 对偶理论说明原问题和对偶问 题有相等的目标函数值 如果问题有最优解 为了简化表述 我们假设原问题是有m个约束n个变 量的标准最大化问题 那么对偶问题将是有m个 变量n个约束的标准最小化问题 在这种情况下 原问题和对偶问题可以写为如下形式 Tianjin University Tianjin University 弱对偶弱对偶 如果我们选择原问题中的任意可行解和对偶中的任 意可行解 可行对偶解的w值至少与原问题可行 解的z值一样大 这个结果由引理1正式表述 引理引理1 弱对偶 设 是原问题的任意可行解 是对偶问题 的任意可行解 那么 Tianjin University 证明证明 由于 将式 22 中第i个原问题约束 乘以 将得到如下不等式 将式 24 m个不等式相加 我们得到 由于 将式 23 中第j个对偶约束乘以 得 到如下不等式 将式 26 n个不等式相加 我们得到 Tianjin University 比较式 25 和式 27 我们得到 如果已经存在原问题或对偶问题的一个可行解 可 以使用弱对偶来得到另一个问题的最优目标函数 的界限 例如在家具公司问题中 很容易得到 是原始可行的 这个解有z值 60 30 20 110 现在弱对偶表明任何对偶可行 解 必须满足 Tianjin University 由于对偶是一个最小化问题 并且任意对偶可行解 一定有 这表明对偶的最优w值 见下 图 这表明弱对偶使我们可以使用任意原始可 行解来限制对偶目标函数的最优值 Tianjin University 相似地 我们可以使用对偶的任意可行解来产生原 问题目标函数最优值的界限 例如 查看家具公 司对偶 可以很容易验证 是 对偶可行的 这个对偶解的对偶目标函数值是 由弱对偶我们知道任何 原始可行解 必须满足 Tianjin University 由于原问题是一个最大化问题并且每个原始可行解 都有 我们可以得到原问题的最优目标函数 值 的结论 见下图 Tianjin University 如果我们定义 那么对于一个点 原始目标函数值可以写为 对于一个点 对偶目标函数值可以写为 我 们现在使用弱对偶来证明下面重要的结论 Tianjin University 引理引理2 设 是原问题的一个可行解 是对偶问题 的一个可行解 如果 那么 是原问题的最 优解 是对偶问题的最优解 证明证明 由弱对偶我们知道对于任何原始可行点 这样任何原始可行点的z值必定不超过 由于 是原始可行的 并且有原始目标函数值 必是原始最优的 相似的 由于 是原始可行的 弱对偶表明对于任何对偶可行点 Tianjin University 这样 任何对偶可行点的目标函数必定超过 由 于 是对偶可行的 并且对偶目标函数值 必是对偶的最优解 Tianjin University 对偶定理对偶定理 在证明对偶定理前 我们注意到可以使用弱对偶证 明下面的结果 引理引理3 如果原问题无界 对偶问题不可行 自己证 明 引理引理4 如果对偶问题无界 原问题不可行 自己证 明 我们设 最优原目标函数值 最优对偶目标函 数值 如果原问题有最优解 下面的重要结果 对偶理论 描述原问题和对偶问题之间的关系 Tianjin University 定理定理1 对偶定理 对偶定理 假设 是原问题的一个最优基 那么 是对偶的一个最优解 同时 证明证明 用来证明对偶定理的论据包括如下三步 1 使用 是原问题一个最优基的事实证明 是 对偶可行的 2 证明最优原始目标函数值 的对偶目标函 数值 3 我们已经得到了有相同目标函数值的一个原始可 行解 从 和一个对偶可行解 从引 理2 我们现在可以得到对于对偶 是最优 的 并且 的结论 Tianjin University 我们现在验证关于原始问题是一个有n个变量 m个 约束的标准最大化问题情况下的步骤1 对原问题 增加松弛变量 后 我们将原问题和对偶 问题写成如下形式 Tianjin University 设 是原问题的一个最优基 并定义 这样 对于最优基 是 的第i个元素 由于对于原问题是 最优的 在原始单纯