基于分支定价算法的医院资源配置优化方法和装置与流程

1.本发明属于信息技术及运筹优化技术领域，具体涉及一种基于分支定价算法的医院资源配置优化方法和装置。


背景技术：

2.根据国家卫生健康委印发的医疗机构设置规划指导原则，医院应该不断优化医疗资源配置，加快优质资源扩容和区域均衡布局，推动医院服务朝向高质量发展。在这样的政策推动下，国内的公立医院必须基于全院的现状做出最优的决策，从而使全院的各项指标符合高质量发展，如全院cmi值，四级手术占比等指标。
3.其中，cmi值是指病例组合指数，是国际公认的代表医院治疗疾病的技术难度以及收治疑难重症的综合能力，cmi值越高说明病情越严重，不容易治愈。一般cmi值越高，说明病例的难度系数越大，所以cmi值是评价医院能力的重要指标，同时，cmi与平均住院费用也有密切的关系，医保部门可以利用某地区医院的cmi值与平均住院费数据，建立最佳曲线模型，预测各医院的平均住院费用，再结合个医院预期业务量更精准的预测各医院医保预付额度。
4.疾病诊断相关分组(diagnosis related groups,drg)，是用于衡量医疗服务质量效率以及进行医保支付的一个重要工具。drg实质上是一种病例组合分类方案，即根据年龄、疾病诊断、合并症、并发症、治疗方式、病症严重程度及转归和资源消耗等因素，将患者分入若干诊断组进行管理的体系。
5.drg相对权重(rw)是对每一个drg依据其资源消耗程度所给予的权值，反映该drg的资源消耗相对于其它疾病的程度。它是医保支付的基准，其根据各drg组内例均住院费用与所有病例的例均住院费之比计算得出，数值越高，反映该病组的资源消耗越高，反之则越低。
6.近年来，国家医疗保障局对医保支付政策进行了改革，施行了由过去按项目付费的方式转变为按诊断相关分组(diagnosis related groups,drgs)进行打包付费的方式。在新医保支付政策的改革背景下，以及关于三级公立医院高质量发展的要求下，三甲医院的主要管理者和决策者，势必面对医院发展的新局面和新要求。在此大的政策背景下，医院如何合理规划重点学科的发展，如何合理配置有限的医疗资源到不同的临床科室，如何做到医保支付的盈亏平衡等等。这一系列的问题都涉及到医院的战略发展规划和科学决策。
7.针对医院在当前的政策背景下所面临的高质量发展的战略决策问题，如何设计一套通用的技术手段，并有效利用医院生产经营的病例数据，提出科学合理的解决方案，是目前亟需解决的问题。


技术实现要素：

8.鉴于上述，本发明的目的是提供一种基于分支定价算法的医院资源配置优化方法和装置，以实现对医院资源的最优配置，提高医院的高质量发展。
9.为实现上述发明目的，实施例提供了一种基于分支定价算法的医院资源配置优化方法，包括以下步骤：
10.建立医院资源配置主问题的资源配置优化模型；
11.基于丹齐格一沃尔夫分解算法对资源配置优化模型进行分解，同时采用分支定价算法进行分解的求解，以得到资源配置优化结果。
12.在一个实施例中，所述资源配置优化模型包括：
[0013][0014]
s.t. nb·
tb
l
≤∑
w∈wyw
≤nb·
tbuꢀꢀ
(1)
[0015]
nc·
hc
l
≤∑
p∈p
∑
w∈w
x
pw
≤nc·
hcuꢀꢀ
(2)
[0016]
∑
w∈wyw
·
t
·
hu
l
≤∑
p∈p
∑
w∈w
x
pw
los
pw
≤∑
w∈wyw
·
t
·
huuꢀꢀ
(3)
[0017][0018]
∑
p∈p
∑
w∈w
x
pw
·
los
pw
≤losh·
∑
p∈p
∑
w∈w
x
pw
ꢀꢀ
(5)
[0019]
margins≤∑
p∈p
rw
p
∑
w∈w
x
pw
ꢀꢀ
(6)
[0020]
cmi
past
·
∑
p∈p
∑
w∈w
x
pw
≤∑
p∈p
rw
p
∑
w∈w
x
pw
ꢀꢀ
(7)
[0021][0022][0023][0024]
上述公式定义的约束条件包括：(1)表示全院总床位数约束，(2)表示全院总病例数约束，(3)表示全院床位使用率约束，(4)表示每个科室的床位使用率约束，(5)表示全院平均住院日约束，(6)表示全院总权重约束，(7)表示全院cmi约束，(8-10)表示决策变量的上下界以及整数约束；
[0025]
其中，p表示drg病组索引，p表示drg病组集合，rwp表示病组p的rw值，w表示科室，w表示科室集合，x
pw
为一决策变量，表示科室w收治病组p的病例数，total
rw
表示总rw值，yw表示科室w的床位数，tbu和tb
l
表示全院总床位数的预设上下限，nb表示tbu和tb
l
的波动幅度，hcu和hc
l
表示全院总病例数的预设上下限，nc表示hcu和hc
l
的波动幅度，los
pw
表示病组p在科室w的平均住院日，t表示天数，huu和hu
l
表示全院床位使用率的上下波动幅度，du
lw
和du
uw
表示科室床位使用率的上下波动幅度，losh表示全院的平均住院日，margins表示全院总权重阈值，cmi
past
表示全院去年的总体cmi值，lp
pw
,up
pw
表示病例数x
pw
的上下限，lbw,ubw表示yw的上下限，表示正整数。
[0026]
在一个实施例中，所述方法还包括：通过指示变量和大整数m调整所述资源配置优化模型，具体包括：
[0027]
对资源配置优化模型中每个约束条件(1)-(7)通过指示变量和大整数m进行如下转换：
[0028]-m
·
(1-i1)+nb·
tb
l
≤∑
w∈wyw
≤nb·
tbu+m
·
(1-i1)
ꢀꢀ
(1)
[0029]-m
·
(1-i2)+nc·
hc
l
≤∑
p∈p
∑
w∈w
x
pw
≤nc·
hcu+m
·
(1-i2)
ꢀꢀ
(2)
[0030]-m
·
(1-i3)+nc∑
w∈wyw
·
t
·
hu
l
≤∑
p∈p
∑
w∈w
x
pw
los
pw
≤∑
w∈wyw
·
t
·
huu+m
·
(1-i3)
ꢀꢀ
(3)
[0031][0032]
∑
p∈p
∑
w∈w
x
pw
·
los
pw
≤losh·
∑
p∈p
∑
w∈w
x
pw
+m
·
(1-i5)
ꢀꢀ
(5)
[0033]
margins≤∑
p∈p
rw
p
∑
w∈w
x
pw
+m
·
(1-i6)
ꢀꢀ
(6)
[0034]
cmi
past
·
∑
p∈p
∑
w∈w
x
pw
≤∑
p∈p
rw
p
∑
w∈w
x
pw
+m
·
(1-i7)
ꢀꢀ
(7)
[0035]
同时基于指示变量将优化目标max total
rw
＝∑
p∈p
rw
p
∑
w∈w
x
pw
转化为如下形式：
[0036]
max cmi
·
i0+total
rw
·
(1-i0)
[0037]
其中，i
0-i7为指示变量，取值为0或1，用于指示约束条件是否成立；
[0038]
应用时通过配置指示变量的取值来调整约束条件以使资源配置优化模型适配医院实际情况。
[0039]
在一个实施例中，基于丹齐格一沃尔夫分解算法对资源配置优化模型进行分解时，对病例数x
pw
按照drg病组进行聚合，即将属于drg病组p的所有科室w的一组病例数x
pw
聚合；
[0040]
或对病例数x
pw
按照科室聚合，即将属于科室w的所有病组p的一组x
pw
进行聚合。
[0041]
在一个实施例中，当对病例数x
pw
按照科室聚合时，形成可行列，并引入如下新决策变量c
wk
表示可行列，
[0042][0043]
这样基于丹齐格一沃尔夫分解算法的资源配置优化模型表示为：
[0044][0045]
s.t. nb·
tb
l
≤∑
w∈w
∑
k∈kywk
·cwk
≤nb·
tbuꢀꢀ
(8)
[0046]
nc·
hc
l
≤∑
w∈w
∑
k∈k
x
wk
·cwk
≤nc·
hcuꢀꢀ
(9)
[0047][0048]
∑
w∈w
∑
k∈kywk
·cwk
·
t
·
hu
l
≤∑
w∈w
∑
k∈k
los
wk
·cwk
≤∑
w∈w
∑
k∈kywk
·cwk
·
t
·
huuꢀꢀ
(11)
[0049]
∑
w∈w
∑
k∈k
rw
wk
·cwk
≥cmi
past
∑
w∈w
∑
k∈k
x
wk
·cwk
ꢀꢀ
(12)
[0050][0051]
其中，rw
wk
表示科室w选择第k列的rw值，k表示列集合，y
wk
表示科室w选择第k列的床位数，x
wk
表示科室w选择第k列的病例数，los
wk
表示科室w选择第k列的平均住院日。
[0052]
在一个实施例中，根据基于丹齐格一沃尔夫分解算法的资源配置优化模型，利用对偶变量构造子问题，对科室w的列k的子问题构造如下：
[0053][0054][0055]
[0056][0057][0058][0059][0060][0061]
其中，上述公式定义的约束条件包括：(14)表示限定科室w的病例数为列k的所有病组的病例数之和，(15)表示限定科室w的住院天数为列k的所有病组的住院天数之和，(16)表示限定科室w选择的列k的床位使用率的上界，(17)表示限定科室w选择的列k的床位使用率的下界，(18)-(19)表示科室w选择的列k的病组的病例数的区间范围、床位数的区间范围以及整数限制。
[0062]
在一个实施例中，以最大化降低成本值为目标函数对子问题进行求解，当求解结果对应的最大降低成本值大于0时，将子问题对应的列加入到列集合中，其中，降低成本值rc
wk
的计算公式为：
[0063]
rc
wk
＝rw
wk-y
wk
πa+y
wk
π
b-x
wk
γa+x
wk
γ
b-β
w-(los
wk-y
wk
·cwk
·
t
·
huu)μa+(los
wk-y
wk
·cwk
·
t
·
huu)μb+(rw
wk-cmi
past
·
x
wk
)ε
[0064]
其中，πa、πb为约束条件(8)的对偶变量，γa、γb为约束条件(9)的对偶变量，βw为约束条件(10)的对偶变量，μa、μb为约束条件(11)的对偶变量，ε为约束条件(12)的对偶变量。
[0065]
在一个实施例中，所述方法还包括：判断当前子问题产生的解是否为医院资源配置主问题的最优解，如果不是，将当前子问题对应的列进行剪枝处理。
[0066]
为实现上述发明目的，实施例还提供了一种基于分支定价算法的医院资源配置优化装置，包括模型建立模块和模型优化求解模块；
[0067]
所述模型建立模块用于建立医院资源配置主问题的资源配置优化模型；
[0068]
所述模型优化求解模块用于基于丹齐格一沃尔夫分解算法对资源配置优化模型进行分解，同时采用分支定价算法进行分解的求解，以得到资源配置优化结果。
[0069]
为了实现上述发明目的，实施例还提供了一种计算设备，包括存储器、处理器以及存储在所述存储器中并可在所述处理器上执行的计算机程序，所述处理器执行所述计算机程序时实现上述基于分支定价算法的医院资源配置优化方法。
[0070]
与现有技术相比，本发明具有的有益效果至少包括：
[0071]
在建立医院资源配置主问题的资源配置优化模型的基础上，通过于丹齐格一沃尔夫分解算法和分子定价算法来快速进行求解，求解结果可以有效辅助医院管理者在医院运营管理中进行决策，对医院科学高效的完成资源配置、提高医院的医疗服务能力和医疗效率、合理控制医保超支以及促进医院的高质量发展具有重要的理论和现实意义。
附图说明
[0072]
为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图做简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动前提下，还可以根
据这些附图获得其他附图。
[0073]
图1是实施例提供的基于分支定价算法的医院资源配置优化方法的流程图；
[0074]
图2是实施例提供的分子定价算法的流程图。
具体实施方式
[0075]
为使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例对本发明进行进一步的详细说明。应当理解，此处所描述的具体实施方式仅仅用以解释本发明，并不限定本发明的保护范围。
[0076]
以解决目前医院运营决策存在的实际问题，实施例提供了一种基于分支定价算法的医院资源配置优化方法，包括以下步骤：
[0077]
步骤1，建立医院资源配置主问题的资源配置优化模型。
[0078]
基于医院的实际业务需求，模型的目标函数为最大化drg总权重。drg病组的权重rw值代表了病组收治患者的疑难危重程度，而drg总权重则反映医院提供的医疗服务总量。drg总权重越大，说明医院提供的高质量医疗服务越多。drg总权重为医院每个科室所有drg病组的病例数与其权重乘积的求和，具体公式如下：total
rw
＝∑
p∈p
rw
p
∑
w∈w
x
pw
[0079]
基于此，针对医院资源配置主问题建立的资源配置优化模型为：
[0080][0081]
s.t. nb·
tb
l
≤∑
w∈wyw
≤nb·
tbuꢀꢀ
(1)
[0082]
nc·
hc
l
≤∑
p∈p
∑
w∈w
x
pw
≤nc·
hcuꢀꢀ
(2)
[0083]
∑
w∈wyw
·
t
·
hu
l
≤∑
p∈p
∑
w∈w
x
pw
los
pw
≤∑
w∈wyw
·
t
·
huuꢀꢀ
(3)
[0084][0085]
∑
p∈p
∑
w∈w
x
pw
·
los
pw
≤losh·
∑
p∈p
∑
w∈w
x
pw
ꢀꢀ
(5)
[0086]
margins≤∑
p∈p
rw
p
∑
w∈w
x
pw
ꢀꢀ
(6)
[0087]
cmi
past
·
∑
p∈p
∑
w∈w
x
pw
≤∑
p∈p
rw
p
∑
w∈w
x
pw (7)
[0088][0089][0090][0091]
上述公式定义的约束条件包括：(1)表示全院总床位数约束，(2)表示全院总病例数约束，(3)表示全院床位使用率约束，(4)表示每个科室的床位使用率约束，(5)表示全院平均住院日约束，(6)表示全院总权重约束，(7)表示全院cmi约束，(8-10)表示决策变量的上下界以及整数约束；
[0092]
其中，p表示drg病组索引，p表示drg病组集合，rwp表示病组p的rw值，w表示科室，w表示科室集合，x
pw
为一决策变量，表示科室w收治病组p的病例数，total
rw
表示总rw值，yw表示科室w的床位数，tbu和tb
l
表示全院总床位数的预设上下限，nb表示tbu和tb
l
的波动幅度，hcu和hc
l
表示全院总病例数的预设上下限，nc表示hcu和hc
l
的波动幅度，los
pw
表示病组p在科室w的平均住院日，t表示天数，huu和hu
l
表示全院床位使用率的上下波动幅度，du
lw
和du
uw
表示科室床位使用率的上下波动幅度，losh表示全院的平均住院日，margins表示全院总权重阈值，cmi
past
表示全院去年的总体cmi值，lp
pw
,up
pw
表示病例数x
pw
的上下限，lbw,ubw表示yw的上下限，表示正整数。需要说明的是，素有波动幅度取值为百分比，在实际应用中，可以根据需求设定。
[0093]
为了增加模型的通用性和适配性，能够满足模型对不同医院的需求，同时也是为了减少人为因素对模型的直接操作，在上述模型的基础上做出了进一步的优化，采用指示变量i和任意大的整数m，对大于等于和小于等于不等约束不等式做如下处理：
[0094]
针对形如ax+b≤c的不等式，处理为ax+b≤c+m
·
(1-i)；
[0095]
针对形如ax+b≥c的不等式，处理为ax+b≥c-m
·
(1-i)。
[0096]
需要说明的是，指示变量i取值为0或1，整数m的理论取值为任意大整数，数学定义为：，都恒存在m＞a。在实际计算机程序仿真时的取值为计算机的最大位数所表示的整数，如计算机是64位的，则m的取值为2
64-1。
[0097]
基于以上处理方式，通过指示变量和大整数m将上述资源配置优化模型优化为：
[0098]-m
·
(1-i1)+nb·
tb
l
≤∑
w∈wyw
≤nb·
tbu+m
·
(1-i1)
ꢀꢀ
(1)
[0099]-m
·
(1-i2)+nc·
hc
l
≤∑
p∈p
∑
w∈w
x
pw
≤nc·
hcu+m
·
(1-i2)
ꢀꢀ
(2)
[0100]-m
·
(1-i3)+nc∑
w∈wyw
·
t
·
hu
l
≤∑
p∈p
∑
w∈w
x
pw
los
pw
≤∑
w∈wyw
·
t
·
huu+m
·
(1-i3)
ꢀꢀ
(3)
[0101][0102]
∑
p∈p
∑
w∈w
x
pw
·
los
pw
≤losh·
∑
p∈p
∑
w∈w
x
pw
+m
·
(1-i5)
ꢀꢀ
(5)
[0103]
margins≤∑
p∈p
rw
p
∑
w∈w
x
pw
+m
·
(1-i6)
ꢀꢀ
(6)
[0104]
cmi
past
·
∑
p∈p
∑
w∈w
x
pw
≤∑
p∈p
rw
p
∑
w∈w
x
pw
+m
·
(1-i7)
ꢀꢀ
(7)
[0105]
同时基于指示变量将优化目标max total
rw
＝∑
p∈p
rw
p
∑
w∈w
x
pw
转化为如下形式：
[0106]
max cmi
·
i0+total
rw
·
(1-i0)
[0107]
其中，i
0-i7为指示变量，取值为0或1，用于指示约束条件是否成立。当与某家医院进行交互的时候，医院的需求可能是多样的，通过配置指示变量来调整约束条件的成立状态以适配医院的实际需求。例如，当i0＝1时，此时的目标函数就要变成了最大化cmi，否则就是最大化总权重；当i3＝1时，全院床位使用率的上界是成立的，否则这个约束失效了。以此类推，其他的约束条件是否发挥作用完全取决于指示变量的值，这些指示变量值是保存在独立的配置文件里，可以根据客户需求进行配置调整，而不用直接在模型里修改，大大减少了工作量和工作复杂度。
[0108]
步骤2，基于丹齐格一沃尔夫分解算法对资源配置优化模型进行分解，同时采用分子定价算法进行分解的求解，以得到资源配置优化结果。
[0109]
步骤1构建的医院资源配置模型规模大求解难度高，使用一般的整数规划方法无法求解，因此，本实施例采用丹齐格一沃尔夫分解算法和分支定价算法相结合的方式以高效率求解医院资源配置主问题。
[0110]
丹齐格一沃尔夫分解算法(dantzig-wolfe decomposition)是求解可分解的大规模线性规划问题的算法。对于可分解的线性规划问题(称为母规划)，可以分解成几个规模较小的子规划。分解算法的过程是从母规划的一个基可行解开始，作对应的乘数，并将母规
划分解成几个子规划。通过解几个子规划来判断这一基可行解是否为最优的。若不是最优的，就利用单纯形法对母规划进行换基迭代，得到一个新的基可行解，再作相应的乘数，经有限次计算就可以得到母规划的最优解。
[0111]
采用丹齐格一沃尔夫分解算法分解的维度有多种，可以对病例数x
pw
按照drg病组进行聚合，即将属于drg病组p的所有科室w的一组病例数x
pw
聚合。还可以对病例数x
pw
按照科室聚合，即将属于科室w的所有病组p的一组x
pw
进行聚合。
[0112]
例如，按照科室w聚合，对属于科室w的所有病组p的一组x
pw
进行聚合将会形成一个新决策变量，它代表着属于科室w的一种病组组合的模式。通过找到一个能够覆盖全院的，并且总权重最大的可行列组合，也就得到了一个最优的病例组合模式，以及科室的床位分配。
[0113]
对于每一个科室w中的所有drg病组p的病例数x
pw
进行聚合，形成一个可行列，为表示可行列，引入一个新决策变量，定义如下：
[0114][0115]
这样，基于丹齐格一沃尔夫分解算法的资源配置优化模型表示为：
[0116][0117]
s.t. nb·
tb
l
≤∑
w∈w
∑
k∈kywk
·cwk
≤nb·
tbuꢀꢀ
(8)
[0118]
nc·
hc
l
≤∑
w∈w
∑
k∈k
x
wk
·cwk
≤nc·
hcuꢀꢀ
(9)
[0119][0120]
∑
w∈w
∑
k∈kywk
·cwk
·
t
·
hu
l
≤∑
w∈w
∑
k∈k
los
wk
·cwk
≤∑
w∈w
∑
k∈kywk
·cwk
·
t
·
huuꢀꢀ
(11)
[0121]
∑
w∈w
∑
k∈k
rw
wk
·cwk
≥cmi
past
∑
w∈w
∑
k∈k
x
wk
·cwk
ꢀꢀ
(12)
[0122][0123]
其中，rw
wk
表示科室w选择第k列的rw值，k表示列集合，y
wk
表示科室w选择第k列的床位数，x
wk
表示科室w选择第k列的病例数，los
wk
表示科室w选择第k列的平均住院日。
[0124]
实施例中，根据基于丹齐格一沃尔夫分解算法的资源配置优化模型，利用对偶变量构造子问题，对科室w的列k的子问题构造如下：
[0125][0126][0127][0128][0129][0130]
[0131][0132][0133]
其中，上述公式定义的约束条件包括：(14)表示限定科室w的病例数为列k的所有病组的病例数之和，(15)表示限定科室w的住院天数为列k的所有病组的住院天数之和，(16)表示限定科室w选择的列k的床位使用率的上界，(17)表示限定科室w选择的列k的床位使用率的下界，(18)-(19)表示科室w选择的列k的病组的病例数的区间范围、床位数的区间范围以及整数限制。
[0134]
以最大化降低成本值(reduce cost)为目标函数对子问题进行求解，当列k的reduce cost为正时，该列能够改进原问题的解。因此，可以通过计算所有可能列的最大reduce cost值，当求解结果对应的最大降低成本值大于0时，将子问题对应的列加入到列集合rmlp中，不断地更新和求解rmlp，直到没有新生成的列为止。
[0135]
其中，rc
wk
的计算公式为：
[0136]
rc
wk
＝rw
wk-y
wk
πa+y
wk
π
b-x
wk
γa+x
wk
γ
b-β
w-(los
wk-y
wk
·cwk
·
t
·
huu)μa+(los
wk-y
wk
·cwk
·
t
·
huu)μb+(rw
wk-cmi
past
·
x
wk
)ε
[0137]
其中，πa、πb为约束条件(8)的对偶变量，γa、γb为约束条件(9)的对偶变量，βw为约束条件(10)的对偶变量，μa、μb为约束条件(11)的对偶变量，ε为约束条件(12)的对偶变量。
[0138]
分支定价算法包括分支定界算法和列生成算法。分支定界算法始终围绕着一颗搜索树进行的，将原问题看作是搜索树的根节点，从根节点出发，进行分支。分支的含义是将大的问题分割成小的问题，大问题可以看成是搜索树的父节点，那么从大问题分割出来的小问题就是父节点的子节点了。分支的过程就是不断的给树增加子节点的过程。定界的过程就是在分支的过程中去检查子问题的上下界，如果子问题不能产生一个比当前最优解还要优的解，那么就要进行剪枝操作，直到所有的子问题都不能产生一个最优的解，分支定界过程结束。
[0139]
列生成算法是用于求节点的下界，即节点的最优解。列生成算法因其求解方法的本质会大大减少计算量，求解的并非当前问题，而是受限制的子问题，即减少了决策变量规模。
[0140]
分支定价就在在枚举的基础上，加上了定界的过程，大大的缩小了解空间的查找范围。
[0141]
图2为分支定价算法的流程框图，如图2所示。具体步骤如下：
[0142]
step 1.首先采用启发式算法对原问题(1)-(10)进行求解，得到初步的可行解集合，将可行解集合按科室转换为各科室可行列的集合k。
[0143]
step 2.然后采用丹齐格一沃尔夫分解算法和从上述的集合k选择若干列k，将原问题分解为求解若干个科室最优资源配置的子问题，也称为拉格朗日松弛后的受限主问题(restricted master lagrange problem,rmlp)。
[0144]
step 3.求解上述的rmlp，根据对偶变量的值构造rmlp的对偶子问题，再求解科室为单元的整数规划子问题，查看是否存在检验数(reduce cost)为负的列，有的话则加入选择的列集合中，作为新生成的列，即为列生成算法。
[0145]
step 4.当所求解的子问题的解不存在检验数为负的列时，则需要查看所有子问
题的解是否为整数，如果不是整数，则对该解进行分支。如最优解中某科室w收治病组p的患者数为45.6，则对该解进行分支，分别新增两个不同的约束x
pw
≥46和x
pw
≤45到原问题(1)-(10)中，从而新增两个主问题p1和p2到问题队列中，因此下一次需要依次从问题队列中取出问题节点node，回到step 1，该步骤简称为分支定界算法。
[0146]
step 5.当所有的解都为整数时且为最优解，则求得该整数规划最优解。
[0147]
基于同样的发明构思，实施例还提供了一种基于分支定价算法的医院资源配置优化装置，包括模型建立模块和模型优化求解模块；其中，模型建立模块用于建立医院资源配置主问题的资源配置优化模型；模型优化求解模块用于基于丹齐格一沃尔夫分解算法对资源配置优化模型进行分解，同时采用分支定价算法进行分解的求解，以得到资源配置优化结果。
[0148]
需要说明的是，上述实施例提供的基于分支定价算法的医院资源配置优化装置在进行基于分支定价算法的医院资源配置优化时，应以上述各功能模块的划分进行举例说明，可以根据需要将上述功能分配由不同的功能模块完成，即在终端或服务器的内部结构划分成不同的功能模块，以完成以上描述的全部或者部分功能。另外，上述实施例提供的基于分支定价算法的医院资源配置优化装置与基于分支定价算法的医院资源配置优化方法实施例属于同一构思，其具体实现过程详见基于分支定价算法的医院资源配置优化方法实施例，这里不再赘述。
[0149]
基于同样的发明构思，实施例还提供了一种计算设备，包括存储器、处理器以及存储在所述存储器中并可在所述处理器上执行的计算机程序，所述处理器执行所述计算机程序时实现上述基于分支定价算法的医院资源配置优化方法，具体包括以下步骤：
[0150]
步骤1，建立医院资源配置主问题的资源配置优化模型；
[0151]
步骤2，基于丹齐格一沃尔夫分解算法对资源配置优化模型进行分解，同时采用分子定价算法进行分解的求解，以得到资源配置优化结果。
[0152]
其中，存储器可以为在近端的易失性存储器，如ram，还可以是非易失性存储器，如rom，flash，软盘，机械硬盘等，还可以是远端的存储云。处理器可以为中央处理器(cpu)、微处理器(mpu)、数字信号处理器(dsp)、或现场可编程门阵列(fpga)，即可以通过这些处理器实现基于分支定价算法的医院资源配置优化方法。
[0153]
以上所述的具体实施方式对本发明的技术方案和有益效果进行了详细说明，应理解的是以上所述仅为本发明的最优选实施例，并不用于限制本发明，凡在本发明的原则范围内所做的任何修改、补充和等同替换等，均应包含在本发明的保护范围之内。

技术特征：
1.一种基于分支定价算法的医院资源配置优化方法，其特征在于，包括以下步骤：建立医院资源配置主问题的资源配置优化模型；基于丹齐格一沃尔夫分解算法对资源配置优化模型进行分解，同时采用分支定价算法进行分解的求解，以得到资源配置优化结果。2.根据权利要求1所述的基于分支定价算法的医院资源配置优化方法，其特征在于，所述资源配置优化模型包括：s.t.n
b
·
tb
l
≤∑
w∈w
y
w
≤n
b
·
tb
u
ꢀꢀꢀꢀ
(1)n
c
·
hc
l
≤∑
p∈p
∑
w∈w
x
pw
≤n
c
·
hc
u
ꢀꢀ
(2)∑
w∈w
y
w
·
t
·
hu
l
≤∑
p∈p
∑
w∈w
x
pw
los
pw
≤∑
w∈w
y
w
·
t
·
hu
u
ꢀꢀꢀ
(3)∑
p∈p
∑
w∈w
x
pw
·
los
pw
≤los
h
·
∑
p∈p
∑
w∈w
x
pw
ꢀꢀꢀ
(5)morgins≤∑
p∈p
rw
p
∑
w∈w
x
pw
ꢀꢀꢀ
(6)cmi
past
·
∑
p∈p
∑
w∈w
x
pw
≤∑
p∈p
rw
p
∑
w∈w
x
pw
ꢀꢀ
(7)(7)(7)上述公式定义的约束条件包括：(1)表示全院总床位数约束，(2)表示全院总病例数约束，(3)表示全院床位使用率约束，(4)表示每个科室的床位使用率约束，(5)表示全院平均住院日约束，(6)表示全院总权重约束，(7)表示全院cmi约束，(8-10)表示决策变量的上下界以及整数约束；其中，p表示drg病组索引，p表示drg病组集合，rwp表示病组p的rw值，w表示科室，w表示科室集合，x
pw
为一决策变量，表示科室w收治病组p的病例数，total
rw
表示总rw值，y
w
表示科室w的床位数，tb
u
和tb
l
表示全院总床位数的预设上下限，n
b
表示tb
u
和tb
l
的波动幅度，hc
u
和hc
l
表示全院总病例数的预设上下限，n
c
表示hc
u
和hc
l
的波动幅度，los
pw
表示病组p在科室w的平均住院日，t表示天数，hu
u
和hu
l
表示全院床位使用率的上下波动幅度，du
lw
和du
uw
表示科室床位使用率的上下波动幅度，los
h
表示全院的平均住院日，margins表示全院总权重阈值，cmi
past
表示全院去年的总体cmi值，lp
pw
，up
pw
表示病例数x
pw
的上下限，lb
w
，ub
w
表示y
w
的上下限，表示正整数。3.根据权利要求1所述的基于分支定价算法的医院资源配置优化方法，其特征在于，所述方法还包括：通过指示变量和大整数m调整所述资源配置优化模型，具体包括：对资源配置优化模型中每个约束条件(1)-(7)通过指示变量和大整数m进行如下转换：-m
·
(1-i1)+n
b
·
tb
l
≤∑
w∈w
y
w
≤n
b
·
tb
u
+m
·
(1-i1)
ꢀꢀꢀ
(1)-m
·
(1-i2)+n
c
·
hc
l
≤∑
p∈p
∑
w∈w
x
pw
≤n
c
·
hc
u
+m
·
(1-i2)
ꢀꢀ
(2)-m
·
(1-i3)+n
c
∑
w∈w
y
w
·
t
·
hu
l
≤∑
p∈p
∑
w∈w
x
pw
los
pw
≤∑
w∈w
y
w
·
t
·
hu
u
+m
·
(1-i3) {3)
∑
p∈p
∑
w∈w
x
pw
·
los
pw
≤los
h
·
∑
p∈p
∑
w∈w
x
pw
+m
·
(1-i5) (5)margins≤∑
p∈p
rw
p
∑
w∈w
x
pw
+m
·
(1-i6)
ꢀꢀꢀꢀ
(6)cmi
past
·
∑
p∈p
∑
w∈w
x
pw
≤∑
p∈p
rw
p
∑
w∈w
x
pw
+m
·
(1-i7)
ꢀꢀꢀ
(7)同时基于指示变量将优化目标max total
rw
＝∑
p∈p
rw
p
∑
w∈w
x
pw
转化为如下形式：max cmi
·
i0+total
rw
·
(1-i0)其中，i
0-i7为指示变量，取值为0或1，用于指示约束条件是否成立；应用时通过配置指示变量的取值来调整约束条件以使资源配置优化模型适配医院实际情况。4.根据权利要求2所述的基于分支定价算法的医院资源配置优化方法，其特征在于，基于丹齐格一沃尔夫分解算法对资源配置优化模型进行分解时，对病例数x
pw
按照drg病组进行聚合，即将属于drg病组p的所有科室w的一组病例数x
pw
聚合；或对病例数x
pw
按照科室聚合，即将属于科室w的所有病组p的一组x
pw
进行聚合。5.根据权利要求4所述的基于分支定价算法的医院资源配置优化方法，其特征在于，当对病例数x
pw
按照科室聚合时，形成可行列，并引入如下新决策变量c
wk
表示可行列，这样基于丹齐格一沃尔夫分解算法的资源配置优化模型表示为：s.tn
b
·
tb
l
≤∑
w∈w
∑
k∈k
y
wk
·
c
wk
≤n
b
·
tb
u
ꢀꢀꢀ
(8)n
c
·
hc
l
≤∑
w∈w
∑
k∈k
x
wk
·
c
wk
≤n
c
·
hc
u
ꢀꢀꢀ
(9)∑
w∈w
∑
k∈k
y
wk
·
c
wk
·
t
·
hu
l
≤∑
w∈w
∑
k∈k
los
wk
·
c
wk
≤∑
w∈w
∑
k∈k
y
wk
·
c
wk
·
thu
u
ꢀꢀꢀꢀ
(11)∑
w∈w
∑
k∈k
rw
wk
·
c
wk
≥cmi
past
∑
w∈w
∑
k∈k
x
wk
·
c
wk
ꢀꢀꢀ
(12)其中，rw
wk
表示科室w选择第k列的rw值，k表示列集合，y
wk
表示科室w选择第k列的床位数，x
wk
表示科室w选择第k列的病例数，los
wk
表示科室w选择第k列的平均住院日。6.根据权利要求5所述的基于分支定价算法的医院资源配置优化方法，其特征在于，根据基于丹齐格一沃尔夫分解算法的资源配置优化模型，利用对偶变量构造子问题，对科室w的列k的子问题构造如下：的列k的子问题构造如下：
其中，上述公式定义的约束条件包括：(14)表示限定科室w的病例数为列k的所有病组的病例数之和，(15)表示限定科室w的住院天数为列k的所有病组的住院天数之和，(16)表示限定科室w选择的列k的床位使用率的上界，(17)表示限定科室w选择的列k的床位使用率的下界，(18)-(19)表示科室w选择的列k的病组的病例数的区间范围、床位数的区间范围以及整数限制。7.根据权利要求6所述的基于分支定价算法的医院资源配置优化方法，其特征在于，以最大化降低成本值为目标函数对子问题进行求解，当求解结果对应的最大降低成本值大于0时，将子问题对应的列加入到列集合中，其中，降低成本值rc
wk
的计算公式为：rc
wk
＝rw
wk-y
wk
π
a
+y
wk
π
b-x
wk
γ
a
+x
wk
γ
b-β
w-(los
wk-y
wk
·
c
wk
·
t
·
hu
u
)μ
a
+(los
wk-y
wk
·
c
wk
·
thu
u
)μ
b
+(rw
wk-cmi
past
·
x
wk
)ε其中，π
a
、π
b
为约束条件(8)的对偶变量，γ
a
、γ
b
为约束条件(9)的对偶变量，β
w
为约束条件(10)的对偶变量，μ
a
、μ
b
为约束条件(11)的对偶变量，ε为约束条件(12)的对偶变量。8.根据权利要求7所述的基于分支定价算法的医院资源配置优化方法，其特征在于，还包括：判断当前子问题产生的解是否为医院资源配置主问题的最优解，如果不是，将当前子问题对应的列进行剪枝处理。9.一种基于分支定价算法的医院资源配置优化装置，其特征在于，包括模型建立模块和模型优化求解模块；所述模型建立模块用于建立医院资源配置主问题的资源配置优化模型；所述模型优化求解模块用于基于丹齐格一沃尔夫分解算法对资源配置优化模型进行分解，同时采用分支定价算法进行分解的求解，以得到资源配置优化结果。10.一种计算设备，包括存储器、处理器以及存储在所述存储器中并可在所述处理器上执行的计算机程序，其特征在于，所述处理器执行所述计算机程序时实现权利要求1-8任一项所述的基于分支定价算法的医院资源配置优化方法。

技术总结
本发明公开了一种基于分支定价算法的医院资源配置优化方法和装置，包括以下步骤：建立医院资源配置主问题的资源配置优化模型；基于丹齐格一沃尔夫分解算法对资源配置优化模型进行分解，同时采用分子定价算法进行分解的求解，以得到资源配置优化结果。该方法可以有效辅助医院管理者在医院运营管理中进行决策，对医院科学高效的完成资源配置、提高医院的医疗服务能力和医疗效率、合理控制医保超支以及促进医院的高质量发展具有重要的理论和现实意义。意义。意义。


技术研发人员：张洪波 马国选 陈浦兰 刘建 黄健豪
受保护的技术使用者：杭州火树科技有限公司
技术研发日：2023.04.14
技术公布日：2023/7/21