|
|||||
|
|
| 时变网络中零等待时间最短路问题的一个对偶算法 | |
| 作者姓名： | 朱建明 沙丹 |
| 作者单位： | 1. 上海师范大学,数理信息学院,上海,200234 2. 上海对外贸易学院,国际经贸学院,上海,201620 |
| 摘 要： | 时变最短路问题是最短路问题的一个推广.假设图G=(V,A)是一个有向图且有唯一的源点t,图G中的每条弧(i,j)∈A都附有两个参数:弧的传送时间b(i,j,u)和弧的传送费用c(i,j,u),它们都是在弧的顶点i上的出发时间u的函数.找出从源点到其它各点的最短路,即最小费用的路,并且要求每条最短路的传送时间不能超过给定的时间限制T.假设除源点外,在其它任何顶点都不能等待,b(i,j,u)是满足u b(i,j,u)≥0( (i,j)∈A,u=0,1,…,T)的任意整数,c(i,j,u)是任意的非负整数.给出了该问题的原规划和对偶规划,提出了一个最优性条件和一个对偶算法,并用一个数值例子来阐述算法. |
| 关 键 词： | 最短路 对偶算法 时变网络 最优化 shortest path dual algorithm time-varying network optimization 时变网络 等待时间 最短路问题 对偶算法 constraints waiting time shortest path problem numerical example algorithm optimality condition develop dual linear programming form nonnegative integers times costs subject |
| 文章编号： | 1000-5137(2008)01-0014-08 |
| 修稿时间： | 2007-09-10 |
| 本文献已被 维普 万方数据 等数据库收录！ | |
| 点击此处可从《上海师范大学学报(自然科学版)》浏览原始摘要信息 | |
| 点击此处可从《上海师范大学学报(自然科学版)》下载全文 | |