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

高引民， 陳建斌

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

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

高引民， 陳建斌

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

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

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

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

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

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

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

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

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

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

考慮如下線性規(guī)劃問題(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為LP的可行解域，D≠φ,hi={X|li(X)=0,X∈D},X*為LP最優(yōu)解,Z*為LP的最優(yōu)值. 取i0∈{1,2,…,m}, 在LP中刪掉第i0約束條件， 構(gòu)造線性規(guī)劃問題(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}, 對于(LP)構(gòu)造如下線性規(guī)劃問題(LPi0)

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

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

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

則li0≤0 為LP的最優(yōu)松約束條件.

同理可證明2)成立.

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

2 降階的單純形法(DRSM)

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

具體步驟如下：

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

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

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

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

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

確定換出基變量為xl.

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實例及數(shù)值實驗分析

例 1 對線性規(guī)劃問題

maxZ=2x1+3x2,

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

maxZ=2x1+3x2,

線性規(guī)劃問題最優(yōu)等價.

例 2 數(shù)值實驗分析

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

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

maxZ=CX,

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

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

表 1 DRSM與SM比較

將SM法和DRSM法對問題的計算時間繪成對比曲線圖如圖 1 所示.

圖 1 SM與DRSM對問題的計算時間對比圖Fig.1 Computing time contrast figure of SM and DRSM

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

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

2) 同樣問題的求解時間減少；

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

4 結(jié)束語

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

[1]胡艷杰， 黃思明， Adren N， 等. 對偶性在線性規(guī)劃預(yù)處理中的應(yīng)用分析[J]. 中國管理科學(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é)報， 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ī)劃問題非有效約束條件性質(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]. 運籌學(xué)學(xué)報， 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ī)劃的投影動態(tài)方法[J]. 南京師大學(xué)報(自然科學(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ī)劃界面算法的高效實現(xiàn)” [J]. 運籌學(xué)學(xué)報， 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é)實踐與認(rèn)識， 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é)報(自然科學(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

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

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

O221.1

A

10.3969/j.issn.1673-3193.2017.04.003