線性規劃的教學模式探討

苗連英，逄世友

（中國礦業大學　理學院，江蘇　徐州　221008）

線性規劃的教學模式探討

苗連英，逄世友

（中國礦業大學理學院，江蘇徐州221008）

線性規劃是運籌學的核心內容，求解線性規劃的單純形法在理論上已趨于成熟，應用也越來越廣泛。為了使學生更容易、更深刻地理解這種算法及其理論基礎，本文給出了一種循序漸進的教學模式。這種模式也適用于運籌學其他內容的教學。

單純形法；循序漸進；教學模式

運籌學是二戰期間發展起來的一門應用學科，它廣泛應用現有的科學技術知識和數學方法，解決實際中提出的一些問題，為決策者選擇最優策略提供定量依據，其內容包括：規劃論（線性規劃、非線性規劃、整數規劃、動態規劃、多目標規劃等）、圖論與網絡分析、對策論、排隊論、存儲論、決策論、排序與統籌方法等[1]。運籌學的實際應用涉及生產計劃、運輸問題、人事管理、庫存管理、市場營銷、財務和會計等方面。另外，還應用于設備維修、更新和可靠性分析，項目的選擇與評價、工程優化設計、環境保護等問題中。據統計，50%數學建模問題與運籌學內容相關，可以用運籌學的方法解決。另外，為各大高校數次爭得榮譽的建模隊伍，長期以來一直接受運籌學相關知識的培訓。

運籌學中最主要的分支是線性規劃。線性規劃模型是前蘇聯著名經濟學家康托羅維奇于1939年提出的，這一重大發現使他獲得了諾貝爾經濟學獎。1947年G.B.Dantzig提出求解線性規劃的單純形法。針對退化問題，1952年A.Charner和W.W.Cooper[2]給出了攝動法，1954年G.B.Dantzig，A.Orden和P.Wolfe[3]提出了字典序方法，1976年G.G.Bland[4]提出了Bland法則，這些方法都能避免循環發生。線性規劃理論上已趨于成熟，應用也越來越廣泛。事實上，運籌學中許多問題都可以或需要用線性規劃模型來描述或近似地描述，如運輸問題——求解運輸問題的表上作業法本質上就是單純形法，并且這種方法充分展示了單純形法的魅力。求最短路、最小費用最大流的問題都可以用線性規劃模型來解決。求解指派問題的匈牙利法本質上也是單純形法[5]。矩陣對策問題最后轉化成求解線性規劃。學習運籌學的先修課程主要有線性代數、微積分、概率論與數理統計。事實上，運籌學不僅應用了這些學科，也從理論上進一步發展了這些學科。

單純形法是建立在一系列理論基礎之上的。首先，如果線性規劃的可行域非空，則它是一個凸集，這個結論很容易證明。線性規劃的可行域的頂點與基可行解之間是一一對應的，所以其頂點個數有限，這個結論與單純形法的關系不大，其證明可以省略。其次，線性規劃若有可行解，則一定有基可行解，這個結論是很重要的，為了更好地理解它的證明，我們先看下面的例子。

任意找出該線性規劃的一個可行解，比如X0=（1，1，12，2，3）T。由于其正分量的個數大于3，所以它不是基可行解。如何找出一個基可行解呢？由（1）可知P1-P2-2P3-4P4+2P5=0，令α=（1，-1，-2，-4，2）T.

設t是一個很小的正數，構造兩個向量：

首先注意到AXi=A（X0±tα）=AX0±tAα=b.另外我們要取適當的t，使得X1≥0，X2≥0.通過觀察上面兩式可知時，X1和X2都是可行解。取得，

進一步講，若線性規劃有最優解，其最優解一定可以在其可行域的頂點上找到，也就是在其基可行解中找到，這樣就把一個從無限個可行解中找最優轉化成在有限個可行解中找最優。這是單純形法的理論基礎。為了更好地理解這一重要結論的證明，我們看下一個例子。

X0=（1，2，0，1）T是（2）的一個最優解，由于其正分量的個數大于2，所以它不是基可行解。下面找一個基可行解也是最優解，方法與例1類似。由（2）可知2P1-P2-P4=0，令α=（2，-1，0，-1）T.

設t是一個很小的正數，構造兩個向量：

首先注意到AXi=A（X0±tα）=AX0±tAα=b。另外我們要取適當的t，使得X1≥0，X2≥0。通過觀察上面的式子可知時，X1和X2都是可行解。

而且有CX0≥CX1，CX0≥CX2，即CX0+tCα=CX1≤CX0，CX0-tCα=CX2≤CX0.從而Cα=0，即X1和X2都是最優解。X2的正分量的個數是2。由于P2，P4線性無關，所以X2是基可行解。這樣我們就找到了一個最優解也是基可行解。一般地，若X2的正分量對應的系數列與線性相關，繼續上述過程，直到找到基可行解為止。

從基可行解中找最優解所用的方法是單純形迭代法。那么，如何判斷一個線性規劃是否有最優解？如何判斷一個基可行解是否是最優解？在一個基可行解不是最優的情況下如何迭代到下一個與其相鄰的更好的基可行解？為回答這些問題，我們舉例說明。

該問題有一明顯的基可行解X0=（0，0，18，6，5）T，且（3）就是X0對應的典式，由于x1，x2的價值系數都小于0，從而X0是最優解，且是唯一的最優解。因為若還有另一個最優解則必有，從而即X0=X1.

把上例稍作修改，如下例：

X0是（4）的基可行解。由于x1的價值系數是0，所以只要保持x2=0，x1的增加不會改變z的值。由約束方程組可知，x1可取中的任何值。當時，可得另一最優解，X0的X1任意凸組合都是最優解，從而該問題有無窮多最優解。

再看下例：

X0是（5）的基可行解，但不是最優解，因為只要x1增大，z就會增大。若令x2=0，則約束方程組變成：

令x1=θ＞5，則得一個可行解X=（θ，0，18+4θ， 6+4θ，5）T，其對應的由此可知，該問題無最優解或有無界解。

通過例3~例5可以引出最優性判別定理：

設X0是基可行解，其對應典式為：

①如果對一切j=m+1，…，n，有σj≤0，則X0是線性規劃的最優解。

②如果對一切j=m+1，…，n，有σj＜0，則X0是線性規劃的唯一最優解。

③如果對一切j=m+1，…，n，有σj≤0，且存在某個σm+k=0，則線性規劃有無窮多最優解。

④若存在某個σm+k＞0，且對一切i=1，2，…，m，有βi，m+k≤0，則線性規劃無最優解（最優值為無窮大）。

再看一個例子：

X0是（6）的基可行解，但不是最優解，因為當x1、x2增大時，z也會增大。注意我們只能讓x1、x2之一增大，這樣才能得到一個與X0相鄰的基可行解。由于x1的價值系數比x2的價值系數大，我們一般是讓x1增大，x2還是0。

由于x1最大可以增大到，從而得到新的基可行解：

這里需要說明X1還是基可行解，只要證明P1，P2，P3線性無關即可。由于P1，P3，P4與P3，P4，P5等價（容易看出，從而X1也是基可行解。通過變換求出X1對應的典式，完成一次單純形迭代。

通過上例可以引入基可行解的改進定理：

設X0是基可行解，其對應典式如（6）：

①若存在某個σm+k＞0.

②存在i∈{1，2，…，m}，使得βi，m+k＞0.

③所有的αi＞0，i∈{1，2，…，m}，則一定存在另一個基可行解X1，使得CX0＜CX1。

進而提出單純形算法的基本步驟：

①找出一個初始基可行解X0，寫出X0相應的典式。

②如果所有非基變量xj的檢驗數都不大于0，則X0是最優解，計算結束，否則轉至③。

③取一個最大的檢驗數σk＞0，如果所有的βik≤0，則線性規劃問題無最優解，計算結束，否則轉至④。

則xk為換入變量，xl為換出變量，得到一個新的基可行解X1，轉⑤。

⑤進行基變換，得到X1的典式，轉②。

先講特例再引入最優性判別定理、基可行解的改進定理以及單純形法的迭代步驟，學生就容易理解。即使針對有些專業的學生講解這些定理的證明，也容易接受。

總之，現代社會信息量大，大學生需要學習的課程很多，用于預習或復習的時間就很少，這樣上課時間就尤為珍貴，教師應該如何講，才能使學生當堂聽明白所授內容，這是一個必須思考的問題。其實，運籌學這門學科更側重的是應用，數學理論并不難，之所以有人覺得難學，是因為沒有把握一種好的學習方法。本文針對單純形法給出了一種循序漸進的教學模式，實踐證明這種模式能使學生更容易的理解課堂內容，有利于激發學生的自信心和學習興趣，使學生在輕松掌握數學理論的基礎上，能更好地探討運籌學的經典案例的建模和求解，加強學生運用所學知識解決實際問題的能力和創新能力。

[1]《運籌學》教材編寫組.運籌學[M].北京：清華大學出版社，2004.

[2]Charnes，A.And CooperW.W.，The stepping stonemethod of explaining linear programm ing calculations in thansportation problems，ManagementScience，1954，（1）：49-69.

[3]Dantzig，G.B.，O rden.A.and W olfe.P.，Note on linear programm ing，Pacific J.Math.1955，（5）：183-195.

[4]Bland，G.G.，New finite pivoting rules of Simplex method，Math.O fOperationsResearch，1977，（2）：103-107.

[5]Hamdy，A.Taha，Operations Research-An Introduction[M].北京：人民郵電出版社，2007.

G642.0

A

1674-9324（2014）45-0036-04

2014年度江蘇省研究生教育教學改革研究與實踐課題，《運籌學》立體化教學平臺建設；2014年中國礦業大學精品資源共享課：《運籌學》

苗連英（1966-），女，中國礦業大學理學院教授，主要從事運籌學教學和科研工作。