驾驶问题
驾驶问题
1.限定区域的问题 如图,从平面上的A(-2,0)经上半平面驾驶到 B(2,0)不能穿过湖所在的区域D:x2+y2<1, 求最短路径 A(-2,0) B(2,0)
1. 限定区域的问题 • 如图,从平面上的A(-2,0)经上半平面驾驶到 B(2,0),不能穿过湖所在的区域D:x2+y2<1, 求最短路径. • • A(-2,0) B(2,0)
背景知识 平面上连接两点的 最短路径是连接这 两点的直线段 如图,在一个环扇形 区域内连接两条向 径的最短路径是圆 弧EF EFIPQ 事实上,我们以极坐标形式表示曲线PQ时, 曲线PQ:p=p(0),记r=OE|,则 aV02+(,'(0)2d0≥r(B-a)
背景知识 • 平面上连接两点的 最短路径是连接这 两点的直线段 . • 如图 ,在一个环扇形 区域内连接两条向 径的最短路径是圆 弧EF. | EF | ≤ | PQ| ( ( )) ( ). : ( ), r |OE |, , P Q , 2 2 = + − = = l d r 曲 线PQ 记 则 事实上 我们以极坐标形式表示曲 线 时 O •E • F • • P Q
思考1:在y轴上取一点C(02y)2使得折线ACB 与区城O不交于是其长度为 ACB=2(4+y2)2 显然ACB随着y的减小而减小减小y使得y=y1 时C1(0,y1)满足:AC1与C1B都与区域D的边界相 切切点分别记为E和F C C A(-2,0 B(2,0)
思考1:在y轴上取一点C(0,y),使得折线ACB 与区域O不交.于是其长度为 | | 2(4 ) . 2 1/ 2 ACB = + y 显然,|ACB|随着y的减小而减小.减小y使得y= y1 时C1 (0,y1 )满足:A C1与C1 B都与区域D的边界相 切,切点分别记为E和F. • • A(-2,0) B(2,0) • • C1 • •C E F
因此我们得到折线AC1B是最短的折线 且 AE亠OE,BF亠OF 由于弧EF比折线EC1F更短的路径可以证 明路径:直线段AE弧EF直线段FB是最短的 路径. C E F A(-2,0) B(2,0)
因此,我们得到:折线A C1 B是最短的折线. 且 AEᅩOE,BF ᅩOF; 由于弧EF比折线E C1 F更短的路径.可以证 明路径:直线段AE,弧EF,直线段FB是最短的 路径. • • A(-2,0) B(2,0) • • C1 • •C E F O
路径直线段AE弧EF直线段FB是最短的路径. 证明是很容易的:我们延长OE和OF任何一条连 接AB的路径交OEOF的延长线于PQ则由 AE|<=AP|FB<=QB弧EF的长度不大于 曲线段PQ的长度 C A(-2,0) B(2,0)
路径:直线段AE,弧EF,直线段FB是最短的路径. 证明是很容易的:我们延长OE和OF,任何一条连 接AB的路径交OE,OF的延长线于P,Q,则由 |AE|<=|AP|,|FB|<=|QB|,弧EF的长度不大于 曲线段PQ的长度. • • A(-2,0) B(2,0) • • C1 • •C • P • Q E F O
C A(-2,0) B(2. 结论:具有有限区城的最短路径是由两部 分构成的,一部分是平面上的自然最短路径 (即直线段),另一部分是区域的自然边界这 兩部分是相切地互相连接
结论:具有有限区域的最短路径是由两部 分构成的,一部分是平面上的自然最短路径 (即直线段),另一部分是区域的自然边界.这 两部分是相切地互相连接. • • A(-2,0) B(2,0) • • C1 • •C • P • Q E F O
思考题: 寻找从A到B的最短路径,不能经过图中的 阴影区域 B
思考题： · · A B 寻找从A到B的最短路径,不能经过图中的 阴影区域
驾驶问题的模型 像上面的这个例子在驾驶车辆、船舶等交通 工具时经常会遇到某些约束条件(车不入湖,船 不上岸,飞机必须绕过高山),如何将交通工具从 个地方行驶到另一个地方,使得某种经济效 果最优即: (1)交通工具从起点(am0b驶到终点(a,b) (2)运动轨迹限定在某一区域中或前进方向的 角度受到限制; (3)达到最优(行驶距离最短用时最少或费用最 省)
驾驶问题的模型 (1)交通工具从起点(a0 ,b0 )驶到终点(a,b); (2) 运动轨迹限定在某一区域中或前进方向的 角度受到限制; (3) 达到最优(行驶距离最短,用时最少或费用最 省). 像上面的这个例子,在驾驶车辆、船舶等交通 工具时经常会遇到某些约束条件(车不入湖,船 不上岸,飞机必须绕过高山),如何将交通工具从 一个地方行驶到另一个地方,使得某种经济效 果最优.即:
像刚才的例子,一般地可以写成:设其运动轨 迹为x(O)y(),0ssT则我们求运动距离 s=∫x()+)t 最小的路径,这里x()w()满足 x(0)=-2,y(0)=0;x(T)=2,y(T)=0; x2(t)+y(t)≥1,y()≥0. 这实际上是一个具体的最优控制问题其 般形式是有着干个状态变量(=(x1(0), x()和若干个控制变量α(t)=(au1(),, un八()
像刚才的例子,一般地可以写成:设其运动轨 迹为x(t),y(t) ,0 ≤t ≤T.则我们求运动距离 s x t y t dt T = + 0 2 2 [ ( )] [ ( )] 最小的路径,这里x(t),y(t)满足 ( ) ( ) 1, ( ) 0. (0) 2, (0) 0; ( ) 2, ( ) 0; 2 2 + = − = = = x t y t y t x y x T y T 这实际上是一个具体的最优控制问题.其一 般形式是:有若干个状态变量x(t)=(x1 (t),…, xn (t))和若干个控制变量α(t)=(α1 (t),…, α n (t))