LP之單純形法教輔軟件設計與實現

曹迎槐　張靜　趙強

摘要：在線性規劃理論中，單純形法是非常經典的求解算法，但它計算復雜，涉及數據較多，掌握相對困難，為提高教學效果，筆者開發了《軍事運籌原理仿真模擬系統》，其中涉及了線性規劃模型的單純形求解算法仿真問題，經教學實用，效果良好。

關鍵詞：LP;模型;單純形法;仿真

中圖分類號：TP311 文獻標識碼：A

文章編號：1009-3044（2020）20-0070-02

Design and Implementation of LP Simplex Method Teaching Auxiliary Software

CAO Ying-huai. ZHANG Jing， ZHAO Qiang

（China Coast Cuard Academy， Ningb0 315801. China）

Abstract： In the theory of' linear programming， Simplex method is a very c：lassical solution algorithm， But it's complicated， More da-to involved， lt's relatively difficult to master. In order to improve the teaching effect， 'rhe author develc}ped the simulation system ofmilitary operation principle， It involves the simulation of' simplex algorithm of' linear programming model， After teaching practical，the effect is good.

Key words： linear programming; simplex method; foundation： simulation

目前，在運籌學之線性規劃（linear programming，簡稱LP）分支中，最經典的求解算法就是單純形法，它既是運籌學教材之重點，也是教學之難點所在。但該算法相對復雜，計算過程煩瑣，學生掌握相對困難，為此，筆者開發了該算法的求解仿真軟件，教學效果良好。

1單純形法的求解步驟

單純形法和基于窮舉思想的基可行解法不同，它不需要求出所有的基可行解，而是以LP模型之標準形式為出發點先求出一個基可行解，并檢驗其是否為最優解。如果它已最優，則求解結束，算法終止;如果它不是最優解，就按照算法給定的方法求出另一個基可行解，該算法可以保證新求出的基可行解肯定要優于上一個基可行解。只要LP問題存在最優解，就一定可通過有限次的運算求出最優解。如果，所求的問題不存在有限的最優解（即無解），則該算法也有相應法則判斷之。

其具體的求解算法可歸納為五步。

1.1確定初始基可行解

確定出初始（即第一個）可行基時，因標準化處理中多加入松弛變量，所以，初始基可行解的確定往往并不困難，一般直接選取各松弛變量即可。當然，若個別約束方程未添加松弛變量，亦可借助線性代數知識，通過行或列的交換等操作來得到。

1.2最優解檢驗

檢驗初始基可行解是否最優。若是最優解，則停止運算;若不是最優解，就轉下一步。

1.3無解檢驗

當檢驗初始基可行解不是最優解時，繼續檢驗該規劃問題是否無解（即無有限的最優解）。若無解則停止運算，若依然無法判定是否無解則轉下一步。

1.4基變換

當經過上面的兩種檢驗發現，該基可行解既不最優，也不能判定其無解，則需要尋找另一個基可行解。即在該可行基之基礎上，先從原非基變量中選一個變量，稱換人變量;再于原基變量中選擇一個變量使其成為非基變量，稱之為換出變量。于是，新的基變量對應的系數列向量，同原來保持不變的基變量對應的系數列向量（m-1）個，就組成一個新的可行基，此即基變換。

1.5旋轉運算

基變換完成后，需進一步求出其相應的新基可行解，該過程即旋轉運算。然后，轉步驟12。

單純行法的求解算法亦可用傳統流程圖來描述，在仿真實現中如圖1所示。

2單純形表

利用單純形法求解LP問題，涉及大量的數值計算，且各數值之間關系復雜，種類繁多，為簡明其見，通常是列表（稱為單純形表，見圖2）進行。一般地，單純形表中應考慮以下數據：

1）基變量：這里用xBi，表示，有xBi=xi（i=l，2，…，m），如圖2上部左側第1列;

2）基變量的價值系數：用cBi表示，有cBi=ci（i=1，2，…，m），如圖2上部左側第2列;

3）約束方程右端的常數bi（i=l，2，…，m），如圖2上部有側第2列;

4）目標函數中各變量的價值系數cj（j=1，2，…，n），填入Cj列，如圖2上部第1行;

5）規劃模型之各基向量，Pj（j=1，2，…，n），填人xj行下面的對應區域，如圖2上部中間區域;

6）檢驗數σj（j=1，2，…，n）填在單純形表的最下面一行，如圖2中部σj所示。公式為：

7）確定換人變量時，利用“θ最小比法則”計算出來的θi（i-1，2，…，m），填入單純形表最右側一列。當然，換入變量確定之后，計算θi=bi/aik時，當aik>0時才須計算之，當aik≤0時不用計算。所以，運算過程中，θi一列并非總要填滿，要視情況而定。

3單純形法求解仿真

單純形法仿真求解是筆者設計開發之《軍事運籌學原理仿真模擬系統》中的一個子模塊，假設給定的LP問題之標準型如圖2下半部區域所示。其中涉及目標函數系數、約束方程系數矩陣、資源列向量、未知變量個數、約束方程個數等。

界面最底部的文字用來描述仿真求解過程中相關操作信息。而“導入”按鈕則可將已標準化的LP模型納入單純形法求解仿真模塊，導人操作剛完成時，并沒有圖2界面中上半部分單純形表中的相關數據，這些數據是在求解過程中隨著各步操作的進行而出現并動態變化的。“清除”按鈕則可將該仿真模塊中的LP數據清空，屆時整個仿真界面呈現空白狀態。

本仿真模塊的求解分兩種模式，一是“分步求解”，一是“連續求解”。當LP模型數據導入完成后，即可通過單擊“分步求解”按鈕，啟動單純形求解之第一步“確定初始可行基”，該步完成則同時填充該界面上半部分的“單純形表”之相關區域，并將“分步求解按鈕上的文字變為“下一步”，如圖2所示。此后，可依次單擊“下一步”按鈕，則求解過程中各相關數據的變化即體現在該界面上半部分的單純形表相關區域中。

持續單擊“下一步”按鈕，如果該LP模型存在最優解，則求解完成時，最優解出現在相應位置，同時“下一步”命令按鈕變為“分步求解”，如圖3所示。

任何時候，均可通過“打印”按鈕將當前界面的狀態打印出來，不過，在一般教學實施過程中，該功能使用并不多。通過“設置”按鈕可改變未知變量的個數和約束方程的個數等LP規模數據，當LP規模較高時，可協同“高維模型”按鈕共同使用，但此刻仿真模塊已基本失去教學輔助之意義，逐漸靠向求解工具的范疇，因此，課堂上不常使用。

“連續求解”按鈕可從導入標準化模型開始，直達最后得到求解結果，中間的各步信息也不再顯示在界面的底部，界面上半部直接顯示最優解，這里不再贅述。

“基解列表”按鈕可顯示該LP模型在本模塊之仿真求解過程中得到的所有可行基，如圖4所示。但一般肯定不是該LP模型的所有可能的基（含不可行的），這一點必須清楚。

當然，在該仿真模塊中，標準化之后LP模型未必能直接得出初始可行基，此時可借助大M法或兩階段法求解之。另外，如果LP模型無解，仿真模塊同樣會給出相關反饋信息。鑒于篇幅這里不再詳述。因水平所限，不妥和錯誤之處，敬請大家批評指正！

參考文獻：

[1]錢頌迪.運籌學[M].北京：清華大學出版，1993.

[2]曹迎槐，尹健，梁春美.軍事運籌學[M].北京：國防工業出版社.2013.

[3]曹迎槐.LP模型標準化教輔軟件設計與實現[J].電腦知識與技術，2018（7）：87-88.

[4]曹迎槐.LP之單純形法教輔軟件設計與實現[J].電腦知識與技術，2020（17）：63-64.

【通聯編輯：謝媛媛】

收稿日期：2020-05-08

作者簡介：曹迎槐（1966-），男，河北蔚縣人，教授，技術5級，碩士，長期從事計算機技術、運籌建模、海警信息與情報等領域的教學與科研工作;張靜（1980-），女，遼寧大連人，副教授，碩士，從事信息安全專業教學工作;趙強（1976-），男，青海西寧人，講師，碩士，從事多媒體和信息技術專業教學和科研工作。