变量有上界的线性规划的对偶算法

线性规划中对偶理论的一系列定理是针对变量无上界的线性规划的。本文将有上界的线性规划及对偶规划化为无上界的线性规划及对偶规划,从而得到几个相应的定理。根据这些定理推出变量有上界的线性规划对偶单纯形算法,并证明了它的收敛性。本文还给出了第一个正则解的一个求法,并讨论了退化情况。     

广义的变量有上界的对偶单纯形法

本文研究了广义的变量有上界的线性规划问题的对偶单纯形法,给出了比较简单的计算公式。     

对偶单纯形法的一个注记

针对运筹学教学难点--对偶单纯形法,通过讨论证明了单纯形表中的列可以视为对偶问题的非基变量的检验数,并讨论了在对偶单纯形法迭代过程中的进基变量与出基变量的确定原则亦如同在单纯形法迭代过程中进基变量与出基变量的确定原则,得出结论是对偶单纯形法本质上就是单纯形法,只是在运用对偶单纯形法解线性规划时需要将单纯形表旋转90°.     

递增斜率分段线性规划的对偶算法

针对目标函数具有递增斜率的分段线性规划问题,提出了一种快速的对偶算法。算法基于单纯形的思想,引入指针的概念来建立问题最优性和可行性判据,不需设置分段变量,不会扩大问题的规模,从而减少了内存和计算量。     

线性规划若干问题的实例说明

用实例对线性规划中诸如退化和循环问题、单纯形算法中的问题和对偶问题最优解在原问题最优单纯形表中的位置问题等若干问题进行了说明     

时间最优控制的一种算法

本文提出了对于控制作用和状态均受约束的多入多出线性系统的求解时间最优控制问题的算法。在离散数学模型的基础上,首先应用求解线性规划问题的有界变量单纯形方法求出满足控制约束的控制序列,然后再利用割平面方法处理状态约束,以求得满足约束条件的最优控制。除时间最优外,本算法还允许提出线性形式的附加目标函数。在具有附加目标函数时为能有效地处理状态约束,推导出了有界变量对偶单纯形方法。本算法通过扩展状态或部分扩展状态,可应用于一类有状态滞后的系统。为提高计算效率和减少存储容量,采取改进了的跳步算法和压缩存储技术等措施。     

求解线性规划问题最优解时常遇到的几种特殊情况

重点介绍了单纯形法在求解过程中常遇到的几种特殊情况.首先,在一个线性规划问题的最优解对应的单纯形表中,如果至少有一个非基变量的检验数为零,那么该线性规划问题的最优解可能不只一个,当求到另一个最优解时,则原问题必有多重最优解;其次,在单纯形表中,如果某一负检验数所对应的列向量的分量全部非正,则原问题无最优解;再次,在求解过程中,若原问题不可行,而对偶问题可行时,我们可以应用对偶单纯形法进行求解.     

单纯形方法和对偶单纯形方法的一个注记

对于每一个线性规划问题,证明了仅在一张单纯形表中采用单纯形法或对偶单纯形法就可以把该线性规划问题和它的对偶问题求解出来,同时用Lingo加以了验证。     

二阶锥规划的Lagrange对偶及2维原始对偶单纯形法

目前对二阶锥规划算法的研究是数学规划领域的研究热点之一,在这方面的研究成果初具规模.文中着重研究两方面问题:一是详细推导二阶锥规划的Lagrange对偶问题;二是将2维二阶锥规划(即二阶锥约束都是2维的,但自变量的总维数是2r维的,r表示二阶锥约束的个数)转化成相应的标准形线性规划,给出其原始对偶单纯形法,并举例说明算法的应用,最后进行部分灵敏度分析.这一工作基本完善了2维二阶锥规划的单纯形类方法,即至此,2维二阶锥规划的原始单纯形法、对偶单纯形法和原始对偶单纯形法的理论已较完善.其他拓广的单纯形类方法可在将2维二阶锥规划转化成相应的标准形线性规划之后对应线性规划的拓广单纯形类方法直接得到.     

求解LP问题的部分基变量算法

一般形式的线性规划问题在找不到基本可行解或对偶问题的基本可行解时,无法用传统的单纯形法或对偶单纯形法求解,即"两看一算"算法.为了解决这个问题,结合两种"两看一算"算法,提出了一种新的算法--部分基变量算法.该算法首先从部分基变量出发,由初等行变换将LP问题转化为准典式,然后由初等行变换找到全部可行基变量,最后用对偶单纯形法得到最优解.对算法的正确性和可行性进行了严格证明,提出算法的实现方式并举例进行了说明,对算法的特点进行了讨论.分析表明所提出的算法是实现线性规划问题求解的较为理想的算法.     

关于单纯形方法的一点注记

通过高斯－约当消元法,对极小化的标准形式的线性规划问题,求得某个单位矩阵的基B对应的基本解,但此基本解既不是原始问题的可行解,也不是对偶问题的可行解,在此情形下作者给出了直接求解某一类线性规划问题的扩充的单纯形法。     

关于人工约束法寻找对偶初始可行解的一个注记

用对偶单纯形法求解线性规划问题,在无法直接求得对偶问题的可行解时,引入人工约束法寻找对偶问题初始可行解．讨论了原问题（LP）与新规划（LPM）解之间的关系,并给出了证明．     

寻找第一个对偶可行基的一般方法

文章给出了线性规划问题标准形式的一种较弱形式——准标准形并给出了相应的单纯形方法,然后以此为工具给出了寻找第一个对偶可行基的一般方法,从而为求解常量含参数的线性规划问题提供了一般解法.这一方法使对偶单纯性方法这一理论体系得以完善.     

一类绝对值规划的算法

针对一类绝对值规划问题,提出对偶规划,给出其弱对偶性及对偶问题的最优性充分条件,并证明对偶间隙也是该类绝对值规划问题的解。同时,引入变量代换,基于线性规划的单纯形法,提出该类绝对值规划问题的全局优化求解算法。算例表明该算法是有效的。     

线性规划问题解法比较

给出单纯形法、大M法、对偶单纯形法适应的线性规划问题的特征,并给出相应解法的一般规律.     

广义对偶单纯形方法

在已经得到的线性规划问题的基本解既不是原始问题的可行解，也不是对偶问题的可行解的情形下，介绍求解线性规划问题的广义对偶单纯形法，它是对偶单纯形法的推广，用此法迭代一次就可得到一个对偶可行解。     

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

根据双层线性规划全局最优解可在约束域极点上达到的性质和线性规划对偶理念,引进上层目标函数对应的一种割平面约束,对双层线性规划的约束域不断进行切割,求得问题更好的可行解,提出了一种利用单纯形法寻找双层线性规划全局最优解的方法。算例说明了算法的求解过程,并验证了算法的有效性。     

电网规划中最小模糊缺负荷量计算方法

为在计及不确定性的电网规划中进行可靠性和经济性分析比较,提出了一种电网最小模糊缺负荷量计算方法．首先应用模糊集合论里的梯形模糊数描述电网规划中预测负荷及发电机可用率的不确定性,由此建立求解最小模糊缺负荷量的模糊线性规划模型,然后将其转化为参数线性规划模型,进而用推广的Ｂｌａｎｄ反转对偶单纯形算法进行求解．最后,给出了一个２４节点、３０条支路的算例．