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