运筹学学报

高强, 鲁习文

2014, 18(4): 1-10.

摘要 ( 885 )

PDF (510KB) ( 1127 )

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

研究了带有拒绝的单机和同型机排序问题. 对于单机情形, 工件的惩罚费用是对应加工时间的\alpha倍. 如果工件有到达时间, 目标为最小化时间表长与惩罚费用之和, 证明了这个问题是可解的. 如果所有工件在零时刻到达, 目标为最小化总完工时间与惩罚费用之和, 也证明了该问题是可解的. 对于同型机排序问题, 研究了工件分两批在线实时到达的情形, 目标为最小化时间表长与惩罚费用之和. 针对机器台数2和m, 分别给出了竞争比为2和4-2/m的在线算法.

二阶锥规划的基于自协调指数核函数的原始-对偶内点算法

张景, 白延琴

2014, 18(4): 11-24.

摘要 ( 994 )

PDF (591KB) ( 619 )

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

基于一个自协调指数核函数, 设计求解二阶锥规划的原始-对偶内点算法. 根据自协调指数核函数的二阶导数与三阶导数的特殊关系, 在求解问题的中心路径时, 用牛顿方向代替了负梯度方向来确定搜索方向. 由于自协调指数核函数不具有``Eligible''性质, 在分析算法的迭代界时, 利用牛顿方法求解目标函数满足自协调性质的无约束优化问题的技术, 估计算法内迭代中自协调指数核函数确定的障碍函数的下降量, 得到原始-对偶内点算法大步校正的迭代界O(2N\frac{\log2N}{\varepsilon}), 这里N是二阶锥的个数. 这个迭代界与线性规划情形下的迭代界一致. 最后, 通过数值算例验证了算法的有效性.

内生网络环境下具有异质连接费用的局部策略互动

孙丽萍, 高红伟, VASIN Alexander, 宋丽, 李茹, 王磊

2014, 18(4): 25-35.

摘要 ( 846 )

PDF (535KB) ( 583 )

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

考察内生网络环境下局中人之间的局部策略互动, 网络中的局中人只与直接邻居进行协同对策. 网络生成的过程中, 建立连接的费用是异质的~(具有两种水平), 与采取有效行动的局中人建立连接时执行高水平费用, 与采取风险占优行动的局中人建立连接时执行低水平费用. 在异质连接费用的情形下, 首次较为完整地给出了均衡网络的结构特性和局中人的行动选择, 并分析了费用参数对均衡结果的影响.

满意度优化运输问题

胡勋锋, 李登峰

2014, 18(4): 36-44.

摘要 ( 914 )

PDF (589KB) ( 1195 )

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

传统运输问题只考虑配送方案的效率, 而不考虑参与者对配送方案的满意度. 通过引入参与者对配送方案的满意度这一概念, 提出了满意度优化运输问题, 构建了以最大化相对公平为目标的满意度优化运输模型, 并证明了: (1) 当运输问题的可行域不空时, 新模型的解集非空; (2) 从满意度的角度来看, 新模型的解是唯一的. 另外, 还给出了新模型的求解方法. 研究结果进一步丰富了运输问题的类型, 可为解决其他类型运输问题提供借鉴.

面向制造成本甄别和销售努力激励的供应链协调契约研究

黄梅萍, 汪贤裕, 张欢

2014, 18(4): 45-57.

摘要 ( 840 )

PDF (967KB) ( 787 )

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

针对二级供应链中制造商隐藏成本信息和销售商隐藏努力行动引发的低效率问题, 结合委托代理理论, 引入一个虚拟第三方为利他的委托人, 建立逆向选择和道德风险下供应链协调模型, 来甄别制造商的真实成本且对销售商的努力实施有效激励, 并通过模型求解得到供应链实现协调时各契约参数需满足的关系. 结果表明, 所设计的协调契约能够激励制造商自愿真实上报成本信息, 刺激销售商寻求低成本的制造商进行合作并付出最优努力. 最后, 通过算例分析验证了契约模型对供应链协调的有效性.

向量优化中\varepsilon-真有效解的非线性标量化性质

夏远梅, 赵克全

2014, 18(4): 58-64.

摘要 ( 1165 )

PDF (435KB) ( 742 )

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

利用G\"{o}pfert等提出的非线性标量化函数给出了向量优化中\varepsilon-真有效解的一个非线性标量化性质, 并提出几个例子对主要结果进行了解释.

Pancake网络的t/k-诊断度及其算法

宋苏琳, 林丽美, 周书明

2014, 18(4): 65-77.

摘要 ( 1097 )

PDF (1434KB) ( 685 )

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

由于大型多处理机系统规模的不断扩大, 其组件脆弱性也随之增加, 因此故障容错性能对于多处理机系统尤为重要. t/k-诊断分析是一种能极大提高多处理机系统自我诊断性能的系统级故障诊断策略，该诊断策略能识别至多t个故障处理机节点, 其中可能包含至多$k$个被误诊的处理机. 首先给出了Pancake网络P_n(n\geq 5) 的容错性分析, 其后证明了P_n在PMC模型下是((k+1)n-3k-1)/k-可诊断的, 其中1\leq k\leq 3, 最后还给出复杂度为O(NlogN)的快速诊断算法来识别所有的故障节点.

多数满意偏好规则的充分必要条件

胡毓达

2014, 18(4): 78-84.

摘要 ( 864 )

PDF (487KB) ( 546 )

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

研究基于满意选择的群体决策的一个基本数学理论问题. 给出并证明了群体在方案集上的任一群体满意偏好映射是多数满意偏好规则的充分必要条件.

不含偶圈双圈图的极小斜能量

肖毛, 王文环

2014, 18(4): 85-95.

摘要 ( 959 )

PDF (574KB) ( 727 )

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

令G为简单连通图. 给图G的每条边赋予一个方向, 得到的有向图, 记为G^\sigma. 有向图G^\sigma的斜能量E_{s}(G^{\sigma})定义为G^\sigma的斜邻接矩阵特征值的绝对值之和. 令\mathcal{B}^\circ_{n}表示顶点个数为n不含偶圈的双圈图的集合. 考虑了\mathcal{B}^\circ_{n}中图依斜能量从小到大的排序问题. 利用有向图斜能量的积分公式和实分析的方法, 当n \geq 156和155 \geq n\geq 12时, 分别得到了\mathcal{B}^\circ_{n}中具有最小、次二小和次三小斜能量的双圈图.

网络最小覆盖流问题

林浩, 林澜

2014, 18(4): 96-104.

摘要 ( 894 )

PDF (795KB) ( 610 )

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

网络流理论中最基本的模型是最大流及最小费用流问题. 为研究堵塞现象, 文献中出现了最小饱和流问题, 但它是NP-难的. 研究类似的最小覆盖流问题, 即求一流, 使每一条弧的流量达到一定的额定量, 而流的值为最小. 主要结果是给出多项式时间算法, 并应用于最小饱和流问题.

图加一条边后的带宽和

林艺舒, 刘岩

2014, 18(4): 105-110.

摘要 ( 631 )

PDF (452KB) ( 599 )

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

令$BS(G,f)=\sum\limits_{uv\in E(G)}|f(u)-f(v)|$, 其中$f$为$V(G)\rightarrow\{1,2,\cdots,|V(G)|\}$的双射, 并称$BS(G)=\min\limits_{f}BS(G,f)$为图$G$的带宽和. 讨论顶点数为$n$的简单图$G$加上一条边$e\in\overline{E(G)}$后, 带宽和$BS(G+e)$与$BS(G)$的关系, 得其关系式$BS(G)+1\leq BS(G+e)\leq BS(G)+n-1$. 并证明此不等式中等号可取到, 即存在图$G_{1}$和$G_{2}$使得$BS(G_{1}+e)=BS(G_{1})+1$, $BS(G_{2}+e)=BS(G_{2})+n-1$.

工件的运输和继列分批加工协作排序问题

谷存昌, 张玉忠

2014, 18(4): 111-118.

摘要 ( 924 )

PDF (546KB) ( 614 )

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

近年来，工件的运输和加工协作排序问题在物流和供应链管理领域得到广泛关注. 讨论了先用 $\ m$ 台车辆将工件从等待区域运输到继列分批处理机处, 再进行分批加工的协作排序问题, 加工一批工件需要支付一定的费用, 目标为最小化工件的总完工时间与批的加工费用之和. 在工件的加工时间都相等的情况下, 如果工件运输方案确定, 给出了多项式时间的动态规划算法; 如果工件运输方案不确定, 证明了该问题是{\, NP}-难的, 给出了车辆返回时间 $\ t=0$ 时, 最差性能比等于 $\ 2-\frac{1}{m}$ 的近似算法.

求解互补约束优化问题的乘子松弛法

刘水霞, 陈国庆

2014, 18(4): 119-130.

摘要 ( 910 )

PDF (528KB) ( 758 )

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

利用互补问题的Lagrange函数, 给出了互补约束优化问题\,(MPCC)\,的一种新松弛问题. 在较弱的条件下, 新松弛问题满足线性独立约束规范. 在此基础上, 提出了求解互补约束优化问题的乘子松弛法. 在MPCC-LICQ条件下, 松弛问题稳定点的任何聚点都是MPCC的M-稳定点. 无需二阶必要条件, 只在ULSC条件下, 就可保证聚点是MPCC的B-稳定点. 另外, 给出了算法收敛于B-稳定点的新条件.

当期目录