求非线性规划的混合整数解的降维搜索法

我们在《求解混合整数线性规划的降维搜索法》一文中提出的方法和步骤可以完全推广到求非线性规划的混合整数解,有关定理的证明也完全相似。     

关于尤格定理的推广

尤格(Юнга)定理是这样叙述的:“设函数,(x,y)对分量x、y分别是连续的,而且对其中一个分量是单调的,则f(x,y)是连续函数。”我们现在把这个定理推广到n维向量函数。和二维空间一般正度量函数。定理1 设函数f(x)对各个分量分别连续,对其中n-1个分量分别单调,则f(x)是连续函数。证明当n=a时,由尤格定理知是成立的。下面用数学归纳法来证明。假设任意,n-1维的向量函数f(x)(其中x=(x_1,x_2,…,x_n-1))如果对每个分量连续,对其中n-2个分量分别单调,则f(x)连续。然后来推导:任意n维向量函数f(x)(x=(x,x,)),如果对每个分量连续,对其中n-1个分量分别单调,则f(x)连续。     

关于整数线性规划全部最优解的一个注记

研究在整数线性规划基最优解已经求出且不唯一的条件下,如何求整数线性规划的全部最优解问题.当整数线性规划具有两个基最优解时,文章给出其全部最优解的个数公式及求全部最优解的一个有效算法.     

多元一次不定方程整数解的通解公式

在不定方程中,二元一次不定方程的全部整数解可用公式表示,而多元一次不定方程a_1x_1+a_2x_2+……+a_nx_n=c,我们知道其有整数解的充要条件是(a_1,a_2,…,a_n)|c,并且求它的整数解的方法,一般是通过解n-1个二元一次不定方程来进行的。本文将给出多元一次不定方程整数解的通解公式。     

一类n阶完全常微分方程边值问题解的存在性

用Leray-Schauder不动点定理,讨论完全n阶边值问题:{-u~((n))(t)=f(t,u(t),u′(t),…,u~((n-1))(t)), t∈[0,1],u~((i))(0)=0, i=0,1,2,…,n-2,u~((n-1))(1)=0烅烄烆解的存在性,其中f:[0,1]×R~n→R为连续函数.在一个允许f(t,x_0,x_1,…,x_(n-1))关于x_i(i=0,1,2,…,n-1)超线性增长的不等式条件及f(t,x_0,x_1,…,x_(n-1))关于x_(n-1)满足Nagumo型增长的条件下,得到了该问题解的存在性.     

一类二维微分差分方程具有多个周期的周期解的一个条件

给出了二维微分差分方程(E)具有周期为4/2n+1,4/2n-1, 4/2n-3,…,4/7,4/5,4/3,4的周期解的一个条件,并在定理的证明过程中给出了如何求出其相应周期解的方法.     

第五章 射影簇的次数

§5A.deg(X)、mult_xX、Blow—upB_r(X)的定义,投射的影响;例题。令 X~rP~n 为 r 维的簇,X 的次数乃是交点的个数,此交点乃是几乎所有线子空间 L~(n-r)P~n 与 X 相交的交点。(y~s 表 S—维簇)(5.1)定理.对一切子簇 X~rP~n 存在整数 d≥1 以致若 L~(n-r)P~n 为线性空间满足下列:a)L∩X=有限集{x_1,…,x_k)b)_i,x_i 为光滑于 X 上,而 T_(xi),P~n 的2个子空间T_(xi),x,T_(xi),_L 在0处相交。则 k=d。     

线性规划最优解集的降维算法

本文对求解线性规划问题提出了可去零约束和可去零分量的概念,并以此为工具,给出了线性规划最优解集的降维算法.     

不定方程 a_1x_1 a_2x_2 … a_sx_s=n 的Frobenius问题

对于 n 和 a_1,a_2均是正整数,且(a_1,a_2)=1的二元一次不定方程 a_1x1 a_2x_2=n,能够找到仅与 a_1,a_2有关的整数 g(a_1,a_2)=a_1a_2-a_1-a_2,使得当 n>g(a_1,a_2)时,不定方程有非负整数解,而当 n=g(a_1,a_2)时,不定方程没有非负整数解。求 g(a_1,a_2)的问题就是二元一次不定方程的 Frobenius 问题。本文解决如何求仅与不定方程 a_1x_1 a_2x_2 … a_2x_2     

解某些线代数方程组的降阶方法

对于n阶的线代数方程组Ax=k (1)其中I_(11),I_(22)分别为r×r及n-r×n-r的单位阵,且B=(?) (3)是指数为2的弱循环收敛阵[1].[2][3]已指出,为求解(1),只需解r×r的方程组(I_(11)-B_(12)B_(21))x_1=k_1+B_(12)Ek_2 (4)求出x_1,然后按x_2=B_(21)x_1+k_2 (5)求出x_2.在此基础上,[2]介绍了当B为不可分的非负阵[1]时,解(4)的导出的正则     

关于不定方程a_1X_1+a_2X_2+…+a_nX_n=N的非负解个数的讨论

设不定方程(1)a_1x_1+a_2x_2+…+a_nx_n=N,其中,n≥2,(a_1,…a_n)=1,N和a_i(i=1,2,…,n)均为正整数(且不妨假设a_1≤a_2≤…≤a_n)。 (1) (1)的非负整数解的个数是有限的,设为T_n(N)。记0相似文献   

目标等值面切割定界与割平面法结合求解整数规划

把目标等值面切割定界原理与Gomory的割平面法结合起来求解整数线性规划(ILP)问题．首先通过目标函数等值面的平行移动来切去(LP)可行域中含其非整数最优解但不含(ILP)可行解的“无用部分”;然后,应用Gomory的割平面在通过(ILP)最优解的目标等值面上切割其最优解。     

求解线性规划的快速算法

本文给出了一类求解线性规划min{cTx|Ax≤b}的快速算法,大量数值实验表明计算速度是单纯形方法和Karmarkar方法的几十倍到几百倍。其基本计算步骤为: Step 0 给出初始可行解x_0和正整数k_0,置k=0 Step 1 从x_0出发,沿方向P=-C搜索到约束边界得x_1     

关于Sylvester问题的n维Hostinsky公式

1925年Hostinsky得到了关于Sylvester问题的3维Hostinsky公式。在n维欧氏空间的一个凸体内独立随机地取n+2个点,这n+2个点形成凹多面体的概率是多少,这就是n维Sylvester问题,本文将得到n维的Hostinsky公式。引理1 n-1维欧氏空间的n个点(?)_1(x_1~(1),…,x_(n-1)~(1),),……,(?)_n(x_1~(1),…,x_(n-1)~(n))所成多面体的体积是     

关于Sylvester问题的n维Hostinsky公式

1925年Hostinsky得到了关于Sylvester问题的3维Hostinsky公式。在n维欧氏空间的一个凸体内独立随机地取n 2个点,这n 2个点形成凹多面体的概率是多少,这就是n维Sylvester问题,本文将得到n维的Hostinsky公式。引理1 n-1维欧氏空间的n个点Q_1(x_1~(1),…,x_(n-1)~(1)),……,Q_n(x_1~(1),…,x_(n-1)~(1))所成多面体的体积是     

Z／mZ上的多变元置换多项式

设m和n是二个正整数,f(x_1,…,x_n)是一个整系数多项式,如果同余式f(x_1,…,x_n)≡a(modm)对所有的整数a均有m~(n-1)个解,则称f(x_1,…,x_2)是一个模m的置换多项式.一个基本的问题是:如何决定一个多项式是否置换多项式,如果m是素数,已知一些判别方法.在本文中,我们研究m为复合数的情形.     

一种求解N人合作对策核仁的方法

本文采用Maschler, Peleg和Shaply,[4]所给核仁的等价定义。用与此定义相同的递归顺序,先通过解一线性规划问题求出(ε~i,Σ_i)中的ε~i和达到这一最优值的最优极点解。再以这一点为起点,以Kohlberg定理([8] Theorem2)为基础,建立一个线性规划问题,求它的最优极点解,反复迭代计算,最后求出Σ_(io)这样,就求出了(ε~i,Σ_i)(i=1,2,…,τ)和达到这一结果的相应点列。这个点列收敛到核仁,点列中地多有(2~n-2)~2/2个点。     

求任意正整数m的缩系的新方法

一引言熟知,缩系的概念和构造缩系都是很重要的。通常,求一正整数m的缩系主要依据如下定理[1]:若(m_1, m_2)=1(m_1m_2=m),x_1过m_1之一缩系,x_2过m_2_之一缩系,则m_1x_2 m_2x~1过m之一缩系.或在特殊情形,即m=2,4,p~l及2p~l(此处p为素数)时,先求出模     

基本解全为整数的线性规划构造

线性规划minf=C^TX,AX=6,X≥0的系数矩阵A,列向量C及6都由整数组成,要求它的基本解全为整数组成,为了构造这样的线性规划,本文定义了互逆整数矩阵,不变整数矩阵和多1连接向量三个概念,并导出7个定理．在定理5、定理6及定理7的基础上,给出m行、1/2m(m 1)列不变整数矩阵A的构造方法,使对应的线性规划的基本解全由整数所组成。     

差分方程xn+1=(α+B1xn-1+B3xn-3+…+B2k+1xn-2k-1)/(A+B0xn+B2xn-2+…+B2kxn-2k)的动力学

考察差分方程x_(n 1)=(α B_1x_(n-1) B_3x_(n-3) … B_(2k 1)x_(n-2k-1))/(A B_0x_n B_2x_(n-2) … B_(2k)x_(n-2k)),n=0,1,…的动力学行为,在4种情形下分别讨论方程解的性质.