运筹与优化模型.pptx

《运筹与优化模型.pptx》由会员分享，可在线阅读，更多相关《运筹与优化模型.pptx（97页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、1目标函数 约束条件 其中(,)为决策向量，满足约束条件的(,)称为可行决策。线性规划问题就是指目标函数为诸决策变量的线性函数，给定的条件可用诸决策变量的线性等式或不等式表示的决策问题。线性规划求解的有效方法是单纯形法（进一步了解可参考有关书籍），当然简单的问题也可用图解法。第1页/共97页2如用图解法求解例1：由约束条件决定的可行域如图阴影所示，目标函数的等值线向右上方移动时其值增大，在到达点 时f取得最大值；第2页/共97页3当 =20,=24时，即产品A生产20t，产品B生产24t时，生产方案最优。其最大利润为：7201224428千元例2：某两个煤厂 .，每月进煤数量分别为60t和10

2、0t联合供应3个居民区 。3个居民区每月对煤的需求量依次分别为50t,70t,40t，煤厂 离3个居民区 的距离依次为10km,5km,6km，煤厂 离3个居民区 的距离依次分别为4km,8km,12km，问如何分配供煤量使得运输费（即tkm）达到最小？第3页/共97页4 解：设 表示 (i=1.2)煤厂提供给 （居民区的煤量；f表示总运输费此问题归结为：第4页/共97页5一般线性规划问题的数学表达式：s.t 第5页/共97页6例3：生产组织与计划问题 设有m种资源，第i(i=1,2,m)种资源的现存量为 ，现要生产n种产品，已知生产j(j=1,2,n)种产品时，每单位产品需要第i种资源量为

3、，而每单位j种产品可得利润 ，问如何组织生产才能使利润最大？解：用 表示生产第j(j=1,2,n)种产品的计划数，上述问题可归结为如下的数学问题：第6页/共97页7 二、整数规划模型对于线性规划：决策变量是连续变量，最优解可能是小数或分数。第7页/共97页8 但是在许多实际问题中，往往要求所得的解为整数，例如投资项目的选择、机器的台数、完成工作的人数、装货的车数等，分数和小数的答案就没有现实意义了。在现性规划中，若限制 (j=1,2,n)是非负整数，则这种线性规划问题称为整数规划问题。第8页/共97页9 例4：分配问题 假设某工厂用m台机床加工n种零件。在一个生产周期内，第i(i=1,2,m)

4、台机床只能工作 个机时，而第j(j=1,2,n)种零件必须完成 个，又第i台机床加工第j种零件所需机时和成本分别为 （机时个）和 （元个）。问在这个生产周期内怎样安排各机床的生产任务，才能使得既完成加工任务，又使总的加工成本最少？解：在一个生产周期内，假设第i台机床加工第j种零件的个数为 。由于 是零件个数，因此 必须是非负整数，第9页/共97页10本问题的数学模型为：第10页/共97页11三、非线性规划模型非线性规划模型的一般形式为：f(X)为目标函数，(2)、(3)为约束条件，(2)为不等式约束，(3)为等式约束；若只有(1)称为无约束问题。第11页/共97页12第12页/共97页13例5

5、：容器的设计问题 某公司专门生产储藏用容器，定货合同要求该公司制造一种敞口的长方体容器，容积恰好为12立方米，该容器的底必须为正方形，容器总重量不超过68公斤。已知用作容器四壁的材料为每平方米10 元，重3公斤；用作容器底的材料每平方米20元，重2公斤。试问制造该容器所需的最小费用是多少？模型建立 设该容器底边长和高分别为 米、米，则问题的数学模型为（容器的费用）第13页/共97页14一般来说，非线性规划模型的求解要比线性规划模型求解困难得多，虽然现在已经发展了许多非线性规划的算法，但到目前为止，还不象线性规划那样有通用的单纯形算法，而是各种算法都有自己特定的适用范围，如求解法有：最速下降法、

6、牛顿法、可行方向法、惩罚函数法等。尽管如此，非线性规划的实际应用还是相当广泛的。第14页/共97页15 5.2 实际问题中的优化模型一、投资策略 某部门现有资金10万元，五年内有以下投资项目供选择：项目A,从第一年到第四年每年初投资，次年末收回本金且获利15%；项目B，第三年初投资，第五年末收回本金且获利25%，最大投资额为4万元；项目C，第二年初投资，第五年末收回本金且获利40%，最大投资额为3万元；项目D，每年初投资，年末收回本金且获利6%。问如何确定投资策略使第五年末本息总额最大。第15页/共97页16问题的目标函数是第五年末的本息总额，决策变量是每年初各个项目的投资额，约束条件是每年初

7、拥有的资金。用表示第年初（）项目分别代表A,B,C,D)的投资额，根据所给条件只有下表1列出的才是需要求解的。项目 年份 A B C D 1 2 3 4 5 第16页/共97页17 因为项目D 每年初可以投资，且年末能收回本息，所以每年初都应把资金全部投出去，项目A,从第一年到第四年每年初投资，次年末收回本金且获利15%；项目B，第三年初投资，第五年末收回本金且获利25%，最大投资额为4万元；项目C，第二年初投资，第五年末收回本金且获利40%，最大投资额为3万元；项目D，每年初投资，年末收回本金且获利6%。由此可得如下的约束条件：第一年初：第二年初：第三年初 第四年初：第五年初：项目B,C对投

8、资额的限制：第17页/共97页18项目A,从第一年到第四年每年初投资，次年末收回本金且获利15%；项目B，第三年初投资，第五年末收回本金且获利25%，最大投资额为4万元；项目C，第二年初投资，第五年末收回本金且获利40%，最大投资额为3万元；项目D，每年初投资，年末收回本金且获利6%。每项投资应为非负的：第五年末本息总额为第18页/共97页19由此得投资问题的线性规划模型如下：s.t.第19页/共97页20求解得 即第1年项目A,D分别投资3.8268和6.1732(万元)；第2年项目A,C分别投资3.5436和3(万元)；第3年项目A,B分别投资0.4008和4(万元)；第4年项目A投资4.

9、0752(万元)；第5年项目D投资0.4609(万元)；5年后总资金 14。375万元，即盈利43.75%.第20页/共97页21二、货机装运问题 某架货机有三个货舱：前仓、中仓、后仓。三个货舱所能装载的货物的最大重量和体积都有限制，如表3所示。并且，为了保持飞机的平衡，三个货舱中实际装载货物的重量必须与其最大容许重量成比例。前仓中仓后仓重量限制（吨）10168体积限制（米3）680087005300 现有四类货物供该货机本次飞行装运，其有关信息如表4，最后一列指装运后所获得的利润。第21页/共97页22重量（吨）空间（米3/吨）利润（元/吨）货物1184803100货物2156503800货

10、物3235803500货物4123902850应如何安排装运，使该货机本次飞行获利最大？模型假设 问题中没有对货物装运提出其它要求，我们可作如下假设：1）每种货物可以分割到任意小；2）每种货物可以在一个或多个货舱中任意分布；第22页/共97页233）多种货物可以混装，并保证不留空隙。模型建立决策变量：表示第i种货物装入第j个货舱的重量（吨），货舱j=1,2,3分别表示前仓、中仓、后仓。决策目标是最大化总利润，即约束条件包括以下4个方面：1）从装载的四种货物的总重量约束，即第23页/共97页242）三个货舱的重量限制，即3）三个货舱的空间限制，即第24页/共97页254）三个货舱装入重量的平衡约

11、束，即模型求解将以上模型输入LINDO求解，可以得到：第25页/共97页26OBJECTIVE FUNCTION VALUE1)121515.8VARIABLE VALUE REDUCED COSTX11 0.000000 400.000000X12 0.000000 57.894737X13 0.000000 400.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

12、 0.000000 650.000000X42 3.052632 0.000000X43 0.000000 650.000000实际上，不妨将所得最优解作四舍五入，第26页/共97页27结果为 货物2装入前仓10吨、装入后仓5吨；货物3装入中仓13吨、装入后仓3吨；货物4装入中仓3吨，最大利润约121516元。评注 初步看来，本例与运输问题类似，似乎可以把4种货物看成4个供应点，3个货舱看成3个需求点（或者反过来，把货舱看成供应点，货物看成需求点）。但是，这里对供需量的限制包括两个方面：重量限制和空间限制，且有装载均匀要求，因此它只能看成是运输问题的一种变形和扩展。第27页/共97页28三、钢

13、管下料问题 某钢管零售商从钢管厂进货，将钢管按照顾客的要求切割后售出，从钢管厂进货时得到的原料钢管都是19m。（1）现有一客户需要50根4 m、20根6 m和15根8 m的钢管，应如何下料最节省？（2）零售商如果采用的不同切割模式太多，将会导致生产过程的复杂化，从而增加生产和管理成本，所以该零售商规定采用的不同切割模式不能超过3种。此外，该客户除需要（1）中的三种钢管外，还需要10根5 m的钢管。应如何下料最节省。问题（1）的求解问题分析 首先，应当确定哪些切割模式是可行的。第28页/共97页29 所谓一个切割模式，是指按照客户需要在原料钢管上安排切割的一种组合。例如：我们可以将19 m的钢管

14、切割成3根4 m的钢管，余料为7 m；或者将19 m的钢管切割成4 m、6 m和8 m的钢管各1根，余料为1 m。显然，可行的切割模式是很多的。其次，应当确定哪些切割模式是合理的。通常假设一个合理的切割模式的余料不应该大于或等于客户需要的钢管的最小尺寸。例如：将19 m的钢管切割成3根4 m的钢管，余料为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模式412

15、03模式51111模式60301模式70023 问题化为在满足客户需要的条件下，按照哪些种合理的模式，切割多少根原料钢管，最为节省。而所谓节省，可以有两种标准：第30页/共97页31一是切割后剩余的总余料量最小，二是切割原料钢管的总根数最小。下面将对这两个目标分别讨论。模型建立决策变量 表示按照第i种模式（）切割的原料钢管的根数，显然它们应当是非负整数。决策目标 以切割后剩余的总余料量最小为目标，则由表9可得 以切割原料钢管的总根数最少为目标，则有第31页/共97页324 m钢管根数6 m钢管根数8 m钢管根数余料（m）模式14003模式23101模式32013模式41203模式51111模式

16、60301模式70023约束条件 为满足客户的需求，按照表9应有 模型求解第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.0000

17、00 1.000000 X3 0.000000 3.000000 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 FUN

18、CTION VALUE1）25.00000VARIABLE 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根。在余料没有用途情况下

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

20、小尺寸（本题中为4 m），切割计划中只使用合理的切割模式，而由于本题中参数都是整数，所以合理的切割模式的余量不能大于3 m。此外，这里我们仅选择总根数最小为目标进行求解。模型建立决策变量 由于不同切割模式不能超过3种，可以用表示按照第i种模式（）切割的原料钢管的根数，显然它们应当是非负整数。第37页/共97页38 设所使用的第i种切割模式下每根原料钢管生产4 m，5 m，6 m和8 m的钢管数量分别为（非负整数）。决策目标 切割原料钢管的总根数最小，目标为约束条件 为满足客户的需求，应有第38页/共97页39 每一种切割模式必须可行、合理，所以每根原料钢管的成品量不能超过19m，也不能少于16

21、 m（余量不能大于3 m），于是模型求解 在（7）（10）式中出现决策变量的乘积，是一个整数非线性规划模型，虽然用LINGO软件可以直接求解，但我们发现运行很长时间也难以得到最优解。为了减少运行时间，可以增加一些显然的约束条件，从而缩小可行解的搜索范围。第39页/共97页40 例如，由于3种切割模式的排列顺序是无关紧要的，所以不妨增加以下约束 又例如，我们注意到所需原料钢管的总根数有着明显的上界和下界。首先，无论如何，原料钢管的总根数不可能少于根即至少需26根。其次，考虑一种非常特殊的生产计划：第一种切割模式下只生产4m钢管，一根原料钢管切割成4根4 m钢管，为满足50根4 m钢管的需求，需要

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

23、+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；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

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

25、d at iteration：12211Objective value：28.00000 Variable Value Reduced 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.0000

26、00 R42 0.00000 0.000000 R43 2.00000 0.000000第44页/共97页45 即按照模式1，2，3分别切割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：最短线路问题 问题：现选择一条从 到 的铺管线路，使总距离最短？若用穷举法要算23222148种不同线路，比较这48种结果即可得出，但当段数增加，且各段选择也增

27、加时，穷举法将变得非常庞大，以至利用计算机都十分困难。第46页/共97页47下面用动态规划的方法计算最短线路问题的特性：如果最短线路在第k站通过点 ，则这一线路在由 出发到达终点的那一部分线路，对于从 点到达终点的所有可能选择的不同线路来说，必定也是距离最短的。（反正法）最短线路问题的这一特性启示我们，从最后一段 开始，用从后向前逐步递推的方法，求出各点到 的最短线路，最后求得从 到 的最短线路。第47页/共97页48k6时：设 表示由 到 的最短距离；设 表示由 到 的最短距离；显然 k5时：如果 表示由 到 的最短距离。第48页/共97页49最短线路是 最短线路是 最短线路是 第49页/共

28、97页50k4时：最短线路是 最短线路是 第50页/共97页51最短线路是 k3时：最短线路是 第51页/共97页52最短线路是 最短线路是 第52页/共97页53最短线路是 k2时：最短线路是 第53页/共97页54最短线路是 出发点只有 最短线路是 最短距离为18。第54页/共97页55说明 1)此例揭示了动态规划的基本思想。2)动态规划方法比穷举法（48种）大大节省了计算量。3)计算结果不仅得到了 到 的最短线路和最短距离，而且得到了其它各点到 的最短线路和最短距离，这对于很多实际问题来说是很有用处的。动态规划法求解的数学描述 讨论动态规划中最优目标函数的建立，一般有下列术语和步骤：、阶

29、段 用动态规划求解多阶段决策系统时，要根据具体情况，将系统适当地分成若干个阶段，以便分若干个阶段求解，描述阶段的变量称为阶段变量。第55页/共97页56 上例分六个阶段，是一个六阶段的决策过程。例中由系统的最后阶段向初始阶段求最优解的过程称为动态规划的逆推解法。、状态状态表示系统在某一阶段所处的位置或状态。上例中第一阶段有一个状态，第二阶段有两个状态，过程的状态可用状态变量 来描述，某个阶段所有可能状态的全体可用状态集合来描述，第56页/共97页57、决策 某一阶段的状态确定之后，从该状态演变到下一阶段某一状态所作的选择称为决策。描述决策的变量称为决策变量 如上例中在第k阶段用 表示处于 状态

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

31、+1个阶段的状态 用 表示从k阶段到k+1阶段的状态转移规律，称它为状态转移方程。、阶段效益 系统某阶段的状态一经确定，执行某一决策所得的效益称为阶段效益，它是整个系统效益的一部分，是 阶段状态和 阶段决策的函数，记为、指标函数 指标函数是系统执行某一策略所产生的效益的数量表示，根据不同的实际问题，效益可以是利润、距离、产量或资源的耗量等。第59页/共97页60 指标函数可以定义在全过程上，也可以定义在后部子过程上。指标函数往往是各阶段效益的某种和式，取最优策略时的指标函数称为最优策略指标。如上例中，表示从 出发到终点 的最优策略指标。上例中 显然为零，称它为边值条件。而动态规划的求解就是对k

32、n,n-1,2,1逐级求出最优策略指标的过程。、动态规划的基本方程第60页/共97页61例9：机器负荷分配问题 某种机器可以在高低两种负荷下生产，年产量与年初投入生产的机器数有关。在高负荷下生产时，年产量 ，式中 为投入生产的机器数，年终的完好机器数为 ，称系数0.7为机器完好率。在低负荷下生产时，年产量 ，式中 为投入生产的机器数，机器完好率为0.9，设开始时，完好的机器数为 台，要求制定一个五年计划，在每年开始时决定如何重新分配完好机器在两种不同负荷下工作的数量，使五年的总产量最高。第61页/共97页62解：此问题与上例类似。设阶段变量k表示年度；状态变量 是第k年初拥有的完好机器数（也是

33、第k-1年度末完好机器数）。决策变量 规定为第k年度中分配在高负荷下生产的机器数。于是 是该年度分配在低负荷下生产的机器数。k=2 k=3 k=4 k=5 第62页/共97页63记 表示第k年到第五年末的最高总产量k5时 这说明第5年初要把全部完好机器投入高负荷下生产。k4时第63页/共97页64k3时第64页/共97页65k2时k1时第65页/共97页66 由此知五年最高总产量为23700再由上递推知 第66页/共97页67高负荷生产的完好机器的最优组合简记：这表明在前两年年初全部完好机器投入低负荷生产，后三年年初全部完好机器投入高负荷生产。第五年末的完好机器数为 0.7397278台 在此

34、例中，我们仅考虑最高产量，而未考虑五年计划后的完好机器数。问题1：若计划为n个年度，怎样决策？问题2：若要求在第5年末完好的机器数为500台，如何决策使5年总产量最高？第67页/共97页68这类问题称为固定终端问题由上讨论知：状态转移方程仍为 表示第k年初开始到第5年末的最高产量，称为最优值函数，其递推关系为 k=1,2,3,4,5第68页/共97页69其中 为第k段的效益值，即第k年的产量。表示第6年的产量不计算在总产量之内，故为零。由假设 ，又根据(1)得 一般地，当 确定后，选择 来确定 ，现在 已经给定，故 已经没有选择余地，它由 和 确定。于是第69页/共97页70由(2)可知最优值

35、 第70页/共97页71最优值 类似地得到 这是五年最高产量 这表明，如果限定五年后的完好机器数为500台，则总产量低于无限制的情况，最优策略也相应有所变化，由第一年到第四年全部完好机器投入低负荷生产。第71页/共97页72 为了计算第5年投入高负荷生产的完好机器数 ，先计算 所以 即第5年有452台机器投入高负荷生产，其余投入低负荷生产。第72页/共97页733 存贮模型 工厂为了连续生产必须贮存一些原材料，商店为了连续销售必须贮存一些商品，象这类的实际问题当然要考虑其经济效益。因此就必须考虑一个贮存多少的问题。原料、商品存得太多，贮存费用高，存得太少则无法满足需求。第73页/共97页74第

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

37、这个最低存量之上计算的。模型建立 订货周期T、订货量Q与每天需求量r之间满足 QrT (3-1)订货后贮存量由Q均匀地下降，记任意时刻t的贮存量为q，则q(t)的变化规律可以用图表示：第76页/共97页77 考察一个订货周期的总费用：订货费为 ；贮存费是 因为积分值恰是图中三角形面积A，显然A 。第77页/共97页78由(3-1)式可知一个订货周期T内的总费用为于是平均每天的费用为 所以制定最优贮存策略可归结为：求订货周期T,使C(T)最小。思考：为什么不用 作为目标函数？利用微分法，第78页/共97页79再根据(3-1)式有 (3-5)式是经济理论中著名的经济订货批量公式（简称公式）。(3-

38、5)式表明：订货费越高，需求量r越大，订货批量Q应越大；贮存费越高，则每次订货批量应越小。这些当然符合常识，但公式中平方根关系是凭常识难以得到的。说明：货物本身的价格不影响最优贮存策略。因为若记每吨货物价格为k，则一周期T的总费用 中应添加一项kQ，由于QrT，所以(3-3)中增加一常数项kr对求解结果(3-4),(3-5)无影响。第79页/共97页80 例1.某商店有甲商品出售，每单位甲商品价格500元，其存贮费每年为价格的20，甲商品每次订购费需20元，顾客对甲商品的年需求量为365单位，而且需求率为常数（即顾客每天需求商品1单位），在不缺货的条件下，求最优策略。解：以年为单位，则需求速度

39、：r365 于是订货批量（单位）订货周期 第80页/共97页81即每隔12天订一次货，每次订12个单位为最优策略。若按天为单位：则r1，这与以年为单位结果相同。第81页/共97页82模型二：允许缺货的存贮模型 允许缺货就是企业或商店可以在存贮降到零后，还可以再等一段时间订货。缺货时因失去销售机会而使利润减少，减少的利润可以视为因缺货而付出的费用，称缺货费；于是此模型的第1,2条假设与不允许缺货的存贮模型相同，而第3条该为：每隔T天订货Q吨，允许缺货，每天每吨货物缺货费为 。缺货时贮存量视作负值，q(t)图形如下：第82页/共97页83 货物在t 时售完，有一段时间缺货（这时需求量仍为r），在t

40、T时下一次订货量Q到达。于是 一个订货周期T内的总费用：订货费 贮存费 由图知 缺货费 由图知所以总费用 第83页/共97页84每天平均费用下面问题是当T,Q为何值时，使C(T,Q)最小。利用微分法，求出T,Q的最优值，记为 第84页/共97页85则与不允许缺货的存贮模型相比即：允许缺货时订货周期应增大，而订货批量应减少。当缺货费 越大时,和 越接近T和Q。这个结果是合理的，因为 即缺货造成的损失无限变大，相当于不允许缺货。第85页/共97页86问题 1、某厂每天需要角钢100吨，目前每月订购一次，每次订购的费用为2500元，每天每吨角钢的储存费为0.18元。（1）如果不允许缺货，问是否应改变

41、订货策略，改变后能节省多少费用。（2）如果允许缺货，每天每吨的缺货费为0.4元，试制订订策略。2、饮料厂某种饮料生产能力为5000L/天，需求为2000L/天，每次生产准备费为300元，生产成本为10元/L，而资金为贷款，贷款月息为3%，试制订生产计划。第86页/共97页874 森林救火的数学模型 问题：森林失火了，消防站接到报警后应派多少消防队员前去救火？问题分析 森林损失费通常正比于森林烧毁的面积，而烧毁的面积与失火、灭火（指火被扑灭）的时间有关，灭火的时间又取决于消防队员数目，队员越多，灭火越快。救援费除与消防队员人数有关外，也与消防队员灭火时间的长短有关。记失火时刻为t0，开始救火时刻

42、为 ，将火扑灭的时刻为 。设在时刻t森林烧毁面积为B(t)，第87页/共97页88则造成损失的森林烧毁面积为 ，建模时要对函数B(t)的形式作出合理的简单假设。研究 比B(t)更为直接和方便。是单位时间烧毁的面积，表示火势蔓延的程度。在消防队员到达之前，即 火势越来越大，即 随t的增加而增加；开始救火以后，即 ，如果消防队员救火能力足够强，火势会越来越小，即 应减少，并且当 时 =0。救援费可分为两部分；一部分是灭火器材的消耗及消防队员的薪金等，与队员人数及灭火所用的时间均有关，第88页/共97页89 另一部分是运送队员和器材等一次性支出，只与队员人数有关。模型假设 需要对烧毁森林的损失费，救

43、援费及火势蔓延程度的形式 作出假设：、森林损失费与森林烧毁面积 成正比，比例系数 ，即烧毁单位面积的损失费。、从失火到开始救火这段时间()内，火势蔓延程度 与时间t成正比，比例系数 称为火势蔓延速度。、派出消防队员x名，开始救火以后()火势蔓延速度降为 ，其中 可视为每个队员的平均灭火速度；显然应有 。第89页/共97页90 、每个消防队员单位时间的费用为 ，于是每个队员的救火费用是 ；每个队员的一次性支出是 。第条假设可作如下解释：火势以失火点为中心，以均匀速度向四周呈圆形蔓延，所以蔓延的半径r与时间t成正比，又因为烧毁面积B与 成正比，故B与 成正比，从而 与t成正比。模型构成根据假设条件

44、1,3,4，森林损失费为 救援费为 第90页/共97页91 所以这个模型的目标函数即总费用（把它作为队员人数x的函数）为 为求解 的极值问题，必须确定B(t)的形式及,x间的关系。根据假设条件2,3，火势蔓延程度 在 线性地增加，在 线性地减少，第91页/共97页92烧毁的面积 恰是图中三角形的面积，显然有 而 满足于是 第92页/共97页93将(4-2),(4-3)代入(4-1)，所以救火总费用：于是问题归结为求x使C(x)达到最小。可以得到应派出的队员人数第93页/共97页94结果解释：1).首先，应派出队员数目由两部分组成，其中一部分 是为了把火扑灭所必须的最低限度。因为 是火势蔓延速度

45、，而 是每个队员的平均灭火速度，所以这个结果是明显的。从上图中也可看出，只有当 时，斜率为 的直线才会与t轴有交点 。其次，派出队员数的另一部分，即在最低限度之上的人数与问题的各个参数有关。第94页/共97页95 当队员灭火速度和队员一次性支出增大时，队员数减少；当火势蔓延速度、开始救火时的火势b及损失费用系数增加时，队员数增加。这些结果与常识是一致的。(4-5)式还表明：当救援费用系数变大时，队员数也增加（思考：这个结果是否合理？）。2).实际应用这个模型时，是已知常数，由森林类型、消防队员素质等因素决定 ，可以预先制成表格以备查用，较难掌握的是开始救火时的火势b，它可以由失火到救火的时间 按 算出，或根据现场情况估计。第95页/共97页96评注：建立这个模型的关键是对 的假设。比较合理而又简化的假设条件2,3只能符合无风的情况，在风势的影响应考虑另外的假设。再者，有人对队员灭火的平均速度 是常数的假设提出异议，认为应与开始救火时的火势b有关，b越大越小，这时要对函数作出合理的假设，再得到进一步的结果。思考题：在有风的情况下如何建立数学模型？第96页/共97页97感谢您的观看！第97页/共97页