运筹学课程总结

1、课程总结（下）动态规划、图论、网络规划动态规划、图论、网络规划1、动态规划1、动态规划的应用条件：无后效性的多阶段决策问题2、动态规划的基本概念与动态规划模型建立 阶段k 状态变量s（取值范围） 决策变量u（取值范围） 状态转移方程：sk+1=f(sk，xk) 阶段指标函数：有连续型、离散型 过程指标函数：有 和 两种形式 最优指标函数（动态规划方程）： 边界条件：)1 , 2 , 1,)(),(min)(11nnksfxsdsfkkkkkkk10)(11或nnsf3、动态规划的求解目标 最优解 最优策略 最有轨线4、动态规划的求解方法：逆序法和顺序法两种5、动态规划7个基本案例 （1）最短路

2、问题 （2）资源分配问题（投资问题、设备分配问题、背包问题） （3）连续生产控制问题（机器负荷分配） （4）生产与存储问题 （5）设备更新问题（1）最短路问题AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643123456（1 1）划分阶段：按中转站空间位置将整体路线划分为）划分阶段：按中转站空间位置将整体路线划分为6 6个阶段个阶段（2 2）设状态变量）设状态变量s sk k： 表示每一阶段上的中转站个数表示每一阶段上的中转站个数skSk 。（3 3）设决策变量）设决策变量u uk k：表示从某一阶段上、某一中转站出发到下：

3、表示从某一阶段上、某一中转站出发到下 一阶段各个中转站的决定。一阶段各个中转站的决定。 xk Xk（4 4）状态转移方程：）状态转移方程：S Sk+1k+1=x=xk k(s (sk k) ) 表示从第表示从第k k阶段某一中转站阶段某一中转站s sk k出出 发，选择决策发，选择决策x xk k，达到第，达到第k+1k+1阶段中转站阶段中转站s sk+1k+1（5 5）阶段指标函数：）阶段指标函数： R Rk k(s (sk k，x xk k) )表示在第表示在第k k阶段的中转站阶段的中转站s sk k处，处， 选择决策选择决策x xk k 的距离值。的距离值。（6 6）子过程指标函数：）

4、子过程指标函数：R R k k，n n示表示在第示表示在第k k阶段阶段s sk k处到终点的距离处到终点的距离（7 7）基本方程：）基本方程：（8 8）边界条件：）边界条件：)1 , 2 , 1,)(),(min)(11nnksfxsdsfkkkkkkk解：最短路问题的动态规划模型为：解：最短路问题的动态规划模型为：nkikkknkxsdV),(,0)(77sf（2）多元投资问题（收益函数是连续的） 胜利家具厂现有资金胜利家具厂现有资金1010万元，若投资于万元，若投资于3 3个项目，每个项目的个项目，每个项目的投资额为投资额为x xi i(i=1,2,3)(i=1,2,3)时，其效益分别为

5、：时，其效益分别为： 问如何分配投资数额才能使总效益最大问如何分配投资数额才能使总效益最大（特点：收益函数是（特点：收益函数是连续的）。连续的）。 解：可列出静态规划问题的模型如下解：可列出静态规划问题的模型如下23332221112)(9)(4)(xxgxxgxxg)3,2,1(,010.294max3212321ixxxxtsxxxZi动态规划模型为：动态规划模型为： 1 1、分阶段：按投资项目的、分阶段：按投资项目的 个数分为三个阶段，个数分为三个阶段，k=1k=1，2 2，3 32 2、确定决策变量、确定决策变量x xk k：给第：给第 k k个项目投资的资金数。个项目投资的资金数。

6、决策变量集合为：决策变量集合为：3 3、 确定状态变量确定状态变量s sk k：投资于第：投资于第k k个项目到最后项目的资金额。个项目到最后项目的资金额。 状态变量集合为：状态变量集合为：4 4、状态转移方程：、状态转移方程：5 5、阶段指标函数：、阶段指标函数：6 6、过程指标函数：、过程指标函数：7、动态规划递推方程：动态规划递推方程：8 8、边界条件：、边界条件：),10(2231121xssxsss33,)(kiiikxgV1 , 2 , 3)()(max)(110ksfxgsfkkkksxkkkkkkkxss1kksx 0100ks23332221112)(9)(4)(xxgxxg

7、xxg0)(44sf（3）设备分配问题（收益函数是离散的） 胜利家具厂拟将某种高效率的设备胜利家具厂拟将某种高效率的设备5 5台分配给所属的甲、乙、台分配给所属的甲、乙、丙三个车间，各车间若获得这种设备之后，可以为工厂提供丙三个车间，各车间若获得这种设备之后，可以为工厂提供的盈利如表。问这五台设备如何分配给各车间，才能使工厂的盈利如表。问这五台设备如何分配给各车间，才能使工厂得到的盈利最大得到的盈利最大（特点：收益函数是离散的）（特点：收益函数是离散的）。 车间设备 盈利甲乙丙000013542710639111141211125131112解：建立动态规划模型解：建立动态规划模型1 1、分阶

8、段：每个车间作为一个阶段，分为三个阶段，用、分阶段：每个车间作为一个阶段，分为三个阶段，用k k表示表示2 2、决策变量、决策变量x xk k: : 表示分配给第表示分配给第k k个车间的设备台数，个车间的设备台数， 决策变量集合为：决策变量集合为： 0 0 x xk k s sk k 3 3、状态变量、状态变量s sk k: : 表示分配给第表示分配给第k k个车间至第个车间至第3 3车间的设备台数；车间的设备台数； 状态变量集合为：状态变量集合为： ： 0 0 s sk k 5 54 4、状态转移方程：、状态转移方程：5 5、阶段指标函数：、阶段指标函数：g gi i(s (si i，x

9、xi i) )表示对第表示对第i i的项目投入的项目投入x x台机器所获台机器所获 得的收入值。得的收入值。6 6、过程指标函数：、过程指标函数：7 7、动态规划递推模型：、动态规划递推模型：8 8、边界条件：、边界条件：33,),(kiiiikxsgV1 , 2 , 3)(),(max)(110ksfxsgsfkkkkksxkkkk0)(44sfkkkxss1（4）背包问题（决策变量要求为整数）有一个人带一个背包上山，其可以携带物品的重量限度为有一个人带一个背包上山，其可以携带物品的重量限度为1010公斤。设有公斤。设有3 3种物品可供选择，物品编号为种物品可供选择，物品编号为1 1，2 2

10、，3 3 。已知各。已知各种物品每件重量为种物品每件重量为3 3、2 2、5 5公斤，且在上山过程中的作用（价公斤，且在上山过程中的作用（价值）是携带数量分别是值）是携带数量分别是6060、4040、6060。问此人应如何选择携带。问此人应如何选择携带物品（各几件），使所起作用（总价值）最大？物品（各几件），使所起作用（总价值）最大？（特点：决（特点：决策变量要求取整数）策变量要求取整数）用动态规划方法求解背包问题（整数规划）用动态规划方法求解背包问题（整数规划）32,1010523604060321321，且为整数，ixxxxxxxMaxZi（特点：决策变量要求取整数）（特点：决策变量要求取

11、整数）建立动态规划模型：建立动态规划模型：设：设：w wk k是第是第k k种物品单位重量，种物品单位重量，c ck k为第为第k k种物品单位价值种物品单位价值（1 1）划分阶段划分阶段k k：按可以装入物品的种类划分为：按可以装入物品的种类划分为3 3个阶段。个阶段。（2 2）状态变量）状态变量s sk k：第：第k k次装载时，背包剩余的装载重量。次装载时，背包剩余的装载重量。 状态变量集合为：状态变量集合为： （3 3）决策变量）决策变量x xk k：第：第k k次装载第次装载第k k种物品的件数种物品的件数 决策变量集合为：决策变量集合为： x xk k为整数为整数 （4 4）状态转

12、移方程：）状态转移方程：（5 5）阶段指标函数：）阶段指标函数： （6 6）过程指标函数：）过程指标函数：（7 7）动态规划递推方程：）动态规划递推方程：（8 8）边界条件：）边界条件：)(),(max)(110kkkkkwsxkksfxsvsfkkknkiiiinkxsgV),(,100kskkkwsx0kkkkxwss1kkkkkxcxsg),(0)(44sf（5）连续生产控制问题机器负荷分配胜利家具厂购进了一批先进的家具制造机器，该机器床可在高低两种不同负荷下进行生产。 当机器在高负荷情况下的产量函数为g=8u1，其中u1是投入高负荷生产的机器数量，年完好率为 a=0.7； 当机器在低负

13、荷情况下的产量函数为h=5u2，其中u2是投入低负荷生产的机器数量，年完好率为b=0.9； 假定开始生产时完好机器的数量为1000台，试问每年如何安排机器在高、低两种负荷下生产，可使5年内生产的产品总产量最高。解：解： 建立动态规划模型建立动态规划模型（1 1）分阶段：按年度划分为）分阶段：按年度划分为5 5个阶段，个阶段，k=5k=5 （2 2）状态变量）状态变量s sk k：表示第：表示第k k年初拥有的完好机器台数。年初拥有的完好机器台数。（3 3）决策变量）决策变量u uk k：表示为第：表示为第k k年度中分配给高负荷下生产的机年度中分配给高负荷下生产的机 器台数；因此低负荷下生产的

14、机器台数是器台数；因此低负荷下生产的机器台数是s sk k-u-uk k 决策允许集合：决策允许集合：0 0 u uk k s sk k（4 4）状态转移方程：）状态转移方程：（5 5）阶段指标函数：）阶段指标函数：（6 6）过程指标函数：）过程指标函数：（7 7）动态规划递推模型）动态规划递推模型f fk k(s (sk k) )为：为：（8 8）边界条件：）边界条件：5 , 2 , 1),( 9 . 07 . 0)(1kusuusbauskkkkkkk)( 58),(kkkkkkusuusg515,1),(kkkkusgR1 , 2 , 5)(9 . 07 . 0()( 58max)(10

15、kusufususfkkkkkkksukkkk0)(66sf（6）生产与存储问题 胜利家具厂要制定一年4个季度的办公家具的生产计划。某厂经过调查知在未来四个月中每月市场对该厂产品的需求量如下表所示。季度1234季度需求量（件）2324该厂每批产品的生产准备费（固定成本）为 3 千元，若不生产则为0。 每件产品的生产成本（可变成本）为 1千元，该厂最大生产能力为每批次生产不超过 6 件，每件产品每季度的库存费用为 0.5千元，仓库最大库存容量为4件。年初该厂没有此产品的库存，并要求年末也无库存剩余。该厂每季度初应如何计划产品的生产量及库存量，才能既满足每个季度市场对该厂产品的需求又使其总费用（生

16、产费用与库存费用之和）最低。解：建立动态规划模型解：建立动态规划模型（1 1）分阶段：按生产周期划分为）分阶段：按生产周期划分为4 4个阶段，个阶段，k=4k=4（2 2）状态变量）状态变量s sk k：第：第k k月初（月初（ k-1k-1月末）的库存量，已知月末）的库存量，已知s s1 1=s=s5 5=0 =0 状态变量集合状态变量集合S Sk k：阶段：阶段k k的库存量即不能超过库存容量的库存量即不能超过库存容量4 4， 也不能超过阶段也不能超过阶段k k至阶段至阶段4 4的需求总量的需求总量( (因为第因为第5 5阶段的库阶段的库 存量为存量为0 0），故：），故：（3 3）决策变

17、量）决策变量u uk k：第：第k k月的生产量。月的生产量。 决策变量集合决策变量集合U Uk k：阶段产量必须不超过生产能力和第阶段产量必须不超过生产能力和第k k阶阶 段到第段到第4 4阶段的总需求减去第阶段的总需求减去第k k阶段初的库存量，同时要阶段初的库存量，同时要 大于该阶段的市场需求大于该阶段的市场需求 量与该阶段初库存量之差：量与该阶段初库存量之差：4 , 3 , 2 , 1, 4min041kdddskkk,6min1knkkkkksdddusd（4 4） 状态转移方程为：状态转移方程为：kkkkduss1（5 5） 阶段指标函数：为阶段生产费用和库存费用之和，即阶段指标函

18、数：为阶段生产费用和库存费用之和，即0001)(5.03),(kkkkkkkuuysuyusg阶段阶段k k的生产费用的生产费用k k阶段结束时库存费用阶段结束时库存费用（7 7）动态规划基本方程）动态规划基本方程（8 8）边界条件：）边界条件：)()(5 .03min)(11)(kkkksUukksfsuysfkkk（6 6）过程指标函数：）过程指标函数：44,),(kiiiikusgV0)(55sf（7）设备更新问题 胜利家具厂购进了一台先进新设备，该设备的年效益及年均维修费用、更新净费用如下表，试确定今后五年内的更新策略，使总效益最大。（每年初进行决策是更新还是保留） 役龄项目01234

19、5效益54.543.7532.5维护费0.511.522.53更新费0.51.52.22.533.5效益在第k 年初已使用了t 年（或称役龄为t年）的设备在第k 年继续再使用一年的所获得的收益。 维护费在第k 年初已使用了t 年（或称役龄为t年）的设备在第k 年继续再使用一年的维修费用。 更新费在第k 年初已使用了t 年（或称役龄为t年）的设备更换一台新设备已知一台设备的效益函数为已知一台设备的效益函数为r r（t t），维修费用函数为），维修费用函数为u u（t t），更），更新费用函数为新费用函数为c c（t t），在），在n n 年内，每年年初都须作出决策，是继年内，每年年初都须作出决策

20、，是继续使用（续使用（KeepKeep）旧设备还是更换（）旧设备还是更换（ReplacementReplacement）一台新的设备，）一台新的设备，使在使在n n年内总净效益最大。年内总净效益最大。r r k k（t t）在第在第k k 年初已使用了年初已使用了t t 年（或称役龄为年（或称役龄为t t年）的设备年）的设备 在第在第k k 年继续再使用一年的效益。年继续再使用一年的效益。u u k k（t t）在第在第k k 年初已使用了年初已使用了t t 年（或称役龄为年（或称役龄为t t年）的设备年）的设备 在第在第k k 年继续再使用一年的维修费用。年继续再使用一年的维修费用。c c

21、k k（t t）在第在第k k 年初已使用了年初已使用了t t 年（或称役龄为年（或称役龄为t t年）的设备年）的设备 更换一台新设备的更新费用。更换一台新设备的更新费用。 为折扣因子（为折扣因子（0 0 1 1），表示一年以后的单位收入），表示一年以后的单位收入 的价值是现年的的价值是现年的 单位。单位。设备更新问题的一般性描述：设备更新问题的一般性描述：建立动态规划模型如下：建立动态规划模型如下：（1 1）划分阶段：）划分阶段：k k表示计划使用该设备的年数。表示计划使用该设备的年数。 k=1k=1，2 2，n n（2 2）状态变量）状态变量s sk k：第：第k k年初，设备已使用过的年数（役龄）。年初，设备已使用过的年数（役龄）。（3 3）决策变量）决策变量x xk k：第：第k k年初是更新设备（年初是更新设备（Replacem