线性规划的对偶理论在图解法中的应用

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

互补基解性质的应用研究

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

一类系数为梯形模糊数的两层多随从线性规划模型

针对一类系数为梯形模糊数的两层多随从线性规划问题,利用模糊结构元理论定义了模糊结构元加权序,证明了一类系数为梯形模糊数的两层多随从线性规划问题的最优解等价于两层多随从线性规划问题的最优解.根据线性规划的对偶定理和互补松弛性质,得到了两层多随从线性规划模型的最优化条件.最后,利用两层多随从线性规划模型的最优化条件,设计了求解一类系数为梯形模糊数的两层多随从线性规划问题的算法,并通过算例验证了该方法的可行性和合理性.     

隐互补问题的极小化变形及其稳定点

1 引言 互补问题在最优化中有着广泛的应用,例如线性规划中的对偶问题,非线性规划中求稳定点的KKT条件以及变分不等式的求解都可以转化为互补问题,另外,某些均衡网络设计问题、信号最优化问题以及交通配置等问题也可利用互补问题来求解.     

实时求解线性规划问题的原对偶神经网络(英文)

本文探讨了线性规划的原问题与对偶问题理论,并在此基础上可开发出一种用于在线求解线性规划的递归神经网络和应用于冗余机器手臂逆运动学的求解问题上.如,Tang等人开展的原对偶神经网络.但鉴于对偶理论的复杂性和多样性,该原对偶神经网络模型仅可以得到线性规划问题的可行解,而本文对该网络模型改进后可得到线性规划问题的最优解.仿真结果证实了这种改进模型在解决线性规划问题上的有效性、正确性和高效率.     

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

用线性规划对偶理论分析了双层线性规划的最优解与下层问题的对偶问题可行域上极点之间的关系，通过求得下层问题的对偶问题可行域上的极点，将双层线性规划转化为有限个线性规划问题，从而用线性规划方法求得问题的全局最优解．由于下层对偶问题可行域上只有有限个极点，所以方法具有全局收敛性．     

求最优权对集的一个对偶算法

1.引言 Edmonds给出了求一个图的最大权对集的算法它是从一个满足原始对偶可行的解出发使其逐步满足互补松驰条件。[1]描述了一个求最大权完美对集原始算法。它是从一个满足互补松驰条件的原始可行解出发,使其逐步满足对偶可行条件。我们给出一个求图的最大权完美对集的对偶算法,它是从一个满足互补松驰条件的对偶可行解出发使其逐步满足可行条件。本算法开始不要求给出图的一个完全对集,其对偶变量的改变法则也较[1]中的法则简单得多。其基本方法仍是用Edmonds的花的算法[2]。我们将说明本文的算法可用来解其他的最优对集问题。本文中采用的术语参看[2]。     

基于指数型核函数的线性规划原始对偶内点算法

给出线性规划原始对偶内点算法的一个单变量指数型核函数.首先研究了这个指数型核函数的性质以及其对应的障碍函数.其次,基于这个指数型核函数,设计了求解线性规划问题的原始对偶内点算法,得到了目前小步算法最好的理论迭代界.最后,通过数值算例比较了基于指数型核函数的原始对偶内点算法和基于对数型核函数的原始对偶内点算法的计算效果.     

基于半光滑方程的线性规划问题局部灵敏度分析

本文考虑线性规划的局部灵敏度问题.首先用非线性互补函数将线性规翊I问题的KKT系统转化为一个半光滑的方程组,然后利用半光滑函数的性质,得到一个能同时求所有变量(包括对偶变量)关于价值系数c,资源向量b,技术消耗系数aij的局部灵敏度的计算公式.该方法能处理任意特性的最优解(包括严格互补解和退化解)的局部灵敏度分析.具体算例说明了分析方法的应用.     

影子价格及其在资源配置中的应用研究

为了应用影子价格实现资源在全社会的最优配置,本文通过线性规划的对偶理论和非线性优化问题的Kuhn-Tucker条件揭示了影子价格的本质,在资源配置优化问题中线性规划模型中的影子价格就是其对偶问题的最优解,非线性规划模型中的影子价格就是与最优解相对应的拉格朗日乘数。根据松紧定理解释了资源影子价格与资源限量之间的关系,还对线性规划模型与非线性规划模型中影子价格的不同表现进行了分析。最后阐明了影子价格在资源配置中的应用。     

Graphical analysis of duality and the Kuhn-Tucker conditions in linear programming

Careful inspection of the geometry of the primal linear programming problem reveals the Kuhn-Tucker conditions as well as the dual. Many of the well-known special cases in duality are also seen from the geometry, as well as the complementary slackness conditions and shadow prices. The latter at demonstrated to differ from the dual variables in situations involving primal degeneracy. Virtually all the special relationships between linear programming and duality theory can be seen from the geometry of the primal and an elementary application of vector analysis.     

非线性-线性二层规划问题的罚函数方法

利用下层问题的K-T最优性条件将下层为线性规划的一类非线性二层规划转化成相应的单层规划,同时取下层问题的互补条件为罚项,构造了该类非线性二层规划的罚问题.通过对相应罚问题性质的分析,得到了该类非线性二层规划问题的最优性条件,同时设计了该类二层规划问题的求解方法.数值结果表明该方法是可行、有效的.     

Asymptotic kuhn-tucker conditions in abstract spaces

Asymptotic extensions of the Kuhn-Tucker conditions, in which both the adjoint equation and the complementary slackness condition are solved asymptotically, are given for vector-valued mathematical programming problems in locally convex spaces. Under appropriate hypotheses, the conditions are both necessary and sufficient for optimality. In particular, they characterize optimality for linear programs. An asymptotic dual program is also given.     

ON SOME PROPERTIES OF SOLUTIONS TO SEMIDEFINITE PROGRAMMING

It is well known that for symmetric linear programming there exists a strictly complementary solution if the primal and the dual problems are both feasible. However, this is not necessary true for symmetric or general semide finite programming even if both the primal problem and its dual problem are strictly feasible. Some other properties are also concerned.     

集值映射多目标半定规划的Kuhn-Tucker鞍点最优性条件

首先在序拓扑线性空间中定义了集值映射多目标半定规划问题的KuhnTucker鞍点,在广义锥-次类凸条件下,讨论了此集值优化问题的弱有效解和Benson真有效性解与Kuhn-Tucker鞍点之间的关系.     

Complementary variational principle and duality in mathematical programming

The relationship between the complementary variational principle and duality in mathematical programming is demonstrated through a geometric approach in a Hilbert space setting. A necessary and sufficient condition for the existence of such a principle is given in the case of a convex functional constrained by linear dynamics. Its relationship to the Kuhn-Tucker saddle point theory is indicated. Applications to various programming and control problems are discussed.     

On geometric programming and complementary slackness

When the terms in a convex primal geometric programming (GP) problem are multiplied by slack variables whose values must be at least unity, the invariance conditions may be solved as constraints in a linear programming (LP) problem in logarithmically transformed variables. The number of transformed slack variables included in the optimal LP basis equals the degree of difficulty of the GP problem, and complementary slackness conditions indicate required changes in associated GP dual variables. A simple, efficient search procedure is used to generate a sequence of improving primal feasible solutions without requiring the use of the GP dual objective function. The solution procedure appears particularly advantageous when solving very large geometric programming problems, because only the right-hand constants in a system of linear equations change at each iteration.The influence of J. G. Ecker, the writer's teacher, is present throughout this paper. Two anonymous referees and the Associate Editor made very helpful suggestions. Dean Richard W. Barsness provided generous support for this work.     

Posynomial geometric programming as a special case of semi-infinite linear programming

This paper develops a wholly linear formulation of the posynomial geometric programming problem. It is shown that the primal geometric programming problem is equivalent to a semi-infinite linear program, and the dual problem is equivalent to a generalized linear program. Furthermore, the duality results that are available for the traditionally defined primal-dual pair are readily obtained from the duality theory for semi-infinite linear programs. It is also shown that two efficient algorithms (one primal based and the other dual based) for geometric programming actually operate on the semi-infinite linear program and its dual.