国赛建模题 2020B-穿越沙漠 第一关模型求解
原题连接
因为这年的比赛题目内有道题数据量很大，不方便直接下原题查看，这里就重述一遍题目，看题解请直接跳转题解。
题目重述
背景
考虑如下的小游戏：玩家凭借一张地图，利用初始资金购买一定数量的水和食物（包括食品和其他日常用品），从起点出发，在沙漠中行走。途中会遇到不同的天气，也可在矿山、村庄补充资金或资源，目标是在规定时间内到达终点，并保留尽可能多的资金。
游戏的基本规则
- 以天为基本时间单位，游戏的开始时间为第 0 天，玩家位于起点。玩家必须在截止日期或之前到达终点，到达终点后该玩家的游戏结束。
? - 穿越沙漠需水和食物两种资源，它们的最小计量单位均为箱。每天玩家拥有的水和食物质量之和不能超过负重上限。若未到达终点而水或食物已耗尽，视为游戏失败。
? - 每天的天气为“晴朗”、“高温”、“沙暴”三种状况之一，沙漠中所有区域的天气相同。
? - 每天玩家可从地图中的某个区域到达与之相邻的另一个区域，也可在原地停留。沙暴日必须在原地停留。
? - 玩家在原地停留一天消耗的资源数量称为基础消耗量，行走一天消耗的资源数量为基础消耗量的 2 倍。
? - 玩家第 0 天可在起点处用初始资金以基准价格购买水和食物。玩家可在起点停留或回到起点，但不能多次在起点购买资源。玩家到达终点后可退回剩余的水和食物，每箱退回价格为基准价格的一半。
? - 玩家在矿山停留时，可通过挖矿获得资金，挖矿一天获得的资金量称为基础收益。如果挖矿，消耗的资源数量为基础消耗量的 3 倍；如果不挖矿，消耗的资源数量为基础消耗量。到达矿山当天不能挖矿。沙暴日也可挖矿。
? - 玩家经过或在村庄停留时可用剩余的初始资金或挖矿获得的资金随时购买水和食物，每箱价格为基准价格的 2 倍。
第一问
假设只有一名玩家，在整个游戏时段内每天天气状况事先全部已知，试给出一般情况下玩家的最优策略。
图1 第一关地图
?
参数设定:
| 负重上限 | 1200千克 | 初始资金 | 10000元 | ||
|---|---|---|---|---|---|
| 截止日期 | 第30天 | 基础收益 | 1000元 | ||
| 资源 | 每箱质量 （千克） | 基准价格 （元/箱） | 基础消耗量（箱） | ||
| 晴朗 | 高温 | 沙暴 | |||
| 水 | 3 | 5 | 5 | 8 | 10 |
| 食物 | 2 | 10 | 7 | 6 | 10 |
?
天气情况：
| 日期 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 天气 | 高温 | 高温 | 晴朗 | 沙暴 | 晴朗 | 高温 | 沙暴 | 晴朗 | 高温 | 高温 |
| 日期 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| 天气 | 沙暴 | 高温 | 晴朗 | 高温 | 高温 | 高温 | 沙暴 | 沙暴 | 高温 | 高温 |
| 日期 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
| 天气 | 晴朗 | 晴朗 | 高温 | 晴朗 | 沙暴 | 高温 | 晴朗 | 晴朗 | 高温 | 高温 |
题目解析
决策变量
核心决策变量是玩家在第
i
i
i 天是否停留在第
j
j
j 号区域，类型为0-1变量。
这里的第
i
i
i 天停留区域是指玩家在这一天内的全部行动结束后，还未进入第二天前所停留的区域。
符号说明
为了更好的表述题意，模型符号的命名不采用规范命名。
| 符号名称 | 描述 | 备注 |
|---|---|---|
| f i , j f_{i,j} fi,j? | 玩家第 i i i 天是否停留在第 j j j 号区域 | 0-1 变量，停留在 j j j 区域 = 1，停留在 j j j 以外 = 0 |
| b w i bw_i bwi? | 第 i i i 天的水基础消耗量 | 整数变量，单位：箱 |
| b f i bf_i bfi? | 第 i i i 天的食物基础消耗量 | 整数变量，单位：箱 |
| t i t_i ti? | 第 i i i 天的天气 | 整数变量，晴朗 = 1，高温 = 2，沙暴 = 3 |
| w a t e r i water_i wateri? | 玩家第 i i i 天行动完后剩余水量 | 整数变量，单位：箱 |
| f o o d i food_i foodi? | 玩家第 i i i 天行动完后剩余食物量 | 整数变量，单位：箱 |
| m o n e y i money_i moneyi? | 玩家第 i i i 天行动完后剩余资金 | 整数变量，单位：元 |
| m i n e i mine_i minei? | 玩家第 i i i 天是否挖矿 | 0-1 变量，挖矿 = 1，不挖 = 0 |
| w a l k i walk_i walki? | 玩家第 i i i 天是否行走 | 0-1 变量，行走 = 1，不走 = 0 |
| w c o s t i wcost_i wcosti? | 玩家第 i i i 天需要消耗的水量 | 整数变量，单位：箱 |
| f c o s t i fcost_i fcosti? | 玩家第 i i i 天需要消耗的食物量 | 整数变量，单位：箱 |
| D i , j D_{i,j} Di,j? | 表示区域 i i i 与区域 j j j 是否相邻 | 0-1变量，相邻 = 1，不相邻 = 0 |
| w b u y i wbuy_i wbuyi? | 玩家第 i i i 天行动结束后购买的水量 | 整数变量，单位：箱 |
| f b u y i fbuy_i fbuyi? | 玩家第 i i i 天行动结束后购买的食物量 | 整数变量，单位：箱 |
| m i m_i mi? | 地图上第 i i i 个村庄的地区编号 | 整数变量，由每关地图决定 |
| n i n_i ni? | 地图上第 i i i 个矿山的地区编号 | 整数变量，由每关地图决定 |
| a a a | 地图上矿山的数量 | 整数变量，由每关地图决定 |
| m w mw mw | 每箱水的质量 | 整数常量，单位：千克 |
| m f mf mf | 每箱食物的质量 | 整数常量，单位：千克 |
| M M M | 初始资金数 | 整数常量，单位：元 |
| c w cw cw | 每箱水的基准价格 | 整数常量，单位：元/箱 |
| c f cf cf | 每箱食物的基准价格 | 整数常量，单位：元/箱 |
| d l dl dl | 游戏截止日期 | 整数常量，单位：天 |
| l m lm lm | 玩家负重上限 | 整数常量，单位：千克 |
| e a ea ea | 挖矿一次基础收益 | 整数常量，单位：元 |
?
约束条件分析
游戏中的天数从第 0 天开始，模型在运行过程中不能是用 0 下标，统一将游戏天数推迟一天，改为第 1 天在起点做准备，游戏从第 2 天正式开始，截止日期变更为第 d l + 1 dl + 1 dl+1 天。
玩家第一天购买物资约束
玩家第 1 天位于1号区域：
f
1
,
1
=
1
f_{1,1} = 1
f1,1?=1
?
玩家第 1 天要在其实起始区域做准备，不能行走：
w
a
l
k
1
=
0
walk_1 = 0
walk1?=0
?
第 1 天购买的水和食物即为初始物资：
{
w
b
u
y
1
=
w
a
t
e
r
1
f
b
u
y
1
=
f
o
o
d
1
\begin{cases} & wbuy_1 = water_1 \\ & fbuy_1 = food_1 \\ \end{cases}
{?wbuy1?=water1?fbuy1?=food1??
?
玩家第一天购买的物资总花费不能大于初始资金：
c
w
×
w
b
u
y
1
+
c
f
×
f
b
u
y
1
<
=
M
cw \times wbuy_1 + cf \times fbuy_1 <= M
cw×wbuy1?+cf×fbuy1?<=M
?
玩家在第 1 天的剩余资金为初始资金减去购置物资的花费：
m
o
n
e
y
1
=
M
?
c
w
×
w
b
u
y
1
?
c
f
×
f
b
u
y
1
money_1 = M - cw \times wbuy_1 - cf \times fbuy_1
money1?=M?cw×wbuy1??cf×fbuy1?
?
玩家行走约束
从第 2 天开始，如果玩家某一天在某个区域，则必须保证玩家前一天的位置在该区域的相邻区域之中：
f
i
,
j
<
=
∑
k
=
1
27
f
i
?
1
,
k
×
D
k
,
j
(
i
=
2..31
,
j
=
1..27
)
f_{i,j} <= \sum_{k = 1}^{27} f_{i-1,k} \times D_{k,j} \quad (i = 2..31, j = 1..27)
fi,j?<=k=1∑27?fi?1,k?×Dk,j?(i=2..31,j=1..27)
?
同时，从第 2 天开始，如果玩家这一天行走了，则玩家当天停留区域与前一天不可以一样：
∑
j
=
1
27
f
i
?
1
,
j
×
f
i
,
j
=
1
?
w
a
l
k
i
(
i
=
2..31
)
\sum_{j = 1}^{27} f_{i - 1, j} \times f_{i, j} = 1 - walk_i \quad (i = 2..31)
j=1∑27?fi?1,j?×fi,j?=1?walki?(i=2..31)
?
当天天气为沙暴
t
i
=
3
t_i = 3
ti?=3 的话，就不能行走：
w
a
l
k
i
<
=
1
?
?
t
i
3
?
(
i
=
2..31
)
walk_i <= 1 - \lfloor \frac{t_i}{3} \rfloor \quad (i = 2..31)
walki?<=1??3ti???(i=2..31)
?
玩家挖矿约束
玩家在第
i
i
i 天挖矿的话，必须保证前一天和这一天都停留在同一个矿山，
n
j
n_j
nj? 为第
j
j
j 个矿山的地区编号，矿山数量为
a
a
a ：
∑
j
=
1
a
f
i
?
1
,
n
j
×
f
i
,
n
j
>
=
m
i
n
e
i
(
i
=
2..31
)
\sum_{j = 1}^a f_{i - 1, n_j} \times f_{i, n_j} >= mine_{i} \quad (i = 2..31)
j=1∑a?fi?1,nj??×fi,nj??>=minei?(i=2..31)
?
玩家购买约束
玩家经过或在村庄停留时可用剩余的初始资金或挖矿获得的资金随时购买水和食物，每箱价格为基准价格的 2 倍 （玩家购买物资的时刻是当天所有行动结束后）。
当玩家在第 i i i 天选择购买物资时，当天的停留地点必须为村庄， m j m_j mj? 为第 j j j 个村庄的编号， b b b 为村庄数量 （这里的停留不是绝对停留，比如题目规定玩家经过村庄时也可以购买物资，但是玩家的行动力是每天最多移动一个区域，那么在玩家移动到下一个区域前，玩家必须停留在某个区域，所以玩家经过村庄也是可以表达为某天行动结束后必须停留在村庄区域）。
当购买的物资总数大于 0 时，需要满足：（这里
∞
\infty
∞ 是一个比玩家一天能购买的水和食物的最大值总和还要大的常数即可）
w
b
u
y
i
+
f
b
u
y
i
<
=
∞
×
∑
j
=
1
b
f
i
,
m
j
(
i
=
2..31
)
wbuy_i + fbuy_i <= \infty \times \sum_{j = 1}^b f_{i, m_j} \quad (i = 2..31)
wbuyi?+fbuyi?<=∞×j=1∑b?fi,mj??(i=2..31)
?
玩家当天购买的花费要小于等于前一天的剩余资金：
2
?
(
c
w
?
w
b
u
y
i
+
c
f
?
f
b
u
y
i
)
<
=
m
o
n
e
y
i
?
1
(
i
=
2..31
)
2 * (cw * wbuy_i + cf * fbuy_i) <= money_{i - 1} \quad (i = 2..31)
2?(cw?wbuyi?+cf?fbuyi?)<=moneyi?1?(i=2..31)
?
玩家的负重约束
玩家的每天的物资总负重不能超过负重上限：
m
w
×
w
a
t
e
r
i
+
m
f
×
f
o
o
d
i
<
=
l
m
(
i
=
1..31
)
mw \times water_i + mf \times food_i <= lm \quad (i = 1..31)
mw×wateri?+mf×foodi?<=lm(i=1..31)
?
玩家的行走和挖矿矛盾约束
玩家当天行走的话，就不能挖矿：
w
a
l
k
i
<
=
1
?
m
i
n
e
i
(
i
=
2..31
)
walk_i <= 1 - mine_i \quad (i = 2..31)
walki?<=1?minei?(i=2..31)
?
玩家的资源约束
?
从第二天开始，消耗约束如下：
?
玩家每天消耗 （玩家在原地停留一天消耗的资源数量称为基础消耗量，行走一天消耗的资源数量为基础消耗量的 2 倍；如果挖矿，消耗的资源数量为基础消耗量的 3 倍）：
{
w
c
o
s
t
i
=
b
w
i
×
(
1
+
w
a
l
k
i
+
2
×
m
i
n
e
i
)
(
i
=
2..31
)
f
c
o
s
t
i
=
b
f
i
×
(
1
+
w
a
l
k
i
+
2
×
m
i
n
e
i
)
(
i
=
2..31
)
\begin{cases} & wcost_i = bw_i \times (1 + walk_i + 2 \times mine_i) \quad & (i = 2..31) \\ & fcost_i = bf_i \times (1 + walk_i + 2 \times mine_i) \quad & (i = 2..31) \\ \end{cases}
{?wcosti?=bwi?×(1+walki?+2×minei?)fcosti?=bfi?×(1+walki?+2×minei?)?(i=2..31)(i=2..31)?
?
玩家每天的消耗必须小于等于前一天剩余的资源数：
{
w
c
o
s
t
i
<
=
w
a
t
e
r
i
?
1
(
i
=
2..31
)
f
c
o
s
t
i
<
=
f
o
o
d
i
?
1
(
i
=
2..31
)
\begin{cases} & wcost_i <= water_{i - 1} \quad & (i = 2..31) \\ & fcost_i <= food_{i - 1} \quad & (i = 2..31) \\ \end{cases}
{?wcosti?<=wateri?1?fcosti?<=foodi?1??(i=2..31)(i=2..31)?
?
玩家停留后的剩余资源数，为前一天的剩余资源减去消耗的，再加上购买的资源
{
w
a
t
e
r
i
=
w
a
t
e
r
i
?
1
?
w
c
o
s
t
i
+
w
b
u
y
i
(
i
=
2..31
)
f
o
o
d
i
=
f
o
o
d
i
?
1
?
f
c
o
s
t
i
+
f
b
u
y
i
(
i
=
2..31
)
\begin{cases} & water_i = water_{i - 1} - wcost_i + wbuy_i \quad & (i = 2..31) \\ & food_i = food_{i - 1} - fcost_i + fbuy_i \quad & (i = 2..31) \\ \end{cases}
{?wateri?=wateri?1??wcosti?+wbuyi?foodi?=foodi?1??fcosti?+fbuyi??(i=2..31)(i=2..31)?
?
玩家的剩余资金数为前一天剩余资金减去购买花费加上挖矿所得：（实际上购买和挖矿不能同时进行，因为村庄和矿山不会出现在同个地点）
m
o
n
e
y
i
=
m
o
n
e
y
i
?
1
?
2
?
(
c
w
×
w
b
u
y
i
+
c
f
×
f
b
u
y
i
)
+
e
a
×
m
i
n
e
i
(
i
=
2..31
)
money_i = money_{i - 1} - 2 * (cw \times wbuy_i + cf \times fbuy_i) + ea \times mine_i \quad (i = 2..31)
moneyi?=moneyi?1??2?(cw×wbuyi?+cf×fbuyi?)+ea×minei?(i=2..31)
?
除了到达终点的那天，玩家沿途停留时，水与食物的剩余数都不能为 0 ：
{
w
a
t
e
r
i
>
=
∑
j
=
1
26
f
i
,
j
(
i
=
1..31
)
f
o
o
d
i
>
=
∑
j
=
1
26
f
i
,
j
(
i
=
1..31
)
\begin{cases} & water_i >= \sum_{j = 1}^{26} f_{i, j} & \quad (i = 1..31) \\ \\ & food_i >= \sum_{j = 1}^{26} f_{i, j} & \quad (i = 1..31) \\ \end{cases}
???????wateri?>=∑j=126?fi,j?foodi?>=∑j=126?fi,j??(i=1..31)(i=1..31)?
?
玩家停留约束
玩家每天仅能停留在一个区域：
∑
j
=
1
27
f
i
,
j
<
=
1
(
i
=
1..31
)
\sum_{j = 1}^{27} f_{i, j} <= 1 \quad (i = 1..31)
j=1∑27?fi,j?<=1(i=1..31)
?
玩家停留在终点有且仅有一天
∑
i
=
1
31
f
i
,
27
=
1
\sum_{i = 1}^{31} f_{i, 27} = 1
i=1∑31?fi,27?=1
?
终点资源约束
为了取得收益最大化，约束玩家在终点时的剩余物资量为 0：（这里
∞
\infty
∞ 是一个比玩家一天能持有的水和食物的最大值总和还要大的常数即可）
w
a
t
e
r
i
+
f
o
o
d
i
<
=
(
1
?
f
i
,
27
)
×
∞
(
i
=
1..31
)
water_i + food_i <= (1 - f_{i, 27}) \times \infty \quad (i = 1..31)
wateri?+foodi?<=(1?fi,27?)×∞(i=1..31)
?
目标函数
模型目标为玩家在终点是的剩余资金最大：
M
a
x
z
=
∑
i
=
1
31
(
f
i
,
27
×
m
o
n
e
y
i
+
1
2
×
(
c
w
?
w
a
t
e
r
i
+
c
f
?
f
o
o
d
i
)
)
Max \quad z = \sum_{i = 1}^{31} (f_{i, 27} \times money_i + \frac{1}{2} \times (cw * water_i + cf * food_i))
Maxz=i=1∑31?(fi,27?×moneyi?+21?×(cw?wateri?+cf?foodi?))
?
总模型
M a x z = ∑ i = 1 31 ( f i , 27 × m o n e y i + 1 2 × ( c w ? w a t e r i + c f ? f o o d i ) ) s . t . { f 1 , 1 = 1 w a l k 1 = 0 w b u y 1 = w a t e r 1 f b u y 1 = f o o d 1 c w × w b u y 1 + c f × f b u y 1 < = M m o n e y 1 = M ? c w × w b u y 1 ? c f × f b u y 1 f i , j < = ∑ k = 1 27 f i ? 1 , k × D k , j ( i = 2..31 , j = 1..27 ) ∑ j = 1 27 f i ? 1 , j × f i , j = 1 ? w a l k i ( i = 2..31 ) w a l k i < = 1 ? ? t i 3 ? ( i = 2..31 ) ∑ j = 1 a f i ? 1 , n j × f i , n j > = m i n e i ( i = 2..31 ) w b u y i + f b u y i < = ∞ × ∑ j = 1 b f i , m j ( i = 2..31 ) 2 ? ( c w ? w b u y i + c f ? f b u y i ) < = m o n e y i ? 1 ( i = 2..31 ) m w × w a t e r i + m f × f o o d i < = l m ( i = 1..31 ) w a l k i < = 1 ? m i n e i ( i = 2..31 ) w c o s t i = b w i × ( 1 + w a l k i + 2 × m i n e i ) ( i = 2..31 ) f c o s t i = b f i × ( 1 + w a l k i + 2 × m i n e i ) ( i = 2..31 ) w c o s t i < = w a t e r i ? 1 ( i = 2..31 ) f c o s t i < = f o o d i ? 1 ( i = 2..31 ) w a t e r i = w a t e r i ? 1 ? w c o s t i + w b u y i ( i = 2..31 ) f o o d i = f o o d i ? 1 ? f c o s t i + f b u y i ( i = 2..31 ) m o n e y i = m o n e y i ? 1 ? 2 ? ( c w × w b u y i + c f × f b u y i ) + e a × m i n e i ( i = 2..31 ) w a t e r i > = ∑ j = 1 26 f i , j ( i = 1..31 ) f o o d i > = ∑ j = 1 26 f i , j ( i = 1..31 ) ∑ j = 1 27 f i , j < = 1 ( i = 1..31 ) ∑ i = 1 31 f i , 27 = 1 w a t e r i + f o o d i < = ( 1 ? f i , 27 ) × ∞ ( i = 1..31 ) Max \quad z = \sum_{i = 1}^{31} (f_{i, 27} \times money_i + \frac{1}{2} \times (cw * water_i + cf * food_i)) \\ s.t. \begin{cases} & f_{1,1} = 1 \\ & walk_1 = 0 \\ & wbuy_1 = water_1 \\ & fbuy_1 = food_1 \\ & cw \times wbuy_1 + cf \times fbuy_1 <= M \\ & money_1 = M - cw \times wbuy_1 - cf \times fbuy_1 \\ & f_{i,j} <= \sum_{k = 1}^{27} f_{i-1,k} \times D_{k,j} \quad & (i = 2..31, j = 1..27) \\ & \sum_{j = 1}^{27} f_{i - 1, j} \times f_{i, j} = 1 - walk_i \quad & (i = 2..31) \\ & walk_i <= 1 - \lfloor \frac{t_i}{3} \rfloor \quad & (i = 2..31) \\ & \sum_{j = 1}^a f_{i - 1, n_j} \times f_{i, n_j} >= mine_{i} \quad & (i = 2..31) \\ & wbuy_i + fbuy_i <= \infty \times \sum_{j = 1}^b f_{i, m_j} \quad & (i = 2..31) \\ & 2 * (cw * wbuy_i + cf * fbuy_i) <= money_{i - 1} \quad & (i = 2..31) \\ & mw \times water_i + mf \times food_i <= lm \quad & (i = 1..31) \\ & walk_i <= 1 - mine_i \quad & (i = 2..31) \\ & wcost_i = bw_i \times (1 + walk_i + 2 \times mine_i) \quad & (i = 2..31) \\ & fcost_i = bf_i \times (1 + walk_i + 2 \times mine_i) \quad & (i = 2..31) \\ & wcost_i <= water_{i - 1} \quad & (i = 2..31) \\ & fcost_i <= food_{i - 1} \quad & (i = 2..31) \\ & water_i = water_{i - 1} - wcost_i + wbuy_i \quad & (i = 2..31) \\ & food_i = food_{i - 1} - fcost_i + fbuy_i \quad & (i = 2..31) \\ & money_i = money_{i - 1} - 2 * (cw \times wbuy_i + cf \times fbuy_i) + ea \times mine_i \quad & (i = 2..31) \\ & water_i >= \sum_{j = 1}^{26} f_{i, j} \quad & (i = 1..31) \\ & food_i >= \sum_{j = 1}^{26} f_{i, j} \quad & (i = 1..31) \\ & \sum_{j = 1}^{27} f_{i, j} <= 1 \quad & (i = 1..31) \\ & \sum_{i = 1}^{31} f_{i, 27} = 1 \\ & water_i + food_i <= (1 - f_{i, 27}) \times \infty \quad & (i = 1..31) \\ \end{cases} Maxz=i=1∑31?(fi,27?×moneyi?+21?×(cw?wateri?+cf?foodi?))s.t.?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????f1,1?=1walk1?=0wbuy1?=water1?fbuy1?=food1?cw×wbuy1?+cf×fbuy1?<=Mmoney1?=M?cw×wbuy1??cf×fbuy1?fi,j?<=∑k=127?fi?1,k?×Dk,j?∑j=127?fi?1,j?×fi,j?=1?walki?walki?<=1??3ti???∑j=1a?fi?1,nj??×fi,nj??>=minei?wbuyi?+fbuyi?<=∞×∑j=1b?fi,mj??2?(cw?wbuyi?+cf?fbuyi?)<=moneyi?1?mw×wateri?+mf×foodi?<=lmwalki?<=1?minei?wcosti?=bwi?×(1+walki?+2×minei?)fcosti?=bfi?×(1+walki?+2×minei?)wcosti?<=wateri?1?fcosti?<=foodi?1?wateri?=wateri?1??wcosti?+wbuyi?foodi?=foodi?1??fcosti?+fbuyi?moneyi?=moneyi?1??2?(cw×wbuyi?+cf×fbuyi?)+ea×minei?wateri?>=∑j=126?fi,j?foodi?>=∑j=126?fi,j?∑j=127?fi,j?<=1∑i=131?fi,27?=1wateri?+foodi?<=(1?fi,27?)×∞?(i=2..31,j=1..27)(i=2..31)(i=2..31)(i=2..31)(i=2..31)(i=2..31)(i=1..31)(i=2..31)(i=2..31)(i=2..31)(i=2..31)(i=2..31)(i=2..31)(i=2..31)(i=2..31)(i=1..31)(i=1..31)(i=1..31)(i=1..31)?
?
问题求解
Lingo 求解
在模型下标与约束关系十分规范的情况下（本题解中的变量命名并不规范），可以直接使用 L i n g o Lingo Lingo 的建模语言来构建模型进行求解。这里用的是 L i n g o 18 Lingo 18 Lingo18 。
model:
sets:
day/1..31/: food, water, money, mine, walk, wcost, fcost, t, buyf, buyw, bf, bw,
stay;
area/1..27/;
idx3(area, area): D;
idx4(day, area): f;
endsets
data:
! 邻接矩阵;
D = @ole('E:\建模文件\mathmodeling\assets\B题数据\沙漠B题Lingo\1.xlsx', 'D');
! 每天的水基础消耗;
bw = @ole('E:\建模文件\mathmodeling\assets\B题数据\沙漠B题Lingo\2.xlsx', 'bw');
! 每天的食物基础消耗;
bf = @ole('E:\建模文件\mathmodeling\assets\B题数据\沙漠B题Lingo\2.xlsx', 'bf');
! 每天的天气;
t = @ole('E:\建模文件\mathmodeling\assets\B题数据\沙漠B题Lingo\2.xlsx', 't');
! 输出答案;
@ole('E:\建模文件\mathmodeling\assets\B题数据\沙漠B题Lingo\Result.xlsx', 'stay') = stay;
@ole('E:\建模文件\mathmodeling\assets\B题数据\沙漠B题Lingo\Result.xlsx', 'spare_money') = money;
@ole('E:\建模文件\mathmodeling\assets\B题数据\沙漠B题Lingo\Result.xlsx', 'spare_food') = food;
@ole('E:\建模文件\mathmodeling\assets\B题数据\沙漠B题Lingo\Result.xlsx', 'spare_water') = water;
! 水质量;
mw = 3;
! 食物质量;
mf = 2;
! 水基准价格;
cw = 5;
! 食物基准价格;
cf = 10;
! 负重上限;
lm = 1200;
! 初始资金;
M = 10000;
! 基础收益;
ea = 1000;
enddata
Max = @sum(day(i): f(i, 27) * (money(i) + 0.5 * (cf * food(i) + cw * water(i))));
cf * food(1) + cw * water(1) <= M;
money(1) = M - cf * food(1) - cw * water(1);
walk(1) = 0;
f(1, 1) = 1;
@for( idx4(i, j) | i #ge# 2: f(i, j) <= @sum(area(k): f(i - 1, k) * D(k, j)) );
@for( day(i) | i #ge# 2:
@sum(area(j): f(i - 1, j) * f(i, j) ) = 1 - walk(i);
f(i - 1, 12) * f(i, 12) >= mine(i);
buyf(i) + buyw(i) <= 1000 * f(i, 15);
2 * (cf * buyf(i) + cw * buyw(i)) <= money(i - 1);
walk(i) <= 1 - mine(i);
walk(i) <= 1 - @floor( t(i) / 3 );
fcost(i) = bf(i) * (1 + walk(i) + 2 * mine(i));
wcost(i) = bw(i) * (1 + walk(i) + 2 * mine(i));
fcost(i) <= food(i - 1);
wcost(i) <= water(i - 1);
food(i) = food(i - 1) - fcost(i) + buyf(i);
water(i) = water(i - 1) - wcost(i) + buyw(i);
money(i) = money(i - 1) - 2 * (cf * buyf(i) + cw * buyw(i)) + ea * mine(i);
);
@for(day(i):
mf * food(i) + mw * water(i) <= lm;
food(i) >= @sum(area(j) | j #le# 26: f(i, j) );
water(i) >= @sum(area(j) | j #le# 26: f(i, j) );
@sum(area(j): f(i, j) ) <= 1.5;
);
@sum(day(i): f(i, 27) ) = 1;
@for( idx4: @bin(f) );
@for( day:
@bin(walk); @bin(mine);
@gin(buyf); @gin(buyw);
@gin(food); @gin(water);
);
! 每天的食物最大600，水最大400;
@for(day:
0 <= food; !food * mf <= lm; food <= 600;
0 <= water; !water * mw <= lm; water <= 400;
0 <= buyf; !buyf * mf <= lm; buyf <= 600;
0 <= buyw; !buyw * mw <= lm; buyw <= 400;
);
! 终点资源清空约束;
@for(day(i): food(i) + water(i) <= (1 - f(i, 27)) * 1000 );
! 计算停留区域;
@for(day(i): stay(i) = @sum(area(j): f(i, j) * j) );
end
?
Lingo 结果
?
Lingo 第一关 10230 方案
(10230 方案不唯一)
| 日期 | 所在区域 | 剩余资金数 | 剩余水量 | 剩余食物量 |
|---|---|---|---|---|
| 0 | 1 | 4990 | 98 | 452 |
| 1 | 25 | 4990 | 82 | 440 |
| 2 | 26 | 4990 | 66 | 428 |
| 3 | 23 | 4990 | 56 | 414 |
| 4 | 23 | 4990 | 46 | 404 |
| 5 | 22 | 4990 | 36 | 390 |
| 6 | 9 | 4990 | 20 | 378 |
| 7 | 9 | 4990 | 10 | 368 |
| 8 | 15 | 3350 | 164 | 354 |
| 9 | 14 | 3350 | 148 | 342 |
| 10 | 12 | 3350 | 132 | 330 |
| 11 | 12 | 4350 | 102 | 300 |
| 12 | 12 | 5350 | 78 | 282 |
| 13 | 12 | 6350 | 63 | 261 |
| 14 | 12 | 7350 | 39 | 243 |
| 15 | 14 | 7350 | 23 | 231 |
| 16 | 15 | 7220 | 20 | 219 |
| 17 | 15 | 7220 | 10 | 209 |
| 18 | 15 | 5230 | 199 | 199 |
| 19 | 13 | 5230 | 183 | 187 |
| 20 | 12 | 5230 | 167 | 175 |
| 21 | 12 | 6230 | 152 | 154 |
| 22 | 12 | 7230 | 137 | 133 |
| 23 | 12 | 8230 | 113 | 115 |
| 24 | 12 | 9230 | 98 | 94 |
| 25 | 12 | 10230 | 68 | 64 |
| 26 | 11 | 10230 | 52 | 52 |
| 27 | 10 | 10230 | 42 | 38 |
| 28 | 9 | 10230 | 32 | 24 |
| 29 | 21 | 10230 | 16 | 12 |
| 30 | 27 | 10230 | 0 | 0 |
?
编程求解
动态规划解析
- 用（天数，区域，剩余水量，剩余食物）来表示一个解的状态
- 题目包含多种状态，某一天的最优解状态由前面已求得的状态转换而来
- 有大量的重叠状态，比如（15, 15, 133, 145）这种随机状态，可能前一天的相邻区域最优解 + 今天行走，
或者前一天当前区域最优解 + 今天停留得到，适合用动态规划记录大量重复状态 - 大的分支有
停留和行走，停留情况下可能有挖矿和购买，行走下只可能有购买 - 由此得出状态转移方程如下：
当前停留点是终点，当天不是沙暴
dp(day, point, 0, 0) =
max( dp(day - 1, 相邻点, water + 今日行走水消耗,
food + 今日行走食物消耗 ),
dp(day - 1, point, 0, 0)
);
当前点是终点, 当天是沙暴
dp(day, point, 0, 0) = dp(day - 1, point, 0, 0);
当不是终点时，当天不是沙暴
dp(day, point, water, food) =
max( dp(day - 1, 相邻点, water + 今日行走水消耗,
food + 今日行走食物消耗 ),
dp(day - 1, point, water + 今日停留水消耗,
food + 今日停留食物消耗 ),
dp(day - 1, point, water + 今日挖矿水消耗,
food + 今日挖矿食物消耗 ) + ea, 如果在矿山
dp(day - 1, point, water + 今日停留水消耗 - 购买水量,
food + 今日停留食物消耗 - 购买食物量 ) - 购买花费, 如果 point 是村庄
dp(day - 1, 相邻点, water + 今日行走水消耗 - 购买水量,
food + 今日行走食物消耗 - 购买食物量 ) - 购买花费, 如果 point 是村庄
);
C 语言实现
核心代码如下：
完整代码资源：GitHub
// ============================ 初始化全局变量 =============================
int adj_list[MAX_AREA][MAX_AREA]; // 简易邻接表，每行第一个元素记录表长度
int D[MAX_AREA][MAX_AREA]; // 邻接矩阵
int profit[MAX_DAY][MAX_AREA][MAX_WATER][MAX_FOOD]; // (day, point, water, food) 剩余资金
int path[MAX_DAY][MAX_AREA][MAX_WATER][MAX_FOOD]; // 路径记录变量
int t[MAX_DAY] = { 0, 2, 2, 1, 3, 1, 2, 3, 1, 2, 2, 3, 2, 1, 2, 2, 2, 3, 3,
2, 2, 1, 1, 2, 1, 3, 2, 1, 1, 2, 2 }; // 天气
int base_cost_water[MAX_DAY] = { 0, 8, 8, 5, 10, 5, 8, 10, 5, 8, 8, 10, 8,
5, 8, 8, 8, 10, 10, 8, 8, 5, 5, 8, 5, 10, 8, 5, 5, 8, 8 }; // 水基础消耗量
int base_cost_food[MAX_DAY] = { 0, 6, 6, 7, 10, 7, 6, 10, 7, 6, 6, 10, 6,
7, 6, 6, 6, 10, 10, 6, 6, 7, 7, 6, 7, 10, 6, 7, 7, 6, 6 }; // 食物基础消耗量
int M = 10000; // 初始资金数
int mw = 3; // 每箱水的质量
int mf = 2; // 每箱食物的质量
int cw = 5; // 每箱水的基准价格
int cf = 10; // 每箱食物的基准价格
int lm = 1200; // 玩家负重上限
int ea = 1000; // 挖矿一次基础收益
// ============================ END ============================
int main() {
_log = fopen("record.txt", "w");
// ======================== 读取文件内容 ========================
// loggin("func: resolvePath", testResolvePath() == AC ? "Accepted" : "Error");
char data_dir[COMMON_LEN] = "./data";
char data_file_path[COMMON_LEN] = "/map.csv";
char map_data_path[COMMON_LEN];
resolvePath(map_data_path, COMMON_LEN, data_dir, data_file_path);
loggin("map csv path", map_data_path);
FILE* map_csv = fopen(map_data_path, "r");
int line_len = readCSVByLine(map_csv, 2);
if (fclose(map_csv) != 0)
printf("文件 %s 关闭出错！", map_data_path);
// ======================== END ========================
// ==================== 将地图信息转换为邻接矩阵数据 ====================
takeFile2AdjacentMatrix(line_len);
matrix2List();
// print_list();
// ==================== END ====================
// ========================= 初始化表格状态 =========================
// 填充初始值
memset(profit, NO, sizeof profit);
memset(bfs_record, NO, sizeof bfs_record);
memset(path, NO, sizeof path);
bfs(1, 0);
// 计算水和食物在不同购买数量组合下的剩余资金
for (int wbuy = 0; wbuy < MAX_WATER; wbuy++) {
for (int fbuy = 0; fbuy < MAX_FOOD; fbuy++) {
// 初始资金 - 购买水量 * 水基础价格 - 购买食物量 * 食物基础价格
if (weight(wbuy, fbuy) <= lm && price(wbuy, fbuy, 1) <= M) {
profit[0][1][wbuy][fbuy] = M - price(wbuy, fbuy, 1);
}
}
}
// ========================= END =========================
// 动态规划表格法
// ========================= 开始打表 =========================
time1 = clock();
global_ans.value = -INF;
global_ans.record = NO;
dp();
// ========================= END =========================
printf("30 天游戏最优解为：%d\n", profit[30][END_POINT][0][0]);
fprintf(_log, "30 天游戏最优解为：%d\n", profit[30][END_POINT][0][0]);
// ========================= 打印答案 =========================
produceTable(global_ans.record);
struct status a = decompress(global_ans.record);
output_ans[a.day + 1][0] = a.day + 1;
output_ans[a.day + 1][1] = END_POINT;
output_ans[a.day + 1][2] = 0;
output_ans[a.day + 1][3] = 0;
puts("\n======================================\n");
fputs("\n======================================\n", _log);
for (int i = 0; i <= a.day + 1; i++) {
for (int j = 0; j < 4; j++) {
printf("%d%s", output_ans[i][j], j == 3 ? "\n" : ",\t");
fprintf(_log, "%d%s", output_ans[i][j], j == 3 ? "\n" : ",\t");
}
}
puts("\n======================================\n");
fputs("\n======================================\n", _log);
// ========================= END =========================
fclose(_log);
return 0;
}
void dp() {
int day, point, _food, _water;
int fb, wb;
int adj_len, k;
int _cost_w, _cost_f;
int water_spa, food_spa;
struct ans walk_profit, stay_profit, stay_mine_profit, walk_buy_profit, stay_buy_profit;
struct ans mid, ans;
int w1, f1;
int yes_money, today_money_cost;
float tt;
int next = 1;
int n;
for (day = 1; day < MAX_DAY; ++day) {
// 每天根据前一天的最优解更新当天的状态
for (point = 1; point < MAX_AREA; ++point) {
// 如果到达当前点的天数少于最少天数，说明不正常
if (day < bfs_record[point]) continue;
// 遍历每个点
adj_len = adj_list[point][0]; // point 邻接点数量
if (point == END_POINT) {
// 如果今天在终点结束活动
// 那么终点的最优解只可能是昨天就到达终点，以及昨天在终点的邻接点走过来
stay_profit.value = -INF;
stay_profit.record = NO;
if (profit[day - 1][point][0][0] >= 0) {
// 昨天就到达终点，游戏已经结束，没有消耗
stay_profit.value = profit[day - 1][point][0][0];
stay_profit.record = compress(day - 1, point, 0, 0);
}
walk_profit.value = -INF;
walk_profit.record = NO;
if (t[day] != SANDSTORM) {
// 今天不是沙暴才能走
// 行走两倍消耗
_cost_w = 2 * base_cost_water[day];
_cost_f = 2 * base_cost_food[day];
for (int i = 1; i <= adj_len; ++i) {
k = adj_list[point][i]; // 当前邻接点
// 由于今天到达终点，只要昨天能满足今天行走的资源消耗，
// 则其他食物组合都不是最优解
if (profit[day - 1][k][_cost_w][_cost_f] >= 0) {
mid.value = profit[day - 1][k][_cost_w][_cost_f];
mid.record = compress(day - 1, k, _cost_w, _cost_f);
walk_profit = max(2, walk_profit, mid);
}
t_dif = now();
if (t_dif > time_limit) {
goto time_out; // 求解超时
}
}
}
t_dif = now();
ans = max(2, stay_profit, walk_profit);
if (global_ans.value < ans.value) {
global_ans = ans;
}
profit[day][point][0][0] = ans.value;
path[day][point][0][0] = ans.record; // 记录前驱
if (ans.value > max_profit[point])
max_profit[point] = ans.value;
if (ans.value >= 0) {
printf("经过 %d 秒...\n", (int)t_dif);
printf("当前答案: (%d, %d, %d, %d) = %d\n", day, point, 0, 0, ans.value >= 0 ? ans.value : NO);
puts("\n======================================\n");
fprintf(_log, "经过 %d 秒...\n", (int)t_dif);
fprintf(_log, "当前答案: (%d, %d, %d, %d) = %d\n", day, point, 0, 0, ans.value >= 0 ? ans.value : NO);
fputs("\n======================================\n", _log);
}
} else {
// 今天到达的点不是终点
// 未到达终点时，玩家物资水和食物都不能为 0
for (_water = 1; _water < MAX_WATER; ++_water) {
if (weight(_water, 0) > lm) break;
for (_food = 1; _food < MAX_FOOD; ++_food) {
// 遍历今天会遇到的各种物资组合
// 超重情况
if (weight(_water, _food) > lm) break;
// 情况一，由昨天什么都不做，直接停留而来
stay_profit.value = -INF;
stay_profit.record = NO;
_cost_w = base_cost_water[day];
_cost_f = base_cost_food[day];
w1 = _water + _cost_w;
f1 = _food + _cost_f;
if (w1 < MAX_WATER && f1 < MAX_FOOD) {
if (profit[day - 1][point][w1][f1] >= 0) {
stay_profit.value = profit[day - 1][point][w1][f1];
stay_profit.record = compress(day - 1, point, w1, f1);
}
}
stay_buy_profit.value = -INF;
stay_buy_profit.record = NO;
if (point == VILIAGE) {
// 停留时，今天在村庄，可以购买物资
for (wb = 0; wb < _water; ++wb) {
for (fb = 0; fb <= _food; ++fb) {
// 昨天剩余物资
water_spa = _cost_w + (_water - wb);
food_spa = _cost_f + (_food - fb);
if (water_spa >= MAX_WATER || food_spa >= MAX_FOOD) break;
yes_money = profit[day - 1][point][water_spa][food_spa];
today_money_cost = price(wb, fb, point);
if ((yes_money >= 0) && (today_money_cost <= yes_money)) {
// 购买组合可以
mid.value = yes_money - today_money_cost;
mid.record = compress(
day - 1, point, water_spa, food_spa
);
stay_buy_profit = max(2, stay_buy_profit, mid);
}
t_dif = now();
if (t_dif > time_limit) {
goto time_out; // 求解超时
}
}
}
}
stay_mine_profit.value = -INF;
stay_mine_profit.record = NO;
if (point == MINE) {
// 停留时，今天在矿山，不挖矿就是直接停留的收益
// 挖矿 3 倍消耗
_cost_w = 3 * base_cost_water[day];
_cost_f = 3 * base_cost_food[day];
w1 = _water + _cost_w;
f1 = _food + _cost_f;
if (w1 < MAX_WATER && f1 < MAX_FOOD) {
if (profit[day - 1][point][w1][f1] >= 0) {
// 昨天可以到达矿山，今天挖矿获取收益
stay_mine_profit.value = profit[day - 1][point][w1][f1] + ea;
stay_mine_profit.record = compress(
day - 1, point, w1, f1
);
}
}
}
// 情况二，由昨天从相邻点走到当前点
walk_profit.value = -INF;
walk_profit.record = NO;
walk_buy_profit.value = -INF;
walk_buy_profit.record = NO;
if (t[day] != SANDSTORM) {
// 不为沙暴
// 行走两倍消耗
_cost_w = 2 * base_cost_water[day];
_cost_f = 2 * base_cost_food[day];
w1 = _water + _cost_w;
f1 = _food + _cost_f;
if (w1 < MAX_WATER && f1 < MAX_FOOD) {
for (int i = 1; i <= adj_len; ++i) {
k = adj_list[point][i]; // 当前邻接点
if (profit[day - 1][k][w1][f1] >= 0) {
mid.value = profit[day - 1][k][w1][f1];
mid.record = compress(day - 1, k, w1, f1);
walk_profit = max(2, walk_profit, mid);
}
if (point == VILIAGE) {
// 今天结束行走后在村庄停留，可以购买物资
for (wb = 0; wb < _water; ++wb) {
for (fb = 0; fb <= _food; ++fb) {
// 昨天剩余物资
water_spa = _cost_w + (_water - wb);
food_spa = _cost_f + (_food - fb);
if (water_spa >= MAX_WATER || food_spa >= MAX_FOOD) break;
// 现在昨天的钱是从邻接点 K 获取，别搞错了
yes_money = profit[day - 1][k][water_spa][food_spa];
today_money_cost = price(wb, fb, point);
// 昨天状态可达以及今天消费允许时，
if ((yes_money >= 0) && (today_money_cost <= yes_money)) {
// 购买组合可以
mid.value = yes_money - today_money_cost;
mid.record = compress(
day - 1, k, water_spa, food_spa
);
walk_buy_profit = max(2, walk_buy_profit, mid);
}
}
t_dif = now();
if (t_dif > time_limit) {
goto time_out; // 求解超时
}
}
}
}
}
}
ans = max(5,
stay_profit, stay_buy_profit, stay_mine_profit,
walk_profit, walk_buy_profit);
profit[day][point][_water][_food] = ans.value;
path[day][point][_water][_food] = ans.record;
if (ans.value > max_profit[point])
max_profit[point] = ans.value;
t_dif = now();
if (t_dif > time_limit) {
goto time_out; // 求解超时
}
}
}
}
}
// 一天求解结束，打印各个地区的最大值
printf("第 %d 天：\t\t\t用时 %d 秒\n", day, (int)now());
fprintf(_log, "第 %d 天：\t\t\t用时 %d 秒\n", day, (int)now());
for (point = 1; point < MAX_AREA; point++) {
printf("(%2d, %4d)%s", point, max_profit[point],
((point) % 3 == 0 || point == MAX_AREA - 1) ? "\n" : ",");
fprintf(_log, "(%2d, %4d)%s", point, max_profit[point],
((point) % 3 == 0 || point == MAX_AREA - 1) ? "\n" : ",");
}
puts("\n======================================\n");
fputs("\n======================================\n", _log);
}
return ;
time_out:
n = (int)(now());
printf("求解超时，强制结束! 用时: %d 秒\n", n);
fprintf(_log, "求解超时，强制结束! 用时: %d\n", n);
}
?
C 语言 第一关 10460 方案
| 日期 | 所在区域 | 剩余资金数 | 剩余水量 | 剩余食物量 |
|---|---|---|---|---|
| 0 | 1 | 5790 | 178 | 332 |
| 1 | 25 | 5790 | 162 | 320 |
| 2 | 24 | 5790 | 146 | 308 |
| 3 | 23 | 5790 | 136 | 294 |
| 4 | 23 | 5790 | 126 | 284 |
| 5 | 21 | 5790 | 116 | 270 |
| 6 | 9 | 5790 | 100 | 258 |
| 7 | 9 | 5790 | 90 | 248 |
| 8 | 15 | 4150 | 244 | 234 |
| 9 | 13 | 4150 | 228 | 222 |
| 10 | 12 | 4150 | 212 | 210 |
| 11 | 12 | 5150 | 182 | 180 |
| 12 | 12 | 6150 | 158 | 162 |
| 13 | 12 | 7150 | 143 | 141 |
| 14 | 12 | 8150 | 119 | 123 |
| 15 | 12 | 9150 | 95 | 105 |
| 16 | 12 | 10150 | 71 | 87 |
| 17 | 12 | 10150 | 61 | 77 |
| 18 | 12 | 10150 | 51 | 67 |
| 19 | 12 | 11150 | 27 | 49 |
| 20 | 13 | 11150 | 11 | 37 |
| 21 | 15 | 10460 | 36 | 40 |
| 22 | 9 | 10460 | 26 | 26 |
| 23 | 21 | 10460 | 10 | 14 |
| 24 | 27 | 10460 | 0 | 0 |
?
编程求解和 Lingo 求解差异分析
最主要的是 Lingo 很难表示出游戏在到达终点后，后期不再继续的准确约束。 我自己是没能构建这个动态约束，希望能在评论区看到各路大神的精彩解答。
L i n g o Lingo Lingo 的 10230 其实是游戏刚好在第 30 天结束的最优解。而编程算是枚举全部方案，所以会比 L i n g o Lingo Lingo 好。
L i n g o Lingo Lingo 的最大优点就是求解比编程快（仅对本题来说），像本题这样多状态求解问题，第一关的编程即使用了动态规划依旧要算近一小时，而 L i n g o Lingo Lingo 只要能构建出正确的模型，不到 5 分钟就算出一个较好的答案，在时间上的优势不是编程能比得上的。当然我写的这个动态规划非常粗糙，没有很好的剪枝，这是求解慢的主要原因。
?
结语
首先本题的所有资源和代码我都放到 GitHub 这里了，感兴趣的小伙伴自行获取。
这道题总共有六关，第一关只是开胃菜。我只写了一关的题解是因为六关都是同样的基础规则，所以都是按照第一关提供的思路去探索就好。但是不是直接套用代码就能解出答案。 L i n g o Lingo Lingo 逻辑可以沿用，但是编程是要重新改进代码才行。
比如第二关，区域来到 64 个，这时的 C 语言代码已经编译不了，爆内存了。虽然我在 Linux 上可以编译运行，但是求解时间来到了每天要算 4600 秒，等算出答案，比赛都结束了。所以需要用更好的算法，比如多线程求解、蚂蚁、遗传等。
这篇题解我陆陆续续写了很久，完成时已经快开始新一年的比赛了，希望我分享的题解能成为各位参赛者成长的养分，感谢各位看到这里，比赛加油！