LP之單純形法教輔軟件設(shè)計(jì)與實(shí)現(xiàn)

曹迎槐　張靜　趙強(qiáng)

摘要：在線性規(guī)劃理論中，單純形法是非常經(jīng)典的求解算法，但它計(jì)算復(fù)雜，涉及數(shù)據(jù)較多，掌握相對(duì)困難，為提高教學(xué)效果，筆者開發(fā)了《軍事運(yùn)籌原理仿真模擬系統(tǒng)》，其中涉及了線性規(guī)劃模型的單純形求解算法仿真問(wèn)題，經(jīng)教學(xué)實(shí)用，效果良好。

關(guān)鍵詞：LP;模型;單純形法;仿真

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

文章編號(hào)：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

目前，在運(yùn)籌學(xué)之線性規(guī)劃（linear programming，簡(jiǎn)稱LP）分支中，最經(jīng)典的求解算法就是單純形法，它既是運(yùn)籌學(xué)教材之重點(diǎn)，也是教學(xué)之難點(diǎn)所在。但該算法相對(duì)復(fù)雜，計(jì)算過(guò)程煩瑣，學(xué)生掌握相對(duì)困難，為此，筆者開發(fā)了該算法的求解仿真軟件，教學(xué)效果良好。

1單純形法的求解步驟

單純形法和基于窮舉思想的基可行解法不同，它不需要求出所有的基可行解，而是以LP模型之標(biāo)準(zhǔn)形式為出發(fā)點(diǎn)先求出一個(gè)基可行解，并檢驗(yàn)其是否為最優(yōu)解。如果它已最優(yōu)，則求解結(jié)束，算法終止;如果它不是最優(yōu)解，就按照算法給定的方法求出另一個(gè)基可行解，該算法可以保證新求出的基可行解肯定要優(yōu)于上一個(gè)基可行解。只要LP問(wèn)題存在最優(yōu)解，就一定可通過(guò)有限次的運(yùn)算求出最優(yōu)解。如果，所求的問(wèn)題不存在有限的最優(yōu)解（即無(wú)解），則該算法也有相應(yīng)法則判斷之。

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

1.1確定初始基可行解

確定出初始（即第一個(gè)）可行基時(shí)，因標(biāo)準(zhǔn)化處理中多加入松弛變量，所以，初始基可行解的確定往往并不困難，一般直接選取各松弛變量即可。當(dāng)然，若個(gè)別約束方程未添加松弛變量，亦可借助線性代數(shù)知識(shí)，通過(guò)行或列的交換等操作來(lái)得到。

1.2最優(yōu)解檢驗(yàn)

檢驗(yàn)初始基可行解是否最優(yōu)。若是最優(yōu)解，則停止運(yùn)算;若不是最優(yōu)解，就轉(zhuǎn)下一步。

1.3無(wú)解檢驗(yàn)

當(dāng)檢驗(yàn)初始基可行解不是最優(yōu)解時(shí)，繼續(xù)檢驗(yàn)該規(guī)劃問(wèn)題是否無(wú)解（即無(wú)有限的最優(yōu)解）。若無(wú)解則停止運(yùn)算，若依然無(wú)法判定是否無(wú)解則轉(zhuǎn)下一步。

1.4基變換

當(dāng)經(jīng)過(guò)上面的兩種檢驗(yàn)發(fā)現(xiàn)，該基可行解既不最優(yōu)，也不能判定其無(wú)解，則需要尋找另一個(gè)基可行解。即在該可行基之基礎(chǔ)上，先從原非基變量中選一個(gè)變量，稱換人變量;再于原基變量中選擇一個(gè)變量使其成為非基變量，稱之為換出變量。于是，新的基變量對(duì)應(yīng)的系數(shù)列向量，同原來(lái)保持不變的基變量對(duì)應(yīng)的系數(shù)列向量（m-1）個(gè)，就組成一個(gè)新的可行基，此即基變換。

1.5旋轉(zhuǎn)運(yùn)算

基變換完成后，需進(jìn)一步求出其相應(yīng)的新基可行解，該過(guò)程即旋轉(zhuǎn)運(yùn)算。然后，轉(zhuǎn)步驟12。

單純行法的求解算法亦可用傳統(tǒng)流程圖來(lái)描述，在仿真實(shí)現(xiàn)中如圖1所示。

2單純形表

利用單純形法求解LP問(wèn)題，涉及大量的數(shù)值計(jì)算，且各數(shù)值之間關(guān)系復(fù)雜，種類繁多，為簡(jiǎn)明其見，通常是列表（稱為單純形表，見圖2）進(jìn)行。一般地，單純形表中應(yīng)考慮以下數(shù)據(jù)：

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

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

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

4）目標(biāo)函數(shù)中各變量的價(jià)值系數(shù)cj（j=1，2，…，n），填入Cj列，如圖2上部第1行;

5）規(guī)劃模型之各基向量，Pj（j=1，2，…，n），填人xj行下面的對(duì)應(yīng)區(qū)域，如圖2上部中間區(qū)域;

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

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

3單純形法求解仿真

單純形法仿真求解是筆者設(shè)計(jì)開發(fā)之《軍事運(yùn)籌學(xué)原理仿真模擬系統(tǒng)》中的一個(gè)子模塊，假設(shè)給定的LP問(wèn)題之標(biāo)準(zhǔn)型如圖2下半部區(qū)域所示。其中涉及目標(biāo)函數(shù)系數(shù)、約束方程系數(shù)矩陣、資源列向量、未知變量個(gè)數(shù)、約束方程個(gè)數(shù)等。

界面最底部的文字用來(lái)描述仿真求解過(guò)程中相關(guān)操作信息。而“導(dǎo)入”按鈕則可將已標(biāo)準(zhǔn)化的LP模型納入單純形法求解仿真模塊，導(dǎo)人操作剛完成時(shí)，并沒(méi)有圖2界面中上半部分單純形表中的相關(guān)數(shù)據(jù)，這些數(shù)據(jù)是在求解過(guò)程中隨著各步操作的進(jìn)行而出現(xiàn)并動(dòng)態(tài)變化的?！扒宄卑粹o則可將該仿真模塊中的LP數(shù)據(jù)清空，屆時(shí)整個(gè)仿真界面呈現(xiàn)空白狀態(tài)。

本仿真模塊的求解分兩種模式，一是“分步求解”，一是“連續(xù)求解”。當(dāng)LP模型數(shù)據(jù)導(dǎo)入完成后，即可通過(guò)單擊“分步求解”按鈕，啟動(dòng)單純形求解之第一步“確定初始可行基”，該步完成則同時(shí)填充該界面上半部分的“單純形表”之相關(guān)區(qū)域，并將“分步求解按鈕上的文字變?yōu)椤跋乱徊健?，如圖2所示。此后，可依次單擊“下一步”按鈕，則求解過(guò)程中各相關(guān)數(shù)據(jù)的變化即體現(xiàn)在該界面上半部分的單純形表相關(guān)區(qū)域中。

持續(xù)單擊“下一步”按鈕，如果該LP模型存在最優(yōu)解，則求解完成時(shí)，最優(yōu)解出現(xiàn)在相應(yīng)位置，同時(shí)“下一步”命令按鈕變?yōu)椤胺植角蠼狻?，如圖3所示。

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

“連續(xù)求解”按鈕可從導(dǎo)入標(biāo)準(zhǔn)化模型開始，直達(dá)最后得到求解結(jié)果，中間的各步信息也不再顯示在界面的底部，界面上半部直接顯示最優(yōu)解，這里不再贅述。

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

當(dāng)然，在該仿真模塊中，標(biāo)準(zhǔn)化之后LP模型未必能直接得出初始可行基，此時(shí)可借助大M法或兩階段法求解之。另外，如果LP模型無(wú)解，仿真模塊同樣會(huì)給出相關(guān)反饋信息。鑒于篇幅這里不再詳述。因水平所限，不妥和錯(cuò)誤之處，敬請(qǐng)大家批評(píng)指正！

參考文獻(xiàn)：

[1]錢頌迪.運(yùn)籌學(xué)[M].北京：清華大學(xué)出版，1993.

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

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

[4]曹迎槐.LP之單純形法教輔軟件設(shè)計(jì)與實(shí)現(xiàn)[J].電腦知識(shí)與技術(shù)，2020（17）：63-64.

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

收稿日期：2020-05-08

作者簡(jiǎn)介：曹迎槐（1966-），男，河北蔚縣人，教授，技術(shù)5級(jí)，碩士，長(zhǎng)期從事計(jì)算機(jī)技術(shù)、運(yùn)籌建模、海警信息與情報(bào)等領(lǐng)域的教學(xué)與科研工作;張靜（1980-），女，遼寧大連人，副教授，碩士，從事信息安全專業(yè)教學(xué)工作;趙強(qiáng)（1976-），男，青海西寧人，講師，碩士，從事多媒體和信息技術(shù)專業(yè)教學(xué)和科研工作。