线性规划标准型和整数线性规划最优解的两个注记

孟香惠,施保昌,胡新生

(1.深圳广播电视大学学习中心,广东 深圳518001;2.华中科技大学数学与统计学院,湖北 武汉430074;3.深圳广播电视大学教育技术中心,广东 深圳518001)

1.引言

线性规划是运筹学、决策科学和管理科学最重要的基础,现已成为人们合理利用、调配有限资源做出最佳决策的有力工具[1−3].除了生产计划安排和运输问题等经典的应用领域,因其算法简单、高效,适于处理大规模科学与工程问题,线性规划还在现今的机器学习等热点研究领域发挥着重要作用[4−5].线性规划的基本算法: 单纯形法可以被看成是线性方程组的消去法的变形或推广形式,它以其简单、通用及应用广泛等特性而著称于世.在线性规划的实际应用中,如生产计划安排、物资运输与调度、工作指派等对应的线性规划问题中,其所涉及的全部或部分决策变量往往有整数性的要求,这就得到了所谓整数线性规划问题[6−7].整数性要求使得常用的解析方法不便用于整数规划问题,因而整数规划的分析和求解更为困难[6].结合松弛法的思想,单纯形法和对偶单纯形法等线性规划算法可以用于变量有整数性要求的整数线性规划问题,从而进一步扩展了线性规划的应用范围.

我们知道,单纯形法是基于线性规划标准型的.通常,在有关线性规划的教科书和参考文献里介绍标准型时,都会“不失一般性”地对其作些假设,如“约束系数矩阵行满秩”.另外,谈到整数线性规划时,又会说,其最优解一般不能通过对松弛问题的最优解进行“圆整”而得到.仔细考量,人们会提出这样的问题: 无约束和仅有非负约束的线性规划问题分别有怎样的性质? 整数线性规划的松弛问题的最优解与原整数线性规划的最优解相距远吗? 这些问题的解答对学习、理解和掌握线性规划理论和方法很有意义,然而,教科书中并没有对这些问题给出清晰或明确的解答.本文通过线性规划标准型的假设和整数线性规划最优解的两个注记,对这些问题给出作者的见解.文中研究了线性规划标准型的基本假设所蕴含的一些性质,并探讨了整数线性规划最优解和其松弛问题最优解的关系,所得结果有助于理解和掌握线性规划的基本理论和方法.

2.关于线性规划标准型的假设的注记

考虑如下标准线性规划问题：

其中A=(p1,p2,··· ,pn)∈Rm×n,b ∈Rm,c,x ∈Rn.

不失一般性，教科书里大都作如下假设：

(H1) (i) Rank(A) =m

实际上,除这一基本假设外,还有另外一些隐含假设在教科书里往往没有提及,如：

(H2)m>0;pj≠0,∀j:1≤j ≤n.

m=0 对应于仅有非负约束的情形;而当pj=0 时,变量xj不会出现在等式约束中,故其仅有非负的限制.这两种情形有一定的联系.另外,还可考虑类似的问题: 无约束和仅有等式约束的情形,这两种情况有内在联系,文献中也鲜有提及.下面就这四种情况分述之.

1) 无约束线性规划问题：X=Rn.

结论2.1(i) 若c=0，则任意x ∈Rn均为问题(2.1)的最优解；

(ii) 若c≠0，则问题(2.1)有无界解(无最优解).

证 (i) 结论显然成立.(ii) 若c≠ 0，取=θc,θ >0，则有cT=θ‖c‖2→+∞(θ →+∞),故问题(2.1) 有无界解.证毕.

注2.1若c≠ 0,取=−θc,θ >0,还可得出cT=−θ‖c‖2→−∞(θ →+∞),所以,问题(2.1)的目标函数亦无下界.从几何上看,若c≠0,则目标函数z=cTx的等值面在Rn空间中可以沿着c或−c的方向任意移动,因而函数值既无上界,也无下界.

2) 仅有非负约束的线性规划问题：X={x ∈Rn|x ≥0}.

结论2.2(i) 若c ≤0,则x=0 为问题(2.1)的最优解；

(ii) 若存在cl >0,则问题(2.1)有无界解.

证(i) 显然,cTx ≤cT0 = 0,∀x ≥0,故x= 0 为问题(2.1)的最优解；(ii)不妨设c1>0,取=(θ,0,··· ,0)T,θ >0,则有cT=θc1→+∞(θ →+∞),故问题(2.1) 有无界解.证毕.

3) 仅有等式约束的线性规划问题：X={x ∈Rn|Ax=b}.

不妨设Rank(A) =m

于是,由结论(2.1)有

结论2.3(i) 若σN=0，则任意xN ∈Rn−m均为问题(2.2)的最优解,即Ax=b的任意解均为问题(2.1)的最优解；

(ii) 若σN≠0，则问题(2.2)有无界解,从而问题(2.1)有无界解.

4) 问题(2.1)的系数矩阵里,存在j,使得pj=0(1≤j ≤n)的情形.

不妨设pn=0,则问题(2.1)变为：

结论2.4(i) 若=∅,则问题(2.1)无可行解；

(a) 若cn >0,则问题(2.1)有无界解；

(b) 若cn ≤0,则问题(2.1)化为如下降维(n −1维)问题：

证(i) 显然.

因此,x∗= (,0)∈X为问题(2.1)的最优解.若问题(2.4)有无界解，则由从而推知问题(2.1)亦有无界解.证毕.

3.关于整数线性规划最优解的注记

变量的“离散”特性使得整数(线性)规划的分析和求解无法直接运用解析方法.事实上,整数规划往往还会呈现出高度的非线性性：假设某个变量x取值为a1,a2,··· ,am，则等价于(x −a1)(x −a2)···(x −am) = 0.这是一个由m阶多项式构成的非线性等式约束,m越大，其非线性程度越高.

松弛方法是求解整数规划的基本方法之一,其主要思想是通过求解移除整数性要求的“松弛”问题,然后利用最优解的信息,缩小松弛问题的可行域,但又不丢失原问题的整数可行解.逐步施行这一过程,直到某一个松弛问题的最优解满足整数性要求,从而得到原整数规划问题的最优解.实际求解时,一般采用数值计算.源于数值误差的影响,或实际计算的需要,自然会提出这样的问题：是否可以通过对松弛问题的最优解进行“圆整”得到整数规划的近似最优解? 换句话说,整数规划的(近似)最优解是否在松弛问题的最优解附近？这也是在讲授整数规划时会常常提及的问题.

这一问题的答案是否定的！一般地,教科书上说：松弛问题的最优解化整后不一定是整数规划的可行解,或虽是可行解,但不一定是最优解,并可举例说明[1].松弛问题的最优解化整后是不是可以得到整数规划的近似最优解? 尚未见教科书上讨论过这一问题.事实上,可以构造出这样的例子,松弛最优解或化整后的解可以远离整数规划的最优解! 例3.1是我们构造出来的一族二维例子.其构造过程如下：

在第一象限,先做一个由两个不等式约束构成的“狭长”的可行域X,目的是让整数最优解和松弛最优解分别位于X中的两侧,即尽量“远离”.如图3.1所示,让Q3(7.5,2.5)为松弛最优解,而让Q∗(1,3)为整数最优解.这时,可以让第一个约束通过Q3,并且在Q∗和(2,3)之间穿过,通过点Q1(0,3+ε).由Q∗和Q1确定出第一个不等式约束.再由Q∗可行,而(2,3)不可行,定出1/13≤ε<2/11.第二个不等式由通过Q3及x1轴正向的直线构成,并与第一个约束在第一象限构成凸多边形即可,这里选择x1+x2≤10.最后,为使Q3(7.5,2.5)和Q∗(1,3)分别为松弛最优解和整数最优解,由图解法,让目标函数的梯度c(系数向量)与第一个约束的外法矢量接近平行(见图3.1),使得Q∗(1,3)是通过Q3的目标函数等值线沿着目标函数的负梯度方向−c移动时碰到的第一个整数可行点,即所求整数规划的最优解.于是得到z= (2+λ)x1+25x2,并且λ>(10ε −1)/3.最终,得到例3.1.

图3.1 问题3.1的松弛问题的可行域、顶点及目标函数等值线

例3.1整数规划的最优解与其松弛问题的最优解“相距甚远”的例子.

其中λ>(10ε −1)/3,1/13≤ε<2/11.

由上述讨论知,例3.1的松弛问题(即不考虑整数性要求)的最优解为Q3(7.5,2.5),而例3.1(整数规划)的最优解为Q∗(1,3),它们的距离为√可谓相距甚远.而对松弛最优解为Q3(7.5,2.5)圆整得到其附近的整数点(7,2),(8,2),(7,3)和(8,3),前两个是例3.1的可行解,后两个则不可行.它们都“远离”最优解Q∗(1,3).为了能让读者看到具体的例子,特别地,在例3.1中取一组特定的参数,得到例3.2.

例3.2例3.1的特例(λ=1,ε=0.1).

利用以上方法,我们还可以构造出松弛最优解与整数最优解相距更远的例子.例3.3是例3.1的扩展,其中d为正整数.与例3.1类似,让Q3(d+0.5,2.5)为松弛最优解,而让Q∗(1,3)仍为整数最优解(参见图3.2).此时,它们的距离为√由此可见,当d充分大时,Q3与Q∗的距离充分远! 读者可以在例3.3中取具体的参数,得到所需的具体例子.

图3.2 问题3.3的松弛问题的可行域、顶点及目标函数等值线

例3.3例3.1的扩展(d>2).

其中1/(2d −1)≤ε<2/(2d −3),0<ε′ ≪1.