动态规划习题答案

2 某公司有资金 4 百万元向 A B 和 C3 个项目追加投资 各个项目可 以有不同的投资额 百万元计 相应的效益如表所示 问怎样分配 资金 使总效益值最大 表 8 47 投 资 额Wk Xk 项目 k 01234 1 A 41486066 2 B 40425060 3 C 64687884 解 设 S1 A B C 项目的总投资额 S2 B C 项目的总投资额 S3 C 项目的投资额 Xk k 项目的投资额 X1 A 项目的投资额 X2 B 项目的投资额 X3 C 项目的投资 额 Wk Sk Xk 对 K 项目投资 Xk后的收益 Wk Sk Xk Wk Xk Tk Sk Xk Sk 1 Sk Xk fk Sk 当 K 至第 3 项目允许的投资额为 Sk时所能获得的最大收益 为获得最大利润 必须将 4 百万全部投资 假设有 4 阶段存在 有 S4 0 建立递归方程 f4 Sk 0 fk Sk max Wk Xk fk 1 Sk 1 k 3 2 1 Xk Dk Sk 第一步 K 3 f4 S4 0 f3 S3 max W3 X3 f4 S4 X3 D3 S3 S4 S3 X3 S3f3 S3 X3 1641 2682 3783 4844 第二步 K 2 f2 S2 max W2 X2 f3 S3 X2 D2 S2 S3 S2 X2 W2 X2 f3 S2 X2 S2X2 0X2 1X2 2X2 3f2 S2 X2 140 64 1040 240 6842 64 1080 340 7842 6850 64 1180 440 8442 7850 6860 641240 3 第三步 K 1 f1 S1 max W1 X1 f2 S2 X1 D1 S1 S2 S1 X1 W1 X1 f2 S1 X1 S1X1 0X1 1X1 2X1 3f1 S1 X1 4 41 118 48 10860 1041643 S1 4 S2 1 S3 1 X1 3 X2 0 X3 1 A 投资 3 百万 B 不投资 C 投资 1 百万 总收益 164 百万元 3 最优分配问题 有一个仪表公司打算向它的 3 个营业区设 立 6 家销售店 每个营业区至少设一家 所获利润如表 问设立的 6 家销售店数应如何分配 可使总利润最大 营 业 区 Ak 利 润 wk x A1A2A3 销售 店数 x 1 2 3 4 200 280 330 340 210 220 225 230 180 230 260 280 解 sk 对 k 3 营业区允许设立的销售店数 xk 对 k 营业区设立的销售店数 wk sk xk 对 k 营业区设立 xk销售店后的利润 wk sk xk wk xk Tk sk xk sk 1 sk xk fk sk 当第 k 至第 3 个营业区允许设立的销售店数为 sk时所能获得的最大利润 递归方程 f4 s4 0 fk sk max wk xk fk 1 sk 1 k 3 2 1 xk Dk sk k 3 时 有方程 f4 s4 0 f3 s3 max w3 x3 f4 s4 x3 D3 s3 s3 s2 x2 s3f3 s3 x3 11801 22302 32603 42804 k 2 有方程 f2 s2 max w2 x2 f3 s3 x2 D2 s2 s3 s2 x2 s2w2 x2 f3 s2 x2 f2 s2 x2 x2 1x2 2x2 3x2 4 2210 180 3901 3210 230220 180 4401 4210 260220 230225 180 4701 5210 280220 260225 230230 1804901 k 1 有方程 f1 s1 max w1 x1 f2 s2 x1 D1 s1 s2 s1 x1 w1 x1 f2 s1 x1 s1 x1 1x1 2x1 3x1 4 f1 s1 x1 6200 490280 470330 440340 3907703 s1 6 s2 3 s3 2 x1 3 x2 1 x3 2 分别 A1 A2 A3 营业区设立 3 家 1 家 2 家销售店 最大利润 为 770 4 用动态规划方法求解下列模型 maxf 10X1 4X2 5X3 s t 3X1 5 X2 4 X3 15 0 X1 2 0 X2 2 X3 0 Xj为整数 j 1 2 3 解 收费 C1 10 C2 4 C3 5 X1为货物 1 的装载件数 X2为货物 2 的装载件数 X3为货物 3 的装载件数 分 3 阶段 S1为货物 1 2 3 允许的装载重量 3X1 5 X2 4 X3的允许值 S2为货物 2 3 允许装载的重量 5 X2 4 X3的允许值 S3 为货物 3 允许装载的重量 4 X3的允许值 第一步 K 3 f4 S4 0 f3 S3 max 5X3 f4 S4 X3 D3 S3 S4 S3 4 X3 S30 34 78 1112 15 D3 S3 0 0 1 0 1 2 0 1 2 3 S3X3 0X3 1X3 2X3 3f3 S3 X3 0 30 0 00 4 70 05 0 51 8 110 05 010 0 102 12 150 05 010 015 0153 第二步 K 2 f2 S2 max 4X2 f3 S3 X2 D2 S2 S3 S2 5 X2 划分点 04812 004812 S20 45 910 15 D2 S2 0 0 1 0 1 2 5591317 1010141822 4X2 f3 S2 5 X2 S2X2 0X2 1X2 2f2 S2 X2 0 30 0 00 40 5 50 5 70 54 0 50 80 104 0 100 90 104 5 100 10 110 104 58 0100 120 154 58 0150 130 154 108 0150 14 150 154 108 5150 第三步 K 1 f1 S3 max 10X1 f2 S2 X1 D1 S1 S2 S1 3 X1 10X1 f2 S1 3 X1 S1X1 0X1 1X1 2f1 S1 X1 150 1510 1520 10302 顺序追踪 最优策略为 S1 15 S2 9 S3 9 xk Dk sk x5 D5 s5 X1 2 X2 0 X3 2 最优装载方案为 货物 1 装 2 件 货物 2 不装 货物 3 装 2 件 装载收费为 30 元 5 用动态规划方法解下列 0 1 背包问题 Max f 12x1 12x2 9x3 16x4 30 x5 s t 3x1 4x2 3x3 4x4 6x5 12 xj 0 1 j 1 5 解 本问题分为 5 个阶段 令 sk akxk a4x4的允许值 xk 第 k 阶段 xk取值 xk 0 1 wk sk xk xk产生的价值 wk sk xk c kxk Tk sk xk sk 1 sk akxk fk sk 在 akxk a4x4 sk的条件下 c kxk c 4x4 能取得的最大值 递归方程为 k 5 f5 s5 max 30 x5 s5 30 x5f5 s5 x5 f6 s6 0 fk sk max ckxk fk 1 sk 1 k 5 4 3 2 1 x4 D4 s4 f4 s4 max 16x4 f5 s5 x5 0 x5 1 0 50 00 6 12030301 k 4 16x4 f5 s4 4x4 s4 x4 0 x4 1 f4 s4 x4 0 30 0 00 4 50 016 0161 6 90 3016 0300 10 120 30 16 30461 s 5 s4 4x4 x3 D3 s3 f3 s3 max 9x3 f4 s4 k 3 9x3 f4 s3 3x3 s3 x3 0 x3 1 f3 s3 x3 0 20 0 00 30 0 9 091 4 50 16 9 0160 6 0 30 9 0300 7 8 0 309 16300 9 0 30 9 30391 10 12 0 46 9 30460 s 4 s3 3x3 x2 D2 s2 f2 s2 max 12x2 f3 s3 x1 D1 s1 f1 s1 max 12x1 f2 s2 k 2 k 1 12x2 f3 s2 4x2 s2 x2 0 x2 1 f2 s2 x2 0 2 0 0 00 30 9 90 4 5 0 16 12 0160 6 0 30 12 0300 7 0 30 12 9300 8 0 30 12 16300 9 0 39 12 16390 10 0 46 12 30460 11 1 2 0 46 12 30460 s3 s2 4x2 s2 s1 3x1 s1 12 s1 12 s2 9 s3 9 s4 6 s5 6 x1 1 x2 0 x3 1 x4 0 x5 1 11 今设计一种由 4 个元件串联而成的部件 为提高部件的可靠性 每一元件可以由 1 个 2 个或 3 个并联的单位元件组成 关于元件 K K 1 2 3 4 配备 j 个并联单位元件 j 1 2 3 后的可靠 性 Rkj和成本 Ckj由表给出 假设该部件的总成本允许为 15 个单位 试问如何确定各元件的单位元件配备数目 使系统的可靠性最高 K 1K 2K 3K 4j R1jC1jR2jC2jR3jC3jR4jC4j 10 740 620 930 83 20 7550 840 825 30 857 12x1 f2 s1 3x1 s1 x1 0 x1 1 f1 s1 x1 120 46 12 39511 解 逆序解法 解 逆序解法 Sk 仪表上配备 k 4 元件时允许使用的费用 Xk K 元件所选用的单位元件 Wk Sk Xk K 元件采用单位元件时的可靠性 有 Wk Sk Xk Rkxk Tk Sk Xk Sk 1 Sk Ckxk fk Sk 在费用限额为 Sk的条件下 k 3 元件串联时相应 部分可获得的最大可靠性 递归方程 f4 S5 1 fk Sk max Wk Sk Xk fk 1 Sk 1 K 4 3 2 1 第一步 对 K 4 R4x4S4 X4 1X4 2 F4 S1 X4 30 7 0 81 40 8 0 81 50 80 820 822 60 70 820 822 第二步 R3x3 f1 S3 C3x3 S3 X3 1 f2 S2 X3 6 0 9 0 8 0 721 7 0 9 0 8 0 721 8 0 9 0 82 0 7381 9 0 9 0 82 0 7381 第三步 对 K 2 R2x2 f3 S2 C2x2 S2 X2 1X2 2 f2 S2 X2 8 0 6 0 72 0 4321 9 0 6 0 72 0 4321 10 0 6 0 7380 8 0 72 0 5762 11 0 6 0 7380 8 0 72 0 5762 第四步 对 K 4 f4 S4 max R4x4 f3 S3 S3 S4 C4x4 S4 15 R1x1 f2 S41 C1x1 S1 X1 1 X1 2 X1 3 f1 S4 X 1 15 0 7 0 576 0 75 0 576 0 85 0 432 0 4322 S1 15 S3 10 S2 6 S1 3 X1 2 X2 2 X3 1 X4 1 元件 1 为 2 个 元件 2 为 2 个 元件 3 为 1 个 元件 4 为 1 个 可 靠性为 0 432 顺序解法 Sk 仪表上配备 1 K 元件时允许使用的费用 Xk K 元件所选用的单位元件 Wk Sk Xk K 元件采用单位元件时的可靠性 有 Wk Sk Xk Rkxk Tk Sk Xk Sk 1 Sk Ckxk fk Sk 在费用限额为 Sk的条件下 1 K 元件串联时相 应部分可获得的最大可靠性 递归方程 f0 S0 1 fk Sk max Wk Sk Xk fk 1 Sk 1 K 1 2 3 4 第一步 对 K 1 f1 S1 max R1x1 4 S1 7 S1 4 5 6 7 S14567 D1 S1 1 1 2 1 2 1 2 3 R1x1S1 X1 1X1 2X1 3 f1 S1 X1 40 7 0 71 50 70 75 0 752 60 70 75 0 752 70 70 750 80 83 第二步 对 K 2 f2 S2 max R2x2 f1 S1 S1 S2 C2x2 6 S2 9 S2 6 7 8 9 S26789 D2 S2 1 1 1 2 1 2 R2x2 f1 S2 C2x2 S2 X2 1X2 2 f2 S2 X2 6 0 6 0 7 0 421 7 0 6 0 75 0 451 8 0 6 0 750 8 0 7 0 562 9 0 6 0 80 8 0 75 0 62 第三步 对 K 3 f3 S3 max R3x3 f2 S2 S2 S3 C3x3 9 S2 12 S2 9 10 11 12 S39101112 D3 S3 1 1 1 1 R3x3 f2 S3 C3x3 S3 X3 1 f3 S3 X