1、趙明霞 山西大學經(jīng)濟與管理學院,管理運籌學 模型與方法,第2章單純形法,2.1基本思想 2.2基本方法 2.3其它法則,2020/9/5,2,單純形法 內(nèi)容 原本方法 對偶方法 形式 方程組形式 表格形式 矩陣形式,2.1 單純形法的基本思路,2020/9/5,4,需要解決的問題： (1)如何確定初始的基可行解？ (2)目標函數(shù)何時達到最優(yōu)判斷標準是什麼？ (3)為了使目標函數(shù)逐步變優(yōu)，怎么轉(zhuǎn)移？,2020/9/5,5,單純形法的基本思路： 從可行域中某一個頂點開始，判斷此頂點是否是最優(yōu)解， 如不是,則再找另一個使得其目標函數(shù)值更優(yōu)的頂點，稱之為迭代，再判斷此點是否是最優(yōu)解。 直到找到一個頂點

2、為其最優(yōu)解，就是使得其目標函數(shù)值最優(yōu)的解，或者能判斷出線性規(guī)劃問題無最優(yōu)解為止。,2020/9/5,6,線性規(guī)劃的典式,標準形為典式的充要條件：系數(shù)矩陣中存在一個滿秩單位陣。 典式標準形是單純形法的唯一必要前提。,基本性質(zhì)： 線性規(guī)劃問題的可行域是凸集。 標準形線性規(guī)劃的基本可行解與可行域的極點互相對應。 線性規(guī)劃的基本定理 對標準形線性規(guī)劃問題（M）： 若有可行解，則必有基本可行解； 若有最優(yōu)解，則必有最優(yōu)基本解。 若LP問題的可行域R，則R至少有一個極點。 LP問題可行域R的極點為有限個。,2020/9/5,8,2.2 單純形法的基本方法（表格形式）,2020/9/5,9,情況一： 約束條

3、件為 ,1、確定初始基可行解,對于每個條件加上松弛變量,在約束系數(shù)矩陣中的單位矩陣可以構(gòu)成初始基,2020/9/5,10,例2-1 max z=3x1+ 2x2 s.t. x1 +x3 =6 2x2 +x4 =8 2x1+3x2 +x5=18 xj0 （j=1,2,3,4,5）,2020/9/5,11,它的系數(shù)矩陣 其中aj為系數(shù)矩陣A第j列的向量。A的秩為3,A的秩m小于此方程組的變量的個數(shù)n。,可看出 x3, x4 和 x5 的系數(shù)列向量構(gòu)成一個基:,當令非基變量 x1， x2為零時,可得 x3= 6 ， x4 =8 , x5= 18 （0，0，6，8，18）是初始基本可行解,判斷已求得的

4、基本可行解是否是最優(yōu)解。 （1）最優(yōu)性檢驗的依據(jù)檢驗數(shù)j,（2）最優(yōu)解判別定理 對于求最大目標函數(shù)的問題中，對于某個基本可行解，如果所有檢驗數(shù) ，則這個基本可行解是最優(yōu)解。,對于求目標函數(shù)最小值的情況，只需 j0,2、最優(yōu)性檢驗,3、 基變換 (1)入基變量的確定最小檢驗數(shù)規(guī)則 從最優(yōu)解判別定理知道，當某個j0時，非基變量xj變?yōu)榛兞坎蝗×阒悼梢允鼓繕撕瘮?shù)值增大，故我們要選基檢驗數(shù)小于0的非基變量換到基變量中去（稱之為入基變量）。若有兩個以上j0的，則為了使目標函數(shù)增加得更大些，一般選其中的j最小者的非基變量為入基變量。 在本例題中1=-3是檢驗數(shù)中最小的負數(shù)，故選x1為入基變量。 同時，入

5、基變量xk的系數(shù)列向量ak為主列。,2020/9/5,14,(2)出基變量和主元的確定最小比值規(guī)則 確定出基變量的方法：把已確定的入基變量在各約束方程中的正的系數(shù)除其所在約束方程中的常數(shù)項值，把其中最小比值所在的約束方程中的原基變量確定為出基變量。 這樣在下一步迭代的矩陣變換中可以確保新得到的bi值都大于等于零。 出基變量xl所在行的系數(shù)alj構(gòu)成主行。 確定主元的方法：主行（最小比值所在的約束方程）與主列（入基變量系數(shù)列）交于alk為主元。 基變換通過初等變換實現(xiàn)，目標：將主列化為單位向量（alk=1），以符合典式,2020/9/5,15,x1為入基變量，我們把各約束方程中x1的為正的系數(shù)除

6、對應的常量，得 所以，出基變量應為x3，主元為a13,2020/9/5,16,例2-1 max z=3x1+ 2x2 s.t. x1 +x3 =6 2x2 +x4 =8 2x1+3x2 +x5 =18 xj0 （j=1,2,3,4,5）,例2-2,初始單純形表,2020/9/5,19,情況二： 約束條件為 ，=,標準化,非典式,例2-3,添加人工變量,1、大M法,添加人工變量x5來人為的創(chuàng)造一個單位矩陣作為基 M叫做罰因子，任意大的數(shù)。 人工變量只能取零值。必須把x5從基變量中換出去，否則無解。,例2-3,2、兩階段法 將加入人工變量后的線性規(guī)劃劃分兩階段求解。 第一階段：判斷原線性規(guī)劃是否有

7、基可行解，方法是先求解下列線性規(guī)劃問題,2020/9/5,23,例2-4（2-3）,若 ，則原問題無可行解 若 ，則原問題有可行解 若基列中不存在人工變量，直接轉(zhuǎn)入第二階段； 若基列中存在人工變量xBl， 該行xBl前系數(shù)都為0，刪除xBl對應的行和列； 該行xBl前系數(shù)不都為0，alk 0,以alk為主元換基作運算。,無可行解,例2-4（2-3）,第二階段：求解原問題， 刪除第一階段最終單純形表中的人工變量各列、cj列、cj行、檢驗行； 將cj換成原問題的cj； 重新計算。,2020/9/5,29,1、無可行解,2.3 單純形法的其它法則,最優(yōu)解里有人工變量大于零，則此線性規(guī)劃無可行解。,例

8、2-5,2020/9/5,30,2、無界解 在求目標函數(shù)最大值的問題中，所謂無界解是指在約束條件下目標函數(shù)值可以取任意的大。,存在著一個小于零的檢驗數(shù)，并且該列的系數(shù)向量的每個元素都小于或等于零，則此線性規(guī)劃問題是無界的，一般地說此類問題的出現(xiàn)是由于建模的錯誤所引起的。,例2-4,2020/9/5,31,3、退化問題（相持） 在單純形法計算過程中， 確定入基變量時，存在檢驗數(shù)相等 確定出基變量時有時，存在兩個以上的相同的最小比值,例2-6,2020/9/5,33,勃蘭特(E.Beale)法則: 把松弛變量（剩余變量）、人工變量都用xj表示，一般松弛變量（剩余變量）的下標號列在決策變量之后，人工變量的下標號列在松弛變量（剩余變量）之后，在計算中，遵守以下兩個規(guī)則： （1）在所有檢驗數(shù)小于零的非基變量中，任選一個作為入基變量。 （2）在存在兩個和兩個以上最小比值時，選一個下標最大的基變量為出