线性规划及其应用3-线性规划求解方法.ppt

3 3线性规划求解方法 1 重庆大学经济与工商管理学院肖智 第三节线性规划求解方法一 计算机求解方法1 基本思想 迭代的思想方法 2 适用范围 一般线性规划问题 3 例 生产计划问题二 图解法1 基本理论 凸集基本理论 2 基本思想 在目标函数直线族中找一条满足可行域 且取值最大 最小 的直线 3 适用范围 两个变量的线性规划问题 3 3线性规划求解方法 2 重庆大学经济与工商管理学院肖智 4 作用 线性规划理论的几何意义 并说明线性规划解的四种情况 唯一最优解 无穷最优解 有可行解而无最优解 无可行解 5 举例说明 三 单纯形法1 单纯形法的概述1 适用范围 线性规划标准形问题 2 基本原理 1 目标 使Z CX最大 在AX b X 0条件下 2 理论 线性规划基本理论 3 结论 3 3线性规划求解方法 3 重庆大学经济与工商管理学院肖智 3 3 1 3 3 2 3 3 3 3 3线性规划求解方法 4 重庆大学经济与工商管理学院肖智 要使Z CX达到最大 由 3 3 3 知只需去寻找一恰当的基B使得 称为检验数向量 3 基本思路 基于线性规划问题的标准形 先确定一初始基可行解X0 并由此开始在保证目标函数值不下降的情况下逐次施行从一个基可行解到另一个基可行解的转换 如此进行下去 直到取得最优解或判明问题无最优解为止 4 基本步骤 1 对一般线性规划问题标准化 2 确定一初始基可行解X0 3 若所有检验数 j 0 j为的第j个分量 则X0是线性规划问题的最优解 停止计算 否则转 4 3 3线性规划求解方法 5 重庆大学经济与工商管理学院肖智 4 若存在 t 0所对应的系数列向量pt O 则线性规划问题无最优解 停止计算 否则转 5 5 按最大检验数规则 确定进基变量xk和主列pk 再按最小比值规则 确定出基变量xl和主元alk 6 以主元alk进行换基迭代得一新的基可行解x1 将x1记为x0返回到 3 5 基本工具 计算机或单纯形表 3 3线性规划求解方法 6 重庆大学经济与工商管理学院肖智 2 单纯形法应用举例 3 3 4 3 3线性规划求解方法 7 重庆大学经济与工商管理学院肖智 第一步标准化 3 3 5 第二步建立初始单纯形表 3 3线性规划求解方法 8 重庆大学经济与工商管理学院肖智 表3 3 1 3 3线性规划求解方法 9 重庆大学经济与工商管理学院肖智 此表对应一个可行方案和该方案最优检验结果 可行方案 x1 x2 0 x3 12000 x4 4000 x5 6000 最优性检验结果 检验值全部非负 若全部非正 则可行方案是最优方案 3 3线性规划求解方法 10 重庆大学经济与工商管理学院肖智 第三步 改进当前可行方案 计算下一张单纯形表 表3 3 2 3 3线性规划求解方法 11 重庆大学经济与工商管理学院肖智 第四步 改进当前可行方案 计算下一张单纯形表 表3 3 3 3 3线性规划求解方法 12 重庆大学经济与工商管理学院肖智 最优性检验结果 检验值全部为非正最优方案 x1 6250 件 x2 15000 件 x3 x4 x5 0 件 最大效益为 306250 美元 3 3线性规划求解方法 13 重庆大学经济与工商管理学院肖智 3 初始基可行解的求法 在前边的讨论中我们总假定当问题化为标准型后 系数矩阵中有一个全部由松弛变量列向量构成的单位矩阵 如果右边项系数全都大于或等于零 只要取该单位矩阵为初始基就可以得到一个初始基本可行解 但在一般情况下 化为标准型的矩阵中不一定含有单位短阵 例如 当线性规划问题有等式约束时就无法引入松弛变量 如果约束的右边项系数出现负值时也无法直接得到一个初始可行解 在这种情况下 可引入人工变量来构造一个初始基 具体做法是 1 将所有约束的右边项值调整为大于或等于零 对右边项 3 3线性规划求解方法 14 重庆大学经济与工商管理学院肖智 为负的约束 约束两边同乘一l 2 对小于等于型约束 仍引入一个松弛变量 3 对大于等于型约束 引入一个剩余变量和一个人工变量 4 对等于型约束 引入一个人工变量 通过以上调整后 每一个约束或者有一个松弛变量 或者有一个人工变量 它们构成的单位矩阵可以作为一个初始基 可见 调整后的问题一定有可行解 然而 对原问题来说 新引入的人工变量是多余的 如果人工变量在最后的结果中取正值 则表明该解不满足原问题约束条件 因此 尽管引入人工变量后我们可以很容易找到一个初始 3 3线性规划求解方法 15 重庆大学经济与工商管理学院肖智 基 然而该基不一定是原问题的可行基 只有当人工变量都变为非基变量或都为零时 引入人工变量的问题才与原问题等价 因此 应通过某种方法把所有的人工变量从基中赶出去才能得到原问题的一个可行基 常用的方法有以下两种 1 大M法大M法实质上是一种罚函数法 它在目标函数中赋予人工变量一个很大的负系数 一M 由于人工变量对目标函数有很大的负影响 单纯形方法的寻优机制会自动将人工变量赶到基外 从而找到一个原问题的可行基 用单纯形表计算时 可直接在目标函数中使用M参数 3 3线性规划求解方法 16 重庆大学经济与工商管理学院肖智 通过人的计算和判断进行单纯形迭代 用计算机计算时 由于计算机无法直接使用参数计算 M必须赋予一个较大的值 并视求解的情况对M值进行调整 如果给定M后 计算所得的最优基已不含人工变量 该解即为最优可行解 当给定的M足够大时 最优解中仍含有人工变量 则可判断原问题无可行解 下面举例说明如何使用大M法 例 用大M法求解下列线性规划问题 3 3 6 3 3线性规划求解方法 17 重庆大学经济与工商管理学院肖智 具体解题步骤见下表3 3 4 3 3线性规划求解方法 18 重庆大学经济与工商管理学院肖智 表3 3 4续 3 3线性规划求解方法 19 重庆大学经济与工商管理学院肖智 该问题的最优解为 X 0 10 T 最优值为 Z 30与计算机计算结果相同 大M法的优点是方法比较直观 易于理解和手工计算 缺点是当使用计算机计算时 由于M值较大容易引起数值计算上的困难 所以几乎所有商业线性规划软件都不使用大M法而使用另外一种方法 两阶段法 2 两阶段法顾名思义 两阶段法是将线性规划求解过程分为两个阶段 第一阶段只是寻找一个初始可行基 第二阶段再按正常方法寻找最优解 3 3线性规划求解方法 20 重庆大学经济与工商管理学院肖智 第一阶段 在原问题中引入人工变量并找到一个初始基 另构造一个新的求极小值的目标函数 该目标函数除人工变量的系数为1以外 其余变量的目标函数系数都为零 求解该线性规划问题 在不退化的前提下 如果得到的最优解值为零 表明所有的人工变量已经不在基中 第一阶段的最优解即是原问题的一个基可行解 第二阶段 将原目标函数换回 以第一阶段得到的可行基为初始基进行迭代 直到找到最优基为止 在第二阶段的迭代中可以删去所有人工变量 保留它们只会增加不必要的计算 下面举例说明两阶段法求解过程 3 3线性规划求解方法 21 重庆大学经济与工商管理学院肖智 例 用两阶段法求解下列线性规划问题 3 3 7 第一阶段模型 3 3 8 3 3线性规划求解方法 22 重庆大学经济与工商管理学院肖智 具体解题步骤见下表3 3 5 3 3线性规划求解方法 23 重庆大学经济与工商管理学院肖智 表3 3 5续第二阶段模型 3 3 9 3 3线性规划求解方法 24 重庆大学经济与