單純形法在線性規(guī)劃中的應(yīng)用

1、單純形法在線性規(guī)劃中的應(yīng)用0引言20世紀(jì)30年代末，蘇聯(lián)數(shù)學(xué)家康特羅維奇研究交通運(yùn)輸及機(jī)械加工等部門的生產(chǎn)管理工作，于1939年寫了生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法一書初稿，為線性規(guī)劃建立數(shù)學(xué)模型及解法奠定基礎(chǔ),自此開始，線性規(guī)劃經(jīng)過不斷的應(yīng)用和發(fā)展，在工業(yè)、農(nóng)業(yè)生產(chǎn)管理，交通運(yùn)輸?shù)闹笓]調(diào)度，資源開發(fā)，商業(yè)和銀行等領(lǐng)域得到廣泛應(yīng)用，顯著提高了企業(yè)的經(jīng)濟(jì)效益。隨著生產(chǎn)規(guī)模的擴(kuò)大和經(jīng)濟(jì)事務(wù)變得日益繁雜，對(duì)線性規(guī)劃提出了更多的理論要求，又促使這門學(xué)科迅速發(fā)展和完善。線性規(guī)劃不斷發(fā)展，適用領(lǐng)域不斷拓寬，從解決技術(shù)問題的最優(yōu)化設(shè)計(jì)，到工業(yè)、農(nóng)業(yè)、商業(yè)、交通運(yùn)輸業(yè)、軍事、經(jīng)濟(jì)計(jì)劃及管理等領(lǐng)域都發(fā)生著作用，已成為

2、現(xiàn)代科學(xué)管理的重要基礎(chǔ)理論。例如，在生產(chǎn)管理和經(jīng)濟(jì)活動(dòng)中，經(jīng)常遇到這些問題，如生產(chǎn)計(jì)劃問題，即如何合理利用有限的人、財(cái)、物等資源，以便得到最好的經(jīng)濟(jì)效果；材料利用問題，即如何下料使用材最少；配料問題，即在原料供應(yīng)量的限制下如何獲取最大利潤(rùn)；勞動(dòng)力安排問題，即如何用最少的勞動(dòng)力來滿足工作的需要；運(yùn)輸問題，即如何制定調(diào)運(yùn)方案，使總運(yùn)費(fèi)最??；投資問題，即從投資項(xiàng)目中選取方案，使投資回報(bào)最大等等。對(duì)于這些問題，都能建立相應(yīng)的線性規(guī)劃模型。事實(shí)上，線性規(guī)劃就是利用數(shù)學(xué)為工具，來研究在一定條件下，如何實(shí)現(xiàn)目標(biāo)最優(yōu)化。解線性規(guī)劃問題目前最常見的方法有兩種，圖解法和單純形法。單純形法是求解線性規(guī)劃問題的通用方

3、法。1 線性規(guī)劃問題的求解方法1.1 圖解法解線性規(guī)劃問題只含兩個(gè)變量的線性規(guī)劃問題，可以通過在平面上作圖的方法求解，步驟如下：(1) 以變量x1為橫坐標(biāo)軸，x2為縱坐標(biāo)軸，適當(dāng)選取單位坐標(biāo)長(zhǎng)度建立平面坐標(biāo)直角坐標(biāo)系。由變量的非負(fù)性約束性可知，滿足該約束條件的解均在第一象限內(nèi)。(2) 圖示約束條件，找出可行域（所有約束條件共同構(gòu)成的圖形）。(3) 畫出目標(biāo)函數(shù)等值線，并確定函數(shù)增大（或減小）的方向。(4) 可行域中使目標(biāo)函數(shù)達(dá)到最優(yōu)的點(diǎn)即為最優(yōu)解。然而，由于圖解法不適用于求解大規(guī)模的線性規(guī)劃問題，其實(shí)用意義不大。1.2 單純形法解線性規(guī)劃問題它的理論根據(jù)是：線性規(guī)劃問題的可行域是 n維向量空間

4、rn中的多面凸集，其最優(yōu)值如果存在必在該凸集的某頂點(diǎn)處達(dá)到。頂點(diǎn)所對(duì)應(yīng)的可行解稱為基本可行解。單純形法的基本思想是：先找出一個(gè)基本可行解，對(duì)它進(jìn)行鑒別，看是否是最優(yōu)解；若不是，則按照一定法則轉(zhuǎn)換到另一改進(jìn)的基本可行解,再鑒別；若仍不是，則再轉(zhuǎn)換,按此重復(fù)進(jìn)行。因基本可行解的個(gè)數(shù)有限，故經(jīng)有限次轉(zhuǎn)換必能得出問題的最優(yōu)解。如果問題無最優(yōu)解也可用此法判別。單純形法的一般解題步驟可歸納如下：把線性規(guī)劃問題的約束方程組表達(dá)成典范型方程組，找出基本可行解作為初始基本可行解。若基本可行解不存在，即約束條件有矛盾，則問題無解。若基本可行解存在，從初始基本可行解作為起點(diǎn)，根據(jù)最優(yōu)性條件和可行性條件，引入非基變量

5、取代某一基變量，找出目標(biāo)函數(shù)值更優(yōu)的另一基本可行解。按步驟3進(jìn)行迭代,直到對(duì)應(yīng)檢驗(yàn)數(shù)滿足最優(yōu)性條件（這時(shí)目標(biāo)函數(shù)值不能再改善），即得到問題的最優(yōu)解。若迭代過程中發(fā)現(xiàn)問題的目標(biāo)函數(shù)值無界，則終止迭代。1.3 線性規(guī)劃問題的標(biāo)準(zhǔn)化使用單純形法求解線性規(guī)劃時(shí)，首先要化問題為標(biāo)準(zhǔn)形式所謂標(biāo)準(zhǔn)形式是指下列形式：當(dāng)實(shí)際模型非標(biāo)準(zhǔn)形式時(shí)，可以通過以下變換化為標(biāo)準(zhǔn)形式：當(dāng)目標(biāo)函數(shù)為時(shí)，可令z=-z，而將其寫成為求得最終解時(shí)，再求逆變換z=-z即可。當(dāng)st中存在形式的約束條件時(shí)，可引進(jìn)變量便寫原條件成為其中的xn+1稱為松馳變量，其作用是化不等式約束為等式約束。同理，若該約束不是用“”號(hào)連接，而是用“”連接，則

6、可引進(jìn)松馳變量使原條件寫成2 單純形法2.1 單純形法的基本原理單純形法迭代原理：（1） 確定初始可行解 當(dāng)線性規(guī)劃問題的所有約束條件均為號(hào)時(shí)，松弛變量對(duì)應(yīng)的系數(shù)矩陣即為單位矩陣，以松弛變量為基變量可確定基可行解。 對(duì)約束條件含號(hào)或=號(hào)時(shí)，可構(gòu)造人工基，人為產(chǎn)生一個(gè)mm單位矩陣用大m法或兩階段法獲得初始基可行解。（2） 最優(yōu)性檢驗(yàn)與解的判別（目標(biāo)函數(shù)極大型） 當(dāng)所有變量對(duì)應(yīng)的檢驗(yàn)數(shù)均非正時(shí)，現(xiàn)有的基可行解即為最優(yōu)解。若存在某個(gè)非基變量的檢驗(yàn)數(shù)為零時(shí)，線性規(guī)劃問題有無窮多最優(yōu)解；當(dāng)所有非基變量的檢驗(yàn)數(shù)均嚴(yán)格小于零時(shí)，線性規(guī)劃問題具有唯一最優(yōu)解。 若存在某個(gè)非基變量的檢驗(yàn)數(shù)大于零，而該非基變量對(duì)應(yīng)

7、的系數(shù)均非正，則該線性規(guī)劃問題具有無界解（無最優(yōu)解）。 當(dāng)存在某些非基變量的檢驗(yàn)數(shù)大于零，需要找一個(gè)新的基可行解，基要進(jìn)行基變換。2.1 確定初始可行解確定初始的基本可行解等價(jià)于確定初始的可行基，一旦初始的可行基確定了，那么對(duì)應(yīng)的初始基本可行解也就唯一確定，為了討論方便，不妨假設(shè)在標(biāo)準(zhǔn)型線性規(guī)劃中，系數(shù)矩陣中前m個(gè)系數(shù)列向量恰好構(gòu)成一個(gè)可行基，即=（），其中=（1，2，m）為基變量x1，x2，xm的系數(shù)列向量構(gòu)成的可行基，=(m+1，pm+2， pn)為非基變量xm+1，xm+2， xn的系數(shù)列向量構(gòu)成的矩陣。所以約束方程就可以表示為用可行基的逆陣-1左乘等式兩端，再通過移項(xiàng)可推得：若令所有非

8、基變量，則基變量由此可得初始的基本可行解2.2 最優(yōu)性檢驗(yàn)假如已求得一個(gè)基本可行解，將這一基本可行解代入目標(biāo)函數(shù)，可求得相應(yīng)的目標(biāo)函數(shù)值其中分別表示基變量和非基變量所對(duì)應(yīng)的價(jià)值系數(shù)子向量。要判定是否已經(jīng)達(dá)到最大值，只需將代入目標(biāo)函數(shù)，使目標(biāo)函數(shù)用非基變量表示，即： 其中稱為非基變量n的檢驗(yàn)向量，它的各個(gè)分量稱為檢驗(yàn)數(shù)。若n的每一個(gè)檢驗(yàn)數(shù)均小于等于0，即n0，那么現(xiàn)在的基本可行解就是最優(yōu)解。2.3 解的判別定理1：最優(yōu)解判別定理對(duì)于線性規(guī)劃問題，若某個(gè)基本可行解所對(duì)應(yīng)的檢驗(yàn)向量，則這個(gè)基本可行解就是最優(yōu)解。定理2：無窮多最優(yōu)解判別定理 若是一個(gè)基本可行解，所對(duì)應(yīng)的檢驗(yàn)向量，其中存在一個(gè)檢驗(yàn)數(shù)m+

9、k=0，則線性規(guī)劃問題有無窮多最優(yōu)解。定理3：無最優(yōu)解判別定理若是一個(gè)基本可行解，有一個(gè)檢驗(yàn)數(shù)，但是，則該線性規(guī)劃問題無最優(yōu)解。2.4 基本可行解的改進(jìn)如果現(xiàn)行的基本可行解不是最優(yōu)解，即在檢驗(yàn)向量中存在正的檢驗(yàn)數(shù)，則需在原基本可行解的基礎(chǔ)上尋找一個(gè)新的基本可行解，并使目標(biāo)函數(shù)值有所改善。具體做法是：（1）先從檢驗(yàn)數(shù)為正的非基變量中確定一個(gè)換入變量，使它從非基變量變成基變量（將它的值從零增至正值）。（2）再?gòu)脑瓉淼幕兞恐写_定一個(gè)換出變量，使它從基變量變成非基變量（將它的值從正值減至零）。由此可得一個(gè)新的基本可行解，由可知，這樣的變換一定能使目標(biāo)函數(shù)值有所增加。2.4.1 換入變量的確定-最大增

10、加原則把基檢驗(yàn)數(shù)大于0的非基變量定為入基變量。若有兩個(gè)以上的j0，則選其中的j最大者的非基變量為入基變量。從最優(yōu)解判別定理知道，當(dāng)某個(gè)j0時(shí)，非基變量xj變?yōu)榛兞坎蝗×阒悼梢允鼓繕?biāo)函數(shù)值增大，故我們要選基檢驗(yàn)數(shù)大于0的非基變量換到基變量中去（稱之為入基變量）。若有兩個(gè)以上的j0，則為了使目標(biāo)函數(shù)增加得更大些，一般選其中的j最大者的非基變量為入基變量。2.4.2 換出變量的確定-最小比值原則把已確定的入基變量在各約束方程中的正的系數(shù)除以其所在約束方程中的常數(shù)項(xiàng)的值，把其中最小比值所在的約束方程中的原基變量確定為出基變量。即若則應(yīng)令xl出基。其中bi是目前解的基變量取值，aik是進(jìn)基變量xk所在

11、列的各個(gè)系數(shù)分量，要求僅對(duì)正分量做比，（這由前述作法可知，若aik0，則對(duì)應(yīng)的xi不會(huì)因xk的增加減值而成為出基變量）。2.5 表格單純形法在單純形法的求解過程中，有下列重要指標(biāo)：（1）每一個(gè)基本可行解的檢驗(yàn)向量，根據(jù)檢驗(yàn)向量可以確定所求得的基本可行解是否為最優(yōu)解。如果不是最優(yōu)又可以通過檢驗(yàn)向量確定合適的換入變量。（2）每一個(gè)基本可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值 ，通過目標(biāo)函數(shù)值可以觀察單純形法的每次迭代是否能使目標(biāo)函數(shù)值有效地增加，直至求得最優(yōu)目標(biāo)函數(shù)為止。 在單純形法求解過程中，每一個(gè)基本可行解都以某個(gè)經(jīng)過初等行變換的約束方程組中的單位矩陣為可行基。當(dāng)=時(shí)，-1=，易知：，可將這些重要結(jié)論的計(jì)算設(shè)

12、計(jì)成如下一個(gè)簡(jiǎn)單的表格，即單純形表來完成： ccbcncbxbbx1 x2 xmxm+1 xm+2 xnc1c2cmx1x2xmb1b2bmin12mzcbb0c-cbn2.6 大m法大m法首先將線性規(guī)劃問題化為標(biāo)準(zhǔn)型。如果約束方程組中包含有一個(gè)單位矩陣i，那么已經(jīng)得到了一個(gè)初始可行基。否則在約束方程組的左邊加上若干個(gè)非負(fù)的人工變量，使人工變量對(duì)應(yīng)的系數(shù)列向量與其它變量的系數(shù)列向量共同構(gòu)成一個(gè)單位矩陣。以單位矩陣為初始基，即可求得一個(gè)初始的基本可行解。為了求得原問題的初始基本可行解，必須盡快通過迭代過程把人工變量從基變量中替換出來成為非基變量。為此可以在目標(biāo)函數(shù)中賦予人工變量一個(gè)絕對(duì)值很大的負(fù)

13、系數(shù)-。這樣只要基變量中還存在人工變量，目標(biāo)函數(shù)就不可能實(shí)現(xiàn)極大化。以后的計(jì)算與單純形表解法相同，只需認(rèn)定是一個(gè)很大的正數(shù)即可。假如在單純形最優(yōu)表的基變量中還包含人工變量，則說明原問題無可行解。否則最優(yōu)解中剔除人工變量的剩余部分即為原問題的初始基本可行解。2.7 單純形法程序設(shè)計(jì)完整的單純形法的計(jì)算程序設(shè)計(jì)框圖如下所示：圖1 單純形法程序框圖3 應(yīng)用實(shí)例3.1 有最優(yōu)解問題例1 求如下方程的最優(yōu)解在命令行輸入： a=1 2 2 1 0;3 4 1 0 1;b=8;7;c=5 2 3 -1 1; simplemethod(a,b,c);即可得出結(jié)果：x = 1.2000 0 3.4000 0 0

14、 0 0最大值為：z = 16.2000迭代次數(shù)：i = 4程序結(jié)果與例題結(jié)果一致。例2 求解下述線性規(guī)劃問題在命令窗口輸入： a=1 1;2 1;b=40;60;c=3 2; simplemethod(a,b,c);即可得到結(jié)果：已得到最優(yōu)解：x = 20 20 0 0最大值為：z = 100迭代次數(shù)：i = 4程序結(jié)果與例題結(jié)果一致。例3 利用大m法求解下述線性規(guī)劃問題在命令窗口輸入： a=1 1;-1 1;0 1;b=2;1;3;c=-1 2;sign=1 1 -1; simplemethod(a,b,c,sign);結(jié)果如下：已得到最優(yōu)解：x = 0 3 1 2 0 0 0最大值為：z

15、 = 6迭代次數(shù)：i = 6與例題結(jié)果一致。3.2 無可行解問題通過大法或兩階段法求初始的基本可行解。但是如果在大法的最優(yōu)單純形表的基變量中仍含有人工變量，人工變量的值不能取零，說明了原線性規(guī)劃的數(shù)學(xué)模型的約束條件出現(xiàn)了相互矛盾的約束方程，此時(shí)線性規(guī)劃問題也無最優(yōu)解。例4 利用大m法求解下述線性規(guī)劃問題在命令窗口輸入： a=1 1 1;1 0 -1;0 1 -1;b=6;4;3;c=-3 -2 -1;sign=-1 1 1; simplemethod(a,b,c,sign);結(jié)果輸出“此問題無可行解”。3.3 無最優(yōu)解問題無最優(yōu)解則是指線性規(guī)劃問題存在可行解，但是可行解的目標(biāo)函數(shù)達(dá)不到最優(yōu)值，

16、即目標(biāo)函數(shù)在可行域內(nèi)可以趨于無窮大（或者無窮?。?。無最優(yōu)解也稱為有限最優(yōu)解，或無界解。判別方法：無最優(yōu)解判別定理在求解極大化的線性規(guī)劃問題過程中，若某單純形表的檢驗(yàn)行存在某個(gè)大于零的檢驗(yàn)數(shù)，但是該檢驗(yàn)數(shù)所對(duì)應(yīng)的非基變量的系數(shù)列向量的全部系數(shù)都為負(fù)數(shù)或零，則該線性規(guī)劃問題無最優(yōu)解。例5求解下述線性規(guī)劃問題在命令窗口輸入： a=1 -1;-3 2;b=1;6;c=1 1; simplemethod(a,b,c);結(jié)果輸出“此問題無最優(yōu)解或有無界解”。4 總結(jié)本文程序雖能解決簡(jiǎn)單線性規(guī)劃問題，但對(duì)于存在退化解問題卻不能做出解答。還有些實(shí)際問題會(huì)做出錯(cuò)誤解答，因此還需進(jìn)一步改進(jìn)。通過本次學(xué)習(xí)單純形法，

17、我對(duì)單純形法中的基本概念如基變量、非基變量、基向量、非基向量、可行基以及基本可行解等概念有了初步了解。在理解了單純形法的解題步驟的基礎(chǔ)上，編寫了一個(gè)求解簡(jiǎn)單線性規(guī)劃問題的單純形法程序，更加深化了單純形法的理解。下面是贈(zèng)送的中秋節(jié)演講辭，不需要的朋友可以下載后編輯刪除！謝謝中秋佳節(jié)演講詞推薦中秋,懷一顆感恩之心老師們，同學(xué)們：秋濃了，月圓了，又一個(gè)中秋要到了!本周日，農(nóng)歷的八月十五，我國(guó)的傳統(tǒng)節(jié)日中秋節(jié)。中秋節(jié)，處在一年秋季的中期，所以稱為“中秋”，它僅僅次于春節(jié)，是我國(guó)的第二大傳統(tǒng)節(jié)日。中秋的月最圓，中秋的月最明，中秋的月最美，所以又被稱為“團(tuán)圓節(jié)”。金桂飄香，花好月圓，在這美好的節(jié)日里，人們

18、賞月、吃月餅、走親訪友無論什么形式，都寄托著人們對(duì)生活的無限熱愛和對(duì)美好生活的向往。中秋是中華瑰寶之一，有著深厚的文化底蘊(yùn)。中國(guó)人特別講究親情，特別珍視團(tuán)圓，中秋節(jié)尤為甚。中秋，是一個(gè)飄溢親情的節(jié)日;中秋，是一個(gè)彌漫團(tuán)圓的時(shí)節(jié)。這個(gè)時(shí)節(jié)，感受親情、釋放親情、增進(jìn)親情;這個(gè)時(shí)節(jié)，盼望團(tuán)圓、追求團(tuán)圓、享受團(tuán)圓這些，都已成為人們生活的主旋律。同學(xué)們，一定能背誦出許多關(guān)于中秋的千古佳句，比如“舉頭望明月，低頭思故鄉(xiāng)”、“但愿人長(zhǎng)久，千里共嬋娟”、“海上生明月，天涯共此時(shí)”這些佳句之所以能穿透歷史的時(shí)空流傳至今，不正是因?yàn)槲覀內(nèi)祟愑兄墓餐拍顔?。中秋最美是親情。一家人團(tuán)聚在一起，講不完的話，敘不完的情

19、，訴說著人們同一個(gè)心聲：親情是黑暗中的燈塔，是荒漠中的甘泉，是雨后的彩虹中秋最美是思念。月亮最美，美不過思念;月亮最高，高不過想念。中秋圓月會(huì)把我們的目光和思念傳遞給我們想念的人和我們牽掛的人，祝他們沒有憂愁，永遠(yuǎn)幸福，沒有煩惱，永遠(yuǎn)快樂! 一、活動(dòng)主題：游名校、賞名花，促交流，增感情二、活動(dòng)背景：又到了陽春三月，陽光明媚，微風(fēng)吹拂，正是踏青春游的好時(shí)節(jié)。借春天萬物復(fù)蘇之際，我們?nèi)嗑奂谝黄?，彼此多一點(diǎn)接觸，多一點(diǎn)溝通，共話美好未來，與此同時(shí)，也可以緩解一下緊張的學(xué)習(xí)壓力。 相信在這次春游活動(dòng)中，我們也能更親近的接觸自然，感悟自然，同時(shí)吸收萬物之靈氣的同時(shí)感受名校的人文氣息。三、活動(dòng)目的：1

20、. 豐富同學(xué)們的校園生活，陶冶情操。2. 領(lǐng)略優(yōu)美自然風(fēng)光，促進(jìn)全班同學(xué)的交流，營(yíng)造和諧融洽的集體氛圍。 3. 為全體同學(xué)營(yíng)造一種輕松自由的氣氛，又可以加強(qiáng)同學(xué)們的團(tuán)隊(duì)意識(shí)。 4. 有效的利用活動(dòng)的過程及其形式，讓大家感受到我們班級(jí)的發(fā)展和進(jìn)步。四、活動(dòng)時(shí)間：xx年3月27日星期四五、活動(dòng)參與對(duì)象：房產(chǎn)q1141全體及“家屬”六、活動(dòng)地點(diǎn)：武漢市華中農(nóng)業(yè)大學(xué)校內(nèi)七、活動(dòng)流程策劃：1、27日8點(diǎn)在校訓(xùn)時(shí)集合，乘車2、9點(diǎn)前往華農(nóng)油菜基地、果園，賞花攝影3、10點(diǎn)30，回農(nóng)家樂開始做飯，進(jìn)行“我是廚王”大比拼4、1點(diǎn)30，收拾食品殘物，開始集體活動(dòng)5、4點(diǎn)，乘車返校八、職能分工及責(zé)任定崗1、調(diào)研組：負(fù)責(zé)前期的選址、策劃的撰寫、實(shí)地考察、交通工具的聯(lián)系和檢驗(yàn)組長(zhǎng)：金雄成員：吳開慧2、安全保衛(wèi)組：負(fù)責(zé)登記參加春游的人數(shù)，乘車前的人數(shù)的登記，集體活動(dòng)時(shí)同學(xué)的請(qǐng)假的審批，安全知識(shí)的培訓(xùn)與教育，午餐制作的人員分組組長(zhǎng)：徐楊超成員：王沖3、食材采購(gòu)組：根據(jù)春游的人數(shù)和預(yù)算費(fèi)用合理購(gòu)買食材組長(zhǎng)：胡晴瑩成員：何曉藝4、活動(dòng)組織組：在車上、賞花期間、主要是做飯完后的集體活動(dòng)期間的活動(dòng)的組織組長(zhǎng)：武男成員：馮薏