数学建模——运筹模型1.ppt

数学建模与运筹模型数学建模与运筹模型上海海事大学上海海事大学 邓伟邓伟线性规划线性规划运输问题运输问题指派问题指派问题网络优化网络优化动态规划动态规划目录目录 例例 某工厂在计划期内要安排某工厂在计划期内要安排，两种产品的生产，已知生产两种产品的生产，已知生产 单位产品所需的设备台时及单位产品所需的设备台时及A A，B B两种原材料的消耗、资源的两种原材料的消耗、资源的限制，如下表。问题：工厂应分别生产多少单位限制，如下表。问题：工厂应分别生产多少单位，产品产品才能使工厂获利最多？才能使工厂获利最多？线性规划线性规划例例 下料问题下料问题 某工厂要做某工厂要做100100套钢架，每套用长为套钢架，每套用长为2.9m2.9m，2.1m2.1m，1.5m1.5m的圆钢各一根，已知原料每根长的圆钢各一根，已知原料每根长7.4m7.4m。应如何下料，可使所用原料最省？。应如何下料，可使所用原料最省？解：共可设计下列解：共可设计下列5 5种下料方案种下料方案线性规划线性规划建模步骤：建模步骤：(1)(1)确定决策变量：我们需要作出决策或者选择的量，确定决策变量：我们需要作出决策或者选择的量，一般情况下，题目问什么就设什么为决策变量。一般情况下，题目问什么就设什么为决策变量。(2)(2)找出约束条件：即决策变量受到的所有的约束。找出约束条件：即决策变量受到的所有的约束。(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代表糖果甲、乙、丙。代表糖果甲、乙、丙。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;目标函数：利润最大，利润目标函数：利润最大，利润=收入收入-原料成本原料成本-加工费加工费 约束条件：原料用量限制，含量限制约束条件：原料用量限制，含量限制线性规划线性规划线性规划线性规划求解方法：求解方法：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.5x4=320 0.5x1+2x3+x4=240 1.4x1+0.7x4=420 线性规划线性规划 将某种物资从将某种物资从m m个产地遇到个产地遇到n n个销地，每个产地都有一定个销地，每个产地都有一定的产量的产量a ai i，i=1,2,mi=1,2,m，每个销地都对物资有一定的需求，每个销地都对物资有一定的需求量量b bj j,j=1,2,n,j=1,2,n。已知从第。已知从第i i个产地向第个产地向第j j个销地运送单个销地运送单位物资的运价为位物资的运价为c cijij，总产量等于总需求量，总产量等于总需求量()()。如。如何调运物资，才能使总运费最小？何调运物资，才能使总运费最小？设设x xijij为从产地为从产地A Ai i运往销地运往销地B Bj j的运输量，的运输量，运输问题运输问题 运输表：运输表：(产销平衡的运输问题产销平衡的运输问题)求解方法：求解方法：1.1.确定初始基本可行解（西北角法、最小元素法、确定初始基本可行解（西北角法、最小元素法、vogalvogal法）法）2.2.最优性检验；最优性检验；3.3.迭代求新的基本可行解。迭代求新的基本可行解。运输问题运输问题例例 某食品公司下属的三个食品厂某食品公司下属的三个食品厂A1A1、A2A2、A3A3生产食品，生产食品，3 3个厂个厂每月的生产能力分别为每月的生产能力分别为7 7吨、吨、4 4吨、吨、9 9吨，食品被运到吨，食品被运到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=86f=3*4+10*3+1*3+2*1+4*6+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)检验数全都大于等于零时对应的解为最优解。检验数全都大于等于零时对应的解为最优解。运输问题运输问题位势：位势：检验数：检验数：运输问题运输问题3.3.迭代求新基本可行解迭代求新基本可行解(1)(1)负检验数中最小者对应的变量进基；负检验数中最小者对应的变量进基；(2)(2)在运输表中找一个包含进基变量的闭回路，这个回路上其在运输表中找一个包含进基变量的闭回路，这个回路上其他顶点均为基变量。依次对闭回路的四个顶点标号，将顶他顶点均为基变量。依次对闭回路的四个顶点标号，将顶点分为奇点格和偶点格；点分为奇点格和偶点格；(3)(3)偶点格的最小值作为调整量，所有奇点格偶点格的最小值作为调整量，所有奇点格+调整量；偶点调整量；偶点格格-调整量，即一次迭代。调整量，即一次迭代。(4)(4)按位势方程求新解对应的位势及检验数，判别最优性。按位势方程求新解对应的位势及检验数，判别最优性。运输问题运输问题闭回路：闭回路：运输问题运输问题迭代及新基本可行解的检验数计算：迭代及新基本可行解的检验数计算：运输问题运输问题 产销不平衡运输问题：产销不平衡运输问题：1.1.供大于求，引入虚拟销售点，并假设它的需求量为供大于求，引入虚拟销售点，并假设它的需求量为2.2.供不应求，引入虚拟的产地，并假设它的产量为供不应求，引入虚拟的产地，并假设它的产量为 由于虚拟销地是不存在的，实际上这个差值是在产地贮存由于虚拟销地是不存在的，实际上这个差值是在产地贮存的，故从产地到虚拟销地的单位运价为的，故从产地到虚拟销地的单位运价为0 0；同理，由于虚拟产地是不存在的，所以虚设的产地到各个同理，由于虚拟产地是不存在的，所以虚设的产地到各个销地的单位运价也为销地的单位运价也为0.0.运输问题运输问题例例 2 2个化肥厂供应个化肥厂供应3 3个地区的化肥，试决定运费最小的调运方案。个地区的化肥，试决定运费最小的调运方案。解：增加虚设的销地解：增加虚设的销地B4B4，销量为，销量为1010，构造产销平衡的运输表。，构造产销平衡的运输表。运输问题运输问题初始基可行解及其检验数：初始基可行解及其检验数：迭代求新基本可行解：迭代求新基本可行解：运输问题运输问题 n n项任务，恰好有项任务，恰好有n n个人承担，由于每个人的专长不同，完个人承担，由于每个人的专长不同，完成各工作的效率不同，于是产生了应指派哪个人去完成哪项，成各工作的效率不同，于是产生了应指派哪个人去完成哪项，使得完成使得完成n n项任务的总效率最高的问题，这类问题称为指派问项任务的总效率最高的问题，这类问题称为指派问题。题。例例 有一份说明书，需要译成英、日、德、俄四种文字，现有有一份说明书，需要译成英、日、德、俄四种文字，现有甲乙丙丁四个人，他们将说明书译成不同文字所需要的时间甲乙丙丁四个人，他们将说明书译成不同文字所需要的时间如下表所示，问应指派哪个人完成哪项工作，耗用的总时间如下表所示，问应指派哪个人完成哪项工作，耗用的总时间最少？最少？指派问题指派问题 一般地，有一般地，有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.指派问题指派问题指派问题的求解方法：匈牙利法。指派问题的求解方法：匈牙利法。匈牙利法基于下面的事实：如果系数矩阵的所有元素满足：匈牙利法基于下面的事实：如果系数矩阵的所有元素满足：c cijij=0=0，而其中有，而其中有n n个位于不同行不同列的一组个位于不同行不同列的一组0 0元素，则只要元素，则只要令对应于这些令对应于这些0 0元素位置的元素位置的x xijij=1=1，其余的，其余的x xijij=0=0，就得到最优解。，就得到最优解。如如 则则 指派问题指派问题求解上例：求解上例：行变换得行变换得 列变换得列变换得 画出最少覆盖画出最少覆盖0 0元素的直线，元素的直线，r=4=r=4=矩阵阶数，矩阵阶数，则可以找到最优解则可以找到最优解,所需最少时间所需最少时间=4+4+9+11=28=4+4+9+11=28 甲甲-俄语俄语 从而得到最优指派：乙从而得到最优指派：乙-日语日语 丙丙-英语英语 丁丁-德语德语 指派问题指派问题例例 分配甲、乙、丙、丁四个人去完成分配甲、乙、丙、丁四个人去完成A A、B B、C C、D D、E E五项任务，五项任务，每人完成各项任务的时间如下表所示，由于任务重，人手少，每人完成各项任务的时间如下表所示，由于任务重，人手少，考虑以下两种情况下的最优分配方案，使得完成任务的总时考虑以下两种情况下的最优分配方案，使得完成任务的总时间最少。间最少。(1)(1)任务任务E E必须完成，其他必须完成，其他4 4项任务可选项任务可选3 3项完成，但甲不能做项完成，但甲不能做A A项工作；项工作；(2)(2)其中有一人完成其中有一人完成2 2项，其他人每人完成项，其他人每人完成1 1项。项。解：这是一人数与任务数不等的指派问题，若用匈牙利法求解，解：这是一人数与任务数不等的指派问题，若用匈牙利法求解，需作以下处理。需作以下处理。指派问题指派问题(1)(1)由于任务数大于人数，所以需要有一个虚拟的人，设为戊。由于任务数大于人数，所以需要有一个虚拟的人，设为戊。因为工作因为工作E E必须完成，故设戊完成必须完成，故设戊完成E E的时间为的时间为M(MM(M为非常大的正为非常大的正数数)，即戊不能做工作，即戊不能做工作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+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。这些方案较烦琐，采用以下思路更为简便。这些方案较烦琐，采用以下思路更为简便。设有虚拟人戊，他集五人的优势为一身，即戊的费用是每人的设有虚拟人戊，他集五人的优势为一身，即戊的费用是每人的最低，戊所做的工作即为此项工作的费用最低者的工作，效最低，戊所做的工作即为此项工作的费用最低者的工作，效率矩阵分配表为：率矩阵分配表为：指派问题指派问题 采用匈牙利解法求解：采用匈牙利解法求解：对对C C3 3做做0 0元素的最小直线覆盖，得元素的最小直线覆盖，得r=5=nr=5=n。结果为。结果为 甲甲-B-B 乙乙-D-D 丙丙-E-E 丁丁-A-A 戊戊-C-C 但戊为虚拟人，不能真做，它做但戊为虚拟人，不能真做，它做C C工作是借乙工作是借乙(此列最小时数此列最小时数2626是是C C所创业所创业绩绩)的优势，应由乙来做，即乙做两件工作：的优势，应由乙来做，即乙做两件工作：D D、C C。指派问题指派问题例例 最大收益的最优分配问题：有最大收益的最优分配问题：有5 5名工人完成名工人完成5 5项不同的任务收项不同的任务收 益如表所示：益如表所示：求使总收益达到最高的任务分配方案。求使总收益达到最高的任务分配方案。解：这是一个寻求总收益为最大值的极大化问题，需要转化为解：这是一个寻求总收益为最大值的极大化问题，需要转化为极小化问题才能用匈牙利解法。极小化问题才能用匈牙利解法。收益矩阵收益矩阵B=B=（b bijij），设），设b=maxbb=maxbijij，令，令c cijij=b-b=b-bijij ，C=C=（c cijij），），以以C C为效率矩阵的极小化问题即是原最大收益的极大化问题转为效率矩阵的极小化问题即是原最大收益的极大化问题转化而来。化而来。指派问题指派问题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，求得的最大总收益为，求得的最大总收益为74.74.指派问题指派问题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,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,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=8w2=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网络优化网络优化最大流问题：给出一个带收发点的网络，其每条弧的赋权称之最大流问题：给出一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发点到收为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。点的最大流量。2354671ffu25=6u42=2u45=4u23=3u13=7u34=4u46=3u36=1u65=7u57=9u67=8u12=8边的容量和流量：容量边的容量和流量：容量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给出一个初始的可行流给出一个初始的可行流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=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调整链的流量：调整链的流量：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,6,9=1,min 7,1,6,9=1,调整流量调整流量 xij=xij+1xij=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的不饱和链的不饱和链=min 7,5,8=5,min 7,5,8=5,调整流量调整流量 xij=xij+5xij=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=3=6求出一条从求出一条从1 1到到7 7的不饱和链的不饱和链=min 6,7,4,3=3,min 6,7,4,3=3,调整流量调整流量 xij=xij+3xij=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=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+1xij=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的不饱和链，从的不饱和链，从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的运输路线，使总距离最短。的运输路线，使总距离最短。可将问题分为四个阶段：第一阶段，从可将问题分为四个阶段：第一阶段，从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动态规划动态规划阶段：阶段：将所给问题的过程，按时间或空间特征分解成相互联系的阶段，将所给问题的过程，按时间或空间特征分解成相互联系的阶段，以便按次序求每阶段的解以便按次序求每阶段的解 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 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 动态规划动态规划全过程策略：全过程策略：由所有各阶段组成的决策函数序列由所有各阶段组成的决策函数序列,简称简称策略策略。记为：记为：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)最优策略：最优策略：使整个问题达到最优效果的策略。使整个问题达到最优效果的策略。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动态规划动态规划状态转移方程：状态转移方程：本阶段状态与上一阶段状态和上一阶段决策的关系，用状态本阶段状态与上一阶段状态和上一阶段决策的关系，用状态转移方程来表示。转移方程来表示。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,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)动态规划动态规划常见指标函数形式常见指标函数形式(分离性，递推关系分离性，递推关系)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 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到过到过程终止时的最佳效益值。程终止时的最佳效益值。动态规划动态规划动态规划的基本思想：动态规划的基本思想：1.1.多阶段决策过程划分阶段，恰当的选取状态变量、决策多阶段决策过程划分阶段，恰当的选取状态变量、决策变量和定义最优指标函数，从而将问题化为一族同类型的子变量和定义最优指标函数，从而将问题化为一族同类型的子问题逐个求解。问题逐个求解。2.2.求解时从边界条件开始，逆（或顺）过程行进方向，逐求解时从边界条件开始，逆（或顺）过程行进方向，逐段递推寻优。段递推寻优。3.3.既将当前一段与未来各段分开，又将当前效益与未来效既将当前一段与未来各段分开，又将当前效益与未来效益结合起来考虑的一种最优化方法。益结合起来考虑的一种最优化方法。如何建立动态规划模型：如何建立动态规划模型：1.1.分析识别问题的多阶段特性，按时间或空间的先后顺序适分析识别问题的多阶段特性，按时间或空间的先后顺序适当地划分当地划分满足递推关系满足递推关系的若干阶段。的若干阶段。2.2.确定状态变量，满足确定状态变量，满足可知性可知性和和无后效性无后效性。一般为累计量和。一般为累计量和随递推过程变化的量。随递推过程变化的量。3.3.找到状态转移方程。找到状态转移方程。4.4.正确确定基本方程。正确确定基本方程。基础：基础：最优化定理最优化定理作为整个过程的最优策略具有如下性质：不管在此最优策略作为整个过程的最优策略具有如下性质：不管在此最优策略上的某个状态以前的状态和决策如何，对该状态而言，以后上的某个状态以前的状态和决策如何，对该状态而言，以后所有的决策必定构成最优子策略。所有的决策必定构成最优子策略。对最短路问题而言对最短路问题而言,从最短路上任一点到终点的部分道路从最短路上任一点到终点的部分道路（最短路上的子路）也一定是从该点到终点的最短路。（最短路上的子路）也一定是从该点到终点的最短路。动态规划动态规划从最后一段开始计算，由后向前逐步推移至从最后一段开始计算，由后向前逐步推移至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均有三种选择，即均有三种选择，即动态规划动态规划第一阶段，由第一阶段，由A A到到B B，有三种选择，即，有三种选择，即f f1 1(A)=12(A)=12，说明从，说明从A A到到E E的最短距离为的最短距离为1212，最短路线的确定可按，最短路线的确定可按计算顺序反推而得，即计算顺序反推而得，即A-BA-B3 3-C-C2 2-D-D2 2-E-E动态规划动态规划一个著名的命题：一个串村走户的卖货郎，他从某个村庄出一个著名的命题：一个串村走户的卖货郎，他从某个村庄出发，通过若干个村庄一次且仅一次，最后仍回到原出发的村庄，发，通过若干个村庄一次且仅一次，最后仍回到原出发的村庄，问：应如何选择行走路线，能使得总的行程最短。问：应如何选择行走路线，能使得总的行程最短。设有设有n个城市，个城市，1,2,n。Dij表示从表示从i城到城到j城的距离。城的距离。规规定定推推销销员员是是从从城城市市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城的最短路线的距离。城的最短路线的距离。货郎担问题货郎担问题（TSP问题问题traveling 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,)=D1if0(2,)=D128，f0(3,)=D135，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 f1(4,3)+D42 =min14+9,10+7=