最优控制论文综述

1、最优控制方法的分析和综合摘要：主要阐述了关于最优控制问题的基本概念，最优控制是最优化方法的一个应用。最优化一般可以分为最优设计、最优计划、 最优管理和最优控制四个方面。而最优控制理论是研究和解决从一切可能的控制方案中寻找最优解的一门学科，解决最优控制问题的主要方法有古典变分法、 极大值原理和动态规划。通过以上知识的讲解使初学者能够快速掌握最优控制的问题。 最优控制是最优化方法的一个应用，如果想了解最优控制必须知道什么是最优化方法。所谓最优化方法为了达到最优化目的所提出的各种求解方法。第一章最优控制的一般概念1.1背景知识在现代科学技术的众多领域中，自动控制技术起着越来越重要的作用。所谓的自动控

2、制，是指在没有人直接参与的情况下，利用外加的设备和装置，是机器、 设备或生产过程的某个工作状态或参数自动按照预定的规律运行。近几十年来，随着电子计算机技术的发展和应用，在宇宙航行、 机器人控制、 导弹制导以及核动力等高新技术的领域中，自动控制技术更具有特别重要的作用。自动控制理论是研究自动控制共同规律的技术科学。它的发展初期， 是以反馈理论为基础的自动调节原理，主要用于工业控制。第二次世界大战期间，为了设计和制造飞机及船用自动驾驶仪、 火炮定位系统、 雷达跟踪系统以及其它基于反馈原理的军用装备，进一步促进并完善了自动控制理论的发展。到战后， 已形成完整的自动控制理论体系，这就是以传递函数为基础

3、的经典控制理论，它主要研究单输入单输出、线性定常系统的分析和设计问题。随着现代应用数学新成果的推出和电子计算机技术的应用，为适应宇航技术的发展，自动控制理论跨入了一个新阶段现代控制理论。它主要研究具有高性能、高精度的多变量变参数系统的最忧控制问题，主要采用的方法是以状态为基础的状态空间法。从数学意义上说，最优化方法是一种求极值的方法，即在一组约束为等式或不等式的条件下，使系统的目标函数达到极值，即最大值或最小值。从经济意义上说，是在一定的人力、物力和财力资源条件下，使经济效果达到最大（如产值、利润），或者在完成规定的生产或经济任务下，使投入的人力、物力和财力等资源为最少。最优化一般可以分为最优

4、设计、最优计划、最优管理和最优控制四个方面。（1 ）最优设计: 世界各国工程技术界,尤其是飞机、造船、机械、建筑等部门都已广泛应用最优化方法于设计中， 从各种设计参数的优选到最佳结构形状的选取等，结合有限元方法已使许多设计优化问题得到解决。 一个新的发展动向是最优设计和计算机辅助设计相结合。电子线路的最优设计是另一个应用最优化方法的重要领域，它存在着巨大的开发潜力，尤其是对于学电工学1的学生来说。配方配比的优选方面在化工、橡胶、塑料等工业部门都得到成功的应用,并向计算机辅助搜索最佳配方、配比方向发展。 （ 2）最优计划 :现代国民经济或部门经济的计划，直至企业的发展规划和年度生产计划，尤其是农

5、业规划、种植计划、能源规划和其他资源、环境和生态规划的制订 ,都已开始应用最优化方法。一个重要的发展趋势是帮助领导部门进行各种优化决策，使工作结构简单，工作效率最高化，节省了很多时间。（3）最优管理：一般在日常生产计划的制订、调度和运行中都可应用最优化方法。随着管理信息系统和决策支持系统的建立和使用，使最优管理得到迅速的发展。（4）最优控制：主要用于对各种控制系统的优化。最优控制理论是研究和解决从一切可能的控制方案中寻找最优解的一门学科。它是现代控制理论的重要组成部分。这方面的开创性工作主要是由贝尔曼提出的动态规划和庞特里亚金等人提出的最大值原理。这方面的先期工作应该追溯到维纳等人奠基的控制论

6、。1948年维纳发表了题为 控制论 关于动物和机器中控制与通讯的科学的论文， 第一次科学的提出了信息、反馈和控制的概念，为最优控制理论的诞生和发展奠定了基础。钱学森1954年所著的工程控制论直接促进了最优控制理论的发展和形成1.2 最优控制的概念在经典控制理论中， 设计控制系统的各种方法大多建立在试凑的基础上，设计结果与设计人员的经验有很大的关系。对于多输入多输出系统，或者要求高控制精度的复杂系统，经典方法显得无能为力，迫切需要探索新的设计方法。20 年代 60 年代初，由于空间技术的迅猛发展和计算机的广泛应用，动态系统的优化理论得到了迅速的发展，形成了最优控制这一重要的学科分支，并在控制工程

7、、经济管理与决策以及人口控制等领域得到了成功的应用，取得了显著地成效。 最优控制在被控对象参数已知的情况下，已经成为设计复杂系统的有效方法之一。最优控制是现代控制理论的核心。所谓最优控制， 就是在一定的条件下，在完成所要求的控制任务时， 使系统的某种性能指标具有最优值。最优控制系统的设计， 就是选择最优控制，以使某一种性能指标为最小。为了解决最优控制问题，必须建立描述受控运动过程的运动方程，即系统的数学模型，给出控制变量的允许取值范围，指定运动过程的初始状态和目标状态，并且规定一个评价运动过程品质优劣的性能指标。通常，性能指标的好坏取决于所选择的控制函数和相应的运动状态。系统的运动状态受到运动

8、方程的约束，而控制函数只能在允许的范围内选取。最优控制研究的主要问题是： 根据已建立的被控对象的数学模型，选择一个容许的控制律，使得被控对象按预定要求运行， 并使给定的某一性能指标达到极限值。从数学的观点来看，最优控制研究的问题是求解一类带有约束条件的泛函极值问题，属于变分学的范畴。然而，经典变分理论只能解决控制无约束，即容许控制属于开集的一类最优控制问题，为了满足工程实践的需要，出现了现代变分理论，其中最常用的方法是动态规划和极小值原理。2第二章经典变分法2.1函数与变分2.1.1泛函的概念如果变量 j 对于某一函数类中的每一个函数x(t)，都有一个确定的值与之对应，那么就称变量 j 为依赖

9、于函数x( t)的泛函，记为： j=j x(t) 。例 2.1.1函数的定积分1. 连续时间系统：1jx(t)dt0是泛函。因为变量j 的值是由函数的选取而确定的。所以最简单的一类泛函可表示为：j x(t )t flx(t ), x(t ), tdtt0连续泛函如果满足下列条件：（ 1） jx1(t)+ x2(t)= jx1(t)+ jx2(t)（ 2） jcx(t)= cjx(t)其中， c 是任意常数，就称为线性泛函。例如j x(t )t2tx(t) (sin t )x(t)dtt1t 2j x(t ) p(t) x(t )q(t) x( t)dtt 1j x( t)x(t) t 2都满足

10、上述两个条件，故均为线性泛函。连续泛函如果满足下列条件：（ 1） jx1(t)+ jx2(t)=1/2 jx1(t)+x2(t)+ jx1(t)-x2(t)（ 2） jcx(t)= c2jx( t)就称为 *二次型泛函 *。例如1 xt (t f )fx ( t f )t fj1xt (t )qx (t)dt22 t0是关于 x(t) 的二次型泛函，其中f 、 q 均为对称矩阵。2.1.2 泛函的变分变分法（ calculus of variations ）是处理函数的函数的数学领域，和处理数的函数的普通微积分相对。 譬如，这样的泛函可以通过未知函数的积分和它的导数来构造。变分法最终寻求的是极

11、值函数：它们使得泛函取得极大或极小值。如果连续泛函jx(t)的增量可以表示为：j x( t)j x(t)x(t)j x( t)l x( t),x( t)r x(t),x( t)（ 2.1.1）其中， lx(t)， x(t) 是关于 x(t)的线性连续泛函，而 r x(t) ， x(t)是关于 x( t)的高阶无穷小。lx(t)， x(t) 称为泛函的变分，记为jl x(t ),x(t)也就是说， 泛函的变分是泛函增量的线性主部。当一个泛函具有变分时，即泛函的增量可以3用式（ 2.1.1）来表示时，称该泛函是可微的。例如，泛函 j x(t )1x2 (t)dt 的增量为：0j1x(t )2 dt

12、1(t)dt x(t )x21000 2 x(t)x(t )x2 (t)dt12x( t)x(t)dt1(t)dt0x20于是，其变分为 ：1x(t)dtj2 x(t)0可以证明， 泛函的变分是唯一的。因为，若泛函的变分不是唯一的，则泛函的增量可以写为：j l1 x(t),x(t ) r1x(t ),x(t )l2 x(t), x(t) r2 x(t), x(t )l1 x( t), x( t)l2 x(t ),x(t )l x( t), x(t )泛函 jx( t) 的变分为：jj x(t )x( t)0例 2.1.4求泛函1x 2( t)dt 的变分。0该泛函的变分为：jj x(t )x(

13、 t)01x( t) 2 dt x(t )001 x(t)x(t )2dt001x( t)x(t )dt2 x(t )001x(t )dt2 x(t)02.1.3 泛函的极值如果泛函jx(t) 在函数空间中点x=x0(t) 的邻域内，其增量为：jj x( t)j x0 (t )0就称泛函 jx(t) 在点 x0(t)处达到极小值；如果泛函 jx(t) 在函数空间中点x=x0(t) 的邻域内，其增量为：jj x( t)j x0 (t )0就称泛函 jx(t) 在点 x0(t)处达到极大值；x0(t)的邻域包含满足条件： dx(t), x0 (t)的所有点 x(t)的球（即以 x0(t) 为圆心，

14、以为半径的球）。定理（必要条件）若泛函 jx(t) 是连续可微的，并且在点x0(t)处达到极值，则泛函在点x0(t)处的变分等于零，即j x0 ( t), x( t) 02.2 欧拉方程42.2.1 三类基本问题最优控制问题中，根据性能指标的类型（积分型性能指标、终值型性能指标、复合型性能指标）的不同，分别对应了古典变分法中的三类基本问题。拉格朗日（ lagrange）问题 基本问题t fj x(t)l x(t), x(t), tdt(2.2.1)t0麦耶耳 (mayer) 问题j x(t ) x(t f), t f(2.2.2)波尔扎（ bolza）问题j x(t ) x(t f), t f

15、tfl x(t ), x(t), t dt(2.2.3)t0固定端点的 lagrange 问题问题描述：假定点a( t0,x0)和 b(tf , xf)是所要寻求的泛函（1.2.1）的极值曲线x(t)的两个固定端点，如图 1-5 所示，其坐标为：x( t0 )x0(2.2.4)x( tf )x ftf问题：从满足边界条件的二阶可微的函数中，选择使泛函 j x(t)l x(t ), x(t), t dt 达到t0极小值的函数 x(t)解:设 x*(t) 是使泛函达到极小值且满足边界条件的极值曲线。现用x( t)x*( t )x( t)(2.2.5)表示满足边界条件的极值曲线x*( t)的邻域曲线

16、。 其中 x(t)是泛函宗量x(t)的变分， (01)是一参变量。为使x(t) 是满足边界条件的极值曲线x* (t)的邻域曲线，x(t)应具有连续导数且满足条件：x(t0)=x(tf)=0(2.2.6)于是，得到x(t ) x*( t )x(t)(2.2.7)由于 x* (t)是极值曲线，所以泛函tfx* (t)上的变分等j x(t )l x(t), x(t ),t dt 在极值曲线t 0于零，即 (2.2.1)j0(2.2.8)泛函的变分为jj x *( t )x(t)(2.2.9)0将式（ 2.2.1）代入式（ 2.2.9），得jj x *( t )x(t )0t fx(t), x *(

17、t)x(t), tdtl x *( t )t00t fl x *( t)x( t), x *( t)x(t), tdtt005t fl x *(t), x *( t), tx(t)l x *( t), x *( t), tt0x( t)x( t)t fx( t)lxx(t )dt lxt0对式（ 2.2.10）右端第二项进行分部积分t ft ft f( d lx ) x(t)dtlx x(t )dtlxx(t ) t0t0t0dt将式（ 2.2.11）代入式（ 2.2.10），并考虑式j0得t fdt ft0 ( lxlx )x( t)dtlx x(t ) t0 0dt利用条件x(t0)= x

18、(tf)=0 ，则上式变为t fd lx )x( t)dt0(lxt0dt考虑到泛函宗量的变分x(t)是任意的函数，不妨选择x( t)w(t)lxd lxdt其中 w(t)是任一满足下列条件的函数：w(t )0, t t0 ,tt f(c 为某一函数 )c2 , t0tt f将式（ 2.2.14）代入式（ 2.2.13），可得t fd lx2lxdt0w( t)t0dt由上式可见，一个非负的函数的定积分为零，只能是被积函数恒等于零，因此有lxd l x0dt将上式左端第二项展开，可得lxlxt xlxx xlxx02 l, lxx2 l2 l式中 lxt, lxxt xx xx 2若 lxx

19、0 时，欧拉方程是一个二阶微分方程。定理 2.2.1若给定曲线 x(t) 的始端 x(t0)= x0和终端 x(tf)= xf，则泛函t fj x(t )lx(t), x(t), tdtt0达到极值的必要条件是，曲线x(t)满足欧拉方程lxd0l xdt其中 x(t)应有连续的二阶导数，l x(t ), x(t ), t 则至少应是二次连续可微的。x( t)dt(2.2.10)（ 2.2.11）（ 2.2.12）（ 2.2.13）（ 2.2.14）2.2.2 几种特殊的欧拉方程1.被积函数l 不显含 t，即 ll( x, x)在这种情况下，欧拉方程的首次积分为l xlx c（2.2.17）其中

20、 c 是待定的积分常数。62.被积函数l 不显含 x，即 ll( t, x)在这种情况下，欧拉方程的首次积分为l x03.被积函数l 不显含 x ，即 ll(t, x)在这种情况下，欧拉方程的首次积分为ddt2.3 横截条件l x0当极值曲线tfx*( t)首先x* (t)的端点变化时，要使泛函 j x(t)l x(t ), x( t), t 达到极小值，t 0应当满足欧拉方程：dlxdt l x0若端点固定 ,可以利用端点条件:x(t0 )x0x(t f )x f确定欧拉方程中的两个待定的积分常数。定理 2.3.1 若曲线 x(t) 由一给定的点 (t0，x0)到给定的曲线 x( tf)=

21、(tf)上的某一点 (tf ， xf)，则泛函t fj x(t )l x(t), x(t ),t t 0达到极值的必要条件是，x(t)满足欧拉方程dlx 0lxdt和横截条件 l (x)lx t t *f0其中 x(t)应有连续的二阶导数，l x(t), x(t ),t 则至少应是二次连续可微的，而(t) 则应有连续的一阶导数。(1) 始端、终端可变，即x(t0)=(t0)， x(tf)= ( tf)，则横截条件为： l (x)lx t t0*0 l (x)lx t t*f0(2) 当 t0、 tf 可变，而 x(t0)与 x(tf)固定时，则横截条件为： lxlx t t 0*0, lxlx

22、 t t *f07(3) 当 t0、 tf 固定，而 x(t0) 与 x(tf)可变时，即始端与终端分别在 t=t0、t=tf 上滑动，则横截条件为：lx*x(t *f )l x* (t ), x* (t ), t t*dt f 0lx*0t t ftft t f同理 :lx t t 0*0例求 t -x 平面上由给定a(0,1)至给定直线x=2-t 的弧长最短的曲线方程。解：由图2 8，弧长x2x*( t)1da(0,1)o12t图 2 8ds(dt ) 2(dx) 21x 2 dt根据题意，目标泛函应选为：jt f1 x2 dt0这是一个始端固定，终端可变的泛函的变分问题。由于泛函的被积函

23、数l 1 x2中不显含 x(t)，所以 euler 方程为：dxdt 10x2xxcx c1t c21c1c1x2c2由初始条件x(0)=1 ，得 c2=1，从而有xc1t18由横截条件，得1 x2( 1 x)x01x2 整理得 x1 ，所以 c1=1 。最 方程 ：x * (t )t1最 与 定直 垂直。t *f122.4 利用变分法求解最优控制问题 于最 控制 来 ，当状 量和控制 量均不受 束，即x(t)rn，u(t)rm ，是在等式 束条件下求泛函极 的 分 ，因此，可以利用在上一 中介 的拉格朗日乘子法来求解。在 一 中，利用拉格朗日乘子法求解最 控制 ，将引入哈密 函数，推 出几种

24、典型的最 控制 足的必要条件。 定系 状 方程x (t)f x (t),u (t ), t（2.4.1）初始条件x (t0 )x 0（2.4.2） 端条件： tf 固定， x(tf)自由和性能泛函t fjl x (t ),u (t), t dt（2.4.3）t 0要求从容 控制u (t)rm 中确定最 控制u*( t)，使系 （ 2.4.1）从 定的初 x(t0) 移到某个 x(tf) ，并使性能泛函（ 2.4.3）达到极小 。 是拉格朗日 ，又称 分型最 控制 。解：将状 方程（2.4.1）改写 f x (t),u (t), t x (t ) 0（2.4.4）于是，上述最 控制 就 成 在微

25、分方程（2.6.4） 束条件下求泛函（2.6.3）极 的 分 。利用拉格朗日乘子法，引入n 拉格朗日乘子向量(t)= 1(t),2(t), , n (t)t( t)称 量，以便与状 量相 。构造 助泛函j0t fl x (t),u (t ), tt (t ) f x (t),u (t ), t x (t ) dtt 0t f(t),u (t ), t dt（2.4.5）f x (t), x (t ),t0f x (t ), x (t ),(t),u (t), t l x (t ),u (t), t （2.4.6）其中，t (t ) f x (t),u (t ), t x (t )于是，求泛函（

26、 2.4.3）在等式（ 2.4.1 ） 束条件下的极 ，就 成 求泛函（2.4.5）的无 束条件的极 。定 哈密 （hamilton ）函数 :9h x (t), x (t), (t ),u (t), t l x (t ),u (t), t t (t) f x (t),u (t), t （2.4.7）它是一标量函数，则式（2.4.6）变为f x (t ), x (t ),(t),u (t ), th x (t ),(t ),u (t), tt (t ) x (t )h x (t ),(t ),u (t), tx t (t ) (t )（2.4.8）利用变分法可以写出辅助泛函（2.4.5 ）的欧

27、拉方程fdf0, f d f0, f d f0xdtxdtudt u将式（ 2.4.8）代入上式，得(t)hxx (t)hf x (t ),u (t ), t（2.4.9）h0u初始状态为 x (t0 )x 0（2.4.10）由于终端时刻tf 固定，终端状态x(tf)自由，所以横截条件为f0x t t f考虑式（ 2.4.8），得(t f ) 0（ 2.4.11）式（ 2.4.9）（ 2.4.11）就是式（ 2.4.1）（ 2.4.3）所给定的最优控制问题的解应满足的必要条件。这些条件也可以由求辅助泛函j0 对状态变量x(t) 和控制变量u(t) 的变分中推导出来。第三章极大值原理3.1连续系

28、统的极大值原理问题 3.1.1( 积分型最优控制问题) 给定系统的状态方程：x ( t )f x ( t ), u ( t ), t (3.1.1)其中， f 是 n 维连续可微的向量函数；x(t)是 n 维状态变量，其初态 x(t0)=x0， 而终态应满足的条件是：终端时刻tf 固定，终端状态x(tf)自由， u(t)是 m 维控制变量，其所受约束条件是u( t ),t t 0 , t f (3.1.2)其中，是以 u(t)为元素的 m 维实函数空间中的一个闭子集。式(3.1.2) 表明，控制变量是这个闭子集中的元素。 满足式 (3.1.2) 约束条件的控制变量称为容许控制变量，简称容许控1

29、0制。要求在满足式 (3.1.2) 的容许控制中，确定一控制变量 u(t)，使系统（ 3.1.1）从给定的初态 x(t0)转移到某个终态 x(tf) 的过程中，性能泛函t fjl x ( t ), u ( t ), t dtt 0达到极小值。其中l 是连续可微的标量函数。这个积分型最优控制问题所确定的控制u(t)称为最优控制，记为u *( t)。使性能泛函达到极小值的最优控制的必要条件是哈密顿函数h 达到最大值，所以，该定理称为最（极）大值原理。3.2最大值原理的几种具体形式定理 3.2.1( 时不变情况 )给定系统的状态方程：x(t )f x(t ),u(t)（3.2.1）的初态 x(t0)

30、=x0 和终端时刻 tf 固定，终端状态x(tf)自由，控制函数的约束条件u( t ),t t 0, t f（3.2.2）要求从满足约束条件（3.2.2）的容许控制中，确定一最优控制u*( t)，使性能泛函取得最小值：t fju(t ) x(t f)l x(t), u(t) dtt0（ 3.2.3 ）定义 hamilton函数为：h x(t ), u(t ),(t)l x(t), u(t )t (t ) f x(t ), u(t )（3.2.4）式中 (t) 1 (t ),2 (t ),.,n (t)t为待定的 n 维拉格朗日乘子向量。欲使性能指标达最小值，以实现最优控制的必要条件为：1、正则

31、方程组状态方程x(t )hf x(t ), u(t)(3.2.5)协态方程( t )h(3.2.6)x2、极值条件*(t ),(t )*(t), u(t ),(t)(3.2.7)h x(t ), umin h x3、端点约束u ( t )x* (t0 )x04、横截条件 x(t f)(t f)x(t f )(3.2.8)定理 3.2.2( 时变情况 )给定系统的状态方程：x(t) f x(t ), u(t), t （3.2.9）的初态 x(t0)= x0 和 终端时刻 tf 固定，终端状态 x(tf)自由，控制函数的约束条件u (t ),t t0, t f （3.2.10）11要求从满足约束条

32、件（ 3.2.10）的容许控制中，确定一最优控制u*( t)，使性能泛函取得最小值tfju(t ) x(t f ), t f l x(t ), u(t ), tdtt0(3.2.11)定义 hamilton函数为：h x(t ), u(t ),(t), t l x(t ), u(t ), t t (t) f x(t ), u(t), t(3.2.12)式中 (t ) 1 (t ), 2 (t ),., n (t)t 为待定的 n 维拉格朗日乘子向量。欲使性能指标达最小值，以实现最优控制的必要条件为：1、正则方程组hx( t )x ( t ), u( t ), t 状态方程f (3.2.13)协

33、态方程( t )hx(3.2.14)2、极值条件h x* (t), u* (t),(t ), t minh x* (t), u(t), (t ), tu(t )3、端点约束x* (t) x004、横截条件(t f ) x(t f), t fx(t f)例题已知系统的状态方程和端点条件为控制约束为求目标泛函j1xdt 的极大值0解：首先引入hamilton 函数并注意到哈密顿函数是u 的线性泛函，根据 控制方程h x (t),(t),u (t), t maxuh x (t ), (t),u (t), t要使 h 取极大值的最优控制则为：12由于方程中未包含x 和 u, 我们很容易就得到 的表达式

34、：为求, 根据协态方程并根据横截条件（边界条件）将最优控制量和端点条件代入状态方程x*1 得：最优状态轨线为：第四章动态规划4.1 多级决策问题动态规划是美国学者贝尔曼（bellman ）在上世纪50 年代中期创立的，是求解最优控制问题的重要方法之一。最初被用来研究多级决策的最优化问题。但时至今日， 它已在许多领域里获得了广泛、成功的应用。动态规划的理论基础是所谓的贝尔曼最优性原理。动态规划研究的对象是多级决策过程的最优化问题，它在理论和实践上的重要意义在于：1 ）对于离散控制系统，可以用来得到某些理论结果，并可建立起数字计算机的递推或迭代程序；2）对于连续控制系统，除了可以用来得到某些理论结

35、果以外，还可以用来建立与变分法和最大值原理的联系。确定最优行车路线问题x 1(1) 6x 1(21 x 1(3)4614sf542372x2(1)x 2(2x 2(3)第一段第二段第三段第四段图 1这是一个多级决策问题。汽车从s 站到终点站f 有不同的行车路线。各条路线的路程是不13同的，为使从s 站到 f 站的路程为最短，司机在路程的前三段要做三次决策（选择）。由图5 1 可见，汽车经过每站时，可供选择的决策至多有两个。用p 和 q 分别表示走上面路线还是走下面路线的两种不同决策。那么，司机怎样决策才能使所经过的路程为最短？有两种方法：穷举法：找出所有可能(2n-1=8) 的行车路线，将每条

36、路线的每段距离加起来，就可算出每种路线的行车路程。选择其中最小者，便是路程最短的行车路线。动态规划法：从最后一段开始，由后往前，依次确定各站到终点站f 的最优路线，直至计算出起始站s 到终点站 f 的最优路线。利用动态规划法求解最优行车路线问题第一步：(a) 路线 x1(3) f， j* x1(3) 4(b) 路线 x2(3) f， j* x2(3) 3第二步：(a)路线 x1(2)x1(3)f ，j=1+j* x1(3)5路线 x1(2)x2(3)f ，j=1+j* x2(3)4比较：路线x1(2)x2(3)f 更短，所以 j* x1(2)=4，最优决策为q；(b)路线 x2(2)x1(3)f ，j=2+j* x1(3)6路线 x2(2)x2(3)f ，j=2+j* x2(3)5比较：路线x2(2)x2(3)f 更短，所以 j* x2(2)=5，最优决策为 q；第三步(a)路线 x1(1)x1(2)x2(3)f ， j=6 j* x1(2) 10路线 x1(1)x2(2)x2(3)f ， j=6 j* x2(2) 11比较：路线x1(1)x1(2)x2(3)f 更短，所以j* x1(1)=10 ，最优决策为p；(b)路线 x2(1)x1(2)x2(3)f ， j=4 j* x1(2) 8路线 x2(1)x2(2)x2(3)f ， j=7 j* x2(2) 12比较：路线