1、 数学规划的理论与方法数学规划的理论与方法1. 线性规划理论与方法线性规划理论与方法2. 目标规划的理论与方法目标规划的理论与方法3. 整数规划的理论与方法整数规划的理论与方法4. 非线性规划的理论与方法非线性规划的理论与方法5. 动态规划动态规划6. 最优控制理论最优控制理论y一一. .线性规划的理论与方法线性规划的理论与方法 线性规划是指目标函数是由线性函数给出，约束条件由线性等式或者不等式给出的优化问题。 最早提出线性规划问题并进行专门研究的学者康托洛维奇。 康托洛维奇在20世纪30年代就提出了求解线性规划问题的“解乘数法”。 自从1947年美国学者丹青格提出求解线性规划问题的一般方法单
2、纯形方法 后，才使线性规划的理论和方法日臻成熟。（1）由决策变量构成，反映决策的目标是线性函数。（2）一组由决策变量的线性等式或不等式构成约束 条件。（3）对决策变量取值范围加以限制的非负约束。1.1 线性规划模型的特征线性规划模型的特征 例1：某工厂生产甲、乙两种产品，每件产品的利润、所消耗的材料、工时及每天的材料限额和工时限额，如表1.1所示。试问如何安排生产，使每天所得的利润为最大？表表1.11.1材料工时利润(元/件)甲234乙323限额2426 设每天生产甲、乙两种产品分别为 x1 , x2 则该问题可描述为由如下数学模型：0,26232432 .34max 21212121xxxx
3、xxtsxxZ1.2 线性规划问题的标准型线性规划问题的标准型 如下形式的线性规划模型被称作标准型:),2, 1( 0 ),2, 1( .max11njxmibxatsxcZjnjijijnjjj也可用矩阵形式描述: 0 bAX .maxXtsCXZA:资源消耗系数矩阵b: 资源限量向量C:价格向量X:决策变量向量同时我们对标准型作如下假定:. 1 , 0 , 0 )2(. , ,)( ) 1 (即可乘以个约束方程两边同时则可对第若有没有多余方程彼此独立即标准型中的约束方程ibbnmAranki 一般的线性规划问题通过变换可化成标准型 , 变换方式可以归结为:. ) max( ) max()
4、min( :, ) 1 (即可这样我们只要讨论问题可以通过以下方式得到如果目标函数是极小化. 0 , 0 , ) 3()0( , .)0( , . , )2(kkkkkkzyzyxxba其中则可令无非负性限制如果变量该松弛变量右端某松弛变量不等式左端则如果约束条件为该松弛变量右端某松弛变量不等式左端则如果约束条件为变量来得到我们可以通过引进松弛如果约束方程为不等式1.3 线性规划问题解的概念线性规划问题解的概念 对于线性规划问题)3.1( ),2, 1( 0 )2.1( ),2, 1( .)1.1( max11njxmibxatsxcZjnjijijnjjj. ) 1 . 1 ( : . ),
5、( ) 3 . 1 ( ) 2 . 1 ( : 21的可行解称为最优解满足最优解称为可行解的解和满足约束条件可行解TxxX题的一个基。是线性规划问则称阶非奇异子矩阵中的一个是矩阵如果基：设 , )0|(| , )( BBmmABmAranknm个非基向量。有中共，之外各列即为非基向量中除矩阵，中的列向量称为基向量基向量与非基向量：基 mnABAB基变量。为基变量；否则称为非称对应的变量基向量基变量与非基变量：与 jjxP称为基解。的解，求出的满足为基解：令所有非基变量 )2 . 1 ( 0 )3 . 1 ( mnC 基解的数目解的数目基可行为可行基。显然，对应基可行解的基，称的基解称为基可行解
6、。足基可行解与可行基：满优基。为最对应基本最优解的基称优解，的基可行解称为基本最满足基本最优解与最优基： ) 1 . 1 ( 可行解基解基可行解1.4 线性规划问题的图解法线性规划问题的图解法 下面结合例1的求解来说明图解法步骤。0,26232432 .34max 21212121xxxxxxtsxxZ例1第一步：在直角坐标系中分别作出各种约束条件，求出可行域（图中阴影部分）。x2Q2(6,4)x13x1+2x2=262x1+3x2=24ZOQ1(26/3,0)Q3(6,4)为则称点连线上的一切任意两点中的一个点集，若维欧氏空间是设定义，先介绍两个概念。为介绍基本定理的需要 , ) 10( )
7、1 ( )(, 1 . 1)2()1()2()1()2()1(KKXXXXXKXXEnKn第二步：作出一条目标函数等值线，并确定 Z 值增大的方向。第三步：沿 Z 值增大方向移动，当移至 Q2(6,4) 点时，Z 值为最大，Z*=36 .1.5 基本定理基本定理. 凸集., 1 . 1域必为凸集则其可行空可行域若线性规划问题存在非定理的一个为则称的线性组合表示为点若不能用两个不同的是凸集，设定义 , ) 10( )1 ( , ; 2 . 1)2()1()2()1(KXKXXXKXKXKXK. 极点., 2 . 1可行域的极点上达到数最优值一定可以在其则其目标函域有界若线性规划问题的可行定理.
8、3 . 1的极点对应于可行域解线性规划问题的基可行定理X 从理论上来讲,采用“枚举法”找出所有基可行解,并1.6 求解求解线性规划问题的单纯形方法线性规划问题的单纯形方法 一一比较,一定会找到最优解。但当 m, n 较大时,这种方法是不经济和不可取的。 下面介绍求解线性规划问题的有效方法单纯形方法。单纯形法的实质是从一个基可行解向另一个基可行解（极点到极点）的迭代方法。 以下通过例1的求解过程说明单纯形方法的基本步骤。0,26232432 .34max 21212121xxxxxxtsxxZ例1：第一步：第一步：引进松驰变量 x3 , x4 将原问题化为标准型。0,26 2324 32 . 0
9、034max 43214213214321xxxxxxxxxxtsxxxxZ标准标准型型第二步：第二步：找出初始可行基，建立初始单纯形表。 见下表1.2。 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 ),( 则本例中，初始可行基第三步：第三步：最优性检验。 可能有下面三种情况：的检验数检验各非基变量 , jjxij行换基迭代。四步，进不是最优基，须转入第则基分量，所对应的列向量有正若有某个负检验数，停止计算。函数无上界，即无界解标则该线性规划问题的目（部分量它所对应的
10、列向量的全若有某，停止计算。可行解即为基本最优解为最优基，相应的基则基若所有的 B 0 ) 3( , 0), , 0 )2( , 0 ) 1 (21jmssssjaaaB量。所在的列变为单位列向即把基变量进行初等行变换，为主元，在单纯形表中以为主元。为出基变量，其中确定元按最小比值原则求出主确定换出变量取确定换入变量 )3( ,0|min : )2(. 0 , 0|min : ) 1 (srsrsrrsrisisiirjsxaaxabaabxnjjsx第四步：第四步：换基迭代。的单纯形表。，得到新的可行基和新换为中的同时将 srBxxX有无界解，计算终止。出至获得最优解，或判断重复第三、第四步
11、，直 所在行的交叉处所在列和换出基变量，并以为确定，为换入变量。所以，因为来说，对于表针对例 326326,2240|min 13, 4|min: 2 . 1 1 414121xxxaabxjsisisiii元素为主元进行迭代。 cj 4 3 0 0 CBXBb x1 x2 x3 x400 x3x42426 2 3 1 0 3 2 0 11226/3Z0 -4 -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同理，确定 x2 换入，x3 换出，继续迭代得表 1.3 cj 4 3 0 0 CBX
12、Bb 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*=36 。ji例2 一奶制品加工厂用牛奶生产 A1 , A2 两种奶制品，1 桶牛奶可以在设备甲上用 12 小时加工成 3 公斤 A1,或者在设备乙上用 8 小时加工成 4 公斤 A2。根据市场需求，生产的 A1 , A2 全部能售出，且每公斤 A1 获利
13、24 元，每公斤 A2 获利 16 元。现在加工厂每天能得到 50 桶牛奶的供应，每天正式工人总的劳动时间为 480 小时，并且设备甲每天至多能加工 100 公斤 A1 , 设备乙的加工能力没有限制。试为该厂制定一个 我们无意过深涉及线性规划的具体计算方法，而着重介绍的是如何建立若干实际的线性规划模型，如何使用现成的数学软件进行求解，以及如何对结果进行深入的分析。 下面以奶制品加工生产计划为例，进行详细的讨论。生产计划，使每天获利最大，并进一步讨论以下 3 个附加问题： 若用 35 元可买到 1 桶牛奶，买吗？若买，每天最多 买多少? 若可以聘用临时工人以增加劳动时间，付给临时工人 的工资最多
14、是每小时几元? 由于市场需求的变化，A1 的获利增加到 30元/公斤， 应否改变生产计划？1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶 时间480小时 至多加工100公斤A1 每天：分析x1 桶牛奶生产 A1 x2 桶牛奶生产 A2 获利 243x1 获利 164 x2 决策变量决策变量 0, 1003 480812 50 .6472 211212121xxxxxxxtsxxzMax数学模型原料供应原料供应 劳动时间劳动时间 加工能力加工能力 非负约束非负约束 解法1：图解法。 x1x20ABCDl1l2l3l4l55021 xx4808
15、1221 xx10031x0,21xx约约束束条条件件50:211 xxl480812:212 xxl1003:13xl0:, 0:2514xlxl216472xxzMaxZ=0Z=2400Z=3360c从图中可以看出，在 B(20,30) 点得到最优解。解法2：软件实现。求解线性规划有不少现成的数学软件，比如用 LINDO 软件就可以很方便地实现。在 LINDO6.1版本下打开一个新文件，像书写模型一样。直接输入：max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end注：LINDO中已规定所有决策变量均为非负，故变量非负的条件不必输入。输入文件中第1
16、行为目标函数，2),3),4)是为了标示各约束条件，便于从输出结果中查找相应信息；程序最后以end 结束。 将文件存储并命名后，选择菜单 “Solve” 并对提示 “ DO RANGE(SENSITIVITY)ANALYSIS? ”回答“是”，即可得到如下输出： 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
17、.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 220桶牛奶生产桶牛奶生产A1, 30桶生产桶生产A2，利润，利润3360元。元。 原料无剩余原料无剩余时间无剩余时间无剩余加工能力剩余加工能力剩余40三三种种资资源源“资源资源” 剩余剩余为零的约束为为零的约束为紧约束（有效紧约束（有效约束）约束） 结果解释结果解释 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 R
18、OW 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 加工能力增长不影响利润加工能力增长不影响利润影子价格影子价格 35元可买到元可买到1桶牛奶，要买吗？桶牛奶，要买吗？35 0 ,并将各个约束条件加到目标函数上，得一新函数如下：1( ,)( )
19、( ) (4.12)ljjP X Mf XMg X 可以看出，当 时，有 ；当 时，由于M 很大，将使 很大，从而使XR( ,)( )P X Mf XXR1 ( )ljjMg X( ,)P X M很大，这就相当于对非可行点的“惩罚”。而且，X 点离可行域越远惩罚越严厉。可以想见，当 M 变得足够大时，相应于这样的 M 值，(4.12) 的无约束极小点 X(M) , 就会和原来的约束问题的极小点足够接近。而当 时，它就成为原约束问题的极小点。 惩罚函数（4.12）也可改写成另外的形式：XR21( ,)( ) min(0, ( ) (4.13)ljjP X Mf XMg X 或者：)14. 4(
20、)()()(),(12ljjjjXguXgMXfMXP 是阶越函数：)(Xgujj0)( 1 0)( 0 )(XgXgXgujjjj当当 假定对某一罚因子，例如说 M1 , , 就加大罚因子的值。随着罚因子数值的增加，惩罚函数中的惩罚项所起的作用随之增大，minP(X,M) 的解 X(M) 离可行域 R 的“距离”就会越来越近，当RMX)(1kMMM210趋于无穷大时，点列 X(Mk) 就从可行域 R 的外部趋于原非线性规划问题的极小点。和不等式约束问题类似，对于等式约束问题，即：miXhXfi, 2 , 1 0)()(min采用以下形式的罚函数：miiXhMXfMXP12)()(),( 对于
21、既包含等式约束又包含不等式约束的一般非线性规划问题(4.1),其罚函数为)15. 4( )(, 0min()()(),(1212ljjmiiXgMXhMXfMXP或)16. 4( (X)()()()(),(1212jjljjmiiguXgMXhMXfMXP罚函数法的迭代步骤如下：（1）取第一个罚因子 M1 0 (例如M1 =1），允许误差 ，并令 k :=1 。（2）求下述无约束极值问题的最优解：其中P(X,Mk) 可取式（4.15)或(4.16)的形式。设其极小点为 X(k) 。（3）若存在某一个 ，有或存在某一个 ,有则取 Mk+1Mk ( 例如 Mk+1=cMk , c=10 )，并令
22、k:=k+1 。然后，0),(minkMXP) 1 ( ljj) 1 ( mii)()(kjXg | )(|)(kiXh转回第(2)步。否则，停止迭代，得所要的点 X(k) 。4.6.2 4.6.2 障碍函数法障碍函数法( (内点法）内点法） 罚函数法的一个重要特点，就是函数 P(X,M) 可在整个 En 空间内进行优化，可以任意选择初始点，这给计算带来了很大方便。但由于迭代过程常常是在可行域外进行，因而不能以中间结果直接作为近似解使用。 如果要求每次的近似解都是可行解，以便观察目标函数值的改善情况；或者，如果目标函数在可行域外的性质比较复杂，甚至没有定义，这时就无法使用上面所述的罚函数法了。
23、 障碍函数法与罚函数法不同，它要求迭代过程始终在可行 域内部进行。 考虑非线性规划（4.3），当 X 点从可行域 R 内部趋于其边界时，至少有某一个约束函数 趋于零。从而，下述倒数函数和对数函数都将无限增大。如果把式 (4.17) 或 (4.18) 加到非线性规划 (4.3)的目标函数上，就能构成新的目标函数障碍函数。)1 ( )(ljXgj)17. 4( )(11ljjXg)18. 4( )(lg(1ljjXg或)19. 4( )(1)() 1 XgrXf(X,rPljjkk)20. 4( )(lg()() 1 XgrXf(X,rPljjkk 如果从某一点 出发，求下列无约束极小化问题)21
24、. 4( ),(min0kRXrXP0)0(RX 则随着障碍因子 的逐渐减小，即障碍项所起的作用也越来越小，因而，求出的问题（4.21）的kr021krrr解 就会逐步逼近原约束问题 (4.3) 的极小解。)(krX障碍函数法的迭代步骤如下：（1）取第一个障碍因子 ，允许误差 ，并令 k:=1 。（2）构造障碍函数，可采取 (4.19) 或 (4.20) 。（3）对障碍函数进行无约束极小化，设所得解为 。（4）检查是否满足收敛准则：) 0 ( 011rr如00)(RXkljkjkXgr1)()(1或ljkjkXgr1)(|)(lg(|如果满足此准则，则以 X(k) 为原约束问题的近似极小解，停
25、止迭代；否则，取 rk+1 rk ，令 k:=k+1 , 转回第（3）步继续进行迭代。五五. . 动态规动态规划划 动态规划是解决多阶段决策过程最优化问题的一种方法。该方法是由美国数学家贝尔曼等人在 20 世纪 50 年代初提出的。他们针对多阶段决策问题的特点，提出了解决这类问题的最优化原理，并成功地解决了生产管理、工程技术等方面的许多实际问题。 多阶段决策问题的特点是整个决策过程可以分为好几个彼此有联系的阶段，而每一个阶段都有多于一个的小方案需要选择确定，决策者需要在可供选择的小方案中选出其中的一个最优方案，使其效果在预定的目标下达到最好。A5BDFCE11121067一个简单的多级决策：有
26、某旅行者从 A 地出发到 F 地，可以选择两条路线，一是途经 B 地，D 地到 F ;另一是途经 C 地，E 地到 F (如图),每段路程所需的费用在图中标出。这个问题是以总旅费达到最小作为目标，显然应选择：A C E F。 整个规划的目标是使得最终结果达到最优，这就意味着，某一段作出的决策，就这个阶段来说，并不一定是一个最优的选择，甚至要作出某些牺牲（如上例第一段）。但是由于各阶段的相互影响，到最后却会得到一个最优的结果。相反，在这一阶段选择了一个最优的决策，并不等于最后得到最优结果，这就是动态规划的特点。 使用动态规划方法解决多阶段决策问题，首先要将实际问题写成动态规划模型，此时要用到以下
27、概念：（1）阶段；（2）状态；（3）决策和策略；（4）状态转移；（5）指标函数。 下面我们结合以下例题说明这些概念。例 5.1 最短路线问题。 如图所示，给定一个线路网络图，要从 A 地向 F 地铺设一条输油管道，各点间连线上的数字表示距离，问应选择什么线路，可使总距离最短？ A468335425B1B2E2FD1E1C1C2C3C4D3D2737835448431265（1）阶段。 将所给问题的过程，按时间或空间特征分解成若干互相联系的阶段，以便按次序去求每阶段的解。 （2）状态。 各阶段开始时的客观条件叫状态。描述各阶段状态的变量称为状态变量，sk 表示第 k 阶段的状态变量 ，sk 的取
28、值集合称为状态集合，用 Sk 表示。在例5.1中，各阶段的状态集合分别是： 当某段的初始状态已选定某个点时，从这个点以后的铺管路线只与该点有关，不受以前铺管路线的影响，这叫状态变量的“无后效性”，如果所选的状态变量不具备“无后效性”就不能用来构造动态规划模型。, , , 2153214432132121EESDDDSCCCCSBBSAS（3）决策和策略。 当各段的状态取定以后，就可以作出不同的决定，从而确定下一阶段的状态，这种决定称为决策。表示决策的变量，称为决策变量，常用 uk(sk) 表示第 k 阶段当状态为 sk 时的决策变量，Dk(sk) 表示第 k 阶段从状态 sk 出发的允许决策集
29、合。 在例5.1中，有 D2(B1)=C1, C2, C3 如我们决定选择 C3，则可表为： u2(B1)=C3 各段决策确定后，整个问题的决策序列就构成一个策略，用 p1,n u1(s1),u2(s2),un(sn)表示，P1,n 表示允许决策的集合，使整个问题达到最优效果的策略就是最优策略。(4)状态转移方程。 动态规划中，如果给定了第 k 阶段的状态 sk 和本阶段决策 uk(sk) 则第 k+1 段的状态 sk+1 也就完全确定，它们的关系可用下列状态转移方程表示： sk+1=Tk(sk,uk)例5.1中，状态转移方程为： sk+1=uk(sk)（5）指标函数。 用于衡量所选定策略优劣
30、的数量指标称为指标函数。它分 为阶段指标函数和过程指标函数两种。阶段指标函数是指第 k段，从状态 sk 出发，采取决策 uk 时的效益，用 d (sk,uk) 表示。一个 n 段的决策过程，从 1 到 n 叫做问题的原过程，对任意给定的 ,从第 k 段到第 n 段的过程称为原过程的一个后部子过程。V1,n(s1,p1,n) 表示初始状态为 (1)kkns1 采用策略 p1,n 时，后部子过程的指标函数值，而Vk,n(sk,pk,n)表示在第 k 段，状态为 sk 采用策略 pk,n时 ，后部子过程的指标函数值。最优指标函数记为 fk(sk) ,它表示从第 k 段状态 sk 采用最优策略 到过程
31、终止时的最佳效益值。即：当 k1 时， 就是从初始状态 到全过程结束的整体最优函数。 下面用动态规划方法求解例5.1 。本方法是从过程的最后一段开始，用逆序递推方法求解，逐步求出各段各点到终点 F 的最短路线。*,k np,*,()(,)(,)k nk nkkk nkk nk nkk npPfsVspopt Vsp11( )f s1s第一步：从 k=5 开始，状态变量 s5 可取两种状态 E1, E2, 它们到 F 点的路长分别为 4，3 。即：第二步：k=4，状态变量可取三个值D1, D2, D3, 从 D1 到 F 有两条路线，需要加以比较，取其中最短的，即：这说明 D1 到 F 最短距离
32、为 7 , 其路径为 D1 E1 F 。相应决策 。5152()4 ()3fEfE735 43 min)(),( )(),( min)(2521151114EfEDdEfEDdDf11*4)(EDu532 46 min)(),( )(),( min)(2522151224EfEDdEfEDdDf即 D2 到 F 最短距离为 5 , 其路径为 D2 E2 F 。相应决策为 。即 D3 到 F 最短距离为 5 , 其路径为 D3 E1 F 。相应决策为 。类似地，可算得：*4()22uDE533 41 min)(),( )(),( min)(2523151334EfEDdEfEDdDf13*4)(
33、EDu34*34323*33322*32311*313)( 9)( )( 8)( )( 10)( )( 12)( 3DCuCfDCuCfDCuCfDCuCfk时，有FEDCBAFEuEDuDCuCBuBAuuBAuFABfBAdBfBAdAfCBuBfCBuBfkk22212*522*422*321*21*11*1222121132*22221*212 )( ,)( ,)( ,)( ,)(: , . )( 17 17155 134 min)(),( )(),( min)( A 1k)( 15)( )( 13)( 2所以最优路线为：即最优决策序列在按计算顺序反推可得。本段决策为的最短距离为到即从
34、，则只有一个状态点时，时，有。转移关系有递推的状态证各阶段的状态变量具正确选择状态变量，保的关键又在于建立基本递推关系方程的若干子问题，而正确系式联系起来题分解成为可用递推关题的多阶段特征，将问，在于识别问用动态规划方法的关键划基本方程。成功地应的动态规是分析问题并建立问题建立动态规划模型，就规划的基本方程。这种递推关系称为动态段的如下关系：段和第第利用了，在求解的各阶段，都的计算过程中可以看出从例 ),( 0)(1 , 2 , 3 , 4 , 5 )(),(min)( 1 1 . 516611kkkkkkkkkukkusTssfksfusdsfkkk全渡河那？人怎样才能安掌握在商人们手中。商
35、是如何乘船渡河的大权杀人越货。但从的人数比商人多，就在河的任一岸，一旦随。随从们密约，二人，由他们自己划行河，一只小船只能容纳从乘船渡）三名商人各带一个随（商人们怎样安全过河例成最优策略”。其以后的所有决策应构的状态而言，对于先前决策所形成始状态及初始决策如何质：即无论初最优策略具有这样的性表述为：“一个过程的理，它可曼等人提出的最优化原动态规划方法基于贝尔 2 . 5 3名商人名商人 3名随从名随从问题分析问题分析: 安全渡河问题可以安全渡河问题可以视为一个多步决策过程。视为一个多步决策过程。每一步，即船由每一步，即船由此岸到此岸到彼岸或从彼岸驶回此岸，彼岸或从彼岸驶回此岸，都要对都要对船上
36、的人员（商船上的人员（商人、随从各几人）作出人、随从各几人）作出决策，在保证安全的前决策，在保证安全的前提下（两岸的随从数都提下（两岸的随从数都河河小船小船(至多至多2人人)不比商人数多），在有限步内全部人员过河。用状态变不比商人数多），在有限步内全部人员过河。用状态变量表示某一岸的人员状况，决策变量表示船上的人员状量表示某一岸的人员状况，决策变量表示船上的人员状况，于是可以找出状态随决策变化的规律。况，于是可以找出状态随决策变化的规律。模型构成模型构成xk第第k次渡河前此岸的商人数次渡河前此岸的商人数yk第第k次渡河前此岸的随从数次渡河前此岸的随从数xk, yk=0,1,2,3; k=1,2
37、, 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 +(-1)k状态转移律状态转移律求求dk D(k=1,2, n), 使使sk S, 并按并按转移律转移律由由 s1=(3,3)到达到达 sn+1=(0,0).多步决策多
38、步决策问题问题模型求解模型求解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), 1(miAi), 1(njXjj1 , 101n
39、jjj：评价对象（可替代且非劣的方案）评价对象（可替代且非劣的方案）：评价指标（准则、项目）：评价指标（准则、项目）：评价指标权重，评价指标权重，1、关联矩阵法、关联矩阵法综合评价方法综合评价方法 n21Vi X1 X2 Xn mjjjmjjjnjjjVVVVVV22111XjjVijAi?ijVij = ?逐对比较法、古林法逐对比较法、古林法 A1A2AmV11 V12 V1nV21 V22 V2nVm1 Vm2 Vmn . . .评价指标评价指标Xj替代方案替代方案Ai期望利期望利润（万润（万元）元）产品成品产品成品率（率（%）市场占有市场占有率（率（%）投资费用投资费用（万元）（万元）产
40、品外观产品外观自行设计自行设计（A1）6509530110美美 观观国外引进国外引进（A2）7309735180比较美观比较美观改改 建（建（A3）520922550美美 观观 方案预期结果例表方案预期结果例表评价指标评价指标得分序号得分序号累计得累计得分分权重权重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 逐对比较法例表逐对比较法例表 评价尺度评价尺度(得分得分)评价指标评价
41、指标54321期望利润（万期望利润（万元）元）800以上以上701-800601-700501-600500以下以下产 品 成 品 率产 品 成 品 率（%）97以上以上96-9791-9586-9085以下以下市 场 占 有 率市 场 占 有 率（%）40以上以上35-3930-3425-2925以下以下投资费用（万投资费用（万元）元）20以下以下21-8081-120121-160160以上以上产品外观产品外观非常美观非常美观美观美观比较美观比较美观一般一般不美观不美观 评价尺度例表评价尺度例表 VijAij 期望期望利润利润产品成产品成品率品率市场占市场占有率有率投资投资费用费用产品产品
42、外观外观Vi0.40.30.10.20.0自行设自行设计计(A1)333343.0国外引国外引进进(A2)444133.4改建改建(A3)232442.7Xj 关联矩阵表（逐对比较法）关联矩阵表（逐对比较法）j341/2序号序号评价指标评价指标RjKj1期望利润期望利润180.5802产品成品率产品成品率60.1943市场占有率市场占有率20.0654投资费用投资费用40.1295产品外观产品外观10.032合计合计311.0003Rj Kj Wj 基准化基准化 归一化归一化 古林法求古林法求j 例表例表序号（序号（j）评价指标评价指标替代方案替代方案RijKijVij1期望利润期望利润A10
43、.8901.2500.342A21.4041.4040.384A31.0000.2742产品成品产品成品率率A10.9791.0320.334A21.0541.0540.342A31.0000.324 古林法求古林法求Vij例表例表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.272A31.0000.364 古林法求古林法求Vij例表（续）
44、例表（续）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 关联矩阵例表（古林法）关联矩阵例表（古林法）Analytic Hierarchy ProcessAHP（美国运筹学家、匹兹堡大学教授（美国运筹学家、匹兹堡大学教授T.L.Saaty,1977）投资效果好（投资效果好（T）风险程度（风险程度
45、（I1）资金利润率（资金利润率（I2）转产难易程度（转产难易程度（I3）产品产品1（P1）产品产品2（P2）产品产品3（P3）（目的层）（目的层）（准则层）（准则层）（方案层）（方案层）三、层次分析（三、层次分析（AHP）法）法判断矩阵标度定义判断矩阵标度定义 标度标度含义含义1两个要素相比，具有同样重要性两个要素相比，具有同样重要性3两个要素相比，前者比后者稍微重要两个要素相比，前者比后者稍微重要5两个要素相比，前者比后者明显重要两个要素相比，前者比后者明显重要7两个要素相比，前者比后者强烈重要两个要素相比，前者比后者强烈重要9两个要素相比，前者比后者极端重要两个要素相比，前者比后者极端重要
46、2，4，6，8上述相邻判断的中间值上述相邻判断的中间值倒数倒数两个要素相比，后者比前者的重要性标度两个要素相比，后者比前者的重要性标度 AHP方法的基本工具方法的基本工具判断矩阵判断矩阵TI1I2I3WiWioI111/320.8740.230I23152.4660.648I31/21/510.4640.122(3.804) 注注 Wi的求取采用方根法（求根法或称几何平均值法）的求取采用方根法（求根法或称几何平均值法） I1P1P2P3WiWioP111/31/50.4060.105P2311/31.0000.258P35312.4660.637 判断矩阵及其分析处理举例判断矩阵及其分析处理举
47、例I2P1P2P3WiWioP11272.4100.592P21/2151.3570.333P31/71/510.3060.075I3P1P2P3WiWioP111/31/70.3620.081P2311/50.8430.188P37513.2710.731 判断矩阵及其分析处理举例（续）判断矩阵及其分析处理举例（续） 求综合重要度（加权和）求综合重要度（加权和） T I1 I2 I3 综合综合 重要度重要度 权重权重 0.230 0.648 0.122（加权和）（加权和） P1 0.105 0.592 0.149 0.426 P2 0.258 0.333 0.066 0.283 P3 0.6
48、37 0.075 0.785 0.291（1）分析评价系统中各基本要素之间的关系，建立）分析评价系统中各基本要素之间的关系，建立系统的递阶层次结构（分解法）；系统的递阶层次结构（分解法）；（2）对同一层次的各要素关于上一层次中某一准则）对同一层次的各要素关于上一层次中某一准则的重要性进行两两比较，构造判断矩阵（专家调查的重要性进行两两比较，构造判断矩阵（专家调查法）；法）；（3）由判断矩阵计算被比较要素对于该准则的相对）由判断矩阵计算被比较要素对于该准则的相对权重（方根法）；权重（方根法）；（4）计算各层要素相对于系统目的（总目标）的合）计算各层要素相对于系统目的（总目标）的合成（总）权重，并
49、据此对方案等排序（加权和法）。成（总）权重，并据此对方案等排序（加权和法）。AHP方法步骤方法步骤 课程：课程： 教师：教师： 班级：班级： 评价项目（权重）评价项目（权重）好好（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
50、 0.0410 0.4011 0.443 0.12评价结果评价结果(票数票数/隶属度隶属度) ) 评价等级评价等级四、模糊综合评判法（四、模糊综合评判法（1）5.课堂教学形式的多样化程度（课堂教学形式的多样化程度（0.10）2 0.0811 0.4412 0.480 0.006.理论联系实际程度及教学案例使用情理论联系实际程度及教学案例使用情况（况（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.321
