运筹习题课.pdf

1 1 单纯形法单纯形法 图解法 图解法 a 12 12 12 12 12 min35 26 410 4 0 0 Zxx xx xx xx xx 解解 图解法 单纯形法 Cj 3 5 0 0 0 b CB XB x1 x2 x3 x4 x5 0 x3 1 2 1 0 0 6 0 x4 1 4 0 1 0 10 0 x5 1 1 0 0 1 4 j 3 5 0 0 0 0 0 x3 0 5 0 1 0 5 0 1 5 x2 0 25 1 0 0 25 0 2 5 0 x5 0 75 0 0 0 25 1 1 5 j 1 75 0 0 1 25 0 12 5 3 x1 1 0 2 1 0 2 5 x2 0 1 0 5 0 5 0 2 0 x5 0 0 1 5 0 5 1 0 2 j 0 0 3 5 0 5 0 16 3 x1 1 0 1 0 2 2 5 x2 0 1 1 0 1 2 0 x4 0 0 3 1 2 0 j 0 0 2 0 1 16 至此 检验数0 j 得最优解为 2 2 T X 最优值为16Z b 12 12 12 12 max105 349 528 0 0 Zxx xx xx xx 解解 图解法 单纯形法 Cj 10 5 0 0 b CB XB x1 x2 x3 x4 0 x3 3 4 1 0 9 0 x4 5 2 0 1 8 j 10 5 0 0 0 0 x3 0 14 5 1 3 5 21 5 10 x1 1 2 5 0 1 5 8 5 j 0 1 0 2 16 3 5 x2 0 1 5 14 3 14 3 2 10 x1 1 0 1 7 2 7 1 j 0 0 5 14 25 14 35 2 至此 检验数0 j 得最优解为 3 1 2 T X 最优值为 35 2 Z 2 对偶规划对偶规划 a 写出下列线性规划的对偶问题 1234 1234 134 1234 1 1234 max2367 3269 656 222 510 0 Zxxxx xxxx xxx xxxx x xx x x 无约束 解解 1234 1234 134 1234 1 1 1234 max2367 3269 656 222 5 10 0 Zxxxx xxxx xxx xxxx x x xx x x 无约束 对偶问题为 12345 12345 12 123 123 12345 min962 510 362 223 56 627 0 000 wyyyyy yyyyy yy yyy yyy yyyyx 无约束 b 已知线性规划问题 1234 1234 1234 1234 max234 22320 23220 0 Zxxxx xxxx xxxx x xx x 其对偶问题的最优解为 12 1 2 0 2yy 根据对偶理论求出原问题的最优解 解解 原问题的对偶问题为 4 12 12 12 12 12 12 min2020 21 22 233 324 0 Zyy yy yy yy yy y y 由 12 1 2 0 2yy 均不为零知 原问题的松弛变量 12 0 0 ss xx 故有 1234 1234 22320 23220 xxxx xxxx 而对于对偶问题 易知第一式和第二式不为等式 也即 12 0 0 ss yy 故原问题 的 12 0 0 xx 进一步计算可得 34 4 4xx 所以原问题的最优解为 0 0 4 4 TX 最优值为28Z 3 整数规划整数规划 a 用分支界定法求解下列整数规划问题 12 12 12 12 max23 5735 4936 0 Zxx xx xx x x 且为整数 解解 先求对应的松弛问题 记为 LP0 12 12 12 12 max23 5735 04936 0 Zxx xx LPxx x x 用图解法得最优解为 63 40 17 17 X 0 246 17 Z 如图 3 1 所示 图图 3 3 1 1 5 12 x x不是整数解 任意选一个非整数变量分支 这里选 1 x 在 LP0 中加入 约束 1 3x 及 1 4x 得到线性规划 LP1 和 LP2 12 12 12 1 12 max23 5735 4936 1 3 0 Zxx xx xx LP x x x 12 12 12 1 12 max23 5735 4936 2 4 0 Zxx xx xx LP x x x 图解法如图 3 2 所示 图图 3 3 2 2 选择目标值最大的分支 LP2 进行分支 增加约束 2 2x 及 2 3x 由图 3 2 知 1 3x 不可行 因此得到线性规划 LP3 图解法如图 3 3 所示 12 12 12 12 12 max23 5735 4936 3 42 0 Zxx xx xx LP xx x x 6 图图 3 3 3 3 由图 3 3 可知 对 1 x进行分支 增加约束 1 4x 及 1 5x 得到线性规划 LP4 和 LP5 显然 LP4 的可行解在 1 4 x的线段上 且有图 3 4 易知 LP5 的最大值 5 Z没 有 LP4 的最大值 4 Z 因此 LP4 的解是整数规划的最优解 最优解为 4 2X 14Z 图图 3 3 4 4 b 用割平面法求解下列整数规划问题 12 12 12 12 max79 36 735 0 Zxx xx xx x x 且为整数 7 解解 先求对应的松弛问题是 12 12 12 12 max79 36 735 0 Zxx xx xx x x 加入松弛变量 34 x x后 用单纯形法求解 最优表如表 3 1 所示 表表 3 3 1 1 Cj 7 9 0 0 b CB XB x1 x2 x3 x4 0 x3 1 3 1 0 6 0 x4 7 1 0 1 35 j 7 9 0 0 0 9 x2 1 3 1 1 3 0 2 0 x4 22 3 0 1 3 1 33 j 10 0 3 0 18 9 x2 0 1 7 22 1 22 7 2 7 x1 1 0 1 22 3 22 9 2 j 0 0 28 11 15 11 63 最优解为 0 9 7 2 2 X 不是 IP 的最优解 选择表 3 1 中最优表的第一行 也可 以选择第二行 为源行 得 234 717 22222 xxx 分离系数后改写为 234 711 30 22222 xxx 加入松弛变量 5 x得到高莫雷约束方程 345 711 22222 xxx 将上式作为约束条件添加到表 3 1 的最优表中 用对偶单纯形法计算 如表 3 2 所示 表表 3 3 2 2 Cj 7 9 0 0 0 b CB XB x1 x2 x3 x4 x5 9 x2 0 1 7 22 1 22 0 7 2 7 x1 1 0 1 22 3 22 0 9 2 0 x5 0 0 7 22 1 22 1 1 2 8 j 0 0 28 11 15 11 0 63 9 x2 0 1 0 0 1 3 7 x1 1 0 0 1 7 1 7 32 7 0 x3 0 0 1 1 7 22 7 11 7 j 0 0 0 1 8 59 最优解为 1 32 3 7 X 不是 IP 的最优解 选择表 3 2 中最优表的第二行 也 可以选择第三行 为源行 得 145 1132 777 xxx 分离系数后 并加入松弛变量 6 x得到高莫雷约束方程 456 164 777 xxx 将此约束条件添加到表 3 2 的最优表中 用对偶单纯形法计算 如表 3 3 所示 表表 3 3 3 3 Cj 7 9 0 0 0 0 b CB XB x1 x2 x3 x4 x5 x6 9 x2 0 1 0 0 1 0 3 7 x1 1 0 0 1 7 1 7 0 32 7 0 x3 0 0 1 1 7 22 7 0 11 7 0 x6 0 0 0 1 7 6 7 1 4 7 j 0 0 0 1 8 0 59 9 x2 0 1 0 0 1 0 3 7 x1 1 0 0 0 1 1 4 0 x3 0 0 1 0 4 1 1 0 x6 0 0 0 1 6 7 4 j 0 0 0 0 2 7 55 最优解为 2 4 3X 最优值为55Z 所有变量都为整数 2 X就是 IP 的最 优解 4 运输问题运输问题 习题习题 5 6 某试验设备厂按合同规定在当年前四个月末分别提供同一型号的干燥箱某试验设备厂按合同规定在当年前四个月末分别提供同一型号的干燥箱 50 40 60 80 台给用户 该厂每个月的生产能力为台给用户 该厂每个月的生产能力为 65 台 如果生产的产品当月不台 如果生产的产品当月不 能交货 每台每月必须支付维护及储存费能交货 每台每月必须支付维护及储存费 0 15 万元 已知四个月内每台生产费万元 已知四个月内每台生产费 9 分别是分别是 1 1 25 0 87 0 98 万元 试安排这四个月的生产计划 使既能按合万元 试安排这四个月的生产计划 使既能按合同如期同如期 交货 又能使总费用最小 交货 又能使总费用最小 1 建立此问题的数学模型 建立此问题的数学模型 2 将此问题化为运输问题 建立平衡运价表 将此问题化为运输问题 建立平衡运价表 3 求最优解 求最优解 1 设 xij为第 i 月生产的产品第 j 月交货的台数 则此生产计划问题的数学模 型为 111213142144 11213141 12223242 13233343 14243444 11121314 21222324 31323334 41424344 min1 151 31 450 98 50 40 60 80 65 65 65 65 0 ij ZxxxxMxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xi j 1 4 2 化为运输问题后运价表 即生产费用加上存储费用 如下 其中第 5 列是 虚设销地费用为零 需求量为 30 1 2 3 4 5 ai 1 2 3 4 1 M M M 1 15 1 25 M M 1 3 1 4 0 87 M 1 45 1 55 1 02 0 98 0 0 0 0 65 65 65 65 bj 50 40 60 80 30 3 用最小元素法 得如下表 表表 4 4 1 1 1 2 3 4 5 ai 1 3 1 5 1 15 1 3 1 45 0 65 50 15 2 M 6 1 25 1 4 7 1 55 8 0 65 25 10 30 3 M M 1 0 87 4 1 02 0 65 60 5 4 M M M 2 0 98 0 65 65 bj 50 40 60 80 30 用闭回路法求得非基变量的检验数0 ij 说明上表的运输方案最优 最优解为 1 50 1 15 15 1 25 25 0 87 60 1 55 10 1 02 5 0 98 65 235Z 也即 一月份生产 65 台 当月交货 50 台 二月份交货 15 台 二月份生产 35 台 当月交货 25 台 四月份交货 10 台 三月份生产 65 台 当月交货 60 台 四月份 交货 5 台 4 月份生产 65 台当月交货 最小费用 Z 235 万元 10 补充补充 若严格用最小元素法直接求 表表 4 4 2 2 1 2 3 4 5 ai 1 4 1 6 1 15 1 3 1 45 0 65 50 15 2 M 7 1 25 1 4 1 55 0 65 25 40 3 M M 2 0 87 5 1 02 0 65 60 5 4 M M M 3 0 98 1 0 65 35 30 bj 50 40 60 80 30 但 是 经 计 算 检 验 数 15151222244445 0 470CCCCCC 2525244445 0 570CCCC 其余非基变量检验数均大于等于 0 所以这 组基本可行解不是最优解 251525 min 最小 对应的非基变量 25 x进基 25 x 的闭回路是 25244445 xxxx 标负号的变量是 2445 xx 取运量最小值即 2445 40 3030min xxmin 45 x最小 45 x是出基量 调整量30 在 25 x的闭回路上 2544 xx分别加上 30 2445 xx分别减去 30 并且在 45 x处打上记号 作为非基变量 其余变量的值 保持不变 调整后得到一组新的基本可行解 如下表 4 3 表表 4 4 3 3 1 2 3 4 5 ai 1 4 1 6 1 15 1 3 1 45 0 65 50 15 2 M 7 1 25 1 4 1 55 0 65 25 40 30 30 3 M M 2 0 87 5 1 02 0 65 60 5 4 M M M 3 0 98 1 0 65 35 30 30 30 bj 50 40 60 80 30 重新求得所有检验数均大于等于 0 表明此解为最优解 事实上易知 表 4 3 即为表 4 1 5 指派问题指派问题 习题习题 5 10 学校举行游泳 自行车 长跑和登山四项接力赛 已知五名运动员完成各项目学校举行游泳 自行车 长跑和登山四项接力赛 已知五名运动员完成各项目 的成绩 分钟 如表的成绩 分钟 如表 5 58 所示 如何从中选拔一个接力队 使预期的比赛成绩所示 如何从中选拔一个接力队 使预期的比赛成绩 最好 最好 解 设 xij为第 i 人参加第 j 项目的状态 则数学模型为 11 1112131454 11121314 21222324 31323334 41424344 51525354 1121314151 1222324252 1323334353 14243444 min2043332928 1 1 1 1 1 1 1 1 Zxxxxx xxxx xxxx xxxx xxxx xxxx xxxxx xxxxx xxxxx xxxxx 54 1 01 1 2 5 1 2 3 4 ij xij 或 用匈牙利算法计算 第一步 找出效率矩阵每行的最小元素 并分别从每行中减去最小元素 有 20433329 20023139 15332826 150181311 18423829 180242011 19443227 19025138 17343028 170171311 min 第二步 找出矩阵