风向图上两问题的复杂性

本文证明了风向图上两问题是ＮＰ－完全的和强ＮＰ－完全的．并进一步指出：即使所给风向图是平面的，它们仍是ＮＰ－完全的及强ＮＰ－完全的．这两个问题是：一是叫２ＷＰＰ，它是由带风向投递员问题限制投递员穿过每条边至多两次而得到的问题；

用最小下标原则避免对偶单纯形迭代的循环

本文提出了用对偶单纯形方法求解线性规划问题时避免循环的最小下标原则,即:(ⅰ)当有几个基变量可以出基时,就选下标最小的那个为换出变量;(ⅱ)当有几个非基变量可以进基时,就选下标最小的那个为换入变量.

有向图上最大权圈装箱问题的有效算法

对弧赋权的有向图,其一组有向图称为图装箱,若其中任两个图无公共弧.有向图上最大权图装箱问题是:对任给的赋权有向图,找一图装箱,使所含弧的总权最大.本文给出了求解这一问题的多项式算法.

带风向投递员问题的一个多项式1—近似算法

当投递员穿过边的方向不同,费用就不同时,中国投递员问题就成为带风向的投递员问题(WPP)。本文给出了欧拉图上WPP的一个多项式算法,并由此又给出了WPP的一个多项式1—近似算法。

带风向投递员问题的又一多项式1——近似算法

本文提出了带风向投递员问题(WPP)的一整数线性规划形式,并由此给出了WPP的一个多项式1——近似算法。文中指出:当所给风向图是欧拉图时,由这一近似算法求得的投递员路线是最优的投递员路线。