基于单纯形方法的双层线性规划全局优化算法

通过分析双层线性规划可行域的结构特征和全局最优解在约束域的极点上达到这一特性,对单纯形方法中进基变量的选取法则进行适当修改后,给出了一个求解双层线性规划局部最优解方法,然后引进上层目标函数对应的一种割平面约束来修正当前局部最优解,直到求得双层线性规划的全局最优解.提出的算法具有全局收敛性,并通过算例说明了算法的求解过程.     

一类全局优化问题的线性化方法

本文对带有不定二次约束且目标函数为非凸二次函数的最优化问题提出了一类新的确定型全局优化算法,通过对目标函数和约束函数的线性下界估计,建立了原规划的松弛线性规划,通过对松弛线性规划可行域的细分以及一系列松弛线性规划的求解过程,得到原问题的全局最优解.我们从理论上证明了算法能收敛到原问题的全局最优解.     

求解上层含约束条件且具有模糊决策变量二层线性规划的结构元方法

讨论一类含模糊决策变量二层线性规划模型,利用模糊结构元理论,证明该模型最优解等价于二层线性规划模型最优解,并通过极点搜索法得到该模型最优解,最后通过数值算例验证该方法的可行性。     

线性规划标准型和整数线性规划最优解的两个注记

本文研究线性规划标准型的基本假设所蕴含的一些性质,并探讨整数线性规划最优解和其松弛问题最优解的关系.首先,分别讨论四种情形下线性规划最优解的性质,即无约束线性规划问题、仅有非负约束的线性规划问题、仅有等式约束的线性规划问题,以及标准线性规划问题系数矩阵的列向量有为零的情形等.然后,构造两族二维整数线性规划,其松弛问题的最优解与其(整数)最优解"相距甚远".     

基于遗传算法的二层线性规划问题的求解算法

本研究了下层以最优解返回上层的二层线性规划问题的遗传算法。在提出可行度概念的基础上，构造了二层线性规划上层规划问题的适应度函数，由此设计了求解二层线性规划问题遗传算法。为了提高遗传算法处理约束的能力，在产生初始种群时将随机产生的初始种群变为满足约束的初始种群，从而避免了使用罚函数处理约束带来的困难，最后用实例验证了本提出的二层线性规划的遗传算法的有效性。     

双层规划问题基于对偶理论的遗传算法

针对下层为线性规划的非线性双层规划问题，提出了一种基于下层对偶理论的遗传算法。首先利用下层对偶问题可行域的极点对上层变量的取值域进行划分，使得每一个划分区域对应一个极点。根据原一对偶问题最优解的关系，确定每个划分区域对应的下层最优解。其次利用罚函数方法处理了上层约束，设计了一个依赖于种群变化的动态罚因子。对20个测试问题的数值结果表明，所提出的算法是可行有效的。     

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

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

双层线性规划的一个全局优化方法

用线性规划对偶理论分析了双层线性规划的最优解与下层问题的对偶问题可行域上极点之间的关系，通过求得下层问题的对偶问题可行域上的极点，将双层线性规划转化为有限个线性规划问题，从而用线性规划方法求得问题的全局最优解．由于下层对偶问题可行域上只有有限个极点，所以方法具有全局收敛性．     

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

讨论了一类系数为梯形模糊数的两层线性规划问题,首先是利用模糊结构元理论将梯形模糊数去模糊化,将其转化成常规的两层线性问题,并验证其去模糊化后的常规的两层线性规划的最优解与系数为梯形模糊数的两层线性规划问题的最优解一致,并给出具体的算法,数例进行验证.     

区间线性规划的代数最优解

提出了区间线性规划问题代数最优解的概念,给出了在非负约束的条件下区间矩阵与区间向量乘积的刻画形式,在此基础上建立了区间线性方程组及区间线性不等式组代数可行性的等价条件.最后,建立了标准型区间线性规划问题代数最优解及代数最优值的有效算法,并用若干实例说明了算法的实施过程.     

A new approach for solving linear bilevel problems using genetic algorithms

Bilevel programming involves two optimization problems where the constraint region of the first level problem is implicitly determined by another optimization problem. This paper develops a genetic algorithm for the linear bilevel problem in which both objective functions are linear and the common constraint region is a polyhedron. Taking into account the existence of an extreme point of the polyhedron which solves the problem, the algorithm aims to combine classical extreme point enumeration techniques with genetic search methods by associating chromosomes with extreme points of the polyhedron. The numerical results show the efficiency of the proposed algorithm. In addition, this genetic algorithm can also be used for solving quasiconcave bilevel problems provided that the second level objective function is linear.     

On degeneracy and collapsing in the construction of the set of objective values in a multiple objective linear program

In this paper an algorithm is developed to generate all nondominated extreme points and edges of the set of objective values of a multiple objective linear program. The approach uses simplex tableaux but avoids generating unnecessary extreme points or bases of extreme points. The procedure is based on, and improves, an algorithm Dauer and Liu developed for this problem. Essential to this approach is the work of Gal and Kruse on the neighborhood problem of determining all extreme points of a convex polytope that are adjacent to a given (degenerate) extreme point of the set. The algorithm will incorporate Gal's degeneracy graph approach to the neighborhood problem with Dauer's objective space analysis of multiple objective linear programs.     

A genetic algorithm for solving linear fractional bilevel problems

Bilevel programming has been proposed for dealing with decision processes involving two decision makers with a hierarchical structure. They are characterized by the existence of two optimization problems in which the constraint region of the upper level problem is implicitly determined by the lower level optimization problem. In this paper a genetic algorithm is proposed for the class of bilevel problems in which both level objective functions are linear fractional and the common constraint region is a bounded polyhedron. The algorithm associates chromosomes with extreme points of the polyhedron and searches for a feasible solution close to the optimal solution by proposing efficient crossover and mutation procedures. The computational study shows a good performance of the algorithm, both in terms of solution quality and computational time.     

A regression study of the number of efficient extreme points in multiple objective linear programming

In this paper we employ regression analysis to construct relationships for predicting the number of efficient extreme points in MOLPs (multiple objective linear programs) with up to 120,000 efficient extreme points, and the CPU time to compute them. Principal among the factors affecting the number of efficient extreme points and CPU time are the number of objectives, criterion cone size, number of constraints, number of variables, and the nonzero density of the constraint matrix. The regression equations show the degree to which interactions are present among the factors and provide a more formal basis for understanding how the complexity of the efficient set, an indicator of the difficulty involved in solving a multiple criteria problem, increases with problem size.     

Computation of spectral sets for uncertain linear fractional-order systems

The present paper proposes an algorithm to compute the spectral set of a family of fractional-order pseudo-polynomials. The algorithm makes use of interval constraint propagation technique to find out all the structural roots of the given uncertain fractional-order systems in the given search domain. It is first shown that the problem of finding the spectral set can be formulated as an interval constraint satisfaction problem and then solved using branch and prune algorithm. The algorithm guarantees that all the points of the spectral set are computed to prescribed accuracy. The proposed algorithm is demonstrated on a plant with nonlinear parametric dependencies and also on a practical application of a gas turbine plant.     

约束优化问题的一类光滑罚算法的全局收敛特性

对约束优化问题给出了一类光滑罚算法.它是基于一类光滑逼近精确罚函数 l_p(p\in(0,1]) 的光滑函数 L_p 而提出的.在非常弱的条件下, 建立了算法的一个摄动定理, 导出了算法的全局收敛性.特别地, 在广义Mangasarian-Fromovitz约束规范假设下, 证明了当 p=1 时, 算法经过有限步迭代后, 所有迭代点都是原问题的可行解; p\in(0,1) 时,算法经过有限迭代后, 所有迭代点都是原问题可行解集的内点.     

Determining maximal efficient faces in multiobjective linear programming problem

Finding an efficient or weakly efficient solution in a multiobjective linear programming (MOLP) problem is not a difficult task. The difficulty lies in finding all these solutions and representing their structures. Since there are many convenient approaches that obtain all of the (weakly) efficient extreme points and (weakly) efficient extreme rays in an MOLP, this paper develops an algorithm which effectively finds all of the (weakly) efficient maximal faces in an MOLP using all of the (weakly) efficient extreme points and extreme rays. The proposed algorithm avoids the degeneration problem, which is the major problem of the most of previous algorithms and gives an explicit structure for maximal efficient (weak efficient) faces. Consequently, it gives a convenient representation of efficient (weak efficient) set using maximal efficient (weak efficient) faces. The proposed algorithm is based on two facts. Firstly, the efficiency and weak efficiency property of a face is determined using a relative interior point of it. Secondly, the relative interior point is achieved using some affine independent points. Indeed, the affine independent property enable us to obtain an efficient relative interior point rapidly.     

基于灰色理论的价格控制问题及其算法

针对排污收费的最优定价问题,提出了基于灰色理论的价格控制问题,并给出了该问题的模型及相关的定理。在约束域为非空紧集的条件下,证明了漂移型价格控制问题的最优解一定可以在约束域的极点达到。针对漂移型价格控制问题,采用价格控制问题的搜索算法的求解技术,把灰参数看做一个新的决策变量,将该问题转化为多个含参数的非线性规划问题。最后,通过一算例验证了模型及求解方法的有效性。     

An extension of the simplex algorithm for semi-infinite linear programming

We present a primal method for the solution of the semi-infinite linear programming problem with constraint index setS. We begin with a detailed treatment of the case whenS is a closed line interval in . A characterization of the extreme points of the feasible set is given, together with a purification algorithm which constructs an extreme point from any initial feasible solution. The set of points inS where the constraints are active is crucial to the development we give. In the non-degenerate case, the descent step for the new algorithm takes one of two forms: either an active point is dropped, or an active point is perturbed to the left or right. We also discuss the form of the algorithm when the extreme point solution is degenerate, and in the general case when the constraint index set lies in ^p . The method has associated with it some numerical difficulties which are at present unresolved. Hence it is primarily of interest in the theoretical context of infinite-dimensional extensions of the simplex algorithm.