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確定初始基可行解

確定出初始（即第一個）可行基時，因標準化處理中多加入松弛變量，所以，初始基可行解的確定往往并不困難，一般直接選取各松弛變量即可。……