最短路径与最速方案问题

在解决实际问题时，注意观察和善于想象是十分重要的，观察与想象不仅能发现问题隐含的某些属性，有时还能顺理成章地找到解决实际问题的钥匙。本节的几个例子说明，猜测也是一种想象力。没有合理而又大胆的猜测，很难做出具有创新性的结果。开普勒的三大定律（尤其是后两条）并非一眼就能看出的，它们隐含在行星运动的轨迹之中，隐含在第谷记录下来的一大堆数据之中。历史上这样的例子实在太多了。在获得了一定数量的资料数据后，人们常常会先去猜测某些结果，然后试图去证明它。猜测一经证明就成了定理，而定理一旦插上想象的翅膀，又常常会被推广出许多更为广泛的结果。即使猜测被证明是错误的，结果也决不是一无所获的失败而常常是对问题的更为深入的了解。§2.9最短路径与最速方案问题例5（最短路径问题）设有一个半径为r的圆形湖，圆心为O。A、B位于湖的两侧，AB连线过O，见图。现拟从A点步行到B点，在不得进入湖中的限制下，问怎样的路径最近。ABOr将湖想象成凸出地面的木桩，在AB间拉一根软线，当线被拉紧时将得到最短路径。根据这样的想象，猜测可以如下得到最短路径：过A作圆的切线切圆于E，过B作圆的切线切圆于F。最短路径为由线段AE、弧EF和线段FB连接而成的连续曲线（根据对称性，AE′，弧E′F′，F′B连接而成的连续曲线也是）。EFE′F′以上只是一种猜测，现在来证明这一猜测是正确的。为此，先介绍一下凸集与凸集的性质。定义2.1（凸集）称集合R为凸集，若x1、x2∈R及λ∈[0，1]，总有λx1+（1+λ）x2∈R。即若x1、x2∈R，则x1、x2的连线必整个地落在R中。定理2.2（分离定理）对平面中的凸集R与R外的一点K，存在直线l,l分离R与K，即R与K分别位于l的两侧（注：对一般的凸集R与R外的一点K，则存在超平面分离R与K），见图。klR下面证明猜想猜测证明如下：（方法一）显然，由AE、EF、FB及AE′，E′F′，F′B围成的区域R是一凸集。利用分离定理易证最短径不可能经过R外的点，若不然，设Γ为最短路径，Γ过R外的一点M，则必存在直线l分离M与R，由于路径Γ是连续曲线，由A沿Γ到M，必交l于M1，由M沿Γ到B又必交l于M2。这样，直线段M1M2的长度必小于路径M1MM2的长度，与Γ是A到B的最短路径矛盾，至此，我们已证明最短路径必在凸集R内。不妨设路径经湖的上方到达B点，则弧EF必在路径F上，又直线段AE是由A至E的最短路径，直线FB是由F到B的最短路径，猜测得证。ABOrEFE′F′M1M2MΓl还可用微积分方法求弧长，根据计算证明满足限止条件的其他连续曲线必具有更大的长度；此外，本猜测也可用平面几何知识加以证明等。根据猜测不难看出，例5中的条件可以大大放松，可以不必设AB过圆心，甚至可不必设湖是圆形的。例如对下图，我们可断定由A至B的最短路径必为l1与l2之一，其证明也不难类似给出。ABl1l2D到此为止，我们的研讨还只局限于平面之中，其实上述猜测可十分自然地推广到一般空间中去。1973年，J.W.Craggs证明了以上结果：若可行区域的边界是光滑曲面。则最短路径必由下列弧组成，它们或者是空间中的自然最短曲线，或者是可行区域的边界弧。而且，组成最短路径的各段弧在连接点处必定相切。例6一辆汽车停于A处并垂直于AB方向，此汽车可转的最小圆半径为R，求不倒车而由A到B的最短路径。解（情况1）若|AB|2R，最短路径由弧AC与切线BC组成（见图①）。（情况2）若|AB|2R，则最短路径必居于图②（a）、（b）两曲线之中。可以证明，（b）中的曲线ABC更短。AR2RBRC①②ABoC（a）CABo1o2（b）例7驾驶一辆停于A处与AB成θ1角度的汽车到B处去，已知B处要求的停车方向必须与AB成θ2角，试找出最短路径（除可转的最小圆半径为R外，不受其他限止）。解根据Craggs定理并稍加分析可知，最短路径应在l1与l2中，见图，比较l1与l2的长度，即可得到最短路径。Al1l2Bθ2θ1最速方案问题例8将一辆急待修理的汽车由静止开始沿一直线方向推至相隔S米的修车处，设阻力不计，推车人能使车得到的推力f满足:-B≤f≤A,f0为推力，f0为拉力。问怎样推车可使车最快停于修车处。设该车的运动速度为υ=υ(t)，根据题意，υ(0)=υ(T)=0，其中T为推车所花的全部时间。由于-B≤f≤A，且f=mυ′，可知-b≤υ′≤a（其中m为汽车质量，a=A/m,b=B/m）。据此不难将本例归纳为如下的数学模型：minTυ(0)=υ(T)=0TSυ(t)dt0s.tadtdvb此问题为一泛函极值问题，求解十分困难，为得出一个最速方案。我们作如下猜测：猜测最速方案为以最大推力将车推到某处，然后以最大拉力拉之，使之恰好停于修车处，其中转换点应计算求出证明设υ=υ(t)为在最速推车方案下汽车的速度，则有。设此方案不同于我们的猜测。现从O点出发，作射线y=at；从（t,0）出发，作直线y=-b(t-T)交y=at于A，由于，曲线υ=υ(t)必位于三角形区域DAT的内部，从而有ΔOAT的面积大于S。在O到T之间任取一点T′，过T′作AT的平行线交OA于A′。显然ΔOA′T′的面积S（T′）是T′的连续函数，当T′=0时S（0）=0，当T′=T时，S（T）S，故由连续函数的性质存在某T′T，S（T′）=S但这一结果与υ=υ(t)是最优方案下的车速的假设矛盾，因为用我们猜测的推车方法推车，只需T′时间即可将车推到修车处，而T′T。T0Sυ(t)dtadtdvboυtAT′TA′Sy=aty=-b(t-T)