設線性規劃的標準型maxZ=CX

（1.1）AX=b

（1.2）X≥0（1.3）式中A是m×n矩陣，m≤n并且r（A）=m，顯然A中至少有一個m×m子矩陣B，使得r（B）=m。基A中m×m子矩陣B并且有r（B）=m，則稱B是線性規劃的一個基（或基矩陣）。當m=n時，基矩陣唯一，當m<n時，基矩陣就可能有多個，但數目不超過4/8/2025【例1.12】線性規劃求所有基矩陣。【解】約束方程的系數矩陣為2×5矩陣容易看出r（A）=2，2階子矩陣有=10個，基矩陣只有9個，即4/8/2025由線性代數知，基矩陣B必為非奇異矩陣并且|B|≠0。當矩陣B的行列式等式零即|B|=0時就不是基當確定某一矩陣為基矩陣時，則基矩陣對應的列向量稱為基向量，其余列向量稱為非基向量

基向量對應的變量稱為基變量，非基向量對應的變量稱為非基變量

在上例中B2的基向量是A中的第一列和第四列，其余列向量是非基向量，x1、x4是基變量，x2、x3、x5是非基變量。基變量、非基變量是針對某一確定基而言的，不同的基對應的基變量和非基變量也不同。4/8/2025可行解滿足式（1.2）及（1.3）的解X=（x1,x2…，xn)T

稱為可行解。基本可行解，若基本解是可行解則稱為是基本可行解（也稱基可行解）。例如，與X=（0，0，0，3，2，）都是例1的可行解。基本解對某一確定的基B，令非基變量等于零，利用式（1.２）解出基變量，則這組解稱為基Ｂ的基本解。最優解滿足式（1.1）的可行解稱為最優解，即是使得目標函數達到最大值的可行解就是最優解，例如可行解

是例2的最優解。4/8/2025顯然，只要基本解中的基變量的解滿足式（1.３）的非負要求，那么這個基本解就是基本可行解。在例1中，對Ｂ１來說，x1,x2是基變量，x3,x4，x5是非基變量，令x3=x4=x5=0，則式（1.２）為因|Ｂ１|≠０，由克菜姆法則知，x1,x2有唯一解x2=1則基本解為對B2來說，x1,x4,為基變量，令非變量x2,x3,x5為零，由式（1.2）得到

，x4=4，4/8/2025由于是基本解，從而它是基本可行解，在中x1<0,因此不是可行解，也就不是基本可行解。反之，可行解不一定是基本可行解例如

滿足式（1.2）～（1.3），但不是任何基矩陣的基本解。基本解為4/8/2025最優基基可行解對應的基稱為可行基；基本最優解對應的基稱為最優基，如上述B3就是最優基，最優基也是可行基。當最優解唯一時，最優解亦是基本最優解，當最優解不唯一時，則最優解不一定是基本最優解。例如右圖中線段的點為最優解時，Q1點及Q2點是基本最優解,線段的內點是最優解而不是基本最優解。基本最優解

最優解是基本解稱為基本最優解。例如，滿足式（1.1）~(1.3)是最優解,又是B3的基本解,因此它是基本最優解.4/8/2025基本最優解、最優解、基本可行解、基本解、可行解的關系如下所示：基本最優解基本可行解可行解最優解基本解例如,B點和D點是可行解,不是基本解;C點是基本可行解;A點是基本最優解,同時也是最優解、基本可行解、基本解和可行解。4/8/2025凸集設K是n維空間的一個點集，對任意兩點

時，則稱K為凸集。就是以X（1）、X（2）為端點的線段方程，點X的位置由α的值確定，當α=0時，X=X（2），當α=1時X=X（1）凸組合設是Rn中的點若存在使得成立，則稱X為的凸組合。4/8/2025極點

設K是凸集，，若X不能用K中兩個不同的點的凸組合表示為則稱X是K的一個極點或頂點。X是凸集K的極點即X不可能是K中某一線段的內點，只能是K中某一線段的端點。4/8/2025【定理1.1】若線性規劃可行解K非空,則K是凸集.【定理1.2】線性規劃的可行解集合K的點X是極點的充要條件為X是基本可行解.【定理1.3】若線性規劃有最優解,則最優值一定可以在可行解集合的某個極點上到達,最優解就是極點的坐標向量.定理1.2刻劃了可行解集的極點與基本可行解的對應關系，極點是基本可行解，反之，基本可行解一定是極點，但它們并非一一對應，有可能兩個或幾個基本可行解對應于同一極點（退化基本可行解時）。線性規劃的基本定理4/8/2025定理1.3描述了最優解在可行解集中的位置，若最優解唯一，則最優解只能在某一極點上達到，若具有多重最優解，則最優解是某些極點的凸組合，從而最優解是可行解集的極點或界點，不可能是可行解集的內點。若線性規劃的可行解集非空且有界，則一定有最優解；若可行解集無界，則線性規劃可能有最優解，也可能沒有最優解。定理1.2及1.3還給了我們一個啟示，尋求最優解不是在無限個可行解中去找，而是在有限個基本可行解