《数学建模-第五章-数学规划模型ppt课件.ppt》由会员分享，可在线阅读，更多相关《数学建模-第五章-数学规划模型ppt课件.ppt（117页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数学建模数学建模（Mathematical Modeling)黑龙江科技学院理学院黑龙江科技学院理学院工程数学教研室工程数学教研室第五章第五章 数学规划模型数学规划模型 黑龙江科技学院 数数 学学 建建 模模 理学院理学院第五章第五章 数学规划模型数学规划模型 数学规划论起始数学规划论起始20世纪世纪30年代末年代末，50年代与年代与60年代年代发展成为一个完整的分支并发展成为一个完整的分支并受到数学界和社会各界的重视。受到数学界和社会各界的重视。七八十年七八十年代代是数学规划飞速发展时期，无论是从理是数学规划飞速发展时期，无论是从理论上还是算法方面都得到了进一步完善。论上还是算法方面都得到了
2、进一步完善。时至今日数学规划仍然是运筹学领域中热时至今日数学规划仍然是运筹学领域中热点研究问题。从国内外的数学建模竞赛的点研究问题。从国内外的数学建模竞赛的试题中看，有近试题中看，有近1/4的问题可用数学规划的问题可用数学规划进行求解。进行求解。 黑龙江科技学院 数数 学学 建建 模模理学院理学院动态规划模型动态规划模型数学规划模型数学规划模型第五章非线性规划模型非线性规划模型重点重点:数学规划模型的建立和求解数学规划模型的建立和求解难点难点:数学规划模型的基本原理及数值计算数学规划模型的基本原理及数值计算线性规划模型线性规划模型 黑龙江科技学院 数数 学学 建建 模模 理学院理学院建模举例建
3、模举例多目标规划模型多目标规划模型 整数规划模型整数规划模型 1、例、例1：某机床厂生产甲、乙两种机床，每台销售后某机床厂生产甲、乙两种机床，每台销售后的利润分别为的利润分别为4000元与元与3000元。生产甲机床元。生产甲机床需用需用A，B机器加工，加工时间分别为每台机器加工，加工时间分别为每台2小小时和时和1小时；生产乙机床需用小时；生产乙机床需用A，B，C三种机三种机器加工，加工时间为每台各一小时。若每天可器加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为用于加工的机器时数分别为A机器机器10小时、小时、B机器机器8小时和小时和C机器机器7小时，问该厂应生产甲、小时，问该厂
4、应生产甲、乙机床各几台，才能使总利润最大？乙机床各几台，才能使总利润最大？ 黑龙江科技学院 数数 学学 建建 模模理学院理学院设该厂生产x1台甲机床和x2台乙机床时总利润最大，则x1,x2应满足:目标函数 :约束条件 : 2134maxxxz0,781022122121xxxxxxx 黑龙江科技学院 数数 学学 建建 模模理学院理学院1minnjjjzc x1s.t. 1,2,nijjija xbim1 12211 11221121 1222221 122min.0(1,2, )nnnnnnmmmnnmifc xc xc xa xa xa xba xa xa xbsta xaxaxbxin一般
5、线性规划问题的标准型为线性规划的Matlab标准形式 黑龙江科技学院 数数 学学 建建 模模理学院理学院 线性规划模型矩阵的形式： 例如线性规划 Matlab标准型为 bAxxcxT that such minbAxxcxT that such maxbAxxcxT that such min 黑龙江科技学院 数数 学学 建建 模模理学院理学院0246810012345678910 x2=72x1+x2=10 x1+x2=8z=12(2,6)Tx)6 , 2(*26*z4、线性规划的图解法本例的最优解为 最优目标值 黑龙江科技学院 数数 学学 建建 模模理学院理学院 5、求解线性规划的Matl
6、ab解法 单纯形法单纯形法是首先由George Dantzig于1947年提出的，近60年来，虽有许多变形体已被开发，但却保持着同样的基本观念。由于有如下结论结论：若线性规划问题有有限最优解，则一定有某个最优解是可行区域的一个极点。基于此，单纯形法的基本思路是基本思路是：先找出可行域的一个极点，据一定规则判断其是否最优；若否，则转换到与之相邻的另一极点，并使目标函数值更优；如此下去，直到找到某一最优解为止。 黑龙江科技学院 数数 学学 建建 模模理学院理学院 Matlab2008b中线性规划的标准型为：基本函数形式为linprog(c,A,b)，它的返回值是向量的值。还有其它的一些函数调用形式
7、（在 Matlab 指令窗运行 help linprog 可以看到所有的函数调用形式），如：x,fval=linprog(c,A,b,Aeq,beq,LB,UB,X0,OPTIONS)这里fval返回目标函数的值，Aeq和beq对应等式约束，LB和UB分别是变量的下界和上界，是的初始值，OPTIONS是控制参数。 bAxxcTx such that min 黑龙江科技学院 数数 学学 建建 模模理学院理学院例例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
8、,beq,zeros(3,1) value=c*x （ii）将M文件存盘，并命名为example1.m。 （iii）在Matlab指令窗运行example1即可得所 求结果。 321532max xxxz0,10527321321321xxxxxxxxx 黑龙江科技学院 数数 学学 建建 模模理学院理学院 例例5.1.3 求解线性规划问题 32132 minxxxz0,62382432121321xxxxxxxx 解解 编写Matlab程序如下：c=2;3;1;a=1,4,2;3,2,0;b=8;6;x,y=linprog(c,-a,-b, , ,zeros(3,1) 黑龙江科技学院 数数 学
9、学 建建 模模理学院理学院例例5.15拟分配n人去干n项工作，每人干且仅干一项工作，若分配第i人去干第j项工作，需花费cij单位时间，问应如何分配工作才能使工人花费的总时间最少？ 引入变量xij，若分配i干j工作，则取xij=1，否则取xij=0。上述指派问题的数学模型为: 11minnnijijijc x n,1,2,ji, 1 0,2, 1, 1,2, 1, 111或ijniijnjijxnjxnix 指派问题指派问题 黑龙江科技学院 数数 学学 建建 模模理学院理学院 可行解既可以用一个矩阵(称为解矩阵)表示，其每行每列均有且只有一个元素为1，其余元素均为0，也可以用1,n中的一个置换表
10、示。 求解指派问题的匈牙利算法求解指派问题的匈牙利算法 由于指派问题的特殊性，又存在着由匈牙利数学家D.Konig提出的更为简便的解法匈牙利匈牙利算法算法。算法主要依据以下事实：如果系数矩阵C=cij一行（或一列）中每一元素都加上或减去同一个数，得到一个新矩阵B=bij，则以C或B为系数矩阵的指派问题具有相同的最优指派。 黑龙江科技学院 数数 学学 建建 模模理学院理学院可将原系数阵C变换为含零元素较多的新系数阵B，而最优解不变。若能在B中找出n个位于不同行不同列的零元素，令解矩阵中相应位置的元素取值为1，其它元素取值为0，则所得该解是以B为系数阵的指派问题的最优解，从而也是原问题的最优解。由
11、C到B的转换可通过先让矩阵C的每行元素均减去其所在行的最小元素得矩阵D，D的每列元素再减去其所在列的最小元素得以实现。 黑龙江科技学院 数数 学学 建建 模模理学院理学院例例5.1.6 求解指派问题，其系数矩阵为 将第一行元素减去此行中的最小元素15，同样，第二行元素减去17，第三行元素减去17，最后一行的元素减去16，得16221917171822241819211722191516C06310157124074011B 黑龙江科技学院 数数 学学 建建 模模理学院理学院 再将第3列元素各减去1，得 以B2为系数矩阵的指派问题有最优指派 *20531005711407301B43124321
12、0100100000100001X即 黑龙江科技学院 数数 学学 建建 模模理学院理学院 例例5.1.7 求解系数矩阵求解系数矩阵C的指派问题的指派问题解解 先作等价变换如下先作等价变换如下 61071041066141512141217766698979712C 2636040*08957510*00*0032202*056107104106614151214121776669897971246767 黑龙江科技学院 数数 学学 建建 模模理学院理学院容易看出，从变换后的矩阵中只能选出四个位于不同行不同列的零元素，但n=5，最优指派还无法看出。此时等价变换还可进行下去。步骤如下：（1）对未选
13、出0元素的行打；（2）对行中0元素所在列打；（3）对列中选中的0元素所在行打；重复（2）、（3）直到无法再打为止。可以证明，若用直线划没有打的行与打的列，就得到了能够覆盖住矩阵中所有零元素的最少条数的直线集合，找出未覆盖的元素中的最小者，令行元素减去此数，列元素加上此数，则原先选中的0元素不变，而未覆盖元素中至少有一个已转变为0，且新矩阵的指派问题与原问题也等价。 黑龙江科技学院 数数 学学 建建 模模理学院理学院 上述过程可反复采用，直到能选取出足够的0元素为止。例如，对例5.1.7变换后的矩阵再变换，第三行、第五行元素减去2，第一列元素加上2，得 最优指派为 041404008113538
14、000034202075314254321 黑龙江科技学院 数数 学学 建建 模模理学院理学院建模举例：营养配餐问题建模举例：营养配餐问题 每种蔬菜含有的营养素成份是不同的，从医每种蔬菜含有的营养素成份是不同的，从医学上知道，每人每周对每种营养成分的最低需求学上知道，每人每周对每种营养成分的最低需求量。某医院营养室在制定下一周菜单时，需要确量。某医院营养室在制定下一周菜单时，需要确定表定表2-42-4中所列六种蔬菜的供应量，以便使费用中所列六种蔬菜的供应量，以便使费用最小而又能满足营养素等其它方面的要求。规定最小而又能满足营养素等其它方面的要求。规定白菜的供应一周内不多于白菜的供应一周内不多于
15、2020千克，其它蔬菜的供千克，其它蔬菜的供应在一周内不多于应在一周内不多于4040千克，每周共需供应千克，每周共需供应140140千千克蔬菜，为了使费用最小又满足营养素等其它方克蔬菜，为了使费用最小又满足营养素等其它方面的要求，问在下一周内应当供应每种蔬菜各多面的要求，问在下一周内应当供应每种蔬菜各多少千克？少千克？ 黑龙江科技学院 数数 学学 建建 模模理学院理学院表表5-4 黑龙江科技学院 数数 学学 建建 模模理学院理学院问题分析问题分析设设 分别表示下一周内应当供应的青分别表示下一周内应当供应的青豆、胡萝卜、菜花、白菜、甜菜及土豆的量，豆、胡萝卜、菜花、白菜、甜菜及土豆的量，费用费用
16、目标函数目标函数为：为： (1 6)ix i 123456558263fxxxxxx1234560.450.451.050.400.500.506xxxxxx约束条件：约束条件：铁的需求量至少铁的需求量至少6 6个单位数：个单位数：磷的需求量至少磷的需求量至少2525个单位数：个单位数：12345610285925227525xxxxxx 黑龙江科技学院 数数 学学 建建 模模理学院理学院12345641590652550751523517500 xxxxxx12345683532758245xxxxxx问题分析问题分析维生素维生素A A的需求量至少的需求量至少1750017500个单位：个单
17、位：维生素维生素C C的需求量至少的需求量至少245245个单位：个单位：烟酸的需求量至少烟酸的需求量至少5 5个单位数：个单位数：1234560.300.350.600.150.250.805xxxxxx每周需供应每周需供应140140千克蔬菜，即千克蔬菜，即123456140 xxxxxx 黑龙江科技学院 数数 学学 建建 模模理学院理学院模型的建立模型的建立123456123456123456123456123456123456min5582631400.450.451.050.400.500.50610285925227525.41590652550751523517500835327
18、582450.3fxxxxxxxxxxxxxxxxxxxxxxxxstxxxxxxxxxxxx12345600.350.600.150.250.805xxxxxx00 x x140 0140 0 x x240 0240 0 x x34034000 x x420 0420 0 x x540 0540 0 x x640640 黑龙江科技学院 数数 学学 建建 模模理学院理学院模型求解模型求解利用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
19、,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(菜
20、花需要的份数菜花需要的份数 )x(3)disp(白菜需要的份数白菜需要的份数 )x(4)disp(甜菜需要的份数甜菜需要的份数 )x(5)disp(土豆需要的份数土豆需要的份数)x(6) 黑龙江科技学院 数数 学学 建建 模模理学院理学院执执行行输输出出模型求解模型求解青豆需要的份数青豆需要的份数ans = 40胡罗卜需要的份数胡罗卜需要的份数 ans = 40.0000菜花需要的份数菜花需要的份数 ans = 0白菜需要的份数白菜需要的份数 ans = 20.0000 黑龙江科技学院 数数 学学 建建 模模理学院理学院甜菜需要的份数甜菜需要的份数 ans = 0土豆需要的份数土豆需要的份数a
21、ns = 40最小费用最小费用 ans = 560.0000模型求解模型求解执执行行输输出出 黑龙江科技学院 数数 学学 建建 模模理学院理学院5.2 整数规划模型 黑龙江科技学院 数数 学学 建建 模模有些LP往往要求全部或部分决策变量取非负整数值，如计件产品的生产计划、合理下料、设施的配备决策等，这样的LP称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。理学院理学院 1. 整数规划的分类 如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类： （i）变量全限制为整数时，称纯（完全）整数规划。 （ii）
22、变量部分限制为整数的，称混合整数规划。 （iii）变量只能取0或1时，称之为0-1整数规划。 2.整数规划特点 （i）原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况： 原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。整数规划无可行解 （ii） 整数规划最优解不能按照实数最优解简单取整而获得。理学院理学院分枝定界法分枝定界法 对有约束条件的最优化问题（其可行解为对有约束条件的最优化问题（其可行解为有限数）的可行解空间恰当地进行系统搜有限数）的可行解空间恰当地进行系统搜索，这就是索，这就是分枝分枝与与定界定界内容。通常，把全内容。通常，把全部可行解空间反复地分割
23、为越来越小的子部可行解空间反复地分割为越来越小的子集，称为集，称为分枝分枝；并且对每个子集内的解集；并且对每个子集内的解集计算一个目标下界（对于最小值问题），计算一个目标下界（对于最小值问题），这称为这称为定界定界。在每次分枝后，凡是界限不。在每次分枝后，凡是界限不优于已知可行解集目标值的那些子集不再优于已知可行解集目标值的那些子集不再进一步分枝，这样，许多子集可不予考虑，进一步分枝，这样，许多子集可不予考虑，这称这称剪枝剪枝。这就是分枝定界法的主要思路。这就是分枝定界法的主要思路。 黑龙江科技学院 数数 学学 建建 模模理学院理学院 设有最大化的整数规划问题A，与它相应的线性规划为问题B，从
24、解问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数Z*的上界，记作 ；而A的任意可行解的目标函数值将是Z*的一个下界Z 。分枝定界法就是将B的可行域分成子区域再求其最大值的方法。逐步减小 和增大Z，最终求到Z*。 ZZ 黑龙江科技学院 数数 学学 建建 模模理学院理学院例例5.2.3 求解下述整数规划 解解 （i）先不考虑整数限制，即解相应的线性规划，得最优解为： 可见它不符合整数条件。这时Z是问题A的最优目标函数值Z*的上界，记作 。而x1=0,x2=0显然是问题A的一个整数可行解，这时Z=0，是Z*的一个下界，记作，即0Z*356。219040Maxxxz
25、121212975672070,0 xxxxx x且为整数 s.t. 355.8779,8168. 1,8092. 421zxxZ 因为x1,x2当前均为非整数，故不满足整数要求，任选一个进行分枝。设选x1进行分枝，把可行集分成2个子集： ，因为4与5之间无整数，故这两个子集内的整数解必与原可行集合整数解一致。这一步称为分枝。这两个子集的规划及求解如下：问题B1： 最优解为： 14.84x 14.8 15x 219040Maxxxz12121297567207004,0 xxxxxx s.t. 349, 1 . 2, 0 . 4121zxx 问题B2 最优解为：219040Maxxxzs.t.
26、 1212129756720705,0 xxxxxx4 .341,57. 1, 0 . 5121zxx3490* z以此类推找出最优解。 从以上解题过程可得用分枝定界法求解整数规划（最大化）问题的步骤为： 开始，将要求解的整数规划问题称为问题A，将与它相应的线性规划问题称为问题B。 （i）解问题B可能得到以下情况之一： （a）B没有可行解，这时A也没有可行解，则停止 （b）B有最优解，并符合问题A的整数条件，B的最优解即为A的最优解，则停止。 （c）B有最优解，但不符合问题A的整数条件，记它的目标函数值为 。Z （ii）用观察法找问题A的一个整数可行解，一般可取xj=0，j=1,n试探，求得其
27、目标函数值，并记作Z。以Z*表示问题A的最优目标函数值；这时有 进行迭代。 第一步：分枝，在B的最优解中任选一个不符合整数条件的变量xj，其值为bj，以bj表示小于bj的最大整数。构造两个约束条件 将这两个约束条件，分别加入问题B，求两个后继规划问题B1和B2。不考虑整数条件求解这两个后继问题。 zzz*jjbx 1jjbx定界，以每个后继问题为一分枝标明求解的结果，与其它问题的解的结果中，找出最优目标函数值最大者作为新的上界 。从已符合整数条件的各分支中，找出目标函数值为最大者作为新的下界Z，若无作用Z=0。第二步：比较与剪枝，各分枝的最优目标函数中若有小于Z者，则剪掉这枝，即以后不再考虑了
28、。若大于Z，且不符合整数条件，则重复第一步骤。一直到最后得到Z*=Z为止。得最优整数解 xj*,j=1,n.Z 黑龙江科技学院 数数 学学 建建 模模0-1型整数规划型整数规划 0-1型整数规划是整数规划中的特殊情形，它的变量xj仅取值0或1。这时称为0-1变量，或称二进制变量。xj仅取值0或1这个条件可由下述约束条件： 整数所代替，是和一般整数规划的约束条件形式一致的。在实际问题中，如果引入0-1变量，就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中讨论了。我们先介绍引入0-1变量的实际问题，再研究解法。 01jx 黑龙江科技学院 数数 学学 建建 模模 例例5.2.4 某公司拟
29、在市东、西、南三区建立门市部。拟议中有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点没被选中当点被选中当，iAiAixiiixcz71Max10, 112765432171或iiiixxxxxxxxBxb 黑龙江科技学院 数数 学学
30、 建建 模模 0-1型整数规划解法之一（过滤隐枚举法）型整数规划解法之一（过滤隐枚举法） 解0-1型整数规划最容易想到的方法，和一般整数规划的情形一样，就是穷举法，即检查变量取值为0或1的每一种组合，比较目标函数值以求得最优解，这就需要检查变量取值的2n个组合。对于变量个数n较大，这几乎是不可能的。因此常设计一些方法，只检查变量取值的组合的一部分，就能求到问题的最优解。这样的方法称为隐枚举法，分枝定界法也是一种隐枚举法。当然，对有些问题隐枚举法并不适用，所以有时穷举法还是必要的。 黑龙江科技学院 数数 学学 建建 模模理学院理学院 例例5.2.5 求解思路及改进措施： （i） 先试探性求一个可
31、行解，易看出(x1,x2,x3)=(1,0,0)满足约束条件，故为一个可行解，且相应的目标函数值为z=3。 321523Maxxxxz10,64344223213221321321或xxxxxxxxxxxxx s.t. 黑龙江科技学院 数数 学学 建建 模模理学院理学院 ii） 因为是求极大值问题，故求最优解时，凡是目标值z3的解不必检验是否满足约束条件即可删除，因它肯定不是最优解，于是应增加一个约束条件（目标值下界）： 称该条件为过滤条件)。从而原问题等价于：3523321 xx321523Maxxxxz10,643442235233213221321321321或xxxxxxxxxxxxx
32、xxxabcdef 黑龙江科技学院 数数 学学 建建 模模 若用全部枚举法，3个变量共有8种可能的组合，我们将这8种组合依次检验它是否满足条件(a)(e)，对某个组合，若它不满足(a)，即不满足过滤条件，则(b)(e)即可行性条件不必再检验；若它满足(a)(e)且相应的目标值严格大于3，则进行（iii）。 （iii） 改进过滤条件。 （iv） 由于对每个组合首先计算目标值以验证过滤条件，故应优先计算目标值大的组合，这样可提前抬高过滤门槛，以减少计算量。 按上述思路与方法，例5.2.5的求解过程可由下表来表示： 黑龙江科技学院 数数 学学 建建 模模3523321 xx5523321 xx852
33、3321 xx (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从而得最优解 *123(,)(1,0,1)xxx最优值 *8z 黑龙江科技学院 数数 学学 建建 模模整数规划的计算机解法整数规划的计算机解法 整数规划问题的求解可以使用Lingo等专用软件。对于一般的整数规划规划问题，无法直接利用Matlab的函数，必须利用Matlab编程实现分枝定界解法和割平面解法。但对于指派问题等特殊的0-1整数规划问题或约束矩阵A是幺模矩阵时，有时可以直接利
34、用Matlab的函数linprog。 黑龙江科技学院 数数 学学 建建 模模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)1096109532485724679278310283求得最优指派方案为 15233
35、244511xxxxx5.3 非线性规划非线性规划如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非线性规划问题。一般说来，解非线性规划要比解线性规划问题困难得多。而且，也不象线性规划有单纯形法这一通用方法，非线性规划目前还没有适于各种问题的一般算法，各个方法都有自己特定的适用范围。例例5.3.1 （投资决策问题）某企业有个项目可供选择投资，并且至少要对其中一个项目投资。已知该企业拥有总资金元，投资于第个项目需花资金元，并预计可收益元。试选择最佳投资方案。 解解 设投资决策变量为 1,0iixi决定投资第 个项目，决定不投资第 个项目10niiia xA限制条件 (1)0,1, .i
36、ixxin由于xi只取值0或1 最佳投资方案应是投资额最小而总收益最大的方案，所以这个最佳投资决策问题归结为总资金以及决策变量（取0或1）的限制条件下，极大化总收益和总投资之比。因此，其数学模型为 11maxniiiniiib xQa x1. .0niiista xA(1)0,1, .iixxin 非线性规划问题一般形式：)(minxfqjxhj, 1, 0)(s.t.pixgi, 1, 0)(其中 称为模型的决策变量，f称为目标函数，gi(x)和 hi(x)称为约束函数。另外， gi(x)=0 称为等式约束， hi(x)0 称为不等式约束 Tnxxx1 非线性规划的Matlab解法 Matl
37、ab中非线性规划的数学模型形式 minf(x)( )0( )0AxBAeq xBeqC xCeq x其中是标量函数，是相应维数的矩阵和向量，是非线性向量函数。Matlab中的命令是X=FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON,OPTIONS) 例例5.3.1 求下列非线性规划问题221221221212min ( )8020,0.f xxxxxxxx x(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)
38、-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 A点到点到B B点的最短路径共有多少条？点的最短路径共有多少条？A AB B最优路线为：最优路线为：A B1 C2 D1 E2 F2 GAB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643求从求从A A点到点到G G
39、点的最短路径？点的最短路径？B1B2C1C2C3C4D1D2D3EA5313687668353384322引例导入：引例导入：最短路问题及其解法最短路问题及其解法在下面网络图中，其中圆圈称为点，两点之间在下面网络图中，其中圆圈称为点，两点之间的连线称为弧，弧上的数字称为弧长。的连线称为弧，弧上的数字称为弧长。动态规划的研究对象是：动态规划的研究对象是：多阶段决策问题多阶段决策问题一、多阶段决策问题一、多阶段决策问题多阶段决策问题：多阶段决策问题：根据问题本身的特点，可以根据问题本身的特点，可以将其求解的全过程划分为若干个相互联系的阶将其求解的全过程划分为若干个相互联系的阶段段( (即将问题划分
40、为许多个相互联系的子问题即将问题划分为许多个相互联系的子问题) )，在它的每一阶段都需要作出决策，并且在一，在它的每一阶段都需要作出决策，并且在一个阶段的决策确定以后再转移到下一个阶段。个阶段的决策确定以后再转移到下一个阶段。多阶段决策过程多阶段决策过程前一个阶段的决策要影响到后一个阶段的决策，从前一个阶段的决策要影响到后一个阶段的决策，从而影响整个过程。各个阶段所确定的决策就构成了而影响整个过程。各个阶段所确定的决策就构成了一个一个决策序列决策序列，称为一个，称为一个策略策略。一般来说，由于每。一般来说，由于每一阶段可供选择的决策往往不止一个，因此，对于一阶段可供选择的决策往往不止一个，因此
41、，对于整个过程，就会有许多可供选择的策略。整个过程，就会有许多可供选择的策略。最优策略最优策略若对应于一个策略，可以由一个量化的指标来确定若对应于一个策略，可以由一个量化的指标来确定这个策略所对应的活动过程的效果，那么不同的策这个策略所对应的活动过程的效果，那么不同的策略就有各自的效果。在所有可供选择的策略中，对略就有各自的效果。在所有可供选择的策略中，对应效果最好的策略称为应效果最好的策略称为最优策略最优策略。把一个问题划分。把一个问题划分成若干个相互联系的阶段选取其最优策略，这类问成若干个相互联系的阶段选取其最优策略，这类问题就是题就是多阶段决策问题多阶段决策问题。二、多阶段决策问题类型二
42、、多阶段决策问题类型由于市场需求是一随着时间而变化的因素，因由于市场需求是一随着时间而变化的因素，因此，为了取得全年最佳经济效益，就要在全年此，为了取得全年最佳经济效益，就要在全年的生产过程中，逐月或者逐季度地根据库存和的生产过程中，逐月或者逐季度地根据库存和需求情况决定生产计划安排。需求情况决定生产计划安排。工厂工厂生产生产过程过程设设备备更更新新问问题题一般企业用于生产活动的设备，刚买来时故障少，一般企业用于生产活动的设备，刚买来时故障少，经济效益高，随着使用年限的增加，就会逐渐变经济效益高，随着使用年限的增加，就会逐渐变为故障多，维修费用增加，可正常使用的工时减为故障多，维修费用增加，可
43、正常使用的工时减少，加工质量下降，经济效益差，并且，使用的少，加工质量下降，经济效益差，并且，使用的年限越长、处理价值也越低，自然，如果卖去旧年限越长、处理价值也越低，自然，如果卖去旧的买新的，还需要付出更新费因此就需要综合的买新的，还需要付出更新费因此就需要综合权衡决定设备的使用年限，使总的经济效益最好。权衡决定设备的使用年限，使总的经济效益最好。资资源源分分配配问问题题某工业部门或公司，拟对其所属企业进行稀缺某工业部门或公司，拟对其所属企业进行稀缺资源分配，为此需要制定出收益最大的资源分资源分配，为此需要制定出收益最大的资源分配方案。这种问题原本要求一次确定出对各企配方案。这种问题原本要求
44、一次确定出对各企业的资源分配量，它与时间因素无关，不属动业的资源分配量，它与时间因素无关，不属动态决策，而是属于静态决策问题，但是，我们态决策，而是属于静态决策问题，但是，我们可以人为地规定一个资源分配的阶段和顺序，可以人为地规定一个资源分配的阶段和顺序，从而使其变成一个多阶段决策问题。从而使其变成一个多阶段决策问题。运运输输网网络络问问题题在运输网络中，点与点之间连线上的数字表示两在运输网络中，点与点之间连线上的数字表示两地距离地距离(也可是运费、时间等也可是运费、时间等)，要求从一点，要求从一点 到另一到另一点点 的最短路线。的最短路线。 这种运输网络问题也是静态决策问题。但是，这种运输网
45、络问题也是静态决策问题。但是，按照网络中点的分布，可以把它分为若干个阶段按照网络中点的分布，可以把它分为若干个阶段，而作为多阶段决策问题来研究。，而作为多阶段决策问题来研究。1 1、阶段：、阶段： 把一个问题的过程，恰当地分为若干个相互把一个问题的过程，恰当地分为若干个相互联系的联系的阶段阶段，以便于按一定的次序去求解。，以便于按一定的次序去求解。 描述阶段的变量称为描述阶段的变量称为阶段变量阶段变量。阶段的划分。阶段的划分, ,一般是根据时间和空间的自然特征来进行的，但一般是根据时间和空间的自然特征来进行的，但要便于问题转化为多阶段决策。要便于问题转化为多阶段决策。2 2、状态：、状态：表示
46、每个阶段开始所处的表示每个阶段开始所处的自然状况或自然状况或客观条件客观条件。通常一个阶段有若干个状态，描述。通常一个阶段有若干个状态，描述过程状态的变量称为过程状态的变量称为状态变量状态变量。状态变量的取值有一定的允许集合或范围，此状态变量的取值有一定的允许集合或范围，此集合称为集合称为状态允许集合状态允许集合。年年, ,月月, ,路段路段一个数、一个数、一组数、一组数、一个向量一个向量 3、决策：、决策：表示当过程处于某一阶段的某个状态表示当过程处于某一阶段的某个状态时，可以作出不同的决定，从而确定下一阶段的状时，可以作出不同的决定，从而确定下一阶段的状态，这种决定称为态，这种决定称为决策
47、决策。 描述决策的变量，称为描述决策的变量，称为决策变量决策变量。决策变量是状。决策变量是状态变量的函数。可用一个数、一组数或一向量（多态变量的函数。可用一个数、一组数或一向量（多维情形）来描述。维情形）来描述。 在实际问题中决策变量的取值往往在某一范围在实际问题中决策变量的取值往往在某一范围之内，此范围称为之内，此范围称为允许决策集合允许决策集合。 系统在某一阶段的状态转移不但与系统的当前系统在某一阶段的状态转移不但与系统的当前的状态和决策有关，而且还与系统过去的历史状的状态和决策有关，而且还与系统过去的历史状态和决策有关。态和决策有关。 4、多阶段决策过程、多阶段决策过程 可以在各个阶段进
48、行决策，控制过程发展的多段可以在各个阶段进行决策，控制过程发展的多段过程；其发展是通过一系列的状态转移来实现；过程；其发展是通过一系列的状态转移来实现；5 5、策略：、策略：是一个按顺序排列的决策组成的集合。是一个按顺序排列的决策组成的集合。在实际问题中，可供选择的策略有一定的范围，在实际问题中，可供选择的策略有一定的范围，称为称为允许策略集合允许策略集合。从允许策略集合中找出达到。从允许策略集合中找出达到最优效果的策略称为最优效果的策略称为最优策略最优策略。 6 6、状态转移方程：、状态转移方程：是确定过程由一个状态到另是确定过程由一个状态到另一个状态的演变过程，描述了状态转移规律。一个状态
49、的演变过程，描述了状态转移规律。7 7、指标函数和最优值函数：、指标函数和最优值函数：用来衡量所实现过用来衡量所实现过程优劣的一种数量指标，为程优劣的一种数量指标，为指标函数指标函数。指标函数。指标函数的最优值，称为的最优值，称为最优值函数最优值函数。在不同的问题中，。在不同的问题中，指标函数的含义是不同的，它可能是距离、利润、指标函数的含义是不同的，它可能是距离、利润、成本、产量或资源消耗等。成本、产量或资源消耗等。 动态规划模型的指标函数，应具有可分离性，动态规划模型的指标函数，应具有可分离性，并满足并满足递推递推关系。关系。B1B2C1C2C3C4D1D2D3EA531368766835
50、3384322引例：引例：最短路问题及其解法最短路问题及其解法在下面网络图中，其中圆圈称为点，两点之间在下面网络图中，其中圆圈称为点，两点之间的连线称为弧，弧上的数字称为弧长。的连线称为弧，弧上的数字称为弧长。1、提出问题、提出问题求一条从起点求一条从起点A A到终点到终点E E的连通弧，使其总弧长的连通弧，使其总弧长最短最短最短路问题。最短路问题。2、意义说明、意义说明最短路问题最短路问题的含义是很广泛的，如点代表加油的含义是很广泛的，如点代表加油站，弧代表管道，弧长代表铺设管道的费用。站，弧代表管道，弧长代表铺设管道的费用。问题就变成让我们设计一条从起点问题就变成让我们设计一条从起点A A