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

第五步，求出新基對應(yīng)的典式以及基可行解x(1)，然后以取代B，x(1)取代x(0)，返回第二步。從第二步到第五步的每一次循環(huán)，稱為一次單純形迭代。單純形法的計(jì)算步驟復(fù)習(xí)2.4退化情形的處理最大檢驗(yàn)數(shù)規(guī)則最小下標(biāo)規(guī)則當(dāng)前1頁，總共26頁。2.4退化情形的處理一、退化問題可能會出現(xiàn)基的循環(huán)

2、由于退化問題的目標(biāo)函數(shù)值在迭代過程中可能并不改進(jìn)，一旦前面出現(xiàn)的基在迭代過程中又重新出現(xiàn)，則后面的迭代過程可能會在幾個基上面兜圈子，此現(xiàn)象成為“基的循環(huán)”。對退化的線性規(guī)劃問題，使用單純形法時：

對非退化的線性規(guī)劃問題使用單純形法時，由于每次迭代都使目標(biāo)函數(shù)值有所改進(jìn)，從而經(jīng)過有限次迭代，必能求得最優(yōu)解或判斷問題無最優(yōu)解。非退化情形：退化情形：

3、若問題還未達(dá)到最優(yōu)就出現(xiàn)了“基的循環(huán)”，再按照通常的單純形法繼續(xù)迭代下去，必然導(dǎo)致“死循環(huán)”，以致最終不能得到最優(yōu)解。(如P48的Beale例子)

1、如果迭代過程中基不出現(xiàn)重復(fù)，則經(jīng)過有限次迭代也能得到最優(yōu)解或判斷問題無最優(yōu)解。(如2.3節(jié)的例4)當(dāng)前2頁，總共26頁。2.4退化情形的處理二、退化問題中避免基循環(huán)的方法方法：攝動法、字典序法、布蘭德規(guī)則定理2.7(P50)

對任一線性規(guī)劃問題LP用單純形法求解時，按Bland規(guī)則確定進(jìn)基變量和離基變量，便不會出現(xiàn)基的循環(huán)?？纱_保不出現(xiàn)基的循環(huán)規(guī)則1、當(dāng)有多個檢驗(yàn)數(shù)是正數(shù)時，選對應(yīng)變量中下標(biāo)最小者為進(jìn)基變量?！膛c普通單純形法：有區(qū)別布蘭德(Bland)規(guī)則規(guī)則2、當(dāng)最小比值θ同時在多行達(dá)到時，選取對應(yīng)基變量中下標(biāo)最小者為離基變量。即由確定進(jìn)基變量為xr。即由確定離基變量為xjs?！M(jìn)基、離基均采用最小下標(biāo)規(guī)則與普通單純形法：沒有區(qū)別當(dāng)前3頁，總共26頁。2.4退化情形的處理P48Beale例子——用Bland法則求解解：取初始基為B0=(p5，p6，p7)且原問題即為基B0對應(yīng)的典式。且此問題為退化的線性規(guī)劃問題?；鵅0對應(yīng)的單純形表見表2-15。二、退化問題中避免基循環(huán)的方法當(dāng)前4頁，總共26頁。在第1、2行取得，故x5為離基變量。2.4退化情形的處理由表2-15可知，x1、x3的檢驗(yàn)數(shù)均為正數(shù)，由Bland規(guī)則，取x1為進(jìn)基變量。因?yàn)樽钚”戎郸冉猓夯?/p>

B0=(p5，p6，p7)對應(yīng)的單純形表見表2-15。于是，b11為表2-15的樞元，新基為B1=(

p1，p6，p7)。并將x5換為x1，得新基B1對應(yīng)的單純形表，見表2-16：對表2-15作初等行變換，x1為新的基變量，則對應(yīng)單位列向量進(jìn)基的選擇也符合：最大檢驗(yàn)數(shù)規(guī)則*最小下標(biāo)規(guī)則離基進(jìn)基P48Beale例子——用Bland法則求解二、退化問題中避免基循環(huán)的方法當(dāng)前5頁，總共26頁。2.4退化情形的處理由表2-16可知，x2、x3的檢驗(yàn)數(shù)均為正數(shù)，由Bland規(guī)則，取x2為進(jìn)基變量。解：基

B1=(

p1，p6，p7)對應(yīng)的單純形表見表2-16。進(jìn)基的選擇也符合：最大檢驗(yàn)數(shù)規(guī)則。進(jìn)基類似地，得到基

B2=(p1，p2，p7)。P48Beale例子——用Bland法則求解二、退化問題中避免基循環(huán)的方法當(dāng)前6頁，總共26頁。2.4退化情形的處理由表2-17可知，只有x3的檢驗(yàn)數(shù)均為正數(shù)，取x3為進(jìn)基變量。解：基

B2=(p1，p2，p7)對應(yīng)的單純形表見表2-17。進(jìn)基類似地，得到基

B3=(p3，p2，p7)。P48Beale例子——用Bland法則求解二、退化問題中避免基循環(huán)的方法進(jìn)基的選擇：既符合最大檢驗(yàn)數(shù)規(guī)則，又符合Bland規(guī)則。當(dāng)前7頁，總共26頁。2.4退化情形的處理由表2-18可知，x4、x5的檢驗(yàn)數(shù)均為正數(shù)，由Bland規(guī)則，取x4為進(jìn)基變量。解：基

B3=(p3，p2，p7)對應(yīng)的單純形表見表2-18。進(jìn)基進(jìn)基的選擇也符合：最大檢驗(yàn)數(shù)規(guī)則。類似地，得到基

B4=(p3，p4，p7)。前4次迭代：用最大檢驗(yàn)數(shù)規(guī)則和Bland規(guī)則的結(jié)論一樣，具體結(jié)果都是表2-15與2-19。P48Beale例子——用Bland法則求解二、退化問題中避免基循環(huán)的方法當(dāng)前8頁，總共26頁。在第3行取得，故x7為離基變量。2.4退化情形的處理由表2-19可知，x1、x5的檢驗(yàn)數(shù)均為正數(shù)，由Bland規(guī)則取x1為進(jìn)基變量。因?yàn)樽钚”戎郸冉猓夯?/p>

B4=(p3，p4，p7)對應(yīng)的單純形表見表2-19。于是，b31為表2-19的樞元，新基為B5=(p3，p4，p1)。并將x7換為x1，得新基B5對應(yīng)的單純形表，見表2-22：對表2-19作初等行變換，x1為新的基變量，則對應(yīng)單位列向量進(jìn)基的選擇：不符合最大檢驗(yàn)數(shù)規(guī)則，否則x5才是進(jìn)基變量。*離基進(jìn)基P48Beale例子——用Bland法則求解二、退化問題中避免基循環(huán)的方法當(dāng)前9頁，總共26頁。在第2行取得，故x4為離基變量。2.4退化情形的處理由表2-22可知，只有x5的檢驗(yàn)數(shù)為正數(shù)，故取x5為進(jìn)基變量。因?yàn)樽钚”戎郸冉猓夯?/p>

B5=(p3，p4，p1)對應(yīng)的單純形表見表2-22。于是，b25為表2-22的樞元，新基為B6=(p3，p5，p1)。并將x4換為x5，得新基B6對應(yīng)的單純形表，見表2-23：對表2-22作初等行變換，x3為新的基變量，則對應(yīng)單位列向量進(jìn)基的選擇也符合：最大檢驗(yàn)數(shù)規(guī)則*離基進(jìn)基P48Beale例子——用Bland法則求解二、退化問題中避免基循環(huán)的方法當(dāng)前10頁，總共26頁。2.4退化情形的處理解：基

B6=(p3，p5，p1)對應(yīng)的單純形表見表2-23。，最優(yōu)值為f*=f(x*)由表2-23可知，檢驗(yàn)數(shù)全部非正，故表2-23為最優(yōu)解表。檢驗(yàn)數(shù)全部非正，滿足定理2.4對應(yīng)最優(yōu)解為x*最優(yōu)解表為該基解的基分量的值為該基解對應(yīng)的目標(biāo)函數(shù)值P48Beale例子——用Bland法則求解二、退化問題中避免基循環(huán)的方法當(dāng)前11頁，總共26頁。解：基

B4=(p3，p4，p7)對應(yīng)的單純形表見表2-19。2.4退化情形的處理由Bland規(guī)則，x1為進(jìn)基變量；*離基進(jìn)基★對比★由最大檢驗(yàn)數(shù)規(guī)則，x5為進(jìn)基變量；進(jìn)基*離基x3為離基變量。x7為離基變量。采用Bland規(guī)則后，目標(biāo)函數(shù)值得到了改善，也不在再現(xiàn)基的循環(huán)了，詳見表2-20與2-22.二、退化問題中避免基循環(huán)的方法當(dāng)前12頁，總共26頁。2.4退化情形的處理★對比★退化的非退化的采用Bland規(guī)則后，目標(biāo)函數(shù)值得到了改善；也不再現(xiàn)基的循環(huán)了。二、退化問題中避免基循環(huán)的方法當(dāng)前13頁，總共26頁。2.4退化情形的處理①雖然Bland法則可避免循環(huán)，但一般說來求解LP的迭代效率較低(長期的實(shí)際表明，退化經(jīng)常有，而循環(huán)極為罕見)。②一般方法：用單純形法求解LP問題時，一般按照2.3節(jié)(P37—38)的步驟與規(guī)則(最大檢驗(yàn)數(shù)規(guī)則)來進(jìn)行單純形迭代，對于

退化問題萬一遇到循環(huán)現(xiàn)象，再改用Bland規(guī)則。二、退化問題中避免基循環(huán)的方法★說明★當(dāng)前14頁，總共26頁。2.4退化情形的處理①問題無可行解(當(dāng)然就沒有最優(yōu)解)。②有可行解，但是目標(biāo)函數(shù)在可行域上無下界(此時也無最優(yōu)解)三、線性規(guī)劃問題LP的解的情況綜合定理2.2至2.7，可得到如下結(jié)論：線性規(guī)劃問題LP(不管是否退化)有且僅有如下三種可能情形：③有最優(yōu)解，且必能在基可行解中找到最優(yōu)解?？尚杏?yàn)榭占ɡ?.8若線性規(guī)劃問題LP的可行域非空，且目標(biāo)函數(shù)在可行域上有下界，則LP必有最優(yōu)解。可行域非空檢驗(yàn)數(shù)全部≤0時為最優(yōu)解全部<0?唯一解。存在=0?無窮多個解。非基變量檢驗(yàn)數(shù)當(dāng)前15頁，總共26頁。2.6單純形法的幾何意義第二章單純形方法第二章單純形方法當(dāng)前16頁，總共26頁。在1.3節(jié)“圖解法”已經(jīng)得到如下結(jié)論：2.6單純形法的幾何意義1、線性規(guī)劃的可行域是一個什么形狀？——多邊形，而且是“凸”的多邊形。2、最優(yōu)解在什么位置獲得？——在邊界，而且是在某個頂點(diǎn)獲得。這些結(jié)論具有普遍意義，對于兩個以上變量的線性規(guī)劃問題也成立。凸集頂點(diǎn)——基可行解當(dāng)前17頁，總共26頁。x(1)2.6單純形法的幾何意義一、基本概念1、凸集和凸組合(1)、直線段：并稱x(1)，x(2)為線段的端點(diǎn)(他們分別對應(yīng)α=0與α=1)；x(2)設(shè)，稱集合為Rn中的直線段，記為稱線段上其余的點(diǎn)為線段的內(nèi)點(diǎn)。端點(diǎn)端點(diǎn)內(nèi)點(diǎn)當(dāng)前18頁，總共26頁。2.6單純形法的幾何意義一、基本概念1、凸集和凸組合(2)、凸集(P62定義1):定義1

設(shè)C是Rn中的點(diǎn)集，若對任意的x(1)，x(2)∈C和任意實(shí)數(shù)

∈(0，1)，有

x(1)+(1-)x(2)∈C則稱C是Rn中的凸集，否則為非凸集。代數(shù)定義凸集的幾何意義：是集合中任意兩點(diǎn)的連線仍在該集合中。即集中任意兩點(diǎn)間的直線段上的所有點(diǎn)都屬于該集合。從直觀上講，凸集無凹陷部分，其內(nèi)部沒有洞。凸集非凸集線段上的點(diǎn)當(dāng)前19頁，總共26頁。例如：凸集非凸集2.6單純形法的幾何意義一、基本概念1、凸集和凸組合(2)、凸集:凸集的特殊情況：一條線、一個點(diǎn)、空集。兩點(diǎn)連線的中的任一點(diǎn)能夠表示，如何表示三角形中的任一點(diǎn)呢？如何表示多維空間中的任一點(diǎn)呢？——集合中任意兩點(diǎn)的連線仍在該集合中。凸組合當(dāng)前20頁，總共26頁。2.6單純形法的幾何意義一、基本概念1、凸集和凸組合(3)、凸組合(P63):①直線段中任意一點(diǎn)皆為兩端點(diǎn)的凸組合?！魞蓚€點(diǎn)的凸組合：當(dāng)時，稱向量為x(1)與x(2)的凸組合?！鬹個點(diǎn)的凸組合:設(shè)，0i1且

則稱是x(1)，

x(2)，…，x(k)的凸組合。注:②凸集——集合中任意兩點(diǎn)的凸組合仍然屬于此集合。推廣：凸集C中任意有限個點(diǎn)的凸組合仍屬于C。(P69第5題)凸組合凸組合當(dāng)前21頁，總共26頁。2.6單純形法的幾何意義一、基本概念2、極點(diǎn)(P63)凸集C的極點(diǎn)屬于此集合C，但是（頂點(diǎn)）定義2：設(shè)C為Rn中的凸集，設(shè)x(0)∈C，稱x(0)為C的極點(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)?！荒鼙硎緸镃中任意兩點(diǎn)的凸組合，只能表示為極點(diǎn)自身的凸組合即是說：極點(diǎn)不能用不同的兩點(diǎn)的連線表示。x(0)＝(1-)x(0)+x(0)——它不能成為C中任何兩個不同點(diǎn)的連線的內(nèi)點(diǎn)內(nèi)點(diǎn)凸集只能為端點(diǎn)當(dāng)前22頁，總共26頁。二維平面中的凸集與極點(diǎn)舉例極點(diǎn)有無數(shù)個極點(diǎn)橢圓周上的點(diǎn)都是極點(diǎn)1、多邊形2.6單純形法的幾何意義一、基本概念2、極點(diǎn)(P63)僅有有限個極點(diǎn)沒有極點(diǎn)2、閉橢圓域3、開圓域不是極點(diǎn)4、第一象限只有一個極點(diǎn)，即坐標(biāo)原點(diǎn)當(dāng)前23頁，總共26頁。2.6單純形法的幾何意義一、基本概念3、超平面和閉半空間(1)、超平面：(2)、閉半空間:集合H稱為Rn中的超平面，其中集合H＋和H－稱為Rn中的閉半空間，其中即，H＋和H－是由超平面H所劃分的兩個閉半空間。注:①超平面H恰為兩個閉半空間的交集，即H=H＋∩H－。平面中，超平面實(shí)為平面中的直線，而由此超平面所劃分的兩個閉半空間實(shí)為兩個半平面。三維空間中，超平面就是通常所說的平面。②閉半空間是閉凸集(P69第2題)。