一、线性规划
1.简介
1.1适用情况
用现有资源来安排生产，以取得最大经济效益的问题。如： （1）资源的合理利用
（2）投资的风险与利用问题 （3）合理下料问题 （4）合理配料问题 （5）运 输 问 题 （6）作物布局问题
（7）多周期生产平滑模型 （8）公交车调度安排 1.2建立线性规划的条件
（1）要求解问题的目标函数能用数值指标来反映，且为线性函数； （2）要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描述。 1.3线性规划模型的构成
决策变量、目标函数、约束条件。
2、一般线性规划问题
数学标准形式：
目标函数：
1
max ==
∑ n
j
j
j z c
x
约束条件：1
,1,2,...,,..0,1,2,...,.=?==???≥=?∑n
ij j i j j
a x
b i m s t x j n
matlab 标准形式：
min ,
,.,.?≤??
?=??≤≤?
T s t Aeq beq lb ub f x A x b x x
3、可以转化为线性规划的问题
例：求解下列数学规划问题
1234123412341234min ||2||3||4||,2,..31,123.
2=+++?
?--+≤-?-+-≤-???--+≤-?
z x x x x x x x x s t x x x x x x x x
解：作変量変换1||||,,1,2,3,4,22
+-=
==i i i i
i x x x x u v i 并把新变量重新排序成一维变量[]1414,,,,,??==????
L L T
u y u u v v v ，则可把模型转化为线性规划模型
[]min ,
,,..0.???-≤???????≥?
T c y u A A b s t v y 其中：[]1,2,3,4,1,2,3,4;=T c 12,1,;2??=---???
?T
b 111111131 - - ??
??= - -???? -1 -1 3??A 。 利用matlab 计算得最优解：12342,0,=-===x x x x 最优值z=2。 程序如下：
略
二、整数规划
1.简介
数学规划中的变量(部分或全部)限制为整数时称为整数规划。目前流行求解整数规划的方法一般适用于整数线性规划。 1.1整数规划特点
1）原线性规划有最优解，当自变量限制为整数后，出现的情况有
①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。
②整数规划无可行解。
③有可行解（存在最优解），但最优解值变差。
2）整数规划最优解不能按照实数最优解简单取整获得。 1.2求解方法分类
（1）分枝定界法—可求纯或混合整数线性规划。 （2）隔平面法—可求纯或混合整数线性规划。 （3）隐枚举法—可求“0-1”整数规划。 （4）匈牙利法—解决指派问题。
（5）蒙特卡洛法—求解各种类型规划. 1.3整数规划的应用模型 （1）固定费用的问题。 （2）指派问题。 （3）合理下料问题。 （4）流动推销员问题。 （5）生产与销售计划问题。
2、一般整数规划模型
目标函数：
1
max ==
∑ n
j
j j z c
x
约束条件：
1
,1,2,...,,..0,1,2,...,.=?==???≥=?∑n
ij j j j j
a x
b i m s t x j n
例：指派问题的数学模型(0-1型整数规划)
拟分配n 人去做n 项工作，若分配第i 人去做第j 项工作，需花费ij c 单位时间，如何分配工作才能使花费总时间最少？ 模型的建立
引入0-1变量1,i j 0第人做第项工作，
，第i 人不做第j 项工作.?=??ij x
指派问题的数学模型为
1
1
min ,===
∑∑ n
n
ij
ij i j z c
x
111,1,2,...,,..1,1,2,...,,01,,1,2,...,.或==?==???==???= =??
∑∑n
ij j n ij i ij x i n s t x j n x i j n 利用匈牙利算法、拍卖算法等求解出最优解。
三、非线性规划
1、简介
目标函数或约束条件中包含非线性函数的规划问题为非线性规划问题。 1.1非线形规划模型的构成
决策变量、目标函数、约束条件。 1.2非线性规划的应用模型
（1）存贮模型 （2）飞行管理问题 （3）森林救火
（4）抽水费用最小问题 （5）钢管下料问题 （6）投资决策问题 （7）供应与选址问题 （8）广告的费用及其效用
2、非线性规划的模型
一般形式：
min (),
()0,1,2,,,..()0,1,2,,.目标函数：约束条件：≥=??==?L L j
i f h j q s t g i p x x x
其中：[]1,,=L T
n x x x 为模型的决策变量。 Matlab 中非线性规划的数学模型
min (),
,,..()0,()0,.
f x A x b Aeq x beq s t c x ceq x lb x ub ?≤???=??≤??=?≤≤?? 其中：f(x)是标量函数；A,b,Aeq,beq,lb,ub 是相应维数的矩阵和向量；c(x),cex(x)
是非线性向量函数。
3、罚函数法
利用罚函数法可将非线性规划问题的求解转化为求解一系列无约束极值问题。 问题
min (),
()0,1,,,
..()0,1,,,()0,1,,.
i j m f x g x i r s t h x j s k x m t ?≤=?
≥=??
==?L L L 取一个充分大的数M>0，构造函数
1
1
1
(,)()max((),0)min((),0)|()|,r s t
i j m i j m p x M f x M g x M h x M k x ====+-+∑∑∑
（或()()(,)()max min ||()||,00m G x H x p x M f x Msum Msum M k x ????
????=+-+ ? ? ? ?????????这
里[][][]111()(),,(),()(),,(),()(),,(),r s t G x g x g x H x h x h x K x k x k x ===L L L 可直接利用matlab 中的max 、min 和sum 函数），则增广目标函数P(x,M)为目标函数
的无约束极值问题minP(x,M)的最优解x 即为原问题的最优解。 注意：
1）如果非线性规划问题要求实时算法，则可用罚函数法，但计算精度较低。
2）如果非线性规划问题不要求实时算法，但要求精度高，可使用Lingo 软件编程求解或使用Matlab 的fmincon 命令求解。
四、目标规划
1、简介
1.1求解目标规划的思路
（1）加权系数法
为每一目标赋一个权系数，把多目标模型转化成单一目标的模型。但困难是要确定合理的权系数，以反映不同目标之间的重要程度。 （2）优先等级法
将各目标按其重要程度不同的优先等级，转化为单目标模型。 （3）有效解法
寻求能够照顾到各个目标，并使决策者感到满意的解。由决策者来确定选取哪一个解，即得到一个满意解。但有效解的数目太多而难以将其一一求出。 1.2建立目标规划的条件
（1）正、负偏差变量。
（2）绝对（刚性）约束和目标约束。 （3）优先因子（优先等级）与权系数。 1.3 目标规划的目标函数
目标规划的目标函数基本三种形式为
（1）第i 个目标要求恰好达到目标值，即正、负偏差变量都要尽可能地小，这时
i i i i min w d w d --++ +.
（2）第i 个目标要求不超过目标值，即允许达不到目标值，就是正偏差变量要尽可能地小，这时
.i i min w d ++
（3）第i 个目标要求超过目标值，即超过量不限，但必须是负偏差变量要尽可能地小，这时
.i i min w d --
1.4目标规划的模型应用
（1）求多目标下产品利润最优的决策方案。 （2）求多目标下总运费最小的运输调度方案。
2、目标规划的一般数学模型
设(1,2,,)j x j n =L 是目标规划的决策变量，共有m 个约束是刚性约束，可能是等式约束，也可能是不等式约束。设有l 个柔性目标约束，其目标规划约束的偏差为,(1,2,,)i i d d i l +-=L 。设有q 个优先级别，分别为12,,,q p p p ?。在同一个优先级k p 中，有不同的权重，分别
记为,(1,2,,)ki
ki w w i l +-=L 。目标规划模型的一般数学表达式如下 1
1
1
01
min ()
(,),1,,,,1,,,..0,1,2,,,,0,1,2,,.
q l
k ki i ki i k i n
tj j t j n ij j i i i j j i i z p w d w d a x b t m c x d d d i l s t x j n d d i l --++===-+=-+=+?≤=≥=?
???+-==???≥=?≥=??∑∑∑∑L L L L 可用序贯算法求解目标规划。
3、数据包网络分析（DEA ）
3.1适用范围
DEA 特别适用于具有多输入多输出的复杂系统，如技术进步、技术创新、资源配置、金融投资等领域，特别对非单纯利益公共部门，如学校、医院、某些文化设施的评价方面。 3.2特点
1）DEA 以决策单位各输入/输出的权重为变量，
1）数据包络分析的C2R 模型
设有n 个DMU ，每个DMU 都有m 种投入和s 种产出，设
1,,;1,,ij x i m j n
==L L （）表示第 j 个DMU 的第i 种投入量， 1,,1,,rj y r s j n ==L L （；）表示第 j 个DMU 的第r 种产出量，(1,,)i v i m =L 表示第i 种投入的权值，1,,r u r s =L （）
表示第r 种产出的权值。
向量,(1,,)j j X Y j n =L 分别表示决策单元 j 的输入和输出向量，v 和u 分别表示输入输出权值向量，则12(,,,)T j j j mj X x x x =L ，12(,,,),
T j j j sj Y x x x =L 12(,,,)T m u u u u =L ，12(,,,)T S v v v v =L 。
定义决策单元j 的效率评价指数为
()/(),1,2,,.T T j j j h u Y v X j n ==L
评价决策单元0j 效率的数学模型为
00
max
,
1,1,2,,,..0,0,0,0.
T j T
j T j
T
j
u Y v X u Y j n s t v X u v u v ?≤=???
≥≥≠≠?L （1） 通过Charnes ?Cooper 变换：01
,,()
T j tv tu t v X ωμ===可以将模型（1）
转化为等价的线性规划问题
000max ,
0,1,2,,,
..1,0.T j j T T j j T
j j n s t =?-≥=??=??
≥≥??
L V Y X Y X μωμωω0,μ 对于C 2R 模型，有如下定义：
（1）若线性规划问题的最优目标01j v =,则称决策单元0j 是弱DEA 有效的。
（2）若线性规划问题存在最优解**0,0,μω>>并且其最优目标值
01j V =，则称决策单元0j 是EDA 有效的。
【关键字】设计、方法、条件、动力、增长、计划、问题、系统、网络、理想、要素、工程、项目、重点、检验、分析、规划、管理、优化、中心 数学建模常用模型方法总结 无约束优化 线性规划连续优化 非线性规划 整数规划离散优化 组合优化 数学规划模型多目标规划 目标规划 动态规划从其他角度分类 网络规划 多层规划等… 运筹学模型 （优化模型） 图论模型存 储论模型排 队论模型博 弈论模型 可靠性理论模型等… 运筹学应用重点:①市场销售②生产计划③库存管理④运输问题⑤财政和会计⑥人事管理⑦设备维修、更新和可靠度、项目选择和评价⑧工程的最佳化设计⑨计算器和讯息系统⑩城市管理 优化模型四要素：①目标函数②决策变量③约束条件 ④求解方法(MATLAB--通用软件LINGO--专业软件) 聚类分析、 主成分分析 因子分析 多元分析模型判别分析 典型相关性分析 对应分析 多维标度法 概率论与数理统计模型 假设检验模型 相关分析 回归分析 方差分析 贝叶斯统计模型 时间序列分析模型 决策树 逻辑回归
传染病模型马尔萨斯人口预测模型微分方程模型人口预 测控制模型 经济增长模型Logistic 人口预测模型 战争模型等等。。 灰色预测模型 回归分析预测模型 预测分析模型差分方程模型 马尔可夫预测模型 时间序列模型 插值拟合模型 神经网络模型 系统动力学模型(SD) 模糊综合评判法模型 数据包络分析 综合评价与决策方法灰色关联度 主成分分析 秩和比综合评价法 理想解读法等 旅行商(TSP)问题模型 背包问题模型车辆路 径问题模型 物流中心选址问题模型 经典NP问题模型路径规划问题模型 着色图问题模型多目 标优化问题模型 车间生产调度问题模型 最优树问题模型二次分 配问题模型 模拟退火算法(SA) 遗传算法(GA) 智能算法 蚁群算法(ACA) (启发式) 常用算法模型神经网络算法 蒙特卡罗算法元 胞自动机算法穷 举搜索算法小波 分析算法 确定性数学模型 三类数学模型随机性数学模型 模糊性数学模型
1. 什么是数学模型与数学建模 简单地说：数学模型就是对实际问题的一种数学表述。 具体一点说：数学模型是关于部分现实世界为某种目的的一个抽象的简化的数学结构。 更确切地说：数学模型就是对于一个特定的对象为了一个特定目标，根据特有的内在规律，做出一些必要的简化假设，运用适当的数学工具，得到的一个数学结构。数学结构可以是数学公式，算法、表格、图示等。 数学建模就是建立数学模型，建立数学模型的过程就是数学建模的过程（见数学建模过程流程图）。数学建模是一种数学的思考方法，是运用数学的语言和方法，通过抽象、简化建立能近似刻划并"解决"实际问题的一种强有力的数学手段。 2.美国大学生数学建模竞赛的由来： 1985年在美国出现了一种叫做MCM的一年一度大大学生数学模型（1987年全称为Mathematical Competition in Modeling,1988年改全称为Mathematical Contest in Modeling,其所写均为MCM）。这并不是偶然的。在1985年以前美国只有一种大学生数学竞赛（The william Lowell Putnam mathematial Competition,简称Putman(普特南）数学竞赛），这是由美国数学协会（MAA--即Mathematical Association of America的缩写）主持，于每年12月的第一个星期六分两试进行，每年一次。在国际上产生很大影响，现已成为国际性的大学生的一项著名赛事。该竞赛每年2月或3月进行。 我国自1989年首次参加这一竞赛，历届均取得优异成绩。经过数年参加美国赛表明，中国大学生在数学建模方面是有竞争力和创新联想能力的。为使这一赛事更广泛地展开，1990年先由中国工业与应用数学学会后与国家教委联合主办全国大学生数学建模竞赛（简称CMCM），该项赛事每年9月进行。
数学建模常用的十大算法==转 (2011-07-24 16:13:14) 转载▼ 1. 蒙特卡罗算法。该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟来检验自己模型的正确性，几乎是比赛时必用的方法。 2. 数据拟合、参数估计、插值等数据处理算法。比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用MA TLAB 作为工具。 3. 线性规划、整数规划、多元规划、二次规划等规划类算法。建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo 软件求解。 4. 图论算法。这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备。 5. 动态规划、回溯搜索、分治算法、分支定界等计算机算法。这些算法是算法设计中比较常用的方法，竞赛中很多场合会用到。 6. 最优化理论的三大非经典算法：模拟退火算法、神经网络算法、遗传算法。这些问题是用来解决一些较困难的最优化问题的，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用。 7. 网格算法和穷举法。两者都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具。 8. 一些连续数据离散化方法。很多问题都是实际来的，数据可以是连续的，而计算机只能处理离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。 9. 数值分析算法。如果在比赛中采用高级语言进行编程的话，那些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。 10. 图象处理算法。赛题中有一类问题与图形有关，即使问题与图形无关，论文中也会需要图片来说明问题，这些图形如何展示以及如何处理就是需要解决的问题，通常使用MA TLAB 进行处理。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 2 十类算法的详细说明 2.1 蒙特卡罗算法 大多数建模赛题中都离不开计算机仿真，随机性模拟是非常常见的算法之一。 举个例子就是97 年的A 题，每个零件都有自己的标定值，也都有自己的容差等级，而求解最优的组合方案将要面对着的是一个极其复杂的公式和108 种容差选取方案，根本不可能去求解析解，那如何去找到最优的方案呢？随机性模拟搜索最优方案就是其中的一种方法，在每个零件可行的区间中按照正态分布随机的选取一个标定值和选取一个容差值作为一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从中选取一个最佳的。另一个例子就是去年的彩票第二问，要求设计一种更好的方案，首先方案的优劣取决于很多复杂的因素，同样不可能刻画出一个模型进行求解，只能靠随机仿真模拟。 2.2 数据拟合、参数估计、插值等算法 数据拟合在很多赛题中有应用，与图形处理有关的问题很多与拟合有关系，一个例子就是98 年美国赛A 题，生物组织切片的三维插值处理，94 年A 题逢山开路，山体海拔高度的插值计算，还有吵的沸沸扬扬可能会考的“非典”问题也要用到数据拟合算法，观察数据的
-16- 第二章 整数规划 §1 概论 1.1 定义 规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。 1.2 整数规划的分类 如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类： 1o 变量全限制为整数时，称纯（完全）整数规划。 2o 变量部分限制为整数的，称混合整数规划。 1.2 整数规划特点 （i ） 原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况： ①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。 ②整数规划无可行解。 例1 原线性规划为 21min x x z += 0,0, 5422121≥≥=+x x x x 其最优实数解为：4 5 min ,45,021===z x x 。 ③有可行解（当然就存在最优解），但最优解值变差。 例2 原线性规划为 21min x x z += 0,0, 6422121≥≥=+x x x x 其最优实数解为：2 3 min ,23,021===z x x 。 若限制整数得：2min ,1,121===z x x 。 （ii ） 整数规划最优解不能按照实数最优解简单取整而获得。 1.3 求解方法分类： （i ）分枝定界法—可求纯或混合整数线性规划。 （ii ）割平面法—可求纯或混合整数线性规划。 （iii ）隐枚举法—求解“0-1”整数规划： ①过滤隐枚举法； ②分枝隐枚举法。 （iv ）匈牙利法—解决指派问题（“0-1”规划特殊情形）。 （v ）蒙特卡洛法—求解各种类型规划。 下面将简要介绍常用的几种求解整数规划的方法。 §2 分枝定界法 对有约束条件的最优化问题（其可行解为有限数）的所有可行解空间恰当地进行系统搜索，这就是分枝与定界内容。通常，把全部可行解空间反复地分割为越来越小的子集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为定界。在每次分枝后，凡是界限超出已知可行解集目标值的那些子集不再进一步分枝，
线性规划 1.简介： 线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料.二是生产组织与计划的改进，即合理安排人力物力资源. 线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好.规划问题。一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域。 (x)都是线性函数，则该模型称为在优化模型中，如果目标函数f(x)和约束条件中的g i 线性规划。 2.线性规划的3个基本要素 （1）决策变量 （2）目标函数f(x) (x)≤0称为约束条件） （3）约束条件（g i 3.建立线性规划的模型 （1）找出待定的未知变量（决策变量），并用袋鼠符号表示他们。 （2）找出问题中所有的限制或者约束，写出未知变量的线性方程或线性不等式。
（3）找到模型的目标或判据，写成决策变量的线性函数，以便求出其最大值或最小值。以下题为例，来了解一下如何将线性规划用与实际的解题与生活中。 生产计划问题 某工厂生产甲乙两种产品，每单位产品消耗和获得的利润如表 试拟订生产计划，使该厂获得利润最大 解答：根据解题的三个基本步骤 （1）找出未知变量，用符号表示： 设甲乙两种产品的生产量分别为x 1与x 2 吨，利润为z万元。 （2）确定约束条件： 在这道题目当中约束条件都分别为：钢材，电力，工作日以及生产量不能为负的限制 钢材：9x 1+5 x 2 ≤360， 电力：4x 1+5 x 2 ≤200， 工作日：3x 1+10 x 2 ≤300， x 1≥0 ，x 2 ≥0， （3）确定目标函数： Z=7x 1+12 x 2
数学建模中常见的十大 模型 Document serial number【KKGB-LBS98YT-BS8CB-BSUT-BST108】
数学建模常用的十大算法==转 (2011-07-24 16:13:14) 1. 蒙特卡罗算法。该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟来检验自己模型的正确性，几乎是比赛时必用的方法。 2. 数据拟合、参数估计、插值等数据处理算法。比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用MATLAB 作为工具。 3. 线性规划、整数规划、多元规划、二次规划等规划类算法。建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo 软件求解。 4. 图论算法。这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备。 5. 动态规划、回溯搜索、分治算法、分支定界等计算机算法。这些算法是算法设计中比较常用的方法，竞赛中很多场合会用到。 6. 最优化理论的三大非经典算法：模拟退火算法、神经网络算法、遗传算法。这些问题是用来解决一些较困难的最优化问题的，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用。 7. 网格算法和穷举法。两者都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具。
8. 一些连续数据离散化方法。很多问题都是实际来的，数据可以是连续的，而计算机只能处理离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。 9. 数值分析算法。如果在比赛中采用高级语言进行编程的话，那些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。 10. 图象处理算法。赛题中有一类问题与图形有关，即使问题与图形无关，论文中也会需要图片来说明问题，这些图形如何展示以及如何处理就是需要解决的问题，通常使用MATLAB 进行处理。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 2 十类算法的详细说明 蒙特卡罗算法 大多数建模赛题中都离不开计算机仿真，随机性模拟是非常常见的算法之一。 举个例子就是97 年的A 题，每个零件都有自己的标定值，也都有自己的容差等级，而求解最优的组合方案将要面对着的是一个极其复杂的公式和108 种容差选取方案，根本不可能去求解析解，那如何去找到最优的方案呢随机性模拟搜索最优方案就是其中的一种方法，在每个零件可行的区间中按照正态分布随机的选取一个标定值和选取一个容差值作为一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从中选取一个最佳的。另一个例子就是去年的彩票第二问，要求设计一种更好的方案，首先方案的优劣取决于很多复杂的因素，同样不可能刻画出一个模型进行求解，只能靠随机仿真模拟。
-1- 第一章线性规划 §1 线性规划 在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济 效益的问题。此类问题构成了运筹学的一个重要分支—数学规划，而线性规划(Linear Programming 简记LP)则是数学规划的一个重要分支。自从1947 年G. B. Dantzig 提出 求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在实用中日益广泛与深入。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性 规划的适用领域更为广泛了，已成为现代管理中经常采用的基本方法之一。 1.1 线性规划的实例与定义 例1 某机床厂生产甲、乙两种机床，每台销售后的利润分别为4000 元与3000 元。 生产甲机床需用A、B机器加工，加工时间分别为每台2 小时和1 小时；生产乙机床 需用A、B、C三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时 数分别为A 机器10 小时、B 机器8 小时和C 机器7 小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？ 上述问题的数学模型：设该厂生产1 x 台甲机床和2 x 乙机床时总利润最大，则1 2 x , x 应满足 （目标函数）1 2 max z = 4x + 3x (1) s.t.（约束条件） ?? ? ?? ? ? ≥ ≤ + ≤ + ≤ , 0 7 8 2 10 1 2 2 1 2 1 2 x x x x x x x （2） 这里变量1 2 x , x 称之为决策变量，（1）式被称为问题的目标函数，（2）中的几个不等式是问题的约束条件，记为s.t.(即subject to)。由于上面的目标函数及约束条件均为线性
数学建模
论文题目： 一个医药公司的新药研究部门为了掌握一种新止痛剂的疗效，设计了一个药物试验，给患有同种疾病的病人使用这种新止痛剂的以下4个剂量中的某一个：2 g，5 g，7 g和10 g，并记录每个病人病痛明显减轻的时间（以分钟计）. 为了解新药的疗效与病人性别和血压有什么关系，试验过程中研究人员把病人按性别及血压的低、中、高三档平均分配来进行测试. 通过比较每个病人血压的历史数据，从低到高分成3组，分别记作，和. 实验结束后，公司的记录结果见下表（性别以0表示女，1表示男）. 请你为该公司建立一个数学模型，根据病人用药的剂量、性别和血压组别，预测出服药后病痛明显减轻的时间.
一、摘要 在农某医药公司为了掌握一种新止痛药的疗效，设计了一个药物实验，通过观测病人性别、血压和用药剂量与病痛时间的关系，预测服药后病痛明显减轻的时间。我们运用数学统计工具m i n i t a b软件，对用药剂量，性别和血压组别与病痛减轻
时间之间的数据进行深层次地处理并加以讨论概率值P （是否<）和拟合度R-S q的值是否更大（越大，说明模型越好）。 首先，假设用药剂量、性别和血压组别与病痛减轻时间之间具有线性关系，我们建立了模型Ⅰ。对模型Ⅰ用m i n i t a b 软件进行回归分析，结果偏差较大，说明不是单纯的线性关系，然后对不同性别分开讨论，增加血压和用药剂量的交叉项，我们在模型Ⅰ的基础上建立了模型Ⅱ，用m i n i t a b软件进行回归分析后，用药剂量对病痛减轻时间不显着，于是我们有引进了用药剂量的平方项，改进模型Ⅱ建立了模型Ⅲ，用m i n i t a b 软件进行回归分析后，结果合理。最终确定了女性病人服药后病痛减轻时间与用药剂量、性别和血压组别的关系模型： Y=1x 3x 1x 3x 2 1 x 对模型Ⅱ和模型Ⅲ关于男性病人用m i n i t a b软件进行回归分析，结果偏差依然较大，于是改进模型Ⅲ建立了模型Ⅳ，用m i n i t a b软件进行回归分析后，结果合理。最终确定了男性病人服药后病痛减轻时间与用药剂量、性别和血压组别的关系模 型：Y=1x1x 3x 2 1 x关键词止痛剂药剂量性别病痛减轻时 间
整数规划模型
实际问题中 x x x x f z Max Min T n "),(),()(1==或的优化模型 m i x g t s i ",2,1,0)(..=≤x ~决策变量f (x )~目标函数g i (x )≤0~约束条件 多元函数决策变量个数n 和数 线性规划条件极值约束条件个数m 较大最优解在可行域学 规 非线性规划解 的边界上取得划 整数规划
Programming +Integer 所有变量都取整数，称为纯整数规划；有一部分取整数，称为混合整数规划；限制取0，1称为0‐1型整数规划。 型整数规划
+整数线性规划 max(min) n z c x =1j j j n =∑1 s.t. (,) 1,2,,ij j i j a x b i m =≤=≥=∑"12 ,,,0 () n x x x ≥"且为整数 或部分为整数
+例：假设有m 种不同的物品要装入航天飞机，它们的重量和体积分别为价值为w j 和v j ，价值为c j ，航天飞机的载重量和体积限制分别为W 和V ，如何装载使价值最大化？ m 1?1 max j j j c y =∑ 1 0j j y =?被装载 s.t. m j j v y V ≤∑0 j ?没被装载1 j m =1 j j j w y W =≤∑ 0 or 1 1,2,,j y j m =="
(Chicago)大学的Linus Schrage教授于1980年美国芝加哥(Chi)Li S h 前后开发, 后来成立LINDO系统公司（LINDO Systems Inc.），网址：https://www.doczj.com/doc/39397122.html, I）网址htt//li d LINDO: Interactive and Discrete Optimizer (V6.1) Linear(V61) LINGO: Linear Interactive General Optimizer (V8.0) LINDO——解决线性规划LP—Linear Programming，整数规划IP—Integer Programming问题。 LINGO——解决线性规划LP—Linear Programming，非线性规划NLP—Nonlinear Programming，整数规划IP—Integer Programming g g整划g g g 问题。
工厂资源规划问题 冉光明 29 信息与计算科学 指导老师：赵姣珍
目录 摘要 (1) 关键词 (1) 问题的提出 (2) 问题重述与分析 (3) 符号说明 (4) 模型假设 (4) 模型建立与求解 (5) 模型检验 (9) 模型推广 (10) 参考文献 (11) 附录 (12)
摘要：本问题是个优化问题。问题首先选择合适的决策变量即各种产品数，然后通过决策变量来表达约束条件和目标函数，再利用或编写程序，求得最优产品品种计划；最后通过优化模型对问题作以解释，得出当技术服务消耗33小时、劳动力消耗67小时、不消耗行政管理时，得到的是最优品种规划。 问题一回答：当技术服务消耗33小时、劳动力消耗67小时、不消耗行政管理时， 产品不值得生产。用运算分析，当产品的利润增加至25 3 时，若使产品品种计划最优， 此时需要消耗技术服务29h，劳动力消耗46h，行政管理消耗25h。 问题二回答：利用得到当技术服务增加1h时，利润增加2.5元;劳动力增加1h，利润增加1元；行政管理的增减不会影响利润。 问题三回答：增加的决策变量，调整目标函数。当技术服务消耗33h，劳动力消耗17h，不消耗行政管理，新增量50h时，管理部门采取这样的决策得到最优的产品品种规划。 问题四回答：增加新的约束条件，此时当技术服务消耗32h，劳动力消耗58h，行政管理消耗10h时，得到最优产品品种规划。 本文对模型的求解给出在线性约束条件下的获利最多的产品品种规划。 关键词：线性规划；优化模型；最优品种规划
问题的提出 某工厂制造三种产品，生产这三种产品需要三种资源：技术服务、劳动力和行政管理。下表列出了三种单位产品对每种资源的需要量： 现有100h的技术服务、600h劳动力和300h的行政管理时间可使用，求最优产品品种规划。且回答下列问题： ⑴若产品值得生产的话，它的利润是多少？假使将产品的利润增加至25/3元，求获利最多的产品品种规划。 ⑵确定全部资源的影子价格。 ⑶制造部门提出建议，要生产一种新产品，该种产品需要技术服务1h、劳动力4h 和行政管理4h。销售部门预测这种产品售出时有8元的单位利润。管理部门应有怎样的决策？ ⑷假定该工厂至少生产10件产品，试确定最优产品品种规划。
五邑大学 数学建模 课程考核论文 2010-2011 学年度第 2 学期 010 20 30 40 50 60 70 8090 第一季度第三季度 东部西部北部 论文题目 抑制物价快速上涨问题 得分 学号 姓名（打印） 姓名（手写） ap0808221 林加海 ap0808204 陈荣昌 指导老师—邹祥福
——2011.6.20 抑制物价快速上涨问题 摘要 本文通过一个多元线性回归模型较好地解决了影响物价因素的问题。使我国经济快速发展的同时，使百姓得到真的实惠，又保证了经济的长远的发展。 物价问题比较复杂。在本次实验中我们参阅大量资料把影响物价的的因素主要概括括需求性因素（消费，投资，进出口，政府支出等）、货币性因素（货币供给量）、结构性因素（房地产价格，农产品价格等）以及其他因素（如预期因素等）。 总结出原先物价计算方法的不足之处，需要建立一种新的计算和预测的方法。首先，为了确定物价和影响因素之间的关系我们用了多元线性回归，从国家统计局找到相关数据经过挑选，建立了函数关系，为了使函数更具有说服力我们进一步用了残差分析，检验所得到的结果的合理性 。本文利用matlab 软件实现了拟合出多元线性回归函数y=86.4798967193207+0.00441024146152813*x1+4.32730555279258e-007*x2+0.00377788223112076*x3+2.70211635024846e-006*x4+7.58738000216411e-005*x5，置信度95％，且20.932609896853743,_R F ==检验值8.30338450288840>，但是显著性概率.α=005相关的0.055839341752489056>0.p =。再利用逐步回归的方法，拟合出Y=94.4958+0.00771506*x1+5.8917e-007*x2+0.00250019*x3+1.90595e-006*x4+ 6.62396e-005*x5.93269896853743R =200，修正的R 2值.R α =20897797，F_检验值＝26.3535，与显著性概率相关的p 值＝..<000106754005，残差均方RMSE ＝0.204517，以上指标值都很好，说明回归效果比较理想。通过对物价形成及演化问题的讨论，提出以量化分析为基础的调节物价的方法，深入分析找出影响物价的主要因素，并就此分析现在物价的上涨情况，根据《关于稳定消费价格总水平保障群众基本生活的通知》，根据模型分析给出抑制物价的政策建议，并对未来的形势走向根据模型给出预测。 关键字：物价，逐步回归分析，上涨因素，预测，多元回归分析
2011高教社杯全国大学生数学建模竞赛 承诺书 我们仔细阅读了中国大学生数学建模竞赛的竞赛规则. 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。 我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）：北京大学 参赛队员(打印并签名) ：1. 姚胜献 2. 许锦敏 3. 刘迪初 指导教师或指导教师组负责人(打印并签名)：刘业辉 日期： 2011 年 9 月 12日赛区评阅编号（由赛区组委会评阅前进行编号）：
2011高教社杯全国大学生数学建模竞赛 编号专用页 赛区评阅编号（由赛区组委会评阅前进行编号）： 全国评阅编号（由全国组委会评阅前进行编号）： 交巡警服务平台的设置与调度 摘要 本文通过建立整数规划模型，解决了分配各平台管辖范围、调度警务资源以及合理设置交巡警服务平台这三个方面的问题；通过建立线性加权评价模型定量评价了某市现有交巡警服务平台设置方案的合理性，并根据各个区对服务平台需求量的不同，提出了重新分配全市警力资源的解决方案。在计算交巡警服务平台到各个路口节点的路程时，使用了图论里的floyd算法。 针对问题一的第一个子问题，首先假设交巡警服务平台对某个路口节点的覆盖度是二元的，引入决策变量，建立了0-1整数规划模型。交巡警出警应体现时间的紧迫性，所以选择平均每个突发事件的出警时间最短作为目标函数，运用基于MATLAB的模拟退火算法进行求解，给出了中心城区A的20个服务平台的管辖范围，求得平均每个案件的出警时间为1.013分钟。 针对问题一的第二个子问题，为了实现对中心城区A的13个交通要道的快速全封锁，以最短的封锁时间为目标，建立了0-1整数规划模型，利用lingo软件编程求解，给出了该区交巡警服务平台警力合理的调度方案，并求得对13个交通要道实现全封锁最短需要8.02分钟。 问题一的第三个子问题是交巡警服务平台的选址问题。考虑到建设新的服务平台需要投入更多的成本和警务资源，还需平衡各个服务平台的工作量。因此，以增加最少的服务平台数和服务平台工作量方差最小为目标，采用集合覆盖理论，建立了双目标0-1整数规划模型，用基于MATLAB的模拟退火算法求解出增加的服务平台数为4个，新增 的服务平台具体位置为A 28,A 40 ,A 48 ,A 88 ，并得到各个服务平台的工作强度方差为2.28。 针对问题二的第一个子问题，通过建立线性加权评价模型定量评价了该市现有交巡警服务平台设置方案的合理性，结果发现全市服务平台覆盖率较低且各个区的工作量不均衡，得出全市服务平台的布局存在明显的不合理的结论。并确定各区域人口密度、各区域公路总长度以及各区域平均每天总的发案率为各区域对交巡警需求的指标，然后根据各个区对服务平台需求量的不同，提出了较为合理的分配全市警力资源的解决方案。 对于问题二的第二个子问题，以围堵范围最小和调动警力最少的原则，通过分析案发后嫌疑犯可能到达的位置，给出了围堵方案。 关键词：交巡警服务平台 0-1整数规划模拟退火法
一、线性规划 1.简介 1.1适用情况 用现有资源来安排生产，以取得最大经济效益的问题。如： （1）资源的合理利用 （2）投资的风险与利用问题 （3）合理下料问题 （4）合理配料问题 （5）运 输 问 题 （6）作物布局问题 （7）多周期生产平滑模型 （8）公交车调度安排 1.2建立线性规划的条件 （1）要求解问题的目标函数能用数值指标来反映，且为线性函数； （2）要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描述。 1.3线性规划模型的构成 决策变量、目标函数、约束条件。 2、一般线性规划问题 数学标准形式： 目标函数： 1 max == ∑ n j j j z c x 约束条件：1 ,1,2,...,,..0,1,2,...,.=?==???≥=?∑n ij j i j j a x b i m s t x j n matlab 标准形式：
min , ,.,.?≤?? ?=??≤≤? T s t Aeq beq lb ub f x A x b x x 3、可以转化为线性规划的问题 例：求解下列数学规划问题 1234123412341234min ||2||3||4||,2,..31,123. 2=+++? ?--+≤-?-+-≤-???--+≤-? z x x x x x x x x s t x x x x x x x x 解：作変量変换1||||,,1,2,3,4,22 +-= ==i i i i i x x x x u v i 并把新变量重新排序成一维变量[]1414,,,,,??==???? L L T u y u u v v v ，则可把模型转化为线性规划模型 []min , ,,..0.???-≤???????≥? T c y u A A b s t v y 其中：[]1,2,3,4,1,2,3,4;=T c 12,1,;2??=---??? ?T b 111111131 - - ?? ??= - -???? -1 -1 3??A 。 利用matlab 计算得最优解：12342,0,=-===x x x x 最优值z=2。 程序如下： 略
传染病模型 摘要 当今社会，人们开始意识到通过定量地研究传染病的传播规律，建立传染病的传播模型，可以为预测和控制传染病提供可靠、足够的信息。本文利用微分方程稳定性理论对传统传染病动力学建模方式进行综述，且针对甲流，SARS等新生传染病模型进行建模和分析。 不同类型的传染病的传播过程有其各自不同的特点，我们不是从医学的角度一一分析各种传染病的传播，而是从一般的传播机理分析建立各种模型，如简单模型，SI模型，SIS模型，SIR模型等。本文中，我们应用传染病动力学模型来描述疾病发展变化的过程和传播规律，运用联立微分方程组体现疫情发展过程中各类人的内在因果联系，并在此基础上建立方程求解算法。然后，通过借助Matlab程序拟合出与实际较为符合的曲线并进行了疫情预测，评估各种控制措施的效果，从而不断完善文中的模型。 本文由简到难、全面地评价了该模型的合理性与实用性，而后对模型和数据也做了较为扼要的分析，进一步改进了模型的不妥之处。同时，在对问题进行较为全面评价的基础上又引入更为全面合理的假设，运用双线性函数模型对卫生部的措施进行了评价并给出建议，做好模型的完善与优化工作。 关键词：传染病模型,简单模型，SI，SIS,SIR，微分方程，Matlab。
一、问题重述 有一种传染病（如SARS、甲型H1N1）正在流行，现在希望建立适当的数学模型，利用已经掌握的一些数据资料对该传染病进行有效地研究，以期对其传播蔓延进行必要的控制，减少人民生命财产的损失。考虑如下的几个问题，建立适当的数学模型，并进行一定的比较分析和评价展望。 1、不考虑环境的限制，设单位时间内感染人数的增长率是常数，建立模型求t 时刻的感染人数。 2、假设单位时间内感染人数的增长率是感染人数的线性函数，最大感染时的增长率为零。建立模型求t时刻的感染人数。 3、假设总人口可分为传染病患者和易感染者，易感染者因与患病者接触而得病，而患病者会因治愈而减少且对该传染病具有很强的免疫功能，建立模型分析t 时刻患病者与易感染者的关系，并对传染情况（如流行趋势，是否最终消灭）进行预测。 二、问题分析 1、这是一个涉及传染病传播情况的实际问题，其中涉及传染病感染人数随时间的变化情况及一些初始资料，可通过建立相应的微分方程模型加以解决。 2、问题表述中已给出了各子问题的一些相应的假设。 3、在实际中，感染人数是离散变量，不具有连续可微性，不利于建立微分方程模型。但由于短时间内改变的是少数人口，这种变化与整体人口相比是微小的。 因此，为了利用数学工具建立微分方程模型，我们还需要一个基本假设：感染人数是时间的连续可微函数。
实验四 混合整数规划 一、问题重述 某开放式基金现有总额为15亿元的资金可用于投资，目前共有8个项目可供投资者选择，每个项目可重复投资。根据专家经验，对每个项目投资总额不能太高，应有上限。这些项目所需要的投资额已知，一般情况下投资一年后各项目所得利润也可估算出来，如表1所示。 请帮该公司解决以下问题： (1) 就表1提供的数据，应该投资哪些项目，使得第一年所得利润最高？ (2) 在具体投资这些项目时，实际还会出现项目之间互相影响的情况。公司咨询有关专家后，得到以下可靠信息：同时投资项目A 1，A 3，它们的年利润分别是1005万元，1018.5万元；同时投资项目A 4，A 5，它们的年利润分别是1045万元，1276万元；同时投资项目A 2，A 6，A 7，A 8，它们的年利润分别是1353万元，840万元，1610万元，1350万元，该基金应如何投资？ 其中M 为你的学号后3位乘以10。 (3) 如果考虑投资风险，则应如何投资，使收益尽可能大，而风险尽可能小。投资项目 总体风险可用投资项目中最大的一个风险来衡量。专家预测出各项目的风险率，如表2所示。 二、符号说明 i A :：投资额； i b ：i A 个项目所获得的年利润； i C ：第i A 个项目投资所获得的利润； 'i C ：第i A 个项目同时投资所获得的利润； i m ：投资i A 的上限； i y ：表示0—1变量； i p ：投资第i A 个项目的投资风险； 三、模型的建立 对于问题一 目标函数：8 1max i i i c x ==∑
s.t. 150000i i i i i i b x b x m ?≤? ??≤?∑ 对于问题二 设定0—1变量 131130...,1...,A A y A A ?? ?项目不同时投资项目同时投资 452450...,1...,A A y A A ???项目不同时投资 项目同时投资 2678326780...,,1...,,A A A A y A A A A ?? ?,项目不同时投资 ,项目同时投资 目标函数：'''' 11133111332445524455' '''322 66 77 88 322667788max ()(1)()()(1)()()(1)() y x c x c y x c x c y x c x c y x c x c y x c x c x c x c y x c x c x c x c =++-++++-++ ++++-+++ s.t. 1 13 131 24545 23267826783 1500001000i i i i i i b x k y x x x x y k y x x x x y k y x x x x x x x x y k b x m ?≤?? =??≤??≥?? ≤???≥? ?≤? ?≥?? ≤?∑ 对于问题三： 目标函数： max min max() i i i i i i c x b x p =∑ s.t. 150000i i i i i i b x b x m ?≤? ??≤?∑ 对于问题三模型的简化 固定投资风险，优化收益，设a 为固定的最大风险。 max i i i c x =∑
常见评价模型简介 评价类数学模型是全国数学建模竞赛中经常出现的一类模型，如200５年全国赛A题长江水质的评价问题，20０8年B题高校学费标准评价体系问题等。主要介绍三种比较常用的评价模型:层次分析模型，模糊综合评价模型,灰色关联分析模型，以期帮助大家了解不同背景下不同评价方法的应用。 层次分析模型 层次分析法(AＨP)是根据问题的性质和要求，将所包含的因素进行分类，一般按目标层、准则层和子准则层排列，构成一个层次结构，对同层次内诸因素采用两两比较的方法确定出相对于上一层目标的权重，这样层层分析下去, 直到最后一层,给出所有因素相对于总目标而言,按重要性程度的一个排序。其主要特征是,它合理地将定性与定量决策结合起来，按照思维、心理的规律把决策过程层次化、数量化。 运用层次分析法进行决策,可以分为以下四个步骤: 步骤1 建立层次分析结构模型 深入分析实际问题,将有关因素自上而下分层(目标—准则或指标—方案或对象)，上层受下层影响,而层内各因素基本上相对独立。 步骤2构造成对比较阵 对于同一层次的各元素关于上一层次中某一准则的重要性进行两两比较,借助1～9尺度，构造比较矩阵； 步骤3计算权向量并作一致性检验 由判断矩阵计算被比较元素对于该准则的相对权重，并进行一致性检验，若通过,则最大特征根对应的特征向量做为权向量。 步骤４计算组合权向量（作组合一致性检验) 组合权向量可作为决策的定量依据 通过一个具体的例子介绍层次分析模型的应用。 例（选择旅游地决策问题)如何在桂林、黄山、北戴河3个目的地中按照景色、费用、居住条件、饮食、旅途条件等因素进行选择。 步骤1 建立系统的递阶层次结构 将决策问题分为3个层次:目标层O,准则层Ｃ，方案层P；每层有若干
1 预测模块：灰色预测、时间序列预测、神经网络预测、曲线拟合（线性回归）； 2 归类判别：欧氏距离判别、fisher判别等； 3 图论：最短路径求法； 4 最优化：列方程组用lindo 或lingo软件解； 5 其他方法：层次分析法马尔可夫链主成分析法等； 6 用到软件：matlab lindo （lingo）excel ； 7 比赛前写几篇数模论文。 这是每年参赛的赛提以及获奖作品的解法，你自己估量着吧…… 赛题解法 93A非线性交调的频率设计拟合、规划 93B足球队排名图论、层次分析、整数规划 94A逢山开路图论、插值、动态规划 94B锁具装箱问题图论、组合数学 95A飞行管理问题非线性规划、线性规划 95B天车与冶炼炉的作业调度动态规划、排队论、图论 96A最优捕鱼策略微分方程、优化 96B节水洗衣机非线性规划 97A零件的参数设计非线性规划 97B截断切割的最优排列随机模拟、图论 98A一类投资组合问题多目标优化、非线性规划 98B灾情巡视的最佳路线图论、组合优化 99A自动化车床管理随机优化、计算机模拟 99B钻井布局0-1规划、图论 00A DNA序列分类模式识别、Fisher判别、人工神经网络 00B钢管订购和运输组合优化、运输问题 01A血管三维重建曲线拟合、曲面重建 01B 工交车调度问题多目标规划 02A车灯线光源的优化非线性规划 02B彩票问题单目标决策 03A SARS的传播微分方程、差分方程 03B 露天矿生产的车辆安排整数规划、运输问题 04A奥运会临时超市网点设计统计分析、数据处理、优化 04B电力市场的输电阻塞管理数据拟合、优化 05A长江水质的评价和预测预测评价、数据处理 05B DVD在线租赁随机规划、整数规划
《数学建模》题库 为了培养想象力、洞察力和判断力，考察对象时除了从正面分析，还常常需要从侧面或反面思考，尽可能迅速的回答1-5题。 1. 某人早上8：00从山下旅馆出发，沿一条路径上山，下午5：00到达山顶并留 宿。次日早8：00沿同一路径下山，下午5：00回到旅馆。则此人必在两天中同一时刻经过路径中的同一地点，为什么？ 2. 37支球队进行冠军争夺赛，每轮比赛中出场的每两支球队的胜者以及轮空者 进入下一轮，直到比赛结束，问共需进行多少场比赛，共需进行多少轮比赛？ 3. 甲乙两站之间有电车相通，每隔十分钟甲乙两站相互发一趟车，但发车时刻 不一定相同。甲乙之间有一中间站丙，某人每天在随机时刻到达兵站，并搭乘最先经过丙站的那趟车，结果发现100天中约有90天到达甲站。问开往甲乙两站的电车经过丙站的时刻表是如何安排的？ 4. 某人家住T市在他乡工作，每天下班后乘火车于6：00抵达T市车站，他的妻 子驾车准时到车站接他回家。一日他提前下班，搭乘早一班火车于5：30抵达T市车站，随即步行回家，他的妻子像往常一样驾车前来，在半路上遇到他，即接他回家，此时发现比往常提前了十分钟。问他步行了多长时间？ 5. 一男孩和一女孩分别在离家2千米和1千米且方向相反的两所学校上学，每天 同时放学后分别以4千米/小时和2千米/小时的速度步行回家。一小狗以6千米/小时的速度由男孩处奔向女孩，又从女孩处奔向男孩，如此往返只至回到家中，问小狗奔波了多少路程？ 6. 任意拿出黑白两种颜色的棋子共8个，排成如图一所示的一个圆圈，然后在两 颗颜色相同棋子中间放一颗黑棋子，在两颗颜色不同的棋子中间放一颗白棋子，放完后撤掉原来所放的棋子，再重复以上的过程，这样放下一圈后就拿走前次的一圈棋子，问这样重复下去棋子的颜色会发生怎样的变化？ 图一
四类基本模型 1 优化模型 1.1 数学规划模型 线性规划、整数线性规划、非线性规划、多目标规划、动态规划。 1.2 微分方程组模型 阻滞增长模型、SARS 传播模型。 1.3 图论与网络优化问题 最短路径问题、网络最大流问题、最小费用最大流问题、最小生成树问题(MST)、旅行商问题(TSP)、图的着色问题。 1.4 概率模型 决策模型、随机存储模型、随机人口模型、报童问题、Markov 链模型。 1.5 组合优化经典问题 ● 多维背包问题(MKP) 背包问题：n 个物品，对物品i ，体积为i w ，背包容量为W 。如何将尽可能多的物品装入背包。 多维背包问题：n 个物品，对物品i ，价值为i p ，体积为i w ，背包容量为W 。如何选取物品装入背包，是背包中物品的总价值最大。 多维背包问题在实际中的应用有：资源分配、货物装载和存储分配等问题。该问题属于NP 难问题。 ● 二维指派问题(QAP) 工作指派问题：n 个工作可以由n 个工人分别完成。工人i 完成工作j 的时间为ij d 。如何安排使总工作时间最小。 二维指派问题（常以机器布局问题为例）：n 台机器要布置在n 个地方，机器i 与k 之间的物流量为ik f ，位置j 与l 之间的距离为jl d ，如何布置使费用最小。 二维指派问题在实际中的应用有：校园建筑物的布局、医院科室的安排、成组技术中加工中心的组成问题等。 ● 旅行商问题(TSP) 旅行商问题：有n 个城市，城市i 与j 之间的距离为ij d ，找一条经过n 个城市的巡回（每个城市经过且只经过一次，最后回到出发点），使得总路程最小。 ● 车辆路径问题(VRP) 车辆路径问题（也称车辆计划）：已知n 个客户的位置坐标和货物需求，在