最短时限最小耗费的缺省指派问题及决策求解

章指出了存在于军事决策与管理科学中最短时限最少耗费的缺省指派问题，并对其进行了深入的理论研究。论证了逼近最短时限的一个重要的定理及联系最短时限、最少耗费缺省指派最优解与经典指派问题最优解之间的相关性定理，据此首次建立了求解最短时限、最少耗费缺省指派的决策方法，这一方法可被广泛地应用于军事决策中进攻目标最优缺省选择与经济建设中工程最优缺省立项尽快见效等方面的一类新的科学决策。     

指派矩阵同解改造理论变换定理论证

本文对指派问题的“周良泽算法”赖以成立而又尚未具体证明的一个重要的基础性定理，给出了严谨的论证，对指派矩阵同解改造理论作了抬遗补证的工作。     

一类最优指派问题的动态规划模型

考虑一类指派问题：欲指派m个人去做n项工作(m≥n)，要求每个人只做一项工作，第j项工作可以由b_j个人共同去做，其中，b_j(b_j≥1)是待求的未知数，j=1,2,…,n,满足．假定已知第i人做第j项工作的效益为c_ij≥0,i=1,2,…m;j=1,2,…,n.本文建立了求解上述问题最优指派（即使总的效益最大)的动态规划模型．     

有资格限制的指派问题的求解方法

在实际的指派工作中，常会遇到某个人有没有资格去承担某项工作的问题，因此，本建立了有资格限制的指派问题的数学模型。在此数学模型中，将效益矩阵转化为判定矩阵，由此给出了判定此种指派问题是否有解的方法；在有解的情况下，进一步将效益矩阵转化为求解矩阵，从而将有资格限制的指派问题化为传统的指派问题来求解。最后给出了一个数值例子来说明这样的处理方法是有效的。     

基于全局搜索算法的不平衡指派问题研究

目前求解不平衡指派问题的主要是将其转化为平衡的指派问题后再去处理.针对不平衡指派问题提出了全局搜索算法,算法不用将不平衡问题转化为平衡问题进行求解,而是基于全局最优策略对任务进行指派,方法理论更加简单,操作更加方便,使得不平衡指派问题得到了很好地解决,同时,这种算法对平衡指派问题、运输问题等依然有效.     

双层指派模型及算法

介绍了指派问题应用中出现的一种新类型——双层指派问题,建立了双层指派问题的数学模型,并提出了针对双层指派模型的算法,最后给出它在铁路客车车底周转运用中的实例.     

求解指派问题的一个算法

为了便于建立与指派问题有关的决策支持系统，本给出了一个求解指派问题的数值算法，证明了算法的理论依据。该算法能求得问题的最优解，并具有易于编程实现、收敛性好等优点，大量数值实验表明该算法非常实用有效。     

任务数多于人数的指派问题

本文给出任务数多于人数指派问题的两种解决方法。     

指派问题在供应商选优决策中的应用

通常供应链中供应商选优问题为多指标决策问题,本将此问题视为指派问题。指派问题中的关键是确定“效率”矩阵,本充分利用供应商单排序结果,评价指标权重以及供应商指标评价值构造了“效率”矩阵,建立了供应商综合选优指派问题模型,案例试算表明该方法合理、有效,为多指标方案决策提供了又一种可行的决策方法。     

多目标指派问题在潜艇兵力配置中的应用

运用模糊数学的思想，首先将各目标下的属性值矩阵转化为模糊关系矩阵，再将模糊关系合成矩阵与解决传统指派问题的匈牙利法相结合，提出一种求解多目标指派问题的综合方法：模糊匈牙利法，并结合优化潜艇兵力配置问题进行了应用分析。     

An implementation of exact knapsack separation

Cutting planes have been used with great success for solving mixed integer programs. In recent decades, many contributions have led to successive improvements in branch-and-cut methods which incorporate cutting planes in branch and bound algorithm. Using advances that have taken place over the years on 0–1 knapsack problem, we investigate an efficient approach for 0–1 programs with knapsack constraints as local structure. Our approach is based on an efficient implementation of knapsack separation problem which consists of the four phases: preprocessing, row generation, controlling numerical errors and sequential lifting. This approach can be used independently to improve formulations with cutting planes generated or incorporated in branch and cut to solve a problem. We show that this approach allows us to efficiently solve large-scale instances of generalized assignment problem, multilevel generalized assignment problem, capacitated \(p\)-median problem and capacitated network location problem to optimality.     

On the Use of Exact and Heuristic Cutting Plane Methods for the Quadratic Assignment Problem

This paper uses the formulation of the quadratic assignment problem as that of minimizing a concave quadratic function over the assignment polytope. Cutting plane procedures are investigated for solving this problem. A lower bound derived on the number of cuts needed for termination indicates that conventional cutting plane procedures would require a huge computational effort for the exact solution of the quadratic assignment problems. However, several heuristics which are derived from the cutting planes produce optimal or good quality solutions early on in the search process. An illustrative example and computational results are presented.     

A cutting plane algorithm for graph coloring

We present an approach based on integer programming formulations of the graph coloring problem. Our goal is to develop models that remove some symmetrical solutions obtained by color permutations. We study the problem from a polyhedral point of view and determine some families of facets of the 0/1-polytope associated with one of these integer programming formulations. The theoretical results described here are used to design an efficient Cutting Plane algorithm.     

An infeasible (exterior point) simplex algorithm for assignment problems

The so called Modified Hung—Rom Algorithm, based upon theoretical considerations of Hirsch-paths, seems to be one of the most efficient algorithms for assignment problems. Since any two basic feasible solutions to a linear problem can always be connected with a short simplex path passing through the infeasible region, development of algorithms based upon theoretical considerations on infeasible paths seems to be of great practical interest. This paper presents an algorithm of this kind for assignment problems.     

Extensions of the sequential stochastic assignment problem

The sequential stochastic assignment problem (SSAP) allocates N workers to N IID sequentially arriving tasks so as to maximize the expected total reward. This paper studies two extensions of the SSAP. The first one assumes that the values of any two consecutive tasks are dependent on each other while the exact number of tasks to arrive is unknown until after the final arrival. The second extension generalizes the first one by assuming that the number of workers is also random. Optimal assignment policies for both problems are derived and proven to have the same threshold structure as the optimal policy of the SSAP.     

关于存在多组最优解的整数线性规划问题的割平面法的研究

利用割平面法求解具有多组最优解情形的整数线性规划问题时,会出现不能求出全部最优解的现象,这是割平面法的一个缺陷.针对割平面法的这种缺陷,基于构造非线性标量化函数时引入凸锥的思想,提出了一种割平面一线性交叉搜索方法,这种割平面一线性交叉搜索方法可以解决利用割平面法求解整数线性规划问题时出现的缺陷.最后,通过数值例验证了割平面一线性交叉搜索方法的可行性与有效性.     

千古绝技“割圆术”(续)

本文是文[1]的续篇,进一步阐述“割圆术”的思维模式对现代演化数学研究的启迪意义。全文的结论是,无论是数学成就还是数学才能,刘徽都应当与“古代数学之神”阿基米德并列。     

On a Primal-Dual Analytic Center Cutting Plane Method for Variational Inequalities

We present an algorithm for variational inequalities VI( , Y) that uses a primal-dual version of the Analytic Center Cutting Plane Method. The point-to-set mapping is assumed to be monotone, or pseudomonotone. Each computation of a new analytic center requires at most four Newton iterations, in theory, and in practice one or sometimes two. Linear equalities that may be included in the definition of the set Y are taken explicitly into account.We report numerical experiments on several well—known variational inequality problems as well as on one where the functional results from the solution of large subproblems. The method is robust and competitive with algorithms which use the same information as this one.     

A Special Multi-Objective Assignment Problem

The following assignment problem is considered. There are n activities to be assigned to n personnel. The cost of assigning activity i to person j is c _ij . It is required to find all the efficient assignments, i.e. those for which there exists no other assignment which has at least as small costs for each person and strictly smaller costs for at least one person. The main results are as follows. In Theorem 1 it is shown that whereas, for many integer problems, the standard scalar weighting factor approach will not produce all the efficient solutions, in this case it will. In Theorem 2 it is shown that when each efficient vector is determined by a single assignment solution, the efficient set is identical to the set of efficient vertices of the convex hull of the assignment solution set.     

Epsilon Dominance and Constraint Partitioning in Multiple Objective Problems

In this paper we consider efficient sets of multiple objective problems, in which the feasible action set is the intersection of two other sets, and where one of these sets has a special structure, such as an assignment or transportation structure. The objective is to find the efficient set of the special structure set, and its intersection with the other set, and to examine how good an approximation this set is to the desired efficient set. The approximation set is called an -efficient solution set. Some theoretical partition results are given for a special constraint structure with upper bounds on the objective function levels. For the case of 0-efficient solution sets, and finite explicit sets, a computational cost analysis of two computational sequences is given. We also consider two other 0-efficient solution set cases. Then -efficiency is considered for linear problems. Finally, the approach is illustrated by a special multiple objective transportation problem.