一類帶有絕對值的線性規(guī)劃MATLAB 求解方法在數(shù)學(xué)建模教學(xué)中的應(yīng)用

莫潔安

（廣西民族師范學(xué)院數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院，崇左532200）

0 引言

線性規(guī)劃（Linear Programming，LP）是最簡單、應(yīng)用最廣泛的一種數(shù)學(xué)規(guī)劃方法，也是應(yīng)用最早的一種優(yōu)化方法，自從1947 年Dantzig 提出的單純形法使得線性規(guī)劃算法逐漸趨于成熟，在理論上發(fā)展到現(xiàn)在已經(jīng)是比較成熟，同時在實際應(yīng)用中更加的廣泛與深入，特別是在計算機(jī)能大規(guī)模處理成千上萬的約束條件和決策變量的線性規(guī)劃問題之后，線性規(guī)劃的適用領(lǐng)域就更為廣泛了。線性規(guī)劃的基本性質(zhì)有：如果可行域是非空，則是一個凸集-凸多面體；如果有最優(yōu)解，則最優(yōu)解在可行域的頂點；如果可行域有界且只有有限個數(shù)的頂點，則最優(yōu)解存在且在有限個數(shù)的頂點中；最優(yōu)解由最優(yōu)頂點的有效約束形成的方程組的解來確定。

對于線性規(guī)劃的各種研究也很有很多深入的研究，常用的求解方法有單純形法與內(nèi)點法。一般的線性規(guī)劃問題使用單純形法可以通過變換轉(zhuǎn)化成線性規(guī)劃的標(biāo)準(zhǔn)形式進(jìn)行求解，但是對于大規(guī)模的線性規(guī)劃問題中，單純形法顯得有點吃力，這時，內(nèi)點法的快速發(fā)展填補了單純形法的獲得最優(yōu)解的收斂速度等問題，使得線性規(guī)劃發(fā)展的更加快。利用線性規(guī)劃求解問題的步驟一般為“確定決策變量、目標(biāo)函數(shù)、約束條件、非負(fù)約束和求解”五個步驟，為了方便求解，通常需要將之化為標(biāo)準(zhǔn)形式。

在實際教學(xué)過程中，運用數(shù)學(xué)規(guī)劃求解問題的時候的會遇到各種各樣的問題，例如在《數(shù)學(xué)建模算法與應(yīng)用》課程里有一個比較典型的案例---可以轉(zhuǎn)化為線性規(guī)劃的問題，其中規(guī)劃問題為：

其中x=[x1,x2,…,xn]T，A和b為相應(yīng)的矩陣和向量。

該目標(biāo)函數(shù)的變量含有絕對值的問題，一般來說，求解的時候可以通過一些變換轉(zhuǎn)化成線性規(guī)劃，這時可令任意xi，存在ui,vi≥0，存在滿足以下條件：

因此，記u=[u1,u2…,un]T，v=[v1,v2…,vn]T，上述的線性規(guī)劃問題（1）式子可得：

轉(zhuǎn)化成線性規(guī)劃的標(biāo)準(zhǔn)型求解之后，這時可以運用MATLAB 中求線性規(guī)劃問題的函數(shù)linprog（），該函數(shù)包含了求解線性規(guī)劃問題的好幾種算法，例如單純形法和內(nèi)點法?？梢园焉鲜鍪阶痈某删€性規(guī)劃求解的MATLAB 標(biāo)準(zhǔn)型即得：

上式中，f表示目標(biāo)函數(shù)的系數(shù)矩陣，A和b為線性不等式約束條件相應(yīng)的矩陣和向量，運用MATLAB軟件自帶的linprog（）函數(shù)來求解該類線性規(guī)劃問題，其中函數(shù)用法是：[x，fval]=linprog（c，A，b，Aeq，beq，lb，ub，options），這里的x 表示取得最優(yōu)值的時候x 變量的取值，fval 表示最優(yōu)值，c 表示目標(biāo)函數(shù)的系數(shù)，A 和b表示線性不等式約束條件的系數(shù)矩陣，Aeq 和beq 表示線性等式約束條件的系數(shù)矩陣，lb 和ub 表示變量的取值范圍，lb 表示最小值，ub 表示最大值，options 表示對該求解函數(shù)的高級應(yīng)用，例如定義初始值、定義用具體哪個方法求解等等，這里一般用默認(rèn)的方法求解即可。本案例的求解代碼如下：

從該例子可以知道，目標(biāo)函數(shù)中含有絕對值的情況可以轉(zhuǎn)化成線性規(guī)劃問題，相當(dāng)于把變量的維度升高，對目標(biāo)函數(shù)及約束條件的變量也是如此，在用MATLAB 求解處理的最終變量的結(jié)果要注意轉(zhuǎn)化成x，因為算出來的是u，v的值，用x=u-v即可求得。

1 各類帶絕對值的線性規(guī)劃討論及求解

對于課堂中教學(xué)的時候遇到上述問題（1）式中，按照正常的教學(xué)模式，該案例講解完畢學(xué)生也能快速掌握該問題的處理方法、推導(dǎo)過程和MATLAB 求解的過程，接下來需要對該問題進(jìn)行試探性的探討與反思，例如啟發(fā)學(xué)生進(jìn)一步思考一下：目標(biāo)函數(shù)的變量含有絕對值這種情況可以這樣處理，那么如果是約束條件出現(xiàn)該怎么處理呢？或者是目標(biāo)函數(shù)的變量沒有含絕對值，約束條件有怎么辦？或者是目標(biāo)函數(shù)和約束條件均有絕對值的變量，這該如何處理呢？

因為在實際運用的過程，各種可能都會發(fā)生，特別是數(shù)學(xué)建模的課程，本身比較強調(diào)學(xué)生需要多角度思考、多方面考慮各種情況和條件的，因此接下來可以啟發(fā)學(xué)生進(jìn)行思考，通過對該問題的進(jìn)一步提出假設(shè)問題，并根據(jù)已學(xué)習(xí)的案例進(jìn)行推導(dǎo)、計算，達(dá)到一舉多得的教學(xué)效果，接下來進(jìn)行下面的探討和求解：

（1）如果約束條件中含有絕對值變量呢，該如何處理？把該問題引出新的求解問題如下：

其中x=[x1,x2,…,xn]T，A和b為相應(yīng)的矩陣和向量。

那么求解該問題的時候，可以根據(jù)上述問題（1）的求解過程接著進(jìn)行，同理也可以轉(zhuǎn)化為線性規(guī)劃問題，因此，記u=[u1,u2…,un]T，v=[v1,v2…,vn]T，上述的線性規(guī)劃問題（3）式可得：

把上述（4）式寫成線性規(guī)劃求解的MATLAB 標(biāo)準(zhǔn)型即得：

上式中，f表示目標(biāo)函數(shù)的系數(shù)矩陣，A和b為線性不等式約束條件相應(yīng)的矩陣和向量。因此，可以用MATLAB 的linprog（）函數(shù)來求解該類線性規(guī)劃問題，代碼如下：

從這里可以的簡單推導(dǎo)和計算過程可以看出，雖然是基于問題（1）的擴(kuò)展討論，但是對問題的分析和求解過程是舉一反三的一個很重要的案例，同時也激起學(xué)生對該問題的進(jìn)一步探討研究，提高學(xué)習(xí)的興趣與參與程度，對課堂而已，這里對問題的拓展既包括難度合適以及引導(dǎo)學(xué)生動腦筋思考的雙重考慮，也是對學(xué)生學(xué)習(xí)能力的一次檢測。

（2）接下來，在（1）的基礎(chǔ)上進(jìn)一步討論：如果添加等式約束條件呢？那么該問題為：

其中x=[x1,x2,…,xn]T，A和b為相應(yīng)的矩陣和向量，lb 和ub表示變量的范圍。

該問題比之上述問題稍稍有點麻煩，主要是添加了變量的取值范圍，這時，對于含有絕對值情況討論的時候有點不一樣，哪里不一樣呢？可以引導(dǎo)學(xué)生對上述問題重新進(jìn)行推導(dǎo)，這時會發(fā)現(xiàn)，推導(dǎo)過程的時候，需要把變量的取值范圍加進(jìn)來考慮，因此，求解該目標(biāo)函數(shù)的變量中含有絕對值的問題，參考上述（1）式中轉(zhuǎn)化成線性規(guī)劃的求解過程，記u=[u1,u2…,un]T，v=[v1,v2…,vn]T，上述的線性規(guī)劃問題式子可得：

把上述（6）式寫成線性規(guī)劃求解的MATLAB 標(biāo)準(zhǔn)型即得：

上式中，f表示目標(biāo)函數(shù)的系數(shù)矩陣，A和b為線性不等式約束條件相應(yīng)的矩陣和向量，lb 和ub表示變量的范圍，這里需要注意的是不等式矩陣?yán)锏? 表示的不是一個數(shù)字1，是一個1×n的向量矩陣。可以運用MATLAB 的linprog（）函數(shù)來求解該類線性規(guī)劃問題，代碼如下：

通過本例中的推導(dǎo)可以看出，這里的求解和推導(dǎo)過程比上述第一種情況難度稍微大一點，主要考慮到變量的取值范圍對替換變量之后的轉(zhuǎn)變，這時引導(dǎo)學(xué)生應(yīng)該注意對該問題轉(zhuǎn)化的認(rèn)知，對含有絕對值的變量進(jìn)行線性轉(zhuǎn)換的過程的認(rèn)識，從而達(dá)到更加深刻理解和認(rèn)識該問題的推導(dǎo)與求解過程。

（3）根據(jù)以上1、2 討論的情況的，可以進(jìn)一步綜合分析，引導(dǎo)學(xué)生思考：若目標(biāo)函數(shù)及約束條件的變量中均含由絕對值的情況，這時該如何處理？有了前面兩種情況的討論，那么對于這個更加復(fù)雜的問題，可以有一定的基礎(chǔ)和經(jīng)驗進(jìn)行了。如對線性規(guī)劃標(biāo)準(zhǔn)型帶有絕對值的模型如下所示：

同理，把上面的問題轉(zhuǎn)化成線性規(guī)劃問題，記u=[u1,u2…,un]T，v=[v1,v2…,vn]T，該線性規(guī)劃問題的MATLAB 標(biāo)準(zhǔn)型可以得：

上式中，f表示目標(biāo)函數(shù)的系數(shù)矩陣，A和b為線性不等式約束條件相應(yīng)的矩陣和向量，lb 和ub表示變量的范圍，需要注意的是不等式矩陣?yán)锏? 表示的不是一個數(shù)字1，是一個1×n的向量矩陣，可以用MAT?LAB 的linprog（）函數(shù)來求解該類的線性規(guī)劃問題，代碼如下：

通過由淺入深一步一步的引導(dǎo)學(xué)生進(jìn)行推導(dǎo)、計算到最好求解的過程，既符合數(shù)學(xué)建模課程舉一反三的思想，也滿足引導(dǎo)學(xué)生進(jìn)行探討式學(xué)習(xí)的需要，一舉多得。

2 應(yīng)用舉例及結(jié)論

上述部分主要講解理論推導(dǎo)及MATLAB 的計算函數(shù)，接下來舉個具體的案例進(jìn)行分析，求解下列線性規(guī)劃問題：

把上述問題轉(zhuǎn)化成線性規(guī)劃MATLAB 求解標(biāo)準(zhǔn)型，即：

其中f、A、b矩陣如下所示：

根據(jù)本文上述的線性規(guī)劃標(biāo)準(zhǔn)型的MATLAB 求解方式，其運行代碼如下：

在實際過程中處理線性規(guī)劃問題的時候，有些問題看起來不是線性規(guī)劃問題，例如目標(biāo)函數(shù)或者約束條件的變量帶有絕對值情況，本文通過一些線性變換即可轉(zhuǎn)化成標(biāo)準(zhǔn)的線性規(guī)劃問題進(jìn)行求解，并且討論了其含有絕對值變量情況，由淺入深、一步一步引導(dǎo)學(xué)生進(jìn)行思考、推導(dǎo)及其求解過程。

總而言之，在實際過程中處理線性規(guī)劃問題的時候，有些問題看起來好像不是線性規(guī)劃問題，這時可以通過一些線性變換轉(zhuǎn)化成線性規(guī)劃問題來處理。因此本文對該類問題進(jìn)行深入探討分析，綜合得出一個針對各種情況中變量含有絕對值的求解情況并給出MATLAB 求解方法，給該課引入舉一反三思想，達(dá)到理論學(xué)習(xí)與實踐能力雙向豐收的教學(xué)效果。