整数规划中割平面法的研究

割平面法是求解整数规划问题常用方法之一.用割平面法求解整数规划的基本思路是:先用单纯形表格方法去求解不考虑整数约束条件的松弛问题的最优解,如果获得的最优解的值都是整数,即为所求,运算停止.如果所得最优解不完全是整数,即松弛问题最优解中存在某个基变量为非整数值时,就从最优表中提取出关于这个基变量的约束等式,再从这个约束式出发构造一个割平面方程加入最优表中,再求出新的最优解,这样不断重复的构造割平面方程,直到找到整数解为止.主要研究以下四个关键点:一是研究从最优表中提取出的、关于基变量的约束等式出发,通过将式中的系数进行整数和非负真分数的分解,从而得到一个小于等于0的另外一个不等式的推导过程;二是总结出从小于等于0的那个约束不等式出发构造割平面方程的四种方法;三是分析构造割平面方程的这四种方法相互之间的区别和联系;四是探讨割平面法的几何意义.通过对这四个方面的分析和研究,对割平面法进行透彻的剖析,使读者能够全面把握割平面法.     

Gomory割平面的构造方式与选择标准

本文从Gomory割平面构造原理出发,在证明了利用Gomory割平面法则导出的整数和真分数两种割平面等价的基础上,将当前Gomory割平面分为标准割平面和化整割平面两类.其次,通过比较两类割平面,指出化整割平面存在使系数向量压缩,从而导致化整割平面构造困难的不足;最后,在扩大割平面备选集合和改进备选方程选择标准的基础上,给出了更为系统的Gomory割平面选择方法.     

科学计数法与近似数

一、方法导学1 .科学记数法　把一个数写成ａ× 1 0 ｎ 的形式 (其中 1≤ａ<1 0 ,ｎ是整数 ) ,这种记数法叫做科学记数法 .记数的方法 :①确定ａ .ａ是只有一位整数数位的数 .②确定ｎ .当原数≥ 1时 ,ｎ等于原数的整数位数减 1 ;当原数 <1时 ,ｎ是负整数 ,它的绝对值等于原数中左起第一个非零数字前零的个数 (含整数位上的零 ) .2 .近似数　一般地 ,一个近似数四舍五入到哪一位就说这个近似数精确到哪一位 .一个近似数 ,从左边起第一个非 0数字起 ,直到精确到的数位 ,所有的数字都叫做这个近似数的有效数字 .注意 :2 .0 5与 2 .0 50 0的区…     

再谈梯形与不等式

文[1]中,笔者曾构造了一个特殊梯形,直观地解释了一个著名不等式,在对这个梯形的继续研究中,发现如果让和底边垂直的腰长等于上下底的和,通过计算特殊线段的长度,同样可以直观地解释这组著名不等式.     

求非线性规划的非可行滤子无二次子规划方法

本文研究了不等式约束的非线性规划问题.利用带滤子的无二次子规划(QP-free)非可行域方法,构造一个等价于原约束问题的一阶KKT条件的非光滑方程组,给出解这个方程组的迭代算法,并获得算法的全局收敛性.     

巧用判别式 简解数学题

<正>一元二次方程根的判别式是方程知识的核心内容,是联系3个"二次"(二次函数、二次方程与二次不等式)的重要桥梁.巧用判别式简解数学题,关键在于构造出一元二次方程,然后利用Δ≥0来求解;或构造恒大于等于(或小于等于)0的二次不等式,然后利用Δ≤0来解答.对有些看似与一元二次方程毫无关联的     

混合整数半无限规划问题

本文主要讨论混合整数半无限规划(mixed integer semi-infinite programming, MISIP)问题的求解方法.首先分离内层约束中的连续变量和整数变量并将原问题转化为混合整数互补约束规划(mixed integer mathematical programming with complementarity constraints, MIMPCC)问题.其次在假设内层问题满足Slater约束规范的条件下得到了转化前后问题的等价性.继而分别将MIMPCC问题转化为可用常规优化软件求解的混合整数规划问题和非线性规划问题.由于在转化过程中会生成大量的变量和约束,为求解内层问题中变量较多的MISIP问题,本文提出一种行约束生成法,并证明该算法可在最多O(|Z|)次迭代之后得到最优解.最后通过一些数值实例验证算法的有效性.     

非线性规划的一个罚内点方法

针对具有不等式约束的非线性规划,结合罚内点途径,且在牛顿法的基础上,提出一个算法.通过引入辅助变量松弛不等式约束,把约束集合转化为两个集合的交集:一个是容易计算内点的,另一个是简单线性的.这样就提出了解决此问题的一个新的障碍和罚函数方法且给出了其方法的一般收敛性结果.对接近度量和算法参数的选择途径也进行了研究,从而程序上保证了一旦障碍参数被更新,算法仅需要有限牛顿步就能达到近似中心.数值例子说明了方法的有效性.     

一类实代数整数的无理性的初等证明

假设复数ε是某个首1的整系数方程xn a1xn-1 a2xn-2 … an=0的根,那么称ε是一个代数整数.通过整数的整除性理论(算术基本定理),我们可以证明:若实代数整数ε不是一个有理整数,则ε必是一个无理数.在本文里,我们只需用到最基本的不等式技巧即可得到这个常用结论的证明.为了说明这个方法,我们从最简单的无理的代数整数√2谈起.     

整数规划新进展

整数规划是对全部或部分决策变量为整数的最优化问题的模型、算法及应用等的研究, 是运筹学和管理科学中应用最广泛的优化模型之一. 首先简要回顾整数规划的历史和发展进程, 概述线性和非线性整数规划的一些经典方法. 然后着重讨论整数规划若干新进展, 包括0-1二次规划的半定规划~(SDP)~松弛和随机化方法, 带半连续变量和稀疏约束的优化问题的整数规划模型和方法, 以及0-1二次规划的协正锥规划表示和协正锥的层级半定规划~(SDP)~逼近. 最后, 对整数规划未来研究方向进行展望并对一些公开问题进行讨论.     

Long-step primal-dual target-following algorithms for linear programming

In this paper we propose a long-step target-following methodology for linear programming. This is a general framework, that enables us to analyze various long-step primal-dual algorithms in the literature in a short and uniform way. Among these are long-step central and weighted path-following methods and algorithms to compute a central point or a weighted center. Moreover, we use it to analyze a method with the property that starting from an initial noncentral point, generates iterates that simultaneously get closer to optimality and closer to centrality.This work is completed with the support of a research grant from SHELL.The first author is supported by the Dutch Organization for Scientific Research (NWO), grant 611-304-028.The fourth author is supported by the Swiss National Foundation for Scientific Research, grant 12-34002.92.     

Trefftz,collocation, and other boundary methods—A comparison

In this article we survey the Trefftz method (TM), the collocation method (CM), and the collocation Trefftz method (CTM). We also review the coupling techniques for the interzonal conditions, which include the indirect Trefftz method, the original Trefftz method, the penalty plus hybrid Trefftz method, and the direct Trefftz method. Other boundary methods are also briefly described. Key issues in these algorithms, including the error analysis, are addressed. New numerical results are reported. Comparisons among TMs and other numerical methods are made. It is concluded that the CTM is the simplest algorithm and provides the most accurate solution with the best numerical stability. © 2006 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2007     

Volume preserving RK methods for linear systems

1. IntroductionIn recent yearss there has been a great interest in constructing numerical integrationschemes for ODEs in such a way that some qualitative geometrical properties of the solutionof the ODEs are exactly preserved. R.th[ll and Feng Kang[2'31 has proposed symplectic algorithms for Hamiltollian systems, and since then st ruct ure s- preserving me t ho ds fordynamical systems have been systematically developed[4--7]. The symplectic algorithms forHamiltonian systems, the volume-pre…     

求解离散不适定问题的正则化GMERR方法

迭代极小残差方法是求解大型线性方程组的常用方法, 通常用残差范数控制迭代过程.但对于不适定问题, 即使残差范数下降, 误差范数未必下降. 对大型离散不适定问题,组合广义最小误差(GMERR)方法和截断奇异值分解(TSVD)正则化方法, 并利用广义交叉校验准则(GCV)确定正则化参数,提出了求解大型不适定问题的正则化GMERR方法.数值结果表明, 正则化GMERR方法优于正则化GMRES方法.     

s个几乎相等的素数的k次方和(Ⅰ)

假定pθ‖k,当p=2,2|k时，γ=θ 2；其它情况时，γ=θ 1。而R＝П(p-1)|kp^γ。本文在GRH（广义Riemann假设下），证明了当s=2^k 1,1≤k≤11时，任何足够大的整N≡s(modR)都可以表示为s个几乎相等的素数的k次方程。     

A note on the biasing of Newton's direction

This note deals with the geometric interpretation of the Levenberg-Marquardt search direction when the augmented Hessian is not positive definite.     

Diagonalized multiplier methods and quasi-Newton methods for constrained optimization

Two approaches to quasi-Newton methods for constrained optimization problems inR ⁿ are presented. These approaches are based on a class of Lagrange multiplier approximation formulas used by the author in his previous work on Newton's method for constrained problems. The first approach is set in the framework of a diagonalized multiplier method. From this point of view, a new update rule for the Lagrange multipliers which depends on the particular quasi-Newton method employed is given. This update rule, in contrast to most other update rules, does not require exact minimization of the intermediate unconstrained problem. In fact, the optimal convergence rate is attained in the extreme case when only one step of a quasi-Newton method is taken on this intermediate problem. The second approach transforms the constrained optimization problem into an unconstrained problem of the same dimension.The author would like to thank J. Moré and M. J. D. Powell for comments related to the material in Section 13. He also thanks J. Nocedal for the computer results in Tables 1–3 and M. Wright for the results in Table 4, which were obtained via one of her general programs. Discussions with M. R. Hestenes and A. Miele regarding their contributions to this area were very helpful. Many individuals, including J. E. Dennis, made useful general comments at various stages of this paper. Finally, the author is particularly thankful to R. Byrd, M. Heath, and R. McCord for reading the paper in detail and suggesting many improvements.This work was supported by the Energy Research and Development Administration, Contract No. E-(40-1)-5046, and was performed in part while the author was visiting the Department of Operations Research, Stanford University, Stanford, California.     

投入产出技术在计划平衡中的理论与应用

在用投入产出技术作计划平衡时，目前一般采用最终产品法、总产品法及国民收入法等．本文从理论上研究了这些方法的可行性问题，并在此基础上提出一个较理想的综合法．最后附有实例并说明综合法的现实意义．     

A comparison of some ODE solvers which require Jacobian evaluations

A variety of third-order ODE solvers which have a minimum configuration (i.e. minimum work per step) have been numerically tested and the results compared. They include implicit and explicit processes, and share the property that a Jacobian matrix must be evaluated at least once during the integration. Some of these processes have not been previously described in the literature.     

一种求解鞍点问题的广义对称超松弛迭代法

本文研究了鞍点问题的迭代算法.利用新的待定参数加速迭代格式并结合SSOR分裂的方法,获得了有两个参数的广义对称超松弛迭代法及其收敛性条件.数值例子表明选择适当的参数值可以提高算法的收敛效率,推广和改进了SOR-like迭代法.