高引民， 陳建斌

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

基于逐步降階的線性規(guī)劃的單純形算法

高引民， 陳建斌

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

為完善線性規(guī)劃約束條件方面的基本理論， 研究了一種高效的求解線性規(guī)劃問(wèn)題的算法. 以區(qū)分最優(yōu)松約束條件和最優(yōu)緊約束條件為主線， 利用線性規(guī)劃， 線性代數(shù)等數(shù)學(xué)理論， 進(jìn)行分析， 并通過(guò)大量的數(shù)據(jù)實(shí)驗(yàn)進(jìn)行驗(yàn)證. 從理論上獲得了最優(yōu)緊約束條件一些性質(zhì)及識(shí)別最優(yōu)松約束條件的定理， 提供了一種新的單純形算法. 數(shù)據(jù)試驗(yàn)和理論上表明， 在求解大規(guī)模解線性規(guī)劃問(wèn)題時(shí)， 利用新的求解算法， 使得模型逐步降階， 能達(dá)到求解的高效率.

線性規(guī)劃； 單純形算法； 約束條件； 最優(yōu)緊約束條件

近年來(lái)， 信息科學(xué)技術(shù)的發(fā)展、 互聯(lián)網(wǎng)的廣泛應(yīng)用， 推動(dòng)了經(jīng)濟(jì)全球化的進(jìn)程. 企業(yè)信息化改變了企業(yè)管理的模式. 對(duì)企業(yè)經(jīng)營(yíng)資源進(jìn)行優(yōu)化, 需要借助運(yùn)籌學(xué)、 大數(shù)據(jù)技術(shù)等方法來(lái)解決企業(yè)的生產(chǎn)經(jīng)營(yíng)的各類(lèi)優(yōu)化問(wèn)題,有大量具體應(yīng)用的實(shí)際問(wèn)題需要利用線性規(guī)劃模型來(lái)解決. 實(shí)際問(wèn)題的復(fù)雜性導(dǎo)致線性規(guī)劃問(wèn)題的規(guī)模不斷增大， 而計(jì)算求解線性規(guī)劃問(wèn)題過(guò)程中的工作量和復(fù)雜度都與線性規(guī)劃問(wèn)題的規(guī)模大小有關(guān)， 尤其對(duì)大規(guī)模線性規(guī)劃問(wèn)題. 縮小原模型的規(guī)模,降低原模形的復(fù)雜性,有利于線性規(guī)劃的求解[1，4]. 要達(dá)到這樣的目的,在線性規(guī)劃的理論和算法方面應(yīng)解決以下幾個(gè)問(wèn)題.

1) 對(duì)線性規(guī)劃約束條件的性質(zhì)進(jìn)行研究， 分析約束條件與約束條件的關(guān)系及約束條件與最優(yōu)解的關(guān)系[2].

2) 對(duì)線性規(guī)劃模型中變量的性質(zhì)進(jìn)行研究[3].

3) 以什么方式來(lái)識(shí)別線性規(guī)劃模型中的約束條件及變量的性質(zhì)[3].

4) 什么時(shí)間(建模的過(guò)程， 求解線性規(guī)劃模型前還是求解線性規(guī)劃模型過(guò)程中)來(lái)刪除線性規(guī)劃模型中的一些約束條件及一些變量, 使得線性規(guī)劃模型簡(jiǎn)化.

文獻(xiàn)[1]從線性規(guī)劃對(duì)偶問(wèn)題的角度出發(fā)， 對(duì)應(yīng)用對(duì)偶性進(jìn)行數(shù)據(jù)預(yù)處理的方法做了總結(jié)， 并研究了利用對(duì)偶性理論所產(chǎn)生的方法在預(yù)處理的效用， 尤其對(duì)大規(guī)模線性規(guī)劃問(wèn)題[1]. 線性規(guī)劃的研究直接推動(dòng)了其他數(shù)學(xué)規(guī)劃問(wèn)題包括整數(shù)規(guī)劃、 隨機(jī)規(guī)劃和非線性規(guī)劃的算法研究. 通過(guò)求解線性規(guī)劃問(wèn)題的基本解來(lái)逼近最優(yōu)解是求解線性規(guī)劃問(wèn)題的方法體系中非常重要的一類(lèi)方法， 稱(chēng)這一類(lèi)方法為基點(diǎn)上迭代逼近最優(yōu)解方法， 它包括線性規(guī)劃問(wèn)題單純形法、 對(duì)偶單純形法、 原始-對(duì)偶單純形法， 松弛法， 以及將攝動(dòng)算法和虧基原始單純形算法相結(jié)合的方法， 該方法采用最陡邊的列主元規(guī)則， 以充分發(fā)揮這兩種算法的優(yōu)勢(shì)[4-11]. 同樣識(shí)別非有效變量的理論及變量與約束條件的關(guān)系理論都是有價(jià)值的. 本文主要從理論方面深入地研究最優(yōu)緊約束條件方面的有關(guān)問(wèn)題并提供了一種新的單純形法(DRSM). 數(shù)據(jù)試驗(yàn)和理論上表明， DRSM在求解大規(guī)模解線性規(guī)劃問(wèn)題時(shí)， 利用新的求解算法， 使得模型逐步降階， 能達(dá)到求解的高效率.

1 線性規(guī)劃降階的基本理論

考慮如下線性規(guī)劃問(wèn)題(LP)

s.t.

記A=(aij)m×n,bT=(b1,b2,…,bm),cT=(c1,c2,…,cn),li(X)=∑aij·xj-bi, (i=1,2,…,m),D為L(zhǎng)P的可行解域，D≠φ,hi={X|li(X)=0,X∈D},X*為L(zhǎng)P最優(yōu)解,Z*為L(zhǎng)P的最優(yōu)值. 取i0∈{1,2,…,m}, 在LP中刪掉第i0約束條件， 構(gòu)造線性規(guī)劃問(wèn)題(LP-i0)

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

2) 若D≠D-i0(反證法), 設(shè)

Z(X0)>Z*.

(4)

Z(X0)

(5)

式 (4)和式(5)矛盾. 證畢.

定理 2 給定i0∈{1,2,…,m}, 對(duì)于(LP)構(gòu)造如下線性規(guī)劃問(wèn)題(LPi0)

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

證明 反證法， 若li0=∑ai0j·xj-bi0≤0為L(zhǎng)P的最優(yōu)緊約束條件， 則li0(X*)=0，

定義 2 稱(chēng)模型(6)中l(wèi)i0≤0為(1)的準(zhǔn)最優(yōu)緊約束條件.

則li0≤0 為L(zhǎng)P的最優(yōu)松約束條件.

同理可證明2)成立.

定理 3 說(shuō)明在滿足何條件下可從原線性規(guī)劃模型中刪掉li0=∑ai0j·xj-bi0≤0約束.

2 降階的單純形法(DRSM)

DRSM基本思想是， 以單純形法原理求(LPi0)， 然后， 根據(jù)定理3來(lái)判定約束條件li0≤0的性質(zhì)， 若li0≤0為最優(yōu)松約束條件， 則在原模型中刪掉li0≤0約束條件， 繼續(xù)選準(zhǔn)最優(yōu)緊約束條件， 再求解.其特點(diǎn)有： 解的過(guò)程是降階的(變量數(shù)減少， 約束矩陣的階數(shù)降低)， 簡(jiǎn)便性， 在計(jì)算機(jī)上的易實(shí)現(xiàn)性， 高效性(解的穩(wěn)定性增加， 用時(shí)節(jié)省).

具體步驟如下：

第一階段(選定某個(gè)界面Dl， 先在此界面上求最優(yōu)解)

1) 列出初始可行單純形表.

2) 計(jì)算變量xj對(duì)應(yīng)的檢驗(yàn)數(shù)σj， σk=max(σj|j=1,2,…,n).

3) 若σk≤0， 則停止， 得最優(yōu)解.

4) 若σk>0, 以xk為進(jìn)基變量， 用SM的θ規(guī)則

確定換出基變量為xl.

由此， 選定的界面是Dl={X|X∈D,xl=0}， 下面在此界面上求最優(yōu)解， 并判斷變量xl是否為最優(yōu)變量.

以akl為主元做旋轉(zhuǎn)運(yùn)算(連同目標(biāo)函數(shù))， 將xk與xl對(duì)換位置， 則得新的單純形表.

5) 計(jì)算變量xj對(duì)應(yīng)的檢驗(yàn)數(shù)σj， σk=min(σj|j=1,2,…,n,j≠1).

6) 若σk≤0， 則轉(zhuǎn)9).

7) 若σk>0， 以xk為進(jìn)基變量， 用SM的θ規(guī)則

確定換出基變量為xl1, 以akl1為主元做旋轉(zhuǎn)運(yùn)算(連同目標(biāo)函數(shù))， 將xk與xl1對(duì)換位置， 則得新的單純形表.

8)返回5)繼續(xù)迭代運(yùn)算.

第二階段(判斷Dl界面的特性)

9) 若σ1≤0， 則停止， 得LP的最優(yōu)解. 否則， 可判定xl為最優(yōu)基變量, 轉(zhuǎn)下一步.

10) 若xl為基本變量(非松弛變量)， 返回4)， 以xl為進(jìn)基變量,繼續(xù)迭代運(yùn)算.

11)若xl為松弛變量， 用SM的θ規(guī)則

確定換出基變量為xl2, 以al2l為主元做旋轉(zhuǎn)運(yùn)算(連同目標(biāo)函數(shù))， 則得新的單純形表.

12) 在新的單純形表中刪除第l列及第l2行， n變?yōu)閚-1, m變?yōu)閙-1,使得原線性規(guī)劃模型降階， 返回2).

3 實(shí)例及數(shù)值實(shí)驗(yàn)分析

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

maxZ=2x1+3x2,

計(jì)算最優(yōu)解X*=(2,3), 由定理1可判斷原線性規(guī)劃模型與

maxZ=2x1+3x2,

線性規(guī)劃問(wèn)題最優(yōu)等價(jià).

例 2 數(shù)值實(shí)驗(yàn)分析

為了驗(yàn)證DRSM算法的效率， 應(yīng)用MATLAB語(yǔ)言開(kāi)發(fā)了在Windows環(huán)境下運(yùn)行的DRSM程序及單純形法(SM) 程序， 在具有700MHz,PentiumⅢ處理器，RAM256Mb及WindowsXP的計(jì)算機(jī)平臺(tái)上進(jìn)行數(shù)據(jù)試驗(yàn).

為簡(jiǎn)化起見(jiàn)， 線性規(guī)劃模型為

maxZ=CX,

aij, ci都在區(qū)間[1 000, -1 000]內(nèi)隨機(jī)產(chǎn)生， bj=1.

數(shù)據(jù)試驗(yàn)的結(jié)果如表 1 所示.

表 1 DRSM與SM比較

將SM法和DRSM法對(duì)問(wèn)題的計(jì)算時(shí)間繪成對(duì)比曲線圖如圖 1 所示.

圖 1 SM與DRSM對(duì)問(wèn)題的計(jì)算時(shí)間對(duì)比圖Fig.1 Computing time contrast figure of SM and DRSM

表 1 及圖 1 說(shuō)明隨著線性規(guī)劃問(wèn)題的規(guī)模增大， DRSM計(jì)算效率明顯優(yōu)于SM， 且具有以下優(yōu)點(diǎn)：

1) 由于減少約束條件導(dǎo)致計(jì)算的迭代次數(shù)減少， 有利于計(jì)算結(jié)果精度增加；

2) 同樣問(wèn)題的求解時(shí)間減少；

3) 線性規(guī)劃規(guī)模越大效果越好.

4 結(jié)束語(yǔ)

線性規(guī)劃的基本理論表明： 在求解前或求解過(guò)程中能判斷模型中哪些變量是最優(yōu)基變量， 哪些約束條件為最優(yōu)約束， 刪掉多余的非最有約束和非最有基變量， 只要計(jì)算一個(gè)由這些最優(yōu)約束和基變量構(gòu)成的線性規(guī)劃問(wèn)題， 降階后規(guī)劃模型與原問(wèn)題等價(jià)， 不會(huì)改變問(wèn)題的最優(yōu)性質(zhì). 以上述研究?jī)?nèi)容為基礎(chǔ)， 本文提出并研究了一種求解線性規(guī)劃新方法(逐步降階的線性規(guī)劃的算法DRSM). 該方法主要優(yōu)點(diǎn)是每次迭代計(jì)算簡(jiǎn)單(都是初等運(yùn)算)， 幾何解釋很直觀便于人們掌握和理解， 迭代次數(shù)少， 逼近最優(yōu)解的速度快， 計(jì)算量少等. 進(jìn)一步需要研究的是， 可綜合利用線性規(guī)劃對(duì)偶理論、 單純形法的逆的乘積、 稀疏矩陣技術(shù)和LU分解等改進(jìn)技術(shù)推廣到DRSM算法中.

[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 f'or presolving in linear programming[J]. Chinese Journal of Management Science， 2016， 24(12)： 117-126. (in Chinese)

[2]高引民， 甘仞初， 吳立志. 線性規(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)

[3]高引民， 甘仞初. 線性規(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)

[4]Gammth G， Koch T， Martin A， et al. Progress in pre solving for mixed integer programming[J]. Mathcmatical Programming Computation， 2015， 7(4)： 1-32.

[5]戴或虹， 劉新為. 線性與非線性規(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)

[6]Pan P Q. A dual projective pivot algorithm for linear programming[J]. Computational Optimization and Applications， 2004， 29: 333-344.

[7]孫黎明. 一種求解線性規(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)

[8]孟香惠， 施保昌. 線性規(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]. J. of Math. (PRC)， 2013， 33(2)： 373-380. (in Chinese)

[9]潘平奇. 關(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)

[10]楊歡， 陶鳳玲， 李若東， 等. “準(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)

[11]敖特根. 單純形法的產(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 Soienc;e Edition)， 2012， 42(5)： 861-864. (in Chinese)

A Simplex Method Base on Reducing the Constraint Conditions of Linear Programming

GAO Yin-min, CHEN Jian-bin

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

Aiming to improve the theory of linear programming with respect to the constraint conditions, a new simple method in solving the large-scale problem ineffective variables was presented. Methods to study the property of optimal slack constraint conditions and optimal tight constraint conditions employing some mathematical tools in linear programming and linear algebra and so forth were used to do numerical tests. The characteristics of the optimal tight constraint conditions, the theorems of identifying optimal slack constraint conditions and a new simple method have been obtained from results. Numerical tests and theory illustrated that identifying and eliminating optimal slack constraint conditions can simplify its constraint conditions and improve the efficiency of solving the problem of linear programming in solving the large-scale problem.

linear programming; simplex method; constraint conditions; optimal tight constraint conditions

1673-3193(2017)04-0409-05

2016-12-24

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

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

O221.1

A

10.3969/j.issn.1673-3193.2017.04.003