2020年全国大学生数学建模竞赛B题 穿越沙漠 
题目是讲玩家在不同地图下穿越沙漠，所获得的资金数要最多（大概是这个意思）。然后通过文章的描述又总结了N个约束条件。整体的思路就是对资金最大化作为目标函数在给定约束，利用具体（已知）条件，进行单目标优化。 总的分三小问： 第一问：玩家在已知每天天气条件下，对地图1和2进行路径规划。 第二问：玩家在未知每天天气条件下，对地图3和4进行路径规划。 第三问：多个玩家游戏，讨论已知天气条件（地图5）和未知天气条件（地图6）的合理决策。 每个地图在Result.xls附录中给出了具体的信息，其中包括：
地图拓扑结构，初始购买金额限值，负重限制，日期限值，不同天气对当日物资消耗的影响。 玩家总的思路就是从起点去往终点，在路途中确定当天合适的决策（移动/停留），物资不能消耗殆尽（不能饿死也不能渴死）。如果选择在矿山停留可以选择挖矿，经过村落可以通过资金进行补给，最后到达终点时使剩余资金最大化。 确定好思路后，就可以开始建模了。 主要考虑四大部分： 已知条件、决策变量、约束条件、目标函数 1.已知条件： 前两问给出了已知的天气情况，这里用w i w_iwi表示第iii天的天气：w i={ 1 2 3晴朗 高温 沙暴 w_i=\left\{ \begin{array}{c} 1\\ 2\\ 3\\ \end{array} \right. \begin{array}{c} \text{晴朗}\\ \text{高温}\\ \text{沙暴}\\ \end{array}wi=⎩⎨⎧123晴朗高温沙暴 
根据题目给出的已知信息，可以知道对应基础水和食物的消耗量分别为：p i={ 5 8 10wi = 1wi = 2wi = 3 q i={ 7 6 10wi = 1wi = 2wi = 3p_i=\left\{ \begin{array}{c} 5\\ 8\\ 10\\ \end{array} \right. \begin{array}{c} w_i=1\\ w_i=2\\ w_i=3\\ \end{array}\,\, q_i=\left\{ \begin{array}{c} 7\\ 6\\ 10\\ \end{array} \right. \begin{array}{c} w_i=1\\ w_i=2\\ w_i=3\\ \end{array}pi=⎩⎨⎧5810wi=1wi=2wi=3qi=⎩⎨⎧7610wi=1wi=2wi=3 2.决策变量： 初始食物和水的购买量：X,Y均为正整数 村落食物和水的补给量：CX,CY均为正整数 当日行动决策变量均为0-1变量：xjk i={1 第i天从地方j走向地方k0 其他 z1 i={1 停留0 行走 z2 i={1 挖矿0 不挖矿 z3 i={1 购买物资0 不购买物资x_{jk}^{i}=\left\{ \begin{array}{c} 1 \text{ 第}i\text{天从地方}j\text{走向地方}k\\ 0 \text{ 其他}\\ \end{array} \right. \\ \,\, \\ \,\,z1_i=\left\{ \begin{array}{c} 1 \text{ 停留}\\ 0 \text{ 行走}\\ \end{array} \right. \,\, \\ \,\, \\ z2_i=\left\{ \begin{array}{c} 1 \text{ 挖矿}\\ 0 \text{ 不挖矿}\\ \end{array} \right. \,\, \\ \,\, \\ z3_i=\left\{ \begin{array}{c} 1 \text{ 购买物资}\\ 0 \text{ 不购买物资}\\ \end{array} \right.xjki={1 第i天从地方j走向地方k0 其他z1i={1 停留0 行走z2i={1 挖矿0 不挖矿z3i={1 购买物资0 不购买物资 3.约束条件 物资（水和食物）的重量限制和初始资金限制： {w e i g h t = 3 X + 2 Y ⩽ 1200 c o s t = 5 X + 10 Y ⩽ 10000\left\{ \begin{array}{c} weight=3X+2Y\leqslant 1200\\ cost=5X+10Y\leqslant 10000\\ \end{array} \right.{weight=3X+2Y⩽1200cost=5X+10Y⩽10000 对于移动我们只能在相邻的区域之间进行移动，因此我们需要通过matlab对图区域之间的接壤情况列出距离矩阵di jd_{ij}dij：dij={ 1 0 区域 i 与区域 j 接壤不接壤 d_{ij}=\begin{cases} 1\\ 0\\ \end{cases}\begin{array}{c} \text{区域}i\text{与区域}j\text{接壤}\\ \text{不接壤}\\ \end{array}dij={10区域i与区域j接壤不接壤 列出距离矩阵后，对决策变量进行限制，使玩家只能在相邻区域之间进行移动：xjk i⩽djk{x_{jk}^{i}}\leqslant d_{jk}xjki⩽djk 每天的决策只能有一个，要么在某地停留要么移动，因此有约束条件：∑j=1 N∑k=1Nxjki= 1 \sum_{j=1}^N{\sum_{k=1}^N{x_{jk}^{i}}}=1j=1∑Nk=1∑Nxjki=1 首先第1天要从起点1开始出发去往某地k，于是便有：∑k=1 N x1k 1= 1 \sum_{k=1}^N{x_{1k}^{1}}=1k=1∑Nx1k1=1 其次我们需要保证路径是连续的，因此当天的出发地要是前一天的目的地：∑j=1 N xjk i =∑j=1 N xkji+1\sum_{j=1}^N{x_{jk}^{i}}\,\,=\sum_{j=1}^N{x_{kj}^{i+1}}j=1∑Nxjki=j=1∑Nxkji+1 最后需要某一天抵达终点，因此需要保证：∑i=1 n∑k=1N−1xkNi= 1 \sum_{i=1}^{n}{\sum_{\begin{array}{c} k=1 \end{array}}^{N-1}{x_{kN}^{i}}}=1i=1∑nk=1∑N−1xkNi=1 到达终点停止，若到达终点，未满30天，后面的天数则视为在终点处停留，不消耗物资，资金数也不发生变化：∑j=1 Nxj 27i −x2727i+1= 0 \sum_{j=1}^N{x_{j\,\,27}^{i}-x_{27 27}^{i+1}}=0j=1∑Nxj27i−x2727i+1=0 如果第iii天想在某地jjj停留则可以表示为：xj ji =1x_{jj}^{i}=1xjji=1，那么表示停留/行走的0-1变量z1 i z1_iz1i就需要满足表达式： z1 i=∑j=1 N xjj iz1_i=\sum_{j=1}^N{x_{jj}^{i}}z1i=j=1∑Nxjji 题目给定的额外条件有： 沙暴天气一定得停留：w i−∑j=1 n xjj i⩽ 2 w_i-\sum_{j=1}^n{x_{jj}^{i}}\leqslant 2wi−j=1∑nxjji⩽2 停留矿山可以挖矿，设矿山为mmm则有： z2 i⩽xmm iz2_i\leqslant x_{mm}^{i}z2i⩽xmmi 途径村落可以购买物资，设村庄为ttt则有： z3 i⩽∑j=1 Nxtji +xjtiz3_i\leqslant \sum_{j=1}^N{x_{tj}^{i}+x_{jt}^{i}}z3i⩽j=1∑Nxtji+xjti 决策所产生的资金变化： a.挖矿收益：r i={ 0 1000 z2i = 1 z2i = 0r_i=\left\{ \begin{array}{c} 0\\ 1000\\ \end{array} \right. \begin{array}{c} z2_i=1\\ z2_i=0\\ \end{array}ri={01000z2i=1z2i=0 b.物资购买为初始地的两倍价格。 最后得出的每天资金减少量为：closs i =10cX i +20cY i −r i closs_i=10cX_i+20cY_i-r_iclossi=10cXi+20cYi−ri 剩余资金：reward i =10000−cost−∑q = 1 i − 1c l o ss qreward_i=10000-cost-\sum_{q=1}^{i-1}{closs_q}rewardi=10000−cost−∑q=1i−1clossq 决策后所剩余的水和食物必须充足，满足生存条件，同时资金限制和重量限制也需要满足：10000 − c o s t −∑q=1i−1 c l o ssq⩾ c l o ss i 1200 − w e i g h t −∑q=1i−1 w l o ssq⩾ w l o ss i\\ 10000-cost-\sum_{q=1}^{i-1}{closs_q}\geqslant closs_i \\ 1200-weight-\sum_{q=1}^{i-1}{wloss_q}\geqslant wloss_i10000−cost−q=1∑i−1clossq⩾clossi1200−weight−q=1∑i−1wlossq⩾wlossi 每天水和食物的消耗量计算公式： yX i={pibi 0 未抵达终点抵达终点 yY i={qibi 0 未抵达终点抵达终点 yX_i=\left\{ \begin{array}{c} p_ib_i\\ 0\\ \end{array} \right. \,\,\begin{array}{c} \,\,\text{未抵达终点}\\ \text{抵达终点}\\ \end{array}\,\,yY_i=\left\{ \begin{array}{c} q_ib_i\\ 0\\ \end{array} \right. \begin{array}{c} \,\,\text{未抵达终点}\\ \text{抵达终点}\\ \end{array}yXi={pibi0未抵达终点抵达终点yYi={qibi0未抵达终点抵达终点 其中倍数b i b_ibi的计算公式为：b i={ 1 2 3停留 移动 挖矿 b_i=\left\{ \begin{array}{c} 1\\ 2\\ 3\\ \end{array} \right. \begin{array}{c} \text{停留}\\ \text{移动}\\ \text{挖矿}\\ \end{array}bi=⎩⎨⎧123停留移动挖矿 4.目标函数： 剩余物资半价回收处理： max f = r e w a rd 30+ 5 f o od 30+ 2.5 w a t er 30\max f=reward_{30}+5food_{30}+2.5water_{30}maxf=reward30+5food30+2.5water30 LINGO编程求解：