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

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

全方位搜索的亚基迭代算法

文章改进了单纯形算法中的进基规则和迭代方式,与原始单纯形算法相比,能够有效地减少迭代次数,提高计算速度     

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

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

基于核心矩阵的线性规划块转轴算法研究

本文在线性规划问题核心矩阵概念的基础之上,对单纯形算法的块转轴规则进行了深入的研究.在线性规划的Kuhn-Tucker条件基础之上,证明了单纯性算法块转轴规则的理论可行性,并在文章中给出了块转轴规则的理论算法,为转轴规则的研究提出了一个新的方向.     

线性规划的改进行旋转算法

行旋转算法是求解线性不等式组的一种直接、有效的算法,为大数据时代众多与线性不等式组紧密相关的问题提供了统一、高效的解决思路.求解线性规划问题本质上是求解线性不等式组,因而行旋转算法可以作为基础算法直接应用于求解线性规划.不同于以单纯形法为代表的列旋转算法,线性规划的行旋转算法以行几何(或行向量)为基础,其核心思想是在保证最优性条件始终成立的前提下求解约束条件对应的线性不等式组.改进的行旋转算法保持了原算法的所有特色.该算法的改进之处在于利用约束条件变量的部分系数构成的非奇异矩阵的逆矩阵(称为特征逆矩阵)和原始数据计算出枢轴行和枢轴列,从而完成一次旋转运算.特征逆矩阵的阶数一般要比约束的数目和变量的数目小很多,在每次迭代过程中只需要计算原算法算表中的小部分必要元素,因而能够显著提高计算效率.     

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

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

线性规划中一个避免人工变元的方法的改进

有许多文献讨论了线性规划问题中单纯形方法的改进(如文献[1～5]等)。我们在文献[1]的基础上,突破了传统方法中要求单纯形表中的基变量始终非负的想法,给出了求解线性规划问题中一个新的避免人工变量的方法,使其计算量得到减少。     

单纯形算法的一种新改进

一、改进的要点考虑标准线性规划问题(Ⅰ°)其中这样,(x_1,x_2,…,x_(n m))=(0,0,…,0,b_1,…,b_m)是(Ⅰ°)之基本可行解。对标准单纯形算法改进的基本点如下: 1°由(Ⅰ°)得到初始松弛问题(I~1)(I~1) 通常选取 2°由第(I~t)得到松弛问题(I~(t 1))(I~t) 用单纯形算法求解(I~t),记每步单纯形旋转的基矩阵是B~t;基变量足标集是IB~t;基变量取值;按进基规则选取足标是j_o的非基变量x_(jo)换入基内,并且得到向量     

线性规划的最钝角松弛算法

本文提出一个基于最钝角原理的松弛算法求解线性规划问题。该算法依据最钝角原理略去部分约束得到一个规模较小的子问题,用原始单纯形算法解之;再添加所略去的约束恢复原问题,若此时全部约束条件均满足则已获得一个基本最优解,否则用对偶单纯形算法继续求解。初步的数值试验表明,新算法比传统两阶段单纯形算法快得多。     

避免引入人工变量求线性规划可行基的一个新方法

讨论了线性规划的单纯形解法,给出了不须加人工变量就可得到一个可行基的算法.通过大量的算例表明此法比传统的单纯形方法具有算法结构简单,计算量小的优点.     

对线性规划单纯形法的注记

为了更有效地应用单纯形算法求解线性规划问题,本文提出了以下几点注记。(1)人工变量列不必参与数值计算,也不占存储空间,从而可大量节省计算量和存储量;(2)使用基变量指标集来判断人工变量是否离基,可避免舍人误差的影响;(3)虚设人工变量的最终非零值对于修改存在矛盾的数学模型将起着关键性作用;(4)可将大M法与两阶段法统一处理,且M可不取具体的数值,也不参与数值计算;(5)实际计算中宜将Dantzig算法与Bland算法结合起来使用,既可对一般问题达到快速收敛的目的,又可避免退化问题可能产生的循环现象,而且在软件设计与实现上要比字典序方法等简单容易;(6)对于大型稀疏矩阵的计算机数据录入,建议采用二元数组的数据结构逐行录入,则可节省三分之一的录入工作量。     

线性规划问题的符号计算

应用各种符号计算系统可以很方便地求解各种线性代数问题,利用初等变换即可得到问题的精确解而不必预先编写程序,本文通过例子,根据单纯形算法原理,详细介绍了使用muMATH系统直接求解线性规划问题精确解的运算方法,人工变量所对应的列向量始终不参加运算,从而可大量节省存储量和计算量。     

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

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

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

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

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

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

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

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

互补基解性质的应用研究

对线性规划互补基解性质进行了研究,得到了由线性规划问题最优基对应的单纯形表直接获得对偶线性规划问题最优基对应的单纯形表的一个有效方法,给出了应用实例.     

一类带反凸约束的非线性比式和问题的全局优化算法

本文针对一类带有反凸约束的非线性比式和分式规划问题,提出一种求其全局最优解的单纯形分支和对偶定界算法.该算法利用Lagrange对偶理论将其中关键的定界问题转化为一系列易于求解的线性规划问题.收敛性分析和数值算例均表明提出的算法是可行的.     

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

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

带策略约束的区间数双矩阵博弈的双线性规划求解方法

传统区间数双矩阵博弈理论研究局中人支付值为区间数的策略选择问题,但没有考虑局中人策略选择可能受到各种约束.创建一种求解局中人策略选择受约束且支付值为区间数的双矩阵博弈(简称带策略约束的区间数双矩阵博弈)的简单、有效的双线性规划求解方法.首先,将局中人的博弈支付看作支付值区间中数值的函数.通过证明这种函数具有单调性,据此利用支付值区间的上、下界,构造了一对辅助双线性规划模型,可分别用于显式地计算任意带策略约束的区间数双矩阵博弈中局中人区间数博弈支付的上、下界及其相应的最优策略.最后,利用考虑策略约束条件下企业和政府针对发展低碳经济策略问题的算例,通过比较其与不考虑策略约束情形下的结果,说明了提出的模型和方法的有效性、优越性及可应用性.