运筹学讲义-单纯形方法(ppt 78页).ppt

2020 3 22 1 运筹学 耿修林 2020 3 22 2 五 单纯形方法 一 单纯形方法的初步讨论1 单纯形方法的基本思想从可行域中的一个基本可行解出发 判断它是否已是最优解 若不是 寻找下一个基本可行解 并使目标函数得到改进 如此迭代下去 直到找出最优解或判定问题无界为止 从另一个角度说 就是从可行域的某一个极点出发 迭代到另一个极点 并使目标函数的值有所改善 直到找出有无最优解时为止 2020 3 22 3 五 单纯形方法 一 单纯形方法的初步讨论2 单纯形方法 消去法 例 求解线性规划模型解 第一步 将线性规划模型标准化 MaxZ 50 x1 30 x2 0 x3 0 x4s t 4x1 3x2 x3 1202x1 x2 x4 50 x1 x2 x3 x4 0 2020 3 22 4 2 单纯形方法 消去法第二步 寻找初始可行解 变量x3 x4对应的列向量A3 A4可作为初始可行基 那么X3 X4为基变量 X1 X2为非基变量 用非基量表示基变量 则有 MaxZ 50 x1 30 x2 0 x3 0 x4s t x3 120 4x1 3x2x4 50 2x1 x2x1 x2 x3 x4 0令x1 x2 0 得到基本可行解X 0 0 120 50 文本 文本 文本 文本 文本 文本 文本 文本 2020 3 22 5 五 单纯形方法 2 单纯形方法 消去法第三步 判断目标函数是否达到了最优 第四步 选取入基变量 确定x1为基变量 x2仍为非基变量 第五步 选取出基变量 x3 120 4x1 3x2 0 x4 50 2x1 x2 0解不等式得 x1 25 只有当x1 25时 x4恰好等于0 所以x4确定为出基变量 于是新的典则方程为 x1 25 0 5x2 0 5x4x3 20 x2 2x4 2020 3 22 6 一 单纯形方法的初步讨论 第六步 产生新的基本可行解及目标函数值 令x2 x4等于0 得到x1 25 x3 20 于是新的基本可行解为X 25 0 20 0 目标函数值为Z 1250 第七步 判定目标函数值是否得到了最优 根据分析目前的方案还不是最优的 重复第四 五 六步 x2入基 x3出基 建立新的典则方程 x1 15 0 5x3 1 5x4x2 20 2x3 2x4令非基变量x3 x4等于0 得到新的基本可行解X 15 20 0 0 目标函数值为1350 问题求解完成 2020 3 22 7 五 单纯形方法 二 单纯形方法的矩阵描述1 线性规划的典则形式 MaxZ CBB 1b CN CBB 1N XNS t XB B 1b B 1NXNXB XN 02 判别向量与判别数 a CN CBB 1A为对应基B的所有X的判别向量 其中任一分量 j cj CBB 1Aj为变量xj关于基B的判别数 j 1 2 n 2020 3 22 8 五 单纯形方法 2 判别向量与判别数 b N CN CBB 1N为对应基B的所有非基变量XN的判别向量 其中任一分量 j cj CBB 1Aj为非基变量xj关于基B的判别数 j m 1 m 2 n c 所有基变量的判别向量是零向量 所有基变量的判别数是0 为什么 3 最优解的判定 a 如果所有的检验数都小于0 则当前解为最优解 2020 3 22 9 五 单纯形方法 3 最优解的判定 b 如果至少存在一个检验数大于0 且该检验数对应的列向量中至少有一个正分量 则需要继续进行迭代寻找最优解 c 如果至少存在一个检验数大于0 且该检验数对应的列向量的所有分量都小于0 则线性规划问题不存在有界最优解 2020 3 22 10 五 单纯形方法 三 单纯形方法 表上作业法1 单纯形表的构造方法1 C CBB 1A CB CN CBB 1 B N 0 CN CBB 1N 两边同乘上X得 C CBB 1A X 0 CN CBB 1N X 化简得 Z CBB 1b CN CBB 1N XN构造联立方程 Z CBB 1A C X CBB 1bB 1AX B 1b 2020 3 22 11 五 单纯形方法 1 单纯形表的构造这样得到单纯形表 2020 3 22 12 五 单纯形方法 1 单纯形表的构造方法2 XB B 1b B 1NXN 则有 XB B 1NXN B 1b又Z CBB 1b CN CBB 1N XN 于是 Z CBB 1N CN XN CBB 1b 这样得 Z CBB 1N CN XN CBB 1bXB B 1NXN B 1b构造单纯形表 2020 3 22 13 五 单纯形方法 三 单纯形方法 表上作业法1 表上作业的步骤 第一步 将线性规划问题进行标准化处理 第二步 确定初始基本可行解与初始可行基 第三步 编制单纯形计算表 第四步 计算检验数 判断线性规划问题是否有最优解 第五步 确定入基变量 一是最大检验数准则 二是最小下标准则 第六步 确定出基变量 最小检验数对应的基变量出基 第七步 编制新的单纯形表 重复以上的第四 七步 直到能够确定线性规划问题是否有最优解为止 2020 3 22 14 五 单纯形方法 2 单纯形方法 表上作业法应用举例求解下列线性规划问题 MinZ X1 3X2S t 2X1 4X2 6 X1 3X2 5X1 X2 0解 第一步 将上述问题进行标准化处理 2020 3 22 15 五 单纯形方法 应用举例MaxZ X1 3X2S t 2X1 4X2 X3 6 X1 3X2 X4 5X1 X2 X3 X4 0第二步 确定初始基本可行解与初始基本可行基 初始可行基 B A3 A4 初始可行解 X 0 0 6 5 2020 3 22 16 五 单纯形方法 应用举例第三步 构造单纯形表 2020 3 22 17 五 单纯形方法 应用举例第四步 计算检验数并判断是否是最优解 检验数列在初始单纯形表中的最后一行 第五步 确定入基变量 对应的检验数最大 所以确定X2为入基变量 第六步 确定出基变量 计算的检验数列在初始单纯形表中的最后一列 根据出基变量的判别准则 应确定X3出基 2020 3 22 18 五 单纯形方法 第七步 构造新的单纯形表 2020 3 22 19 五 单纯形方法 应用举例第八步 判定迭代到这一步是否应该停止 因为所有的非基变量的检验数都为负数 因此可以判断迭代到此步的基是最优基 目标函数值为Z 4 5 最优解为X 0 1 5 0 0 原问题的最优解为X 0 1 5 0 0 目标函数值为Z 4 5 2020 3 22 20 五 单纯形方法 四 确定初始基本可行解的方法1 对于约束方程中都是小于等于0 并且约束方程右边项皆大于0的情况 只要引进松弛变量即可得到单位阵的初始可行基 2 如果约束方程都是等于某些值的情况 此时需要引进人工变量才能构造出单位阵的初始可行基和初始可行解 3 如果约束方程中有大于某些值的情况 则需要引进剩余变量并同时引进人工变量 才能构造出单位阵的初始可行基和初始可行解 2020 3 22 21 六 线性规划的其他解法 一 人工变量消除法 M法1 M法的含义 通过引进人工变量 构造一个辅助的线性规划问题 然后由辅助的线性规划问题找出原问题的第一个初始可行基 在此基础上 利用单纯形方法求出原问题的最优解 2020 3 22 22 六 线性规划的其他解法 一 人工变量消除法 M法2 M法的辅助线性规划问题 原问题 Maxz c1x1 c2x2 cnxns t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 2020 3 22 23 六 线性规划的其他解法 一 人工变量消除法 M法2 M法的辅助线性规划问题 Maxz c1x1 c2x2 cnxn MXn 1 MXn 2 MXn ms t a11x1 a12x2 a1nxn Xn 1 b1a21x1 a22x2 a2nxn Xn 2 b2 am1x1 am2x2 amnxn Xn m bmx1 x2 xn 0 2020 3 22 24 六 线性规划的其他解法 3 M法的解题步骤 1 把原线性规划问题进行标准化处理 2 引进人工变量 构造辅助线性规划问题 3 运用单纯形方法 把人工变量全部剔除出基变量 4 在得到的原问题的初始可行基的基础上 运用单纯形方法进行迭代 5 直到能够判断原问题有无最优解时为止 2020 3 22 25 六 线性规划的其他解法 4 M法解的判定 1 经过若干次迭代后 基变量中无人工变量 则说明原问题有基本可行解 2 经过若干次迭代后 基变量中仍有人工变量 并且全部检验数皆小于0 则表明原问题无可行解 2020 3 22 26 六 线性规划的其他解法 二 人工变量消除法 两阶段法1 含义 在原来问题引入人工变量后分两个阶段求解线性规划问题的方法 其中 第一阶段在原来问题中引入人工变量 设法构造一个单位阵的初始可行基 另外在目标函数中令非人工变量的系数全部为0 人工变量的系数为1 构造一个新的辅助目标函数 在此基础上 建立辅助线性规划问题 然后运用单纯形方法求解 直到辅助目标函数为0时为止 第二阶段重新回到原来的问题 以第一阶段得到的可行基为初始可行基 运用单纯形方法以求出原来问题的解 2020 3 22 27 六 线性规划的其他解法 二 人工变量消除法 两阶段法2 两阶段法的辅助问题 原问题 Maxz c1x1 c2x2 cnxns t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 2020 3 22 28 六 线性规划的其他解法 二 人工变量消除法 两阶段法2 两阶段法的辅助问题 辅助问题 MinZ Xn 1 Xn 2 Xn ms t a11x1 a12x2 a1nxn Xn 1 b1a21x1 a22x2 a2nxn Xn 2 b2 am1x1 am2x2 amnxn Xn m bmx1 x2 xn 0Xn 1 Xn 2 Xn m 0 2020 3 22 29 六 线性规划的其他解法 二 人工变量消除法 两阶段法3 解的判断 1 辅助问题的目标函数值Z 0 2 假定B为辅助问题最优基 此时若辅助问题的目标函数值Z 0 则原问题无解 证明 请同学们自己做一做 3 辅助问题在最优基B下目标函数的值Z 0 此时有两种情况 第一种情况 若辅助问题的最优基B对应的基变量中无人工变量 则该最优基也是原问题的可行基 这时候只要在单纯形表中去掉人工变量所在的列和最后一行 即可得到原问题的初始可行单纯形表 2020 3 22 30 六 线性规划的其他解法 二 人工变量消除法 两阶段法3 解的判断 3 第二种情况 若辅助问题最优基B对应的基变量中还有人工变量 即存在 yr a rkyk a rjxj 0这时需要进行讨论 第一 若a rj 0 即有 yr a rkyk 0则表明原问题中的第r个约束是多余的 可以从辅助问题单纯形表中 直接划掉这一行 第二 若a rj中至少有一个不等于0 则需要以之为转轴元素再进行迭代 直到化为第一种情况为止 2020 3 22 31 三 退化 循环及其处理方法 1 退化问题在约束系数矩阵A aij mn m n 中 若R A m 则称该线性规划问题是退化的 2 退化迭代的特点 1 退化解的基变量中至少有一个取值为0 2 退化迭代中基在不断变化但解始终不变 3 退化迭代不会引起目标函数值的改进 3 防止循环迭代的方法 1 摄动法 2 字典顺序法 3 最小下标法 2020 3 22 32 三 退化 循环及其处理方法 4 退化问题的单纯形摄动方法 1 原理对退化的线性规划问题的右边项作微小的扰动 以避免因退化而引起的循环 2 应用举例 2020 3 22 33 七 电子表格建模及其求解 见Excel中的演示 2020 3 22 34 案例讨论 2020 3 22 35 第四讲线性规划建模 第一节线性规划建模的几个问题第二节常见的线性规划模型第三节案例讨论 2020 3 22 36 第一节线性规划建模的有关问题 一 线性规划建模的要求与思路1 要求 繁简适当 要能够反映实际问题的主要因素 得出结论和产生效益 2 思路 首先将实际问题简化得能比较容易地建立一个粗略的 可以使用的模型 在这个基础上考虑加进先前被省略掉的一些因素 改进已建立的模型 重复这个过程直到能建立符合要求的模型为止 2020 3 22 37 第一节线性规划建模的有关问题 二 线性规划建模的一般过程1 明确决策变量2 确定目标函数3 确立约束方程4 给出变量取值的限制 2020 3 22 38 第一节线性规划建模的有关问题 三 参数资料的来源1 统计资料2 会计核算资料3 工程分析4 实验研究5 合理规定等 2020 3 22 39 第二节常见的线性规划模型 一 配料问题假设有n种原料 已知每种原料都含有m种成分 又已知每种原料的单位成分含量为aij i 1 2 m j 1 2 n 现欲用这n种原料配制成一种产品 要求单位产品的各种成分的含量为bi 如果每种原料的单价为cj 问如何配料才能使产品的生产成本最低 2020 3 22 40 第二节常见的线性规划模型 二 资源利用问题生产n种产品 每种产品都要经过m道工序 其中 第j种产品在第i道工序上加工所需要的工时为aij i 1 2 m j 1 2 n 第i道工序可提供的工时最多为bi 第j种产品的单位利润为cj 问如何规划各种产品的数量 使获得的利润最大 2020 3 22 41 第二节常见的线性规划模型 三 运输问题 某种物资有m个产地 n个需地 产地产量 需地的需求量及由产地到需地的单位运价如下 2020 3 22 42 第二节常见的线性规划模型 三 运输问题 问如何设计运输方案 才能使运输成本达到最小 1 产销平衡 2 产大于销 3 产小于销 4 运力限制等 2020 3 22 43 第二节常见的线性规划模型 四 投资问题 设有n个投资项目可供选择 Cj表示第j个投资项目的收益率 a表示第i种资源用于第j个项目的投资数量 b表示第i种资源的数量 问如何进行投资才能使投资总收益率最大 2020 3 22 44 第二节常见的线性规划模型 五 混合问题 某石油公司用A B C三种原料混合成普通汽油 R 高级汽油 P 和低铅汽油 L 3种成品出售 3种原料的单位成本及每月最大购入量 原料单位成本最大购入量Aa100Bb150Cc50 2020 3 22 45 第二节常见的线性规划模型 五 混合问题 每千克成品油的售价为 普通汽油为d元 高级汽油为e元 低铅汽油为f元 低铅汽油每月最多销售50吨 各种汽油的规格如下 普通汽油R A少于20 C不多于30 高级汽油P A不少于40 B不少于己于10 且不多于20 C不多于10 低铅汽油 B不少于30 试建立线性规划模型 2020 3 22 46 第二节常见的线性规划模型 六 下料问题 用某种材料切割m种毛坯 根据经验 单位材料上有n种不同的下料方案 每种下料方案可得各种毛坯数量及每种毛坯的需求量为 2020 3 22 47 第二节常见的线性规划问题 六 下料问题 问应该怎样安排下料方案 才能是材料的消耗最省 2020 3 22 48 第二节常见的线性规划问题 七 分派问题 设有n件工作B1 B2 Bn 分派给n个人A1 A2 An去做 每人只做一件工作且每件工作只安排一人做 Ai完成Bj的工时为Cij 问应如何分派才能使总工时最省 2020 3 22 49 第二节常见的线性规划模型 八 生产进度问题 某企业生产一种季节性很强的产品 产品只能在k个月内销售 同时生产也要在这些月内进行 除正常生产时间生产外 也可以加班生产 产品在正常生产时间每月最多能生产A个单位 单位成本为a元 加班生产每月最多能生产B个单位 单位成本为b元 当月生产未及时销售出去的需贮存 库存容量为C 贮存费为单位产品c元 k个月的需求量分别为O1 O2 Ok 试建立线性规划模型 使得总的生产费用最低 2020 3 22 50 第四讲线性规划对偶理论及其应用 第一节线性规划的对偶问题一 问题的提出二 原问题与对偶问题的关系 1 原问题求极大 小 对偶问题求极小 大 2 原问题目标函数的系数变成对偶问题的约束方程的右边项 同样 对偶问题目标函数的系数是原问题的约束方程的右边项 3 原问题的变量的个数 主约束的个数分别等于对偶问题的主约束个数和变量的个数 4 原问题的约束系数矩阵与对偶问题的约束系数矩阵存在转置关系 2020 3 22 51 第一节线性规划的对偶问题 二 原问题与对偶问题的关系 5 在原极小问题中的 大于等于 小于等于 等于 约束 分别与对偶问题中变量的 大于等于0 小于等于0 无约束 相对应 反之 在原极小问题中的变量 大于等于0 小于等于0 无约束 分别对应着对偶问题约束中的 小于等于 大于等于 等于 2020 3 22 52 第一节线性规划的对偶问题 三 原问题与对偶问题的转换举例说明 2020 3 22 53 第二节线性规划的对偶理论 一 原问题与对偶问题是相互对称的 二 弱对偶定理 原问题的目标函数值以对偶问题的目标函数值为上界 对偶问题的目标函数值以原问题的目标函数值为下界 三 无界性定理 若原问题 对偶问题 为无界解 则对偶问题 原问题 无可行解 2020 3 22 54 第二节线性规划的对偶理论 四 最优解性质定理 X Y 分别是原问题与对偶问题的可行解 若有CX Y b存在 则X Y 分别是原问题与对偶问题的最优解 五 对偶定理 若原问题有最优解 那么对偶问题也有最优解 且目标函数的值相等 六 互补松弛性定理 X Y 分别是原问题和对偶问题的可行解 若Y Xs YsX 当且仅当X Y 为最优解 2020 3 22 55 第三节互补松弛性定理的应用 一 关于互补松弛性定理的几个重要的推论二 互补松弛定理的应用 应用举例 Max2X1 4X2 X3 X4S t X1 3X2 X4 82X1 X2 6X2 X3 X4 6X1 X2 X3 9X1 X2 X3 X4 0 2020 3 22 56 第三节互补松弛性定理的应用 二 互补松弛定理的应用其最优解为X 2 2 4 0 目标函数值为16 试运用互补松弛定理求对偶问题的最优解 2020 3 22 57 第三节互补松弛定理的应用 三 对偶解的解释1 对偶解与影子价格2 检验数与边际贡献 2020 3 22 58 第四节对偶单纯形方法 一 对偶单纯形方法的基本思想从对偶问题的可行解和原问题的不可行解出发 进行换基迭代 一旦当原问题的解也变成可行解时 这时的解就是原问题的最优解 二 对偶单纯形方法与原单纯形方法的区别1 原单纯形方法从可行解和对偶问题不可行解出发 直到所有的检验数皆小于等于0 而对偶单纯形方法则从对偶可行解和原问题不可行解出发 直到原问题的解也变成可行 2020 3 22 59 第四节对偶单纯形方法 二 对偶单纯形方法与原单纯形方法的区别2 最优解的判定标准不一样 3 确定出入基变量的顺序不同 原单纯形方法 先确定入基变量后再确定出基变量 而对偶单纯形方法先确定出基变量后确定入基变量 4 确定出入基变量的方法不同 2020 3 22 60 第四节对偶单纯形方法 三 对偶单纯形方法的解的判定1 B 1b 0 表明已求出了原问题的最优解 2 B 1b中至少有一个负分量 且该负分量所在行的各元素都是非负数 则问题无最优解 3 B 1b中至少有一个负分量 且该负分量所在行的元素中存在负数 则需要继续迭代 2020 3 22 61 第四节对偶单纯形方法 四 对偶单纯形算法的过程1 对问题进行标准化处理2 确定一个初始的对偶可行解3 编制对偶单纯形表4 判定目标函数是否达到最优5 换基迭代 直到能判定问题有无最优解时为止 五 应用举例 2020 3 22 62 第五节敏感性分析 一 敏感性分析的含义由于受到政策 价格 工艺水平 资源贮备 设备更新等若干因素的影响 线性规划模型中的参数C A b经常会发生变化 那么C A b在什么样的范围内变化 才不会导致已求出的最优基的改变 这就是敏感性分析所要解决的问题 2020 3 22 63 第五节敏感性分析 二 目标函数系数C变化的敏感性分析1 单个目标函数系数Cj变化的情况 1 Cj为非基变量的目标函数系数 2 Cj为基变量的目标函数系数2 多个目标函数系数变化的情况 1 变化的目标函数系数都是非基变量 2 变化的目标函数系数中有一个是基变量 其他的是非基变量 3 变化的目标函数系数中有多于一个基变量 2020 3 22 64 第五节敏感性分析 三 右边项发生变化的敏感性分析1 单个右边项发生变化2 多个右边项发生变化四 增加新变量的敏感性分析在原问题中增加新变量 会导致约束系数矩阵的列向量增加 同时也会增加检验数的个数 如果增加新变量后 新变量的检验数仍小于0 则最优解保持不变 否则最优解会发生变化 五 增加新约束的敏感性分析1 如果原问题的最优解满足新约束条件 则最优解保持不变 2 如果原问题的最优解不满足新约束条件 则需要寻找新的最优解 2020 3 22 65 第六讲整数规划 第一节概述一 概念对决策变量的取值有整数限制的规划问题 称为整数规划 二 整数规划的分类1 线性整数规划与非线性整数规划2 纯整数规划与混合整数规划 2020 3 22 66 第一节概述 三 线性整数规划的模型MaxZ CXS t AX bX 0 且取整数 2020 3 22 67 第一节概述 四 整数线性规划与一般线性规划的关系1 对整数线性规划的整数约束的放松 便得到一般的线性规划 反之 对一般线性规划增加变量取整的要求 则便变成整数线性规划 因此 整数线性规划的约束比一般线性规划的约束更紧 2 整数线性规划的可行域是一般线性规划问题可行域的子集 3 整数线性规划问题的目标函数值以一般线性规划问题目标函数值为界 即整数线性规划问题的最优值 不可能优于一般线性规划问题的最优值 2020 3 22 68 第二节整数线性规划的几个典型模型 一 背包问题一个背包的容积为V 现有n种物品待装 物品的重量为wj 体积为vj j 1 2 n 问如何配装才能使得既不超过背包的容量 又能装入的物品重量最大 二 工厂的选址问题有n城市 1 2 n 需要某种物资的数量分别为d1 d2 dn 现欲打算建造m座工厂 假设在城市j建厂 规模为sj 需要投资为fj 从城市i到城市j的单位运输费用为cij 问m座工厂应分设在何处比较合适 2020 3 22 69 第二节整数线性规划的几个典型模型 三 加工问题有m台同类型的机床 有n种零件要在这些机床上进行加工 设加工的时间分别是a1 a2 an 问如何分配才能使各机床的总加工任务相等 或尽可能均衡 四 旅游推销问题一个旅游推销商从家门口A0出发 经过预先确定的村子A1 A2 An 然后回到家 假定村子Ai到村子Aj的距离为dij 问如何确定一条行走路线 经过所有要去的村庄 且使总的行走路程最短 2020 3 22 70 第三节分枝定界法 一 公理 1 对一个整数线性规划问题 如果不考虑变量取整的要求 由此求得的整数最优解X 也一定是整数线性规划问题的最优解 2 对