麻省理工学院试卷习题 2000年期中考试_Dynamic Programming and Stochastic Control（动态规划与随机控制）.pdf_大学文库

间题3(50分) 一个航运公司（在0时刻》有一个尺寸为整数K的空集装箱，在每个阶段青(k=0,1,一，水1)，一个顺客出现，并出价P:(正整数)预定尺寸为：（正整数。小于集装箱容积）的空间。假设在不同阶段★，出价(P·3:》是相互独立的，且概率分布已知：每一次，公司可以选择接受顾客《假如集装箱空间足够)或者抱绝顾客。目标是使期望收益最大化 ()给出此付完整的动南规划表达式（状志、运动方程等），以及动态规划算法。 ()证明最优策略具有如下性质：对于任意的固定状态和时间，如果接受出价《乃：·5：)：票么同样尺寸品，而出价更高可>P的〔戌，5)也要接受。 ()正明最优策略具有如下性质：对于任意的四定状态和时间。如果接受出价(P:·5:, 那么较小尺寸《<5：)而出价一样的(P·)也要接受。 (假设订单中的尺寸要求不能精确得知：当公司接受一个尺寸要求为5，的订单时，而实际尺寸卸变成5+鸟，其中鸟，是均值为0方差为。的不可测量的独立正态分布变量.（理论上，这能导致订单的尺寸为负值。但是假设石是相当小的，所以我们不必考饱这件可能性)。在阶段N,统计所有的订单，如果它们的总和大于K的话，公司需要第二个集装箱，而且代价为C。给出此问墨的动态规划方程（状态，动态方程、代价等），使期望收益最大，期望代价最小。 )附如得分题，翼如承有空汆时间，禁必述. 让我们国到)部分的状态信息完整问愿，并假设订单的尺寸大小总是1(3=1)：我们提出命题如下，如果当己接受订单的总大小为时再接受一个订单(P:·品)是最优的，那么当已接受订单的总大小小于时再接受一个同样的订单也是最优的。 (间性能泛函的哪一性质是以迁明此命题。 (可迁明（回中的性质。 ()通过一个例子说明，若没有5,1的假设，命题的最优策略性质不能成立

问题 3（50 分）一个航运公司（在 0 时刻）有一个尺寸为整数 K 的空集装箱。在每个阶段k（ k =0,1，…， N-1），一个顾客出现，并出价 pk （正整数）预定尺寸为 k s （正整数，小于集装箱容积）的空间。假设在不同阶段 k ，出价（ pk ， k s ）是相互独立的，且概率分布已知。每一次，公司可以选择接受顾客（假如集装箱空间足够）或者拒绝顾客。目标是使期望收益最大化。 (a) 给出此问题完整的动态规划表达式（状态、运动方程等），以及动态规划算法。 (b) 证明最优策略具有如下性质：对于任意的固定状态和时间，如果接受出价（ pk ， k s ），那么同样尺寸 k s 而出价更高( k p′ > pk )的（ k p′ ， k s ）也要接受。 (c) 证明最优策略具有如下性质：对于任意的固定状态和时间，如果接受出价（ pk ， k s ），那么较小尺寸（ k s′ < k s ）而出价一样的（ pk ， k s′ ）也要接受。 (d) 假设订单中的尺寸要求不能精确得知：当公司接受一个尺寸要求为 k s 的订单时，而实际尺寸却变成 k s +ωk ，其中ωk 是均值为 0 方差为 2 σ 的不可测量的独立正态分布变量。（理论上，这能导致订单的尺寸为负值。但是假设 2 σ 是相当小的，所以我们不必考虑这种可能性）。在阶段 N，统计所有的订单，如果它们的总和大于 K 的话，公司需要第二个集装箱，而且代价为C 。给出此问题的动态规划方程（状态、动态方程、代价等），使期望收益最大，期望代价最小。 (e) 附加得分题，假如你有空余时间，非必选。让我们回到(a)-(c)部分的状态信息完整问题，并假设订单的尺寸大小总是 1（ k s =1）。我们提出命题如下：如果当已接受订单的总大小为 a 时再接受一个订单（ pk ， k s ）是最优的，那么当已接受订单的总大小小于 a 时再接受一个同样的订单也是最优的。 (i) 性能泛函的哪一性质足以证明此命题。 (ii) 证明(i)中的性质。 (iii) 通过一个例子说明，若没有 k s =1 的假设，命题的最优策略性质不能成立

3. (a) 状态是( k x , pk , k s )，其中 k x 是以前接受订单的尺寸总和。如果接受( pk , k s )，令uk =1，否则，令uk =0。运动方程为 k k k k x = x + u s +1 ，( pk+1 , k+1 s )=ωk+1，其中ωk+1是随机订单。期望值与( pk+1 , k+1 s )的分布有关的。只有当 x + s ≤ K 时，上式中第二项才有意义。（解决此问题的简单方法是，当 x > K 时令 J (x, p,s) = −∞ ）。并且对于任何 x pk ，那么 1 1 () ( ) k k k k kk p J x J xs + + ′ ≥ −+ ，也应该接受订单( k p′ , k s )。 (c) 我们说明性能泛函是单调（非增）的：若 x k 。我们可以直观地看到：如果状态由 y 减小到 x ，那么我们（从状态 x 开始）可以做我们（从状态 y 开始）以前能做的任何事情，并且可以得到相同的收益。从数学上讲，这可以通过归纳法证明。单调性对于 N J 也成立，假设 J (x) k 对 x 而言是非增的，那么 ( ) 1 J x k+ 和 ( ) k k 1 k k p + J x + s + 也是 x 的非增函数。两个非增函数中的最小者也是非增的。取非增函数的加权平均的期望值，就可以看出 J (x) k 也是非增的。根据这种单调性，以及假设 k s′ < k s ，我们看到 1 1 ()() k kk k kk J xs J xs + + + ′ ≥ + 。如果接受( pk , k s )，那么 ( ) ( ) 1 1 p J x s J x k + k+ + k ≥ k+ ，这意味着 1 1 ( ) () kk k k p J xs J x + + + + ≥ ′ ，所以也接受( pk , k s′ )。 (d) 这里，我们的信息不完整，过去所接受的订单大小的总和也是未知的。然而，它的总大小为 ∑ − = + 1 0 ( ) k i k k k u s ω ，是正态随机变量，均值为 ∑ − = 1 0 k i k k u s ，方差为 ∑ − = 1 0 2 k i k u σ ，因此均值和方差是充分统计。我们可以用二维状态变量( mk , k v )，它的运动方程如下：每阶段的收益依然是 k k p u ，也有一个终端代价 ( , ) N N g m v ，它等于均值为 mN 方差为 N v 的正态随机变量的概率

麻省理工学院 试卷习题 2000年期中考试_Dynamic Programming and Stochastic Control（动态规划与随机控制）

麻省理工学院试卷习题 2000年期中考试_Dynamic Programming and Stochastic Control（动态规划与随机控制）