求解二层线性规划问题的一种算法

对下层含有约束的二层线性规划问题,提出了求全局最优解的一种算法.首先由该算法求出约束凸集的全部极点,再对极点进行可行性检验,从而得到了二层线性规划问题的全局最优解,最后以实例验证了算法的有效性.     

Comments on “An Algorithm for Solving the Linear Goal-Programming Problem by Solving Its Dual”

Goal Programming within a pre-emptive priority structure has been one of the most widely used multi-objective mathematical model formulations. By considering its dual problem, Ignizio has shown that a very efficient computational procedure for solving linear goal-programming problems can be problems can be implemented with any conventional large-scale simplex system. This note gives an overview of Ignizio's dual formulation, and identifies when a certain dual variable must be incorporated in the model to preserve the pre-emptive priority structure.     

二层线性规划的自适应遗传算法

提出了一种自适应遗传算法来求解二层线性规划问题.该方法克服了难以确定合适的交叉概率和变异概率的困难.另外,在该方法中还采用了其它一些技巧不仅解决了在采用遗传算法经常出现的有些个体不可行的问题,而且还改进了算法的效率.     

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

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

A Reply to “Comments on an Algorithm for Solving the Linear Goal-Programming Problem by Solving its Dual”

In a recent paper, it was claimed that an algorithm published earlier by Ignizio (for the solution to the lexicographic linear goal-programming model) is in error. In this reply, it is noted that the alleged error simply does not exist but is due solely to the misapplication of the algorithm.     

线性分式运输问题的一个解法

线性分式运输问题是线性分式规划问题的一种特殊情况，通常可以用线性分式规划问题的一般解法来解这类问题，本文针对分式运输问题的特点给出了一种简便的解法．     

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

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

An Algorithm for Solving Multicriterion Linear Programming Problems with Examples

The purpose of this paper is to develop a useful technique for solving linear programmes involving more than one objective function. Motivation for solving multicriterion linear programmes is given along with the inherent difficulty associated with obtaining a satisfactory solution set. By applying a linear programming approach for the solution of two person–zero sum games with mixed strategies, it is shown that a linear optimization problem with multiple objective functions can be formulated in this fashion in order to obtain a solution set satisfying all the requirements for an efficient solution of the problem. The solution method is then refined to take into account disparities between the magnitude of the values generated by each of the objective functions and solution preferences as determined by a decision-maker. A summary of the technique is then given along with several examples in order to demonstrate its applicability.     

运筹学中若干线性目标规划和线性规划的人工智能-代数解法

运筹学中的线性目标规划和线性规划问题一直分别采用修正单纯形法和单纯形法求解.当变量稍多时计算还是有些繁琐、费时,最近作者通过研究发现,可应用人工智能-代数方法求得这两类问题的解,而且具有相当广泛的适用性.若干例题说明,本法的结果和传统方法的结果由于传统算法在计算中发生的错误,除少数例外大都是一致的.本文的一个 重要目的是希望和广大读者一起研究该方法是否具有通用性.     

应用模糊目标规划方法求解多目标线性分式规划问题

针对多目标分式线性规划问题,提出利用上(下)界表示目标期望水平及允许上(下)限,且利用一阶泰勒公式逼近隶属函数,将多目标分式规划转化为线性规划问题,并用单纯形法求解,通过实验算例说明了所提出的方法的有效性.     

解线性目标规划的《量化优先因子法》—基于LP过程的算法

本文提出一种解线性目标规划及整数线性目标规划的《量化优先因子法》,即把目标规划中表示优先等级的优先因子 pl( l=1 ,2 ,… ,L)用能从数量级上刻划优先因子 Pl Pl+ 1的本质特征的数来表示 ,进而用 SAS/OR软件包中解线性规划的 LP过程即可求解此线性目标规划 .通过实例给出算法与用 LP过程求解的程序 .     

LP问题的K算法

本文给出了求 LP问题最优解的λ算法 ,并指出了此法旋转运算的次数 .此算法不需要基本可行解或对偶基本可行解 .     

优化方法解决无上层约束的线性双层规划问题

In this paper we propose an optimal method for solving the linear bilevel programming problem with no upper-level constraint. The main idea of this method is that the initial point which is in the feasible region goes forward along the optimal direction firstly. When the iterative point reaches the boundary of the feasible region, it can continue to go forward along the suboptimal direction. The iteration is terminated until the iterative point cannot go forward along the suboptimal direction and effective direction, and the new iterative point is the solution of the lower-level programming. An algorithm which bases on the main idea above is presented and the solution obtained via this algorithm is proved to be optimal solution to the bilevel programming problem. This optimal method is effective for solving the linear bilevel programming problem.     

A Dual Projective Pivot Algorithm for Linear Programming

Recently, a linear programming problem solver, called dual projective simplex method, was proposed (Pan, Computers and Mathematics with Applications, vol. 35, no. 6, pp. 119–135, 1998). This algorithm requires a crash procedure to provide an initial (normal or deficient) basis. In this paper, it is recast in a more compact form so that it can get itself started from scratch with any dual (basic or nonbasic) feasible solution. A new dual Phase-1 approach for producing such a solution is proposed. Reported are also computational results obtained with a set of standard NETLIB problems.     

Pattern Classification by Linear Goal Programming and its Extensions

Pattern classification is one of the main themes in pattern recognition, and has been tackled by several methods such as the statistic one, artificial neural networks, mathematical programming and so on. Among them, the multi-surface method proposed by Mangasarian is very attractive, because it can provide an exact discrimination function even for highly nonlinear problems without any assumption on the data distribution. However, the method often causes many slits on the discrimination curve. In other words, the piecewise linear discrimination curve is sometimes too complex resulting in a poor generalization ability. In this paper, several trials in order to overcome the difficulties of the multi-surface method are suggested. One of them is the utilization of goal programming in which the auxiliary linear programming problem is formulated as a goal programming in order to get as simple discrimination curves as possible. Another one is to apply fuzzy programming by which we can get fuzzy discrimination curves with gray zones. In addition, it will be shown that using the suggested methods, the additional learning can be easily made. These features of the methods make the discrimination more realistic. The effectiveness of the methods is shown on the basis of some applications.     

An Integer Linear Programming Formulation and Branch-and-Cut Algorithm for the Capacitated m-Ring-Star Problem

We study the capacitated m-ring-star problem (CmRSP) that faces the design of minimum cost network structure that connects customers with m rings using a set of ring connections that share a distinguished node (depot), and optionally star connections that connect customers to ring nodes. Ring and star connections have some associated costs. Also, rings can include transit nodes, named Steiner nodes, to reduce the total network cost if possible. The number of customers in each ring-star (ringʼs customers and customer connected to it through star connections) have an upper bound (capacity).These kind of networks are appropriate in optical fiber urban environments. CmRSP is know to be NP-Hard. In this paper we propose an integer linear programming formulation and a branch-and-cut algorithm.     

线性规划对偶问题的一个注记

指出了线性规划对偶问题定义中的一个小漏洞,并作了改正     

求解运输问题的一个算法

给出一个求解问题的数值算法，证明了算法的理论依据，并举例说明算法的应用。     

求解指派问题的一个算法

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