当期目录

2011年 第15卷 第3期    刊出日期：2011-09-20

上一期    下一期

论文

一类多目标优化问题的有效性

赵克全 杨新民

2011, (3):  1-8. 

摘要 ( 1203 )   PDF (152KB) ( 257 )  

相关文章 | 多维度评价

本文研究了一类带不等式约束的多目标优化问题，给出了该类问题的有效解的一些充分必要条件，在适当条件下利用线性标量化方法证明了其有效解和真有效解的等价性。本文的主要结论是对最近一些文献中相应结果的改进与推广。

运筹学

一类多目标优化问题的有效性

赵克全 杨新民

2011, 15(3):  1-8. 

摘要 ( 3193 )   PDF (152KB) ( 1880 )  

相关文章 | 多维度评价

本文研究了一类带不等式约束的多目标优化问题，给出了该类问题的有效解的一些充分必要条件，在适当条件下利用线性标量化方法证明了其有效解和真有效解的等价性。本文的主要结论是对最近一些文献中相应结果的改进与推广。

论文

大规模无约束优化的一族有限存储BFGS类算法

钱小燕, 施庆生, 刘浩, 石岿然

2011, (3):  9-18. 

摘要 ( 1497 )   PDF (189KB) ( 245 )  

相关文章 | 多维度评价

本文尝试在有限存储类算法中利用目标函数值所提供的信息. 我们首先利用插值条件构造了一个新的二次函数逼近目标函数,得到了一个新的弱割线方程，然后将此弱割线方程与袁\cite{yuan1991}的弱割线方程相结合，给出了一族包括标准LBFGS的有限存储BFGS类算法，证明了这族算法的收敛性. 从标准试验函数库CUTE中选择试验函数进行了数值试验, 试验结果表明这族算法的数值表现都与标准LBFGS类似.

运筹学

大规模无约束优化的一族有限存储LBFGS类算法

钱小燕, 施庆生, 刘浩, 石岿然

2011, 15(3):  9-18. 

摘要 ( 5020 )   PDF (187KB) ( 1793 )  

相关文章 | 多维度评价

本文尝试在有限存储类算法中利用目标函数值所提供的信息. 我们首先利用插值条件构造了一个新的二次函数逼近目标函数,得到了一个新的弱割线方程，然后将此弱割线方程与袁\cite{yuan1991}的弱割线方程相结合，给出了一族包括标准LBFGS的有限存储BFGS类算法，证明了这族算法的收敛性. 从标准试验函数库CUTE中选择试验函数进行了数值试验, 试验结果表明这族算法的数值表现都与标准LBFGS类似.

论文

给定顶点数和边数的连通图的Q-谱半径

陈琳, 黄琼湘

2011, (3):  19-28. 

摘要 ( 1679 )   PDF (235KB) ( 282 )  

相关文章 | 多维度评价

图的无符号拉普拉斯矩阵是图的邻接矩阵和度对角矩阵的和, 其特征值记为$q_1\geq q_2\geq \cdots \geq q_n$. 设$\mathscr{C}(n,m)$是由$n$个顶点$m$条边的连通图构成的集合, 这里$1\leq n-1\leq\ m \leq\bigl(\begin{smallmatrix}n\\2\end{smallmatrix}\bigr)$. 图$G^\star \in \mathscr{C}(n,m)$叫做最大图, 如果对于任意的$G\in \mathscr{C}(n,m)$都有$\ q_1(G^\star )\geq q_1(G)$ 成立. 在这篇文章中, 我们证明了对任意给定的正整数 $a=m-n+1$, 如果 $n>-\frac{1}{2}+a+\frac{1}{2}\sqrt{1+12a+12a^2}$, 那么$n-\frac{1}{2}+a+\frac{1}{2}\sqrt{1+12a+12a^2}$, 就有$q_1(G)

运筹学

给定顶点数和边数的连通图的Q-谱半径的界

陈琳 黄琼湘

2011, 15(3):  19-28. 

摘要 ( 2446 )   PDF (235KB) ( 1290 )  

相关文章 | 多维度评价

图的无符号拉普拉斯矩阵是图的邻接矩阵和度对角矩阵的和, 其特征值记为$q_1\geq q_2\geq \cdots \geq q_n$. 设$\mathscr{C}(n,m)$是由$n$个顶点$m$条边的连通图构成的集合, 这里$1\leq n-1\leq\ m \leq\bigl(\begin{smallmatrix}n\\2\end{smallmatrix}\bigr)$. 图$G^\star \in \mathscr{C}(n,m)$叫做最大图, 如果对于任意的$G\in \mathscr{C}(n,m)$都有$\ q_1(G^\star )\geq q_1(G)$ 成立. 在这篇文章中, 我们证明了对任意给定的正整数 $a=m-n+1$, 如果 $n>-\frac{1}{2}+a+\frac{1}{2}\sqrt{1+12a+12a^2}$, 那么$n-\frac{1}{2}+a+\frac{1}{2}\sqrt{1+12a+12a^2}$, 就有$q_1(G)

 关于可嵌入曲面图的列表(d,1)-全标号问题

于永, 张欣, 刘桂真

2011, (3):  29-37. 

摘要 ( 1336 )   PDF (154KB) ( 343 )  

相关文章 | 多维度评价

 图的(d,1)-全标号问题最初是由Havet等人提出的.
在本文中，我们考虑了可嵌入曲面图的列表(d,1)-全标号问题,并证明了其列表(d,1)-全标号数不超过$\Delta(G)+2d.$

关于可嵌入曲面图的列表(d,1)-全标号问题

于永, 张欣, 刘桂真

2011, 15(3):  29-37. 

摘要 ( 2476 )   PDF (154KB) ( 1240 )  

相关文章 | 多维度评价

图的(d,1)-全标号问题最初是由Havet等人提出的. 在本文中，我们考虑了可嵌入曲面图的列表(d,1)-全标号问题,并证明了其列表(d,1)-全标号数不超过$\Delta(G)+2d.$  

 1-平面图的线性荫度

张欣, 刘桂真, 吴建良

2011, 15(3):  38-44. 

摘要 ( 2598 )   PDF (132KB) ( 1387 )  

相关文章 | 多维度评价

证明了最大度$\Delta\geq 33$的1-平面图的线性荫度为$\lceil\Delta/2\rceil$

m重似星树的谱半径

吴廷增, 扈生彪

2011, 15(3):  45-50. 

摘要 ( 2843 )   PDF (156KB) ( 1342 )  

相关文章 | 多维度评价

仅有一个顶点的度大于2的树称为似星树.
在一棵似星树的每个一度点粘接一棵似星树构成的图称为$m$重似星树.
 Gutman 和L. Shi给出了似星树谱半径的一个界.
在本文中我们给出了另外一个更简洁的证明方法并做了深入的讨论,
同时给出了$m$重似星树谱半径的一个最好界.

完全图中的正常染色的路和圈

王光辉, 周珊

2011, 15(3):  51-56. 

摘要 ( 2376 )   PDF (151KB) ( 1342 )  

相关文章 | 多维度评价

令$K_{n}^{c}$表示$n$ 个顶点的边染色完全图.
令 $\Delta^{mon}
(K_{n}^{c})$表示$K^c_{n}$的顶点上关联的同种颜色的边的最大数目.
如果$K_{n}^{c}$中的一个圈（路）上相邻的边染不同颜色，则称它为正常染色的.
B. Bollob\'{a}s和P. Erd\"{o}s (1976) 提出了如下猜想：若 $\Delta^{{mon}}
(K_{n}^{c})<\lfloor \frac{n}{2} \rfloor$, 则$K_{n}^{c}$中含有一个正常染
色的Hamilton圈. 这个猜想至今还未被证明.我们研究了上述条件下的正常染色的路和圈.  

 含有两个非临界点的强连通定向图的弧数

林上为, 李春芳, 王世英

2011, 15(3):  57-61. 

摘要 ( 2141 )   PDF (149KB) ( 1186 )  

相关文章 | 多维度评价

证明顶点数为$n\geq 4$,弧数为$m\geq {n-1 \choose 2}+3$的强连通定向
图$D$中存在两点$u^*$、!$v^*$,使得$D-u^*$和$D-v^*$都是强连通的, 并用例子说明这里所给的
关于弧数的下界是紧的.

有使用限制的二台机器流水作业问题

杨名, 鲁习文

2011, 15(3):  62-69. 

摘要 ( 3247 )   PDF (298KB) ( 1504 )  

相关文章 | 多维度评价

本文研究了机器有使用限制的二台机器流水作业排序问题,目标为最小化最大完工时间，工件加工可以被机器的不可用时间段中断。我们讨论了两台机器上均有使用限制离线问题的可近似情形，并给出了性能比为3/2的近似算法。同时我们还考虑了在第二台机器上存在一个不可用时间段情况下的半在线问题，给出了一个竞争比为3/2的半在线算法。

支持向量顺序回归机的统计学习基础

阳红英, 杨志霞

2011, 15(3):  70-80. 

摘要 ( 2227 )   PDF (343KB) ( 1354 )  

相关文章 | 多维度评价

对处理顺序回归问题的支持向量顺序回归机的统计学习理论基础进行研究.
首先, 利用结构风险最小化原则推导出一种顺序回归机,
称之为结构风险最小化顺序回归机, 其次,
证明了结构风险最小化顺序回归机与支持向量顺序回归机解之间的关系.
进一步从统计学习的角度证明了支持向量顺序回归机是结构风险最小化原则的一种直接实现,
并给出了惩罚参数C的含义.

有多种运输方式的供应链排序问题

王磊, 王国庆, 易余胤

2011, 15(3):  81-94. 

摘要 ( 2874 )   PDF (396KB) ( 1478 )  

相关文章 | 多维度评价

本文考虑了由一个制造商和多个客户组成的供应链系统。每个客户有一个订单交给制造商加工,每个订单都有一个强制交货期。工厂采用承诺到货时间的发货方式，目标是在满足客户强制交货期的情况下，合理的安排订单的加工顺序，以极小化总的运输费用。本文考虑了多种情况，分别给出了相应的算法。

泊松图P(4,1)与路Pn的笛卡尔积的交叉数

袁梓瀚 黄元秋

2011, 15(3):  95-106. 

摘要 ( 2654 )   PDF (517KB) ( 1303 )  

相关文章 | 多维度评价

泊松图$P(m, 1)$与路$P_n$的笛卡尔积的交叉数是一个NP-完全问题, Y.H. Peng和Y.C.Yiew 证明了$P(3,1)$与$P_n$的笛卡尔积的交叉数为$4n$, 我们证明明了$P(4,1)$与$P_n$的笛卡尔积的交叉数为$8n$.

具有线性恶化效应的在线分批排序问题

王成飞, 张玉忠, 柏庆国

2011, 15(3):  107-114. 

摘要 ( 2768 )   PDF (268KB) ( 1182 )  

相关文章 | 多维度评价

本文研究一类具有线性恶化效应的单机在线分批排序问题,工件$J_j$的加工时间为$p_j=b_j+\alpha t$, 其中$b_j$为基本加工时间, $\alpha>0$为恶化率, $t$是开工时间. 工件的到达时间是未知的, 工件的基本加工时间只有在工件到达之后才能知道.多个工件可以作为一批被机器同时加工, 批的加工时间为该批中工件最大加工时间.本文对于目标为极小化makespan的批容量无限的单机问题给出一个在线算法$\beta H^\infty$,并证明其竞争比和问题的下界相同, 进而算法是最优的.

互连网络的向量图模型

师海忠, 牛攀峰, 马继勇, 侯斐斐

2011, 15(3):  115-123. 

摘要 ( 3324 )   PDF (345KB) ( 1356 )  

相关文章 | 多维度评价

n-超立方体,环网,k元n超立方体,Star网络,煎饼(pancake)网络,冒泡排序(bubble sort)网络,对换树的Cayley图,De Bruijn图,Kautz图,Consecutive-d有向图,循环图以及有向环图等已被广泛的应用做处理机或通信互连网络.这些网络的性能通常通过它们的度,直径,连通度,hamiltonian性,容错度以及路由选择算法等来度量.在本文中,首先,我们提出了有向向量图和向量图的概念;其次,我们开发了有向向量图模型和向量图模型来更好地设计,分析,改良互连网络;我们进一步证明了上述各类著名互连网络都可表示为有向向量图模型或向量图模型;更重要的是该模型能够使我们设计出了新的互连网络---双星网络和三角形网络.

分配小于人数和任务数的指派问题的反点算法

王立柱, 刘阳

2011, 15(3):  124-128. 

摘要 ( 3606 )   PDF (267KB) ( 2392 )  

相关文章 | 多维度评价

摘要：本文对从 个人中派出 个人去完成 项任务中的 项任务使总效率最高这类指派问题给出了新算法，通过对这类指派问题引入了反点的概念，讨论了反点所具有的一些性质并证明了相关结论，利用这些结论找到了通过增加反点来解决此类指派问题的反点算法。