数学建模教材第5-8章.doc

第五章 最优化方法及图论法建模5.1 可口可乐易拉罐形状问题在我国每年要生产大量的铝制易拉罐，要进口大量的铝，花掉大量的外汇。因此，怎样节省制造易拉罐所用的铝材，对于降低成本来说是十分重要的。而制造一个易拉罐所用的铝材和罐的表面积是成比例的。因此，在体积一定的前提下，设计能够使其表面积最小的罐的形状就是关键了。本教学单元就是讨论与之相关的数学建模问题。在讲述最优化(导数的应用 极值问题)的前一堂课结束前510分钟，先提出问题：可口可乐、雪碧、健力宝等销量极大的饮料罐(易拉罐)顶盖的直径和从顶盖到底部的高之比为多少? 为什么? 它们的形状为什么是这样的? 也可以要求同学在下一堂课前做(或预习)传统的微积分教材中的一道例题，例如“面向二十一世纪课程教材”中由王绵森、马知恩主编的工科数学分析基础(上册)，高等教育出版社，1998，pp. 154-155 的例 6.7 “用铁皮做成一个容积一定的圆柱形的无盖(或有盖)容器，问应当如何设计，才能使用料最省，这时圆柱的直径和高之比为多少? ”(我们略有修改)或者托马斯微积分第10版，高等教育出版社，2003，例2(pp.291-293). 实际上, 用几何语言来表述就是: 体积给定的圆柱体, 其表面积最小的尺寸 (半径和高)为多少? 表面积用 S 表示, 体积用 V 表示, 则有测量还要求同学在下一堂课之前自己找一个可口可乐饮料罐具体测量一下:它顶盖的直径和从顶盖到底部的高: 约为6厘米和12厘米. 中间胖的部分的直径约为6.6厘米，胖的部分高约为10.2厘米. 可口可乐饮料罐上标明净含量为 355 毫升(即 355 立方厘米). 怎样测量比较简捷? (用一条窄的薄纸条, 绕饮料罐相关部分一圈测得周长, 再换算得半径和直径). 下一堂课上课时, 教师带一个用过的可口可乐饮料罐, 给坐在前面的同学测量一下, 告诉同学们有关的数据, 要求同学和教师一起通过数学建模的方法来回答相关的问题. 简化模型分析和假设：首先把饮料罐近似看成一个正圆柱是有一定合理性的. 要求饮料罐内体积一定时, 求能使易拉罐制作所用的材料最省的顶盖的直径和从顶盖到底部的高之比. 实际上，饮料罐的形状是如下平面图形绕其中轴线旋转而成的立体。my = AbsoluteThickness2,Line2.3,0.4,2.3,0,2.7,0,2.7,0.8,3.3,0.8,3.3,11,3,12,3,12.4,2.7,0,-3,12,-3,12.4,-3,12,-3.3,11,-3.3,0.8,-2.7,0.8,-2.7,0,-2.3,0,-2.3,0.4mygrapg = ShowGraphicmy,AxesLabel-x,y,AspectRatio-Automatic, PlotRange-0,12.4用手摸一下顶盖就能感觉到它的硬度要比其他的材料要硬(厚, 因为要使劲拉), 假设除易拉罐的顶盖外, 罐的厚度相同, 记作, 顶盖的厚度为 . 想象一下, 硬度体现在同样材料的厚度上(有人测量过, 顶盖厚度大约是其他部分的材料厚度的 3 倍). 因此, 我们可以进行如下的数学建模. 这时必须考虑所用材料的体积. F=AbsoluteThickness1,Line-3.1,0,3.1,0,3.1,12.4,-3.1,0,-3,0.1,3,0.1,3,12.1,-3,12.1,-3,0.1mygrapg = ShowGraphicF,AxesLabel-x,y,AspectRatio-Automatic, PlotRange-0,12.5 明确变量和参数：设饮料罐的半径为 r（因此，直径为 d = 2r）, 罐的高为 h. 罐内体积为 V. b 为除顶盖外的材料的厚度. 其中 r, h 是自变量, 所用材料的体积 SV 是因变量, 而 b 和 V 是固定参数, 是待定参数. 饮料罐侧面所用材料的体积为饮料罐顶盖所用材料的体积为 饮料罐底部所用材料的体积为 所以, SV 和 V 分别为, 因为 , 所以带 的项可以忽略(极其重要的合理假设或简化). 因此记 . 于是我们可以建立以下的数学模型：其中 S 是目标函数，是约束条件, V 是已知的(即罐内体积一定), 即要在体积一定的条件下, 求罐的体积最小的 r, h 和 使得 r, h 和测量结果吻合. 这是一个求条件极值的问题. 模型的求解：一种解法(从约束中解出一个变量，化条件极值问题为求一元函数的无条件极值问题)从 解出 ,代入 S, 使原问题化为：求 d : h 使 S 最小, 即, 求 r 使最小. 求临界点: 令其导数为零得解得临界点为 , 因此测量数据为 h/r=2, 即 , 即顶盖的厚度是其他材料厚度的 3 倍. 为验证这个 r 确实使 S 达到极小。计算 S 的二阶导数所以, 这个 r 确实使 S 达到局部极小, 因为临界点只有一个, 因此也是全局极小. 如果不忽略高级无穷小量，那么代入 h 的表达式, 得到为与 的解 相比较.我们可以先画图, 再具体地数值计算. 两个函数的图形Plot730/r+4 Pi r2, 730/r+4 Pi r2+8 r+7.3/(r2)+0.0004 Pi,r,2,4它们的导数的图形Plot4 Pi r3-365, 8 Pi r4+0.08 Pi r3-730 r-7.3, r,-10,10, AxesLabel-r,SV 数值计算FindRoot8 Pi r4+0.08 Pi r3-730 r-7.3=0,r,3.07 (r3.07393)3.0739325482285473.0739325482945477-3.073932548228547 差: 3.0739325482945477 - 3.073932548228547求 极小的初等方法是应用算术几何平均值不等式 ，当且仅当时等号成立.(n=2,3 时有明显的几何意义: 周长一定的矩形中正方形的面积最大;三边长的和一定的长方体中立方体的体积最大)令 , 于是有, 当且仅当 时等号成立, 即, 结果相同. 模型另一种解法 Lagrange 乘子法 (增加一个变量化条件极值问题为求多元函数无条件极值问题临界点(驻点)的问题) 在讲多元函数的导数应用时, 也可以用标题: “最优化 导数的应用(极值问题) (续)”，或者“多元极值问题 再论易拉罐问题”。当然, 这个问题在讲一元函数求极值问题时没有办法讲, 但是可以作为以后讲多元函数极值问题的伏笔. 在课堂上可以启发性地讲一点. 在上述解法中, 从解出 h 是关键的一步. 但是常常不容易或不能从约束条件中解出一个变量为另一个变量的函数(或者虽然能解出来, 但很复杂), 无助于问题的求解. 但是，如果表示变量间的隐函数关系, 并假设从中能确定隐函数(尽管没有解析表达式, 或表达式很复杂), 那么, 我们仍然可以写成 , 而且, 由隐函数求导法则, 我们有 因此, 是 S 的临界点的必要条件为假设 是 S 的临界点, 则有于是, 在 处, 因此, 如果我们引入 , 那么, 就有 把问题化为求三元函数 L 的无条件极值的问题.函数 L 称为 Lagrange 函数, 这种方法称为Lagrange 乘子法. 具体到我们这个问题, 有如下的结果. 引入参数 , 令求临界点从第 2，3 式解得 ，代入第 1 式得.和前面的结果相同. 大家可能会觉得这个方法不如前一个方法简单, 但是当你们做习题时你们就会体会到Lagrange 乘子法的优点, 以及进一步体会到使用数学软件的重要性和必要性. 验证和进一步的分析：有人测量过顶盖的厚度确实为其他材料厚度的 3 倍. 如果易拉罐的半径为3厘米, 则其体积为 , 即装不下那么多饮料，为什么？模型到底对不对? 按照, V = 365立方厘米, 可以算得r = 3.074 厘米. 要给学生留下尽可能大的想象空间, 鼓励学生讨论、争论, 建立自己的数学模型, 等等. 下面只是一种可能的考虑. 粗略的计算, 可以把饮料罐的体积看成两部分,一是上底半径为 3 厘米，下底半径为 3.3 厘米, 高为 1 厘米的锥台, 二是半径为 3.3 厘米, 高为 10.2 厘米的圆柱体. 它们的体积分别为 31.2 立方厘米和 349 立方厘米总共为 380.2 立方厘米. 然后, 我们再来通过测量重量或容积(怎么测量?)来验证. 我们可以认为 1 立方厘米的水和饮料的重量都是 1 克. 测量结果为: 未打开罐时饮料罐的重量为 370 克, 倒出来的可乐确实重 355 克, 空的饮料罐重量为 15 克, 装满水的饮料罐重量为 380 克. 这和我们的近似计算 380.2 立方厘米十分接近！饮料罐不能装满饮料, 而是留有 10 立方厘米的空间余量. 有意思的是, 计算饮料罐的胖的部分的直径和高的比为 6.6/10.2 = 0.647, 非常接近黄金分割比 0.618. 这是巧合吗? 还是这样的比例看起来最舒服, 最美? 此外, 诸如底部的形状, 上拱的底面, 顶盖实际上也不是平面的, 略有上拱, 顶盖实际上是半径为 3 + 0.4 + 0.2 = 3.6 平方厘米的材料冲压而成的, 从顶盖到胖的部分的斜率为 0.3, 这些要求也许保证了和饮料罐的薄的部分的焊接(粘合)很牢固、耐压. 所有这些都是物理、力学、工程或材料方面的要求, 必须要有有关方面的实际工作者或专家来确定. 因此, 我们可以体会到真正用数学建模的方法来进行设计是很复杂的过程, 只依靠数学知识是不够的, 必须和实际工作者的经验紧密结合. 还可以从其他角度来考虑各种各样罐的数学建模.可以参看有关的阅读材料.建议学生到市场(超市等)调查各种罐、杯的尺寸，回答它们的设计是否都用到了优化设计？实际上, 这类问题是数学中著名的等周问题的推广或扩充的一些特例. 学生可以阅读本教学单元所附的等周问题阅读材料, 或其他参考资料. 习题(任课教师可以自行配置习题)1. 如果正圆柱形饮料罐, 上底的厚度为其它部分厚度的 3 倍, 饮料罐的总面积固定, 求能够使其体积最大的饮料罐的尺寸(直径和高之比). 2. 试证明, 在周长相等的矩形中, 正方形的面积最大. 试证明, 表面积相等的长方体中, 正方体的体积最大. (到市场上去考察各种箱包、容器的尺寸, 并给予一定的解释.) 3, 假设饮料罐的剖面图如下图所示上半部分是一个圆锥台, 下半部分是一个圆柱体. 如果顶盖的厚度为其他部分厚度的倍. 求罐内体积固定时, 所用材料最省的罐的尺寸. 4在正圆柱形饮料罐的最优设计中, 你有没有发现什么规律性的事实？5正椭圆柱形状的饮料罐的设计. 求长轴为短轴K倍的正椭圆柱体积一定时能使其表面积最小的短轴和高的比. (提示: 长轴为 a，短轴为 b (a b0)的椭圆的面积为，它的周长为 .虽然它不能用初等函数表示, 但是当给出 a 和 b 的具体数值时, 可以用数学软件来计算它的值. 若令 称为第二类不完全椭圆积分, 或Legendre第二类椭圆积分, 是一类重要的特殊函数. 椭圆函数是椭圆积分的反函数.) 4. 太空船(航天飞机, Space Shuttle)里的水箱的外形是由半径为 r 的球放在一个正圆锥上形成的, 形如我们通常吃的冰淇淋的样子. (其中心纵断面的图形见下图).圆锥体的底部直径等于球体的半径(见上图). 如果球体的半径限定为正好为6英尺, 设计的水箱表面积为460平方英尺, 请确定球拱高和圆锥体高的尺寸, 使得水箱容积最大. 试着从约束中解出一个变量, 化条件极值问题为求一元函数的无条件极值问题, 手算容易吗？再用数学软件试试, 体会数学软件的优势. 什么情况下数学软件是可以信任的, 什么情况下会出问题.阅读材料 一、有关饮料罐的形状和制造A. 有关饮料罐的制造过程。在网上可以查到有关制作饮料罐的工序，这里我们采用西安交通大学周义仓教授在教授“数学建模”课程时，应数31班王小宝同学提供的资料。CCB-1A型罐罐体的主要制造工艺流程如下：卷料输送卷料润滑落料、拉伸罐体成形修边清洗/烘干堆垛卸涂底色烘干彩印底涂烘干内喷涂内烘干罐口润滑缩颈旋压缩颈。在工艺流程中，落料、拉伸、罐体成形、修边、缩径、旋压缩径翻边工序需要模具加工，其中以落料、拉伸和罐体成形工序与模具最为关键，其工艺水平及模具设计制造水平的高低，直接影响易拉罐的质量和生产成本。如图所示：B. 比较早的教材中谈及罐的形状的是：Consordium for Mathematics and its Applications(COMAP), Principles and Practice of Mathematics, Springer-Verlag New York Inc., 1997, p. 21. (中译本，数学的原理与实践，申大维、叶其孝 等译，北京，高等教育出版社；德国：施普林格出版社，1998，p.15)所谈及的，即背景聚焦 “精明的罐装”：每年都有几百万吨铝，用于制造饮料容器。为减少这种金属的消耗，了解什么是能装下 12盎司液体的容器的理想形状是十分有用的。初一看，你可能会认为制造不同形状的容器所用的金属相差无几。但是如果你做一个很窄细的容器去盛 12 盎司的饮料，那么容器必须非常高，而且所用的总的金属量将大于你曾用过的平常的容器所需的金属量。如果容器是圆柱形的，你若选定半径 (r)，那么为盛下 12 盎司的饮料，高度 (h) 也就确定了，从而也确定了所需金属的总量。下面的公式给出了制作这样一个饮料罐头的高度以及所需的用铝总量 (r 和 h 的单位都是英寸)：，其中 0.02 表示罐头侧边和底部的厚度。(你可以根据圆柱体表面积的公式自己导出这个公式，但你需要知道顶盖的厚度是底部厚度的3倍。这个加厚的厚度是为了当你砰的一下打开罐头时防止把整个顶盖撕下来。)利用这个关于 a 的公式，你可以用本书的方法确定使金属用量最少的 r。你将发现你得到的 r 和 h 的值非常接近实际的饮料罐头的这些值。为找到罐头的最佳形状，饮料公司已经做过这样的数学计算了。C. 有关罐的形状的最优设计也可以从其他角度来研究。例如，在很多国家使用很多的一本优秀的微积分教材，James Stewart 著，Calculus (Fifth Edition): Early Transcendentals, 2003, Brooks/Cole, pp. 341-342 (“ 4.7 优化问题”的应用课题 (Applied Project)就是这样的研究。它也可以作为学生课外活动的素材。译文如下(读者也可以参阅 James Stewart,微积分(上册) , 白峰杉 主译, 高等教育出版社, 2004年7月第1版, pp. 353-354. )：应用课题 罐的形状在本课题中我们将研究罐的最经济的形状。首先来说明要研究的问题是什么，那就是假设圆柱形罐的体积 V 给定，要求其高 h 和半径 r 使得制作罐的金属材料的成本最低(图略)。如果我们不考虑在制作过程中产生的任何边角料，那么问题就变成要使圆柱体的表面积最小。我们在 4.7 的例2中已经解决了这个问题，并求得 h = 2r，即高和直径应该相等。但是如果你带一把尺子去你的碗橱或超市看看(量一下)，你就会发现罐的高通常都大于其直径，而比 h/r 在 2 到 3.8 之间变化。我们来看看能否解释这种现象。1 制罐的材料是从金属片上切割下来的。圆柱体的侧面是由矩形弯曲而成；这些矩形从金属片切割下来时边角料很少或者根本没有边角料。但是，如果顶盖和底盖是从边长为 2r的正方形切割而得(图略)，那么就会留下很可观的边角料了。也许可以回收这些边角料，但这对于罐的制造商而言却没有多大价值或没有价值。如果是这样的话，证明当 时所用的金属材料最少。2更为有效的切割圆片的方法是把金属片划分成正六边形，并从正六边形切割圆形顶盖和底盖(图略)。证明如果采用这种方法，则有. 3. 在问题 1 和 2 中求得的 h/r 的值和超市货架上罐的值比较接近，但仍然没有考虑到所有的事情。如果我们更加仔细地看看某些实际的罐头，就会发现顶盖和底盖是用半径大于 r 的圆片把其边缘弯过来盖在罐的侧边上制成罐的。如果是这种情况，那么 h/r 将会变大。更重要的是，除了金属材料的成本外，还要加上罐的制作成本。假设大多数制作费用用于连接罐的各边缘。如果按问题 2 的方案从正六边形切割圆片，则总成本与 成比例，其中是按单位面积金属材料的成本计算的可以连接的长度的倒数。证明当 时该表达式取到最小值。4画 作为 的函数的图形，并利用这个图形证明当罐的体积大或者连接成本低时，应该使 h/r 大致等于(问题2所述的)2.21。但是当罐的体积小或者连接成本高时，h/r 应该比较大。5我们的分析表明大罐的中心断面差不多应该是正方形的，即 h = 2r，而小罐则应该高而细。去超市看看有关的罐的形状。我们的结论在实践中通常是正确的吗？有例外吗？你能说明为什么小罐并不总是高而细的理由吗？D. 在国外的工程类图书(教材)中也有涉及饮料罐的设计的，考虑的方面也更多些，而且是学工程的学生考试的内容，值得我们了解。以下是由John Halliwell、Barry Lambert、Dave Webster和Jon Attwood所著的 Revise for Product Design: Graphics with Materials Technology，Heinemann Educational Publishers, 2004, p. 85 的中译文。分析旨在降低制造成本的任何修改设计的建议。这些修改可以包括： 使用较少的元件的更简单的设计 更换材料以使产品更轻或更有成本效益 选择能减少浪费的材料和生产过程 选择需要较少能源的材料和生产过程 改变元件的形状使之更适合于制模 改变机械加工的过程以减少浪费或节省时间案例研究：可口可乐罐头由于PET瓶(译注：PET即Polyethylene terephthalate，聚脂饮料瓶，常常包上一层铝以降低它的渗透性，并使之不透光)的日益普及，可口可乐公司决定重新考察206铝罐的设计，新罐必须满足以下条件： 符合制造过程的要求 符合灌装的要求 强度和206铝罐一样 保持销售和陈列所要求的可叠起堆放 符合售货机的要求 确保标准以使所有欧洲的制造商都会采用图 3.26 新的Coca-Cola是“轻量化”的一个很好的例子一种产品的微小的改变有可能导致巨大的节省。缩小罐盖的直径的202铝罐，每只罐只降低了0.1便士的成本。但是，考虑到可口可乐公司每年要出售20亿只铝罐，很容易算出所节省的钱十分巨大。新的更轻质铝罐的设计，由于降低了运输成本和所需要的原材料，甚至简化了生产过程，从而产生了额外的效益。该公司非常小心地确保新的规定将为欧洲所有的制造商接受。美感、质量和物有所值设计总是要涉及功能、外观(美感)、材料和成本之间的妥协。质量和成本随不同的产品而变化，但是必须满足顾客在美感和功能方面的期望，只有这样顾客才会感到物有所值。5.2 人力资源安排的最优化模型摘要:某大学数学系人力资源安排问题是一个整数规划的最优化问题，通过具体分析数学系现有的技术力量和各方面的约束条件，在问题一的求解中，可以列出一天最大直接收益的整数规划，求得最大的直接收益是42860元；而在问题二的求解中，由于教授一个星期只能工作四天，副教授一个星期只能工作五天，在这样的约束条件下，列出一个星期里最大直接收益的整数规划模型，求得其最大直接收益是198720元。关键词：技术力量；整数规划；直接收益621. 问题的提出数学系的教师资源有限，现有四个项目来源于四个不同的客户，工作的难易程度不一，各项目对有关技术人员的报酬不同。所以：1. 在满足工作要求的情况下，如何分配数学系现有的技术力量，使得其一天的直接收益最大？2. 在教授与副教授工作时间受到约束的条件下，如何分配数学系现有的技术力量，使得其在一个星期里的直接收益最大？2.模型的假设1. 不同技术力量的人每天被安排工作的几率是相等的，且相同职称的个人去什么地方工作是随机的；2. 客户除了支付规定的工资额外，在工作期间里，还要支付所有相关的花费（如餐费，车费等）；3. 当天工作当天完成3.符号的约定取1，2，3，4，分别表示教授、副教授、讲师、助教取1，2，3，4，分别表示地取1到7，分别表示一个星期里的七天种职称的人员在地第天工作的人数职称的人在地工作平均每天的报酬表示每天在地所需的最多工作人数数学系有职称的人数数学系职称的人每天的工资额地所需职称技术人员人数的最小值地所需职称技术人员人数的最大值.问题的分析由题意可知各项目对不同职称人员人数都有不同的限制和要求对客户来说质量保证是关键，而教授相对稀缺，因此各项目对教授的配备有不能少于一定数目的限制其中由于项目技术要求较高，助教不能参加而两项目主要工作是在办公室完成，所以每人每天有50元的管理费开支由以上分析可得：最大直接收益=总收益技术人员工资、两地保管费5.模型的建立与求解5.1.1模型一的建立用表示数学系一天最大的直接收益。当时，表示一天职称的人员地工作的人数。考虑各方面的条件，列出如下的整数规划模型：约束条件：(1)数学系现有技术人员总人数的约束： 5.1.2模型二的建立用表示一个星期的最大直接收益。由于每个星期里，教授只能工作4天副教授只能工作5天，把每个技术人员工作一天看作是一次，那么在一个星期里教授有48人次可以被安排工作，副教授有125人次可以被安排工作，而讲师与助教分别有119和70人次可以被安排工作，总人次为362。根据以上分析可以列出如下整数规划模型：约束条件：5.2模型的求解相关数据表格如下：数学系的职称结构及工资情况教授副教授讲师助教人 数工资/日（元）12250252001717010110不同项目和各种人员的报酬标准教授副教授讲师助教收费（元/天）ABCD1000150013001000800800900800600700700700500600400500各项目对专业技术人员结构的要求ABCD教授副教授讲师助教总计1322117252232022211512281-185.2.1模型一的求解：由模型一求得的最优解是：相应分配在各地的人员是，如下表1：地点 职 称ABCD教授2522副教授12238讲师21041助教1360表1数学系一天直接收益的最大值是：5.2.2模型二的求解：根据模型二可以求出最优解是：（由于向量太多在此省略）在一个星期里其中任六天分别安排在各地的人力资源是：（如下表2，3）地点职称ABCD教授1321副教授42102讲师2726助教1810表2 其中剩下一天分别安排在各地的人力资源是：地点职称ABCD教授1221副教授32102讲师2825助教1810表3数学系在一个星期里最大的直接收益是：6.模型的评价与改进本模型通过合理的假设，充分考虑各方面的限制条件，得出的人员安排和直接收益都是本模型的最优解与最优值，对武汉大学数学系的人力资源安排有一定的指导作用。但从模型假设中，我们可以知道对数学系现有的技术力量的安排是随机的，在相同工作时段里，可能会出现部分人工作次数较多，而部分人较少的不公平情况。所以在满足工作需求的情况下，分配工作时应该要人为地尽量使得每个人的工作次数不要相差太远，或者相等。7.模型的应用与推广此模型通过对人力资源的调配，从量化的角度得出数学系的最大直接收益。利用此模型的方法可以求出所有类似本模型的线性规划模型。但是，本模型只是单目标的规划，可以在此基础上，增加目标要求。如在数学系的直接收益尽可能大的基础上，使得客户所花费的资金最少，等等。从而建立多目标规划模型。解决更为复杂的实际问题。8.参考文献：1 王沫然,业出版社.2001年2 李强 基础应用教程中国水利水电出版社.2004年3 姜启源,数学模型（第三版），北京：高等教育出版社，2003年9.附录f=-1000;-800;-550;-450;-1500;-800;-650;-550;-1300;-900;-650;-350;-1000;-800;-650;-450;A=zeros(9,16);for i=1:1 for j=1:16 A(i,j)=1; endendfor i=2:5 for j=i-1:4:11+i A(i,j)=1; endendi0=0;for i=6:9 for j=i0+1:(i-5 )*4 A(i,j)=1; end i0=j;endb=64;17;20;15;18;12;25;17;10;Aeq=zeros(1,16);Aeq(1,3)=1;beq=2;LB=1;2;2;1;2;2;2;2;2;2;2;1;1;3;1;0;UB=3;5;2;2;inf;inf;inf;8;inf;inf;inf;inf;inf;inf;inf;0;x,fval=linprog(f,A,b,Aeq,beq,LB,UB)f=-1000;-1000;-1000;-1000;-1000;-1000;-1000;-1500;-1500;-1500;-1500;-1500;-1500;-1500;-1250;-1250;-1250;-1250;-1250;-1250;-1250;-950;-950;-950;-950;-950;-950;-950;-800;-800;-800;-800;-800;-800;-800;-800;-800;-800;-800;-800;-800;-800;-850;-850;-850;-850;-850;-850;-850;-750;-750;-750;-750;-750;-750;-750;-600;-600;-600;-600;-600;-600;-600;-700;-700;-700;-700;-700;-700;-700;-650;-650;-650;-650;-650;-650;-650;-650;-650;-650;-650;-650;-650;-650;-500;-500;-500;-500;-500;-500;-500;-600;-600;-600;-600;-600;-600;-600;-350;-350;-350;-350;-350;-350;-350;-450;-450;-450;-450;-450;-450;-450;A=zeros(60,112);for i=1;1 for j=1:112 A(i,j)=1; end endi0=0;for i=2:4 for j=i0+1:(i-1)*28 A(i,j)=1; end i0=j;endfor i=5:32 for j=(i-4):28:80+i A(i,j)=1; endendfor i=33:39 for j= i-32:7:(i-11) A(i,j)=1; endendj0=j;for i=40:46 for j=j0+(i-39):7:(i-18)+j0 A(i,j)=1; endendj0=j;for i=47:53 for j=j0+(i-46):7:j0+(i-25) A(i,j)=1; endendj0=j;for i=54:60 for j=j0+(i-53):7:j0+(i-32) A(i,j)=1; endendb=362;48;125;119;17;17;17;17;17;17;17;20;20;20;20;20;20;20;15;15;15;15;15;15;15;18;18;18;18;18;18;18;12;12;12;12;12;12;12;25;25;25;25;25;25;25;17;17;17;17;17;17;17;10;10;10;10;10;10;10;UB=3;3;3;3;3;3;3;5;5;5;5;5;5;5;3;3;3;3;3;3;3;2;2;2;2;2;2;2;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;8;8;8;8;8;8;8;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;+inf;0;0;0;0;0;0;0;LB=1;1;1;1;1;1;1;2;2;2;2;2;2;2;1;1;1;1;1;1;1;1;1;1;1;1;1;1;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;1;1;1;1;1;1;1;1;1;1;1;1;1;1;3;3;3;3;3;3;3;1;1;1;1;1;1;1;0;0;0;0;0;0;0;Aeq=zeros(7,112);for i=1:7 Aeq(i,i+14)=1;endbeq=2;2;2;2;2;2;2;x,fval=linprog(f,A,b,Aeq,beq,LB,UB)5.3.服务点的选址问题（图论模型）（缺图） 某县拟建一个消防站，为该县辖区内七个城镇服务，问需设计在哪个城镇上，才能使它至最远城镇的路程达到最小？ 该问题抽象成图，如图8.4.6所示。 类似本例中的消防站设置问题有：医院、商店、电影院、仓库等的设置，总之可称为“服务店选址问题”。这类问题的一般提法是： 对一个连通赋权图G=(V,E,L)现取其中一点，然后考虑此点与G中其它各点间最短路的长：，我们称这几个距离中最大数为顶点的最大服务距离，记为，即有。我们现在的问题就是要求出：中最小者的值及其所对应的点。设就是所求的点，即有，我们称为图G的中心点。 求中心点的算法步骤如下：1） 用Floyd算法求出图G的距离表，2） 对每个点，求出数3） 求出中心点。对本例计算结果如下表。0356.39.34.569.33023.36.31.536.3520252.5456.33.32031.83.36.39.36.35304.86.39.34.51.52.51.84.801.54.86343.36.31.506.5由该表可知为所求的中心点=min =4.8 即消防站应设在. 第六章 数学规划模型 6.1 线性规划在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济效益的问题。此类问题构成了运筹学的一个重要分支数学规划，而线性规划(Linear Programming 简记LP)则是数学规划的一个重要分支。自从1947年G. B. Dantzig 提出求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在实用中日益广泛与深入。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了，已成为现代管理中经常采用的基本方法之一。1.1 线性规划的实例与定义例1 某机床厂生产甲、乙两种机床，每台销售后的利润分别为4000元与3000元。生产甲机床需用机器加工，加工时间分别为每台2小时和1小时；生产乙机床需用三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为机器10小时、机器8小时和机器7小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？上述问题的数学模型：设该厂生产台甲机床和乙机床时总利润最大，则应满足（目标函数） (1)s.t.（约束条件） （2）这里变量称之为决策变量，（1）式被称为问题的目标函数，（2）中的几个不等式是问题的约束条件，记为s.t.(即subject to)。上述即为一规划问题数学模型的三个要素。由于上面的目标函数及约束条件均为线性函数，故被称为线性规划问题。一、问题提出 市场上有n种资产（i=1,2n）可以选择，现用数额为M的相当大的资金作一个时期的投资。这n种资产在这一时期内购买的平均收益率为 ，风险损失率为 ，投资越分散，总的风险越小，总体风险可用投资的中最大的一个风险来度量。 购买时要付交易费，(费率)，当购买额不超过给定值时，交易费按购买计算。另外，假定同期银行存款利率是，既无交易费又无风险。（=5%）已知n=4时相关数据如下：（%）（%）（%）（元）S1282.51103S2211.52198S3235.54.552S4252.66.540试给该公司设计一种投资组合方案，即用给定达到资金M，有选择地购买若干种资产或存银行生息，使净收益尽可能大，使总体风险尽可能小。基本假设：1. 投资数额M相当大,为了便于计算，假设M=1；2投资越分散，总的风险越小；3总体风险用投资项目中最大的一个风险来度量；4n种资产S之间是相互独立的；5在投资的这一时期内, ri,pi,qi，r0为定值，不受意外因素影响；6净收益和总体风险只受 ri,pi,qi影响，不受其他因素干扰。符号规定：Si 第i种投资项目，如股票，债券ri,pi,qi -分别为Si的平均收益率, 交易费率，风险损失率 ui -Si的交易定额 -同期银行利率xi -投资项目Si的资金 a -投资风险度Q -总体收益 Q -总体收益的增量2购买Si所付交易费是一个分段函数,即 pixi xiui 交易费 = piui xiui而题目所给定的定值ui(单位:元)相对总投资M很小, piui更小,可以忽略不计,这样购买Si的净收益为(ri-pi)xi3要使净收益尽可能大，总体风险尽可能小,这是一个多目标规划模型: 目标函数 MAX MINmax qixi 约束条件 =M xi0 i=0,1,na 在实际投资中，投资者承受风险的程度不一样，若给定风险一个界限a，使最大的一个风险qixi/Ma，可找到相应的投资方案。这样把多目标规划变成一个目标的线性规划。模型1 固定风险水平，优化收益 目标函数： Q=MAX 约束条件： a ， xi 0 i=0，1，n b若投资者希望总盈利至少达到水平k以上，在风险最小的情况下寻找相应的投资组合。模型2 固定盈利水平，极小化风险 目标函数： R= minmax qixi 约束条件：k， ， xi 0 i=0，1，n c投资者在权衡资产风险和预期收益两方面时，希望选择一个令自己满意的投资组合。因此对风险、收益赋予权重s（0s1)，s称为投资偏好系数.模型3 目标函数：min smaxqixi -（1-s） 约束条件 =M， xi0 i=0,1,2,nc投资者在权衡资产风险和预期收益两方面时，希望选择一个令自己满意的投资组合。因此对风险、收益赋予权重s（0s1)，s称为投资偏好系数.模型3 目标函数：min smaxqixi -（1-s） 约束条件 =M， xi0 i=0,1,2,n由于a是任意给定的风险度，到底怎样给定没有一个准则，不同的投资者有不同的风险度。我们从a=0开始，以步长a=0.001进行循环搜索，编制程序如下：a=0;while(1.1-a)1 c=-0.05 -0.27 -0.19 -0.185 -0.185; Aeq=1 1.01 1.02 1.045 1.065; beq=1; A=0 0.025 0 0 0;0 0 0.015 0 0;0 0 0 0.055 0;0 0 0 0 0.026; b=a;a;a;a; vlb=0,0,0,0,0;vub=; x,val=linprog(c,A,b,Aeq,beq,vlb,vub); a x=x Q=-val plot(a,Q,.)，axis(0 0.1 0 0.5)，hold on a=a+0.001;end xlabel(a),ylabel(Q)a = 0.0030 x = 0.4949 0.1200 0.2000 0.0545 0.1154 Q = 0.1266a = 0.0060 x = 0 0.2400 0.4000 0.1091 0.2212 Q = 0.2019a = 0.0080 x = 0.0000 0.3200 0.5333 0.1271 0.0000 Q = 0.2112a = 0.0100 x = 0 0.4000 0.5843 0 0 Q =0.2190a = 0.02