ch5 (1) 單純形法.ppt

1、,第五章 單 純 形 法,5.2 單純形法的表格形式,5.1 單純形法的原理,5.3 對偶單純形法,5.4 幾種特殊情況,單純形法的基本思路：首先將模型標準化,再從可行域中某一個頂點開始，判斷此頂點是否是最優(yōu)解，如不是,則再找另一個使得其目標函數(shù)值更優(yōu)的頂點，稱之為迭代，再判斷此點是否,是最優(yōu)解。直到找到一個頂點為其最優(yōu)解，就是使得其目標函數(shù)值最優(yōu)的解，或者能判斷出線性規(guī)劃問題無最優(yōu)解為止。,一、基本概念: 設(shè)線性規(guī)劃問題的標準形式為：,基： 已知A是約束條件的mn系數(shù)矩陣，其秩為m。若B是A中mm階非奇異子矩陣（即可逆矩陣），則稱B是線性規(guī)劃問題中的一個基。,基向量：基B中的每一列即稱為一個

2、基向量?；鵅中共有m個基向量。 非基向量：在A中除了基B之外的每一列則稱之為基B的非基向量。,基變量：與基向量pi相應的變量xi叫基變量，基變量有m個。 非基變量：與非基向量pj相應的變量xj叫非基變量，非基變量有nm個。,由線性代數(shù)的知識知道，如果我們在約束方程組系數(shù)矩陣中找到一個基，令這個基的非基變量為零，再求解這個m元線性方程組就可得到唯一的解了，這個解我們稱之為線性規(guī)劃的基本解。,下面通過第二章例1來解釋這些概念：,首先將其變?yōu)槿缦碌臉藴市停?其中pj為系數(shù)矩陣A第j列的向量。A的秩為3,A的秩m小于此方程組的變量的個數(shù)n，,它的系數(shù)矩陣為：,在此例中我們不妨以下列矩陣為為A的一個基，

3、,令這個基對應的非基變量x，x4為零。這時約束方程就變?yōu)榛兞康募s束方程：,求解得到此線性規(guī)劃的一個基本解： x1=0，x2=400，x3=100， x4=0，x5=150 由于在這個基本解中x3與x5不滿足該線性規(guī)劃x3 0， x5 0的約束條件，顯然不是此線性規(guī)劃的可行解。,一個基本解可以是可行解，也可以是非可行解，它們之間的主要區(qū)別在于其所有變量的解是否滿足非負的條件。我們把滿足非負條件的一個基本解叫做基本可行解，并把這樣的基叫做可行基。,上述幾個定義之間的關(guān)系可用下圖表示。,一般來說判斷一個基是否是可行基，只有在求出其基本解以后，當其基本解所有變量的解都是大于等于零，才能斷定這個解是基

4、本可行解，這個基是可行基。,那么我們能否在求解之前，就找到一個可行基呢？也就是說我們找到的一個基能保證在求解之后得到的解一定是基本可行解呢？,由于在線性規(guī)劃的標準型中要求bj都大于等于零，如果我們能找到一個基是單位矩陣，或者說一個基是由單位矩陣的各列向量所組成（至于各列向量的前后順序是無關(guān)緊要的事）例如：,那么顯然所求得的基本解一定是基本可行解，這個單位矩陣或由單位矩陣各列向量組成的基一定是可行基。,實際上，這個基本可行解中的各個變量或等于某個bj或等于零。 在本例題中我們就找到了一個基是單位矩陣。,在第一次找可行基時，所找到的基或為單位矩陣或為由單位矩陣的各列向量所組成，稱之為初始可行基，其

5、相應的基本可行解叫初始基本可行解。 如果找不到單位矩陣或由單位矩陣的各列向量組成的基作為初始可行基，我們將構(gòu)造初始可行基，具體做法在以后詳細講述。,二 單純形法的基本思想：,下面通過第二章例1來說明單純形法的基本思想。其標準形式如下：,易知其系數(shù)矩陣的秩為，并選擇后三列對應的矩陣為初始基。,它的系數(shù)矩陣為：,即令矩陣：,為初始基，令對應的非基變量,可得初始基本可行解：,在原問題中這個初始基本可行解表示：工廠沒有安排甲、乙產(chǎn)品的生產(chǎn)，因此三種資源都沒有利用，工廠的利潤即目標函數(shù)值自然為零。,從對應的目標函數(shù)表達式可以看出： 目標函數(shù)中不含基變量。 其次，非基變量在目標函數(shù)中的系數(shù)都是正數(shù)，如果將

6、其中的一個非基變量變?yōu)樾碌幕兞浚ǚQ為入基變量，或者換入變量），則其取值可以由零變?yōu)檎?。,由于原非基變量在目標函數(shù)中的系數(shù)均大于零，所以，對應的目標函數(shù)值就會增大。 從經(jīng)濟意義上講，若安排生產(chǎn)甲產(chǎn)品或乙產(chǎn)品，就可使企業(yè)的利潤指標增加。,所以只要目標函數(shù)的表達式中不含基變量（此時變量的系數(shù)稱為檢驗數(shù)），而且還有正系數(shù)的非基變量，就表示目標函數(shù)值還有改進的可能。,為了使得目標函數(shù)值增大的更快一些，可以選擇目標函數(shù)中系數(shù)最大的非基變量作為入基變量。 在本例中，我們選擇 為入基變量。,另一方面，為了保證基變量的個數(shù)即系數(shù)矩陣的秩，就必須從原來的基變量中找一個變量，作為新的非基變量而取零值（稱為出基

7、變量，或者換出變量）。,為了選擇出基變量，我們進行如下分析： 首先，當 作為入基變量時，不管基變量中那個變量作為出基變量， 仍然要為非基變量，即 仍然要取零。所以，我們可以將原問題的主約束條件簡化為：,同時，不管基變量中那個變量作為出基變量，當 作為入基變量時，必須保證新的到的基本解仍然是基本可行解，即：,為使上述不等式組成立，只有選擇：,而當 時，變量 即表明所有變量都滿足非負約束條件，同時也表明， 在三個變量 中，隨著 的增大是最先達到0的。所以，應該選 由基變量變?yōu)榉腔兞?，也就是?去替換 這一過程稱為“換基”，或者稱為“迭代”。：,令對應的非基變量 可以求得一個新的基本可行解：,為了

8、對新的基本可行解進行最優(yōu)性檢驗，我們用新的非基變量表示目標函數(shù)，由（1）式可得：,代入原來的目標函數(shù)可得：,顯然，目標函數(shù)值還可以增大。為此，選擇 為入基變量。 同理，為了選擇出基變量，必須使得：,所以，選擇 為出基變量。,令對應的非基變量取零，可以求得一個新的基本可行解：,為了對新的基本可行解進行最優(yōu)性檢驗，我們用新的非基變量表示目標函數(shù)，由（1）式可得：,代入原來的目標函數(shù)可得：,顯然，目標函數(shù)值已經(jīng)無法再增大增大。所以，對應的基本可行解為最優(yōu)解。,作為練習，大家用剛才的方法求解下列規(guī)劃：,從以上實例可以看出，單純形法的主要步驟可以用下列的流程圖來表示：,第一步： 求出一個初始基本可行解

9、以單位矩陣或者單位向量組成的矩陣為初始基。令對應的非基變量為零。即可得到一個初始基本可行解。 如果找不到這樣的基，可用人工變量法。,第二步： 最優(yōu)性檢驗 所謂最優(yōu)性檢驗就是判斷已求得的基本可行解是否是最優(yōu)解。,1 最優(yōu)性檢驗的依據(jù)檢驗數(shù) 一般來說目標函數(shù)中既包括基變量，又包括非基變量。現(xiàn)在我們用非基變量來表示目標函數(shù)。目標函數(shù)中所有變量的系數(shù)即為各變量的檢驗數(shù)。,這只要在約束等式中通過移項等處理就可以用非基變量來表示基變量，然后用非基變量的表示式代替目標函數(shù)中基變量，這樣目標函數(shù)中只含有非基變量了，或者說目標函數(shù)中基變量的系數(shù)都為零了。顯然所有基變量的檢驗數(shù)必為零。,在本例題中目標函數(shù)為50

10、x1+100 x2。由于初始可行解中x1，x2為非基變量，所以此目標函數(shù)已經(jīng)用非基變量表示了，不需要再代換出基變量了。這樣我們可知：1=50，2=100，3=0，4=0，5=0。,2.最優(yōu)解判別定理 對于求最大目標函數(shù)的問題中，對于某個基本可行解，如果所有檢驗數(shù) 則這個基本可行解是最優(yōu)解。,第三步： 基變換 通過檢驗，我們知道這個初始基本可行解不是最優(yōu)解。下面介紹如何進行基變換找到一個新的可行基。,具體的做法是從可行基中換一個列向量，得到一個新的可行基，使得求解得到的新的基本可行解，其目標函數(shù)值更優(yōu)。為了換基就要確定換入變量與換出變量。,1. 入基變量的確定 從最優(yōu)解判別定理知道，當某個j0時

11、，非基變量xj變?yōu)榛兞坎蝗×阒悼梢允鼓繕撕瘮?shù)值增大，故我們要選基檢驗數(shù)大于0的非基變量換到基變量中去（稱之為入基變量）。,若有兩個以上的檢驗數(shù)大于零，則為了使目標函數(shù)增加得更大些，一般選其中的檢驗數(shù)最大者的非基變量為入基變量.,2. 出基變量的確定：,用入基變量在各約束方程中的正系數(shù)除其所在約束方程中的常數(shù)項的值，把其中最小比值所在的約束方程中的原基變量確定為出基變量。,在本例題中約束方程為：,在第二步中已經(jīng)知道x2為入基變量，我們用各約束方程中x2的為正的系數(shù)除對應的常量，得：,其中 的值最小，所以可以知道，原基變量中的s3為出基變量，這樣可知x2， x3 ， x4為新的基變量，x1， x5為新的非基變量。,令非基變量為零，得： x