数学建模_第五章_数学规划模型

1、数学建模（Mathematical Modeling)黑龙江科技学院理学院工程数学教研室黑龙江科技学院第五章数学规划模型数学建模理学院第五章 数学规划模型黑龙江科技学院数学规划论起始20世纪30年代末，50年代与60年代发展成为一个完整的分支并受到数学界和社会各界的重视。七八十年代是数学规划飞速发展时期，无论是从理论上还是算法方面都得到了进一步完善。时至今日数学规划仍然是运筹学领域中热点研究问题。从国内外的数学建模竞赛的试题中看，有近1/4的问题可用数学规划进行求解。理学院数学建模第五章 数学规划模型线性规划模型 整数规划模型 非线性规划模型动态规划模型 多目标规划模型建模举例重点:数学规划模

2、型的建立和求解难点:数学规划模型的基本原理及数值计算理学院黑龙江科技学院数学建模1、例1：黑龙江科技学院某机床厂生产甲、乙两种机床，每台销售后的利润分别为4000元与3000元。生产甲机床需用A，B机器加工，加工时间分别为每台2小时和1小时；生产乙机床需用A，B，C三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为A机器10小时、B 机器8小时和C机器7小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？数学建模理学院设该厂生产x1台甲机床和x2台乙机床时总利润最大，则x1,x2应满足:黑龙江科技学院z = 4x1 + 3x2目标函数 : max约束条件 :2x+ x 1

3、012x+ x 812数学建模x2 7, x 0x12理学院一般线性规划问题的标准型为nz = cj xj黑龙江科技学院minj=1naij xj j=1 bii = 1, 2,s.t., m线性规划的Matlab标准形式f= c1x1 + c2 x2 + cn xnmin数学建模+ a12 x2 + a1n xn b1a11 x1ax+ ax+ ax b2112222nn2s.t ax+ ax+ ax bm11m22mnnmxi 0(i = 1, 2, n)理学院线性规划模型矩阵的形式：黑龙江科技学院Ax bmin cT x xsuch that例如线性规划max cT x xAx bsuc

4、h that数学建模Matlab标准型为min- cT x x- Ax -bsuch that理学院 4、线性规划的图解法黑龙江科技学院1092x1+x2=1087x2=76(2,6)543数学建模2x1+x2=81z=1200246810x* = (2,6)T本例的最优解为最优目标值z* = 26理学院5、求解线性规划的Matlab解法单纯形法是首先由George Dantzig于1947年提出的，近60年来，虽有许多变形体已被开发，但却保持着同样的基本观念。由于有如下结论：若线性规划问题有有限最优解，则一定有某个最优解是可行区域的一个极点。基于此，单纯形法的基本思路是：先找出可行域的一个极

5、点，据一定规则判断其是否最优；若否，则转换到与之相邻的另一极点，并使目标函数值更优；如此下去，直到找到某一最优解为止。黑龙江科技学院数学建模理学院Matlab2008b中线性规划的标准型为：黑龙江科技学院Ax bmin cT xsuch that基本函数x 形式为linprog(c,A,b)，它的返回值是向量的值。还有其它的一些函数调用形式（在 Matlab 指令窗运行help linprog 可以看到所有的函数调用形式），如：x,fval=linprog(c,A,b,Aeq,beq,LB,UB,X0,OPTIONS) 这里fval返回目标函数的值，Aeq和beq对应等式约束， LB和UB分别

6、是变量的下界和上界，是的初始值，OPTIONS是控制参数。数学建模理学院例5.1.2求解下列线性规划问题max z = 2x1 + 3x2 - 5x3黑龙江科x1 + x2 + x3 = 72x- 5x+ x 10123x , x , x 0123解 （i）编写M文件c=2;3;-5;a=-2,5,-1; b=-10;aeq=1,1,1;beq=7;x=linprog(-c,a,b,aeq,beq,zeros(3,1) value=c*x（ii） 将M文件存盘，并命名为example1.m。（iii） 在Matlab指令窗运行example1即可得所技学 院数学建 模理学院求结果。黑龙江科技学

7、院例5.1.3 求解线性规划问题minz = 2x1 + 3x2+ x3x1 + 4x2 + 2x3 83x1 + 2x2 6x , x, x 0123解 编写Matlab程序如下：c=2;3;1; a=1,4,2;3,2,0; b=8;6;x,y=linprog(c,-a,-b, , ,zeros(3,1)数学建模理学院指派问题例5.15拟分配n人去干n项工作，每人干且仅干一项工作，若分配第i人去干第j项工作， 需花费cij单位时间，问应如何分配工作才能使工人花费的总时间最少？黑龙江科技学院引入变量xij，若分配i干j工作，则取xij=1， 否则取xij=0。上述指派问题的数学模型为:nx=

8、 1,i = 1,2,L, n数学建模nncij xiji=1j =1ijminj=1n xij= 1, j = 1,2,L, n i=1xij= 0 或1,i, j = 1,2,L, n理学院黑 龙江科可行解既可以用一个矩阵(称为解矩阵)表示， 其每行每列均有且只有一个元素为1，其余元素均为0，也可以用1,n中的一个置换表示。求解指派问题的匈牙利算法技学院由于指派问题的特殊性，又存在着由匈牙利数学家D.Konig提出的更为简便的解法匈牙利算法。算法主要依据以下事实：如果系数矩阵数学建模C=c 一行（或一列）中每一元素都加上或减去ij同一个数，得到一个新矩阵B=bij，则以C或B为系数矩阵的指

9、派问题具有相同的最优指派。理学院黑龙江科技学院数学建模理学院可将原系数阵C变换为含零元素较多的新系数阵B， 而最优解不变。若能在B中找出n个位于不同行不同列的零元素，令解矩阵中相应位置的元素取值为1， 其它元素取值为0，则所得该解是以B为系数阵的指派问题的最优解，从而也是原问题的最优解。由C到B的转换可通过先让矩阵C的每行元素均减去其所在行的最小元素得矩阵D，D的每列元素再减去其所在列的最小元素得以实现。例5.1.6求解指派问题，其系数矩阵为黑龙江科技学院161722152122191919182218C = 17241716将第一行元素减去此行中的最小元素15， 同样，第二行元素减去17，第

10、三行元素减去17，最后一行的元素减去16，得数学建模107045342161= 0B1710理学院再将第3列元素各减去1，得黑龙江科技学院 10*7 0*453310*51 = B 70 2 1*0以B2为系数矩阵的指派问题有最优指派0100数学建模 14213310即 24000010X = 0001理学院例5.1.7 求解系数矩阵C的指派问题黑龙江科技学院127917141096126776146109 86 C = 7121510 46 解 先作等价变换如下数学建模- 7- 6- 7- 6- 4127917141096126776146109 50 *310862050 *300 *70

11、62 86 20 75 12 0 *1510 94 46 02 理学院容易看出，从变换后的矩阵中只能选出四个位于不同行不同列的零元素，但n=5，最优指派还无法看出。此时等价变换还可进行下去。步骤如下：黑龙江科技学院（1） 对未选出0元素的行打；（2） 对行中0元素所在列打；（3） 对列中选中的0元素所在行打； 重复（2）、（3）直到无法再打为止。可以证明，若用直线划没有打的行与打的列，就得到了能够覆盖住矩阵中所有零元素的最少条数的直线集合，找出未覆盖的元素中的最小者，令行元素减去此数，列元素加上此数，则原先选中的0元素不变，而未覆盖元素中至少有一个已转变为0，且新矩阵的指派问题与原问题也等价。

12、理学院数学建模黑 龙江科技学院上述过程可反复采用，直到能选取出足够的0 元素为止。例如，对例5.1.7变换后的矩阵再变换，第三行、第五行元素减去2，第一列元素加上2，得 70388420301005042 40 03114 00数学建 15243143模最优指派为 25理学院 建模举例：营养配餐问题黑龙江科技学院每种蔬菜含有的营养素成份是不同的，从医学上知道，每人每周对每种营养成分的最低需求量。某医院营养室在制定下一周菜单时，需要确定表2-4中所列六种蔬菜的供应量，以便使费用最小 而又能满足营养素等其它方面的要求。规定白菜 的供应一周内不多于20千克，其它蔬菜的供应在 一周内不多于40千克，每

13、周共需供应140千克蔬 菜，为了使费用最小又满足营养素等其它方面的 要求，问在下一周内应当供应每种蔬菜各多少千克？数学建模理学院 表5-4黑龙江科技学院数学建模理学院序号蔬 菜每 份 所 含 营 养 素 单 位 数每千克费 用铁磷维生素A维生素C烟酸1青 豆0.451041580.3052胡萝卜0.4528906530.3553菜 花1.05592550530.6084白 菜0.402575270.1525甜 菜0.50221550.2566土 豆0.507523580.803要求蔬菜提供的营养6.0025175002455.00问题分析黑龙江科技学设xi (i = 1分别) 表示下一周内应当

14、供应的青 6豆、胡萝卜、菜花、白菜、甜菜及土豆的量， 费用目标函数为： f= 5x+ 5x+ 8x+ 2x+ 6x+ 3x123456院束约条件：铁的需求量至少6个单位数：0.45x1 + 0.45x2 +1.05x3 + 0.40x4 + 0.50x5磷的需求量至少25个单位数：数学建模+ 0.50x6 610x1 + 28x2 + 59x3 + 25x4 + 22x5 + 75x6 25理学院问题分析黑维生素A的需求量至少17500个单位： 415x1 + 9065x2 + 2550x3 + 75x4 +15x5 + 235x6 17500龙江科维生素C的需求量至少245个单位：技8x1

15、+ 3x2 + 53x3 + 27x4 + 5x5 + 8x6 245学院烟酸的需求量至少5个单位数：数 0.30x1 + 0.35x2 + 0.60x3 + 0.15x4 + 0.25x5 + 0.80x6 5学每周需供应140千克蔬菜，即 x1 + x2 + x3 + x4 + x5 + x6= 140建模理学院 模型的建立黑龙江科技学院f= 5x + 5x+ 8x+ 2x+ 6x+ 3xmin123456x1 + x2 + x3 + x4 + x5 + x6 = 1400.45x + 0.45x+1.05x+ 0.40x+ 0.50x+ 0.50x 612345610x + 28x+ 5

16、9x+ 25x+ 22x+ 75x 25123456s.t 415x1 + 9065x2 + 2550x3 + 75x4 +15x5 + 235x6 175008x1 + 3x2 + 53x3 + 27x4 + 5x5 + 8x6 245数学建模0.30x + 0.35x+ 0.60x+ 0.15x+ 0.25x+ 0.80x 51234560x1400x4200x2400x5400x3400x640理学院 模型求解黑龙江科技学院利用Matlab软件编程序：% 营养配餐ch21% 文件名： ch21 m c=5;5;8;2;6;3;A=(-1)*1,1,1,1,1,1;0.45,0.45,1.

17、05,0.40,0.50,0.50;10,28,59,25,22,75; 415,9065,2550,75,15,235;8,3,53,27,5,8;0.30,0.35,0.60,0.15,0.25,0.80; b=(-1)*140;6;25;17500;245;5;xLB=zeros(6,1); xUB=40;40;40;20;40;40;nEq=1; x0=0*ones(6,1);x=lp(c,A,b,xLB,xUB,x0,nEq);数学建模理学院 模型求解黑龙江科技学院disp(青豆需要的份数)x(1)disp(胡罗卜需要的份数x(2) 行disp(菜花需要的份数x(3)disp(白菜需

18、要的份数x(4)disp(甜菜需要的份数x(5) 输 出)数学建模)disp(土豆需要的份数)x(6)理学院执 模型求解黑龙江科技学院青豆需要的份数ans =40胡罗卜需要的份数ans =40.0000菜花需要的份数ans =0白菜需要的份数ans =20.0000 行 出数学建模理学院输执 模型求解黑龙江科技学院甜菜需要的份数ans =0土豆需要的份数ans =40最小费用ans = 560.0000 行 出数学建模理学院输执5.2 整数规划模型有些LP往往要求全部或部分决策变量取非负整数值，如计件产品的生产计划、合理下料、设施的配备决策等， 这样的LP称为整数线性规划。黑龙江科技学院目前所

19、流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。数学建模理学院1. 整数规划的分类如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类：（i） 变量全限制为整数时，称纯（完全）整数规划。（ii） 变量部分限制为整数的，称混合整数规划。（iii） 变量只能取0或1时，称之为0-1整数规划。2.整数规划特点（i） 原线性规划有最优解，当自变量限制为整数后， 其整数规划解出现下述情况：原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。整数规划无可行解（ii） 整数规划最优解不能按照实数最优解简单取整而获得。理学院 分枝定

20、界法黑 对有约束条件的最优化问题（其可行解为有限数）的可行解空间恰当地进行系统搜索，这就是分枝与定界内容。通常，把全部可行解空间反复地分割为越来越小的子集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题）， 这称为定界。在每次分枝后，凡是界限不优于已知可行解集目标值的那些子集不再 进一步分枝，这样，许多子集可不予考虑， 这称剪枝。这就是分枝定界法的主要思路。理学院龙江科技学院数学建模设有最大化的整数规划问题A，与它相应的线性规划为问题B，从解问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标Z函数Z*的上界，记作 Z；黑龙江科技学院而A的任意可行解

21、的目标函数值将是Z*的一个下界Z。分枝定界法就是将B的可行域分成子区域再求其最大值的方法。逐步减小大Z，最终求到Z*。和增数学建模理学院例5.2.3求解下述整数规划Maxz = 40x1 + 90x29x1 + 7x2 567x+ 20xs.t. 70且为整数12x , x 012解 （i）先不考虑整数限制，即解相应的线性规= 4.8092, x2 = 1.8168, z = 355.8779划，得最优解为：x1可见它不符合整数条Z件。这时Z是问题A的最优目标函数值Z*的上界，记作。而x1=0,x2=0显然是问题A的一个整数可行解，这时Z=0，是Z*的一个下界，记作，即0Z*356。因为x1,

22、x2当前均为非整数，故不满足整数要求， 任选一个进行分枝。设选x1进行分枝，把可行集分成2个子集：x1 4.8 = 4x1 4.8 +1 = 5，因为4与5之间无整数，故这两个子集内的整数解s.t. 必与原可行集合整数解一致。这一步称为分枝。这两个子集的规划及求解如下：问题B1：z = 40x1 + 90x29x1 + 7x2 56Max7x+ 20x 70120 x 4, x 012最优解为：x1 = 4.0, x2= 2.1, z1 = 349z = 40x1 + 90x2问题B2Max9x1 + 7x2 567x+ 20xs.t. 7012x 5, x 012x1 = 5.0, x2 =

23、 1.57, z1= 341.4最优解为：0 z* 349以此类推找出最优解。从以上解题过程可得用分枝定界法求解整数规划（最大化）问题的步骤为：开始，将要求解的整数规划问题称为问题A， 将与它相应的线性规划问题称为问题B。（i） 解问题B可能得到以下情况之一：（a） B没有可行解，这时A也没有可行解， 则停止（b） B有最优解，并符合问题A的整数条件，B的最优解即为A的最优解，则停止。（c）B有最优解Z，但不符合问题A的整数条件，记它的目标函数值为。（ii）用观察法找问题A的一个整数可行解， 一般可取xj=0，j=1,n试探，求得其目标函数 值，并记作Z。以Z*表示问题A的最优目标函数z z*

24、 z值；这时有x j bj xj bj + 1 进行迭代。第一步：分枝，在B的最优解中任选一个不符合整数条件的变量xj，其值为bj，以bj表示小于bj的最大整数。构造两个约束条件将这两个约束条件，分别加入问题B，求两个后继规划问题B1和B2。不考虑整数条件求解这两个后继问题。定界，以每个后继问题为一分枝标明求解的结果，与其它问题的解的结果中，找出最优黑龙江科技学院目标函数值最大者作为新的上界。从已符合整数条件的各分支中Z，找出目标函数值为最大者作为新的下界Z，若无作用Z=0。第二步：比较与剪枝，各分枝的最优目标函数中若有小于Z者，则剪掉这枝，即以后不再考虑了。若大于Z，且不符合整数条件， 则重

25、复第一步骤。一直到最后得到Z*=Z为止。得最优整数解 xj*,j=1,n.数学建模 0-1型整数规划 0-1型整数规划是整数规划中的特殊情形， 它的变量xj仅取值0或1。这时称为0-1变量，黑龙江科技学院或称二进制变量。x 仅取值0或1这个条件可j由下述约束条件：0 xj 1整数所代替，是和一般整数规划的约束条件形式一致的。在实际问题中，如果引入0-1变量，就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中讨论了。我们先介绍引入0-1变量的实际问题，再研究解法。数学建模例5.2.4某公司拟在市东、西、南三区建立黑龙江科技学院门市部。拟议中有7个位置（点）Ai(i=1,2,7)可供选择

26、。规定在东区：由A1,A2,A3三个点中至多选两个；在西区：由A ,A 两个点中至少选一个；45在南区：由A6,A7两个点中至少选一个。数学建模如选用Ai点，设备投资估计为bi元，每年可获利润估计为c 元，但投资总额不能超过Bi元。问应选择哪几个点可使年利润为最大？黑 解 先引入0-1变量xi,i=1,2,7龙 令1,当Ai点被选中，江科技学= xi0， 当Ai点没被选中.7z = ci xii=1院 于是问题可列写成M：ax7bi xi B+ x3 1 1,数学建模 i=1x1+ x2+ x5 2x4x6 + x7xi = 0或1黑0-1型整数规划解法之一（过滤隐枚举法）解0-1型整数规划最

27、容易想到的方法，和一般整数规划的情形一样，就是穷举法，即检查变量取值为0或1的每一种组合，比较目标函数值以求得最优解，这就需要检查变量取值的2n个组合。对于变量个数n较大，这几乎是不可能的。因此常设计一些方法，只检查变量取值的组合的一部分，就能求到问题的最优解。这样的方法称为隐枚举法，分枝定界法也是一种隐枚举法。当然，对有些问题隐枚举法并不适用， 所以有时穷举法还是必要的。龙江科技学院数学建模理学院黑龙江 例5.2.5z = 3x1 - 2x2+ 5x3Maxx科技学院+ 2x- x 2123+ 4x2 + x3 4x1s.t.+ x2 3x14x+ x 623数学x1 , x2 , x3 =

28、 0或1建 模 求解思路及改进措施：（i） 先试探性求一个可行解，易看出(x1,x2,x3)=(1,0,0)满足约束条件，故为一个可行解，且相应的目标函数值为z=3。理学院黑ii） 因为是求极大值问题，故求最优解时，凡龙 是目标值z3的解不必检验是否满足约束条件江 即可删除，因它肯定不是最优解，于是应增加科技 一个约束条件（目标值下界）：3x1- 2x2 + 53 3学 称该条件为过滤条件)。从而原问题等价于：院a b cd ef3x- 2x+ 5x 3123x+ 2x- x 2123数学建模z = 3x1 - 2x2 + 5x3Maxx1x+ 4x2 + x3 4+ x 3124x2 + x

29、3 6= 0或1x1 , x2 , x3黑 龙江科技学院若用全部枚举法，3个变量共有8种可能的组合，我们将这8种组合依次检验它是否满足条件(a)(e)，对某个组合，若它不满足(a)，即不满足过滤条件，则(b)(e)即可行性条件不必再检验；若它满足(a)(e)且相应的目标值严格大于3，则进行（iii）。（iii） 改进过滤条件。（iv） 由于对每个组合首先计算目标值以验证过滤条件，故应优先计算目标值大的组合，这样可提前抬高过滤门槛，以减少计算量。按上述思路与方法，例5.2.5的求解过程可由下表来表示：数学建模 黑龙江科技学院数学建模最优值= 8z*(x*, x*, x*) = (1, 0,1)从

30、而得最优解123(x1,x2,x3)目标值约束条件过滤条件a b c d e(0,0,0)0(1,0,0)3 3x1 - 2x2 + 53 3(0,1,0)-2(0,0,1)5 3x1 - 2x2 + 53 5(1,1,0)1(1,0,1)8 3x1 - 2x2 + 53 8(1,1,1)6(0,1,1)3整数规划的计算机解法黑龙江 整数规划问题的求解可以使用Lingo等专用软件。对于一般的整数规划规划问题，无法直接利用Matlab的函数，必须利用Matlab编程实现分枝定界解法和割平面解法。但对于指派问题等特殊的0-1整数规划问题或约束矩阵A是幺模矩阵时，有时可以直接利用Matlab的函数l

31、inprog。科技学院数学建模5.2.6求解下列指派问题，已知指派矩阵为解 编写Matlab程序如下：33 874422226109739c=3 8 2 10 3;8 7 2 9 7;6 4 2 7 5867 5 8 4 2 3 5;9 10 6 9 10;c=c(:);a=zeros(10,25); for i=1:5a(i,(i-1)*5+1:5*i)=1;85 91010a(5+i,i:5:25)=1;end b=ones(10,1);x,y=linprog(c,a,b,zeros(25,1),ones(25,1)= x23 = x32 = x44 = x51 =1x15求得最优指派方案

32、为5.3非线性规划如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非 线性规划问题。一般说来，解非线 性规划要比解线性规划问题困难得 多。而且，也不象线性规划有单纯 形法这一通用方法，非线性规划目前还没有适于各种问题的一般算法， 各个方法都有自己特定的适用范围。例5.3.1（投资决策问题）某企业有个项目可供选择投资，并且至少要对其中一个项目投资。已知该企业拥有总资金元，投资于第个项目需花资金元，并预计可收益元。试选择最佳投资方案。解设投资决策变量为= 1,决定投资第i个项目xi0， 决定不投资第i个项目n0 ai xi A限制条件i=1由于xi只取值0或1xi (1- xi ) =

33、0, i =1, n.最佳投资方案应是投资额最小而总收益最大的方案，所以这个最佳投资决策问题归结为总资金以及决策变量（取0或1）的限制条件下，极大化总收益和总投资之比。因此，其数学模型为nbi xi i=1ns.t.0 a x Amax Q =niia xi=1iii=1xi (1- xi ) = 0, i =1, n.非线性规划问题一般形式：minf ( x)hj (x) 0,j = 1,L, qs.t.gi (x) = 0,i = 1,L, px = xT其中Lx称为模型的决策变量，1nf称为目标函数，gi(x)和hi(x)称为约束函数另外， gi(x)=0 称为等式约束，hi(x)0 称

34、为不等式约束 非线性规划的Matlab解法Matlab中非线性规划的数学模型形式minf(x) Ax B Aeq x = BeqC(x) 0Ceq(x) = 0其中是标量函数，是相应维数的矩阵和向量， 是非线性向量函数。Matlab中的命令是X=FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB, NONLCON,OPTIONS)例5.3.1 求下列非线性规划问题min f (x) = x 2 + x+ 8212- x 0x212- x- x+ 2 = 0212x , x 0.12(1) 编写M文件fun1.mfunction f=fun1(x); f=x(1)2+x(2)2+8

35、;和M文件fun2.mfunction g,h=fun2(x); g=-x(1)2+x(2);h=-x(1)-x(2)2+2; %等式约束(2) 在Matlab的命令窗口依次输入options=optimset;x,y=fmincon(fun1,rand(2,1),zeros(2,1),fun2, options)就可以求得当时x1=1，x2=1最小值y=10。课前讨论题：最短路径问题求从A点到B点的最短路径共有多少条？BA求从A点到G点的最短路径？C1685122D1E135B331CF568742151233AD2E2G233833BC26F2366D3E34C4最优路线为：A B1 C2

36、 D1 E2 F2 G 引例导入：最短路问题及其解法在下面网络图中，其中圆圈称为点，两点之间的连线称为弧，弧上的数字称为弧长。6C11D1B1833536C25A82D2E337C3B23268D34C4 一、多阶段决策问题动态规划的研究对象是：多阶段决策问题多阶段决策问题：根据问题本身的特点，可以将其求解的全过程划分为若干个相互联系的阶段(即将问题划分为许多个相互联系的子问题)，在它的每一阶段都需要作出决策，并且在一个阶段的决策确定以后再转移到下一个阶段。 多阶段决策过程 前一个阶段的决策要影响到后一个阶段的决策，从而影响整个过程。各个阶段所确定的决策就构成了一个决策序列，称为一个策略。一般

37、来说，由于每一阶段可供选择的决策往往不止一个，因此，对于整个过程，就会有许多可供选择的策略。 最优策略 若对应于一个策略，可以由一个量化的指标来确定这个策略所对应的活动过程的效果，那么不同的策略就有各自的效果。在所有可供选择的策略中，对应效果最好的策略称为最优策略。把一个问题划分成若干个相互联系的阶段选取其最优策略，这类问题就是多阶段决策问题。 二、多阶段决策问题类型由于市场需求是一随着时间而变化的因素，因 工厂 生产 过程此，为了取得全年最佳经济效益，就要在全年的生产过程中，逐月或者逐季度地根据库存和需求情况决定生产计划安排。一般企业用于生产活动的设备，刚买来时故障少， 经济效益高，随着使用

38、年限的增加，就会逐渐变 设 备 更 新 问 题为故障修费用增加，可正常使用的工时减少，加工质量下降，经济效益差，并且，使用的年限越长、处理价值也越低，自然，如果卖去旧的买新的，还需要付出更新费因此就需要综合权衡决定设备的使用年限，使总的经济效益最好。 资 源 分 配 问 题某工业部门或公司，拟对其所属企业进行稀缺资源分配，为此需要制定出收益最大的资源分配方案。这种问题原本要求一次确定出对各企业的资源分配量，它与时间因素无关，不属动态决策，而是属于静态决策问题，但是，我们可以人为地规定一个资源分配的阶段和顺序， 从而使其变成一个多阶段决策问题。 运 输 网 络 问 题在运输网络中，点与点之间连线

39、上的数字表示两地距离(也可是运费、时间等)，要求从一点 到另一点的最短路线。这种运输网络问题也是静态决策问题。但是， 按照网络中点的分布，可以把它分为若干个阶段， 而作为多阶段决策问题来研究。1、阶段：把一个问题的过程，恰当地分为若干个相互联系的阶段，以便于按一定的次序去求解。描述阶段的变量称为阶段变量。阶段的划分,一般是根据时间和空间的自然特征来进行的，但要年,月, 路段便于问题转化为多阶段决策。2、状态：表示每个阶段开始所处的自然状况或客观条件。通常一个阶段有若干个状态，描述一个数、一组数、过程状态的变量称为状态变量。一个向量状态变量的取值有一定的允许集合或范围，此集合称为状态允许集合。3

40、、决策：表示当过程处于某一阶段的某个状态时，可以作出不同的决定，从而确定下一阶段的状态，这种决定称为决策。描述决策的变量，称为决策变量。决策变量是状在实际问题中决策变量的取值往往在某一范围之内，此范围称为允许决策集合。4、多阶段决策过程可以在各个阶段进行决策，控制过程发展的多段过程；其发展是通过一系列的状态转移来实现；系统在某一阶段的状态转移不但与系统的当前的状态和决策有关，而且还与系统过去的历史状态和决策有关。5、策略：是一个按顺序排列的决策组成的集合。在实际问题中，可供选择的策略有一定的范围， 称为允许策略集合。从允许策略集合中找出达到最优效果的策略称为最优策略。6、状态转移方程：是确定过

41、程由一个状态到另一个状态的演变过程，描述了状态转移规律。7、指标函数和最优值函数：用来衡量所实现过程优劣的一种数量指标，为指标函数。指标函数的最优值，称为最优值函数。在不同的问题中，指标函数的含义是不同的，它可能是距离、利润、成本、产量或资源消耗等。动态规划模型的指标函数，应具有可分离性， 并满足递推关系。 引例：最短路问题及其解法在下面网络图中，其中圆圈称为点，两点之间的连线称为弧，弧上的数字称为弧长。6C11D1B1833536C25A82D2E337C3B23268D34C41、提出问题求一条从起点A到终点E的连通弧，使其总弧长最短最短路问题。2、意义说明最短路问题的含义是很广泛的，如点

42、代表加油站，弧代表管道，弧长代表铺设管道的费用。问题就变成让我们设计一条从起点A到终点E的管道，使其总费用最少。3、问题特点1）从A到E整个过程可分为从A到B（B有二种选择B1,B2）从B到C（C有四种选择C1，C2，C3，C4），从C到D（D有三种选择D1，D2，D3）在从D到E四个阶段，是一个多x阶段决策问题。2）每个阶段都有起点，用k表示第K阶段的起点，并称为状态变量：每个阶段都有终点，前一段的终点就是后一段的起点。3）从每个起点出发（状态出发），都有若干选择（例如从B1出发有三种选择），用uk表示从第K阶段的状x态k出发所作的选择并成为决策变量。决策变量全体成为决策集合（允许决策集合）

43、，即为Dk( xk )表示从第K阶段的状态 xk出发到4）如果用 fk终点的最短弧长，或者用f( x)表示从起点到第Kkk阶段的状态xk的最短弧长，则问题就变成求f1 (x1 )(=f1 ( A), 或者求出f5 (x5 )(=f5 (E)。4、问题求解1）顺序解法：从前逐步求出从起点A到各阶段起点的最短弧长及其对应的路径。最后求出f5 (x5 ) =f5 (E)用顺序解法：求 f5 (x5 )f1 (x1 ) =f1 ( A) = 0k = 1k = 2, f2 (B1) = 5, f2 (B2 ) = 3k = 3, f3 (C1 ) = d (B1,C1 ) +f2 (B1 ) = 1+

44、 5 = 6d (B ,C) + f(B )5 + 3f(C ) = min1221= 8mind (B ,C) + f(B )328 + 32222d(B ,C ) +6 + 5f(B )f (C ) = min1321=10min33d(B2 ,C3 ) + f2 (B2 )7 + 3f3 (C4 ) = d (B2 ,C4 ) + f2 (B2 ) = 6 + 3 = 9k = 4,d (C , D ) + f(C )6 + 61131f(D ) = min= min= 11d (C , D ) + f(C)8 + 3 412213d (C2 , D2 ) + f3 (C1 ) 8 + 6d (C , D ) + f(C)8 + 5f(D ) = min = min = 132232d (C , D ) + f(C ) 3 +10423233d (C4 , D2 ) +