第三章單純形

第三章單純形第1頁，課件共45頁，創(chuàng)作于2023年2月它的一般形式為：其中，,，是已知數(shù)，是待決策的變量。一、線性規(guī)劃問題的一般形式第2頁，課件共45頁，創(chuàng)作于2023年2月第3頁，課件共45頁，創(chuàng)作于2023年2月一般情況下m<n,m,n為正整數(shù),分別表示約束條件的個(gè)數(shù)和決策變量的個(gè)數(shù),稱為約束條件(Subjectto)。

稱為變量的非負(fù)約束條件。其余的變量可取正值、負(fù)值、或零值，稱這樣的變量為符號(hào)無限制變量或自由變量。

線性規(guī)劃模型的特征是：一組決策變量，一組約束條件。一個(gè)目標(biāo)函數(shù)。目標(biāo)函數(shù)和約束條件都是線性的。

第4頁，課件共45頁，創(chuàng)作于2023年2月由前面一般形式可知,線性規(guī)劃問題可能有各種不同的形式。目標(biāo)函數(shù)有實(shí)現(xiàn)最大化也有實(shí)現(xiàn)最小化的;約束條件可以是“”形式、“”形式不等式,有的是等式

決策變量有時(shí)有非負(fù)限制有時(shí)沒有。這種多樣性給討論問題代來了不便。為了便于今后討論，我們就要規(guī)定線性規(guī)劃問題的標(biāo)準(zhǔn)型第5頁，課件共45頁，創(chuàng)作于2023年2月二、線性規(guī)劃問題的標(biāo)準(zhǔn)行式是什么？

如何將一個(gè)LP問題的一般形式轉(zhuǎn)換為

標(biāo)準(zhǔn)形式？

(1)、這里規(guī)定的標(biāo)準(zhǔn)形式為：

第6頁，課件共45頁，創(chuàng)作于2023年2月

這里我們假設(shè)bi

0(i=1,2,···,m),否則兩端同時(shí)乘以“-1”。第7頁，課件共45頁，創(chuàng)作于2023年2月簡記為：第8頁，課件共45頁，創(chuàng)作于2023年2月用矩陣表示為：第9頁，課件共45頁，創(chuàng)作于2023年2月用列向量表示為：第10頁，課件共45頁，創(chuàng)作于2023年2月（2）為了把一般形式的LP變換為標(biāo)準(zhǔn)形式，必須消除其不等式約束和符號(hào)無限制變量。

目標(biāo)函數(shù)的轉(zhuǎn)換

約束條件的轉(zhuǎn)換

變量的非負(fù)約束的轉(zhuǎn)換

任何形式的線性規(guī)劃數(shù)學(xué)模型都可以轉(zhuǎn)換成標(biāo)準(zhǔn)型的線性規(guī)劃第11頁，課件共45頁，創(chuàng)作于2023年2月例4:試將如下線性規(guī)劃問題化成標(biāo)準(zhǔn)型解：令x3=x4-x5,x4,x5

0,(1)式左端加上非負(fù)松弛變量x6,(2)式左端減去非負(fù)剩余變量x7,則可將上述線性規(guī)劃問題化成如下的標(biāo)準(zhǔn)型:第12頁，課件共45頁，創(chuàng)作于2023年2月第13頁，課件共45頁，創(chuàng)作于2023年2月三、什么是可行解、可行域，可行域的幾何結(jié)構(gòu)？

滿足所有約束條件的決策變量，稱為可行解或可行點(diǎn)(feasiblepoint)。使目標(biāo)函數(shù)值最大的可行解稱為最優(yōu)解所有可行點(diǎn)組成的集合稱為可行域（feasibleregion），記為D.給定一個(gè)LP問題可行域D,下列三種情況必居其一第14頁，課件共45頁，創(chuàng)作于2023年2月

D=?稱該問題無解或不可行。

D?且可行域有界。則線性規(guī)劃問題一定存在最優(yōu)解。這時(shí)最優(yōu)解唯一，也可能有無窮多。

D?，且可行域?yàn)闊o界，則線性規(guī)劃問題或者有最優(yōu)解（唯一或無窮多）也可能沒有有限的最優(yōu)解。

當(dāng)可行域非空時(shí)，可行域的幾何結(jié)構(gòu)為(多面)凸集

第15頁，課件共45頁，創(chuàng)作于2023年2月四、基本解、基本可行解

(basicsolution、basicfeasiblesolution)秩（A）=m，則矩陣A中存在一個(gè)m階滿秩子方陣B。稱B矩陣為線性規(guī)劃問題的一個(gè)基。第16頁，課件共45頁，創(chuàng)作于2023年2月第17頁，課件共45頁，創(chuàng)作于2023年2月第18頁，課件共45頁，創(chuàng)作于2023年2月解之間的關(guān)系可行解：滿足約束條件 最優(yōu)解：滿足約束條件，同時(shí)使目標(biāo)函數(shù)值最優(yōu)?；A(chǔ)解：滿足且非零分量的數(shù)目不大于方程的個(gè)數(shù)m。 基可行解：是基礎(chǔ)解又是可行解?；顑?yōu)解：滿足約束條件，且無非零分量，或非零分量對(duì)應(yīng)的列向量現(xiàn)性無關(guān)，同時(shí)使目標(biāo)函數(shù)值最優(yōu)。

第19頁，課件共45頁，創(chuàng)作于2023年2月五、LP問題的幾何意義（單純形表的數(shù)學(xué)原理）

若線性規(guī)劃問題存在可行域，則其可行域D是凸集線性規(guī)劃問題的可行解為基可行解的充要條件是的正分量所對(duì)應(yīng)的系數(shù)列向量線性無關(guān)。X是基本可行解的充分必要條件是X是可行域D的頂點(diǎn)一個(gè)標(biāo)準(zhǔn)的LP問題，若有可行解，則至少有一個(gè)基本可行解一個(gè)標(biāo)準(zhǔn)的LP問題，若有有限的最優(yōu)值，則一定存在一個(gè)基本可行解是最優(yōu)解。第20頁，課件共45頁，創(chuàng)作于2023年2月若線性規(guī)劃問題存在可行域，則其可行域D是凸集第21頁，課件共45頁，創(chuàng)作于2023年2月線性規(guī)劃問題的可行解X為基可行解的充要條件是X的正分量所對(duì)應(yīng)的系數(shù)列向量線性無關(guān)。第22頁，課件共45頁，創(chuàng)作于2023年2月X是基本可行解的充分必要條件是X是可行域D的頂點(diǎn)

第23頁，課件共45頁，創(chuàng)作于2023年2月第24頁，課件共45頁，創(chuàng)作于2023年2月由以上定理可知，最優(yōu)解一定在某一基本可行解處達(dá)到。因此單純形法的基本思想是：先找一個(gè)基本可行解，然后判斷它是否為最優(yōu)解，如不是，就找一個(gè)更好的基本可行解，再進(jìn)行判斷，如此迭代進(jìn)行，直到找到最優(yōu)解或者判斷該問題無界。

六、單純形法(Simplexmethod)第25頁，課件共45頁，創(chuàng)作于2023年2月

1．單純形表

為了計(jì)算的方便，我們可以將單純形法的全部計(jì)算過程在一個(gè)類似增廣矩陣的數(shù)表上進(jìn)行，這種表格稱單純形表，不同的教材設(shè)計(jì)表格稍有不同，這里設(shè)計(jì)如下：第26頁，課件共45頁，創(chuàng)作于2023年2月2．

單純形方法步驟

Step1轉(zhuǎn)換一般的LP模型為標(biāo)準(zhǔn)型。Step2找一個(gè)初始可行基。Step3計(jì)算單純形表中的各矩陣。Step4構(gòu)造單純形表。Step5判斷最優(yōu)解，是，則結(jié)束。否則，轉(zhuǎn)入下一步。Step6換基迭代，返回Step5。第27頁，課件共45頁，創(chuàng)作于2023年2月

如何得到第一個(gè)基本可行解？

為了得到初始基本可行解，要首先找到初始基本可行基，設(shè)B為約束矩陣的一個(gè)m階子式，如果B非奇異，則矩陣B是一個(gè)基，

進(jìn)一步，若，那么B是初始基本可行基。

就是初始基本可行解。找初始基本可行基的方法如下

1．觀察法與試驗(yàn)法。2.大M法。3.兩階段法

第28頁，課件共45頁，創(chuàng)作于2023年2月如何判斷基本可行解是最優(yōu)解？

對(duì)線性規(guī)劃問題的求解結(jié)果可能出現(xiàn)唯一最優(yōu)解、無窮多最優(yōu)解、無界解和無可行解四種情況，

第29頁，課件共45頁，創(chuàng)作于2023年2月第30頁，課件共45頁，創(chuàng)作于2023年2月第31頁，課件共45頁，創(chuàng)作于2023年2月

找入基變量找出基變量定軸心項(xiàng)作行變換交換變量

如何進(jìn)行換基迭代

第32頁，課件共45頁，創(chuàng)作于2023年2月——掌握線性規(guī)劃問題的數(shù)學(xué)原理及代數(shù)的單純形解法是學(xué)習(xí)LP的最高境界。

——掌握這一方法對(duì)于以后的學(xué)習(xí)大有裨益，希望同學(xué)們發(fā)揚(yáng)十二分的耐心和鉆研精神。第33頁，課件共45頁，創(chuàng)作于2023年2月例題、用單純形法求解第34頁，課件共45頁，創(chuàng)作于2023年2月１．化為滿秩標(biāo)準(zhǔn)形第35頁，課件共45頁，創(chuàng)作于2023年2月2、寫出初始單純形表

第36頁，課件共45頁，創(chuàng)作于2023年2月第37頁，課件共45頁，創(chuàng)作于2023年2月3、判斷基本可行解是最優(yōu)解

由于檢驗(yàn)數(shù)有正數(shù)，且對(duì)應(yīng)的列向量不全為負(fù)，故進(jìn)行換基迭代，第38頁，課件共45頁，創(chuàng)作于2023年2月

4、換基迭代

選上表中的為軸心項(xiàng)

第39頁，課件共45頁，創(chuàng)作于2023年2月5、判斷、由于檢驗(yàn)數(shù)有正數(shù)且對(duì)應(yīng)的列向量不全為負(fù)，故進(jìn)行換基迭代，選上表中的為軸心項(xiàng)

第40頁，課件共45頁，創(chuàng)作于2023年2月由單純形表得一基最優(yōu)解，

由于有非基變量的檢驗(yàn)數(shù)為零，則此線性規(guī)劃有無窮解。選上表中的為軸心項(xiàng).

第41頁，課件共45頁，創(chuàng)作于2023年2月

原線性規(guī)劃所有最優(yōu)解為：

由此表的另一最優(yōu)解所有最優(yōu)解為：第42頁，課件共45頁，創(chuàng)作于2023年2月如何用QM軟件求解LP問題