第19讲-欧拉回路及哈密顿回路

数学建模与数学实验欧拉回路及哈密顿回路问题行遍性问题一、中国邮递员问题二、推销员问题三、建模案例（一）欧拉图（二）中国邮递员问题（一）哈密尔顿图（二）推销员问题

7

3

1

2

3

4

1

2

4

5

5

6

6

7

8

9割边G的边是割边的充要条件是不含在G的圈中．

割边的定义：设G连通，E(G),若从G中删除边后，图G-{}不连通，则称边为图G的割边．

e3

v1

v2

v3

v4e1e2e4

e5e6欧拉图

e3

v1

v2

v3

v4

e1e

2e4e5巡回：v1e1v2e2v3e5v1e4v4e3v3e5v1欧拉道路：v1e1v2e2v3e5v1e4v4e3v3欧拉巡回：v1e1v2e2v3e5v1e4v4e3v3e6v1e3

v1

v2

v3v4e1e2e4

e5e3

v1

v2

v3v

4

e1

e2e4

e5e6欧拉图

非欧拉图返回中国邮递员问题-定义中国邮递员问题-算法Fleury算法基本思想：从任一点出发，每当访问一条边时，先要进行检查．如果可供访问的边不只一条，则应选一条不是未访问的边集的导出子图的割边作为访问边，直到没有边可选择为止.

v7e3

v1v2

v3v4e1

e2e4

e5

v5

e6e6

e7

e8

e9e10

若G不是欧拉图，则G的任何一个巡回经过某些边必定多于一次．

解决这类问题的一般方法是：在一些点对之间引入重复边（重复边与它平行的边具有相同的权），使原图成为欧拉图，但希望所有添加的重复边的权的总和为最小．v7e3v1v2v3v4e1e2e4e5v5v6e6e7e8e9（３）求出G1的最小权理想匹配M，得到奇次顶点的最佳配对．返回哈密尔顿图返回推销员问题-定义

流动推销员需要访问某地区的所有城镇，最后回到出发点．问如何安排旅行路线使总行程最小．这就是推销员问题．

若用顶点表示城镇，边表示连接两城镇的路，边上的权表示距离（或时间、或费用），于是推销员问题就成为在加权图中寻找一条经过每个顶点至少一次的最短闭通路问题．定义在加权图G=(V,E)中，（１）权最小的哈密尔顿圈称为最佳H圈．（２）经过每个顶点至少一次的权最小的闭通路称为最佳推销员回路．

一般说来，最佳哈密尔顿圈不一定是最佳推销员回路，同样最佳推销员回路也不一定是最佳哈密尔顿圈．H回路，长22最佳推销员回路，长4推销员问题近似算法：二边逐次修正法：例对以下完备图，用二边逐次修正法求较优H圈．返回1、引例（最短路问题）

假如上图是一个线路网络，两点之间连线上的数字表示两点间的距离（或费用），我们的问题是要将货物从A地运往E地，中间通过B、C、D三个区域，在区域内有多条路径可走，现求一条由A到E的线路，使总距离最短（或总费用最小）。AB1B2B3C1C2C3D1D2E24374632426534633334

将该问题划分为4个阶段的决策问题，即第一阶段为从A到Bj（j=1，2，3），有三种决策方案可供选择；第二阶段为从Bj到Cj（j=1,2,3），也有三种方案可供选择；第三阶段为从Cj到Dj(j=1,2)，有两种方案可供选择；第四阶段为从Dj到E，只有一种方案选择。如果用完全枚举法，则可供选择的路线有3×3×2×1=18（条），将其一一比较才可找出最短路线：A→B1→C2→D3→E

其长度为12。显然，这种方法是不经济的，特别是当阶段数很多，各阶段可供的选择也很多时，这种解法甚至在计算机上完成也是不现实的。由于我们考虑的是从全局上解决求A到E的最短路问题，而不是就某一阶段解决最短路线，因此可考虑从最后一阶段开始计算，由后向前逐步推至A点：第四阶段，由D1到E只有一条路线，其长度f4（D1）=3，同理f4（D2）=4。第三阶段，由Cj到Di分别均有两种选择，即，决策点为D1,决策点为D1，决策点为D2第二阶段，由Bj到Cj分别均有三种选择，即：决策点为C2

决策点为C1或C2决策点为C2

第一阶段，由A到B，有三种选择，即：决策点为B3f1（A）=15说明从A到E的最短距离为12，最短路线的确定可按计算顺序反推而得。即A→B3→C2→D2→E

上述最短路线问题的计算过程，也可借助于图形直观的表示出来：

图中各点上方框的数，表示该点到E的最短距离。图中红箭线表示从A到E的最短路线。从引例的求解过程可以得到以下启示：

①对一个问题是否用上述方法求解，其关键在于能否将问题转化为相互联系的决策过程相同的多个阶段决策问题。

AB1B2B3C1C2C3D1D2E2437463242653463333434676991112

所谓多阶段决策问题是：把一个问题看作是一个前后关联具有链状结构的多阶段过程，也称为序贯决策过程。如下图所示：

②在处理各阶段决策的选取上，不仅只依赖于当前面临的状态，而且还要注意对以后的发展。即是从全局考虑解决局部（阶段）的问题。③各阶段选取的决策，一般与“时序”有关，决策依赖于当前的状态，又随即引起状态的转移，整个决策序列就是在变化的状态中产生出来，故有“动态”含义。因此，把这种方法称为动态规划方法。④决策过程是与阶段发展过程逆向而行。

2、多阶段决策问题的典型例子：企业在生产过程中，由于需求是随着时间变化的因素，因此企业为了获得全年最佳经济效益，就要在整个生产过程中逐月或逐季的根据库存和需求决定生产计划。某种机器，可以在高、低两种负荷下生产。高负荷下生产的产量多，但每生产一个阶段后机器的完好率低；低负荷下生产时的情况则相反。现在需要安排该种机器在多个阶段内的生产，问应该如何决定各阶段中机器的使用，使整个计划期内的总产量最大。某台设备，例如汽车，刚买来时故障少，耗油低，出车时间长，处理价值和经济效益高。随着使用时间的增加则变为故障多，耗油高，维修费用增加，经济效益差。使用时间愈长，处理价值也愈低。另外，每次更新都要付出更新费用。因此，应当如何决定设备的使用年限，使总的效益最佳。动态规划的基本概念(一)、动态规划的基本要素

1、阶段。阶段的划分，一般根据时序和空间的自然特征来划分，但要便于把问题的过程能转化为阶段决策的过程。描述阶段的变量称为阶段变量，常用自然数k表示。如引例可划分为4个阶段求解，k=1，2，3，4。

2、状态。状态就是阶段的起始位置。它既是该阶段某支路的起点，又是前一阶段某支路的终点。（1）状态变量和状态集合。描述过程状态的变量称为状态变量。它可用一个数、一组数或一向量（多维情形）来描述，常用Sk表示第k阶段的状态变量。通常一个阶段有若干个状态。第k阶段的状态就是该阶段所有始点的集合。如引例中

（2）状态应具有无后效性（即马尔可夫性）。即如果某阶段状态给考虑，则在这阶段以后过程的发展不受这阶段以前各阶段状态的影响。3、决策与决策变量。在某阶段对可供选择状态的决定（或选择），称为决策。描述的变量称为决策变量。常用dk(Sk)表示第k阶段处于状态Sk时的决策变量，它是状态变量的函数。决策变量允许取值的范围，称为允许决策集合，常用Dk(Sk)表示。显然dk（Sk）∈Dk(Sk)。如在引例的第二阶段中，若从B1出发，D2（B1）={B1C1,B1C2,B1C3}如果决定选取B1C2，则d2（B1）=B1C2。称可供选择策略的范围，为允许策略集，用P表示。动态规划方法就是要从允许策略集P中找出最优策略P1n*。

4、策略与子策略。策略是一个决策序列的集合。当k=1时，P1n（S1）={d1(s1),d2(s2),…,dn(sn)}就称为全过程的一个策略，简称策略，简记为P1n(S1).

称Pk,n(Sk)={dk(sk),dk+1(sk+1),…,dn(sn)}为由第k阶段开始到最后阶段止的一个子策略，简称后部子策略。简记为Pk,n(Sk)5、状态转移方程。它是确定过程由某一阶段的一个状态到下一阶段另一状态的演变过程，用Sk+1=Tk(Sk,dk)表示。该方程描述了由第k阶段到第k+1阶段的状态转移规律。因此又称其为状态转移函数。6、阶段指标、指标函数和最优指标函数（1）衡量某阶段决策效益优劣的数量指标，称为阶段指标，用vk(Sk,dk)表示第k阶段的阶段指标。在不同的问题中，其含义不同。它可以是距离、利润、成本等。在引例中，用dk=vk(Sk,dk)表示在第k阶段由点Sk到点Sk+1=dk(Sk)距离。如d2(B3,C1)=6。（2）用于衡量所选定策略优劣的数量指标，称为指标函数。它是定义在全过程和所有后部子过程上确定的数量函数。记为Vk,n(Sk,Pk,n).Vk,n(Sk,Pk,n)=Vk,n(Sk,dk,Sk+1,…Sn+1)k=1,2,…,n。构成动态规划模型的指标函数，应具有可分离性，并满足递推关系。常见的指标函数的形式有：①

②（3）最优指标函数fk(Sk),表示从第k阶段的状态Sk开始采用最优子策略P*k,n，到第n阶段终止时所得到的指标函数值。即fk(Sk)=OptVk,n(Sk,dk,…Sn+1)

其中Opt是最优化的缩写,可根据题意取max或min。在引例中,指标函数Vk,n表示在第k阶段由点Sk至终点E的距离。fk(sk)表示第k阶段点Sk到终点E的最短距离。f2(B1)=11表示从第2阶段中的点B1到点E的最短距离。

7、基本方程（递推关系式）从引例求A到E的最短路的计算过程中可以看出，在求解的各个阶段，我们利用了k阶段与k+1阶段之间的递推关系一般地，若则有若(二)、动态规划的基本思想与最优化原理

1、基本思想：动态规划方法的关键在于正确地写出基本方程，因此首先必须将问题的过程划分为多个相互联系的多阶段决策过程，恰当地选取状态变量和决策变量及定义最优指标函数，从而把问题化成一族同类型的子问题。然后从边界条件开始，逆过程行进方向，逐段递推寻优。在每个子问题求解时，均利用它前面已求出的子问题的最优化结果依次进行，最后一个子问题所得的最优解，就是整个问题的最优解。在多阶段决策过程中，动态规划方法是既把当前的一段和未来的各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。因此，每阶段决策的选取是从全局来考虑，与该段的最优选择一般是不同的。动态规划方法的基本思想体现了多阶段性、无后效性、递归性、总体优化性。

2、最优化原理动态规划方法基于R·Bellman等人提出的最优化原理：“作为整个过程的最优策略具有这样的性质，即无论过去的状态和决策如何，对于先前的决策所形成的状态而言，余下的诸决策必须构成最优策略。”简言之，“一个最优策略的子策略总是最优的”。但是，最优化原理仅是策略最优性的必要条件，而基本方程是策略最优性的充要条件。由此可见，基本方程是动态规划理论与方法的基础。动态规划模型的建立与求解(一)、构成动态规划模型的条件

建立动态规划模型，就是分析问题并建立问题的动态规划基本方程。为此，必须满足以下条件：1、将问题的过程划分成恰当的阶段；2、正确选择状态变量Sk，使它既能描述过程的演变，又要满足无后效性；3、确定决策变量dk及每阶段的允许决策集合Dk(Sk)；4、正确写出状态转移方程；5、正确写出指标函数Vk,n的关系式，它应具有以下三个性质；（1）是定义全过程和所有后部子过程上的数量函数；（2）具有可分离性，并满足递推关系，即Vk,n(Sk,dk,…Sn+1)=f(Sk,dk,Vk+1,n)（3）函数f（Sk,dk,Vk+1,n）对于Vk+1,n要求严格单调。以上五点是正确写出动态规划基本方程的要素。(二)、求解动态规划模型的方法1、在已知初始状态S1下，采用逆序解法：（反向递归）

按上图示意的求解方法称为逆序法。例如引例的求解，就是把A看作始端，E为终端，规定从A到E为过程的行进方向，而寻优则是从E到A逆过程进行，所以是采用了逆序法。阶段1s1d1(s1)v1(s1,d1)阶段2s2d2(s2)v2(s2,d2)…阶段kskdk(sk)vk(sk,dk)阶段k+1sk+1dk+1(sk+1)vk+1(sk+1,dk+1)阶段nsndn(sn)vn(sn,dn)…vk,nfk(sk)=optVk,n寻优方向2、在已知终止状态Sn下，采用顺序解法（正向递归）

如果我们把引例中E看作始端，A为终端，规定从E到A过程为行进方向，而寻优则是从A到E过程进行求解的方法称为顺序法。其示意图如下：

逆序法与顺序法的不同仅在对始端终端看法的颠倒或在规定的行进方向不同。但在寻优时却都是逆行进方向，从最后一阶段开始，逐段逆推向前计算，找出最优结果。…阶段1s0d1(s1)v1(s1,d1)阶段2s1d2(s2)v2(s2,d2)阶段kdk(sk)vk(sk,dk)阶段k+1sk+1dk+1(sk+1)vk+1(sk+1,dk+1)阶段ndn(sn)vn(sn,dn)…vk,nfk(sk)=optV1,k寻优方向sksn3、两种解法在建模时的区别如下表所示

应用动态规划解决问题时必须首先建立动态规划模型，再用逆序或顺序算法求解。写一个问题的动态规划模型一般包含以下6个步骤：（1）阶段划分k=1,2,…,n

（2）确定状态变量sk

（3）确定决策变量dk

（4）确定状态转移方程sk+1=f(sk,dk)或sk-1=f(sk,dk)

（5）确定阶段指标V(sk,dk)

（6）确定基本递推方程或案例1

某商店在未来四个月里，利用一个仓库经销某种商品。该仓库的最大容量为1000件，每月中旬订购商品，并于下月初取到订货。据估计，今后四个月这种商品的购价和售价如下表所示。假定商店在1月初开始经销时仓库已存有该种商品500件，每月市场需求不限，问应如何计划每个月的订购与销售量，使这四个月的总利润最大（不考虑仓库的存储费用）？月份k购价pk售价qk110122993111341517解：首先建立动态规划模型。（1）问题划分为四个阶段K=1，2，3，4；（2）状态变量sk表示第k阶段初的库存量，且s1=500（3）决策变量xk表示第k月的订货量，yk表示第k月的销售量；（4）状态转移方程sk+1=sk+xk-yk,（5）指标函数表示第k月的利润V(sk,xk,yk)=qkyk-pkxk（6）基本方程为案例2

某工厂有100台机器，拟分四期使用，在每一期都有两种生产任务。据经验，若把x1台机器投入第一种生产任务，则在本期结束时将有1/3x1台机器损坏报废，剩下的机器全部投入第二种生产任务，则有1/10的机器在期未损坏报废。如果干第一种生产任务时每台机器可获得利润10，干第二种生产任务时每台机器可获利润7，问应怎样分配使用机器以使四期的总利润最大（期未剩下的完好机器数量不限）？解：1、首先建立动态规划模型。（1）问题划分为四个阶段K=1，2，3，4；（2）状态变量sk表示第k阶段初可用于分配的机器数，且s1=100（3）决策变量xk表示第k阶段分配于干第一种任务的机器数，则干第二种任务的机器数为sk-xk（4）状态转移方程sk+1=2/3xk+9/10（sk-xk）=9/10sk-7/30xk,（5）阶段指标表示第k期的利润V(sk,xk)=10xk+7（sk-xk）=3xk+7sk（6）基本方程为：思考：某厂在未来3个月连续生产某种产品。每月初开始生产，月产量为x，生产成本为x2，库存费为每月每单位1元。假如3个月的需求量预测为：b1=100,b2=110,b3=120，且初始存货s0=0，第三个月的期未存货s3=0，问应如何安排生产使总成本最小？案例3（生产存贮问题）某工厂与购货单位签订的供货合同如下表。该厂每月最大产量为4百件，仓库的存货能力为3百件。已知每一百件货物的生产费为一万元。在生产的月份，每批产品的生产准备费为4千元，仓库保管费为每一百件货物每月一千元。假定1月初开始时及6月底交货后仓库中都无存货。问该厂应该如何安排每月的生产与库存，才能既满足交货合同的要求，又使总费用最小？月份123456交货量（百件）125321解：1、建立动态规划模型（1）阶段划分：k=1，2，3，4，5，6（2）状态变量sk表示第k月初的库存量，s1=0（3）决策变量dk表示第k月的计划生产量表示第月的合同交货量（4）状态转移方程：（5）第k月的总费用包括生产费和库存费（6）基本递推方程2、用逆序算法求解当k=6时，s6+d6-1=s7=0,所以s6+d6=1f6(s6)=min{v6(s6,d6)}

当s6=0,d6=1,f6(s6)=14

当s6=1,d6=0,f6(s6)=1当k=5时，s5+d5-2=s6,所以当k=4时，s4+d4-3=s5,所以所求最优决策结果如下表：月初存货量

sk最优生产量

dk月底存货量

sk+1041302145033032101案例4

（背包问题）某工厂生产三种产品，各种产品重量与利润的关系下表所示。现将此三种产品运往市场出售，运输能力总重量不超过6吨，问如何安排使运输总利润最大？种类重量（吨/件）利润（元/件）12802418033130解：其实本例是一个整数规划问题，其整数规划模型如下但是由于整数规划的求解需用分枝定界法求解，计算量非常大，因而在此我们选用动态规划方法来解。1、建立动态规划模型（在此用的是逆序算法求解，与课本不同）（1）阶段划分：k=1,2,3，把装载一种产品看成一个阶段（2）状态变量sk表示第k阶段初可用于装载产品的总容量量，s1=6（3）决策变量dk表示第k阶段装载第k种货物的件数。（4）状态转移方程：其中ak表示第k种货物的单件重量（6）基本递推方程（5）指标函数：vk(sk,dk)表示装载第k种货物dk件所得的利润，即v1(s1,d1)=80d1,v2(s2,d2)=180d2,v3(s3,d3)=130d32、用逆序法求解。其结果如下表s3d3f3(s3)d3*000*01000200030101301401013015010130160120130260*2其计算结果如下表s2d2s3f3(s3)f2(s2)d2*00000010100020200030313013014014013000+130180+0*1501511301800+130180+01601622601800+260*180+00其计算结果如下表s1d1s2f2(s2)f1(s1)d1*601236420260180000+260*80+180*160+0240+001按计算次序反推，得到最优解有两个：（1）x1=0,x2=0,x3=2；（2）x1=1,x2=1,x3=0；案例5（一维资源分配问题）某公司拟将3千万元资金用于改造扩建所属的3个工厂，每个工厂的利润增长额与所分配到的投资额有关。各工厂在获得不同的投资额时所能增加的利润如下表。问应如何分配这些资金，使公司总的利润增长额最大？

投资工厂0102030102.541020358.530269解：这是一个静态问题，通过将对三个工厂的投资看成三个阶段化为一个多阶段的动态问题。1、建立动态规划模型（1）阶段划分：k=1,2,3，把对每个工厂的投资看成一个阶段（2）状态变量sk表示第k阶段初可用于投资的投资总额，s1=3（3）决策变量dk表示第k阶段对第k个工厂的投资额。（4）状态转移方程：（5）阶段指标vk(sk,dk)表示对k第个工厂投资dk后所增加的利润，其值为表中数据。（6）基本递推方程2、用逆序算法求解。其计算结果见下表：s30123f3(s3)0269d*30123s2d2s3f3(s3)f2(s2)d2*00000+0010110200+2=23+0=3120122106200+6=63+2=55+0=5030123321096200+9=93+6=95+2=78.5+0=8.50,1其计算结果见下表：其计算结果见下表：s1d1s2f2(s2)f1(s1)d1*30123321096300+9=92.5+6=8.54+3=710+0=103所求最优解为d1=3，d2=0，d3=0，公司总的最大利润增长额为期10千万元。案例6、设备更新问题

在已知一台设备的效益函数r(i)，维修费用函数u(i)及更新费用函数C(i)条件下，在n年内，每年年初作出决策，是继续使用旧设备还是更换一台新设备，使n年总效益最大的这类问题称为设备更新问题。设rk(i)表示在第