驾驶问题
1,限定区域的问题
如图,从平面上的 A(-2,0)经上半平面驾驶到
B(2,0),不能穿过湖所在的区域 D:x2+y2<1,
求最短路径,
B(2,0)A(-2,0)
背景知识? 平面上连接两点的最短路径是连接这两点的直线段,
如图,在一个环扇形区域内连接两条向径的最短路径是圆弧 EF.
EF| | PQ| |≤
).())((
|,OE|r),(:
,PQ,
22
rdl
PQ 则记曲线时曲线我们以极坐标形式表示事实上
O
FE QP
思考 1:在 y轴上取一点 C(0,y),使得折线 ACB
与区域 O不交,于是其长度为
.)4(2|| 2/12yACB
显然,|ACB|随着 y的减小而减小,减小 y使得 y= y1
时 C1(0,y1)满足,A C1与 C1 B都与区域 D的边界相切,切点分别记为 E和 F.
B(2,0)A(-2,0)
C1?
C?
E F
因此,我们得到,折线 A C1 B是最短的折线,
且
AE? OE,BF? OF;
由于弧 EF比折线 E C1 F更短的路径,可以证明路径,直线段 AE,弧 EF,直线段 FB是最短的路径,
B(2,0)A(-2,0)
C1?
C?
E F
O
路径,直线段 AE,弧 EF,直线段 FB是最短的路径,
证明是很容易的,我们延长 OE和 OF,任何一条连接 AB的路径交 OE,OF的延长线于 P,Q,则由
|AE|<=|AP|,|FB|<=|QB|,弧 EF的长度不大于曲线段 PQ的长度,
B(2,0)A(-2,0)
C1?
C?
P Q
FE
O
结论,具有有限区域的最短路径是由两部分构成的,一部分是平面上的自然最短路径
(即直线段 ),另一部分是区域的自然边界,这两部分是相切地互相连接,
B(2,0)A(-2,0)
C1?
C?
P Q
FE
O
思考题：
·
·
A
B
寻找从 A到 B的最短路径,不能经过图中的阴影区域,
驾驶问题的模型
(1)交通工具从起点 (a0,b0)驶到终点 (a,b);
(2) 运动轨迹限定在某一区域中或前进方向的角度受到限制 ;
(3) 达到最优 (行驶距离最短,用时最少或费用最省 ).
像上面的这个例子,在驾驶车辆、船舶等交通工具时经常会遇到某些约束条件 (车不入湖,船不上岸,飞机必须绕过高山 ),如何将交通工具从一个地方行驶到另一个地方,使得某种经济效果最优,即,
像刚才的例子,一般地可以写成,设其运动轨迹为 x(t),y(t),0 ≤t ≤T.则我们求运动距离
dttytxs
T
0
22 )]([)]([
最小的路径,这里 x(t),y(t)满足
.0)(,1)()(;0)(,2)(;0)0(,2)0(
22
tytytx
TyTxyx
这实际上是一个具体的最优控制问题,其一般形式是,有若干个状态变量 x(t)=(x1(t),…,
xn(t))和若干个控制变量 α(t)=(α1(t),…,
α n(t)).
要求选择控制变量 α(t),在状态变量满足方程和一定的定解条件
)()(,)0(
)),(),((
0 或落在某超曲面上TxTxxx
tttxf
dt
dx
以及满足一定的约束条件
0))((,0))(( ttx
的前提下,使目标泛函
T
dtttxG
0
))(),((?
达到最小,这里 φ,ψ分别为向量函数,
2.具有优先方向的运动
问题,在风速风向不变的情形下,为帆船选择一条最佳航行路径,设海面上刮东风,要找出从 A点行至位于其东侧的 B点的最佳路径,
A
B
风向背景知识
风从东边吹来,帆船能否往偏东方向行驶?
具有帆船知识的人知道,通过调节帆船的方向和操纵船舵可以使船向偏东方向前进,利用这种方法操纵船走之字形路线,可以使帆船到达位于正东方向的任何地点,风向
w(风力 )
P
α
θ
F
θ:船的前进方向与正东方向的夹角,
α:帆与正东方向的夹角,
先进行力的分析,设帆的面积为 C0,则风力垂直于帆面的分力为
P= C0 w sinα.
将此力沿帆船的前进方向及横向分解,(横向的分力由舵产生的力抵消 ),得到沿帆船前进方向的分力为风向
w(风力 )
P
α
θ
F
].c o s)2[ c o s (
)s i n (s i n
)s i n (
1
0
C
wC
PF
].c o s)2[ c o s (
)s i n (s i n)s i n (
1
0
C
wCPF
由此易知,当 α= θ/2时,此力 F达到最大,此时
).c o s1(1 CF
风向
w(风力 )
P
α
θ
F
另一方面,风也会对船体产生阻力,其阻力
(即风吹在帆船上的力沿船的前进方向的分力 )大小
G= C2 cos θ,
其中 C2与风力以及船的形状有关,G
这样由风产生的推动船沿与正东方向成 θ角的推进力为
).c o s1()c o s1( 1
1
21
1
C
C
CCCGF
由流体力学我们知道,在行驶速度不大时,船行驶的速度正比于船所受的推进力,故船前进的速度为
),c o s1(0 vv
这里 v0是一个正常数,为确定起见,我们选定
σ的一个值,比如 σ =2,对一般情形我们可以类似讨论,此时速度公式为
c o s)c o s1( 21 CCGF
此时有时等号成立当且仅当易知帆船的向东分速度为
.
4275)4/1(a r cc o s
,
8
1
])
4
1
( c o s
16
1
[2
,c o s)c o s21(c o s
).c o s21(
0
0
2
0
0
0
vvv
vvv
vv
e
e
),c o s1(0 vv
.21,81 00 vvvv e
w
v
.4275,
2
1,
8
1
000vvvv e
即当 θ=θ0时,向东分速度达到最大值,所以当目的地位于正东时,取与正东夹角为 θ0的行驶路线 (如图中的折线 ACB).这种行驶方式称为 抢风行驶,
θ0 θ0
B
C
A
风向若目的地不在正东
设目的地与正东方向的夹角为 γ.首先讨论 γ<
θ0的情形,若 γ<60o,则从上面的速度公式可以看出,直接行驶是不可能的,也必须采取折线行驶,若采用抢风行驶,如图,行驶路线为折线 ACB.
θ0 θ0
D
C
A
风向
B
γ
./c o s|AB|8)81/(c o s|AB:| 00 vv所需时间为可以证明,此时抢风行驶是最快的,证明如下,
设 A,B的坐标分别是 (0,0),(a,b),则沿任何一条分段光滑的路径行驶所需的时间为
).8//(c o s||v8a8 0
000
vABdxv
a
a
xxv
dxT
0 )(c o s)(?
a
xxv
dx
0 0 )(c o s))(c o s21(
.
.(a,b)
x
y
dxx?x
)(x?
)(xv
同理,当 60o≤γ< θ0时,抢风行驶仍为最优,
此时虽然可以直接行驶,但所需时间较长,
若 γ> θ0时,采用直接行驶最优,
思考题,你能证明最后一点吗?
3.加速度有限制的运动
考虑最速推车问题,将一辆静止于 A
点的车到 B点停住,在加速度有限制
-b ≤ f ≤ a(a,b>0)
的情形下,求时间最短的推车方法,
设速度函数为 v(t),则上述问题的数学模型为,
.T
)BA,( )(
,)(
,0)()0(
T
0
达到最小值下使得间的距离为约束
ssdttv
atf
dt
dv
b
Tvv条件在考虑一种极端的情形,推车分成加速和减速两个阶段,加速度分别为 a和 -b,即都取到最大限度的值,设推车所用时间为 T0,则
.),(
,0,
)()(
0
0
0
0
0
Tt
ba
bT
tTb
ba
bT
tat
tvtv
下面我们计算出 T0的值,由
0
0
0 )(
T
dttvs,
2
1 2
0Tba
ab
由此解得
,)(20
ab
sbaT
可以证明,用此法推车用时最少,
事实上,若某一满足约束条件的 v(t)推车时间更省,设其用时为 T,那么有 T<T0.
构造函数
.),(
,0,
)(
0
Tt
ba
bT
tTb
ba
bT
tat
tv
.0)()(
],0[,0)0()0(
,],0[)()(
,0)())()((,0
tvtv
ba
bT
vv
ba
bT
tvtv
tfatvtv
dt
d
ba
bT
t
上由此推出在区间而上单调增加在区间故时当
.0)()(,
.0)()(,],[
tvtv
tvtvT
ba
bT
恒有从而上同理可证在区间得由,21)()(
00
Tba abdttvdttvs
TT
,)(2 0Tab sbaT
这与 T<T0矛盾,这说明用速度 v0推车用时最少,
此时速度不是光滑函数,最优解在控制变量 ---
-速度取极端值时实现,
推广,增加约束 v(t) ≤ K(K为常数 ).
可以证明,最优解 v(t)由满足 f=a,v(t)=K,
f=-b的三段构成 (如图所示 ).
K
O
v
t
f=a f=-b
V=at
4.曲率有限制的情形一辆汽车,静止于 A处,要开到与车身垂直方向的
B处,不能倒车,沿什么路径行驶路程最短?从 A到
B必须拐弯,但是车身有一定长度,转弯不能转得太小,即路径的曲率 κ不能太大,故约束条件为
./1 aa 或曲率半径设路径轨迹为 (x(t),y(t)),故数学模型为,已知
(x(0),y(0)),(x(T),y(T)),在约束条件
atytx
tytxtytx
a
1
))()((
)()()()(1
2/322
下使
dttytxs
T
0
22 )]([)]([
达到最小,
分情形讨论,可用初等方法求解,
(i) |AB|>2a
首先,我们可以证明最优路径与线段 AB围成的区域必是凸区域,进一步可以证明最优路径为,半径为 a的圆弧
AC,以及它的切线段
CB,A B
C
O
(ii) |AB|=b<2a
遵循最优解往往对应于控制变量取极端值的情形的思路,我们可以构造出如下解 (如图 ):
C
A B
Oa
a
此时,路径 ACB的长为
.)a r c s i n23(2 2 aa abbabs
我们也可以构造出以下形式的解 (如图 ):
先往左边开,圆心为 O1,半径为 a;接着往右开,圆心为 O2,半径为 a.此时
O1
O2a
a
α bA
C
B
β
)
4
24ar cco s
44
24ar cco s2(
)2(
2
2
2
2 22
a
baba
aba
babaa
as
可以证明,当
b<2a时,s′<s.即由此两圆弧段构成的路径为最优,
b/a 0 0.5 1 1.5 2
(s-s′)/a 0 0.13 0.24 0.27 0
.0
2
2
3
2
2)(,0
2
23)(
,0)(,0)2()0(
02 7 4 6.0)3 7 8.1(,3 7 8.1 ( 0,2 )
,01460)(
,
)4)(2)(2()1(
63
2
)(
,20
),1a rc s i n (
44
24
a rc c o s)
42
1a rc c o s (
2
2)(
limlim
20
23
2
2
22
2
xxf
x
xf
xfff
fx
xxxf
xxxxx
xx
xx
x
xf
x
x
x
xxxx
xxxf
xx
故由于求得根为在区间得令则这里函数进一步，我们考虑如下
.20
),1a rc s i n (44 24a rc co s)421a rc co s (22)(
22
2
x
xx xxxxxxxf
这里
0 0,2 0,4 0,6 0,8 1 1,2 1,4 1,6 1,8 2
0
0,0 5
0,1
0,1 5
0,2
0,2 5
0,3
0,3 5
)( xf
图形法
X=0:0.01:2;
u=sqrt(2*x-x.^2)+acos(1-x/2-x.^2/4)
-acos((4+2*x+x.^2)./(4+4*x))-asin(x-1)-pi/2;
plot(x,u)
附,Matlab作 f(x)图形
1,限定区域的问题
如图,从平面上的 A(-2,0)经上半平面驾驶到
B(2,0),不能穿过湖所在的区域 D:x2+y2<1,
求最短路径,
B(2,0)A(-2,0)
背景知识? 平面上连接两点的最短路径是连接这两点的直线段,
如图,在一个环扇形区域内连接两条向径的最短路径是圆弧 EF.
EF| | PQ| |≤
).())((
|,OE|r),(:
,PQ,
22
rdl
PQ 则记曲线时曲线我们以极坐标形式表示事实上
O
FE QP
思考 1:在 y轴上取一点 C(0,y),使得折线 ACB
与区域 O不交,于是其长度为
.)4(2|| 2/12yACB
显然,|ACB|随着 y的减小而减小,减小 y使得 y= y1
时 C1(0,y1)满足,A C1与 C1 B都与区域 D的边界相切,切点分别记为 E和 F.
B(2,0)A(-2,0)
C1?
C?
E F
因此,我们得到,折线 A C1 B是最短的折线,
且
AE? OE,BF? OF;
由于弧 EF比折线 E C1 F更短的路径,可以证明路径,直线段 AE,弧 EF,直线段 FB是最短的路径,
B(2,0)A(-2,0)
C1?
C?
E F
O
路径,直线段 AE,弧 EF,直线段 FB是最短的路径,
证明是很容易的,我们延长 OE和 OF,任何一条连接 AB的路径交 OE,OF的延长线于 P,Q,则由
|AE|<=|AP|,|FB|<=|QB|,弧 EF的长度不大于曲线段 PQ的长度,
B(2,0)A(-2,0)
C1?
C?
P Q
FE
O
结论,具有有限区域的最短路径是由两部分构成的,一部分是平面上的自然最短路径
(即直线段 ),另一部分是区域的自然边界,这两部分是相切地互相连接,
B(2,0)A(-2,0)
C1?
C?
P Q
FE
O
思考题：
·
·
A
B
寻找从 A到 B的最短路径,不能经过图中的阴影区域,
驾驶问题的模型
(1)交通工具从起点 (a0,b0)驶到终点 (a,b);
(2) 运动轨迹限定在某一区域中或前进方向的角度受到限制 ;
(3) 达到最优 (行驶距离最短,用时最少或费用最省 ).
像上面的这个例子,在驾驶车辆、船舶等交通工具时经常会遇到某些约束条件 (车不入湖,船不上岸,飞机必须绕过高山 ),如何将交通工具从一个地方行驶到另一个地方,使得某种经济效果最优,即,
像刚才的例子,一般地可以写成,设其运动轨迹为 x(t),y(t),0 ≤t ≤T.则我们求运动距离
dttytxs
T
0
22 )]([)]([
最小的路径,这里 x(t),y(t)满足
.0)(,1)()(;0)(,2)(;0)0(,2)0(
22
tytytx
TyTxyx
这实际上是一个具体的最优控制问题,其一般形式是,有若干个状态变量 x(t)=(x1(t),…,
xn(t))和若干个控制变量 α(t)=(α1(t),…,
α n(t)).
要求选择控制变量 α(t),在状态变量满足方程和一定的定解条件
)()(,)0(
)),(),((
0 或落在某超曲面上TxTxxx
tttxf
dt
dx
以及满足一定的约束条件
0))((,0))(( ttx
的前提下,使目标泛函
T
dtttxG
0
))(),((?
达到最小,这里 φ,ψ分别为向量函数,
2.具有优先方向的运动
问题,在风速风向不变的情形下,为帆船选择一条最佳航行路径,设海面上刮东风,要找出从 A点行至位于其东侧的 B点的最佳路径,
A
B
风向背景知识
风从东边吹来,帆船能否往偏东方向行驶?
具有帆船知识的人知道,通过调节帆船的方向和操纵船舵可以使船向偏东方向前进,利用这种方法操纵船走之字形路线,可以使帆船到达位于正东方向的任何地点,风向
w(风力 )
P
α
θ
F
θ:船的前进方向与正东方向的夹角,
α:帆与正东方向的夹角,
先进行力的分析,设帆的面积为 C0,则风力垂直于帆面的分力为
P= C0 w sinα.
将此力沿帆船的前进方向及横向分解,(横向的分力由舵产生的力抵消 ),得到沿帆船前进方向的分力为风向
w(风力 )
P
α
θ
F
].c o s)2[ c o s (
)s i n (s i n
)s i n (
1
0
C
wC
PF
].c o s)2[ c o s (
)s i n (s i n)s i n (
1
0
C
wCPF
由此易知,当 α= θ/2时,此力 F达到最大,此时
).c o s1(1 CF
风向
w(风力 )
P
α
θ
F
另一方面,风也会对船体产生阻力,其阻力
(即风吹在帆船上的力沿船的前进方向的分力 )大小
G= C2 cos θ,
其中 C2与风力以及船的形状有关,G
这样由风产生的推动船沿与正东方向成 θ角的推进力为
).c o s1()c o s1( 1
1
21
1
C
C
CCCGF
由流体力学我们知道,在行驶速度不大时,船行驶的速度正比于船所受的推进力,故船前进的速度为
),c o s1(0 vv
这里 v0是一个正常数,为确定起见,我们选定
σ的一个值,比如 σ =2,对一般情形我们可以类似讨论,此时速度公式为
c o s)c o s1( 21 CCGF
此时有时等号成立当且仅当易知帆船的向东分速度为
.
4275)4/1(a r cc o s
,
8
1
])
4
1
( c o s
16
1
[2
,c o s)c o s21(c o s
).c o s21(
0
0
2
0
0
0
vvv
vvv
vv
e
e
),c o s1(0 vv
.21,81 00 vvvv e
w
v
.4275,
2
1,
8
1
000vvvv e
即当 θ=θ0时,向东分速度达到最大值,所以当目的地位于正东时,取与正东夹角为 θ0的行驶路线 (如图中的折线 ACB).这种行驶方式称为 抢风行驶,
θ0 θ0
B
C
A
风向若目的地不在正东
设目的地与正东方向的夹角为 γ.首先讨论 γ<
θ0的情形,若 γ<60o,则从上面的速度公式可以看出,直接行驶是不可能的,也必须采取折线行驶,若采用抢风行驶,如图,行驶路线为折线 ACB.
θ0 θ0
D
C
A
风向
B
γ
./c o s|AB|8)81/(c o s|AB:| 00 vv所需时间为可以证明,此时抢风行驶是最快的,证明如下,
设 A,B的坐标分别是 (0,0),(a,b),则沿任何一条分段光滑的路径行驶所需的时间为
).8//(c o s||v8a8 0
000
vABdxv
a
a
xxv
dxT
0 )(c o s)(?
a
xxv
dx
0 0 )(c o s))(c o s21(
.
.(a,b)
x
y
dxx?x
)(x?
)(xv
同理,当 60o≤γ< θ0时,抢风行驶仍为最优,
此时虽然可以直接行驶,但所需时间较长,
若 γ> θ0时,采用直接行驶最优,
思考题,你能证明最后一点吗?
3.加速度有限制的运动
考虑最速推车问题,将一辆静止于 A
点的车到 B点停住,在加速度有限制
-b ≤ f ≤ a(a,b>0)
的情形下,求时间最短的推车方法,
设速度函数为 v(t),则上述问题的数学模型为,
.T
)BA,( )(
,)(
,0)()0(
T
0
达到最小值下使得间的距离为约束
ssdttv
atf
dt
dv
b
Tvv条件在考虑一种极端的情形,推车分成加速和减速两个阶段,加速度分别为 a和 -b,即都取到最大限度的值,设推车所用时间为 T0,则
.),(
,0,
)()(
0
0
0
0
0
Tt
ba
bT
tTb
ba
bT
tat
tvtv
下面我们计算出 T0的值,由
0
0
0 )(
T
dttvs,
2
1 2
0Tba
ab
由此解得
,)(20
ab
sbaT
可以证明,用此法推车用时最少,
事实上,若某一满足约束条件的 v(t)推车时间更省,设其用时为 T,那么有 T<T0.
构造函数
.),(
,0,
)(
0
Tt
ba
bT
tTb
ba
bT
tat
tv
.0)()(
],0[,0)0()0(
,],0[)()(
,0)())()((,0
tvtv
ba
bT
vv
ba
bT
tvtv
tfatvtv
dt
d
ba
bT
t
上由此推出在区间而上单调增加在区间故时当
.0)()(,
.0)()(,],[
tvtv
tvtvT
ba
bT
恒有从而上同理可证在区间得由,21)()(
00
Tba abdttvdttvs
TT
,)(2 0Tab sbaT
这与 T<T0矛盾,这说明用速度 v0推车用时最少,
此时速度不是光滑函数,最优解在控制变量 ---
-速度取极端值时实现,
推广,增加约束 v(t) ≤ K(K为常数 ).
可以证明,最优解 v(t)由满足 f=a,v(t)=K,
f=-b的三段构成 (如图所示 ).
K
O
v
t
f=a f=-b
V=at
4.曲率有限制的情形一辆汽车,静止于 A处,要开到与车身垂直方向的
B处,不能倒车,沿什么路径行驶路程最短?从 A到
B必须拐弯,但是车身有一定长度,转弯不能转得太小,即路径的曲率 κ不能太大,故约束条件为
./1 aa 或曲率半径设路径轨迹为 (x(t),y(t)),故数学模型为,已知
(x(0),y(0)),(x(T),y(T)),在约束条件
atytx
tytxtytx
a
1
))()((
)()()()(1
2/322
下使
dttytxs
T
0
22 )]([)]([
达到最小,
分情形讨论,可用初等方法求解,
(i) |AB|>2a
首先,我们可以证明最优路径与线段 AB围成的区域必是凸区域,进一步可以证明最优路径为,半径为 a的圆弧
AC,以及它的切线段
CB,A B
C
O
(ii) |AB|=b<2a
遵循最优解往往对应于控制变量取极端值的情形的思路,我们可以构造出如下解 (如图 ):
C
A B
Oa
a
此时,路径 ACB的长为
.)a r c s i n23(2 2 aa abbabs
我们也可以构造出以下形式的解 (如图 ):
先往左边开,圆心为 O1,半径为 a;接着往右开,圆心为 O2,半径为 a.此时
O1
O2a
a
α bA
C
B
β
)
4
24ar cco s
44
24ar cco s2(
)2(
2
2
2
2 22
a
baba
aba
babaa
as
可以证明,当
b<2a时,s′<s.即由此两圆弧段构成的路径为最优,
b/a 0 0.5 1 1.5 2
(s-s′)/a 0 0.13 0.24 0.27 0
.0
2
2
3
2
2)(,0
2
23)(
,0)(,0)2()0(
02 7 4 6.0)3 7 8.1(,3 7 8.1 ( 0,2 )
,01460)(
,
)4)(2)(2()1(
63
2
)(
,20
),1a rc s i n (
44
24
a rc c o s)
42
1a rc c o s (
2
2)(
limlim
20
23
2
2
22
2
xxf
x
xf
xfff
fx
xxxf
xxxxx
xx
xx
x
xf
x
x
x
xxxx
xxxf
xx
故由于求得根为在区间得令则这里函数进一步，我们考虑如下
.20
),1a rc s i n (44 24a rc co s)421a rc co s (22)(
22
2
x
xx xxxxxxxf
这里
0 0,2 0,4 0,6 0,8 1 1,2 1,4 1,6 1,8 2
0
0,0 5
0,1
0,1 5
0,2
0,2 5
0,3
0,3 5
)( xf
图形法
X=0:0.01:2;
u=sqrt(2*x-x.^2)+acos(1-x/2-x.^2/4)
-acos((4+2*x+x.^2)./(4+4*x))-asin(x-1)-pi/2;
plot(x,u)
附,Matlab作 f(x)图形
