第三章單純形

第三章單純形第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ù),分別表示約束條件的個數(shù)和決策變量的個數(shù),稱為約束條件(Subjectto)。

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

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

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

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

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

標準形式？

(1)、這里規(guī)定的標準形式為：

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

這里我們假設bi

0(i=1,2,···,m),否則兩端同時乘以“-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變換為標準形式，必須消除其不等式約束和符號無限制變量。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1．單純形表

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

單純形方法步驟

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

如何得到第一個基本可行解？

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

進一步，若，那么B是初始基本可行基。

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

1．觀察法與試驗法。2.大M法。3.兩階段法

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

對線性規(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月

找入基變量找出基變量定軸心項作行變換交換變量

如何進行換基迭代

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

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

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

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

4、換基迭代

選上表中的為軸心項

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

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

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

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

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

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