离散优化数学建模.ppt

2008年B题 高等教育学费标准探讨 请你们根据中国国情，收集诸如国家生均拨款、培养费用、家庭收入等相关数据，并据此通过数学建模的方法，就几类学校或专业的学费标准进行定量分析，得出明确、有说服力的结论。数据的收集和分析是你们建模分析的基础和重要组成部分。你们的论文必须观点鲜明、分析有据、结论明确。 最后，根据你们建模分析的结果，给有关部门写一份报告，提出具体建议。 参考网站 [1] 全国大学生数学建模竞赛网： [2] 数学中国网站 [3] 中国数学建模网站： 最优化概论 从数学意义上说，最优化方法是一种求极值的方法，即在一组约束为等式或不等式的条件下，使系统的目标函数达到极值，即最大值或最小值。从经济意义上说，是在一定的人力、物力和财力资源条件下，使经济效果达到最大（如产值、利润），或者在完成规定的生产或经济任务下，使投入的人力、物力和财力等资源为最少。 一、最优化概念 所有类似的这种课题统称为最优化问题，研究解决这些问题的科学一般就总称之为最优化理论和方法 另外也可用学术味更浓的名称：“运筹学”。由于最优化问题背景十分广泛，涉及的知识不尽相同，学科分枝很多，因此这个学科名下到底包含哪些分枝，其说法也不一致。 比较公认的是：“规划论”（包括线性和非线性规划、整数规划、动态规划、多目标规划和随机规划等），“组合最优化”，“对策论”及“最优控制”等等。 数学建模竞赛中的优化问题 2000B 钢管订购和运输问题— 组合优化 2001B 公交车优化调度—图论 2002B 彩票中的数学— 决策分析 2003B 露天矿生产的车辆安排问题— 离散优化 2004A 奥运会临时超市网点设计问题 —图论 2005B DVD在线租赁— 离散优化 2006A 出版社的资源配置问题 — 决策分析 07B 乘公交，看奥运 —图论 整数规划 08B 高等教育学费探讨— 层次分析法 多目标优化 09B 眼科病床的合理安排—动态规划 10B 上海世博会经济影响力定量评估 —决策分析 11B 交巡警服务平台的设置与调度—图论 多目标规划 12B 太阳能小屋的设计 — 离散优化 13A 车道被占用对城市道路通行能力的影响 — 离散优化 从数学上来看，所谓最优化问题可以概括为这样一种数学模型：给定一个“函数”，F(X)，以及“自变量”X应满足的一定条件，求X为怎样的值时，F(X)取得其最大值或最小值。通常，称F(X)为“目标函数”，X应满足的条件为“约束条件”。约束条件一般用一个集合D表示为：X∈D。 求目标函数F(X)在约束条件X∈D下的最小值或最大值问题，就是一般最优问题的数学模型． 二、最优化问题的一般形式 三、最优化问题分类 三、最优化问题分类 三、最优化问题分类 最优化方法解决问题的步骤 （1）确定变量，写出目标函数和有关约束条件，建立数学模型。 （2）分析模型，搞清它属于运筹学哪一分枝，选择合适的最优化方法； （3）编程求解；尽量利用现有的数学软件或最优化软件，比如 Matlab，Mathematica， Lindo， Lingo等，来计算。 （4）最优解的验证和实施。 Chapter1 线性规划 (Linear Programming) 线性规划问题的数学模型 1. 规划问题 线性规划问题的数学模型 线性规划问题的数学模型 解：设x1、x2分别为甲、乙两种产品的产量，则数学模型为： 这是一个典型的利润最大化的生产计划问题。其中，“Max”是英文单词“Maximize”的缩写，含义为“最大化”；“s.t.”是“subject to”的缩写，表示“满足于…”。因此，上述模型的含义是：在给定条件限制下，求使目标函数 z 达到最大的x1 ,x2 的取值。 线性规划问题的数学模型 线性规划问题的数学模型 线性规划问题的数学模型 线性规划问题的数学模型 3. 线性规划问题的标准形式 线性规划问题的数学模型 线性规划问题的数学模型 线性规划问题的数学模型 4. 线性规划问题的解 线性规划问题的数学模型 Chapter2 运输问题( Transportation Problem ) 1.运输问题模型及有关概念 问题的提出 一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。 运输问题的数学模型 例2.1 某公司从两个产地A1、A2将物品运往三个销地B1, B2, B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？ 运输问题的数学模