数学建模与数学实验：CH8 优化模型

1、第8章,优化模型,优化模型,泛函优化模型,图论优化模型,经典等周问题,抢渡长江,函数优化模型,函数最优化模型的标准形式,LP,ILP,BILP,NLP,INLP,QP,IQP,线性规划模型(LP)的标准形式,MATLAB命令：linprog, bintprog,泛函优化模型,Dido传奇,公元前814年，腓尼基人泰尔（Tyer）王国（位于现今黎巴嫩南部西南海岸）的Dido公主因其兄庇格玛里翁（Pygmalion）在国王死后，排斥公主而独揽大权。为免遭迫害，Dido带着财宝与仆人飘洋过海，在突尼斯湾登陆。她向柏柏人部落首领马西塔尼求借一张牛皮之地栖身，得到应允；于是她便把一张牛皮切成一根根细条，

2、然后把细牛皮连在一起，在紧靠海边的山丘上围起一块约3.15平方公里地皮，建起了迦太基城（Carthage）,迦太基假想图200B.C,迦太基遗址,牛皮圈地”之台湾版,天启四年八月，荷人请和。许 之，与互市，乃退澎湖，而东入台湾。 先是，海澄人颜思齐居台湾，郑芝龙附 之。既去，而荷人来，借地于土番，不 可，绐之曰，愿得地如牛皮，多金不 惜。许之，乃剪皮为缕，周围里许，筑 热兰遮城以居，驻兵二千八百人，附近 土番多服焉。 -清龚柴 台湾小志,热兰遮城(Zeelandia) 1625年简图,1622年，荷属东印度公司占领了澎湖，以之作为东亚贸易的转口基地。1623年，荷兰人在“一鲲鯓”建立一座简单的

3、砦城，这就是安平古堡的前身。1624年，在与中国明朝的军队激战了八个月以后，荷兰人和中国官方达成协议，同意把设置于澎湖的要塞和炮台毁坏，而于1624年转移至台湾岛，中国则不干涉荷兰对台湾的占领。荷兰人Martinus Sonck占台以后，在原来的砦城旧城址上，重新兴建规模宏大的城堡“奥伦治城”（Orange），1627年以荷兰省名泽兰省（或译热兰省）改建命名为“热兰遮城”（Zeelandia）。 1662年，郑成功攻下“热兰遮城”，顺利将荷兰人驱逐出台湾，建立了台湾历史上第一个汉人政权。郑氏同时也将该城改为“安平城”，这就是现今“安平古堡”这个名称的由来。 - http:/zh.wikiped

4、,安平古堡里的郑成功像,国家一级古迹 -安平古堡,什么是变分法,约翰伯努利（Johann Bernoulli，16671748）“最速降线”问题（The Brachistochrone Problem,欧拉（Euler Lonhard，17071783）和拉格朗日(Lagrange, Joseph Louis，1736-1813)确立了变分学,现实中很多现象可以表达为泛函极值问题，我们称之为变分问题。求解方法通常有两种：古典变分法和最优控制论,变分法基本知识,定义,泛函,设S 为一函数集合，若对于每个函数,都有一个实数 J 与之对应,则称 J 是定义在 S 上的泛函，记 为 ，S

5、称为 J 的容许集,泛函最简形式,泛函极值,则称泛函 J 在 有极小值（极大值,函数变分,泛函增量,如果,线性项高次项,线性项就称为泛函 J 的变分,极值与变分,若泛函 J 在 取得极值，则,变分法的基本引理,泛函极值的必要条件,容许函数集S取为满足端点条件的二阶可微函数集合,则泛函 J 在 取极值的必要条件为 满足欧拉方程,欧拉方程的解称为泛函J的驻留函数，容许函数集S内的驻留函数通常就是使泛函取极值的函数,欧拉方程推导,对右端第二项做分部积分，并利用,利用泛函极值的变分表示，得,根据变分法的基本引理以及条件,欧拉方程可以推广到含多个未知函数（可视为向量值函数）的情况，如假设,则其欧拉方程组

6、为,泛函极值与函数极值的比较,驻留函数,驻点,泛函变分,函数全微分,极值函数,极值点,等周问题（特殊条件极值问题,目标泛函,约束条件（等周条件,等周问题解法（条件极值问题转化为无条件极值问题,设x(t)是等周问题（F,G）的极值函数，但不是约束条件泛函的驻留函数，则必存在常数 ，使得x(t)是Lagrange函数 对应的辅助泛函,定理8.3,的驻留函数,即,经典等周问题,目标泛函,约束条件（等周条件,容许函数集,边界条件,作Lagrange函数,对应的欧拉方程为,对应的欧拉方程为,泛函极（大）值为,驻留函数对应曲线为圆,极值函数对应曲线,用变分法证明偏角引理,设游泳者的速度,而流速,其中 u

7、为常数, = (y)为游泳偏角,于是游泳者的路线 (x(t), y(t) 满足,求最优路线 (x(t), y(t) 等价于求最优偏角策略， 可以化为等周问题,最优偏角的求法(变分法,目标泛函,约束条件等周条件,容许函数集,作Lagrange函数,对应的欧拉方程为,即,驻留函数,偏角引理,若 u 为常数, v 是 y 的函数，则最优路径的偏角取,若 u,v 为常数，则最优路径的偏角始终不变,最优路径就是连接起点与终点的直线段,水流速分布函数为n段常数、光滑函数间隔的模型,8.2最短路问题,1、图 论 的 基 本 概 念,2、最 短 路 问 题 及 其 算 法,3、最 短 路 的 应 用,4、建模

8、案例：调度问题,5、实验作业,2、会用LINGO、Matlab软件求优化问题,1、了解最短路问题与调度的算法及其应用,图 论 的 基 本 概 念,一、 图 的 概 念,1、图的定义,2、顶点的度,3、子图,二、 图 的 矩 阵 表 示,1、 关联矩阵,2、 邻接矩阵,返回,定义,有序二元组G=(V,E )称为一个图,图的定义,V的元素为G的顶点，V称为顶点集,如果G的边有方向，则称为图的有向边，否则称为无向边，每条边都是有向边的图称为有向图，每条边都是无向边的图称为无向图，既有有向边又有无向边的图称为混合图,将图的每一条边都赋以一个数字，称为该边的权，每个边都赋权的图称为赋权图,1.端点相同的

9、边称为环,2.若一对顶点之间有两条以上的边联结，则这些边称为重边,3.有边联结的两个顶点称为相邻的顶点，有一个公共端点的边称为相邻的边,4.边和它的端点称为互相关联的,5.既没有环也没有重边的图，称为简单图,图的有关概念,子图,顶点的度,1)在图中，顶点v关联的边的数目(环算两次)称为v的度，记为d(v,2)在有向图中，以顶点v为起点的边的数目称为v的出度，记为d+(v), 以顶点v为终点的边的数目称为v的入度，记为d-(v,邻接矩阵,注：假设图为简单图,返回,无向赋权图的邻接矩阵可类似定义,关联矩阵,注：假设图为简单图,返回,最 短 路 问 题 及 其 算 法,一、 基 本 概 念,二、固

10、定 起 点 的 最 短 路,返回,基 本 概 念,返回,定义1.任意两点均有路径的图称为连通图 2.起点与终点重合的路径称为圈 3.连通而无圈的图称为树 4.若G的生成子图T是树，则T称为G的生成树,定义 设P(u,v)是赋权图G中从u到v的路径，则路径上全体边的权之和 称为路径P的权,最短路问题（SRP: Shortest Route Problem） 在赋权图G中，从顶点u到顶点v的具有最小权的路，称为u到v的最短路,最小生成树问题(MSTP: Minimum Spanning Tree Problem) 在赋权图G中，求权最小的生成树,计划评审技术/关键路径方法（PERT/CPM: Pr

11、ogram Evaluation and Review Technique/Critical Path Method ） 在无回路有向赋权图G中，从顶点u到顶点v的具有最大权的路，称为u到v的 关键路径,计划评审方法和关键路径法PERT/CPM,如下图，某个项目由4个事件（边）完成，每个事件需要一定时间（边的权值）完成，并且每个事件都需要在一定的状态（顶点）下才能开始，即要完成所有先行事件（所有进入该顶点的边）。求完成这个项目的最短时间。 无回路有向赋权图中的最长路径：关键路径,固 定 起 点 的 最 短 路,最短路的无后效性）最短路的任意一段也是最短路,求指定顶点到其余顶点的最短路可采用树生

12、长的过程来实现,Dijkstra算法（计算从S到T的最短路,1）从点S出发，因LSS=0 ,将此值标注在S旁的小方框内，表示S点已标号； （2）从S点出发找出与S相邻的点中距离最小的一个，设为r，将 Lsr=Lss+dsr的值标注在r的小方框内，表明r也已标号； （3）从已标号的的点出发，找出与这些点相邻的所有未标号点p，若有Lsp=minLss+dsp;Lsr+drp,则对p点标号，并将Lsp的值标注在p点旁的小方框内； （4）重复第3步，一直到T点得到标号为止,Dijkstra算法（标号法）演示,Dijkstra算法（标号法）演示,Dijkstra算法（标号法）演示,Dijkstra算法（

13、标号法）演示,Dijkstra算法（标号法）演示,最短路问题(SRP)的Lingo/Matlab解决方案转化为0-1整数规划(BILP,引入0-1决策变量xij： 若边eij在最短路上，则取值1，否则取值0,为邻接矩阵,问题：假设图有n个顶点，求顶点1到顶点n的最短路,解法,Kruskal算法,Kruskal算法时间复杂度与顶点数无关，因此适用于边稀疏的图,最小生成树的实现,Prim算法,Prim算法时间复杂度与边数无关，因此适用于边稠密的图,欲建设一个连接5个城市的光纤通信网络。各城市间线路的造 价如图所示，求一个使总造价最少的线路建设方案,例 通信网络的建设问题,解：采用Kruskal算法

14、,解：采用Prim算法,欲建设一个连接6个城市的光纤通信网络。各城市间线路的造 价如图所示，求一个使总造价最少的线路建设方案,例8.4通信网络的建设问题,解：采用Prim算法,54,管梅谷（）。我国著名数学家，曾任山东师范大学校长。中国运筹学会第一、二届常务理事，第六届全国政协委员。从事运筹学及其应用的研究，对最短投递路线问题的研究取得成果 ，冠名为中国邮路问题，该问题被列入经典图论教材和著作,补充材料：管梅谷的破圈法,在克鲁斯克尔算法基础上，我国著名数学家管梅谷教授于1975年提出了最小生成树的破圈法,破圈法求最小生成树的求解过程是：从赋权图G的任意圈开始，去掉该圈中权值最大的一条边，称为破

15、圈。不断破圈，直到G中没有圈为止，最后剩下的G的子图为G的最小生成树,55,解： 过程如下,例用破圈法求下图G的最小生成树,1）根结点至少有一个子节点,2）除根外,每个点有且仅有 一个父节点,最小生成树问题(MSTP)的Lingo/Matlab解决方案转化为0-1整数规划(BILP,引入0-1决策变量xij： 若边eij在最小生成树上，则取值1，否则取值0,问题：假设图有n个顶点，设顶点1为生成树的根，求最小生成树,解法,设1和n分别是最初和最终事件; Si是事件i的开始时间, tij是事件(i,j)的计划（正常）时间,问题：求最后一个事件的最早开始时间,PERT/CPM的Lingo/Matl

16、ab解决方案 转化为线性规划(LP,解法,关键路径也可以看成最长路，可用求最短路径 的方法来求解,为了得到每个作业的最早开工时间和最迟开工时间，可更改模型如下LP,当rij0时，说明对应的事件的开始时间最多可以推迟rij，从而可以得到每个事件i的最迟开工时间,Crashing Analysis的Lingo/Matlab解决方案 转化为线性规划(LP,问题1：求符合规定完成时间F而费用最小的可行计划,Crashing Analysis的Lingo/Matlab解决方案 转化为线性规划(LP,问题2：求费用最小的提前或延期计划,例8.5 工程调度问题,单位（千元,改为30,利用LINGO求解可得全局最优解87000，工程总工期最多可以缩减到54周,欲建设一个连接6栋楼的光纤网络。楼宇间线