共查询到18条相似文献,搜索用时 625 毫秒
1.
陆宗元 《上海师范大学学报(自然科学版)》2002,31(2):39-43
在已经得到的线性规划问题的基本解既不是原始问题的可行解,也不是对偶问题的可行解的情形下,介绍求解线性规划问题的广义对偶单纯形法,它是对偶单纯形法的推广,用此法迭代一次就可得到一个对偶可行解。 相似文献
2.
单纯形法是求解线性规划问题的基本方法,它的基本思想是:先找出一个基本可行解,对它进行检验,看是否是最优解;若不是,则按照一定法则迭代到另一改进的基本可行解,再检验;若仍不是,则再迭代,直到解为最优解。本文首先介绍了线性规划问题中单纯形法的具体算法,并对其算法方法进行了分析和应用。 相似文献
3.
4.
对求极小化线性规划问题max Z=CX,AX=b,x≥O,通过添加人工变量,可直接获得问题的基解,若求得问题的基解不是原问题的可行解,也不是对偶问题的可行解的情况下,本文给出了求解该类规划问题初始可行解的一般方法. 相似文献
5.
本文给出了求解线性规划问题的一种算法,该算法在用初等行变换求约束条件的基本可行解时,通过控制目标函数的检验数使基本可行解靠近最优解,减少了迭代次数,从而减少计算量,并可以在计算机上实现. 相似文献
6.
张卫国 《西安科技大学学报》2002,22(3):321-324
单纯形法是求解线性规划问题的有效方法。本文给出用初等行变换求线性规划问题的初始基本可行解的新方法 ,该方法与传统的方法相比 ,具有计算量小且占用存储空间少的特点 ,算例证明该方法是可行且有效的 相似文献
7.
吉训仁 《中山大学学报(自然科学版)》1997,(1)
对一类线性规划问题提出了一个强多项式算法.此算法可进行双向搜索.可行解集、目标函数的两个目标值以及相应的最优解,全部可行基与最优基可以一步求得,无需迭代.算法的复杂性为O(n3+n2+n),其中n为线性规划问题变量的个数 相似文献
8.
张卫国 《西安科技学院学报》2002,22(3):321-324
单纯形法是求解线性规划问题的有效方法。本文给出用初等行变换求线性规划问题的初始基本可行解的新方法,该方法与传统的方法相比,具有计算量小且占用存储空间少的特点,算例证明该方法是可行且有效的。 相似文献
9.
吉训仁 《中山大学学报(自然科学版)》1997,36(1):6-10
对一类线性规划问题提出了一个强多项算法,此算法可进行双向搜索,可行解集,目标函数的两个目标值以有相就的最优解,全部可行基与最优基可以一步求得,无需迭代,算法的复杂性为O(n^2+n^2+n),其中n为线性规划问题变量的个数。 相似文献
10.
单纯形方法是解线性规划问题的一种有效方法,用这种方法解线性规划问题首先要找出初始可行解,然后通过迭化得出最优解。由于退化,迭代时往往会出现循环,为了避免循环的发生,A. Charnes在1952年提出了摄动法, G. B. Dantring等人在1954年提出了字典序方法,1977年R. G. Bland给出了用组合方法解决退化的索性规划问题的迭代方法。这些方法在解退化的线性规划问题时都是通过迭代代得出最优解。我们将用对偶模型给出线性规划问题的又一解法及其最优判别准则。这种解法其实是一次性择优而不需迭代,在某种意义下,可使线性规划问题的解决变得简洁明了,显示出此方法较其它解线性规划的方法优越。 相似文献
11.
贺明峰 《大连理工大学学报》1986,(Z1)
本文对含有自由变量(无非负性要求的变量)的LP问题进行了讨论,在自由变量不 做差的条件下,给出了基可行解的定义,并得到基可行解的存在定理及为最优解的条件。 最后给出直接求解相应LP问题的早纯形法。该法在求解过程中让自由变量首先进基,以 减少迭代步数。 相似文献
12.
最优解唯一的线性规划问题 总被引:1,自引:0,他引:1
闻振卫 《苏州大学学报(医学版)》2004,20(2):12-16
给出了线性规划问题最优解何时唯一存在的充分必要条件,从而一方面彻底解决了线性规划何时最优解唯一存在的问题,另一方面也纠正和弥补了一些教材或专在此问题上的错误和不足. 相似文献
13.
解线性规划问题的一种半单纯形法 总被引:3,自引:0,他引:3
本文提出解线性规划问题的一种方法,主要是对约束Ax=b求初始基可行解时,不必引入人工变量而可直接用旋转运算获得,之后就完全和单纯形法一样求最优解,并提出了判定无可行解的方法和准则,对算法的理论问题也作了证明和解释。 相似文献
14.
线性规划问题的一种改进的单纯形法 总被引:1,自引:0,他引:1
范国兵 《海南大学学报(自然科学版)》2007,25(3):243-247
提出了一种求解线性规划问题的方法,即对约束Ax=b求初始基可行解时,不必引入人工变量而直接用旋转运算获得,之后利用传统单纯形法求最优解,并给出了该方法的实算例子. 相似文献
15.
考虑带有二次约束的一般二次规划问题的求解,当约束条件为非凸二次函数时,对原问题中的某个二次约束进行凸二次松驰,或在原问题的约束条件中增加一个球约束,使得原问题的可行域包含在松驰二次规划问题的可行域内。采用椭球剖分策略剖分可行域为小 椭球,用投影次梯度算法解松驰二次规划问题的拉格朗日对偶问题,从而获得原问题的一个下界。原问题最优值的一个上界可从迭代过程中的可行点得到,并在迭代过程中得到调整。该算法或在原问题最优值的一个上下界相同时终止,得到原问题的整体最优解;或产生一无限序列,其任一聚点都是原问题的整体最优解。 相似文献
16.
解一般形式线性规划的一个直接方法 总被引:3,自引:0,他引:3
薛声家 《广西大学学报(自然科学版)》1989,(3)
本文提出了一个直接处理一般形式线性规划的算法而不需要把问题转化为标准形(即所有约束都是等式约束,所有变量都是非负的)。由于算法的基本思想与单纯形法相同,所以当应用子标准形式的线性规划问题时此算法化为单纯形法。文中证明了算法的有限步终止性,最后还讨论了可行域不存在极点的情形。 相似文献
17.
18.
求第一个可行基的一种不同的方法 总被引:1,自引:0,他引:1
肖蓬 《福建师范大学学报(自然科学版)》2002,18(2):20-23
给出求第一个可行基的一种新方法,这种方法不要引进辅助线性规划问题,不要添加松驰变量,计算比较简便。 相似文献