数学建模第五章数学规划模型.ppt

《数学建模第五章数学规划模型.ppt》由会员分享，可在线阅读，更多相关《数学建模第五章数学规划模型.ppt（117页珍藏版）》请在三一办公上搜索。

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应满足:目标函数:约束条件:,理学院,一般线性规划问题的标准型为,线性规划的Matlab标准形式,理学院,线性规划模型矩阵的形式：例如线性规划 Matlab标准型为,理学

3、院,4、线性规划的图解法,本例的最优解为 最优目标值,理学院,5、求解线性规划的Matlab解法 单纯形法是首先由George Dantzig于1947年提出的，近60年来，虽有许多变形体已被开发，但却保持着同样的基本观念。由于有如下结论：若线性规划问题有有限最优解，则一定有某个最优解是可行区域的一个极点。基于此，单纯形法的基本思路是：先找出可行域的一个极点，据一定规则判断其是否最优；若否，则转换到与之相邻的另一极点，并使目标函数值更优；如此下去，直到找到某一最优解为止。,理学院,Matlab2008b中线性规划的标准型为：基本函数形式为linprog(c,A,b)，它的返回值是向量的值。还有

4、其它的一些函数调用形式（在 Matlab 指令窗运行 help linprog 可以看到所有的函数调用形式），如：x,fval=linprog(c,A,b,Aeq,beq,LB,UB,X0,OPTIONS)这里fval返回目标函数的值，Aeq和beq对应等式约束，LB和UB分别是变量的下界和上界，是的初始值，OPTIONS是控制参数。,理学院,例5.1.2 求解下列线性规划问题,解（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文件存盘，并命名为

5、example1.m。（iii）在Matlab指令窗运行example1即可得所求结果。,理学院,例5.1.3 求解线性规划问题,解 编写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。上述指派问题的数学模型为:,指派问题,理学院,可行解既可以用一个矩阵(称为解矩阵)表示，其每行每

6、列均有且只有一个元素为1，其余元素均为0，也可以用1,n中的一个置换表示。求解指派问题的匈牙利算法 由于指派问题的特殊性，又存在着由匈牙利数学家D.Konig提出的更为简便的解法匈牙利算法。算法主要依据以下事实：如果系数矩阵C=cij一行（或一列）中每一元素都加上或减去同一个数，得到一个新矩阵B=bij，则以C或B为系数矩阵的指派问题具有相同的最优指派。,理学院,可将原系数阵C变换为含零元素较多的新系数阵B，而最优解不变。若能在B中找出n个位于不同行不同列的零元素，令解矩阵中相应位置的元素取值为1，其它元素取值为0，则所得该解是以B为系数阵的指派问题的最优解，从而也是原问题的最优解。由C到B的

7、转换可通过先让矩阵C的每行元素均减去其所在行的最小元素得矩阵D，D的每列元素再减去其所在列的最小元素得以实现。,理学院,例 求解指派问题，其系数矩阵为,将第一行元素减去此行中的最小元素15，同样，第二行元素减去17，第三行元素减去17，最后一行的元素减去16，得,理学院,再将第3列元素各减去1，得 以B2为系数矩阵的指派问题有最优指派,即,理学院,例5.1.7 求解系数矩阵C的指派问题解 先作等价变换如下,理学院,容易看出，从变换后的矩阵中只能选出四个位于不同行不同列的零元素，但n=5，最优指派还无法看出。此时等价变换还可进行下去。步骤如下：（1）对未选出0元素的行打；（2）对行中0元素所在列

8、打；（3）对列中选中的0元素所在行打；重复（2）、（3）直到无法再打为止。可以证明，若用直线划没有打的行与打的列，就得到了能够覆盖住矩阵中所有零元素的最少条数的直线集合，找出未覆盖的元素中的最小者，令行元素减去此数，列元素加上此数，则原先选中的0元素不变，而未覆盖元素中至少有一个已转变为0，且新矩阵的指派问题与原问题也等价。,理学院,上述过程可反复采用，直到能选取出足够的0元素为止。例如，对例变换后的矩阵再变换，第三行、第五行元素减去2，第一列元素加上2，得 最优指派为,理学院,建模举例：营养配餐问题,每种蔬菜含有的营养素成份是不同的，从医学上知道，每人每周对每种营养成分的最低需求量。某医院营

9、养室在制定下一周菜单时，需要确定表2-4中所列六种蔬菜的供应量，以便使费用最小而又能满足营养素等其它方面的要求。规定白菜的供应一周内不多于20千克，其它蔬菜的供应在一周内不多于40千克，每周共需供应140千克蔬菜，为了使费用最小又满足营养素等其它方面的要求，问在下一周内应当供应每种蔬菜各多少千克？,理学院,表5-4,理学院,问题分析,设 分别表示下一周内应当供应的青豆、胡萝卜、菜花、白菜、甜菜及土豆的量，费用目标函数为：,约束条件：,铁的需求量至少6个单位数：,磷的需求量至少25个单位数：,理学院,问题分析,维生素A的需求量至少17500个单位：,维生素C的需求量至少245个单位：,烟酸的需求

10、量至少5个单位数：,每周需供应140千克蔬菜，即,理学院,模型的建立,0 x140 0 x240 0 x3400 x420 0 x540 0 x640,理学院,模型求解,利用Matlab软件编程序：%营养配餐ch21%文件名：ch21 mc=5;5;8;2;6;3;A=(-1)*1,1,1,1,1,1;0.45,0.45,1.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=

11、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(白菜需要的份数)x(4)disp(甜菜需要的份数)x(5)disp(土豆需要的份数)x(6),理学院,执行输出,模型求解,青豆需要的份数ans=40胡罗卜需要的份数 ans=40.0000菜花需要的份数 ans=0白菜需要的份数 ans=20.0000,理学院,甜菜需要的份数 ans=0土豆需

12、要的份数ans=40最小费用 ans=560.0000,模型求解,执行输出,理学院,5.2 整数规划模型,有些LP往往要求全部或部分决策变量取非负整数值，如计件产品的生产计划、合理下料、设施的配备决策等，这样的LP称为整数线性规划。,目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。,理学院,1.整数规划的分类如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类：（i）变量全限制为整数时，称纯（完全）整数规划。（ii）变量部分限制为整数的，称混合整数规划。（iii）变量只能取0或1时，称之为0-1整数规划。2.整数规划特点（

13、i）原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况：原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。整数规划无可行解（ii）整数规划最优解不能按照实数最优解简单取整而获得。,理学院,分枝定界法,对有约束条件的最优化问题（其可行解为有限数）的可行解空间恰当地进行系统搜索，这就是分枝与定界内容。通常，把全部可行解空间反复地分割为越来越小的子集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为定界。在每次分枝后，凡是界限不优于已知可行解集目标值的那些子集不再进一步分枝，这样，许多子集可不予考虑，这称剪枝。这就是分枝定界法的主要思路。,理学

14、院,设有最大化的整数规划问题A，与它相应的线性规划为问题B，从解问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数Z*的上界，记作；而A的任意可行解的目标函数值将是Z*的一个下界Z。分枝定界法就是将B的可行域分成子区域再求其最大值的方法。逐步减小 和增大Z，最终求到Z*。,理学院,例 求解下述整数规划 解（i）先不考虑整数限制，即解相应的线性规划，得最优解为：可见它不符合整数条件。这时Z是问题A的最优目标函数值Z*的上界，记作。而x1=0,x2=0显然是问题A的一个整数可行解，这时Z=0，是Z*的一个下界，记作，即0Z*356。,s.t.,因为x1,x2当前均为

15、非整数，故不满足整数要求，任选一个进行分枝。设选x1进行分枝，把可行集分成2个子集：，因为4与5之间无整数，故这两个子集内的整数解必与原可行集合整数解一致。这一步称为分枝。这两个子集的规划及求解如下：问题B1：最优解为：,s.t.,问题B2最优解为：,s.t.,以此类推找出最优解。,从以上解题过程可得用分枝定界法求解整数规划（最大化）问题的步骤为：开始，将要求解的整数规划问题称为问题A，将与它相应的线性规划问题称为问题B。（i）解问题B可能得到以下情况之一：（a）B没有可行解，这时A也没有可行解，则停止（b）B有最优解，并符合问题A的整数条件，B的最优解即为A的最优解，则停止。（c）B有最优解

16、，但不符合问题A的整数条件，记它的目标函数值为。,（ii）用观察法找问题A的一个整数可行解，一般可取xj=0，j=1,n试探，求得其目标函数值，并记作Z。以Z*表示问题A的最优目标函数值；这时有 进行迭代。第一步：分枝，在B的最优解中任选一个不符合整数条件的变量xj，其值为bj，以bj表示小于bj的最大整数。构造两个约束条件 将这两个约束条件，分别加入问题B，求两个后继规划问题B1和B2。不考虑整数条件求解这两个后继问题。,定界，以每个后继问题为一分枝标明求解的结果，与其它问题的解的结果中，找出最优目标函数值最大者作为新的上界。从已符合整数条件的各分支中，找出目标函数值为最大者作为新的下界Z，

17、若无作用Z=0。第二步：比较与剪枝，各分枝的最优目标函数中若有小于Z者，则剪掉这枝，即以后不再考虑了。若大于Z，且不符合整数条件，则重复第一步骤。一直到最后得到Z*=Z为止。得最优整数解 xj*,j=1,n.,0-1型整数规划 0-1型整数规划是整数规划中的特殊情形，它的变量xj仅取值0或1。这时称为0-1变量，或称二进制变量。xj仅取值0或1这个条件可由下述约束条件：整数所代替，是和一般整数规划的约束条件形式一致的。在实际问题中，如果引入0-1变量，就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中讨论了。我们先介绍引入0-1变量的实际问题，再研究解法。,例5.2.4 某公司拟在市

18、东、西、南三区建立门市部。拟议中有7个位置（点）Ai(i=1,2,7)可供选择。规定在东区：由A1,A2,A3三个点中至多选两个；在西区：由A4,A5两个点中至少选一个；在南区：由A6,A7两个点中至少选一个。如选用Ai点，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不能超过B元。问应选择哪几个点可使年利润为最大？,解 先引入0-1变量xi,i=1,2,7令于是问题可列写成：,0-1型整数规划解法之一（过滤隐枚举法）解0-1型整数规划最容易想到的方法，和一般整数规划的情形一样，就是穷举法，即检查变量取值为0或1的每一种组合，比较目标函数值以求得最优解，这就需要检查变量取值的2n个

19、组合。对于变量个数n较大，这几乎是不可能的。因此常设计一些方法，只检查变量取值的组合的一部分，就能求到问题的最优解。这样的方法称为隐枚举法，分枝定界法也是一种隐枚举法。当然，对有些问题隐枚举法并不适用，所以有时穷举法还是必要的。,理学院,例 求解思路及改进措施：（i）先试探性求一个可行解，易看出(x1,x2,x3)=(1,0,0)满足约束条件，故为一个可行解，且相应的目标函数值为z=3。,s.t.,理学院,ii）因为是求极大值问题，故求最优解时，凡是目标值z3的解不必检验是否满足约束条件即可删除，因它肯定不是最优解，于是应增加一个约束条件（目标值下界）：称该条件为过滤条件)。从而原问题等价于：

20、,a,b,c,d,e,f,若用全部枚举法，3个变量共有8种可能的组合，我们将这8种组合依次检验它是否满足条件(a)(e)，对某个组合，若它不满足(a)，即不满足过滤条件，则(b)(e)即可行性条件不必再检验；若它满足(a)(e)且相应的目标值严格大于3，则进行（iii）。（iii）改进过滤条件。（iv）由于对每个组合首先计算目标值以验证过滤条件，故应优先计算目标值大的组合，这样可提前抬高过滤门槛，以减少计算量。按上述思路与方法，例的求解过程可由下表来表示：,从而得最优解,最优值,整数规划的计算机解法,整数规划问题的求解可以使用Lingo等专用软件。对于一般的整数规划规划问题，无法直接利用Mat

21、lab的函数，必须利用Matlab编程实现分枝定界解法和割平面解法。但对于指派问题等特殊的0-1整数规划问题或约束矩阵A是幺模矩阵时，有时可以直接利用Matlab的函数linprog。,求解下列指派问题，已知指派矩阵为,解 编写Matlab程序如下：c=3 8 2 10 3;8 7 2 9 7;6 4 2 7 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;a(5+i,i:5:25)=1;end b=ones(10,1);x,y=linprog(c,a,b,zeros(25,1),ones(

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

23、及决策变量（取0或1）的限制条件下，极大化总收益和总投资之比。因此，其数学模型为,非线性规划问题一般形式：,其中 称为模型的决策变量，f称为目标函数，gi(x)和 hi(x)称为约束函数。另外，gi(x)=0 称为等式约束，hi(x)0 称为不等式约束,非线性规划的Matlab解法,Matlab中非线性规划的数学模型形式,minf(x),其中是标量函数，是相应维数的矩阵和向量，是非线性向量函数。Matlab中的命令是X=FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON,OPTIONS),例 求下列非线性规划问题,(1)编写M文件fun1.mfunction f=

24、fun1(x);f=x(1)2+x(2)2+8;和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点的最短路径共有多少条？,A,B,最优路线为：A B1 C2 D1 E2 F2 G,求从A点到G点的最短路径？,第四节 动态规划模型,多阶段决策过程最优化,动态

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

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

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

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

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

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

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

32、段的状态 出发到终点的最短弧长，或者用 表示从起点到第K阶段的状态 的最短弧长，则问题就变成求 或者求出。,4、问题求解,1）顺序解法：从前逐步求出从起点A到各阶段起点的最短弧长及其对应的路径。最后求出,用顺序解法：求,递推公式,所求的最短弧长,路径,决策,其中,2）逆序解法：从后向前逐步求出各阶段到终点E的最短路线与最短弧长，最后求出即从最后一个阶段K=4开始。用逆序解法：求,K=3,有4个状态，每个状态又有两个决策可选,最短弧长,9,路径,决策,类似有,K=2，有2个状态，每个状态又有3个决策可选,路径和决策,路径和决策,或,K=1,路径,决策,A到E的最短弧长,14,归纳总结,其中,练习

33、、从A 地到D 地要铺设一条煤气管道,其中需经过两级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线,使总距离最短？,解：整个计算过程分三个阶段，从最后一个阶 段开始。,第三阶段（CD）：C 有三条路线到终点D。,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,D,C1,C2,C3,显然有 f3(C1)=1；f3(C2)=3；f3(C3)=4,第四阶段 f4(D)=0；,第二阶段（B C）：B 到C 有六条路线。,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,D,C1,C2,C3,B1,B2,(最短路线为

34、B1C1 D),A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,D,C1,C2,C3,B1,B2,(最短路线为B2C1 D),第三阶段（A B）：A 到B 有二条路线。,f1(A)1=d(A,B1)f2(B1)246 f1(A)2=d(A,B2)f2(B2)437,(最短路线为AB1C1 D),A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,D,C1,C2,C3,B1,B2,A,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,D,C1,C2,C3,B1,B2,A,最短路线为：AB1C1 D 最

35、短路长为：6,动态规划的基本步骤,1、划分阶段划分阶段是运用动态规划求解多阶段决策问题的第一步，在确定多阶段特性后，按时间或空间先后顺序，将过程划分为若干相互联系的阶段。对于静态问题要人为地赋予“时间”概念，以便划分阶段。,2、正确选择状态变量选择变量既要能确切描述过程演变又要满足无后效性，而且各阶段状态变量的取值能够确定。一般地，状态变量的选择是从过程演变的特点中寻找。,3、确定决策变量及允许决策集合通常选择所求解问题的关键变量作为决策变量，同时要给出决策变量的取值范围，即确定允许决策集合。,4、确定状态转移方程根据k 阶段状态变量和决策变量，写出k+1阶段状态变量，状态转移方程应当具有递推

36、关系。,5、确定阶段指标函数和最优指标函数，建立动态规划基本方程。阶段指标函数是指第k 阶段的收益，最优指标函数是指从第k 阶段状态出发到第n 阶段末所获得收益的最优值，最后写出动态规划基本方程。,以上五步是建立动态规划数学模型的一般步骤。由于动态规划模型与线性规划模型不同，动态规划模型没有统一的模式，建模时必须根据具体问题具体分析，只有通过不断实践总结，才能较好掌握建模方法与技巧。,动态规划的应用,例 生产与存储问题 假设某车间每月底都要供应总装车间一定数量的部件，由于生产条件的变化，该车间每月生产单位部件所耗费的工时不同；每月的生产量除供本月需要外，剩余部分的存入仓库备用。今已知半年内各月

37、份的需求量及生产该部件每单位数所需工时数（如表2-7所示）设库存容量H=9,开始时量为2,期终库存量为0。,要求制定一个半年生产计划，使得既满足需要和库存容量的限制，又使总耗费工时数最少。,状态变量 第K月的部件库存量（上月产品送入后，本月需求量送出前）。,决策变量 表示第K月生产的部件数量。,这是一个多阶段决策问题，采用逆序解法。,问题分析与符号说明,按月份划分阶段，即阶段变量为k=0,1,2,6.,状态转移方程为,最优函数 表示在状态 之下，从第K月到6月末，生产部件的最小累计工时数。边界条件为。,阶段指标,指标函数,动态规划模型的建立,模型求解,K=6，因为期终库存量为0，故，从而可知，

38、而，故由状态转移方程 知，从而,K=5，,K=4,类似地求,最后再求最优策略,所以逐用生产计划为7，4，9，3，0，4。,例2.12机器设备管理问题。设有数量为 的某种机器，可在高低两种负荷下进行生产。假设在高负荷下生产时，产品的年产量 和投入生产的机器数量y的关系为，机器的完好率为a（0a1）,在低负荷下进行生产时，产品的年产量 和投入生产的机器数量Z的关系为 机器的完好率为b(0b1)。现在要求制定一个N年生产计划，在每年开始时，如何重新分配完好的机器在两种负荷下工作的数量，才能使N年内的总生产量最高.,状态转移方程：,状态变量:第K年度初具有的完好机器数量,决策变量:第K年度分配高负荷生

39、产的机器数,：第K年度分配高负荷生产的机器数,一个典型多阶段决策问题，阶段数K表示年度。,问题分析与符号说明,阶段效益函数：,若用 表示从状态 出发，采用最优策略，到第N年结束时的最高生产量，则根据最优化原理，得动态规划模型：,当，N，a，b，g，h都给定以后，借此动态规划模型即可获得问题的答案。,动态规划模型的建立,模型求解,由于 线性单调递增函数，故当 时取最大值故。,K=5,K=4,K=3,K=2,K=1,最优策略为，即头两年把年初的完好机器全部投入低负荷生产，后三年则全部投入高负荷生产。这时最高产量为。,利用状态转移方程可以求出每年初尚有的完好机器数量为:,通过问题讨论，始终状态 台是

40、给定的，但终端状态 没有限制，这样是砸锅卖铁的“破坏式”生产，对在生产不利，因此通常对终端状态是有要求的。,例如，规定 台，即5年后尚需保存完好机器500台。问这时如何安排生产，才能在满足这一要求得条件下产量最高?,由状态转移方程可得,说明第5年度的决策变量已不能取其他值，故：,类似地可得,在利用状态转移方程求出每年年初尚有完好机器的数量为：,由此得：,即头4年把好机器全部投入低负荷生产，第5年将452台好机器投入高负荷生产，其余656-452=204台好机器投入低负荷生产，最高产量为,这时产量较自由终端是低。,多目标规划模型,多目标规划模型的一般形式为,若,模型可简记为,多目标规划问题的几种

41、解法,1 主要目标法,主要目标法的基本思想是：在多目标决策问题中，根据问题的实际情况，确定一个目标为主要目标，而把其余目标作为次要目标，并且根据决策者的经验，选取一定的界限值。这样就可以把次要目标也作为约束来处理，于是就将原多目标决策问题转化成一个在新约束下，求主要目标的单目标规划问题。,2 线性加权法,3极大极小法,4 理想点法,5.建模举例,投资收益和风险问题。市场上有n种资产（股票、债券、）Si供投资者选择，某公司有数额为M的一笔相当大的资金可用作一个时间的投资。公司财务分析人员对S种资产进行评估，估算在这一时期内购买Si有平均收益率为ri，并预测出购买Si的损失率为qi。考虑到投资越分

42、散，总的风险越小，公司确定，当用这笔资金购买若干种资产时，总体风险可用所投资的Si中的最大一个风险来度量.购买要付交易费，费率为pi,并且当购买额不超过ui给定值时，交易费按购买ui计算（不买当然无须付费）。另外，假定同期银行存款利率是r0，且既无交易费又无风险（r0=0.05）。,已知n=4时的相关数据如下：,试给该公司设计一种投资组合方案，即用给定的资金M，有选择地购买若干种资产或存银行生息，使净收益尽可能大，而总体风险尽可能小。,1 模型的假设及符号说明,1)模型的假设 在一个时期内所给出ri,qi,pi的保持不变。在一个时间内所购买的各种资产（如股票、证券等）不进行买卖交易，即在买入后

43、不再卖出。每种投资是否收益是相互独立的。在投资过程中，无论盈利与否必须先付交易费。,2)符号说明M（元）：公司现有投资总金额；Si(i=1n)：欲购买的第i种资产种类（其中i=0表示存入银行）；xi：公司购买Si金额；ri：公司购买Si的平均收益率；qi：公司购买Si的平均损失率；pi：公司购买Si超过ui时所付交易费率。,2 问题的分析,设购买Si的金额为xi，所付的交易费ci(xi),令 c0(x0)=0,因为投资额M相当大，所以总可以假定对每个Si的投资xiui，这时上式可简化为,对Si投资的净收益,对投资的风险,对投资所需资金,净收益总额,整体风险,资金约束,3 多目标规划数学模型,我

44、们的想法是净收益总额R(x)尽可能大，而整体风险Q(x)又尽可能小，则该问题的数学模型可归为多目标规划模型,模型属于多目标规划模型，为了对其求解，可把多目标规划转化为单目标规划,1)假定投资的平均风险水平q，则投资M的风险k=qM，若要求整体风险Q(x)限制在风险k以内，即Q(x)k则模型式可转化为,求模型式的最优解模型式可转化为如下线性规划：,下面针对n=4,M=1的情形，按原问题给定的数据模型为：,利用Mathematica求解以上模型的方法如下（以为例）：文件名：ch561.mk=0.005;f=0.005*x0+0.27*x1+0.19*x2+0.185*x3+0.185*x4;st=x0+1.01*x1+1.02*x2+1.045*x3+1.065*x4=1,0.025*x10.158192,x1-0.2,x2-0.333333,x3-0.0909091,x4-0.192308,当k=0.05时，易计算得,当时k=0.01时，易计算得,按模型得到一组结果,理学院,本章小结,