运筹学动态规划1ppt课件

动动 态态 规规 划划(Dynamic programming)动态规划的根本思想动态规划的根本思想最短途径问题最短途径问题投资分配问题投资分配问题背包问题背包问题 动态规划是用来处理多阶段决策过程最优动态规划是用来处理多阶段决策过程最优化的一种数量方法。其特点在于，它可以把一化的一种数量方法。其特点在于，它可以把一个个n 维决策问题变换为几个一维最优化问题，从维决策问题变换为几个一维最优化问题，从而一个一个地去处理。而一个一个地去处理。需指出：动态规划是求解某类问题的一种需指出：动态规划是求解某类问题的一种方法，是调查问题的一种途径，而不是一种算方法，是调查问题的一种途径，而不是一种算法。必需对详细问题进展详细分析，运用动态法。必需对详细问题进展详细分析，运用动态规划的原理和方法，建立相应的模型，然后再规划的原理和方法，建立相应的模型，然后再用动态规划方法去求解。用动态规划方法去求解。即在系统开展的不同时辰或阶段根据系统即在系统开展的不同时辰或阶段根据系统所处的形状，不断地做出决策；所处的形状，不断地做出决策；每个阶段都要进展决策每个阶段都要进展决策,目的是使整个过程的决策目的是使整个过程的决策 到达最优效果。到达最优效果。动态决策问题的特点：动态决策问题的特点：系统所处的形状和时辰是进展决策的重要要素；系统所处的形状和时辰是进展决策的重要要素；找到不同时辰的最优决策以及整个过程的最优战略。找到不同时辰的最优决策以及整个过程的最优战略。多阶段决策问题：多阶段决策问题：是动态决策问题的一种特殊方式；是动态决策问题的一种特殊方式；在多阶段决策过程中在多阶段决策过程中,系统的动态过程可以按照时间系统的动态过程可以按照时间进程分为形状相互联络而又相互区别的各个阶段；进程分为形状相互联络而又相互区别的各个阶段；多阶段决策问题的典型例子：多阶段决策问题的典型例子：1.1.消费决策问题：企业在消费过程中，消费决策问题：企业在消费过程中，由于需求是随时间变化的，因此企业为了获由于需求是随时间变化的，因此企业为了获得全年的最正确消费效益，就要在整个消费得全年的最正确消费效益，就要在整个消费过程中逐月或逐季度地根据库存和需求决议过程中逐月或逐季度地根据库存和需求决议消费方案。消费方案。2.机器负荷分配问题：某种机器可以在高低两种不同的负荷下进展消费。在高负荷下进展消费时，产品的年产量g和投入消费的机器数量u1的关系为g=g(u1)12n形状形状决策决策形状形状决策决策形状形状形状形状决策决策 这时，机器的年完好率为a，即假设年初完好机器的数量为u，到年终完好的机器就为au,0a1。在低负荷下消费时，产品的年产量h和投入消费的机器数量u2的关系为 h=h(u2)假定开场消费时完好的机器数量为s1。要求制定一个五年方案，在每年开场时，决议如何重新分配完好的机器在两种不同的负荷下消费的数量，使在五年内产品的总产量到达最高。相应的机器年完好率b,0 b1。3.航天飞机飞行控制问题：由于航天飞机的运动的环境是不断变化的，因此就要根据航天飞机飞行在不同环境中的情况，不断地决议航天飞机的飞行方向和速度形状，使之能最省燃料和实现目的如软下落问题。不包含时间要素的静态决策问题本质上是一次决策问题也可以适当地引入阶段的概念，作为多阶段的决策问题用动态规划方法来处理。4.线性规划、非线性规划等静态的规划问题也可以经过适当地引入阶段的概念，运用动态规划方法加以处理。5.最短路问题：给定一个交通网络图如下，其中两点之间的数字表示间隔或破费，试求从A点到G点的最短间隔总费用最小。123456AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643 一、根本概念一、根本概念 1、阶段：、阶段：把一个问题的过程，恰当地分为假设干个相互联络把一个问题的过程，恰当地分为假设干个相互联络的阶段，以便于按一定的次序去求解。的阶段，以便于按一定的次序去求解。描画阶段的变量称为阶段变量。阶段的划分，普通描画阶段的变量称为阶段变量。阶段的划分，普通是根据时间和空间的自然特征来进展的，但要便于问题是根据时间和空间的自然特征来进展的，但要便于问题转化为多阶段决策。转化为多阶段决策。2、形状：表示每个阶段开场所处的自然情况或客观、形状：表示每个阶段开场所处的自然情况或客观条件。通常一个阶段有假设干个形状，描画过程形状条件。通常一个阶段有假设干个形状，描画过程形状的变量称为形状变量。的变量称为形状变量。年、月、年、月、路段路段一个数、一个数、一组数、一组数、一个向一个向量量 形状变量的取值有一定的允许集合或范围，此集合形状变量的取值有一定的允许集合或范围，此集合称为形状允许集合。称为形状允许集合。一、动态规划的根本思想一、动态规划的根本思想 3、决策：表示当过程处于某一阶段的某个形状时，、决策：表示当过程处于某一阶段的某个形状时，可以作出不同的决议，从而确定下一阶段的形状，这可以作出不同的决议，从而确定下一阶段的形状，这种决议称为决策。种决议称为决策。描画决策的变量，称为决策变量。决策变量是形状描画决策的变量，称为决策变量。决策变量是形状变量的函数。可用一个数、一组数或一向量多维情变量的函数。可用一个数、一组数或一向量多维情形来描画。形来描画。在实践问题中决策变量的取值往往在某一范围之内，在实践问题中决策变量的取值往往在某一范围之内，此范围称为允许决策集合。此范围称为允许决策集合。系统在某一阶段的形状转移不但与系统的当前的形状系统在某一阶段的形状转移不但与系统的当前的形状和决策有关，而且还与系统过去的历史形状和决策有和决策有关，而且还与系统过去的历史形状和决策有关。关。4、多阶段决策过程、多阶段决策过程 可以在各个阶段进展决策，去控制过程开展的多段过可以在各个阶段进展决策，去控制过程开展的多段过程；程；其开展是经过一系列的形状转移来实现的；其开展是经过一系列的形状转移来实现的；),(),(),(221112211231112kkkkusususTsususTsusTs 图示如下：图示如下：形状转移方程是确定形状转移方程是确定过程由一个形状到另过程由一个形状到另一个形状的演化过程。一个形状的演化过程。假设第假设第k k阶段形状变量阶段形状变量sksk的值、该阶段的决的值、该阶段的决策变量一经确定，第策变量一经确定，第k+1k+1阶段形状变量阶段形状变量sk+1sk+1的值也就确定。的值也就确定。其形状转移方程如下普通方式其形状转移方程如下普通方式12ks1u1s2u2s3skuksk+1 能用动态规划方法求解的多阶段决策过程是一类能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程，即具有无后效性的多阶段特殊的多阶段决策过程，即具有无后效性的多阶段决策过程。决策过程。假设形状变量不能满足无后效性的要求，应假设形状变量不能满足无后效性的要求，应适当地改动形状的定义或规定方法。适当地改动形状的定义或规定方法。),(),(),(122231112kkkkusTsusTsusTs 动态规划中能动态规划中能处置的形状转移处置的形状转移方程的方式。方程的方式。形状具有无后效性的多阶段决策过程的形形状具有无后效性的多阶段决策过程的形状转移方程如下状转移方程如下无后效性无后效性(马尔可夫性马尔可夫性)假设某阶段形状给定后，那么在这个阶段以假设某阶段形状给定后，那么在这个阶段以后过程的开展不受这个阶段以前各段形状的影响；后过程的开展不受这个阶段以前各段形状的影响；过程的过去历史只能经过当前的形状去影响过程的过去历史只能经过当前的形状去影响它未来的开展；它未来的开展；构造动态规划模型时，要充分留意构造动态规划模型时，要充分留意能否满足无后效性的要求；能否满足无后效性的要求；形状变量要满足无后效性的要求；形状变量要满足无后效性的要求；5 5、战略：是一个按顺序陈列的决策组成的集合。在、战略：是一个按顺序陈列的决策组成的集合。在实践问题中，可供选择的战略有一定的范围，称为允实践问题中，可供选择的战略有一定的范围，称为允许战略集合。从允许战略集合中找出到达最优效果的许战略集合。从允许战略集合中找出到达最优效果的战略称为最优战略。战略称为最优战略。6 6、形状转移方程：是确定过程由一个形状到另一、形状转移方程：是确定过程由一个形状到另一个形状的演化过程，描画了形状转移规律。个形状的演化过程，描画了形状转移规律。7 7、目的函数和最优值函数：用来衡量所实现过程优、目的函数和最优值函数：用来衡量所实现过程优劣的一种数量目的，为目的函数。目的函数的最优值，劣的一种数量目的，为目的函数。目的函数的最优值，称为最优值函数。在不同的问题中，目的函数的含义称为最优值函数。在不同的问题中，目的函数的含义是不同的，它能够是间隔、利润、本钱、产量或资源是不同的，它能够是间隔、利润、本钱、产量或资源耗费等。耗费等。动态规划模型的目的函数，应具有可分别性，并满动态规划模型的目的函数，应具有可分别性，并满足递推关系。足递推关系。小结小结:),()(1,susVoptsfnkknkkkuunk),(,111,1nkknkkkksusVus方程方程 :形状转移方程形状转移方程),(1kkkkusTs概念概念 :阶段变量阶段变量k k形状变量形状变量sksk决策变量决策变量uk;uk;目的目的:),(111,nkkkknknksususVV动态规划本质上是多阶段决策过程动态规划本质上是多阶段决策过程;效益目的函数方式目的函数方式:和、积积无后效性无后效性),(111,nkkkknksususV可递推可递推,*2*1nuuu,*2*1nsss解多阶段决策过程问题，求出解多阶段决策过程问题，求出 最优战略，即最优决策序列 susvoptsfnkknkkkuunk1,f1(s1)最优轨线，即执行最优战略时的形状序列 最优目的函数值最优目的函数值),(*1*1*,1*,1nnnnususVV从从 k k 到终点最优战略到终点最优战略子战略的最优目的函数值子战略的最优目的函数值 1、动态规划方法的关键在于正确地写出根本、动态规划方法的关键在于正确地写出根本的递推关系式和恰当的边境条件简称根本方的递推关系式和恰当的边境条件简称根本方程。要做到这一点，就必需将问题的过程分程。要做到这一点，就必需将问题的过程分成几个相互联络的阶段，恰当的选取形状变量成几个相互联络的阶段，恰当的选取形状变量和决策变量及定义最优值函数，从而把一个大和决策变量及定义最优值函数，从而把一个大问题转化成一组同类型的子问题，然后逐个求问题转化成一组同类型的子问题，然后逐个求解。即从边境条件开场，逐段递推寻优，在每解。即从边境条件开场，逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进展，最后一个子问题题的最优化结果，依次进展，最后一个子问题所得的最优解，就是整个问题的最优解。所得的最优解，就是整个问题的最优解。二、动态规划的根本思想二、动态规划的根本思想 2、在多阶段决策过程中，动态规划方法是既把当前、在多阶段决策过程中，动态规划方法是既把当前一段和未来一段分开，又把当前效益和未来效益结合一段和未来一段分开，又把当前效益和未来效益结合起来思索的一种最优化方法。因此，每段决策的选取起来思索的一种最优化方法。因此，每段决策的选取是从全局来思索的，与该段的最优选择答案普通是不是从全局来思索的，与该段的最优选择答案普通是不同的同的.最优化原理：作为整个过程的最优战略具有这样的最优化原理：作为整个过程的最优战略具有这样的性质：无论过去的形状和决策如何，相对于前面的决性质：无论过去的形状和决策如何，相对于前面的决策所构成的形状而言，余下的决策序列必然构成最优策所构成的形状而言，余下的决策序列必然构成最优子战略。也就是说，一个最优战略的子战略也是最子战略。也就是说，一个最优战略的子战略也是最优的。优的。3、在求整个问题的最优战略时，由于初始形状是、在求整个问题的最优战略时，由于初始形状是知的，而每段的决策都是该段形状的函数，故最优战知的，而每段的决策都是该段形状的函数，故最优战略所经过的各段形状便可逐段变换得到，从而确定了略所经过的各段形状便可逐段变换得到，从而确定了最优道路。最优道路。三、建立动态规划模型的步骤三、建立动态规划模型的步骤 1、划分阶段、划分阶段划分阶段是运用动态规划求解多阶段决策问题的第一划分阶段是运用动态规划求解多阶段决策问题的第一步，在确定多阶段特性后，按时间或空间先后顺序，步，在确定多阶段特性后，按时间或空间先后顺序，将过程划分为假设干相互联络的阶段。对于静态问题将过程划分为假设干相互联络的阶段。对于静态问题要人为地赋予要人为地赋予“时间概念，以便划分阶段。时间概念，以便划分阶段。2、正确选择形状变量、正确选择形状变量选择变量既要能确切描画过程演化又要满足无后效性，选择变量既要能确切描画过程演化又要满足无后效性，而且各阶段形状变量的取值可以确定。普通地，形状而且各阶段形状变量的取值可以确定。普通地，形状变量的选择是从过程演化的特点中寻觅。变量的选择是从过程演化的特点中寻觅。3、确定决策变量及允许决策集合、确定决策变量及允许决策集合通常选择所求解问题的关键变量作为决策变量，同时通常选择所求解问题的关键变量作为决策变量，同时要给出决策变量的取值范围，即确定允许决策集合。要给出决策变量的取值范围，即确定允许决策集合。4 4、确定形状转移方程、确定形状转移方程根据根据k k 阶段形状变量和决策变量，写出阶段形状变量和决策变量，写出k+1k+1阶段形状变阶段形状变量，形状转移方程该当具有递推关系。量，形状转移方程该当具有递推关系。5 5、确定阶段目的函数和最优目的函数，建立动态规、确定阶段目的函数和最优目的函数，建立动态规划根本方程划根本方程 阶段目的函数是指第阶段目的函数是指第k k 阶段的收益，最优目的函数阶段的收益，最优目的函数是指从第是指从第k k 阶段形状出发到第阶段形状出发到第n n 阶段末所获得收益的阶段末所获得收益的最优值，最后写出动态规划根本方程。最优值，最后写出动态规划根本方程。以上五步是建立动态规划数学模型的普通步骤。由于以上五步是建立动态规划数学模型的普通步骤。由于动态规划模型与线性规划模型不同，动态规划模型没有一动态规划模型与线性规划模型不同，动态规划模型没有一致的方式，建模时必需根据详细问题详细分析，只需经过致的方式，建模时必需根据详细问题详细分析，只需经过不断实际总结，才干较好掌握建模方法与技巧。不断实际总结，才干较好掌握建模方法与技巧。例一、从例一、从A 地到地到D 地要铺设一条煤气管道地要铺设一条煤气管道,其中需经过其中需经过两级中间站，两点之间的连线上的数字表示间隔，如两级中间站，两点之间的连线上的数字表示间隔，如下图。问应该选择什么道路，使总间隔最短？下图。问应该选择什么道路，使总间隔最短？AB1B2C1C2C3D24333321114二、最短途径问题二、最短途径问题 解：整个计算过程分三个阶段，从最后一个阶段开场。解：整个计算过程分三个阶段，从最后一个阶段开场。第一阶段第一阶段C D：C 有三条道路到终点有三条道路到终点D。AB1B2C1C2C3D24333321114DC1C2C3显然有显然有 f1(C1)=1 ；f1(C2)=3 ；f1(C3)=4 d(B1,C1)+f1(C1)3+1 f2(B1)=min d(B1,C2)+f1(C2)=min 3+3 d(B1,C3)+f1(C3)1+4 4 =min 6 =4 5第二阶段第二阶段B C：B 到到C 有六条道路。有六条道路。AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短道路为最短道路为B1C1 D)d(B2,C1)+f1(C1)2+1 f2(B2)=min d(B2,C2)+f1(C2)=min 3+3 d(B2,C3)+f1(C3)1+4 3 =min 6 =3 5AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短道路为最短道路为B2C1 D)第三阶段第三阶段 A B：A 到到B 有二条道路。有二条道路。f3(A)1=d(A,B1)f2(B1)246 f3(A)2=d(A,B2)f2(B2)437 f3(A)=min =min6,7=6d(A,B1)f2(B1)d(A,B2)f2(B2)(最短道路为最短道路为AB1C1 D)AB1B2C1C2C3D24333321114DC1C2C3B1B2AAB1B2C1C2C3D24333321114DC1C2C3B1B2A最短道路为最短道路为 AB1C1 D 路长为路长为 6练习练习1：AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876368533842221333525664最优道路为：最优道路为：A B1 C2 D1 E2 F2 G 路长路长18求从求从A A到到G G的最短途径的最短途径3k=5k=5，出发点，出发点E1E1、E2E2、E3E3 73543min,min2621516115FfFEdFfFEdu5(E1)=F1E1 F1 G 53245min,min262251612525FfFEdFfFEdfEAB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643)(15Efu5(E2)=F2E2 F2 G 93646min,min262351613535FfFEdFfFEdfEu5(E3)=F2E3 F2 Gk=6,k=6,F1 G f6(F1)=4F2 G,f6(F2)=3k=4，f4(D1)=7 u4(D1)=E2f4(D2)=6 u4(D2)=E2f4(D3)=8 u4(D3)=E2k=2,f2(B1)=13 u2(B1)=C2 f2(B2)=16 u2(B2)=C3f3(C1)=13 u3(C1)=D1f3(C2)=10 u3(C2)=D1f3(C3)=9 u3(C3)=D1f3(C4)=12 u3(C4)=D3k=3,=minf1(A)=mind1(A,B1)+f2(B1)d1(A,B2)+f2(B2)5+133+16=18k=1,u1(A)=B1 u2(B1)=C2u3(C2)=D1u4(D1)=E2u1(A)=B1 u2(B1)=C2u3(C2)=D1u4(D1)=E2u5(E1)=F1E1 F1 Gu5(E2)=F2E2 F2 Gu5(E3)=F2E3 F2 G7 5 9 u5(E2)=F2u6(F2)=G最优战略最优战略AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643求从求从A A到到E E的最短途径的最短途径道路为道路为AB2C1 D1 E AB2C1 D1 E，最短途径为，最短途径为1919AB2B1B3C1C3D1D2EC25214112610104312111396581052练习练习2：1 现有数量为现有数量为a万元的资金，方案分配给万元的资金，方案分配给n 个工厂个工厂,用于扩展再消费。用于扩展再消费。假设：假设：xi 为分配给第为分配给第i 个工厂的资金数量万元个工厂的资金数量万元；gi(xi)为第为第i 个工厂得到资金后提供的利润值万元。个工厂得到资金后提供的利润值万元。问题是如何确定各工厂的资金数，使得总的利润为问题是如何确定各工厂的资金数，使得总的利润为最大。最大。nixaxxgZiniiniii.2.1 0)(max11据此，有下式：据此，有下式：三、投资分配问题三、投资分配问题 令：令：fk(x)=以数量为以数量为x 的资金分配给前的资金分配给前k 个工厂，所个工厂，所得到的最大利润值。得到的最大利润值。用动态规划求解，就是求用动态规划求解，就是求 fn(a)的问题。的问题。当当 k=1 时，时，f1(x)=g1(x)由于只给一个工厂由于只给一个工厂 当当1kn 时，其递推关系如下：时，其递推关系如下：设：设：y 为分给第为分给第k 个工厂的资金其中个工厂的资金其中 0y x，此，此时还剩时还剩 x y万元的资金需求分配给前万元的资金需求分配给前 k-1 个工厂个工厂,假设采取最优战略，那么得到的最大利润为假设采取最优战略，那么得到的最大利润为fk1(xy),因此总的利润为：因此总的利润为：gk(y)fk1(xy)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,02yfygfy12006520605055655080408520850max)0()60()10()50()20()40()30()30()40()20()50()10()60()0(max12121212121212fgfgfgfgfgfgfg最优战略为最优战略为40，20，此时最大利润为，此时最大利润为120万元。万元。同理可求得其它同理可求得其它 f2(x)的值。的值。105)0()50()10()40()20()30()30()20()40()10()50()0()50()(max)50(1212121212121250,10,02fgfgfgfgfgfgyfygfy最优战略为最优战略为30，20，此时最大利润为，此时最大利润为105万元。万元。90 )40()(max)40(1240,10,02yfygfy最优战略为最优战略为20，20，此时最大利润为，此时最大利润为90万元。万元。70 )30()(max)30(1230,20,10,02yfygfy最优战略为最优战略为20，10，此时最大利润为，此时最大利润为70万元。万元。50 )20()(max)20(1220,10,02yfygfy20 )10()(max)10(12,10,02yfygfy最优战略为最优战略为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,03yfygfy1550115201105010070859060105251200max)0()60()10()50()20()40()30()30()40()20()50()10()60()0(max23232323232323fgfgfgfgfgfgfg最优战略为最优战略为20，10，30，最大利润为，最大利润为155万元。万元。同理可求得其它同理可求得其它 f3(x)的值。得到下表的值。得到下表 投资投资利润利润0102030405060f3(x)0256085110155最优最优战略战略(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,04yfygfy16007025656060855011040135251550max)0()60()10()50()20()40()30()30()40()20()50()10()60()0(max34343434343434fgfgfgfgfgfgfg最优战略为最优战略为20，0，30，10，最大利润为，最大利润为160万元。万元。练习：练习：求投资分配问题得最优战略，其中求投资分配问题得最优战略，其中a50 万元，万元，其他资料如表所示。其他资料如表所示。投资投资利润利润01020304050g1(x)02140528085g2(x)015365073100g3(x)02560656870例：某公司计划在例：某公司计划在3 3个不同的地域设置个不同的地域设置4 4个销售点，个销售点，根据市场部门估计，在不同地域设置不同数量的销根据市场部门估计，在不同地域设置不同数量的销售点每月可得到的利润如表所示。试问在各地域如售点每月可得到的利润如表所示。试问在各地域如何设置销售点可使每月总利润最大。何设置销售点可使每月总利润最大。地地域域销售点销售点01234123000161210251714302116322217 x1=2，x2=1，x3=1，f3(4)=47 有一个徒步游览者，其可携带物品分量的限制为有一个徒步游览者，其可携带物品分量的限制为a 公公斤，设有斤，设有n 种物品可供他选择装入包中。知每种物品种物品可供他选择装入包中。知每种物品的分量及运用价值作用，问此人应如何选择携带的分量及运用价值作用，问此人应如何选择携带的物品各几件，使所起作用运用价值最大？的物品各几件，使所起作用运用价值最大？物品物品 1 2 j n分量公斤分量公斤/件件 a1 a2 aj an每件运用价值每件运用价值 c1 c2 cj cn 这就是背包问题。类似的还有工厂里的下料问题、这就是背包问题。类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题运输中的货物装载问题、人造卫星内的物品装载问题等。等。四、背包问题四、背包问题设设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例题：求下面背包问题的最优解例题：求下面背包问题的最优解 且且为为整整数数0,55231258max321321321xxxxxxxxxZ物品物品 1 2 3分量公斤分量公斤 3 2 5运用价值运用价值 8 5 12解：解：a5 ，问题是求，问题是求 f3(5)55(12max)5(323503333xfxfxax 整整数数 )1()0(223231032355032350333333333)0(12),5(0max)55(12max)55(12max)55(12max)5(xxxxxxaxffxfxxfxxfxf ，整整数数整整数数 5 5 )(2)1()0(1112122,10212250212502222222222)1(10),3(5),5(0max)25(max)25(max)25(5max)5(xxxxxxxaxfffxfxxfxxfxf，整整数数整整数数 )0()0(0max)20(max)20(max)20(5max)0(1)0(121202122002120022222222ffxfxxfxxfxfxxxxxax 5 5 整数整数整数整数)0(0308)0()0(0318)1()1(8338)3()1(8358)5(1111111111111111 xxcfxxcfxxcfxxcf )1,1(1310,85,8max)1(10),3(5),5(0max)5(212)1()0(1112222 xxffffxxx )()0,0(0)0()0(0max)0(211)0(122 xxfffx )0,1,1(13012,130max)0(12),5(0max)5(321)1()0(22333 xxxfffxx所以，最优解为所以，最优解为 X1.1.0，最优值为，最优值为 Z=13。练习练习1：某厂消费三种产品，各种产品分量与利：某厂消费三种产品，各种产品分量与利润的关系如表所示。现将此三种产品运往市场出卖，润的关系如表所示。现将此三种产品运往市场出卖，运输才干总分量不超越运输才干总分量不超越 6 吨，问如何安排运输，使吨，问如何安排运输，使总利润最大？总利润最大？种类种类 1 2 3分量吨分量吨/公斤公斤 2 3 4 单件利润元单件利润元 80 130 180最优方案：最优方案：X1=X1=0,2,00,2,0X2=X2=1,0,11,0,1Z=260Z=260 练习练习2：求以下问题的最优解：求以下问题的最优解 且且为为整整数数0,10543654max321321321xxxxxxxxxZ X=(2.1.0)最优值为 Z=13 排序问题指排序问题指n 种零件经过不同设备加工是的顺序问题。种零件经过不同设备加工是的顺序问题。其目的是使加工周期为最短。其目的是使加工周期为最短。1、n 1 排序问题排序问题 即即n 种零件经过种零件经过1 种设备进展加工，如何安排？种设备进展加工，如何安排？14682023交货日期交货日期d45173加工时间加工时间t零件代号零件代号2j1j3j4j5j例一、例一、五、排序问题五、排序问题 1平均经过设备的时间最小平均经过设备的时间最小 按零件加工时间非负次序陈列顺序，其时间最小。即按零件加工时间非负次序陈列顺序，其时间最小。即将加工时间由小到大陈列即可将加工时间由小到大陈列即可1j2j3j4j5j零件加工顺序零件加工顺序 工序时间工序时间13457 实践经过时间实践经过时间1481320 交货时间交货时间82314620 平均经过时间平均经过时间2.9)1481320(51 x延迟时间延迟时间=13 6=7 2按时交货陈列顺序按时交货陈列顺序1j2j3j4j5j零件加工顺序零件加工顺序 工序时间工序时间13457 实践经过时间实践经过时间56101720 交货时间交货时间82314620 平均经过时间平均经过时间6.11)56101720(51 x延迟时间延迟时间=0 3既满足交货时间，又使平均经过时间最小既满足交货时间，又使平均经过时间最小1j2j3j4j5j零件加工顺序零件加工顺序 工序时间工序时间13457 实践经过时间实践经过时间1691320 交货时间交货时间82314620延迟时间延迟时间=0 平均经过时间平均经过时间8.9)1691320(51 x 2、n 2 排序问题排序问题 即即n 种零件经过种零件经过2 种设备进展加工，如何安排？种设备进展加工，如何安排？例二、例二、49523B53786A 零件零件2j1j3j4j5j设备设备ABT经变换为经变换为49523B53786A 零件零件2j1j3j4j5j设备设备加工顺序图如下：加工顺序图如下：ABT3j1j2j4j5j3756895432+2+2-5 加工周期加工周期 T=3+7+5+6+8+2=31小小即即BAtti 3、n 3 排序问题排序问题 即即n 种零件经过种零件经过 3 种设备进展加工，如何安排？种设备进展加工，如何安排？例三、例三、3468564683579310CBA1j2j3j4j5jABCT变换变换4+36+45+86+56+48+65+37+53+910+3B+CA+B1j2j3j4j5j排序排序4+36+45+86+56+48+65+37+53+910+3B+CA+B1j2j3j4j5j复原复原3468564683579310CBA1j2j3j4j5j计算计算T=6+10+8+7+6+4+3=44计算根据：计算根据：ABcCBABCBAttttttttttiiiiii maxmin maxmin或或即即可可按按下下式式计计算算或或练习：练习：11851079827746CBA1j2j3j4jT=451j2j3j4j