Variations on a cutting plane method for solving concave minimization problems with linear constraints

A cutting plane method for solving concave minimization problems with linear constraints has been advanced by Tui. The principle behind this cutting plane has been applied to integer programming by Balas, Young, Glover, and others under the name of convexity cuts. This paper relates the question of finiteness of Tui's method to the so-called generalized lattice point problem of mathematical programming and gives a sufficient condition for terminating Tui's method. The paper then presents several branch-and-bound algorithms for solving concave minimization problems with linear constraints with the Tui cut as the basis for the algorithm. Finally, some computational experience is reported for the fixed-charge transportation problem.     

A finite descent theory for linear programming,piecewise linear convex minimization,and the linear complementarity problem

A descent algorithm simultaneously capable of solving linear programming, piecewise linear convex minimization, and the linear complementarity problem is developed. Conditions are given under which a solution can be found in a finite number of iterations using the geometry of the problem. A computer algorithm is developed and test problems are solved by both this method and Lemke's algorithm. Current results indicate a decrease in the number of cells visited but an increase in the total number of pivots needed to solve the problem.     

The truck assignment problem

Let us consider the following problem: A group of cement factories produces several types of cement, but each factory produces only one type. There is also a group of purchasers and each purchaser may need several types of cement. The amounts supplied and the demands are assumed to be known for each cement factory and each purchaser. Each cement factory has several trucks, but there is only one dispatcher for ail of the trucks from all of the factories. It is assumed that the entire lcad of each truck is for one purchaser only. A truck begins its workday by leaving its base depot loaded and ends its day by returning to it empty. During the day it may be required to transport cement from any of the cement factories. The distances from various factories to individual purchasers are known. The problem to be solved is that of finding a truck schedule such that cement in the needed quantities is delivered daily to the individual purchasers and in such a manner that the total truck-kilometers traveled will be as small as possible. This paper presents the method of solution, though the assumption of an 8-hour workday may not be met. On the other hand, there are methods developed for effecting a variety of cyclic routings which can be used to lend considerable flexibility to the schedules.     

Efficient computational devices for the capacitated transportation problem

This paper presents the details for applying and specializing the work of Ellis Johnson [10] and [11] to develop a primal code for the well-known capacitated transportation problem. The code was developed directly from the work of Johnson, but is similar to codes developed by Glover, Karney, Klingman, and Napier [6] and Srinivasan and Thompson [14]. The emphasis in the presentation is the use of the graphical representation of the basis to carry out the revised simplex operations. This is a means of exploiting the special structure and sparseness of the constraint matrix to minimize computational effort and storage requirements. We also present the results of solving several large problems with the code developed.     

例谈数学问题解决中的创造性思维策略

数学思维策略的选择和运用对于数学问题解决的成败起着关键的作用。通过实例介绍了数学问题解决中常用的几种创造性思维策略:逆向思维策略、发散思维策略、直觉思维策略、转化思维策略和联想类比策略。最后强调指出我们不仅要学生掌握这些思维策略,更重要的是要要求学生在学习、生活中经常有意识地去加以运用,尤其是创造性的运用。这不仅有助于今天的数学学习,更有助于学生将来的发明和创造。     

基于时滞分割法的具有leakage项时滞的离散型神经网络状态估计

摘要：研究一类具有leakage时滞的离散型神经网络的状态估计问题．通过构造新的Lyapunov泛函得到保证估计误差全局渐近稳定的充分条件,并通过求解一个线性矩阵不等式（LMI）得到状态估计器的增益矩阵．采用一种新的时滞分割方法将变时滞区间分割为多个子区间,使该结果在获得更小的保守性同时也降低了计算的复杂度．     

直杆塑性动力屈曲的能量准则和特征参数解

提出弹塑性应力波作用下直杆动力屈曲的定量求解方法,将临界应力和惯性指数作为一对特征参数求解.由相平衡邻位形准则得出屈曲控制方程和边界条件,由所导出的能量转换和守恒准则得出压缩波阵面上的附加约束方程,由此得出了问题的完备定解条件,从而提出了求解直杆塑性动力屈曲的特征参数方法.     

Optimal schedules for special structure flowshops

This paper considers the problem of scheduling a given number of jobs on a specified number of machines in a flowshop where the objective function is to minimize the total throughput time in which all jobs complete processing on all machines. Based on the combinatorial analysis of the problem, several simple algorithms are developed for solving special structure flowshop scheduling problems where the process times are not completely random, but bear a well-defined relationship to one another. The proposed algorithms are both simple and computationally efficient and can optimally solve large-sized problems even with manual computational devices.     

嵌入CPU PCB结构测试方法研究

论述了嵌入CPU印制电路板（PCB）故障测试与故障诊断的一般方法。研究表明:只要满足一定的测试性设计要求,嵌入CPU PCB采用结构化测试方法是可行的。     

A generalized euclidean procedure for integer linear programs

This paper investigates a new procedure for solving the general-variable pure integer linear programming problem. A simple transformation converts the problem to one of constructing nonnegative integer solutions to a system of linear diophantine equations. Rubin's sequential algorithm, an extension of the classic Euclidean algorithm, is used to find an integer solution to this system of equations. Two new theorems are proved on the properties of integer solutions to linear systems. This permits a modified Fourier-Motzkin elimination method to be used to construct a nonnegative integer solution. An experimental computer code was developed for the algorithm to solve some test problems selected from the literature. The computational results, though limited, are encouraging when compared with the Gomory all-integer algorithm.     

索的UL列式分析方法

通过求解索的微分方程边值问题 ,提出了分析索的收敛迭代公式。利用迭代解可顺利地确定索端位置坐标差、索力及索重之间的关系。算例表明 :本文计算索的方法 ,理论上可达到任意高的精度 ,可十分方便地用于含有索或索网混合复杂结构物的大变形分析 ,用这种方法能解决斜拉桥缆索应力松驰的计算问题。     

A branch and bound algorithm for allocation problems in which constraint coefficients depend upon decision variables

A branch and bound algorithm is developed for a class of allocation problems in which some constraint coefficients depend on the values of certain of the decision variables. Were it not for these dependencies, the problems could be solved by linear programming. The algorithm is developed in terms of a strategic deployment problem in which it is desired to find a least-cost transportation fleet, subject to constraints on men/materiel requirements in the event of certain hypothesized contingencies. Among the transportation vehicles available for selection are aircraft which exhibit the characteristic that the amount of goods deliverable by an aircraft on a particular route in a given time period (called aircraft productivity and measured in kilotons/aircraft/month) depends on the ratio of type 1 to type 2 aircraft used on that particular route. A model is formulated in which these relationships are first approximated by piecewise linear functions. A branch and bound algorithm for solving the resultant nonlinear problem is then presented; the algorithm solves a sequence of linear programming problems. The algorithm is illustrated by a sample problem and comments concerning its practicality are made.     

Transshipment along a single road

This article explores the problem of the transshipment of goods between centers that are situated along a single road. Costs are incurred both for goods that are shipped and for goods that remain in their original centers. A procedure is developed that determines a partial optimal assignment by use of a northwest corner rule solution. This partial assignment then is completed by solving a number of smaller tridiagonal transportation problems.     

Optimal location of public facilities

Location of both public and private facilities has become an important consideration in today's society. Progress in solution of location problems has been impeded by difficulty of the fixed charge problem and the lack of an efficient algorithm for large problems. In this paper a method is developed for solving large-scale public location problems. An implicit enumeration scheme with an imbedded transportation algorithm forms the basis of the solution technique.     

货郎担问题新算法

将指派问题的匈牙利解法用于货郎担问题,通过恰当地添加大正数构造效率矩阵,得到了计算货郎担问题较快的算法。文中给出的2个例子具体地说明了算法实施过程,该算法具有一定的实用性。     

战时铁路运输油料抢收模拟优化

战时,铁路运输油料抢收是一个受到各种随机因素影响的复杂过程,很难采用数学方法建立模型求解。以运筹学的排队论为建模指导思想,采用GPSSW语言对这一动态过程进行模拟,并对模拟结果进行统计分析,结合实际情况采用优化技术对模拟结果作出改进,从而得到最佳的抢收方案。结果表明,该模拟方法适用于解决此类半结构化问题,可为战时铁路运输油料抢收提供有效的决策支持。     

Postoptimality analysis in zero-one programming by implicit enumeration

The procedures for postoptimality analysis that are so much a part of linear programming studies have no simple counterparts in an integer programming context. In the case of Balas' Additive Algorithm, however, it would appear that the capacity of the technique to facilitate certain types of postoptimality analysis has not been fully exploited. This paper proposes an extension of the additive algorithm that utilizes insights generated while solving the original problem to do subsequent analysis upon it. In particular, procedures are developed for doing limited parameter ranging and for seeking new optima in light of parameter changes.     

战车火控外弹道实时解算的研究

论证了战车火控系统弹道实时解算技术的现状和发展 ,提出了现代火控弹道问题实时解算的新的数学模型。这一先进的弹道解算设计方法 ,适应于计算机运算速度已大幅提高的技术水平 ,具有高度通用化的特点 ,并且使弹道问题的解算可以完全脱离射表进行     

Adjacency‐based local top‐down search method for finding maximal efficient faces in multiple objective linear programming

It is well‐known that the efficient set of a multiobjective linear programming (MOLP) problem can be represented as a union of the maximal efficient faces of the feasible region. In this paper, we propose a method for finding all maximal efficient faces for an MOLP. The new method is based on a condition that all efficient vertices (short for the efficient extreme points and rays) for the MOLP have been found and it relies on the adjacency, affine independence and convexity results of efficient sets. The method uses a local top‐down search strategy to determine maximal efficient faces incident to every efficient vertex for finding maximal efficient faces of an MOLP problem. To our knowledge, the proposed method is the first top‐down search method that uses the adjacency property of the efficient set to find all maximal efficient faces. We discuss this and other advantages and disadvantages of the algorithm. We also discuss some computational experience we have had with our computer code for implementing the algorithm. This computational experience involved solving several MOLP problems with the code.     

An approximative algorithm for the fixed charge problem

This paper describes an approximate solution method for solving the fixed charge problem. This heuristic approach is applied to a set of test problems to explore the margin of error. The results indicate that the proposed fixed charge simplex algorithm is capable of finding optimal or near optimal solutions to moderate sized fixed charge problems. In the absence of an exact method, this heuristic should prove useful in solving this fundamental nonlinear programming problem.