三种新变形的全一问题

该文研究三种新变形的全一问题及最小全一问题. 原始的全一问题可被形象的称为顶点点亮顶点问题, 而这三类新问题则分别被称为顶点点亮边问题,边点亮顶点问题,边点亮边问题. 顶点点亮顶点问题已经得到了广泛的研究. 比如,解的存在性问题和求解的有效算法已经被解决,一般图上的最小顶点点亮顶点问题已经被证明是NP- 完备的,树、单圈图和双圈图上的最小顶点点亮顶点问题的线性时间最优算法也已被给出等. 该文对于顶点点亮边问题,证明一个图有解当且仅当它是二部图,因此只可能有两组解和最优解. 对于边点亮顶点问题,证明一个图有解当且仅当它包含偶数个顶点,并通过将其最优问题多项式变换成最小权的完美匹配问题,得出一般图上的最小边点亮顶点问题可在多项式时间内求解. 边点亮边问题可归约成线图上的顶点点亮顶点问题.     

Reconstruction of boundary regimes in the inverse problem of thermal convection of a high-viscosity fluid

A problem of reconstruction of boundary regimes in a model for free convection of a high-viscosity fluid is considered. A variational method and a quasi-inversion method are suggested for solving the problem in question. The variational method is based on the reduction of the original inverse problem to some equivalent variational minimum problem for an appropriate objective functional and solving this problem by a gradient method. When realizing the gradient method for finding a minimizing element of the objective functional, an iterative process actually reducing the original problem to a series of direct well-posed problems is organized. For the quasi-inversion method, the original differential model is modified by means of introducing special additional differential terms of higher order with small parameters as coefficients. The new perturbed problem is well-posed; this allows one to solve this problem by standard methods. An appropriate choice of small parameters gives an opportunity to obtain acceptable qualitative and quantitative results in solving the inverse problem. A comparison of the methods suggested for solving the inverse problem is made with the use of model examples.     

A study of mixed discrete bilevel programs using semidefinite and semi-infinite programming

In this paper, we study the bilevel programming problem with discrete polynomial lower level problem. We start by transforming the problem into a bilevel problem comprising a semidefinite program (SDP for short) in the lower level problem. Then, we are able to deduce some conditions of existence of solutions for the original problem. After that, we again change the bilevel problem with SDP in the lower level problem into a semi-infinite program. With the aid of the exchange technique, for simple bilevel programs, an algorithm for computing a global optimal solution is suggested, the convergence is shown, and a numerical example is given.     

Error estimates for shooting methods in two-point boundary value problems for second-order equations

This paper is concerned with a procedure for estimating the global discretization error arising when a boundary value problem for a system of second order differential equations is solved by the simple shooting method, without transforming the original problem in an equivalent first order problem. Expressions of the global discretization error are derived for both linear and nonlinear boundary value problems, which reduce the error estimation for a boundary value problem to that for an initial value problem of same dimension. The procedure extends to second order equations a technique for global error estimation given elsewhere for first order equations. As a practical result the accuracy of the estimates for a second order problem is increased compared with the estimates for the equivalent first order problem.     

Heuristic Solution Methods for the Multilevel Generalized Assignment Problem

The multilevel generalized assignment problem is a problem of assigning agents to tasks where the agents can perform tasks at more than one efficiency level. A profit is associated with each assignment and the objective of the problem is profit maximization. Two heuristic solution methods are presented for the problem. The heuristics are developed from solution methods for the generalized assignment problem. One method uses a regret minimization approach whilst the other method uses a repair approach on a relaxation of the problem. The heuristics are able to solve moderately large instances of the problem rapidly and effectively. Procedures for deriving an upper bound on the solution of the problem are also described. On larger and harder instances of the problem one heuristic is particularly effective.     

Inverse Eigenvalue Problem in Structural Dynamics Design

1 Introduction Structural dynamics design is to design a structure subject to the dynamic characteristics re- quirement, i.e., determine physical and geometrical parameters such that the structure has the given frequencies and (or) mode shapes. This problem often arises in engineering connected with vibration. Recently, Joseph [1], Li et al. [2,3] converted the structural dynamics design to the following inverse eigenvalue problem. GIEP Let x = (x1, , xm)T , and let A(x) and B(x) be real n…     

On optimal shape design of systems governed by mixed Dirichlet-Signorini boundary value problems

A problem for finding optimal shape for systems governed by the mixed unilateral boundary value problem of Dirichlet-Signorini-type is considered. Conditions for the solvability of the problem are stated when a variational inequality formulation and when a penalty method is used for solving the state problem in question. The asymptotic relation of design problems based on these two formulations is presented. The optimal shape design problem is discretized by means of finite element method. The convergence results for the approximation are proved. The discretized versions are then formulated as a non-linear programming problem. Results of practical computations of the problem in question are reported.     

Preemptive and nonpreemptive multi-objective programming: Relationship and counterexamples

In this paper, we formally establish connections between two standard approaches proposed for resolving multi-objective programs, namely, the nonpreemptive and the preemptive methods. We demonstrate in the linear case that, if the preemptive problem has an optimal solution, then there exists a set of weights for the nonpreemptive problem, such that any optimal solution to the nonpreemptive problem is optimal to the preemptive problem. Conversely, and more importantly, any optimal solution to the preemptive problem is optimal to the nonpreemptive problem. A similar result is established for arbitrary multi-objective functions being optimized over a finite discrete set. Thus, the preemptive problem is subsumed within the nonpreemptive problem in these cases. Although we actually construct a set of equivalent weights, we do not advocate our technique as a computational device for solving the preemptive problem. However, a previous attempt (Ref. 1), which does prescribe a set of equivalent weights to solve a preemptive problem as a linear program, is shown to be erroneous. Moreover, our constructive proof exhibits the features of the problem which govern the determination of such equivalent weights.     

A hybrid method for multidimensional scaling using city-block distances

The problem of multidimensional scaling with city-block distances in the embedding space is reduced to a two level optimization problem consisting of a combinatorial problem at the upper level and a quadratic programming problem at the lower level. A hybrid method is proposed combining randomized search for the upper level problem with a standard quadratic programming algorithm for the lower level problem. Several algorithms for the combinatorial problem have been tested and an evolutionary global search algorithm has been proved most suitable. An experimental code of the proposed hybrid multidimensional scaling algorithm is developed and tested using several test problems of two- and three-dimensional scaling.     

Coefficient identification in Euler-Bernoulli equation from over-posed data

A method for solving the inverse problem for coefficient identification in the Euler-Bernoulli equation from over-posed data is presented. The original inverse problem is replaced by a minimization problem. The method is applied to the problem for identifying the coefficient in the case when it is a piece-wise polynomial function. Several examples are elaborated and the numerical results confirm that the solution of the imbedding problem coincides with the direct simulation of the original problem within the second order of approximation.     

Boundary conditions of the second-order differential equation and the Riccati equation

The conversion of a second-order linear ordinary differential equation with variable coefficients into a Riccati equation depends on whether the second-order problem is an initial-value or two-point boundary-value problem. The distinction is critical in determining the initial condition for the Riccati equation. If the second-order problem is an initial-value problem, the choice of the Riccati transformation depends on whether a zero initial condition for the function or its derivative is specified. If the problem is a two-point boundary-value problem, special methods must be introduced as described in the paper.     

Global Method for Monotone Variational Inequality Problems with Inequality Constraints

We consider optimization methods for monotone variational inequality problems with nonlinear inequality constraints. First, we study the mixed complementarity problem based on the original problem. Then, a merit function for the mixed complementarity problem is proposed, and some desirable properties of the merit function are obtained. Through the merit function, the original variational inequality problem is reformulated as simple bounded minimization. Under certain assumptions, we show that any stationary point of the optimization problem is a solution of the problem considered. Finally, we propose a descent method for the variational inequality problem and prove its global convergence.     

A branch and bound network approach to the canonical constrained entropy problem

In this paper, we present a branch and bound algorithm for solving the constrained entropy mathematical programming problem. Unlike other methods for solving this problem, our method solves more general problems with inequality constraints. The advantage of the proposed technique is that the relaxed problem solved at each node is a singly constrained network problem. The disadvantage is that the relaxed problem has twice as many variables as the original problem. An application to regional planning is given, and an example problem is solved.     

Split Null Point Problems and Fixed Point Problems for Demicontractive Multivalued Mappings

In this paper, we consider the split null point problem and the fixed point problem for multivalued mappings in Hilbert spaces. We introduce a Halpern-type algorithm for solving the problem for maximal monotone operators and demicontractive multivalued mappings, and establish a strong convergence result under some suitable conditions. Also, we apply our problem of main result to other split problems, that is, the split feasibility problem, the split equilibrium problem, and the split minimization problem. Finally, a numerical result for supporting our main result is also supplied.     

An Exact Solution Method for the MTSP

A new mathematical model for the multi-travelling salesman problem (MTSP) is presented. The MTSP formulation is modified, and a branch-and-bound algorithm for solving this problem exactly is developed. The significance of this procedure is that it does not need to transform the problem into a single travelling salesman problem, which has been the case in the dominant algorithms for solving the above problem. Moreover, computational experience has shown that for a fixed number of cities to be visited, the time required to solve the problem decreases markedly as the number of salesmen increases.     

Single machine stochastic JIT scheduling problem subject to machine breakdowns

In this paper we research the single machine stochastic JIT scheduling problem subject to the machine breakdowns for preemptive-resume and preemptive-repeat.The objective function of the problem is the sum of squared deviations of the job-expected completion times from the due date.For preemptive-resume,we show that the optimal sequence of the SSDE problem is V-shaped with respect to expected processing times.And a dynamic programming algorithm with the pseudopolynomial time complexity is given.We discuss the difference between the SSDE problem and the ESSD problem and show that the optimal solution of the SSDE problem is a good approximate optimal solution of the ESSD problem,and the optimal solution of the SSDE problem is an optimal solution of the ESSD problem under some conditions.For preemptive-repeat,the stochastic JIT scheduling problem has not been solved since the variances of the completion times cannot be computed.We replace the ESSD problem by the SSDE problem.We show that the optimal sequence of the SSDE problem is V-shaped with respect to the expected occupying times.And a dynamic programming algorithm with the pseudopolynomial time complexity is given.A new thought is advanced for the research of the preemptive-repeat stochastic JIT scheduling problem.     

MERIT FUNCTION AND GLOBAL ALGORITHM FOR BOX CONSTRAINED VARIATIONAL INEQUALITIES

1 IntroductionWe consider tlie variational inequality problelll, deuoted by VIP(X, F), wliicli is to find avector x* E X such thatF(X*)"(X -- X-) 2 0, VX E X, (1)where F: R" - R" is any vector-valued f11uction and X is a uonelllpty subset of R'.This problem has important applicatiolls. in equilibriun1 modeIs arising in fields such asecououtics, transportatioll scieuce alld operations research. See [1]. There exist mauy lllethodsfor solviug tlie variational li1equality problem VIP(X. …     

2010年研究生数学建模竞赛A题综述

第七届全国研究生数学建模竞赛A题是生物信息学中的一个急需解决的问题.虽然有关问题的研究已经经历了十多年,但由于问题的复杂性,人们的认识还很局限,基本的结论大多还以定性的为主,定量的探讨正方兴未艾.对参赛队员来讲解决该问题是一个极大的挑战.研究生们在讨论该问题时,大多直接进行分类.然而对于一个小样本的学习问题,显然这样做是行不通的.所以问题的关键是从数学和生物学角度减少用于分类的特征数目.同时,对于获取的基因标签,需要从临床上或生物学角度找到验证.该问题的求解过程引导研究生们从数学建模走向解决实际问题.     

A semidefinite programming approach for solving fractional optimal control problems

This paper presents a numerical scheme for solving fractional optimal control. The fractional derivative in this problem is in the Riemann–Liouville sense. The proposed method, based upon the method of moments, converts the fractional optimal control problem to a semidefinite optimization problem; namely, the nonlinear optimal control problem is converted to a convex optimization problem. The Grunwald–Letnikov formula is also used as an approximation for fractional derivative. The solution of fractional optimal control problem is found by solving the semidefinite optimization problem. Finally, numerical examples are presented to show the performance of the method.     

Numerical solution of an equilibrium problem of based on the generalized level method

An equilibrium problem is studied whose special case is finding a Nash point in a noncooperative multiperson game. A numerical algorithm for solving this problem is described. Conditions on the problem are stated under which an estimate is obtained for the convergence rate of the algorithm to a unique solution of the problem. The results are used for a numerical analysis of noncooperative games.