【天津大學】《運籌學》（精品課） P5 - 5. 單純形法 教學錄像（2）

基本解與基本可行解 我們當A中的基B取定後 不妨設B表示A中的前面m列 則可把A寫成分塊矩陣的形式 也就是計A等於Bn 這個B表示A中的前m列 它是一個基 那麼後面的n-m列 因爲A一共有n列 後面的n-m列 就是飛機矩陣G座n 那麼係數陣A就可以寫成這樣分塊的形式 相應的我們可以把決策變量x的向量形式 也可以寫成分塊的形式 因爲剛纔我們已經說過 這個A中的每一列都對應於一個變量 和G矩陣對應的變量 這些變量就是G變量 它的向量記號就是xB 和飛機矩陣對應的變量 就是飛機變量 它們的記號xn 也就是隨着G的確定和係數陣按G分塊形式之後 決策變量x也可以寫成相應的分塊形式 於是我們的約束中的資源約束ax等於b 就可以用分塊的形式加以表示 其中a表示成bn分塊 x的相應分塊是xb和xn 那麼按照分塊矩陣的乘法規則 把這個等式左端分塊矩陣部分把它乘出來 就是後面這個表達式 也就是bxb加上nxn 那麼等於右端就是小寫的字母b 也就是資源限制向量 在這個表達式中 由於它的第一項這個b是一個G 它是可逆的 所以我們在這個式子的兩端 同時左乘一個b逆 那麼第一項這個原來是bxb這一項 左乘了b逆之後 b逆乘以b是單位就可以不寫了 那就剩下了一個xb 然後這個等式的第二項原來是nxn 左乘了b逆就是b逆nxn 把它移到等式的右端 等式右端原來就是一個資源限制向量b 乘以左邊的 左邊乘以b逆之後 就是b逆b 那麼上面這個約束方程的分塊矩陣表達式 左乘了b逆之後 就可以寫成這樣的形式 也就是xb等於b逆b減去b逆nxn 這相當於是把積變量給解出來了 也就是把積變量xb的表達式表示了出來 這個表達式 它的右端是b逆b減去b逆nxn xn是非積變量 那麼這就是用一個含有非積變量的表達式來表示積變量的表達式 這個表達式也可以看作是 約束方程ax等於b 資源約束部分 約束方程ax等於b的一個通解表達式 在這個通解表達式中 xn每取一組值 則可以得到相應的xb的一組值 那麼特別當取xn通通爲0的時候 因爲xn是一個向量 它表示所有的非積變量 我們剛纔這個通解表達式呢 xn取任意的值的時候就可以得到 取任意不同值的時候可以得到xb的相應的值 那麼特別取xn都等於0的時候 這個時候呢我們就得到xb的表達式 就是b逆b 因爲這個時候呢 xn那一項爲0了 所以xb就是等於b逆b 我們把這樣的一組解 也就是xn等於0 xb等於b逆b的這組解 把它表示出來 就是如右邊這個表達式 也就是x等於b逆b0 這組解是在通解表達式的所有解中的一個特殊的解 它相應於一個積 當然積如果換了 那這個解也就換了 但是一個積它相應於的 這個一個解呢 它是一個特定的表達式 我們就把這樣形式的一組解 把它稱作一個基本解 把它稱作一個就是ax等於b的 形如b逆b0的這樣的一個解 就稱爲線性規劃的一個基本解 那麼基本解是什麼呢 首先它是ax等於b的解 約數方程的解 在這個約數方程的所有解中 它是非積變量通通取0的相應的這組解 非積變量通通取0 得到的這個解 也就是突出了積變量的這個在裏面的作用 也就是它的表達式裏 主要體現的是積變量部分 是由一個積所決定的 表達式剛纔推導出是b逆b 也就是說呢 一個基本解是由一個積所決定的 那麼剛纔也說了基本解 它僅是資源約數的解 並未要求它非負 因此這個基本解並不一定都可行 當一個基本解滿足非負約數的時候 這樣的基本解就是可行的基本解 我們就把它稱作基本可行解 簡稱基可行解 好 我們把這個概念 稍加再小節一下 我們剛纔介紹了基本解和基本可行解的概念 所謂基本解就是 線性規劃的約數中的資源約數部分 as等於b的 形如b逆b0 也就是非積變量通通等於0時的 這樣的解稱爲它的一個基本解 一個基本解是由一個積所決定的 那麼這個基本解 如果又滿足非負條件 就稱爲基本可行解 下面舉例說明 在剛纔的例1.3的模型中 我們在 例1.3中啊 已經分析了 這個約數的係數矩陣中的 的基矩陣 b1和b2 其中b1 是由這個約數係數矩陣的後兩列組成的單位陣 而b2呢 是由前兩列組成的一個子陣 這兩個基都可以相應於它們的基本解 下面我們來分析這兩個基相應的基本解 是否基本可行解 那麼爲了分析這個題呢 首先基本解的概念要清楚 什麼叫基本解 怎麼算呢 基本解剛纔說了 你首先得把它相應的那個基先確定出來 剛纔這兩個基 b1和b2已經確定明確了 兩個基有了之後 怎麼算它相應的基本解呢 由定義 就是先求這兩個基的逆陣 也就是b逆 拿b逆分別乘以右端向b 也就是小寫的b 它表示資源限制向量 拿b逆乘以b 得到的就是這個基本解中的基變量部分 非基變量通通取零 這是基本解的算法 那麼這個基本解計算出來之後 只要它滿足非負條件 也就是這個解的所有分量都是大於等於零的話 那它們就是基本可行解 下面我們對這個例子進行分析 首先來看b1 這個b1呢 剛纔說了是由這個立體的係數陣A中的後兩列 三四兩列組成的是一個單位陣 我們有線性代數的知識可知 單位陣 它的逆陣的就是它本身 這裏涉及到逆陣的概念 一個方陣的逆矩陣 是指和它相乘 無論左乘還是右乘 和它相乘等於單位陣的矩陣 那當然這個現在這個b1就是單位陣 誰和它相乘得單位陣呢 它的根據定義呢 它的逆陣也是一個單位陣 也就是b1的逆是單位陣 我們用這個b b逆乘以小寫的b 也就是b逆b 經過運算得到的結果 也就是b逆b乘出來的結果 就是基本解中的g變量部分 那麼由於這個g呢是三四兩列 所以啊 它的g變量也是x3和x4 也就是說我們算出的這個b逆b呢 我們看到等於1 3這個向量 它呢就是這個g相應的基本解中的 x3和x4的取值 於是我們可以寫出 相應於這個g b1的基本解 就是0013 前兩個分量是0 是因爲前兩個分量是非g變量 因爲這個g是三四兩列嘛 它的g變量就是x3和x4 這個解 也就是相應於b1的這個基本解 0013 由於它的所有分量都是非負 都是大於等於零的 也就是它滿足非負約數 因此它是一個基本可行解 我們再來看 第二個矩陣 b2 b2是由係數陣A中的前兩列所組成 我們經過線性代數的知識 可以計算出它的逆陣 計算逆陣的方法 不是唯一的 由線性代數的知識可以知 它可以怎樣計算呢 比如說我們現在求 這個b2的逆陣 可以把b2和一個和它同階的單位陣並排寫在一起 然後採用初等行變換的方法 把這個b2的部分削成單位陣 那麼它並排的那個單位陣的位置 跟着一塊變出來的那個結果就是b逆 也就是說b逆可以用線性代數的方法 比如剛纔說的初等行變換的方法求得 我們現在假設求得的結果b2逆 如這個矩陣所示 它應該滿足和b2相乘等於單位陣 好b2逆求出來之後 我們就可以來求基本解了 基本解由定義 就是用b逆b計算出g變量部分 我們經過計算 用b2逆乘以b b2逆b 這個b小寫的b就是約數的等式的右端項 在這道題就是13 那麼我們把這個b逆b經過計算之後得到的結果 看一下它是五分之七和負五分之五組成的一個項量 這個應該是這個b2相應的基本解中的g變量部分 由於b2是a中的前兩列組成 也就是p1和p2 那麼相應的g變量應該也是前兩個變量 也就是x1和x2 因此這個基本解寫出來就是x等於五分之七負五分之一 由於這個基本解中有一個負五分之一不滿足非負要求 所以它不是基本可行解 它只是一個基本解 它不是基本可行解 好 我們通過這個例子 主要複習了一下 一個基本概念 一組重要的基本概念 就是基本解和基本可行解的概念 這個例子說明了怎樣計算基本解和基本可行解 計算基本解 就是要首先確定係數陣中一個g 只有確定了一個g才能計算基本解 這個g確定之後怎麼算基本解呢 就是用B逆B 確定的這個g就是B 先算它的逆陣B逆 再乘以右端向小寫的B 那麼B逆B就作爲這個基本解的g變量部分 非g變量通通等於零 這個基本解算出來之後 只要是滿足非負約數 全部分量都是大於等於零 它就是一個基本可行解 否則的話 它只能是一個基本解 而不是基本可行解 我們剛纔介紹了兩組概念 第一組概念是g矩陣 g向量和g變量 第二組概念是基本解和基本可行解 下面我們把兩組概念間的聯繫稍加小節一下 我們在第一組概念中介紹的是g矩陣 g向量和g變量的概念 它們都是相應於一個g 所謂一個g就是係數陣A中的一個可逆子陣 用大寫字母B來表示 一個g確定了 它相應的g向量和g變量也就跟着確定了 那麼在這個g確定之後 接下來就可以計算 這個g相應的一個基本解 就是剛纔例子中 B逆B計算它的g變量部分 非g變量爲零的這樣的解 就是這個g相應的一個基本解 這個基本解假若是非負的 每個分量都是非負的 它就是基本可行解 我們再用一個圖示 再把幾個概念之間的關係呢 再來看一下 我們在這組概念的學習中 首先學習了可行解的概念 可行解的集合 如左邊這個圓圈所示 那麼在可行解的外面 假如所有的解用這個大的方塊 那麼可行解的集合之外 就是非可行解 剛纔我們又學習了基本解的概念 基本解的集合 用右邊這個圓圈表示 那麼基本解 它不一定都是可行的 如果一個基本解是可行的 也就是基本解和可行解的公共部分了 這一部分呢 我們就把它稱作基本可行解 基本可行解 也就是可行解和基本解兩個集合的交集 用圖中陰影線所示 我們看到基本可行解 是可行解中 因爲我們求最優解的話 我們是要在可行解中尋優 那麼在可行解的這麼大的一個範圍裏 基本可行解只是它的一部分 那麼這個基本可行解 又是可行解中的哪些解呢 或者直觀的說 基本可行解 在可行域中 是由哪些特殊的點來組成呢 我們接下來呢 有一組結論 也就是可以證明有下面的這些關係 這幾個結論呢 都是線性規劃的基本定理 其中呢 第一個和第三個 我們已經在圖解法中 已經進行了總結 已經能夠由圖解法看到了 但是我們呢 這裏的第二個定理 是我們現在這一節給出的 我們重點來看一下這個第二個定理 這個定理就是回答了剛纔提出的問題 剛纔提出的問題是 基本可行解是可行解中的哪些點呢 因爲基本可行解 只是可行域中的一部分點 到底是哪些點呢 我們這個定理給出了答案 那就是線性規劃可行域的頂點 與基本可行解一一對應 什麼叫一一對應呢 就是在這個定理 它的意思就是說 線性規劃可行域的頂點 只要是頂點 一定是一個基本可行解 是一個頂點 它一定對應於一個基本可行解 也就是可以表示成 B0的形式 反過來呢 一個基本可行解 也就是由一個G所計算出的 B0的 而且滿足可行的這樣一個 一個G 它在幾何上 也一定 可以找到可行域的一個頂點 與之對應 它們兩個是一一對應的 那麼這個定理 給我們一個很重要的啓示 實際上這個啓示呢 是接着我們由圖解法 已經得到的這第三個結論 第三個結論 我們當時在圖解法已經說過 由圖解法可知 線性規劃的最優解 若存在的話 一定能在可行域的頂點 也稱腳點處獲得 那麼這個腳點只是 一個幾何上的一個概念 對於高維的複雜的線性規劃 大規模的線性規劃問題 是很難在幾何圖形上 畫出來的 我們對於二維的問題 簡單的問題 可以畫圖 但是呢 對於複雜大規模的問題 很難畫出它的圖形 來找它的頂點 因此就需要 我們研究頂點的數學表達式 也就是解析表達式 我們不依靠畫圖 也能表示出頂點是什麼 我們今天介紹的 這個第二個定理 就解決了這個問題 也就是頂點的 解析表達式的問題 我們不依靠畫圖直觀來看 也可以表示出頂點是什麼 也可以找到誰是頂點 那怎麼找呢 我們這個結論不是已經說了嗎 頂點是和基本可行解 一一對應的 一個線性規劃 只要確定了這個模型 它的係數陣也就確定了 係數陣A確定了之後 它裏邊的G 也就可以確定出來 每一個G相應一個基本解 其中可行的那些基本解呢 就是它的基本可行解 也就是可行域的頂點 因此 我們在可行域的頂點中 尋優的思想 就可以具體實現爲 一個一般的算法了 這個一般的算法就是 在基本可行解中尋優 那麼 由於頂點與基本可行解 一一對應 基本可行解 又是由G所決定 一個係數矩陣的G的個數 是有限個 我們剛纔說它最多是個數CNM個 那也就是說在頂點中尋優的工作 是可以經過有限步而完成的 經過這樣的分析 經過這幾個基本定理給出的結論 我們就可以來設計一種一般的算法 這個算法呢就是 我們將來介紹的單純型方法