北郵運籌學ch線性規(guī)劃解的概念

1、 設線性規(guī)劃的標準型max Z=CX （1.1）AX=b （1.2）X0 （1.3）式中A是mn矩陣，mn并且r（A）=m，顯然A中至少有一個mmB，使得r（B）=m?；?A中mmB并且有r（B）=m，則稱B是線性規(guī)劃的一個基（或基矩陣 ）。當m=n時，基矩陣唯一，當mn時，基矩陣就可能有多個，但數目不超過7/25/2022【例1.12】線性規(guī)劃 求所有基矩陣。 【解】約束方程的系數矩陣為25矩陣 容易看出r（A）=2，2階子矩陣有 =10個，基矩陣只有9個，即7/25/2022由線性代數知，基矩陣B必為非奇異矩陣并且|B|0。當矩陣B的行列式等式零即|B|=0時就不是基 當確定某一矩陣為基矩

2、陣時，則基矩陣對應的列向量稱為基向量，其余列向量稱為非基向量 基向量對應的變量稱為基變量，非基向量對應的變量稱為非基變量 在上例中B2的基向量是A中的第一列和第四列，其余列向量是非基向量，x1、x4是基變量，x2、x3、x5是非基變量。基變量、非基變量是針對某一確定基而言的，不同的基對應的基變量和非基變量也不同。7/25/2022可行解 滿足式（1.2）及（1.3）的解X=（x1,x2，xn)T 稱為可行解 。基本可行解，若基本解是可行解則稱為是基本可行解（也稱基可行解）。 例如， 與X=（0，0，0，3，2，）都是例1 的可行解。 基本解 對某一確定的基B，令非基變量等于零，利用式（1.）

3、解出基變量，則這組解稱為基的基本解。 最優(yōu)解 滿足式 （1 .1）的可行解稱為最優(yōu)解，即是使得目標函數達到最大值的可行解就是最優(yōu)解，例如可行解 是例2的最優(yōu)解。7/25/2022顯然，只要基本解中的基變量的解滿足式（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，7/25/2022由于 是基本解，從而它是基本可行解，在 中x10,因此不是

4、可行解，也就不是基本可行解。 反之，可行解不一定是基本可行解例如 滿足式（1.2）（1.3），但不是任何基矩陣的基本解?；窘鉃?/25/2022最優(yōu)基 基可行解對應的基稱為可行基；基本最優(yōu)解對應的基稱為最優(yōu)基，如上述B3就是最優(yōu)基，最優(yōu)基也是可行基。當最優(yōu)解唯一時，最優(yōu)解亦是基本最優(yōu)解，當最優(yōu)解不唯一時，則最優(yōu)解不一定是基本最優(yōu)解。例如右圖中線段 的點為最優(yōu) 解時，Q1點及Q2點是基本最優(yōu)解,線段 的內點是最優(yōu)解而不是基本最優(yōu)解。 基本最優(yōu)解 最優(yōu)解是基本解稱為基本最優(yōu)解。例如，滿足式（1.1）(1.3)是最優(yōu)解,又是B3的基本解,因此它是基本最優(yōu)解.7/25/2022基本最優(yōu)解、最優(yōu)解、基

5、本可行解、基本解、可行解的關系如下所示：基本最優(yōu)解基本可行解可行解最 優(yōu) 解基本解例如,B點和D點是可行解,不是基本解;C點是基本可行解;A點是基本最優(yōu)解,同時也是最優(yōu)解、基本可行解、基本解和可行解。7/25/2022凸集設K是n維空間的一個點集，對任意兩點 時，則 稱K為凸集。 就是以X（1）、X（2）為端點的線段方程，點X的位置由的值確定，當=0時，X=X（2），當=1時X=X（1）凸組合 設 是Rn中的點若存在 使得 成立， 則稱X為 的凸組合。7/25/2022極點 設K是凸集， ，若X不能用K中兩個不同的 點 的凸組合表示為則稱X是K的一個極點或頂點。 X是凸集K的極點即X不可能是K

6、中某一線段的內點，只能是K中某一線段的端點。 7/25/2022【定理1.1】 若線性規(guī)劃可行解K非空,則K是凸集. 【定理1.2】線性規(guī)劃的可行解集合K的點X是極點的充要條件為X是基本可行解.【定理1.3】若線性規(guī)劃有最優(yōu)解,則最優(yōu)值一定可以在可行解集合的某個極點上到達,最優(yōu)解就是極點的坐標向量.定理1.2刻劃了可行解集的極點與基本可行解的對應關系，極點是基本可行解，反之，基本可行解一定是極點，但它們并非一一 對應 ，有可能兩個或幾個基本可行解對應于同一極點（退化基本可行解時）。線性規(guī)劃的基本定理7/25/2022 定理1.3描述了最優(yōu)解在可行解集中的位置，若最優(yōu)解唯一，則最優(yōu)解只能在某一極點上達到，若具有多重最優(yōu)解，則最優(yōu)解是某些極點的凸組合，從而最優(yōu)解是可行解集的極點或界點，不可能是可行解集的內點 。 若線性規(guī)劃的可行解集非空且有界，則一定有最優(yōu)解；若可行解集無界，則線性規(guī)劃可能有最優(yōu)解，也可能沒有最優(yōu)解。 定理1.2及1.3還給了我們一個啟示，尋求最優(yōu)解不是在無限個可行解中去找，而是在有限個基本可行解中去尋求。下一節(jié)將介紹一種有效地尋找最優(yōu)解的方法。7/25/20221. 線性規(guī)劃常用的