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

数学建模第五章数学规划模型第1页，共117页，2023年，2月20日，星期六第五章数学规划模型

黑龙江科技学院

数学建模理学院第2页，共117页，2023年，2月20日，星期六第五章数学规划模型数学规划论起始20世纪30年代末，50年代与60年代发展成为一个完整的分支并受到数学界和社会各界的重视。七八十年代是数学规划飞速发展时期，无论是从理论上还是算法方面都得到了进一步完善。时至今日数学规划仍然是运筹学领域中热点研究问题。从国内外的数学建模竞赛的试题中看，有近1/4的问题可用数学规划进行求解。

黑龙江科技学院

数学建模理学院第3页，共117页，2023年，2月20日，星期六动态规划模型数学规划模型第五章非线性规划模型重点:数学规划模型的建立和求解难点:数学规划模型的基本原理及数值计算线性规划模型

黑龙江科技学院

数学建模理学院建模举例多目标规划模型

整数规划模型

第4页，共117页，2023年，2月20日，星期六1、例1：某机床厂生产甲、乙两种机床，每台销售后的利润分别为4000元与3000元。生产甲机床需用A，B机器加工，加工时间分别为每台2小时和1小时；生产乙机床需用A，B，C三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为A机器10小时、B机器8小时和C机器7小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？

黑龙江科技学院

数学建模理学院第5页，共117页，2023年，2月20日，星期六设该厂生产x1台甲机床和x2台乙机床时总利润最大，则x1,x2应满足:目标函数:约束条件:

黑龙江科技学院

数学建模理学院第6页，共117页，2023年，2月20日，星期六一般线性规划问题的标准型为线性规划的Matlab标准形式

黑龙江科技学院

数学建模理学院第7页，共117页，2023年，2月20日，星期六线性规划模型矩阵的形式：例如线性规划Matlab标准型为

黑龙江科技学院

数学建模理学院第8页，共117页，2023年，2月20日，星期六4、线性规划的图解法本例的最优解为最优目标值

黑龙江科技学院

数学建模理学院第9页，共117页，2023年，2月20日，星期六5、求解线性规划的Matlab解法单纯形法是首先由GeorgeDantzig于1947年提出的，近60年来，虽有许多变形体已被开发，但却保持着同样的基本观念。由于有如下结论：若线性规划问题有有限最优解，则一定有某个最优解是可行区域的一个极点。基于此，单纯形法的基本思路是：先找出可行域的一个极点，据一定规则判断其是否最优；若否，则转换到与之相邻的另一极点，并使目标函数值更优；如此下去，直到找到某一最优解为止。

黑龙江科技学院

数学建模理学院第10页，共117页，2023年，2月20日，星期六

Matlab2008b中线性规划的标准型为：基本函数形式为linprog(c,A,b)，它的返回值是向量的值。还有其它的一些函数调用形式（在Matlab指令窗运行helplinprog可以看到所有的函数调用形式），如：[x,fval]=linprog(c,A,b,Aeq,beq,LB,UB,X0,OPTIONS)这里fval返回目标函数的值，Aeq和beq对应等式约束，LB和UB分别是变量的下界和上界，是的初始值，OPTIONS是控制参数。

黑龙江科技学院

数学建模理学院第11页，共117页，2023年，2月20日，星期六例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文件存盘，并命名为example1.m。（iii）在Matlab指令窗运行example1即可得所求结果。

黑龙江科技学院

数学建模理学院第12页，共117页，2023年，2月20日，星期六例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))

黑龙江科技学院

数学建模理学院第13页，共117页，2023年，2月20日，星期六例5.15拟分配n人去干n项工作，每人干且仅干一项工作，若分配第i人去干第j项工作，需花费cij单位时间，问应如何分配工作才能使工人花费的总时间最少？引入变量xij，若分配i干j工作，则取xij=1，否则取xij=0。上述指派问题的数学模型为:

指派问题

黑龙江科技学院

数学建模理学院第14页，共117页，2023年，2月20日，星期六可行解既可以用一个矩阵(称为解矩阵)表示，其每行每列均有且只有一个元素为1，其余元素均为0，也可以用1,…,n中的一个置换表示。求解指派问题的匈牙利算法

由于指派问题的特殊性，又存在着由匈牙利数学家D.Konig提出的更为简便的解法—匈牙利算法。算法主要依据以下事实：如果系数矩阵C=cij一行（或一列）中每一元素都加上或减去同一个数，得到一个新矩阵B=bij，则以C或B为系数矩阵的指派问题具有相同的最优指派。

黑龙江科技学院

数学建模理学院第15页，共117页，2023年，2月20日，星期六可将原系数阵C变换为含零元素较多的新系数阵B，而最优解不变。若能在B中找出n个位于不同行不同列的零元素，令解矩阵中相应位置的元素取值为1，其它元素取值为0，则所得该解是以B为系数阵的指派问题的最优解，从而也是原问题的最优解。由C到B的转换可通过先让矩阵C的每行元素均减去其所在行的最小元素得矩阵D，D的每列元素再减去其所在列的最小元素得以实现。

黑龙江科技学院

数学建模理学院第16页，共117页，2023年，2月20日，星期六例5.1.6求解指派问题，其系数矩阵为

将第一行元素减去此行中的最小元素15，同样，第二行元素减去17，第三行元素减去17，最后一行的元素减去16，得

黑龙江科技学院

数学建模理学院第17页，共117页，2023年，2月20日，星期六再将第3列元素各减去1，得以B2为系数矩阵的指派问题有最优指派即

黑龙江科技学院

数学建模理学院第18页，共117页，2023年，2月20日，星期六例5.1.7求解系数矩阵C的指派问题解先作等价变换如下

黑龙江科技学院

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

黑龙江科技学院

数学建模理学院第20页，共117页，2023年，2月20日，星期六上述过程可反复采用，直到能选取出足够的0元素为止。例如，对例5.1.7变换后的矩阵再变换，第三行、第五行元素减去2，第一列元素加上2，得最优指派为

黑龙江科技学院

数学建模理学院第21页，共117页，2023年，2月20日，星期六建模举例：营养配餐问题

每种蔬菜含有的营养素成份是不同的，从医学上知道，每人每周对每种营养成分的最低需求量。某医院营养室在制定下一周菜单时，需要确定表2-4中所列六种蔬菜的供应量，以便使费用最小而又能满足营养素等其它方面的要求。规定白菜的供应一周内不多于20千克，其它蔬菜的供应在一周内不多于40千克，每周共需供应140千克蔬菜，为了使费用最小又满足营养素等其它方面的要求，问在下一周内应当供应每种蔬菜各多少千克？

黑龙江科技学院

数学建模理学院第22页，共117页，2023年，2月20日，星期六表5-4

黑龙江科技学院

数学建模理学院第23页，共117页，2023年，2月20日，星期六问题分析设分别表示下一周内应当供应的青豆、胡萝卜、菜花、白菜、甜菜及土豆的量，费用目标函数为：约束条件：铁的需求量至少6个单位数：磷的需求量至少25个单位数：

黑龙江科技学院

数学建模理学院第24页，共117页，2023年，2月20日，星期六问题分析维生素A的需求量至少17500个单位：维生素C的需求量至少245个单位：烟酸的需求量至少5个单位数：每周需供应140千克蔬菜，即

黑龙江科技学院

数学建模理学院第25页，共117页，2023年，2月20日，星期六模型的建立0≤x1≤400≤x2≤400≤x3≤400≤x4≤200≤x5≤400≤x6≤40

黑龙江科技学院

数学建模理学院第26页，共117页，2023年，2月20日，星期六模型求解利用Matlab软件编程序：%营养配餐ch21

%文件名：ch21m

c=[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=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);

黑龙江科技学院

数学建模理学院第27页，共117页，2023年，2月20日，星期六模型求解执行输出disp('青豆需要的份数')

x(1)disp('胡罗卜需要的份数')x(2)disp('菜花需要的份数')x(3)disp('白菜需要的份数')x(4)disp('甜菜需要的份数')x(5)disp('土豆需要的份数')x(6)

黑龙江科技学院

数学建模理学院第28页，共117页，2023年，2月20日，星期六执行输出模型求解青豆需要的份数ans=

40胡罗卜需要的份数ans=

40.0000菜花需要的份数ans=

0白菜需要的份数ans=

20.0000

黑龙江科技学院

数学建模理学院第29页，共117页，2023年，2月20日，星期六甜菜需要的份数ans=

0土豆需要的份数ans=

40最小费用ans=

560.0000模型求解执行输出

黑龙江科技学院

数学建模理学院第30页，共117页，2023年，2月20日，星期六§5.2整数规划模型

黑龙江科技学院

数学建模有些LP往往要求全部或部分决策变量取非负整数值，如计件产品的生产计划、合理下料、设施的配备决策等，这样的LP称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。理学院第31页，共117页，2023年，2月20日，星期六1.整数规划的分类如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类：（i）变量全限制为整数时，称纯（完全）整数规划。（ii）变量部分限制为整数的，称混合整数规划。（iii）变量只能取0或1时，称之为0-1整数规划。2.整数规划特点（i）原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况：①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。②整数规划无可行解（ii）整数规划最优解不能按照实数最优解简单取整而获得。理学院第32页，共117页，2023年，2月20日，星期六分枝定界法

对有约束条件的最优化问题（其可行解为有限数）的可行解空间恰当地进行系统搜索，这就是分枝与定界内容。通常，把全部可行解空间反复地分割为越来越小的子集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为定界。在每次分枝后，凡是界限不优于已知可行解集目标值的那些子集不再进一步分枝，这样，许多子集可不予考虑，这称剪枝。这就是分枝定界法的主要思路。

黑龙江科技学院

数学建模理学院第33页，共117页，2023年，2月20日，星期六设有最大化的整数规划问题A，与它相应的线性规划为问题B，从解问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数Z*的上界，记作；而A的任意可行解的目标函数值将是Z*的一个下界Z。分枝定界法就是将B的可行域分成子区域再求其最大值的方法。逐步减小和增大Z，最终求到Z*。

黑龙江科技学院

数学建模理学院第34页，共117页，2023年，2月20日，星期六例5.2.3求解下述整数规划解（i）先不考虑整数限制，即解相应的线性规划，得最优解为：可见它不符合整数条件。这时Z是问题A的最优目标函数值Z*的上界，记作。而x1=0,x2=0显然是问题A的一个整数可行解，这时Z=0，是Z*的一个下界，记作，即0<Z*<356。s.t.第35页，共117页，2023年，2月20日，星期六因为x1,x2当前均为非整数，故不满足整数要求，任选一个进行分枝。设选x1进行分枝，把可行集分成2个子集：，因为4与5之间无整数，故这两个子集内的整数解必与原可行集合整数解一致。这一步称为分枝。这两个子集的规划及求解如下：问题B1：最优解为：s.t.第36页，共117页，2023年，2月20日，星期六问题B2最优解为：s.t.以此类推找出最优解。第37页，共117页，2023年，2月20日，星期六从以上解题过程可得用分枝定界法求解整数规划（最大化）问题的步骤为：开始，将要求解的整数规划问题称为问题A，将与它相应的线性规划问题称为问题B。（i）解问题B可能得到以下情况之一：（a）B没有可行解，这时A也没有可行解，则停止．（b）B有最优解，并符合问题A的整数条件，B的最优解即为A的最优解，则停止。（c）B有最优解，但不符合问题A的整数条件，记它的目标函数值为。第38页，共117页，2023年，2月20日，星期六（ii）用观察法找问题A的一个整数可行解，一般可取xj=0，j=1,…,n试探，求得其目标函数值，并记作Z。以Z*表示问题A的最优目标函数值；这时有进行迭代。第一步：分枝，在B的最优解中任选一个不符合整数条件的变量xj，其值为bj，以[bj]表示小于bj的最大整数。构造两个约束条件将这两个约束条件，分别加入问题B，求两个后继规划问题B1和B2。不考虑整数条件求解这两个后继问题。第39页，共117页，2023年，2月20日，星期六定界，以每个后继问题为一分枝标明求解的结果，与其它问题的解的结果中，找出最优目标函数值最大者作为新的上界。从已符合整数条件的各分支中，找出目标函数值为最大者作为新的下界Z，若无作用Z=0。第二步：比较与剪枝，各分枝的最优目标函数中若有小于Z者，则剪掉这枝，即以后不再考虑了。若大于Z，且不符合整数条件，则重复第一步骤。一直到最后得到Z*=Z为止。得最优整数解xj*,j=1,…,n.

黑龙江科技学院

数学建模第40页，共117页，2023年，2月20日，星期六0-1型整数规划

0-1型整数规划是整数规划中的特殊情形，它的变量xj仅取值0或1。这时称为0-1变量，或称二进制变量。xj仅取值0或1这个条件可由下述约束条件：整数所代替，是和一般整数规划的约束条件形式一致的。在实际问题中，如果引入0-1变量，就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中讨论了。我们先介绍引入0-1变量的实际问题，再研究解法。

黑龙江科技学院

数学建模第41页，共117页，2023年，2月20日，星期六例5.2.4某公司拟在市东、西、南三区建立门市部。拟议中有7个位置（点）Ai(i=1,2,…7)可供选择。规定在东区：由A1,A2,A3三个点中至多选两个；在西区：由A4,A5两个点中至少选一个；在南区：由A6,A7两个点中至少选一个。如选用Ai点，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不能超过B元。问应选择哪几个点可使年利润为最大？

黑龙江科技学院

数学建模第42页，共117页，2023年，2月20日，星期六解先引入0-1变量xi,i=1,2,…7令于是问题可列写成：

黑龙江科技学院

数学建模第43页，共117页，2023年，2月20日，星期六0-1型整数规划解法之一（过滤隐枚举法）

解0-1型整数规划最容易想到的方法，和一般整数规划的情形一样，就是穷举法，即检查变量取值为0或1的每一种组合，比较目标函数值以求得最优解，这就需要检查变量取值的2n个组合。对于变量个数n较大，这几乎是不可能的。因此常设计一些方法，只检查变量取值的组合的一部分，就能求到问题的最优解。这样的方法称为隐枚举法，分枝定界法也是一种隐枚举法。当然，对有些问题隐枚举法并不适用，所以有时穷举法还是必要的。

黑龙江科技学院

数学建模理学院第44页，共117页，2023年，2月20日，星期六例5.2.5

求解思路及改进措施：（i）先试探性求一个可行解，易看出(x1,x2,x3)=(1,0,0)满足约束条件，故为一个可行解，且相应的目标函数值为z=3。s.t.

黑龙江科技学院

数学建模理学院第45页，共117页，2023年，2月20日，星期六ii）因为是求极大值问题，故求最优解时，凡是目标值z<3的解不必检验是否满足约束条件即可删除，因它肯定不是最优解，于是应增加一个约束条件（目标值下界）：称该条件为过滤条件)。从而原问题等价于：abcdef

黑龙江科技学院

数学建模第46页，共117页，2023年，2月20日，星期六若用全部枚举法，3个变量共有8种可能的组合，我们将这8种组合依次检验它是否满足条件(a)—(e)，对某个组合，若它不满足(a)，即不满足过滤条件，则(b)—(e)即可行性条件不必再检验；若它满足(a)—(e)且相应的目标值严格大于3，则进行（iii）。（iii）改进过滤条件。（iv）由于对每个组合首先计算目标值以验证过滤条件，故应优先计算目标值大的组合，这样可提前抬高过滤门槛，以减少计算量。按上述思路与方法，例5.2.5的求解过程可由下表来表示：

黑龙江科技学院

数学建模第47页，共117页，2023年，2月20日，星期六(x1,x2,x3)目标值约束条件过滤条件abcde(0,0,0)0(1,0,0)3√√√√√(0,1,0)-2(0,0,1)5√√√√√(1,1,0)1(1,0,1)8√√√√√(1,1,1)6(0,1,1)3从而得最优解

最优值

黑龙江科技学院

数学建模第48页，共117页，2023年，2月20日，星期六整数规划的计算机解法

整数规划问题的求解可以使用Lingo等专用软件。对于一般的整数规划规划问题，无法直接利用Matlab的函数，必须利用Matlab编程实现分枝定界解法和割平面解法。但对于指派问题等特殊的0-1整数规划问题或约束矩阵A是幺模矩阵时，有时可以直接利用Matlab的函数linprog。

黑龙江科技学院

数学建模第49页，共117页，2023年，2月20日，星期六5.2.6求解下列指派问题，已知指派矩阵为

解编写Matlab程序如下：c=[382103;87297;6427584235;9106910];c=c(:);a=zeros(10,25);fori=1:5a(i,(i-1)*5+1:5*i)=1;a(5+i,i:5:25)=1;endb=ones(10,1);[x,y]=linprog(c,[],[],a,b,zeros(25,1),ones(25,1))求得最优指派方案为第50页，共117页，2023年，2月20日，星期六§5.3非线性规划如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非线性规划问题。一般说来，解非线性规划要比解线性规划问题困难得多。而且，也不象线性规划有单纯形法这一通用方法，非线性规划目前还没有适于各种问题的一般算法，各个方法都有自己特定的适用范围。第51页，共117页，2023年，2月20日，星期六例5.3.1（投资决策问题）某企业有个项目可供选择投资，并且至少要对其中一个项目投资。已知该企业拥有总资金元，投资于第个项目需花资金元，并预计可收益元。试选择最佳投资方案。解设投资决策变量为限制条件由于xi只取值0或1第52页，共117页，2023年，2月20日，星期六最佳投资方案应是投资额最小而总收益最大的方案，所以这个最佳投资决策问题归结为总资金以及决策变量（取0或1）的限制条件下，极大化总收益和总投资之比。因此，其数学模型为第53页，共117页，2023年，2月20日，星期六非线性规划问题一般形式：其中称为模型的决策变量，f称为目标函数，gi(x)和hi(x)称为约束函数。另外，gi(x)=0称为等式约束，hi(x)<0称为不等式约束第54页，共117页，2023年，2月20日，星期六非线性规划的Matlab解法Matlab中非线性规划的数学模型形式minf(x)其中是标量函数，是相应维数的矩阵和向量，是非线性向量函数。Matlab中的命令是X=FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON,OPTIONS)第55页，共117页，2023年，2月20日，星期六例5.3.1求下列非线性规划问题第56页，共117页，2023年，2月20日，星期六(1)编写M文件fun1.mfunctionf=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。第57页，共117页，2023年，2月20日，星期六课前讨论题：最短路径问题求从A点到B点的最短路径共有多少条？AB第58页，共117页，2023年，2月20日，星期六最优路线为：A→B1→C2→D1→E2→F2→GAB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643求从A点到G点的最短路径？第59页，共117页，2023年，2月20日，星期六第四节动态规划模型多阶段决策过程最优化动态规划基本概念动态规划的基本步骤动态规划的应用第60页，共117页，2023年，2月20日，星期六B1B2C1C2C3C4D1D2D3EA5313687668353384322引例导入：最短路问题及其解法在下面网络图中，其中圆圈称为点，两点之间的连线称为弧，弧上的数字称为弧长。第61页，共117页，2023年，2月20日，星期六多阶段决策过程最优化动态规划的研究对象是：多阶段决策问题一、多阶段决策问题多阶段决策问题：根据问题本身的特点，可以将其求解的全过程划分为若干个相互联系的阶段(即将问题划分为许多个相互联系的子问题)，在它的每一阶段都需要作出决策，并且在一个阶段的决策确定以后再转移到下一个阶段。第62页，共117页，2023年，2月20日，星期六多阶段决策过程前一个阶段的决策要影响到后一个阶段的决策，从而影响整个过程。各个阶段所确定的决策就构成了一个决策序列，称为一个策略。一般来说，由于每一阶段可供选择的决策往往不止一个，因此，对于整个过程，就会有许多可供选择的策略。最优策略若对应于一个策略，可以由一个量化的指标来确定这个策略所对应的活动过程的效果，那么不同的策略就有各自的效果。在所有可供选择的策略中，对应效果最好的策略称为最优策略。把一个问题划分成若干个相互联系的阶段选取其最优策略，这类问题就是多阶段决策问题。第63页，共117页，2023年，2月20日，星期六二、多阶段决策问题类型由于市场需求是一随着时间而变化的因素，因此，为了取得全年最佳经济效益，就要在全年的生产过程中，逐月或者逐季度地根据库存和需求情况决定生产计划安排。工厂生产过程设备更新问题一般企业用于生产活动的设备，刚买来时故障少，经济效益高，随着使用年限的增加，就会逐渐变为故障多，维修费用增加，可正常使用的工时减少，加工质量下降，经济效益差，并且，使用的年限越长、处理价值也越低，自然，如果卖去旧的买新的，还需要付出更新费．因此就需要综合权衡决定设备的使用年限，使总的经济效益最好。第64页，共117页，2023年，2月20日，星期六资源分配问题某工业部门或公司，拟对其所属企业进行稀缺资源分配，为此需要制定出收益最大的资源分配方案。这种问题原本要求一次确定出对各企业的资源分配量，它与时间因素无关，不属动态决策，而是属于静态决策问题，但是，我们可以人为地规定一个资源分配的阶段和顺序，从而使其变成一个多阶段决策问题。运输网络问题在运输网络中，点与点之间连线上的数字表示两地距离(也可是运费、时间等)，要求从一点到另一点的最短路线。这种运输网络问题也是静态决策问题。但是，按照网络中点的分布，可以把它分为若干个阶段，而作为多阶段决策问题来研究。第65页，共117页，2023年，2月20日，星期六1、阶段：

把一个问题的过程，恰当地分为若干个相互联系的阶段，以便于按一定的次序去求解。

描述阶段的变量称为阶段变量。阶段的划分,一般是根据时间和空间的自然特征来进行的，但要便于问题转化为多阶段决策。动态规划基本概念2、状态：表示每个阶段开始所处的自然状况或客观条件。通常一个阶段有若干个状态，描述过程状态的变量称为状态变量。状态变量的取值有一定的允许集合或范围，此集合称为状态允许集合。年,月,路段一个数、一组数、一个向量第66页，共117页，2023年，2月20日，星期六

3、决策：表示当过程处于某一阶段的某个状态时，可以作出不同的决定，从而确定下一阶段的状态，这种决定称为决策。

描述决策的变量，称为决策变量。决策变量是状态变量的函数。可用一个数、一组数或一向量（多维情形）来描述。在实际问题中决策变量的取值往往在某一范围之内，此范围称为允许决策集合。

系统在某一阶段的状态转移不但与系统的当前的状态和决策有关，而且还与系统过去的历史状态和决策有关。4、多阶段决策过程可以在各个阶段进行决策，控制过程发展的多段过程；其发展是通过一系列的状态转移来实现；第67页，共117页，2023年，2月20日，星期六5、策略：是一个按顺序排列的决策组成的集合。在实际问题中，可供选择的策略有一定的范围，称为允许策略集合。从允许策略集合中找出达到最优效果的策略称为最优策略。6、状态转移方程：是确定过程由一个状态到另一个状态的演变过程，描述了状态转移规律。7、指标函数和最优值函数：用来衡量所实现过程优劣的一种数量指标，为指标函数。指标函数的最优值，称为最优值函数。在不同的问题中，指标函数的含义是不同的，它可能是距离、利润、成本、产量或资源消耗等。动态规划模型的指标函数，应具有可分离性，并满足递推关系。第68页，共117页，2023年，2月20日，星期六B1B2C1C2C3C4D1D2D3EA5313687668353384322引例：最短路问题及其解法在下面网络图中，其中圆圈称为点，两点之间的连线称为弧，弧上的数字称为弧长。第69页，共117页，2023年，2月20日，星期六1、提出问题求一条从起点A到终点E的连通弧，使其总弧长最短—最短路问题。2、意义说明最短路问题的含义是很广泛的，如点代表加油站，弧代表管道，弧长代表铺设管道的费用。问题就变成让我们设计一条从起点A到终点E的管道，使其总费用最少。第70页，共117页，2023年，2月20日，星期六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阶段的状态出发所作的选择并成为决策变量。决策变量全体成为决策集合（允许决策集合），即为

第71页，共117页，2023年，2月20日，星期六4）如果用表示从第K阶段的状态出发到终点的最短弧长，或者用表示从起点到第K阶段的状态的最短弧长，则问题就变成求或者求出。4、问题求解1）顺序解法：从前逐步求出从起点A到各阶段起点的最短弧长及其对应的路径。最后求出用顺序解法：求第72页，共117页，2023年，2月20日，星期六第73页，共117页，2023年，2月20日，星期六第74页，共117页，2023年，2月20日，星期六递推公式所求的最短弧长路径决策其中第75页，共117页，2023年，2月20日，星期六2）逆序解法：从后向前逐步求出各阶段到终点E的最短路线与最短弧长，最后求出即从最后一个阶段K=4开始。用逆序解法：求

K=3,有4个状态，每个状态又有两个决策可选第76页，共117页，2023年，2月20日，星期六最短弧长9路径决策类似有K=2，有2个状态，每个状态又有3个决策可选第77页，共117页，2023年，2月20日，星期六路径和决策路径和决策或第78页，共117页，2023年，2月20日，星期六K=1路径决策A到E的最短弧长14归纳总结其中第79页，共117页，2023年，2月20日，星期六B1B2C1C2C3C4D1D2D3EA5313687668353384322第80页，共117页，2023年，2月20日，星期六练习、从A地到D地要铺设一条煤气管道,其中需经过两级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线,使总距离最短？AB1B2C1C2C3D24333321114第81页，共117页，2023年，2月20日，星期六解：整个计算过程分三个阶段，从最后一个阶段开始。

第三阶段（C→D）：C有三条路线到终点D。

AB1B2C1C2C3D24333321114DC1C2C3显然有

f3(C1)

=1；

f3(C2)

=3；

f3(C3)

=4

第四阶段

f4(D

)

=0；第82页，共117页，2023年，2月20日，星期六第二阶段（B→C）：B到C有六条路线。

d(B1,C1)+f3(C1)

3+1f2(B1)=mind(B1,C2

)+f3(C2)

=min3+3

d(B1,C3)+f3(C3)1+44=min6=45AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路线为B1→C1→D)第83页，共117页，2023年，2月20日，星期六

d(B2,C1)+f3(C1)

2+1f2(B2)=mind(B2,C2

)+f3(C2)

=min3+3

d(B2,C3)+f3(C3)1+43=min6=35AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路线为B2→C1→D)第84页，共117页，2023年，2月20日，星期六第三阶段（A→B）：A到B有二条路线。

f1(A)1=d(A,B1)＋f2(B1)＝2＋4＝6

f1(A)2=d(A,B2)＋f2(B2)＝4＋3＝7∴f1(A)

=min=min｛6,7}=6d(A,B1)＋f2(B1)d(A,B2)＋f2(B2)(最短路线为A→B1→C1→D)AB1B2C1C2C3D24333321114DC1C2C3B1B2A第85页，共117页，2023年，2月20日，星期六AB1B2C1C2C3D24333321114DC1C2C3B1B2A最短路线为：A→B1→C1→D最短路长为：6第86页，共117页，2023年，2月20日，星期六动态规划的基本步骤1、划分阶段划分阶段是运用动态规划求解多阶段决策问题的第一步，在确定多阶段特性后，按时间或空间先后顺序，将过程划分为若干相互联系的阶段。对于静态问题要人为地赋予“时间”概念，以便划分阶段。2、正确选择状态变量选择变量既要能确切描述过程演变又要满足无后效性，而且各阶段状态变量的取值能够确定。一般地，状态变量的选择是从过程演变的特点中寻找。3、确定决策变量及允许决策集合通常选择所求解问题的关键变量作为决策变量，同时要给出决策变量的取值范围，即确定允许决策集合。第87页，共117页，2023年，2月20日，星期六4、确定状态转移方程根据k阶段状态变量和决策变量，写出k+1阶段状态变量，状态转移方程应当具有递推关系。5、确定阶段指标函数和最优指标函数，建立动态规划基本方程。

阶段指标函数是指第k阶段的收益，最优指标函数是指从第k阶段状态出发到第n阶段末所获得收益的最优值，最后写出动态规划基本方程。以上五步是建立动态规划数学模型的一般步骤。由于动态规划模型与线性规划模型不同，动态规划模型没有统一的模式，建模时必须根据具体问题具体分析，只有通过不断实践总结，才能较好掌握建模方法与技巧。

第88页，共117页，2023年，2月20日，星期六动态规划的应用例生产与存储问题假设某车间每月底都要供应总装车间一定数量的部件，由于生产条件的变化，该车间每月生产单位部件所耗费的工时不同；每月的生产量除供本月需要外，剩余部分的存入仓库备用。今已知半年内各月份的需求量及生产该部件每单位数所需工时数（如表2-7所示）设库存容量H=9,开始时量为2,期终库存量为0。月份k0123456月需求量单位工时0853274111813172010要求制定一个半年生产计划，使得既满足需要和库存容量的限制，又使总耗费工时数最少。第89页，共117页，2023年，2月20日，星期六②状态变量—第K月的部件库存量（上月产品送入后，本月需求量送出前）。③决策变量—表示第K月生产的部件数量。这是一个多阶段决策问题，采用逆序解法。问题分析与符号说明①按月份划分阶段，即阶段变量为k=0,1,2,…,6.④状态转移方程为第90页，共117页，2023年，2月20日，星期六⑥最优函数表示在状态之下，从第K月到6月末，生产部件的最小累计工时数。边界条件为。⑤阶段指标

指标函数

动态规划模型的建立第91页，共117页，2023年，2月20日，星期六模型求解K=6，因为期终库存量为0，故，从而可知，而，故由状态转移方程知，从而K=5，第92页，共117页，2023年，2月20日，星期六K=4类似地求第93页，共117页，2023年，2月20日，星期六最后再求最优策略所以逐用生产计划为7，4，9，3，0，4。第94页，共117页，2023年，2月20日，星期六例2.12机器设备管理问题。设有数量为的某种机器，可在高低两种负荷下进行生产。假设在高负荷下生产时，产品的年产量和投入生产的机器数量y的关系为，机器的完好率为a（0<a<1）,在低负荷下进行生产时，产品的年产量和投入生产的机器数量Z的关系为机器的完好率为b(0<b<1)。

现在要求制定一个N年生产计划，在每年开始时，如何重新分配完好的机器在两种负荷下工作的数量，才能使N年内的总生产量最高.第95页，共117页，2023年，2月20日，星期六状态转移方程：状态变量:第K年度初具有的完好机器数量决策变量:第K年度分配高负荷生产的机器数：第K年度分配高负荷生产的机器数一个典型多阶段决策问题，阶段数K表示年度。问题分析与符号说明阶段效益函数：第96页，共117页，2023年，2月20日，星期六若用表示从状态出发，采用最优策略，到第N年结束时的最高生产量，则根据最优化原理，得动态规划模型：当，N，a，b，g，h都给定以后，借此动态规划模型即可获得问题的答案。动态规划模型的建立第97页，共117页，2023年，2月20日，星期六模型求解由于线性单调递增函数，故当时取最大值故。K=5K=4第98页，共117页，2023年，2月20日，星期六K=3K=2第99页，共117页，2023年，2月20日，星期六K=1最优策略为，即头两年把年初的完好机器全部投入低负荷生产，后三年则全部投入高负荷生产。这时最高产量为。利用状态转移方程可以求出每年初尚有的完好机器数量为:第100页，共117页，2023年，2月20日，星期六通过问题讨论，始终状态台是给定的，但终端状态没有限制，这样是砸锅卖铁的“破坏式”生产，对在生产不利，因此通常对终端状态是有要求的。例如，规定台，即5年后尚需保存完好机器500台。问这时如何安排生产，才能在满足这一要求得条件下产量最高?由状态转移方程可得第101页，共117页，2023年，2月20日，星期六说明第5年度的决策变量已不能取其他值，故：第102页，共117页，2023年，2月20日，星期六类似地可得在利用状态转移方程求出每年年初尚有完好机器的数量为：第103页，共117页，2023年，2月20日，星期六由此得：即头4年把好机器全部投入低负荷生产，第5年将452台好机器投入高负荷生产，其余656-452=204台好机器投入低负荷生产，最高产量为这时产量较自由终端是低。第104页，共117页，2023年，2月20日，星期六多目标规划模型多目标规划模型的一般形式为若模型可简记为第105页，共117页，2023年，2月20日，星期六5.5.3多目标规划问题