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

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

求解线性规划的一种单纯形矩阵法

线性规划的单纯形法一直是运筹学教学中的难点,是求解线性规划的一种重要方法.通过实例从代数角度探讨了单纯形法的迭代思想,提出了用单纯形矩阵求解线性规划的方法.同传统的单纯形表计算比较而言,此方法操作简单,不易出错,为线性规划的求解提供了一种行之有效的方法。     

单纯形法检验数的新计算方法

单纯形法仍然是求解线性规划最具竞争力的算法之一,改进它的计算效率仍具有理论和现实意义.本文通过改进检验数的计算方式,提出了一种实施单纯形法新的计算方式.这种计算方式方便简单,无论采用单纯形表还是采用数值迭代计算都可以提高计算效率.     

基于半单纯形法的模板优选研究

利用半单纯形法研究了建筑结构施工中各类模板的最优选取问题 ,建立了各类模板最优组合的数学模型及求解算法。对实际问题的算例表明该方法非常有效。     

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

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

基于单单纯形法的模板优选研究

利用半单纯形法研究了建筑结构施工中各类模板的最优选取问题，建立了各类模板最优组合的数学模型及求解算法。对实际问题的算例表明该方法非常有效。     

线性规划单纯形法的动态灵敏度分析及其应用

本文研究了线性规划的灵敏度分析方法.运用灵敏度分析的方法,分析了单纯形法求解过程中新增变量的动态变化所需的条件,并从具体的二维和三维例子出发,构造出一系列的高维线性规划问题.用单纯形法求解这些问题时,使用某种主元规则(如最大改进规则)的迭代次数可以比约束数目多一至三次.     

一种简易的单纯形表

通过对单纯形法的分析和研究,提出了一种简易的单纯形表,并利用矩形法则进行计算而得到一种改进的单纯形法.结果表明该法简单易行,并减少了计算量和存储量.     

线性规划对偶单纯形法的常识性经济解释

线性规划对偶单纯形法的数学描述是抽象且不易理解的 ,本文找到了一种常识性经济解释的描述 .既通俗易懂、又能抓住方法的实质 .这将从通俗易懂的思想方法上促进线性规划问题解法的普及推广应用     

可行下降视角下退化运输问题的最优性条件

运输问题是一类特殊的线性规划问题,通常用特殊的单纯形法—运输单纯形法(也叫表上作业法)进行求解,其最优性条件为所有非基变量的检验数大于等于零.针对实际算例中出现的某个非基变量的检验数小于零,却已经达到最优的情况,从可行下降方向的角度进行了探讨.结论表明:一般情况下非基变量的检验数大于等于零仅是运输问题最优解的充分条件;而问题非退化时,该判别条件成为充要条件.     

如何利用单纯形表上的信息

本文分析了求解线性规划的基本方法－－单纯形法所使用的单纯形表，将表中所提供的信息分为直接信息和间接信息两类，论述了如何充分利用这些信息的方法。例如如何由最终表求原问题、如何利用表中的数据互相推演和校正等。这是一篇教学经验的总结，对初学者可能有一定的帮助。     

A Simplex Approach for Finding Local Solutions of a Linear Bilevel Program by Equilibrium Points

In this paper, a linear bilevel programming problem (LBP) is considered. Local optimality conditions are derived. They are based on the notion of equilibrium point of an exact penalization for LBP. It is described how an equilibrium point can be obtained with the simplex method. It is shown that the information in the simplex tableaux can be used to get necessary and sufficient local optimality conditions for LBP. Based on these conditions, a simplex type algorithm is proposed, which attains a local solution of LBP by moving in equilibrium points. A numerical example illustrates how the algorithm works. Some computational results are reported.     

Some fundamental issues of basic line search algorithm for linear programming problems

In this article we present the fundamental idea, concepts and theorems of a basic line search algorithm for solving linear programming problems which can be regarded as an extension of the simplex method. However, unlike the iteration of the simplex method from a basic point to an improved adjacent basic point via pivot operation, the basic line search algorithm, also by pivot operation, moves from a basic line which contains two basic feasible points to an improved basic line which also contains two basic feasible points whose objective values are no worse than that of the two basic feasible points on the previous basic line. The basic line search algorithm may skip some adjacent vertices so that it converges to an optimal solution faster than the simplex method. For example, for a 2-dimensional problem, the basic line search algorithm can find an optimal solution with only one iteration.     

Application of Nelder-Mead simplex method for unconfined seepage problems

In unconfined seepage problems, the phreatic line resulted from mesh deforming methods is rarely a smooth and continuous curve. The main problem is at the meeting point of the phreatic line with the down stream face of the dam where the phreatic line must be tangent to the seepage face according to the fluid continuity principle. In this paper a mesh deforming finite element method based on Nelder-Mead simplex optimization is presented to solve this problem. The phreatic line is approximated by a 4th degree polynomial and Nelder-Mead simplex method is used to calculate the polynomial’s coefficients minimizing an error function which is introduced based on the conditions on the phreatic line. Tangentiality of the phreatic line to the seepage face is introduced in the solution by a constraint in optimization procedure. The results of the presented method are verified by the results of the nonlinear finite element and other mesh deforming methods.     

线性规划单纯形代数7小步法与简易矩阵表格法

在《运筹学》这门课的教学过程中,单纯形法一直是教学的一个难点,学生也比较难理解、不容易学明白.通过多年的运筹学教学经验,针对目标为max的线性规划问题,提出"单纯形代数7小步法"和"简易矩阵表格法".对于"单纯形代数7小步法",只需要按照这7个步骤一步一步操作就能得到最优解和目标函数最优值;对于"简易矩阵表格法",根据题目的模型得到初始矩阵表格后,就是不断地在矩阵表格中寻找主元,然后将主元变成1,并将主元所在列的其他元素变成0,再根据矩阵的最后一行元素的正负进行最优性检验;最后得到最优矩阵表格,从最优矩阵表格里就能直接读出最优解和目标函数的最优值.将单纯形法提炼成比较容易理解和接受的这两种形式,为学生学习单纯形法提供重要的参考,同时也为运筹学老师的对这一部分内容的教学提供借鉴.     

A polynomial-time simplex method for the maximumk-flow problem

A generalization of the maximum-flow problem is considered in which every unit of flow sent from the source to the sink yields a payoff of $k. In addition, the capacity of any arce can be increased at a per-unit cost of $c _e . The problem is to determine how much arc capacity to purchase for each arc and how much flow to send so as to maximize the net profit. This problem can be modeled as a circulation problem. The main result of this paper is that this circulation problem can be solved by the network simplex method in at mostkmn pivots. Whenc _e = 1 for each arce, this yields a strongly polynomial-time simplex method. This result uses and extends a result of Goldfarb and Hao which states that the standard maximum-flow problem can be solved by the network simplex method in at mostmn pivots.Research partially supported by Office of Naval Research Grant N00014-86-K-0689 at Purdue University.     

Hyper-Sparsity in the Revised Simplex Method and How to Exploit it

The revised simplex method is often the method of choice when solving large scale sparse linear programming problems, particularly when a family of closely-related problems is to be solved. Each iteration of the revised simplex method requires the solution of two linear systems and a matrix vector product. For a significant number of practical problems the result of one or more of these operations is usually sparse, a property we call hyper-sparsity. Analysis of the commonly-used techniques for implementing each step of the revised simplex method shows them to be inefficient when hyper-sparsity is present. Techniques to exploit hyper-sparsity are developed and their performance is compared with the standard techniques. For the subset of our test problems that exhibits hyper-sparsity, the average speedup in solution time is 5.2 when these techniques are used. For this problem set our implementation of the revised simplex method which exploits hyper-sparsity is shown to be competitive with the leading commercial solver and significantly faster than the leading public-domain solver.     

Dual simplex method for GUB problems

The dual simplex method for generalized upper bound (GUB) problems is presented. One of the major operations in the dual simplex method is to update the elements of therth row, wherer is the index for the leaving basic variable. Those updated elements are used for the ratio test to determine the entering basic variabble. A very simple formula for therth row update for the dual simplex method for a GUB problem is derived, which is similar to the formula for the standard linear program. This derivation is based on the change key operation, which is to exchange the key column and its counterpart in the nonkey section. The change key operation is possible because of a theorem that guarantees the existence of such a counterpart.     

n维欧氏空间En中Child不等式的推广

利用几何不等式理论与解析方法,研究了n维欧氏空间En中n维单形的内点到各顶点的距离与到各侧面距离之间的关系,获得相关的几个几何不等式,推广了Child不等式．