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

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

线性规划单纯形法的三种实现形式探析

按照一般寻优算法原则,在定义可行方向和步长的基础上,从线性规划问题系数矩阵的列向量子空间出发,说明了单纯形法的顶点寻优过程是一个在约束条件的仿射空间和系数矩阵的零子空间交错前进的过程,并在此基础上归纳和总结了数据字典式单纯形表、经典单纯形表和简化单纯形表的实现形式及其迭代计算的特点和优势,并建议未来在《运筹学》教学中广泛推广这三种类型的单纯形表.     

模糊线性规划问题的一种新的单纯形算法

提出求解模糊线性规划问题的一种新的思路 ,就是应用单纯形法先求解与 (FLP)相应的普通线性规划问题 ,通过模糊约束集与模糊目标集的隶属度的比较 ,获得两个集合交集的最优隶属度 ,将此最优隶属度代入最优单纯形表中 ,即可求得 (FLP)的解。本算法只需在一张适当的迭代表台上执行单纯形迭代过程 ,简捷方便适用     

一种简易的单纯形表

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

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

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

关于线性规划单纯形法的注记

本文讨论了单纯形法中最优解和检验数之间的关系,以及确定主元列标号的不同原则。     

綫性規划的一个新方法——直除法

§1.前言自1958年大跃进以来,运筹学綫性規划在我国得到了巨大的发展,广泛地应用在我国社会主义建設事业中并取得了比較显著的效果,从而又促进了对运筹学綫性規划的深入研究,无論是线性規划的理論和方法都获得了很多結果,大大丰富了这門新兴学科的內容。所謂綫性規划,就是在一組綫性等式及不等式的約束条件下,求綫性目标函数的极大值或极小值(最优值)的问題。它可以归結为在約束条件的約束下,来极优化目标函数的数学問題。使目标函数达最优值的点叫做規划的最优解或規划的解。滿足約束条件(1)的非負解叫做預备解。解綫性規划的方法一般是用“单純形”法,它是按下述三个步驟来进行的: 1) 用某种方法給出一个預备解;     

解线性规划的单纯形算法中避免循环的几种方法

在线性不等式或等式组的约束下,求线性目标函数的极值问题,通常称为线性规划.线性规划是运筹学中最基本的数学模型之一.五十年代初,[1]首先提出了解线性规划的单纯形算法,20多年来的计算实践已证明,这一算法是有效的,而且这一算法已成为整数规划和非线性规划某些算法的基础.为了保证单纯形算法是有限步迭代的,必须避免迭     

对于单纯形法矩阵描述的认识

从修正单纯形法的提出、对偶单纯形法的出现、对偶问题最优解的确定以及灵敏度分析的基本依据等四个方面阐述了对单纯形法矩阵描述的认识,充分显示出单纯形法矩阵描述在线性规划发展中的重要性.     

线性规划基线算法的基本概念

１．运算表格线性规划的基线算法是单纯形法（基点算法）的发展,因为每张运算表格对应着一条基线而得名．它象单纯形法一样好学易用,操作简便,而解题速度比单纯形法快．考虑标准型线性规划问题（ＬＰ）：：其中ｃ,ｘｅＲ"＋",Ａ是。ｘ（佩十。）矩阵,ｂｅＲ"。是（ＬＰ）的维数,。是约束个数．Ｘ＝｛ＸＥＲ""叫ＡＸ＝ｂ,Ｘ三０｝是（＊利的可行集．Ｘ是一个多面凸集．本文假定Ｃ４０．并且原点不是最优解．把Ｘ看作参数．方程组０．】Ｘ＝０,】的系数表称为母表（表１）．恒假设矩阵０－１－＼Ａｊ＼ｈｉ一"-一'-－"－"'一'-"-一"…     

基于线性规划核心矩阵的单纯形算法

本文讨论了线性规划中的核心矩阵及其特性,探讨了利用核心矩阵实现单纯形算法的可能性,并进一步提出了一个基于核心矩阵的两阶段原始一对偶单纯形方法,该方法通过原始和对偶两个阶段的迭代,可以在有限次迭代中收敛到原问题的最优解或证明问题无解或无界．在试验的22个问题中,该算法的计算效率总体优于基于传统单纯形方法的MINOS软件．     

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.     

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

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

确定递阶层次结构的简便方法

运用层次分析法(AHP)解决决策问题时,第一步就是要确定问题的递阶层次结构.对此,现有文献中给出的数学方法都是基于可达矩阵的,它通常需要借助计算机来完成.在文中充分考虑到AHP递阶层次结构的特点严格的逐层相关性及元素间无互相关性,给出一种非常简单的方法—划列法(DRM),并严格证明了其正确性,然后通过举例给予说明.该方法使递阶层次结构的确定不必再进行可达矩阵等计算,只依靠手工即可完成.     

线形分式规划消耗系数矩阵灵敏度分析及应用

基于解非线形规划的凸单纯形法,对一类线形分式规划的消耗系数矩阵进行灵敏度分析.求出使最优解或最优基保持最优的消耗系数矩阵中列向量和行向量的可变范围.并进行了应用计算.     

微分变换法求解二维非线性Volterra积分微分方程

为了解决二维非线性Volterra积分微分方程的求解问题,本文给出微分变换法.利用该方法将方程中的微分部分和积分部分进行变换,这样简化了原方程,进而得到非线性代数方程组,从而将原问题转换为求解非线性代数方程组的解,使得计算更简便.文中最后数值算例说明了该方法的可行性和有效性.     

n(2≤n≤4)次方程的一种统一解法

研究普通代数方程的解法,借助矩阵理论,给出了三次代数方程的解法,把n次(2≤n≤4)方程的解的形式统一到了一起,解法思路简单,解的形式简洁.     

Complexity of the Gravitational Method for Linear Programming

In the gravitational method for linear programming, a particle is dropped from an interior point of the polyhedron and is allowed to move under the influence of a gravitational field parallel to the objective function direction. Once the particle falls onto the boundary of the polyhedron, its subsequent motion is constrained to be on the surface of the polyhedron with the particle moving along the steepest-descent feasible direction at any instant. Since an optimal vertex minimizes the gravitational potential, computing the trajectory of the particle yields an optimal solution to the linear program.Since the particle is not constrained to move along the edges of the polyhedron, as the simplex method does, the gravitational method seemed to have the promise of being theoretically more efficient than the simplex method. In this paper, we first show that, if the particle has zero diameter, then the worst-case time complexity of the gravitational method is exponential in the size of the input linear program. As a simple corollary of the preceding result, it follows that, even when the particle has a fixed nonzero diameter, the gravitational method has exponential time complexity. The complexity of the version of the gravitational method in which the particle diameter decreases as the algorithm progresses remains an open question.     

A Linearized Spectral-Galerkin Method for Three-Dimensional Riesz-Like Space Fractional Nonlinear Coupled Reaction-Diffusion Equations

In this paper, we establish a novel fractional model arising in the chemical reaction and develop an efficient spectral method for the three-dimensional Riesz-like space fractional nonlinear coupled reaction-diffusion equations. Based on the backward difference method for time stepping and the Legendre-Galerkin spectral method for space discretization, we construct a fully discrete numerical scheme which leads to a linear algebraic system. Then a direct method based on the matrix diagonalization approach is proposed to solve the linear algebraic system, where the cost of the algorithm is of a small multiple of $N^4$ ($N$ is the polynomial degree in each spatial coordinate) flops for each time level. In addition, the stability and convergence analysis are rigorously established. We obtain the optimal error estimate in space, and the results also show that the fully discrete scheme is unconditionally stable and convergent of order one in time. Furthermore, numerical experiments are presented to confirm the theoretical claims. As the applications of the proposed method, the fractional Gray-Scott model is solved to capture the pattern formation with an analysis of the properties of the fractional powers.     

PSD方法的最优因子及效率分析

在系数矩阵是相容序2循环阵的情况下，本文给出了PSD方法的最优松弛参数和最优收敛因子，分析和讨论了它的实用性，并进而得到了一个新的迭代法，它的最优收敛因子与PSD方法一样，而迭代参数却只有一个．