一類帶有絕對值的線性規劃MATLAB 求解方法在數學建模教學中的應用

莫潔安

（廣西民族師范學院數學與計算機科學學院，崇左532200）

0 引言

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

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

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

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

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

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

轉化成線性規劃的標準型求解之后，這時可以運用MATLAB 中求線性規劃問題的函數linprog（），該函數包含了求解線性規劃問題的好幾種算法，例如單純形法和內點法。可以把上述式子改成線性規劃求解的MATLAB 標準型即得：

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

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

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

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

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

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

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

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

把上述（4）式寫成線性規劃求解的MATLAB 標準型即得：

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

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

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

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

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

把上述（6）式寫成線性規劃求解的MATLAB 標準型即得：

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

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

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

同理，把上面的問題轉化成線性規劃問題，記u=[u1,u2…,un]T，v=[v1,v2…,vn]T，該線性規劃問題的MATLAB 標準型可以得：

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

通過由淺入深一步一步的引導學生進行推導、計算到最好求解的過程，既符合數學建模課程舉一反三的思想，也滿足引導學生進行探討式學習的需要，一舉多得。

2 應用舉例及結論

上述部分主要講解理論推導及MATLAB 的計算函數，接下來舉個具體的案例進行分析，求解下列線性規劃問題：

把上述問題轉化成線性規劃MATLAB 求解標準型，即：

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

根據本文上述的線性規劃標準型的MATLAB 求解方式，其運行代碼如下：

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

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