1、1.2 線性規劃解的概念1圖解法對二維問題，可作出約束的圖，簡單直觀地理解線性規劃的解。例 考察線性規劃問題等值線 x+3y=C可行域 最優解繼續2解的概念可行解(feasible solution) ：滿足線性規劃問題(LP)的所有約束條件的解，稱為線性規劃問題的一個可行解。可行域：(LP)的所有可行解組成的集合K稱為(LP)的可行域。若可行域為空，則稱不可行。對標準型線性規劃問題，其可行域為最優解(optimal solution) ：可行域中每個可行解都對應一個目標值，其中對應的目標函數值最小的可行解x*，稱為(LP)的最優解，也稱為(LP)的解。即最優值：最優解對應的目標值稱為最優值。

2、3基 設 為滿秩矩陣(秩為m)， 是A中的非奇異子矩陣 ，則稱B為（LP)的一個基。基變量與非基變量 B是由A的m個線性無關的列組成，對應的變量稱為基變量，剩下的變量稱為非基變量。基解 令非基變量變量等于0，可得線性方程組的一個解，稱為基解(basic solution).基可行解 若基解還是可行的，即滿足非負性條件，則稱為基可行解(basic feasible solution 簡記為bfs)。4基解的個數非退化的基可行解：若基變量全部為正。否則稱為退化的基可行解，即有基變量為0可行解基解基可行解非可行解5例 求出線性規劃問題的全部基解，指出哪些是可行的。圖解法6線性規劃解的幾種可能情況無可

3、行解 可行域為空集，約束中存在矛盾方程。有唯一的最優解（通常的情況），必是可行域的頂點。有無窮多個最優解。有可行解但無最優解 可行域必無界。71.3線性規劃問題的幾何意義8基本概念凸集 設K為n維線性空間的一點集，若對K中任意兩點x,y，及任意的 ，有則稱K為凸集。規定空集和單點集為凸集。9例 超平面和半空間都是凸集。凸組合 設 為 中的點，為滿足下列條件的一組實數則稱 為 的凸組合。極點 設K為凸集， ，若x不能表示成K中不同的兩點的凸組合，則稱x為K的一個極點(頂點)。10基本定理定理1 任意一組凸集的交集仍為凸集。定理2 線性規劃問題的可行域是凸集。引理1 線性規劃問題的可行解為基可行解

4、的充要條件是其正分量所對應的系數列向量是線性無關的。證明： 必要性 若x是基解，由定義，正分量對應的列線性無關。充分性 若正分量對應的列線性無關，則個數不超過m，若=m,則是基，若m,可擴充成基。11定理3 線性規劃問題的基可行解對應于可行域的頂點。證明：若x是基可行解，設前m個分量為基變量，但不是極點，則存在x1,x2,01, x=x1 +(1-) x2.x1,x2的后n-m個分量為0。若x是極點，但不是基可行解，正分量對應的列線性相關。對任意的實數取充分小的得兩可行解x1,x2 ，使x= x1/2+x2/2。12推論 線性規劃可行域的頂點個數有限。引理2 若K為有界閉凸集，則其中任何一點可

5、表示為其頂點的凸組合。不證明，舉例說明。定理4 若可行域有界，線性規劃問題的目標函數一定可以在其可行域的頂點達到最優。證明：另外，若可行域無界，但有最優解，則一定也可在頂點處達到最優。定理4換成代數說法就是：線性規劃問題若存在最優解，則一定存在最優的基可行解。13第二章 單純形法14窮舉法的困難已知線性規劃問題的一基可行解，問題此基可行解是否最優；該問題是否無最優解；如何改進（求一更好的基可行解）；算法是否會有限步結束；如何找一基可行解。152.1 單純形表為計算方便，將系數提出來，形成表格：16設有一可行基，不妨設是前m個向量，則線性方程組可化為如下形式其中目標函數可表成非基變量的函數將系數

6、提出列成表，稱為對應于基B的單純形表17單純形表18最優性檢驗與解的判別定理1（最優解的判別定理）設 為(LP)的一基可行解，若對任意的非基變量，都有 ，則 為最優解，稱 為檢驗數。定理2 若對某非基變量，有那么，該線性規劃問題無最優解。19基可行解的改進進基變量的選擇出基變量的選擇最小比值原則證明新的解是基可行解，在非退化假設下，新解目標值下降。 20單純形法的計算步驟算法(單純形法)1)找出初始可行基,確定初始可行解,建立初始單純形表；2)檢驗各非基變量的檢驗系數,若全部非正，結束,得到最優解;3)若某非基變量檢驗數為正，且其對應的系數列向量全部非正，結束，問題無最優解;4)選某個檢驗數為正的非基變量進基，計算最小比值，確定出基變量，5)以所選元素為主元進行消元,得新單純形表，轉2)。21例1 用單純形法求線性規劃問題的解化為標準型,列初始單純形表6/18/222作旋轉變換得新的單純形表5/2-4/33/2（2/3）主元23例2 用單純形法求線性規劃問題的解基x1x4x6-310/3主元241/40-1/