《運(yùn)籌學(xué)茹少峰課件》由會(huì)員分享，可在線閱讀，更多相關(guān)《運(yùn)籌學(xué)茹少峰課件（45頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),*,第三章 線性規(guī)劃的一般求解方法 單純形法,它的一般形式為：,其中，,，,是已知數(shù)，,是待決策的變量。,一、線性規(guī)劃問(wèn)題的一般形式,一般情況下,m,n,m,n,為正整數(shù),分別表示約束條件的個(gè)數(shù)和決策變量的個(gè)數(shù),稱(chēng)為約束條件(,Subject to)。,稱(chēng)為變量的非負(fù)約束條件。其余的變量可取正值、負(fù)值、或零值，稱(chēng)這樣的變量為符號(hào)無(wú)限制變量或自由變量。線性規(guī)劃模型的特征是：一組決策變量，一組約束條件。一個(gè)目標(biāo)函數(shù)。目標(biāo)函數(shù)和約束條件都是線性的。,由前面一般形式可知,線性規(guī)劃問(wèn)題可能有各種不同的形式。目標(biāo)函數(shù)有實(shí)現(xiàn)

2、最大化也有實(shí)現(xiàn)最小化的;約束條件可以是“,”形式、“”形式不等式,有的是等式,決策變量有時(shí)有非負(fù)限制有時(shí)沒(méi)有。這種多樣性給討論問(wèn)題代來(lái)了不便。為了便于今后討論，我們就要規(guī)定線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型,二、線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)行式是什么？如何將一個(gè),LP,問(wèn)題的一般形式轉(zhuǎn)換為標(biāo)準(zhǔn)形式,？(1)、,這里規(guī)定的標(biāo)準(zhǔn)形式為：,這里我們假設(shè),b,i,0(,i,=1,2,m,),否則兩端同時(shí)乘以“-1”。,簡(jiǎn)記為,：,用矩陣表示為,：,用列向量表示為：,（2）為了把一般形式的,LP,變換為標(biāo)準(zhǔn)形式，必須消除其不等式約束和符號(hào)無(wú)限制變量。,目標(biāo)函數(shù)的轉(zhuǎn)換,約束條件的轉(zhuǎn)換,變量的非負(fù)約束的轉(zhuǎn)換,任何形式的線性規(guī)劃數(shù)學(xué)

3、模型都可以轉(zhuǎn)換成標(biāo)準(zhǔn)型的線性規(guī)劃,例4:試將如下線性規(guī)劃問(wèn)題化成標(biāo)準(zhǔn)型,解：令,x,3,=,x,4,-,x,5,x,4,x,5,0,(1),式左端加上非負(fù)松弛變量,x,6,(2),式左端減去非負(fù)剩余變量,x,7,則可將上述線性規(guī)劃問(wèn)題化成如下的標(biāo)準(zhǔn)型:,三、什么是可行解、可行域，可行域的幾何結(jié)構(gòu)？,滿(mǎn)足所有約束條件的決策變量，稱(chēng)為可行解或可行點(diǎn)(,feasible point)。,使目標(biāo)函數(shù)值最大的可行解,稱(chēng),為最優(yōu)解,所有可行點(diǎn)組成的集合稱(chēng)為可行域（,feasible region），,記為,D.,給定一個(gè),LP,問(wèn)題,可行域,D,下列三種情況必居其一,D=,稱(chēng)該問(wèn)題無(wú)解或不可行。,D ,且

4、可行域有界。則線性規(guī)劃問(wèn)題一定存在最優(yōu)解。這時(shí)最優(yōu)解唯一，也可能有無(wú)窮多。,D ，,且可行域?yàn)闊o(wú)界，則線性規(guī)劃問(wèn)題或者有最優(yōu)解（唯一或無(wú)窮多）也可能沒(méi)有有限的最優(yōu)解。,當(dāng)可行域非空時(shí)，可行域的幾何結(jié)構(gòu)為(多面)凸集,四、基本解、基本可行解,(,basic solution、basic feasible solution),秩（,A）=m，,則矩陣,A,中存在一個(gè),m,階滿(mǎn)秩,子方陣,B。,稱(chēng),B,矩陣為線性規(guī)劃問(wèn)題的一個(gè)基。,解之間的關(guān)系,可行解：滿(mǎn)足約束條件,最優(yōu)解：滿(mǎn)足約束條件，同時(shí)使目標(biāo)函數(shù)值最優(yōu)。,基礎(chǔ)解：滿(mǎn)足 且非零分量的數(shù)目不大于方程的個(gè)數(shù),m。,基可行解：是基礎(chǔ)解又是可行解。,基

5、最優(yōu)解：滿(mǎn)足約束條件，且無(wú)非零分量，或非零分量對(duì)應(yīng)的列向量現(xiàn)性無(wú)關(guān)，同時(shí)使目標(biāo)函數(shù)值最優(yōu)。,五、,LP,問(wèn)題的幾何意義（單純形表的數(shù)學(xué)原理）,若線性規(guī)劃問(wèn)題存在可行域，則其可行域,D,是凸集,線性規(guī)劃問(wèn)題的可行解為基可行解的充要條件是的正分量所對(duì)應(yīng)的系數(shù)列向量線性無(wú)關(guān),。,X,是基本可行解的充分必要條件是,X,是可行域,D,的頂點(diǎn),一個(gè)標(biāo)準(zhǔn)的,LP,問(wèn)題，若有可行解，則至少有一個(gè)基本可行解,一個(gè)標(biāo)準(zhǔn)的,LP,問(wèn)題，若有有限的最優(yōu)值，則一定存在一個(gè)基本可行解是最優(yōu)解。,若線性規(guī)劃問(wèn)題存在可行域，則其可行域,D,是凸集,線性規(guī)劃問(wèn)題的可行解,X,為基可行解的充要條件是,X,的正分量所對(duì)應(yīng)的系數(shù)列向

6、量線性無(wú)關(guān),。,X,是基本可行解的充分必要條件是,X,是可行域,D,的頂點(diǎn),由以上定理可知，最優(yōu)解一定在某一基本可行解處達(dá)到。因此單純形法的基本思想是：先找一個(gè)基本可行解，然后判斷它是否為最優(yōu)解，如不是，就找一個(gè)更好的基本可行解，再進(jìn)行判斷，如此迭代進(jìn)行，直到找到最優(yōu)解或者判斷該問(wèn)題無(wú)界。,六、單純形法,(,Simplex method),1單純形表,為了計(jì)算的方便，我們可以將單純形法的全部計(jì)算過(guò)程在一個(gè)類(lèi)似增廣矩陣的數(shù)表上進(jìn)行，這種表格稱(chēng)單純形表，不同的教材設(shè)計(jì)表格稍有不同，這里設(shè)計(jì)如下：,2 單純形方法步驟,Step1,轉(zhuǎn)換一般的,LP,模型為標(biāo)準(zhǔn)型。,Step2,找一個(gè)初始可行基。,St

7、ep3,計(jì)算單純形表中的各矩陣。,Step4,構(gòu)造單純形表。,Step5,判斷最優(yōu)解，是，則結(jié)束。否 則，轉(zhuǎn)入下一步。,Step6,換基迭代，返回,Step5。,如何得到第一個(gè)基本可行解？,為了得到初始基本可行解，要首先找到初始基本可行基，設(shè),B,為約束矩陣的一個(gè),m,階子式，如果,B,非奇異，則矩陣,B,是一個(gè)基，進(jìn)一步，若 ，那么,B,是初始基本可行基。就是初始基本可行解。找初始基本可行基的方法如下1觀察法與試驗(yàn)法。2.大,M,法。3.兩階段法,如何判斷基本可行解是最優(yōu)解,？,對(duì)線性規(guī)劃問(wèn)題的求解結(jié)果可能出現(xiàn)唯一最優(yōu)解、無(wú)窮多最優(yōu)解、無(wú)界解和無(wú)可行解四種情況，,找入基變量,找出基變量,定軸

8、心項(xiàng),作行變換,交換變量,如何進(jìn)行換基迭代,掌握線性規(guī)劃問(wèn)題的數(shù)學(xué)原理及代數(shù)的單純形解法是學(xué)習(xí),LP,的最高境界。掌握這一方法對(duì)于以后的學(xué)習(xí)大有裨益，希望同學(xué)們發(fā)揚(yáng)十二分的耐心和鉆研精神。,例題、用單純形法求解,化為滿(mǎn)秩標(biāo)準(zhǔn)形,2、,寫(xiě)出初始單純形表,3、,判斷基本可行解是最優(yōu)解,由于檢驗(yàn)數(shù)有正數(shù)，且對(duì)應(yīng)的列向量不全為負(fù)，故進(jìn)行換基迭代，,4、換基迭代,選上表中的為軸心項(xiàng),5、判斷、,由于檢驗(yàn)數(shù)有正數(shù)且對(duì)應(yīng)的列向量不全為負(fù)，故進(jìn)行換基迭代，選上表中的為軸心項(xiàng),由單純形表得一基最優(yōu)解，由于有非基變量的檢驗(yàn)數(shù)為零，則此線性規(guī)劃有無(wú)窮解。選上表中的 為軸心項(xiàng).,原線性規(guī)劃所有最優(yōu)解為：,由此表的另一最優(yōu)解,所有最優(yōu)解為：,如何用,QM,軟件求解,LP,問(wèn)題,三角洲航空公司的航班配置問(wèn)題（怎樣為各條航線分配班機(jī)和為乘客分配座位）。用,LP,模型解決，用到60000個(gè)變量，40000個(gè)約束條件。,課堂練習(xí),A、,用單純形法求解兩個(gè)變量的,LP,問(wèn)題。,B、,用,QM,軟件求解,LP,問(wèn)題,END,謝謝,