《运筹学》复习题

1 工商工商 12 运筹学运筹学 复习题复习题 一 求解下列线性规划 0 16284 2042 4224 2max 321 321 21 321 321 xxx xxx xx xxx xxxz 解 标准型为 用 M 法求解 0 16284 2042 4224 2max 7321 6321 521 74321 7321 xxxx xxxx xxx xxxxx Mxxxxz 211000 M B C B X b 1 x 2 x 3 x 4 x 5 x 6 x 7 x i M7 x 4 4 22 10011 05 x 20240010010 06 x 1648200104 z4M4M 22M 12M 1 M000 21 x 111 21 2 1 4001 4 05 x 1803 11 210 1 236 06 x 12060 1 01 112 z 20001 200 M 1 2 21 x 4121 2001 40 05 x 1200 101 1 2 1 04 x 12060101 1 z 80 3000 1 M 2 所以 8 0 0 12 12 0 0 4 zX T 二 已知线性规划模型 无约束 321 321 321 321 321 0 10 1632 182 635max xxx xxx xxx xxx xxxz 的最优解为 试用对偶理论求其对偶问题的最优解 T X 4 0 14 解 其对偶模型为 无约束 321 321 321 321 321 0 63 32 52 101618min yyy yyy yyy yyy yyyw 因为 所以014 1 x52 3 2 1 yyy 又因为 所以18102 3 2 1 xxx0 1 y 根据 有 wz 46101618 3 2 1 yyy 解上述三个联立方程得 3 1 0 3 2 1 yyy 三 求解下列指派问题 要求给出所有最优解要求给出所有最优解 6864 4346 5673 8665 min 44 4 1 4 1 ij ij ijij c xcz 解 1410 0003 1330 2100 2420 1013 2340 3110 6864 4346 5673 8665 3 0300 0004 0220 2101 最优方案为 0001 0100 1000 0010 1000 0100 0001 0010 或X 最优值为 18 z 四 某生产线单独生产一种产品的能力为 36000 件 年 对该产品的需求速度为 18000 件 年 该产品的存贮费为 1 8 元 件 年 准备在生产线上轮流生产多种产 品 更换生产品种时 需准备结束费 500 元 次 假设不允许缺货 求该产品每 次最佳的生产批量 解 依题意 有 P 36000 件 年 R 18000 件 年 次元 500 3 C 年件元 8 1 1 C 件 4472 1800036000 8 1 360001800050022 1 3 0 RP P C RC Q 五 求解下列运输问题 使总运费最低 运价 销地 产地 1 B 2 B 3 B 产量 1 A42210 2 A21410 3 A32310 销量8910 解 用最小元素法确定初始运输方案如下 运价 销地 产地 1 B 2 B 3 B B 产量 1 A42 7 2 3 010 7 2 A 1 2 9 14010 1 3 A 7 32 3 3010 4 销量8 7910 33 计算各行各列的位势得 运价 销地 产地 1 B 2 B 3 B Bi u 1 A42 7 2 3 00 2 A 1 2 9 1400 3 A 7 32 3 301 j v212 计算各空格的检验数得 运价 销地 产地 1 B 2 B 3 B Bi u 1 A 2 4 1 2 7 2 3 00 2 A 1 2 9 1 2 4 0 00 3 A 7 3 0 2 3 3 1 0 1 j v2120 重新调整方案并计算检验数得 运价 销地 产地 1 B 2 B 3 B Bi u 1 A 2 4 1 2 10 2 1 00 2 A 1 2 9 1 2 4 0 00 3 A 7 3 0 2 0 3 3 01 j v2120 所以 上表所示的运输方案即为最优运输方案 最小运价为 52 5 六 求下图所示网络流的最大流和最小截集 要求写出标号过程 解 一 标号过程 1 0 s v 1s vV 2 3 3s vv 31 vvV s 3 3 1 3 323632 vvvvvv 231 vvvV s 4 3 2 2 1 3 2126252421 vvvvvvvvvv 1231 vvvvV s 5 3 14 vv 41231 vvvvvV s 6 3 3 445 vvvv t 541231ts vvvvvvvV 二 调整过程 经逆向追踪得到增广链 调整量为 3 ts vvvvvv 4123 调整后的网络流如下图 V5 V1 Vs V2 V3V6 V4 Vt 5 5 8 5 6 6 3 3 5 1 2 1 4 4 2 0 9 8 5 4 5 1 9 6 6 6 10 6 3 1 6 再标号得 标号过程中断 0 s v 可知 如上图所示的网络流即为最大流 最小截集为 65411ttt vvvvvvVV 七 写出动态规划中设备更新问题的基本方程 并解释其中 tf j tI j 的含义 tQj tCj 答 1 1 1 1 max 1 2 0 0 1 0 jjj j jjjj n I tQ tft f tjn IQC tf ft L 第 j 年年初 设备的役龄为 t 从第 j 年初至第 n 年末采取最优策略所 tf j 创造的净收益 第 j 年年初 设备的役龄为 t 继续使用该设备一年所创造的收入 tI j 第 j 年年初 设备的役龄为 t 继续使用该设备一年所需要的运行维 tQj 护费 第 j 年年初 设备的役龄为 t 更换该设备所需的更新费用 tCj V5 V1 Vs V2 V3V6 V4 Vt 5 5 8 8 6 6 3 0 5 4 2 1 4 4 2 0 9 8 5 4 5 1 9 9 6 6 10 9 3 1 7 八 已知求解下列线性规划 0 2442 328 2024 2944 64max 21 21 1 21 21 21 xx xx x xx xx xxz 时的最优表格为 试求解下列整数规划 为整数 且 121 21 1 21 21 21 x0 2442 328 2024 2944 64max xx xx x xx xx xxz 解 恢复所在的方程 2 x 2 5 2 1 2 1 631 xxx 整分分解 整分分离得 6361 2 1 2 1 2 1 2xxxx 割平面方程为 0 2 1 2 1 2 1 63 xx 标准化得 2 1 2 1 2 1 763 xxx 添加到上一步的最优表格中得 460000 B C B X b 1 x 2 x 3 x 4 x 5 x 6 x i 41 x 5 2101 200 1 2 04 x 1 200 3 2101 05 x 1200 4014 62 x 19 401 1 4001 2 z 77 200 1 200 1 8 所以 整数规划的最优解为 最优值为 T X 5 2 38 z 九 某人外出旅游 可选择三种物品 A B C 装入包裹 但包裹重量有限制 总重量不超过 17 千克 物品的单件重量及其价值的关系如下表所示 试问如何 装这些物品 使整个包裹所携带物品的总价值最大 只要求写出每个阶段的 动态规划基本方程 物品单件重量 千克 单件价值 元 A B C 5 3 4 5 4 6 解 根据需要将问题划分为 3 个阶段 动态规划基本方程为 1 0 4 max 1 2 3 0 k k kkkkkk x u a fxc ufxa u k fx 且为整数 4600000 B C B X b 1 x 2 x 3 x 4 x 5 x 6 x 7 x 41 x 5 2101 200 1 20 04 x 1 200 3 21010 05 x 1200 40140 62 x 19 401 1 4001 20 07 x 1 200 1 2 00 1 21 z 77 200 1 200 10 41 x 5 210000 11 04 x 2000105 2 3 05 x 16000018 8 62 x 5