Dijkstra算法是很有代表性的最短路算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等
注意:你的指定点开始的问题,直接从把下面的东西看完后,应用(6)就可以解决,任意开始点的话,就把所有点都指定一下就行了。。。
再补充一个,这个算法一般图论书上都有,但是写的非常之高深莫测,看不懂的。。。建议去看清华大学的数据结构与算法这本书上的算法,(蓝色封皮的)
设S为最短距离已确定的顶点集(看作红点集),V-S是最短距离尚未确定的顶点集(看作蓝点集)。
①初始化
初始化时,只有源点s的最短距离是已知的(SD(s)=0),故红点集S=,蓝点集为空。
②重复以下工作,按路径长度递增次序产生各顶点最短路径
在当前蓝点集中选择一个最短距离最小的蓝点来扩充红点集,以保证算法按路径长度递增的次序产生各顶点的最短路径。
当蓝点集中仅剩下最短距离为∞的蓝点,或者所有蓝点已扩充到红点集时,s到所有顶点的最短路径就求出来了。
注意:
①若从源点到蓝点的路径不存在,则可假设该蓝点的最短路径是一条长度为无穷大的虚拟路径。
②从源点s到终点v的最短路径简称为v的最短路径;s到v的最短路径长度简称为v的最短距离,并记为SD(v)。
(3)在蓝点集中选择一个最短距离最小的蓝点k来扩充红点集
根据按长度递增序产生最短路径的思想,当前最短距离最小的蓝点k的最短路径是:
源点,红点1,红点2,…,红点n,蓝点k
距离为:源点到红点n最短距离+<红点n,蓝点k>边长
为求解方便,设置一个向量D[0..n-1],对于每个蓝点v∈ V-S,用D[v]记录从源点s到达v且除v外中间不经过任何蓝点(若有中间点,则必为红点)的"最短"路径长度(简称估计距离)。
若k是蓝点集中估计距离最小的顶点,则k的估计距离就是最短距离,即若D[k]=min,则D[k]=SD(k)。
初始时,每个蓝点v的D[c]值应为权w<s,v>,且从s到v的路径上没有中间点,因为该路径仅含一条边<s,v>。
注意:
在蓝点集中选择一个最短距离最小的蓝点k来扩充红点集是Dijkstra算法的关键
(4)k扩充红点集s后,蓝点集估计距离的修改
将k扩充到红点后,剩余蓝点集的估计距离可能由于增加了新红点k而减小,此时必须调整相应蓝点的估计距离。
对于任意的蓝点j,若k由蓝变红后使D[j]变小,则必定是由于存在一条从s到j且包含新红点k的更短路径:P=<s,…,k,j>。且D[j]减小的新路径P只可能是由于路径<s,…,k>和边<k,j>组成。
所以,当length(P)=D[k]+w<k,j>小于D[j]时,应该用P的长度来修改D[j]的值。
(5)Dijkstra算法
Dijkstra(G,D,s){
//用Dijkstra算法求有向网G的源点s到各顶点的最短路径长度
//以下是初始化 *** 作
S=;D[s]=0; //设置初始的红点集及最短距离
for( all i∈ V-S )do //对蓝点集中每个顶点i
D[i]=G[s][i]; //设置i初始的估计距离为w<s,i>
//以下是扩充红点集
for(i=0;i<n-1;i++)do{//最多扩充n-1个蓝点到红点集
D[k]=min; //在当前蓝点集中选估计距离最小的顶点k
if(D[k]等于∞)
return; //蓝点集中所有蓝点的估计距离均为∞时,
//表示这些顶点的最短路径不存在。
S=S∪; //将蓝点k涂红后扩充到红点集
for( all j∈V-S )do //调整剩余蓝点的估计距离
if(D[j]>D[k]+G[k][j])
//新红点k使原D[j]值变小时,用新路径的长度修改D[j],
//使j离s更近。
D[j]=D[k]+G[k][j];
}
}
(6)保存最短路径的Dijkstra算法
设置记录顶点双亲的向量P[0..n-1]保存最短路径:
当顶点i无双亲时,令P[i]=-1。
当算法结束时,可从任一P[i]反复上溯至根(源点)求得顶点i的最短路径,只不过路径方向正好与从s到i的路径相反。
。
Dijkstra算法的时间复杂度为O(n2)
参考资料:
如果还没解决你的问题,可以加我百度HI账号。
这个你最好先把两两点间的最短路算出来 并用一组0-1变量来表示某个点能不能覆盖到另一个点 比如说是c
那么下面就用这个模型求解 不过这个问题很难写出线性的模型 求解以后自己注意检查一下 一般只能作为参考
sets:
p/18/:demand,x;
pp(p,p):c,supply;
endsets
min=@sum(p:x);
@for(p(j):@sum(p(i):x(i)c(i,j))>=1);
@for(p(j):@sum(p(i):supply(i,j))=demand(j));
@for(p(i):@sum(p(j):supply(i,j))>=100;@sum(p(j):supply(i,j))<=300);
@for(pp:c>=@if(supply#gt#0,1,0));
@for(p:@bin(x));
首先不可能一句一句的讲语法 需要你自己学一下lingo
只说一下主要的模型 首先他calc段是给出了具体的w的数据
然后主要模型的目标自然就是路线最短 这里面x表示的选择的路线 x(i,j)是0-1变量 用来表示i到j的路线是否选择
下面的第一个约束就是对于非起点和非终点的这些点来说 进这点的路线数和出这点的路线数是相同的
最后就是出起点的路线数为1 进起点的路线数为0 进终点的路线数为0
自己看看教程就懂了 lingo每句后面都要加分号 lindo不要加分号 另外lindo 有st lindo乘号不用写 但是能直接做的东西少于lingo的能力
具体要你自己去看自己去写 光问有什么不同没什么意义
LINDO是一种专门用于求解数学规划问题的软件包。由于LINDO执行速度很快、易于方便输入、求解和分析数学规划问题。因此在数学、科研和工业界得到广泛应用。LINDO主要用于解线性规划、非线性规划、二次规划和整数规划等问题。也可以用于一些非线性和线性方程组的求解以及代数方程求根等。LINDO中包含了一种建模语言和许多常用的数学函数(包括大量概论函数),可供使用者建立规划问题时调用。
LINDO 61是求解线性、整数和二个规划问题的多功能工具。LINDO 61互动的环境可以让你容易得建立和求解最佳化问题,或者你可以将LINDO的最佳化引擎挂在您己开发的程序内。而另一方面,LINDO也可以用来解决一些复杂的二次线性整数规划方面的实际问题。如在大型的机器上,LINDO被用来解决一些拥有超过50,000各约束条件和200,000万个变量的大规模复杂问题
LINGO则用于求解非线性规划(NLP—NON—LINEAR PROGRAMMING)和二次规则(QP—QUARATIC PROGRAMING)其中LINGO 60学生版最多可版最多达300个变量和150个约束的规则问题,其标准版的求解能力亦再10^4量级以上。虽然LINDO和LINGO不能直接求解目标规划问题,但用序贯式算法可分解成一个个LINDO和LINGO能解决的规划问题。
运用LINDO软件编写下列程序并运行 实验步骤 (1)在模型窗口中输入一个LP 使用Lingo软件编制程序基于产大于销的不平衡模型,即 则运输问题的数学模型为: 的自然形式(数学形式)非常相似,几乎没有什么差别,因此几乎不需要专门学习就可以掌握。 在Lindo中有一些可帮助寻找错误的功能,其中之一就是菜单命令“Report
结果:x=20;y=20; 利润100
lingo程序:
!设生产甲x台,生产议y台;
!目标函数;
max=3x+2y;
!约束条件;
!原料;
2x+3y<=100;
!工时;
4x+2y<=120;
!台数;
x>=5;y>=10;
运行结果:
Global optimal solution found
Objective value: 1000000
Total solver iterations: 2
Variable Value Reduced Cost
X 2000000 0000000
Y 2000000 0000000
Row Slack or Surplus Dual Price
1 1000000 1000000
2 0000000 02500000
3 0000000 06250000
4 1500000 0000000
5 1000000 0000000
灵敏度分析结果:
Ranges in which the basis is unchanged:
Objective Coefficient Ranges
Current Allowable Allowable
Variable Coefficient Increase Decrease
X 3000000 1000000 1666667
Y 2000000 2500000 05000000
Righthand Side Ranges
Row Current Allowable Allowable
RHS Increase Decrease
2 1000000 6000000 2000000
3 1200000 4000000 4000000
4 5000000 1500000 INFINITY
5 1000000 1000000 INFINITY
结果分析就自己看着分析吧,上面都有了!
前言
第1章引言
§11优化模型的基本概念
§111优化模型的一般形式
§112可行解与最优解
§113优化模型的基本类型
§12优化问题的建模实例
§121线性规划模型
§122二次规划模型
§123非线性规划模型
§124整数规划模型
§125其它优化模型
§13LINDO/LINGO 软件简介
§131LINDO/LINGO软件的基本功能
§132LINDO/LINGO软件的求解过程
§133建立LINDO/LINGO优化模型需要注意的几个基本问题
习题一
第2章LINDO软件的基本使用方法
§21LINDO入门
§211LINDO软件的安装过程
§212编写一个简单的LINDO程序
§213一些注意事项
§22敏感性分析
§23整数线性规划的求解
§24 二次规划的求解
§25LINDO的主要菜单命令
§26 LINDO命令窗口
§27 LINDO命令脚本文件
§28 附录:MPS格式数据文件
习题二
第3章LINGO软件的基本使用方法
§31LINGO入门
§311LINGO软件的安装过程和主要特色
§312在LINGO中使用LINDO模型
§313编写一个简单的LINGO程序
§32在LINGO中使用集合
§321集合的基本用法和LINGO模型的基本要素
§322基本集合与派生集合
§323稠密集合与稀疏集合
§324集合的使用小结
§33运算符和函数
§331运算符及其优先级
§332基本的数学函数
§333集合循环函数
§334集合 *** 作函数
§335变量定界函数
§336财务会计函数
§337概率论中的相关函数
§338文件输入输出函数
§339结果报告函数
§3310其他函数
§34LINGO的主要菜单命令
§341文件(File)主菜单
§342编辑(Edit)主菜单
§343LINGO系统(LINGO)主菜单
§35LINGO命令窗口
习题三
第4章 LINGO软件与外部文件的接口
§41通过WINDOWS剪贴板传递数据
§411粘贴命令的用法
§412特殊粘贴命令的用法
§42通过文本文件传递数据
§421通过文本文件输入数据
§422通过文本文件输出数据
§43通过电子表格文件传递数据
§431在LINGO中使用电子表格文件的数据
§432将LINGO模型嵌入、链接到电子表格文件中
§44LINGO命令脚本文件
§45附录:LINGO出错信息
习题四
第5章生产与服务运作管理中的优化问题
51生产与销售计划问题
§511问题实例
§512建立模型
§513求解模型
§52有瓶颈设备的多级生产计划问题
§521问题实例
§522建立模型
§523求解模型
§53下料问题
§531钢管下料问题
§532易拉罐下料问题
§54面试顺序与消防车调度问题
§541面试顺序问题
§542消防车调度问题
§55飞机定位和飞行计划问题
§551飞机的精确定位问题
§552飞行计划问题
习题五
第六章 经济与金融中的优化问题
§61 经济均衡问题及其应用
§611单一生产商、单一消费者的情形
§612两个生产商、两个消费者的情形
§613拍卖与投标问题
§614交通流均衡问题
§62 投资组合问题
§621基本的投资组合模型
§622存在无风险资产时的投资组合模型
§623考虑交易成本的投资组合模型
§624利用股票指数简化投资组合模型
625其他目标下的投资组合模型
§63 市场营销问题
§631新产品的市场预测
§632产品属性的效用函数
§633机票的销售策略
习题六
第十二章数学建模竞赛中的部分优化问题
§12.1 一个飞行管理问题
§1211问题描述
§1212模型1及求解
§1213模型2及求解
§12.2钢管订购和运输
§1221问题描述
§1222运费矩阵的计算模型
§1223运输量计算模型及求解
§12.3露天矿生产的车辆安排
§1231问题描述
§1232运输计划模型及求解
§12.4 空洞探测
§1241问题描述
§1242优化模型及求解
习题十二
你去这个网页看看吧>
以上就是关于在lingo的最小路径算法中,如何控制所走的路径全部的内容,包括:在lingo的最小路径算法中,如何控制所走的路径、lingo软件求解数学建模。、lingo中11个城市,从1到11的最短路问题等相关内容解答,如果想了解更多相关内容,可以关注我们,你们的支持是我们更新的动力!
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)