【正文】 條件判定 X是否是基礎解。 其中 ， XB = B?1 b， XN = 0 – XB 是 基礎解 必須滿足如下條件： ? 1） 非 0分量的個數(shù) ? m； ? m個基變量所對應的系數(shù)矩陣為非奇異的； ? 滿足 m個約束條件。 二、 標準型線性規(guī)劃解的若干基礎概念 ? 標準型有 n+m 個變量， m 個約束行 ? “ 基 ”的概念 – 在標準型中，技術系數(shù)矩陣有 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 nmC ?二、標準型線性規(guī)劃解的若干基礎概念 ? 可行解 與 非可行解 – 滿足約束條件和非負條件的解 X 稱為 可行解 ，不滿足約束條件或非負條件的解 X 稱為 非可行解 ? 基礎解 – 對應某一基 B且令其 非基變量 XN = 0，求得 基變量 XB的值。 該基礎解中 x1和 x3均大于 0，滿足線性規(guī)劃（ 10）的變量非負約束條件，因此，該基礎解（ 7）是線性規(guī)劃（ 10）的基礎可行解。 ???????5231 211xxB變量 x1和 x2為基變量，變量 x3為非基變量，令 x3=0， 得 解（ 5）為線性規(guī)劃（ 10）的基礎解，但 因 該基礎解中 x1= 10，不滿足線性規(guī)劃（ 10）的變量非負約束條件，因此，該基礎解（ 5） 是線性規(guī)劃（ 10）的基礎非可行解。如： (10 ) 0,0,085253..32)(321321321321?????????????????xxxxxxxxxtsxxxxMaxf一、線性方程組的解 對于 上述標準型線性規(guī)劃（ 10） ,稱 B1 、 B2和 B3為線性規(guī)劃（ 10）的基。 一、線性方程組的解 同樣，由于方程組組（ 3）中的變量 x1和 x3的系數(shù)矩陣行列式|B2|不等于 0與 變量 x2和 x3的系數(shù)矩陣行列式 |B3|不等于 0， 即 0112 11B 2 ??? 0115 13B 3 ??才能得到方程組（ 3）的通解或特解（ 6）或（ 7） 與 通解或特解（ 8）或（ 9） 。 一、線性方程組的解 考慮如下線性方程組的解： (1) 852532121???????xxxx(2) 2121??????xx再考慮如下線性方程組的解： (3) 85253321321?????????xxxxxx (4)221333231???????????xxxxxx(5) 021321?????????xxx一、線性方程組的解 類似地，如果將方程組（ 3）中的變量 x2或 x1當成常數(shù)，分別移到其方程的右邊后采用消元法進行求解，則也可得到如下兩組 通 解 及其特解 ： (6) 223222321??????????xxxxxx(8) 21212123111312??????????????xxxxxx(7) 02321???????xxx(9) 02123132???????????xxx一、線性方程組的解 仔細觀察和思考方程組（ 3）的三組通解（ 4）、（ 6）和（ 8）或三組特解（ 5）、（ 7）和（ 9）是如何得到的，以及能夠得到這些通解或特解的條件是什么？根據(jù)求解線性方程組克萊姆條件可知，能夠得到方程組（ 3）的通解（ 4）或特解（ 5）的條件是方程組（ 3）中的變量 x1和 x2的系數(shù)矩陣行列式不等于 0，即 015231B1 ???或變量 x1和 x2的系數(shù)矩陣 B1是非奇異矩陣或變量 x1和 x2的系數(shù)列向量是線性無關。 本 課程 將從大家熟悉的一些簡單問題入手，然后逐步過渡到運籌學一些相對比較抽象和難的概念和原理。為了幫助大家比較容易理解這些概念，我們先從大家熟悉的兩個變量兩個線性方程組這一簡單問題入手，然后逐步過渡到我們所要討論的線性規(guī)劃問題的基和基礎解等相關概念。令 g(x) = f(x) = CX, 有 min f(x) = max [ f(x)] = max g(x) ? 第 i 個約束的 bi 為負值，則該行左右兩端系數(shù)同時反號，同時不等號也要反向 ? 第 i 個約束為 ? 型，在不等式左邊增加一個非負的變量 xn+i ， 稱為松弛變量；同時令 +i = 0 ? 第 i 個約束為 ? 型，在不等式左邊減去一個非負的變量 xn+i ， 稱為剩余變量；同時令 +i = 0 ? 若 xj ?0，令 xj= xj? ，代入非標準型，則有 xj? ? 0 ? 若 xj ?不限，令 xj= xj? xj?， xj? ? 0， xj? ? 0，代入非標準型 29 五、 變換舉例： ??????????????????????????????????????????????0,2004006653004432..0004423)(max:65433216332153321433216543321xxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxf標準型 線性規(guī)劃問題的解和 基礎 定理 本章開始到現(xiàn)在已討論的內(nèi)容，相信大部分讀者都會感到比較容易理解和掌握。此時，決策變量就有 n+m個。我們知道，對于線性規(guī)劃背景模型，有 m個約束方程，且每個約束方程的不等式均為“ ?”號。 ? 線性規(guī)劃求解的 基礎 原理和單純形法 線性規(guī)劃問題的標準形 一、線性規(guī)劃模型一般形式 二、求解思路 規(guī)定一標準型線性的規(guī)劃問題數(shù)學模型； 如何把非標準形的線性規(guī)劃問題數(shù)學模型轉化為標準形線性規(guī)劃問題數(shù)學模型？ 如何求解標準形線性規(guī)劃問題數(shù)學模型。 ? 上述 3個結論是線性規(guī)劃的 3個 基礎 定理，可以用嚴格的數(shù)學方法進行證明 。,( ..)(max210212121010bbbbaaaPxxxXcccC0XbxPtsCXxfmmjjjjTnnnjjj????23 矩陣式 0]0,00[),(),()。: 。: 。 2）背景模型的思考 利用一些相對比較簡單的問題來闡述一些相對復雜和抽象的運籌學中的一些 基礎 概念和原理是 本課程 力求在 教學 中體現(xiàn)的第一個特點， 希望大家 用心體會 。把該背景模型的條件一般化后可敘述如下：用有限量的幾種資源生產(chǎn)若干種產(chǎn)品，如何安排生產(chǎn)，才能使工廠的總收入或利潤達到最大。 線性規(guī)劃數(shù)學模型的定義 定義 有一個目標函數(shù)和一組約束方程，且目標函數(shù)和約束方程都是線性的數(shù)學模型稱為線性規(guī)劃數(shù)學模型。當目標為成本型時取最小，而當目標為效益型時取最大。 問該該加工廠應如何搭配