数学建模示例2优化.doc

数学建模示例------郭洪奇16 第四章第四章 优化、规划模型优化、规划模型 在实际生活中，特别是在工程技术、经济管理和科学研究领域中 存在着很多优化模型，如投资的成本最小、利润最大问题，路线最短 问题，货物的运输调度问题，风险证券投资中的收益最大，风险最小 问题 优化模型大致的可以分成两大类：无约束优化模型和约束优化模 型无约束优化模型即求一个函数在定义域内的最大值或最小值，这 类问题往往可以使用微分的方法得到最终的结论，如一元及多元函数 的最值归结为求函数的驻点；约束优化模型即求函数在一些条件约束 下的最优解，对于等式约束的问题，可以使用了数学软件等求解 在建模过程中需要解决的问题的基本步骤为： （1） 确定目标 函数（按照模型所需要解决的问题，用数学函数来描述目标） （2） 确定决策变量（目标的实现与那些变量有关，这里有主要变量和次要 变量，在建模的初期可以进考虑主要变量对目标的影响，随后可以逐 步增加变量的个数） （3） 确定约束条件（这是优化模型建模过程 中最重要，也是最难的，在很多情况下，是否能够得到最优解，最优 解是否合理，都是取决于约束条件的建立） （4） 模型求解（使用 数学工具或数学软件求解） （5） 结果分析（分析结果的合理性、 稳定性、敏感程度等） 例例1：森林救火模型。

森林救火模型森林失火后，要确定派出消防队员的数量队员多，森林损失小， 救援费用大；队员少，森林损失大，救援费用小综合考虑损失费和 救援费，确定队员数量 问题分析：总的目标是确定队员数量使得损失费与救援费的总和 最小决策变量应当是消防队员的数量1）损失费：损失费由大 火熄灭时，被烧毁的森林面积B决定，若假设单位面积损失为c1，则 损失费为c1B将起火的时间定为0，开始灭火的时间设为t1，灭火结 束的时间为t2，因此烧毁的森林面积为B（t2）在[0，t1]中，由于没 有人员参与灭火，火势蔓延的速度可以认为与时间成正比，而蔓延的 速度直接影响到被烧毁的森林圆的半径，从而在[0，t1]内，B（t）与 时间的平方成正比在[t1，t2]区间内，由于灭火的影响，火势的蔓 延速度减慢，与参与的队员人数即每个队员的灭火能力成反比，结果 在时刻t2，蔓延速度将为0，即火被扑灭2）救援费：影响救援费 的因素有两个，救援队员的人数与救援的时间，而这两个因素之间也 是相关的，人数多则救援时间短，反之，人数少则救援时间长因此 在考虑救援费时，必须考虑单位时间内每个队员的费用例例2：最优价格模型最优价格模型数学建模示例------郭洪奇17例例3：存贮货物模型。

存贮货物模型数学建模示例------郭洪奇18例例4：血管分支模型血管分支模型数学建模示例------郭洪奇19例例5：冰山运送模型冰山运送模型数学建模示例------郭洪奇20例例6：空气污染管理问题空气污染管理问题诺利公司为当地的主要钢铁厂家之一，公司为钢城的繁荣与发展作出了一定的贡献但现在情况有所改变，由于钢厂对熔炉的排放物未进行管理，致使空气污染破坏了钢城的环境，并危害了当地居民的健康公司董事会就此作出了明智的决定，指定专门人员与市政官员和人民团体商讨解决空气污染问题，以保证工厂的排放物能达到环保部门的要求研究发现，造成空气污染的物质主要有三种：微粒、氧化硫及碳化氢，钢厂每年须减少的污染物排放量达到表1的要求时，方满足环保的要求 表1 （环保部门的空气清洁标准）污染物每年须减少的污染物排放量（百万磅） 微粒60 氧化硫150 碳化氢125污染物的主要来源为：（1）制造生铁之鼓风炉；（2）炼钢之敞炉减少污染物排放的有效方法为：（1）增加烟囱高度；（2）在烟囱内安装过滤器；（3）使用优质燃料这些方法对减少污染虽有帮助（其效果见表 2） ，但任一方法的单独使用，均不能达到环保部门的要求，若三种方法同时以最高的标准实施，则工厂的产品成本将陡增，从而使产品失去市场竞争力甚至因此而破产，管理部门因此而忧心忡忡。

表 2（各减污法每年最高可能减少的污染排放量（百万磅） ）增高烟囱安装过滤器使用优质燃料污染物鼓风炉敞炉鼓风炉敞炉鼓风炉敞炉 微 粒12925201713 氧化硫354218315649 碳化氢375328242920专题组人员经分析知各减污方法中最高减污量之总成本的近似值如表 3 所示而公司每年可拨出的治污专款也有一底限，试确定该公司是否能实施“空气污染管理”工程表 3（最高减污法之总成本：以百万元为单位）减 污 法鼓风炉敞 炉 增高烟囱810 过 滤 器76 优质燃料1192）假设与模型的建立工程实施的关键在于既要确保排污效果能达到环保部门的要求，又要最大限度地降低成本（不超过其所能承受的底限） 由于问题的解决具有组合性，故可考虑用线性规划模型求解，假设决策变量)6 ,, 2 , 1(Ljxj分别表示各减污法中最高成本的比例值（见下表）减污方法鼓风炉敞炉 增高烟囱1x2x过滤器3x4x优质燃料5x6x则其目标函数为：65432191167108minxxxxxxz约束条件为：125202924285337,6)1,2,j1,(0 1504956311842356013172025912654321654321654321xxxxxxxxxxxxxxxxxxxjL求解：数学建模示例------郭洪奇21得：) 1 ,048. 0, 1 ,343. 0,623. 0 , 1 (),,,,,(654321xxxxxx工程造价为：)(159.329111048. 0617343. 010623. 081百万元L若问题的最优解 3215.9 万元未超过公司所能承受的底限，则该治污工程可上马，否则得另谋它法。

例例 7：连续投资问题连续投资问题某部门在今后五年内考虑给下列项目投资，已知如下条件：项目 A，从第一年到第四年每年年初均需投资，并于次年末回收本利 115%；项目 B，第三年初需要投资，到第五年末回收本利125%，但规定最大投资额不超过 4 万元；项目 C，第二年初需要投资，到第五年末回收本利140%，但规定最大投资额不超过 3 万元；项目 D，五年内每年初可购买公债，于当年末归还，可获利息 6%该部门现有资金 10 万元，问应如何确定给这些项目每年的投资额，使到第五年末部门所拥有的资金的本利总额最大假设与分析：这是一个连续投资问题，能否定义好决策变量，并使之满足线性关系，是能否用线性规划方法求最优解的关键我们用)5 , 4 , 3 , 2 , 1(, , ,jxxxxjDjCjBjA表示第j年初分别用于项目 A，B，C，D 的投资额（即决策变量） ，根据题设条件，可列出下表（表中空格部分表示该项目当年的投资为 0）：年份项目12345 AAx1Ax2Ax3Ax4 BBx3 CCx2 DDx1Dx2Dx3Dx4Dx5下面讨论这些决策变量应满足)5 , 4 , 3 , 2 , 1(,,,jxxxxjDjCjBjA的线性约束条件。

从表 4.9 知：第一年年初仅对项目 A、D 进行投资，因年初拥有资金 10 万元，设项目 A、D 的投资额分别为Ax1、Dx1，则有：10000011DAxx同理，第二年对项目 A、C、D 的投资额应满足方程：DDCAxxxx122206. 1而第三年、第四年、第五年对项目 A、B、D；项目 A、D；项目 D 的投资额应分别满足如下的方程：DADBAxxxxx2233306. 115. 1DADAxxxx324406. 115. 1DADxxx43506. 115. 1另外，项目 B、C 的投资额度应受如下条件的约束：300004000023 CB xx由于“连续投资问题”要求第五年末部门所拥有的资金的本利总额最大，故其目标函树为：DBCAxxxxzMax532406. 125. 140. 115. 1 模型的建立与求解：有了如上的分析，我们可给出该“连续投资问题”的线性规划模型为：DBCAxxxxzMax532406. 125. 140. 115. 1 40000300000 0611510 06115100611510 06110000 32543443233321222111BCDDADADADBADADCADDAxxxx.x.xxx.x.xxxx.x.xxxx.xx求解得：第一年：65217 ,3478311DAxx第二年：元元元0 ,30000 , 39130222DCAxxx第三年：元元元0 ,40000 , 0333DBAxxx第四年：元元0 , 4500044DAxx第五年：元05Dx由此求出第五年末该部门所拥有的资金的本利总额为：143750 元，即部门赢利 43.75% 。

例例8 8：：工程上马的决策问题，某部门三年内有四项工程可以考虑上马，每项工程的期望收益和年度费用（千元）如下表所示：假定每一项已选定的工程要在三年内完成，是确定应该上马哪些工程，方能使该部门可能的期望收益最大费 用工 程第 1 年第 2 年第 3 年期望收益1518 24710 3392 4861020 40 20 30 可用资金182224模型分析与变量的假设：这是工程上马的决策问题，对任一给定的工程而言，它只有两种可能，要么上马，要么不上马，这两种情况分别对应二进制数中的 1、0，大凡这样的实际背景所对应的工程问题，大都可考虑用 0—1 型整数规划模型建立其相应的模型设 ) , 4 , 3 , 2 , 1( , 1, 0 jjjxj项工程不上马第项工程可上马第因每一年的投资不超过所能提供的可用资金数 25 千元，故该 0—1 型整数规划问题的约束条件为：  4 , 3 , 2 , 1 , 1|02410210822697188345432143214321jxxxxxxxxxxxxxi要收益尽量大，目标函数为：432130204020ax xxxxzm模型的建立与求解：至此，我们得到该问题的 0—1 型整数规划模型为：432130204020ax xxxxzm约束条件为：  4 , 3 , 2 , 1 , 1|0(3) 24102108(2) 22697(1) 188345432143214321jxxxxxxxxxxxxxi下面用隐枚举法求其最优解。

易知，该 0—1 型整数规划模型有一可行解（0，0，0，1） ，它对应的目标函数值为： 30z该模型的最优解所对应的目标函数值应不小于 30，增加一过滤条件为：30302040204321xxxx（4）数学建模示例------郭洪奇22在此过滤条件（过滤条件可不唯一）下，用隐枚举法求0—1 型整数规划模型的最优解的步骤为：（1）先判断第一枚举点所对应的目标函数值是否满足过滤条件，若不满足，则转下一步；若满足，再判断该枚举点是否满足各约束条件，若有一个约束条件不满足，则转下一步，若均满足，则将该枚举点所对应的目标函数值 z1（本例中，z130）作为新的目标值，并修改过滤条件为：1432130204020zxxxx，再转下一步； (2) 再判断第二枚举点所对应的目标函数值是否满足新的过滤条件，若不满。