Ch章对偶理论说课.ppt

问题5：设生产第三种产品，产量为 件， 对应的 求最优生产计划。 解： 代入最终原单纯形表中 主元 换基后有： 四、增加一个约束条件的分析 增加一个约束条件相当于增添一道工序。 分析方法： 将最优解代入新的约束中 （1）若满足要求，则原最优解不变； （2）若不满足要求，则原最优解改变， 将新增的约束条件添入最终的 单纯形表中继续分析。 例2-12 最优单纯形表 问题：增加新约束 2 -1 4 0 0 0 XB b x1 x2 x3 x4 x5 x6 4 x3 2 0 5/7 1 1/7 3/7 0 2 x1 1 1 2/7 0 －1/7 4/7 0 0 x6 1 0 －2 0 0 －1 1 0 -31/7 0 -2/7 -20/7 0 。 引入松弛变量x7得 将最优解代入新的约束条件，不满足要求，则原最优解改变，需将新增的约束条件添入最终的单纯形表中继续分析。 2 -1 4 0 0 0 0 XB b x1 x2 x3 x4 x5 x6 x7 4 x3 2 0 5/7 1 1/7 3/7 0 0 2 x1 1 1 2/7 0 －1/7 4/7 0 0 0 x6 1 0 －2 0 0 －1 1 0 0 x7 5 -5 1 6 0 0 0 1 4 x3 2 0 5/7 1 1/7 3/7 0 0 2 x1 1 1 2/7 0 －1/7 4/7 0 0 0 x6 1 0 －2 0 0 －1 1 0 0 x7 －2 0 －13/7 0 [－11/7] 2/7 0 1 0 －31/7 0 －2/7 －20/7 0 0 2 -1 4 0 0 0 0 XB b x1 x2 x3 x4 x5 x6 x7 4 x3 2 0 5/7 1 1/7 3/7 0 0 2 x1 1 1 2/7 0 －1/7 4/7 0 0 0 x6 1 0 －2 0 0 －1 1 0 0 x7 －2 0 －13/7 0 [－11/7] 2/7 0 1 0 －31/7 0 －2/7 －20/7 0 0 4 x3 20/11 0 6/11 1 0 5/11 0 1/11 2 x1 13/11 1 5/11 0 0 6/11 0 －1/11 0 x6 1 0 －2 0 0 －1 1 0 0 x4 14/11 0 13/11 0 1 －2/11 0 －7/11 0 －45/11 0 0 －32/11 0 －2/11 最优解 五、分析 的变化 若 对应的 变量 为基变量， B将改变。重新用单纯形法求解。 若 对应的变量 为非基变量， 参见三的分析。 灵敏度分析的步骤归纳如下： （1）将参数的改变计算反映到最终 单纯形表上； （2）检查原问题是否仍为可行解； （3）检查对偶问题是否仍为可行解； （4）按下表所列情况得出结论和决 定继续计算的步骤。 原问题 对偶问题 结论或继续计算的步骤 可行解 可行解 问题的最优解或最优基不变 可行解 非可行解 用单纯形法继续迭代 非可行解 可行解 用对偶单纯形法继续迭代 非可行解 非可行解 编制新的单纯形表重新计算 总之 练习： 某厂计划生产甲、乙、丙三种产品，这三种产品单位利润及生产产品所需材料、劳动力如下表： 单位产品 甲 乙 丙 可使用资源量 劳动力 1/3 1/3 1/3 1 材料 1/3 4/3 7/3 3 利润（元） 2 3 1 （1）确定最优的生产方案； （2）当 增大至多少时，丙产品安排生产； （3）增加3个劳动力，最优解是否改变？ （4）劳动力在哪个范围内变化，对利润值 的改变有利； （5）增加新的产品丁，需1个劳动力，1个 单位原料，利润3元。确定最优的生产方案。 （6）添加新约束： 最优解是否改变？ 解：初始及最终单纯形表为 返回 灵敏度分析 2.4 对偶单纯形法 对偶单纯形法的基本思路 对偶单纯形法的计算步骤 返回 继续 对偶单纯形法的基本思路 单纯形法的基本思路： 原问题基可行解