杨春艳 (银川大学数学系,宁夏 银川 750105)

雍龙泉 (陕西理工学院数学系,陕西 汉中 723001)

线性互补问题测试算例的一个构造方法

杨春艳 (银川大学数学系,宁夏 银川 750105)

雍龙泉 (陕西理工学院数学系,陕西 汉中 723001)

建立了线性互补问题测试函数的一个构造方法。给出了一般线性互补问题、单调线性互补问题以及反对称矩阵线性互补问题测试算例的构造方法。结果表明，建立的构造方法是有效的。这些结果对线性互补问题的研究具有重要的意义，进而可以利用该方法来构造一系列的线性互补做测试算例，这在很大程度上丰富了线性互补问题的数值试验。

线性互补问题; 测试算例; 单调线性互补; 混合整数线性规划

线性互补问题就是求一个向量x∈Rn，使得：

x≥0Mx+q≥0xT(Mx+q)=0

线性互补问题简记为LCP(q,M)。求解线性互补问题的算法有很多，经典的有Lemke算法。近年来出现的一些具有多项式复杂性的算法，诸如投影法、内点法、非光滑牛顿法、光滑牛顿法等已成为目前研究的热点[1-5]。文献[6]中把线性互补问题转化为一个混合整数线性规划，通过求解混合整数线性规划得到原问题的最优解，该方法更实用，且更容易上机操作，因此也可以作为求解线性互补问题的一个实用方法。

下面，笔者就线性互补问题测试算例的一个构造方法做了研究，给出了一般线性互补问题、单调线性互补问题以及反对称矩阵线性互补问题测试算例的构造方法。

1 一般线性互补问题

随机产生矩阵M∈Rn×n,随机生成非负向量x∈Rn×1,令q=-Mx,因此就得到矩阵M和向量q,由于x≥0,Mx+q=0，故xT(Mx+q)=0,因此相应的线性互补问题LCP(q,M)的解就是x。……