运筹学习题杂.pdf

P127 5 2 分别分别用图解法和单纯形法用图解法和单纯形法找出以下找出以下目标规划问题的满意解目标规划问题的满意解 1 111223 1211 1222 1233 12 min 2 1050 3520 86100 0 1 2 3 ii zP ddPdd xxdd xxdd xxdd x x ddi 图解法 根据优先因子 首先考虑 111 P dd 为了满足该目标 可以看出 1 x 2 x应该在 12 1050 xx 且 2 0 x 的射线上 再考虑 223 2 Pdd 因为 2 d 的系数大于 3 d 所以要找上述射线中距离直线 12 3520 xx 最近的点 得到满意解 12 50 0 xx 单纯形法 j c 1 P 1 P 2 2P 2 P B C B X b 1 x 2 x 1 d 1 d 2 d 2 d 3 d 3 d 1 P 1 d 50 1 10 1 1 50 2 d 20 3 5 1 1 20 3 3 d 100 8 6 1 1 25 2 jj cz 1 P 1 10 2 2 P 1 P 1 d 130 3 35 3 1 1 1 3 1 3 130 1 x 20 3 1 5 3 1 3 1 3 3 d 140 3 22 3 8 3 8 3 1 1 35 2 jj cz 1 P 35 3 2 1 3 1 3 2 P 1 P 1 d 75 2 43 4 1 1 1 8 1 8 1 x 25 2 1 3 4 1 8 1 8 2 2P 2 d 35 2 11 4 1 1 3 8 3 8 jj cz 1 P 43 4 2 1 8 1 8 2 P 2 P 3 d 300 86 8 8 1 1 1 x 50 1 10 1 1 2 2P 2 d 130 35 3 3 1 1 jj cz 1 P 1 1 2 P 156 14 14 2 1 因为第二行检验数中 不存在检验数为负数且对应第一行检验数为 0 的数 计算结束 由最终表可得满意解 12 50 0 xx 5 4 南溪市计划在下一年度预算中购置一批救护车 已知每辆购置价为南溪市计划在下一年度预算中购置一批救护车 已知每辆购置价为 20 万元 救护车用万元 救护车用 于所属于所属 A B 两个郊区县 各分配两个郊区县 各分配 a x辆和辆和 b x A 县救护站从接到呼叫到出动的相应时间为县救护站从接到呼叫到出动的相应时间为 a 40 3x 分钟 分钟 B 县救护站的相应时间为 县救护站的相应时间为 b 50 4x 分钟 该市确定如下优化目标 分钟 该市确定如下优化目标 1 P 用于救护车的购置费不超过用于救护车的购置费不超过 400 万元 万元 2 P A 县的响应时间不超过县的响应时间不超过 8 分钟 分钟 3 P B 县的响应时间不超过县的响应时间不超过 8 分钟 分钟 解解 目标规划模型为 112233 minzp dp dp d 11 22 33 2020400 4038 5048 0 0 1 2 3 ab a b ab ii xxdd xdd xdd xx ddi 的整数 P152 6 2 用用分支界限法分支界限法解解 21 maxxxz 整数 21 21 21 21 0 3 1 2 14 51 14 9 xx xx xx xx 解 解 利用分支定界法 首先 用单纯形法解相应的线性规划问题 如下 将该线性规划问题 转换为标准型 使用单纯形表求解 不同的替换方式会有两种过程 1 j c 1 1 0 0 B C B X b 1 x 2 x 3 x 4 x 0 3 x 14 51 1 14 9 1 0 14 51 0 4 x 3 1 2 1 0 1 z 0 1 1 0 0 1 1 x 14 51 1 14 9 1 0 9 51 0 4 x 21 160 0 7 16 2 1 3 10 z 14 51 0 14 5 1 0 1 1 x 2 3 1 0 16 7 32 9 1 2 x 3 10 0 1 8 7 16 7 z 6 29 0 0 16 21 32 5 2 j c 1 1 0 0 B C B X b 1 x 2 x 3 x 4 x 0 3 x 14 51 1 14 9 1 0 9 51 0 4 x 3 1 2 1 0 1 3 1 z 0 1 1 0 0 0 3 x 7 24 7 16 0 1 14 9 2 3 1 2 x 3 1 2 1 0 1 z 3 1 3 0 0 1 1 1 x 2 3 1 0 16 7 32 9 1 2 x 3 10 0 1 8 7 16 7 z 6 29 0 0 16 21 32 5 相应的线性规划问题有最优解 2 3 1 x 3 10 2 x 6 29 0 z 这时 0 z是原整数规划问 题的最优目标函数值 z的上界 记作zz 0 而0 1 x 0 2 x时 显然是原整数规划问 题的一个整数可行解 这时 z 0 是 z的一个下界 记作0 z 即 6 29 0 z 下面利用分支定界法求解 过程如下 问题 0 B 3 10 2 3 21 xx 6 29 0 z 1 1 x2 1 x 问题 1 B 3 7 1 21 xx 3 10 1 z 问题 2 B 9 5 2 2 21 xx 9 5 4 2 z 6 29 0 zz 9 5 4 0 zz 2 2 x3 2 x 问题 3 B 2 14 5 2 21 xx 14 5 4 3 z 问题 4 B 无可行解 2 1 x3 1 x 问题 5 B 2 2 21 xx 4 5 z 问题 6 B 1 3 21 xx 4 6 z 14 5 4 0 zz 4 zz 可以得到问题的最优解 1 2 1 x 2 2 x 4 z 2 3 1 x 1 2 x 4 z 6 3 用用 Gomory 切割法解切割法解 1 21 maxxxz 1 整数 21 21 21 21 0 2054 62 xx xx xx xx 5 4 3 2 解 解 利用 Gomory 切割法 首先 用单纯形法解相应的线性规划问题 如下 将该线性规划问题转换为标准型 4321 00maxxxxxz 0 2054 62 4321 421 321 xxxx xxx xxx 7 6 使用单纯形表求解 不同的替换方式会有两种过程 1 j c 1 1 0 0 B C B X b 1 x 2 x 3 x 4 x 0 3 x 6 2 1 1 0 3 0 4 x 20 4 5 0 1 5 z 0 1 1 0 0 1 1 x 3 1 2 1 2 1 0 6 0 4 x 8 0 3 2 1 3 8 z 3 0 2 1 2 1 0 1 1 x 3 5 1 0 6 5 6 1 1 2 x 3 8 0 1 3 2 3 1 z 3 13 0 0 6 1 6 1 2 j c 1 1 0 0 B C B X b 1 x 2 x 3 x 4 x 0 3 x 6 2 1 1 0 6 0 4 x 20 4 5 0 1 4 z 0 1 1 0 0 0 3 x 2 5 6 0 1 5 1 6 10 1 2 x 4 5 4 1 0 5 1 5 z 4 5 1 0 0 5 1 1 1 x 3 5 1 0 6 5 6 1 1 2 x 3 8 0 1 3 2 3 1 z 3 13 0 0 6 1 6 1 相应的线性规划问题有最优解 3 5 1 x 3 8 2 x 3 13 0 z 由最终计算表中得到变量间的关系式 3 5 6 1 6 5 431 xxx和 3 8 3 1 3 2 432 xxx 将系数和常数项都分解成整数和非负真分数之和 移项以上两式变为 6 5 6 5 3 2 1 4341 xxxx 和 3 1 3 1 3 2 2 4332 xxxx 先考虑整数条件 5 要求 1 x和 2 x都是非负整数 于是由条件 6 7 知道 3 x和 4 x 也都是非负整数 在上式中从等式左边看是整数 在等式右边的括号内是正书 所以等式右 边必为负数 也就是说 整数条件 5 可以由下式代替 2 2 5 4 0 3 1 3 1 3 2 0 6 5 6 5 3 2 43 43 43 43 43 xx xx xx xx xx 8 这样就得到一个切割方程 将它作为增加约束条件 再解该整数线性规划问题 引入松弛变量 5 x 得到等式2 543 xxx 将这新的约束方程加到上面的最终计算表 得下表 j c 1 1 0 0 0 B C B X b 1 x 2 x 3 x 4 x 5 x 1 1 x 3 5 1 0 6 5 6 1 0 1 2 x 3 8 0 1 3 2 3 1 0 0 5 x 2 0 0 1 1 1 z 3 13 0 0 6 1 6 1 0 从上表中的 b 列可以看出 这时得到的是非可行解 于是需要用对偶单纯形法继续进行 计算 选择 5 x为换出变量 计算 6 1 1 6 1 1 6 1 min0 min lj lj jj j a a zc 1 将 3 x作为换入变量 再按照单纯形法进行迭代 得下表 j c 1 1 0 0 0 B C B X b 1 x 2 x 3 x 4 x 5 x 1 1 x 0 1 0 0 1 6 5 1 2 x 4 0 1 0 1 3 2 0 3 x 2 0 0 1 1 1 z 4 0 0 0 0 6 1 得到最优解0 1 x 4 2 x 4 z 2 将 4 x作为换入变量 再按照单纯形法进行迭代 得下表 j c 1 1 0 0 0 B C B X b 1 x 2 x 3 x 4 x 5 x 1 1 x 2 1 0 1 0 6 1 1 2 x 2 0 1 1 0 3 1 0 4 x 2 0 0 1 1 1 z 4 0 0 0 0 6 1 得到最优解2 1 x 2 2 x 4 z 6 8 解解 0 1 规划规划 2 4321 4352minxxxxz 10 1 44242 04 4321 4321 4321 4321 或xxxx xxxx xxxx xxxx 解 解 首先 通过试探的方法找一个可行解 容易看出 1 0 0 0 4321 xxxx就是符合各 个约束条件的可行解 相应的目标函数值 z 4 于是 增加一个约束条件 过滤的条件 44352 4321 xxxx 然后 整理该 0 1 规划问题 重新排列 i x的顺序使目标函数中 i x的系数是递减的 因为本题是求因为本题是求 min z 所以 所以 i x的系数是递减的 相当于的系数是递减的 相当于 max z 中的中的 i x的系数是递增的系数是递增 的的 这样的好处在于将导致解变化最大的因素放在变化最频繁的地方 可以减少计算量这样的好处在于将导致解变化最大的因素放在变化最频繁的地方 可以减少计算量 整理后得到 1342 2345minxxxxz 1 42244 04 42345 1342 1342 1342 1342 xxxx xxxx xxxx xxxx 3 2 1 具体解题步骤如下 1342 xxxx 条 件 是否满足 条件 z 值 1 2 3 0 0 0 0 0 X 0 0 0 1 2 4 X 0 0 1 0 3 1 2 X 0 0 1 1 5 X 0 1 0 0 4 1 4 1 Y 4 0 1 0 1 6 X 0 1 1 0 7 X 0 1 1 1 9 X 1 0 0 0 5 X 1 0 0 1 7 X 1 0 1 0 8 X 1 0 1 1 10 X 1 1 0 0 9 X 1 1 0 1 11 X 1 1 1 0 12 X 1 1 1 1 14 X 所以 该 0 1 规划问题最优解为 T X 1 0 0 0 4 z 6 9 有有 4 个工人 要指派他们分别完成个工人 要指派他们分别完成 4 种工作 每人做各种工作所消耗的时间如下表所示 种工作 每人做各种工作所消耗的时间如下表所示 问指派那个人去完成哪种工作 可使总的消耗时间为最小 问指派那个人去完成哪种工作 可使总的消耗时间为最小 解 解 第一步 进行系数矩阵变换 过程如下 17232119 19161726 18222319 24211815 17 16 18 15 min 0642 30110 0451 9630 min 0632 30010 0441 9620 第二步 进行试指派 得到如下矩阵 632 310 441 962 这时 的个数是 m 3 而 n 4 所以解题没有完成 第三步 作直线覆盖所有 0 元素 如下 632 310 441 962 直线数 l 3 n 4 进一步变换系数矩阵 第四步 增加 0 元素 过程如下 选择系数矩阵中没有被直线覆盖的部分中最小的元素为1 21 c 然后在打 行各元素 上减去该最小元素 而在打 列的各元素上都加上该最小元素 以保证原来 0 元素不变 得到新的系数矩阵为 0521 40010 0330 10620 重复第二步 进行试指派 得到如下矩阵 521 410 33 1062 这时 的个数是 m 3 而 n 4 所以解题没有完成 第三步 作直线覆盖所有 0 元素 如下 521 410 33 1062 直线数 l 3 n 4 进一步变换系数矩阵 第四步 增加 0 元素 过程如下 选择系数矩阵中没有被直线覆盖的部分中最小的元素为2 12 c 然后在打 行各元素 上减去该最小元素 而在打 列的各元素上都加上该最小元素 以保证原来 0 元素不变 得到新的系数矩阵为 0301 60012 0110 10400 重复第二步 进行试指派 得到如下矩阵 31 612 11 104 或者 31 612 11 104 这两种方案中的 个数是 m n 4 所以解题已经完成 最优的指派方案是 70 P327 11 9 在下图中在下图中 4 3 1 1 4 4 3 3 2 6 7 61 v 2 v 5 v 7 v 3 v 4 v6 v 8 v 用用 Dijkstra 方法求从方法求从 v1 到到各点各点的最短路 的最短路 解解 11 Sv 1 0P v 1 0v i T v i vM 2 3 8 i 1k 1 i 1 12 v vA 21 vS 得 21122 min 4T vP vwT v 2 1v 15 v vA 51 vS 得 51155 min 1T vP vwT v 5 1v 17 v vA 71 vS 得 71177 min 3T vP vwT v 7 1v 2575 min T vT vT vT v 令 55 1P vT v 21515 SSvv v 5k 2 i 2 56 v vA 62 vS 得 65566 min 7T vP vwT v 6 5v 2677 min T vT vT vT v 令 77 3P vT v 327157 SSvv v v 7k 3 i 3 262 min T vT vT v 令 22 4P vT v 4321257 SSvv v v v 2k 4 i 4 66 min T vT v 令 66 7P vT v 54612567 SSvv v v v v 6k 5 i 5 68 v vA 85 vS 得 86688 min 10T vP vwT v 8 6v 88 min T vT v 令 88 10P vT v 658125678 SSvv v v v v v 8k 6 i 6 8 3 4 i v vA i 算法结束 所以 12 4d v v 13 d v v 14 d v v 15 1d v v 16 7d v v 17 3d v v 18 10d v v 11 13 求求下图所示的网络的最大流下图所示的网络的最大流 s v t v8 4 7 10 15 9 6 11 10 5 15 12 7 9 13 18 6 解 图上数值为 ij c容量值 开始时我们令 ij f 0 就可以得到可行流 0 用标号法求所 示的网络最大流 每弧旁的数字是 ijij fc 起始图如下 s v t v8 0 4 0 15 0 7 0 10 0 9 0 9 0 5 0 10 0 6 0 15 0 110 13 0 18 0 7 0 12 0 2 v 6 v 1 v 3 v 4 v 5 v 7 v 8 v 6 0 具体过程如下 1 1 开始时 先给 s v标上 0 1 2 检查 s v 在 弧 1 vvs上 11 08 ss fc 则 1 v的 标 号 为 1 vlvs 其 中 111 min min 8 8 sss l vl vcf s v标号且检查 1 v标号但未检查 1 3 检查 1 v 在弧 31 v v上 不满足条件 在弧 14 v v上 1414414 411414 07 min min 8 7 7 fcvv l v l vl vcf 则 的标号为 其中 1 v标号且检查 4 v标号但未检查 1 4 检查 4 v 在弧 43 v v上 4343343 344343 06 min min 7 6 6 fcvv l v l vl vcf 则 的标号为 其中 4 v标号且检查 3 v标号但未检查 1 5 检查 3 v 在弧 3 t v v上 3t33 333 05 min min 6 5 5 ttt ttt fcvv l v l vl vcf 则 的标号为 其中 3 v标号且检查 t v标号 增广链形成 进行调试 1 6 有增广链 143 st v v v v v 调整量 5 t l v 令 ji ji ji ij ij ij ij vv vv vv f f f f 可以得到如下新的可行流 s v t v 8 5 4 0 15 0 7 5 10 0 9 0 9 0 5 5 10 0 6 0 15 0 110 13 0 18 0 7 0 12 0 2 v 6 v 1 v 3 v 4 v 5 v 7 v 8 v 6 5 去掉所有的标号 对新的可行流 如上图 重新进入标号过程 重复上面过程 直至标号过程无法继续下去 算法结束重复上面过程 直至标号过程无法继续下去 算法结束 最终图为最终图为 s v t v 8 5 4 0 1511 7 5 10 9 9 9 9 9 5 5 10 2 6 2 15 9 1111 13 0 18 9 7 0 12 9 2 v 6 v 1 v 3 v 4 v 5 v 7 v 8 v 6 5 最大流最大流 5 9 1125v f 最小截流为 最小截流为 111s263141578t vvvv v v v v vvv v v v 11 15 求求下图所示的网络的最小费用最大流 每弧旁的数字是下图所示的网络的最小费用最大流 每弧旁的数字是 ijij b c s v t v 3 3 1 4 3 5 1 1 2 1 4 2 2 5 1 3 4 2 1 v 2 v 3 v 4 v 解 解 1 取 0 0f 为初始可行流 构造赋权有向图 0 W f 并求出 s v到 t v的最短路 13 st v v v v s v t v 1 v 2 v 3 v 4 v 1 3 11 3 2 2 4 4 对应增广链 13 st v v v v 进行调整 3 得 1 f s v t v 1 v 2 v 3 v 4 v 3 3 3 0 0 0 0 0 0 2 构造赋权有向图 1 W f 并求出 s v到 t v的最短路 1243 st v v v v v v s v t v 1 v 2 v 3 v 4 v 1 3 11 3 2 2 4 4 1 2 进行调整 1 得 2 f s v t v 1 v 2 v 3 v 4 v 4 3 4 0 1 1 0 1 0 3 构造赋权有向图 2 W f 并求出 s v到 t v的最短路 243 st v v v v v s v t v 1 v 2 v 3 v 4 v 3 1 1 3 2 2 4 4 1 2 1 4 进行调整 1 得 3 f s v t v 1 v 2 v 3 v 4 v 4 3 5 1 1 2 0 2 0 4 构造赋权有向图 3 W f s v t v 1 v 2 v 3 v 4 v 3 1 1 3 2 2 4 1 2 1 4 此时 已经不存在 s v到 t v的最短路径 则 3 f就是最小费用最大流 最大流为 5 费用为 37 11 16 求解如图所示的中国邮递员问题求解如图所示的中国邮递员问题 解 解 对上面左图从上到下 从左到右一次编号 编号如下矩阵所示 14710 25811 36912 vvvv vvvv vvvv 可知 245678911 v v v v v v v v 将 8 个奇点分为 4 组 254769811 v vv vv vv v 然后去链 并调整方案 使重复边总权重下降 最终结果如上右图 由上图可知 1 在图的每一条边上至多有一条重复边 2 图中每圈上重复边的总权重不大于该圈总权值的一半 故上右图中任一欧拉