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

数学建模第五章数学规划模型第1页，共117页，编辑于2022年，星期六第五章第五章 数学规划模型数学规划模型 黑龙江科技学院 数数 学学 建建 模模 理学院理学院第2页，共117页，编辑于2022年，星期六第五章第五章 数学规划模型数学规划模型 数学规划论起始数学规划论起始20世纪世纪30年代末年代末，50年年代与代与60年代年代发展成为一个完整的分支并受发展成为一个完整的分支并受到数学界和社会各界的重视。到数学界和社会各界的重视。七八十年代七八十年代是是数学规划飞速发展时期，无论是从理论上还是数学规划飞速发展时期，无论是从理论上还是算法方面都得到了进一步完善。时至今日数学算法方面都得到了进一步完善。时至今日数学规划仍然是运筹学领域中热点研究问题。从国规划仍然是运筹学领域中热点研究问题。从国内外的数学建模竞赛的试题中看，有近内外的数学建模竞赛的试题中看，有近1/4的问的问题可用数学规划进行求解。题可用数学规划进行求解。黑龙江科技学院 数数 学学 建建 模模理学院理学院第3页，共117页，编辑于2022年，星期六动态规划模型动态规划模型数学规划模型数学规划模型第五章非线性规划模型非线性规划模型重点重点:数学规划模型的建立和求解数学规划模型的建立和求解难点难点:数学规划模型的基本原理及数值计算数学规划模型的基本原理及数值计算线性规划模型线性规划模型 黑龙江科技学院 数数 学学 建建 模模 理学院理学院建模举例建模举例多目标规划模型多目标规划模型 整数规划模型整数规划模型 第4页，共117页，编辑于2022年，星期六1、例、例1：某机床厂生产甲、乙两种机床，每台销售后某机床厂生产甲、乙两种机床，每台销售后的利润分别为的利润分别为4000元与元与3000元。生产甲机床元。生产甲机床需用需用A，B机器加工，加工时间分别为每台机器加工，加工时间分别为每台2小小时和时和1小时；生产乙机床需用小时；生产乙机床需用A，B，C三种机三种机器加工，加工时间为每台各一小时。若每天可器加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为用于加工的机器时数分别为A机器机器10小时、小时、B机器机器8小时和小时和C机器机器7小时，问该厂应生产甲、小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？乙机床各几台，才能使总利润最大？黑龙江科技学院 数数 学学 建建 模模理学院理学院第5页，共117页，编辑于2022年，星期六设该厂生产x1台甲机床和x2台乙机床时总利润最大，则x1,x2应满足:目标函数:约束条件:黑龙江科技学院 数数 学学 建建 模模理学院理学院第6页，共117页，编辑于2022年，星期六一般线性规划问题的标准型为线性规划的Matlab标准形式 黑龙江科技学院 数数 学学 建建 模模理学院理学院第7页，共117页，编辑于2022年，星期六线性规划模型矩阵的形式：例如线性规划 Matlab标准型为 黑龙江科技学院 数数 学学 建建 模模理学院理学院第8页，共117页，编辑于2022年，星期六4、线性规划的图解法本例的最优解为 最优目标值 黑龙江科技学院 数数 学学 建建 模模理学院理学院第9页，共117页，编辑于2022年，星期六5、求解线性规划的Matlab解法 单纯形法单纯形法是首先由George Dantzig于1947年提出的，近60年来，虽有许多变形体已被开发，但却保持着同样的基本观念。由于有如下结论结论：若线性规划问题有有限最优解，则一定有某个最优解是可行区域的一个极点。基于此，单纯形法的基本思路是基本思路是：先找出可行域的一个极点，据一定规则判断其是否最优；若否，则转换到与之相邻的另一极点，并使目标函数值更优；如此下去，直到找到某一最优解为止。黑龙江科技学院 数数 学学 建建 模模理学院理学院第10页，共117页，编辑于2022年，星期六 Matlab2008b中线性规划的标准型为：基本函数形式为linprog(c,A,b)，它的返回值是向量的值。还有其它的一些函数调用形式（在 Matlab 指令窗运行 help linprog 可以看到所有的函数调用形式），如：x,fval=linprog(c,A,b,Aeq,beq,LB,UB,X0,OPTIONS)这里fval返回目标函数的值，Aeq和beq对应等式约束，LB和UB分别是变量的下界和上界，是的初始值，OPTIONS是控制参数。黑龙江科技学院 数数 学学 建建 模模理学院理学院第11页，共117页，编辑于2022年，星期六例例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页，编辑于2022年，星期六例例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页，编辑于2022年，星期六例例5.15拟分配n人去干n项工作，每人干且仅干一项工作，若分配第i人去干第j项工作，需花费cij单位时间，问应如何分配工作才能使工人花费的总时间最少？引入变量xij，若分配i干j工作，则取xij=1，否则取xij=0。上述指派问题的数学模型为:指派问题指派问题 黑龙江科技学院 数数 学学 建建 模模理学院理学院第14页，共117页，编辑于2022年，星期六可行解既可以用一个矩阵(称为解矩阵)表示，其每行每列均有且只有一个元素为1，其余元素均为0，也可以用1,n中的一个置换表示。求解指派问题的匈牙利算法求解指派问题的匈牙利算法 由于指派问题的特殊性，又存在着由匈牙利数学家D.Konig提出的更为简便的解法匈牙利匈牙利算法算法。算法主要依据以下事实：如果系数矩阵C=cij一行（或一列）中每一元素都加上或减去同一个数，得到一个新矩阵B=bij，则以C或B为系数矩阵的指派问题具有相同的最优指派。黑龙江科技学院 数数 学学 建建 模模理学院理学院第15页，共117页，编辑于2022年，星期六可将原系数阵C变换为含零元素较多的新系数阵B，而最优解不变。若能在B中找出n个位于不同行不同列的零元素，令解矩阵中相应位置的元素取值为1，其它元素取值为0，则所得该解是以B为系数阵的指派问题的最优解，从而也是原问题的最优解。由C到B的转换可通过先让矩阵C的每行元素均减去其所在行的最小元素得矩阵D，D的每列元素再减去其所在列的最小元素得以实现。黑龙江科技学院 数数 学学 建建 模模理学院理学院第16页，共117页，编辑于2022年，星期六例例5.1.6 求解指派问题，其系数矩阵为 将第一行元素减去此行中的最小元素15，同样，第二行元素减去17，第三行元素减去17，最后一行的元素减去16，得 黑龙江科技学院 数数 学学 建建 模模理学院理学院第17页，共117页，编辑于2022年，星期六再将第3列元素各减去1，得 以B2为系数矩阵的指派问题有最优指派 即 黑龙江科技学院 数数 学学 建建 模模理学院理学院第18页，共117页，编辑于2022年，星期六例例5.1.7 求解系数矩阵求解系数矩阵C的指派问题的指派问题解解 先作等价变换如下先作等价变换如下 黑龙江科技学院 数数 学学 建建 模模理学院理学院第19页，共117页，编辑于2022年，星期六容易看出，从变换后的矩阵中只能选出四个位于不同行不同列的零元素，但n=5，最优指派还无法看出。此时等价变换还可进行下去。步骤如下：（1）对未选出0元素的行打；（2）对行中0元素所在列打；（3）对列中选中的0元素所在行打；重复（2）、（3）直到无法再打为止。可以证明，若用直线划没有打的行与打的列，就得到了能够覆盖住矩阵中所有零元素的最少条数的直线集合，找出未覆盖的元素中的最小者，令行元素减去此数，列元素加上此数，则原先选中的0元素不变，而未覆盖元素中至少有一个已转变为0，且新矩阵的指派问题与原问题也等价。黑龙江科技学院 数数 学学 建建 模模理学院理学院第20页，共117页，编辑于2022年，星期六上述过程可反复采用，直到能选取出足够的0元素为止。例如，对例5.1.7变换后的矩阵再变换，第三行、第五行元素减去2，第一列元素加上2，得 最优指派为 黑龙江科技学院 数数 学学 建建 模模理学院理学院第21页，共117页，编辑于2022年，星期六建模举例：营养配餐问题建模举例：营养配餐问题 每种蔬菜含有的营养素成份是不同的，从医学上知道，每种蔬菜含有的营养素成份是不同的，从医学上知道，每人每周对每种营养成分的最低需求量。某医院营养室每人每周对每种营养成分的最低需求量。某医院营养室在制定下一周菜单时，需要确定表在制定下一周菜单时，需要确定表2-42-4中所列六种蔬菜的中所列六种蔬菜的供应量，以便使费用最小而又能满足营养素等其它方面供应量，以便使费用最小而又能满足营养素等其它方面的要求。规定白菜的供应一周内不多于的要求。规定白菜的供应一周内不多于2020千克，其它蔬千克，其它蔬菜的供应在一周内不多于菜的供应在一周内不多于4040千克，每周共需供应千克，每周共需供应140140千克千克蔬菜，为了使费用最小又满足营养素等其它方面的要求，蔬菜，为了使费用最小又满足营养素等其它方面的要求，问在下一周内应当供应每种蔬菜各多少千克？问在下一周内应当供应每种蔬菜各多少千克？黑龙江科技学院 数数 学学 建建 模模理学院理学院第22页，共117页，编辑于2022年，星期六表表5-4 黑龙江科技学院 数数 学学 建建 模模理学院理学院第23页，共117页，编辑于2022年，星期六问题分析问题分析设设 分别表示下一周内应当供应的青分别表示下一周内应当供应的青豆、胡萝卜、菜花、白菜、甜菜及土豆的量，豆、胡萝卜、菜花、白菜、甜菜及土豆的量，费用费用目标函数目标函数为：为：约束条件：约束条件：铁的需求量至少铁的需求量至少6 6个单位数：个单位数：磷的需求量至少磷的需求量至少2525个单位数：个单位数：黑龙江科技学院 数数 学学 建建 模模理学院理学院第24页，共117页，编辑于2022年，星期六问题分析问题分析维生素维生素A A的需求量至少的需求量至少1750017500个单位：个单位：维生素维生素C C的需求量至少的需求量至少245245个单位：个单位：烟酸的需求量至少烟酸的需求量至少5 5个单位数：个单位数：每周需供应每周需供应140140千克蔬菜，即千克蔬菜，即 黑龙江科技学院 数数 学学 建建 模模理学院理学院第25页，共117页，编辑于2022年，星期六模型的建立模型的建立00 x x140 0140 0 x x240 0240 0 x x34034000 x x420 0420 0 x x540 0540 0 x x640640 黑龙江科技学院 数数 学学 建建 模模理学院理学院第26页，共117页，编辑于2022年，星期六模型求解模型求解利用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=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页，编辑于2022年，星期六模型求解模型求解执执行行输输出出disp(青豆需要的份数青豆需要的份数)x(1)disp(胡罗卜需要的份数胡罗卜需要的份数 )x(2)disp(菜花需要的份数菜花需要的份数 )x(3)disp(白菜需要的份数白菜需要的份数 )x(4)disp(甜菜需要的份数甜菜需要的份数 )x(5)disp(土豆需要的份数土豆需要的份数)x(6)黑龙江科技学院 数数 学学 建建 模模理学院理学院第28页，共117页，编辑于2022年，星期六执执行行输输出出模型求解模型求解青豆需要的份数青豆需要的份数ans=40胡罗卜需要的份数胡罗卜需要的份数 ans=40.0000菜花需要的份数菜花需要的份数 ans=0白菜需要的份数白菜需要的份数 ans=20.0000 黑龙江科技学院 数数 学学 建建 模模理学院理学院第29页，共117页，编辑于2022年，星期六甜菜需要的份数甜菜需要的份数 ans=0土豆需要的份数土豆需要的份数ans=40最小费用最小费用 ans=560.0000模型求解模型求解执执行行输输出出 黑龙江科技学院 数数 学学 建建 模模理学院理学院第30页，共117页，编辑于2022年，星期六5.2 整数规划模型 黑龙江科技学院 数数 学学 建建 模模有些LP往往要求全部或部分决策变量取非负整数值，如计件产品的生产计划、合理下料、设施的配备决策等，这样的LP称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。理学院理学院第31页，共117页，编辑于2022年，星期六1.整数规划的分类如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类：（i）变量全限制为整数时，称纯（完全）整数规划。（ii）变量部分限制为整数的，称混合整数规划。（iii）变量只能取0或1时，称之为0-1整数规划。2.整数规划特点（i）原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况：原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。整数规划无可行解（ii）整数规划最优解不能按照实数最优解简单取整而获得。理学院理学院第32页，共117页，编辑于2022年，星期六分枝定界法分枝定界法 对有约束条件的最优化问题（其可行解为有对有约束条件的最优化问题（其可行解为有限数）的可行解空间恰当地进行系统搜索，限数）的可行解空间恰当地进行系统搜索，这就是这就是分枝分枝与与定界定界内容。通常，把全部可行内容。通常，把全部可行解空间反复地分割为越来越小的子集，称为解空间反复地分割为越来越小的子集，称为分枝分枝；并且对每个子集内的解集计算一个目；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为标下界（对于最小值问题），这称为定界定界。在每次分枝后，凡是界限不优于已知可行解在每次分枝后，凡是界限不优于已知可行解集目标值的那些子集不再进一步分枝，这样集目标值的那些子集不再进一步分枝，这样，许多子集可不予考虑，这称，许多子集可不予考虑，这称剪枝剪枝。这就是。这就是分枝定界法的主要思路。分枝定界法的主要思路。黑龙江科技学院 数数 学学 建建 模模理学院理学院第33页，共117页，编辑于2022年，星期六设有最大化的整数规划问题A，与它相应的线性规划为问题B，从解问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数Z*的上界，记作 ；而A的任意可行解的目标函数值将是Z*的一个下界Z 。分枝定界法就是将B的可行域分成子区域再求其最大值的方法。逐步减小 和增大Z，最终求到Z*。黑龙江科技学院 数数 学学 建建 模模理学院理学院第34页，共117页，编辑于2022年，星期六例例5.2.3 求解下述整数规划 解解（i）先不考虑整数限制，即解相应的线性规划，得最优解为：可见它不符合整数条件。这时Z是问题A的最优目标函数值Z*的上界，记作 。而x1=0,x2=0显然是问题A的一个整数可行解，这时Z=0，是Z*的一个下界，记作，即0Z*356。s.t.第35页，共117页，编辑于2022年，星期六因为x1,x2当前均为非整数，故不满足整数要求，任选一个进行分枝。设选x1进行分枝，把可行集分成2个子集：，因为4与5之间无整数，故这两个子集内的整数解必与原可行集合整数解一致。这一步称为分枝。这两个子集的规划及求解如下：问题B1：最优解为：s.t.第36页，共117页，编辑于2022年，星期六问题B2最优解为：s.t.以此类推找出最优解。第37页，共117页，编辑于2022年，星期六从以上解题过程可得用分枝定界法求解整数规划（最大化）问题的步骤为：开始，将要求解的整数规划问题称为问题A，将与它相应的线性规划问题称为问题B。（i）解问题B可能得到以下情况之一：（a）B没有可行解，这时A也没有可行解，则停止 （b）B有最优解，并符合问题A的整数条件，B的最优解即为A的最优解，则停止。（c）B有最优解，但不符合问题A的整数条件，记它的目标函数值为 。第38页，共117页，编辑于2022年，星期六（ii）用观察法找问题A的一个整数可行解，一般可取xj=0，j=1,n试探，求得其目标函数值，并记作Z。以Z*表示问题A的最优目标函数值；这时有 进行迭代。第一步：分枝，在B的最优解中任选一个不符合整数条件的变量xj，其值为bj，以bj表示小于bj的最大整数。构造两个约束条件 将这两个约束条件，分别加入问题B，求两个后继规划问题B1和B2。不考虑整数条件求解这两个后继问题。第39页，共117页，编辑于2022年，星期六定界，以每个后继问题为一分枝标明求解的结果，与其它问题的解的结果中，找出最优目标函数值最大者作为新的上界 。从已符合整数条件的各分支中，找出目标函数值为最大者作为新的下界Z，若无作用Z=0。第二步：比较与剪枝，各分枝的最优目标函数中若有小于Z者，则剪掉这枝，即以后不再考虑了。若大于Z，且不符合整数条件，则重复第一步骤。一直到最后得到Z*=Z为止。得最优整数解 xj*,j=1,n.黑龙江科技学院 数数 学学 建建 模模第40页，共117页，编辑于2022年，星期六0-1型整数规划型整数规划 0-1型整数规划是整数规划中的特殊情形，它的变量xj仅取值0或1。这时称为0-1变量，或称二进制变量。xj仅取值0或1这个条件可由下述约束条件：整数所代替，是和一般整数规划的约束条件形式一致的。在实际问题中，如果引入0-1变量，就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中讨论了。我们先介绍引入0-1变量的实际问题，再研究解法。黑龙江科技学院 数数 学学 建建 模模第41页，共117页，编辑于2022年，星期六例例5.2.4 某公司拟在市东、西、南三区建立门市部。拟议中有7个位置（点）Ai(i=1,2,7)可供选择。规定在东区：由A1,A2,A3三个点中至多选两个；在西区：由A4,A5两个点中至少选一个；在南区：由A6,A7两个点中至少选一个。如选用Ai点，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不能超过B元。问应选择哪几个点可使年利润为最大？黑龙江科技学院 数数 学学 建建 模模第42页，共117页，编辑于2022年，星期六解解 先引入0-1变量xi,i=1,2,7令于是问题可列写成：黑龙江科技学院 数数 学学 建建 模模第43页，共117页，编辑于2022年，星期六0-1型整数规划解法之一（过滤隐枚举法）型整数规划解法之一（过滤隐枚举法）解0-1型整数规划最容易想到的方法，和一般整数规划的情形一样，就是穷举法，即检查变量取值为0或1的每一种组合，比较目标函数值以求得最优解，这就需要检查变量取值的2n个组合。对于变量个数n较大，这几乎是不可能的。因此常设计一些方法，只检查变量取值的组合的一部分，就能求到问题的最优解。这样的方法称为隐枚举法，分枝定界法也是一种隐枚举法。当然，对有些问题隐枚举法并不适用，所以有时穷举法还是必要的。黑龙江科技学院 数数 学学 建建 模模理学院理学院第44页，共117页，编辑于2022年，星期六例例5.2.5 求解思路及改进措施：（i）先试探性求一个可行解，易看出(x1,x2,x3)=(1,0,0)满足约束条件，故为一个可行解，且相应的目标函数值为z=3。s.t.黑龙江科技学院 数数 学学 建建 模模理学院理学院第45页，共117页，编辑于2022年，星期六 ii）因为是求极大值问题，故求最优解时，凡是目标值z3的解不必检验是否满足约束条件即可删除，因它肯定不是最优解，于是应增加一个约束条件（目标值下界）：称该条件为过滤条件)。从而原问题等价于：abcdef 黑龙江科技学院 数数 学学 建建 模模第46页，共117页，编辑于2022年，星期六若用全部枚举法，3个变量共有8种可能的组合，我们将这8种组合依次检验它是否满足条件(a)(e)，对某个组合，若它不满足(a)，即不满足过滤条件，则(b)(e)即可行性条件不必再检验；若它满足(a)(e)且相应的目标值严格大于3，则进行（iii）。（iii）改进过滤条件。（iv）由于对每个组合首先计算目标值以验证过滤条件，故应优先计算目标值大的组合，这样可提前抬高过滤门槛，以减少计算量。按上述思路与方法，例5.2.5的求解过程可由下表来表示：黑龙江科技学院 数数 学学 建建 模模第47页，共117页，编辑于2022年，星期六(x1,x2,x3)目标值约束条件过滤条件a b c d e(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页，编辑于2022年，星期六整数规划的计算机解法整数规划的计算机解法 整数规划问题的求解可以使用Lingo等专用软件。对于一般的整数规划规划问题，无法直接利用Matlab的函数，必须利用Matlab编程实现分枝定界解法和割平面解法。但对于指派问题等特殊的0-1整数规划问题或约束矩阵A是幺模矩阵时，有时可以直接利用Matlab的函数linprog。黑龙江科技学院 数数 学学 建建 模模第49页，共117页，编辑于2022年，星期六5.2.6 求解下列指派问题，已知指派矩阵为 解解 编写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(25,1)求得最优指派方案为 第50页，共117页，编辑于2022年，星期六5.3 非线性规划非线性规划如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非线性规划问题。一般说来，解非线性规划要比解线性规划问题困难得多。而且，也不象线性规划有单纯形法这一通用方法，非线性规划目前还没有适于各种问题的一般算法，各个方法都有自己特定的适用范围。第51页，共117页，编辑于2022年，星期六例例5.3.1 （投资决策问题）某企业有个项目可供选择投资，并且至少要对其中一个项目投资。已知该企业拥有总资金元，投资于第个项目需花资金元，并预计可收益元。试选择最佳投资方案。解解 设投资决策变量为 限制条件 由于xi只取值0或1 第52页，共117页，编辑于2022年，星期六最佳投资方案应是投资额最小而总收益最大的方案，所以这个最佳投资决策问题归结为总资金以及决策变量（取0或1）的限制条件下，极大化总收益和总投资之比。因此，其数学模型为 第53页，共117页，编辑于2022年，星期六非线性规划问题一般形式：其中 称为模型的决策变量，f称为目标函数，gi(x)和 hi(x)称为约束函数。另外，gi(x)=0 称为等式约束，hi(x)0 称为不等式约束 第54页，共117页，编辑于2022年，星期六 非线性规划的Matlab解法 Matlab中非线性规划的数学模型形式 minf(x)其中是标量函数，是相应维数的矩阵和向量，是非线性向量函数。Matlab中的命令是X=FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON,OPTIONS)第55页，共117页，编辑于2022年，星期六例例5.3.1 求下列非线性规划问题第56页，共117页，编辑于2022年，星期六(1)编写M文件fun1.mfunction f=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页，编辑于2022年，星期六课前讨论题：课前讨论题：最短路径问题最短路径问题求从求从A A点到点到B B点的最短路径共有多少条？点的最短路径共有多少条？A AB B第58页，共117页，编辑于2022年，星期六最优路线为：最优路线为：A B1 C2 D1 E2 F2 GAB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643求从求从A A点到点到G G点的最短路径？点的最短路径？第59页，共117页，编辑于2022年，星期六第60页，共117页，编辑于2022年，星期六B1B2C1C2C3C4D1D2D3EA5313687668353384322引例导入：引例导入：最短路问题及其解法最短路问题及其解法在下面网络图中，其中圆圈称为点，两点之间的在下面网络图中，其中圆圈称为点，两点之间的连线称为弧，弧上的数字称为弧长。连线称为弧，弧上的数字称为弧长。第61页，共117页，编辑于2022年，星期六动态规划的研究对象是：动态规划的研究对象是：多阶段决策问题多阶段决策问题一、多阶段决策问题一、多阶段决策问题多阶段决策问题：多阶段决策问题：根据问题本身的特点，可以将根据问题本身的特点，可以将其求解的全过程划分为若干个相互联系的阶段其求解的全过程划分为若干个相互联系的阶段(即即将问题划分为许多个相互联系的子问题将问题划分为许多个相互联系的子问题)，在它的，在它的每一阶段都需要作出决策，并且在一个阶段的决每一阶段都需要作出决策，并且在一个阶段的决策确定以后再转移到下一个阶段。策确定以后再转移到下一个阶段。第62页，共117页，编辑于2022年，星期六多阶段决策过程多阶段决策过程前一个阶段的决策要影响到后一个阶段的决策，从而影前一个阶段的决策要影响到后一个阶段的决策，从而影响整个过程。各个阶段所确定的决策就构成了一个响整个过程。各个阶段所确定的决策就构成了一个决策决策序列序列，称为一个，称为一个策略策略。一般来说，由于每一阶段可供选择。一般来说，由于每一阶段可供选择的决策往往不止一个，因此，对于整个过程，就会有许多的决策往往不止一个，因此，对于整个过程，就会有许多可供选择的策略。可供选择的策略。最优策略最优策略若对应于一个策略，可以由一个量化的指标来确定这个策若对应于一个策略，可以由一个量化的指标来确定这个策略所对应的活动过程的效果，那么不同的策略就有各自的略所对应的活动过程的效果，那么不同的策略就有各自的效果。在所有可供选择的策略中，对应效果最好的策略称效果。在所有可供选择的策略中，对应效果最好的策略称为为最优策略最优策略。把一个问题划分成若干个相互联系的阶。把一个问题划分成若干个相互联系的阶段选取其最优策略，这类问题就是段选取其最优策略，这类问题就是多阶段决策问题多阶段决策问题。第63页，共117页，编辑于2022年，星期六二、多阶段决策问题类型二、多阶段决策问题类型由于市场需求是一随着时间而变化的因素，因此，由于市场需求是一随着时间而变化的因素，因此，为了取得全年最佳经济效益，就要在全年的生产为了取得全年最佳经济效益，就要在全年的生产过程中，逐月或者逐季度地根据库存和需求情况过程中，逐月或者逐季度地根据库存和需求情况决定生产计划安排。决定生产计划安排。工厂工厂生产生产过程过程设设备备更更新新问问题题一一般般企企业业用用于于生生产产活活动动的的设设备备，刚刚买买来来时时故故障障少少，经经济济效效益益高高，随随着着使使用用年年限限的的增增加加，就就会会逐逐渐渐变变为为故故障障多多，维维修修费费用用增增加加，可可正正常常使使用用的的工工时时减减少少，加加工工质质量量下下降降，经经济济效效益益差差，并并且且，使使用用的的年年限限越越长长、处处理理价价值值也也越越低低，自自然然，如如果果卖卖去去旧旧的的买买新新的的，还还需需要要付付出出更更新新费费因因此此就就需需要要综综合合权权衡衡决决定定设设备备的的使使用用年年限限，使总的经济效益最好。使总的经济效益最好。第64页，共117页，编辑于2022年，星期六资资源源分分配配问问题题某工业部门或公司，拟对其所属企业进行稀缺资源分某工业部门或公司，拟对其所属企业进行稀缺资源分配，为此需要制定出收益最大的资源分配方案。这种配，为此需要制定出收益最大的资源分配方案。这种问题原本要求一次确定出对各企业的资源分配量，它问题原本要求一次确定出对各企业的资源分配量，它与时间因素无关，不属动态决策，而是属于静态决策与时间因素无关，不属动态决策，而是属于静态决策问题，但是，我们可以人为地规定一个资源分配的阶问题，但是，我们可以人为地规定一个资源分配的阶段和顺序，从而使其变成一个多阶段决策问题。段和顺序，从而使其变成一个多阶段决策问题。运运输输网网络络问问题题在运输网络中，点与点之间连线上的数字表示两地距在运输网络中，点与点之间连线上的数字表示两地距离离(也可是运费、时间等也可是运费、时间等)，要求从一点，要求从一点 到另一点到另一点 的最的最短路线。短路线。这种运输网络问题也是静态决策问题。但是，按照这种运输网络问题也是静态决策问题。但是，按照网络中点的分布，可以把它分为若干个阶段，而作为网络中点的分布，可以把它分为若干个阶段，而作为多阶段决策问题来研究。多阶段决策问题来研究。第65页，共117页，编辑于2022年，星期六1 1、阶段：、阶段：把一个问题的过程，恰当地分为若干个相互联系把一个问题的过程，恰当地分为若干个相互联系的的阶段阶段，以便于按一定的次序去求解。，以便于按一定的次序去求解。描述阶段的变量称为描述阶段的变量称为阶段变量阶段变量。阶段的划分。阶段的划分,一一般是根据时间和空间的自然特征来进行的，但要便于问般是根据时间和空间的自然特征来进行的，但要便于问题转化为多阶段决策。题转化为多阶段决策。2 2、状态：、状态：表示每个阶段开始所处的表示每个阶段开始所处的自然状况或客观自然状况或客观条件条件。通常一个阶段有若干个状态，描述过程状态的。通常一个阶段有若干个状态，描述过程状态的变量称为变量称为状态变量状态变量。状态变量的取值有一定的允许集合或范围，此集合状态变量的取值有一定的允许集合或范围，此集合称为称为状态允许集合状态允许集合。年年,月月,路段路段一个数、一个数、一组数、一组数、一个向量一个向量第66页，共117页，编辑于2022年，星期六 3、决策：、决策：表示当过程处于某一阶段的某个状态时，可表示当过程处于某一阶段的某个状态时，可以作出不同的决定，从而确定下一阶段的状态，这种决定以作出不同的决定，从而确定下一阶段的状态，这种决定称为称为决策决策。描述决策的变量，称为描述决策的变量，称为决策变量决策变量。决策变量是状态变。决策变量是状态变量的函数。可用一个数、一组数或一向量（多维情形）量的函数。可用一个数、一组数或一向量（多维情形）来描述。来描述。在实际问题中决策变量的取值往往在某一范围之内，在实际问题中决策变量的取值往往在某一范围之内，此范围称为此范围称为允许决策集合允许决策集合。系统在某一阶段的状态转移不但与系统的当前的状系统在某一阶段的状态转移不但与系统的当前的状态和决策有关，而且还与系统过去的历史状态和决策态和决策有关，而且还与系统过去的历史状态和决策有关。有关。4、多阶段决策过程、多阶段决策过程 可以在各个阶段进行决策，控制过程发展的多段过程；可以在各个阶段进行决策，控制过程发展的多段过程；其发展是通过一系列的状态转移来实现；其发展是通过一系列的状态转移来实现；第67页，共117页，编辑于2022年，星期六5 5、策略：、策略：是一个按顺序排列的决策组成的集合。在实是一个按顺序排列的决策组成的集合。在实际问题中，可供选择的策略有一定的范围，称为际问题中，可供选择的策略有一定的范围，称为允许允许策略集合策略集合。从允许策略集合中找出达到最优效果的策略。从允许策略集合中找出达到最优效果的策略称为称为最优策略最优策略。6 6、状态转移方程：、状态转移方程：是确定过程由一个状态到另一个是确定过程由一个状态到另一个状态的演变过程，描述了状态转移规律。状态的演变过程，描述了状态转移规律。7 7、指标函数和最优值函数：、指标函数和最优值函数：用来衡量所实现过程优劣用来衡量所实现过程优劣的一种数量指标，为的一种数量指标，为指标函数指标函数。指标函数的最优值，。指标函数的最优值，称为称为最优值函数最优值函数。在不同的问题中，指标函数的含。在不同的问题中，指标函数的含义是不同的，它可能是距离、利润、成本、产量或义是不同的，它可能是距离、利润、成本、产量或资源消耗等。资源消耗等。动态规划模型的指标函数，应具有可分离性，并满足动态规划模型的指标函数，应具有可分离性，并满足递推递推关系。关系。第68页，共117页，编辑于2022年，星期六B1B2C1C2C3C4D1D2D3EA5313687668353384322引例：引例：最短路问题及其解法最短路问题及其解法在下面网络图中，其中圆圈称为点，两点之间的连在下面网络图中，其中圆圈称为点，两点之间的连线称为弧，弧上的数字称为弧长。线称为弧，弧上的数字称为弧长。第69页，共117页，编辑于2022年，星期六1、提出问题、提出问题求一条从起点求一条从起点A A到终点到终点E E的连通弧，使其总弧长最短的连通弧，使其总弧长最短最短路问题。最短路问题。2、意义说明、意义说明最短路问题最短路问题的含义是很广泛的，如点代表加油的含义是很广泛的，如点代表加油站，弧代表管道，弧长代表铺设管道的费用。问站，弧代表管道，弧长代表铺设管道的费用。问题就变成让我们设计一条从起点题就变成让我们设计一条从起点A A到终点到终点E E的管道，的管道，使其总费用最少。使其总费用最少。第70页，共117页，编辑于2022年，星期六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阶段的状态阶段的状态 出发所作的选择并成为出发所作的选择并成为决策变量决策变量。决策变量全体成为决策集合（允许决策集合），决策变量全体成为决策集合（