数学建模优化理论与方法PPT课件

1、（1）由决策变量构成，反映决策的目标是线性函数。（2）一组由决策变量的线性等式或不等式构成约束 条件。（3）对决策变量取值范围加以限制的非负约束。1.1 线性规划模型的特征线性规划模型的特征 例1：某工厂生产甲、乙两种产品，每件产品的利润、所消耗的材料、工时及每天的材料限额和工时限额，如表1.1所示。试问如何安排生产，使每天所得的利润为最大？第1页/共178页表表1.11.1甲乙限额材料2324工时3226利润(元/件)43 设每天生产甲、乙两种产品分别为 x1 , x2 则该问题可描述为由如下数学模型：0,26232432 .34max 21212121xxxxxxtsxxZ第2页/共178

2、页1.2 线性规划问题的标准型线性规划问题的标准型 如下形式的线性规划模型被称作标准型:),2, 1( 0 ),2, 1( .max11njxmibxatsxcZjnjijijnjjj也可用矩阵形式描述: 0 bAX .maxXtsCXZA:资源消耗系数矩阵b: 资源限量向量C:价格向量X:决策变量向量第3页/共178页同时我们对标准型作如下假定:. 1 , 0 , 0 )2(. , ,)( ) 1 (即可乘以个约束方程两边同时则可对第若有没有多余方程彼此独立即标准型中的约束方程ibbnmAranki 一般的线性规划问题通过变换可化成标准型 , 变换方式可以归结为:. ) max( ) max

3、() min( :, ) 1 (即可这样我们只要讨论问题可以通过以下方式得到如果目标函数是极小化第4页/共178页. 0 , 0 , ) 3()0( , .)0( , . , )2(kkkkkkzyzyxxba其中则可令无非负性限制如果变量该松弛变量右端某松弛变量不等式左端则如果约束条件为该松弛变量右端某松弛变量不等式左端则如果约束条件为变量来得到我们可以通过引进松弛如果约束方程为不等式第5页/共178页1.3 线性规划问题解的概念线性规划问题解的概念 对于线性规划问题)3.1( ),2, 1( 0 )2.1( ),2, 1( .)1.1( max11njxmibxatsxcZjnjijijn

4、jjj. ) 1 . 1 ( : . ),( ) 3 . 1 ( ) 2 . 1 ( : 21的可行解称为最优解满足最优解称为可行解的解和满足约束条件可行解TxxX第6页/共178页题的一个基。是线性规划问则称阶非奇异子矩阵中的一个是矩阵如果基：设 , )0|(| , )( BBmmABmAranknm个非基向量。有中共，之外各列即为非基向量中除矩阵，中的列向量称为基向量基向量与非基向量：基 mnABAB基变量。为基变量；否则称为非称对应的变量基向量基变量与非基变量：与 jjxP第7页/共178页称为基解。的解，求出的满足为基解：令所有非基变量 )2 . 1 ( 0 )3 . 1 ( mnC

5、基解的数目解的数目基可行为可行基。显然，对应基可行解的基，称的基解称为基可行解。足基可行解与可行基：满优基。为最对应基本最优解的基称优解，的基可行解称为基本最满足基本最优解与最优基： ) 1 . 1 ( 可行解基解基可行解第8页/共178页1.4 线性规划问题的图解法线性规划问题的图解法 下面结合例1的求解来说明图解法步骤。0,26232432 .34max 21212121xxxxxxtsxxZ例1第一步：在直角坐标系中分别作出各种约束条件，求出可行域（图中阴影部分）。x2Q2(6,4)x13x1+2x2=262x1+3x2=24ZOQ1(26/3,0)Q3(6,4)第9页/共178页为则称

6、点连线上的一切任意两点中的一个点集，若维欧氏空间是设定义，先介绍两个概念。为介绍基本定理的需要 , ) 10( )1 ( )(, 1 . 1)2()1()2()1()2()1(KKXXXXXKXXEnKn第二步：作出一条目标函数等值线，并确定 Z 值增大的方向。第三步：沿 Z 值增大方向移动，当移至 Q2(6,4) 点时，Z 值为最大，Z*=36 .1.5 基本定理基本定理. 凸集第10页/共178页., 1 . 1域必为凸集则其可行空可行域若线性规划问题存在非定理的一个为则称的线性组合表示为点若不能用两个不同的是凸集，设定义 , ) 10( )1 ( , ; 2 . 1)2()1()2()1

7、(KXKXXXKXKXKXK. 极点., 2 . 1可行域的极点上达到数最优值一定可以在其则其目标函域有界若线性规划问题的可行定理. 3 . 1的极点对应于可行域解线性规划问题的基可行定理X 从理论上来讲,采用“枚举法”找出所有基可行解,并第11页/共178页1.6 求解求解线性规划问题的单纯形方法线性规划问题的单纯形方法 一一比较,一定会找到最优解。但当 m, n 较大时,这种方法是不经济和不可取的。 下面介绍求解线性规划问题的有效方法单纯形方法。单纯形法的实质是从一个基可行解向另一个基可行解（极点到极点）的迭代方法。 以下通过例1的求解过程说明单纯形方法的基本步骤。0,26232432 .

8、34max 21212121xxxxxxtsxxZ例1：第12页/共178页第一步：引进松驰变量 x3 , x4 将原问题化为标准型。0,26 2324 32 . 0034max 43214213214321xxxxxxxxxxtsxxxxZ标准型第二步：找出初始可行基，建立初始单纯形表。 见下表1.2。第13页/共178页 cj 4 3 0 0 CBXBb x1 x2 x3 x400 x3x42426 2 3 1 0 3 2 0 1Z0 -4 -3 0 0 表 1.2bBbIPPB10430 ),( 则本例中，初始可行基第三步：最优性检验。 可能有下面三种情况：的检验数检验各非基变量 , j

9、jxij第14页/共178页行换基迭代。四步，进不是最优基，须转入第则基分量，所对应的列向量有正若有某个负检验数，停止计算。函数无上界，即无界解标则该线性规划问题的目（部分量它所对应的列向量的全若有某，停止计算。可行解即为基本最优解为最优基，相应的基则基若所有的 B 0 ) 3( , 0), , 0 )2( , 0 ) 1 (21jmssssjaaaB第15页/共178页量。所在的列变为单位列向即把基变量进行初等行变换，为主元，在单纯形表中以为主元。为出基变量，其中确定元按最小比值原则求出主确定换出变量取确定换入变量 )3( ,0|min : )2(. 0 , 0|min : ) 1 (srs

10、rsrrsrisisiirjsxaaxabaabxnjjsx第四步：换基迭代。第16页/共178页的单纯形表。，得到新的可行基和新换为中的同时将 srBxxX有无界解，计算终止。出至获得最优解，或判断重复第三、第四步，直 所在行的交叉处所在列和换出基变量，并以为确定，为换入变量。所以，因为来说，对于表针对例 326326,2240|min 13, 4|min: 2 . 1 1 414121xxxaabxjsisisiii第17页/共178页元素为主元进行迭代。 cj 4 3 0 0 CBXBb x1 x2 x3 x400 x3x42426 2 3 1 0 3 2 0 11226/3Z0 -4

11、-3 0 0 04x3x120/326/3 0 5/3 1 -2/3 1 2/3 0 1/3413Z104/3 0 -1/3 0 4/3表1.3ijj第18页/共178页同理，确定 x2 换入，x3 换出，继续迭代得表 1.3 cj 4 3 0 0 CBXBb x1 x2 x3 x434x2x146 0 1 3/5 -2/5 1 0 -2/5 3/5Z36 0 0 1/5 6/5 表 1.3 表中最后一行的所有检验数都已是正数或零，从而得到基本最优解 X*=(6,4,0,0)T, Z*=36 。由于 x3 , x4 是引进的松弛变量，因此原问题的最优解为 x1=6, x2=4, 最优值 Z*=

12、36 。ji第19页/共178页例2 一奶制品加工厂用牛奶生产 A1 , A2 两种奶制品，1 桶牛奶可以在设备甲上用 12 小时加工成 3 公斤 A1,或者在设备乙上用 8 小时加工成 4 公斤 A2。根据市场需求，生产的 A1 , A2 全部能售出，且每公斤 A1 获利 24 元，每公斤 A2 获利 16 元。现在加工厂每天能得到 50 桶牛奶的供应，每天正式工人总的劳动时间为 480 小时，并且设备甲每天至多能加工 100 公斤 A1 , 设备乙的加工能力没有限制。试为该厂制定一个 我们无意过深涉及线性规划的具体计算方法，而着重介绍的是如何建立若干实际的线性规划模型，如何使用现成的数学软

13、件进行求解，以及如何对结果进行深入的分析。 下面以奶制品加工生产计划为例，进行详细的讨论。第20页/共178页生产计划，使每天获利最大，并进一步讨论以下 3 个附加问题： 若用 35 元可买到 1 桶牛奶，买吗？若买，每天最多 买多少? 若可以聘用临时工人以增加劳动时间，付给临时工人 的工资最多是每小时几元? 由于市场需求的变化，A1 的获利增加到 30元/公斤， 应否改变生产计划？第21页/共178页1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶 时间480小时 至多加工100公斤A1 每天：分析x1 桶牛奶生产 A1 x2 桶牛奶生产

14、A2 获利 243x1 获利 164 x2 决策变量决策变量 0, 1003 480812 50 .6472 211212121xxxxxxxtsxxzMax数学模型原料供应 劳动时间 加工能力 非负约束 第22页/共178页解法1：图解法。 x1x20ABCDl1l2l3l4l55021 xx48081221 xx10031x0,21xx约束条件50:211 xxl480812:212 xxl1003:13xl0:, 0:2514xlxl216472xxzMaxZ=0Z=2400Z=3360c从图中可以看出，在 B(20,30) 点得到最优解。解法2：软件实现。求解线性规划有不少现成的数学软

15、件，比如用 LINDO 软件就可以很方便地实现。在 LINDO6.1版本下打开一个新文件，像书写模型一样。直接输入：第23页/共178页max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end注：LINDO中已规定所有决策变量均为非负，故变量非负的条件不必输入。输入文件中第1行为目标函数，2),3),4)是为了标示各约束条件，便于从输出结果中查找相应信息；程序最后以end 结束。 将文件存储并命名后，选择菜单 “Solve” 并对提示 “ DO RANGE(SENSITIVITY)ANALYSIS? ”回答“是”，即可得到如下输出：第24页/共178页

16、OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 220桶牛奶生产A1, 30桶生产A2，利润3360元。 原料无剩余时间无剩余加工能力剩余40三种资源“资源” 剩余为零的约束为紧约束（有效约束） 第25

17、页/共178页结果解释结果解释 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2最优解下“资源”增加1单位时“效益”的增量 原料增加1单位, 利润增长48 时间增加1单位, 利润增长2 加工能力增长不

18、影响利润影子价格 35元可买到1桶牛奶，要买吗？35 0 ,并将各个约束条件加到目标函数上，得一新函数如下：1( ,)( ) ( ) (4.12)ljjP X Mf XMg X 可以看出，当 时，有 ；当 时，由于M 很大，将使 很大，从而使XR( ,)( )P X Mf XXR1 ( )ljjMg X( ,)P X M第121页/共178页很大，这就相当于对非可行点的“惩罚”。而且，X 点离可行域越远惩罚越严厉。可以想见，当 M 变得足够大时，相应于这样的 M 值，(4.12) 的无约束极小点 X(M) , 就会和原来的约束问题的极小点足够接近。而当 时，它就成为原约束问题的极小点。 惩罚函

19、数（4.12）也可改写成另外的形式：XR21( ,)( ) min(0, ( ) (4.13)ljjP X Mf XMg X 或者：)14. 4( )()()(),(12ljjjjXguXgMXfMXP第122页/共178页 是阶越函数：)(Xgujj0)( 1 0)( 0 )(XgXgXgujjjj当当 假定对某一罚因子，例如说 M1 , , 就加大罚因子的值。随着罚因子数值的增加，惩罚函数中的惩罚项所起的作用随之增大，minP(X,M) 的解 X(M) 离可行域 R 的“距离”就会越来越近，当RMX)(1kMMM210趋于无穷大时，点列 X(Mk) 就从可行域 R 的外部趋于原非线性规划问

20、题的极小点。第123页/共178页和不等式约束问题类似，对于等式约束问题，即：miXhXfi, 2 , 1 0)()(min采用以下形式的罚函数：miiXhMXfMXP12)()(),( 对于既包含等式约束又包含不等式约束的一般非线性规划问题(4.1),其罚函数为)15. 4( )(, 0min()()(),(1212ljjmiiXgMXhMXfMXP或)16. 4( (X)()()()(),(1212jjljjmiiguXgMXhMXfMXP第124页/共178页罚函数法的迭代步骤如下：（1）取第一个罚因子 M1 0 (例如M1 =1），允许误差 ，并令 k :=1 。（2）求下述无约束极值

21、问题的最优解：其中P(X,Mk) 可取式（4.15)或(4.16)的形式。设其极小点为 X(k) 。（3）若存在某一个 ，有或存在某一个 ,有则取 Mk+1Mk ( 例如 Mk+1=cMk , c=10 )，并令 k:=k+1 。然后，0),(minkMXP) 1 ( ljj) 1 ( mii)()(kjXg | )(|)(kiXh第125页/共178页转回第(2)步。否则，停止迭代，得所要的点 X(k) 。障碍函数法( (内点法） 罚函数法的一个重要特点，就是函数 P(X,M) 可在整个 En 空间内进行优化，可以任意选择初始点，这给计算带来了很大方便。但由于迭代过程常常是在可行域外进行，因

22、而不能以中间结果直接作为近似解使用。 如果要求每次的近似解都是可行解，以便观察目标函数值的改善情况；或者，如果目标函数在可行域外的性质比较复杂，甚至没有定义，这时就无法使用上面所述的罚函数法了。 障碍函数法与罚函数法不同，它要求迭代过程始终在可行 第126页/共178页域内部进行。 考虑非线性规划（4.3），当 X 点从可行域 R 内部趋于其边界时，至少有某一个约束函数 趋于零。从而，下述倒数函数和对数函数都将无限增大。如果把式 (4.17) 或 (4.18) 加到非线性规划 (4.3)的目标函数上，就能构成新的目标函数障碍函数。)1 ( )(ljXgj)17. 4( )(11ljjXg)18

23、. 4( )(lg(1ljjXg第127页/共178页或)19. 4( )(1)() 1 XgrXf(X,rPljjkk)20. 4( )(lg()() 1 XgrXf(X,rPljjkk 如果从某一点 出发，求下列无约束极小化问题)21. 4( ),(min0kRXrXP0)0(RX 则随着障碍因子 的逐渐减小，即障碍项所起的作用也越来越小，因而，求出的问题（4.21）的kr021krrr第128页/共178页解 就会逐步逼近原约束问题 (4.3) 的极小解。)(krX障碍函数法的迭代步骤如下：（1）取第一个障碍因子 ，允许误差 ，并令 k:=1 。（2）构造障碍函数，可采取 (4.19)

24、或 (4.20) 。（3）对障碍函数进行无约束极小化，设所得解为 。（4）检查是否满足收敛准则：) 0 ( 011rr如00)(RXkljkjkXgr1)()(1或ljkjkXgr1)(|)(lg(|如果满足此准则，则以 X(k) 为原约束问题的近似极小解，停第129页/共178页止迭代；否则，取 rk+1 rk ，令 k:=k+1 , 转回第（3）步继续进行迭代。第130页/共178页五五. . 动态规动态规划划 动态规划是解决多阶段决策过程最优化问题的一种方法。该方法是由美国数学家贝尔曼等人在 20 世纪 50 年代初提出的。他们针对多阶段决策问题的特点，提出了解决这类问题的最优化原理，并

25、成功地解决了生产管理、工程技术等方面的许多实际问题。 多阶段决策问题的特点是整个决策过程可以分为好几个彼此有联系的阶段，而每一个阶段都有多于一个的小方案需要选择确定，决策者需要在可供选择的小方案中选出其中的一个最优方案，使其效果在预定的目标下达到最好。第131页/共178页A5BDFCE11121067一个简单的多级决策：有某旅行者从 A 地出发到 F 地，可以选择两条路线，一是途经 B 地，D 地到 F ;另一是途经 C 地，E 地到 F (如图),每段路程所需的费用在图中标出。这个问题是以总旅费达到最小作为目标，显然应选择：A C E F。 整个规划的目标是使得最终结果达到最优，这就意味着

26、，某一段作出的决策，就这个阶段来说，并不一定是一个最优的选择，甚至要作出某些牺牲（如上例第一段）。但是第132页/共178页由于各阶段的相互影响，到最后却会得到一个最优的结果。相反，在这一阶段选择了一个最优的决策，并不等于最后得到最优结果，这就是动态规划的特点。 使用动态规划方法解决多阶段决策问题，首先要将实际问题写成动态规划模型，此时要用到以下概念：（1）阶段；（2）状态；（3）决策和策略；（4）状态转移；（5）指标函数。 下面我们结合以下例题说明这些概念。例 5.1 最短路线问题。 如图所示，给定一个线路网络图，要从 A 地向 F 地铺设一条输油管道，各点间连线上的数字表示距离，问应选择第

27、133页/共178页什么线路，可使总距离最短？ A468335425B1B2E2FD1E1C1C2C3C4D3D2737835448431265（1）阶段。 将所给问题的过程，按时间或空间特征分解成若干互相联系的阶段，以便按次序去求每阶段的解。 （2）状态。 各阶段开始时的客观条件叫状态。描述各阶段状态的变量称为状态变量，sk 表示第 k 阶段的状态变量 ，sk 的取值集合称为状态集合，用 Sk 表示。第134页/共178页在例5.1中，各阶段的状态集合分别是： 当某段的初始状态已选定某个点时，从这个点以后的铺管路线只与该点有关，不受以前铺管路线的影响，这叫状态变量的“无后效性”，如果所选的状

28、态变量不具备“无后效性”就不能用来构造动态规划模型。, , , 2153214432132121EESDDDSCCCCSBBSAS（3）决策和策略。 当各段的状态取定以后，就可以作出不同的决定，从而确定下一阶段的状态，这种决定称为决策。表示决策的变量，称为决策变量，常用 uk(sk) 表示第 k 阶段当状态为 sk 时的决第135页/共178页策变量，Dk(sk) 表示第 k 阶段从状态 sk 出发的允许决策集合。 在例5.1中，有 D2(B1)=C1, C2, C3 如我们决定选择 C3，则可表为： u2(B1)=C3 各段决策确定后，整个问题的决策序列就构成一个策略，用 p1,n u1(s

29、1),u2(s2),un(sn)表示，P1,n 表示允许决策的集合，使整个问题达到最优效果的策略就是最优策略。(4)状态转移方程。 动态规划中，如果给定了第 k 阶段的状态 sk 和本阶段决策 uk(sk) 则第 k+1 段的状态 sk+1 也就完全确定，它们的关第136页/共178页系可用下列状态转移方程表示： sk+1=Tk(sk,uk)例5.1中，状态转移方程为： sk+1=uk(sk)（5）指标函数。 用于衡量所选定策略优劣的数量指标称为指标函数。它分 为阶段指标函数和过程指标函数两种。阶段指标函数是指第 k段，从状态 sk 出发，采取决策 uk 时的效益，用 d (sk,uk) 表示

30、。一个 n 段的决策过程，从 1 到 n 叫做问题的原过程，对任意给定的 ,从第 k 段到第 n 段的过程称为原过程的一个后部子过程。V1,n(s1,p1,n) 表示初始状态为 (1)kkn第137页/共178页s1 采用策略 p1,n 时，后部子过程的指标函数值，而Vk,n(sk,pk,n)表示在第 k 段，状态为 sk 采用策略 pk,n时 ，后部子过程的指标函数值。最优指标函数记为 fk(sk) ,它表示从第 k 段状态 sk 采用最优策略 到过程终止时的最佳效益值。即：当 k1 时， 就是从初始状态 到全过程结束的整体最优函数。 下面用动态规划方法求解例5.1 。本方法是从过程的最后一

31、段开始，用逆序递推方法求解，逐步求出各段各点到终点 F 的最短路线。*,k np,*,()(,)(,)k nk nkkk nkk nk nkk npPfsVspopt Vsp11( )f s1s第138页/共178页第一步：从 k=5 开始，状态变量 s5 可取两种状态 E1, E2, 它们到 F 点的路长分别为 4，3 。即：第二步：k=4，状态变量可取三个值D1, D2, D3, 从 D1 到 F 有两条路线，需要加以比较，取其中最短的，即：这说明 D1 到 F 最短距离为 7 , 其路径为 D1 E1 F 。相应决策 。5152()4 ()3fEfE735 43 min)(),( )()

32、,( min)(2521151114EfEDdEfEDdDf11*4)(EDu532 46 min)(),( )(),( min)(2522151224EfEDdEfEDdDf第139页/共178页即 D2 到 F 最短距离为 5 , 其路径为 D2 E2 F 。相应决策为 。即 D3 到 F 最短距离为 5 , 其路径为 D3 E1 F 。相应决策为 。类似地，可算得：*4()22uDE533 41 min)(),( )(),( min)(2523151334EfEDdEfEDdDf13*4)(EDu34*34323*33322*32311*313)( 9)( )( 8)( )( 10)(

33、)( 12)( 3DCuCfDCuCfDCuCfDCuCfk时，有第140页/共178页FEDCBAFEuEDuDCuCBuBAuuBAuFABfBAdBfBAdAfCBuBfCBuBfkk22212*522*422*321*21*11*1222121132*22221*212 )( ,)( ,)( ,)( ,)(: , . )( 17 17155 134 min)(),( )(),( min)( A 1k)( 15)( )( 13)( 2所以最优路线为：即最优决策序列在按计算顺序反推可得。本段决策为的最短距离为到即从，则只有一个状态点时，时，有第141页/共178页。转移关系有递推的状态证各

34、阶段的状态变量具正确选择状态变量，保的关键又在于建立基本递推关系方程的若干子问题，而正确系式联系起来题分解成为可用递推关题的多阶段特征，将问，在于识别问用动态规划方法的关键划基本方程。成功地应的动态规是分析问题并建立问题建立动态规划模型，就规划的基本方程。这种递推关系称为动态段的如下关系：段和第第利用了，在求解的各阶段，都的计算过程中可以看出从例 ),( 0)(1 , 2 , 3 , 4 , 5 )(),(min)( 1 1 . 516611kkkkkkkkkukkusTssfksfusdsfkkk第142页/共178页全渡河那？人怎样才能安掌握在商人们手中。商是如何乘船渡河的大权杀人越货。但

35、从的人数比商人多，就在河的任一岸，一旦随。随从们密约，二人，由他们自己划行河，一只小船只能容纳从乘船渡）三名商人各带一个随（商人们怎样安全过河例成最优策略”。其以后的所有决策应构的状态而言，对于先前决策所形成始状态及初始决策如何质：即无论初最优策略具有这样的性表述为：“一个过程的理，它可曼等人提出的最优化原动态规划方法基于贝尔 2 . 5 第143页/共178页 3名商人 3名随从问题分析问题分析: 安全渡河问题可以视为一个多步决策过程。每一步，即船由此岸到彼岸或从彼岸驶回此岸，都要对船上的人员（商人、随从各几人）作出决策，在保证安全的前提下（两岸的随从数都河小船(至多2人)不比商人数多），在

36、有限步内全部人员过河。用状态变量表示某一岸的人员状况，决策变量表示船上的人员状况，于是可以找出状态随决策变化的规律。第144页/共178页模型构成模型构成xk第k次渡河前此岸的商人数yk第k次渡河前此岸的随从数xk, yk=0,1,2,3; k=1,2, sk=(xk , yk)过程的状态（向量）S=(x , y) x=0, y=0,1,2,3; x=3, y=0,1,2,3; x=y=1,2S 允许状态集合uk第k次渡船上的商人数vk第k次渡船上的随从数dk=(uk , vk)决策D=(u , v) u+v=1, 2 允许决策集合uk, vk=0,1,2; k=1,2, sk+1=sk dk

37、 +(-1)k状态转移律求dk D(k=1,2, n), 使sk S, 并按转移律由 s1=(3,3)到达 sn+1=(0,0).多步决策多步决策问题问题第145页/共178页模型求解模型求解xy3322110 穷举法 编程上机 图解法图解法状态s=(x,y) 16个格点 10个 点允许决策 移动1或2格; k奇,左下移; k偶,右上移.s1sn+1d1, ，d11给出安全渡河方案 同学们还可以进一步考虑 4 名商人各带一随从的情况（小船同前）。d1d11允许状态S=(x , y) x=0, y=0,1,2,3; x=3, y=0,1,2,3; x=y=1,2第146页/共178页), 1(m

38、iAi), 1(njXjj1 , 101njjj：评价对象（可替代且非劣的方案）：评价指标（准则、项目）：评价指标权重，1、关联矩阵法综合评价方法第147页/共178页 n21Vi X1 X2 Xn mjjjmjjjnjjjVVVVVV22111XjjVijAi?ijVij = ?逐对比较法、古林法 A1A2AmV11 V12 V1nV21 V22 V2nVm1 Vm2 Vmn . . .第148页/共178页评价指标Xj替代方案Ai期望利润（万元）产品成品率（%）市场占有率（%）投资费用（万元）产品外观自行设计（A1）6509530110美 观国外引进（A2）7309735180比较美观改

39、建（A3）520922550美 观 方案预期结果例表第149页/共178页评价指标得分序号累计得分权重12345678910期望利润（X1）1111 40.4产品成品率（X2）0 111 30.3市场占有率（X3） 0 0 01 10.1投资费用（X4） 0 0 1 120.2产品外观（X5） 0 0 0000.0 逐对比较法例表 第150页/共178页评价尺度(得分)评价指标54321期望利润（万元）800以上701-800601-700501-600500以下产 品 成 品 率（%）97以上96-9791-9586-9085以下市 场 占 有 率（%）40以上35-3930-3425-29

40、25以下投资费用（万元）20以下21-8081-120121-160160以上产品外观非常美观美观比较美观一般不美观 评价尺度例表 第151页/共178页VijAij 期望利润产品成品率市场占有率投资费用产品外观Vi0.40.30.10.20.0自行设计(A1)333343.0国外引进(A2)444133.4改建(A3)232442.7Xj 关联矩阵表（逐对比较法）第152页/共178页j341/2序号评价指标RjKj1期望利润180.5802产品成品率60.1943市场占有率20.0654投资费用40.1295产品外观10.032合计311.0003Rj Kj Wj 基准化 归一化 古林法求

41、j 例表第153页/共178页序号（j）评价指标替代方案RijKijVij1期望利润A10.8901.2500.342A21.4041.4040.384A31.0000.2742产品成品率A10.9791.0320.334A21.0541.0540.342A31.0000.324 古林法求Vij例表第154页/共178页3市场占有率A10.8571.2000.333A21.4001.4000.389A31.0000.2784投资费用A11.6360.4550.263A20.2870.2870.160A31.0000.5775产品外观A11.3331.0000.364A20.7500.7500.

42、272A31.0000.364 古林法求Vij例表（续）第155页/共178页VijAij期望利润产品成品率市场占有率投资费用产品外观Vi0.5800.1940.0650.1290.032A10.3420.3840.2740.3340.3420.3240.3330.3890.2780.2630.1600.5770.3640.2720.3640.3300.3340.326A2A3Xj 关联矩阵例表（古林法）第156页/共178页Analytic Hierarchy ProcessAHP（美国运筹学家、匹兹堡大学教授）投资效果好（T）风险程度（I1）资金利润率（I2）转产难易程度（I3）产品1（P

43、1）产品2（P2）产品3（P3）（目的层）（准则层）（方案层）三、层次分析（AHP）法第157页/共178页判断矩阵标度定义 标度含义1两个要素相比，具有同样重要性3两个要素相比，前者比后者稍微重要5两个要素相比，前者比后者明显重要7两个要素相比，前者比后者强烈重要9两个要素相比，前者比后者极端重要2，4，6，8上述相邻判断的中间值倒数两个要素相比，后者比前者的重要性标度 AHP方法的基本工具判断矩阵第158页/共178页TI1I2I3WiWioI111/320.8740.230I23152.4660.648I31/21/510.4640.122(3.804) 注 Wi的求取采用方根法（求根法

44、或称几何平均值法） I1P1P2P3WiWioP111/31/50.4060.105P2311/31.0000.258P35312.4660.637 判断矩阵及其分析处理举例第159页/共178页I2P1P2P3WiWioP11272.4100.592P21/2151.3570.333P31/71/510.3060.075I3P1P2P3WiWioP111/31/70.3620.081P2311/50.8430.188P37513.2710.731 判断矩阵及其分析处理举例（续）第160页/共178页 求综合重要度（加权和） T I1 I2 I3 综合综合 重要度重要度 权重权重 0.230

45、0.648 0.122（加权和）（加权和） P1 0.105 0.592 0.149 0.426 P2 0.258 0.333 0.066 0.283 P3 0.637 0.075 0.785 0.291第161页/共178页（1）分析评价系统中各基本要素之间的关系，建立系统的递阶层次结构（分解法）；（2）对同一层次的各要素关于上一层次中某一准则的重要性进行两两比较，构造判断矩阵（专家调查法）；（3）由判断矩阵计算被比较要素对于该准则的相对权重（方根法）；（4）计算各层要素相对于系统目的（总目标）的合成（总）权重，并据此对方案等排序（加权和法）。AHP方法步骤第162页/共178页 课程： 教

46、师： 班级： 评价项目（权重）好（100）较好(85)一般（70）较差（55）1.教学计划及教学内容安排（0.10）9 0.3614 0.562 0.080 0.002.教材及参考资料状况(0.10)3 0.1214 0.567 0.281 0.043.教师教学态度及责任心(0.15)5 0.2015 0.605 0.200 0.004.教师讲解能力（0.10）1 0.0410 0.4011 0.443 0.12评价结果(票数/隶属度) ) 评价等级四、模糊综合评判法（1）第163页/共178页5.课堂教学形式的多样化程度（0.10）2 0.0811 0.4412 0.480 0.006.理论

47、联系实际程度及教学案例使用情况（0.10）5 0.2014 0.566 0.240 0.007.辅助教学环节及考核情况(0.10)4 0.166 0.2413 0.522 0.088.教学改革与创新情况(0.10)3 0.128 0.3212 0.482 0.089.从本课程学习中所获得的收益程度（0.15）5 0.2012 0.486 0.242 0.08综合评价结果综合隶属度 0.168 0.470 0.318 0.044综合得分81.43四、模糊综合评判法（2）第164页/共178页49)(ijrR91)(iwW41)(jdDTDS 隶属度 rij 指多个评价主体对某个评价对象在第i个项

48、目下作出第j等级评定的可能性程度。 若记：隶属度矩阵为 评价项目权重向量为 评价等级分值向量为 则有：综合隶属度向量 S=WR综合得分 四、模糊综合评判法（3）第165页/共178页 动态规划模型常被用来求解经济管理中的货物存储、动态规划模型常被用来求解经济管理中的货物存储、设备更新、资源分配、任务均衡、水库调度、系统可靠性设备更新、资源分配、任务均衡、水库调度、系统可靠性等问题，在离散系统最优控制中也有广泛应用。等问题，在离散系统最优控制中也有广泛应用。动态规划模型的主要缺点是：动态规划模型的主要缺点是：1.1. 没有统一的标准模型，也没有万能的构造模型的没有统一的标准模型，也没有万能的构造

49、模型的 方法，方法，需要对每类问题具体分析。在定义状态变量、建立状态转需要对每类问题具体分析。在定义状态变量、建立状态转移率等方面，需要灵活技巧，这就带来了应用上的局限性。移率等方面，需要灵活技巧，这就带来了应用上的局限性。2.2. 用数值方法求解时存在维数灾。由于状态个数随维数呈指用数值方法求解时存在维数灾。由于状态个数随维数呈指数增长，对高维问题求解十分困难。数增长，对高维问题求解十分困难。第166页/共178页六六. . 最优控制理论最优控制理论 最优控制理论是从20世纪50年代末60年代初发展起来的现代控制理论的一个重要分支。它最初研究的对象是由导弹、航天、航空、航海中的制导、导航和控

50、制中所总结出来的一类按某个性能指标取最优（极小或极大）的控制问题。其核心问题是如何为被控制系统选择一个控制策略，使得被控制系统本身获得优良的技术品质和满意的经济效益。今天，最优控制理论的研究，无论在深度和广度上都有了较大的发展，诸如分布参数系统的最优控制、随机系统的最优控制、大系统的最优控制、微分对策等许多方面都是当前极其活跃的科学研究领域。6.1 6.1 控制工程中的几个实际问题 为了更好地说明最优控制问题，我们给出几个工程控制中的实例。第167页/共178页例6.1 （升降机的最快升降问题）一个内部带控制器的物体 M ，其质量为 1 。常重力加速度 g 垂直向下作用到M 的质心上，控制器可提供一个作用于 M 使其垂直上升或下降的加速度 。设 和 分别表示 t0 时刻质心距地面的垂直距离和垂直运动速度。我们的问题是如何选择 ，使 M 从初始时刻 t0 的初态 最快地到达终端时刻 tf 的末态 (到