数学建模运筹模型幻灯片.ppt

《数学建模运筹模型幻灯片.ppt》由会员分享，可在线阅读，更多相关《数学建模运筹模型幻灯片.ppt（82页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数学建模运筹模型第1页，共82页，编辑于2022年，星期六线性规划线性规划运输问题运输问题指派问题指派问题网络优化网络优化动态规划动态规划目录目录 第2页，共82页，编辑于2022年，星期六例例 某工厂在计划期内要安排某工厂在计划期内要安排，两种产品的生产，已知生产两种产品的生产，已知生产 单位产单位产品所需的设备台时及品所需的设备台时及A A，B B两种原材料的消耗、资源的限制，如下表。两种原材料的消耗、资源的限制，如下表。问题：工厂应分别生产多少单位问题：工厂应分别生产多少单位，产品才能使工厂获利最多？产品才能使工厂获利最多？线性规划线性规划第3页，共82页，编辑于2022年，星期六例例

2、下料问题下料问题 某工厂要做某工厂要做100100套钢架，每套用长为套钢架，每套用长为2.9m2.9m，2.1m2.1m，1.5m1.5m的圆钢各一根，已知原料每根长的圆钢各一根，已知原料每根长7.4m7.4m。应如何下料，。应如何下料，可使所用原料最省？可使所用原料最省？解：共可设计下列解：共可设计下列5 5种下料方案种下料方案线性规划线性规划第4页，共82页，编辑于2022年，星期六第5页，共82页，编辑于2022年，星期六建模步骤：建模步骤：(1)(1)确定决策变量：我们需要作出决策或者选择的量，一确定决策变量：我们需要作出决策或者选择的量，一般情况下，题目问什么就设什么为决策变量。般情

3、况下，题目问什么就设什么为决策变量。(2)(2)找出约束条件：即决策变量受到的所有的约束。找出约束条件：即决策变量受到的所有的约束。(3)(3)写出目标函数：即问题所要达到的目标，并明确是写出目标函数：即问题所要达到的目标，并明确是求求maxmax还是还是minmin。线性规划线性规划第6页，共82页，编辑于2022年，星期六例例 混合配料问题混合配料问题 某糖果厂用原料某糖果厂用原料1 1、2 2、3 3加工三种不同牌加工三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中原料号的糖果甲、乙、丙。已知各种牌号糖果中原料1 1、2 2、3 3的含量、原料每月限用量、三种牌号糖果的加工费及售的含量、

4、原料每月限用量、三种牌号糖果的加工费及售价，如下表所示。该厂每月如何生产才能获利最大？价，如下表所示。该厂每月如何生产才能获利最大？线性规划线性规划第7页，共82页，编辑于2022年，星期六解：用解：用i=1,2,3i=1,2,3代表原料代表原料1,2,3,j=1,2,31,2,3,j=1,2,3代表糖果甲、乙、丙。代表糖果甲、乙、丙。X Xijij表示第表示第j j中产品中原料中产品中原料i i的含量，则的含量，则 对于原料对于原料1 1：x x1111,x,x1212,x,x1313;对于原料对于原料2 2：x x2121,x,x2222,x,x2323;对于原料对于原料3 3：x x31

5、31,x,x3232,x,x3333;对于甲：对于甲：x x1111,x,x2121,x,x3131;对于乙：对于乙：x x1212,x,x2222,x,x3232;对于丙：对于丙：x x1313,x,x2323,x,x3333;目标函数：利润最大，利润目标函数：利润最大，利润=收入收入-原料成本原料成本-加工费加工费 约束条件：原料用量限制，含量限制约束条件：原料用量限制，含量限制线性规划线性规划第8页，共82页，编辑于2022年，星期六线性规划线性规划第9页，共82页，编辑于2022年，星期六求解方法：求解方法：1.1.图解法图解法 适合含有两个决策变量的模型；适合含有两个决策变量的模型；

6、max z=x1+3x2s.t.x1+x26-x1+2x28x1 0,x20可行域目标函数等值线最优解64-860 x1x2线性规划线性规划第10页，共82页，编辑于2022年，星期六2.2.单纯形法单纯形法(人工变量法、对偶单纯形法人工变量法、对偶单纯形法)软件求解：软件求解：lingolingo，lindolindo，MatlabMatlabMin f=0.4x1+1.5x2+x3+1.3x4 S.t.0.3x1+3x2+1.5x4=320 0.5x1+2x3+x4=240 1.4x1+0.7x4=420 线性规划线性规划第11页，共82页，编辑于2022年，星期六 将某种物资从将某种物资

7、从m m个产地遇到个产地遇到n n个销地，每个产地都有一定的产量个销地，每个产地都有一定的产量a ai i，i=1,2,i=1,2,m,m，每个销地都对物资有一定的需求量，每个销地都对物资有一定的需求量b bj j,j=1,2,j=1,2,n,n。已知从第已知从第i i个产地向第个产地向第j j个销地运送单位物资的运价为个销地运送单位物资的运价为c cijij，总产量等，总产量等于总需求量于总需求量()()。如何调运物资，才能使总运费最小？。如何调运物资，才能使总运费最小？设设x xijij为从产地为从产地A Ai i运往销地运往销地B Bj j的运输量，的运输量，运输问题运输问题第12页，共

8、82页，编辑于2022年，星期六 运输表：运输表：(产销平衡的运输问题产销平衡的运输问题)求解方法：求解方法：1.1.确定初始基本可行解（西北角法、最小元素法、确定初始基本可行解（西北角法、最小元素法、vogalvogal法）法）2.2.最优性检验；最优性检验；3.3.迭代求新的基本可行解。迭代求新的基本可行解。运输问题运输问题第13页，共82页，编辑于2022年，星期六例例 某食品公司下属的三个食品厂某食品公司下属的三个食品厂A1A1、A2A2、A3A3生产食品，生产食品，3 3个厂每月个厂每月的生产能力分别为的生产能力分别为7 7吨、吨、4 4吨、吨、9 9吨，食品被运到吨，食品被运到B1

9、B1、B2B2、B3B3、B4B4四个销售点，它们对方便食品的月需求量分别为四个销售点，它们对方便食品的月需求量分别为3 3吨、吨、6 6吨、吨、5 5吨、吨、6 6吨，运输表如下表，试制定最优运送方案。吨，运输表如下表，试制定最优运送方案。运输问题运输问题第14页，共82页，编辑于2022年，星期六解：解：1.1.确定初始基可行解确定初始基可行解 最小元素法：最小元素法：运输问题运输问题第15页，共82页，编辑于2022年，星期六解：解：1.1.确定初始基可行解确定初始基可行解(最小元素法最小元素法)初始基本可行解对应的目标函数值：初始基本可行解对应的目标函数值：f=3*4+10*3+1*3

10、+2*1+4*6+5*3=86 f=3*4+10*3+1*3+2*1+4*6+5*3=86运输问题运输问题第16页，共82页，编辑于2022年，星期六解：解：2.2.最优性检验最优性检验 (1)(1)位势：位势：u ui i+v vj j=c cij ij (i=1,2,(i=1,2,m,j=1,2,m,j=1,2,n),n)其中其中c cij ij 为基本可行解中基变量对应的单位运价。为基本可行解中基变量对应的单位运价。注：注：m+n-1m+n-1个方程，个方程，m+nm+n个变量。个变量。(2)(2)利用位势求非基变量检验数利用位势求非基变量检验数 检验数计算公式：检验数计算公式：c ci

11、j ij-u-ui i-v vj j (3)(3)检验数全都大于等于零时对应的解为最优解。检验数全都大于等于零时对应的解为最优解。运输问题运输问题第17页，共82页，编辑于2022年，星期六位势：位势：检验数：检验数：运输问题运输问题第18页，共82页，编辑于2022年，星期六3.3.迭代求新基本可行解迭代求新基本可行解(1)(1)负检验数中最小者对应的变量进基；负检验数中最小者对应的变量进基；(2)(2)在运输表中找一个包含进基变量的闭回路，这个回路上其他顶点均为在运输表中找一个包含进基变量的闭回路，这个回路上其他顶点均为基变量。依次对闭回路的四个顶点标号，将顶点分为奇点格和偶点格；基变量。

12、依次对闭回路的四个顶点标号，将顶点分为奇点格和偶点格；(3)(3)偶点格的最小值作为调整量，所有奇点格偶点格的最小值作为调整量，所有奇点格+调整量；偶点格调整量；偶点格-调整量，即一次迭代。调整量，即一次迭代。(4)(4)按位势方程求新解对应的位势及检验数，判别最优性。按位势方程求新解对应的位势及检验数，判别最优性。运输问题运输问题第19页，共82页，编辑于2022年，星期六闭回路：闭回路：运输问题运输问题第20页，共82页，编辑于2022年，星期六迭代及新基本可行解的检验数计算：迭代及新基本可行解的检验数计算：运输问题运输问题第21页，共82页，编辑于2022年，星期六 产销不平衡运输问题：

13、产销不平衡运输问题：1.1.供大于求，引入虚拟销售点，并假设它的需求量为供大于求，引入虚拟销售点，并假设它的需求量为2.2.供不应求，引入虚拟的产地，并假设它的产量为供不应求，引入虚拟的产地，并假设它的产量为 由于虚拟销地是不存在的，实际上这个差值是在产地贮存的，由于虚拟销地是不存在的，实际上这个差值是在产地贮存的，故从产地到虚拟销地的单位运价为故从产地到虚拟销地的单位运价为0 0；同理，由于虚拟产地是不存在的，所以虚设的产地到各个销同理，由于虚拟产地是不存在的，所以虚设的产地到各个销地的单位运价也为地的单位运价也为0.0.运输问题运输问题第22页，共82页，编辑于2022年，星期六例例 2

14、2个化肥厂供应个化肥厂供应3 3个地区的化肥，试决定运费最小的调运方案。个地区的化肥，试决定运费最小的调运方案。解：增加虚设的销地解：增加虚设的销地B4B4，销量为，销量为1010，构造产销平衡的运输表。，构造产销平衡的运输表。运输问题运输问题第23页，共82页，编辑于2022年，星期六初始基可行解及其检验数：初始基可行解及其检验数：迭代求新基本可行解：迭代求新基本可行解：运输问题运输问题第24页，共82页，编辑于2022年，星期六 n n项任务，恰好有项任务，恰好有n n个人承担，由于每个人的专长不同，完成各工个人承担，由于每个人的专长不同，完成各工作的效率不同，于是产生了应指派哪个人去完成

15、哪项，使得完成作的效率不同，于是产生了应指派哪个人去完成哪项，使得完成n n项任务的总效率最高的问题，这类问题称为指派问题。项任务的总效率最高的问题，这类问题称为指派问题。例例 有一份说明书，需要译成英、日、德、俄四种文字，现有甲有一份说明书，需要译成英、日、德、俄四种文字，现有甲乙丙丁四个人，他们将说明书译成不同文字所需要的时间如下乙丙丁四个人，他们将说明书译成不同文字所需要的时间如下表所示，问应指派哪个人完成哪项工作，耗用的总时间最少？表所示，问应指派哪个人完成哪项工作，耗用的总时间最少？指派问题指派问题第25页，共82页，编辑于2022年，星期六 一般地，有一般地，有n n项任务、项任务

16、、n n个完成人，第个完成人，第i i人完成第人完成第j j项任务的代价项任务的代价为为c cijij(i,j=1,2,i,j=1,2,n,n),),为了求得总代价最小的指派方案，引入为了求得总代价最小的指派方案，引入0-10-1型变型变量量x xij ij,令令 数学模型为数学模型为 注：指派问题是注：指派问题是0-10-1整数规划的特例，也是运输问题的特例，其产地整数规划的特例，也是运输问题的特例，其产地和销地数均为和销地数均为1 1，各产地产量和各销地销量均为，各产地产量和各销地销量均为1.1.指派问题指派问题第26页，共82页，编辑于2022年，星期六指派问题的求解方法：匈牙利法。指派

17、问题的求解方法：匈牙利法。匈牙利法基于下面的事实：如果系数矩阵的所有元素满足：匈牙利法基于下面的事实：如果系数矩阵的所有元素满足：c cijij=0=0，而其中有，而其中有n n个位于不同行不同列的一组个位于不同行不同列的一组0 0元素，则只要令对应于这元素，则只要令对应于这些些0 0元素位置的元素位置的x xijij=1=1，其余的，其余的x xijij=0=0，就得到最优解。，就得到最优解。如如 则则 指派问题指派问题第27页，共82页，编辑于2022年，星期六求解上例：求解上例：行变换得行变换得 列变换得列变换得 画出最少覆盖画出最少覆盖0 0元素的直线，元素的直线，r=4=r=4=矩阵

18、阶数，矩阵阶数，则可以找到最优解则可以找到最优解,所需最少时间所需最少时间=4+4+9+11=28=4+4+9+11=28 甲甲-俄语俄语 从而得到最优指派：乙从而得到最优指派：乙-日语日语 丙丙-英语英语 丁丁-德语德语 指派问题指派问题第28页，共82页，编辑于2022年，星期六例例 分配甲、乙、丙、丁四个人去完成分配甲、乙、丙、丁四个人去完成A A、B B、C C、D D、E E五项任务，每五项任务，每人完成各项任务的时间如下表所示，由于任务重，人手少，考人完成各项任务的时间如下表所示，由于任务重，人手少，考虑以下两种情况下的最优分配方案，使得完成任务的总时间最虑以下两种情况下的最优分配

19、方案，使得完成任务的总时间最少。少。(1)(1)任务任务E E必须完成，其他必须完成，其他4 4项任务可选项任务可选3 3项完成，但甲不能做项完成，但甲不能做A A项工作；项工作；(2)(2)其中有一人完成其中有一人完成2 2项，其他人每人完成项，其他人每人完成1 1项。项。解：这是一人数与任务数不等的指派问题，若用匈牙利法求解，需作解：这是一人数与任务数不等的指派问题，若用匈牙利法求解，需作以下处理。以下处理。指派问题指派问题第29页，共82页，编辑于2022年，星期六(1)(1)由于任务数大于人数，所以需要有一个虚拟的人，设为戊。因为工作由于任务数大于人数，所以需要有一个虚拟的人，设为戊。

20、因为工作E E必须完成，故设戊完成必须完成，故设戊完成E E的时间为的时间为M(MM(M为非常大的正数为非常大的正数)，即戊不能做，即戊不能做工作工作E E，其余的假想时间为，其余的假想时间为0 0，建立的效率矩阵为：，建立的效率矩阵为：采用匈牙利解法求解过程如下：采用匈牙利解法求解过程如下：指派问题指派问题第30页，共82页，编辑于2022年，星期六(1)(1)由于由于r=4r=4矩阵阶数矩阵阶数=5=5，需要调整，需要调整0 0元素的分布。元素的分布。从该矩阵可看出，从该矩阵可看出，r=5=r=5=矩阵阶数，因此能找到最优指派方案。矩阵阶数，因此能找到最优指派方案。甲甲-B-B 乙乙-D-

21、D 丙丙-E-E 丁丁-A-A 戊戊-C-C（戊（戊 为虚拟人，即任务为虚拟人，即任务C C无人完成）无人完成）最少的耗时数最少的耗时数 z=29+20+32+24=105 z=29+20+32+24=105 指派问题指派问题第31页，共82页，编辑于2022年，星期六(2)(2)思路：思路：方案方案1 1：甲，【甲】，乙，丙，丁：甲，【甲】，乙，丙，丁方案方案2 2：甲，乙，【乙】，丙，丁：甲，乙，【乙】，丙，丁方案方案3 3：甲，乙，丙，【丙】，丁：甲，乙，丙，【丙】，丁方案方案4 4：甲，乙，丙，丁，【丁】：甲，乙，丙，丁，【丁】方案方案5 5：甲，【甲】，乙，【乙】，丙，【丙】，丁，【

22、丁】，工作：甲，【甲】，乙，【乙】，丙，【丙】，丁，【丁】，工作A A，B B，C C，D D，E E，虚拟工作，虚拟工作F F，G G，H H。这些方案较烦琐，采用以下思路更为简便。这些方案较烦琐，采用以下思路更为简便。设有虚拟人戊，他集五人的优势为一身，即戊的费用是每人的最低，设有虚拟人戊，他集五人的优势为一身，即戊的费用是每人的最低，戊所做的工作即为此项工作的费用最低者的工作，效率矩阵分配表戊所做的工作即为此项工作的费用最低者的工作，效率矩阵分配表为：为：指派问题指派问题第32页，共82页，编辑于2022年，星期六 采用匈牙利解法求解：采用匈牙利解法求解：对对C C3 3做做0 0元素的

23、最小直线覆盖，得元素的最小直线覆盖，得r=5=nr=5=n。结果为。结果为 甲甲-B-B 乙乙-D-D 丙丙-E-E 丁丁-A-A 戊戊-C-C 但戊为虚拟人，不能真做，它做但戊为虚拟人，不能真做，它做C C工作是借乙工作是借乙(此列最小时数此列最小时数2626是是C C所创业绩所创业绩)的优势，的优势，应由乙来做，即乙做两件工作：应由乙来做，即乙做两件工作：D D、C C。指派问题指派问题第33页，共82页，编辑于2022年，星期六例例 最大收益的最优分配问题：有最大收益的最优分配问题：有5 5名工人完成名工人完成5 5项不同的任务收项不同的任务收 益如益如表所示：表所示：求使总收益达到最高

24、的任务分配方案。求使总收益达到最高的任务分配方案。解：这是一个寻求总收益为最大值的极大化问题，需要转化为极解：这是一个寻求总收益为最大值的极大化问题，需要转化为极小化问题才能用匈牙利解法。小化问题才能用匈牙利解法。收益矩阵收益矩阵B=B=（b bijij），设），设b=maxbb=maxbijij，令，令c cijij=b-b=b-bijij ，C=C=（c cijij），以），以C C为效为效率矩阵的极小化问题即是原最大收益的极大化问题转化而来。率矩阵的极小化问题即是原最大收益的极大化问题转化而来。指派问题指派问题第34页，共82页，编辑于2022年，星期六b=maxbb=maxbijij=

25、19=19，令，令c cijij=19-b=19-bijij ，C=C=（c cijij），），继续对继续对C C矩阵采用匈牙利法求解，得到矩阵采用匈牙利法求解，得到C C的最优分配方案为的最优分配方案为即即 甲甲-D-D 乙乙-B-B 丙丙-E-E 丁丁-A-A 戊戊-C-C，求得的最大总收益为，求得的最大总收益为74.74.指派问题指派问题第35页，共82页，编辑于2022年，星期六237184566134105275934682网络优化网络优化最短路径问题：有一批货物要从节点最短路径问题：有一批货物要从节点1运送到节点运送到节点8，这两点间的通路如下，这两点间的通路如下图，每条弧旁边的数

26、字表明该弧的长度。总路径越短，运费越低，为节图，每条弧旁边的数字表明该弧的长度。总路径越短，运费越低，为节省运输费用，应该选择怎样的运输路线？省运输费用，应该选择怎样的运输路线？求从求从1 1到到8 8的最短路径。的最短路径。第36页，共82页，编辑于2022年，星期六237184566134105275934682X=1,w1=0min c12,c14,c16=min 0+2,0+1,0+3=min 2,1,3=1X=1,4,w4=1w1=0w1=0第37页，共82页，编辑于2022年，星期六237184566134105275934682X=1,4min c12,c16,c42,c47=m

27、in 0+2,0+3,1+10,1+2=min 2,3,11,3=2X=1,2,4,w2=2w1=0w4=1w2=2第38页，共82页，编辑于2022年，星期六237184566134105275934682X=1,2,4min c16,c23,c25,c47=min 0+3,2+6,2+5,1+2=min 3,8,7,3=3X=1,2,4,6,w6=3w2=2w4=1w1=0w6=3第39页，共82页，编辑于2022年，星期六237184566134105275934682X=1,2,4,6min c23,c25,c47,c67=min 2+6,2+5,1+2,3+4=min 8,7,3,7

28、=3X=1,2,4,6,7,w7=3w2=2w4=1w1=0w6=3w7=3第40页，共82页，编辑于2022年，星期六237184566134105275934682X=1,2,4,6,7min c23,c25,c75,c78=min 2+6,2+5,3+3,3+8=min 8,7,6,11=6X=1,2,4,5,6,7,w5=6w2=2w4=1w1=0w6=3w7=3w5=6第41页，共82页，编辑于2022年，星期六237184566134105275934682X=1,2,4,6,7min c23,c53,c58,c78=min 2+6,6+9,6+4,3+8=min 8,15,10,

29、11=8X=1,2,3,4,5,6,7,w3=8w2=2w4=1w1=0w6=3w7=3w5=6w3=8第42页，共82页，编辑于2022年，星期六237184566134105275934682X=1,2,3,4,6,7min c38,c58,c78=min 8+6,6+4,3+8=min 14,10,11=10X=1,2,3,4,5,6,7,8,w8=10w2=2w4=1w1=0w6=3w7=3w5=6w3=8w8=10第43页，共82页，编辑于2022年，星期六237184566134105275934682X=1,2,3,4,6,7,81到10的最短路径为1，4，7，5，8，长度为10

30、。w2=2w4=1w1=0w6=3w7=3w5=6w3=8w8=10第44页，共82页，编辑于2022年，星期六网络优化网络优化最大流问题：给出一个带收发点的网络，其每条弧的赋权称之为容量，在不最大流问题：给出一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。超过每条弧的容量的前提下，求出从发点到收点的最大流量。2354671ffu25=6u42=2u45=4u23=3u13=7u34=4u46=3u36=1u65=7u57=9u67=8u12=8第45页，共82页，编辑于2022年，星期六边的容量和流量：容量边的容量和流量：容量u uij

31、ij，流量，流量x xijij可行流：可行流：满足以下条件的流称为可行流：满足以下条件的流称为可行流：1 1、每一个节点流量平衡、每一个节点流量平衡2 2、0 x0 xijij u uijij如果如果x xijij=u=uijij，边从，边从i i到到j j的方向是饱和的；的方向是饱和的；如果如果x xijiju00，边从，边从j j到到i i的方向是不饱和的的方向是不饱和的网络优化网络优化21xij=0uij=521xij=5uij=5（2 2，1 1）是不饱和的）是不饱和的间隙为间隙为 1212=x=x1212=5=5第47页，共82页，编辑于2022年，星期六给出一个初始的可行流给出一个

32、初始的可行流x xijij=0=02354671f=0f=0u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0网络优化网络优化第48页，共82页，编辑于2022年，星期六2354671f=0f=0u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0找到所有的不饱和边，以及各边可以调整流量的方向找到所有的不饱和边，以及各边可以调整流量的方向第49页，共82页，编辑于20

33、22年，星期六2354671f=0f=0u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0=3=1=8=8x=0找到一条从找到一条从1 1到到7 7的不饱和链的不饱和链链的间隙为：链的间隙为：=min8,3,1,8=1=min8,3,1,8=1调整链的流量：调整链的流量：xijxij=xij+=xij+第50页，共82页，编辑于2022年，星期六2354671f=1f=1u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0 x=0 x=0 x=0 x=0 x=0

34、 x=0 x=0 x=1x=1x=1x=1调整流量，调整流量，f=1f=1。继续求出网络的不饱和边。继续求出网络的不饱和边第51页，共82页，编辑于2022年，星期六2354671f=1f=1u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=1x=1x=1x=1=1=6=9=7求出一条从求出一条从1 1到到7 7的不饱和链的不饱和链=min 7,1,6,9=1,min 7,1,6,9=1,调整流量调整流量 xij xij=xij+1=xij+1,f,f=f+1=2=f+1=2第52页，共82页，编辑于20

35、22年，星期六2354671f=2f=2u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=1x=0 x=0 x=1x=0 x=0 x=0 x=1x=1x=1x=1x=0调整流量，继续求出网络的不饱和边调整流量，继续求出网络的不饱和边第53页，共82页，编辑于2022年，星期六2354671f=2f=2u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=1x=0 x=0 x=1x=0 x=0 x=0 x=1x=1x=1x=1x=0=5=8=7求出一条从求出一条从1到到7的不饱和链的不饱和链=min 7,5,8=5,min 7,5,8=5,调整流量

36、调整流量 xij xij=xij+5=xij+5,f,f=f+5=2+5=7=f+5=2+5=7第54页，共82页，编辑于2022年，星期六2354671f=7f=7u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0 x=0 x=1x=0 x=0 x=0 x=6x=1x=1x=6x=0调整流量，继续求出网络的不饱和边调整流量，继续求出网络的不饱和边第55页，共82页，编辑于2022年，星期六2354671f=7f=7u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0 x=0 x=1x=0 x=0 x=0 x=6x=1x=1x=

37、6x=0=4=4=3=6求出一条从求出一条从1 1到到7 7的不饱和链的不饱和链=min 6,7,4,3=3,min 6,7,4,3=3,调整流量调整流量 xij xij=xij+3=xij+3,f,f=f+3=7+3=10=f+3=7+3=10第56页，共82页，编辑于2022年，星期六2354671f=10f=10u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0 x=3x=4x=3x=0 x=0 x=9x=1x=1x=6x=0调整流量，继续求出网络的不饱和边调整流量，继续求出网络的不饱和边第57页，共82页，编辑于2022年，星期六2354671f=10

38、u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0 x=3x=4x=3x=0 x=0 x=9x=1x=1x=6x=0f=10=1=3=7=3求出一条从求出一条从1 1到到7 7的不饱和链的不饱和链=min 3,1,3,7=1,min 3,1,3,7=1,调整流量调整流量 xij xij=xij+1=xij+1,f,f=f+1=10+1=11=f+1=10+1=11第58页，共82页，编辑于2022年，星期六2354671f=11f=11u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0 x=4x=5x=3x=1x=0 x=9x

39、=2x=1x=6x=0调整流量，继续求出网络的不饱和边调整流量，继续求出网络的不饱和边已找不到一条从已找不到一条从1 1到到7 7的不饱和链，从的不饱和链，从1 1开始可以到达的节点为开始可以到达的节点为1 1，2 2，3 3第59页，共82页，编辑于2022年，星期六2354671f=11u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0 x=4x=5x=3x=1x=0 x=9x=2x=1x=6x=0f=11已求得最大流已求得最大流最大流f=11，最小割集为（2,5）（3,4）（3,5）u25+u34+u35=6+4+1=11第60页，共82页，编辑于202

40、2年，星期六最短路问题：最短路问题：给定一个运输网络，两点之间连线上的数字表示两点之间的距离，试求一条从给定一个运输网络，两点之间连线上的数字表示两点之间的距离，试求一条从A A到到B B的运输路线，的运输路线，使总距离最短。使总距离最短。可将问题分为四个阶段：第一阶段，从可将问题分为四个阶段：第一阶段，从A A到到B B；第二阶段，从；第二阶段，从B B到到C C；第三阶段，从；第三阶段，从C C到到D D；第四阶段，；第四阶段，从从D D到到E E。完全枚举：完全枚举：3*3*2*1=243*3*2*1=24条。条。最优解：最优解：A AB3 C2 D2 E动态规划动态规划第61页，共82

41、页，编辑于2022年，星期六阶段：阶段：将所给问题的过程，按时间或空间特征分解成相互联系的阶段，以便将所给问题的过程，按时间或空间特征分解成相互联系的阶段，以便按次序求每阶段的解按次序求每阶段的解 k k描述阶段的变量描述阶段的变量状态：状态：表示每个阶段表示每个阶段开始时开始时所处的自然状况或条件，描述了研究问题的状况。所处的自然状况或条件，描述了研究问题的状况。s sk k状态变量状态变量 S Sk k状态集合状态集合 S S1 1=A,=A,S S2 2=B=B1 1,B,B2 2,B,B3 3,S S3 3=C=C1 1,C,C2 2,C,C3 3,S S4 4=D=D1 1,D,D2

42、 2 动态规划中状态的性质：动态规划中状态的性质：无后效性无后效性，即如果某个阶段状态给定之后，则在这阶段以，即如果某个阶段状态给定之后，则在这阶段以后过程的发展不受这阶段以前各阶段状态的影响。后过程的发展不受这阶段以前各阶段状态的影响。决策：决策：指在某阶段对可供选择状态的选择，描述的变量称为决策变量。指在某阶段对可供选择状态的选择，描述的变量称为决策变量。d dk k(s sk k)决策变量决策变量 D Dk k(s sk k)允许决策集合允许决策集合 D D2 2(B(B1 1)=C)=C1 1,C,C2 2,C,C3 3 动态规划动态规划第62页，共82页，编辑于2022年，星期六全过

43、程策略：全过程策略：由所有各阶段组成的决策函数序列由所有各阶段组成的决策函数序列,简称简称策略策略。记为：。记为：P P1,n1,n(s(s1 1)或或P P1,n1,n(s(s1 1)=d)=d1 1(s(s1 1),d),d2 2(s(s2 2),),d,dn n(s(sn n)k k子过程策略子过程策略(后部子策略后部子策略)：由由k k阶段开始到最后阶段结束，组阶段开始到最后阶段结束，组成的决策函数序列。成的决策函数序列。P Pk,nk,n(s(sk k)=d)=dk k(s(sk k),d),dk+1k+1(s(sk+1k+1),),d,dn n(s(sn n)最优策略：最优策略：使

44、整个问题达到最优效果的策略。使整个问题达到最优效果的策略。P P*1,n1,n(A)=(A)=B3,C2,D2,E A AB3 C2 D2 E允许策略集：允许策略集：可供选择策略的范围，用可供选择策略的范围，用P P表示。表示。动态规划方法就是要从允许策略集动态规划方法就是要从允许策略集P P中找出最优策略中找出最优策略 P P*k,nk,n动态规划动态规划第63页，共82页，编辑于2022年，星期六状态转移方程：状态转移方程：本阶段状态与上一阶段状态和上一阶段决策的关系，用状态转移本阶段状态与上一阶段状态和上一阶段决策的关系，用状态转移方程来表示。方程来表示。s sk+1k+1=T=Tk k

45、(s(sk k,d,dk k)该方程描述了由第该方程描述了由第k k阶段到第阶段到第k+1k+1阶段的状态转移规律，又称为阶段的状态转移规律，又称为状态转移函数。状态转移函数。s sk+1k+1=d=dk k(s(sk k)阶段指标：阶段指标：衡量某阶段决策效益优劣的策略指标，如距离，成衡量某阶段决策效益优劣的策略指标，如距离，成本，利润等。本，利润等。v vk k(s(sk k,d,dk k)指标函数：指标函数：衡量所选定策略优劣的数量指标。衡量所选定策略优劣的数量指标。V Vk,nk,n(s(sk k,P,Pk,nk,n)=V)=Vk,nk,n(s(sk k,d,dk k,s,sk+1k+

46、1,s,sn+1 n+1)动态规划动态规划第64页，共82页，编辑于2022年，星期六常见指标函数形式常见指标函数形式(分离性，递推关系分离性，递推关系)V Vk,nk,n(s(sk k,P,Pk,nk,n)=V)=Vk,nk,n(s(sk k,d,dk k,s,sk+1k+1,s,sn+1 n+1)=V =Vk k(s(sk k,d,dk k)+V)+Vk+1k+1(s(sk+1k+1,P,Pk,nk,n)V Vk,nk,n(s(sk k,P,Pk,nk,n)=V)=Vk,nk,n(s(sk k,d,dk k,s,sk+1k+1,s,sn+1 n+1)=V =Vk k(s(sk k,d,dk

47、 k)*V)*Vk+1k+1(s(sk+1k+1,P,Pk,nk,n)最优指标函数最优指标函数:指标函数的最优值，指标函数的最优值，f fk k(s(sk k)表示从第表示从第k k阶段阶段状态状态s sk k开始开始采用最优策略采用最优策略P P*k,nk,n到过程终止时的最佳效益到过程终止时的最佳效益值。值。f fk k(s(sk k)=opt V)=opt Vk,nk,n(s(sk k,d,dk k,s,sk+1k+1,s,sn+1 n+1)f f1 1(s(s1 1)表示从第表示从第1 1阶段状态阶段状态s s1 1采用最优策略采用最优策略P P*1,n1,n到过程终止到过程终止时的最

48、佳效益值。时的最佳效益值。动态规划动态规划第65页，共82页，编辑于2022年，星期六动态规划的基本思想：动态规划的基本思想：1.1.多阶段决策过程划分阶段，恰当的选取状态变量、决策变量和定义多阶段决策过程划分阶段，恰当的选取状态变量、决策变量和定义最优指标函数，从而将问题化为一族同类型的子问题逐个求解。最优指标函数，从而将问题化为一族同类型的子问题逐个求解。2.2.求解时从边界条件开始，逆（或顺）过程行进方向，逐段递推寻优。求解时从边界条件开始，逆（或顺）过程行进方向，逐段递推寻优。3.3.既将当前一段与未来各段分开，又将当前效益与未来效益结合起既将当前一段与未来各段分开，又将当前效益与未来

49、效益结合起来考虑的一种最优化方法。来考虑的一种最优化方法。如何建立动态规划模型：如何建立动态规划模型：1.1.分析识别问题的多阶段特性，按时间或空间的先后顺序适当地划分析识别问题的多阶段特性，按时间或空间的先后顺序适当地划分分满足递推关系满足递推关系的若干阶段。的若干阶段。2.2.确定状态变量，满足确定状态变量，满足可知性可知性和和无后效性无后效性。一般为累计量和随递。一般为累计量和随递推过程变化的量。推过程变化的量。3.3.找到状态转移方程。找到状态转移方程。4.4.正确确定基本方程。正确确定基本方程。第66页，共82页，编辑于2022年，星期六基础：基础：最优化定理最优化定理作为整个过程的

50、最优策略具有如下性质：不管在此最优策略上作为整个过程的最优策略具有如下性质：不管在此最优策略上的某个状态以前的状态和决策如何，对该状态而言，以后所有的某个状态以前的状态和决策如何，对该状态而言，以后所有的决策必定构成最优子策略。的决策必定构成最优子策略。对最短路问题而言对最短路问题而言,从最短路上任一点到终点的部分道路（最短路从最短路上任一点到终点的部分道路（最短路上的子路）也一定是从该点到终点的最短路。上的子路）也一定是从该点到终点的最短路。动态规划动态规划第67页，共82页，编辑于2022年，星期六从最后一段开始计算，由后向前逐步推移至从最后一段开始计算，由后向前逐步推移至A A点。点。第