关于三个相同伪硬币问题的一些新结果

本文中,给定一台比较型测试装置和确切的三个相同伪硬币出现的信息,作者研究最小测试数的探求问题,这个最小测试数能从λ个有同样外观的硬币组成的集合中鉴别出三个相同的伪硬币,这里λ≥4.作者构造了对于无限多个λ值的一个最优鉴别分组测试算法,这个最优鉴别分组测试算法改进了To（s）ic的对于无限多个λ值的一个最优鉴别分组测试算法,也改进了Bo（s）njak的对于无限多个λ值的一个最优鉴别分组测试算法.作者还提出另一个鉴别分组测试算法,并且猜想这个算法是最优的.     

关于两个伪硬币问题的一些新结果

下面的问题被称为n个外观不可区分硬币的分组测试问题,每个硬币可以是伪硬币或是标准硬币.本文所涉及的问题是:已知一个由n个硬币组成的集合中有两个伪(较重的)硬币,用一台天平以最小的称重次数,从这n个硬币组成的集合中探测出两个伪(较重的)硬币. 我们构造了找出两个伪(较重的)硬币的两个算法,并且这两个算法是最优的.     

关于四个相同伪硬币问题的一些新结果

本文给定一台比较型测试装置和确切的四个相同伪硬币出现的信息,作者研究最小测试数的探求问题,这个最小测试数能从λ个有同样外观的硬币组成的集合中鉴别出四个相同的伪硬币,这里λ≥5.作者构造了一个鉴别四个相同伪硬币的测试算法,这个测试算法改进了Toic的一个测试算法,还修正了另外一个测试算法.     

一装置搜索四个坏硬币的分组测试过程

从n个硬币的集合中搜索d(d≥2)个坏硬币是一个相当困难且至今尚未完全解决的问题,本文研究了d=4的一装置分组测试模型,令tk为用测试（搜索）过程t经k次测试所能鉴别的最大硬币数,nk=maxtk,我们给出了一个相当好 的测试过程使tk/nk=0.85。     

搜索两个不同坏硬币的最优化方法

设n个外观相同的硬币的集合X中含有两个坏硬币，这两个坏硬币的重量彼此不同，但都比好硬币重，而假定好硬币有相同的重量．以g2（n）表示用天平从X中找出两个坏硬币的最少测试次数．本文证明了对任意的n成立［log3（n2）］≤g2（n）≤［log3（n2）］＋1．且对无穷多个n，文中所给的测试过程是最优的．     

顶点覆盖约束下的同类机排序算法研究

给定m台同类机和n个工件,其中第j台机器的速度为s_j,第i个工件的加工时间为p_i并且在第j台机器上的负载为p_i/s_j.构造一个顶点赋权无向图G=(V,E;w),其中图G的n个顶点代表这n个工件,顶点权重代表相应工件的加工时间.本文研究顶点覆盖约束下的同类机排序问题.该问题是两个组合最优化问题的组合问题,其目标为首先确定图G的一个顶点覆盖,即图的一个顶点子集,使得图中每一条边都至少存在一个顶点属于该子集;然后把这个子集所代表的相应工件集放到m台同类机上加工,使得最大完工时间最小.该问题是NP-hard的.本文基于分层算法和LSPT算法设计一个■-近似算法,当所有机器的速度都相差不大时,该算法的近似效果较好.     

需要安装时间的平行多功能机排序问题的启发式算法

考虑需要安装时间的平行多功能机排序问题。在该模型中,每个工件对应机器集合的一个子集,其只能在这个子集中的任一台机器上加工,称这个子集为该工件的加工集合;工件分组,同组工件具有相同的加工时间和加工集合,不同组中的工件在同一台机器上连续加工需要安装时间,目标函数为极小化最大完工时间。对该问题NP-难的一般情况设计启发式算法:首先按照特定的规则将所有工件组都整组地安排到各台机器上,然后通过在各机器间转移工件不断改进当前最大完工时间。通过与下界的比较检验算法的性能,大量的计算实验表明,算法是实用而有效的。     

不确定线性系统的最优保性能可靠控制

针对一类不确定线性系统,采用连续增益故障模型提出了考虑执行器故障的保性能可靠控制问题.通过对具有执行器增益故障的系统分析,利用线性矩阵不等式(LMI)分别给出了保性能标准控制、最优保性能标准控制、保性能可靠控制、最优保性能可靠控制存在的充分条件.根据凸优化理论,最优保性能标准控制和最优保性能可靠控制的设计方法转化为一个线性凸优化算法.仿真数例验证了文中所提出方法的可行性.在相同形式的故障发生时,比较最优保性能标准控制与最优保性能可靠控制,进一步说明了最优保性能可靠控制的必要性.     

搜索四个坏硬币的最优化方法

给出了用天平从ｎ个硬币的集合中搜索出４个坏硬币的最少测试次数的一个估计。     

关于最大权k－子集分拆问题

对给定规模为ｎ的集合Ｓ，其每一个规模至多为ｋ的子集对应一个权．本文研究如何将Ｓ分为　个互不相交的规模至多为ｋ的子集且满足权和最大的问题．我们证明了该问题当ｋ＝２时是多项式时间可解的；当ｋ≥３时为ＮＰ－完全的；同时给出了一个Ｏ（ｎ￣（ｋ＋１））时间的启发式算法，所得到的解与最优解之比不小于１／ｋ．     

分组测试与迫进控制标准

1引言 在第二次世界大战期间,珍珠港事件发生后,美国为了反击德国法西斯挑起的侵略战争,多次进行大规模的征兵活动．在征兵活动中,需要对大量报名入伍者进行健康检查,看其身体是否符合入伍的条件．其中一项健康检查的内容是血液抗体检测,通过血液抗体检测,查出梅毒的携带者．当时,由于被检测者数量巨大,部队又急需补充兵员,检测时间紧、任务重,这就需要找到一种科学的检测方法,用尽可能少的测试次数检测出所有病毒携带者,这一问题后来称为搜索坏硬币的最优化问题．在这个问题中,被检测者抽象为硬币,血液不带病毒者抽象为标准硬币,血液带病毒者抽象为伪硬币,检测的设备称为装置．如何用特定性能的若干台装置,以尽可能少的测试次数从由硬币组成的集合中检测出全部伪硬币,是一个有很强实际背景的最优化问题,正因为如此,近一段时间组合搜索中的伪硬币问题一直受到人们的广泛关注．     

An efficient randomized group testing procedure to determine the number of defectives

In many fault detection problems, we want to detect or identify defective items in a sample set by using the minimum number of tests. Group testing is for the scenario where each test is on a subset of items, and tells whether the subset contains at least one defective item or not. In this paper, we present an efficient randomized group testing procedure that determines the exact number of defectives in a sample set with high success probability.     

Selecting two different defective coins

In this paper, given a balance scale and the information that there are exactly two different defective coins present, the authors consider the problem of ascertaining the minimum number of testing which suffice to determine the two different defective coins in a set of λ coins in same appearance, and here λ  3. A testing algorithm for all the possible values of λ is constructed, and the testing algorithm needs at most one testing step more than the optimal testing algorithm.     

Optimal control of a class of strongly nonlinear parabolic systems

This paper considers some typical optimal control problems for a class of strongly nonlinear parabolic systems. After some necessary preparation, it is shown that the family of admissible trajectories is a weakly closed and weakly sequentially compact subset of a reflexive Banach space and that the set of attainable states at any given time is a weakly compact subset of a Hilbert space. Using these basic results, proofs of existence of optimal controls are presented. A terminal control problem, a special Bolza problem, and a time optimal control problem are solved, and the necessary conditions of optimality for the corresponding control problems are given.     

Relaxation techniques applied to some loading problems

In this paper a two-stage loading problem, dealing with allocation of jobs to machines, is studied. The outer problem is to choose a subset among a number of available machines such that a feasible assigment exists and the total cost price is minimized. The inner problem, is then to find the optimal allocation, given the subset of machines and some assigment criterion at this lower level. It is shown that the choice of problem formulation can be crucial for the strength of the continuous relaxation. Computational results are also presented     

An ideal column algorithm for integer programs with special ordered sets of variables

One of the most frequently occurring integer programming structures is the one which has special ordered sets of variables included in multiple choice constraints. For problems with this structure a set of ideal columns are defined from the linear programming relaxation of the integer program and a reduced integer program is formed by keeping only those columns within a specified distance from the ideal column. Conditions are established which guarantee when the optimal solution to the reduced problem is als optimal for the original problem. When these conditions are not satisfied, bounds on the optimal solution value are provided. Ideal columns are also used to establish weights for the special ordered set variables. This procedure has been implemented through a control program written by the authors for MPSX/370-MIP/370. Computational results are given.     

Mean-Field Pontryagin Maximum Principle

This paper provides a characterization of the optimal average cost function, when the long-run (risk-sensitive) average cost criterion is used. The Markov control model has a denumerable state space with finite set of actions, and the characterization presented is given in terms of a system of local Poisson equations, which gives as a by-product the existence of an optimal stationary policy.     

Dynamics and control of a system of two non‐interacting preys with common predator

In this paper, we consider a Holling type model, which describes the interaction between two preys with a common predator. First, we give some sufficient conditions for the globally asymptotic stability and prove that local stability implies global stability. Then, we present a set of sufficient conditions for the existence of a positive periodic solution with strictly positive components. Finally, the optimal control strategy is developed to minimize the number of predator and maximize the number of preys. We also show the existence of an optimal control for the optimal control problem and derive the optimality system. The technical tool used to determine the optimal strategy is the Pontryagin Maximum Principle. Finally, the numerical simulations of global stability and the optimal problem are given as the conclusion of this paper. Copyright © 2011 John Wiley & Sons, Ltd.     

A maxmin location problem with nonconvex feasible region

The problem dealt with consists of locating a point in a given convex polyhedron which maximizes the minimum Euclidean distance from a given set of convex polyhedra representing protected areas around population points. The paper describes a finite dominating solution set for the optimal solution and develops a geometrical procedure for obtaining the optimal solution comparing a finite number of candidates.