第13章：血液管理问题

本章概览

血液管理问题是一个多维资源分配问题,因为我们必须管理八种不同的血型,同时还要跟踪血液的存储时长(除非是冷冻血液)。这是我们第一次需要借助线性规划这样的工具来在每个时间点做出决策。

我们首先说明一种短视策略,该策略需要求解一个简单的线性规划,而这种做法忽略了当前决策对未来影响的理解。对于血液管理而言,这种情况可能出现在$O-$型血液的管理中——该血型被称为万能供血者,可用于任何患者。保留一定量的$O-$型血液储备是有帮助的,以防其他血型出现短缺。

随后我们演示了如何使用近似动态规划来平衡当前收益与未来收益。为了将ADP应用于一个多维问题,我们在设计未来血液库存集合的值近似时,利用了该问题本身的结构特点。当我们能够利用问题的结构时,这种思路是可行的。

叙述

血液库存管理问题是资源分配问题的一个尤为优雅的示例。我们先假设自己在管理单个医院的库存,每周都需要决定用哪些血液库存来满足下周需要服务的需求。

我们需要先介绍一些关于血液的背景知识。就血液库存管理而言,我们主要关心血型和血液存储时长。尽管两个人的血液之间存在着极为广泛的差异,但出于大多数目的,医生们主要关注八种主要血型:$A+$(“A型阳性”)、$A-$(“A型阴性”)、$B+$、$B-$、$AB+$、$AB-$、$O+$和$O-$。虽然不同血型之间能否相互替代取决于具体手术的性质,但在大多数情况下,血液可以按照表13.1进行替代。

血液的另一个重要特征是其存储时长。血液的存储期限为六周,超过这一期限就必须废弃。医院需要预先判断血液能否在达到这一期限之前被使用,因为血液可以转运到血液中心,由其监测该地区内不同医院的库存情况。如果医院能够尽早识别出自己不会用到的血液,这将有助于将这些血液转运到血液短缺的地方。

问题构建框架

针对三个构建问题的答案如下:

• 度量指标: 最大化奖励减去惩罚的期望总和,惩罚产生于用一种血型的血液满足另一种血型需求的情形。
• 决策: 决定分配多少某一血型的血液以满足对另一血型血液的需求,以及每种血型应保留多少库存。
• 不确定性: 每种血型未来的需求,以及每种血型的献血量。

基本模型

状态变量

我们可以将血液问题建模为一个异质资源分配问题。我们先从一个相当基础的模型开始,该模型几乎可以在不改变符号的情况下轻松扩展。我们首先用以下方式描述一个存储血液单位的属性

并令$\Bcal$为所有血液属性类型的集合。我们将血液存储时长限定在$0 \leq b_2 \leq 6$范围内。存储时长为$b_2 = 6$(意味着血液已存放满六周)的血液不再可用。我们假设决策时期以一周为增量。血液库存用$R_{tb}$表示,即在时间$t$可供分配或保留的$b$型血液的单位数,其中$R_t = (R_{tb})_{b\in\Bcal}$。

血液需求的属性由下式给出

并令$\Acal$为血液需求的所有属性类型的集合。属性$a_3$刻画了这样一个事实:在某些手术中,医生不允许进行任何替代。一个例子是分娩,因为婴儿可能无法承受不同的血型,即使该血型是允许的替代品。在我们的基本模型中,我们不允许某一周未满足的需求被延迟到之后的周次。

然后我们用$D_{ta}$定义血液需求,即在时间$t$具有属性$a$的患者所需的血液单位数,其中$D_t = (D_{ta})_{a\in\Acal}$。

状态变量由下式给出

决策变量

我们通过决策$d$作用于血液资源,这是一种决策类型,包括将血液提供给具有属性$a\in\Acal$的患者,或者不采取行动而保留血液,我们用$d^\phi$表示这种情形;而$\Dcal$则是所有可能决策的集合,$\Dcal = \Acal \cup d^\phi$。

然后我们令$x_{tbd}$为在时间$t$以类型为$d$的决策处理的、属性为$b$的血液单位数,其中$x_t = (x_{tbd})_{b\in\Bcal,d\in\Dcal}$。

可行域$\Xcal_t$由以下约束定义:

外源信息

在我们做出决策之后到达的信息由献血量给出,我们用$\Rhat_{t+1,b}$表示,即在$t$到$t+1$之间新捐献的$b$型血液单位数,其中$\Rhat_{t+1} = (\Rhat_{t+1,b})_{b\in\Bcal}$。

新的血液需求用$\Dhat_{t+1,a}$建模,即在$t$到$t+1$之间产生的具有属性$a$的需求单位数,其中$\Dhat_{t+1} = (\Dhat_{t+1,a})_{a\in\Acal}$。

我们的外源信息变量为

转移函数

被保留的血液只是老化一周,但我们将存储时长上限设为六周。被用于满足需求的血液可以建模为被转移到一个血型汇点,或许可用$b_{t,1} = \phi$(空血型)表示。血液属性转移函数$b^M(b_t,d_t)$由下式给出

为表示转移函数,定义以下内容会很有用

并令$\Delta$为第$b’$行第$(b,d)$列元素为$\delta_{b’}(b,d)$的矩阵。

我们注意到该属性转移函数是确定性的。若血液检验发现存储时长不满六周的血液被判定已过期,则可能出现随机因素。资源转移函数现在可以写为

以矩阵形式,这些可写为

需求$D_{t+1}$只是从新需求$\Dhat_{t+1}$中观测得到,因此我们将其写为

图13.1展示了第$t$周发生的转移情况。我们要么必须决定使用哪种血型来满足需求(图13.1a),要么将血液保留到下一周。如果我们使用血液来满足需求,则假设该血液从系统中消失。如果我们将血液保留到下一周,它就转变为存储时长增加一周的血液。存储时长满六周的血液不能用于满足任何需求,因此我们可以将六周龄的血液批次视为不可用血液的汇点(这部分血液的价值为零)。请注意,假设捐献的血液以存储时长为0到达。

图13.1所表示的模型对资源分配问题非常有用。我们已经成功地运用该模型来优化制成品在配送中心之间的分配,并优化货运运输中卡车、货运车厢和机车的分配。在估计值函数近似时需要格外小心,但一旦这些近似被估计出来,其使用便会产生一系列如图所示的非常小的网络问题。

目标函数

用一种血型分配给另一种血型的需求,并没有真正的”成本”(我们没有考虑诸如花钱鼓励额外献血,或将库存从一家医院运送到另一家医院等步骤)。相反,我们使用贡献函数来刻画医生的偏好。我们希望捕捉这样一种自然偏好:一般来说不进行替代更好,并且满足紧急需求比满足择期需求更为重要。

例如,我们可以使用表13.2中描述的贡献值。因此,如果我们使用$O-$型血液来满足一名择期患者对$A+$型血液的需求,我们将获得-＄10的贡献(由于是负值,这是一种惩罚)以对应血液替代,+＄5用于使用$O-$型血液(这是医院乐于鼓励的),以及+＄20的贡献用于服务择期需求,总贡献为+＄15。

(在时间$t$的)总贡献最终由下式给出

如前所述,令$X^\pi_t(S_t)$为一种策略(某种决策规则),它根据$S_t$确定$x_t\in\Xcal_t$。我们希望通过求解以下问题找到最佳策略

其中$S_{t+1} = S^M(S_t,X^\pi(S_t),W_{t+1})$。

不确定性建模

该问题中的不确定性来源是献血量以及新的手术需求(需要用血)的到来。我们在对这种不确定性进行建模时需要考虑的一些问题包括:

• 献血单位数量存在随机性,献血的血型也同样存在随机性。
• 献血既存在按星期分布的模式,也存在季节性模式,同时还会对呼吁产生响应,而这自然也是一种决策。
• 由于天气或暴力事件,新手术的到来可能呈现爆发式增长。
• 献血人群的类型与需要手术的人群类型之间存在持续的错配,这体现为血型分布的差异。
• 一个重要问题是管理血型替代。人们高度关注$O-$型血液能够供任何人使用这一能力,但对于所有血型而言,都存在不同类型的替代方案。

策略设计

我们将从一个基本的短视策略开始,然后过渡到一个依赖于近似未来血液库存价值的策略。

短视策略

解决这个问题最直接的方法是简单的短视策略,即在每个时间点最大化贡献,而不考虑我们的决策对未来的影响。通过调整单期贡献,我们可以获得一族短视策略。

例如,我们对使用$O-$血液给予＄5的奖励(见表13.2),实际上就是一种短视策略。我们鼓励使用$O-$血液,因为它通常比其他血型更容易获得。通过改变这个奖励,我们得到不同类型的短视策略,可以用集合$\Pi^M$来表示,其中对于$\pi\in\Pi^M$,我们的决策函数由下式给出

$\eqref{eq:bloodmyopic}$中的优化问题是一个简单的线性规划。在方程$\eqref{eq:bloodobjective}$给出的优化问题中搜索策略,意味着在使用$O-$血液的奖励的不同取值上进行搜索。

VFA策略

作为一个传统的动态规划,方程$\eqref{eq:bloodobjective}$中提出的优化问题相当棘手。状态变量$S_t$具有$\vert \Acal\vert + \vert \Bcal\vert = 8 \times 6 + 8 \times 2 \times 2 = 80$个维度。随机变量$\Rhat$和$\Dhat$共有80个维度。决策向量$x_t$具有$27 + 8 = 35$个维度。

自然而然地,我们会想到使用值函数近似来确定分配向量$x_t$,即使用

其中$R^x_t = R^M(R_t,x_t)$由方程$\eqref{eq:bloodresourcetransition1}$给出,$\Xcal^n_t$由约束$\eqref{eq:blood1}$–$\eqref{eq:blood3}$定义。关键约束是$\eqref{eq:blood1}$,它限制了每种血型供应的可用性。

我们面临的第一个(也是最重要的)挑战是为$\Vbar^{x,n-1}_t(R^x_t)$确定一个合适的近似策略。一个简单而有效的近似方法是使用可分离的分段线性近似,也就是说

其中$\Vbar^x_{tb}(R^x_{tb})$是关于决策后库存$R^x_{tb}$的标量分段线性函数,针对每种血型$b$。

容易证明值函数是凹的(同时也是分段线性的),因此每个$\Vbar^x_{tb}(R^x_{tb})$也应该是凹的。不失一般性,我们可以假设$\Vbar^x_{tb}(R^x_{tb}) = 0$对于$R^x_{tb} = 0$成立,这意味着该函数完全由其斜率集合来刻画。我们可以将该函数写成

其中$\lfloor R \rfloor$是小于或等于$R$的最大整数。可以看到,该函数由斜率集合$(\vbar^{n-1}_{tb}(r))$确定,其中$r = 0, 1, \ldots, R^{max}$,$R^{max}$是特定类型资源数量的上界。

我们估计$\Vbar_t(R_t)$中斜率的方法是为时间$t$的问题构建目标函数

当我们求解这个线性规划时,我们得到了关于$a$类型血液额外一单位的边际价值的估计,由$R^n_{ta}$给出。我们将这个值称为$\vhat^n_{ta}$,它可以直接从任何线性规划软件包中获得(而且我们可以同时得到每种血型$a$的这个值)。

或者,我们可以通过构造一个扰动的资源向量$R^{n+}_{ta} = R^n_{ta} +1$来更精确地计算边际价值。设$\Xcal^{n+}_t(a)$为可行域(由方程$\eqref{eq:blood1}$–$\eqref{eq:blood3}$构成),其中对于单个属性$a$,我们使用$R^{n+}_{ta}$代替$R^n_{ta}$;设$\Vtilde^+_{ta}(S_t)$与$\Vtilde_t(S_t)$相同,只是可行域$\Xcal^{n+}_{ta}$使用扰动后的资源$R^{n+}_{ta}$代替$R^n_{ta}$。然后我们可以使用下式求出边际价值$\vhat^n_{ta}$

请注意,我们必须对每个$a$分别计算$\Vtilde^+_{ta}(S_t)$(而使用对偶变量时,我们可以一次性得到整个边际价值集合)。

然后我们使用$\vhat^n_{ta}$来更新先前的决策后值函数近似$\vbar^{x,n}_{t-1,a}$,具体方法是

我们可以证明,斜率$\vbar^{x,n}_{ta}(R^{x,n}_{ta})$随着$R^{x,n}_{ta}$的增加而减小,因此保持这一性质很有帮助。我们可以使用诸如CAVE算法或Leveling算法等方法来实现这一点(参见《Reinforcement Learning and Stochastic Optimization》第18.3节)。

假设我们能够估计这个函数,那么我们必须求解的优化问题(方程$\eqref{eq:adpblood}$)就是图13.2所示的一个相当适中的线性规划。与图13.1一样,我们必须同时考虑将不同类型的血液分配给不同类型的需求,以及是否持有血液的决策。

为了简化图示,我们将不同需求类型的网络合并为一个具有需求$\Dhat_t$的单一聚合方框。这个网络实际上看起来就像图13.1a中的网络一样。持有血液的决策必须考虑一种血型(包括其存放时长)在未来的价值,我们使用可分离的分段线性值函数来近似这一价值。

在这里,我们使用了一种标准的建模技巧,将可分离的分段线性值函数近似转化为一系列从代表$R^x_t$中每个元素的节点到一个超汇点的并行链路。分段线性函数不仅易于求解(我们只需要能够访问线性规划求解器),而且易于估计。此外,对于许多问题类别(但并非全部),已经发现它们能够以高质量的解产生非常快的收敛速度。

有了这个决策函数,我们将使用一种称为近似值迭代的方法,通过时间段$t=0, \ldots, T$向前迭代地进行模拟。设$n = 1, \ldots, N$为迭代计数器,我们沿着外源信息$W^n_t,~t=0, \ldots, T$的一条样本路径前进(这些信息可能取自历史数据,或从某个分布中抽样得到)。在时间$t$、迭代$n$时,当我们处于状态$S^n_t$时,我们使用方程$\eqref{eq:adpblood}$做出决策$x^n_t$。然后我们观测到$W^n_{t+1}$,并使用我们的转移函数(方程$\eqref{eq:bloodresourcetransition1}$–$\eqref{eq:bloodresourcetransition2}$)完成从$R^n_t$到$R^n_{t+1}$的转移。当处于状态$S^n_t = (R^n_t, \Dhat^n_t)$时,我们使用方程$\eqref{eq:adpblood}$中的VFA策略来计算$x^n_t$,然后我们计算$\vhat^n_t$以更新斜率$\vbar^{x,n}_{t-1}$。接着我们观测到$W^n_{t+1}$(其中包含$\Dhat^n_{t+1}$),从而转移到状态$S^n_{t+1}$。

对于大多数实际运营应用,这个问题会在一个有限的时域内求解(比如说10周),从而给出我们现在应该采取的行动建议。我们可以使用值函数近似$\Vbar^x_t(R^x_t)$多次模拟该策略,从而产生一种关于未来库存的概率预测形式。

扩展

这是一个丰富而复杂的资源分配问题,可以通过多种方式进行扩展。下面是几个例子。

1) 我们假设在时间$t$未得到满足的任何需求都会丢失。设想我们有必须满足的紧急手术,以及可以延迟到之后时间段的择期手术。为这个新问题写出状态变量。

2) 假设择期手术可以延迟。考虑使用一个关于血液库存的分段线性且可分离的值函数近似(这就是上面提出的VFA),同时对(按血型分类的)待处理需求量也使用分段线性且可分离的VFA。我们使用血液库存的对偶变量来更新血液供应的VFA。我们该如何更新待处理需求的VFA呢?

3) 考虑冷冻血液的存在,以及冷冻血液的决策,其中未被使用的冷冻血液必须丢弃。这意味着我们必须认识到,手术所需的血液量在手术前是未知的,而解冻血液的决策必须在此之前做出。

4) 医院可能需要社区血库每周输送血液,以弥补系统性短缺。设想每周有固定数量(例如100单位)的血液到达,但每种类型和存放时长(血液可能已经在库存中存放了几周)的血液数量可能是随机的。

5) 我们提出的模型只关注单个医院的血液库存。我们可以通过简单地添加一个位置属性,并提供从一个位置向另一个位置移动血液(需要付出代价)的决策,来处理多个医院和配送中心的情况。

这个模型也可以应用于任何多产品库存问题,只要存在不同类型的产品和不同类型的需求,并且我们有能力选择将哪种类型的产品分配给哪种类型的需求。我们还假设产品是不可重复使用的;一旦产品被分配给某个需求,它就从系统中消失了。

我们学到了什么?

• 我们介绍了一个具有极大状态空间的多维资源分配问题,但该问题具有凹性结构,我们可以在值函数的近似中加以利用。
• 我们展示了如何为一个多属性资源分配问题建模,这使得引入额外的属性变得相当容易。
• 我们说明了一个基本的短视策略,其中当前所做决策的下游影响被忽略。
• 然后我们描述了一个VFA策略,在其中我们利用问题本身固有的凹性,提出了一种基于可分离分段线性值函数近似的近似方法。
• 我们的VFA策略必须以滚动方式实施,因此我们的策略实际上是一种随机DLA,即使用VFA策略作为前瞻策略。这与我们在第6章中使用动态规划求解确定性最短路径问题的做法相呼应,该确定性问题是我们随机、动态最短路径问题的一种近似。

习题

复习题

1. 状态变量$S_t$的维度是多少?
2. 决策向量$x_t$的维度是多少?
3. 不确定性的来源是什么?
4. 描述目标函数中成本的性质。这些成本来自哪里?
5. 纯短视策略的局限性是什么?你希望从一个更好的策略中看到什么样的行为?
6. 使用值函数如何改进解?

问题求解题

1. 血液管理——第一部分:建模——我们将考虑血液管理问题,但假设只有一种血型,不过我们仍然要对老化过程建模,其中血液的存放时长可以是0到5周。任何存放满5周的血液如果被继续持有,则必须丢弃。与书中一样,存在两类患者:紧急患者和择期患者。设:

   $R_{t\tau}$	时间$t$时手头已存放了$\tau$个时间段的血液单位数,$\tau = 0, \ldots, 5$。
   $\Rhat_t$	在$t-1$和$t$之间到达的新献血,其中$\Rhat_t$是一个标量。
   $\Dhat^{urgent}_t$	时间$t$到达的新的紧急需求。
   $\Dhat^{elective}_t$	时间$t$到达的新的择期需求。

   在时间$t$,我们必须决定:

   $x^{urgent}_t$	分配给紧急患者的血液数量。
   $x^{elective}_t$	分配给择期患者的血液数量。
   $x^{hold}_t$	要持有的血液数量。
   $x_t$	$(x^{urgent}_t,x^{elective}_t,x^{hold}_t)$。

   需求不一定必须得到满足,但真正的问题在于:是现在就满足一个择期需求(假设有足够的血液满足所有紧急需求),还是将血液保留下来以应对未来可能出现的紧急需求。与之前一样,假设任何未得到满足的需求都会离开系统。

   你的目标是最大化一个效用函数,该函数对每覆盖一位紧急患者给予10分的奖励,对每覆盖一位择期患者给予5分的奖励。

   1. 这个问题的状态变量是什么?
   2. 决策变量和外源信息是什么?
   3. 转移函数是什么?
   4. 目标函数是什么?假设我们可以在模拟器中模拟该策略。
   5. 创建一个参数化成本函数近似,为每个决策分配以下成本:$c^{urgent}$,未覆盖紧急患者的惩罚;$c^{elective}$,未覆盖择期患者的惩罚;以及$c^{discard}$,丢弃超过5周库龄血液的惩罚。 作为你的策略,假设你将在每个时间段最小化这些成本。将向量$c=(c^{urgent},c^{elective},c^{discard})$视为一组可调参数。描述如何使用随机梯度算法优化向量$c$。务必给出计算随机梯度的方程。
2. 血液管理——第二部分:后向近似动态规划——现在我们将基于使用后向近似动态规划来近似值函数的思想设计一个策略。这意味着你必须为近似$V^x_t(S^x_t)$指定一个线性模型。这个模型的细节并不那么重要,但你可以使用类似这样的东西 $$ \Vbar^x_t(S^x_t) = \thetabar_{t0} + \sum_{age=0}^5 \theta_{t1,age} R^{urgent,x}_{t,age} + \sum_{age=0}^5 \theta_{t2,age} R^{elective,x}_{t,age}. $$ 为了本习题的目的,你可以直接写作$\Vbar^x_t(S^x_t) = (\theta_t)^T \phi(S^x_t)$,其中$\theta_t$是系数的列向量,$\phi(S^x_t)$是特征的列向量。
   1. 定义后决策状态,并用它来写出表征最优策略的贝尔曼方程。你需要用处于后决策状态$S^x_t$的值$V^x_t(S^x_t)$来写出处于时间$t$的前决策状态$S_t$的值$V_t(S_t)$的表达式。然后你需要用$V_{t+1}(S_{t+1})$来写出$V^x_t(S^x_t)$的表达式。假设血液单位始终为整数。
   2. 前决策和后决策状态变量的维度是多少?我们是否关心状态空间有多大?
   3. 写出详细的伪代码,描述如何在有限时域$0, \ldots, T$上估计该问题的值函数近似。将此视为一个编程练习,但不需要实际编程。它必须足够详细,以至于你可以把它交给课程中的同学(且熟悉该材料)让其编写代码。
   4. 使用你的近似值函数表达式写出策略。
3. 血液管理——第三部分:前瞻策略——这次,我们将假设我们拥有供应和需求的滚动预测。设$f^R_{tt'}$为使用时间$t$已知信息对时间$t'$血液捐献量的预测。设$f^{D,urgent}_{tt'}$和$f^{D,elective}_{tt'}$为根据时间$t$已知信息,对时间$t'$到达的新紧急和择期需求的预测。假设预测是外源提供的(也就是说,我们不必对预测如何从$t$演变到$t+1$进行建模)。你可以使用 $$ \begin{align*} f^R_t &= (f^R_{tt'})_{t'=t+1}^T, \\ f^{D,urgent}_t &= (f^{D,urgent}_{tt'})_{t'=t+1}^T, \\ f^{D,elective}_t &= (f^{D,elective}_{tt'})_{t'=t+1}^T, \\ f_t &= (f^R_t,f^{D,urgent}_t,f^{D,elective}_t). \end{align*} $$ 设$\sigma^R_{t'-t}$为实际捐献量$\Rhat_{tt'}$之间误差的标准差,我们假设这可以根据过去的表现得知。我们假设这纯粹是我们规划的未来时长的函数,由$t'-t$给出。类似地,设$\sigma^{D,urgent}_{t'-t}$和$\sigma^{D,elective}_{t'-t}$为新紧急和择期需求预测误差的标准差。
   1. 为此情境建模序贯决策问题的五个要素。你应该能够从之前的某一部分复制元素到此问题中。如果你愿意,可以引用任何已编号的方程以便重复使用。主要变化是纳入了预测。
   2. 使用确定性前瞻(以预测作为任何未来捐献和需求的点估计)写出DLA策略。
   3. 现在设计一个参数化策略,将每个预测替换为高于(或低于)点预测若干标准差的值。使用三个参数,你可以将其记为$\theta = (\theta^R, \theta^{urgent}, \theta^{elective})$。将寻找$\theta$最佳值的问题写作一个优化问题。解释你的表述中必须做出的任何假设。
   4. 你在(c)部分中的目标函数涉及近似一个期望值。你可以通过模拟来实现这一点,在这种情况下,你将在$T$个时间段的时域内模拟样本路径$\omega$。$\omega$是什么意思?
   5. 给出使用样本路径$\omega^1, \ldots, \omega^L$从$L$次模拟计算策略性能的均值和样本方差的公式。
   6. 假设你用样本$\theta^1, \ldots, \theta^K$表示向量$\theta$可能取值的集合。描述一种使用由$\lambda^{IE}$参数化的区间估计的搜索方法(在本书中我们使用了$\theta^{IE}$,但这会产生太多的$\theta$)。你需要描述你的信念模型,以及每次运行使用$\theta = \theta^k$的模拟后如何更新它。假设你有$N$次模拟的预算,并且$\lambda^{IE}$是已知的。

编程题

这些练习使用tinyurl.com/sdagithub上的Python模块BloodManagement。

1. 我们的目标是管理不同血型对不同患者的分配,患者首先以自身血型为特征,其次以手术是紧急还是择期为特征。

   本习题将让你使用两类策略:短视参数化成本函数近似,以及基于值函数近似的策略。

   我们将首先假设你只是将不同血型与不同需求进行匹配。血液以血型(共有八种)和库龄来描述,库龄范围从0到2周(3周库龄的血液将被丢弃)。患者以血型以及手术是紧急还是择期来描述。有各种奖励和惩罚来指导分配。例如,对覆盖紧急患者有正向奖励(这是最高的)。对血型完全匹配(例如A型阳性血液与A型阳性患者)也有奖励,对血液变得太陈旧后丢弃有惩罚。

   如果我们忽略当前决策对未来的影响,我们就有一个简单的线性规划来匹配供给和需求,成本由这组奖励给出。问题在于,通过忽略当前决策对未来的影响,我们可能会发现我们没有做到我们能做到的最好。出现的一个问题是,当我们现在将血液用于择期手术时,我们忽略了这些血液可能在以后紧急手术用血耗尽时值得保留的事实。或者,我们现在可能使用O型阴性血液,而不是为将来可能耗尽其他血型时保留它。

   设$R_{ta}$为第$t$周属性$a$血液的供给量,并设$R_t = (R_{ta})_{a\in\Acal}$,其中$\Acal$是所有不同血液属性(血型和库龄)的集合。类似地,设$D_{tb}$为患者的属性,其中$b$捕捉了血型以及手术是紧急还是择期,并设$D_t = (D_{tb})_{b\in\Bcal}$。我们系统的状态是$S_t = (R_t,D_t)$。

   现在设$\Rhat_{t+1,a}$为在第$t$周和第$t+1$周之间捐献的具有属性$a$的血液单位数。类似地,设$\Dhat_{t+1,b}$为具有属性$b$的新患者到达数量。我们可以写作

   $$ W_{t+1} = (\Rhat_{t+1,a},\Dhat_{t+1,b}). $$

   最后设$\omega$表示在我们$T$周时域内捐献和新患者的样本路径$W_1(\omega), \ldots, W_T(\omega)$。假设我们已经创建了一组关于$W_t$的模拟,并设$\Omega=(\omega_1, \ldots, \omega_N)$为这组样本实现的集合。

   1. 状态变量$S_t$有多少维度?
   2. 设$X^\pi(S_t\vert \theta)$为给定状态$S_t$求解线性规划的结果,其中$\theta$是不同分配所有奖励和惩罚的向量。设$D^{urgent}_t(x_t)$为给定决策向量$x_t$下被覆盖的紧急患者数量,并设$D^{elective}_t(x_t)$为被覆盖的择期患者数量。将寻找$\theta$最佳值的问题写作一个优化问题,其中你将用$\Omega$中样本路径的平均值来代替我们通常的期望值。
   3. 我们将考虑一个存在需求偶尔激增概率的数据集。你可以在电子表格中设置此概率。将此激增概率设置为50%。为使用血液覆盖择期手术设有一个特殊惩罚,以鼓励短视模型为可能在以后需求增加的紧急手术保留血液。在运行20次测试迭代后,从集合$\lbrace -4,-9,-14,-19,-24\rbrace $中找出该惩罚的最佳值。
   4. 在不做任何额外数值工作的情况下,现在设想O型阴性血液的惩罚需要根据周次而变化,以处理季节性变化。由于你正在模拟15周,描述一种在15维向量上进行优化的方法(我们在之前的作业中描述了两种核心策略——你可以选择其中一种,或发明一种新的策略)。

2. 现在我们将切换到基于VFA的策略,即使用每种血型(和库龄)为未来保留的边际价值。这将通过上述VFA策略部分中描述的自适应学习算法来完成(与我们针对最短路径问题的ADP策略非常相似,只是现在我们是针对决策为向量的问题来做这件事)。

   将用于择期手术血液的惩罚设置为0。当使用基于VFA的策略时,VFA应学习到超过供给量的紧急血液可能在未来需要用到。在使用VFA策略时,你需要运行20次训练迭代来估计值函数。在这些估计完成后,你将运行20次测试迭代来评估策略的质量。

   我们将针对一个存在需求偶尔激增概率的数据集测试我们的策略。你可以在电子表格中设置此概率。首先将此激增概率设置为0.7。

   1. 自适应学习算法需要估计每种血型的边际价值。设$\vhat^n_{ta}$为我们在模拟样本路径$\omega^n$时,对第$t$周血型$a$边际价值的估计。 设$\Vbar^{n-1}_t(R_{ta})$为经过$n-1$次迭代后,我们对第$t$周末(这是我们的"后决策"状态变量)当$r = R^x_{ta}$时血液第$r$个单位边际价值的估计。回想一下,我们使用$\vhat^n_{ta}$围绕前一个后决策状态变量来更新值函数近似。我们将此更新过程写作 $$ \Vbar^n_{t-1,a}(R^{x,n}_{t-1,a}) = (1-\alpha) \Vbar^{n-1}_{t-1,a}(R^{x,n}_{t-1,a}) + \alpha \vhat^n_{ta}. $$ 我们的第一个任务是调整$\alpha$。针对$\alpha \in \lbrace 0, 0.05, 0.1, 0.2, 0.3\rbrace $运行20次近似动态规划算法的迭代(这是电子表格的设置方式)并报告结果。注意步长$\alpha = 0$等同于将值函数近似保持为零(换句话说,即短视策略)。如果$\alpha = 0$,你不需要训练VFA,因此你只需运行20次测试迭代来评估策略。 VFA策略相对于短视策略(对应于$\alpha = 0$)表现如何?
   2. 现在将激增概率切换为零,并使用步长$\alpha = 0.2$比较短视策略与VFA策略。这些相比如何?你能否解释与存在激增时相比,该数据集的这种行为?