LP之基可行求解算法教輔軟件設計與實現

摘要：在線性規劃求解過程中，基可行求解算法是個非常重要的知識點，它向上承接模型標準化過程，向下則為后續的單純形求解算法做理論基礎，故在教學中分量較重。為提高教學效果，筆者開發了《軍事運籌原理仿真模擬系統》，其中涉及了線性規劃模型的基可行求解算法仿真問題，經教學實用，效果良好。

關鍵詞：LP;模型;基;仿真

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

文章編號：1009-3044（2020）17-0063-02

Abstract： In the process of linear programming， feasible basic foundation algorithm is a very important knowledge point. It goes up to model standardization， downward for the subsequent simplex algorithm to do the theory， Therefore in the teaching weight is heavier. In order to improve the teaching effect， the author developed the simulation system of military operation principle， the feasible basic fundamental solution algorithm simulation problem of lp model involved. Practical teaching， it worked well.

Key words： linear programming; model; foundation; simulation

可用一組決策變量x1，x2，…，xn來描述問題之實施方案，且存在一組線性等式（或不等式）來表示的限制條件，還有一個可用決策變量的線性函數來表示追求目標（或求最大化，抑或是最小），則此類問題之求解理論即線性規劃（linear programming，簡稱LP）。

1 LP標準型

LP求解算法較多，為方便可規定LP之數學模型的標準形式如圖1所示。

2 基可行求解

3 基可行解仿真實現

基可行求解是筆者設計開發之《軍事運籌學原理仿真模擬系統》中的一個子模塊，假設給定的LP抽象模型如圖2所示。

則經該系統之標準化處理之后，再調用基可行求解處理模塊，則系統界面如圖2所示。

通過該界面上的“導入”命令按鈕可以將已標準化并保存的LP模型導入該基可行求解模塊。導入操作的完成后，則被導入模型之相關信息，諸如未知變量個數、約束方程個數、資源列向量等數據均直接顯示在該界面的中間區域。而‘清除命令按鈕則可將該模塊的當前模型數據清除，操作完成則相關數據區呈空白狀態。‘求解命令按鈕即啟動具體的基可行解求解處理過程，其背后的程序代碼相對較多，鑒于篇幅所限本文從略。就圖2所示之LP模型，經‘求解處理完成后，其最優解為28，對應的基序號為7，對應的可行基為（P1，P2，P4），其基解為：X （7） =（6，2，0，6，0）T ，如圖3所示。

“列表”命令按鈕可將經該模塊求解出來的所有基之對應情況以表格的形式列出（如圖4），便于操作者對比分析之，以進一步理解LP求解之原理等諸多細節。

當然，在該系統中，標準化之后即可選擇性地使用基可行解法或單純形解法，但基于本文所關注的重點所限，單純法求解等仿真模擬過程不再贅述。鑒于水平所限，不妥和錯誤之處，敬請批評指正。

參考文獻：

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

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

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

【通聯編輯：謝媛媛】