| 引用本文: | 岳菊梅,陈增强,闫永义,金鑫.k轨道任务分配问题的可解性条件: 图论方法[J].控制理论与应用,2017,34(4):457~466.[点击复制] |
| YUE Jv-mei,CHEN Zeng-qiang,YAN Yong-yi,JIN Xin.Solvability of k--track assignment problem: a graph approach[J].Control Theory and Technology,2017,34(4):457~466.[点击复制] |
|
| k轨道任务分配问题的可解性条件: 图论方法 |
| Solvability of k--track assignment problem: a graph approach |
| 摘要点击 3236 全文点击 2525 投稿时间：2016-02-23 |
| 查看全文 查看/发表评论 下载PDF阅读器 |
| DOI编号 10.7641/CTA.2017.16033 |
| 2017,34(4):457-466 |
| 中文关键词 k轨道任务分配 k内稳定集 可解性 图论方法 矩阵的半张量积 |
| 英文关键词 k--track assignment k--internally stable set solvability graph method semi-tensor product of matrices |
| 基金项目 |
|
| 中文摘要 |
| 将图论及一种新的数学分析工具–—矩阵的半张量积(semi-tensor product of matrices, STP), 作为研究工具,通过研究图的k内稳定集的充分必要条件, 研究了k轨道任务分配问题的可解性条件. 定义了图的顶点子集的特征向量, 利用STP方法得到图的k内稳定集新的若干充分必要条件. 基于这些新的充分必要条件, 建立了能够搜索出图的所有k内稳定集的两种算法. 进而将上述结果应用到k轨道任务分配问题, 得到了该问题可解性的两个充分必要条件. 此外, 通过这些充分必要条件, 也发现了一些有趣的现象. 例如, 完全最优方案(completely optimal schedules)的存在. |
| 英文摘要 |
| The theory of graph and a new mathematical analysis tool, semi-tensor product (STP) of matrices are applied to consider the solvability conditions of k--track assignment problem by investigating the necessary and sufficient conditions of k--internally stable sets of graphs (k--ISS). By defining characteristic vectors for vertex subsets of graphs and using the STP, several new necessary and sufficient conditions of k--ISS are obtained, based on which two algorithms able to find all the k--ISSs of a graph are established. The results obtained are further applied to the k--track assignment problem, and two necessary and sufficient conditions of the solvability of the problem are proposed; also some interesting phenomena such as completely optimal schedules are discovered by the new method. |
|
|
|
|
|