最优化(线性整数)教程方案.ppt

优化模型与数学建模 第一讲 规划理论及模型 一、引言 最优化概论 当今，“优化”无疑是一个热门词。做宏观经济规划要优化资源配置，搞企业经营管理要优化生产计划，作新产品设计要优化性能成本比。就是在人们的日常生活中，优化的要求也比比皆是，消费时，如何花尽可能少的钱办尽可能多的事，出行时，如何走最短的路程到达目的地，等等。总而言之，在经济如此发展，竞争如此剧烈，资源日渐紧张的今天，人们做任何事，无不望求事半功倍之术，以求或提效、或增收、或节约等等之目标。 数学建模竞赛中的优化问题 2000B 钢管订购和运输问题—二次规划 2001B 公交车优化调度 2001C 基金使用的最优策略-----线性规划 2002B 彩票中的数学 2003B 露天矿生产的车辆安排问题 2004A 奥运会临时超市网点设计问题 2004D 公务员招聘工作中录用方案—多目标规划 2005B DVD在线租赁 2006A 出版社的资源配置问题 2007A 乘公交，看奥运 2008B 高等教育学费探讨 2009B 眼科病床的合理安排 2011B 交巡警服务平台的设置和调度 2012B 太阳能小屋的设计 2013B 碎纸片的拼接复原 数学建模竞赛中的优化问题 2002B，彩票中的数学—约束非线性规划 最优化概念 所有类似的这种课题统称为最优化问题，研究解决这些问题的科学一般就总称之为最优化理论和方法 另外也可用学术味更浓的名称：“运筹学”。由于最优化问题背景十分广泛，涉及的知识不尽相同，学科分枝很多，因此这个学科名下到底包含哪些分枝，其说法也不一致。 比较公认的是：“规划论”（包括线性和非线性规划、整数规划、动态规划、多目标规划和随机规划等），“组合最优化”，“对策论”及“最优控制”等等。 从数学上来看，所谓最优化问题可以概括为这样一种数学模型：给定一个“函数”，F(X)，以及“自变量”X应满足的一定条件，求X为怎样的值时，F(X)取得其最大值或最小值。通常，称F(X)为“目标函数”，X应满足的条件为“约束条件”。约束条件一般用一个集合D表示为：X∈D。 求目标函数F(X)在约束条件X∈D下的最小值或最大值问题，就是一般最优问题的数学模型． 最优化问题的一般形式 最优化问题分类 最优化问题分类(续） 最优化问题分类(续） 二、线性规划模型 线性规划模型的三种形式 ②．为了把一般形式的LP问题变换为标准形式，必须消除其不等式约束和符号无限制变量. 运输问题 例2. 设要从甲地调出物资2000吨，从乙地调出物 数学模型： 背包问题 例4. 有 n 个物品，编号为1, 2, …, n，第 i 件物品 指派问题 例5. 有n 项任务，由 n 个人来完成，每个人只能 DVD在线租赁第二个问题的求解 问题二的分析 问题二的模型及求解 乙 甲 D C B A 解 一般的运输问题可以表述如下： 若其中各产地的总产量等于各销地的总销量，即 类似与将一般的线性规划问题转化为其标准 否则，称为不平衡的运输问题，包括： ，则称该问题为平衡的运输问题. 总产量总销量和总产量总销量. 形式，我们总可以通过引入假想的销地或产地， 将不平衡的运输问题转化为平衡的运输问题. 从 而，我们的重点就是解决平衡运输问题的求解. 显然，运输问题是一个标准的线性规划问题，因而当然可以运用单纯形方法求解. 但由于平衡的运输问题的特殊性质，它还可以用其它的一些特殊方法求解，其中最常用的就是表上作业法，该方法将单纯形法与平衡的运输问题的特殊性质结合起来，很方便地实行了运输问题的求解. 关于运输问题及其解法的进一步介绍参加文献[2]. 对于线性规划问题，如果要求其决策变量取 整数值，则称该问题为整数线性规划问题. 平面法和分支定界法是两种常用的求解整数线性 对于整数线性规划问题的求解，其难度和运 三、整数线性规划模型 算量远大于同规模的线性规划问题. Gomory割 规划问题的方法（见文献[1]）. 此外，同线性规 划模型一样，我们也可以运用LINGO和LINDO软 件包来求解整数线性规划模型. 以1988年美国大学生数学建模竞赛B题为例，说明整数线性规划模型的建立及用LINGO软件包如何求解整数线性规划模型。 例3. 有七种规格的包装箱要装到两节铁路平板车 上去。包装箱的宽和高是一样的，但厚度（t，以 cm 计）及重量（w，以kg计）是不同的. 表1给出 了每种包装箱的厚度、重量以及数量。每节平板 车有10.2m 长的地方可用来装包装箱（像面包片 那样），载重为40t. 由于当地货运的限制，对于 C5, C6, C7 类包装箱的总数有一个特别的限制：这 类箱子所占的空间（厚度）不能