【文章內容簡介】 手，然后逐步過渡到運籌學一些相對比較抽象和難的概念和原理。這是本 課程教學 力求的另一特點。 一、線性方程組的解 考慮如下線性方程組的解： (1) 852532121???????xxxx(2) 2121??????xx再考慮如下線性方程組的解： (3) 85253321321?????????xxxxxx (4)221333231???????????xxxxxx(5) 021321?????????一、線性方程組的解 類似地，如果將方程組（ 3）中的變量 x2或 x1當成常數，分別移到其方程的右邊后采用消元法進行求解，則也可得到如下兩組 通 解 及其特解 ： (6) 223222321??????????xxxxxx(8) 21212123111312??????????????xxxxxx(7) 023231?????xxx(9) 02123132???????????xxx一、線性方程組的解 仔細觀察和思考方程組（ 3）的三組通解（ 4）、（ 6）和（ 8）或三組特解（ 5）、（ 7）和（ 9）是如何得到的，以及能夠得到這些通解或特解的條件是什么？根據求解線性方程組克萊姆條件可知，能夠得到方程組（ 3）的通解（ 4）或特解（ 5）的條件是方程組（ 3）中的變量 x1和 x2的系數矩陣行列式不等于 0，即 015231B1 ???或變量 x1和 x2的系數矩陣 B1是非奇異矩陣或變量 x1和 x2的系數列向量是線性無關。顯然，這三個條件是等價的。 一、線性方程組的解 同樣，由于方程組組（ 3）中的變量 x1和 x3的系數矩陣行列式|B2|不等于 0與 變量 x2和 x3的系數矩陣行列式 |B3|不等于 0， 即 0112 11B 2 ??? 0115 13B 3 ??才能得到方程組（ 3）的通解或特解（ 6）或（ 7） 與 通解或特解（ 8）或（ 9） 。 將上面討論的方程組（ 3）加上一目標函數和變量非負約束條件后就變成一標準型線性規(guī)劃。如： (10 ) 0,0,085253..32)(321321321321?????????????????xxxxxxxxxtsxxxxMaxf一、線性方程組的解 對于 上述標準型線性規(guī)劃（ 10） ,稱 B1 、 B2和 B3為線性規(guī)劃（ 10）的基。因利用其中任何一個基 B1 或 B2或 B3，都能得到線性規(guī)劃（ 10）的一組通解和特解（見式（ 4） （ 9））。 ???????5231 211xxB變量 x1和 x2為基變量，變量 x3為非基變量，令 x3=0， 得 解（ 5）為線性規(guī)劃（ 10）的基礎解，但 因 該基礎解中 x1= 10，不滿足線性規(guī)劃（ 10）的變量非負約束條件，因此，該基礎解（ 5） 是線性規(guī)劃（ 10）的基礎非可行解。 ???????1211 312xxB變量 x1和 x3為基變量，變量 x2為非基變量，令 x2=0， 得 解（ 7）為線性規(guī)劃（ 10）的基礎解 。 該基礎解中 x1和 x3均大于 0，滿足線性規(guī)劃（ 10）的變量非負約束條件，因此，該基礎解（ 7）是線性規(guī)劃（ 10）的基礎可行解。 ???????1513 323xxB變量 x2和 x3為基變量，變量 x1為非基變量，令 x1=0， 得 解（ 9）為線性規(guī)劃（ 10）的基礎解 .該基礎解中 x2和 x3均大于 0，滿足線性規(guī)劃（ 10）的變量非負約束條件，因此，該基礎解（ 9）是線性規(guī)劃（ 10）的基礎可行解。 二、 標準型線性規(guī)劃解的若干基礎概念 ? 標準型有 n+m 個變量， m 個約束行 ? “ 基 ”的概念 – 在標準型中，技術系數矩陣有 n+m 列，即 A = ( P1, P2 , … , Pn+m ) – A中線性獨立的 m 列，構成該標準型的一個 基 ，即 B = ( P1 ?, P2 ? , … , Pm ?)， | B | ? 0 – P1 ?, P2 ? , … , Pm ?稱為 基向量 – 與 基向量 對應的變量稱為 基變量 ，記為 XB = ( x1 ?, x2 ? , … , xm ? )T，其余的變量稱為 非基變量 ，記為 XN = ( xm+1 ?, xm+2 ?, … , xm+n ? ) T ， 故有 X = （ XB ， XN ) – 最多有 個基 m nC ?二、標準型線性規(guī)劃解的若干基礎概念 ? 可行解 與 非可行解 – 滿足約束條件和非負條件的解 X 稱為 可行解 ，不滿足約束條件或非負條件的解 X 稱為 非可行解 ? 基礎解 – 對應某一基 B且令其 非基變量 XN = 0，求得 基變量 XB的值。稱 X = (XB , XN)T為 基礎解。 其中 ， XB = B?1 b， XN = 0 – XB 是 基礎解 必須滿足如下條件： ? 1） 非 0分量的個數 ? m； ? m個基變量所對應的系數矩陣為非奇異的； ? 滿足 m個約束條件。 二、標準型線性規(guī)劃解的若干基礎概念 基礎可行解 與 基礎非可行解 基礎解 XB 的非零分量都 ? 0 時，稱為 基礎可行解 ，否則為 基礎非可行解。 退化 解 基礎可行解 的非零分量個數 m 時，稱為 退化解 可行基 對應于基礎可行解的基稱為 可行基 最優(yōu)解 使目標函數達到最優(yōu)的 基礎 可行解稱為最優(yōu)解 無窮多最優(yōu)解 當最優(yōu)解的基變量組成不止一個時，線性規(guī)劃有 無窮多最優(yōu)解 39 三、 線性規(guī)劃標準型問題解的關系 約束方程的 解空間 基礎解 可行解 非可行解 基礎 可行解 退化解 四、線性規(guī)劃解的判定 對于某一線性規(guī)劃的任意一個解 X，我們如何判定 X是基礎解、或是基礎可行解、或是基礎非可行解、或是非可行解、或是可行解呢？ 判定 步驟： 寫出給定線性規(guī)劃問題的標準型線性規(guī)劃； 根據基礎解的三個條件判定 X是否是基礎解。當三個條件均滿足時， X才是基礎解；否則 X不是基礎解。若 X是基礎解，轉3；否則，轉 4； X是否滿足非負約束，即其基變量值是否都大于 0？若是，X是基礎可行解；否則 X是基礎非可行解。 將 X代入給定線性規(guī)劃的所有約束方程，包括非負約束，若X滿足所有約束方程，則 X為可行解，否則 X為非可行解。 41 五、線性規(guī)劃解的判定舉例 ??????????????????0,78102..46)(max543215242132121xxxxxxxxxxxxxtsxxxf1187654322 x1876543O109x2A BCEDFGH123f(x)=36K非基變量 基變量 圖中的點 解 x1, x2 x3 = 1 0 x4 =8 x5 =7 O 基礎可行解 x1, x3 x2 = 1 0 x4 = 2 x5 = 3 F 基礎解 x1, x4