实用管理运筹学 第3章 单纯形法和对偶理论.ppt

由于 且 ，由矩阵乘法可知，行向量 的每一个分量乘以对应列向量 的每一个分量的结果都“ ”，因此，要使行向量 乘以列向量 的结果为0，只能是行向量 的每一个分量乘以对应列向量 的每一个分量的结果都“ ”。则如果 的第 个分量 时， 的第 个分量 必为0，即 。同样，当 时， 。 同理可证，若 ，则 ；若 ，则 。 证明：若原问题和对偶问题的可行解分别为 ，由弱对偶性可知， 。设 分别为原问题和对偶问题的最优解，由最优性可知， ，则可得 ，即 。 有时利用互补松弛定理，可以快速求出原问题或对偶问题的最优解。 对偶规划的基本性质 对偶规划基本性质的应用 例3-11 已知下列线性规划的对偶问题的最优解为 , ，目标函数最优值为14。试用互补松弛定理求解原问题的最优解。 将 , 代入约束不等式， 其中1、(2)和(4)式等号成立， 2、(1)和(3)式等式不成立， 即对应的松弛变量不为0。 由互补松弛定理有 。 首先写出其对偶问题 将 代入原问题的约束条件，得 又由于 ， ，由互补松弛定理可知原问题的两个约束应该取“=”， 解得 ， 。可知原问题的最优解为 ，对应的目标函数最大值为14。 对偶规划基本性质的应用 对偶问题的经济解释 设 是原问题 的最优基， 是其对偶问题的最优解，则 对 求导得： 因此，变量 的经济意义表现为在其他条件不变的情况下，单位资源变化所引起的目标函数值的变化。 代表当原问题达到最优时，第i种资源的“估价”。这种估价是特定资源在特定问题中的特殊价格，称为“影子价格(Shadow Price)”。 只有当约束条件表示的是资源限制时，该约束条件才有对应的影子价格，此时影子价格等于对偶价格。 对偶问题的经济解释 影子价格的经济意义： 影子价格反映了资源对目标函数的边际贡献及资源转化成效益的效率。影子价格越大，则资源对目标函数的边际贡献越大，资源转化成效益的效率越大。 影子价格反映了资源的稀缺程度。当某种资源的影子价格大于0时，表示这种资源稀缺，且影子价格越大，资源越稀缺；当某种资源的影子价格等于0时，说明这种资源有剩余或供大于求。 影子价格对市场有调节作用。影子价格不同于市场价格，是在特定问题中资源使用者赋予资源的一个估价，而资源的市场价格是其价值的客观体现，随供求关系的变化，价格围绕价值波动。在完成市场经济的条件下，当某种资源的市场价格低于影子价格时，就买进资源；当市场价格高于影子价格时，就卖出资源。 PART 6 对偶单纯形法 对偶单纯形法 对偶单纯形法也是解决线性规划问题的一种方法。 对偶单纯形法是在保持原问题所有σi ≤0的情况下，通过迭代，使所有约束条件常数bj ≥0，最后求得最优解。 对偶单纯形法使用上有局限性，主要是大多线性规划问题很难找到初始解使其所有检验数均σi ≤0。 初始解可以是非可行解，当检验数都非正时就可以进行基变换，这时不需要加入人工变量，因此可以简化计算。 对于决策变量多于约束条件的线性规划，用对偶单纯形法可以减少计算工作量，因此对于决策变量较少，约束条件较多的线性规划，可以写出它的对偶问题，再用对偶单纯形法求解。 在做线性规划常数项灵敏度分析时，有时用对偶单纯形法可以简化计算。 对偶单纯形法的步骤如下： 步骤1：根据线性规划问题列出初始单纯形表。 步骤2：检查常数列，如果常数列的所有分量都 ，且检验数均 ，则已经得到最优解，停止计算。如果常数列中至少还有一个负分量，且检验数均 ，则进行以下计算。 步骤3：确定出基变量：在常数列中找到一个最小的负分量，即 ，则这个负分量所在行的基变量 为出基变量。 步骤4：确定入基变量：检查出基变量 所在行的各系数 ，如果所有的 都 ，则无可行解，停止计算。如果存在 为负数，则计算所有为负数的 与其对应的检验数 的比值，找出其中的最小值，即 ，则其对应的非基变量 为入基变量。 步骤5：以 为主元，按原单纯形法在表中进行迭代，得到新的单纯形表，重复步骤2~4。 对偶单纯形法 例3-12 用对偶单纯形法求