集的最优分划问题简介

很多高校都要对一年级新生按他们的英语程度进行分班,以利于英语教学.分班的原则通常足先将学生按英语成绩高低进行排队,然后给出几个分数段,每一段中的学生编为一个水平班.比如:85分以上的编为快班;70-84分的编为中班;70分以下的编为慢班.这样分班的合理性是显而易见的.我们不难用数学语言给它一个描述:设 E={新生集合).每个学生 e∈E 对应有一个英语成绩 w(e)≥0.现将新生分成三个了集 E_1,E_2,E_3.满足 E=E_1∪E_2∪E_3,且 E_i∩E_j=φ(i≠j),问这三个子集应如何划分能使得同一子集中学生的英语成绩尽可能接近.我们可以在每一子集 E_i

最短内接折线问题

本文对具有固定边界点的最短内接折线问题、退化的问题和非凸多边形的问题进行了讨论,并给出了有效的组合优化求解方法.我们还提出了通过固定内点的最短内接折线问题,并对特殊情况给出了一些结果.

一类新的分划问题:有限集的约束分划

本文研究带有附加约束条件的分划问题。定义1 (K-约束分划) 设E是一个有限元素集,M_i=(E,T_i)(i=1,…,K)是建立在E上的K个拟阵,E的分划P=(S_1,…,S_K)被称作K-约束分划,如果且满足类似可定义Shape分划。在数集2-Shape分划中,若固定则我们建立拟阵如下:其中记M_i的基集为B_i,即,这样,2-

点带约束成本的最短路问题

本文提出了点带约束成本的最短路问题．证明了该问题是ＮＰ－完全的，并利用动态规划给出了一个伪多项式算法．对所有顶点约束成本相同的情况，给出了一个时间复杂性为Ｏ（ｍ ｎ２）的算法．对最小点成本最短路问题，给出了一个时间复杂性为Ｏ（ｎ２）的算法．

关于最短路问题的一个双目标优化问题

本文研究了一个双目标最短路问题的变形问题,在该变形问题中,一个目标函数还是路的长度,另一个目标函数则是路的容量.在Pareto-optimal最优解的意义下,本文给出了一个时间复杂性为O（n3）的算法,在字典序最优解的意义下,本文给出了一个时间复杂性为O（n2）的算法.

带有宵禁限制的动态最短费用路问题

很多实际优化问题可用最短路的模型来描述,以往的很多研究都是静态的,而实际问题中往往要求所出现的参数及其所考虑的目标是与时间相关的,也即动态的.本文通过构建时间扩张网络,将有宵禁的动态问题转化为一般静态问题来讨论,给出了带有宵禁限制的动态最短费用路问题的数学模型,设计了求解它的算法,并给出了一个应用实例.

最短路问题的字典序多目标算法

本文研究了双目标最短路问题,给出了字典序最优解的定义,最后给出了一个时间复杂性为O(n^2)的字典序双目标算法。

带服务器的Flow Shop问题

经典的 Flow Shop问题是排序理论中一个得到广泛研究的问题 .本文研究的是带服务器的Flow Shop问题 .证明了 F2 ,S∥ Cmax 是强 N P- C的 ,并构造了一个渐近比为 2的近似算法 .此外 。

带多重选择的最短路问题:复杂性和算法

本文提出了带多重选择的最短路问题 ,建立了该问题的数学模型 .利用背包问题的一个变形问题——带限制选择的背包问题 ,证明了该问题是 NP- C的 .最后利用动态规划给出了一个伪多项式算法 ,其时间复杂性 O(Chmn) ,其中 h是最大的选择重数 .

稳定材料在应力π平面上屈服曲线的特性

对稳定材料来说，在应力π平面上，双剪应力屈服准则［１］为所有屈服准则的外包络线，Ｍｏｈｒ－Ｃｏｕｌｏｍｂ屈服准则为所有屈服准则的内包络线（当材料的单向拉伸强度与单向压缩强度相等时，Ｍｏｈｒ－Ｃｏｕｌｏｍｂ屈服准则退化为广义Ｔｒｅｓｃａ屈服准则）．但关于此问题的严格数学证明却还是空白．本文作者通过引入凸集概念，对上述问题做出了数学上的严格证明．

约束最小支撑树(C-MST)问题:复杂性和上下界估计

本文首先建立了约束最小支撑树问题的模型 ,利用背包问题的复杂性 ,证明了该问题是 NP-完全的 .然后利用一个广义线性规划的对偶算法 ,对目标函数的上下界作出了估计 。

λ_5-geometry中的Steiner树问题(Ⅰ)

本文首先提出了 λ5-geometry中的 Steiner最小树问题 .讨论了 λ5-ge-ometry中的 Steiner最小树的若干性质 ,并给出了给定点数为 3或 4时 Steiner最小树的基本结构 .

带点弧约束的最短路问题——复杂性和算法

本文首先提出了带点弧约束的最短路问题，证明了该问题属于ＮＰ－Ｃ，然后给出了一个伪多项式时间算法．最后给出了最小成本最短路问题的一个时间复杂性为Ｏ（ｎ２）的算法．

带服务器的三台平行机排序问题的复杂性和近似算法

讨论带有两个服务器的三台机的平行机排序问题,在这个问题的实例中,每一个工件都有一个时间长度为1的安装操作必须要由服务器来完成,而每一个服务器在同一时刻只能安装一个工件,用三段式描述表示此问题即为P3,S2/si=1/Cmax.证明了此问题为NP-C的,分别给出了在在线和离线条件下的近似算法,并且估计了算法的最坏情况界.

带核箱覆盖问题的在线算法

经典的箱覆盖问题是组合优化中一个著名的问题，并且得到了广泛的研究．本文主要讨论带核元的箱覆盖问题的复杂性和在线条件下的算法．指出了带核的箱覆盖问题是强ＮＰ－ｈａｒｄ的．给出了在不同的在线条件下可行算法渐近比的上界，指出仅在条件三下才存在渐近比好于０的在线算法，并给出了在此条件下一个渐近比为１／２的最好的在线算法。

带圆周约束的Steiner树问题

本文首先考虑了带圆周约束的Ｓｔｅｉｎｅｒ树问题．设欧氏平面上有一圆，平面上有ｎ个点，所成点集为Ｎ，该问题是要在圆周上找一点Ｐ，使Ｎ∪｛Ｐ｝这ｎ＋１个点的Ｓｔｅｉｎｅｒ树之长度达到最短．本文对于ｎ＝２的情形给出解．另一方面，鉴于问题的复杂性为ＮＰ－Ｃ，作者提出了一个近似解，并证明了近似解的性能比为３／２．

单背包问题的半定松弛算法

首先给出了单背包问题的秩 1半定松弛规划 ,然后在此基础上提出了求解该问题的半定松弛随机算法 KSSD.分析结果表明 :(1 )当σ>0 .1 9时 ,算法KSSD的近似比就会超过 0 .2 7.(2 )算法

平行机的实时到达on-line算法下界的改进

本文考虑了平行机实时到达的在线问题．模型中，工件是陆续到达的，工件的个数、到达时间是事先未知的，而且只有当工件到达，才知其加工时间，目标是使所有工件都加工完的时间达到最小．Ｃｈｅｎ与Ｖｅｓｔｊｅｎｓ（１９９６年）证明了该在线问题不存在性能比小于１．３４７３的ｏｎ－ｌｉｎｅ算法．本文将此界改进为（５－５）／２．

带硬宵禁限制的动态最短费用路问题

很多实际优化问题可用最短路的模型来描述,以往的很多研究都是静态的,而实际问题中往往要求所出现的参数及其所考虑的目标是与时间相关的,也即动态的问题。本文简述了带有硬宵禁限制的动态最短费用路问题的数学模型及给出了求解方法,并对模型中的控制参数"M"的取值进行了研究。

最小最大后悔支撑树问题

本文建立了最小最大后悔支撑树问题的模型 .利用划分问题 ,证明了该问题是 NP- C的 .然后利用两个已有的算法 ,给出了上下界估计 .最后对一种特殊情况 ,给出了一个启发式算法 。