运筹学知识点总结

精品文档 1欢迎下载 运筹学运筹学 考试时间 考试时间 2009 1 42009 1 4 10 00 12 0010 00 12 00 考试地点 考试地点 金融金融 1 1 2 2 二 二 201201 会计 会计 1 1 2 2 二 二 106106 人资人资 1 1 2 2 二 二 203203 工商 工商 1 1 2 2 二 二 205205 林经林经 1 1 2 2 二 二 306306 答疑时间 答疑时间 1717 周周二周四上午周周二周四上午 8 8 00 1100 11 0000 1818 周周一周三上午周周一周三上午 8 8 00 1100 11 0000 地点 基础楼地点 基础楼 201201 精品文档 2欢迎下载 线性规划线性规划 如何建立线性规划的数学模型 如何建立线性规划的数学模型 线性规划的标准形有哪些要求 如何把一般的线性规划化为标线性规划的标准形有哪些要求 如何把一般的线性规划化为标 准形式 准形式 如何用图解法求解两个变量的线性规划问题 由图解法总结出如何用图解法求解两个变量的线性规划问题 由图解法总结出 线性规划问题的解有哪些性质 线性规划问题的解有哪些性质 如何用单纯形方法求解线性规划问题 如何用单纯形方法求解线性规划问题 如何确定初始可行基或如何求初始基本可行解 两阶段方法 如何确定初始可行基或如何求初始基本可行解 两阶段方法 如何写出一个线性规划问题的对偶问题 如果已知原问题的最如何写出一个线性规划问题的对偶问题 如果已知原问题的最 优解如何求解对偶问题的最优解 对偶的性质 互补松紧条优解如何求解对偶问题的最优解 对偶的性质 互补松紧条 件 件 对偶单纯形方法适合解决什么样的问题 如何求解 对偶单纯形方法适合解决什么样的问题 如何求解 对于已经求解的一个线性规划问题如果改变价值向量和右端向对于已经求解的一个线性规划问题如果改变价值向量和右端向 量原最优解量原最优解 基是否仍是最优解基是否仍是最优解 基 如果不是 如何进一步求基 如果不是 如何进一步求 解 解 精品文档 3欢迎下载 1 1 建立线性规划的数学模型 建立线性规划的数学模型 特点 特点 1 1 每个行动方案可用一组变量 每个行动方案可用一组变量 x x1 1 x xn n 的值表示 这 的值表示 这 些变量一般取非负值 些变量一般取非负值 2 2 变量的变化要受某些限制 这些限制条件用一些线性等式 变量的变化要受某些限制 这些限制条件用一些线性等式 或不等式表示 或不等式表示 3 3 有一个需要优化的目标 它也是变量的线性函数 有一个需要优化的目标 它也是变量的线性函数 2 2 线性规划的标准形有哪些限制 如何把一般的线性规划化为线性规划的标准形有哪些限制 如何把一般的线性规划化为 标准形式 标准形式 目标求极小 约束为等式 变量为非负 目标求极小 约束为等式 变量为非负 min b 0 T zC X AX X 例 把下列线性规划化为标准形式 例 把下列线性规划化为标准形式 12 12 12 1 12 max 23 28 1 2 0 0 zxx xx xx x xx 解 令解 令标准型为 标准型为 13245 xxxxx 精品文档 4欢迎下载 345 3456 3457 38 min 23 2 8 x1 x2 0 3 4 5 6 7 8 i zxxx xxxx xxx x xi 3 3 如何用图解法求解两个变量的线性规划问题 由图解法总结 如何用图解法求解两个变量的线性规划问题 由图解法总结 出线性规划问题的解有哪些性质 出线性规划问题的解有哪些性质 例 参看例 参看 pptppt 唯一最优解 无穷多最优解 无界解 无解 唯一最优解 无穷多最优解 无界解 无解 线性规划解的性质 基 基本解 基本可行解 凸集 顶点 线性规划解的性质 基 基本解 基本可行解 凸集 顶点 定理定理 1 1 线性规划的可行域是凸集 线性规划的可行域是凸集 定理定理 2 2 X X是线性规划基可行解的充分必要条件是是线性规划基可行解的充分必要条件是X X是可行域的顶点 是可行域的顶点 定理定理 3 3 线性规划如果有可行解 则一定有基可行解 如果有最优解 线性规划如果有可行解 则一定有基可行解 如果有最优解 则一定有基可行解是最优解 则一定有基可行解是最优解 4 4 如何用单纯形方法求解线性规划问题 单纯形表 如何用单纯形方法求解线性规划问题 单纯形表 单纯形法的基本法则单纯形法的基本法则 法则法则 1 1 最优性判定法则 检验数全部小于等于零时最优 最优性判定法则 检验数全部小于等于零时最优 法则法则 2 2 换入变量确定法则 谁最正谁进基 换入变量确定法则 谁最正谁进基 法则法则 3 3 换出变量确定法则 最小比值原则 换出变量确定法则 最小比值原则 法则法则 4 4 换基迭代运算法则换基迭代运算法则 精品文档 5欢迎下载 12 123 124 25 12345 min 25 2 8 52 20 4 12 0 zxx xxx xxx xx xxxxx x x1 1x x2 2x x3 3x x4 4x x5 5RHSRHS z z2 25 50 00 00 00 0 x x3 3 x x4 4 x x5 5 1 1 5 5 0 0 2 2 2 2 4 4 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 8 8 2020 1212 z z2 20 00 00 0 5 4 5 4 15 15 x x3 3 x x4 4 x x2 2 1 1 5 5 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 0 0 1 2 1 2 1 2 1 2 1 41 4 2 2 1414 3 3 z z0 00 0 2 20 0 1 4 1 4 19 19 x x1 1 x x4 4 x x2 2 1 1 0 0 0 0 0 0 0 0 1 1 1 1 5 5 0 0 0 0 1 1 0 0 1 2 1 2 2 2 1 41 4 2 2 4 4 3 3 最优解最优解X X 2 2 3 3 0 0 4 4 0 0 T T z z 2 2 5 3 19 2 2 5 3 19 5 5 如何确定初始可行基或如何求初始基本可行解 两阶段方如何确定初始可行基或如何求初始基本可行解 两阶段方 法 法 精品文档 6欢迎下载 例例 求下列求下列 LPLP 问题的最优解问题的最优解 123 123 123 13 123 min 3 211 423 2 1 0 zxxx xxx xxx xx xxx 用两阶段法来求解用两阶段法来求解 它的第一阶段是先解辅助问题 它的第一阶段是先解辅助问题 67 1234 12356 137 17 min 2 11 42 3 2 1 0 gxx xxxx xxxxx xxx xx x x1 1x x2 2x x3 3x x4 4x x5 5x x6 6x x7 7RHSRHS g g0 00 00 00 00 0 1 1 1 10 0 x x4 4 x x6 6 x x7 7 1 1 4 4 2 2 2 2 1 1 0 0 1 1 2 2 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1111 3 3 1 1 g g 6 61 13 30 0 1 10 00 04 4 x x4 4 x x6 6 x x7 7 1 1 4 4 2 2 2 2 1 1 0 0 1 1 2 2 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1111 3 3 1 1 g g0 01 10 00 0 1 10 0 3 31 1 x x4 43 3 2 20 01 10 00 0 1 11010 精品文档 7欢迎下载 x x6 6 x x3 3 0 0 2 2 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 1 1 0 0 2 2 1 1 1 1 1 1 g g0 00 00 00 00 0 1 1 1 10 0 x x4 4 x x2 2 x x3 3 3 3 0 0 2 2 0 0 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 2 2 1 1 0 0 2 2 1 1 0 0 5 5 2 2 1 1 1212 1 1 1 1 第二阶段第二阶段 x x1 1x x2 2x x3 3x x4 4x x5 5RHSRHS z z 3 31 11 10 00 00 0 x x4 4 x x2 2 x x3 3 3 3 0 0 2 2 0 0 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 2 2 1 1 0 0 1212 1 1 1 1 z z 1 10 00 00 01 1 2 2 x x4 4 x x2 2 x x3 3 3 3 0 0 2 2 0 0 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 2 2 1 1 0 0 1212 1 1 1 1 原问题无界 原问题无界 6 6 如何写出原问题的对偶问题 如果已知原问题的最优解 如如何写出原问题的对偶问题 如果已知原问题的最优解 如 何求解对偶问题的最优解 何求解对偶问题的最优解 minmax 1 0 1 0 01 01 TT T iii T iii T jjj T jjj c xb w s ta xbips tw a xbipmw xjqA wc xjqnA wc 精品文档 8欢迎下载 例例 写出下面线性规划问题的对偶问题写出下面线性规划问题的对偶问题 解 原问题的对偶问题为 解 原问题的对偶问题为 7 7 对偶单纯形方法适合解决什么样的问题 如何求解 对偶单纯形方法适合解决什么样的问题 如何求解 例 例 123 234 1235 12345 min 15245 6 2 52 1 0 zxxx xxx xxxx xxxxx 对偶单纯形法的基本法则对偶单纯形法的基本法则 法则法则 1 1 最优性判定法则 检验数全部小于等于零时最优 最优性判定法则 检验数全部小于等于零时最优 法则法则 2 2 换出变量确定法则 谁最负谁出基 换出变量确定法则 谁最负谁出基 法则法则 3 3 换入变量确定法则 最小比值原则 换入变量确定法则 最小比值原则 法则法则 4 4 换基迭代运算法则换基迭代运算法则 1234 1234 134 234 1234 min235 3 5 2 244 6 00 zxxxx xxxx xxx xxx x x x x 123 12 13 123 123 123 max546 22 3 325 41 0 0 ywww ww ww www www www 精品文档 9欢迎下载 x x1 1x x2 2x x3 3x x4 4x x5 5RHSRHS z z 15 15 24 24 5 50 00 00 0 x x4 4 x x5 5 0 0 5 5 6 6 2 2 1 1 1 1 1 1 0 0 0 0 1 1 2 2 1 1 z z 15 150 0 1 1 4 40 08 8 x x2 2 x x5 5 0 0 5 5 1 1 0 0 1 61 6 2 3 2 3 1 6 1 6 1 3 1 3 0 0 1 1 1 31 3 1 3 1 3 z z 15 2 15 20 00 0 7 2 7 2 3 2 3 217 217 2 x x2 2 x x3 3 5 4 5 4 15 215 2 1 1 0 0 0 0 1 1 1 4 1 4 1 21 2 1 41 4 3 2 3 2 1 41 4 1 21 2 写出对偶问题并求解 利用互补松紧条件 写出对偶问题并求解 利用互补松紧条件 8 8 对于已经求解的一个线性规划问题如果改变价值向量和右端对于已经求解的一个线性规划问题如果改变价值向量和右端 向量原最优解向量原最优解 基是否仍是最优解基是否仍是最优解 基 如果不是 如何进一步基 如果不是 如何进一步 求解 求解 例 线性规划例 线性规划 12 12 12 12 12 max 54 390 280 45 0 zxx xx xx xx xx 已知最优表 已知最优表 x x1 1x x2 2x x3 3x x4 4x x5 5RHSRHS 精品文档 10欢迎下载 z z0 00 00 0 1 1 3 3 215 215 x x3 3 x x1 1 x x2 2 0 0 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 2 2 1 1 1 1 5 5 1 1 2 2 2525 3535 1010 1 1 确定 确定x x2 2的系数的系数c c2 2的变化范围 使原最优解保持最优 的变化范围 使原最优解保持最优 2 2 若 若c c2 2 6 6 求新的最优计划 求新的最优计划 解解 1 1 将上表中的第 将上表中的第 0 0 行重新计算检验数 得到 行重新计算检验数 得到 x x1 1x x2 2x x3 3x x4 4x x5 5RHSRHS z z5 5c c2 20 00 00 00 0 x x3 3 x x1 1 x x2 2 0 0 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 2 2 1 1 1 1 5 5 1 1 2 2 2525 3535 1010 z z0 00 00 0 c c2 2 5 55 5 2 2c c2 2 175 175 1010c c2 2 x x3 3 x x1 1 x x2 2 0 0 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 2 2 1 1 1 1 5 5 1 1 2 2 2525 3535 1010 令令c c2 2 5 5 0 0 5 5 2 2c c2 2 0 0 解得 解得 5 25 2 c c2 2 5 5 即当 即当c c2 2在区间在区间 5 2 5 2 5 5 中变化时 最优解中变化时 最优解X X 3535 1010 2525 0 0 0 0 T T保持不变 保持不变 2 2 当 当c c2 2 6 6 时 时 c c2 2 5 5 1 0 1 0 原最优解失去最优性 在表中修 原最优解失去最优性 在表中修 改第改第 0 0 行后 用单纯形法容易求得新的最优表如下 行后 用单纯形法容易求得新的最优表如下 x x1 1x x2 2x x3 3x x4 4x x5 5RHSRHS 精品文档 11欢迎下载 z z0 00 00 01 1 7 7 235 235 x x3 3 x x1 1 x x2 2 0 0 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 2 2 1 1 1 1 5 5 1 1 2 2 2525 3535 1010 z z0 00 0 1 2 1 20 0 9 2 9 2 495 2 495 2 x x4 4 x x1 1 x x2 2 0 0 1 1 0 0 0 0 0 0 1 1 1 21 2 1 2 1 2 1 21 2 1 1 0 0 0 0 5 2 5 2 3 23 2 1 2 1 2 25 225 2 45 245 2 45 245 2 故新的最优解为故新的最优解为x x1 1 45 2 45 2 x x2 2 45 2 45 2 x x4 4 25 2 25 2 x x3 3 x x5 5 0 0 最 最 优值优值z z 495 2 495 2 例例 对于上例中的线性规划作下列分析 对于上例中的线性规划作下列分析 1 1 b b3 3在什么范围内变化 原最优基不变 在什么范围内变化 原最优基不变 2 2 若 若b b3 3 55 55 求出新的最优解 求出新的最优解 解解 原最优基为原最优基为B B P P3 3 P P1 1 P P2 2 由表 由表 2 62 6 可得 可得 B B 1 1 1 2 5 0 1 1 0 1 2 1 1 由 由B B 1 1 0 0 3 90 80 b 1 2 5 0 1 1 0 1 2 3 90 80 b 3 3 3 250 5b 80b 802b 解得解得 40 40 b b3 3 50 50 即当 即当b b3 3 40 40 50 50 时 最优基时 最优基B B不变 最优解为 不变 最优解为 x x4 4 x x5 5 0 0 z z 5 5 8080 b b3 3 3 1 2 x x x 3 3 3 250 5b 80b 802b 精品文档 12欢迎下载 4 4 80 280 2b b3 3 80 3 80 3b b3 3 2 2 当 当b b3 3 55 55 时 时 以它代替表的 以它代替表的b b列 用对偶单纯形法继续求列 用对偶单纯形法继续求 3 3 3 250 5b 80b 802b 25 25 30 解 解 x x1 1x x2 2x x3 3x x4 4x x5 5RHSRHS z z0 00 00 0 1 1 3 3 245 245 x x3 3 x x1 1 x x2 2 0 0 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 2 2 1 1 1 1 5 5 1 1 2 2 25 25 2525 3030 z z0 00 0 3 5 3 5 11 5 11 50 0 230 230 x x5 5 x x1 1 x x2 2 0 0 1 1 0 0 0 0 0 0 1 1 1 5 1 5 1 5 1 5 2 52 5 2 5 2 5 3 53 5 1 5 1 5 1 1 0 0 0 0 5 5 3030 2020 故新的最优解为故新的最优解为x x1 1 30 30 x x2 2 20 20 x x5 5 5 5 x x3 3 x x4 4 0 0 最优值 最优值 z z 230 230 精品文档 13欢迎下载 整数线性规划整数线性规划 0 10 1 规划规划 如何建立整数线性规划的数学模型 如何建立整数线性规划的数学模型 如何用图解法求解两个变量的整数线性规划问题 如何用图解法求解两个变量的整数线性规划问题 割平面方法的基本思想 如何用割平面方法求解整数线性规划割平面方法的基本思想 如何用割平面方法求解整数线性规划 问题 问题 分支定界方法的基本思想 如何用分支定界方法求解整数线性分支定界方法的基本思想 如何用分支定界方法求解整数线性 规划问题 规划问题 如何建立如何建立 0 10 1 规划问题的数学模型 规划问题的数学模型 如何用隐枚举法求解如何用隐枚举法求解 0 10 1 规划和匈牙利法求解指派问题 规划和匈牙利法求解指派问题 精品文档 14欢迎下载 1 1 如何建立整数线性规划的数学模型 如何建立整数线性规划的数学模型 2 2 如何用图解法求解两个变量的整数线性规划问题 如何用图解法求解两个变量的整数线性规划问题 3 3 割平面方法的基本思想 如何用割平面方法求解整数线性割平面方法的基本思想 如何用割平面方法求解整数线性 规划问题 规划问题 例例 考虑纯整数规划问题考虑纯整数规划问题 12 max zxx 12 12 12 26 4520 0 0 xx xx xx 且 且且 且且 且且 且 解解 先不考虑整数条件 求得其松弛问题的最优单纯形表为 先不考虑整数条件 求得其松弛问题的最优单纯形表为 x x1 1x x2 2x x3 3x x4 4RHSRHS z z0 00 0 1 6 1 6 1 6 1 6 13 3 13 3 精品文档 15欢迎下载 x x1 1 x x2 2 1 1 0 0 0 0 1 1 5 65 6 2 3 2 3 1 6 1 6 1 31 3 5 35 3 8 38 3 由第二行可以生成割平面 由第二行可以生成割平面 x x3 3 x x4 4 1 3 1 3 2 3 引入松弛变量引入松弛变量 s s1 1后得 后得 x x3 3 x x4 4 s s1 1 1 3 1 3 2 3 将此约束条件加到表中继续求解如下 将此约束条件加到表中继续求解如下 x x1 1x x2 2x x3 3x x4 4s s1 1RHSRHS z z0 00 0 1 6 1 6 1 6 1 60 0 13 3 13 3 x x1 1 x x2 2 s s1 1 1 1 0 0 0 0 0 0 1 1 0 0 5 65 6 2 3 2 3 1 3 1 3 1 6 1 6 1 31 3 1 3 1 3 0 0 0 0 1 1 5 35 3 8 38 3 2 3 2 3 z z0 00 00 00 0 1 2 1 2 4 4 x x1 1 x x2 2 x x3 3 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 5 25 2 2 2 3 3 0 0 4 4 2 2 所以原问题的最优解为 所以原问题的最优解为 x x1 1 0 0 x x2 2 4 4 最优值 最优值z z 4 4 4 4 分支定界方法的基本思想 如何用分支定界方法求解整数分支定界方法的基本思想 如何用分支定界方法求解整数 线性规划问题 线性规划问题 例例 求解下面整数规划求解下面整数规划 12 max32zxx 精品文档 16欢迎下载 12 12 12 29 2314 0 0 xx xx xx 且 且且 且且 且且 且且 且 P0 x1 3 25 x2 2 5 z 0 14 755 P2 x1 2 5 x2 3 z 2 13 5 P3 x1 3 x2 2 z 3 13 P4 x1 4 x2 1 z 4 14 P1 x1 3 5 x2 2 z 1 14 5 X2 4X1 3 5 5 如何建立 如何建立 0 10 1 规划问题的数学模型 规划问题的数学模型 6 6 如何用隐枚举法求解 如何用隐枚举法求解 0 10 1 规划和匈牙利法求解指派问题 规划和匈牙利法求解指派问题 例例 123 max543zxxx 123 123 23 123 325 2735 22 5327 0 3 j xxx xxx xx xxx xj 且 且1 1 1 1 2 2 123 5434xxx 满满 足足 条条 件件 x x1 1 x x2 2 x x3 3 满足所有满足所有 条件 条件 z z值值 0 0 0 0 0 0 精品文档 17欢迎下载 0 0 0 0 1 1 0 0 1 1 0 0 4 4 0 0 1 1 1 1 1 1 0 0 0 0 1 1 0 0 1 1 8 8 1 1 1 1 0 0 9 9 1 1 1 1 1 1 动态规划动态规划 了解基本概念 如多阶段决策问题 阶段 策略 了解基本概念 如多阶段决策问题 阶段 策略 了解最优性原理 了解最优性原理 如何用动态规划方法求解最短路问题 图上作业 公式求解 如何用动态规划方法求解最短路问题 图上作业 公式求解 如何用动态规划方法求解旅行售货员问题 如何用动态规划方法求解旅行售货员问题 如何求解多阶段的资源分配问题 如何求解多阶段的资源分配问题 精品文档 18欢迎下载 网络分析网络分析 了解图的基本概念 如无向图 有向图 点 边 关联 邻接 了解图的基本概念 如无向图 有向图 点 边 关联 邻接 次 关联矩阵 邻接矩阵 握手定理 次 关联矩阵 邻接矩阵 握手定理 树 支撑树 如何找最小树 破圈法 避圈法 反圈法 树 支撑树 如何找最小树 破圈法 避圈法 反圈法 最短路问题 图上标号法 列表法 最短路问题 图上标号法 列表法 最大流问题 找增广路 最大流问题 找增广路 精品文档 19欢迎下载 1 1 树 支撑树 如何找最小树 破圈法 避圈法 反圈法 树 支撑树 如何找最小树 破圈法 避圈法 反圈法 例例 设树有设树有 7 7 条边 则它有 条边 则它有 8 8 个结点 个结点 例例 一个由一个由 3 3 个分支构成的森林 如果有个分支构成的森林 如果有 1515 个结点 则该森林至少个结点 则该森林至少 有 有 1212 条边 条边 例例 一棵树一棵树 T T 有有 5 5 个度为个度为 2 2 的结点 的结点 3 3 个度为个度为 3 3 的结点 的结点 4 4 个度为个度为 4 4 的结点 的结点 2 2 个度为个度为 5 5 的结点 其余均是度为的结点 其余均是度为 1 1 的结点 问的结点 问 T T 有几个有几个 度为度为 1 1 的结点 的结点 解解 设设 T T 有有 x x 个度为个度为 1 1 的结点 则有的结点 则有 精品文档 20欢迎下载 5 5 2 32 3 3 43 4 4 24 2 5 x5 x 2m2m m m n n 1 1 5 3 4 2 x5 3 4 2 x n n 解以上三个方程得解以上三个方程得 x x 1919 例 例 公园路径系统见下图 公园路径系统见下图 S S 为入口 为入口 T T 为出口 为出口 A A B B C C D D E E 为为 5 5 个景点 现安装电话线连接各景点 则最小线路安装是什么 个景点 现安装电话线连接各景点 则最小线路安装是什么 如果某游客刚进入入口就急需从出口离开 那么该游客应该如何走如果某游客刚进入入口就急需从出口离开 那么该游客应该如何走 最快 最快 2 2 最短路问题 图上标号法 列表法 最短路问题 图上标号法 列表法 3 3 最大流问题 找增广路 最大流问题 找增广路 从甲地到乙地的公路网纵横交错 每天每条路上的通车量有上限从甲地到乙地的公路网纵横交错 每天每条路上的通车量有上限 从甲地到乙地的每天最多能通车多少辆从甲地到乙地的每天最多能通车多少辆 精品文档 21