利用对偶理论求解线性规划问题的策略探讨 被引量：2

1

作者 赵芹 章舜哲 +1 位作者 刘慧清 雷琪 《湖北大学学报（自然科学版）》 CAS 2021年第5期551-554,共4页

利用对偶理论求解线性规划问题是教学中的重点及难点之一.本研究将从例子出发,分析互补松弛条件的使用方法,探讨求解线性规划问题的多种解题思路.

关键词 线性规划问题 对偶理论 互补松弛 最优解

下载PDF 职称材料

有向最短路的“原始-对偶”算法

2

作者 沙元霞 《齐齐哈尔大学学报（自然科学版）》 2008年第2期85-87,共3页

给出了利用"互补松弛原理"以及"原始-对偶原理",在一个有向图D=(V,A,ω)中寻找顶点s到顶点t最短路的算法和过程。

关键词 原始-对偶 有向图 互补松弛 修正 路

下载PDF 职称材料

最大权完美匹配的“原始—对偶”算法

3

作者 沙元霞 任静 《佳木斯大学学报（自然科学版）》 CAS 2008年第1期100-101,105,共3页

给出了利用"互补松弛原理"以及"原始—对偶原理"在一个完全赋权二部图G=(X,Y,E,ω),ω≥0,|X|=|Y|=n中寻找最大权完美匹配的算法和过程.

关键词 原始-对偶 完美匹配 互补松弛 修正 完全赋权二部图

下载PDF 职称材料

二层规划扰动的收敛性

4

作者 彭爱民 《湖北第二师范学院学报》 2010年第2期5-6,共2页

通过探讨二层规划在化为普通约束规划后的约束规格问题,在一般利用KKT条件所必须的约束规格不能满足的情况下,给予互补松弛条件一个较小的扰动后,利用MPEC-LICQ约束规格,可以求解二层规划的一种途径。

关键词 约束规格 互补松弛 扰动

下载PDF 职称材料

配电网故障区段定位的互补松弛约束新模型与算法 被引量：17

5

作者 郭壮志 陈涛 +1 位作者 徐其兴 陈璟华 《电力自动化设备》 EI CSCD 北大核心 2020年第5期129-136,共8页

研究快速高容错性馈线故障区段辨识技术对于提升配电网运行安全可靠性具有重要作用。基于故障电流信号并联叠加特性和逼近关系理论,首次提出代数建模机制下馈线故障区段定位的互补松弛约束模型,其优势为:克服了逻辑模型对群体智能算法... 研究快速高容错性馈线故障区段辨识技术对于提升配电网运行安全可靠性具有重要作用。基于故障电流信号并联叠加特性和逼近关系理论,首次提出代数建模机制下馈线故障区段定位的互补松弛约束模型,其优势为:克服了逻辑模型对群体智能算法的依赖,可采用数值稳定性好的梯度算法求解;利用互补松弛约束条件将非线性整数规划模型转化为具有光滑特性的非线性规划模型,降低了决策求解复杂性;无需对配电网进行分层解耦,即可实现单一和多重故障区段的有效辨识。为有效求解互补松弛故障定位模型,基于模型等价转换思想和松弛因子压缩策略,提出具有全局收敛特性的交互式优化决策算法。仿真算例验证新方法可实现配电网馈线单一或多重故障区段的准确高容错性辨识,且数值稳定性好、故障定位效率高。 展开更多

关键词 配电网 故障区段定位 高容错性 互补松弛约束模型 交互式优化算法

下载PDF 职称材料

求解计及输电约束的线性供给函数均衡模型的分支定界方法 被引量：6

6

作者 杨建林 严正 《中国电机工程学报》 EI CSCD 北大核心 2010年第13期94-100,共7页

在计算线性供给函数均衡模型(linear supply function equilibrium,LSFE)的过程中,通常需要多次求解各发电商(generation company,GenCo)个体所对应的双层优化问题。提出采用分支定界方法求解计及输电约束的线性供给函数均衡问题。采用... 在计算线性供给函数均衡模型(linear supply function equilibrium,LSFE)的过程中,通常需要多次求解各发电商(generation company,GenCo)个体所对应的双层优化问题。提出采用分支定界方法求解计及输电约束的线性供给函数均衡问题。采用分支剪支操作处理互补松弛约束,仅需要计算少量的子优化问题,就可以达到遍历所有系统松弛子模式的效果。通过3节点系统和IEEE30节点系统2个算例可以看出,所提算法具有很好的搜索效率,为求解大规模电力市场均衡问题提供了一条有效途径。 展开更多

关键词 线性供给函数 分支定界方法 互补松弛约束 松弛子模式

下载PDF 职称材料

无严格互补松驰条件的序列线性方程组新算法 被引量：2

7

作者 高自友 任华玲 贺国平 《数学物理学报（A辑）》 CSCD 北大核心 2004年第3期275-284,共10页

该文通过构造特殊形式的有效集来逼近KKT点处的有效集,给出了一个任意初始点下的序列线性方程组新算法。

关键词 非线性规划 序列线性方程组算法 严格互补松弛 全局收敛性 超线性收敛性

下载PDF 职称材料

(m,n,k)指派问题的最小费用流模型及其算法 被引量：3

8

作者 胡勇文 陈国华 《数学的实践与认识》 北大核心 2017年第18期162-170,共9页

构造(m,n,k)指派问题的最小费用流模型,并将基于对偶原理的最小费用流的允许边算法求解该模型,提出求解(m,n,k)指派问题的一种算法.算法直接在其对应的网络中保持互补松弛条件不变,通过调整节点势以扩大允许网络从而寻求增广链并进行流... 构造(m,n,k)指派问题的最小费用流模型,并将基于对偶原理的最小费用流的允许边算法求解该模型,提出求解(m,n,k)指派问题的一种算法.算法直接在其对应的网络中保持互补松弛条件不变,通过调整节点势以扩大允许网络从而寻求增广链并进行流量增广,直至在网络中得到流量为k的最小费用流,此时非O流边对应(m,n,k)指派问题的最优解.给出了(m,n,k)指派问题的最优解及多重最优解的重要性质,数值试验表明算法有效可行. 展开更多

关键词 (m n k)指派问题 最小费用流问题 最优解性质 互补松弛条件 允许边算法

原文传递

线性规划的对偶理论在图解法中的应用 被引量：3

9

作者 卢楠 孟红云 刘三阳 《高等数学研究》 2019年第1期56-57,89,共3页

对于多个变量两个约束的线性规划,首先利用线性规划的对偶理论,写出其对偶问题;其次利用图解法求出对偶问题的最优解,最后利用互补松弛条件求出原问题的最优解.

关键词 线性规划 对偶理论 对偶问题 图解法 互补松弛条件

下载PDF 职称材料

对线性规划多重解与退化解关系的一点新认识 被引量：2

10

作者 张汉斌 《邢台职业技术学院学报》 2004年第3期24-26,共3页

本文分析得出原问题是多重解,则对偶问题为退化最优解的命题,同时指出它的逆命题不成立,进一步指出多重解与退化解的互补松弛关系。

关键词 线性规划 多重解 退化解 对偶问题 原问题 互补松弛关系

下载PDF 职称材料

树上的限制性node multicut问题 被引量：2

11

作者 杨惠娟 《大理学院学报（综合版）》 CAS 2014年第12期21-25,共5页

割集问题在图论和组合优化中占有重要地位,限制性node multicut问题是割集问题的一类比较重要的推广问题。树上的限制性node multicut问题是值得研究的一个问题。首先说明此问题是NP难的,其次用线性规划理论中的互补松弛条件设计了一个... 割集问题在图论和组合优化中占有重要地位,限制性node multicut问题是割集问题的一类比较重要的推广问题。树上的限制性node multicut问题是值得研究的一个问题。首先说明此问题是NP难的,其次用线性规划理论中的互补松弛条件设计了一个近似值2且时间复杂度为O(max{kn,n log n})的算法。并进一步说明了通过算法得到的解具有半整数的性质。 展开更多

关键词 限制性node multicut 近似算法 互补松弛条件

下载PDF 职称材料

有限资源下最大可靠性网络流中断模型 被引量：1

12

作者 赵佳 于华 《中国工程科学》 北大核心 2015年第1期137-142,共6页

提出了最大可靠性网络流中断模型。此模型是在给定的网络图中,通过在边上设置监测点来阻止给定两个顶点之间的网络流量,同时考虑所设置监测点失效的可能,在给定的资源限制下,最大化中断网络流的可能性,即给定起点和终点的网络图,在资源... 提出了最大可靠性网络流中断模型。此模型是在给定的网络图中,通过在边上设置监测点来阻止给定两个顶点之间的网络流量,同时考虑所设置监测点失效的可能,在给定的资源限制下,最大化中断网络流的可能性,即给定起点和终点的网络图,在资源有限的情况下,选择一些边设置监测点使得从起点到终点的所有路都包含尽可能多的已被设置中断点的边。在给定图中,两点之间的路的条数是图的规模的指数次幂,为此将此模型转化为双层整数规划模型,鉴于双层整数规划模型在一般情况下是不可解的,通过探讨下层整数规划问题与其线性规划松弛之间的关系以及线性规划对偶理论来解此双层整数规划模型。本文不仅将该模型约束的个数从图的规模的指数次幂降到一次幂,同时也提供了一种解双层整数规划问题的方法。 展开更多

关键词 中断模型 k-可靠性 对偶 线性规划松弛 互补松弛型

下载PDF 职称材料

线性规划原问题与其对偶问题基解的互补松弛性

13

作者 卢跃奇 《洛阳师范学院学报》 2023年第5期12-13,19,共3页

线性规划原问题与其对偶问题的关系是研究有关线性规划对偶理论的核心内容,基解的互补松弛性是其中最重要的性质之一.首先完整阐述了线性规划原问题与其对偶问题基解的互补松弛性的内涵,给出了其严格证明过程,并通过具体例子说明基解互... 线性规划原问题与其对偶问题的关系是研究有关线性规划对偶理论的核心内容,基解的互补松弛性是其中最重要的性质之一.首先完整阐述了线性规划原问题与其对偶问题基解的互补松弛性的内涵,给出了其严格证明过程,并通过具体例子说明基解互补松弛性的意义. 展开更多

关键词 对偶问题 基解 互补松弛性

下载PDF 职称材料

求线性二层规划∈-全局最优解的一种方法 被引量：1

14

作者 郑跃 雷国梁 曹晓刚 《数学杂志》 CSCD 北大核心 2013年第5期941-945,共5页

本文研究了线性二层规划问题.利用下层问题的KKT最优性条件将其转化为一个具有互补约束的数学规划问题,提出了一种新的求解方法.该方法仅仅需要求解若干个双线性规划问题,便可以获得原问题的-全局最优解.最后,通过一个算例说明了所提出... 本文研究了线性二层规划问题.利用下层问题的KKT最优性条件将其转化为一个具有互补约束的数学规划问题,提出了一种新的求解方法.该方法仅仅需要求解若干个双线性规划问题,便可以获得原问题的-全局最优解.最后,通过一个算例说明了所提出方法的可行性. 展开更多

关键词 线性二层规划 互补松弛条件 ∈-全局最优解

下载PDF 职称材料

应用同伦法求解原有-对偶线性规划问题

15

作者 高培旺 贺伟奇 《系统工程》 CSCD 北大核心 2004年第1期29-32,共4页

根据线性规划对偶理论中的互补松弛性质,直接构造线性对偶问题的一个同伦模型,并提出相应的同伦算法求解。如果最优解存在,迭代过程常常是收敛的。尤其是在求解过程中,随着参数取值接近1,可获得原有问题的一个近似最优解。

关键词 同伦法 原有-对偶线性规划 互补松弛性质 近似最优解 单纯形法

下载PDF 职称材料

基于模糊关系的互补松弛定理

16

作者 刘心 《辽宁师范大学学报（自然科学版）》 CAS 2010年第4期423-428,共6页

为完善和推广模糊线性规划对偶理论,在基于模糊关系的模糊线性规划(FLP)对偶理论的研究的基础上,分析对偶模糊线性(DFLP)最优解的概念,对经典LP对偶问题中的重要结果进行了推广.提出并推导证明了对偶模糊线性规划(DFLP)问题的对称性定... 为完善和推广模糊线性规划对偶理论,在基于模糊关系的模糊线性规划(FLP)对偶理论的研究的基础上,分析对偶模糊线性(DFLP)最优解的概念,对经典LP对偶问题中的重要结果进行了推广.提出并推导证明了对偶模糊线性规划(DFLP)问题的对称性定理和互补松弛性定理.并举例说明该理论具有一定的应用价值,为存在于现实中的诸多模糊优化问题提供了理论基础. 展开更多

关键词 模糊线性规划 模糊对偶 对称性定理 互补松弛定理

下载PDF 职称材料

非凸半定规划的一个等价性问题

17

作者 任咏红 《辽宁师范大学学报（自然科学版）》 CAS 北大核心 2008年第4期393-397,共5页

求解具有等式约束的非线性优化问题的方法已经很完善,有乘子法,惩罚函数法等,其中将具有不等式约束的优化问题转化为具有等式约束的优化问题进行求解是一种重要途径.将具有不等式约束的非凸半定规划问题(NCSDP)转化为具有等式约束的非... 求解具有等式约束的非线性优化问题的方法已经很完善,有乘子法,惩罚函数法等,其中将具有不等式约束的优化问题转化为具有等式约束的优化问题进行求解是一种重要途径.将具有不等式约束的非凸半定规划问题(NCSDP)转化为具有等式约束的非线性规划问题(ESDP),证明了在(NCSDP)局部解的充分性条件及严格互补与非退化条件之下两个问题的局部等价性. 展开更多

关键词 非凸半定规划 等价性 二阶充分条件 严格互补松弛条件

下载PDF 职称材料

互联网信息组织中一个模型的对偶求解

18

作者 孔淑兰 刘家壮 《山东大学学报（理学版）》 CAS CSCD 北大核心 2003年第3期27-30,共4页

讨论了互联网信息组织和规划的一个新问题 :带拒绝装箱问题 ,利用原始对偶互补松弛条件给出此问题的一个最优值的下界 ,利用下界值对应解的性质得到带拒绝装箱问题的一个近似算法 .

关键词 装箱问题 互联网络 原始对偶互补松弛条件 近似算法

下载PDF 职称材料