平面上的min-max型点-线选址问题

本文研究两类平面选址问题：(1)求一直线到n个给定点的最大加权距离为最小；(2)求一点到n条给定直线的最大加权距离为最小．对这两个非线性优化问题，我们给出最优解的刻划及迭代次数为多项式的算法．     

具有最小度距离的双圈图

记G（n）为所有n阶连通简单双圈图所构成的集合．本文主要讨论G（n）按其度距离从小到大进行排序的问题，并确定了该序的前两个图及其相应的度距离，其中具有最小度距离的图是由星图K1,n-1的一个悬挂点与另外两个悬挂点之间各连上一条边所得的图Sn．     

关于Heilbron型问题的一个猜测的纠正和证明

Heilbron型问题是组合几何中较为困难的问题,其中一个是: 平面上任给n个点,每两点之间有一个距离,最大距离与最小距离的比记为λ_n,求λ_n的     

一次漏解引发的讨论

近日，笔者在高三的复习课上让学生练习了这样一道题： 已知点A1（3，2）和A2（3，-2），若以OA1，OA2为两渐近线的双曲线上的动点P（x，y）到定点Q（2，0）的最小距离为1，求此双曲线方程．     

加权斯坦勒尔问题

加权斯坦勒尔问题贝清泉（汕头大学数学系５１５０６３）平面上有三城市Ａ、Ｂ、Ｃ，求点Ｐ的位置以设立公共机场，要使三城市通向机场的公路网之长为极小．这样一个问题导致下述费马问题或称斯坦勒尔问题；即求ΔＡＢＣ所在平面上一点Ｐ，使Ｐ到三顶点距离之和：ＰＡ＋Ｐ...     

一个具有两类工件的多目标排序的多项式时间算法

本文考虑具有两个工件集的单机排序问题.第一个工件集J1以完工时间和为目标函数,第二个工件集J2以最大加权完工时间为目标函数.问题的目标是寻找一种排序,使得两个目标函数的加权和达到最小.本文证明该问题可在O(n1n2(n1 n2))时间内求解.     

数列通项最值问题的流行错解

已知数列{αn}的通项αn=f（n）（n∈N^＋），求αn的最大值或最小值，对于这个问题，目前普遍的解法是通过如下不等式组来确定取最大值或最小值时n的值即：     

四面体有内切球吗？

求函数周期尤其是求两个函数和（差）的周期（本文所提的周期均指最小正周期），是高中数学的难点，有些书刊资料介绍了一种最小公倍数法，即先求出两个函数各自的周期，然后求它们的最小公倍数即为两个函数和（或差）的周期．对此学习者有很多疑惑，如结论是否恒成立？两个函数可否不是三角函数？可否推广到多个函数和（差）？本文作如下探究．     

基于Hamilton路模型的蛋白质结构预测的研究

提出一种基于Hamilton路模型的新方法研究蛋白质结构预测问题,为使结构匹配序列,把已知蛋白质的3D结构信息转化为一个加权的完全图Kn,则求这个特定空间结构所匹配的氨基酸残基序列问题转化为求Kn图的最小H路问题.用此方法研究了72个单链蛋白质结构,结果表明Kn图的最小H路对应此蛋白质的序列,图的顶点数n与最小H路总长度成正比.     

关于加权全最小一乘的探讨

设p（v;a;μ）为v∈Rk到超平面μTv+a=0的垂直距离,其中μ∈Rk,a∈R1.本文研讨的是寻找适当的a和μ使达到最小,这里{v1,v2,…,vn}(?)Rk而qi>0,i=1,2,…,n是给定的权.本文采用一条全新的途径来研讨上述加权全最小一乘问题的求解.文中导出了要使Q（u0,μ）达到最小,μ和u0应满足的若干本质性必要条件,而满足该条件的（μ,u0）只有有限多个;进而提出了一个求解加权全最小一乘问题的有限步终止算法.     

干线网络的选址问题研究

考虑平面上和三维空间中同时确定多条干线的干线网络选址问题.对于平面上情形,通过最小化每个点到离它最近干线的加权距离之和,给出了一种有限步终止算法和基于k-means聚类分析、加权全最小一乘和重抽样方法的线性类算法;对于空间情形,给出了线性聚类算法.通过计算机仿真说明以上算法可以有效地确定平面和空间中干线网络位置.     

一类网络上的干线选址

考虑一类在网络上点到路的距离意义下的最优干线选址问题,这是一类新型的选址问题.首先证明所讨论的两个问题是NP-hard,然后讨论树的情况,给出了当G是树时求解问题的算法,该算法的复杂性是O(n2).并对一些特殊网络的情况进行了讨论.     

Two Characterizations of Smooth Norms

In an arbitrary Minkowski space M, n2, let there be given an arbitrary finite set P of weighted points whose affine hull is n-dimensional. We show that the unit ball B of M has smooth boundary if and only if each median hyperplane (minimizing the sum of weighted distances with respect to P) is spanned by n affinely independent points from P. Moreover, B has the same property if and only if every center hyperplane (minimizing the maximal weighted distance with respect to P) has the same maximal distance to at least n+1 affinely independent points from P.     

Exact pseudopolynomial algorithms for a balanced 2-clustering problem

We consider the strongly NP-hard problem of partitioning a set of Euclidean points into two clusters so as to minimize the sum (over both clusters) of the weighted sum of the squared intracluster distances from the elements of the clusters to their centers. The weights of sums are the sizes of the clusters. The center of one cluster is given as input, while the center of the other cluster is unknown and determined as the average value over all points in the cluster (as the geometric center). Two variants of the problems are analyzed in which the cluster sizes are either given or unknown. We present and prove some exact pseudopolynomial algorithms in the case of integer components of the input points and fixed space dimension.     

无关机上极小化求和问题的平行分批排序(英文)

本文我们考虑了无关机上的平行分批排序问题.对于批容量无限的平行批排序模型,目标是极小化总完工时间,我们对p_(ij)≤p_(ik)(i=1,…,m;1≤j≠k≤n)这种一致性的情况设计了多项式的动态规划算法.对于批容量有限的平行批排序模型,我们讨论了p_(ij)=p_i(i=1,…,m;j=1,…,n)这种情况,当不考虑工件可被拒绝时,对极小化加权总完工时间的排序,我们给出了其最优算法;当考虑工件可被拒绝时,对极小化被接收工件的加权总完工时间加上被拒绝工件的总拒绝费用的排序,我们设计了一拟多项时间算法.     

Linear facility location — Solving extensions of the basic problem

The basic problem is to locate a linear facility to minimize the sume of weighted shortest Euclidean distances from demand points to the facility. We extend the analysis to locating a constrained linear facility, a radial facility, a linear facility where distances are rectangular and a linear facility under the minimax criterion. Each case is shown to admit a simple solution technique.     

具有学习效应和加工时间可控的平行机排序问题

本文研究了一类不相关平行机的排序问题,在该问题中工件的加工时间既具有学习效应,又资源可控,也就是说在该问题模型中,工件的实际加工时间为其正常的加工时间、加工过程中工件所处位置以及加工时间可控这些变量的函数。该研究的目的是为使得总机器负载和总的控制费用的加权和最小以及总的完工时间和总的控制费用的加权和最小。文章通过对问题的相关性质的分析和证明找到了一个解决问题的最优化算法,并且也证明了在处理机的数量给定的条件下,该问题的时间复杂性为O(n^m+2),最后也给出了相应的数值例子来阐述该问题。     

一个混合协调分配机制下自私调度问题的社会无序代价分析

自私调度问题是一类应用于互联网和云计算的特殊调度问题.不同于传统调度问题,它的每个工件是一个自私的参与者,可以自主地选择一台机器加工以谋求自身加工费用最小化.针对机器可以自由选择WSPT机制或PS机制的混合协调分配机制自私调度问题,通过设计一个该问题的松弛线性规划,然后写出该线性规划的对偶规划.比较上述两个规划的最优目标值,以及该自私调度问题的最优社会费用和混合Nash均衡解的最差社会费用这四个数值,分析出该自私调度问题的混合社会无序代价为4.