物资分配问题
摘要
在各种各样的抢险救灾行动中,应急物资的合理分配在降低灾害的影响方面体现
出重要作用。我们通过对问题的深入理解和分析,将问题归结为非线性规划问题。
我们首先确立了通过合理优化救灾物资的分配使其能最大限度降低灾害的影响为
根本分配原则。
接着我们根据不同物资在维持灾民正常生活中所起到的作用大小不同划定了各物
资的优先级,给定了适当的权重;接着综合考虑各个灾民所缺物资的数量、种类、供给
量及物资的权重,确定了不同灾民受灾程度的判定标准;随后对受灾情况和物质分配情
况进行了矩阵描述。
在此基础上我们用救灾效果表示整个救灾过程使灾情降低的程度,并假设每分配
出一个最小单位的救灾物资就相应产生一定量的救灾效果,最终整体救灾效果为它们之
和。我们又进一步假设每个最小单位救灾物资产生的救灾效果与分配物资的权重、分配
给的灾民受灾程度正相关,得到了基本的数学模型:
单位物资救灾效果 = 该物资权重 × 分配给灾民的受灾程度
最终救灾效果 = 单位物资救灾效果求和
模型的约束条件由各种物资的数量有限得到。我们以最大限度减小灾害影响为分
配原则,即最大限度增强最终救灾效果,在此抽象为求解最终救灾效果在约束条件下的
最大值。其对应的最优解即为最佳分配方案。
在模型求解中,我们本着最大程度地发挥各种物资效用的原则,按照物资的优先
级从高到低逐一对物资进行了分配。在具体分配某一物资时,首先求得分配结果与产生
的救灾效果的函数,继而简化为有约束的多元函数最值问题,并分别采用了 MATLAB 程
序解法和拉格朗日乘数法。
紧接着我们给出了一个具体灾情,并用量化后的模型求出最优解,通过对结果的
分析研究讨论了模型的合理性。
最后,我们对模型的优缺点进行了讨论,并提出了模型的改进方案,并且对模型
的实际应用做了推广。
救灾效果 物资权重 受灾程度 单位物资
关键词
- - 1 - -
一、问题重述
某一灾区有 N 名受灾群众,现有一批救灾物资要发放给这些受灾者。物资共有 M
种,每种物质的数量有限;各受灾者的灾情不同,对每种物资的急需程度和需求量不同。
(1) 你作为一名分配者,请制定分配原则并给出合理的分配方法。
(2) 试给出一个符合题意的数值算例。
2.1 符号说明
二、符号说明与基本假设
含义
符号
iP 第 i 位灾民
jM 第 j 种物资
第 i 位灾民短缺第 j 种物资的数量
第 i 位灾民分配到的第 j 种物资的数量
第 j 种物资总量
iS
ijt
ijx
j 第 j 种物资的权重
ip 第 i 位灾民的受灾程度
2.2 基本假设
1. 所有物资对降低灾害的贡献取决于每单位物资贡献之和
2. 每单位物资对降低灾害的贡献与该物资的作用大小正相关
3. 每单位物资对降低灾害的贡献与得到该物资灾民的灾情大小正相关
4. 每种物资的供给均小于需求
三、问题分析与基本思路
为减轻自然灾害的影响,对应急物资分配策略的研究就有了十分重要的意义。通
过对问题的分析与理解并结合实际情况,我们给出了抗险救灾中物资分配的基本原则:
在应急物资有限的情况下,对救灾物资进行最优分配,使得分配结果能最大限度地降低
灾害。我们用最终救灾效果表示物资分配降低灾害的程度,那么分配原则就等价于使最
终救灾效果最大。而最终救灾效果又与每单位物资产生的救灾效果有关。通过给出物资
权重和受灾程度的概念我们对每单位物资产生的救灾效果进行了数学表示,从而通过求
和,最终确定了主函数——最终救灾效果。
- - 2 - -
在求解模型时,由于非线性离散优化问题的求解十分困难,我们进行了适当的简化,
转化为非线性连续优化问题,继而通过 MATLAB 优化工具箱和拉格朗日乘数法求解了
模型。
在此我们给出整体研究思路:
M×N 矩阵对
物资需求的描述
受灾程度的
分析判定
目标函数规划
物资权重
的说明与优
先级划分
Matlab 优化
工具箱
拉格朗日极值
M×N 型矩阵描述
物资分配的方案
具体算例比较
模型改进与推广
优缺点评价
- - 3 - -
四、模型的准备
4.1 物资需求状况的描述
某地区遭受灾害的一种表现形式为该地区灾民的各种生活物资出现了不同程度的
短缺。为了描述灾情即各个灾民缺少各种物资的量,我们建立了 N×M 型矩阵 A:
A
t
1
…
t
12
M
… … …
t
11
t
21
… … … …
t
… …
t
NM
N
1
其中 ijt 表示灾民 ip 缺少物资 jM 的量。
A 中数据由物资分配者通过对灾情的调查得到,均为非负常数。其中 A 的行向量 ia
表
示灾民 ip 对不同物资的需求量。A 的列向量 jb
4.2 物资权重的说明
表示整个灾区对物资 jM 的需求量情况。
由于不同物资在维持灾民正常生活中的作用不同,相同量的不同物资在减轻灾害的
效用上不同。为表征物资的这一特性,我们首先将物资化分为四大类,并为其评定了优
先级。
优先级
物资大类
举例
最高优先级 关键物资 应急食品:方便面、矿泉水等
较高优先级 基础物资
中等优先级 重要物资
较低优先级 可替代物资
其他生活物资:帐蓬等
大米、面粉、豆油等
衣被、棉被等
根据物资 jM 所属大类及其优先级,按优先级与权重正相关的原则,给于物资 jM
合理的权重 j ,规定 1> j >0。
4.3 受灾程度的评定
为表征不同灾民受灾严重程度的大小不同,引入函数 iJ 表示灾民 ip 的受灾程度。
受灾程度取决于短缺物资的种类和数量,同时受灾程度也与供给物资总量有关,当物资
充足,受灾程度就相应较小。
x
假设某一时刻灾民 ip 已分到各物资的量为 1
i
、 …… ,
x
im
x
i
2
我们定义这一时刻 iJ 为:
- - 4 - -
M
j
1
J
i
4.4 分配方案的描述
j
(
t
ij
x
ij
)
, (
j
j
/
jS
)
为了说明某一时刻分配出去物资的情况,我们建立了 N×M 型矩阵 B:
B
…
这里 ijx 表示该时刻已分配给灾民 ip 物资 jM 的数量。
x
x
12
1
M
… … …
…
x
x
11
x
21
… …
x
x
ij
… …
NM
N
1
其中 B 的行向量 ic
表示该时刻灾民 ip 已分配到各种物资的数量,B 的列向量 jd
表示该时刻已分配出物资 jM 的情况。
五、模型的建立
5.1 目标函数说明
设函数 y 表示最终救灾效果,则目标函数为 max y ,
j ky 。
(1)设物资 jM 的第 k 个单位量分配给灾民 ip 之后产生的救灾效果为 ,
i
,
则由假设 2 和 3 可得
y
,
,
i j k
1
j
J k
i
1
。
(2)当物资 jM 分配该灾民 ip 的数量为 ijx 时,物资 jM 在灾民 ip 上产生的救灾效果
y
之和为 ,
i
j
,
。
y
i
,
j k
,
ijx
k
1
(3)物资 jM 全部分完后在所有灾民中产生的救灾效果之和为
y
j
N
i
1
y
,
i j
x
ij
N
i
1
k
1
y
,
,
i j k
x
ij
N
i
1
k
1
1
j
J k
i
- - 5 - -
(4)所有种物资分配完后,得到最终救灾效果为:
y
M
j
1
y
j
从而
y
ijx
M N
j
1
i
1
k
1
1
j
J
I
k
1
目标函数进一步表示为:
ijx
M N
j
1
i
1
k
1
1
j
J
I
k
1
max
5.2 约束条件
本题约束条件为:各种物资的数量有限,即物资 jM 的分配总量不大于其给供给总
量 iS ,
通过 4.4 中矩阵 B 的列向量 jd
x
ij
N
S
j
,可将约束条件表述为:
i
1
同时附加一约束条件:灾民 ip 得到物资 jM 的量不大于其需求总量 ijt ,即:
ijx ijt 。
六、模型求解
6.1 分配次序的确立
根据不同物资的优先级,对物资进行排序。考虑到实际救灾中必须优先对关键性
物资进行分配,我们按物资的优先级从大到小进行排序,之后再逐一对每种物资进行分
配。
不妨设排序后物资先后顺序为 1
M M
、 …… 。
M
M
2
6.2 物资的分配方法
按排序后的物资 1
M M
2
M
M
、 …… 的顺序逐种进行分配,假设已分配了
1j
种,现给出第种 j 物资的分配方法:
- - 6 - -
(1)设前 1j 种物资分配情况为矩阵 B’:
…
…
B
'
j
j
2,
1
21
1
…
x
x
0
0
'
1,
'
0
'
x
11
'
x
… …
… … … 0 … …
… … … 0 … …
… … … 0 … …
'
0
x
…
x
'
0
用 A’表示此时各种灾民物资短缺情况则有
…
,
N j
1
N
1
A
'
A B
'
t
12
'
11
'
21
t
11
t
21
x
x
…
…
…
x
'
21
…
… …
… …
… …
… …
t
1,
t
2,
j
1
j
1
d
j
x
1
j
x
2
j
…
T
x
Nj
(2)设对 jM 的分配方案为
量为 ijx 。
j
j
j
j
j
j
2,
1
1
1
1
'
1,
'
2,
t
1,
t
x
x
…
t
…
1,
t
…
2,
… … …
… … …
…
… … …
,即灾民 ip 分到物资 jM 的数
…
未分 jM 时,灾民 ip 的受灾程度为:
'
x
t
x
2
1
1
i
i
t
t
,
, 1
i j
j
j
i j
k
J
i
t
, 1
i j
1
j
x
,
i k
'
i
1
M
t
,
i k k
j
t
,
i j
1
k j
……
2
2
t
……
,
1
i M M
j
0
t
1
i
'
x
, 1
i j
t
,
i k
1
k
a t
,
i j
j
1
j
t
,
i k
a
1
k
k
x
,
i k
M
1
k j
t
,
i k k
当灾民 ip 得到 1 个单位物资 jM 时,产生救灾效果为:
a
j
j
,1 1
a t
ij
j
(0)
y
i
J
(
)
j
j
i
j
,
2
t
ij
- - 7 - -
此时,由于 ip 得到一个单位 jM , iJ 发生变化;当 ip 再得到一个单位 jM 时,
产生救灾效果为:
J
1
y
i
,2
j
i
,
(1)
j
j
[
a
(
t
ij
1)
j
a
]
j
j
2
(
t
ij
1)
以此类推,当得到第 ijx 个单位 jM 时,产生救灾效果为:
y
,
,
i j x
ij
2
a
j
j
(
t
,
i j
x
,
i j
1)
综上,当 ip 分到 jM 的数量为 ijx 时,产生的救灾效果之和为:
y
i
,
j
,
y
j
所以最终
[
a
j
j
2
(
t
ij
1
k
)]
2
j
)
2
j
j
(
x x
ij
ij
1)/ 2
x
ij
1
t
ij
2
j
x
ij
y
i
,
,
j k
k
1
k
(
x a
ij
。
y
i
N
j
,
i
1
即当只针对 jM 进行分配时目标函数为:
N
max
y
ij
i
1
max
y
j
约束条件为:
N
x S
ij
j
1
i
(3)MATLAB 程序直接求解
x
在分物资 jM 时,目标函数为关于 1,
。此时可直接利用 MATLAB 程序求出最优解。
x S
ij
j
x
1,
j
i
......
x
2,
x
i
,
N
j
j
j
,
条件为
1
i
的 N 元二次函数,约束
(4)利用拉个朗日乘数法继续化简
引入变量,对方程
N
i
1
(
x a
ij
2
j
)
2
j
2
j
t
ij
j
(
x x
ij
ij
1) / 2
(
- - 8 - -
N
i
1
x
ij
S
j
) 0