数学建模运筹模型课件.ppt

1、? 线性规划? 运输问题? 指派问题? 网络优化? 动态规划目录例 某工厂在计划期内要安排，两种产品的生产，已知生产单位产品所需的设备台时及A，B两种原材料的消耗、资源的限制，如下表。问题：工厂应分别生产多少单位，产品才能使工厂获利最多？线性规划例 下料问题 某工厂要做100套钢架，每套用长为2.9m ，2.1m ，1.5m的圆钢各一根，已知原料每根长7.4m 。应如何下料，可使所用原料最省？解：共可设计下列5种下料方案线性规划建模步骤：(1)确定决策变量：我们需要作出决策或者选择的量，一般情况下，题目问什么就设什么为决策变量。(2)找出约束条件：即决策变量受到的所有的约束。(3)写出目标函数

2、：即问题所要达到的目标，并明确是求max 还是min。线性规划例 混合配料问题 某糖果厂用原料1、2、3加工三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中原料1、2、3的含量、原料每月限用量、三种牌号糖果的加工费及售价，如下表所示。该厂每月如何生产才能获利最大？线性规划解：用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;对于丙：x1

3、3, x23, x33;目标函数：利润最大，利润=收入-原料成本-加工费约束条件：原料用量限制，含量限制线性规划线性规划求解方法：1.图解法 适合含有两个决策变量的模型；maxz = x1+3x2s.t.x1+ x26-x1+2x28x1 0, x20可行域目标函数等值线最优解64-860 x1x2线性规划2.单纯形法(人工变量法、对偶单纯形法 )软件求解：lingo，lindo ，MatlabMin f= 0.4x1+1.5x2+x3+1.3x4 S.t. 0.3x1+3x2 + +1.5x4=3200.5x1+ +2x3+x4 =240 1.4x1+ +0.7x4=420 线性规划将某种物

4、资从m个产地遇到n个销地，每个产地都有一定的产量ai，i=1,2, ,m，每个销地都对物资有一定的需求量bj,j=1,2, ,n。已知从第i个产地向第j个销地运送单位物资的运价为cij，总产量等于总需求量( )。如何调运物资，才能使总运费最小？设xij为从产地Ai运往销地Bj的运输量，运输问题11mnijijab?运输表：(产销平衡的运输问题)求解方法：1.确定初始基本可行解（西北角法、最小元素法、vogal法）2.最优性检验；3.迭代求新的基本可行解。运输问题例 某食品公司下属的三个食品厂A1、A2、A3生产食品，3个厂每月的生产能力分别为7吨、4吨、9吨，食品被运到B1、B2、B3、B4四

5、个销售点，它们对方便食品的月需求量分别为3吨、6吨、5吨、6吨，运输表如下表，试制定最优运送方案。运输问题 B1 B2 B3 B4 产量 ai A1 3 11 3 10 7 A2 1 9 2 8 4 A3 7 4 10 5 9 需求量 bj 3 6 5 6 20 解：1.确定初始基可行解最小元素法：运输问题 B1 B2 B3 B4 ai 3 11 3 10 A1 x11 x12 x13 x14 7 1 9 2 8 A2 x21 x22 x23 x24 4 7 4 10 5 A3 x31 x32 x33 x34 9 bj 3 6 5 6 20 解：1.确定初始基可行解(最小元素法)初始基本可行解

6、对应的目标函数值：f=3*4+10*3+1*3+2*1+4*6+5*3=86运输问题 B1 B2 B3 B4 ai 3 11 3 10 A1 4 3 7 1 9 2 8 A2 3 1 4 7 4 10 5 A3 6 3 9 bj 3 6 5 6 20 解：2.最优性检验(1)位势：ui+vj =cij (i=1,2, ,m,j=1,2, ,n)其中cij 为基本可行解中基变量对应的单位运价。注：m+n-1个方程，m+n个变量。(2)利用位势求非基变量检验数检验数计算公式：cij -ui-vj(3)检验数全都大于等于零时对应的解为最优解。运输问题位势：检验数： -3 4 -2 5 ai 3 11

7、 3 10 5 1 2 4 3 7 1 9 2 8 4 3 1 1 -1 4 7 4 10 5 0 10 6 12 3 9 bj 3 6 5 6 20 运输问题 v1 v2 v3 v4 ai 3 11 3 10 u1 4 3 7 1 9 2 8 u2 3 1 4 7 4 10 5 u3 6 3 9 bj 3 6 5 6 20 3.迭代求新基本可行解(1)负检验数中最小者对应的变量进基；(2)在运输表中找一个包含进基变量的闭回路，这个回路上其他顶点均为基变量。依次对闭回路的四个顶点标号，将顶点分为奇点格和偶点格；(3)偶点格的最小值作为调整量，所有奇点格+调整量；偶点格-调整量，即一次迭代。(4

8、)按位势方程求新解对应的位势及检验数，判别最优性。运输问题闭回路：运输问题 ai 3 11 3 10 4 3 7 1 9 2 8 3 1 4 7 4 10 5 6 3 9 bj 3 6 5 6 20 迭代及新基本可行解的检验数计算：运输问题 -2 4 -2 5 ai 3 11 3 10 5 0 2 5 2 7 1 9 2 8 3 3 2 1 1 4 7 4 10 5 0 9 6 12 3 9 bj 3 6 5 6 20 产销不平衡运输问题：1. 供大于求，引入虚拟销售点，并假设它的需求量为2.供不应求，引入虚拟的产地，并假设它的产量为由于虚拟销地是不存在的，实际上这个差值是在产地贮存的，故从产

9、地到虚拟销地的单位运价为0；同理，由于虚拟产地是不存在的，所以虚设的产地到各个销地的单位运价也为0.11mnijijab?运输问题11mnijijab?11mnijijab?11nmjijiba?例 2个化肥厂供应3个地区的化肥，试决定运费最小的调运方案。解：增加虚设的销地B4，销量为10，构造产销平衡的运输表。 B1 B2 B3 产量 ai A1 2 7 4 25 A2 3 6 5 35 需求量 bj 10 25 15 5060 运输问题 B1 B2 B3 B4 ai 2 7 4 0 A1 25 3 6 5 0 A2 35 bj 10 25 15 10 60 初始基可行解及其检验数：迭代求新

10、基本可行解： 0 3 2 -2 ai 2 7 4 0 2 10 2 5 10 25 3 6 5 0 3 0 25 10 -1 35 bj 10 25 15 10 60 运输问题 0 3 2 -3 ai 2 7 4 0 2 10 2 15 1 25 3 6 5 0 3 0 25 0 10 35 bj 10 25 15 10 60 n项任务，恰好有n个人承担，由于每个人的专长不同，完成各工作的效率不同，于是产生了应指派哪个人去完成哪项，使得完成n项任务的总效率最高的问题，这类问题称为指派问题。例 有一份说明书，需要译成英、日、德、俄四种文字，现有甲乙丙丁四个人，他们将说明书译成不同文字所需要的时间

11、如下表所示，问应指派哪个人完成哪项工作，耗用的总时间最少？指派问题 英语 日语 德语 俄语 甲 2 15 13 4 乙 10 4 14 15 丙 9 14 16 13 丁 7 8 11 9 一般地，有n项任务、n个完成人，第i人完成第j项任务的代价为cij(i,j=1,2,n),为了求得总代价最小的指派方案，引入0-1型变量xij ,令数学模型为注：指派问题是0-1整数规划的特例，也是运输问题的特例，其产地和销地数均为1，各产地产量和各销地销量均为1.指派问题? 指派问题的求解方法：匈牙利法。? 匈牙利法基于下面的事实：如果系数矩阵的所有元素满足：cij=0，而其中有n个位于不同行不同列的一组

12、0元素，则只要令对应于这些0元素位置的xij=1，其余的xij=0，就得到最优解。如则指派问题求解上例：行变换得列变换得画出最少覆盖0元素的直线，r=4=矩阵阶数，则可以找到最优解,所需最少时间=4+4+9+11=28甲-俄语从而得到最优指派：乙-日语丙-英语丁-德语指派问题 英语 日语 德语 俄语 甲 2 15 13 4 乙 10 4 14 15 丙 9 14 16 13 丁 7 8 11 9 例 分配甲、乙、丙、丁四个人去完成A、B、C、D、E五项任务，每人完成各项任务的时间如下表所示，由于任务重，人手少，考虑以下两种情况下的最优分配方案，使得完成任务的总时间最少。(1)任务E必须完成，其

13、他4项任务可选3项完成，但甲不能做A项工作；(2)其中有一人完成2项，其他人每人完成1项。解：这是一人数与任务数不等的指派问题，若用匈牙利法求解，需作以下处理。指派问题 A B C D E 甲 25 29 31 42 37 乙 39 38 26 20 33 丙 34 27 28 40 32 丁 24 42 36 23 45 (1)由于任务数大于人数，所以需要有一个虚拟的人，设为戊。因为工作E必须完成，故设戊完成E的时间为M(M为非常大的正数)，即戊不能做工作E，其余的假想时间为0，建立的效率矩阵为：采用匈牙利解法求解过程如下：指派问题 A B C D E 甲 M 29 31 42 37 乙 3

14、9 38 26 20 33 丙 34 27 28 40 32 丁 24 42 36 23 45 戊 0 0 0 0 M (1)由于r=4矩阵阶数=5，需要调整0元素的分布。从该矩阵可看出，r=5=矩阵阶数，因此能找到最优指派方案。甲-B乙-D丙-E丁-A戊-C（戊 为虚拟人，即任务C无人完成）最少的耗时数 z=29+20+32+24=105 指派问题(2)思路：方案1：甲，【甲】，乙，丙，丁方案2：甲，乙，【乙】，丙，丁方案3：甲，乙，丙，【丙】，丁方案4：甲，乙，丙，丁，【丁】方案5：甲，【甲】，乙，【乙】，丙，【丙】，丁，【丁】，工作A，B，C，D，E，虚拟工作F，G，H。这些方案较烦琐，

15、采用以下思路更为简便。设有虚拟人戊，他集五人的优势为一身，即戊的费用是每人的最低，戊所做的工作即为此项工作的费用最低者的工作，效率矩阵分配表为：指派问题采用匈牙利解法求解：对C3做0元素的最小直线覆盖，得r=5=n。结果为甲-B 乙-D 丙-E 丁-A 戊-C但戊为虚拟人，不能真做，它做C工作是借乙(此列最小时数26是C所创业绩)的优势，应由乙来做，即乙做两件工作：D、C。指派问题 A B C D E 甲 25 29 31 42 37 乙 39 38 26 20 33 丙 34 27 28 40 32 丁 24 42 36 23 45 戊 24 27 26 20 32 例 最大收益的最优分配问

16、题：有5名工人完成5项不同的任务收益如表所示：求使总收益达到最高的任务分配方案。解：这是一个寻求总收益为最大值的极大化问题，需要转化为极小化问题才能用匈牙利解法。收益矩阵B=（bij），设b=maxbij，令cij=b-bij，C=（cij），以C为效率矩阵的极小化问题即是原最大收益的极大化问题转化而来。指派问题 A B C D E 甲 10 5 9 18 11 乙 13 19 6 12 14 丙 3 2 4 4 5 丁 18 9 12 17 15 戊 11 6 14 19 10 b=maxbij=19，令cij=19-bij，C=（cij），继续对C矩阵采用匈牙利法求解，得到C的最优分配方案

17、为即 甲-D 乙-B 丙-E 丁-A 戊-C ，求得的最大总收益为74.指派问题237184566134105275934682网络优化最短路径问题：有一批货物要从节点1 运送到节点8 ，这两点间的通路如下图，每条弧旁边的数字表明该弧的长度。总路径越短，运费越低，为节省运输费用，应该选择怎样的运输路线？求从1到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,c

18、42,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=

19、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=823718456613410527593468

20、2X=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=2u

21、45=4u23=3u13=7u34=4u46=3u36=1u65=7u57=9u67=8u12=8边的容量和流量：容量uij，流量xij可行流：满足以下条件的流称为可行流：1、每一个节点流量平衡2、0 xijuij如果xij=uij，边从i到j的方向是饱和的；如果xij0，边从j到i的方向是不饱和的网络优化21xij=0uij=521xij=5uij=5（2，1）是不饱和的间隙为?12=x12=5给出一个初始的可行流xij=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

22、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到7的不饱和链链的间隙为：? = min8,3,1,8=1调整链的流量：xij =xij+ ?235467

23、1f=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=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到7的不饱和链?=min 7,1,6,9=1, 调整流量 xij =xij+1, f =f+1=22354671f=2f=2u=6u=2u=4u=3u=7u=4u=

24、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, 调整流量 xij =xij+5, 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=

25、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到7的不饱和链?=min 6,7,4,3=3, 调整流量 xij =xij+3, f =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调整流量，继续求出网络

26、的不饱和边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到7的不饱和链?=min 3,1,3,7=1, 调整流量 xij =xij+1, f =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到7的不饱和链，从1开始可以到达的节点

27、为1，2，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到B的运输路线，使总距离最短。?可将问题分为四个阶段：第一阶段，从A到B；第二阶段，从B到C；第三阶段，从C到D；第四阶段，从D到E。?完全枚举：3*3*2*1=24 条。?最优解：AB3C2D2E动态规划?阶段：将

28、所给问题的过程，按时间或空间特征分解成相互联系的阶段，以便按次序求每阶段的解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动态规划? 全过程策略：由所有各阶段组成的决策函数序列,简称策略。

29、记为： 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 AB3C2D2E? 允许策略集：可供选择策略的范围，用P表示。? 动态规划方法就是要从允许策略集P中找出最优策略P*k,n动态规划? 状态转移方程：? 本阶段状态与上一阶段状态和上一阶段决策的关系，用状态转移方程来表示。?sk+1=Tk(sk,dk)? 该方程描述了

30、由第k阶段到第k+1阶段的状态转移规律，又称为状态转移函数。?sk+1=dk (sk)? 阶段指标：衡量某阶段决策效益优劣的策略指标，如距离，成本，利润等。 vk(sk,dk)? 指标函数：衡量所选定策略优劣的数量指标。? 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,n(sk,Pk,n)= Vk,n(sk,dk,sk+1, ,sn+1 )= Vk(sk,dk )*

31、 Vk+1(sk+1, Pk,n)? 最优指标函数:指标函数的最优值， fk(sk)表示从第k阶段状态sk开始采用最优策略P*k,n到过程终止时的最佳效益值。? fk(sk)=opt Vk,n(sk,dk,sk+1, ,sn+1 )? f1(s1)表示从第1阶段状态s1采用最优策略P*1,n到过程终止时的最佳效益值。动态规划? 动态规划的基本思想：?1. 多阶段决策过程划分阶段，恰当的选取状态变量、决策变量和定义最优指标函数，从而将问题化为一族同类型的子问题逐个求解。?2. 求解时从边界条件开始，逆（或顺）过程行进方向，逐段递推寻优。?3. 既将当前一段与未来各段分开，又将当前效益与未来效益结

32、合起来考虑的一种最优化方法。? 如何建立动态规划模型：? 1. 分析识别问题的多阶段特性，按时间或空间的先后顺序适当地划分满足递推关系的若干阶段。? 2. 确定状态变量，满足可知性和无后效性。一般为累计量和随递推过程变化的量。? 3.找到状态转移方程。? 4.正确确定基本方程。? 基础：最优化定理? 作为整个过程的最优策略具有如下性质：不管在此最优策略上的某个状态以前的状态和决策如何，对该状态而言，以后所有的决策必定构成最优子策略。?对最短路问题而言,从最短路上任一点到终点的部分道路（最短路上的子路）也一定是从该点到终点的最短路。动态规划从最后一段开始计算，由后向前逐步推移至A点。第四阶段，由

33、D1到E只有一条线路，其长度f4(D1)=3，同理f4(D2)=4；第三阶段，由Cj到Di均有两种选择，即第二阶段，由Bj到Ci均有三种选择，即动态规划*114131112422141322*2242*31413313242()33()minmin6,()44()63()minmin7,()34()33()minmin6,()34C Df Df CDC Df DC Df Df CDC Df DC Df Df CDC Df D?决策点为决策点为决策点为第一阶段，由A到B，有三种选择，即f1(A)=12 ，说明从A到E的最短距离为12，最短路线的确定可按计算顺序反推而得，即A-B3-C2-D2-E

34、1131*12322121333*2131*22322212233331313376()()(B )minmin11,47()66()36()()minmin9,27()46()()minBCf CBCf CfCBCf CBCf CBCf Cf BCCBCf CBCf CBf B?决策点为决策点为或者*32322333366()min9,27()56Cf CCBCf C?决策点为动态规划12122213*323211()49()( )minmin12,()39ABf BABf Bf ABABf B?决策点为一个著名的命题：一个串村走户的卖货郎，他从某个村庄出发，通过若干个村庄一次且仅一次，最后

35、仍回到原出发的村庄，问：应如何选择行走路线，能使得总的行程最短。设有n个城市，1,2, ,n。Dij表示从i城到j城的距离。规定推销员是从城市 1开始的，设推销员走到 i城，记Ni2,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问题 traveling salesperson problem）3）递推关系式：fk(i,S)=

36、minfk-1(j,Sj)+Dji(k=1,2, ,n-1. i=2,3 ,n. SNi)边界条件：f0(i,?)= D1i4） Pk(i,S )为最优决策函数，表示从1城开始经k个中间城市到i城的最短路线上紧挨着i城前面的那个城市。?距离1城2城3城4城1城08562城60853城79054城9780例：当推销员从1 城出发，经过每个城市一次且仅一次，最后回到1 城，问按怎样的路线走，使总的行程距离最短。（四个城市，其距离矩阵如下表）5）由边界条件可知： f0(i,?)= D1if0(2,?)= D128，f0(3,?)= D135，f0(4,?)=D146当k=1 时，即从1城开始，中间经

37、过一个城市到达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距离1城2城3城4城1城08562城60853城79054城9780当k=2时，即从1城开始，中间经过两个城市到达i城的最短距离是：f2(2,3,4)=minf1(3,4)+D32f1(4,3)+D42= m i n1 4 + 9 , 1 0 +

38、7 = 1 7P2(2,3,4)=41i距离1城2城3城4城1城08562城60853城79054城9780f2(3,2,4)=min f1(2, 4)+D23 f1(4, 2)+D43=min13+8 ,13+8=21 P2(3,2,4)=2或4f2(4,3,2)=min f1(3, 2)+D34 f1(2, 3)+D24=min16+5 ,14+5=19 P2(4,3,2)=2f1(3,4)= 14f1(4,3)=10当k=3 时，即从1城开始，中间经过三个城市到达1城的最短距离是：f3(1，2,3,4)=minf2(2,3,4)+D21f2(3,4,2)+D31f2(4,3,2)+D41

39、=min17+6,21+7, 19+9=23P3(1,2,3,4)=21由此可知，推销员的最短行走路线为 13421，最短总距离为23。? 某种工作系统有几个部件串联组成，称部件正常工作的概率为该部件的可靠性，称整个工作系统为正常工作的概率为系统的可靠性。? 在这种串联系统中，只要有一个部件失灵，整个系统就不能正常工作。? 为了提高串联系统工作的可靠性，可以给各个部件设置备用件，并设计备用件自动投入装置，一旦部件损坏，则备用部件自动投入运行。显然，备用件越多，部件工作的可靠性就越大。从而整个系统工作可靠性就越大。部件1部件2部件n复合系统工作可靠性问题? 备用件越多，整个系统工作可靠性就越大。

40、?但是备用件多了，整个系统的成本、重量、体积都要相应的增大。? 系统所允许的总成本、总重量、总体积往往是有限的。? 因此，复合系统工作可靠性问题主要是：? 讨论在上述限制条件下，如何选择各个部件的备用件数量，使系统的工作可靠性最大。? 上述问题是一个非线性规划问题，像一维资源问题一样，可以用动态规划方法求解这类问题。? 与以前的资源分配问题不同，本问题的总效果不是等于各阶段效果的和，而是等于各个阶段效果的乘积。kkkkucss? 1? ? ? ?11 , 2, 1,max1111nnkkkkkksfnnksfuPsf? 以给各部件分配备用件的顺序为阶段， k=1,2, ,n；? 以由第k个到第

41、n个部件所允许使用的总费用 s k为状态变量；?u k表示部件k拥有的元件数。建模过程通常如下：? ?kksf为部件k到部件n最大工作可靠性，则? 例：某工厂设计一种电子设备，由元件串联组成。已知这三种元件的单价和可靠性如下表所示。要求设计中所使用的元件的费用不超过 105元，试问应该如何设计可使设备的可靠性最大？kckP321DDDD k元件单价 （元） 可靠性3015200.90.80.5解：按元件种类分成三个阶段 k=1,2,3;设状态变量 s k表示元件D k到D 3允许使用的费用；u k为部件D k所用并联元件数；则kkkkucss?1kukP)1 (1? ?kksf? ? ? ?1

42、1 ,2, 3,)1(1max4411sfksfPsfkkukukkkk为部件D k到D 3的最大可靠性，则：用可靠性作为指标，则部件 D k的可靠性为：D k元件单价ck（元） 可靠性PkD1D2D33015200.90.80.5? ? ? ?11 , 2 , 3,)1 (1max4411sfksfPsfkkukukkkk6045303或或?s? ? ?; 130, 5 . 0)()5 . 01 (13034413?usff? ? ?;245,75.0)5 .01 (145323?uf同理? ? ?;360,875.0)5.01(160333?ufK=3 时元件1元件2元件3费用不超过105

43、 元D k元件单价ck（元） 可靠性PkD1D2D33015200.90.80.5? ? ?; 130, 5 . 03033?uf? ? ?; 245,75. 04533?uf? ? ?;360,875.06033?ufK=2 时75452或?s? ?)30(8 .04532ff?2)75(,72. 0)60(8 . 0)45() 8 . 01 (1)30() 8 . 01 (1max)75(2332332?uffff则同理? ?; 145, 4 . 05 . 08 . 02?u1051?s1)105(,648. 0)45()9 . 01 (1)75(9 . 0max)105(12221?ufff则则K=1 时? ? ? ?11 , 2 , 3,)1 (1max4411sfksfPsfkkukukkkk精品课件精品课件！精品课件精品课件！逆推回去得最优方案为:u1*1，u2*2，u3*2即D1元件用1个,D2元件用2个,D3元件用2个.其总费用为100元,可靠性为0.648D k元件单价ck（元）可靠性PkD1D2D33015200.90.80.5