运筹与优化模型PPT课件

1、1目标函数 21127maxxxf约束条件 3605921 xx2005421 xx30010321xx. 0, 021xx其中( , )为决策向量， 1x2x满足约束条件的( , )称为可行决策。 1x2x 线性规划问题就是指目标函数为诸决策变量的线性函数，给定的条件可用诸决策变量的线性等式或不等式表示的决策问题。线性规划求解的有效方法是单纯形法（进一步了解可参考有关书籍），当然简单的问题也可用图解法。第1页/共97页2如用图解法求解例1： 由约束条件决定的可行域如图阴影所示， 目标函数的等值线向右上方移动时其值增大，在到达点 时f取得最大值； 2Q第2页/共97页3当 =20, =24时，

2、即产品A生产20t，产品B生产24t时，生产方案最优。 1x2x其最大利润为：7201224428千元例2：某两个煤厂 . ，每月进煤数量分别为60t和100t联合供应3个居民区 。3个居民区每月对煤的需求量依次分别为50t,70t,40t，煤厂 离3个居民区 的距离依次为10km,5km,6km，煤厂 离3个居民区 的距离依次分别为4km,8km,12km，问如何分配供煤量使得运输费（即tkm）达到最小？1A2A321,BBB321,BBB2A321,BBB1A第3页/共97页4 解：设 表示 (i=1.2)煤厂提供给 （居民区的煤量； ijxiAjBf表示总运输费此问题归结为： 23222

3、113121112846510minxxxxxxfts.60131211xxx100232221xxx502111 xx702212 xx402313 xx, 3 , 2 , 1, 2 , 1, 0jixij第4页/共97页5一般线性规划问题的数学表达式： nnxcxcxcf2211max(min) s.t 11212111),(bxaxaxann22222121),(bxaxaxannmnmnmmbxaxaxa),(22110,21nxxx第5页/共97页6例3：生产组织与计划问题 设有m种资源，第i(i=1,2,m)种资源的现存量为 ，现要生产n种产品，已知生产j(j=1,2,n)种产品时

4、，每单位产品需要第i种资源量为 ，而每单位j种产品可得利润 ，问如何组织生产才能使利润最大？ ibijajc 解：用 表示生产第j(j=1,2,n)种产品的计划数， jx上述问题可归结为如下的数学问题： njjjxc1maxts.mibxainjjij2 . 11njxj2 . 10第6页/共97页7 二、整数规划模型对于线性规划： njxmibxaxcfjnjijijnjjj2 , 102 , 1min11 决策变量是连续变量，最优解可能是小数或分数。 第7页/共97页8 但是在许多实际问题中，往往要求所得的解为整数，例如投资项目的选择、机器的台数、完成工作的人数、装货的车数等，分数和小数的

5、答案就没有现实意义了。 在现性规划中，若限制 (j=1,2,n)是非负整数，则这种线性规划问题称为整数规划问题。 jx为整数为整数如如212112121,0,115851215maxxxxxxxxxxf第8页/共97页9 例4：分配问题 假设某工厂用m台机床加工n种零件。在一个生产周期内，第i(i=1,2,m)台机床只能工作 个机时，而第j(j=1,2,n)种零件必须完成 个，又第i台机床加工第j种零件所需机时和成本分别为 （机时个）和 （元个）。问在这个生产周期内怎样安排各机床的生产任务，才能使得既完成加工任务，又使总的加工成本最少？ iajbijtijc 解：在一个生产周期内，假设第i台机

6、床加工第j种零件的个数为 。 ijx由于 是零件个数，因此 必须是非负整数， ijxijx第9页/共97页10本问题的数学模型为： minjijijxc11mints.injijijaxt1mi2 , 1jmiijbx 1nj2 , 1 为为非非负负整整数数ijx第10页/共97页11三、非线性规划模型非线性规划模型的一般形式为： )2(., 2 , 10)(.miXgtsi)3(., 2 , 10)(ljXhiDX 为为可可行行集集其其中中nTnRDxxxX,),(21 f(X)为目标函数， (2)、(3)为约束条件， (2)为不等式约束，(3)为等式约束；若只有(1)称为无约束问题。 )

7、1 ()(minXf第11页/共97页1232321213215),(minxxxxxxxxf如如0516223121xxxxx010312221xxxx第12页/共97页13例5：容器的设计问题 某公司专门生产储藏用容器，定货合同要求该公司制造一种敞口的长方体容器，容积恰好为12立方米，该容器的底必须为正方形，容器总重量不超过68公斤。已知用作容器四壁的材料为每平方米10 元，重3公斤；用作容器底的材料每平方米20元，重2公斤。试问制造该容器所需的最小费用是多少？ 模型建立 设该容器底边长和高分别为 米、 米， 1x2x则问题的数学模型为 21212040)(minxxxXf（容器的费用）

8、. 0, 0,68212,12. .212121221xxxxxxxts（容器重量）（容器重量）（容器体积）（容器体积）第13页/共97页14一般来说，非线性规划模型的求解要比线性规划模型求解困难得多，虽然现在已经发展了许多非线性规划的算法，但到目前为止，还不象线性规划那样有通用的单纯形算法，而是各种算法都有自己特定的适用范围，如求解法有：最速下降法、牛顿法、可行方向法、惩罚函数法等。尽管如此，非线性规划的实际应用还是相当广泛的。第14页/共97页15 5.2 实际问题中的优化模型一、投资策略 某部门现有资金10万元，五年内有以下投资项目供选择： 项目A,从第一年到第四年每年初投资，次年末收回

9、本金且获利15%； 项目B，第三年初投资，第五年末收回本金且获利25%，最大投资额为4万元； 项目C，第二年初投资，第五年末收回本金且获利40%，最大投资额为3万元； 项目D，每年初投资，年末收回本金且获利6%。问如何确定投资策略使第五年末本息总额最大。第15页/共97页16问题的目标函数是第五年末的本息总额， 决策变量是每年初各个项目的投资额， 约束条件是每年初拥有的资金。 用ijx表示第i年初（5 , , 2 , 1i）项目4 , 3 , 2 , 1(jj分别代表A,B,C,D)的投资额， 根据所给条件只有下表1列出的ijx才是需要求解的。 项目 年份 A B C D 1 2 3 4 5

10、11x21x31x41x32x23x14x24x34x44x54x第16页/共97页17 因为项目D 每年初可以投资，且年末能收回本息，所以每年初都应把资金全部投出去， 项目A,从第一年到第四年每年初投资，次年末收回本金且获利15%； 项目B，第三年初投资，第五年末收回本金且获利25%，最大投资额为4万元； 项目C，第二年初投资，第五年末收回本金且获利40%，最大投资额为3万元； 项目D，每年初投资，年末收回本金且获利6%。由此可得如下的约束条件： 第一年初： 101411 xx第二年初： 1424232106. 1xxxx第三年初 241134323106. 115. 1xxxxx第四年初：

11、 3421444106. 115. 1xxxx第五年初： 44315406. 115. 1xxx项目B,C对投资额的限制： 3, 42332xx第17页/共97页18项目A,从第一年到第四年每年初投资，次年末收回本金且获利15%； 项目B，第三年初投资，第五年末收回本金且获利25%，最大投资额为4万元； 项目C，第二年初投资，第五年末收回本金且获利40%，最大投资额为3万元； 项目D，每年初投资，年末收回本金且获利6%。 每项投资应为非负的： 0ijx第五年末本息总额为5432234106. 125. 140. 115. 1xxxxz将上条件等价变形如1424232106. 1xxxx006.

12、 124232114xxxx第18页/共97页19由此得投资问题的线性规划模型如下：5432234106. 125. 140. 115. 1maxxxxxzs.t. 101411 xx006. 124232114xxxx006. 115.xxxx006. 115, 144413421xxxx006. 115. 1544431xxx3, 42332xx0ijx第19页/共97页20求解得4008. 0, 0,000. 3,5436. 3,1732. 6,8268. 3312423211411xxxxxx4609. 0, 0,0752. 4, 0,0000. 454444

13、13432xxxxx3750.14z 即第1年项目A,D分别投资3.8268和6.1732(万元)；第2年项目A,C分别投资3.5436和3(万元)；第3年项目A,B分别投资0.4008和4(万元)；第4年项目A投资4.0752(万元)；第5年项目D投资0.4609(万元)；5年后总资金 14。375万元，即盈利43.75%.第20页/共97页21二、货机装运问题 某架货机有三个货舱：前仓、中仓、后仓。三个货舱所能装载的货物的最大重量和体积都有限制，如表3所示。并且，为了保持飞机的平衡，三个货舱中实际装载货物的重量必须与其最大容许重量成比例。前仓中仓后仓重量限制（吨）10168体积限制（米3）

14、680087005300 现有四类货物供该货机本次飞行装运，其有关信息如表4，最后一列指装运后所获得的利润。第21页/共97页22重量（吨）空间（米3/吨）利润（元/吨）货物1184803100货物2156503800货物3235803500货物4123902850应如何安排装运，使该货机本次飞行获利最大？模型假设 问题中没有对货物装运提出其它要求，我们可作如下假设： 1）每种货物可以分割到任意小；2）每种货物可以在一个或多个货舱中任意分布；第22页/共97页233）多种货物可以混装，并保证不留空隙。模型建立决策变量： ijx表示第i种货物装入第j个货舱的重量（吨）， 货舱j=1,2,3分别表

15、示前仓、中仓、后仓。 决策目标是最大化总利润，即)(3800)(3100232221131211xxxxxxZMax)(2850)(3500434241333231xxxxxx)13(约束条件包括以下4个方面：1）从装载的四种货物的总重量约束，即)14(18131211xxx第23页/共97页24)15(15232221xxx)16(23333231xxx)17(12434241xxx2）三个货舱的重量限制，即)18(1041312111xxxx)19(1642322212xxxx)20(843332313xxxx3）三个货舱的空间限制，即)21(68003905806504804131211

16、1xxxx)22(870039058065048042322212xxxx)23(530039058065048043332313xxxx第24页/共97页254）三个货舱装入重量的平衡约束，即)24(81610433323134232221241312111xxxxxxxxxxxx模型求解将以上模型输入LINDO求解，可以得到：第25页/共97页26OBJECTIVE FUNCTION VALUE1) 121515.8VARIABLE VALUE REDUCED COSTX11 0.000000 400.000000X12 0.000000 57.894737X13 0.000000 400

17、.000000X21 10.000000 0.000000X22 0.000000 239.473679X23 5.000000 0.000000X31 0.000000 0.000000X32 12.947369 0.000000X33 3.000000 0.000000X41 0.000000 650.000000X42 3.052632 0.000000X43 0.000000 650.000000实际上，不妨将所得最优解作四舍五入， 第26页/共97页27结果为 货物2装入前仓10吨、装入后仓5吨； 货物3装入中仓13吨、装入后仓3吨； 货物4装入中仓3吨， 最大利润约121516元。

18、 评注 初步看来，本例与运输问题类似，似乎可以把4种货物看成4个供应点，3个货舱看成3个需求点（或者反过来，把货舱看成供应点，货物看成需求点）。但是，这里对供需量的限制包括两个方面：重量限制和空间限制，且有装载均匀要求，因此它只能看成是运输问题的一种变形和扩展。 第27页/共97页28三、钢管下料问题 某钢管零售商从钢管厂进货，将钢管按照顾客的要求切割后售出，从钢管厂进货时得到的原料钢管都是19m。（1）现有一客户需要50根4 m、20根6 m和15根8 m的钢管，应如何下料最节省？（2）零售商如果采用的不同切割模式太多，将会导致生产过程的复杂化，从而增加生产和管理成本，所以该零售商规定采用的

19、不同切割模式不能超过3种。此外，该客户除需要（1）中的三种钢管外，还需要10根5 m的钢管。应如何下料最节省。问题（1）的求解问题分析 首先，应当确定哪些切割模式是可行的。 第28页/共97页29 所谓一个切割模式，是指按照客户需要在原料钢管上安排切割的一种组合。 例如：我们可以将19 m的钢管切割成3根4 m的钢管，余料为7 m；或者将19 m的钢管切割成4 m、6 m和8 m的钢管各1根，余料为1 m。 显然，可行的切割模式是很多的。其次，应当确定哪些切割模式是合理的。 通常假设一个合理的切割模式的余料不应该大于或等于客户需要的钢管的最小尺寸。 例如：将19 m的钢管切割成3根4 m的钢管

20、，余料为7 m，可进一步将7m的余料切割成4m 钢管（余料为3 m），或者将7 m的余料切割成6 m钢管（余料为1 m）。 第29页/共97页30 在这种合理性假设下，切割模式一共有7种，如表9所示。4 m钢管根数6 m钢管根数8 m钢管根数余料（m）模式14003模式23101模式32013模式41203模式51111模式60301模式70023 问题化为在满足客户需要的条件下，按照哪些种合理的模式，切割多少根原料钢管，最为节省。 而所谓节省，可以有两种标准： 第30页/共97页31一是切割后剩余的总余料量最小， 二是切割原料钢管的总根数最小。 下面将对这两个目标分别讨论。模型建立决策变量

21、ix表示按照第i种模式（7 , 2, 1i ）切割的原料钢管的根数，显然它们应当是非负整数。 决策目标 以切割后剩余的总余料量最小为目标，则由表9可得 ) 1 (333376543211xxxxxxxZMin以切割原料钢管的总根数最少为目标，则有)2(76543212xxxxxxxZMin第31页/共97页324 m钢管根数6 m钢管根数8 m钢管根数余料（m）模式14003模式23101模式32013模式41203模式51111模式60301模式70023约束条件 为满足客户的需求，按照表9应有 )3(5023454321xxxxx)4(20326542xxxx)5(152753xxx模型求

22、解第32页/共97页33 1将（1），（3），（4），（5）构成的整数线性规划模型（加上整数约束）输入LINDO如下： Min 3x1+x2+3x3+3x4+x5+x6+3x7s.t. 4x1+3x2+2x3+x4+x5=50 x2+2x4+x5+3x6=20 x3+x5+2x7=15endgin7求解可以得到最优解如下：第33页/共97页34OBJECTIVE FUNCTION VALUE1) 27.00000VARIABLE VALUE REDUCED COST X1 0.000000 3.000000 X2 12.000000 1.000000 X3 0.000000 3.000000

23、X4 0.000000 3.000000 X5 15.000000 1.000000 X6 0.000000 1.000000 X7 0.000000 3.000000 即按照模式2切割12根原料钢管，按照模式5切割15根原料钢管，共27根，总余料量为27m。 显然，在总余料量最小的目标下，最优解将是使用余料尽可能小的切割模式（模式2和5的余料为1 m），这会导致切割原料钢管的总根数较多。第34页/共97页35 2将（2）（5）构成的整数线性规划模型（加上整数约束）输入LINDO求解，可以得到最优解如下： OBJECTIVE FUNCTION VALUE1） 25.00000VARIABLE

24、VALUE REDUCED COST X1 0.000000 1.000000 X2 15.000000 1.000000 X3 0.000000 1.000000 X4 0.000000 1.000000 X5 5.000000 1.000000 X6 0.000000 1.000000 X7 5.000000 1.000000 即按照模式2切割15根原料钢管、按模式5切割5根、按模式7切割5根、共25根，可算出总余料量为35 m。 与上面得到的结果相比，总余料量增加了8 m，但是所用的原料钢管的总根数减少了2根。 在余料没有用途情况下，通常选择总根数最小为目标。 第35页/共97页36问题

25、（2）的求解问题（2）：零售商如果采用的不同切割模式太多，将会导致生产过程的复杂化，从而增加生产和管理成本，所以该零售商规定采用的不同切割模式不能超过3种。此外，该客户除需要（1）中的三种钢管外，还需要10根5 m的钢管。应如何下料最节省。问题分析 按照（1）的思路，可以通过枚举法首先确定哪些切割模式是可行的。但由于需求的钢管规格增加到4种，所以枚举法的工作量较大。 下面介绍的整数非线性规划模型，可以同时确定切割模式和切割计划，是带有普遍性的方法。 第36页/共97页37 同（1）类似，一个合理的切割模式的余料不应该大于或等于客户需要的钢管的最小尺寸（本题中为4 m），切割计划中只使用合理的切

26、割模式，而由于本题中参数都是整数，所以合理的切割模式的余量不能大于3 m。 此外，这里我们仅选择总根数最小为目标进行求解。模型建立决策变量 由于不同切割模式不能超过3种， 可以用ix表示按照第i种模式（3, 2, 1i ）切割的原料钢管的根数，显然它们应当是非负整数。 第37页/共97页38 设所使用的第i种切割模式下每根原料钢管生产4 m，5 m，6 m和8 m的钢管数量分别为iiiirrrr4321,（非负整数）。 决策目标 切割原料钢管的总根数最小，目标为)6(321xxxMin约束条件 为满足客户的需求，应有)7(50313212111xrxrxr)8(10323222121xrxrx

27、r)9(20333232131xrxrxr)10rxrxr第38页/共97页39 每一种切割模式必须可行、合理，所以每根原料钢管的成品量不能超过19m，也不能少于16 m（余量不能大于3 m），于是)11(1986541641312111rrrr)12(1986541642322212rrrr)13(1986541643332313rrrr模型求解 在（7）（10）式中出现决策变量的乘积，是一个整数非线性规划模型，虽然用LINGO软件可以直接求解，但我们发现运行很长时间也难以得到最优解。 为了减少运行时间，可以增加一些显然的约束条件，从而缩小可行解的搜索范围。 第39

28、页/共97页40 例如，由于3种切割模式的排列顺序是无关紧要的，所以不妨增加以下约束)14(321xxx 又例如，我们注意到所需原料钢管的总根数有着明显的上界和下界。 首先，无论如何，原料钢管的总根数不可能少于19158206105504根即至少需26根。 其次，考虑一种非常特殊的生产计划： 第一种切割模式下只生产4m钢管，一根原料钢管切割成4根4 m钢管，为满足50根4 m钢管的需求，需要13根原料钢管； 第40页/共97页41 第二种切割模式下只生产5 m、6 m钢管，一根原料钢管切割成1根5 m钢管和2根6 m钢管，为满足10根5 m和20根6 m钢管的需求，需要10根原料钢管； 第三种

29、切割模式下只生产8 m钢管，一根原料钢管切割成2根8 m钢管，为满足15根8 m钢管的需求，需要8根原料钢管。 于是满足要求的这种生产计划共需13+10+8=31根原料钢管，这就得到了最优解的一个上界。 所以可增加以下约束)15(3126321xxx将（6）（15）构成的模型输入LINGO如下：第41页/共97页42model：min=x1+x2+x3；x1*r11+x2*r12+x3*r13=50；x1*r21+x2*r22+x3*r23=10；x1*r31+x2*r32+x3*r33=20；x1*r41+x2*r42+x3*r43=15；4*r11+5*r21+6*r31+8*r41=19

30、；4*r12+5*r22+6*r32+8*r42=19；4*r13+5*r23+6*r33+8*r43=16；4*r12+5*r22+6*r32+8*r42=16；4*r13+5*r23+6*r33+8*r43=16；x1+x2+x3=26；x1+x2+x3=x2；x2=x3；gin(x1) ；gin(x2) ；gin(x3) ；gin(r11) ；gin(r12) ；gin(r13) ；gin(r21) ；gin(r22) ；gin(r23) ；gin(r31) ；gin(r32) ；gin(r33) ；gin(r41) ；gin(r42) ；gin(r43) ；end第42页/共97页43

31、 注：LINGO软件用于求解非线性规划（包括含有整数变量的），输入总是以“model：”开始，以“end”结束；中间的语句必须以“；”分开。约束中“gin(x1)”表示x1为整数，其他类似（如果要表示x1为0-1整数，应该用“int(x1)”）。在LINGO8.0版本中，缺省设置假定所有变量非负，所以上面的输入中没有关于变量非负的显式约束。经过运行（一般需要几分钟），得到输出如下：第43页/共97页44Local optimal solution found at iteration： 12211Objective value： 28.00000 Variable Value Reduced

32、Cost X1 10.00000 0.000000 X2 10.00000 2.000000 X3 8.00000 1.000000 R11 3.00000 0.000000 R12 2.00000 0.000000 R21 0.00000 0.000000 R22 1.00000 0.000000 R31 1.00000 0.000000 R32 1.00000 0.000000 R33 0.00000 0.000000 R41 0.00000 0.000000 R42 0.00000 0.000000 R43 2.00000 0.000000第44页/共97页45 即按照模式1，2，3分别

33、切割10，10，8根原料钢管，使用原料钢管总根数为28根， 第一种切割模式下一根原料钢管切割成3根4m钢管和1根6 m钢管； 第二种切割模式下一根原料钢管切割成2根4 m钢管、1根5 m钢管和1根6 m钢管； 第三种切割模式下一根原料钢管切割成2根8 m钢管。第45页/共97页46 5.3 动态规划模型例8：最短线路问题0A6A 问题：现选择一条从 到 的铺管线路，使总距离最短？ 若用穷举法要算23222148种不同线路，比较这48种结果即可得出，但当段数增加，且各段选择也增加时，穷举法将变得非常庞大，以至利用计算机都十分困难。 第46页/共97页47下面用动态规划的方法计算最短线路问题的特性

34、： 如果最短线路在第k站通过点 ，则这一线路在由 出发到达终点的那一部分线路，对于从 点到达终点的所有可能选择的不同线路来说，必定也是距离最短的。（反正法） kPkPkP 最短线路问题的这一特性启示我们，从最后一段 开始，用从后向前逐步递推的方法，求出各点到 的最短线路，最后求得从 到 的最短线路。 6A0A6A第47页/共97页48k6时： 设 表示由 到 的最短距离； )(56Af5A6A设 表示由 到 的最短距离； )(56Bf5B6A显然 4)(56Af3)(56Bfk5时： 如果 表示由 到 的最短距离。 )(45Af4A6Amin)(45Af)(),()(),(56545654Bf

35、BAdAfAAd73543min（以下类似定义）（以下类似定义）第48页/共97页49最短线路是 654AAA)(45Bf53245min)(),()(),(min5654556545BfBBdAfABd最短线路是 654ABB93646min)(),()(),(min)(565455654545BfBCdAfACdCf最短线路是 654ABC第49页/共97页50k4时： 75272min)(),()(),(min)(454344543434BfBAdAfAAdAf最短线路是 6543ABBA69251min)(),()(),(min)(454344543434CfCBdBfBBdBf最短线

36、路是 6543ABBB第50页/共97页5189353min)(),()(),(min)(454344543434CfCCdBfBCdCf最短线路是 6543ABBCk3时： 136876min)(),()(),(min)(343233432323BfBAdAfAAdAf最短线路是 65432ABBAA第51页/共97页52106573min)(),()(),(min)(343233432323BfBBdAfABdBf最短线路是 65432ABBAB98363min)(),()(),(min)(343233432323CfCCdBfBCdCf最短线路是 65432ABBBC第52页/共97页5

37、3128468min)(),()(),(min)(343233432323CfCDdBfBDdDf最短线路是 65432ABBCDk2时： 1396103131min)(),()(),()(),(min)(23212232122321212CfCAdBfBAdAfAAdAf最短线路是 654321ABBABA第53页/共97页541612697108min)(),()(),()(),(min)(23212232122321212DfDBdCfCBdBfBBdBf最短线路是 出发点只有 0A18163135min)(),()(),(min)(121011210101BfBAdAfAAdAf最短线

38、路是 6543210ABBABAA最短距离为18。654321ABBBCB第54页/共97页55说明 1)此例揭示了动态规划的基本思想。 2)动态规划方法比穷举法（48种）大大节省了计算量。 3)计算结果不仅得到了 到 的最短线路和最短距离，而且得到了其它各点到 的最短线路和最短距离，这对于很多实际问题来说是很有用处的。 0A6A6A动态规划法求解的数学描述 讨论动态规划中最优目标函数的建立，一般有下列术语和步骤： 、阶段 用动态规划求解多阶段决策系统时，要根据具体情况，将系统适当地分成若干个阶段，以便分若干个阶段求解，描述阶段的变量称为阶段变量。 第55页/共97页56 上例分六个阶段，是一

39、个六阶段的决策过程。例中由系统的最后阶段向初始阶段求最优解的过程称为动态规划的逆推解法。 、状态状态表示系统在某一阶段所处的位置或状态。 上例中第一阶段有一个状态， ；即即0A第二阶段有两个状态， ；即即,11BA 过程的状态可用状态变量 来描述，某个阶段所有可能状态的全体可用状态集合来描述， kx01AS 如如,22223112DCBASBAS第56页/共97页57、决策 某一阶段的状态确定之后，从该状态演变到下一阶段某一状态所作的选择称为决策。描述决策的变量称为决策变量 如上例中在第k阶段用 表示处于 状态时的决策变量。 )(kkxukx决策变量限制的范围称为允许决策集合。 用 表示第k阶

40、段从 出发的决策集合。 )(kkxDkx、策略 由每阶段的决策 (i1,2,n)组成的决策函数序列称为全过程策略或简称策略，用p表示， )(iixu)(,),(),()(22111nnxuxuxuxP即即第57页/共97页58 由系统的第k个阶段开始到终点的决策过程称为全过程的后部子过程，相应的策略称为后部子过程策略。 用 表示k子过程策略， )(kkxP)(,),(),()(11nnkkkkkkxuxuxuxP即即 对于每一个实际的多阶段决策过程，可供选择的策略有一定的范围限制，这个范围称为允许策略集合。 允许策略集合中达到最优效果的策略称为最优策略。 、状态转移 某一阶段的状态变量及决策变

41、量取定后，下一阶段的状态就随之而定。 第58页/共97页59 设第k个阶段的状态变量为 ，决策变量为 ，则第k+1个阶段的状态 用 表示从k阶段到k+1阶段的状态转移规律，称它为状态转移方程。kx)(kkxu1kx),(1kkkkuxTx、阶段效益 系统某阶段的状态一经确定，执行某一决策所得的效益称为阶段效益，它是整个系统效益的一部分，是 阶段状态和 阶段决策的函数，记为 kxku),(kkkuxW、指标函数 指标函数是系统执行某一策略所产生的效益的数量表示，根据不同的实际问题，效益可以是利润、距离、产量或资源的耗量等。 第59页/共97页60 指标函数可以定义在全过程上，也可以定义在后部子过

42、程上。指标函数往往是各阶段效益的某种和式，取最优策略时的指标函数称为最优策略指标。 如上例中， 表示从 出发到终点 的最优策略指标。 )(45Af4A6A上例中 显然为零，称它为边值条件。 )(66Af 而动态规划的求解就是对kn,n-1,2,1逐级求出最优策略指标的过程。 、动态规划的基本方程)(),(min)(11kkkkkukkxfuxWxfk第60页/共97页61例9：机器负荷分配问题 某种机器可以在高低两种负荷下生产，年产量与年初投入生产的机器数有关。在高负荷下生产时，年产量 ，式中 为投入生产的机器数，年终的完好机器数为 ，称系数0.7为机器完好率。在低负荷下生产时，年产量 ，式中

43、 为投入生产的机器数，机器完好率为0.9，设开始时，完好的机器数为 台，要求制定一个五年计划，在每年开始时决定如何重新分配完好机器在两种不同负荷下工作的数量，使五年的总产量最高。 118us 1u17 . 0 u225us 2u10001x第61页/共97页62解：此问题与上例类似。 设阶段变量k表示年度； 状态变量 是第k年初拥有的完好机器数（也是第k-1年度末完好机器数）。 kx 决策变量 规定为第k年度中分配在高负荷下生产的机器数。 ku 于是 是该年度分配在低负荷下生产的机器数。 kkux k=2 k=3 k=4 k=5 1k1x2x3x4x5x 1u2u3u4u5u第62页/共97页

44、63记 表示第k年到第五年末的最高总产量)(kkxfk5时)(58max)(55505555uxuxfxu5550835max55xuxxu最优点最优点5*5xu 这说明第5年初要把全部完好机器投入高负荷下生产。 k4时4444452 . 09 . 0)(9 . 07 . 0uxuxux因为因为)()(58max)(5544404444xfuxuxfxu所所以以)2 . 09 . 0(835max4444044uxuxxu第63页/共97页6444406 .134 . 12 .12max44xuxxu最优点最优点4*4xu k3时3333342 . 09 . 0)(9 . 07 . 0uxux

45、ux因为因为)()(58max)(4433303333xfuxuxfxu所所以以)2 . 09 . 0(6 .1335max3333033uxuxxu33305 .1728. 024.17max33xuxxu最优点最优点3*3xu 第64页/共97页65k2时2222232 . 09 . 0)(9 . 07 . 0uxuxux因为因为)()(58max)(3322202222xfuxuxfxu所所以以)2 . 09 . 0(5 .1735max2222022uxuxxu22208 .205 . 075.20max22xuxxu最优点最优点0*2uk1时10001x因为因为1111122 . 0

46、9 . 0)(9 . 07 . 0uxuxux)()(58max)1000(221110111xfuxufxu所所以以)2 . 09 . 0(8 .2035max1111011uxuxxu第65页/共97页66)2 . 09 . 0(8 .2035max1111011uxuxxu16. 172.23max11011uxxu2370010007 .237 .231x最优点最优点0*1u 由此知五年最高总产量为23700再由上递推知 10001x0*1u9002x0*2u8103x810*3u5674x567*4u3975x397*5u第66页/共97页67高负荷生产的完好机器的最优组合简记：39

47、7,567,810, 0, 0,*5*2*1uuu 这表明在前两年年初全部完好机器投入低负荷生产，后三年年初全部完好机器投入高负荷生产。 第五年末的完好机器数为 0.7397278台 在此例中，我们仅考虑最高产量，而未考虑五年计划后的完好机器数。 问题1：若计划为n个年度，怎样决策？ 问题2：若要求在第5年末完好的机器数为500台，如何决策使5年总产量最高？ 第67页/共97页68这类问题称为固定终端问题1x2x3x4x5x5006x1u2u3u4u5u由上讨论知：状态转移方程仍为 ) 1 (2 . 09 . 0)(9 . 07 . 01kkkkkkuxuxux 表示第k年初开始到第5年末的最

48、高产量，称为最优值函数，其递推关系为 )(kkxf)2()2 . 09 . 0()(58(max)(10kkkkkkxukkuxfuxuxfkkk=1,2,3,4,50)(66xf第68页/共97页69其中 为第k段的效益值，即第k年的产量。 )(58),(kkkkkkuxuuxy 表示第6年的产量不计算在总产量之内，故为零。 0)(66xf由假设 ， 5006x又根据(1)得 5562 . 09 . 0uxx一般地，当 确定后，选择 来确定 ，现在 已经给定，故 已经没有选择余地，它由 和 确定。 5x5u6x6x5u6x5x于是25005 . 455 . 45655xxxu第69页/共97

49、页70由(2)可知035max)(5505555uxxfxu)25005 . 4(3555xx75005 .185x)2 . 09 . 0(35max)(4454404444uxfuxxfxu7500)2 . 09 . 0(5 .1835max4444044uxuxxu.max750070652144044uxxu75007 .214x最优值 0*4u第70页/共97页717500)2 . 09 . 0(7 .2135max)(333303333uxuxxfxu75005 .243x最优值 0*3u类似地得到 75007 .21)(222xxf0*2u75004 .29)(111xxf0*1u

50、21900750029400)1000(1f这是五年最高产量 这表明，如果限定五年后的完好机器数为500台，则总产量低于无限制的情况，最优策略也相应有所变化，由第一年到第四年全部完好机器投入低负荷生产。第71页/共97页72 为了计算第5年投入高负荷生产的完好机器数 ，先计算 5u9009 . 012xx8109 . 023xx7299 . 034xx6569 . 045xx所以 45225005 . 455xu 即第5年有452台机器投入高负荷生产，其余投入低负荷生产。 第72页/共97页733 存贮模型 工厂为了连续生产必须贮存一些原材料，商店为了连续销售必须贮存一些商品，象这类的实际问题

51、当然要考虑其经济效益。因此就必须考虑一个贮存多少的问题。原料、商品存得太多，贮存费用高，存得太少则无法满足需求。 如：元。每次的订货费为元，件，每件每天储存费为某商品每天出售10001010元。每天费用件，则无储存费，次订、若每天订一次货，每1000101件，则储存费为天订一次货，每次订、若每100102101010801090元4500第73页/共97页74平均每天的费用1010004500）（元550件，则储存费为天订一次货，每次订、若每30030310101028010290元43500平均每天的费用30100043500）（元1483最好？问题：多少天订一次货第74页/共97页75 问

52、题：寻求一个好的存贮策略，即多长时间订一次货，每次订多少货才能使总费用最少？ 模型一：不允许缺货的存贮模型建模目的： 在单位时间的需求量为常数的情况下，制定最优存贮策略，即多长时间订一次货，每次订多少货，使总费用最小。 模型假设、每次订货费为 ，每天每吨货物贮存费为 ； 1c2c、每天的货物需求量为r吨； 、每T天订货Q吨，当贮存量降到零时，订货立即到达（即不允许缺货）。 第75页/共97页76 对于第3条假设中订货可以瞬时完成，可解释为由于需求是确定和已知的，只要提前订货使得贮存量为零时立即进货就行了，当然，贮存量降到零不符合实际生产需要，应该有一个最低库存量，可以认为模型中的贮存量是在这个

53、最低存量之上计算的。 模型建立 订货周期T、订货量Q与每天需求量r之间满足 QrT (3-1) 订货后贮存量由Q均匀地下降，记任意时刻t的贮存量为q，则q(t)的变化规律可以用图表示： 第76页/共97页77 考察一个订货周期的总费用： 订货费为 ； 1c贮存费是 Tdttqc02)(因为积分值恰是图中三角形面积A，显然A 。 QT21第77页/共97页78由(3-1)式可知一个订货周期T内的总费用为)23(21221rTccc于是平均每天的费用为)33(21)(21rTcTcTcTc 所以制定最优贮存策略可归结为：求订货周期T,使C(T)最小。 思考：为什么不用 作为目标函数？ c 利用微分

54、法， 得得：令令0dTdc)43(221rccT第78页/共97页79再根据(3-1)式有 )53(221crcQ (3-5)式是经济理论中著名的经济订货批量公式（简称公式）。 (3-5)式表明：订货费越高，需求量r越大，订货批量Q应越大；贮存费越高，则每次订货批量应越小。这些当然符合常识，但公式中平方根关系是凭常识难以得到的。 说明：货物本身的价格不影响最优贮存策略。 因为若记每吨货物价格为k，则一周期T的总费用 中应添加一项kQ，由于QrT，所以(3-3)中增加一常数项kr对求解结果(3-4),(3-5)无影响。 c第79页/共97页80 例1.某商店有甲商品出售，每单位甲商品价格500元

55、，其存贮费每年为价格的20，甲商品每次订购费需20元，顾客对甲商品的年需求量为365单位，而且需求率为常数（即顾客每天需求商品1单位），在不缺货的条件下，求最优策略。 解：以年为单位，则需求速度： r365 201c100%205002c于是订货批量 12100365202221crcQ（单位） 订货周期 （天天）年年1236512rQT第80页/共97页81即每隔12天订一次货，每次订12个单位为最优策略。 若按天为单位： 则r1， 201c365100365%205002c)(123651001202221单单位位crcQ)(12112天天T这与以年为单位结果相同。第81页/共97页82模

56、型二：允许缺货的存贮模型 允许缺货就是企业或商店可以在存贮降到零后，还可以再等一段时间订货。缺货时因失去销售机会而使利润减少，减少的利润可以视为因缺货而付出的费用，称缺货费；于是此模型的第1,2条假设与不允许缺货的存贮模型相同，而第3条该为： 每隔T天订货Q吨，允许缺货，每天每吨货物缺货费为 。 3c缺货时贮存量视作负值，q(t)图形如下： 第82页/共97页83 货物在t 时售完，有一段时间缺货（这时需求量仍为r），在tT时下一次订货量Q到达。1T于是 1rTQ 一个订货周期T内的总费用：订货费 1c 贮存费 102)(Tdttqc 由图知 10121)(QTAdttqT缺货费 dttqcT

57、T1)(3由图知21)(21)(1TTrBdttqTT所以总费用 213121)(2121TTrcQTccc第83页/共97页84每天平均费用TTTrcTQTcTcTcQTC2)(2),(213121rTQrTcrTQcTc2)(223221下面问题是当T,Q为何值时，使C(T,Q)最小。利用微分法， 0, 0QcTc令令求出T,Q的最优值，记为 QT,332212cccrccT323212ccccrcQ第84页/共97页85)( 1332ccc 记记则与不允许缺货的存贮模型相比TT QQ TT 显然显然QQ 即：允许缺货时订货周期应增大，而订货批量应减少。 当缺货费 越大时,3c 和 越接近

58、T和Q。 TQ时时，当当3cTTQQ 这个结果是合理的，因为 即缺货造成的损失无限变大，相当于不允许缺货。 3c第85页/共97页86问题 1、某厂每天需要角钢100吨，目前每月订购一次，每次订购的费用为2500元，每天每吨角钢的储存费为0.18元。 （1）如果不允许缺货，问是否应改变订货策略，改变后能节省多少费用。 （2）如果允许缺货，每天每吨的缺货费为0.4元，试制订订策略。 2、饮料厂某种饮料生产能力为5000L/天，需求为2000L/天，每次生产准备费为300元，生产成本为10元/L，而资金为贷款，贷款月息为3%，试制订生产计划。 第86页/共97页874 森林救火的数学模型 问题：森林失火了，消防站接到报警后应派多少消防队员前去救火？ 问题分析 森