数模优化问题

第8章优化模型优化模型泛函优化模型图论优化模型经典等周问题抢渡长江函数优化模型函数最优化模型的标准形式LP,ILP,BILP,NLP,INLP,QP,IQP线性规划模型(LP)的标准形式MATLAB命令：linprog,bintprog泛函优化模型Dido传奇公元前814年，腓尼基人泰尔（Tyer）王国（位于现今黎巴嫩南部西南海岸）的Dido公主因其兄庇格玛里翁（Pygmalion）在国王死后，排斥公主而独揽大权。为免遭迫害，Dido带着财宝与仆人飘洋过海，在突尼斯湾登陆。她向柏柏人部落首领马西塔尼求借一张牛皮之地栖身，得到应允；于是她便把一张牛皮切成一根根细条，然后把细牛皮连在一起，在紧靠海边的山丘上围起一块约3.15平方公里地皮，建起了迦太基城（Carthage）。迦太基假想图200B.C.迦太基遗址.“牛皮圈地”之台湾版天启四年八月，荷人请和。许之，与互市，乃退澎湖，而东入台湾。先是，海澄人颜思齐居台湾，郑芝龙附之。既去，而荷人来，借地于土番，不可，绐之曰，愿得地如牛皮，多金不惜。许之，乃剪皮为缕，周围里许，筑热兰遮城以居，驻兵二千八百人，附近土番多服焉。

------清·龚柴

《台湾小志》热兰遮城(Zeelandia)

1625年简图1622年，荷属东印度公司占领了澎湖，以之作为东亚贸易的转口基地。1623年，荷兰人在“一鲲鯓”建立一座简单的砦城，这就是安平古堡的前身。1624年，在与中国明朝的军队激战了八个月以后，荷兰人和中国官方达成协议，同意把设置于澎湖的要塞和炮台毁坏，而于1624年转移至台湾岛，中国则不干涉荷兰对台湾的占领。荷兰人MartinusSonck占台以后，在原来的砦城旧城址上，重新兴建规模宏大的城堡“奥伦治城”（Orange），1627年以荷兰省名泽兰省（或译热兰省）改建命名为“热兰遮城”（Zeelandia）。1662年，郑成功攻下“热兰遮城”，顺利将荷兰人驱逐出台湾，建立了台湾历史上第一个汉人政权。郑氏同时也将该城改为“安平城”，这就是现今“安平古堡”这个名称的由来。-------------安平古堡里的郑成功像国家一级古迹-----安平古堡什么是变分法？约翰·伯努利（JohannBernoulli，1667－1748）

“最速降线”问题（TheBrachistochroneProblem）欧拉（EulerLonhard，1707～1783）和拉格朗日(Lagrange,JosephLouis，1736-1813)确立了变分学现实中很多现象可以表达为泛函极值问题，我们称之为变分问题。求解方法通常有两种：古典变分法和最优控制论。变分法基本知识定义泛函设S为一函数集合，若对于每个函数都有一个实数J

与之对应，则称J

是定义在S上的泛函，记为，S

称为J的容许集。泛函最简形式

泛函极值

则称泛函J在有极小值（极大值）。函数变分

泛函增量

如果线性项＋高次项线性项就称为泛函J的变分

泛函变分的一个重要形式是可以表示为对参数的导数：极值与变分

若泛函J在取得极值，则变分法的基本引理

泛函极值的必要条件容许函数集S取为满足端点条件的二阶可微函数集合。则泛函J在取极值的必要条件为满足欧拉方程欧拉方程的解称为泛函J的驻留函数，容许函数集S内的驻留函数通常就是使泛函取极值的函数。欧拉方程推导

对右端第二项做分部积分，

并利用利用泛函极值的变分表示，得根据变分法的基本引理以及条件欧拉方程可以推广到含多个未知函数

（可视为向量值函数）的情况，如假设则其欧拉方程组为泛函极值与函数极值的比较泛函函数极值点自变量增量因变量增量因变量增量的线性主部取极值的必要条件无条件极值的必要条件辅助函数条件极值的必要条件驻留函数驻点泛函变分函数全微分极值函数极值点等周问题（特殊条件极值问题）目标泛函约束条件（等周条件）等周问题解法

（条件极值问题转化为无条件极值问题）设x(t)是等周问题（F,G）的极值函数，但不是约束条件泛函的驻留函数，则必存在常数，使得x(t)是Lagrange函数对应的辅助泛函定理8.3的驻留函数。即经典等周问题目标泛函约束条件（等周条件）容许函数集边界条件作Lagrange函数对应的欧拉方程为

对应的欧拉方程为

泛函极（大）值为驻留函数对应曲线为圆极值函数对应曲线用变分法证明偏角引理设游泳者的速度而流速，其中

u为常数,=(y)为游泳偏角。于是游泳者的路线

(x(t),y(t))满足求最优路线

(x(t),y(t))等价于求最优偏角策略，可以化为等周问题最优偏角的求法(变分法)目标泛函约束条件

等周条件容许函数集作Lagrange函数对应的欧拉方程为

即驻留函数偏角引理若u为常数,v

是y的函数，则最优路径的偏角取：若u,v

为常数，则最优路径的偏角始终不变！最优路径就是连接起点与终点的直线段！水流速分布函数为n段常数、光滑函数间隔的模型8.2最短路问题1、图论的基本概念2、最短路问题及其算法3、最短路的应用4、建模案例：调度问题5、实验作业2、会用LINGO、Matlab软件求优化问题1、了解最短路问题与调度的算法及其应用图论的基本概念一、图的概念1、图的定义2、顶点的度

3、子图二、图的矩阵表示1、关联矩阵2、邻接矩阵返回定义有序二元组G=(V,E)称为一个图.图的定义V的元素为G的顶点，V称为顶点集。如果G的边有方向，则称为图的有向边，否则称为无向边，每条边都是有向边的图称为有向图，每条边都是无向边的图称为无向图，既有有向边又有无向边的图称为混合图。将图的每一条边都赋以一个数字，称为该边的权，每个边都赋权的图称为赋权图。1.端点相同的边称为环．2.若一对顶点之间有两条以上的边联结，则这些边称为重边．3.有边联结的两个顶点称为相邻的顶点，有一个公共端点的边称为相邻的边．4.边和它的端点称为互相关联的．5.既没有环也没有重边的图，称为简单图．图的有关概念子图顶点的度(1)在图中，顶点v关联的边的数目(环算两次)称为v的度，记为d(v)。(2)在有向图中，以顶点v为起点的边的数目称为v的出度，记为d+(v),

以顶点v为终点的边的数目称为v的入度，记为d-(v)。邻接矩阵注：假设图为简单图返回无向赋权图的邻接矩阵可类似定义．关联矩阵注：假设图为简单图返回最短路问题及其算法一、基本概念二、固定起点的最短路返回基本概念返回定义２1.任意两点均有路径的图称为连通图．2.起点与终点重合的路径称为圈．3.连通而无圈的图称为树．

4.若G的生成子图T是树，则T称为G的生成树。定义３设P(u,v)是赋权图G中从u到v的路径，则路径上全体边的权之和

称为路径P的权．最短路问题（SRP:ShortestRouteProblem）

在赋权图G中，从顶点u到顶点v的具有最小权的路，称为u到v的最短路．最小生成树问题(MSTP:MinimumSpanningTreeProblem)

在赋权图G中，求权最小的生成树。计划评审技术/关键路径方法（PERT/CPM:ProgramEvaluationand

ReviewTechnique/CriticalPathMethod

）

在无回路有向赋权图G中，从顶点u到顶点v的具有最大权的路，称为u到v的

关键路径．计划评审方法和关键路径法PERT/CPM如下图，某个项目由4个事件（边）完成，每个事件需要一定时间（边的权值）完成，并且每个事件都需要在一定的状态（顶点）下才能开始，即要完成所有先行事件（所有进入该顶点的边）。求完成这个项目的最短时间。无回路有向赋权图中的最长路径：关键路径。142312137100固定起点的最短路（最短路的无后效性）最短路的任一段也是最短路．求指定顶点到其余顶点的最短路可采用树生长的过程来实现．Dijkstra算法（计算从S到T的最短路）（1）从点S出发，因LSS=0,将此值标注在S旁的小方框内，表示S点已标号；（2）从S点出发找出与S相邻的点中距离最小的一个，设为r，将Lsr=Lss+dsr的值标注在r的小方框内，表明r也已标号；（3）从已标号的的点出发，找出与这些点相邻的所有未标号点p，若有Lsp=min｛Lss+dsp;Lsr+drp｝,则对p点标号，并将Lsp的值标注在p点旁的小方框内；（4）重复第3步，一直到T点得到标