数学建模运筹模型

数学建模运筹模型第1页，课件共82页，创作于2023年2月线性规划运输问题指派问题网络优化动态规划目录

第2页，课件共82页，创作于2023年2月例某工厂在计划期内要安排Ⅰ，Ⅱ两种产品的生产，已知生产单位产品所需的设备台时及A，B两种原材料的消耗、资源的限制，如下表。问题：工厂应分别生产多少单位Ⅰ，Ⅱ产品才能使工厂获利最多？

线性规划第3页，课件共82页，创作于2023年2月例下料问题某工厂要做100套钢架，每套用长为2.9m，2.1m，1.5m的圆钢各一根，已知原料每根长7.4m。应如何下料，可使所用原料最省？解：共可设计下列5种下料方案线性规划第4页，课件共82页，创作于2023年2月第5页，课件共82页，创作于2023年2月建模步骤：(1)确定决策变量：我们需要作出决策或者选择的量，一般情况下，题目问什么就设什么为决策变量。(2)找出约束条件：即决策变量受到的所有的约束。(3)写出目标函数：即问题所要达到的目标，并明确是求max还是min。线性规划第6页，课件共82页，创作于2023年2月例混合配料问题某糖果厂用原料1、2、3加工三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中原料1、2、3的含量、原料每月限用量、三种牌号糖果的加工费及售价，如下表所示。该厂每月如何生产才能获利最大？线性规划第7页，课件共82页，创作于2023年2月解：用i=1,2,3代表原料1,2,3,j=1,2,3代表糖果甲、乙、丙。Xij表示第j中产品中原料i的含量，则对于原料1：x11,x12,x13;对于原料2：x21,x22,x23;对于原料3：x31,x32,x33;对于甲：x11,x21,x31;对于乙：x12,x22,x32;对于丙：x13,x23,x33;目标函数：利润最大，利润=收入-原料成本-加工费约束条件：原料用量限制，含量限制线性规划第8页，课件共82页，创作于2023年2月线性规划第9页，课件共82页，创作于2023年2月求解方法：1.图解法适合含有两个决策变量的模型；

max z

=

x1+3x2 s.t. x1+x2≤6 -x1+2x2≤8

x1≥0,x2≥0可行域目标函数等值线最优解64-860x1x2线性规划第10页，课件共82页，创作于2023年2月2.单纯形法(人工变量法、对偶单纯形法)软件求解：lingo，lindo，MatlabMinf=0.4x1+1.5x2+x3+1.3x4S.t.0.3x1+3x2++1.5x4>=3200.5x1++2x3+x4>=2401.4x1++0.7x4>=420线性规划第11页，课件共82页，创作于2023年2月

将某种物资从m个产地遇到n个销地，每个产地都有一定的产量ai，i=1,2,……,m，每个销地都对物资有一定的需求量bj,j=1,2,……,n。已知从第i个产地向第j个销地运送单位物资的运价为cij，总产量等于总需求量()。如何调运物资，才能使总运费最小？设xij为从产地Ai运往销地Bj的运输量，运输问题第12页，课件共82页，创作于2023年2月

运输表：

(产销平衡的运输问题)求解方法：1.确定初始基本可行解（西北角法、最小元素法、vogal法）2.最优性检验；3.迭代求新的基本可行解。运输问题第13页，课件共82页，创作于2023年2月例某食品公司下属的三个食品厂A1、A2、A3生产食品，3个厂每月的生产能力分别为7吨、4吨、9吨，食品被运到B1、B2、B3、B4四个销售点，它们对方便食品的月需求量分别为3吨、6吨、5吨、6吨，运输表如下表，试制定最优运送方案。运输问题第14页，课件共82页，创作于2023年2月解：1.确定初始基可行解最小元素法：运输问题第15页，课件共82页，创作于2023年2月解：1.确定初始基可行解(最小元素法)初始基本可行解对应的目标函数值：f=3*4+10*3+1*3+2*1+4*6+5*3=86运输问题第16页，课件共82页，创作于2023年2月解：2.最优性检验(1)位势：

ui+vj=cij(i=1,2,……,m,j=1,2,……,n)其中cij为基本可行解中基变量对应的单位运价。注：m+n-1个方程，m+n个变量。(2)利用位势求非基变量检验数检验数计算公式：

cij-ui-vj

(3)检验数全都大于等于零时对应的解为最优解。运输问题第17页，课件共82页，创作于2023年2月位势：检验数：运输问题第18页，课件共82页，创作于2023年2月3.迭代求新基本可行解(1)负检验数中最小者对应的变量进基；(2)在运输表中找一个包含进基变量的闭回路，这个回路上其他顶点均为基变量。依次对闭回路的四个顶点标号，将顶点分为奇点格和偶点格；(3)偶点格的最小值作为调整量，所有奇点格+调整量；偶点格-调整量，即一次迭代。(4)按位势方程求新解对应的位势及检验数，判别最优性。运输问题第19页，课件共82页，创作于2023年2月闭回路：

运输问题第20页，课件共82页，创作于2023年2月迭代及新基本可行解的检验数计算：

运输问题第21页，课件共82页，创作于2023年2月

产销不平衡运输问题：1.供大于求，引入虚拟销售点，并假设它的需求量为供不应求，引入虚拟的产地，并假设它的产量为由于虚拟销地是不存在的，实际上这个差值是在产地贮存的，故从产地到虚拟销地的单位运价为0；同理，由于虚拟产地是不存在的，所以虚设的产地到各个销地的单位运价也为0.运输问题第22页，课件共82页，创作于2023年2月例2个化肥厂供应3个地区的化肥，试决定运费最小的调运方案。解：增加虚设的销地B4，销量为10，构造产销平衡的运输表。运输问题第23页，课件共82页，创作于2023年2月初始基可行解及其检验数：迭代求新基本可行解：运输问题第24页，课件共82页，创作于2023年2月

n项任务，恰好有n个人承担，由于每个人的专长不同，完成各工作的效率不同，于是产生了应指派哪个人去完成哪项，使得完成n项任务的总效率最高的问题，这类问题称为指派问题。例有一份说明书，需要译成英、日、德、俄四种文字，现有甲乙丙丁四个人，他们将说明书译成不同文字所需要的时间如下表所示，问应指派哪个人完成哪项工作，耗用的总时间最少？指派问题第25页，课件共82页，创作于2023年2月

一般地，有n项任务、n个完成人，第i人完成第j项任务的代价为cij(i,j=1,2,……,n),为了求得总代价最小的指派方案，引入0-1型变量xij,令

数学模型为

注：指派问题是0-1整数规划的特例，也是运输问题的特例，其产地和销地数均为1，各产地产量和各销地销量均为1.指派问题第26页，课件共82页，创作于2023年2月指派问题的求解方法：匈牙利法。匈牙利法基于下面的事实：如果系数矩阵的所有元素满足：cij>=0，而其中有n个位于不同行不同列的一组0元素，则只要令对应于这些0元素位置的xij=1，其余的xij=0，就得到最优解。

如则

指派问题第27页，课件共82页，创作于2023年2月求解上例：

行变换得列变换得

画出最少覆盖0元素的直线，r=4=矩阵阶数，则可以找到最优解,所需最少时间=4+4+9+11=28甲-俄语从而得到最优指派：乙-日语丙-英语丁-德语指派问题第28页，课件共82页，创作于2023年2月例分配甲、乙、丙、丁四个人去完成A、B、C、D、E五项任务，每人完成各项任务的时间如下表所示，由于任务重，人手少，考虑以下两种情况下的最优分配方案，使得完成任务的总时间最少。(1)任务E必须完成，其他4项任务可选3项完成，但甲不能做A项工作；(2)其中有一人完成2项，其他人每人完成1项。解：这是一人数与任务数不等的指派问题，若用匈牙利法求解，需作以下处理。指派问题第29页，课件共82页，创作于2023年2月(1)由于任务数大于人数，所以需要有一个虚拟的人，设为戊。因为工作E必须完成，故设戊完成E的时间为M(M为非常大的正数)，即戊不能做工作E，其余的假想时间为0，建立的效率矩阵为：

采用匈牙利解法求解过程如下：

指派问题第30页，课件共82页，创作于2023年2月(1)由于r=4<矩阵阶数=5，需要调整0元素的分布。从该矩阵可看出，r=5=矩阵阶数，因此能找到最优指派方案。甲-B乙-D丙-E丁-A戊-C（戊为虚拟人，即任务C无人完成）最少的耗时数z=29+20+32+24=105指派问题第31页，课件共82页，创作于2023年2月(2)思路：方案1：甲，【甲】，乙，丙，丁方案2：甲，乙，【乙】，丙，丁方案3：甲，乙，丙，【丙】，丁方案4：甲，乙，丙，丁，【丁】方案5：甲，【甲】，乙，【乙】，丙，【丙】，丁，【丁】，工作A，B，C，D，E，虚拟工作F，G，H。这些方案较烦琐，采用以下思路更为简便。设有虚拟人戊，他集五人的优势为一身，即戊的费用是每人的最低，戊所做的工作即为此项工作的费用最低者的工作，效率矩阵分配表为：指派问题第32页，课件共82页，创作于2023年2月采用匈牙利解法求解：对C3做0元素的最小直线覆盖，得r=5=n。结果为

甲-B乙-D丙-E丁-A戊-C但戊为虚拟人，不能真做，它做C工作是借乙(此列最小时数26是C所创业绩)的优势，应由乙来做，即乙做两件工作：D、C。指派问题第33页，课件共82页，创作于2023年2月例最大收益的最优分配问题：有5名工人完成5项不同的任务收益如表所示：

求使总收益达到最高的任务分配方案。解：这是一个寻求总收益为最大值的极大化问题，需要转化为极小化问题才能用匈牙利解法。收益矩阵B=（bij），设b=max{bij}，令cij=b-bij，C=（cij），以C为效率矩阵的极小化问题即是原最大收益的极大化问题转化而来。指派问题第34页，课件共82页，创作于2023年2月b=max{bij}=19，令cij=19-bij，C=（cij），继续对C矩阵采用匈牙利法求解，得到C的最优分配方案为即甲-D乙-B丙-E丁-A戊-C，求得的最大总收益为74.指派问题第35页，课件共82页，创作于2023年2月237184566134105275934682网络优化最短路径问题：有一批货物要从节点1运送到节点8，这两点间的通路如下图，每条弧旁边的数字表明该弧的长度。总路径越短，运费越低，为节省运输费用，应该选择怎样的运输路线？求从1到8的最短路径。第36页，课件共82页，创作于2023年2月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页，创作于2023年2月237184566134105275934682X={1,4}min{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页，创作于2023年2月237184566134105275934682X={1,2,4}min{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页，创作于2023年2月237184566134105275934682X={1,2,4,6}min{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页，创作于2023年2月237184566134105275934682X={1,2,4,6,7}min{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页，创作于2023年2月237184566134105275934682X={1,2,4,6,7}min{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页，创作于2023年2月237184566134105275934682X={1,2,3,4,6,7}min{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页，创作于2023年2月237184566134105275934682X={1,2,3,4,6,7,8}1到10的最短路径为{1，4，7，5，8}，长度为10。w2=2w4=1w1=0w6=3w7=3w5=6w3=8w8=10第44页，课件共82页，创作于2023年2月网络优化最大流问题：给出一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。2354671ffu25=6u42=2u45=4u23=3u13=7u34=4u46=3u36=1u65=7u57=9u67=8u12=8第45页，课件共82页，创作于2023年2月边的容量和流量：容量uij，流量xij可行流：

满足以下条件的流称为可行流： 1、每一个节点流量平衡 2、0≤xij≤uij如果xij=uij，边从i到j的方向是饱和的；如果xij<uij，边从i到j的方向是不饱和的；网络优化21xij=5uij=5（1，2）是饱和的21xij=3uij=5（1，2）是不饱和的间隙为12=u12-x12=5-3=2第46页，课件共82页，创作于2023年2月如果xij=0，边从j到i的方向是饱和的

（2，1）是饱和的如果xij>0，边从j到i的方向是不饱和的网络优化21xij=0uij=521xij=5uij=5（2，1）是不饱和的间隙为12=x12=5第47页，课件共82页，创作于2023年2月给出一个初始的可行流xij=02354671f=0f=0u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0x=0x=0x=0x=0x=0x=0x=0x=0x=0x=0x=0网络优化第48页，课件共82页，创作于2023年2月2354671f=0f=0u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0x=0x=0x=0x=0x=0x=0x=0x=0x=0x=0x=0找到所有的不饱和边，以及各边可以调整流量的方向第49页，课件共82页，创作于2023年2月2354671f=0f=0u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0x=0x=0x=0x=0x=0x=0x=0x=0x=0x=0=3=1=8=8x=0找到一条从1到7的不饱和链链的间隙为：=min{8,3,1,8}=1调整链的流量：xij’=xij+第50页，课件共82页，创作于2023年2月2354671f=1f=1u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0x=0x=0x=0x=0x=0x=0x=0x=1x=1x=1x=1调整流量，f=1。继续求出网络的不饱和边第51页，课件共82页，创作于2023年2月2354671f=1f=1u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0x=0x=0x=0x=0x=0x=0x=0x=1x=1x=1x=1=1=6=9=7求出一条从1到7的不饱和链=min{7,1,6,9}=1,调整流量xij’=xij+1,f’=f+1=2第52页，课件共82页，创作于2023年2月2354671f=2f=2u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=1x=0x=0x=1x=0x=0x=0x=1x=1x=1x=1x=0调整流量，继续求出网络的不饱和边第53页，课件共82页，创作于2023年2月2354671f=2f=2u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=1x=0x=0x=1x=0x=0x=0x=1x=1x=1x=1x=0=5=8=7求出一条从1到7的不饱和链=min{7,5,8}=5,调整流量xij’=xij+5,f’=f+5=2+5=7第54页，课件共82页，创作于2023年2月2354671f=7f=7u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0x=0x=1x=0x=0x=0x=6x=1x=1x=6x=0调整流量，继续求出网络的不饱和边第55页，课件共82页，创作于2023年2月2354671f=7f=7u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0x=0x=1x=0x=0x=0x=6x=1x=1x=6x=0=4=4=3=6求出一条从1到7的不饱和链=min{6,7,4,3}=3,调整流量xij’=xij+3,f’=f+3=7+3=10第56页，课件共82页，创作于2023年2月2354671f=10f=10u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0x=3x=4x=3x=0x=0x=9x=1x=1x=6x=0调整流量，继续求出网络的不饱和边第57页，课件共82页，创作于2023年2月2354671f=10u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0x=3x=4x=3x=0x=0x=9x=1x=1x=6x=0f=10=1=3=7=3求出一条从1到7的不饱和链=min{3,1,3,7}=1,调整流量xij’=xij+1,f’=f+1=10+1=11第58页，课件共82页，创作于2023年2月2354671f=11f=11u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0x=4x=5x=3x=1x=0x=9x=2x=1x=6x=0调整流量，继续求出网络的不饱和边已找不到一条从1到7的不饱和链，从1开始可以到达的节点为1，2，3第59页，课件共82页，创作于2023年2月2354671f=11u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0x=4x=5x=3x=1x=0x=9x=2x=1x=6x=0f=11已求得最大流最大流f=11，最小割集为（2,5）（3,4）（3,5）u25+u34+u35=6+4+1=11第60页，课件共82页，创作于2023年2月最短路问题：给定一个运输网络，两点之间连线上的数字表示两点之间的距离，试求一条从A到B的运输路线，使总距离最短。可将问题分为四个阶段：第一阶段，从A到B；第二阶段，从B到C；第三阶段，从C到D；第四阶段，从D到E。完全枚举：3*3*2*1=24条。最优解：A→B3→C2→D2→E动态规划第61页，课件共82页，创作于2023年2月阶段：将所给问题的过程，按时间或空间特征分解成相互联系的阶段，以便按次序求每阶段的解

k——描述阶段的变量状态：表示每个阶段开始时所处的自然状况或条件，描述了研究问题的状况。

sk——状态变量Sk——状态集合S1={A},S2={B1,B2,B3},S3={C1,C2,C3},S4={D1,D2}

动态规划中状态的性质：无后效性，即如果某个阶段状态给定之后，则在这阶段以后过程的发展不受这阶段以前各阶段状态的影响。决策：指在某阶段对可供选择状态的选择，描述的变量称为决策变量。

dk(sk)——决策变量Dk(sk)——允许决策集合D2(B1)={C1,C2,C3}动态规划第62页，课件共82页，创作于2023年2月全过程策略：由所有各阶段组成的决策函数序列,简称策略。记为：P1,n(s1)或P1,n(s1)={d1(s1),d2(s2),……,dn(sn)}k子过程策略(后部子策略)：由k阶段开始到最后阶段结束，组成的决策函数序列。Pk,n(sk)={dk(sk),dk+1(sk+1),……,dn(sn)}最优策略：使整个问题达到最优效果的策略。P*1,n(A)={B3,C2,D2

,E}A→B3→C2→D2→E允许策略集：可供选择策略的范围，用P表示。动态规划方法就是要从允许策略集P中找出最优策略P*k,n动态规划第63页，课件共82页，创作于2023年2月状态转移方程：本阶段状态与上一阶段状态和上一阶段决策的关系，用状态转移方程来表示。

sk+1=Tk(sk,dk)该方程描述了由第k阶段到第k+1阶段的状态转移规律，又称为状态转移函数。sk+1=dk(sk)阶段指标：衡量某阶段决策效益优劣的策略指标，如距离，成本，利润等。vk(sk,dk)指标函数：衡量所选定策略优劣的数量指标。Vk,n(sk,Pk,n)=Vk,n(sk,dk,sk+1,……,sn+1)动态规划第64页，课件共82页，创作于2023年2月常见指标函数形式(分离性，递推关系)Vk,n(sk,Pk,n)=Vk,n(sk,dk,sk+1,……,sn+1)=Vk(sk,dk)+Vk+1(sk+1,Pk,n)Vk,n(sk,Pk,n)=Vk,n(sk,dk,sk+1,……,sn+1)=Vk(sk,dk)*Vk+1(sk+1,Pk,n)最优指标函数:指标函数的最优值，fk(sk)表示从第k阶段状态sk开始采用最优策略P*k,n到过程终止时的最佳效益值。fk(sk)=optVk,n(sk,dk,sk+1,……,sn+1)f1(s1)表示从第1阶段状态s1采用最优策略P*1,n到过程终止时的最佳效益值。动态规划第65页，课件共82页，创作于2023年2月动态规划的基本思想：1.多阶段决策过程划分阶段，恰当的选取状态变量、决策变量和定义最优指标函数，从而将问题化为一族同类型的子问题逐个求解。2.求解时从边界条件开始，逆（或顺）过程行进方向，逐段递推寻优。3.既将当前一段与未来各段分开，又将当前效益与未来效益结合起来考虑的一种最优化方法。如何建立动态规划模型：1.分析识别问题的多阶段特性，按时间或空间的先后顺序适当地划分满足递推关系的若干阶段。2.确定状态变量，满足可知性和无后效性。一般为累计量和随递推过程变化的量。3.找到状态转移方程。4.正确确定基本方程。第66页，课件共82页，创作于2023年2月基础：最优化定理作为整个过程的最优策略具有如下性质：不管在此最优策略上的某个状态以前的状态和决策如何，对该状态而言，以后所有的决策必定构成最优子策略。对最短路问题而言,从最短路上任一点到终点的部分道路（最短路上的子路）也一定是从该点到终点的最短路。动态规划第67页，课件共82页，创作于2023年2月从最后一段开始计算，由后向前逐步推移至A点。第四阶段，由D1到E只有一条线路，其长度f4(D1)=3，同理f4(D2)=4；第三阶段，由Cj到Di均有两种选择，即第二阶段，由Bj到Ci均有三种选择，即动态规划第68页，课件共82页，创作于2023年2月第一阶段，由A到B，有三种选择，即f1(A)=12，说明从A到E的最短距离为12，最短路线的确定可按计算顺序反推而得，即A-B3-C2-D2-E动态规划第69页，课件共82页，创作于2023年2月一个著名的命题：一个串村走户的卖货郎，他从某个村庄出发，通过若干个村庄一次且仅一次，最后仍回到原出发的村庄，问：应如何选择行走路线，能使得总的行程最短。设有n个城市，1,2,…,n。Dij表示从i城到j城的距离。规定推销员是从城市1开始的，设推销员走到i城，记Ni＝{2,3,…,i-1,i+1,…,n}表示由1城到i城的中间城市集合。S表示到达i城中途所经过的城市的集合，则有SNi1）选取（i,S）作为状态变量，表示推销员从城市1开始走到i城，经过若干个城市，构成集合S。2）最优值函数fk(i,S)为从城市1开始经过k个中间城市的S集到达i城的最短路线的距离。货郎担问题（TSP问题——travelingsalespersonproblem）第70页，课件共82页，创作于2023年2月3）递推关系式：fk(i,S)=min[fk-1(j,S\{j})+Dji](k=1,2,…,n-1.i=2,3…,n.SNi)边界条件：f0(i,Ø)=D1i4）

Pk(i,S)为最优决策函数，表示从1城开始经k个中间城市到i城的最短路线上紧挨着i城前面的那个城市。例：当推销员从1城出发，经过每个城市一次且仅一次，最后回到1城，问按怎样的路线走，使总的行程距离最短。（四个城市，其距离矩阵如下表）第71页，课件共82页，创作于2023年2月5）由边界条件可知：f0(i,Ø)=D1if0(2,Ø)=D12＝8，f0(3,Ø)=D13＝5，f0(4,Ø)=D14＝6当k=1时，即从1城开始，中间经过一个城市到达i城的最短距离是：f1(2,{3})=f0(3,Ø)+D32＝5+9=14f1(2,{4})=f0(4,Ø)+D42＝6+7=13f1(3,{2})=f0(2,Ø)+D23＝8+8=16f1(3,{4})=f0(4,Ø)+D43＝6+8=14f1(4,{2})=f0(2,Ø)+D24＝8+5=13f1(4,{3})=f0(3,Ø)+D34＝5+5=101i1i第72页，课件共82页，创作于2023年2月当k=2时，即从1城开始，中间经过两个城市到达i城的最短距离是：f2(2,{3,4})=min[f1(3,{4})+D32

f1(4,{3})+D42]=min[14+9,10+7]=17P2(2,{3,4})=41if2(3,{2,4})=min[f1(2,{4})+D23f1(4,{2})+D43]=min[13+8,13+8]=21P2(3,{2,4})=2或4f2(4,{3,2})=min[f1(3,{2})+D34f1(2,{3})+D24]=min[16+5,14+5]=19P2(4,{3,2})=2f1(3,{4})=14f1(4,{3})=10第73页，课件共82页，创作于2023年2月当k=3时，即从1城开始，中间经过三个城市到达1城的最短距