贷款分配方法的数学模型及其解法

为了解决三角债问题，银行给出一笔贷款，应该如何分配这笔贷款，使清理的债务达到最大。本文建立这个问题的数学模型，并且给出一个解法。     

Detecting embedded pure network structures in LP problems

Recently, linear programming problems with special structures have assumed growing importance in mathematical programming. It is well known that exploiting network structures within linear programs can lead to considerable improvement of the computational solution of large-scale linear programming problems. A linear program is said to contain an embedded network structure provided that some subset of its constraints can be interpreted as specifying conservation of flow. If a column of the constraint matrix has at most two non-zeros, then it leads to embedded generalized network structure and if these non-zeros are unit elements and of opposite signs, then it leads to embedded pure network structure. In this paper, we are concerned with algorithms for detecting embedded pure network structures within linear programs. The network extraction methods are presented in two groups. The first group covers deletion and addition based algorithms and the second group covers GUB based algorithms. We have extended the GUB based algorithm appearing in the second group by introducing Markowitz merit count approach for exploiting matrix non zeros. A set of well known test problems has been used to carry out computational experiments which show that our extensions to the GUB based algorithms give better results than the algorithms reported earlier.     

关于二次规划问题分段线性同伦算法的改进

本文利用Ｃｈｏｌｅｓｋｙ分解，Ｇａｕｓｓ消去等技术和定义适当的同伦映射，将关于二次规划问题的分段线性同伦算法加以改进，改进后的算法，对于严格凸二次规划来说，计算效率与Ｇｏｌｄｆａｒｂ－Ｉｄｎａｎｉ的对偶法相当。     

Interactive optimization

Optimization algorithms or heuristics in which the user interacts significantly either during the solution process or as part of post-optimality analysis are becoming increasingly popular. An important underlying premise of such man/machine systems is that there are some steps in solving a problem in which the computer has an advantage and other steps in which a human has an advantage. This paper first discusses how man/machine systems can be useful in facilitating model specification and revision, coping with aspects of a problem that are difficult to quantify and assisting in the solution process. We then survey successful systems that have been developed in the areas of vehicle scheduling, location problems, job shop scheduling, course scheduling, and planning language-based optimization.     

Global saddle-point duality for quasi-concave programs

General and quasi-concave non-differentiable cases of the maximization of the minimun between two functions are considered. With the aid of duality theory for mathematical programming involving conjugate-like operators and by defining a bifunction we construct a new Lagrangian and generate a class of perturbations. New saddle-point theorems are presented, and equivalence is proved between the existence of a saddle-point and the existence of a certain cone-supporting property of the perturbation function. These results suggest possible improvements in multiplier methods.This work was partially supported by a grant from Control Data.     

Computational aspects of two-segment separable programming

Recursive separable programming algorithms based on local, two-segment approximations are described for the solution of separable convex programs. Details are also given for the computation of lower bounds on the optimal value by both a primal and a dual approach, and these approaches are compared. Computational comparisons of the methods are provided for a variety of test problems, including a water supply application (with more than 600 constraints and more than 900 variables) and an econometric modelling problem (with more than 200 variables). Research supported by National Science Foundation Grants MCS74-20584 A02 and MCS-7901066.     

A bump triangular dynamic factorization algorithm for the simplex method

A dynamic factorization algorithm is developed which algebraically partitions the basis inverse in such a manner so that the simplex method can be executed from a series of small inverses and the basis itself. This partition is maintained dynamically so that the additional memory required to represent the basis inverse reduces to this series of small inverses for in-core implementations.The algorithm is intended for use in solving general large-scale linear programming problems. This new method of basis representation should permit rather large problems to be solved completely in-core.Preliminary computational experience is presented and comparisons are made with Reid's sparsity-exploiting variant of the Bartels—Golub decomposition for linear programming bases. The computational experience indicated that a significant reduction in memory requirements can usually be obtained using the dynamic factorization approach with only a slight (up to about 20%) degradation of execution time.This research was supported in part by the Air Force Office of Scientific Research, Air Force System Command, USAF, under AFOSR Contract/Grant Number AFOSR-74-2715.     

A multiplier method with automatic limitation of penalty growth

This paper presents a multiplier method for solving optimization problems with equality and inequality constraints. The method realizes all the good features that were foreseen by R. Fletcher for this type of algorithm in the past, but which suffers from none of the drawbacks of the earlier attempts.Research sponsored by the National Science Foundation (RANN) Grant ENV76-04264 the National Science Foundation Grant ENG73-08214-A01 and the Sweden-American Foundation.     

Elimination of bounds in optimization problems by transforming variables

The problem of minimizing a nonlinear objective function ofn variables, with continuous first and second partial derivatives, subject to nonnegativity constraints or upper and lower bounds on the variables is studied. The advisability of solving such a constrained optimization problem by making a suitable transformation of its variables in order to change the problem into one of unconstrained minimization is considered. A set of conditions which guarantees that every local minimum of the new unconstrained problem also satisfies the first-order necessary (Kuhn—Tucker) conditions for a local minimum of the original constrained problem is developed. It is shown that there are certain conditions under which the transformed objective function will maintain the convexity of the original objective function in a neighborhood of the solution. A modification of the method of transformations which moves away from extraneous stationary points is introduced and conditions under which the method generates a sequence of points which converges to the solution at a superlinear rate are given.