《数学建模运筹模型优秀PPT.ppt》由会员分享，可在线阅读，更多相关《数学建模运筹模型优秀PPT.ppt（83页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、线性规划线性规划运输问题运输问题指派问题指派问题网络优化网络优化动态规划动态规划书目书目 例例 某工厂在支配期内要支配某工厂在支配期内要支配，两种产品的生产，已知生产两种产品的生产，已知生产 单位产品所需的设备台时及单位产品所需的设备台时及A A，B B两种原材料的消耗、资源的两种原材料的消耗、资源的限制，如下表。问题：工厂应分别生产多少单位限制，如下表。问题：工厂应分别生产多少单位，产品产品才能使工厂获利最多？才能使工厂获利最多？线性规划线性规划例例 下料问题下料问题 某工厂要做某工厂要做100100套钢架，每套用长为套钢架，每套用长为2.9m2.9m，2.1m2.1m，1.5m1.5m的圆
2、钢各一根，已知原料每根长的圆钢各一根，已知原料每根长7.4m7.4m。应如何下料，可使所用原料最省？。应如何下料，可使所用原料最省？解：共可设计下列解：共可设计下列5 5种下料方案种下料方案线性规划线性规划建模步骤：建模步骤：(1)(1)确定决策变量：我们须要作出决策或者选择的量，确定决策变量：我们须要作出决策或者选择的量，一般状况下，题目问什么就设什么为决策变量。一般状况下，题目问什么就设什么为决策变量。(2)(2)找出约束条件：即决策变量受到的全部的约束。找出约束条件：即决策变量受到的全部的约束。(3)(3)写出目标函数：即问题所要达到的目标，并明确写出目标函数：即问题所要达到的目标，并明
3、确是求是求maxmax还是还是minmin。线性规划线性规划例例 混合配料问题混合配料问题 某糖果厂用原料某糖果厂用原料1 1、2 2、3 3加工三种加工三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中不同牌号的糖果甲、乙、丙。已知各种牌号糖果中原料原料1 1、2 2、3 3的含量、原料每月限用量、三种牌号的含量、原料每月限用量、三种牌号糖果的加工费及售价，如下表所示。该厂每月如何糖果的加工费及售价，如下表所示。该厂每月如何生产才能获利最大？生产才能获利最大？线性规划线性规划解：用解：用i=1,2,3i=1,2,3代表原料代表原料1,2,3,j=1,2,31,2,3,j=1,2,3代表糖果甲、
4、乙、丙。代表糖果甲、乙、丙。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;对于丙：对于丙：x x1313,x,x2323,x,x3333;目标函数：利润最大，利润目标函数：利润最大，利润=收入收入-原料成本原料成本-加
5、工费加工费 约束条件：原料用量限制，含量限制约束条件：原料用量限制，含量限制线性规划线性规划线性规划线性规划求解方法：求解方法：1.1.图解法图解法 适合含有两个决策变量的模型；适合含有两个决策变量的模型；max z=x1+3x2s.t.x1+x26-x1+2x28x1 0,x20可行域目标函数等值线最优解64-860 x1x2线性规划线性规划2.2.单纯形法单纯形法(人工变量法、对偶单纯形法人工变量法、对偶单纯形法)软件求解：软件求解：lingolingo，lindolindo，MatlabMatlabMin f=0.4x1+1.5x2+x3+1.3x4 S.t.0.3x1+3x2+1.5x
6、4=320 0.5x1+2x3+x4=240 1.4x1+0.7x4=420 线性规划线性规划 将某种物资从将某种物资从m m个产地遇到个产地遇到n n个销地，每个产地个销地，每个产地都有确定的产量都有确定的产量aiai，i=1,2,mi=1,2,m，每个销地都对，每个销地都对物资有确定的需求量物资有确定的需求量bj,j=1,2,nbj,j=1,2,n。已知从第。已知从第i i个产地向第个产地向第j j个销地运输单位物资的运价为个销地运输单位物资的运价为cijcij，总，总产量等于总需求量产量等于总需求量()()。如何调运物资，。如何调运物资，才能使总运费最小？才能使总运费最小？设设xijxi
7、j为从产地为从产地AiAi运往销地运往销地BjBj的运输量，的运输量，运输问题运输问题 运输表：运输表：(产销平衡的运输问题产销平衡的运输问题)求解方法：求解方法：1.1.确定初始基本可行解（西北角法、最小元素法、确定初始基本可行解（西北角法、最小元素法、vogalvogal法）法）2.2.最优性检验；最优性检验；3.3.迭代求新的基本可行解。迭代求新的基本可行解。运输问题运输问题例例 某食品公司下属的三个食品厂某食品公司下属的三个食品厂A1A1、A2A2、A3A3生产食品，生产食品，3 3个厂个厂每月的生产实力分别为每月的生产实力分别为7 7吨、吨、4 4吨、吨、9 9吨，食品被运到吨，食品
8、被运到B1B1、B2B2、B3B3、B4B4四个销售点，它们对便利食品的月需求量分别为四个销售点，它们对便利食品的月需求量分别为3 3吨、吨、6 6吨、吨、5 5吨、吨、6 6吨，运输表如下表，试制定最优运输方案。吨，运输表如下表，试制定最优运输方案。运输问题运输问题解：解：1.1.确定初始基可行解确定初始基可行解 最小元素法：最小元素法：运输问题运输问题解：解：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+
9、5*3=86运输问题运输问题解：解：2.2.最优性检验最优性检验 (1)(1)位势：位势：u ui i+v vj j=c cij ij (i=1,2,m,j=1,2,n)(i=1,2,m,j=1,2,n)其中其中c cij ij 为基本可行解中基变量对应的单位运价。为基本可行解中基变量对应的单位运价。注：注：m+n-1m+n-1个方程，个方程，m+nm+n个变量。个变量。(2)(2)利用位势求非基变量检验数利用位势求非基变量检验数 检验数计算公式：检验数计算公式：c cij ij-u-ui i-v vj j (3)(3)检验数全都大于等于零时对应的解为最优解。检验数全都大于等于零时对应的解为最
10、优解。运输问题运输问题位势：位势：检验数：检验数：运输问题运输问题3.3.迭代求新基本可行解迭代求新基本可行解(1)(1)负检验数中最小者对应的变量进基；负检验数中最小者对应的变量进基；(2)(2)在运输表中找一个包含进基变量的闭回路，这个回路上其在运输表中找一个包含进基变量的闭回路，这个回路上其他顶点均为基变量。依次对闭回路的四个顶点标号，将顶他顶点均为基变量。依次对闭回路的四个顶点标号，将顶点分为奇点格和偶点格；点分为奇点格和偶点格；(3)(3)偶点格的最小值作为调整量，全部奇点格偶点格的最小值作为调整量，全部奇点格+调整量；偶点调整量；偶点格格-调整量，即一次迭代。调整量，即一次迭代。(
11、4)(4)按位势方程求新解对应的位势及检验数，判别最优性。按位势方程求新解对应的位势及检验数，判别最优性。运输问题运输问题闭回路：闭回路：运输问题运输问题迭代及新基本可行解的检验数计算：迭代及新基本可行解的检验数计算：运输问题运输问题 产销不平衡运输问题：产销不平衡运输问题：1.1.供大于求，引入虚拟销售点，并假设它的供大于求，引入虚拟销售点，并假设它的需求量为需求量为 供不应求，引入虚拟的产地，并假设它的产量供不应求，引入虚拟的产地，并假设它的产量为为 由于虚拟销地是不存在的，事实上这个差值是在由于虚拟销地是不存在的，事实上这个差值是在产地贮存的，故从产地到虚拟销地的单位运价为产地贮存的，故
12、从产地到虚拟销地的单位运价为0 0；同理，由于虚拟产地是不存在的，所以虚设的产同理，由于虚拟产地是不存在的，所以虚设的产地到各个销地的单位运价也为地到各个销地的单位运价也为0.0.运输问题运输问题例例 2 2个化肥厂供应个化肥厂供应3 3个地区的化肥，试确定运费最小的调运方案。个地区的化肥，试确定运费最小的调运方案。解：增加虚设的销地解：增加虚设的销地B4B4，销量为，销量为1010，构造产销平衡的运输表。，构造产销平衡的运输表。运输问题运输问题初始基可行解及其检验数：初始基可行解及其检验数：迭代求新基本可行解：迭代求新基本可行解：运输问题运输问题 n n项任务，恰好有项任务，恰好有n n个人
13、担当，由于每个人的专长不个人担当，由于每个人的专长不同，完成各工作的效率不同，于是产生了应指派哪个同，完成各工作的效率不同，于是产生了应指派哪个人去完成哪项，使得完成人去完成哪项，使得完成n n项任务的总效率最高的问项任务的总效率最高的问题，这类问题称为指派问题。题，这类问题称为指派问题。例例 有一份说明书，须要译成英、日、德、俄四种文有一份说明书，须要译成英、日、德、俄四种文字，现有甲乙丙丁四个人，他们将说明书译成不同文字，现有甲乙丙丁四个人，他们将说明书译成不同文字所须要的时间如下表所示，问应指派哪个人完成哪字所须要的时间如下表所示，问应指派哪个人完成哪项工作，耗用的总时间最少？项工作，耗
14、用的总时间最少？指派问题指派问题 一般地，有一般地，有n n项任务、项任务、n n个完成人，第个完成人，第i i人完成第人完成第j j项任务的项任务的代价为代价为c cijij(i,j=1,2,ni,j=1,2,n),),为了求得总代价最小的指派方案，为了求得总代价最小的指派方案，引入引入0-10-1型变量型变量x xij ij,令令 数学模型为数学模型为 注：指派问题是注：指派问题是0-10-1整数规划的特例，也是运输问题的特例，整数规划的特例，也是运输问题的特例，其产地和销地数均为其产地和销地数均为1 1，各产地产量和各销地销量均为，各产地产量和各销地销量均为1.1.指派问题指派问题指派问
15、题的求解方法：匈牙利法。指派问题的求解方法：匈牙利法。匈牙利法基于下面的事实：假如系数矩阵的全部元素满足：匈牙利法基于下面的事实：假如系数矩阵的全部元素满足：cij=0cij=0，而其中有，而其中有n n个位于不同行不同列的一组个位于不同行不同列的一组0 0元素，则只元素，则只要令对应于这些要令对应于这些0 0元素位置的元素位置的xij=1xij=1，其余的，其余的xij=0 xij=0，就得到最，就得到最优解。优解。如如 则则 指派问题指派问题求解上例：求解上例：行变换得行变换得 列变换得列变换得 画出最少覆盖画出最少覆盖0 0元素的直线，元素的直线，r=4=r=4=矩阵阶数，矩阵阶数，则可
16、以找到最优解则可以找到最优解,所需最少时间所需最少时间=4+4+9+11=28=4+4+9+11=28 甲甲-俄语俄语 从而得到最优指派：乙从而得到最优指派：乙-日语日语 丙丙-英语英语 丁丁-德语德语 指派问题指派问题例例 安排甲、乙、丙、丁四个人去完成安排甲、乙、丙、丁四个人去完成A A、B B、C C、D D、E E五项任务，五项任务，每人完成各项任务的时间如下表所示，由于任务重，人手少，每人完成各项任务的时间如下表所示，由于任务重，人手少，考虑以下两种状况下的最优安排方案，使得完成任务的总时考虑以下两种状况下的最优安排方案，使得完成任务的总时间最少。间最少。(1)(1)任务任务E E必
17、需完成，其他必需完成，其他4 4项任务可选项任务可选3 3项完成，但甲不能做项完成，但甲不能做A A项工作；项工作；(2)(2)其中有一人完成其中有一人完成2 2项，其他人每人完成项，其他人每人完成1 1项。项。解：这是一人数与任务数不等的指派问题，若用匈牙利法求解，解：这是一人数与任务数不等的指派问题，若用匈牙利法求解，需作以下处理。需作以下处理。指派问题指派问题(1)(1)由于任务数大于人数，所以须要有一个虚拟的人，设为戊。由于任务数大于人数，所以须要有一个虚拟的人，设为戊。因为工作因为工作E E必需完成，故设戊完成必需完成，故设戊完成E E的时间为的时间为M(MM(M为特别大的正为特别大
18、的正数数)，即戊不能做工作，即戊不能做工作E E，其余的假想时间为，其余的假想时间为0 0，建立的效率矩，建立的效率矩阵为：阵为：接受匈牙利解法求解过程如下：接受匈牙利解法求解过程如下：指派问题指派问题(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
19、+32+24=105 z=29+20+32+24=105 指派问题指派问题(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。这些方案较烦琐，接受以下思路更为简便。这些方案较烦
20、琐，接受以下思路更为简便。设有虚拟人戊，他集五人的优势为一身，即戊的费用是每人的设有虚拟人戊，他集五人的优势为一身，即戊的费用是每人的最低，戊所做的工作即为此项工作的费用最低者的工作，效最低，戊所做的工作即为此项工作的费用最低者的工作，效率矩阵安排表为：率矩阵安排表为：指派问题指派问题 接受匈牙利解法求解：接受匈牙利解法求解：对对C3C3做做0 0元素的最小直线覆盖，得元素的最小直线覆盖，得r=5=nr=5=n。结果为。结果为 甲甲-B-B 乙乙-D-D 丙丙-E-E 丁丁-A-A 戊戊-C-C 但戊为虚拟人，不能真做，它做但戊为虚拟人，不能真做，它做C C工作是借乙工作是借乙(此列最小时数此
21、列最小时数2626是是C C所创业绩所创业绩)的优势，应由乙来做，即乙做两件工作：的优势，应由乙来做，即乙做两件工作：D D、C C。指派问题指派问题例例 最大收益的最优安排问题：有最大收益的最优安排问题：有5 5名工人完成名工人完成5 5项不同的任务收项不同的任务收 益如表所示：益如表所示：求使总收益达到最高的任务安排方案。求使总收益达到最高的任务安排方案。解：这是一个寻求总收益为最大值的极大化问题，须要转化为解：这是一个寻求总收益为最大值的极大化问题，须要转化为微小化问题才能用匈牙利解法。微小化问题才能用匈牙利解法。收益矩阵收益矩阵B=B=（bijbij），设），设b=maxbijb=ma
22、xbij，令，令cij=b-bij cij=b-bij，C=C=（cijcij），以），以C C为效率矩阵的微小化问题即是原最大收益的为效率矩阵的微小化问题即是原最大收益的极大化问题转化而来。极大化问题转化而来。指派问题指派问题b=maxbij=19b=maxbij=19，令，令cij=19-bij cij=19-bij，C=C=（cijcij），），接着对接着对C C矩阵接受匈牙利法求解，得到矩阵接受匈牙利法求解，得到C C的最优安排方案为的最优安排方案为即即 甲甲-D-D 乙乙-B-B 丙丙-E-E 丁丁-A-A 戊戊-C-C，求得的最大总收益为，求得的最大总收益为74.74.指派问题指派
23、问题237184566134105275934682网络优化网络优化最短路径问题：有一批货物要从节点最短路径问题：有一批货物要从节点1运输到节点运输到节点8，这两点间的，这两点间的通路如下图，每条弧旁边的数字表明该弧的长度。总路径越短，通路如下图，每条弧旁边的数字表明该弧的长度。总路径越短，运费越低，为节约运输费用，应当选择怎样的运输路途？运费越低，为节约运输费用，应当选择怎样的运输路途？求从求从1 1到到8 8的最短路径。的最短路径。237184566134105275934682X=1,w1=0min c12,c14,c16=min 0+2,0+1,0+3=min 2,1,3=1X=1,4
24、,w4=1w1=0w1=0237184566134105275934682X=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=2237184566134105275934682X=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=3237184566134105275934682X=1,2,4,6min c23,c25,c47,c67=min 2+6,2+5,
25、1+2,3+4=min 8,7,3,7=3X=1,2,4,6,7,w7=3w2=2w4=1w1=0w6=3w7=3237184566134105275934682X=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=6237184566134105275934682X=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=8w
26、2=2w4=1w1=0w6=3w7=3w5=6w3=8237184566134105275934682X=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=10237184566134105275934682X=1,2,3,4,6,7,81到10的最短路径为1，4，7，5，8，长度为10。w2=2w4=1w1=0w6=3w7=3w5=6w3=8w8=10网络优化网络优化最大流问题：给出一个带收发点的网络，其每条弧的赋权称之
27、最大流问题：给出一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发点到收为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。点的最大流量。2354671ffu25=6u42=2u45=4u23=3u13=7u34=4u46=3u36=1u65=7u57=9u67=8u12=8边的容量和流量：容量边的容量和流量：容量uijuij，流量，流量xijxij可行流：可行流：满足以下条件的流称为可行流：满足以下条件的流称为可行流：1 1、每一个节点流量平衡、每一个节点流量平衡2 2、0 xij uij0 xij uij假如假如xij=uijxij=uij，
28、边从，边从i i到到j j的方向是饱和的；的方向是饱和的；假如假如xijuijxij0 xij0，边从，边从j j到到i i的方向是不饱和的的方向是不饱和的网络优化网络优化21xij=0uij=521xij=5uij=5（2 2，1 1）是不饱和的）是不饱和的间隙为间隙为 1212=x=x1212=5=5给出一个初始的可行流给出一个初始的可行流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网络优化网络优化2354671f=0f=
29、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找到全部的不饱和边，以及各边可以调整流量的方向找到全部的不饱和边，以及各边可以调整流量的方向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调
30、整链的流量：调整链的流量：xij=xij+xij=xij+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调整流量，调整流量，f=1f=1。接着求出网络的不饱和边。接着求出网络的不饱和边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,
31、6,9=1,min 7,1,6,9=1,调整流量调整流量 xij=xij+1 xij=xij+1,f=f+1=2,f=f+1=22354671f=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调整流量，接着求出网络的不饱和边调整流量，接着求出网络的不饱和边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的不饱和
32、链的不饱和链=min 7,5,8=5,min 7,5,8=5,调整流量调整流量 xij=xij+5 xij=xij+5,f=f+5=2+5=7,f=f+5=2+5=72354671f=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调整流量，接着求出网络的不饱和边调整流量，接着求出网络的不饱和边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=
33、3=6求出一条从求出一条从1 1到到7 7的不饱和链的不饱和链=min 6,7,4,3=3,min 6,7,4,3=3,调整流量调整流量 xij=xij+3 xij=xij+3,f=f+3=7+3=10f=f+3=7+3=102354671f=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调整流量，接着求出网络的不饱和边调整流量，接着求出网络的不饱和边2354671f=10u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0 x=3x=4x=3x=
34、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+1 xij=xij+1,f=f+1=10+1=11f=f+1=10+1=112354671f=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的不饱和链，从的不饱和链
35、，从1 1起先可以到达的节点为起先可以到达的节点为1 1，2 2，3 32354671f=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最短路问题：最短路问题：给定一个运输网络，两点之间连线上的数字表示两点之间的距离，试求一条给定一个运输网络，两点之间连线上的数字表示两点之间的距离，试求一条从从A A到到B B的运输路途，使总距离最短。的运输路途，使总距离最短。可
36、将问题分为四个阶段：第一阶段，从可将问题分为四个阶段：第一阶段，从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条。条。最优解：最优解：AB3 C2 D2 EAB3 C2 D2 E动态规划动态规划阶段：将所给问题的过程，按时间或空间特征分解成相互联系的阶段，阶段：将所给问题的过程，按时间或空间特征分解成相互联系的阶段，以便按次序求每阶段的解以便按次序求每阶段的解 k k描述阶段的变量描述阶段的变量状态：表示每个阶段起先时所处的自然状
37、况或条件，描述了探讨问题的状态：表示每个阶段起先时所处的自然状况或条件，描述了探讨问题的状况。状况。sk sk状态变量状态变量 Sk Sk状态集合状态集合 S1=A,S2=B1,B2,B3,S3=C1,C2,C3,S1=A,S2=B1,B2,B3,S3=C1,C2,C3,S4=D1,D2 S4=D1,D2 动态规划中状态的性质：无后效性，即假如某个阶段状态给定之后，动态规划中状态的性质：无后效性，即假如某个阶段状态给定之后，则在这阶段以后过程的发展不受这阶段以前各阶段状态的影响。则在这阶段以后过程的发展不受这阶段以前各阶段状态的影响。决策：指在某阶段对可供选择状态的选择，描述的变量称为决策变量
38、。决策：指在某阶段对可供选择状态的选择，描述的变量称为决策变量。dk(sk)dk(sk)决策变量决策变量 Dk(sk)Dk(sk)允许决策集合允许决策集合 D2(B1)=C1,C2,C3 D2(B1)=C1,C2,C3动态规划动态规划全过程策略：由全部各阶段组成的决策函数序列全过程策略：由全部各阶段组成的决策函数序列,简称策略。简称策略。记为：记为：P1,n(s1)P1,n(s1)或或P1,n(s1)=d1(s1),d2(s2),dn(sn)P1,n(s1)=d1(s1),d2(s2),dn(sn)k k子过程策略子过程策略(后部子策略后部子策略)：由：由k k阶段起先到最终阶段结束，阶段起先
39、到最终阶段结束，组成的决策函数序列。组成的决策函数序列。Pk,n(sk)=dk(sk),dk+1(sk+1),dn(sn)Pk,n(sk)=dk(sk),dk+1(sk+1),dn(sn)最优策略：使整个问题达到最优效果的策略。最优策略：使整个问题达到最优效果的策略。P*1,n(A)=B3,C2,D2,E AB3 C2 D2 E P*1,n(A)=B3,C2,D2,E AB3 C2 D2 E允许策略集：可供选择策略的范围，用允许策略集：可供选择策略的范围，用P P表示。表示。动态规划方法就是要从允许策略集动态规划方法就是要从允许策略集P P中找出最优策略中找出最优策略 P*k,n P*k,n动
40、态规划动态规划状态转移方程：状态转移方程：本阶段状态与上一阶段状态和上一阶段决策的关系，用状态本阶段状态与上一阶段状态和上一阶段决策的关系，用状态转移方程来表示。转移方程来表示。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)阶段指标：阶段指标：衡量某阶段决策效益优劣的策略指标，如距离，衡量某阶段决策效益优劣的策略指标，如距离，成本，利润等。成本，利润等。v vk k(s(sk k,d,d
41、k 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)动态规划动态规划常见指标函数形式常见指标函数形式(分别性，递推关系分别性，递推关系)Vk,n(sk,Pk,n)=Vk,n(sk,dk,sk+1,sn+1)Vk,n(sk,Pk,n)=Vk,n(sk,dk,sk+1,sn+1)=Vk(sk,dk)+Vk+1(sk+1,Pk,n)=Vk(sk,dk)+Vk+1(sk+1,Pk,n)Vk,n(sk,Pk,n)=Vk,n
42、(sk,dk,sk+1,sn+1)Vk,n(sk,Pk,n)=Vk,n(sk,dk,sk+1,sn+1)=Vk(sk,dk)*Vk+1(sk+1,Pk,n)=Vk(sk,dk)*Vk+1(sk+1,Pk,n)最优指标函数最优指标函数:指标函数的最优值，指标函数的最优值，fk(sk)fk(sk)表示从表示从第第k k阶段状态阶段状态sksk起先接受最优策略起先接受最优策略P*k,nP*k,n到过程终止到过程终止时的最佳效益值。时的最佳效益值。fk(sk)=opt Vk,n(sk,dk,sk+1,sn+1)fk(sk)=opt Vk,n(sk,dk,sk+1,sn+1)f1(s1)f1(s1)表示
43、从第表示从第1 1阶段状态阶段状态s1s1接受最优策略接受最优策略P*1,nP*1,n到到过程终止时的最佳效益值。过程终止时的最佳效益值。动态规划动态规划动态规划的基本思想：动态规划的基本思想：1.1.多阶段决策过程划分阶段，恰当的选取状态变量、决策多阶段决策过程划分阶段，恰当的选取状态变量、决策变量和定义最优指标函数，从而将问题化为一族同类型的子变量和定义最优指标函数，从而将问题化为一族同类型的子问题逐个求解。问题逐个求解。2.2.求解时从边界条件起先，逆（或顺）过程行进方向，逐求解时从边界条件起先，逆（或顺）过程行进方向，逐段递推寻优。段递推寻优。3.3.既将当前一段与将来各段分开，又将当
44、前效益与将来效既将当前一段与将来各段分开，又将当前效益与将来效益结合起来考虑的一种最优化方法。益结合起来考虑的一种最优化方法。如何建立动态规划模型：如何建立动态规划模型：1.1.分析识别问题的多阶段特性，按时间或空间的先后依次适分析识别问题的多阶段特性，按时间或空间的先后依次适当地划分满足递推关系的若干阶段。当地划分满足递推关系的若干阶段。2.2.确定状态变量，满足可知性和无后效性。一般为累计量和确定状态变量，满足可知性和无后效性。一般为累计量和随递推过程变更的量。随递推过程变更的量。3.3.找到状态转移方程。找到状态转移方程。4.4.正确确定基本方程。正确确定基本方程。基础：最优化定理基础：
45、最优化定理作为整个过程的最优策略具有如下性质：不管在此最优策略作为整个过程的最优策略具有如下性质：不管在此最优策略上的某个状态以前的状态和决策如何，对该状态而言，以后上的某个状态以前的状态和决策如何，对该状态而言，以后全部的决策必定构成最优子策略。全部的决策必定构成最优子策略。对最短路问题而言对最短路问题而言,从最短路上任一点到终点的部分道路从最短路上任一点到终点的部分道路（最短路上的子路）也确定是从该点到终点的最短路。（最短路上的子路）也确定是从该点到终点的最短路。动态规划动态规划从最终一段起先计算，由后向前逐步推移至从最终一段起先计算，由后向前逐步推移至A A点。点。第四阶段，由第四阶段，
46、由D1D1到到E E只有一条线路，其长度只有一条线路，其长度f4(D1)=3f4(D1)=3，同理，同理f4(D2)=4f4(D2)=4；第三阶段，由第三阶段，由CjCj到到DiDi均有两种选择，即均有两种选择，即其次阶段，由其次阶段，由BjBj到到CiCi均有三种选择，即均有三种选择，即动态规划动态规划第一阶段，由第一阶段，由A A到到B B，有三种选择，即，有三种选择，即f1(A)=12f1(A)=12，说明从，说明从A A到到E E的最短距离为的最短距离为1212，最短路途的确定可按计算依次反推而，最短路途的确定可按计算依次反推而得，即得，即A-B3-C2-D2-EA-B3-C2-D2-
47、E动态规划动态规划一个著名的命题：一个串村走户的卖货郎，他从某个村庄动一个著名的命题：一个串村走户的卖货郎，他从某个村庄动身，通过若干个村庄一次且仅一次，最终仍回到原动身的村庄，身，通过若干个村庄一次且仅一次，最终仍回到原动身的村庄，问：应如何选择行走路途，能使得总的行程最短。问：应如何选择行走路途，能使得总的行程最短。设有设有n n个城市，个城市，1,2,n1,2,n。DijDij表示从表示从i i城到城到j j城的距离。城的距离。规定推销员是从城市规定推销员是从城市1 1起先的，设推销员走到起先的，设推销员走到i i城，记城，记NiNi2,3,i-1,i+1,n 2,3,i-1,i+1,n
48、 表示由表示由1 1城到城到i i城的中间城市集合。城的中间城市集合。S S表示到达表示到达i i城中途所经过的城市的集合，则有城中途所经过的城市的集合，则有S NiS Ni1 1）选取（）选取（i,Si,S）作为状态变量，表示推销员从城市）作为状态变量，表示推销员从城市1 1起先走起先走到到i i城，经过若干个城市，构成集合城，经过若干个城市，构成集合S S。2 2）最优值函数）最优值函数fk(i,S)fk(i,S)为从城市为从城市1 1起先经过起先经过k k个中间城市的个中间城市的S S集到达集到达i i城的最短路途的距离。城的最短路途的距离。货郎担问题货郎担问题（TSP问题问题trave
49、ling salesperson problem）3）递推关系式：fk(i,S)=min fk-1(j,Sj)+Dji(k=1,2,n-1.i=2,3,n.S Ni)边界条件：f0(i,)=D1i4）Pk(i,S)为最优决策函数，表示从1城起先经k个中间城市到i城的最短路途上紧挨着i城前面的那个城市。例：当推销员从例：当推销员从1城动身，经过每个城市一次且仅城动身，经过每个城市一次且仅一次，最终回到一次，最终回到1城，问按怎样的路途走，使总的城，问按怎样的路途走，使总的行程距离最短。（四个城市，其距离矩阵如下表）行程距离最短。（四个城市，其距离矩阵如下表）5）由边界条件可知：f0(i,)=D1
50、if0(2,)=D12 8，f0(3,)=D13 5，f0(4,)=D146当k=1时，即从1城起先，中间经过一个城市到达i城的最短距离是：f1(2,3)=f0(3,)+D325+9=14f1(2,4)=f0(4,)+D426+7=13f1(3,2)=f0(2,)+D238+8=16f1(3,4)=f0(4,)+D436+8=14f1(4,2)=f0(2,)+D248+5=13f1(4,3)=f0(3,)+D345+5=101i1i当当k=2时时，即即从从1城城起起先先，中中间间经经过过两两个个城城市市到到达达i城的最短距离是：城的最短距离是：f2(2,3,4)=min f1(3,4)+D32