高引民， 陳建斌

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

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

高引民， 陳建斌

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

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

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

0 引 言

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

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

1 定義及引理

對(duì)于線性規(guī)劃問(wèn)題(LP)

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

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

s.t.

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

定義4 若0

定義5 若0

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

引理1 對(duì)于線性方程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)， 且線性無(wú)關(guān).

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

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

s.t.

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

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

2 基本定理

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

證畢.

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

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

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

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

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

證畢.

由定義1可知：

定理3xj0為L(zhǎng)P的非有效變量的充要條件是xj0為L(zhǎng)P的準(zhǔn)自由變量.

定理4 若xj0為L(zhǎng)P的非有效變量，Li0為L(zhǎng)P的非有效約束方程的必要條件是ai0j0≠0.

3 判別定理

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

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

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

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

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

maxZ=x1+2x2+4x3

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

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

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

s.t.

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

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

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

若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) 必要性. 設(shè)點(diǎn)X0為僅受限于約束條件li0=∑ai0jxj-bi0的可行解， 依據(jù)定理3可得出X0為線性規(guī)劃模型

s.t.

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

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

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

證畢.

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

定理8[9]若li=∑aijxj-bi為L(zhǎng)P的有效約束條件， 則li=∑aijxj-bi上至少有n-m個(gè)基本可行解.

推論3 若原線性規(guī)劃可行域D的維數(shù)dim(D)=n-m，li0=∑ai0jxj-bi0約束條件上的基本可行解的個(gè)數(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為L(zhǎng)P的有效變量及l(fā)i=∑aijxj-bi為L(zhǎng)P的有效約束條件的充要條件是dim(Li)=n-m-1.

推論5Kj0={Xk∶Xk∈K,xj0=0}， 若μKj0≤n-m-1， 則xj0為L(zhǎng)P的非有效變量.

4 結(jié) 語(yǔ)

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

[1] 胡艷杰， 黃思明， Adren N， 等. 對(duì)偶性在線性規(guī)劃預(yù)處理中的應(yīng)用分析[J]. 中國(guó)管理科學(xué)， 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]. 運(yùn)籌學(xué)學(xué)報(bào)， 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]. 西北大學(xué)學(xué)報(bào)(自然科學(xué)版)， 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] 楊歡， 陶鳳玲， 李若東， 等. “準(zhǔn)最優(yōu)基”程序?qū)崿F(xiàn)與應(yīng)用探討[J]. 數(shù)學(xué)實(shí)踐與認(rèn)識(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ī)劃的投影動(dòng)態(tài)方法[J]. 南京師大學(xué)報(bào)(自然科學(xué)版)， 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ù)學(xué)雜志， 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ī)劃界面算法的高效實(shí)現(xiàn)” [J]. 運(yùn)籌學(xué)學(xué)報(bào)， 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ī)劃問(wèn)題非有效約束條件性質(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]. 太原理工大學(xué)學(xué)報(bào)， 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

國(guó)家自然科學(xué)基金資助項(xiàng)目(71572015)

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

O222

A

10.3969/j.issn.1673-3193.2017.03.008