有界變量線性規(guī)劃問題的一種解法*

劉海英

(福建廣播電視大學　福建福州　350003)

?

有界變量線性規(guī)劃問題的一種解法*

劉海英

(福建廣播電視大學福建福州350003)

摘要：有界變量的線性規(guī)劃問題可以先轉(zhuǎn)化為標準形式的線性規(guī)劃問題，然后按照單純形方法進行求解.但是，由于這類問題增加了變量和等式的約束，從而導致計算量和存儲量大大增加.因此，文章考慮先把包含上、下界變量限制的線性規(guī)劃問題轉(zhuǎn)化為變量有上界限制的線性規(guī)劃問題，然后再進行求解.

關鍵詞：線性規(guī)劃，有界變量，單純形法

在實際應用中的許多線性規(guī)劃問題，其決策變量具有一定的上、下界限制，這類問題稱為有界變量的線性規(guī)劃問題.有界變量的線性規(guī)劃問題可以先轉(zhuǎn)化為標準形式的線性規(guī)劃問題，然后按照單純形方法進行求解[1-2].但是，由于這類問題增加了變量和等式的約束，從而導致計算量和存儲量大大增加.文章利用一種新的解法，可以在不擴大系數(shù)矩陣的情況下提高運算效率.

1有界變量線性規(guī)劃問題基本解的特征

有界變量的線性規(guī)劃問題的數(shù)學模型可寫為：

minz=cx

(1)

其中，l=(l1,l2,…,ln)T和u=(u1,u2,…,un)T分別是x=(x1,x2,…,xn)T的下界和上界，矩陣A仍為m×n階矩陣，并設A的秩為m.

minz=cx

(2)

為表達方便起見，不妨將式(2)仍用x的形式來表示，即

minz=cx

(3)

式(3)稱為變量有上界限制的線性規(guī)劃問題.對于式(3)若引進松弛變量y，則可將其化為標準形式的線性規(guī)劃問題，即：

minz=cx

(4)

但這樣做之后，系數(shù)矩陣會擴大很多，給計算增加困難.下面將介紹一種在不擴大系數(shù)矩陣前提下來尋求變上界限制的線性規(guī)劃問題的解法.

結(jié)論5：設S1={i1,i2,…,im}，作矩陣B=(pi1,pi2,…,pim)，則B是滿秩的.

由上述結(jié)論可知，式(4)的基本解具有這樣的特征：在它的前n個分量中，有n-m個分量必取上、下界，而可以不取上、下界的m個分量所對應的矩陣A的列向量必線性無關.由此可以對式(3)的基本解和基本可行解進行如下定義：

(1)B=(pi1,pi2,…,pim)是滿秩矩陣；

則稱x0為式(3)的一個基本解，B=(pi1,pi2,…,pim)為x0對應的基陣，變量xi1,xi2,…,xim稱為相應于該基的基變量，其余變量稱為非基變量.另外，稱滿足約束條件0≤x0≤d的基本解 為基本可行解，稱基本可行解對應的基B為式(3)的可行基.

記基變量的指標集為S，非基變量的指標集為R.將指標集合R分成兩個子集R1和R2，若滿足R1∪R2=R，R1∩R2=?，則稱(R1,R2)是R的一個剖分，并稱{xi|i∈R1}為第一類非基變量，取值都為0；稱{xi|i∈R2}為第二類非基變量，取值都為上限di.也就是說，對于R的任一剖分(R1,R2)，非基變量取值為：

(5)

由前面對式(4)基本解的分析及定義容易證明下列定理：

定理2 x0是式(3)的一個基本可行解的充分必要條件是x0是凸集K={x|Ax=b,0≤x≤d}的一個頂點.

定理3 x0是式(2)的一個基本可行解的充分必要條件是(x0,d-x0)是線性規(guī)劃問題(2)的一個基本可行解.

有了上面的幾個定理，下面的兩個結(jié)論就成為顯然的了.

結(jié)論6：如果線性規(guī)劃問題(3)有可行解，則一定有基本可行解.

結(jié)論7：如果線性規(guī)劃問題(3)存在最優(yōu)解，則一定可以在某個基本可行解上達到最優(yōu)值.

所以有：XB=B-1b-B-1N1XN1-B-1N2XN2

(6)

將其代入目標函數(shù)中，可以得到：

cx=CBXB+CN1XN1+CN2XN2

=CB(B-1b-B-1N1XN1-B-1N2XN2)+CN1XN1+CN2XN2

=CB-1b-(CBB-1N1-CN1)XN1)-(CBB-1N2-CN2)XN2

(7)

(8)

(9)

2有界變量單純形法

和通常的單純形法一樣，這里原算法也是分兩個階段來計算的.第一階段是尋求一個初始基本可行解，和單純形法類似[3]，文章不做過多介紹.第二階段是從初始基本可行解出發(fā)，通過基與可行剖分的逐次迭代，不斷改進目標函數(shù)值，最終獲得最優(yōu)解.

所對應的xk作為換入基變量(如果想提高迭代效率，則從不符合最優(yōu)性條件的檢驗數(shù)中選取其絕對值最大的對應變量作為換入基變量).由于變量有上界限制，所以換出基變量xl的選擇要比單純形法復雜，具體要考慮問題如下：

(1)如何選取換出基變量.

(2)變量換出以后歸入哪一類非基變量.

下面對以上兩個問題進行分析.

由變量必須為非負值，并且不能超過上界的限制可知，θ應滿足：

解該不等式組得：

由此可知：

下面分3種情況進行討論.

參照情形1進行類似迭代，也應分成如下3種情況：

綜上可知，不管是哪種情形，都能得出一個新基本可行解x1(如果問題有最優(yōu)解)，并且x1對應的目標函數(shù)值不會超過x0對應的目標函數(shù)值.這一結(jié)論的驗證可查閱參考文獻[4].

現(xiàn)在把有界變量單純形法的計算步驟總結(jié)如下：

第1步從一個基本可行解及對應的典式開始.

確定xk的通常規(guī)則是在所有不滿足最優(yōu)解條件的檢驗數(shù)中取一個絕對值最大的.如果k∈R1，則轉(zhuǎn)第4步；如果k∈R2，則轉(zhuǎn)第5步.

第4步計算θ=

(1)若θ=dk，則轉(zhuǎn)第6步.

第5步計算θ=

(1)若θ=dk，則轉(zhuǎn)第7步.

這里假設每個變量都有上界，如果只是部分變量有上界限制，可令沒有上界的變量的上界是個充分大的正數(shù)，則上述方法同樣適用.在計算時不用寫出這個充分大的正數(shù)，只要在找θ時做個改進就行了.

如果xi的上界是充分大的正數(shù)，則：

例1：求解如下線性規(guī)劃問題[5]：

minz=-2x1-x2

解：第1步 該問題有明顯的初始基本可行解x0=(0,0,5,0,21)T，對應的基為B=(p3,p4,p5)，R1={1,2},R2=?.列出單純形表，為方便起見，直接在單純形表的前邊增加一列為解列，用來表示該基本可行解的各基分量值和對應的目標函數(shù)值，如表1所示.

表1　單純形表1

第3步 取絕對值大的檢驗數(shù)σ1對應的變量x1作為換入基變量.

表2　單純形表2

因此，可以確定x5為換出基變量，取值為0，即R1={5},R2{1}，作單純形表如表3所示.

表3　單純形表3

因此，取x2為換出基變量.進行一次通常的單純形迭代(除了解這一列)，對于解列，則有：

表4　單純形表4

此時，R1={5},R2={2}.

3結(jié)論

文章針對線性規(guī)劃問題中變量有界的情況進行了分析，通過研究基本解的特征，可以把一般形式的有界變量線性規(guī)劃問題轉(zhuǎn)化為變量有上界限制的問題.然后，進一步提出變量有上界限制的單純形法，利用文章提出的在不擴大系數(shù)矩陣的前提下來尋求變上界限制的線性規(guī)劃問題的解法，大大減少運算量，提高效率.

參考文獻：

[1]唐曉文，劉海英，文斌.線性規(guī)劃[M].北京：中央廣播電視大學出版社，2012.33.

[2]管梅谷，鄭漢鼎．線性規(guī)劃[M]．濟南：山東科學技術出版社，1983．56.

[3]中國人民大學數(shù)學教研室．線性規(guī)劃學習指導[M]．北京：中央廣播電視大學出版社，1984.153.

[4]鐘守南，高成修．運籌學理論基礎[M]．武漢：武漢大學出版社，2005．68.

[5]朱求長．運籌學及其應用(第3版)[M].武漢：武漢大學出版社，2004．99.

(責任編輯李佳瑜)

中圖分類號：O 29

文獻標識碼：A

文章編號：1674-9545(2015)04-0077-(07)

通訊作者：劉海英，398118122@qq.com。

收稿日期：2015-9-17

*基金項目：中央廣播電視大學非統(tǒng)設課程資助項目成果之一。