第3章 線性規(guī)劃 §4 單純形方法 2013

1、實驗實驗o 時間：14周，周一下午5-8節(jié)（12月2號？查校歷）o 地點：工程實訓樓（具體到時候大屏幕會有指示）。第第3章章 線性規(guī)劃線性規(guī)劃Linear Programming 4 單純形方法單純形方法結(jié)合結(jié)合例2.4.1p60薛毅講講（同前上次課的例子）直接表上操作，單純形表的樣子提前。直接表上操作，單純形表的樣子提前。例(2.4.1p60，同例2.3.6,p46，薛毅)(在黑板上講，書中也有主要步驟，也可參考)。 min -2x1 - 5x2 st x1 + 2x2 8 x1 4 x2 3 x1 , x2 0第一步，化為標準形min -2x1 - 5x2 st x1 + 2x2 + x3

2、 = 8 x1 + x4 = 4 x2 + x5 = 3 x1 , x2 , x3 , x4 , x5 0A = b =c = (-2,-5, 0, 0, 0)單純形表對應(yīng)線性規(guī)劃的標準形o 用來表示一個線性規(guī)劃問題，含有約束方程組和 目標函數(shù)（不含非負約束，目標函數(shù)也有變形）。o 例子（原來的）基變量基變量f - cTx = 0bA1210010010010018432500001000fx1x2x3x4x5RHSx3x4x5典式典式o 是線性規(guī)劃的一種形式，它的單純形表滿足下面3個條件:第一，矩陣A中有一個基（矩陣），其基向量為 (0,., 1, .,0)T形式。第二，右邊的b0。第三，目

3、標函數(shù) f 行（首行）基變量對應(yīng)的數(shù)為0。 典式典式 化為典式的形式后，可看出一個基本可行解 以及該解所對應(yīng)的目標函數(shù)值。 該基（單位向量組成的這個）是一個可行基是一個可行基。4 單純形(simplex)方法 重點內(nèi)容！重點內(nèi)容！o 已經(jīng)講過，可以在線性規(guī)劃的基本可行解，也即可行域的頂點，中搜索最優(yōu)解。o 單純形方法是從已知線性規(guī)劃的一個基本可行解開是從已知線性規(guī)劃的一個基本可行解開始的（或可行基）開始的，始的（或可行基）開始的，然后找到目標函數(shù)值更小的基本可行解， 逐步找到最優(yōu)的基本可行解。n 等價于從已知線性規(guī)劃的一個可行基開始。等價于從已知線性規(guī)劃的一個可行基開始。n 等價于從已知一個典

4、式開始。等價于從已知一個典式開始。o 以目標函數(shù)值下降下降為導(dǎo)向，同時滿足非負約束。o 結(jié)合例子說明。基本可行解的改進改進o 設(shè)已知線性規(guī)劃問題的一個基本可行解 ，找新的新的基本可行解，并且使目標函數(shù)值減小。換基換基，包括3步。o 1. 選擇一個進基變量選擇一個進基變量：選1個非基變量，變?yōu)榛兞?。方法：在大?的檢驗數(shù)檢驗數(shù)中選一個(通常選值最大的)，令它所對應(yīng)的變量進基，成為新的基變量。 k = max j | j0, j R， R是非基變量的下標集，則選擇xk進基進基。在xk相應(yīng)的檢驗數(shù)上加*標記。檢驗數(shù)的定義見下頁檢驗數(shù)的定義見下頁檢驗數(shù)，最優(yōu)性條件o檢驗數(shù)或判別數(shù)檢驗數(shù)或判別數(shù)：是當

5、線性規(guī)劃形式為典式時， 單純形表中第一行中非基變量的對應(yīng)的數(shù)。 檢驗數(shù)或判別數(shù)記為記為j, jR, R是非基變量下標集。 例中R=1, 2，1=2， 2=5?；厣享摚ㄟx進基變量）o 2. 選擇出基變量，出基變量，即選擇一個基變量，將它變?yōu)榉腔兞俊?（一進一出，保持基變量個數(shù)恒定）設(shè)進基變量為xk，約束矩陣A中xk的系數(shù)aik，i 為行號,第 i 行右端常數(shù)為bi，若min bi /aik，aik 0 = br /ark (某個某個r)則第r行對應(yīng)的原來的基變量被選為出基變量，出基變量，將成為非基變量。(進基變量新的取值為br /ark。把ark框/圈起來。)o 3. 換基換基（也叫轉(zhuǎn)軸，旋轉(zhuǎn)

6、）。（坐標系變換） 利用行的初等變換，把ark變?yōu)?，把ark所在列的其它元素(包括第一行的那個)都變?yōu)?。 化成了新的典式。得到了新的基本可行解(以及新的可行基，換基了),并使f的值變小了。重復(fù)這3步。 使用單純形方法的求解線性規(guī)劃的步驟使用單純形方法的求解線性規(guī)劃的步驟o化為標準形o設(shè)已知線性規(guī)劃問題的一個基本可行解 (或典式，或者一個可行基)，先用行變換化為典式， 然后換基換基，以進行基本可行解的改進o 選擇進基變量，或者已經(jīng)找到最優(yōu)解。o 選擇出基變量，或判斷為無(有限有限)最優(yōu)解.o (最優(yōu)解在無窮遠處)o 換基。o 重復(fù)這3步，或找到最優(yōu)解，或為無(有限有限)最優(yōu)解.上面幾個步驟中

7、會遇到的幾種情況(1)第一步，選進基變量如果檢驗數(shù)中沒有大于0的怎么辦？這時該基本可行解已經(jīng)是最優(yōu)解了。結(jié)論結(jié)論1：線性規(guī)劃形式為典式時，如果檢驗數(shù)全0, 則此時的基本可行解為最優(yōu)解。 檢驗數(shù)全0稱為最優(yōu)性條件最優(yōu)性條件。練習：下頁例2.4.2 p62薛毅 有無窮多個最優(yōu)解的情況 min -x1 - 2x2 st x1 + 2x2 8 x1 4 x2 3 x1 , x2 0結(jié)論結(jié)論2：線性規(guī)劃形式為典式時，如果檢驗數(shù)全0, 并且有的檢驗數(shù)為0，則有無窮多個最優(yōu)解。有一個這樣類型的作業(yè)題。 這時以為以為0的檢驗數(shù)對應(yīng)的非基變量為進基變量的檢驗數(shù)對應(yīng)的非基變量為進基變量，然后選擇出基變量、換基，又

8、可求出一個最優(yōu)基本可行解（頂點）。兩個最優(yōu)兩個最優(yōu)頂點的連線段上的點都是最優(yōu)解，有無窮多個頂點的連線段上的點都是最優(yōu)解，有無窮多個。有時有最優(yōu)解面.上面幾個步驟中會遇到的幾種情況(2)（自學，非重點）自學，非重點）第二步 選擇出基變量若在約束矩陣A中進基變量的系數(shù)全0，怎么辦？無(有限)最優(yōu)解。結(jié)論結(jié)論2 線性規(guī)劃形式為典式時，若某個檢驗數(shù)0,并且相應(yīng)的變量在約束矩陣A中的系數(shù)全0，則該線性規(guī)劃問題的最優(yōu)解在無窮遠處（無有最優(yōu)解在無窮遠處（無有限最優(yōu)解）限最優(yōu)解）。例（2.4.3p64薛毅，自學）o 會不會出現(xiàn)無可行解的情況？不會。因為已知一個基本可行解。練習（或再看一遍例題p60），是怎樣求

9、解的。單純形方法的幾何意義o 單純形方法是從已知的一個基本可行解（或典式）單純形方法是從已知的一個基本可行解（或典式）出發(fā)，從一個基本可行解換到另一個基本可行解出發(fā)，從一個基本可行解換到另一個基本可行解（或典式）的過程，在這個過程中，目標函數(shù)值（或典式）的過程，在這個過程中，目標函數(shù)值 逐步減小，直到找到最優(yōu)解（和最優(yōu)目標函數(shù)值），逐步減小，直到找到最優(yōu)解（和最優(yōu)目標函數(shù)值），或者判定最優(yōu)解在無窮遠處?；蛘吲卸ㄗ顑?yōu)解在無窮遠處。 幾何上看幾何上看：可用2維的情況予以說明(例1，下頁) 。 基本可行解 即 可行域頂點。單純形方法的不足和重要性o 只用只用單純形方法并不能求解所有的線性規(guī)劃問題。n

10、不是典式、基本可行解未知時，不能直接用。n是退化的線性規(guī)劃(下頁)時，有時會陷入循環(huán)。若陷入循環(huán)，則無法求解。o 要解任意一個線性規(guī)劃，還要用一些小的技巧小的技巧 n大大M方法方法，兩階段方法(可得一個基本可行解)nBland防止循環(huán)的方法（求解退化LP問題6）o 單純形方法單純形方法是線性規(guī)劃求解方法的核心核心， 而且實用效果很好。退化的線性規(guī)劃o 基本解中若非0分量少于m個，稱為退化的基本解退化的基本解,若非0分量為m個，稱為非退化的基本解非退化的基本解。 （基本解的非0分量不可能多余m個）o 若線性規(guī)劃所有的所有的可行基本解都是非退化的， 稱線性規(guī)劃為非退化的非退化的。否則為退化的退化的線性規(guī)劃。 （書上的該定義