电力出版社运筹学答案第六章

第第 6 6 章训练题章训练题 一 基本技能训练一 基本技能训练 1 已知网络图各段路线所需费用如下图所示 试选择从到线的最小费用路线 AB 并计算其总的费用 图中线和线上的数字分别代表相应点的有关费用 AB 2 3 1 4 2 5 7 1 2 5 6 1 3 2 3 3 3 2 1 4 3 5 2 4 3 1 2 6 2 1 线 线AB 1 最小费用路线有两条 一条是从线最上方费用为 2 的点到线最上方费用为 3 的点AB 止 其总费用为 17 用动态规划方法求解 2 题至 13 题 2 3 3 32 2 1 maxxxxz 2 22 2 11 295maxxxxxz 3 2 1 0 6 321 ix xxx i 2 1 0 5 21 ix xx i 4 5 2 3 2 2 2 1 43minxxxz 4321 63105maxxxxxz 3 2 1 0 9 321 ix xxx i 4 3 2 1 0 111054 4321 ix xxxx i 且且且且 6 7 2 2 23max 2211 xxxxz 2 4 2 3 2 2 2 1 maxxxxxz 2 1 0 3 21 ix xx i 且且且且4 3 2 1 0 10 4321 ix xxxx i 且且且且 8 9 321 854maxxxxz 2 21 2 1 567maxxxxz 3 2 1 0 114 1363 10 31 321 321 ix xx xxx xxx i 且且且且 2 1 0 93 102 21 21 ix xx xx i 10 11 3 3 2 2 2 1 48maxxxxz 4232 2 1 maxxxxxaxz 且且且b ix bxxx i 3 2 1 0 102 321 且且且 且 a ix xxxx i 4 3 2 1 0 01 4321 2 最优解为 108 3 1 2 max321 zxxx 3 最优解为 8 131 4 9 2 5 max21 zxx 4 最优解为 751 29 147 3 574 1 82 1 max321 zxxx 5 最优解为 92 702 2 0 6 9 max21 zxx 6 最优解为 当时 4000 b 1000 10 0 0 3 max321 b z b xxx 当时 40000 b 2 max321 4 0 0bzxbxx 7 最优解为 当时 4 1 aazxxxx100 0 0 0 10 max4321 当时 有两个最优决策 4 1 4 1 a 25 0 5 5 0 max4321 zxxxx 或25 5 0 5 0 max4321 zxxxx 当时 也有两个最优决策 4 1 a a a zx a a x a a x a x 14 100 0 14 20 14 20 14 10 max4321 或a a z a a xx a a x a x 14 100 14 20 0 14 20 14 10 max4321 8 最优解为 55 0 0 0 11 max4321 zxxxx 9 最优解为 3 1 1 max21 zxx 10 有六个最优决策 26 2 3 3 2 min4321 zxxxx 26 2 3 2 3 min4321 zxxxx 26 2 2 3 3 min4321 zxxxx 26 3 3 2 2 min4321 zxxxx 26 3 2 3 2 min4321 zxxxx 26 3 2 2 3 min4321 zxxxx 11 最优解为 41 0 1 9 max321 zxxx 12 21 78maxxxz 为非负整数 21 21 21 1525 82 xx xx xx 12 最优解为 0 1 x7 2 x49 z 13 21 53maxxxz 0 1823 122 4 21 21 2 1 xx xx x x 13 2 1 x6 2 x36 z 14 如图所示 在处有一油库 为一港口 今需从铺设输油管道到处 拟AEAE 在之一 之一以及 21 D D之一各建一个中间站 各站之间的管道走 321 BBB 321 CCC 向如图所示 连线旁的数字表示两站间的管道长 现要求选择 3 个合适的中间站 使到A 的总输油管道长度最短 E 9 1 B 1 C 7 13 1 D 9 7 A 2 B 2 CE 9 12 11 16 15 2 D 6 3 B 3 C 始点站 第一站 第二站 第三站 终点站 1 2 3 4 AE 14 管道最短长度为 32 路线为 EDCBA 122 15 石油输送管道铺设最优方案的选择问题 考虑如下网络图 设 A 地为出发地 E 为目的地 B C D 分别为三个必须建立油泵加压站的地区 其中的 B1 B2 B3 C1 C2 C3 D1 D2 分别为可供选择的各站站位 下图中的线段表示管道 可铺设的位置 线段旁的数字表示了铺设这些管线所需的费用 问如何铺设管道才能使总 费用最小 15 最优方案为 A B2 C1 D1 E 或 A B3 C1 D1 E 或 A B3 C2 D2 E 总费用是 11 16 最短路线问题 从起点 A 到终点 G 分六个阶段 每个阶段各有若干条可选择的 道路 每条道路的长度如图所示 试确定从 A 点到 G 点的最短路线 10 15 5 8 14 12 7 6 11 AB2 B1 B3 C2 C1 C3 D1 D2 E 2 4 3 7 4 6 3 2 4 4 1 5 1 4 6 3 3 3 3 4 A B2 B1 C1 E2 E1 E3 F1 F2 G 5 3 3 2 1 2 2 6 8 3 3 3 3 5 5 2 6 6 3 4 D1 D2 D3 C2 C3 C4 5 5 8 4 1 3 6 8 6 7 16 A B1 C2 D1 E2 F2 G 总长度为 18 二 实践能力训练二 实践能力训练 1 某商店在未来四个月里 利用仓库经销某种商品 该仓库 的最大容量为 1000 件 每月中旬订购商品 并于下月初取到订 货 据估计 今后四个月这种商品的购价和售价如下表所示 假 定商店在 1 月初开始经销时仓库已存有该种商品 500 件 每月市 场需求不限 问应如何计划每个月订购与销售数量 使这四个月 的总利润最大 不考虑仓库的存储费用 1 各月份生产货物数量的最优决策为 月期前存货 k s售出量 k x购进量 k y 15005000 2001000 3100010001000 4100010000 利润最大值为1600010001050012 2 某工厂在未来 3 个月连续生产某种产品 每月初开始生产 月产量为 生产成x 本为 库存费为每月每单位 1 元 假如 3 个月的需求量预测为 2 x 且初始存货 第三个月的期末存货 问应如120 110 100 321 bbb0 0 s0 3 s 何安排生产使总成本最小 2 最佳生产量为 最低费用为 36321 元 2 1 109 2 1 110 110 321 xxx 3 生产存储问题 某工厂与购货单位签订的供货合同如右表所示 表中的数字为月 份交货量 该厂每月最大产量为 4 百件 仓库 的存货能力为 3 百件 已知每一百件货物的生 产费用为一万元 在生产月份 每批产品的生 产准备费为 4 千元 仓库保管费每一百件货物 每月一千元 假定 1 月初开始时及 6 月底交货 后仓库中都无存货 问该厂应该如何安排每月的生产与库存 才能既满足交货合同的要求 又使总费用最小 3 各月份生产货物数量的最优决策为 月份 123456 生产货物量 百件 404330 4 背包问题 某工厂生产三种产品 各种产品重量与利 润关系如右表所示 现将此三种产品运往市场销售 运输能 力总重量不超过 6 吨 问如何安排运输使总利润最大 4 运输 1 2 两种产品各一吨或运输第 3 类产品两吨 总利 润最大值为 260 元 5 设备更新问题 设某企业在今后 4 年内需使用一辆卡车 现有一辆已使用 2 年的 旧车 根据统计资料分析 预计卡车的年收入 年维修费 包括油料等费 一次更新重 置费及 4 年后残值如右表所示 k 1 2 3 4 试确定 4 年中的最优更新计划 以使总利润最 大 种类 重量 吨 件 利润 元 件 1 2 3 2 4 3 80 180 130 月份购价售价 1 2 3 4 10 9 11 15 12 9 13 17 月份 123456 交货量 百件 125321 i0123456 5 it ic iv ir k k k 1 16 15 18 2 14 12 21 2 11 8 25 3 8 3 29 4 5 0 34 4 2 0 6 某科学实验可以用 3 套不同的仪器 A B C 中任一套去完成 每做完一次试 验后 如果下次实验仍使用原仪器就必须对仪 器进行整修 中间要耽搁一段时间 如果下次 使用另一套仪器 则卸旧装新也要耽搁一段时 间 耽搁时间如右表所示 假定一次试验的 ij t 时间大于 因而某套仪器换下后隔一次再用时 不再另有耽搁 现在要做 4 次实验 首 ij t 次实验指定用仪器 A 其余各实验可用任一套仪器 问应如何安排使用仪器的顺序 才能 使总的耽搁时间最短 6 第一次试验使用 第二次使用 第三次使用 第四次使用 ABCB 最短时间 24 7 某公司准备经销某种货物 货物入库后才能销售 仓库容量为 900 件 公司每月月初订购货物 月底才到货 每月的销售量由公司自己确定 销售月初库存货物 现在一至四月各单位货物的购货成本及销售价格如 右表所示 又知一月初存货 200 件 问如何安排每月的货物购进量与销售 量 使四个月的利润最大 8 计算如右图所示的从到的最短路线及其长度 AE 1 用逆推解法 2 用标号法 8 最短路线 EDCBA 112 其路长为 8 9 某人在每年年底要决策 明年的投资与积累的资金分配 设开始时 他可利用的资金数 为 年利率为 在 年里若投资所得到的效益用来C 1 i i y 为常数bbyyg iii 表示 试用逆推解法和顺推解法来建立该问题在年里获得的最大效益的动态规划模型 n 9 逆推法 设状态变量表示第 年初拥有的资金数 则有逆推关系式 i si 月份 购货 成本 销售 价格 1 2 3 4 40 38 40 42 45 42 40 44 下次使用仪器 本次使用仪器 123 1 A 2 B 3 C 10 9 6 9 12 5 14 10 8 1 E D 3 D 2 D 1 C 1 C 2 AB2 B1 B3 1 3 2 3 5 2 1 1 2 3 4 3 3 3 4 3 4 5 5 1 2 1 max max 1 0 ni ysafygsf ygsf iiiii sy ii ni sy nn ii nn 顺推法 设状态变量表示第年初拥有的资金数 则有顺推关系式 i s1 i ni a sy fygsf ygsf ii iii sacy ii sacy ii 2 max max 1 0 11 0 11 11 10 已知某指派问题的有关数据 每人完成各项工作的 时间 如右表所示 试对此问题用动态归划方法求解 要求 1 列出动态规划的基本方程 2 用逆推法求解 10 1 任务的指派分 4 个阶段完成 用状态变量表示第 k s 阶段初未指派的工作的集合 决策变量为k kj u 0 1 且且 且且且且且且且且且且且jk ukj 状态转移方程为 逆推关系式为 1 1 kjkkk ujsDs且 1 2 3 max min 11 4 44 444 k sfasf asf kkkj sDu kk j sDu kkj j 2 时4 k 4 s 1234 j a4 19212317 j u41 j2 j3 j4 j 44 sf 19212317 时3 k 443 sfa j j u3 3 s 1 32 u1 32 u1 33 u1 34 u 33 sf 3 j u 1 2 26 2118 19 37 1 32 u 1 3 26 2316 19 35 1 33 u 1 4 26 1719 19 38 1 34 u 2 3 18 2316 21 37 1 33 u 2 4 18 1719 21 35 1 32 u 3 4 16 1719 23 33 1 33 u 时2 k 工作 人 1234 1 2 3 4 15 19 26 19 18 23 18 21 21 22 16 23 24 18 19 17 332 sfa j j u2 2 s 1 21 u1 22 u1 23 u1 24 u 22 sf 2 j u 1 2 3 19 3723 3522 37 56 1 21 u 1 2 4 19 3523 3818 37 54 1 21 u 1 3 4 19 3322 3818 35 52 1 21 u 2 3 4 23 3322 3518 37 55 1 24 u 时1 k 221 sfa j j u1 1 s 1 11 u1 12 u1 13 u1 14 u 11 sf 1j u 1 2 3 4 15 5518 5221 5424 56 70 或1 11 u 1 12 u 最优解为 或 1 42332411 uuuu1 44332112 uuuu 11 某公司打算在三个不同的地区设置 4 个销售点 根据市场预测部门估计 在不同的 地区设置不同数量的销售店 每月可得到的利 润如右表所示 试问在各个地区应如何设置销 售点 才能使每月获得的总利润最大 其值为 多少 11 最优决策为 在第一个地区设置 2 个销售点 在第二个地区设置 1 个销售点 在第三个地区设置 1 个销售点 每月可获总利润为 47 12 某工厂购进 100 台机器 准备生产两种产品 若生产产品 每台机器每 21 p p 1 p 年可收入 45 万元 损坏率为 65 若生产产品 每台机器每年收入为 35 万元 但损坏 2 p 率只有 35 估计三年后将有新的机器出现 旧的机器将全部淘汰 试问每年应如何安排 生产使在三年内收入最多 12 最优决策为 第一年将 100 台机器全部生产产品 第二年把余下的机器继续生产 2 p 产品 第三年把余下的所有机器全部生产产品 三年总收入为 7676 25 万元 2 p 1 p 1 yxr 2 yxr 3 yxr y x 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 3 6 4 5 6 7 4 6 7 8 6 7 8 9 0 2 4 6 1 4 6 7 4 6 8 9 6 8 10 11 0 3 5 8 2 5 7 9 4 7 9 11 6 9 11 13 销售店 地区 01234 1 2 3 0 0 0 16 12 10 25 17 14 30 21 16 32 22 17 13 设有两种资源 第 一种资源有单位 第二种x 资源有单位 计划分配给y 个部门 把第一种资源n i x 单位 第二种资源单位分配给部门 所得的利润记为 如设 i yi iii yxr 其利润列于下表中 试用动态规划方法如何分配这两种资源3 3 3 nyx yxri 到 个部门中去 使总的利润最大 i 13 最优决策为 最大利润为 3 0 0 2 0 0 332211 yxyxyx 3 3 16844 3 0 0 2 0 1 1321 frrr 14 某公司有三个工厂 它们 都可以考虑改造扩建 每个工厂可 有若干种方案可供选择 各种方案 的投资及所能取得的收益如右表所 示 单位 千万元 现公司有资 金 5 千万元 问应如何分配投资使 公司的总收益最大 14 有三个最优方案 3 2 2 或 2 3 2 或 2 4 1 总收益是 17 千万元 15 某公司在今后三年的每一年的年初将资金投入和两AB 项工程 年末的回收及其概率如右表所示 每年至多做一项投资 每次只能投入 1000 万元 求三年后所拥有的期望金额最大的投资 方案 15 最优方案是每年均投资于 三年后的最大利润为 440 万元 A 16 某商店在未来的 4 个月里 准备利用商店里一个仓库来 专门经销某种商品 该仓库最多能装这种商品 1000 单位 假定 商店每月只能卖出仓库现有的存货 当商店决定在某个月购货时 只有在该月的下个月初才能得到该货 据估计未来 4 个月这种商 品买卖价格如右表所示 假定商店在 1 月开始经销时 仓库存储 商品有 500 单位 试问 如何制订这 4 个月的订购与销售计划 使获得利润最大 不考虑仓库的存储费用 16 各月份生产货物数量的最优决策为 月份 123456 生产货物量 百件 404330 17 某鞋店出售橡胶雪靴 热销季节是从 10 月 1 日至次年 3 月 31 日 销售部门对这段时间 的需求量预测如右表所示 每月订货数目只有 10 20 30 40 50 几 种可能性 所需费用相应的为 48 86 118 138 160 元 每月末的存货不应超过 40 双 存储费用按月末存靴数计算 每月每双为 0 2 元 因为雪靴季节性强 且样式要变化 希望热销前后存货均为零 假定每月的需求率为常数 贮存费用按每月存货量计算 订购 一次的费用为 10 元 求使热销季节的总费用为最小的定货方案 17 热销季节每月最佳订货方案为 月份 101112123 订购数 双 4050040500 18 设某种机器可以在高 低两种不同负荷下生产 若机器在高负荷下生产 则产品 月份101112123 需求 双 402030403020 投资回收概率 A 00 4 20000 6 B 10000 9 20000 1 月份买价卖价 1 2 3 4 10 9 11 15 12 9 13 17 方 案 工厂 1工厂 2工厂 3 投资收益投资收益投资收益 1 2 3 4 0 1 2 0 5 6 0 2 3 4 0 8 9 12 0 1 0 3 年产量和投入生产的机器数量的关系为 机器的年折损率 若机器在axxa8 3 0 低负荷下生产 则产品年产量和投入生产的机器数量的关系为 机器的年折损bxxb5 率 设开始有完好的机器 1000 台 要求制定一个四年计划 每年年初分配完好机1 0 器在不同负荷下工作 使四年产品总产量达到最高 18 分配方案为 第一年第二年第三年第四年 高负荷0900630441 低负荷1000000 总产量为 20768 19 某工厂在一年进行了三种新产品试制 由于资金不足 估计在年内这三CBA 种新产品研制不成功的概率分别为 因而都研制不成功的概率为80 0 60 0 40 0 192 0 80 0 60 0 40 0 为了促进新产品的研制 决定增拨 2 万元的研制费 并要资金集中使用 以万元为单位进 行分配 其增拨研制费与新产品不成功的概率如下表所示 不成功概率 新产品 研制费 SABC 00 400 600 80 10 200 400 50 20 150 200 30 试问如何分配费用 使这三种新产品都研制不成功的概率为最小 19 分为三个阶段 状态变量表示第种产品至第种产品的研制费用 表示第种 k skn k xk 产品研制费用 表示第种产品补加研制费后的不成功概率 模型为 kk xpk k x 3 1 min i ii xpz 且为整数0 2 321 i xxxx 1 2 3 min 1 1 0 44 k xsfxpsf sf kkkkk sx kk kk 第三阶段 设万元 全部分配给新产品 则不成功概率为 3 s 2 1 0 3 sC 6 04 0 min 3333 33 xpsf sx 其计算如下 33 xp 3 x 3 s012 33 sf 3 x 00 80 80 10 50 51 20 30 32 第二阶段 设万元 全部分配给新产品 则不成功概率为 2 s 2 1 0 2 sCB min 22222 0 22 22 xsfxpsf sx 其计算如下 22222 xsfxp 2 x 2 s012 22 sf 2 x 08 06 0 0 480 15 06 0 8 04 0 0 300 23 06 0 5 04 0 8 02 0 0 162 第一阶段 设万元 全部分配给新产品 则不成功概率为2 1 sCBA 2 min 2 1111 20 1 1 xfxpf x 其计算如下 1 x 1 s 012 2 1 f 1 x 2016 0 4 0 3 02 0 48 0 15 0 0 061 故06 0 2 1 0 1 1 3 2 1 fxxx 即产品分配 1 万元 产品不分配 产品分配 1 万元 这三种产品都研究不成ABC 功的概率最小为 06 0 5 06 02 0 20 资本安排问题 某公司有三个工厂 它们都可以考虑扩建 每个工厂都有若干种 方案可供选择 各种方案的投资及所取得的收益如下表所列 单位 千万元 总投资为 5 千万元 问如何分配投资使公司收益最大 i 1i 2i 3mi 方案 C 投资 R 收益 CRCR 1000000 2152813 32639 4 412 20 最优方案为 2 4 1 或 3 2 2 或 2 3 2 总收益都是 17 万元 21 某科研项目由三个小组用不同手段分别研究 他们失败的概率各为 0 40 0 60 0 80 为了减少三个小组都失败的可能性 现决定给三个小组中增派两名高级 科学家 到各小组后 各小组科研项目失败概率如下表 小 组 高级科学家 123 00 400 600 80 10 200 400 50 20 150 200 30 问如何分派科学家才能使三个小组都失败概率 即科研项目最终失败的概率 最小 21 1 3 小组各派一名科学家 科研项目最终失败的概率为 0 060 22 考虑一种由四个部件组成的系统 各部件都运行时系统才能运行