《線性規(guī)劃》第二章2.4退化問題 2.6單純形法的幾何意義=第八次課

1、 第四步第四步，若檢驗(yàn)數(shù)中有些為正數(shù)，且它們所對(duì)應(yīng)的系數(shù)，若檢驗(yàn)數(shù)中有些為正數(shù)，且它們所對(duì)應(yīng)的系數(shù)bir中有正數(shù)，則需要換基、進(jìn)行迭代運(yùn)算。中有正數(shù)，則需要換基、進(jìn)行迭代運(yùn)算。 在所有大于零的檢驗(yàn)數(shù)中選取最大的一個(gè)，設(shè)對(duì)應(yīng)的在所有大于零的檢驗(yàn)數(shù)中選取最大的一個(gè)，設(shè)對(duì)應(yīng)的非基變量為非基變量為xr， 則取則取xr為進(jìn)基變量，并求最小比值：為進(jìn)基變量，并求最小比值：由此確定由此確定xj s為離基變量為離基變量( (若上述最小值同時(shí)在幾個(gè)比值上若上述最小值同時(shí)在幾個(gè)比值上達(dá)到，則選取其中下標(biāo)最小的變量為離基變量達(dá)到，則選取其中下標(biāo)最小的變量為離基變量) )。然后用然后用pr代代換換pjs，得到新基，得

2、到新基 ，再接下一步。，再接下一步。00m in0,1, 2,iriirrrsbbbimbb B 第五步第五步，求出新基，求出新基 對(duì)應(yīng)的典式以及基可行解對(duì)應(yīng)的典式以及基可行解x (1)，然后，然后以以 取代取代B，x (1)取代取代x (0)，返回第二步。返回第二步。 BB從第二步到第五步的每一次循環(huán)，稱為一次從第二步到第五步的每一次循環(huán)，稱為一次單純形迭代。單純形迭代。復(fù)習(xí)復(fù)習(xí)2.4 2.4 退化情形的處理退化情形的處理最大檢驗(yàn)數(shù)規(guī)則最大檢驗(yàn)數(shù)規(guī)則最小下標(biāo)規(guī)則最小下標(biāo)規(guī)則2.4 2.4 退化情形的處理退化情形的處理 2、由于退化問題的目標(biāo)函數(shù)值在迭代過程中可能并不改、由于退化問題的目標(biāo)函數(shù)

3、值在迭代過程中可能并不改進(jìn)，一旦前面出現(xiàn)的基在迭代過程中又重新出現(xiàn)進(jìn)，一旦前面出現(xiàn)的基在迭代過程中又重新出現(xiàn)，則后面的則后面的迭代過程可能會(huì)在幾個(gè)基上面兜圈子，此現(xiàn)象成為迭代過程可能會(huì)在幾個(gè)基上面兜圈子，此現(xiàn)象成為“基的循基的循環(huán)環(huán)”。對(duì)退化的線性規(guī)劃問題，使用單純形法時(shí)：對(duì)退化的線性規(guī)劃問題，使用單純形法時(shí)： 對(duì)非退化的線性規(guī)劃問題使用單純形法時(shí)，對(duì)非退化的線性規(guī)劃問題使用單純形法時(shí)，由于每次迭代都使目標(biāo)函數(shù)值有所改進(jìn)，從而經(jīng)過有限次迭由于每次迭代都使目標(biāo)函數(shù)值有所改進(jìn)，從而經(jīng)過有限次迭代，必能求得最優(yōu)解或判斷問題無最優(yōu)解。代，必能求得最優(yōu)解或判斷問題無最優(yōu)解。非退化情形：非退化情形：退化情

4、形：退化情形： 3、若問題還未達(dá)到最優(yōu)就出現(xiàn)了、若問題還未達(dá)到最優(yōu)就出現(xiàn)了“基的循環(huán)基的循環(huán)”，再按照通，再按照通常的單純形法繼續(xù)迭代下去，必然導(dǎo)致常的單純形法繼續(xù)迭代下去，必然導(dǎo)致“死循環(huán)死循環(huán)”，以致最終，以致最終不能得到最優(yōu)解。不能得到最優(yōu)解。(如如P48的的Beale例子例子) 1、如果迭代過程中基不出現(xiàn)重復(fù)，則經(jīng)過有限次迭代也、如果迭代過程中基不出現(xiàn)重復(fù)，則經(jīng)過有限次迭代也能得到最優(yōu)解或判斷問題無最優(yōu)解。能得到最優(yōu)解或判斷問題無最優(yōu)解。(如如2.3節(jié)的例節(jié)的例4)2.4 2.4 退化情形的處理退化情形的處理方法：攝動(dòng)法、字典序法、布蘭德規(guī)則方法：攝動(dòng)法、字典序法、布蘭德規(guī)則定理定理2

5、.7(P50) 對(duì)任一線性規(guī)劃問題對(duì)任一線性規(guī)劃問題LP用單純形法求解時(shí)，按用單純形法求解時(shí)，按Bland規(guī)則確定進(jìn)基變量和離基變量，便不會(huì)出現(xiàn)基的循環(huán)。規(guī)則確定進(jìn)基變量和離基變量，便不會(huì)出現(xiàn)基的循環(huán)?？纱_保不出現(xiàn)可確保不出現(xiàn)基的循環(huán)基的循環(huán)規(guī)則規(guī)則1、當(dāng)有多個(gè)檢驗(yàn)數(shù)是正數(shù)時(shí)，選對(duì)應(yīng)變量中下標(biāo)最小者當(dāng)有多個(gè)檢驗(yàn)數(shù)是正數(shù)時(shí)，選對(duì)應(yīng)變量中下標(biāo)最小者 為進(jìn)基變量。為進(jìn)基變量。與普通單純形法：有區(qū)別與普通單純形法：有區(qū)別布蘭德布蘭德(Bland)規(guī)則規(guī)則規(guī)則規(guī)則2、當(dāng)最小比值當(dāng)最小比值同時(shí)在多行達(dá)到時(shí)，選取對(duì)應(yīng)基變量中同時(shí)在多行達(dá)到時(shí)，選取對(duì)應(yīng)基變量中 下標(biāo)最小者為離基變量。下標(biāo)最小者為離基變量。即由

6、即由 確定進(jìn)基變量為確定進(jìn)基變量為xr 。 min|0(2.39)jjr 000minmin(2.40)lsiribrirllbbjjbb 即由即由確定離基變量為確定離基變量為xjs 。進(jìn)基、離基均采用最小下標(biāo)規(guī)則進(jìn)基、離基均采用最小下標(biāo)規(guī)則與普通單純形法：沒有區(qū)別與普通單純形法：沒有區(qū)別s.t. 123412345123463731min150645011609042511903025010 (1,2,7)ifxxxxxxxxxxxxxxxxxi 2.4 2.4 退化情形的處理退化情形的處理P48 Beale例子例子用用Bland法則求解法則求解解：解：取初始基為取初始基為B0=( p5，p

7、6，p7 )且原問題即為基且原問題即為基B0對(duì)應(yīng)的典式。對(duì)應(yīng)的典式。且此問題為退化的線性規(guī)劃問題。且此問題為退化的線性規(guī)劃問題?；鵅0對(duì)應(yīng)的單純形表見表對(duì)應(yīng)的單純形表見表2-15 。 在第在第1、2行取得，行取得，故故x5為離基變量。為離基變量。2.4 2.4 退化情形的處理退化情形的處理由表由表2-15可知，可知， x1 、x3的的檢驗(yàn)數(shù)均為正數(shù)，由檢驗(yàn)數(shù)均為正數(shù)，由Bland規(guī)則，取規(guī)則，取x1為進(jìn)基變量。為進(jìn)基變量。因?yàn)樽钚”戎狄驗(yàn)樽钚”戎到猓航猓?基基 B0=( p5，p6，p7 )對(duì)應(yīng)的單純形表見表對(duì)應(yīng)的單純形表見表2-15 。于是，于是，b11為表為表2-15的樞元，新基為的樞元

8、，新基為B1=( p1，p6，p7 )。 并將并將x5換為換為x1，得新基，得新基B1對(duì)應(yīng)的單純對(duì)應(yīng)的單純形表，見表形表，見表2-16：對(duì)表對(duì)表2-15作初等行變換，作初等行變換，x1為新的基變量，則對(duì)應(yīng)單位列向量為新的基變量，則對(duì)應(yīng)單位列向量進(jìn)基的選擇也進(jìn)基的選擇也符合：最大檢符合：最大檢驗(yàn)數(shù)規(guī)則驗(yàn)數(shù)規(guī)則*最小下標(biāo)規(guī)則最小下標(biāo)規(guī)則離基離基進(jìn)基進(jìn)基P48 Beale例子例子用用Bland法則求解法則求解2.4 2.4 退化情形的處理退化情形的處理由表由表2-16可知，可知， x2 、x3的的檢驗(yàn)數(shù)均為正數(shù)，由檢驗(yàn)數(shù)均為正數(shù)，由Bland規(guī)則，取規(guī)則，取x2為進(jìn)基變量。為進(jìn)基變量。解：解： 基基

9、 B1=( p1，p6，p7 )對(duì)應(yīng)的單純形表見表對(duì)應(yīng)的單純形表見表2-16。進(jìn)基的選擇也符合：最進(jìn)基的選擇也符合：最大檢驗(yàn)數(shù)規(guī)則。大檢驗(yàn)數(shù)規(guī)則。進(jìn)基進(jìn)基類似地，得到基類似地，得到基 B2=( p1，p2，p7 )。P48 Beale例子例子用用Bland法則求解法則求解2.4 2.4 退化情形的處理退化情形的處理由表由表2-17可知，可知， 只有只有x3的的檢驗(yàn)數(shù)均為正數(shù)，取檢驗(yàn)數(shù)均為正數(shù)，取x3為為進(jìn)基變量。進(jìn)基變量。解：解： 基基 B2=( p1，p2，p7 )對(duì)應(yīng)的單純形表見表對(duì)應(yīng)的單純形表見表2-17 。進(jìn)基進(jìn)基類似地，得到基類似地，得到基 B3=( p3，p2，p7 )。P48 B

10、eale例子例子用用Bland法則求解法則求解進(jìn)基的選擇：既符合最進(jìn)基的選擇：既符合最大檢驗(yàn)數(shù)規(guī)則，又符合大檢驗(yàn)數(shù)規(guī)則，又符合Bland規(guī)則。規(guī)則。2.4 2.4 退化情形的處理退化情形的處理由表由表2-18可知，可知， x4 、x5的的檢驗(yàn)數(shù)均為正數(shù)，由檢驗(yàn)數(shù)均為正數(shù)，由Bland規(guī)則，取規(guī)則，取x4為進(jìn)基變量。為進(jìn)基變量。解：解： 基基 B3=( p3，p2，p7 )對(duì)應(yīng)的單純形表見表對(duì)應(yīng)的單純形表見表2-18 。進(jìn)基進(jìn)基進(jìn)基的選擇也符合：最進(jìn)基的選擇也符合：最大檢驗(yàn)數(shù)規(guī)則。大檢驗(yàn)數(shù)規(guī)則。類似地，得到基類似地，得到基 B4=( p3，p4，p7 )。前前4次迭代：用最大檢驗(yàn)數(shù)規(guī)則和次迭代：

11、用最大檢驗(yàn)數(shù)規(guī)則和Bland規(guī)則的結(jié)論一樣，規(guī)則的結(jié)論一樣，具體結(jié)果都是表具體結(jié)果都是表2-15與與2-19。P48 Beale例子例子用用Bland法則求解法則求解 在第在第3行取行取得，得， 故故x7為離基變量。為離基變量。2.4 2.4 退化情形的處理退化情形的處理由表由表2-19可知，可知， x1 、x5的的檢驗(yàn)數(shù)均為正數(shù)，由檢驗(yàn)數(shù)均為正數(shù)，由Bland規(guī)則取規(guī)則取x1為進(jìn)基變量。為進(jìn)基變量。因?yàn)樽钚”戎狄驗(yàn)樽钚”戎到猓航猓?基基 B4=( p3，p4，p7 )對(duì)應(yīng)的單純形表見表對(duì)應(yīng)的單純形表見表2-19 。于是，于是，b31為表為表2-19的樞元，新基為的樞元，新基為B5=( p3，

12、p4，p1 )。 并將并將x7換為換為x1，得新基，得新基B5對(duì)應(yīng)的單純對(duì)應(yīng)的單純形表，見表形表，見表2-22：對(duì)表對(duì)表2-19作初等行變換，作初等行變換，x1為新的基變量，則對(duì)應(yīng)單位列向量為新的基變量，則對(duì)應(yīng)單位列向量進(jìn)基的選擇：進(jìn)基的選擇：不符合不符合最大檢最大檢驗(yàn)數(shù)規(guī)則，否驗(yàn)數(shù)規(guī)則，否則則x5才是進(jìn)基才是進(jìn)基變量。變量。*離基離基進(jìn)基進(jìn)基P48 Beale例子例子用用Bland法則求解法則求解 在第在第2行行取得，取得， 故故x4為離基變量。為離基變量。2.4 2.4 退化情形的處理退化情形的處理由表由表2-22可知，只有可知，只有 x5的的檢驗(yàn)數(shù)為正數(shù)，故取檢驗(yàn)數(shù)為正數(shù)，故取x5為為進(jìn)

13、基變量。進(jìn)基變量。因?yàn)樽钚”戎狄驗(yàn)樽钚”戎到猓航猓?基基 B5=( p3，p4，p1 )對(duì)應(yīng)的單純形表見表對(duì)應(yīng)的單純形表見表2-22 。于是，于是，b25為表為表2-22的樞元，新基為的樞元，新基為B6=( p3，p5，p1)。 并將并將x4換為換為x5，得新基，得新基B6對(duì)應(yīng)的單純對(duì)應(yīng)的單純形表，見表形表，見表2-23：對(duì)表對(duì)表2-22作初等行變換，作初等行變換，x3為新的基變量，則對(duì)應(yīng)單位列向量為新的基變量，則對(duì)應(yīng)單位列向量進(jìn)基的選擇也進(jìn)基的選擇也符合：最大檢符合：最大檢驗(yàn)數(shù)規(guī)則驗(yàn)數(shù)規(guī)則*離基離基進(jìn)基進(jìn)基P48 Beale例子例子用用Bland法則求解法則求解2.4 2.4 退化情形的處理

14、退化情形的處理解：解： 基基 B6=( p3，p5，p1)對(duì)應(yīng)的單純形表見表對(duì)應(yīng)的單純形表見表2-23 。，最優(yōu)值為，最優(yōu)值為f*=f(x*)由表由表2-23可知，檢驗(yàn)數(shù)全部非正，故表可知，檢驗(yàn)數(shù)全部非正，故表2-23為最優(yōu)解表。為最優(yōu)解表。檢驗(yàn)數(shù)全部非正，檢驗(yàn)數(shù)全部非正，滿足定理滿足定理2.4對(duì)應(yīng)最優(yōu)解為對(duì)應(yīng)最優(yōu)解為x*最優(yōu)解表最優(yōu)解表T13(,0,1,0,0,0)25100 為該基解的基分量的值為該基解的基分量的值為該基解對(duì)應(yīng)的目標(biāo)函數(shù)值為該基解對(duì)應(yīng)的目標(biāo)函數(shù)值120 。P48 Beale例子例子用用Bland法則求解法則求解解：解： 基基 B4=( p3，p4，p7 )對(duì)應(yīng)的單純形表見表

15、對(duì)應(yīng)的單純形表見表2-19 。2.4 2.4 退化情形的處理退化情形的處理由由Bland規(guī)則，規(guī)則，x1為進(jìn)基變量；為進(jìn)基變量；*離基離基進(jìn)基進(jìn)基對(duì)比對(duì)比由最大檢驗(yàn)數(shù)規(guī)則，由最大檢驗(yàn)數(shù)規(guī)則，x5為進(jìn)基變量；為進(jìn)基變量；進(jìn)基進(jìn)基*離基離基x3為離基變量。為離基變量。x7為離基變量。為離基變量。采用采用Bland規(guī)則后，目標(biāo)函數(shù)值得到了改善，規(guī)則后，目標(biāo)函數(shù)值得到了改善，也不在再現(xiàn)基的循環(huán)了，詳見表也不在再現(xiàn)基的循環(huán)了，詳見表2-20與與2-22.2.4 2.4 退化情形的處理退化情形的處理對(duì)比對(duì)比退退化化的的非非退退化化的的采用采用Bland規(guī)規(guī)則后，目標(biāo)則后，目標(biāo)函數(shù)值得到函數(shù)值得到了改善；也

16、了改善；也不再現(xiàn)基的不再現(xiàn)基的循環(huán)了。循環(huán)了。2.4 2.4 退化情形的處理退化情形的處理 雖然雖然Bland法則可避免循環(huán)，但一般說來求解法則可避免循環(huán)，但一般說來求解LP的的 迭代效率較低迭代效率較低 (長(zhǎng)期的實(shí)際表明，退化經(jīng)常有，而循環(huán)極為罕見長(zhǎng)期的實(shí)際表明，退化經(jīng)常有，而循環(huán)極為罕見) 。 一般方法：一般方法： 用單純形法求解用單純形法求解LP問題時(shí)，問題時(shí)，一般按照一般按照2.3節(jié)節(jié)(P3738)的的 步驟與規(guī)則步驟與規(guī)則(最大檢驗(yàn)數(shù)規(guī)則最大檢驗(yàn)數(shù)規(guī)則)來進(jìn)行單純形迭代，對(duì)于來進(jìn)行單純形迭代，對(duì)于 退化退化問題萬一問題萬一遇到循環(huán)現(xiàn)象，再改用遇到循環(huán)現(xiàn)象，再改用Bland規(guī)則。規(guī)則。

17、說明說明2.4 2.4 退化情形的處理退化情形的處理 問題無可行解問題無可行解 (當(dāng)然就沒有最優(yōu)解當(dāng)然就沒有最優(yōu)解) 。 有可行解，但是目標(biāo)函數(shù)在可行域上無下界有可行解，但是目標(biāo)函數(shù)在可行域上無下界(此時(shí)也此時(shí)也 無最優(yōu)解無最優(yōu)解)綜合定理綜合定理2.2至至2.7，可得到如下結(jié)論：，可得到如下結(jié)論：線性規(guī)劃問題線性規(guī)劃問題LP(不管是否退化不管是否退化)有且僅有如下三種可能情形：有且僅有如下三種可能情形： 有最優(yōu)解，且必能在基可行解中找到最優(yōu)解。有最優(yōu)解，且必能在基可行解中找到最優(yōu)解?？尚杏?yàn)榭占尚杏驗(yàn)榭占ɡ矶ɡ?.8若線性規(guī)劃問題若線性規(guī)劃問題LP的可行域非空，且目標(biāo)函數(shù)在可行域上的可行

18、域非空，且目標(biāo)函數(shù)在可行域上有下界有下界，則，則LP必有最優(yōu)解。必有最優(yōu)解?？尚杏蚩尚杏蚍强辗强諜z驗(yàn)數(shù)全部檢驗(yàn)數(shù)全部00時(shí)時(shí)為最優(yōu)解為最優(yōu)解全部全部0 唯一解。唯一解。存在存在=0 無窮多個(gè)解。無窮多個(gè)解。非基變量非基變量檢驗(yàn)數(shù)檢驗(yàn)數(shù)第二章第二章 單純形方法單純形方法在在1.31.3節(jié)節(jié)“圖解法圖解法”已經(jīng)得到如下結(jié)論：已經(jīng)得到如下結(jié)論：2.6 2.6 單純形法的幾何意義單純形法的幾何意義1、線性規(guī)劃的可行域是一個(gè)什么形狀？、線性規(guī)劃的可行域是一個(gè)什么形狀？多邊形，而且是多邊形，而且是“凸凸”的多邊形。的多邊形。2、最優(yōu)解在什么位置獲得？、最優(yōu)解在什么位置獲得？在邊界，而且是在某個(gè)頂點(diǎn)獲得。在

19、邊界，而且是在某個(gè)頂點(diǎn)獲得。這些結(jié)論具有這些結(jié)論具有普遍意義，對(duì)普遍意義，對(duì)于兩個(gè)以上變于兩個(gè)以上變量的線性規(guī)劃量的線性規(guī)劃問題也成立。問題也成立。凸集凸集頂點(diǎn)頂點(diǎn)基可行解基可行解x(1)2.6 2.6 單純形法的幾何意義單純形法的幾何意義1、凸集和凸組合、凸集和凸組合(1)、直線段：、直線段：并稱并稱x(1)，x(2)為線段的端點(diǎn)為線段的端點(diǎn)(他們分別對(duì)應(yīng)他們分別對(duì)應(yīng)=0與與=1)；x(2)(1)(2)xx設(shè)設(shè) ，稱集合稱集合為為Rn中的直線段，中的直線段， (1)(2)(1),01xxxx (1)(2),Rnxx 記為記為(1)(2).xx稱線段上其余的點(diǎn)為線段的內(nèi)點(diǎn)。稱線段上其余的點(diǎn)為線

20、段的內(nèi)點(diǎn)。端點(diǎn)端點(diǎn)端點(diǎn)端點(diǎn)內(nèi)點(diǎn)內(nèi)點(diǎn)01 2.6 2.6 單純形法的幾何意義單純形法的幾何意義1、凸集和凸組合、凸集和凸組合(2)、凸集凸集 (P62定義定義1):定義定義1 設(shè)設(shè)C是是Rn中的中的點(diǎn)集，若點(diǎn)集，若對(duì)對(duì)任意任意的的x(1)，x(2)C和和任意任意 實(shí)數(shù)實(shí)數(shù) (0，1)，有有 x(1)+(1- )x(2) C則稱則稱C是是Rn中的中的凸集，否則為非凸集。凸集，否則為非凸集。代數(shù)定義代數(shù)定義凸集的幾何意義：是集合中任意兩點(diǎn)的連線仍在該集合中。凸集的幾何意義：是集合中任意兩點(diǎn)的連線仍在該集合中。即集中任意兩點(diǎn)間的直線段上的所有點(diǎn)都屬于該集合。即集中任意兩點(diǎn)間的直線段上的所有點(diǎn)都屬于該集

21、合。從直觀上講，凸集從直觀上講，凸集無無凹陷凹陷部分，其內(nèi)部分，其內(nèi)部沒有洞。部沒有洞。凸集凸集1x2x非凸集非凸集4x3x3x2x1x (1)(2)(1)(2)(1),01xxxxxx 線段上的點(diǎn)線段上的點(diǎn)4x例如：例如：凸集凸集非凸集非凸集2.6 2.6 單純形法的幾何意義單純形法的幾何意義1、凸集和凸組合、凸集和凸組合(2)、凸集凸集 :凸集的特殊情況：一條線、一個(gè)點(diǎn)、空集。凸集的特殊情況：一條線、一個(gè)點(diǎn)、空集。 兩點(diǎn)連線的中的任一點(diǎn)能夠表示，如何表示三角形中的兩點(diǎn)連線的中的任一點(diǎn)能夠表示，如何表示三角形中的任一點(diǎn)呢？如何表示多維空間中的任一點(diǎn)呢？任一點(diǎn)呢？如何表示多維空間中的任一點(diǎn)呢？

22、 集合中任意兩點(diǎn)的連線仍在該集合中。集合中任意兩點(diǎn)的連線仍在該集合中。凸組合凸組合2.6 2.6 單純形法的幾何意義單純形法的幾何意義1、凸集和凸組合、凸集和凸組合(3)、凸組合凸組合(P63):直線段中任意一點(diǎn)皆為兩端點(diǎn)的凸組合。直線段中任意一點(diǎn)皆為兩端點(diǎn)的凸組合。兩個(gè)點(diǎn)的凸組合：當(dāng)兩個(gè)點(diǎn)的凸組合：當(dāng) 時(shí)，稱向量時(shí)，稱向量 為為x(1)與與x(2)的凸組合。的凸組合。(1)(2)(1)xx 01 k個(gè)點(diǎn)的個(gè)點(diǎn)的凸組合凸組合: 設(shè)設(shè) ，0 i 1 且且 則稱則稱 是是x(1)， x(2)， ，x(k)的凸組合。的凸組合。 ( )R (1,2, )inxik 11kii ( )1kiiix 注注

23、:凸集凸集集合中任意兩點(diǎn)的凸組合仍然屬于此集合。集合中任意兩點(diǎn)的凸組合仍然屬于此集合。推廣：凸集推廣：凸集C中任意中任意有限個(gè)點(diǎn)有限個(gè)點(diǎn)的凸組合仍屬于的凸組合仍屬于C。(P69第第5題題) (1)(2)(1)(2)(1),01x xx xxx 段段線線(1)( 2 )(1)( 2 )0,1(1)CxxCxxC ，凸凸 集集任任 意意 的的任任 意意 的的有有為為凸組合凸組合凸組合凸組合2.6 2.6 單純形法的幾何意義單純形法的幾何意義2、極點(diǎn)極點(diǎn)(P63)凸集凸集C的極點(diǎn)屬于此集合的極點(diǎn)屬于此集合C，但是，但是（頂點(diǎn)）（頂點(diǎn)）定義定義2：設(shè)：設(shè)C為為Rn中的中的凸集凸集，設(shè)，設(shè) x(0)C，

24、 稱稱x(0)為為C的極點(diǎn)的極點(diǎn) 如果存在如果存在x(1) , x(2)C，使，使x(0)(1- )x(1)+ x(2)， 0 1，則必有，則必有x(1)=x(2)= x(0)。不存在不存在x(1)， x(2)C，x(1)x(2)，以及，以及 (0 1)，使得使得 x(0)(1- )x(1)+ x(2) 。不能表示為不能表示為C中任意兩點(diǎn)的凸組合，只能表示為極點(diǎn)中任意兩點(diǎn)的凸組合，只能表示為極點(diǎn) 自身的凸組合自身的凸組合即是說：即是說： 極點(diǎn)不能用不同的兩點(diǎn)的連線表示。極點(diǎn)不能用不同的兩點(diǎn)的連線表示。x(0)(1- )x(0)+ x(0)它不能成為它不能成為C中任何兩個(gè)不同點(diǎn)的連線的內(nèi)點(diǎn)中任何

25、兩個(gè)不同點(diǎn)的連線的內(nèi)點(diǎn)內(nèi)點(diǎn)內(nèi)點(diǎn)凸集凸集5x2x1x4x 只能為端點(diǎn)只能為端點(diǎn)3x7x6x二維平面中的凸集與極點(diǎn)舉例二維平面中的凸集與極點(diǎn)舉例有無數(shù)個(gè)極點(diǎn)有無數(shù)個(gè)極點(diǎn)橢圓周上的點(diǎn)都是極點(diǎn)橢圓周上的點(diǎn)都是極點(diǎn)1、多邊形、多邊形2.6 2.6 單純形法的幾何意義單純形法的幾何意義2、極點(diǎn)極點(diǎn)(P63)僅有有限個(gè)極點(diǎn)僅有有限個(gè)極點(diǎn)2、閉橢圓域、閉橢圓域3、開圓域、開圓域4、第一象限、第一象限oxy只有一個(gè)極點(diǎn)，即坐標(biāo)原點(diǎn)只有一個(gè)極點(diǎn)，即坐標(biāo)原點(diǎn)2.6 2.6 單純形法的幾何意義單純形法的幾何意義3、超平面和閉半空間、超平面和閉半空間(1)、超平面：超平面：(2)、閉半空間閉半空間:集合集合H稱為稱為R

26、n中的超平面，其中中的超平面，其中,nHx axxR ,nHx axxR ,nHx axxR 集合集合H和和H稱為稱為Rn中的閉半空間，其中中的閉半空間，其中即，即，H和和H是由超平面是由超平面H所劃分的兩個(gè)閉半空間。所劃分的兩個(gè)閉半空間。注注: 超平面超平面H 恰為兩個(gè)閉半空間的交集，即恰為兩個(gè)閉半空間的交集，即H=HH。 平面中，超平面實(shí)為平面中的直線，而由此超平面所劃平面中，超平面實(shí)為平面中的直線，而由此超平面所劃分的分的兩個(gè)閉半空間實(shí)為兩個(gè)半平面。兩個(gè)閉半空間實(shí)為兩個(gè)半平面。 三維空間中，超平面就是通常所說的平面。三維空間中，超平面就是通常所說的平面。閉半空間是閉凸集閉半空間是閉凸集(P69第第2題題)。閉半空間的交集是閉凸集閉半空間的交集是閉凸集。閉集閉集閉集閉集閉集閉集凸集凸集凸集凸集凸集凸集Rn中中有限個(gè)有限個(gè)閉半空間的交集稱為多面凸集，閉半空間的交集稱為多面凸集，多面凸集的極點(diǎn)又稱為頂點(diǎn)。多面凸集的極點(diǎn)又稱為頂點(diǎn)。顯然，多面凸集是閉凸集，顯然，多面凸集是閉凸集，但多面凸集不一定有界。但多面凸集不一定有界。有界的多面凸集稱為凸多面體。有界的多面凸集稱為凸多面體。2.6 2.6 單純形法的幾何意義單純形法的幾何意義4、多面凸集和相鄰極點(diǎn)、多面凸集和相鄰極點(diǎn)(1)、多面凸