旅游景点最优化模型(含代码)
张家界景区空中缆车模型
摘要
本文将张家界景区各景点铺设索道路线抽象为图论最短路模型，采用最小生成树进行表述。根据张家界景区管理部门的需求，利用Floyd算法——聚类分析法进行模型的建立和求解，得到问题的最优解。
第一问，本文根据Google地图定位出张家界景区51个旅游景点的经、纬度；通过计算机处理，以国家森林公园为原点，东、北为X,Y轴，建立张家界景区直角坐标系（表1.1、图1.1）。
第二问，假设在每个景点上都建造缆车站，采用图论中的最小生成树法，得出铺设索道的最优路径（图2.1.1）和最小费用S=454655.0万元。观察到许多景点的距离比较近，可以用一个缆车站来接送这些景点的游客，这个站台就是这些景点的聚点，即可优化传统的聚类分析法，使其满足所给定的约束条件（旅客所能容忍步行最小距离为500m），在这些聚点建造缆车站，采用最小生成树法，得出铺设索道的最优路径（图2.2.2）和最小费用S=445050.6万元。
针对上述Floyd算法——聚类分析法模型的优缺点，本文给出了具体的改进，使得更符合实际情况以及节省最多的钱。
关键词Floyd算法聚类分析法Google地图
一、问题重述
随着人们的生活不断提高，旅游已成为提高人们生活质量的重要活动。但时间往往是限制人们旅游一个难题，为了满足旅游者的需要，张家界景区打算造高空浏览缆车，让人们可以在最短的时间内游览更多的景点，现定游览车的起点在张家界国家森林公园，造价为每米10万元，请解决以下问题：
1、针对张家界景点地图，自建坐标系，标出各个景点坐标
2、设计最佳的缆车运行路线
二、问题分析
现在的旅游业日益发达，但因时间紧迫，很多人希望找到最佳旅游线路。而旅游线路遇到的最直接的问题是：景点的具体位置。比如张家界景区，里面的景点多达五十个，怎样才能准确找到自己要去景点的位置，已经成为了亟待解决的关键问题。为此，张家界景区决定铺设空中缆车索道，以解决广大游客的时间问题。
1、问题一的分析：
对于张家界景区里景点的做标问题，首先定位出各景点在地图上的经、纬度；然后运用计算机技术对经、纬度进行处理，再以张家界国家森林公园为新建坐标系原点，以东、北方向为新建坐标系的X、Y轴，新建张家界平面坐标系；经计算机处理，最后给出各景点在新建坐标系中的具体坐标。
2、问题二的分析：
对于问题二，本文先考虑张家界各景点建空中缆车站的理想化情况，即在张家界景区的51个景点都建一个可供游客来回坐的缆车旅游站台，考虑到雷电，狂风等地理环境因素，使得某些旅游景点是不能能够只考虑空中缆车距离最小等等，建立理想模型2.1；但实际上需要考虑费用、路径、空中缆车站的最佳位置等等各方面因素，在理想状态的基础上，考虑运用最小生成树法及聚类分析等方法，建立实际模型2.2；再对本文建立的模型二进行检验分析。
三、模型假设
1、假设所有景区的海拔是一样的，不考虑景点间的高度差。
2、假设总缆车站台的费用相对于总缆车索道的费用很低，可以不计入张家界建造空中缆车系统的总费用。
3、假设Google地图所查询的经纬度是可信的。
4、假设景区地理环境对缆车索道不产生影响，即所有景区间都能够建立笔直的缆车索道。
5、假设旅客所能容忍步行的距离为500m。
四、符号约定
G：连通网络
T：连通网络中的一个支撑树
E：连通网络中的点
W：支撑树的权重
d：地图上的最优路径
D：实际距离
S：最小费用
五、模型建立于求解
1、问题一的模型建立与求解：
旅游已成为现今人们减轻压力的最直接有效的方法，旅游景点线路的选择,是旅游行业的一项基础性工作，也是旅游爱好者比较关心的问题，那么如何在最短的时间内游览到最多的景点呢？
本文以张家界景区为例，建立相应的数学模型，以解决上面提到的问题。根据在网上查找的资料，可以得到张家界景区各景点的经、纬度（附录表1）。
运用计算机知识，将附录表1的数据进行处理，可以得到以张家界国家森林公园为原点的平面坐标系（表1.1）。
表1.1 张家界各景点以国家森林公园为原点的坐标系表
序号旅游点X轴Y轴序号旅游点X轴Y轴
1 张家界九天洞-18 115 27 张家界天书宝匣-9 27
2 张家界天子山镇
3 11
4 28 张家界南天门-8 28
3 张家界将军岩11 95 29 张家界劈山救母-2 26
4 张家界天子峰21 86 30 张家界定海神针-1 28
5 张家界龙泉飞瀑-9 75 31 张家界天桥12 28
6 张家界鸳鸯瀑布21 68 32 张家界花果山 5 25
7 张家界空中田园27 64 33 张家界护鞭神鹰 3 22
8 张家界观光电梯24 55 34 张家界金鞭岩 2 21
9 张家界天波府-19 63 35 张家界闺门岩-2 16
10 张家界天悬白练0 57 36 张家界夫妻岩-9 12
11 张家界空中走廊-16 50 37 张家界国家森林公园0 0
12 张家界天下第一桥-1 50 38 张家界张良墓29 47
13 张家界迷魂台-2 47 39 张家界水绕四门35 45
14 张家界五女拜师-2 44 40 张家界神兵聚会31 53
15 张家界后花园9 45 41 张家界老屋场31 62
16 张家界重欢树16 41 42 张家界采药老人42 68
17 张家界跳鱼潭18 40 43 张家界仙人桥30 77
18 张家界紫草潭9 40 44 张家界雄狮回首56 71
19 张家界天桥遗墩-11 40 45 张家界天台1 46 89
20 张家界黑枞脑-9 38 46 张家界天台2 53 83
21 张家界千里相会11 39 47 张家界仙女献花64 88
22 张家界九重仙阁-24 28 48 张家界御笔峰55 90
23 张家界黄狮寨-5 34 49 张家界西海50 86
24 张家界鸳鸯泉-16 26 50 张家界贺龙公园56 92
25 张家界双龟探溪57 36 51 张家界鹰窝寨109 22
26 张家界南天一柱-6 29
为了更加清楚明白的表示各景点的具体位置，本文运用Matlab技术对表1.1的数据进行处理，可以得到图1.1。
图1.1 张家界各景点以国家森林公园为原点的坐标系图
图 1.1即为问题一所需求得的张家界景区内各景点的位置所构成的直角坐标系图形。
2、问题二的模型建立与求解： 2.1、模型一
模型2.1是一个理想化的模型，即每个景点都有一个空中缆车站。则根据模型2.1的要求，可以将张家界景区内的51个景点都有空中缆车站问题，转化为求51个景点的最小生成树问题，也就是在一个连通图的赋权网络中，寻找最小权数的支撑树。
现给定网络(),,G V E W =,设()',T V E =为G 的一个支撑树，令
()()e E
W T W e ∈=∑表示T 的权，则G 中权最小的支撑树即为G 的最小生成树。
在模型2.1中()(){}*min W T W T =,表示51个景点之间的最短距离。因为单位长度的建造费用是确定的，所以要求空中缆车各景点的总费用最小，也就是求各景点距离最小的最小生成树，即连通所有景点的权最小的支撑树。根据以上信息，考虑运用Floyd 算法，并可用Matlab 程序将其实现。
Floyd 算法基本思想：
令m D 表示一个N ×N 矩阵，它的( i, j) 元素是m ij d 。如果已知图中每条线
段的长度，则可以确定矩阵0D ，最终希望得到最短路长度的矩阵N D 。Floyd 算法从0D 开始，由0D 计算1D ，然后Floyd 算法再由1D 计算2D 。将这个过程重复进行下去，直至由1N D -求得N D 为止。
计算思路如下，设已知：
1)、顶点i 到顶点m 的最短路，其中只容许前m - 1个顶点即1， 2， ?， m - 1
作为中间顶点。
2)、从顶点m 到顶点j 的最短路，其中只容许前m - 1个顶点即1， 2， ?， m - 1
作为中间顶点。
3)、从顶点i 到顶点j 的最短路，其中只容许前m - 1个顶点即1，2， ?，m - 1
作为中间顶点。
因为不存在有负长度的回路，所以 4) 项与 5) 项中给出的2条路中较短的1条一定是从i 到j 的最短路，其中只容许前m 个顶点即顶点1，2， ?， m 作为中间顶点。
4)、1) 项和 2) 项2条路的并。 5)、3) 项的路。
因此，{}m 111
ij d min ,m m m im mj ij d d d ---=+
从以上方程可以看出，只需要1m D -矩阵的各个元素，就可以计算出矩阵m D 的各个元素；而且，无需参看基本图就可以进行计算。现在，求图中每一对顶点之间最短路的Floyd 算法。 Floyd 算法基本步骤：
第1步：将图中各顶点编为1，2，?，N 。 确定矩阵0D ，其中( i, j) 元素等于
从顶点i 到顶点j 最短线段的长度(如果有最短线段的话)。如果没有这
样的线段，则令0ij d =∞，对于i ，令00ii d =，
第2步：对m = 1， 2， ?， N ，依次由1m D -的元素确定m D 的元素,应用下列递归
公式{}m 111
ij d min ,m m m m mj ij d d d ---=+
每当确定一个元素时，就记下它所表示的路。在算法终止时，矩阵n D 的元素( i, j) 元素就表示从顶点i 到顶点j 最短路的长度。
注意：对所有的i 和m ，m
ii d 0=，矩阵12n D , D , ..., D 的对角线元素都无需计算，而且，对所有的i =1，2，?，n ，1im m m im d d -=和1mi m m
mi
d d -=。这是因为不存在有负长度的回路，所以在顶点m 处起始的任一最短路中，顶点m 不是中间点的缘故。因此，在矩阵m D 的计算中，第m 行和m 列都不需计算。在每一个矩阵m D 中，不在对角线上，也不在第 m 行和第 m 列的(N – 1) (N - 2)个元素需要计算。 由以上信息，加上Matlab 技术，对模型1.1的51个景点坐标进行处理。 第一步：由51个景点的坐标，用Matlab 实现任意两点之间的的距离。（程序见附
录程序2.1.1）
第二步：根据51个景点之间的权重，运用Floyd算法找到缆车索道建构最优路径（程序见附录程序2.1.2），其距离d=454.6550mm，实际距离D=45465.50m 所需最小费用为S=445050.6万元。
图2.1.1 50个景点的最小生成树
这一步，将51个空中缆车站坐标进行了处理，得到图2.1.1的权最小的支撑树；因而我们可以得到铺设缆车索道的路线图，即
第三步:画出其路线图：
图2.1.2 50个景点最小生成树的大致走向
根据图2.1.2做出其最优路线表，以便游客查找最佳旅游路线及铺设索道的最优路线。
起点国家森林公园 37
37—36—35—34—3—32—31
37—36—35—34—33—29—30 37—36—35—34—33—29—26—28—27—24—22 37—36—35—34—33—29—26—23—20—19—11—9—5 37—36—35—34—33—29—26—23—20—14—13—12—10 37—36—35—34—33—29—26—23—20—14—15—18—21—16—17—38—40—8 37—36—35—34—33—29—26—23—20—14—15—18—21—16—17—38—39—25—51 37—36—35—34—33—29—26—23—20—14—15—18—21—16—17—38—40—41—7—6—43—4—3—2—1
37—36—35—34—33—29—26—23—20—14—15—18—21—16—17—38—40—41—42—44—46—49—45 37—36—35—34—33—29—26—23—20—14—15—18—21—16—17—38—40—41—42—44—46—49—48—50—47
图2.1.2标示出了建造理想状态下缆车索道的大致走向，在此状态下铺设缆车索道的最短距离，所用费用最小。
2.2、模型二
在模型2.1中，本文建立的是一个理想化的模型，但这种理想化模型不适用于实际。因而，在考虑建造空中缆车索道费用最小这个大前提下，本文给出了一个符合实际要求的模型，即模型2.2。
模型2.1中，运用了Floyd算法，在这个模型中，仍然考虑运用Floyd算法，但考虑到其他因素，本文还加上了经典算法：聚类分析法。将景区内经典比较密集的景点进行分类，以节省建造空中缆车索道的费用。
聚类分析的基本思想：
研究的样品（网点）或指标（变量）之间存在程度不同的相似性（亲疏关系——以样品间距离衡量）。于是根据一批样品的多个观测指标，具体找出一些能够度量样品或指标之间相似程度的统计量，以这些统计量为划分类型的依据。把一些相似程度较大的样品（或指标）聚合为一类，把另外一些彼此之间相似程度较大的样品（或指标）又聚合为另一类，直到把所有的样品（或指标）聚合完毕，这就是分类的基本思想。
聚类分析法可分三种：直接聚类法、最短距离聚类法和最长距离聚类法，本文所需的是第二中聚类算法思想，并根据所添加的约束条件（景点到搜索点的距离不大于500m）进行适当的改进。
聚类分析的基本步骤：
（1）计算n个样本两两间的距离{dij}，记D；
（2）计算出这n个样板是所在长方形最小区域；
（3）搜索出景区满足约束条件的最密集的区域所表示的坐标（i,j）和包含点数k；
（4）如果k等于1，转到（5），否者剔除（3）所搜索的区域所包含的点，回（3）；
（5）将搜索的（i,j）和未剔除的点看作m个类；
（6）画出这m类的位置。
由聚类分析基本步骤，得到其算法流程图（图2.2.1）
图2.2.1 聚类分析算法流程图
根据上述聚类算法步骤，利用最小生成树法中的Floyd算法可得到最佳缆车索道线。
具体的操作可如下：
由于以国家森林公园为旅游的出发点，可以从所有景点中剔除出去，利用聚类分析法对剩余的50个景点进行处理，得到替代两个或两个以上聚点的坐标（表2.2.1）。
表2.2.1 51个景点聚类后得到的数据
五点聚点（29，30，32，33，34）2625
四级聚点（23，26，27，28）1831
四点聚（15，16，18，21）3743
三点聚（12，13，14）2247
三点聚（38，39，40）5850
三点聚（46，48，49）7887
两点聚（35，36）2014
两点聚（22，24）527
两点聚（19，20）1237
两点聚（7，41）5261
两点聚（47，50）8591
由聚类后得到的景点与未被搜索到的18个景点坐标相组合，构出30个新的空中缆车站坐标。
运用Matlab技术对表2.2.1的数据进行处理，用图片的形式展现，可以得到图2.2.2。
图2.2.2 30个新的空中缆车站坐标
聚类后，将得到的30个空中缆车站坐标，运用Floyd算法，找出缆车索道建构最优路径（图2.2.3、程序见附录程序2.2.2）其距离：d=445.0506mm，实际距离D=44505.06m，所需最小费用为S=445050.6万元。
图2.2.3 30个空中缆车站形成的最小生成树
这一步，将新得到的30个空中缆车站坐标进行了处理，得到图2.2.3的权最小的支撑树；因而我们可以得到铺设缆车索道的路线图，即
第三步：画出其线路图；
图2.2.4 30个新缆车站的大致走向
表2.2.2 聚类后的缆车站坐标
序号地名名坐标x 坐标y 序号地名名坐标x 坐标y
1 1 -18 115 16 43 30 77
2 2
3 11
4 17 44 56 71
3 3 11 95 18 45 46 89
4 4 21 86 19 51 109 22
5 5 -9 75 20 五点聚点（29，30，32，33，34）2
6 25
6 6 21 68 21 四级聚点（23，26，27，28）18 31
7 8 24 55 22 四点聚（15，16，18，21）37 43
8 9 -19 63 23 三点聚（12，13，14）22 47
9 10 0 57 24 三点聚（38，39，40）58 50
10 11 -16 50 25 三点聚（46，48，49）78 87
11 17 18 40 26 两点聚（35，36）20 14
12 25 57 36 27 两点聚（22，24） 5 27
13 31 12 28 28 两点聚（19，20）12 37
14 37 0 0 29 两点聚（7，41）52 61
15 42 42 68 30 两点聚（47，50）85 91
根据图2.2.4及表2.2.2做出其最优路线表，以便游客查找最佳旅游路线及铺设索道的最优路线。
起点国家森林公园14
14—26—20—21—13—27
14—26—20—21—28—9—10—8—5
14—26—20—21—28—11—23—22 14—26—20—21—28—11—23—7—6—16—18 14—26—20—21—28—11—23—7—6—16—4—3—2—1 14—26—20—21—28—11—23—7—6—16—15—29—17—25—30 14—26—20—21—28—11—23—7—6—16—15—29—24—12—19 图2.2.4标示出了实际建造缆车索道的大致走向，这个走向是在考虑实际因素的条件下，铺设缆车索道的最短距离，所用费用最小的走向，即为本文所构建的张家界旅游最佳路线。
六、模型评价
问题一：利用Google地图对张家界51个景点进行定位搜索，可以精确的定位出各个点的经、纬度；但由于各点的经、纬度相差不大，对所给经、纬度标准化处理，得到的景点的相对平面坐标有着较大的系统误差。计算机对这些景点坐标进行数据处理和作图与原图比较，存在细微的差别。
问题二：由于建设缆车索道所要考虑的因素有很多，而这些因素有些是难以数据化，譬如地理环境和每个景点的客流量等。本文只能忽略这些因素对张家界旅游管理部门建造缆车索道的影响，相应的构建比较理想的模型环境。在构建最佳路线模型，本文是假设所有景点的海拔时相同的，实际上张家界旅游景点有高山、平地以及湖泊等，它们在二维图上缆车索道建造的长度是不相同的。
根据景点坐标运用聚类分析——最小生成树法作出缆车索道图形，聚类分析法可以精确、清晰的分析51个旅游景点的密集程度，保证聚合得每一类聚点都是唯一确定的且满足约束条件。
本文的创新点在于对密集程度比较高的景点进行新型聚类处理。一般的聚类分析法对已知的所有点中两个最近点合并一类，看作一个新点，反复查找，层层
聚类，直到类数只有一个停止。而本文的聚类相对于一般聚类法多出一个约束条件，也就是旅客所能接受步行距离的最大值为500m。本文对所有可能设置缆站进行迭代搜索，搜寻最密集的区域，进行聚类，看作一类，去除这类所有的缆站，对剩余的缆站再进行迭代搜索，反复迭代，直到搜索到一点归为一类停止，将剩下的一点为一类，通过这种算法可节省张家界旅游管理部门对缆车索道的投资近1亿人民币。
七、模型改进
针对模型评价的某些缺点与不足，我们可以进行适当的改进，具体方法如下：张家界的所有风景区的人流量和地势是不同的。因此，人步行到各个风景区的最大距离，如到高山、平地以及湖泊可以赋予不同的权重；人流量比较高或地势较平的景区可以赋予相对小点的权重，而比较冷僻或地势比较高的景区可以赋予相对大点的权重。对于实际的景区环境进行实地考察，将一些不适合建缆车的景区当作异常点剔除，一些景区间有着比较大的屏障，可以设它们的距离为无穷大，也就是说它们间不能建缆车索道。
人们对张家界旅各游景区的选择：旅游景点的风景好坏对旅客的吸引力有着重要的影响，不同的季节的人流量也略有不同，所以我们可以对每个景点的步行距离的最大值的权重赋多次值进行模拟。
具体操作过程为：
（1）到各个景区进行实地考察，找出每个景区中的地理异常，并大致对比下每个景区的人流情况。对异常的地理环境进行分析是否能建缆车索道以及对人流量的多少进行。
（2）对不能实现缆车索道铺建的景点进行剔除和路线的删减，根据人流量的多少和地势高低赋于不同权重。
（3）通过新型的聚类法，聚类合并出满足约束条件的若干个缆站，通过最小生成树法找到需要铺造缆车索道的路线。
（4）改变各点权重，反复运算，得到最省钱且满足实用的路线。
根据以上步骤，得到改进后的聚类分析流程图（图2.2.5）
图2.2.5 改进后的聚类算法流程图
八、模型的推广与应用
最小生成树法和聚类分析法，就是要在一个连通网络中，寻找最枝数的支撑树，即找到最优解。最小生成树法和聚类分析法不仅仅能够在旅游业中可以用到，在许多服务各地的公司中，如燃气公司、送电公司、有多个分公司的大型公司等的作用尤其明显。
聚类分析的主要作用是：
1、不但可以了解个别变量之间的关系的亲疏程度，而且可以了解各个变量
组合之间的亲疏程度。
2、根据变量的分类结果以及它们之间的关系，可以选择主要变量进行聚类
分析。
九、参考文献
①、谷歌地图
②、张威主编，Matlab基础与编程入门【M】,西安电子科技大学出版社，2008
年
③、刘承平，数学建模方法【M】，北京：高等教育出版社，2002年
④、李祥会、张红，基于模糊动态聚类分析的教学质量评估方法研究【M】，四川
师范大学学报（自然科学版），2004年1月
⑤、叶其孝主编，大学生数学建模竞赛辅导教材【M】，湖南教育出版社，2001
年
⑥、姜启源、谢金星、叶俊，数学建模（第三版）【M】，北京：高等教育出版社，
2003年
十、附录
表1张家界各景点经纬、度表
旅游点经度纬度旅游点经度纬度
张家界九天洞29.324645 110.119486 张家界天书宝匣29.325169 110.433884 张家界天子山镇29.408273 110.447962 张家界南天门29.401321 110.499115 张家界将军岩29.311474 110.045457 张家界劈山救母29.319182 109.790057 张家界天子峰29.408049 110.448389 张家界定海神针29.318839 109.790057 张家界龙泉飞瀑29.321570 109.971429 张家界天桥29.371405 110.466156 张家界鸳鸯瀑布29.311324 109.945518 张家界花果山29.351058 110.442810 张家界空中田园29.309275 109.930712 张家界护鞭神鹰29.317472 109.775251 张家界观光电梯29.310301 109.897399 张家界金鞭岩29.234882 110.463409 张家界天波府29.324987 109.930712 张家界闺门岩29.319183 109.753042 张家界天悬白练29.318497 109.904802 张家界夫妻岩29.321571 109.738237 张家界空中走廊29.323962 109.878892 张家界国家森林公园29.316788 110.434914 张家界天下第一桥29.318839 109.878892 张家界张良墓29.308592 109.867787 张家界迷魂台29.319182 109.867787 张家界水绕四门29.221101 110.465469 张家界五女拜师29.319181 109.856683 张家界神兵聚会29.307909 109.889996 张家界后花园29.342678 110.433197 张家界老屋场29.307909 109.923309 张家界重欢树29.313032 109.845579 张家界采药老人29.304152 109.945518 张家界跳鱼潭29.342678 110.467529 张家界仙人桥29.373948 110.467701 张家界紫草潭29.315423 109.841877 张家界雄狮回首29.299372 109.956622 张家界天桥遗墩29.322254 109.841877 张家界天台1 29.379028 110.493487 张家界黑枞脑29.321571 109.834474 张家界天台2 29.379034 110.493453 张家界千里相会29.366618 110.455172 张家界仙女献花29.296638 110.019547 张家界九重仙阁29.348664 110.419464 张家界御笔峰29.407301 110.490875
张家界黄狮寨29.333701 110.432167 张家界西海29.407301 110.494995 张家界鸳鸯泉29.323962 109.790057 张家界贺龙公园29.371106 110.514565 张家界双龟探溪29.299029 109.827071 张家界鹰窝寨29.281268 109.775251 张家界南天一柱29.327264 110.435944
程序2.1.1
x=[-18 3 11 21 -9 21 27 24 -19 0 -16 -1 -2 -2 9 16 18 9
-11 -9 11 -24 -5 -16 57 -6 -9 -8 -2 -1 12 5 3 2 -2 -9 0
29 35 31 31 42 30 56 46 53 64 55 50 56 109];
y=[115 114 95 86 75 68 64 55 63 57 50 50 47 44 45 41 40 40 40
38 39 28 34 26 36 29 27 28 26 28 28 25 22 21 16 12 0 47
45 53 62 68 77 71 89 83 88 90 86 92 22];
d(:,:)=zeros(51,51);
for i=1:51;
for j=1:51;
d(i,j)=sqrt((x(j)-x(i)).^2+(y(j)-y(i)).^2);
end
end
a
程序2.1.2
a
a(find(a==0))=M;
result=[];p=1;tb=2:length(a);
while length(result)~=length(a)-1
temp=a(p,tb);temp=temp(:);
d=min(temp);
[jb,kb]=find(a(p,tb)==d);
j=p(jb(1));k=tb(kb(1));
result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[];
end
result
d=sum(result(3,:))
输出结果：
1.0000
2.0000
3.0000
4.0000 43.0000 6.0000 7.0000 41.0000
2.0000
3.0000
4.0000 43.0000 6.0000 7.0000 41.0000 40.0000
21.0240 20.6160 13.4540 12.7280 12.7280 7.2111 4.4721 9.0000
38.0000 39.0000 8.0000 40.0000 41.0000 38.0000 17.0000 16.0000
40.0000 38.0000 40.0000 8.0000 42.0000 17.0000 16.0000 21.0000
6.3246 6.3246
7.2801 7.2801 12.5300 13.0380 2.2361 5.3852
21.0000 18.0000 15.0000 14.0000 13.0000 12.0000 14.0000 20.0000
18.0000 15.0000 14.0000 13.0000 12.0000 10.0000 20.0000 19.0000
2.2361 5.0000 11.0450
3.0000 3.1623 7.0711 9.2195 2.8284
20.0000 23.0000 26.0000 28.0000 26.0000 29.0000 29.0000 33.0000 23.0000 26.0000 28.0000 27.0000 29.0000 34.0000 30.0000 33.0000 5.6569 5.0990 2.2361 1.4142 5.0000 2.2361 6.4031 1.4142
33.0000 34.0000 27.0000 32.0000 35.0000 24.0000 19.0000 11.0000 32.0000 35.0000 24.0000 31.0000 36.0000 22.0000 11.0000 9.0000 3.6056 6.4031 7.0711 7.6158 8.0623 8.2462 11.1800 13.3420
42.0000 44.0000 46.0000 49.0000 49.0000 48.0000 50.0000 36.0000 44.0000 46.0000 49.0000 45.0000 48.0000 50.0000 47.0000 37.0000 14.3180 12.3690 4.2426 5.0000 6.4031 2.2361 8.9443 15.0000
9.0000 39.0000 25.0000
5.0000 25.0000 51.0000
15.6200 23.7700 53.8520
d =454.6550
程序2.2.1
p=5; %500m
xx=[-18 3 11 21 -9 21 24 -19 0 -16 18 -9 -24 57 12 42 30
56 46 109];
yy=[115 114 95 86 75 68 55 63 57 50 40 38 28 36 28 68 77
71 89 22];
%所有点的坐标
x=xx+25;
y=yy+1;
x1=minmax(x); %x轴的最值
y1=minmax(y); %y轴的最值
d(:,:,:)=zeros(size(x'),x1(2)-x1(1)+1,y1(2)-y1(1)+1); %定义变量(k,i,j)
for i=x1(1):x1(2)
for j=y1(1):y1(2)
for k=1:size(x')
if (j-y(k)).^2+(i-x(k)).^2 d(k,i,j)=1; %0-1规划 end end end end d1=sum(d); z1=d1(:,:,1); z2=d1(:,:,2); z3=d1(:,:,3); . . . z115=d1(:,:,115); z116=d1(:,:,116); X=[z1',z2',z3',z4',z5',z6',z7',z8',z9',z10',z11',z12',z13',z14',z 15',z16',z17',z18',z19',z20',z21',z22',z23',z24',z25',z26',z27',z28', z29',z30',z31',z32',z33',z34',z35',z36',z37',z38',z39',z40',z41',z42' ,z43',z44',z45',z46',z47',z48',z49',z50',z51',z52',z53',z54',z55',z56 ',z57',z58',z59',z60',z61',z62',z63',z64',z65',z66',z67',z68',z69',z7 0',z71',z72',z73',z74',z75',z76',z77',z78',z79',z80',z81',z82',z83',z 84',z85',z86',z87',z88',z89',z90',z91',z92',z93',z94',z95',z96',z97', z98',z99',z100',z101',z102',z103',z104',z105',z106',z107',z108',z109' ,z110',z111',z112',z113',z114',z115',z116']; bb=X(:); n=max(bb) [cc,dd]=find(X==n); cc(1) dd(1) ddd=zeros(1,size(x')); for k=1:size(x') if (dd(1)-y(k)).^2+(cc(1)-x(k)).^2 ddd(k)=1; end end ddd 程序2.2.2 clear clc x=[-18 3 11 21 -9 21 24 -19 0 -16 18 57 12 0 42 30 56 46 109 26 18 37 22 58 78 20 5 12 52 85]; y=[115 114 95 86 75 68 55 63 57 50 40 36 28 0 68 77 71 89 22 25 31 43 47 50 87 14 27 37 61 91]; d(:,:)=zeros(30,30); for i=1:30; for j=1:30; d(i,j)=sqrt((x(j)-x(i)).^2+(y(j)-y(i)).^2); end end a a(find(a==0))=M; result=[];p=1;tb=2:length(a); 第八章 约束优化最优性条件 §8.1 约束优化问题 一、 问题基本形式 min ()f x 1()0 1,,.. ()0 ,,i e i e c x i m s t c x i m m +==?? ≥=?L L （8.1） 特别地，当()f x 为二次函数，而约束是线性约束时，称为二次规划。 记 {} 1()0 (1,,);()0 ,,i e i e X x c x i m c x i m m +===≥=L L ，称之为可行域（约束域）。 {}1,,e E m =L ，{}1,,e I m m +=L ，{}()()0 i I x i c x i I ==∈ 称()E I x U 是在x X ∈处的积极约束的指标集。积极约束也称有效约束，起作用约束或紧约束（active constraints or binding constraints ）。 应该指出的是，如果x * 是（1）的局部最优解，且有某个0i I ∈，使得 0()0i c x *> 则将此约束去掉，x * 仍是余下问题的局部最优解。 事实上，若x *不是去掉此约束后所得问题的局部极小点，则意味着0δ?>，存在x δ，使得 x x δδ*-<，且()()f x f x δ*<，这里x δ满足新问题的全部约束。注意到当δ充分小时，由0() i c x 的连续性，必有0()0i c x δ≥，由此知x δ是原问题的可行解，但()()f x f x δ*<，这与x * 是局部极小 点矛盾。 因此如果有某种方式，可以知道在最优解x * 处的积极约束指标集()()A x E I x * *=U ，则问题 可转化为等式的约束问题： min ()f x .. ()0i s t c x = ()i A x *∈ （8.2） 一般地，这个问题较原问题（8.1）要简单，但遗憾的是，我们无法预先知道()A x * 。 fgoalattain Solve multiobjective goal attainment problems Equation Finds the minimum of a problem specified by x, weight, goal, b, beq, lb, and ub are vectors, A and Aeq are matrices, and c(x), ceq(x), and F(x) are functions that return vectors. F(x), c(x), and ceq(x) can be nonlinear functions. Syntax x = fgoalattain(fun,x0,goal,weight) x = fgoalattain(fun,x0,goal,weight,A,b) x = fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq) x = fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub) x = fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon) x = fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon,... options) x = fgoalattain(problem) [x,fval] = fgoalattain(...) [x,fval,attainfactor] = fgoalattain(...) [x,fval,attainfactor,exitflag] = fgoalattain(...) [x,fval,attainfactor,exitflag,output] = fgoalattain(...) [x,fval,attainfactor,exitflag,output,lambda] = fgoalattain(...) Description fgoalattain solves the goal attainment problem, which is one formulation for minimizing a multiobjective optimization problem. 配套的处理方式；果蔬采后商品化处理量几乎达到了100％，形成了完整的果蔬冷链体系。而我国的产地基础设施不完善，未能解决分选、分级、预冷、冷藏运输和保鲜等采后果蔬的处理问题。我国果蔬冷链存在许多问题：产地预冷环节薄弱；冷藏运输工具落后；冷库发展水平低；缺乏有影响力的第三方冷链物流。我国果蔬冷链发展水平要赶上发达国家还有较长的路要走。 要完善我国的果蔬冷链业，除了大力研发性价比合理、符合国情的相关冷链设备、设施以外；还需要全面的对整个果蔬冷链过程中存在的影响果蔬产品质量的风险因素进行分析和评价，从而一一破解；更需要系统地梳理整个果蔬冷链链条，是指实现协同化，构建果蔬冷链质量质量保障体系。这样才能真正确保果蔬产品的质量安全，确保千万消费者食用上安全放心的果蔬产品。 流线优化模型与算法研究及应用 张锦*（交通与物流学院） 1 研究背景 目前我国物流产业正处于高速发展期，理论体系与应用研究正在不断完善。物流活动的目的就是使物流服务来满足物流需求，即通过仓储、加工、运输、配送、包装、装卸搬运等活动来满足社会经济活动中供应商、制造商、零售商、消费者等需求方的对物的移动、储存与服务的需求。在宏观层面的区域及城市经济和微观层面的制造、贸易、消费等典型社会经济活动中的物流活动可抽象为具有特定需求的空间结构，称作物流需求网络。 在物流系统中，由若干特定的点、线和特定的权构成的，反映物流服务与需求关系的供需网络称之为流线网络，它具有以下典型特征。 1．反映了仓储、加工、运输、配送、包装、装卸搬运等物流服务与需求方在物品数量、到达时间、物流费用等方面的物流需求间的供需关系。 2．具有嵌套、多层、多级、多维、多准则、拥塞等典型的超网络结构特征，并且具有连接供需两个物流网络的超网络结构。 3．当实际需求为特定值时，物流服务追求的目标为用恰当的费用，在恰当的时间把恰当数量的恰当物品，经恰当的路线送到恰当的地点。 物流供应网络与物流需求网络之间的关系可由超网络结构进行刻画，用匹配度刻画物流服务与物流需求之间的适应程度。 2 国内外研究现状 目前，国内外学者对流线的组织与优化问题研究较少，与此问题相关的内容包括物流网络、物流网络分配、动线优化、超网络理论与应用、变分不等式算法及其在供应链网络中的应用等内容。 2.1 物流网络研究现状 国外的学者大都倾向从微观的企业角度去研究物流网络的资源配置和协调问题,如物流基础设施、市场竞争机制以及配送运输等问题。这类研究大多利用数学规划法、系统仿真法、启发式 *作者简介：张锦，男，教授。 基于数学模型的网络优化方法研究 赵鹏 通信一团技术室 摘 要 为了提高网络链路的利用率，解决网络传输中的最大流问题，该文利用建立数学模 型的方法来求解网络的传输路径，研究了基于路径的网络优化方法。该方法能够极大地提高网络的链路利用率，从而降低网络的拥塞，使得网络的性能得到较大改善。 关键词 网络优化 最大流 数学模型 1 引言 随着网络技术的进步和人们对多媒体综合业务需求，传统的数据网络逐渐转向多媒体网络，在这过程中，除了相关服务以外，我们还面临许多极具战性的网络设计和优化问题。网络优化的目标是提高或保持网络质量，而网络质量是各种因素相互作用的结果，随着网络优化工作的深入开展和优化技术的提高，优化的范围也在不断扩大。 在计算机网络优化设计中，各条链路的容量分配和各节点间的路由选择是两个重要问题。在给定网络拓扑结构和各节点间传输流量的条件下，如何确定各条链路的容量大小和选择各节点间的最佳路由，使整个网络成本费用最低并能满足规定的性能指标呢？ 许多网络优化的文献，研究针对CDMA 网络、GPRS 网络、GSM 网络、PHS 网络等具体网络在投入运行后，对网络进行参数采集、数据分析，找出影响网络质量的原因，通过技术手段或参数调整使网络达到最佳运行状态，涉及到交换网络技术、无线参数、小区参数配置、信令和设备技术等方面。 本文针对目前许多网络传输链路和网络设备没有得到充分利用，从而影响网络性能的问题，利用网络优化方法从理论上进行分析，研究了用于提高网络链路利用率的基于路径的网络优化方法，该方法能够充分地利用网络链路进行流量传输，从而改善网络的整体性能。 2 网络优化理论 很多情况下可以将网络优化问题转化成数学问题进行研究和分析。从根本上讲，优化问题包含三个基本要素： 决策变量集合或向量：n R x ∈（本文，x 代表在一条或多条路径上的流量） 目标函数R R x f n →:)( 一组约束条件g(x)和h(x)，用来定义x 的范围。 解决优化问题实际上就是找出一个点x*，使得f(x)最大化或最小化。 典型的网络优化问题包含找出一组路由和该路由上的流量值以便达到最大或最小化目标函数的目的。目标函数可以代表最大链路利用率、平均延迟或其他指标。 基于路径的问题首先要计算出网络流可能流经的路径，要最大限度的利用网络链路，同时路径上的流量不能超过链路容量。 对于基于路径的网络优化问题可以简单表示成： max f(x) s.t. ∑∈=P p p b x 多目标优化模型 中国水资源具有显著地区域特征，我们对区域水资源多目标优化配置,以多目标和大系统优化为手段,在一定时间内可供水量和需水量确定的条件下,建立区域有限的水资源量在各流域的优化配置模型,求解模型得到水量优化配置方案. 目标函数的建立： 水资源配置主要考虑3 个目标函数,即用水效益函数、用水费用函数和区域均衡性函数。对于优质水资源而言,用水效益重点考虑工业和第三产业所产生的效益,将农业用水排除在外,旨在优先考虑经济效益好的区域用水需求。用水费用主要指输水费用,包括管道铺设和渠道建设费用,优质水资源还需要着重考虑饮用水的制水成本. 区域均衡性函数则为了避免供水一味向经济发达区域倾斜,使各区域供水与需水之差满足某种准则,以体现社会和谐精神.具体目标如下: （1) 用水收益最大;（2) 运营成本最低;（3）区域水资源供需尽量均衡. 设i g 为第i 个流域使用每立方米水资源所产生的效益参数, c ij 为第i 个用户由第j 个供水源输送每立方米水所需的费用, x ij 为由第j 个水源供给第i 个流域的水量,各区域的用水量x M x i j ij =∑=, D i 为第i 个区域的需水总量,则水资源配置的目标函数可以综合表示成如下形式: 2 111max (c )/(1/)n n n i i ij j i i i j i Z opt g x x x D ===??=--???? ∑∑∑ 式中:右边分子第一项表示水资源利用所产生的经济效益,包括环境效益,对 于优质水资源则取非农业经济效益;右边分子第二项为运营成本,主要涉及制水成本和水库至流域的输水成本;分母反映区域水资源供需之间的均衡程度,表示各区域的用水保证率尽可能最大，N 为供水区域数. 1. 2 参数及约束条件设置 中国各流域的水资源需要进行合理分配，以达到水资源的平衡，需要适当设置参数和约束条件. 首先按照2 种方式划分区域:其一以流域为单元,便于在模型中计算经济效益;其二以供水源为单元,以利于分析区域水资源的供需平衡关系. 各流域从水库获得的水量受水库供水量的限制,而水库供水量又受水源的水来源的可供水量约束. 根据中国历年的降雨量资料计算出各水库在不同频率下的可供水量,结合中国供水状况获得在若干种供水保证率下各水库的可供水量,各流域可取得的水量不得超过水源地水库的可供水量与水厂供水量中的较小者 j Q ,以此作为各变量的约束条件1)。设水库数为1R ,供水源为2 R ,供水单元数 为M ,当出现若干水库是同一水源的情形时取2M R = ,而当一个水厂以多个水库为水源地时取1M R = . 在这两种情形下,除满足约束条件1)外,尚需满足这些水库的供水量之和不大于水源地的可供水量或水库的供水量小于水源地的 遗传算法优化的BP神经网络建模 十一月匆匆过去，每天依然在忙碌着与文档相关的东西，在寒假前一个多月里，努力做好手头上的事的前提下多学习专业知识，依然是坚持学习与素质提高并重，依然是坚持锻炼身体，为明年找工作打下基础。 遗传算法优化的BP神经网络建模借鉴别人的程序做出的仿真，最近才有时间整理。 目标： 对y=x1^2+x2^2非线性系统进行建模，用1500组数据对网络进行构建网络，500组数据测试网络。由于BP神经网络初始神经元之间的权值和阈值一般随机选择，因此容易陷入局部最小值。本方法使用遗传算法优化初始神经元之间的权值和阈值，并对比使用遗传算法前后的效果。 步骤： 未经遗传算法优化的BP神经网络建模 1、随机生成2000组两维随机数(x1,x2)，并计算对应的输出y=x1^2+x2^2，前1500组数据作为训练数据input_train，后500组数据作为测试数据input_test。并将数据存储在data中待遗传算法中使用相同的数据。 2、数据预处理：归一化处理。 3、构建BP神经网络的隐层数，次数，步长，目标。 4、使用训练数据input_train训练BP神经网络net。 5、用测试数据input_test测试神经网络，并将预测的数据反归一化处理。 6、分析预测数据与期望数据之间的误差。 遗传算法优化的BP神经网络建模 1、读取前面步骤中保存的数据data； 2、对数据进行归一化处理； 3、设置隐层数目； 4、初始化进化次数，种群规模，交叉概率，变异概率 5、对种群进行实数编码，并将预测数据与期望数据之间的误差作为适应度函数； 6、循环进行选择、交叉、变异、计算适应度操作，直到达到进化次数，得到最优的初始权值和阈值； 7、将得到最佳初始权值和阈值来构建BP神经网络； 8、使用训练数据input_train训练BP神经网络net; 9、用测试数据input_test测试神经网络，并将预测的数据反归一化处理； 10、分析预测数据与期望数据之间的误差。 算法流程图如下： function [a,b,n,x]=fibonacci(fname,a,b,d,L) % fname函数句柄，d辨别常数，L最终区间长度a(1)=a; b(1)=b; F=zeros(1,10); %选择fibonacci数列k值为10，可任意更改 F(1)=1; F(2)=2; for k=2:10 %k取到10，生成fibonacci数列 F(k+1)=F(k)+F(k-1); F(k); end Fn=(b(1)-a(1))/L; Fk=[F Fn]; N=sort(Fk); n=find(Fn==N); %查找计算函数值的次数n t(1)=a(1)+F(n-2)*(b(1)-a(1))/F(n); %计算试探点t(1),u(1) u(1)=a(1)+F(n-1)*(b(1)-a(1))/F(n); for k=1:n-2 ft=feval(fname,t(k)); fu=feval(fname,u(k)); if ft>fu a(k+1)=t(k); b(k+1)=b(k); t(k+1)=u(k); u(k+1)=a(k+1)+F(n-k-1)*(b(k+1)-a(k+1))/F(n-k); while k==n-2 t(n)=t(n-1); u(n)=t(n-1)+d; ft=feval(fname,t(n)); fu=feval(fname,u(n)); if ft>fu a(n)=t(n); b(n)=b(n-1); else a(n)=a(n-1); b(n)=t(n); end end else a(k+1)=a(k); b(k+1)=u(k); u(k+1)=t(k); if k~=n-2 t(k+1)=a(k+1)+F(n-k-2)*(b(k+1)-a(k+1))/F(n-k); ft=feval(fname,t(k)); 图论与网络优化课程设计 四种基本网络（NCN、ER、WS、BA） 的构造及其性质比较 摘要：网络科学中被广泛研究的基本网络主要有四种，即：规则网络之最近邻耦合网络（Nearest-neighbor coupled network）,本文中简称NCN；ER随机网络G(N,p)；WS小世界网络；BA无标度网络。本文着重研究这几种网络的构造算法程序。通过运用Matlab软件和NodeXL网络分析软件，计算各种规模下（例如不同节点数、不同重连概率或者连边概率）各自的网络属性(包括边数、度分布、平均路径长度、聚类系数)，给出图、表和图示，并进行比较和分析。 关键字：最近邻耦合网络；ER随机网络；WS小世界网络；BA无标度网络；Matlab；NodeXL。 四种基本网络（NCN、ER、WS、BA） 的构造及其性质比较 1.概述 1.网络科学的概述 网络科学（Network Science）是专门研究复杂网络系统的定性和定量规律的一门崭新的交叉科学，研究涉及到复杂网络的各种拓扑结构及其性质，与动力学特性（或功能）之间相互关系，包括时空斑图的涌现、动力学同步及其产生机制，网络上各种动力学行为和信息的传播、预测（搜索）与控制，以及工程实际所需的网络设计原理及其应用研究，其交叉研究内容十分广泛而丰富。网络科学中被广泛研究的基本网络主要有四种，即：规则网络之最近邻耦合网络（Nearest-neighbor coupled network）,本文中简称NCN；ER随机网络G(N,p)；WS小世界网络；BA无标度网络。本文着重研究这几种网络的构造算法程序。计算各种规模下（例如不同节点数、不同重连概率或者连边概率）各自的网络属性(包括边数、度分布、平均路径长度、聚类系数)，给出图、表和图示，并进行比较和分析。 2.最近邻耦合网络的概述 如果在一个网络中，每一个节点只和它周围的邻居节点相连，那么就称该网络为最近邻耦合网络。这是一个得到大量研究的稀疏的规则网络模型。 常见的一种具有周期边界条件的最近邻耦合网络包含围成一个环的N个节点，其中每K个邻居节点相连，这里K是一个偶数。这类网络的一个重要特征个节点都与它左右各/2 就是网络的拓扑结构是由节点之间的相对位置决定的，随着节点位置的变化网络拓扑结构也可能发生切换。 NCN的Matlab实现： %function b = ncn(N,K) %此函数生成一个有N个节点，每个节点与它左右各K/2个节点都相连的最近邻耦合网络 %返回结果b为该最近邻耦合网络对应的邻接矩阵 function b = ncn(N,K) b=zeros(N); for i = 1:N for j = (i+1):(i+K/2) if j<=N b(i,j)=1; b(j,i)=1; else b(i,j-N)=1; §8.1多目标最优化问题的基本原理 一、多目标最优化问题的实例 例1 梁的设计问题 设用直径为1的圆木加工成截面积为矩形的梁，为使强度最大而成本最低， 问应如何设计梁的尺寸？ 解： 设梁的截面积宽和高分别为1x 和2x 强度最大=惯性矩最大 2 216 1x x = 成本最低=截面积最小=21x x 故数学模型为： min 1 x 2 x max 2216 1x x .s t 221 2 1x x += 10x ≥，20x ≥ 例2 买糖问题 已知食品店有1A , 2 A , 3 A 三种糖果单价分别为4元∕公斤，2.8元∕公斤， 2.4元∕公斤，今要筹办一次茶话会，要求用于买买糖的钱不超于20元，糖 的总量不少于6公斤，1A ， 2 A 两种糖的总和不少于3公斤，问应如何确定买糖的最佳方案？ 解：设购买1A , 2 A , 3 A 三种糖公斤数为1x ，2x ，3x 1 A 2 A 3 A 重量 1x 2x 3x 单价 4元∕公斤 2.8元∕公斤 2.4元∕公斤 min 14x +22.8x +3 2.4x （用钱最省） max 1x +2x +3x （糖的总量最多） .st 14x +22.8x +3 2.4x 20≤ (用钱总数的限制) 1x +2x +3x 6≥（用糖总量的要求） 1x +2x 3≥（糖品种的要求） 1x ，2x ，3x 0≥ 是一个线性多目标规划。 二、 多目标最优化的模型 12min ()((),(),.....())T m V F x f x f x f x -= .st ()0g x ≥ ()0h x ≥ 多目标规划最优化问题实际上是一个向量函数的优化问题，当m=1,多目标优化就是前面讲的单目标优化问题 三、解的概念 1.序的概念 12,.....()T m a a a a = 12,.....()T m b b b b = （1）b a =?a i i b = 1,2....i m = （2）a b ≤?a i i b ≤ 1,2....i m = 称a 小于等于b （3）a b < =?a i i b ≤ 且?1≤j ≤m ，使a j j b ≠，则a 小于向量b （4）a 最优化理论与算法笔记 在老师的指导下，我学习了最优化理论与算法这门课程。最优化理论与算法是一个重要的数学分支，它所研究的问题是讨论在众多方案中什么样的方案最优以及怎样找出最优方案。 由于生产和科学研究突飞猛进的发展，特别是计算机的广泛应用，使最优化问题的研究不仅成为了一种迫切的需要，而且有了求解的有力工具，因此迅速发展起来形成一个新的学科。至今已出现了线性规划、整数规划、非线性规划、几何规划、动态规划、随机规划、网络流等许多分支。 整个学习安排如下，首先介绍线性与非线性规划问题，凸集和凸函数等基本知识及线性规划的基本性质；然后再这个基础上学习各种算法，包括单纯形法、两阶段法、大M 法、最速下降法、牛顿法、共轭梯度法等，以及各种算法相关的定理和结论；最后了解各种算法的实际应用。 主要学习的基础知识： 1、一般线性规划问题的标准形式 1min n j j j c x =∑ 1 .., 1,...,, 0, 1,...,. n ij j i j j s t a x b i m x j n ===≥=∑ 学会引入松弛变量将一般问题化为标准问题；同时掌握基本可行解的存在问题，通过学习容易发现线性规划问题的求解，可归结为求最优基本可行解的问题。 2、熟练掌握单纯形法、两阶段法和大M 法的概念及其计算步骤。 单纯形法是一种是用方便、行之有效的重要算法，它已成为线性规划的中心内容。其计算步骤如下： 1）解,B Bx b =求得1B x B b b -==，令0,N x =计算目标函数值B B f c x =； 2)求单纯形乘子ω，解B B c ω= ，得到1B c B ω-=； 3)解k k By p =，若0k y ≤，即k y 的每个分量均非正数，则停止计算，问 题不存在有限最优解，否则，进行步骤（4）； 4)确定下标r ，使min{0}r r rk rk rk b b y y y =>，得到新的基矩阵B ，返回第一 步。 两阶段法：第一阶段是用单纯形法消去人工变量，即把人工变量都变换成非基变量，求出原来问题的一个基本可行解；第二阶段是从得到的基本可行解出发，用单纯形法求线性规划的最优解。 大M 法：在约束中增加人工变量a x ，同时修改目标函数，加上罚项T a Me x ，其中M 是很大的正数，这样，在极小化目标函数的过程中，由于M 的存在，将迫使人工变量离基。 3、掌握最速下降法的概念及其算法，并且能够讨论最速下降算法的收敛性。掌握牛顿法，能够熟练运用牛顿迭代公式：(1) ()2()()()()k k k k x x f x x x +=-?- ，掌 握共轭梯度法及其相关结论，以及其收敛性的讨论，掌握最小二乘法及其基本步骤。 最速下降法：迭代公式为(1) ()()k k k k x x d λ+=-。 计算步骤：1）给定点(1)n x R ∈，允许误差0,ε>臵1k =； 2）计算搜索方向() ()()k k d f x =-?； 3）若() k d ε≤，则停止计算，否则，从()k x 出发，沿()k d 进行一维搜索，求k λ，使()()()() ()min ()k k k k k f x d f x d λλλ≥+=+； 4）令(1) ()()k k k k x x d λ+=-，臵:1k k =+，转步骤（2）。 最优化理论与算法（数学专业研究生） 第一章 引论 § 引言 一、历史与现状 最优化理论最早可追溯到古老的极值问题，但成为一门独立的学科则是在20世纪四十年代末至五十年代初。其奠基性工作包括Fritz John 最优性条件（1948），Kuhn-Tucker 最优性条件（1951），和Karush 最优性条件(1939)。近几十年来最优化理论与算法发展十分迅速，应用也越来越广泛。现在已形成一个相当庞大的研究领域。关于最优化理论与方法，狭义的主要指非线性规划的相关内容，而广义的则涵盖：线性规划、非线性规划、动态规划、整数规划、几何规划、多目标规划、随机规划甚至还包括变分、最优控制等动态优化内容。本课程所涉及的内容属于前者。 二、最优化问题的一般形式 1、无约束最优化问题 min ()n x R f x ∈ （） 2、约束最优化问题 min () ()0, ..()0, i i f x c x i E s t c x i I =∈?? ≥∈? （） 这里E 和I 均为指标集。 §数学基础 一、 范数 1. 向量范数 max i x x ∞= （l ∞范数） （） 11n i i x x ==∑ （1l 范数） （） 122 21 ()n i i x x ==∑ （2l 范数） （） 11 ()n p p i p i x x ==∑ （p l 范数） （） 12 ()T A x x Ax = （A 正定） （椭球范数） （） 事实上1－范数、2－范数与∞-范数分别是 p －范数当 p ＝1、2和p →∞时情形。 2．矩阵范数 定义 方阵A 的范数是指与A 相关联并记做A 的一个非负数，它具有下列性质： ① 对于0A ≠都有0A >，而0A =时0A =； ② 对于任意k R ∈，都有kA k A =； ③ A B A B +≤+； ④ AB A B ≤； 若还进一步满足： ⑤ p p Ax A x ≤ 则称之为与向量范数p g 相协调（相容）的方阵范数。若令 max x Ax A x ≠= （这里x 是某一向量范数） （） 可证这样定义的范数是与向量范数g 相协调的，通常称之为由向量范数g 诱导的方阵范数。特别地，对方阵()ij n n A a ?=，有： 11max n ij j i A a ==∑（列和的最大者） （） 1 max n ij i j A a ∞ ==∑（行和的最大者） （） 1 22()T A A A λ=（T A A λ表示T A A 的特征值的最大者） 称为谱范数（注：方阵A 的特征值的模的最大者称为A 的谱半径，记为()A ρ）。 对于由向量诱导的方阵范数，总有： 第9章 多目标函数的优化设计方法 Chapter 9 Multi-object Optimal Design 在实际的机械设计中，往往期望在某些限制条件下，多项设计指标同时达到最优，这类问题称为多目标优化设计问题。与前面单目标优化设计不同的是，多目标优化设计有着多种提法和模式，即数学模型。因此，解决起来要比单目标问题复杂的多。 9.1 多目标最优化模型 9.1.1 问题举例 例9-1 生产计划问题 某工厂生产n （2≥n ）种产品：1号品、2号品、...、n 号品。 已知：该厂生产)...,,2,1(n i i =号品的生产能力是i a 吨/小时； 生产一吨)...,,2,1(n i i =号品可获利润i α元； 根据市场预测，下月i 号品的最大销售量为)...,,2(n i b i =吨； 工厂下月的开工能力为T 小时； 下月市场需要尽可能多的1号品。 问题：应如何安排下月的生产计划，在避免开工不足的条件下，使 工人加班时间尽可能的地少； 工厂获得最大利润； 满足市场对1号品尽可能多地要求。 为制定下月的生产计划，设该厂下月生产i 号品的时间为)...,,1(n i x i =小时。 9.1.2 基本概念 如图9.1所示，两个目标函数f 1,f 2中的若干个设计中，3，4称为非劣解，若 )(min{)(*x f x f j j ≤ S.t ．0)(≤x g u u=1,2,………….m 成立，则称* x 为非劣解。若不存在一个方向，同时满足： 0)(*≤*?s x f (目标函数值下降0)(*≤*?s x g (不破坏约束) 图9.1 则称* x 为约束多目标优化设计问题的K-T 非劣解。这样，多目标优化设计问题的求解过程为：先求出满足K-T 条件的非劣解，再从众多的非劣解确定一个选好解。 多目标优化的数学模型： T r x f x f x f X F V )](),........(),([)(m in 21=-- 人力资源安排的最优化模型 2 1陈才兴 3 黄晓瑜 任冠峰 （韶关学院，广东韶关512005） 1.韶关学院03级信息技术(1)班 2.韶关学院02级应用数学本科班 3.韶关学院03级应用数学本科班 摘要:某大学数学系人力资源安排问题是一个整数规划的最优化问题，通过具体分析数学系现有的技术力量和各方面的约束条件，在问题一的求解中，可以列出一天最大直接收益的整数规划，求得最大的直接收益是42860元；而在问题二的求解中，由于教授一个星期只能工作四天，副教授一个星期只能工作五天，在这样的约束条件下，列出一个星期里最大直接收益的整数规划模型，求得其最大直接收益是198720元。 关键词：技术力量；整数规划；直接收益 1. 问题的提出 数学系的教师资源有限，现有四个项目D C B A 来源于四个不同的客户，工作 的难易程度不一，各项目对有关技术人员的报酬不同。所以： 1. 在满足工作要求的情况下，如何分配数学系现有的技术力量，使得其一天的直接收益最大？ 2. 在教授与副教授工作时间受到约束的条件下，如何分配数学系现有的技术力量，使得其在一个星期里的直接收益最大？ 2.模型的假设 1. 不同技术力量的人每天被安排工作的几率是相等的，且相同职称的个人去什么地方工作是随机的； 2. 客户除了支付规定的工资额外，在工作期间里，还要支付所有相关的花费（如餐费，车费等）； 3. 当天工作当天完成． 3.符号的约定 :i 取1，2，3，4，分别表示教授、副教授、讲师、助教 :j 取1，2，3，4，分别表示D C B A 地 :k 取1到7，分别表示一个星期里的七天 :x ijk i 种职称的人员在j 地第k 天工作的人数 :p ij i 职称的人在j 地工作平均每天的报酬 :b j 表示每天在j 地所需的最多工作人数 :c i 数学系有i 职称的人数 :d i 数学系i 职称的人每天的工资额 j L ij :地所需i 职称技术人员人数的最小值 j U ij :地所需i 职称技术人员人数的最大值 ４.问题的分析 由题意可知各项目对不同职称人员人数都有不同的限制和要求．对客户来说质量保证是关键，而教授相对稀缺，因此各项目对教授的配备有不能少于一定数目的限制．其中由于项目D 技术要求较高，助教不能参加．而D C ,两项目主要工作是在办公室完成， 第六章 最优化数学模型 §1 最优化问题 1．1 最优化问题概念 1．2 最优化问题分类 1．3 最优化问题数学模型 §2 经典最优化方法 2．1 无约束条件极值 2．2 等式约束条件极值 2．3 不等式约束条件极值 §3 线性规划 3．1 线性规划 3．2 整数规划 §4 最优化问题数值算法 4．1 直接搜索法 4．2 梯度法 4．3 罚函数法 §5 多目标优化问题 5．1 多目标优化问题 5．2 单目标化解法 5．3 多重优化解法 5．4 目标关联函数解法 5．5 投资收益风险问题 第六章 最优化问题数学模型 §1 最优化问题 1．1 最优化问题概念 （1）最优化问题 在工业、农业、交通运输、商业、国防、建筑、通信、政府机关等各部门各领域的实际工作中，我们经常会遇到求函数的极值或最大值最小值问题，这一类问题我们称之为最优化问题。而求解最优化问题的数学方法被称为最优化方法。它主要解决最优生产计划、最优分配、最佳设计、最优决策、最优管理等求函数最大值最小值问题。 最优化问题的目的有两个：①求出满足一定条件下，函数的极值或最大值最小值；②求出取得极值时变量的取值。 最优化问题所涉及的内容种类繁多，有的十分复杂，但是它们都有共同的关键因素：变量，约束条件和目标函数。 （2）变量 变量是指最优化问题中所涉及的与约束条件和目标函数有关的待确定的量。一般来说，它们都有一些限制条件（约束条件），与目标函数紧密关联。 设问题中涉及的变量为n x x x ,,,21 ；我们常常也用),,,(21n x x x X 表示。 （3）约束条件 在最优化问题中，求目标函数的极值时，变量必须满足的限制称为约束条件。 例如，许多实际问题变量要求必须非负，这是一种限制；在研究电路优化设 第九章 二次规划 §9.1 二次规划问题 称形如 1m in ()2 T T Q x x H x g x = + 1,,. 1,,T i i e T i i e a x b i m s t a x b i m m ?==??≥=+?? （9.1） 的非线性规划问题为二次规划问题。对二次规划问题，有如下的最优性条件。 定理9.1 设x *是（9.1）的局部极小点，则必存在乘子(1,,)i i m λ*= ，使得 1 0 1,, 0 1,,m i i i T i i i e i e g H x a a x b i m m i m m λλλ**=*** ?+=? ?? ??-==+????≥=+??? ∑ （9.2） 且对于一切满足于： 0, ()T i d a i E I x * =∈ 的n d R ∈，都有0T d Hd ≥。 注：1）上述定理的前后两部分分别对应于一、二阶的必要条件； 2）满足上述条件的d ，都有(,)d S x λ* * ∈； 3）当约束条件均为线性函数时，容易证明： (,)(,) (,F D x X S F D x X L F D x X * * *= =及(,)(,)S x G x λλ**** = 上面给出的是二次规划的必要性条件，下面给出充分性条件。 定理9.2 设x * 是K-T 点，λ* 是相应的Lagrange 乘子，如果对满足 0 0 () 0 () 0 T i T i T i i d a i E d a i I x d a i I x λ* **?=∈?≥∈??=∈>? 且 （9.3） 的一切非零向量n d R ∈，都有0T d Hd >，则x * 是（9.1）的局部严格极小点。 第六章最优化数学模型 §1最优化问题 1．1最优化问题概念 1．2最优化问题分类 1．3最优化问题数学模型 §2经典最优化方法 2．1无约束条件极值 2．2等式约束条件极值 2．3不等式约束条件极值 §3线性规划 3．1线性规划 3．2整数规划 §4最优化问题数值算法 4．1直接搜索法 4．2梯度法 4．3罚函数法 §5多目标优化问题 5．1多目标优化问题 5．2单目标化解法 5．3多重优化解法 5．4目标关联函数解法 5．5投资收益风险问题 第六章最优化问题数学模 §1最优化问题 1．1最优化问题概念 （1）最优化问题在工业、农业、交通运输、商业、国防、建筑、通信、政府机关等各部门各领域的实际工作中，我们经常会遇到求函数的极值或最大值最小值问题，这一类问题我们称之为最优化问题。而求解最优化问题的数学方法被称为最优化方法。它主要解决最优生产计划、最优分配、最佳设计、最优决策、最优管理等求函数最大值最小值问题。 最优化问题的目的有两个：①求出满足一定条件下，函数的极值或最大值最小值； ②求出取得极值时变量的取值。 最优化问题所涉及的内容种类繁多，有的十分复杂，但是它们都有共同的关键因素：变量，约束条件和目标函数。 （2）变量变量是指最优化问题中所涉及的与约束条件和目标函数有关的待确定的量。 一般来说，它们都有一些限制条件（约束条件），与目标函数紧密关联。 设问题中涉及的变量为x1,x2, , x n ；我们常常也用X （x1,x2, ,x n）表示。 3）约束条件 在最优化问题中，求目标函数的极值时，变量必须满足的限制称为约束条件例如，许多实际问题变量要求必须非负，这是一种限制；在研究电路优化设 第六章最优化数学模型 §1 最优化问题 1．1 最优化问题概念 1．2 最优化问题分类 1．3 最优化问题数学模型 §2 经典最优化方法 2．1 无约束条件极值 2．2 等式约束条件极值2．3 不等式约束条件极值 §3 线性规划 3．1 线性规划 3．2 整数规划 §4 最优化问题数值算法4．1 直接搜索法 4．2 梯度法 4．3 罚函数法 §5 多目标优化问题 5．1 多目标优化问题 5．2 单目标化解法 5．3 多重优化解法 5．4 目标关联函数解法5．5 投资收益风险问题 第六章 最优化问题数学模型 §1 最优化问题 1．1 最优化问题概念 （1）最优化问题 在工业、农业、交通运输、商业、国防、建筑、通信、政府机关等各部门各领域的实际工作中，我们经常会遇到求函数的极值或最大值最小值问题，这一类问题我们称之为最优化问题。而求解最优化问题的数学方法被称为最优化方法。它主要解决最优生产计划、最优分配、最佳设计、最优决策、最优管理等求函数最大值最小值问题。 最优化问题的目的有两个：①求出满足一定条件下，函数的极值或最大值最小值；②求出取得极值时变量的取值。 最优化问题所涉及的内容种类繁多，有的十分复杂，但是它们都有共同的关键因素：变量，约束条件和目标函数。 （2）变量 变量是指最优化问题中所涉及的与约束条件和目标函数有关的待确定的量。一般来说，它们都有一些限制条件（约束条件），与目标函数紧密关联。 设问题中涉及的变量为n x x x ,,,21 ；我们常常也用),,,(21n x x x X =表示。 （3）约束条件 在最优化问题中，求目标函数的极值时，变量必须满足的限制称为约束条件。 例如，许多实际问题变量要求必须非负，这是一种限制；在研究电路优化设计问题时，变量必须服从电路基本定律，这也是一种限制等等。在研究问题时，这些限制我们必须用数学表达式准确地描述它们。 用数学语言描述约束条件一般来说有两种： 等式约束条件 m i X g i ,,2,1,0)( == 不等式约束条件 r i X h i ,,2,1, 0)( =≥ 或 r i X h i ,,2,1, 0)( =≤ 注：在最优化问题研究中，由于解的存在性十分复杂，一般来说，我们不考虑不等式约束条件0)(>X h 或0)( 第七章多目标优化问题的求解 优化问题按照目标函数的数量，可以分为单目标优化问题和多目标优化问题，前面我们讲过的线性优化就是一个单目标优化问题，对单目标优化问题进一步突破，将目标函数扩展为向量函数后，问题就转化为多目标优化问题。本节将简要介绍多目标最优化问题的建模与求解方法。 1、多目标优化模型 多目标优化问题一般表示为 ..()min () s t J ≤= x G x 0 x F 其中121()[(),(),,()]T f f f =F x x x x ，下面将通过例子演示多目标优化问题的建模。 例1 设某商店有123,,A A A 三种糖果，单价分别为4,2.8和2.4元/kg ，现在 要举办一次茶话会，要求买糖果的钱不超过20元，但糖果的总重量不少于6kg ， 1A 和2A 两种糖果的总重量不低于3kg ，应该如何确定最好的买糖方案。 分析：首先应该确定目标函数如何选择的问题，本例中，好的方案意味着少花钱多办事，这应该是对应两个目标函数，一个是花钱最少，一个是买的糖果最重，其他的可以认为是约束条件。当然，这两个目标函数有些矛盾，下面考虑如何将这个问题用数学描述。 设123,,A A A 三种糖果的购买重量分别为123,,x x x kg ，这时两个目标函数分别为花钱：1123min ()4 2.8 2.4f x x x =++x ，糖果总重量：2123max ()f x x x =++x ，如果统一用最小值问题表示，则有约束的多目标优化问题可以表示为 123123123123121234 2.8 2.4min -4 2.8 2.4206.. +3,,0 x x x x x x x x x x x x s t x x x x x ++?? ??++??++≤??++≥?? ≥??≥?（）模型建立以后，可以考虑用后面的方法进行求解。 最优化问题的数学模型及其分类 例1.1.1 产品组合问题 某公司现有三条生产线用来生产两种新产品，其主要数据如表1-1所示。请问如何生产可以让公司每周利润最大？ 表1-1 设每周生产的产品一和产品二 的产量分别为1x 和2x ，则每周的生产利润为：2153x x z +=。由于每周的产品生产受到三条生产线的可用时间的限制，因此1x ，2x 应满足以下条件： ?????? ?≥≤+≤≤0, 18231224212121 x x x x x x 故上述问题的数学模型为 2153max x x z += . .t s ?????? ?≥≤+≤≤0, 18231224212121 x x x x x x 其中max 是最大化（maximize ）的英文简称，??t s 是受约束于（subject to ）的简写。 例1.1.2 把一个半径为１的实心金属球熔化后，铸成一个 实心圆柱体，问圆柱体取什么尺寸才能使它的表面积最小？ 设圆柱体的底面半径为r ，高为h ，则该问题的数学模型为： ??? ??=? ?+=ππππ3 422min 22 h r t s r rh S 其中min 是最小化（minimize ）的简写。 通过以上二例，可以看出最优化问题的数学模型具有如下结构： （１） 决策变量（decision variable ）：即所考虑问题 可归结为优选若干个被称为参数或变量的量 n x x x ,,,21 ，它们都取实数值，它们的一组值构 成了一个方案。 （２） 约束条件（constraint condition ）：即对决策 变量n x x x ,,,21 所加的限制条件，通常用不等式或等式表示为： ()(),,,2,1, 0,,,,,2,1, 0,,,2121l j x x x h m i x x x g n j n i ===≥ （３） 目标函数（objective function ）和目标：如使 利润达到最大或使面积达到最小，通常刻划为极大化（maximize ）或极小化（minimize ）一个实值函数()n x x x f ,,21 因此，最优化问题可理解为确定一组决策变量在满足约束条件下，寻求目标函数的最优。 注意到极大化目标函数()n x x x f ,,21相当于极小化 ()n x x x f ,,21-，因此，约束最优化问题的数学模型一般可 表示为： () ()()()?? ? ??===≥??l j x x x h m i x x x g t s x x x f n j n i n ,,2,1,0,,,1.1.1,,2,1,0,,,,,min 212121 若记()T n x x x x ,,21=，则（1.1.1）又可写成：最优化理论与算法(第八章)
matlab多目标优化模型教程
流线优化模型与算法研究及应用
基于数学模型的网络优化方法研究
多目标优化模型
遗传算法优化的BP神经网络建模[精选.]
最优化理论与算法 fibonacci法
图论与网络优化课程设计_Matlab实现
多目标最优化问题全面介绍
最优化理论与算法
最优化理论与算法
多目标函数的优化设计方法
人力资源安排的最优化模型
多目标最优化模型
最优化理论与算法(第九章)
多目标最优化模型
多目标最优化数学模型
多目标优化问题(over)
最优化问题的数学模型及其分类