多目标分式规划的两种新对偶形式

§1.引言和引理 在[1]和[2]中,C.Singh和林锉云曾分别研究了多目标分式规划的对偶问题,本文则给出多目标分式规划的另外两种新的对偶形式。这两种对偶规划和R.Jagannathan以及C.Bector关于非线性规划的对偶理论有关。最后,我们还讨论了所研究的两种多目标分式对偶规划之间的相互关系。 考虑多目标分式规划     

n维复形上一类具有线性分式目标函数的规划问题

ｎ维复形上一类具有线性分式目标函数的规划问题郑汉鼎（山东大学教学系，济南２５０１Ｏ０）文献［１，２］已经研究了ｎ维复形上的规划问题，本文将讨论。维复形上具有线性分式目标函数的规划问题．问题Ⅰ给定一个ｎ维复形Ｋｎ和一个ｒ－１维边缘链，要找一个ｒ维链。使...     

线性分式规划优化分析的元模型方法

1引言线性分式规划(LFP): min f(x)=(p~Tx α)/(q~Tx β) s.t. Ax=b (1) x≥0有着重要的应用背景,特别在经济管理中受到广泛关注．例如,以净收益率为优化目标函数的海洋运输问题;当价格系数为随机变量时,优化目标为获得满意的收益水平概率最大的资源分配问题等[11]．线性分式规划是一类特殊的非线性规划,除一般的非线性规划求解方法外,它还有一些特殊的专用算法．这里,我们要考虑的问题是;当右端资源约束向量在一定范围内(即L≤b≤U,L,U分别为b的下界和上界)变化时,目标函数的最优值如何变化?我们把这一问题称之为线性分式规划的优化分析．     

含有模糊决策的线性分布式多目标规划

针对实际问题中决策变量通常是模糊的情况,讨论具有块角结构的含有模糊决策的线性分式多目标规划模型。使用α－水平集,建立了对应的α－多目标规划模型。为解决这类问题,设计了基于模糊模拟的遗传算法。数值例子表明,遗传算法很好地解决了这个问题。     

多目标规划的障碍函数问题

本文讨论了多目标规划的障碍函数问题。研究了障碍函数问题有效解与原问题有效解之间的关系,也研究了这两问题有效解集E(X_0,μ)和E(X)之间的关系。其中一些结论是非线性规划结论的推广,另一些结论是新的。     

区间目标规划与模糊目标规划

从区间数与模糊数的序关系出发讨论了一类目标函数含区间数系数的非线性规划和目标函数中含有模糊数系数的线性规划问题,提出将相应的规划问题等价地转化为两个依次求解的经典数学规划问题来求最优解.     

一类G-(F,ρ)凸多目标分式规划的最优性条件

本文讨论了一类多目标分式规划问题，其中所包含的函数是局部Lipschitz的和Clarke次可微的．首先，在G-(F，ρ)凸的条件下，证明了择一定理．然后，证明了该多目标分式规划问题在Geoffrion意义下的真有效解的充分条件和必要条件．     

多目标分式规划逆对偶研究

考虑了一类可微多目标分式规划问题.首先,建立原问题的两个对偶模型.随后,在相关文献的弱对偶定理基础上,利用Fritz John型必要条件,证明了相应的逆对偶定理.     

解线性目标规划的《量化优先因子法》—基于LP过程的算法

本文提出一种解线性目标规划及整数线性目标规划的《量化优先因子法》,即把目标规划中表示优先等级的优先因子 pl( l=1 ,2 ,… ,L)用能从数量级上刻划优先因子 Pl Pl+ 1的本质特征的数来表示 ,进而用 SAS/OR软件包中解线性规划的 LP过程即可求解此线性目标规划 .通过实例给出算法与用 LP过程求解的程序 .     

线性等式约束多目标规划的一个降维算法

本文提出具有线性等式约束多目标规划问题的一个降维算法．当目标函数全是二次或线性但至少有一个二次型时，用线性加权法转化原问题为单目标二次规划，再用降维方法转化为求解一个线性方程组．若目标函数非上述情形，首先用线性加权法将原问题转化为具有线性等式约束的非线性规划，然后，对这一非线性规划的目标函数二次逼近，构成线性等式约束二次规划序列，用降维法求解，直到满足精度要求为止．     

求解多层线性规划的模糊规划法

本文用模糊集理论中的隶属函数描述多层线性规划的各层目标,在第一层给定最小满意水平下,通过求解相应层次的模糊规划来确定各层的最小满意度,从而最终得到问题的一个满意解。提出的方法只需求解一系列线性规划问题,具有较好的计算复杂性和可行性,最后的算例进一步验证了方法的有效性。     

正态随机规划的确定性规划及其灵敏度分析

在大量的管理决策问题中,经常会遇到目标函数的系数和右端常数为相互独立的正态随机变量的随机线性规划模型.利用对偶规划将正态随机规划化为具有α可靠度的线性规划,给出了解决该正态随机规划的一个有效方法,并对正态随机变量的参数进行了灵敏度分析,避免了由于参数估计偏差给决策带来的风险,保证了最优方案的α可靠度.     

Maximum Feasibility Problem for Continuous Linear Inequalities with Applications to Fuzzy Linear Programming

Systems of linear inequalities are important tools to formulate optimization problems. However, the feasibility of the whole system was often presumed true in most models. Even if an infeasible system could be detected, it is in general not easy to tell which part of the system caused it. This motivates the study of continuous linear inequalities, given no information whether it is feasible or not, what is the largest possible portion of the system that can be remained in consistency? We first propose a bisection-based algorithm which comes with an auxiliary program to answer the question. For further accelerating the algorithm, several novel concepts, one called “constraint weighting” and the other called “shooting technique”, are introduced to explore intrinsic problem structures. This new scheme eventually replaces the bisection method and its validity can be justified via a solid probabilistic analysis. Numerical examples and applications to fuzzy inequalities are reported to illustrate the robustness of our algorithm.     

Comparison of Two Reformulation-Linearization Technique Based Linear Programming Relaxations for Polynomial Programming Problems

In this paper, we compare two strategies for constructing linear programmingrelaxations for polynomial programming problems using aReformulation-Linearization Technique (RLT). RLT involves an automaticreformulation of the problem via the addition of certain nonlinear impliedconstraints that are generated by using the products of the simple boundingrestrictions (among other products), and a subsequent linearization based onvariable redefinitions. We prove that applying RLT directly to the originalpolynomial program produces a bound that dominates in the sense of being atleast as tight as the value obtained when RLT is applied to the jointcollection of all equivalent quadratic problems that could be constructed byrecursively defining additional variables as suggested by Shor.     

Exterior Minimum-Penalty Path-Following Methods in Semidefinite Programming

A semidefinite programming problem is a mathematical program in which the objective function is linear in the unknowns and the constraint set is defined by a linear matrix inequality. This problem is nonlinear, nondifferentiable but convex. It covers several standard problems, such as linear and quadratic programming, and has many applications in engineering. In this paper, we introduce the notion of minimal-penalty path, which is defined as the collection of minimizers for a family of convex optimization problems, and propose two methods for solving the problem by following the minimal-penalty path from the exterior of the feasible set. Our first method, which is also a constraint-aggregation method, achieves the solution by solving a sequence of linear programs, but exhibits a zigzagging behavior around the minimal-penalty path. Our second method eliminates the above drawback by following efficiently the minimum-penalty path through the centering and ascending steps. The global convergence of the methods is proved and their performance is illustrated by means of an example.     

一类0-1二次规划最优解的新算法

从矩阵的基础知识出发,给出了当目标函数矩阵是严格对角占优阵时,快速地获得0-1二次规划最优解的一个新算法;该方法具有很强的实用性,是此类问题的一个高效求解算法.     

Differential-Algebraic Approach to Linear Programming

This paper presents a differential-algebraic approach for solving linear programming problems. The paper shows that the differential-algebraic approach is guaranteed to generate optimal solutions to linear programming problems with a superexponential convergence rate. The paper also shows that the path-following interior-point methods for solving linear programming problems can be viewed as a special case of the differential-algebraic approach. The results in this paper demonstrate that the proposed approach provides a promising alternative for solving linear programming problems.     

紧急输送策略的线性规划模型

以美国南弗洛里达州递避飓风袭击为例建立了紧急输送情况下的线性规划模型。其中具体建立了以SCEPD(美国南弗洛里达州紧急情况预防部门)提出的公路反向，地区分块撤离，使用小路等三个最受人们关注的策略的模型。模型的灵敏度分析能很好地解释建立更多的临时避难所、限制车辆等策略对撤离的影响。在相近的环境下，中模型解得的结果很接近官方预测的结果，并且本的模型能对更广泛的情况进行分析．可给SCEPD提供一定参考。     

Primal-Dual Simplex Method for Multiobjective Linear Programming

We develop a primal-dual simplex algorithm for multicriteria linear programming. It is based on the scalarization theorem of Pareto optimal solutions of multicriteria linear programs and the single objective primal-dual simplex algorithm. We illustrate the algorithm by an example, present some numerical results, give some further details on special cases and point out future research. The paper was written during a visit of the first author to the University of Sevilla financed by a grant of the Andalusian Consejería de Educación. The research of the first author was partially supported by University of Auckland Grant 3602178/9275. The research of the second and third authors was partially financed by Spanish Grants BFM2001-2378, BFM2001-4028, MTM2004-0909 and HA2003-0121. We thank Anthony Przybylski for the implementation and making his results available. We thank the anonymous referees, whose comments have helped us to improve the presentation of the paper.     

线性规划约束方程系数矩阵的敏感性分析

本文首先给出了用当前基解和系数矩阵A的行(或列)增向量直接计算新基解及其检验数的一个简单公式,进而讨论了关于线性规划系数矩阵A的一行(列)向量变化的敏感性分析问题。给出了保持最优基不变时ΔA的变化范围。