一个新的线性规划多项式算法——Karmarkar 方法

<正> 最近,《纽约时报》和《时代》周刊等许多报刊均以醒目的标题详细地报道了美国贝尔实验室28岁的印度数学家 N.Karmarkar 在线性规划理论方面取得重大突破的消息.所谓线性规划问题,就是在一组线性不等式的约束下求一个线性目标函数的极值问题.其数学模型的一般形式可表示为min c~Tx,x∈P,其中 P-{x∈R~n|Ax≤b,x≥0},c 和 b 分别是 n 维和 m 维实向量,A 是 m×n 实矩阵.就是这样一个简单的问题,其应用广泛性简直令人惊讶.据国外有人统计,它占用了世界上计算机的大部分时间.     

广义预条件迭代方法

§1.引言和新方法的提出 设线性代数方程组 Ax=b,(1.1)这里A是n阶非奇异矩阵,x,b是n维向量且b是已知向量,x是未知向量.对于(1.1)的数值解,我们考虑如下的分裂:     

线性规划的最钝角CRISS-CROSS算法

1 引言 考虑如下标准线性规划问题 minimize c~Tx (1) subject to Ax=b, x≥0 其中A∈R~(m×n) (m相似文献   

解线性规划改进的Bartels-Golub算法

其中A是秩为m的m×n矩阵,c、x是n维向量,b是m维向量,由凸性理论知,约束(1.2)构成一个n维欧几里德空间的凸多面集,这个凸多面集的顶点就是约束的基本可行解,线性函数z=c~Tx在这个凸多面集的顶点上取得它的极值。根据这个理论,线性规划的单纯形法就是从某个基本可行解过渡到另一个基本可行解,而使目标函数值下降。     

SSOR半迭代方法最优参数的确定

§1 SSOR半迭代方法 设n阶线性方程组 Ax=b,(1.1) 其中A是n×n复(或实)非奇异矩阵,b是n维复(或实)向量,x是未知向量。 方程组(1.1)改写成同解方程组     

简单补偿随机线性规划的对偶并行算法

一、引言随机线性规划中,具有简单补偿的二阶段问题是(?){c~Tx E(?)q~Ty|Wy=b(ω)-AX,y≥0}(A)其中 c 是 n 维常向量,q=(q~ /q~-)是2m 维常向量,且(?)=q~ q~-≥0,A 是 m×n 常矩阵,W=((?),I),I 是 m×m 单位矩阵,b(ω)=(b_1(ω),…,b_m(ω))~T 是 m 维随机向量,它的边沿分布函数为 F_b(τ)=(F_1(τ_1),…,F(τ_n))~T,E 表示求随机变量的数学期望,X(?)R~n 是凸多面体集.可以证明,问题(A)与下列问题等价     

解超定病态线性方程组问题

给出超定方程组 Ax=b (1.1)其中A是秩为r的m×n矩阵,b是m维向量,x是n维未知向量. 目前处理病态线性方程组的方法大体上可以分为两类.一类是投影法(即降维法);另一类是正则化法.降维法是把右端向量b投影到A的极大线性无关列所张成的子空间中求解.数值相关性理论为其实际运用奠定了基础.降维法解病态线性方程组的     

南京大学1981年研究生入学考试试题(三小时)

1.给定线性方程组Ax=b,其中A为m×n阶实矩阵,b为m维常向量,x为n维待定向量.试证明方程组对任意的b都最多只有一个解的充分必要条件为rank(A)=n,这时存在有n×m阶的左逆A,使BA=I_n.(18分)     

分段线性规划算法的一个注记

求解分段线性规划问题inf S(x) s.t.Ax≤b 0≤x≤(?) (1)其中(?)=((?)_1,(?)_2,…,(?)_n)及 b=(b_1,b_2,…,b_m)~T 是已知向量,A 是已知的(m,n)矩阵,元素为 α_(ij)。目标函数 s(x)是分段线性函数。即对[0,(?)_j)(j=1,2,…,n)存在分划0=x_j~(0)相似文献   

关于 P.Gács 和 L.Lovász 的一个引理及其推广

文献[1]对哈奇安算法给出了完整的证明.本文首先指出[1]中引理3的证明过程中存在的问题并重新给出了证明,然后在新结果的基础上作了推广。最后给出一个改进哈奇安算法的实用结果。研究由线性规划问题导出的不等式系统:及其相应的扰动系统:Ax相似文献   

关于求解最小二乘问题的SSOR迭代矩阵谱半径极值性质的研究

§1.引言 假设A为大型稀疏m×n实矩阵(m>n),且 rank(A)=n,在实用中,常常需要求解 AX=b,(1.1)其中b为给定的m维实向量. 求(1.1)的最小欧氏范数最小二乘解等价于求解 r Ax=b,A~Tr=0,(1.2)     

带框形约束的线性规划问题的鞍点法

根据作者最近提出的求解线性规划问题的鞍点法[3],本文对带框形约束的问题 min c~Tx, s,t A_x=b, l≤x≤h,给出简单的迭代公式.该法的主要优点是它的强收敛性和它的迭代公式非常容易实现.     

Ax=b 在 M-阵和 S-阵类中的反问题

引言对给定的 n 维实向量 x 和 b,欲求某类 n 阶实矩阵 A,使满足 Ax=b,称为线性方程组Ax=b 的反问题.这种问题的实际背景来自控制系统的绝对稳定性.文[2]讨论了上述反问题在正定阵、正交阵等类中有解的条件.本文将研究这种反问题在 M-阵类和 S-阵类中有解的条件.我们利用这两类矩阵的分块判定法,得到了一些充要条件,使问题完满解决.     

求解一类广义线性规划的分裂算法

1　引　　言我们知道,描述常义线性规划问题的数学模型为:mincTxs.tAx=bx≥0　　在经济问题中,线性规划中的向量c往往表示为价格,而在许多实际规划问题中价格向量c往往会在一定范围内扰动.这时,我们可以考虑这样一类广义线性规划问题:minx{maxy∈YyTx}s.tAx=b　x∈X(1)其中,A∈Rm×n,b∈Rm,X={x∈Rn|x≥0},Y是Rn中的一个凸闭子集.有关广义线性规划问题的求解,何在文献[1]中作过一些讨论.我们通过对线性约束Ax=b引入乘子可得到广义线性规划问题(1)定义在X×Y×Rm上的Lagrange函数为:L(x,y,η)=yTx-ηT(Ax-b)(2)　　如果x*是(1)式的…     

非线性规划中一个梯度投影法的收敛性质

我们考虑非线性规划问题(P)■f(x),其中R={x|Ax=a,Bx≤b},A是p×n矩阵,其秩为p,B是q×n矩阵,x∈E~n,a∈E~p,b∈E~q,f(x)∈C~1.我们以R~*表示(P)的最优解集合,并假定R非空.最近,M.S.Bazaraa与J.J.Goode     

USSOR迭代方法的收敛和发散区域

1 引言 对线性方程组 Ax=b, (1.1)这里A∈C~(n×n)是一个具有非零对角元的非奇异复矩阵,b∈C~n为n维向量,我们考虑A的如下分裂: A=D(I-L-U), (1.2)这里D=diag(A),L和U是D~(-1)A的严格下和严格上三角部分,表示单位矩阵. 不对称的逐次超松驰迭代方法(USSOR)[7]是按如下格式产生的迭代:     

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

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

关于线性代数方程 Ax=b 的一类反问题

<正> 湖南大学李森林教授在研究一类直接控制系统的绝对稳定性的充要条件时提出了一个关于线性代数方程的反问题(以下简称反问题 I):已知 x,b 是非零 n 维向量,x~Tb>0,则一定存在一个对称正定矩阵 A 满足方程Ax=b.(1)李森林教授在[1]中获得了上述反问题 I 的一个特解,本文就这一类反问题给出了解A 的存在性证明,给出了 A 的几种构造方法,并导出了 A 阵的通解表达式.本文中除特别声明外,一律假设非零的 n 维向量 x,b 线性无关,若线性相关则其解是显然的,无需讨论.     

一类直接控制系统绝对稳定的充分必要条件

设 dx/dt=Ax+bf(σ),σ=c~Tx (1)其中 A 为 n 阶实的常方阵,A~T=A(T 表示转置)A 的特征根λ(A)<0;b=(b_1,b_2,…,b_n)~T,c=(c_1,c_2,…,c_n)~T 均为 n 维实的常向量;f(σ)为满足条件σf(σ)>0(σ0),f(0)=0的任意连续函数。若对满足条件的任意函数,f(σ),系统(1)的零解均为全局渐近稳定的,则称系统(1)为绝对稳定的。本文获得的主要结果是:若 A~T=A,且 b 与 c 中至少有一个为方阵 A 的特征向量,则下列两条件(i)A 的特征值均为负数,且 c~Tb≤0;(ii)广义特征方程d_et(A+μbc~T-λE_n)=0 (2)(E_n 为 n 阶单位方阵)的特征根对任μ≥0均具有负实部。均为系统(1)绝对稳定的充分必要条件。     

解病态线性方程组的一个新算法及其解精度的估计

§1.算法的建立为简单计,本文讨论的问题为 Ax=b, (1)其中,A是n阶非奇异实方阵,b是已知的n维向量。定理1.设(1)中的b为非零向量,n阶非异方阵H使得Hb=se_n,其中s为一非零常数,e_n=(0,…,0,1)~T。设HA=LQ,L为下三角阵,Q为直交阵,则Q~T的第n列平行于解向量x。证。记Q~T=(q_1,q_2,…,q_n),L阵的第n个对角元为l_(nn),则由HA=LQ及