运筹学 线性规划 单纯形法ppt课件.ppt

第一章线性规划问题及单纯形法 线性规划问题及其数学模型图解法单纯形法原理单纯形法计算步骤单纯形法的进一步讨论 第五节单纯形法的进一步讨论 本节重点 大M法 两阶段法 解的存在情况判别 由于所添加的剩余变量的技术系数为 1 不能作为初始可行基变量 为此引入一个人为的变量 注意 此时约束条件已为 型 以便取得初始基变量 故称为人工变量 由于人工变量在原问题的解中是不能存在的 应尽快被迭代出去 因此人工变量在目标函数中对应的价值系数应具有惩罚性 称为罚系数 罚系数的取值视解法而定两种方法 大M法和二阶段法 一 人工变量的引入及其解法 1 当约束条件为 型 引入剩余变量和人工变量 2 大M法的求解过程例1 人工变量添加前已为等式 其取值必须为0 M称为 惩罚因子 答 最优解为x1 2 x2 2 x3 0 OBJ 36 例1的单纯型表迭代过程 3 大M法的一些说明 1 人工变量被迭代出去后一般就不会再成为基变量 2 大M法实质上与原单纯形法一样 M可看成一个很大的常数 3 当检验数都满足最优条件 但基变量中仍有人工变量 说明原线性规划问题无可行解 4 大M法手算不会遇到麻烦 但计算机计算很容易产生误差 因此提出了二阶段法 4 二阶段法的求解过程 1 第一阶段的任务是将人工变量尽快迭代出去 从而找到一个没有人工变量的基础可行解 2 若第一阶段结束时 人工变量仍在基变量中 则原问题无解 3 第二阶段以第一阶段得到的基础可行解为初始解 采用原单纯形法求解 4 为了简化计算 在第一阶段重新定义价值系数如下 用二阶段法求解例1的第一阶段 人工变量x6不在基变量中 从最终单纯形表中去除人工变量 更换目标函数为原问题的目标函数 继续用单纯形表计算 用二阶段法求解例1的第二阶段 1 关于退化问题当按照最小比值 确定换出基变量时 存在多个相同的最小比值 从而使下一个表的基可行解中出现一个或多个基变量等于零的退化解 退化的严重性在于可能导致死循环 克服死循环的方法有 字典序 法 即Bland规则 1 当按照最大检验数 j 0确定换入变量时 存在多个相同的最大检验数 始终选取下标值为最小的变量作为换入变量 2 当按照最小比值 确定换出基变量时 存在多个相同的最小比值 始终选取下标值为最小的变量作为换出变量 二 LP解的进一步讨论 2 关于多重解问题最优单纯形表中有非基变量的检验数为0 例3的单纯型表及其迭代过程 4 关于无可行解问题 单纯形表达到最优解检验条件时 人工变量仍在基变量中 例4第一阶段的单纯型表 三 单纯形法小结如下所示 1 线性规划模型及其变换 根据实际问题给出数学模型 进行标准化 列出初始单纯型表 见表 变 量 x j 0 x j 0 x j 无约束 不需要处理 令 x j x j x j 0 令 x j x j x j x j x j 0 约 束 条 件 b 0 b 0 不需要处理 约束条件两端同乘 1 加人工变量 减去剩余 加人工变量 加松弛变量 目 标 函 数 Maxz Minz 加入变量 的系数 松弛变量 人工变量 不需要处理 令 z z 求 M axz 0 M 分别以每一个约束条件中松弛变量或人工变量为基变量 列出初始单纯型表 18 2 线性规划解的情况解除有唯一最优解的情况外 还有如下几种情况 无界解 1 可行区域不闭合 约束条件有问题 2 单纯形中存在某入基变量xk对应的列中所有aik 0退化解 1 退化问题的原因很复杂 当原问题存在平衡约束时 2 当单纯型表中同时有多个基变量可选作出变量时 3 退化的严重性在于可能导致死循环无穷多解 1 多个基础可行解都是最优解 这些解在同一个超平面上 且该平面与目标函数等值面平行 2 最优单纯形表中有非基变量的检验数为0 3 最优解的线性组合仍是最优解 即X aX1 bX2 a b 1无可行解 1 约束条件互相矛盾 无可行域 2 单纯型表达到最优解检验条件时 人工变量仍在基变量中 19 唯一最优解 否 否 否 是 是 是 添加松弛变量 人工变量列出初始单纯形表 计算各列检验数 j 所有 j 0 基变量中有非零的人工变量 某非基变量检验数为零 无可行解 无穷多最优解 对任一 j 0有aik 0 无界解 令 k max j xk为换入变量对所有aik 0计算 i bi aik令 l min i 第l个基变量为换出变量 alk为主元素 1 xk替换xl2 列出新的单纯形表 对主元素行 第l行 其它行i i l 否 3 对目标函数求极大值标准型线性规划问题 单纯形法计算步骤的框图 20 例1 某糖果厂用原材料A B C加工成三种不同牌号的糖果甲 乙 丙 已知各种牌号的糖果中A B C含量 原料成本 各种原料每月限制用量 三种牌号糖果的单位加工费及售价如下表所示 问该厂每月生产这三种牌号糖果多少kg 使该厂获利最大 试建立该问题的LP的数学模型 例2 捷运公司拟在下一年度的1 4月份的4个月需租用仓库堆放物资 已知各月份所需仓库面积数列于下表 仓库租用费随合同期而定 期限越长 折扣越大 具体数字见下表 租借仓库的合同每月初都可办理 每份合同都具体规定租用面积和期限 因此该厂可根据需要 在任何一个月初办理租借合同 每次办理时可签一份 也可签若干份租用面积和租借期限不同的合同 试确定该公司签订的租借合同的最优决策 目的是所付租借费用最小 解 若用变量表示捷运公司在第个月初签定的租借期为个月的仓库面积的合同 单位为100 因5月份起该公司不需要租借仓库 均为零 该公司希望总的租借费用为最小 故有如下的数学模型 目标函数 约束条件 例3某城市在一昼夜间 市内交通需要车辆数如图 对车辆的需求在昼夜间是变化的 车辆的工作制度是一天连续工作8小时 派车时间在各时间间隔的端点 一旦派出 就连续工作8小时 求保证需要的最小车辆数 车辆数 时间 0 4 7 12 16 20 24 4 8 12 4 8 12 10 8 4 派车时间在各时间间隔