CC BY 4.0 （除特别声明或转载文章外）
题目：
考虑如下的小游戏：玩家凭借一张地图，利用初始资金购买一定数量的水和食物（包括食品和其他日常用品），从起点出发，在沙漠中行走。途中会遇到不同的天气，也可在矿山、村庄补充资金或资源，目标是在规定时间内到达终点，并保留尽可能多的资金。
游戏的基本规则如下：
（1）以天为基本时间单位，游戏的开始时间为第0天，玩家位于起点。玩家必须在截止日期或之前到达终点，到达终点后该玩家的游戏结束。
（2）穿越沙漠需水和食物两种资源，它们的最小计量单位均为箱。每天玩家拥有的水和食物质量之和不能超过负重上限。若未到达终点而水或食物已耗尽，视为游戏失败。
（3）每天的天气为“晴朗”、“高温”、“沙暴”三种状况之一，沙漠中所有区域的天气相同。
（4）每天玩家可从地图中的某个区域到达与之相邻的另一个区域，也可在原地停留。沙暴日必须在原地停留。
（5）玩家在原地停留一天消耗的资源数量称为基础消耗量，行走一天消耗的资源数量为基础消耗量的倍。
（6）玩家第0天可在起点处用初始资金以基准价格购买水和食物。玩家可在起点停留或回到起点，但不能多次在起点购买资源。玩家到达终点后可退回剩余的水和食物，每箱退回价格为基准价格的一半。
（7）玩家在矿山停留时，可通过挖矿获得资金，挖矿一天获得的资金量称为基础收益。如果挖矿，消耗的资源数量为基础消耗量的倍；如果不挖矿，消耗的资源数量为基础消耗量。到达矿山当天不能挖矿。沙暴日也可挖矿。
（8）玩家经过或在村庄停留时可用剩余的初始资金或挖矿获得的资金随时购买水和食物，每箱价格为基准价格的2倍。 请根据游戏的不同设定，建立数学模型，解决以下问题。
假设只有一名玩家，在整个游戏时段内每天天气状况事先全部已知，试给出一般情况下玩家的最优策略，求出最优情况下的资金剩余量。
参数设定：
负重上限：1200kg
初始资金：10000元
基础收益：1000元
截止日期：第30天
各物资的信息：
| 资源 | 每箱质量（千克） | 基准价格（元/箱） |
|---|---|---|
| 水 | 3 | 5 |
| 食物 | 2 | 10 |
各物资的基础消耗量：
| 晴朗 | 高温 | 沙暴 | |
|---|---|---|---|
| 水 | 5 | 8 | 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 |
| 天气 | 晴朗 | 晴朗 | 高温 | 晴朗 | 沙暴 | 高温 | 晴朗 | 晴朗 | 高温 | 高温 |
地图：
符号定义
常量
为了描述问题中出现的各类主体，定义常量如下：
- $T$：游戏的总天数，即截止日期
- $N$：地图上的区域个数
- $K$：资源种数
- $M$：足够大的数字
- $L$：玩家的负重上限
- $J$：初始资金
决策变量
根据问题描述和Result.xlsx中的要求，需要进行决策的变量为行走路线（每日所在的位置）和每日的资源购买量；进一步的，需要通过资源购买量和是否挖矿，得出下一日的剩余资金
因此，我们需要定义表示第t天的位置状态、资源购买状态和挖矿状态的决策变量；此外，当日的资源消耗量和挖矿状态都依赖于玩家是否选择停留在原地，所以还需要定义一个表示停留或行动状态的决策变量
-
$x_{t,i}$：0-1变量，表示第$t$天是否到达第$i$个区域，$t = 0,1,…,T$，$i = 1,2,…,N$
-
$y_{t,i}$：0-1变量，第$t$天是否在第$i$个区域停留，$t = 1,2,…,T$，$i = 1,2,…,N$
-
$z_{t,k}$：整数变量，第$t$天购买第$k$种资源的数量，$t = 0,1,2,…,T$，$k = 1,2,…,K$
-
$w_t$：0-1变量，第$t$天是否挖矿，$t = 1,2,…,T$
注意：设置整数变量$x_t$表示第$t$天所在的区域似乎是一个更直观的做法。需要指出的是，这样的设置并不能充分地表达题目所需的状态信息。在需要表示如“只能到达相邻区域”这样的约束时，此种决策变量的定义方法是无法做到的。
参数
为了进行资源补给和挖矿的决策，我们需要的题给参数有：
-
$W_k$：第$k$种资源的单位重量，$k = 1,2,…,K$
-
$P_k$：第$k$种资源的单位价格，$k = 1,2,…,K$
-
$A_{t,k}$：第$t$天第$k$种资源的基础消耗量，$t = 1,2,…,T$，$k = 1,2,…,K$
-
$D_{i,k}$：第$i$个区域是否可以购买第$k$种资源，$i = 1,2,…,N$，$k = 1,2,…,K$ 在进行前进路线的决策时，我们受到的约束有：只能去往相邻的区域，沙暴天气不能前进。需要的题给参数有：
-
$B$：沙暴天气集合
-
$E_i$：第$i$个区域是否为矿山，$i = 1,2,…,N$
-
$F_i$：第$i$个区域是否为终点，$i = 1,2,…,N$
-
$G_i$：第$i$个区域采矿的收益，$i = 1,2,…,N$
-
$H_{i,j}$：第$i$个区域和第$j$个区域是否相邻，$i = 1,2,…,N$，$j = 1,2,…,N$
模型约束
定义中间变量，用于辅助建模
- $a_{t,k}$：第$t$天是否到达第$k$个资源点，$t=0,1,…,T$; $k=1,2,…,K$
- $b_t$：第$t$天是否可以挖矿，$t=1,2,…,T$
- $d_t$：第$t$天是否到达终点，$t=0,1,…,T$
- $g_t$：第$t$天挖矿的收益，$t=1,2,…,T$
- $u_{t,k}$：第$t$天购买资源前资源的数量，$t=0,1,2,…,T$; $k=1,2,…,K$
- $v_{t,k}$：第$t$天购买资源后资源的数量，$t=0,1,2,…,T$; $k=1,2,…,K$
- $s_t$：第$t$天剩余金额的数量，$t=0,1,…,T$
各约束表达如下：
-
第$t$个状态点是否到达第$k$个资源点的数学表达：
\[a_{t,k} = \sum_{i=1}^{N} x_{t,i} D_{i,k}, \quad t = 0,1,…,T; \, k = 1,2,…,K\]
如果第$t$天到达第$i$个区域并且第$i$个区域是第$k$个资源的购买点，那么第$t$天可以购买第$k$种资源 -
第$t$天是否可以挖矿的数学表达：
\[b_t = \sum_{i=1}^{N} y_{t,i} E_i, \quad t = 1,2,…,T\]
如果第$t$天停留在第$i$个区域并且第$i$个区域是矿山，那么第$t$天可以挖矿 -
第$t$个状态点是否到达终点的数学表达：
\[d_t = \sum_{i=1}^{N} x_{t,i} F_i, \quad t = 0,1,…,T\]
如果第$t$天到达第$i$个区域并且第$i$个区域是终点，那么第$t$天到达了终点 -
第$t$天的挖矿收益：
\[g_t = \sum_{i=1}^{N} y_{t,i} E_i G_i\]
第$t$天停留在第$i$个区域，并且第$i$个区域是矿山，则乘以矿山第$i$个点的采矿收益 -
起始状态在第1个区域：
\[x_{0,1} = 1\] -
最后一天必须到达终点：
\[x_{T,N} = 1\] -
每天只能在一个区域：
\[\sum_{i=1}^{N} x_{t,i} = 1, \quad t = 0,1,…,T\] -
相邻两天区域必须相邻：
\[x_{t,i} + x_{t-1,j} \leq H_{i,j} + 1, \quad t = 1,2,…,T; \, i = 1,2,…,N; \, j = 1,2,…,N\] -
购买前资源剩余量必须大于0（生存条件）：
\[u_{t,k} \geq 0, \quad t = 0,1,…,T; \, k = 1,2,…,K\] -
购买后资源满足负重约束：
\[\sum_{k=1}^{K} v_{t,k} W_k \leq L, \quad t = 0,1,…,T\] -
沙暴天必须停留：
\[\sum_{i=1}^{N} y_{t,i} = 1, \quad \forall t \in B\] -
满足挖矿条件才能挖矿：
\[w_t \leq b_t, \quad t = 1,2,…,T\] -
只有在资源点才可以购买资源：
\[z_{t,k} \leq M a_{t,k}, \quad t = 1,2,…,T; \, k = 1,2,…,K\] -
到达终点不能再返回：
\[d_t \leq d_{t+1}, \quad t = 0,1,…,T-1\] -
第$t$天在第$i$个区域停留的条件为：
\[y_{t,i} = x_{t-1,i} x_{t,i}, \quad t = 1,2,…,T; \, i = 1,2,…,N\]
第$t-1$天和第$t$天都在第$i$个区域线性化约束：
\[y_{t,i} \leq x_{t,i}, \quad y_{t,i} \leq x_{t-1,i}, \quad x_{t,i} + x_{t-1,i} \leq y_{t,i} + 1\] -
剩余资源量的状态转移方程：
\[u_{t,k} = v_{t-1,k} - (2w_t - \sum_{i=1}^N y_{t,i} + 2 - d_{t-1}) A_{t,k}, \quad t = 1,2,…,T; \, k = 1,2,…,K\]
第$t$天购买前的资源量（$u_{t,k}$）为第$t-1$天的剩余量（$v_{t-1,k}$）减去相应倍数的基础消耗量（$A_{t,k}$）
注意$\sum_{i=1}^N y_{t,i}$表示是否停留在原地，行走会消耗2倍的基础消耗量；$w_t$表示是否挖矿，挖矿会消耗3倍的基础消耗量；$d_t$表示是否到达终点
用待定系数法可求得各参数前的系数 -
购买后资源的剩余量等于购买前的量加上购买量：
\[v_{t,k} = u_{t,k} + z_{t,k}, \quad t = 0,1,…,T; \, k = 1,2,…,K\] -
初始购买前资源量为0：
\[u_{0,k} = 0, \quad k = 1,2,…,K\] -
初始资金在购买物资后的剩余量计算：
\[s_0 = J - \sum_{k=1}^K z_{0,k} P_k\] -
每天的剩余资金计算：
\[s_t = s_{t-1} + g_t w_t - 2 \sum_{k=1}^K z_{t,k} P_k, \quad t = 1,2,…,T\]
目标函数
目标为走到终点，且最终资金尽量多。最终资金包括了走到终点时的剩余资金，以及剩余资源的退回价值，即：
\[\max \left( s_T + 0.5 \sum_{k=1}^K v_{T,k} P_k \right)\]转载自CORIDM
代码:穿越沙漠代码