LP之基可行求解算法教輔軟件設(shè)計(jì)與實(shí)現(xiàn)

摘要：在線性規(guī)劃求解過(guò)程中，基可行求解算法是個(gè)非常重要的知識(shí)點(diǎn)，它向上承接模型標(biāo)準(zhǔn)化過(guò)程，向下則為后續(xù)的單純形求解算法做理論基礎(chǔ)，故在教學(xué)中分量較重。為提高教學(xué)效果，筆者開(kāi)發(fā)了《軍事運(yùn)籌原理仿真模擬系統(tǒng)》，其中涉及了線性規(guī)劃模型的基可行求解算法仿真問(wèn)題，經(jīng)教學(xué)實(shí)用，效果良好。

關(guān)鍵詞：LP;模型;基;仿真

中圖分類號(hào)：TP312 ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：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來(lái)描述問(wèn)題之實(shí)施方案，且存在一組線性等式（或不等式）來(lái)表示的限制條件，還有一個(gè)可用決策變量的線性函數(shù)來(lái)表示追求目標(biāo)（或求最大化，抑或是最小），則此類問(wèn)題之求解理論即線性規(guī)劃（linear programming，簡(jiǎn)稱LP）。

1 LP標(biāo)準(zhǔn)型

LP求解算法較多，為方便可規(guī)定LP之?dāng)?shù)學(xué)模型的標(biāo)準(zhǔn)形式如圖1所示。

2 基可行求解

3 基可行解仿真實(shí)現(xiàn)

基可行求解是筆者設(shè)計(jì)開(kāi)發(fā)之《軍事運(yùn)籌學(xué)原理仿真模擬系統(tǒng)》中的一個(gè)子模塊，假設(shè)給定的LP抽象模型如圖2所示。

則經(jīng)該系統(tǒng)之標(biāo)準(zhǔn)化處理之后，再調(diào)用基可行求解處理模塊，則系統(tǒng)界面如圖2所示。

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

“列表”命令按鈕可將經(jīng)該模塊求解出來(lái)的所有基之對(duì)應(yīng)情況以表格的形式列出（如圖4），便于操作者對(duì)比分析之，以進(jìn)一步理解LP求解之原理等諸多細(xì)節(jié)。

當(dāng)然，在該系統(tǒng)中，標(biāo)準(zhǔn)化之后即可選擇性地使用基可行解法或單純形解法，但基于本文所關(guān)注的重點(diǎn)所限，單純法求解等仿真模擬過(guò)程不再贅述。鑒于水平所限，不妥和錯(cuò)誤之處，敬請(qǐng)批評(píng)指正。

參考文獻(xiàn)：

[1] 《運(yùn)籌學(xué)》教材編寫(xiě)組.運(yùn)籌學(xué)：本科版[M].北京：清華大學(xué)出版社，2005.

[2] 曹迎槐，尹健，梁春美.軍事運(yùn)籌學(xué)[M].北京：國(guó)防工業(yè)出版社，2013.

[3] 曹迎槐.LP模型標(biāo)準(zhǔn)化教輔軟件設(shè)計(jì)與實(shí)現(xiàn)[J].電腦知識(shí)與技術(shù)，2018，14（17）：87-88.

【通聯(lián)編輯：謝媛媛】