动态规划

精品课程《运筹学》第三节动态规划问题的一些例子§3.1最短路径问题§3.2投资分配问题§3.3背包问题§3.4排序问题精品课程《运筹学》例一、从A地到D地要铺设一条煤气管道,其中需经过两级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？AB1B2C1C2C3D24333321114§3.1最短路径问题精品课程《运筹学》解：整个计算过程分三个阶段，从最后一个阶段开始。第一阶段（C→D）：C有三条路线到终点D。AB1B2C1C2C3D24333321114DC1C2C3显然有f1(C1)=1；f1(C2)=3；f1(C3)=4精品课程《运筹学》d(B1,C1)+f1(C1)3+1f2(B1)=mind(B1,C2)+f1(C2)=min3+3d(B1,C3)+f1(C3)1+44=min6=45第二阶段（B→C）：B到C有六条路线。AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路线为B1→C1→D)精品课程《运筹学》d(B2,C1)+f1(C1)2+1f2(B2)=mind(B2,C2)+f1(C2)=min3+3d(B2,C3)+f1(C3)1+43=min6=35AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路线为B2→C1→D)精品课程《运筹学》第三阶段（A→B）：A到B有二条路线。f3(A)1=d(A,B1)＋f2(B1)＝2＋4＝6f3(A)2=d(A,B2)＋f2(B2)＝4＋3＝7∴f3(A)=min=min｛6,7｝=6d(A,B1)＋f2(B1)d(A,B2)＋f2(B2)(最短路线为A→B1→C1→D)AB1B2C1C2C3D24333321114DC1C2C3B1B2A精品课程《运筹学》AB1B2C1C2C3D24333321114DC1C2C3B1B2A最短路线为A→B1→C1→D路长为6精品课程《运筹学》练习1：AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876368533842221333525664最优路线为：A→B1→C2→D1→E2→F2→G路长＝18求从A到G的最短路径3精品课程《运筹学》k=5，出发点E1、E2、E37}3543min{,,min2621516115FfFEdFfFEdu5(E1)=F1E1F1G5}3245min{,,min262251612525FfFEdFfFEdfEAB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643)(15Efu5(E2)=F2E2F2G9}3646min{,,min262351613535FfFEdFfFEdfEu5(E3)=F2E3F2Gk=6,F1Gf6(F1)=4F2G,f6(F2)=3精品课程《运筹学》k=4，f4(D1)=7u4(D1)=E2f4(D2)=6u4(D2)=E2f4(D3)=8u4(D3)=E2k=2,f2(B1)=13u2(B1)=C2f2(B2)=16u2(B2)=C3f3(C1)=13u3(C1)=D1f3(C2)=10u3(C2)=D1f3(C3)=9u3(C3)=D1f3(C4)=12u3(C4)=D3k=3,=minf1(A)=mind1(A,B1)+f2(B1)d1(A,B2)+f2(B2)5+133+16=18k=1,u1(A)=B1u2(B1)=C2u3(C2)=D1u4(D1)=E2精品课程《运筹学》u1(A)=B1u2(B1)=C2u3(C2)=D1u4(D1)=E2u5(E1)=F1E1F1Gu5(E2)=F2E2F2Gu5(E3)=F2E3F2G759u5(E2)=F2u6(F2)=G最优策略AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643精品课程《运筹学》求从A到E的最短路径路线为A→B2→C1→D1→E，最短路径为19AB2B1B3C1C3D1D2EC25214112610104312111396581052练习2：1精品课程《运筹学》现有数量为a（万元）的资金，计划分配给n个工厂,用于扩大再生产。假设：xi为分配给第i个工厂的资金数量（万元）；gi(xi)为第i个工厂得到资金后提供的利润值（万元）。问题是如何确定各工厂的资金数，使得总的利润为最大。nixaxxgZiniiniii..2.10)(max11据此，有下式：§3.2投资分配问题精品课程《运筹学》令：fk(x)=以数量为x的资金分配给前k个工厂，所得到的最大利润值。用动态规划求解，就是求fn(a)的问题。当k=1时，f1(x)=g1(x)（因为只给一个工厂）当1＜k≤n时，其递推关系如下：设：y为分给第k个工厂的资金（其中0≤y≤x），此时还剩x－y（万元）的资金需要分配给前k-1个工厂,如果采取最优策略，则得到的最大利润为fk－1(x－y),因此总的利润为：gk(y)＋fk－1(x－y)精品课程《运筹学》nkyxfygxfkkxyk..3.2)()(max)(10其中如果a是以万元为资金分配单位，则式中的y只取非负整数0，1，2，…，x。上式可变为：)()(max)(1,,2,1,0yxfygxfkkxyk所以，根据动态规划的最优化原理，有下式：精品课程《运筹学》例题：设国家拨给60万元投资，供四个工厂扩建使用，每个工厂扩建后的利润与投资额的大小有关，投资后的利润函数如下表所示。投资利润0102030405060g1(x)0205065808585g2(x)0204050556065g3(x)0256085100110115g4(x)0254050606570解：依据题意，是要求f4(60)。精品课程《运筹学》按顺序解法计算。第一阶段：求f1(x)。显然有f1(x)＝g1(x)，得到下表投资利润0102030405060f1(x)＝g1(x)0205065808585最优策略0102030405060第二阶段：求f2(x)。此时需考虑第一、第二个工厂如何进行投资分配，以取得最大的总利润。)60()(max)60(1260,,10,02yfygfy精品课程《运筹学》12006520605055655080408520850max)0()60()10()50()20()40()30()30()40()20()50()10()60()0(max12121212121212fgfgfgfgfgfgfg最优策略为（40，20），此时最大利润为120万元。同理可求得其它f2(x)的值。精品课程《运筹学》105)0()50()10()40()20()30()30()20()40()10()50()0()50()(max)50(1212121212121250,,10,02fgfgfgfgfgfgyfygfy最优策略为（30，20），此时最大利润为105万元。精品课程《运筹学》90)40()(max)40(1240,,10,02yfygfy最优策略为（20，20），此时最大利润为90万元。70)30()(max)30(1230,20,10,02yfygfy最优策略为（20，10），此时最大利润为70万元。精品课程《运筹学》50)20()(max)20(1220,10,02yfygfy20)10()(max)10(12,10,02yfygfy最优策略为（10，0）或（0，10），此时最大利润为20万元。f2(0)＝0。最优策略为（0，0），最大利润为0万元。得到下表最优策略为（20，0），此时最大利润为50万元。精品课程《运筹学》投资利润0102030405060f2(x)020507090105120最优策略(0,0)(10,0)(0,10)(20,0)(20,10)(20,20)(30,20)(40,20)第三阶段：求f3(x)。此时需考虑第一、第二及第三个工厂如何进行投资分配，以取得最大的总利润。)60()(max)60(2360,,10,03yfygfy精品课程《运筹学》1550115201105010070859060105251200max)0()60()10()50()20()40()30()30()40()20()50()10()60()0(max23232323232323fgfgfgfgfgfgfg最优策略为（20，10，30），最大利润为155万元。同理可求得其它f3(x)的值。得到下表精品课程《运筹学》投资利润0102030405060f3(x)0256085110135155最优策略(0,0,0)(0,0,10)(0,0,20)(0,0,30)(20,0,20)(20,0,30)(20,10,30)第四阶段：求f4(60)。即问题的最优策略。)60()(max)60(3460,,10,04yfygfy精品课程《运筹学》16007025656060855011040135251550max)0()60()10()50()20()40()30()30()40()20()50()10()60()0(max34343434343434fgfgfgfgfgfgfg最优策略为（20，0，30，10），最大利润为160万元。精品课程《运筹学》练习：求投资分配问题得最优策略，其中a＝50万元，其余资料如表所示。投资利润01020304050g1(x)02140528085g2(x)015365073100g3(x)02560656870精品课程《运筹学》例：某公司打算在3个不同的地区设置4个销售点，根据市场部门估计，在不同地区设置不同数量的销售点每月可得到的利润如表所示。试问在各地区如何设置销售点可使每月总利润最大。地区销售点01234123000161210251714302116322217x1=2，x2=1，x3=1，f3(4)=47精品课程《运筹学》有一个徒步旅行者，其可携带物品重量的限度为a公斤，设有n种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？物品12…j…n重量（公斤/件）a1a2…aj…an每件使用价值c1c2…cj…cn这就是背包问题。类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题等。§3.3背包问题精品课程《运筹学》设xj为第j种物品的装件数（非负整数）则问题的数学模型如下：)..2.1(0max1njxaxaxcZjnijjjnjjj且为整数用动态规划方法求解，令fx(y)=总重量不超过y公斤，包中只装有前k种物品时的最大使用价值。其中y≥0，k＝1,2,…,n。所以问题就是求fn(a)精品课程《运筹学》其递推关系式为：nkxayfxcyfkkkkkayxkkk2)(max)(10其中当k=1时，有：的最大整数表示不超过其中1111111,)(ayayayxaycyf精品课程《运筹学》例题：求下面背包问题