《工学单纯形》PPT课件.ppt

1 从图形解到代数解的转换 2 A B C D E F 最优点 1 2 0 0 方程组有m 2个方程和n 4个变量 因此最大数目的角点为 解空间 到底令哪些点为零才能对应一个特定的角点 0 0 4 5 0 2 5 1 5 0 x1 x2 s1 s2 2 0 0 3 3 可以看到 当问题的大小增加后 即m与n变大 枚举所有角点的过程包含巨量的计算 如m 10和n 20 必须求解184756个10 10阶的方程 而在很多实际的问题中 很多是有成百上千的变量和约束的问题 4 单纯形方法 单纯形方法的迭代本质 A B C D E F 最优点 x1 1 x2 2 正常情况下 单纯形从原点 A点 开始 此时Z 0 能否在当前零值的基础上 通过增加非基变量x1和x2来增加Z值 图形显示 增加x1和x2将增加Z 单纯形方法每次要求增加一个变量 且选择使得Z有最大改善率的那个变量 因此选择增加x2具有最大改善率 因此增加x2直到角点B 在点B 再增加X1的值 达到改进的角点C 他是最优点 因此单纯形方法的路径是沿着A B C 沿着路径的每个角点与一步迭代是对应的 单纯形方法是沿着解空间的边缘移动 不能抄近路 直接A C 5 A B C D E F 最优点 1 2 0 0 0 2 5 1 5 0 2 0 0 3 0 0 4 5 单纯形方法的本质就是换基 6 可以看到 在基变量和非基变量中的变化模式随着解沿着路径A B C的移动而改变 A B 在A处的非基变量x2变成B处的基变量 并且在A处的基变量s2变成在A处的非基变量 称X2为进基变量 s2为离基变量 类似地 在点B x1进基 s1离基 因此到了C点 7 ReddyMikks公司使用M1和M2两种原料生产内 外墙涂料 其基本数据如下 市场调查表明 内墙涂料日需求量不超过外墙涂料的日需求加上1吨 内墙涂料的最大日需求量是2吨 定义x1 外墙涂料的日生产吨数 x2 内墙涂料的日生产吨数 8 完整的ReddyMikks模型是MaxZ 5x1 4x2St6x1 4x2 24 原料M1 x1 2x2 6 原料M1 x1 x2 1 市场限制 x2 2 需求限制 x1 x2 0 9 单纯形算法的计算细节 初始解是最优解吗 目标函数表明可以增加x1或x2来改进这个解 选择具有最正的系数的变量x1为进基变量 这个等价于将目标函数中最负系数的变量作为进基变量 最优性条件 该条件确定进基变量 单纯形迭代开始于原点 x2 x2 0 0 因此 在初始点处的非基 零 变量 x1 x2 在初始点处的基变量 s1 s2 s3 s4 即Z 0 s1 24 s2 6 s3 1 s4 2 10 从单纯形表中确定离基变量的方法是 计算方程的右端项 解列 与相应的在进基变量x1下方的约束系数的非负比 可行性规则 最小非负比自动识别当前基变量s1作为离基变量 并指定进基变量x1的新值为4 11 a b c d 1 4 6 1 2 3 4 5 6 1 2 3 5 s1 0 s2 0 s3 0 s4 0 1 1 1 24 6 4 6 1 6 A B C 在点B处的非基 零 变量 s1 x2 在点B处的基变量 x1 s2 s3 s4 12 进基变量和离基变量如何 交换 一些概念 13 基于高斯 乔丹行操作来计算新的基本解 1 枢轴行a 在基列中 以进基变量替换离基变量b 新的枢轴行 当前枢轴行 枢轴元素2 其他所有行 包括Z行新的行 当前行 当前枢轴列的系数 新的枢轴列 将该方法应用到上表 在基列中 以x1替换s1新的x1行 当前s1行 6 064100024 6 012 31 60004 新的Z行 当前Z行 5 新的x1行 1 5 400000 5 012 31 60004 10 2 35 600020 新的s2行 当前s2行 1 新的x1行 01201006 1 012 31 60004 004 3 1 61002 新的s3行 当前s3行 1 新的x1行 0 1100101 1 012 31 60004 005 31 60105 新的s4行 当前s4行 0 新的x1行 00100012 0 012 31 60004 00100012 14 新的基本解是 x1 s2 s3 s4 因此新的单纯形表为 新的基本解是 x1 s2 s3 s4 4252 而Z 20与下面的公式计算结果一致 新的Z 原来的Z 新的x1的值 它的目标系数 0 4 5 20 15 在前表中 最优性条件表明 x2是进基变量 由可行性条件可得下表 因此 s2离开基本解 并且x2的新值是1 5 相应增加的Z值是2 3x2 2 3 1 5 1 它产生新的Z 20 1 21 在基列中 用进基变量x2替换s2 应用高斯 乔丹行运算 有 1 新的枢轴行x2行 当前s2行 4 3 2 新的Z行 当前Z行 2 3 新的x2行 3 新的x1行 当前x1行 2 3 新的x2行 4 新的s3行 当前s3行 5 3 新的x2行 5 新的s4行 当前s4行 1 新的x2行 16 这些计算产生新的单纯形表为 基于最优性条件 Z行中相应于非基变量s1和s2的系数没有一个是负的 因此最后的单纯形表是最优的 17 单纯形的计算结果还给出了资源的使用情况 如果松弛变量为零 表明资源全部用完 该资源是匮乏的如果松弛变量为正 表明资源尚有余存 该资源是充裕的 18 单纯形方法的总结 最优性条件在极大化 极小化 问题中 进基变量是Z行中具有 最正 系数的非基变量 如有多个可任选其一 当非基变量的所有Z行系数是非负的 非正的 时 迭代达到最优 可行性条件对于极大化 极小化 问题 离基变量都是具有最小非负比 带有严格的正分母 的基变量 如有多个可任选其一 高斯 乔丹行运算 1 枢轴行a 在基列中 用进基变量替换离基变量b 新的枢轴行 当前枢轴行 枢轴元素 2 包括Z的所有其他行新行 当前行 枢轴列系数 新的枢轴行 决定进基变量 决定离基变量 19 单纯形方法总结 第1步确定初始基本可行解第2步用最优性条件选择一个进基变量 如果没有进基变量 停止计算 上一个解就是最优的 否则转第3步 第3步用可行性条件选择离基变量 第4步用适当的高斯 乔丹行运算确定新的基本解 转到第2步 20 单纯形法的进一步拓展 所有约束是 并且有非负右端的线性规划方便地提供了全部为松弛变量的初始基本可行解 带有 和 的约束的线性规划求解过程中 需要增加人工变量以扮演松弛变量的角色 然后在迭代中加以适当处理 21 大M方法 大M方法以等式形式的线性规划开始 如果第i个约束没有松弛变量 则将人工变量Ri加入到初始解中 类似于所有松弛变量为基本解的情况 然后在目标函数中对他们指定非常大的惩罚 强迫人工变量在最优解中等于零 如果问题有可行解 该种情况总会发生 惩罚规则 已知M为一个充分大的数 人工变量的目标系数表示为适当的惩罚 如果 22 Minz 4x1 x2s t 3x1 x2 34x1 3x2 6x1 2x2 4x1 x2 0 Minz 4x1 x2s t 3x1 x2 34x1 3x2 x3 6x1 2x2 x4 4x1 x2 x3 x4 0 松弛变量 剩余变量 Minz 4x1 x2 MR1 MR2s t 3x1 x2 R1 34x1 3x2 x3 R2 6x1 2x2 x4 4x1 x2 x3 x4 R1 R2 0 初始解 R1 R2 x4 3 6 4 23 M可以不采用代数运算的传统 并用数值代替 以简化表达 M值应该多大 依赖于初始线性规划的数据 M相对于初始目标系数必须充分大 使得M能起到惩罚作用 迫使人工变量在最优值为零 也不希望M太大 否则在计算机求解中 非常大的数与非常小的数值在一起运算时 可能产生严重的四舍五入 本例似乎取M 100 24 在进行单纯形方法之前 需要将z行与表的其余部分保持一致 在表中 x1 x2 x3 0 初始基本解 R1 R2 x4 3 6 4 z 100 3 100 6 900 而不是z行右端当前显示的0 这种不一致是由于R1 R2在目标函数中有非零系数 100 100 造成的 在所有松弛变量为初始解中 Z行的松弛变量系数为0 25 为此 在z行选用适当的约束方程替换出R1和R2 注意到橙色部分 用100乘以R1和R2行的每一行 求和之后加到z行 替换出R1和R2 即 X1为进基 最正系数 26 可行性条件 选择R1为离基变量 27 采用高斯 乔丹运算可以计算出如下 最后的单纯形显示x2和R2分别是进基变量与离基变量 连续采用单纯形计算 再经过两步的迭代即可达到最优 最优解为x1 2 5 x2 9 5 z 17 5 R1 0 R2 0 x3 1 x4 0 28 如果线性规划没有可行解 在最终的单纯形迭代中 使用惩罚项将不能迫使人工变量取值为零 此时至少有一个人工变量取正值 29 两阶段法 大M方法中惩罚值的使用 可能会导致大的求解误差 两阶段法分两个阶段来求解线性规划 阶段一试图求一个初始基本可行解 找到一个解以后 调用阶段二求解原问题 30 阶段I将问题变成等式约束形式 并在约束中增加必要的人工变量 如大M方法一样 以保证找到一个初始基本解 接下来 求相应方程的基本解 无论线性规划是求极大化还是极小化 总是使得人工变量之和达到最小 如果其和的最小值为正 则线性规划问题无可行解 正的人工变量约束不满足 否则进行阶段II 阶段II使用阶段I得到的可行解作为原始问题的初始基本可行解 两阶段法的概况 31 Minz 4x1 x2s t 3x1 x2 34x1 3x2 6x1 2x2 4x1 x2 0 Minr R1 R2s t 3x1 x2 R1 34x1 3x2 x3 R2 6x1 2x2 x4 4x1 x2 x3 x4 R1 R2 0 阶段I 32 类似于大M方法中一样 在r行中的R1和R2用以下计算来替换 新的r行 旧的r行 1 R1行 1 R2行 33 采用单纯形法迭代得到如下表格 因为最小值r 0 阶段I产生了基本可行解x1 3 5 x2 6 5 x4 1 此时人工变量以完成了它的使命 从而我们能够从表中连同他们所在的列一起去掉 转入阶段II 34 阶段II Minz 4x1 x2s t x1 x3 5 3 5x2 3x3 5 6 5x3 x4 1x1 x2 0 35 基变量x1和x2在z行有非零的系数 使用下列计算将非零系数替换出去 新的z行 旧的z行 4 x1行 1 x2行 最优解为x1 2 5 x2 9 5 z 17 5 R1 0 R2 0 x3 1 x4 0 36 最优解为x1 2 5 x2 9 5 z 17 5 x3 1 x4 0 采用单纯形方法得到 37 实际上几乎所有的商业软件包都采用两阶段法来求解线性规划 实际中 大M方法由于潜在的不利的舍入误差而可能从来不用的 介绍大M方法纯粹处于历史原因 其发展早于两阶段法 在最后一张表中人工变量及其所在列被去掉 这只有在他们全部是非基变量时才会发生 如果在阶段I的最后一张表中有一个或者多个人工变量是基变量 取零值 则必须采取如下附加步 才能在阶段II开始前去掉人工变量 38 第一步选择一个零人工变量离开基本解 并指定它所在的行为枢轴行 进基变量可以是枢轴行具有系数非零的任意非基变量 完成相应的单纯法迭代 第二步从表中去掉刚刚离基的人工变量的列 如果所有的人工变量已经被去掉转入阶段II 否则转回第一步 第一步的目的是保持基变量的可行性将不受影响 不论其枢轴元素是正还是负的总能使得零人工变量变为非基变量 39 单纯形法的特殊情况 本节考虑单纯形法中的4种情况 退化 可选择最优解 无界解 不存在 或者可行解 1 介绍这些情况的理论解释 2 提供相应的实际解释 40 退化 在单纯形方法可行性条件中 最小比值可能循环出现 可以随意打破这种循环 当这样的情况发生时 至少有一个基变量在下一次迭代中为零 并称新的解退化 Maxz 3x1 9x2Stx1 9x2 8x1 2x2 4x1 x2 0 41 在迭代中 x3和x4均可以是离基变量 在迭代1构成退化 在基变量x4出现零值 再一次迭代后 达到最优值 42 x1 9x2 8 多余约束 x1 2x2 4 超定的 了解到3条直线通过最优点 使得某些约束是多余的 该信息是有价值的 但是没有有效的计算方法能直接从表中识别多余的约束 退化的含义1 注意迭代1和2 你将注意到目标值没有改进 Z 18 单纯形方法有可能进入一个重复迭代的序列 永远不改进目标值 也永远不满足最优性条件 退化的含义2 两个迭代尽管对基变量和非基变量分类不一致 但对于所有的变量和目标值都产生同样的值 在迭代中 遇到退化的时候 是否可以停止计算 答案否定 因为可能出现暂时退化 43 Maxz 3x1 2x2St4x1 x2 84x1 3x2 124x1 x2 8x1 x2 0 习题 44 可选择最优解 当目标函数平行于非冗余的紧约束 bindingconstraint 即在最优解处作为方程而被满足的约束 解 目标函数可以在多于一个解点处相同的最优解 因此产生可选择最优解 Maxz 2x1 4x2Stx1 2x2 5x1 x2 4x1 x2 0 x1 x2 4 x1 2x2 5 z 2x1 4x2 最优基本可行解 B C BC上任意一点都表示了具有相同目标值Z 10的可选最优解 45 迭代1给出了最优解x1 0 x2 5 2和z 10 它与点B相一致 如何从这个表格中知道可选择最优解存在呢 看看迭代1行方程非基变量的系数 非基变量x1的系数为零 表明x1可以进入基本解而不会改变Z值 但会引起变量值的改变 迭代2正是这个情况 x1进基 x4离基 新的解点x1 3 x2 1 z 10 46 单纯形方法仅能确定B点和C点 从数学角度来说 BC上的点 x1 x2 作为点B和C的非负的加权平均 因此B x1 0 x2 5 2C x1 3 x2 1 则线段BC上的所有的点如下 当 0 为C点 当 0 为B点 否则为B到C之间 47 在实践中 可选择最优解是有用的 因为我们可以从许多解中选择而不会损害目标 例如在前例中 在B处显示只有第二项活动是正值 而在C处 两项活动都为正值 如果例子描述的是一种混合产品情形 生产两种产品比生产一种产品对于满足市场或许更加有优势 在这样的情况下C处解可能更加吸引人 48 无界解 在一些线性规划中 可以无限地增加变量的值但不破坏任何一个约束 这个就意味这解空间中至少又一个变量是无界的 其结果是 目标值可以无限制的增加 max情形 或减少 min情形 此时解空间和最优目标都是无界的 出现无界点可能是由于模型构造不合理 此类模型中最大可能的缺陷是一个或多个非多余约束没有考虑在内 一些约束参数估计错误 49 Maxz 2x1 x2Stx1 2x2 102x1 40 x1 x2 0 通过单纯形法迭代会发现 x2可以无限制的增加而不破坏任何约束 因为x2每增加一个单位 z将增加1 x2将增加至无穷 使得z无穷大 因此问题无有界解 无界解空间 无界目标值 z 2x1 x2 x1 2x2 10 无界变量的下方的系数将会产生 也就是可行性条件比的分母 是零或者负的 50 不可行解 具有不相容约束的线性规划模型没有可行解 假如所有的约束类型都是 类型并具有非负的右端项 则这种情况将永远不会出行 因为松弛变量提供了一个可行解 对于其他类型的约束 使用了人工变量 尽管在目标函数中惩罚人工变量迫使他们在最优解处取零 这仅当模型有可行空间才可能发生 否则至少有一个人工变量在最优迭代中取正 不可行解空间表明模型的构建有可能是不正确的 51 Maxz 3x1 2x2St2x1 x2 23x1 4x2 12x1 x2 0 z 3x1 2x2 2x1 x2 2 3x1 4x2 12 伪最优解 最优迭代1显示人工变量R取值为正 表明问题不可行 上图也展示了不可行解空间 由于允许人工变量为正 单纯形方法实际上已经将不等式的方向颠倒 从3x1 4x2 12变为3x1 4x2 12 这个结果为伪最优 M 100 52 灵敏度分析 在线性规划模型中 参数通常是不精确的 借助于灵敏度分析 我们能够探索这种不确定性对最优解质量的影响 例如对于某种产品估计的单位利润 如果灵敏度分析揭示在单位利润改变10 的情况下最优解保持不变 即可认为最优解比不变范围仅为1 的情况更稳健 线性规划中 模型参数 输入数据 能够在一定的限度内变化而不引起最优解的改变 这些内容涉及灵敏度的分析如果输入的数据中做特定的变化后如何得到新的最优解 53 图形灵敏度分析 考虑两种情况 最优解对于资源的可利用性 约束的右端项 变化的灵敏度分析 最优解对于单位利润或单位费用 目标函数系数 变化的灵敏度分析 54 例 右端项变化 JOBCO公司在两台机器上生产两种产品 1个单位的产品1需要2小时机器1和1小时机器2 对于产品2 一个单位产品需要1小时机器1和3小时机器2 每个单位产品1和产品2的收益分别是30美元和20美元 每台机器的日加工时间是8小时 令x1和x2分别表示产品1和产品2的日产量 则线性规划模型给出如下 Maxz 30 x1 20 x2St2x1 x2 8 机器1 x1 3x2 8 机器2 x1 x2 0 55 如果日工作能力从8小时增加到9小时 则生产能力增加的收益率是多少 2x1 x2 9 2x1 x2 8 x1 3x2 8 X1 3 2 x2 1 6 z 128 X1 3 8 x2 1 4 z 142 C D 计算出的变化率提供了模型的输入 资源 和它的输入 总收益 的直接联系 表示成为资源的单位价值 即可用资源的单位变化引起目标函数的变化 这意味着机器1的能力增加 或者减少 1个单位 将增加 或减少 收益14美元 56 尽管目标函数变化率的恰当说法是资源的单位价值 然而在技术上的名称是对偶价格 dualprice 或者影子价格 shadowprice 2x1 x2 9 2x1 x2 8 x1 3x2 8 X1 3 2 x2 1 6 z 128 X1 3 8 x2 1 4 z 142 C G B F 由右图 当机器1工作能力变化 增加或者减少 即其约束平移到线段BF的任意一点 每小时14美元的对偶价格仍然有效 这意味着 可以按照下式计算得到给定对偶价格的适用范围 机器1工作能力最小值B点 0 2 67 2 0 1 2 67 2 67小时机器1工作能力最大值F点 8 0 2 8 1 0 16小时 因此 每小时14美元的对偶价格将在如下区域保持不变2 67 机器1的工作能力 16小时 D E 57 类似方法可以验证 机器2工作能力的对偶价格是每小时2美元 它在如下区域内变化时保持不变 即约束平行移动到线段DE的任意一点时 将产生下面的限制区域 机器2工作能力最小值D点 0 4 1 4 3 0 4小时机器2工作能力最大值E点 0 8 2 8 3 8 24小时 因此 对于机器2 每小时2美元的对偶价格将在如下区域保持不变4 机器2的工作能力 24小时 机器1和机器2计算出的限制称为可行性区域 feasibilityrange 58 关于线性规划问题 对偶价格能够作出相应的经济决策 比如 问题1如果JOBCO能够增加两种机器的能力 哪种机器应该有更高的优先权 机器1和机器2的对偶价格分别为14和2美元 小时 这时优先权应该是机器1问题2一项建议提出 要以10美元 小时的额外费用增加机器1和机器2的能力 这项建议可取吗 对于机器1 每小时附加净收入为14 10 4美元 而对于机器2净收入为2 10 8美元 因此只应该增加机器1 59 问题3如果机器1的工作能力从现在的8小时增加到13小时 这个增加将如何影响最优收益 对于机器1的对偶价格是14美元 在 2 67 16 小时的区域内使用 所提出的增加到13小时落在可行域内 因此收入增加量是14 13 8 70美元 这意味着总收入将增加到 当前收益 收益变化 128 70 198美元 问题4假定机器1的工作能力可以增加到20小时 这个增加将如何影响最优收益 所提出的改变超出 2 67 16 小时这个保持14美元的对偶价格区域 因此我们只能增加到16小时 超出部分需要进一步计算才能得到答案 落在可行域之外不意味着问题无解 只是我们没有充分信息立刻作出决策 60 问题5只要资源的改变在可行域内 最优目标值的改变就等于 对偶价格 资源的改变 相应变量的最优值是多少 变量的最优值一定发生改变 然而从图解得到的信息水平并不能充分确定新值 61 例 目标系数的变化 2x1 x2 8 x1 3x2 8 X1 3 2 x2 1 6 z 128 C G B F D E z 30 x1 20 x2 C点为最优解点 收入单位数的变化 目标函数系数 将改变z的斜率 然而从右图可以看到 只要目标函数位于直线BF和DE之间 最优点将保持在C 这2个约束确定了最优点 这意味着存在一个关于目标函数系数的区域 在这个区域内最优解在C点将保持不变 62 可以写出目标函数的一般形式 Maxz c1x1 c2x2 可以想象 直线z在C处转动 并且它能够沿着顺时针和逆时针转动 最优解始终保持在点C 只要z c1x1 c2x2介于直线2x1 x2 8 x1 3x2 8之间 这意味着比值c1 c2可以在1 3与2 1之间变化 这产生如下条件 这个信息能够直接提供有关最优解的答案 例如 63 问题1假设产品1和产品2的单位收入分别改变到35美元和25美元 当前的最优解保持不变吗 新的目标函数为Maxz 35x1 25x2 解在C处保持最优 因为c1 c2 35 25 1 4 保持在最优区域 1 3 2 之间 尽管变量在最优点C的保持不变 z的最优值变到35 3 2 25 1 6 152美元 当比值落在这个区域之外 需要增加额外的计算来求出新的最优解 64 问题2假设产品2的单位收入固定在当前值c2 20美元上 相应于c1 即产品1的单位收入保持最优值不变的区域是什么 在条件中替换c2 20 得到 1 3 20 c1 2 20 即6 67 c1 40 这个区域称为c1的最优区域 并隐含的假设c2固定在20美元 尽管这一节仅处理了二维变量问题 但是这些结果奠定了对一般线性规划进行灵敏度分析的基础 65 代数灵敏度分析 右端项的变化 TOYCO通过3种操作装配3种玩具 玩具火车 卡车和汽车 这个3种操作可用时间限制分别为430 460和420分钟 这3个产品的单位收入分别为3 2和5美元 每辆火车在3种操作中的装配时间分别是1 3和1分钟 玩具卡车和汽车的时间分别是 2 0 4 和 1 2 0 令x1 x2 x3分别为每天装配玩具火车 卡车和汽车的单位数量 则规划模型如下 Maxz 3x1 2x2 5x3Stx1 2x2 x3 430 操作1 3x1 2x3 460 操作2 x1 4x2 420 操作3 x1 x2 x3 0 66 这个结果表明生产玩具卡车100 汽车230 但不生产玩具火车 收入为1350美元 67 对偶价格的确定 在增加松弛变量x4 x5 x6后 模型的约束可以写为 x1 2x2 x3 x4 430 操作1 3x1 2x3 x5 460 操作2 x1 4x2 x6 420 操作3 x1 2x2 x3 430 x4 操作1 3x1 2x3 460 x5 操作2 x1 4x2 420 x6 操作3 或者 借助于上式 我们可以是说 松弛变量上减少1分钟就等价于操作时间上增加1分钟 68 可以用上述信息从最优表的Z的方程中确定对偶价格 Z 4x1 x4 2x5 0 x6 1350 可以写成 Z 1350 4x1 x4 2x5 0 x6 1350 4x1 1 x4 2 x5 0 x6 已知松弛变量值的减少等价于在它的操作时间上的增加 因此 Z 1350 4x1 1 增加操作1的时间 2 增加操作2的时间 0 增加操作3的时间 69 这个方程显示了 1 在操作1上时间增加1分钟z将增加1美元 2 在操作2上时间增加1分钟z将增加2美元 3 在操作2上时间增加1分钟z将保持不变 概括最优表的z行如下 Z行直接产生的对偶价格如下表 70 操作3的零对偶价格意味着 分配给这个操作更多的生产时间没有经济效益 这个结果有意义 因为资源已经参与了 证据就是 在最优解中与操作3相对应的松弛变量是正值 20 即资源过多 至于操作1和2每一个松弛变量 增加1分钟将分别提高1美元和2美元 对偶价格还表明 当分配额外资源时 操作2将得到更高的优先权 因为它的对偶价格是操作1的2倍 上述计算说明对偶价格是如何从最优表的 约束中确定的 对于 约束 该方法仍然适用 但是对偶价格将于对应的 约束符号相反 等式约束则还需要 相关的 计算 71 可行性区域的确定 令D1 D2 D3分别是分配给操作1 2和3的每天生产时间的该变量 正的或者负的 模型可写为 Maxz 3x1 2x2 5x3Stx1 2x2 x3 430 D1 操作1 3x1 2x3 460 D2 操作2 x1 4x2 420 D3 操作3 x1 x2 x3 0 我们将考虑同时发生改变的一般情况 每次只改变一个变量的特殊情况将从这些结果中得到 72 具体方法是 用所修正的右端项从新计算最优单纯形表 然后获得保持解可行的条件 即最优表的右端项保持非负 为了说明右端项如何重新保持计算 我们以修正解列开始 即在初始单纯形表中使用新的右端项 430 D1 460 D2 420 D3 因此 73 在D1 D2 D3下的列与初始基本列x4 x5 x6下的那些列是相同的 这意味着当我们像在初始模型那样完成相同的单纯形迭代是 两组中的列也一定是完全相同 实际上新的最优解变成 74 新的最优表提供了如下的最优解 只要所有变量非负 则当前解保持可行 这就导出可行性条件 任意同步改变D1 D2 D3 只要满足这些不等式 都将保持解可行 如果所有的条件满足 则可在上述等式约束中直接替换D1 D2 D3 来找到新的最优解 75 假设对于操作1 2 3的可利用生产时间分别是480 440和410分钟 则D1 480 430 50 D2 440 460 20 D3 410 420 10 在可行性条件中替换 得到 76 计算表明x6 0 因此当前解并没有保持可行 需要额外的计算才能得到新的解 本课不介绍 如果资源的变化使得D1 30 D2 12 D3 10 则 新的可行解是x2 88 x3 224 x6 78 且z 3 0 2 88 5 224 1296美元 或z 1350 1 30 2 12 1296美元 77 给出的条件可以专门用于产生各自的可行性区域 这就是一次只改变一种资源的变化结果 情况1把操作1的时间从460分钟改变到 460 D1 分钟 这一变化等价于在同步条件中置D2 D3 0 得到 以上考虑的是同时发生改变的一般情况 而每次只改变一个变量的特殊情况将从一般结果中得到 78 情况2把操作2的时间从430分钟改变到 430 D2 分钟 这一变化等价于在同步条件中置D1 D3 0 得到 情况3把操作3的时间从430分钟改变到 430 D3 分钟 这一变化等价于在同步条件中置D1 D2 0 得到 79 对TOYCO模型 总结对偶价格和可行性区域如下 注意 对偶价格有效的同步可行性条件 不一定要求满足所有单个可行性区域 例如D1 30 D2 12 D3 100 则 80 这意味着对偶价格仍然可适用 因此能够从对偶价格中计算出新的最优目标值 z 1350 1 30 2 12 0 100 1356美元 1 如果约束右端项的该变量Di i 1 2 3 m 在同步改变时满足所有可行性条件 或相应的Di在单个发生改变时仍然落在可行性区域内 则对偶价格有效 2 如果同步的可行性条件不满足 或因为单个的可行性区域被破坏 对偶价格就不再有效 此时 可以用新的Di值重新解该问题 或者用后续方法来解决 81 Show Sell能够为其产品在本地电台 电视或者报纸上做广告 广告预算不超过每月10000美元 每分钟电台广告的费用是15美元 每分钟电视广告的费用是300美元 报纸的广告费用是50美元 Show Sell希望电台广告至少是电视广告的2倍 同时 推荐在一个月内至少使用5次报纸广告和不超过400分钟的电台广告 过去的经验表明 电视的广告效果是电台广告的50倍 是报纸的10倍 1 为3种媒体确定最优预算分配 2 对电台和报纸广告设置限制 从经济角度看合理吗 3 如果预算增加50 这会导致整体的广告效果按比例提升吗 82 代数灵敏度分析 目标函数 本节从之前的图形法处理的保持线性规划最优解的条件 拓展到多维的代数方法 简约费用 在TOYCO模型中 在最优表中目标Z行系数是 因此z行方程是z 4x1 x4 2x5 1350即z 1350 4x1 x4 2x5最优解建议不生产玩具火车 X1 0 该建议由z行方程的信息得到证实 因为x1在当前零值情况下 每增加一个单位将降低4美元 即Z 1350 4 1 1 0 2 0 1346美元 83 可以把Z行方程中X1的系数 4 作为费用的单位 因为它引起z的减少 但是这个 费用 来自哪里 在原来的模型中 x1的单位收入是3美元 我们还知道 每个玩具火车消耗资源 操作时间 它本身也导致费用 因此 从优化的观点来看 x1的 吸引力 依赖于单位收入与一个单位资源消耗的费用的相对值 这个关系在线性规划文献中被公式化 定义简约费用如下 单位简约费用 单位消耗资源费用 单位收入 应该尽量降低单位简约费用 以提高运营系统的效益 84 如何理解这个定义的含义 在TOYCO模型中 玩具卡车的单位收入 2美元 少于玩具火车的单位收入 3美元 然而 最优解选择生产玩具卡车却不生产玩具火车 x1 0 原因在于用于玩具卡车资源 即操作时间 的单位费用小于它的单位价格 而对于玩具火车 资源 即操作时间 的单位费用大于它的单位价格 借助于简约费用的定义 现在可以看到无利益的变量 如x1 用下面两种方法使它成为有利可图 1 增加单位收入 2 减少资源消耗的单位费用 85 在大多数情况下 单位产品的销售价格难以提高 因为这由市场决定 现实的选择是减少资源消耗 比如使得生产过程更加高效 这将在后续内容讲解 86 最优性区域的定义 现在讨论使得最优解保持不变的条件 这部分内容是基于简约费用的定义的 在TOYCO模型中 令d1 d2 d3分别是玩具火车 卡车和汽车在单位收入上的该变量 这目标函数为Maxz 3 d1 x1 2 d2 x2 5 d3 x3 我们首先处理一般化的情形 其中目标函数所有的系数做同步改变 然后再利用这个结果专门处理一次一个系数发生改变的情形 87 由于是同步改变 在初始表中z行为 不考虑dj的初始模型 根据单纯形方法选择进基变量和离基变量 进行单纯形运算 得到如下形式 除了简约费用 Z方程系数 发生改变外 新的最优表与原始的最优表完全相同 这意味着目标函数系数的改变可以只影响问题的最优性条件 88 新的z行的检查说明dj的系数直接来自最优表约束的系数 计算新的简约费用的一种方法就是 在最有表上增加新的顶行和新的最左边列 顶行的这些变量是相应于每个变量的该变量dj 最左边的列 由z行的1和每个基变量行中的dj构成 记住 对于松弛变量dj 0 89 对于每个变量 或z的值 计算新的简约费用 用最左端列相应的元素乘以它所在列的元素 并求和 然后减去顶行的元素 例如对于x1 有 注意 对于基变量应用这些计算总是产生零简约费用 这事一个已经理论证明的结果 对于解列应用相同的规则 得到Z 1350 100d2 230d3 90 因为处理的是极大化问题 所以只要对于所有的非基变量新简约费用 z方程的系数 保持非负 单纯形法迭代结束时 非基变量的系数要为正 则当前解就保持最优 因此 对于所有非基变量x1 x4 x5 有下列最优性条件 4 d2 4 3 2d3 d1 01 d2 2 02 d2 4 d3 2 0 这些条件必须同时满足才能维持当前最优解的最优性 91 为了解释这些条件的使用 假定TOYCO的目标函数从Maxz 3x1 2x2 5x3变为Maxz 2x1 1x2 6x3则d1 2 3 1美元 d2 1 2 1美元 d3 6 5 1美元 代入给定条件中 得到 92 4 d2 4 3 2d3 d1 4 4 1 3 2 1 1 6 75 0 满足 1 d2 2 1 1 2 1 0 5 0 满足 2 d2 4 d3 2 2 1 4 1 2 2 75 0 满足 结果说明 所作的上述改变仍然保持当前解 x1 0 x2 100 x3 230 最优 因此 除了目标函数变化到Z 1350 100 1 230 1 1480美元 不需要做进一步计算 如果有任何一个条件不满足的话 则必须求出新的解 到目前为止的讨论已经处理了极大化情况 对于极小化情况 差别仅是简约费用 z方程系数 必须是 0才能维持最优性 93 一般最优性条件可以确定特定的情况 这里改变量dj一次仅有一个发生变化 而不是同步改变 这种分析等价于考虑下列3种情况 当个条件可以看成是同步改变的特例 情况1在同步改变的条件中置d2 d3 0 则有 94 情况2在同步改变的条件中置d1 d3 0 则有 情况3在同步改变的条件中置d1 d2 0 则有 95 所给出的单个条件能够依照总的单位收入来表示 例如 对于玩具卡车 变量x2 总的单位收入是2 d2 相应的条件是 2 d2 8 表示成2 2 d2 2 8或0美元 玩具卡车的单位收入 10美元这个条件假定玩具火车和玩具汽车的单位收入分别固定在3美元和5美元 允许区间 0 10 美元表明 玩具卡车 变量x2 的单位收入可以是最低0美元或最高10美元而不改变当前的最优解 x1 0 x2 100 x3 230 但总收入将变化到1350 100d2 96 注意到下列事实是重要的 改变量d1 d2 d3可以均在它们所许可的单个区域内 而不必满足同步条件 反之亦然 例如 考虑maxz 6x1 8x2 3x3 这里d1 6 3美元 d2 8 2 6美元 d3 3 5 2美元 他们都在可以允许的单个区域 然而 相应的同步改变条件将产生 97 上述结果可以总结如下 1 只要改变目标函数系数的该变量dj j 1 2 n满足所有的最优性条件 当改变是同时发生时 或落在最优性区域之内 当改变是单个发生时 那么最优变量的最优值保持不变 2 对于其他的情况 也就是同步改变时最优性条件不满足或者不满足单个可行性区域 那么可以用新的dj值重新解该问题 或者应用将在后续课程介绍的后最优分析来解决此类问题 98 习题Electra公司生产4种类型的马达 每种马达在各自的装配线上装配 装配线各自的生产能力是每天500 500 800 750台马达 1型马达使用8个单位的某种电子元件 2型马达使用5个单位 3型马达使用4个单位 4型马达使用6个单位 电子元件的供应者每天提供8000件 对于每种类型的马达 每台的售价分别为60 40 25和30美元 a 确定每天的最优产品生产策略 b 现有的生产计划安排能满足Electra的需要 然而 由于竞争 Electra可能需要降低2型马达的售价 要想不改变现有的生产计划安排最多可以降价多少 c Electra还决定大幅度把所有类型的马达价格降低25 用灵敏度分析是否保持最优解保持不变 d 目前 4型马达不生产 它的价格应该在生产计划中增加多少 99 第3章对偶性与后最优分析 前一章讨论的是资源的可利用性 约束右端项 变化的灵敏度 单位利润或单位费用 目标函数的系数 变化的灵敏度分析问题 旨在回答资源该如何使用 生产量如何决策的问题 如果需要对模型的参数进行有目的的调整 求出新的最优解 则需要进行后最优分析 100 前一章讨论了利用有限的资源如何安排生产才能获得最大的利润的问题 在线性规划模型中 决策变量个数比约束的个数小得多 通过求解对偶问题可以节省计算量 因为从对偶问题的解可以自动地求出原始问题的解 现在从另一角度来讨论这个问题 对偶问题的提出 4 1对偶问题的定义 101 例 假设该工厂的决策者决定这些资源不用来生产而是考虑将其出租或出售 这时决策者就要考虑给每种资源如何定价的问题 102 数学模型 目标函数MaxZ 2x1 3x2约束条件x1 2x2 84x1 164x2 12x1 x2 0 x1 x2 设用y1 y2 y3分别表示出租单位设备台时的价格和出让单位原材料A B的价格 于是y1 4y2 22y1 4y3 3则所有资源出租和出让 其所得收入为 8y1 16y2 12y3 则得到下面的线性规划问题min 8y1 16y2 12y3y1 4y2 22y1 4y3 3y1 y2 y3 0称这个线性规划问题为原问题的对偶问题 103 在大多数线性规划处理中 其原始的形式包含最优化含义 极大化或者极小化 约束的类型 或 以及变量的方向 非负 无限制 这种处理有点混乱 对此我们给出一种单一的定义 把所有形式的原始问题自动地包含进来 这就需要我们了解对偶问题 对偶问题是由原始线性规划模型直接按照系统化定义的一种线性规划 这个问题有着极为紧密的关系 以至于一个问题的最优解自动地提供另一个问题的最优解 104 关于对偶问题的定义 要求将原始问题表示成为单纯法中提出的等式形式约束 所有约束是等式方程 有非负的右端项 并且变量非负 从原始问题最优解得到的任何结果都可以直接用到相应的对偶问题上 为了说明如何构造对偶问题 定义等式形式的原始问题如下 变量xj j 1 2 n包含任何剩余变量 松弛变量和人工变量 105 表1从原始问题构造对偶问题 106 上表和上式说明了如何从原始问题构造出对偶问题 事实上 我们有 1 对偶变量是针对原始问题每个 约束 方程定义的 2 对偶约束是针对原始问题的每个变量定义的 3 原始问题变量约束 列 的系数定义对偶约束左端项的系数 它的目标系数定义了右端项 4 对偶目标系数等于原始问题约束方程的右端项 107 下表2概况了确定最优化含义 极大化或者极小化 约束的类型 或 以及对偶变量符号的规则 注意 在对偶问题中 最优化含义总是与原始问题最优化含义相反 记住 对偶问题约束类型 或 的一种容易的方法是 如果对偶目标求极小 则所有约束都是 型的 当对偶目标求极大化时 约束类型相反 所有原始问题约束是等式方程 具有非负右端项 并且所有变量非负 表2构造对偶问题的规则 108 下面的例子说明如何使用对偶规则 对偶问题 109 对偶问题 110 对偶问题 111 第一个和第二个约束方程用等式方程来代替 这种情况发生的规则是 无限制原始问题变量总是对应于对偶问题的等式约束 相反的 原始问题的等式约束总对应于无限制对偶变量 正如第一个原始问题约束显示的那样 112 构造对偶问题规则总结从前面的例子中得到的一般结论是 原始问题和对偶问题中的变量和约束是由下表所示的规则定义的 我们可以检验 这些明确的对应关系包含在表2所示的一般规则中 注意 该表格并不用于指定原始问题和最优问题 这里重要的是最优化含义 如果原始问题是极大化 则对偶问题就是极小化 反之亦然 113 4 2原始 对偶关系 原始线性规划模型中的变化将改变当前最优表的元素 这反过来又会影响到当前解的最优性和 或 当前解的可行性 本节介绍一些原始 对偶之间的关系 用来重新计算最优单纯形表的元素 这些元素将构成线性规划模型经济学解释和后最优性分析的基础 本节先简要复习矩阵的相关理论 因为它是完成单纯形表计算的便利的工具 114 4 2 1简单矩阵运算的复习 单纯形表的计算只用到3种初等矩阵运算 行向量 矩阵 矩阵 行向量 以及 标量 矩阵 1 一个维数为 n m 的矩阵A是一个具有m行n列元素的矩阵阵列 2 一个维数为m的行向量V是一个 1 m 维的矩阵 3 一个维数为n的列向量P是一个 n 1 维的矩阵 这些定义的数学表达如下 115 4 2 2单纯形表的布局图 下图给出了初始和一般单纯形表的一种表达式 初始表中 在初始变量下方的约束系数构成了一个单位矩阵 idengtitymatrix 由于这种排列 由高斯 乔丹行运算产生的后续单纯形表迭代将会修改这个单位矩阵的元素 得到所谓的逆矩阵 本章后续部分将会看到 逆矩阵是计算相应单纯形表所有元素的关键 116 100 0010 0 000 1 逆矩阵 目标z行 约束列 初始变量 初始变量 单位矩阵 目标z行 约束列 初始表 一般迭代 117 4 2 3最优对偶解 原始问题与对偶问题的解有着如此紧密的关系 以至于任何一个问题的最优解直接产生另一个问题的最优解 因此 在线性规划模型中 变量的个数比约束的个数小得多 通过求解对偶问题可以节省计算量 因为从对偶问题的解可以自动地求出原始问题的解 这个结果成立是因为单纯形的计算量在很大程度上依赖于约束的个数 本节提供确定对偶变量的两种方法 对偶问题的对偶问题是原始问题本身 这意味着对偶问题的解还可以用来自动地生成原始问题的最优解 118 方法1对偶变量yi的最优值 初始变量xi的最优原始z的系数 xi的原始目标系数方法2对偶变量yi的最优值 最优原始基变量的原目标系数的行向量 最优原始逆矩阵 119 考虑下面的线性规划 为了准备用单纯形求解问题 我们在第1个约束加上松弛变量x4 并在第二个约束添加人工变量R 因此导出原问题和相应对偶问题定义如下 120 原始问题的最优单纯形表 方法1在表4 4中 初始原始变量x4和R分别唯一地对应于对偶变量y1和y2 因此 我们确定最优对偶解如下 121 方法2最优逆矩阵 即表4 4中初始变量x4和R下面突出显示的部分 即 首先 注意到 最有原始变量在表中 其行的顺序为先x2 再x1 这意味着两个变量原始目标系数的元素必须以相同的顺序出现 也就是 原始目标系数 x2的系数 x1的系数 12 5 因此 最优对偶值计算如下 122 原始 对偶目标值对于任意一对可行的原始解和对偶解 都有 极大化问题的目标值 极小化问题的目标值在最优处 这个关系式作为严格等式成立 这个关系式并没有特别指定哪一个问题是原始问题 哪一个问题作为对偶问题 在这种情况下 只有最优化的含义 极大化或极小化 是重要的 最优值不可能出现Z严格小于w 即z w 因为无论z与w靠得如何近 总是有余地可以改进 这与下图演示的最优性矛盾 123 例在例4 2 1中 x1 0 x2 0 x3 8 3 和 y1 6 y2 0 是可行的原始解与对偶解 相应的目标值是z 5x1 12x2 4x3 5 0 12 0 4 8 3 32 3w 10y1 8y2 10 6 8 0 60 124 习题考虑下面的线性规划 Maxz 5x1 2x2 3x3S t x1 5x2 2x3 30 x1 x2 6x3 40 x1 x2 x3 0 已知人工变量x4和松弛变量x5构成初始基变量 在求解此问题时 令M等于100 最优化表给出如下 写出相应的对偶问题并使用两种方法确定它的最优解 125 4 2 4单纯形表的计算 本节说明如何从问题的原始数据 与迭代相应的逆矩阵 以及对偶问题中产生出整个单纯形表的任意一次迭代 使用上一节介绍的单纯形表的示意图 我们可以把计算分为两类 1 约束列 左端项和右端项 2 目标z行公式1 约束列的计算在任意一次单纯形迭代中 左端项或右端项列的计算如下 第i次迭