線性規(guī)劃問題非有效變量判別定理的研究*

高引民， 陳建斌

(北京聯(lián)合大學 商務學院， 北京 100025)

線性規(guī)劃問題非有效變量判別定理的研究*

高引民， 陳建斌

(北京聯(lián)合大學 商務學院， 北京 100025)

為完善線性規(guī)劃模型的基本理論， 通過分析線性規(guī)劃模型中變量與約束條件的關(guān)系， 非有效變量與最優(yōu)解的關(guān)系， 對線性規(guī)劃模型中非有效變量和有效變量的特性進行了理論探討， 獲得了識別非有效變量的一些判定定理， 為構(gòu)造識別非有效變量的方法提供了理論基礎(chǔ).

線性規(guī)劃； 可行域； 非有效變量； 非有效約束條件

0 引 言

為迎接多變的市場帶來的挑戰(zhàn)， 企業(yè)越來越依靠對信息的占有， 對企業(yè)整體狀況的把握， 以及對企業(yè)資源的優(yōu)化配置， 這都需要借助線性規(guī)劃來做出最優(yōu)的決策， 其在經(jīng)濟、 工程、 軍事和農(nóng)業(yè)等方面有著極為廣泛的應用. 近年來， 線性規(guī)劃的理論和求解方法無論從廣度和深度都取得了重大的進展， 為線性規(guī)劃的應用及進一步發(fā)展奠定了基礎(chǔ). 科學技術(shù)與計算機技術(shù)的發(fā)展將為線性規(guī)劃的應用提供了更好的環(huán)境， 同時也對其提出了新的要求.

在將具體應用的實際問題需要轉(zhuǎn)化為利用線性規(guī)劃模型來解決的過程中， 由于具體問題的復雜性可能使不具有有效約束的條件和決策變量都被引進來， 這就造成了線性規(guī)劃問題模型中的約束條件的數(shù)量大大增加， 而整個求解線性規(guī)劃問題的工作量和復雜度都與線性規(guī)劃的約束規(guī)模相關(guān). 文獻[1]從線性規(guī)劃對偶問題的角度出發(fā)， 對應用對偶性進行數(shù)據(jù)預處理的方法做了總結(jié)， 并研究了基于對偶性理論的方法在預處理中的效用， 尤其是針對大規(guī)模線性規(guī)劃問題. 線性規(guī)劃的研究直接推動了其他數(shù)學規(guī)劃問題包括整數(shù)規(guī)劃、 隨機規(guī)劃和非線性規(guī)劃的算法研究[2]. 通過求解線性規(guī)劃問題的基本解來逼近最優(yōu)解是求解線性規(guī)劃問題的方法體系中非常重要的一類方法， 稱為基點上迭代逼近最優(yōu)解方法， 它包括線性規(guī)劃問題單純形法， 對偶單純形法， 原始-對偶單純形法， 松弛法等， 將攝動算法和虧基原始單純形算法相結(jié)合， 采用最陡邊的列主元規(guī)則， 可以充分發(fā)揮這兩種算法的優(yōu)勢[3-8]. 而識別線性規(guī)劃模型中非有效約束方程及非最有效約束方程的理論[9-10]， 對于縮小原模型的規(guī)模、 降低原模形的復雜性、 求解線性規(guī)劃都是有益的. 同樣， 識別非有效變量的理論及變量與約束條件的關(guān)系理論都是有價值的. 本文對線性規(guī)劃模型中的變量性質(zhì)進行研究， 分析了變量與約束條件的關(guān)系， 并對非有效變量與變量及變量與最優(yōu)解的關(guān)系進行了分析與探討.

1 定義及引理

對于線性規(guī)劃問題(LP)

顯然，LP-1變量的個數(shù)為n-1， 約束條件的個數(shù)為m-1.

定義2 對LP做等價變換， 不失一般性， 式(1) 變?yōu)?/p>

s.t.

定義3 在定義2中， 若去掉xj0≥0條件， 而不影響D， 則稱xj0為D的準自由變量.

定義4 若0

定義5 若0

根據(jù)仿射集合的有關(guān)理論可得出以下引理.

引理1 對于線性方程aTX=f，a=(a1,a2,…,an-m)T，X=(x1,x2,…,xn-m)T， 由Xj∈Rn-m，j=(1,2,…,n-m) 唯一確定的充分必要條件是aTXj=f， (j=1,2,…,n-m)， 且線性無關(guān).

引理3[9]?Xj∈P(X0—δ)(j=1,2,…,n-m) 且X1，X2，…，Xn-m線性無關(guān).

引理4[9]如下線性規(guī)劃問題

s.t.

的最優(yōu)值W*滿足

引理5 可行解域D的維數(shù)dim(D)=n-m的充分必要條件為LP可行域D存在內(nèi)點.

2 基本定理

證明由定義1可知顯然成立.

證畢.

定理2 若X0僅受限于約束條件li0=∑ai0jxj-bi0的可行解， 則

1)X0不是LP的基本可行解;

2)X0為D-1的內(nèi)點.

證明1) 可直接由基本可行解的定義及定義4得出.

2) 可由可行解域的內(nèi)點定義及定義4得出.

證畢.

由定義1可知：

定理3xj0為LP的非有效變量的充要條件是xj0為LP的準自由變量.

定理4 若xj0為LP的非有效變量，Li0為LP的非有效約束方程的必要條件是ai0j0≠0.

3 判別定理

定理5 若在li0=∑ai0jxj-bi0上存在非退化的基本可行解， 則li0=∑ai0jxj-bi0一定為有效約束條件，xn-m+i0為LP的有效變量.

證明假設點X0為約束條件li0=∑ai0j·xj-bi0上非退化的基本可行解， 由線性規(guī)劃問題中非退化的基本可行解的定義可知， 如果在原線性規(guī)劃問題中去掉確定X0的一個約束方程， 則X0就不成為原線性規(guī)劃問題的基本可行解. 即有μK≠μK-1成立， 再根據(jù)定理1可得約束條件li0=∑ai0jxj-bi0為有效約束條件， 證畢.

推論1 若xn-m+i0=0，li0=∑ai0jxj-bi0上有基本可行解， 則xn-m+i0成為原線性規(guī)劃問題的非有效變量的必要條件是li0=∑ai0jxj-bi0上的基本可行解都為原線性規(guī)劃問題的退化可行解.

由此， 我們可得出線性規(guī)劃問題存在退化解的充分條件是該線性規(guī)劃問題存在非有效變量. 由于退化解的存在， 它使得求解線性規(guī)劃問題的方法復雜化. 因此， 在線性規(guī)劃問題中能識別并刪掉非有效變量， 不僅減少了求解線性規(guī)劃問題的計算量， 而且能使解線性規(guī)劃問題的復雜性簡化.

推論1的逆命題不成立. 如考慮如下線性規(guī)劃問題

maxZ=x1+2x2+4x3

不難分析驗證：X1=(0,1,1)，X2= (1,0,1)，X3=(1,1,0)為線性規(guī)劃問題3個退化基本可行解， 都滿足約束條件x1+x2+x3=2， 而且滿足約束條件x1+x2+x3=2的基本可行解僅有3個， 但對應該約束條件的松弛變量為該線性規(guī)劃問題的有效變量, 如圖 1 所示.

圖 1 可行域的圖解示意圖Fig.1 The graphical diagram of the feasible region

定理6xn-m+i0為LP非有效變量，li0=∑ai0jxj-bi0為LP的非有效約束條件的充分必要條件是如下線性規(guī)劃

s.t.

有最優(yōu)值w*， 且有w*≤bi0成立.

證明1) 必要性. 依據(jù)定義1可得D1≌D， 再根據(jù)引理4可證.

2) 充分性. 由于w*0， 即xn-m+i0為LP準自由變量， 由定理4和定理5可知xn-m+i0為LP非有效變量，li0=∑ai0jxj-bi0為LP的非有效約束條件.

若w*=bi0， 則必有l(wèi)i0=∑ai0jxj-bi0=0和D相交， 也有線性規(guī)劃

s.t.

的最優(yōu)值w*=bi0, 所以D1≌D， 證畢.

定理7li0=∑ai0jxj-bi0成為原線性規(guī)劃的非有效約束條件的充分必要條件是不存在僅受限于li0=∑ai0jxj-bi0約束條件的可行解.

證明1) 必要性. 設點X0為僅受限于約束條件li0=∑ai0jxj-bi0的可行解， 依據(jù)定理3可得出X0為線性規(guī)劃模型

s.t.

(i=1,2,…,m,i≠i0)

的一個內(nèi)點. 又因為w(X0)=bi0， 則有w*>bi0成立， 依據(jù)定理2可得出li0=∑ai0jxj-bi0不能成為原線性規(guī)劃的非有效約束條件， 與定理假設矛盾.

2)充分性. 由條件可知， 在li0上的任一可行解都可由其余的某些約束方程加以限制， 故約束方程li0失去了真正約束的作用， 由定義1可知li0=∑ai0jxj-bi0為LP的非有效約束條件.

證畢.

推論2 效約束條件li0=∑ai0jxj-bi0為LP的有效約束的充分必要條件是有僅受限于li0=∑ai0jxj-bi0約束條件的可行解存在.

定理8[9]若li=∑aijxj-bi為LP的有效約束條件， 則li=∑aijxj-bi上至少有n-m個基本可行解.

推論3 若原線性規(guī)劃可行域D的維數(shù)dim(D)=n-m，li0=∑ai0jxj-bi0約束條件上的基本可行解的個數(shù)滿足μKn-m+i0≤n-m-1， 則變量xn-m+i0為原線性規(guī)劃的非有效變量，li0=∑ai0jxj-bi0為原線性規(guī)劃的非有效約束.

推論4 令Li={X|li(X)=0,X∈D}，xn-m+i為LP的有效變量及l(fā)i=∑aijxj-bi為LP的有效約束條件的充要條件是dim(Li)=n-m-1.

推論5Kj0={Xk∶Xk∈K,xj0=0}， 若μKj0≤n-m-1， 則xj0為LP的非有效變量.

4 結(jié) 語

本文得出線性規(guī)劃問題存在退化解的充分條件是該線性規(guī)劃問題存在非有效變量， 線性規(guī)劃問題非有效變量和非有效約束條件同時存在. 由于退化解的存在使得求解線性規(guī)劃問題的方法復雜化， 因此， 在線性規(guī)劃問題中能識別并刪掉非有效變量非有效約束條件使得原模型降維數(shù)， 不僅減少了求解線性規(guī)劃問題的計算量， 而且能使解線性規(guī)劃問題的復雜性簡化. 對線性規(guī)劃問題中非有效變量的研究可為尋找和構(gòu)造新的求解線性規(guī)劃問題的算法提供一定的理論基礎(chǔ)和思路. 另外， 可結(jié)合線性規(guī)劃偶理論對非最優(yōu)變量的識別做進一步研究.

[1] 胡艷杰， 黃思明， Adren N， 等. 對偶性在線性規(guī)劃預處理中的應用分析[J]. 中國管理科學， 2016， 24(12)： 117-126.

Hu Yanjie, Huang Siming, Adren N, et al. Analysis of using duality for presolving in linear programming[J]. Chinese Journal of Management Science， 2016， 24(12)： 117-126. (in Chinese)

[2] 戴彧虹， 劉新為. 線性與非線性規(guī)劃算法與理論[J]. 運籌學學報， 2014， 18(1)： 69-92.

Dai Yuhong， Liu Xinwei. Advances in iinear and nonlinear programming[J]. Operations Research Tansactions， 2014， 18(1)： 69-92. (in Chinese)

[3] 敖特根. 單純形法的產(chǎn)生與發(fā)展探析[J]. 西北大學學報(自然科學版)， 2012， 42(5)： 861-864.

Ao Tegen. Analysis of the formation and development of the simplex method[J]. Journal of Northwest University (Natural Science Edition)， 2012， 42(5)： 861-864. (in Chinese)

[4] Pan P Q. A dual projective pivot algorithm for linear programming[J]. Computational Optimization and Applications， 2004， 29(3)： 333-344.

[5] 楊歡， 陶鳳玲， 李若東， 等. “準最優(yōu)基”程序?qū)崿F(xiàn)與應用探討[J]. 數(shù)學實踐與認識， 2014， 44(10)： 219-227.

Yang Huan， Tao Fengling， Li Ruodong， et al. Program realization of (quasi-optimal basis) and its application discussion[J]. Mathematics in Practice and Theory， 2014， 44(10)： 219-227. (in Chinese)

[6] 孫黎明. 一種求解線性規(guī)劃的投影動態(tài)方法[J]. 南京師大學報(自然科學版)， 2015， 38(4)： 8-13.

Sun Liming. A projective dynamic method for solving linear programming[J]. Journal of Nanjing Normal University (Natural Science Edition)， 2015， 38(4)： 8-13. (in Chinese)

[7] 孟香惠， 施保昌. 線性規(guī)劃單純形法主元規(guī)則的幾何分析[J]. 數(shù)學雜志， 2013， 33(2)： 373-380.

Meng Xianghui， Shi Baochang. Geometry analysis of pivot rules in simplex method for linear programming[J]. Journal of Mathematics， 2013， 33(2)： 373-380. (in Chinese)

[8] 潘平奇. 關(guān)于“線性規(guī)劃界面算法的高效實現(xiàn)” [J]. 運籌學學報， 2015， 19(3)： 78-84.

Pan Pingqi. On “an efficient implementation of the face algorithm for linear programming”[J]. Operations Research Tansactions， 2015， 19(3)： 78-84. (in Chinese)

[9] 高引民， 甘仞初. 線性規(guī)劃問題非有效約束條件性質(zhì)研究[J]. 系統(tǒng)工程與電子技術(shù)， 2005， 27(6)： 1041-1043.

Gao Yinmin， Gan Renchu. Characteristics of ineffective constraints in linear programming[J]. Systems Engineering and Electronics， 2005， 27(6)： 1041-1043. (in Chinese)

[10] 高引民， 甘仞初， 吳立志. 線性規(guī)劃非最優(yōu)有效約束方程判別定理研究[J]. 太原理工大學學報， 2004， 35(3)： 371-373.

Gao Yinmin， Gan Renchu， Wu Lizhi. The study of characteristics of ineffective constraints in linear programming[J]. Journal of Taiyuan University of Technology， 2004， 35(3)： 371-373. (in Chinese)

StudyofCriteriaofLinearProgrammingwithIneffectiveVariables

GAO Yin-min, CHEN Jian-bin

(College of Business, Beijing Union University, Beijing 100025, China)

In order to improve the characteristics of the ineffective variables and ineffective constraints, the relations between the ineffective variables and ineffective constraints were discussed. It was proved that the theorems of identifying ineffective variables and ineffective constraints which are the theoretical base of the method of identifying and eliminating further ineffective variables and ineffective constraints in solving linear programming.

linear programming; feasible region; ineffective variables; ineffective constraint conditions

1673-3193(2017)03-0291-04

2016-08-22

國家自然科學基金資助項目(71572015)

高引民(1960-)， 男， 教授， 博士， 主要從事運籌學、 信息系統(tǒng)與企業(yè)信息化的研究.

O222

A

10.3969/j.issn.1673-3193.2017.03.008