数学建模运筹模型精品文稿.ppt

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

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

2、套用长为套钢架，每套用长为2.9m2.9m，2.1m2.1m，1.5m1.5m的圆钢各一根，已知原料每根长的圆钢各一根，已知原料每根长7.4m7.4m。应如何下料，可使所用原料最省？。应如何下料，可使所用原料最省？解：共可设计下列解：共可设计下列5 5种下料方案种下料方案线性规划第4页，本讲稿共82页第5页，本讲稿共82页建模步骤：建模步骤：(1)(1)确定决策变量：我们需要作出决策或者选择的量，确定决策变量：我们需要作出决策或者选择的量，一般情况下，题目问什么就设什么为决策变量。一般情况下，题目问什么就设什么为决策变量。(2)(2)找出约束条件：即决策变量受到的所有的约束。找出约束条件：即决

3、策变量受到的所有的约束。(3)(3)写出目标函数：即问题所要达到的目标，并明确写出目标函数：即问题所要达到的目标，并明确是求是求maxmax还是还是minmin。线性规划第6页，本讲稿共82页例例 混合配料问题混合配料问题 某糖果厂用原料某糖果厂用原料1 1、2 2、3 3加工三种加工三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中不同牌号的糖果甲、乙、丙。已知各种牌号糖果中原料原料1 1、2 2、3 3的含量、原料每月限用量、三种牌号的含量、原料每月限用量、三种牌号糖果的加工费及售价，如下表所示。该厂每月如何糖果的加工费及售价，如下表所示。该厂每月如何生产才能获利最大？生产才能获利最大？线性

4、规划第7页，本讲稿共82页解：用解：用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 x3131,x,x3232,x,x3333;对于甲：对于甲：x x1111,x,x2121,x,x3131;对于乙：对于乙：x x1212,x,x2222,x,x3232

5、;对于丙：对于丙：x x1313,x,x2323,x,x3333;目标函数：利润最大，利润目标函数：利润最大，利润=收入收入-原料成本原料成本-加工费加工费 约束条件：原料用量限制，含量限制约束条件：原料用量限制，含量限制线性规划第8页，本讲稿共82页线性规划第9页，本讲稿共82页求解方法：求解方法：1.1.图解法图解法 适合含有两个决策变量的模型；适合含有两个决策变量的模型；max z=x1+3x2s.t.x1+x26-x1+2x28x1 0,x20可行域目标函数等值线最优解64-860 x1x2线性规划第10页，本讲稿共82页2.2.单纯形法单纯形法(人工变量法、对偶单纯形法人工变量法、对

6、偶单纯形法)软件求解：软件求解：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页 将某种物资从将某种物资从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个产

7、地向第个产地向第j j个销地运送单位物资的运个销地运送单位物资的运价为价为c cijij，总产量等于总需求量，总产量等于总需求量()()。如何调运物资，。如何调运物资，才能使总运费最小？才能使总运费最小？设设x xijij为从产地为从产地A Ai i运往销地运往销地B Bj j的运输量，的运输量，运输问题第12页，本讲稿共82页 运输表：运输表：(产销平衡的运输问题产销平衡的运输问题)求解方法：求解方法：1.1.确定初始基本可行解（西北角法、最小元素法、确定初始基本可行解（西北角法、最小元素法、vogalvogal法）法）2.2.最优性检验；最优性检验；3.3.迭代求新的基本可行解。迭代求新的

8、基本可行解。运输问题第13页，本讲稿共82页例例 某食品公司下属的三个食品厂某食品公司下属的三个食品厂A1A1、A2A2、A3A3生产食品，生产食品，3 3个厂每月个厂每月的生产能力分别为的生产能力分别为7 7吨、吨、4 4吨、吨、9 9吨，食品被运到吨，食品被运到B1B1、B2B2、B3B3、B4B4四四个销售点，它们对方便食品的月需求量分别为个销售点，它们对方便食品的月需求量分别为3 3吨、吨、6 6吨、吨、5 5吨、吨、6 6吨，运输表如下表，试制定最优运送方案。吨，运输表如下表，试制定最优运送方案。运输问题第14页，本讲稿共82页解：解：1.1.确定初始基可行解确定初始基可行解 最小元

9、素法：最小元素法：运输问题第15页，本讲稿共82页解：解：1.1.确定初始基可行解确定初始基可行解(最小元素法最小元素法)初始基本可行解对应的目标函数值：初始基本可行解对应的目标函数值：f=3*4+10*3+1*3+2*1+4*6+5*3=86 f=3*4+10*3+1*3+2*1+4*6+5*3=86运输问题第16页，本讲稿共82页解：解：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 为基本可行解中基变量对应的单位运价。为基本可行解中基变量对应

10、的单位运价。注：注：m+n-1m+n-1个方程，个方程，m+nm+n个变量。个变量。(2)(2)利用位势求非基变量检验数利用位势求非基变量检验数 检验数计算公式：检验数计算公式：c cij ij-u-ui i-v vj j (3)(3)检验数全都大于等于零时对应的解为最优解。检验数全都大于等于零时对应的解为最优解。运输问题第17页，本讲稿共82页位势：位势：检验数：检验数：运输问题第18页，本讲稿共82页3.3.迭代求新基本可行解迭代求新基本可行解(1)(1)负检验数中最小者对应的变量进基；负检验数中最小者对应的变量进基；(2)(2)在运输表中找一个包含进基变量的闭回路，这个回路上其他顶点均为

11、在运输表中找一个包含进基变量的闭回路，这个回路上其他顶点均为基变量。依次对闭回路的四个顶点标号，将顶点分为奇点格和偶点格；基变量。依次对闭回路的四个顶点标号，将顶点分为奇点格和偶点格；(3)(3)偶点格的最小值作为调整量，所有奇点格偶点格的最小值作为调整量，所有奇点格+调整量；偶点格调整量；偶点格-调整量，调整量，即一次迭代。即一次迭代。(4)(4)按位势方程求新解对应的位势及检验数，判别最优性。按位势方程求新解对应的位势及检验数，判别最优性。运输问题第19页，本讲稿共82页闭回路：闭回路：运输问题第20页，本讲稿共82页迭代及新基本可行解的检验数计算：迭代及新基本可行解的检验数计算：运输问题

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

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

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

15、的代项任务的代价为价为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页指派问题的求解方法：匈牙利法。指派问题的求解方法：匈牙利法。匈牙利法基于下面的事实：如果系数矩阵的所有元素满足：匈牙利法基于下面

16、的事实：如果系数矩阵的所有元素满足：c cijij=0=0，而其中有，而其中有n n个位于不同行不同列的一组个位于不同行不同列的一组0 0元素，则只要令对应元素，则只要令对应于这些于这些0 0元素位置的元素位置的x xijij=1=1，其余的，其余的x xijij=0=0，就得到最优解。，就得到最优解。如如 则则 指派问题第27页，本讲稿共82页求解上例：求解上例：行变换得行变换得 列变换得列变换得 画出最少覆盖画出最少覆盖0 0元素的直线，元素的直线，r=4=r=4=矩阵阶数，矩阵阶数，则可以找到最优解则可以找到最优解,所需最少时间所需最少时间=4+4+9+11=28=4+4+9+11=28

17、 甲甲-俄语俄语 从而得到最优指派：乙从而得到最优指派：乙-日语日语 丙丙-英语英语 丁丁-德语德语 指派问题第28页，本讲稿共82页例例 分配甲、乙、丙、丁四个人去完成分配甲、乙、丙、丁四个人去完成A A、B B、C C、D D、E E五项任务，每五项任务，每人完成各项任务的时间如下表所示，由于任务重，人手少，考虑人完成各项任务的时间如下表所示，由于任务重，人手少，考虑以下两种情况下的最优分配方案，使得完成任务的总时间最少。以下两种情况下的最优分配方案，使得完成任务的总时间最少。(1)(1)任务任务E E必须完成，其他必须完成，其他4 4项任务可选项任务可选3 3项完成，但甲不能做项完成，但

18、甲不能做A A项工作；项工作；(2)(2)其中有一人完成其中有一人完成2 2项，其他人每人完成项，其他人每人完成1 1项。项。解：这是一人数与任务数不等的指派问题，若用匈牙利法求解，需解：这是一人数与任务数不等的指派问题，若用匈牙利法求解，需作以下处理。作以下处理。指派问题第29页，本讲稿共82页(1)(1)由于任务数大于人数，所以需要有一个虚拟的人，设为戊。因为工作由于任务数大于人数，所以需要有一个虚拟的人，设为戊。因为工作E E必必须完成，故设戊完成须完成，故设戊完成E E的时间为的时间为M(MM(M为非常大的正数为非常大的正数)，即戊不能做工作，即戊不能做工作E E，其余的假想时间为其余

19、的假想时间为0 0，建立的效率矩阵为：，建立的效率矩阵为：采用匈牙利解法求解过程如下：采用匈牙利解法求解过程如下：指派问题第30页，本讲稿共82页(1)(1)由于由于r=4r=4矩阵阶数矩阵阶数=5=5，需要调整，需要调整0 0元素的分布。元素的分布。从该矩阵可看出，从该矩阵可看出，r=5=r=5=矩阵阶数，因此能找到最优指派方案。矩阵阶数，因此能找到最优指派方案。甲甲-B-B 乙乙-D-D 丙丙-E-E 丁丁-A-A 戊戊-C-C（戊（戊 为虚拟人，即任务为虚拟人，即任务C C无人完成）无人完成）最少的耗时数最少的耗时数 z=29+20+32+24=105 z=29+20+32+24=105

20、 指派问题第31页，本讲稿共82页(2)(2)思路：思路：方案方案1 1：甲，【甲】，乙，丙，丁：甲，【甲】，乙，丙，丁方案方案2 2：甲，乙，【乙】，丙，丁：甲，乙，【乙】，丙，丁方案方案3 3：甲，乙，丙，【丙】，丁：甲，乙，丙，【丙】，丁方案方案4 4：甲，乙，丙，丁，【丁】：甲，乙，丙，丁，【丁】方案方案5 5：甲，【甲】，乙，【乙】，丙，【丙】，丁，【丁】，工作：甲，【甲】，乙，【乙】，丙，【丙】，丁，【丁】，工作A A，B B，C C，D D，E E，虚拟工作，虚拟工作F F，G G，H H。这些方案较烦琐，采用以下思路更为简便。这些方案较烦琐，采用以下思路更为简便。设有虚拟人戊，

21、他集五人的优势为一身，即戊的费用是每人的最低，设有虚拟人戊，他集五人的优势为一身，即戊的费用是每人的最低，戊所做的工作即为此项工作的费用最低者的工作，效率矩阵分配戊所做的工作即为此项工作的费用最低者的工作，效率矩阵分配表为：表为：指派问题第32页，本讲稿共82页 采用匈牙利解法求解：采用匈牙利解法求解：对对C C3 3做做0 0元素的最小直线覆盖，得元素的最小直线覆盖，得r=5=nr=5=n。结果为。结果为 甲甲-B-B 乙乙-D-D 丙丙-E-E 丁丁-A-A 戊戊-C-C 但戊为虚拟人，不能真做，它做但戊为虚拟人，不能真做，它做C C工作是借乙工作是借乙(此列最小时数此列最小时数2626是

22、是C C所创业绩所创业绩)的优的优势，应由乙来做，即乙做两件工作：势，应由乙来做，即乙做两件工作：D D、C C。指派问题第33页，本讲稿共82页例例 最大收益的最优分配问题：有最大收益的最优分配问题：有5 5名工人完成名工人完成5 5项不同的任务收项不同的任务收 益如表益如表所示：所示：求使总收益达到最高的任务分配方案。求使总收益达到最高的任务分配方案。解：这是一个寻求总收益为最大值的极大化问题，需要转化为极小化问题才解：这是一个寻求总收益为最大值的极大化问题，需要转化为极小化问题才能用匈牙利解法。能用匈牙利解法。收益矩阵收益矩阵B=B=（b bijij），设），设b=maxbb=maxbi

23、jij，令，令c cijij=b-b=b-bijij ，C=C=（c cijij），以），以C C为为效率矩阵的极小化问题即是原最大收益的极大化问题转化而来。效率矩阵的极小化问题即是原最大收益的极大化问题转化而来。指派问题第34页，本讲稿共82页b=maxbb=maxbijij=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，求得的最大总收益为，求得的最大总收益为7

24、4.74.指派问题第35页，本讲稿共82页237184566134105275934682网络优化最短路径问题：有一批货物要从节点最短路径问题：有一批货物要从节点1运送到节点运送到节点8，这两点间的，这两点间的通路如下图，每条弧旁边的数字表明该弧的长度。总路径越短，通路如下图，每条弧旁边的数字表明该弧的长度。总路径越短，运费越低，为节省运输费用，应该选择怎样的运输路线？运费越低，为节省运输费用，应该选择怎样的运输路线？求从求从1 1到到8 8的最短路径。的最短路径。第36页，本讲稿共82页237184566134105275934682X=1,w1=0min c12,c14,c16=min 0

25、+2,0+1,0+3=min 2,1,3=1X=1,4,w4=1w1=0w1=0第37页，本讲稿共82页237184566134105275934682X=1,4min c12,c16,c42,c47=min 0+2,0+3,1+10,1+2=min 2,3,11,3=2X=1,2,4,w2=2w1=0w4=1w2=2第38页，本讲稿共82页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页23

26、7184566134105275934682X=1,2,4,6min c23,c25,c47,c67=min 2+6,2+5,1+2,3+4=min 8,7,3,7=3X=1,2,4,6,7,w7=3w2=2w4=1w1=0w6=3w7=3第40页，本讲稿共82页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页237184566134105275934682X

27、=1,2,4,6,7min c23,c53,c58,c78=min 2+6,6+9,6+4,3+8=min 8,15,10,11=8X=1,2,3,4,5,6,7,w3=8w2=2w4=1w1=0w6=3w7=3w5=6w3=8第42页，本讲稿共82页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页2371845661341052759346

28、82X=1,2,3,4,6,7,81到10的最短路径为1，4，7，5，8，长度为10。w2=2w4=1w1=0w6=3w7=3w5=6w3=8w8=10第44页，本讲稿共82页网络优化最大流问题：给出一个带收发点的网络，其每条弧的赋权称之最大流问题：给出一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发点到收为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。点的最大流量。2354671ffu25=6u42=2u45=4u23=3u13=7u34=4u46=3u36=1u65=7u57=9u67=8u12=8第45页，本讲稿共82页边的容量和流量

29、：容量边的容量和流量：容量u uijij，流量，流量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页给出一个初始的可行流

30、给出一个初始的可行流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页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页2354671f=0f=0

31、u=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页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调整流量，调整流量

32、，f=1f=1。继续求出网络的不饱和边。继续求出网络的不饱和边第51页，本讲稿共82页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页2354671f=2f=2u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9

33、u=8u=8x=1x=0 x=0 x=1x=0 x=0 x=0 x=1x=1x=1x=1x=0调整流量，继续求出网络的不饱和边调整流量，继续求出网络的不饱和边第53页，本讲稿共82页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,调整流量调整流量 xij xij=xij+5=xij+5,f,f=f+5=2+5=7=f+5=2+5=7第54页，本讲稿共82页

34、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页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=4=4=3=6求出一条从求出一条从1 1到到7 7的不饱和链的不饱和链=min 6,7,4,3=3,min 6,7,4,3=3,调整流量调整流量 xi

35、j xij=xij+3=xij+3,f f=f+3=7+3=10=f+3=7+3=10第56页，本讲稿共82页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页2354671f=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=0f=10=1=3=7=3求出一条从求出一条从1 1

36、到到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页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=2x=1x=6x=0调整流量，继续求出网络的不饱和边调整流量，继续求出网络的不饱和边已找不到一条从已找不到一条从1 1到到7 7的不饱和链，从的不饱和链，从1 1开始可以到达的节点为开始可以到达的节点为1 1，2 2，

37、3 3第59页，本讲稿共82页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页最短路问题：最短路问题：给定一个运输网络，两点之间连线上的数字表示两点之间的距离，试求一条从给定一个运输网络，两点之间连线上的数字表示两点之间的距离，试求一条从A A到到B B的的运输路线，使总距离最短。运输路线，使总距离最短。可将问题分为四个阶段

38、：第一阶段，从可将问题分为四个阶段：第一阶段，从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页阶段：阶段：将所给问题的过程，按时间或空间特征分解成相互联系的阶段，以便按次将所给问题的过程，按时间或空间特征分解成相互联系的阶段，以便按次序求每阶段的解序求每阶段的解 k k描述阶段的变量描述阶段的变量状态：状态：表示每个阶段表示每个阶段开始时开始时所处的自

39、然状况或条件，描述了研究问题的状况。所处的自然状况或条件，描述了研究问题的状况。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 2 动态规划中状态的性质：动态规划中状态的性质：无后效性无后效性，即如果某个阶段状态给定之后，则在这阶段以，即如果某个阶段状态给定之后，则在这阶段以后过程的发展不受这阶段以前各阶段状态的影响。后过程的发展不受这阶段以前各阶段状态的影响。决策：决策：指在某阶段对可供选择状态的选择，描述的

40、变量称为决策变量。指在某阶段对可供选择状态的选择，描述的变量称为决策变量。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页全过程策略：全过程策略：由所有各阶段组成的决策函数序列由所有各阶段组成的决策函数序列,简称简称策略策略。记为：。记为：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子过程策略子过程策略(后部

41、子策略后部子策略)：由由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)最优策略：最优策略：使整个问题达到最优效果的策略。使整个问题达到最优效果的策略。P P*1,n1,n(A)=(A)=B3,C2,D2,E A AB3 C2 D2 E允许策略集：允许策略集：可供选择策略的范围，用可供选择策略的范围，用P P表示。表示。动态规划方法就是要从允许策略集动态规划方法就是要从允许策略集P P中找出最优策略中找出最

42、优策略 P P*k,nk,n动态规划第63页，本讲稿共82页状态转移方程：状态转移方程：本阶段状态与上一阶段状态和上一阶段决策的关系，用状态转移方程来本阶段状态与上一阶段状态和上一阶段决策的关系，用状态转移方程来表示。表示。s sk+1k+1=T=Tk k(s(sk k,d,dk k)该方程描述了由第该方程描述了由第k k阶段到第阶段到第k+1k+1阶段的状态转移规律，又称为状态阶段的状态转移规律，又称为状态转移函数。转移函数。s sk+1k+1=d=dk k(s(sk k)阶段指标：阶段指标：衡量某阶段决策效益优劣的策略指标，如距离，成本，衡量某阶段决策效益优劣的策略指标，如距离，成本，利润

43、等。利润等。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+1,s,sn+1 n+1)动态规划第64页，本讲稿共82页常见指标函数形式常见指标函数形式(分离性，递推关系分离性，递推关系)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(

44、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 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,

45、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到过到过程终止时的最佳效益值。程终止时的最佳效益值。动态规划第65页，本讲稿共82页动态规划的基本思想：动态规划的基本思想：1.1.多阶段决策过程划分阶段，恰当的选取状态变量、决策变量和定义最多阶段决策过程划分阶段，恰当的选取状态变量、决策变量和定义最优指标函数，从而将问题化为一族同类型的子问题逐个求解。优指标函数，从而将问题化为一族同类型的子问题逐个求解。2.2.求解时从边界条件开始，逆（或顺

46、）过程行进方向，逐段递推寻求解时从边界条件开始，逆（或顺）过程行进方向，逐段递推寻优。优。3.3.既将当前一段与未来各段分开，又将当前效益与未来效益既将当前一段与未来各段分开，又将当前效益与未来效益结合起来考虑的一种最优化方法。结合起来考虑的一种最优化方法。如何建立动态规划模型：如何建立动态规划模型：1.1.分析识别问题的多阶段特性，按时间或空间的先后顺序适当分析识别问题的多阶段特性，按时间或空间的先后顺序适当地划分地划分满足递推关系满足递推关系的若干阶段。的若干阶段。2.2.确定状态变量，满足确定状态变量，满足可知性可知性和和无后效性无后效性。一般为累计量和随递推。一般为累计量和随递推过程变

47、化的量。过程变化的量。3.3.找到状态转移方程。找到状态转移方程。4.4.正确确定基本方程。正确确定基本方程。第66页，本讲稿共82页基础：基础：最优化定理最优化定理作为整个过程的最优策略具有如下性质：不管在此最优策略上作为整个过程的最优策略具有如下性质：不管在此最优策略上的某个状态以前的状态和决策如何，对该状态而言，以后所有的某个状态以前的状态和决策如何，对该状态而言，以后所有的决策必定构成最优子策略。的决策必定构成最优子策略。对最短路问题而言对最短路问题而言,从最短路上任一点到终点的部分道路（最短路上从最短路上任一点到终点的部分道路（最短路上的子路）也一定是从该点到终点的最短路。的子路）也

48、一定是从该点到终点的最短路。动态规划第67页，本讲稿共82页从最后一段开始计算，由后向前逐步推移至从最后一段开始计算，由后向前逐步推移至A A点。点。第四阶段，由第四阶段，由D D1 1到到E E只有一条线路，其长度只有一条线路，其长度f4(D1)=3，同理同理f4(D2)=4；第三阶段，由第三阶段，由C Cj j到到D Di i均有两种选择，即均有两种选择，即第二阶段，由第二阶段，由B Bj j到到C Ci i均有三种选择，即均有三种选择，即动态规划第68页，本讲稿共82页第一阶段，由第一阶段，由A A到到B B，有三种选择，即，有三种选择，即f f1 1(A)=12(A)=12，说明从，说

49、明从A A到到E E的最短距离为的最短距离为1212，最短路线的确定可按计算，最短路线的确定可按计算顺序反推而得，即顺序反推而得，即A-BA-B3 3-C-C2 2-D-D2 2-E-E动态规划第69页，本讲稿共82页一个著名的命题：一个串村走户的卖货郎，他从某个村庄出发，通过一个著名的命题：一个串村走户的卖货郎，他从某个村庄出发，通过若干个村庄一次且仅一次，最后仍回到原出发的村庄，问：应如何选择若干个村庄一次且仅一次，最后仍回到原出发的村庄，问：应如何选择行走路线，能使得总的行程最短。行走路线，能使得总的行程最短。设有设有n个城市，个城市，1,2,n。Dij表示从表示从i城到城到j城的距离。

50、城的距离。规规定定推推销销员员是是从从城城市市1开开始始的的，设设推推销销员员走走到到i城城，记记Ni2,3,i-1,i+1,n 表示由表示由1城到城到i城的中间城市集合。城的中间城市集合。S表示到达表示到达i城中途所经过的城市的集合，则有城中途所经过的城市的集合，则有S Ni1）选选取取（i,S）作作为为状状态态变变量量，表表示示推推销销员员从从城城市市1开开始始走走到到i城城，经经过过若干个城市，构成集合若干个城市，构成集合S。2）最最优优值值函函数数fk(i,S)为为从从城城市市1开开始始经经过过k个个中中间间城城市市的的S集集到到达达i城的最短路线的距离。城的最短路线的距离。货郎担问题