当期目录

2014年 第18卷 第3期    刊出日期：2014-09-15

上一期    下一期

运筹学

广义交替近似梯度算法的线性收敛分析

万芮, 徐姿

2014, 18(3):  1-12. 

摘要 ( 1628 )   PDF (668KB) ( 1024 )  

参考文献 | 相关文章 | 多维度评价

针对两个可分凸函数的和在线性约束下的极小化问题, 在交替方向法的框架下, 提出广义的交替近似梯度算法. 在一定的条件下, 该算法具有全局及线性收敛性. 数值实验表明该算法有好的数值表现.

恰有两个Q-主特征值的三圈图

陈琳, 黄琼湘

2014, 18(3):  13-32. 

摘要 ( 903 )   PDF (1637KB) ( 771 )  

参考文献 | 相关文章 | 多维度评价

图G的无符号拉普拉斯 矩阵定义为图G的邻接矩阵与度对角矩阵的和, 其特征值称为图G的Q-特征值. 图G的一个Q-特征值称为Q-主特征值, 如果它有一个特征向量其分量的和不等于零. 确定了所有恰有两个Q-主特征值的三圈图.

可分离凸优化问题的非精确平行分裂算法

杨赟, 彭拯

2014, 18(3):  33-46. 

摘要 ( 1185 )   PDF (526KB) ( 602 )  

参考文献 | 相关文章 | 多维度评价

针对一类可分离凸优化问题提出了一种非精确平行分裂算法. 该算法充分利用了所求解问题的可分离结构, 并对子问题进行非精确求解. 在适当的条件下, 证明了所提出的非精确平行分裂算法的全局收敛性, 初步的数值实验说明了算法有效性.

无预警紧急疏散中公交车辆路径的确定方法

何胜学

2014, 18(3):  47-59. 

摘要 ( 1252 )   PDF (526KB) ( 668 )  

参考文献 | 相关文章 | 多维度评价

针对无预警式紧急疏散中公交救援车辆的最佳路径确定问题, 提出了一个非线性混合整数规划模型. 模型不仅考虑了有接收能力限制的多避难所系统，还对如何处理具有不同载客上限的公交救援车进行了分析. 利用添加了虚拟路段和节点的时空网络，在以加权的综合疏散时间最小为目标的同时实现了疏散伤亡最小化. 通过分析实际疏散的实施过程，得到了一种产生模型可行解的有效方法. 通过将时间滚动式的流量加载模式与经典遗传算法相结合，给出了新模型的实用解法. 最后，通过算例验证了模型和算法的有效性.

二次规划逆问题的牛顿方法

程聪, 张立卫

2014, 18(3):  60-70. 

摘要 ( 1145 )   PDF (535KB) ( 815 )  

参考文献 | 相关文章 | 多维度评价

针对二次规划逆问题, 将其表达为带有互补约束的锥约束优化问题. 借助于对偶理论, 将问题转化为变量更少的线性互补约束非光滑优化问题. 通过扰动的方法求解转化后的问题并证明了收敛性. 采用非精确牛顿法求解扰动问题, 给出了算法的全局收敛性与局部二阶收敛速度. 最后通过数值实验验证了该算法的可行性.

求解0-1线性整数规划问题的有界单纯形法

张惠珍, 魏欣, 马良

2014, 18(3):  71-78. 

摘要 ( 1274 )   PDF (611KB) ( 906 )  

参考文献 | 相关文章 | 多维度评价

提出了一种求解0-1线性整数规划问题的有界单纯形法, 不仅通过数学论证, 讨论了该方法的合理性, 奠定了其数学理论基础, 而且通过求解无容量设施选址问题, 验证了该方法的可行性. 在此基础上, 就该有界单纯形法的不足和存在的问题, 给出了进一步改进的途径和手段.

求解图像分割CV模型的BB算法

彭亚新, 陈飒飒, 沈超敏, 应时辉

2014, 18(3):  79-87. 

摘要 ( 1139 )   PDF (1452KB) ( 742 )  

参考文献 | 相关文章 | 多维度评价

给出图像分割的一种新算法-----BB算法. 该方法的优点在于利用迭代过程中当前点和前一点的信息确定搜索步长, 从而更有效地搜索最优解. 为此, 首先通过变分水平集方法将CV模型转化为最优化问题; 其次, 将BB算法引入该优化问题进行求解; 然后, 对BB算法进行收敛性分析, 为该算法应用在CV模型中提供了理论依据; 最后将该方法与已有的最速下降法、 共轭梯度法的分割结果进行比较. 结果表明, 跟其他两种方法相比, BB算法在保证较好分割效果的前提下, 提高了算法的速度和性能.

Knight不确定下考虑保险和退休的最优消费-投资和遗产问题研究

刘宏建, 费为银, 朱永王, 郑安曼

2014, 18(3):  88-98. 

摘要 ( 946 )   PDF (822KB) ( 772 )  

参考文献 | 相关文章 | 多维度评价

研究在Knight不确定环境下, 考虑投资者遗产和保险, 在三种不同借款约束下的最优消费与投资问题. 借助于倒向随机微分方程~(BSDE)~理论求出了投资者最优消费和投资策略的显式表达式． 最后结合数值分析, 给出含糊与含糊态度对最优消费和投资决策的影响．

二阶数乘问题的一个最优算法

万龙

2014, 18(3):  99-103. 

摘要 ( 847 )   PDF (773KB) ( 536 )  

参考文献 | 相关文章 | 多维度评价

研究一个有趣的组合优化问题------二阶数乘问题. 问题描述如下: 给定~$n\geq 2$~个正整数~$a_1, a_2, \cdots, a_n$, 设$\pi$为$\{1,2,\cdots,n\}$的一个置换， 表示该问题的一个解，试图找到一个置换~$\pi$~以至~$\sum^n_{i=1}a_{\pi_{i}} a_{\pi_{i+1}}$~最小, 在这里~$\pi_{n+1}=\pi_1$. 给出了一个算法复杂度为\,$O(n\log{n})$\,的最优算法.

超图的Alcuin数与其横贯数的关系

单而芳, 孔鹭

2014, 18(3):  104-110. 

摘要 ( 954 )   PDF (537KB) ( 908 )  

参考文献 | 相关文章 | 多维度评价

1000多年前, 英国著名学者Alcuin曾提出过一个古老的渡河问题, 即狼、羊和卷心菜的渡河问题. 最近, Prisner和Csorba等考虑了一般``冲突图"上的渡河问题. 将这一问题推广到超图$H=(V,\mathcal{E})$\,上, 考虑一类情况更一般的运输计划问题. 现在监管者 欲运输超图中的所有点\,(代表``items")\,渡河, 这里$V$的点子 形成超边 当且仅当这些点代表的``items"在无人监管的情况下不能留在一起. 超图$H$的Alcuin数是指超图$H$具有可行运输方案\,(即把$V$的点代表的``items" 全部运到河对岸)\,时船的最小容量. 给出了 $r$-一致完全二部超图和它的伴随超图, 以及$r$-一致超图的Alcuin数, 同时证明了判断$r$-一致超图是否为小船图是NP 困难的.

多目标优化正则条件的一个注记

赵克全, 杨新民

2014, 18(3):  111-115. 

摘要 ( 928 )   PDF (413KB) ( 598 )  

参考文献 | 相关文章 | 多维度评价

给出带不等式约束的非光滑多目标优化问题正则条件的一个例子. 通过该例，指出\linebreak 最近由Burachik和Rizvi利用线性化锥提出的可微多目标优化问题的正则条件不能利用Clarke\linebreak 导数推广到非光滑情形.

不含三角形图的正常染色路和正常染色圈

丁录顺, 王光辉, 颜谨

2014, 18(3):  116-120. 

摘要 ( 1115 )   PDF (460KB) ( 593 )  

参考文献 | 相关文章 | 多维度评价

图G为边染色图, 对G中的任一顶点v, 定义v的色度d^c(v): $G$中与顶点$v$相关联的边中不同染色的数目. 用$\delta^c(G)$\,表示图$G$的最小色度, 即$\delta^c(G)={\rm min}\{d^c(v):v\in G\}$. 若图$G$为不含三角形的边染色图, 且$\delta^c(G)\geq 2$, 则$G$含长为$4d 2$的正常染色路或长至少为$2d-2$的正常染色圈.