关于求解DEA原始CCR模型中最优输入输出权重的方法

本文给出了求解DEA原始CCR模型中最优输入输出权重的简便方法：首先将原始CCR模型化为线性规划模型，然后从该线性规划模型的对偶模型入手，运用单纯形法，在得到决策单元最优效率评价指数时，根据线性规划的对偶理论，得到决策单元最优输入输出权重。该权重可用在逆DEA新算法中。     

用罚函数求解线性双层规划的全局优化方法

用罚函数法将线性双层规划转化为带罚函数子项的双线性规划问题，由于其全局最优解可在约束域的极点上找到，利用对偶理论给出了一种求解该双线性规划的方法，并证明当罚因子大于某一正数时，双线性规划的解就是原线性双层规划的全局最优解。     

一类系数为梯形模糊数的两层多随从线性规划模型

针对一类系数为梯形模糊数的两层多随从线性规划问题,利用模糊结构元理论定义了模糊结构元加权序,证明了一类系数为梯形模糊数的两层多随从线性规划问题的最优解等价于两层多随从线性规划问题的最优解.根据线性规划的对偶定理和互补松弛性质,得到了两层多随从线性规划模型的最优化条件.最后,利用两层多随从线性规划模型的最优化条件,设计了求解一类系数为梯形模糊数的两层多随从线性规划问题的算法,并通过算例验证了该方法的可行性和合理性.     

第一阶段原有单纯形和对偶单纯形算法的计算比较

线性最优化广泛应用于经济与管理的各个领域.在线性规划问题的求解中,如果一个初始基本可行解没有直接给出,则常采用经典的两阶段法求解.对含有"≥"不等式约束的线性规划问题,讨论了第一阶段原有单纯形法和对偶单纯形法两种算法形式,并根据第一阶段问题的特点提出了改进的对偶单纯形枢轴准则.最后,通过大规模数值试验对两种算法进行计算比较,结果表明,改进后的对偶单纯形算法在计算效率上明显优于原有单纯形算法.     

存贮问题的优化算法

本文根据经济模型的特殊结构,利用对偶线性规划的理论和其它技巧,简化求解过程,有利于模型的普及应用.     

线性规划的对偶理论在图解法中的应用

对于多个变量两个约束的线性规划,首先利用线性规划的对偶理论,写出其对偶问题;其次利用图解法求出对偶问题的最优解,最后利用互补松弛条件求出原问题的最优解.     

线性规划影子价格的求解判断方法探讨

针对线性规划对偶问题最优解不唯一时,在已有文献提出的对偶最优解不唯一的充要条件定理基础上,结合线性规划灵敏度分析,提出影子价格的求解判断的简单准则及其命题,并进行证明.最后,用算例加以分析,指出该判断方法简单易行,也可作为通过计算软件求解影子价格的准确判断方法.     

求解弱线性双层规划问题的一种全局优化方法

双层规划在经济、交通、生态、工程等领域有着广泛而重要的应用.目前对双层规划的研究主要是基于强双层规划和弱双层规划.然而,针对弱双层规划的求解方法却鲜有研究.研究求解弱线性双层规划问题的一种全局优化方法,首先给出弱线性双层规划问题与其松弛问题在最优解上的关系,然后利用线性规划的对偶理论和罚函数方法,讨论该松弛问题和它的罚问题之间的关系.进一步设计了一种求解弱线性双层规划问题的全局优化方法,该方法的优势在于它仅仅需要求解若干个线性规划问题就可以获得原问题的全局最优解.最后,用一个简单算例说明了所提出的方法是可行的.     

关于线性规划问题熵障碍对偶法的注记

线性规划是目标优化问题中最常用的模型。关于大规模线性规划问题的有效求解问题一直受到人们的关注。熵障碍对偶法是继内点法之后,又一解线性规划问题的新的算法。本文讨论了熵障碍对偶法的推广形式及其梯度类算法的收敛性。     

解一般线性规划逆问题的一个O（n^3L）算法

本文讨论了一般线性规划逆问题在各种情况下的求解，并基于解凸二次规划的原对偶内点算法，给出了一个O（n3L）算法和一个实用算法．     

Creating Advanced Bases For Large Scale Linear Programs Exploiting Embedded Network Structure

In this paper, we investigate how an embedded pure network structure arising in many linear programming (LP) problems can be exploited to create improved sparse simplex solution algorithms. The original coefficient matrix is partitioned into network and non-network parts. For this partitioning, a decomposition technique can be applied. The embedded network flow problem can be solved to optimality using a fast network flow algorithm. We investigate two alternative decompositions namely, Lagrangean and Benders. In the Lagrangean approach, the optimal solution of a network flow problem and in Benders the combined solution of the master and the subproblem are used to compute good (near optimal and near feasible) solutions for a given LP problem. In both cases, we terminate the decomposition algorithms after a preset number of passes and active variables identified by this procedure are then used to create an advanced basis for the original LP problem. We present comparisons with unit basis and a well established crash procedure. We find that the computational results of applying these techniques to a selection of Netlib models are promising enough to encourage further research in this area.     

基于递归型神经网络动力学求解时变凸二次规划

为了在线求解时变凸二次规划问题,实现误差精度更高、求解时间更短和收敛速度更快的目标。本文采用了求解问题更快的时变网络设计参数,选择了有限时间可以收敛的Sign-bi-power激活函数,构造了一种改进的归零神经网络动力学模型。其后,分析了模型的稳定性和收敛性,得到其解能够在有限时间内收敛。最后,在仿真算例中,与传统的梯度神经网络和归零神经网络模型相比,所提模型具有更高的误差精度、更短的求解时间和更快的收敛速度,优于前两种网络模型。     

切割定界与整数分枝结合求解整数线性规划

把一种改进的割平面方法和分枝定界的思想结合起来求解整数线性规划 ( ILP)问题 .它利用目标函数等值面的移动来切去相应 ( LP)的可行域中含其非整数最优解但不含 ( ILP)可行解的“无用部分”,并将对应的目标函数值作为 ( ILP)目标最优值的一个上界 ;最后 ,通过 ( LP)最优解中非整数基变量的整数分枝来获得整数线性规划的最优解 .     

A further study on inverse linear programming problems

In this paper we continue our previous study (Zhang and Liu, J. Comput. Appl. Math. 72 (1996) 261–273) on inverse linear programming problems which requires us to adjust the cost coefficients of a given LP problem as less as possible so that a known feasible solution becomes the optimal one. In particular, we consider the cases in which the given feasible solution and one optimal solution of the LP problem are 0–1 vectors which often occur in network programming and combinatorial optimization, and give very simple methods for solving this type of inverse LP problems. Besides, instead of the commonly used l₁ measure, we also consider the inverse LP problems under l_∞ measure and propose solution methods.     

A dynamical model for solving degenerate quadratic minimax problems with constraints

This paper presents a new neural network model for solving degenerate quadratic minimax (DQM) problems. On the basis of the saddle point theorem, optimization theory, convex analysis theory, Lyapunov stability theory and LaSalle invariance principle, the equilibrium point of the proposed network is proved to be equivalent to the optimal solution of the DQM problems. It is also shown that the proposed network model is stable in the sense of Lyapunov and it is globally convergent to an exact optimal solution of the original problem. Several illustrative examples are provided to show the feasibility and the efficiency of the proposed method in this paper.     

Polynomial-time identification of robust network flows under uncertain arc failures

We propose Linear Programming (LP)-based solution methods for network flow problems subject to multiple uncertain arc failures, which allow finding robust optimal solutions in polynomial time under certain conditions. We justify this fact by proving that for the considered class of problems under uncertainty with linear loss functions, the number of entities in the corresponding LP formulations is polynomial with respect to the number of arcs in the network. The proposed formulation is efficient for sparse networks, as well as for time-critical networked systems, where quick and robust decisions play a crucial role.     

A dynamical model for solving degenerate quadratic minimax problems with constraints

This paper presents a new neural network model for solving degenerate quadratic minimax (DQM) problems. On the basis of the saddle point theorem, optimization theory, convex analysis theory, Lyapunov stability theory and LaSalle invariance principle, the equilibrium point of the proposed network is proved to be equivalent to the optimal solution of the DQM problems. It is also shown that the proposed network model is stable in the sense of Lyapunov and it is globally convergent to an exact optimal solution of the original problem. Several illustrative examples are provided to show the feasibility and the efficiency of the proposed method in this paper.     

Solving a class of geometric programming problems by an efficient dynamic model

In this paper, a neural network model is constructed on the basis of the duality theory, optimization theory, convex analysis theory, Lyapunov stability theory and LaSalle invariance principle to solve geometric programming (GP) problems. The main idea is to convert the GP problem into an equivalent convex optimization problem. A neural network model is then constructed for solving the obtained convex programming problem. By employing Lyapunov function approach, it is also shown that the proposed neural network model is stable in the sense of Lyapunov and it is globally convergent to an exact optimal solution of the original problem. The simulation results also show that the proposed neural network is feasible and efficient.     

A technique for speeding up the solution of the Lagrangean dual

We propose techniques for the solution of the LP relaxation and the Lagrangean dual in combinatorial optimization and nonlinear programming problems. Our techniques find the optimal solution value and the optimal dual multipliers of the LP relaxation and the Lagrangean dual in polynomial time using as a subroutine either the Ellipsoid algorithm or the recent algorithm of Vaidya. Moreover, in problems of a certain structure our techniques find not only the optimal solution value, but the solution as well. Our techniques lead to significant improvements in the theoretical running time compared with previously known methods (interior point methods, Ellipsoid algorithm, Vaidya's algorithm). We use our method to the solution of the LP relaxation and the Langrangean dual of several classical combinatorial problems, like the traveling salesman problem, the vehicle routing problem, the Steiner tree problem, thek-connected problem, multicommodity flows, network design problems, network flow problems with side constraints, facility location problems,K-polymatroid intersection, multiple item capacitated lot sizing problem, and stochastic programming. In all these problems our techniques significantly improve the theoretical running time and yield the fastest way to solve them.     

分类问题的在线顺序双并联快速学习机

双并联前馈神经网络模型是单层感知机和单隐层前馈神经网络的混合结构,本文构造了一种双并联快速学习机算法,与其他类似算法比较,提出的算法能利用较少的隐层单元及更少的待定参数,获得近似的学习性能.数值实验表明,对很多实际分类问题,提出的算法具备更佳的泛化能力,因而可以作为快速学习机算法的有益补充.