1947年, Fine^[4]解决了一辆吉普用起点给定的燃料穿越沙漠的问题.其中,吉普的行驶策略使用了``蚂蚁搬家"的思想:吉普带上部分燃料离开起点,在沙漠中储存车上的部分燃料后,用剩余的燃料驶回起点,重复若干次.当储存点存放了足够的燃料后,再使用相同的方式往前行驶.随后, Phipps^[9]、Alway^[1]和Gale^[5]给出了该问题的其他解法.一些相关的问题也得到了研究:1947年, Phipps^[9]研究了车队中某些吉普护送另一辆吉普的问题. 1970年, Gale^[5]考虑了多辆吉普共享燃料的情况,同时提出了另一个富有挑战性的问题:当沙漠两端都有燃料供应时,吉普穿越沙漠的策略是怎样的.这个问题于1995年由Hausrath、Jackson、Mitchem和Schmeichel共同解决^[6],他们同时研究了这个问题的一个变形:当起点处的部分燃料可被提前安放在沙漠中的任何地方时,吉普可穿越沙漠的最大长度是多少?

在探险问题和航空器排列等问题中,人们也对吉普问题感兴趣.李晓亚^[8]基于多吉普问题的算法,研究了航空器排列的一个特例. 2016年, Kuwata及Maehara^[7]所研究的远征队的问题与多吉普问题很类似.此外,吉普问题在解决星际探险、无人机运输、多级火箭和新能源汽车行驶等实际问题中可能有帮助.

为了行文方便,首先重述一些相关的问题.

问题1 (Fine^[4])  沙漠一端有一辆最多携带1单位燃料的吉普,每单位燃料可供吉普行驶1单位长度.当起点处有$y$单位燃料时,吉普在沙漠中可到达的最远距离是多少?

问题2 (Phipps^[9])  沙漠一端有一辆最多携带1单位燃料的吉普,每单位燃料可供吉普行驶1单位长度.当起点处有$y$单位燃料且行程结束后吉普需返回起点时,吉普在沙漠中可到达的最远距离是多少?

需要注意的是,在问题1和问题2中,隐含了这样的条件:燃料在沙漠中可以随意存放.而实际问题中,燃料的存放对容器有一定的要求,例如只能存放在罐子而非袋子中.这里罐子和袋子的区别在于:袋子可以折叠,在行驶过程中吉普可以携带足够多的袋子在沙漠中存放燃料；而罐子有固定的形状,吉普只能携带有限的罐子.我们对容器约束的吉普问题感兴趣,因为在航天领域和新能源交通等问题中,容器约束具有实际意义,例如航天燃料只能存放在特定装置中,电能只能存储在电池中.无容器约束的吉普问题中,当提供的燃料足够多时吉普能够穿越任意长的沙漠^[2-3],而在容器约束下,燃料的存储将受到很大影响,我们关心此时是否存在行驶策略使吉普穿越任意长的沙漠.

容器约束的吉普问题中,吉普必须携带超过1个容器,否则没有多余的容器用于在沙漠中储存燃料.我们先解决问题3和问题4,在此基础上讨论问题5和问题6并给出相应的结果.

问题3 (单向多负载) 沙漠一端有一辆最多携带$s$单位燃料的吉普,每单位燃料可供吉普行驶1单位长度.当起点处有$y$单位燃料时,吉普在沙漠中可到达的最远距离是多少?

问题4 (往返多负载)  沙漠一端有一辆最多携带$s$单位燃料的吉普,每单位燃料可供吉普行驶1单位长度.当起点处有$y$单位燃料且行程结束后吉普需返回起点时,吉普在沙漠中可到达的最远距离是多少?

问题5 (单向容器约束)  沙漠一端有一辆最多携带$s$个容器的吉普($s\ge 2$),每个容器至多容纳1单位燃料,每单位燃料可供吉普行驶1单位长度,燃料必须存放在容器中.当起点处提供足够多的燃料且容器的数量恰好盛放这些燃料时,是否存在行驶策略使吉普穿越任意长的沙漠?

问题6 (往返容器约束) 沙漠一端有一辆最多携带$s$个容器的吉普($s\ge 2$),每个容器至多容纳1单位燃料,每单位燃料可供吉普行驶1单位长度,燃料必须存放在容器中.当起点处提供足够多的燃料,容器的数量恰好盛放这些燃料,且行程结束后吉普需返回起点时,是否存在行驶策略使吉普穿越任意长的沙漠?

文章组织如下:第2节中给出问题3和问题4的结果.问题5和问题6在第3节中讨论.

本节讨论问题3和问题4.为了便于表述,记行程的起点为S,终点为F,并约定终点在起点的右方;称沙漠中储存燃料的位置为仓库.

定理2.1  问题3的解为

$\begin{aligned} D_{1}^{s}(y) &=\underbrace{1+\cdots+1}_{s}+\underbrace{\frac{1}{3}+\cdots+\frac{1}{3}}_{s}+\cdots+\frac{1}{2 p-1}+\cdots+\frac{1}{2 p-1}+\frac{f}{2 p+1} \\ &=s\left(1+\frac{1}{3}+\cdots+\frac{1}{2 p-1}\right)+\frac{f}{2 p+1}, \end{aligned}$

其中$y=sp+f$, $0\le f < s$, $p$为正整数. $D_1^s(y)$表示问题3中运载能力为$s$的吉普在S提供$y$单位燃料时能穿越的最大沙漠长度.

证   首先指出,的确存在行驶策略使吉普穿越长为$D_1^s(y)$的沙漠.先讨论$f=0$的情况,即$y=sp$.令吉普于S处装上$s$单位燃料,向右行驶$\frac{s}{2p-1}$单位长度,在此处储存$s-\frac{2s}{2p-1}$单位燃料,用剩余的$\frac{s}{2p-1}$单位燃料返回S.上述过程共进行$p$次,当然,最后一次离开S后不再返回.此时吉普与S间的距离为$\frac{s}{2p-1}$, S的燃料已经全部运走,仓库中共有$s(p-1)$单位燃料.分别用$p-1, p-2, \cdots, 1$替代上述过程中的$p$并重复这个过程,则吉普可以行驶$D_1^s(y)$的距离.对$f\ne 0$的情况,在进行上述过程前,吉普首先于S处装上$s$单位燃料,向右行驶$\frac{f}{2p+1}$单位长度,在此处储存$s-\frac{2f}{2p+1}$单位燃料,并用剩余的$\frac{f}{2p+1}$单位燃料返回S.上述过程共进行$p+1$次,当然,最后一次离开S时吉普只携带$f$单位燃料且不再返回.之后按照$f=0$的方式行驶,吉普可以行驶共$D_1^s(y)$的距离.

其次,证明SF间的距离不能超过$D_1^s(y)$.对所有整数$j$满足$0\le j\le y$,令$x_{j}$表示SF上的点,使得在$x_{j}$右边消耗的燃料总量为$j$单位(即吉普在$x_j$右边行驶的总长度为$j$,包括向左行驶和向右行驶).用$P_k$表示$x_{s(k+1)}$和$x_{sk}$间的任意点,其中$0\le k\le p-1$.先讨论$f=0$的情况,即$y=sp$,此时$S=x_{sp}$, $F=x_0$.由于$x_{sk}$右边消耗了$sk$单位燃料,因此有超过$sk$单位燃料经过$P_k$点被向右运往$x_{sk}$,因为吉普每次至多携带$s$单位燃料,所以在向右行驶的过程中$P_k$至少被经过$k+1$次,而完成这$k+1$次向右行驶至少需要经过$P_k$向左行驶$k$次,因此$P_k$至少被经过$2k+1$次.注意到$x_{s(k+1)}$与$x_{sk}$间消耗的燃料恰为$s$单位,因此$x_{s(k+1)}$与$x_{sk}$间的距离至多为$\frac{s}{2k+1}$,从而SF间的距离至多为$D_1^s(y)$.再来讨论$f\ne 0$的情况,类似地, S与$x_{sp}$间的距离至多为$\frac{f}{2p+1}$,因此SF间的距离至多为$D_1^s(y)$.

至此,我们完成了定理2.1的证明,并在证明的过程中给出了实现定理2.1的一个行驶策略.

定理2.2   问题4的解为

$\begin{eqnarray*}D_2^s(y)&=&\underbrace{\frac{1}{2}+\cdots+\frac{1}{2}}_{s}+\underbrace{\frac{1}{4}+\cdots+\frac{1}{4}}_{s}+\cdots+\underbrace{\frac{1}{2p}+\cdots+\frac{1}{2p}}_{s}+\frac{f}{2p+2}\\&=&s\left(\frac{1}{2}+\frac{1}{4}+\cdots+\frac{1}{2p}\right)+\frac{f}{2p+2}, \end{eqnarray*}$

其中$y=sp+f$,且$0\le f < s$, $p$为正整数, $D_2^s(y)$表示问题4中运载能力为$s$的吉普在S提供$y$单位燃料时能穿越的最大沙漠长度.

证   首先指出,的确存在行驶策略使吉普穿越长为$D_2^s(y)$的沙漠.沿用定理2.1证明中的记号.先讨论$f=0$的情况,即$y=sp$.令吉普于S处装上$s$单位燃料,向右行驶$\frac{s}{2p}$单位长度,在此处储存$s-\frac{2s}{2p}$单位燃料,用剩余的$\frac{s}{2p}$单位燃料返回S.上述过程共进行$p$次,当然,最后一次离开S后不再返回.此时吉普与S间的距离为$\frac{s}{2p}$, S的燃料已经全部运走,仓库中共有$s(p-1)+\frac{s}{2p}$单位燃料.分别用$p-1, p-2, \cdots, 1$替代上述过程中的$p$并重复此过程,则吉普可以行驶$D_2^s(y)$的距离.注意到此时仓库中剩余的燃料数量分别为$\frac{s}{2p}, \frac{s}{2p-2}, \dots, \frac{s}{2}$,从F依次使用仓库中的燃料恰好返回S.对$f\ne 0$的情况,在进行上述过程前,吉普首先于S处装上$s$单位燃料,向右行驶$\frac{f}{2p+2}$单位长度,在此处储存$s-\frac{2f}{2p+2}$单位燃料,并用剩余的$\frac{f}{2p+2}$单位燃料返回S,上述过程共进行$p+1$次,当然,最后一次离开S时吉普只携带$f$单位燃料且不再返回.之后按照$f=0$的方式行驶,吉普可以行驶共$D_2^s(y)$的距离.

其次,证明SF间的距离不能超过$D_2^s(y)$.先讨论$f=0$的情况,即$y=sp$,此时$S=x_{sp}$且$F=x_0$.由于$x_{sk}$的右边消耗了$sk$单位燃料,因此有超过$sk$单位燃料经过$P_k$点被向右运往$x_{sk}$,因为吉普每次至多携带$s$单位燃料,所以在向右行驶的过程中$P_k$至少被经过$k+1$次,而完成这$k+1$次向右行驶并最终回到S至少需要经过$P_k$向左行驶$k+1$次,因此$P_k$至少被经过$2k+2$次.注意到$x_{s(k+1)}$与$x_{sk}$间消耗的燃料恰好为$s$单位,因此$x_{s(k+1)}$与$x_{sk}$间的距离至多为$\frac{s}{2k+2}$,从而SF间的距离至多为$D_2^s(y)$.再来讨论$f\ne 0$的情况,类似地, S与$x_{sp}$间的距离至多为$\frac{f}{2p+2}$,因此SF间距离至多为$D_2^s(y)$.

至此,我们完成了定理2.2的证明,并在证明的过程中给出了实现定理2.2的一个行驶策略.

注2.1   事实上,在问题3和问题4中,可以定义新的长度单位与燃料数量单位.若1新单位长度等于$s$旧单位长度, 1新单位燃料等于$s$旧单位燃料,则问题3和问题4完全转化为问题1和问题2.

注2.2   由定理2.1、2.2的证明可以看出, $P_k$被经过的次数与$x_{s(k+1)}x_{sk}$间消耗燃料的效率是对应的,这里燃料效率是指每单位燃料使吉普前进的距离.由定理2.1、2.2的证明还可以看出,若干段具有同样燃料效率的路程可以随意地拆分合并.例如,由$x_{s(k+1)}$向$x_{sk}$行驶,既可以不做停留地由$x_{s(k+1)}$直接驶向$x_{sk}$,即不在任意$P_k$储存燃料；也可以由$x_{s(k+1)}$出发,先将部分或全部燃料存放在任意一个或几个$P_k$再驶向$x_{sk}$.

注2.3   由定理2.1、2.2可以看出,越接近终点,燃料效率越高;越靠近起点,燃料效率越低.

问题3和问题4可以分别用对偶的方式提出.

问题7   沙漠一端有一辆最多携带$s$单位燃料的吉普,每单位燃料可供吉普行驶1单位长度.当沙漠长度为$l$单位时,起点至少需要多少燃料才能使吉普穿越沙漠?

问题8   沙漠一端有一辆最多携带$s$单位燃料的吉普,每单位燃料可供吉普行驶1单位长度.当沙漠长度为$l$单位时,起点至少需要多少燃料才能使吉普穿越沙漠并返回起点?

由定理2.1和定理2.2可以立刻得到问题7和问题8的解.

推论2.1   问题7的解为$ Z_1^s(l)=sp+\left(l-D_1^s(sp)\right)(2p+1), $其中$p$为使$D_1^s(sp)\le l\le D_1^s\left(s(p+1)\right)$成立的唯一整数. $Z_1^s(l)$表示问题7中运载能力为$s$的吉普在穿越长为$l$的沙漠时需要的最少燃料量.

证   由定理2.1可知,使用$sp+\left(l-D_1^s(sp)\right)(2p+1)$单位燃料可到达的最远距离为$l$,由$D_1^s(y)$的单调性及最优性易知, $sp+\left(l-D_1^s(sp)\right)(2p+1)$是最优的.

推论2.2   问题8的解为$ Z_2^s(l)=sp+\left(l-D_2^s(sp)\right)(2p+2), $其中$p$为使$D_2^s(sp)\le l\le D_2^s\left(s(p+1)\right)$成立的唯一整数. $Z_2^s(l)$表示问题8中运载能力为$s$的吉普在穿越长为$l$的沙漠时需要的最少燃料量.

证   由定理2.2可知,使用$sp+\left(l-D_2^s(sp)\right)(2p+2)$单位燃料可到达的最远距离为$l$,由$D_2^s(y)$的单调性及最优性易知, $sp+\left(l-D_2^s(sp)\right)(2p+2)$是最优的.

本节我们得到了无容器约束时单向及往返吉普问题的最优行驶策略.容易看出,当存在容器约束时,使用相同的燃料,吉普的行驶距离不能比无约束时更长.

在问题1和问题2中,隐含了这样的条件:燃料在沙漠中可以随意地存放.在第2节中解决问题3和问题4时,我们没有对仓库中燃料的存放作任何约束.而实际问题中,对存放燃料的容器可能有一定的要求,例如存放燃料的容器必须是某种“罐子”,而吉普每次最多能携带“罐子”的数量是固定的.本节分别研究容器约束下的单向及往返吉普问题.

为了明确容器约束对问题的影响,首先看一个例子.

例3.1   沙漠一端有一辆最多携带3个容器的吉普,每个容器至多容纳1单位燃料,每单位燃料可供吉普行驶1单位长度,燃料必须存放在容器中.当起点处提供足够多的燃料且容器的数量恰好盛放这些燃料时,吉普能否按照第2节中定理2.1给出的方式行驶?

根据定理2.1,若无容器约束,从F到S,最优路线中每单位燃料的效率依次为

(3.1) $\begin{eqnarray}\label{eq1}&&\overbrace{1, 1, 1}^{3}, \overbrace{\frac{1}{3}, \frac{1}{3}, \frac{1}{3}}^{3}, \overbrace{\frac{1}{5}, \frac{1}{5}, \frac{1}{5}}^{3}, \overbrace{\frac{1}{7}, \frac{1}{7}, \frac{1}{7}}^{3}, \overbrace{\frac{1}{9}, \frac{1}{9}, \frac{1}{9}}^{3}, \overbrace{\frac{1}{11}, \frac{1}{11}, \frac{1}{11}}^{3}, \overbrace{\frac{1}{13}, \frac{1}{13}, \frac{1}{13}}^{3}, \overbrace{\frac{1}{15}, \frac{1}{15}, \frac{1}{15}}^{3}, \\&&\overbrace{\frac{1}{17}, \frac{1}{17}, \frac{1}{17}}^{3}, \overbrace{\frac{1}{19}, \frac{1}{19}, \frac{1}{19}}^{3}, \overbrace{\frac{1}{21}, \frac{1}{21}, \frac{1}{21}}^{3}, \overbrace{\frac{1}{23}, \frac{1}{23}, \frac{1}{23}}^{3}, \cdots, \end{eqnarray}$

而存在容器约束时,这样的效率并不总能实现.例如,无容器约束时,最优策略中$x_{10}$到$x_9$的行驶方式为:于$x_{10}$处携带3单位燃料,向右行驶1/7单位长度到达$x_9$,放下19/7单位燃料并使用车上所剩1/7单位燃料回到$x_{10}$.上述过程共进行4次,最后一次不返回$x_{10}$.而在容器约束下,由于吉普上需要至少1个容器存放燃料,因此每次在仓库处至多放下2个容器,即每次至多只能存储2单位燃料.故而在前3次往返中,吉普每次返回$x_{10}$时都带回5/7单位燃料,在最后一次离开$x_{10}$时,吉普需携带$22/7>3$单位燃料,这超过了吉普的运载能力,所以$x_{10}$到$x_9$段1/7的燃料效率是不可能实现的.因此,在例3.1中,定理2.1给出的最优路线是达不到的.

在例3.1中,为了将$x_{10}$处的燃料全部运至$x_9$,至少需要在定理2.1给出路线的基础上增加一次往返,即$x_{10}$至$x_9$段的燃料效率需降至1/9,对应的行驶方式为:于$x_{10}$处携带3单位燃料,向右行驶1/9单位长度到达$x_9$,在仓库中存储2单位并回到$x_{10}$,放下车上所剩7/9单位燃料.上述过程共进行5次,最后一次中携带的燃料为10/9单位且不返回$x_{10}$.同理, $x_{11}$、$x_{12}$分别向$x_{10}$行驶的燃料效率也降至1/9.

注意到式(3.1)给出的无容器约束的燃料效率中, $x_{15}$至$x_{12}$的燃料效率恰为1/9,那么能否以1/9的效率由$x_{15}$向$x_9$行驶?答案是肯定的:于$x_{15}$处携带3单位燃料,向右行驶6/9单位长度到达$x_9$,放下15/9单位燃料(2个容器)并使用所剩6/9单位燃料返回$x_{15}$.上述过程共进行5次,最后一次不返回$x_{15}$.

例3.1启发我们:为了回答问题5,首先要讨论容器约束何时起作用.命题3.1给出了对这个问题的回答.

命题3.1   在问题5的条件下,在$x_{si}$与$x_{sj}$间行驶时,燃料效率能够达到$\frac{1}{2i-1}$的充要条件为一次往返消耗的燃料不少于1个单位,即$\frac{2s(i-j)}{2i-1}\ge1$,其中$i, j$为整数且$i>j$.

证   需要注意燃料效率为$\frac{1}{2i-1}$表明行驶过程中离开$x_{si}$恰$i$次,返回$x_{si}$恰$i-1$次.必要性显然,下面证明充分性.当$\frac{2s(i-j)}{2i-1}\ge1$时,吉普按照下面的方式行驶可以让燃料效率达到$\frac{1}{2i-1}$.于$x_{si}$处携带$s$单位燃料,向右行驶$\frac{s(i-j)}{2i-1}$单位长度,放下$s-\frac{2s(i-j)}{2i-1}$单位燃料,用剩余$\frac{s(i-j)}{2i-1}$单位燃料回到$x_{si}$.上述过程共进行$i$次,最后一次不返回$x_{si}$.这样的行驶方式可行是因为:若$1\le\frac{2s(i-j)}{2i-1}\le 2$,即$x_{si}$与$x_{sj}$间的一次单向行程消耗燃料不多于1单位且一次往返行程消耗燃料不少于1单位,则由$x_{sj}$返回时, 1个容器足以携带返程需要的不多于1单位燃料,且其余的$s-1$个容器足以盛放每次存储在仓库中的不多于$s-1$单位燃料；若$\frac{2s(i-j)}{2i-1}>2$,即$x_{si}$与$x_{sj}$间的一次单向行程消耗燃料多于1单位,则每次离开$x_{sj}$时, $s$个容器足以将少于$s-1$单位燃料在吉普与仓库间分配.

在问题5的条件下,关于定理2.1中的燃料效率何时能够保持,可以由推论3.1给出回答.

推论3.1   在问题5的条件下,若起点处提供$y$单位燃料,其中$y\ge s^2$,对任意正整数$i$,当且仅当$i\le s-1$时,在$x_{s(i+1)}$到$x_{si}$间行驶时的燃料效率能保持定理2.1中的$\frac{1}{2i+1}$.

证   由命题3.1,在$x_{s(i+1)}$到$x_{si}$间行驶时的燃料效率能达到$\frac{1}{2i+1}$当且仅当$\frac{2s}{2i+1}\ge 1$,即$i\le s-1$.

根据对例3.1的讨论,可以推广得到问题5条件下的一种行驶策略.

命题3.2   在问题5的条件下,由F起向左,吉普能够以这样的效率使用燃料

(3.2) $\begin{equation}\label{eq2}\underbrace{\overbrace{1, \cdots, 1}^{s}, \overbrace{\frac{1}{3}, \cdots, \frac{1}{3}}^{s}, \cdots, \overbrace{\frac{1}{2s-1}, \cdots, \frac{1}{2s-1}}^{s}}_{s^2}, \overbrace{\frac{1}{B_1}, \cdots, \frac{1}{B_1}}^{s(A_2-A_1)}, \overbrace{\frac{1}{B_2}, \cdots, \frac{1}{B_2}}^{s(A_3-A_2)}, \cdots, \overbrace{\frac{1}{B_k}, \cdots, \frac{1}{B_k}}^{s(A_{k+1}-A_k)}, \cdots, \end{equation}$

其中

$\begin{eqnarray*}\label{eq3}\begin{array}{ll}A_1=s, & B_1= 2\lceil \frac{sA_1}{s-1} \rceil-1 , \\ A_2=\frac{B_1+1}{2}, & B_2=2\lceil \frac{sA_2}{s-1} \rceil -1, \\\qquad \cdots &\qquad \cdots\\ A_k=\frac{B_{k-1}+1}{2} , & B_k=2\lceil \frac{sA_k}{s-1} \rceil-1, \end{array}\end{eqnarray*}$

其中, $\lceil a\rceil$表示不小于$a$的最小整数.

注3.1   命题3.2给出的序列具有这样的含义:在容器约束下,对$x_{s(A_k+1)}$到$x_{sA_k}$段,每次往返中吉普到达$x_{sA_k}$时至多存储$s-1$单位燃料;最后一次到达$x_{sA_k}$时不需返回$x_{s(A_k+1)}$,可以存储多于$s-1$单位少于$s$单位燃料.为了存储$x_{sA_k}$需要的$sA_k$个单位燃料, $x_{sA_k}$至少被到达$\lceil \frac{sA_k}{s-1} \rceil$次,被离开$\lceil \frac{sA_k}{s-1} \rceil-1$次,因此线段$x_{sA_k}x_{s(A_k+1)}$上的点至少被经过$B_k$次.即$x_{sA_k}$到$s_{s(A_k+1)}$段的燃料效率至多为$\frac{1}{B_k}$,而$x_{sA_{k+1}}$到$x_{s(A_{k+1}-1)}$恰为$\frac{1}{B_k}$在$D_1^s(y)$中对应的位置.

证   根据命题3.1及推论3.1,只需证$2s\frac{A_{k+1}-A_k}{B_k}\ge1$.

因为

$\begin{eqnarray*}&&\lceil \frac{sA_k}{s-1}\rceil\ge \frac{sA_k}{s-1}\\&\Rightarrow & 2(s-1)\lceil\frac{sA_k}{s-1}\rceil+1>2sA_k\\&\Rightarrow& (s-1)(B_k+1)+1>2sA_k\\&\Rightarrow & sB_k+s-2sA_k>B_k\\&\Rightarrow & 2sA_{k+1}-2sA_k>B_k, \end{eqnarray*}$

因此$2s\frac{A_{k+1}-A_k}{B_k}\ge1$成立.

根据命题3.1和命题3.2,可以回答问题5.

定理3.1   问题5中,存在行驶策略使吉普穿越任意长的沙漠.

证   以命题3.2的方式行驶,吉普可以行驶至无穷远处,下面给出证明.

只需证式(3.2)中数列的部分和序列发散.式(3.2)中燃料效率为$\frac{1}{B_k}$的路径总长为

$\begin{eqnarray*} \frac{s(A_{k+1}-A_{k})}{B_k} = \frac{s\left(\lceil\frac{sA_k}{s-1}\rceil-A_k\right)}{2\lceil\frac{sA_k}{s-1}\rceil-1}> \frac{s\left(\frac{sA_k}{s-1}-A_k\right)}{2\left(\frac{sA_k}{s-1}+1\right)-1}= \frac{\frac{s}{s-1}A_k}{\frac{2s}{s-1}A_k+1}. \end{eqnarray*} $

由$A_k$的构造易知$\mathop {\lim }\limits_{x \to + \infty } {A_k} = + \infty $,则

$\begin{eqnarray*} \lim\limits_{A_k\to \infty}\frac{\frac{s}{s-1}A_k}{\frac{2s}{s-1}A_k+1} = \frac{1}{2} \end{eqnarray*}$

且

$ \begin{eqnarray*} \frac{s(A_{k+1}-A_{k})}{B_k}> \frac{\frac{s}{s-1}A_k}{\frac{2s}{s-1}A_k+1}, \end{eqnarray*} $

因此式(3.2)中数列的部分和序列发散.

注3.2   定理3.1告诉我们,按照命题3.2的策略行驶,问题5中的吉普有能力行驶至无穷远处.但对一些$y$,命题3.2给出的行驶方式并非最优的.如例3.1中, $y=12$时,由$x_{12}$以1/7的燃料效率行至$x_{8.5}$,由$x_{8.5}$以1/5的燃料效率行至$x_6$,再分别以1/3和1的效率行至$x_3$和F,可比命题3.2给出的方式行驶得更远.

与容器约束的单向吉普问题类似,为了明确容器约束对问题的影响,首先看一个例子.

例3.2   沙漠一端有一辆最多携带3个容器的吉普,每个容器至多容纳1单位燃料,每单位燃料可供吉普行驶1单位长度,燃料必须存放在容器中.当起点处提供足够多的燃料,容器的数量恰好盛放这些燃料,且旅程结束后吉普需返回起点时,吉普能否按照第2节中定理2.2给出的方式行驶?

根据定理2.2,若无容器约束,从F到S,最优路线中每单位燃料的效率依次为:

(3.3) $\begin{eqnarray}\label{eq4}&&\overbrace{\frac{1}{2}, \frac{1}{2}, \frac{1}{2}}^{3}, \overbrace{\frac{1}{4}, \frac{1}{4}, \frac{1}{4}}^{3}, \overbrace{\frac{1}{6}, \frac{1}{6}, \frac{1}{6}}^{3}, \overbrace{\frac{1}{8}, \frac{1}{8}, \frac{1}{8}}^{3}, \overbrace{\frac{1}{10}, \frac{1}{10}, \frac{1}{10}}^{3}, \overbrace{\frac{1}{12}, \frac{1}{12}, \frac{1}{12}}^{3}, \overbrace{\frac{1}{14}, \frac{1}{14}, \frac{1}{14}}^{3}, \overbrace{\frac{1}{16}, \frac{1}{16}, \frac{1}{16}}^{3}, \\&&\overbrace{\frac{1}{18}, \frac{1}{18}, \frac{1}{18}}^{3}, \overbrace{\frac{1}{20}, \frac{1}{20}, \frac{1}{20}}^{3}, \overbrace{\frac{1}{22}, \frac{1}{22}, \frac{1}{22}}^{3}, \overbrace{\frac{1}{24}, \frac{1}{24}, \frac{1}{24}}^{3}, \cdots, \end{eqnarray}$

而存在容器约束时,这样的效率并不总能实现.例如,无容器约束时,最优策略中$x_{10}$到$x_9$的行驶方式为:于$x_{10}$处携带3单位燃料,向右行驶1/8单位长度到达$x_9$,放下22/8单位燃料并使用车上所剩1/8单位燃料回到$x_{10}$.上述过程共进行4次,最后一次不返回$x_{10}$,并在离开$x_9$前往$x_8$时在仓库中留下1/8单位燃料供返程时使用.而在容器约束下,由于吉普上需要一个容器存放行驶中使用的燃料,因此每次在仓库处至多放下2个容器,即每次至多储存2单位燃料.从而前3次往返中,吉普每次返回$x_{10}$都带回6/8单位燃料,最后一次离开$x_{10}$时吉普需携带$26/8>3$单位燃料,这超过了吉普的运载能力,所以$x_{10}$到$x_9$中1/8的燃料效率是不可能实现的.因此在例3.2中,定理2.2给出的最优路线是达不到的.

在例3.2中,为了从$x_{10}$运来$x_9$所需的全部燃料,至少需要在定理2.2给出最优路线的基础上增加一次往返,即对应的燃料效率降至1/10:于$x_{10}$处携带3单位燃料,向右行驶1/10单位长度到达$x_9$,在仓库中存储2单位燃料并回到$x_{10}$,放下车上所剩8/10单位燃料.将上述过程进行5次,最后一次中携带的燃料为12/10单位且不返回$x_{10}$.同理, $x_{11}$、$x_{12}$分别向$x_{9}$行驶的燃料效率也需降至1/10.

注意到式(3.3)给出的无容器约束的燃料效率中, $x_{15}$至$x_{12}$的燃料效率恰为1/10,那么是否能够以1/10的效率由$x_{15}$向$x_9$行驶?答案是肯定的:于$x_{15}$处携带3单位燃料,向右行驶6/10单位长度到达$x_9$,放下18/10单位燃料(2个容器)并使用所剩6/10单位燃料返回$x_{15}$.将上述过程进行5次,最后一次不返回$x_{15}$.

例3.2启发我们,为了回答问题6,首先要讨论容器约束何时起作用.通过命题3.1的证明过程易知,单向问题中关于容器约束何时生效的讨论在往返问题中依然适用.因此平行于命题3.1,在问题6的条件下有以下结论.

命题3.3   在问题6的条件下,在$x_{si}$与$x_{sj}$间行驶,燃料效率能够达到$\frac{1}{2i}$的充要条件为一次往返消耗的燃料不少于1个单位,即$\frac{2s(i-j)}{2i}\ge1$,其中$i, j$为整数且$i>j$.

证   与命题3.1完全类似,这里不再赘述.

在问题6的条件下,关于定理2.2中的燃料效率何时能够保持,可以由推论3.2给出回答.

推论3.2   在问题6的条件下,若起点处提供$y$单位燃料,其中$y\ge s^2$,对任意正整数$i$,当且仅当$i\le s-1$时,在$x_{s(i+1)}$到$x_{si}$间行驶时的燃料效率能保持定理2.2中的$\frac{1}{2(i+1)}$.

证   由命题3.3,在$x_{s(i+1)}$到$x_{si}$间行驶时的燃料效率能达到$\frac{1}{2(i+1)}$当且仅当$\frac{2s}{2(i+1)}\ge 1$,即$i\le s-1$.

根据对例3.2的讨论,可以推广得到问题6条件下的一种行驶策略.

命题3.4   在问题6的条件下,由F起向左,吉普能够以这样的效率使用燃料

(3.4) $\begin{equation}\label{eq5}\underbrace{\overbrace{\frac{1}{2}, \cdots, \frac{1}{2}}^{s}, \overbrace{\frac{1}{4}, \cdots, \frac{1}{4}}^{s}, \cdots, \overbrace{\frac{1}{2s}, \cdots, \frac{1}{2s}}^{s}}_{s^2}, \overbrace{\frac{1}{D_1}, \cdots, \frac{1}{D_1}}^{s(C_2-C_1)}, \overbrace{\frac{1}{D_2}, \cdots, \frac{1}{D_2}}^{s(C_3-C_2)}, \cdots, \overbrace{\frac{1}{D_k}, \cdots, \frac{1}{D_k}}^{s(C_{k+1}-C_k)}, \cdots, \end{equation}$

其中

$\begin{eqnarray*}\label{eq6}\begin{array}{ll} C_1=s, & D_1=2 \lceil \frac{sC_1}{s-1} \rceil , \\ C_2=\frac{D_1}{2} , & D_2= 2\lceil \frac{sC_2}{s-1} \rceil, \\\quad \cdots &\qquad \cdots\\ C_k=\frac{D_{k-1}}{2}, & D_k= 2\lceil \frac{s C_k}{s-1} \rceil.\end{array}\end{eqnarray*}$

注3.3   命题3.4给出的序列具有这样的含义:在容器约束下,对$x_{s(C_k+1)}$到$x_{sC_k}$段,每次往返中吉普到达$x_{sC_k}$时至多存储$s-1$个单位的燃料；最后一次到达$x_{sC_k}$时不需返回$x_{s(C_k+1)}$,可以存储多于$s-1$单位少于$s$单位燃料.为了存储$x_{sC_k}$需要的$sC_k$单位燃料, $x_{sC_k}$至少被到达$\lceil \frac{sC_k}{s-1} \rceil$次,被离开$\lceil \frac{sC_k}{s-1} \rceil-1$次,考虑到吉普需要返回S,线段$x_{sC_k}x_{s(C_k+1)}$上的点至少被经过$D_k$次.即$x_{sC_k}$到$s_{s(C_k+1)}$段的燃料效率至多为$\frac{1}{D_k}$,而$x_{sC_{k+1}}$到$x_{s(C_{k+1}-1)}$恰为$\frac{1}{D_k}$在$D_2^s(y)$中对应的位置.

证   根据命题3.3及推论3.2,只需证$2s\frac{C_{k+1}-C_k}{D_k}\ge1$.

因为

$\begin{eqnarray*}&&\lceil \frac{sC_k}{s-1}\rceil\ge \frac{sC_k}{s-1}\\&\Rightarrow & 2(s-1)\lceil\frac{sC_k}{s-1}\rceil\ge 2sC_k\\&\Rightarrow & (s-1)D_k\ge 2sC_k\\&\Rightarrow & sD_k-2sC_k\ge D_k\\&\Rightarrow & 2sC_{k+1}-2sC_k\ge D_k, \end{eqnarray*}$

因此$2s\frac{C_{k+1}-C_k}{D_k}\ge1$成立.

根据命题3.3和命题3.4,可以回答问题6.

定理3.2   问题6中,存在行驶策略使吉普穿越任意长的沙漠.

证   以命题3.4的方式行驶,吉普可以行至无穷远处,下面给出证明.只需证式(3.4)中数列的部分和序列发散.式(3.4)中燃料效率为$\frac{1}{D_k}$的路径总长为

$\begin{eqnarray*} \frac{s(C_{k+1}-C_{k})}{D_k} = \frac{s\left(\lceil\frac{sC_k}{s-1}\rceil-C_k\right)}{2\lceil\frac{sC_k}{s-1}\rceil}> \frac{s\left(\frac{sC_k}{s-1}-C_k\right)}{2\left(\frac{sC_k}{s-1}+1\right)}= \frac{\frac{s}{s-1}C_k}{\frac{2s}{s-1}C_k+2}, \end{eqnarray*} $

由$C_k$的构造易知$\mathop {\lim }\limits_{x \to + \infty } {C_k} = + \infty $,则

$\lim\limits_{C_k\to \infty}\frac{\frac{s}{s-1}C_k}{\frac{2s}{s-1}C_k+2} =\frac{1}{2} , $

且

$ \frac{s(C_{k+1}-C_{k})}{D_k}> \frac{\frac{s}{s-1}C_k}{\frac{2s}{s-1}C_k+2} , $

因此式(3.4)中数列的部分和序列发散.

注3.4   定理3.2告诉我们,以命题3.4的方式行驶,问题6中的吉普有能力行驶至无穷远处.但对一些$y$,命题3.4给出的行驶方式并非最优的.

表 1列出了$s=2$时,依命题3.2、3.4所给方式行驶所达到的距离与无容器约束的最大行驶距离的比较.由第2节易知,使用相同的燃料,无约束时的最远行驶距离是有约束时行驶距离的一个上界.通过表 1可以看出,不同燃料数量下,命题3.2、3.4给出的行驶方式达到的距离与这个上界非常接近,说明我们给出的行驶策略是高效的.

本文研究了无容器约束和容器约束的吉普问题.针对无容器约束吉普问题,本文给出的行驶策略为单向及往返两种情况下的最优策略.针对容器约束的吉普问题,首次研究了容器约束下吉普能否行至无穷远处的问题,并在单向及往返两种情况下给出肯定的回答.通过比较无容器约束行驶策与容器约束行驶策略,可以看出二者的行驶距离差距很小,说明给出的容器约束行驶策略很好,该策略对航天领域和新能源交通等实际问题有参考价值.

对容器约束的吉普问题,文章中给出的行驶策略并非总是最优的.得到这个问题的最优策略将是一项非常有挑战的工作.