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

下面我們來介紹單純型方法的原理步驟 單純型方法是一種迭代的算法 所謂迭代就是按照一種模式反覆進行 也就是一個搜尋的過程 單純型法的思想剛纔已經說過了 是在可行域的頂點 也就是基本可行解中進行尋優 而且剛纔也已經說過 頂點的個數是有限個 因爲G的個數是有限個 因爲每個頂點是和一個基本可行解相對應 而基本可行解由G所決定 所以G的個數是有限個 所以頂點的個數一定是有限個 我們就是把所有的頂點全部都搜尋過來 也可以在有限不中止 但是單純型法它並不是枚矩法 它是迭代的方法 但並不是枚矩 也就是說它不是把所有的頂點 百分之百全都得搜尋過來 而是它設計了一種一步比一步 一步比一步的搜索 效果更好的一個機制 那麼我們呢 下邊來概括的先來看一下 單純型法是一個什麼樣的一個機制和過程 單純型法 它的主要步驟可以歸納爲三個步驟 既然它是一個迭代的方法 首先必須有一個初始的出發點 一個初始的頂點 它是在頂點中尋憂嗎 每一步它就要迭代 每一步迭代它就是要來這個考察一個頂點 所以它要第一步肯定是要從一個初始的頂點 也就是初始的基本可行解中出發 所以線性規劃步驟的第一步可以歸納爲 確定一個初始基本可行解 這個初始基本可行解就是一個初始的腳點 或者說頂點 找到這個初始的基本可行解之後 接下來第二個步驟是什麼呢 單純型法設計的是第二步 檢驗這個初始基本可行解是否最優 它設計了一個公式方法 可以通過計算來判斷這個解是否最優 對於任一個它檢驗的方法 不僅對初始可行解 它對任意的一個基可行解 都能檢驗它是否最優 經過檢驗 如果是最優 計算停止 得到結果 如果不是最優呢 那麼就需要繼續計算 繼續計算 大家想一下該怎樣算呢 因爲剛纔已經說了是在頂點中尋優 也就是在基本可行解中尋優 所以當前這個基本可行解如果不是最優 我們就要繼續搜索下一個基本可行解 我剛纔已經說過單純型法不是每局法 它雖然都是在腳點中尋優 都是在基本可行解中尋優 但是呢 它每搜尋的下一個基本可行解 它可以保證設計一種機制 保證每搜尋的下一個基本可行解 一定來得比上一個更優 就是下一個一定比上一個來得更優 什麼叫更優呢 什麼叫更好 好與不好 我們的評價準則是目標 哪個解是目標最大 是目標最優 它就是更好的 是最優解 那麼哪個解是目標更大 它就是更好的一個解 也就是說呢 單純型法的第三步是 尋找一個更好的下一個基本可行解 那麼找到下一個更好的基本可行解之後 接下來 接哪一步呢 我們不難分析出 它接下來要再進行最優性檢驗 也就是說 這個第三步完成之後 要回到第二個步驟 再對這個新的基本可行解 再進行最優性檢驗 檢驗它是否最優 假若這個新的基本可行解經過檢驗 是最優了 滿足最優性的條件了 那計算停止 如果還不滿足 則還要接着用同樣的模式 接着再繼續尋找再下一個更好的基本可行解 也就是這個 這三個步驟 單純型法的這三個步驟啊 其中二三兩個步驟 是一個形成一個循環 就是形成一個這個 哎 反覆的一個迭代的過程 形成一個迭代的過程 那麼 這個框圖呢 介紹了 單純型法的步驟的框架 需要說明的是 單純型法的前提 是要把模型化爲標準型 也就是說呢 剛纔在預備知識裏 介紹了什麼叫標準型 以及 非標準的各種形式的模型 如何化爲標準型 我們在用單純型法求解線性規劃之前 首先要把模型化爲標準型 然後再進入單純型法 這三個步驟的程序 好 接下來 我們將依次介紹 剛纔圖示的單純型法的三個步驟 剛纔如圖所示的第一步是 確定一個初始基可形解 也就是一個初始的頂點 由於基可形解 也稱爲基本可形解 這個基可形解呢 前面已經學過 它是由一個基所決定的 這個基既然使得它相應的基本解可形 我們也可以稱這個 基本可形解相應的那個基 稱爲一個可形基 也就是 一個基它一定相應於一個基本解 如果這個基本解可形 我們就可以稱這個基爲一個可形基 那麼由於一個基本可形解的確定 我們現在的步驟 是確定一個初始基可形解 而一個基可形解 是由一個可形基所決定 因此 確定初始基可形解 X0的工作 也相當於說主要是確定一個初始可形基 基作B0 因爲只要B0確定出來了 它就可以算出相應的那個基本解 B0就是初始基本可形解 那麼這個初始的可形基B0 怎樣選取確定呢 我們單純刑法設計的這個步驟 很簡單 它就把這個初始的可形基B0取作單位振 單位振記作I 具體方法 假若A中已經含有單位子振 那麼這個B0就是這個A中所含的單位子振I 比如在剛纔前面我們 在前面的內容中 我們通過把模型化爲標準型的時候 如果原來是小於等於約數 加了鬆弛變量 化爲標準型的過程中 自然就加出一個I來 因爲那個鬆弛變量的係數部分就構成一個單位子振I 也就是說 如果這個模型化爲標準型之後 A中已經含有I了 那麼這個初始可形基B0就取爲I 如果A中不含有I 我現在說的這個A是化成標準型以後的等式約數的那個係數振A 如果不含有I 則需要用一些方法 我們在單純型法中管它叫人工變量法 來構造出一個單位振I 總之呢 我們初始可形基B0就取爲單位振I 那麼取B0爲單位振I了以後 它相應的這個初始基可形基X0 也就可以算了出來 這個X0具體表達是 因爲B0是單位振很簡單 我們可以呢 馬上把X0相應的這個 這個表達式 解的表達式 把它表示出來 X0就是由這個初始基B0計算出的基本解 也就是B逆B0 那麼B逆因爲是單位振 B逆B這個B0逆B實際就是B 而這個B呢 小寫的B是 約數方程的右端 表示資源限制向量 我們在標準型中已經規定它是大於等於零的 所以這個X0等於B0 大於等於零是可行的 初始基可形解確定之後 接下來 我們要對它進行最優性檢驗 檢驗這個解是否最優 首先我們來想一下 該用什麼來構造檢驗的方法呢 我們知道檢驗一個解是否最優 或者一個解是不是更優 是用目標來進行判斷的 而目標的表達式 是Z等於CX 這是線性規劃目標的表達式 我們在前面 介紹基本可行解的概念的時候 曾經把決策變量的向量 X按照G來進行了分塊 也就是把X寫成XB和XN 其中XB是基變量部分 它可以表示爲B逆B減去B逆N XN 所以我們的目標表達式 就可以寫成分塊的形式 隨着X的分塊 我們的目標的係數C 也就是稱爲價格係數的C 也可以寫成分塊的形式 分爲CB和CN 按照分塊矩陣的乘法規則 那麼把這個算出來 就是CBXB加上CNXN 把其中的CB這一部分 CB的乘以的XB這一部分 把它用剛纔的XB的表達式 把它代入 就是CBB逆B減去B逆NXN 後邊加上一個CNXN 這個表達式中 有兩項是含有XN的項 我們把它整理在一起 把這個XN提取出來 那麼前面這一項CBB逆B 這是一個不含變量XN的項 只要B決定了 這一項就是一個定數 而後邊那一項是含有XN的項 它隨着XN的取值不同 可以有不同的結果 那麼我們分析這個XN的這一項 這一項的係數部分 也就是CN減去CB逆N 這一塊是XN的係數部分 如果這一塊的係數 因爲這一塊是一個矩陣表達式 那麼它的每個分量 假如都是小於等於零的 這個時候因爲XN它是要可行 滿足可行的條件是要非負的 如果這個係數是小於等於零的 也就是這塊黃線所示的這一塊XN的係數 如果都是小於等於零的 而XN是大於等於零的 它倆乘出來的結果 那就應該是一個小於等於零的 那麼由於前面這一項是一個定數 加上後面一項 如果是小於等於零 也就是CB逆N加上一個小於等於零的值的話 是要比CB逆N來得下降的 我們現在標準形式追求極大化 所以如果這個黃色方框所示的這塊係數部分 它的符號都是小於等於零的 那麼這個時候只有XN通通取零值的時候 可以使後面那一項就爲零了 只剩下CB逆N 這個時候是目標Z可能達到的最大的值 因此我們就把這塊係數部分 它的符號 把這塊係數部分的向量記號記爲σ 當這個σ的所有分量都是小於等於零的時候 當前這個基本可行解 也就是XN等於零時的這個解 就是最優的 否則呢 如果這個σ 它裏邊 它不都是小於等於零 有大於零的分量 那麼我們那個XN的取值 只要相應於這個大於零的分量 取爲正數 其他取爲零的話 我們可以分析呢 就還可以是目標上升 而如果這個σ的符號全都是小於等於零 這個時候呢 只有XN取零的時候纔是最大 它不可能使目標再上升了 所以當前這個基本可行解就是最優的 這個σ呢 我們就把它稱爲檢驗數向量 它的每個分量也稱爲一個檢驗數 下面把剛纔分析的具體方法 我們來給出 最優性檢驗的方法就是 計算每個變量的檢驗數 每個變量計作XJ的話 它相應的檢驗數就是σJ σJ根據剛纔的向量表達式 寫成分量 這個σJ就是剛纔那個σ 那個向量的一個分量 這個σJ的表達式就是CJ-CBBPJ 那個PJ就是剛纔向量表達式中 的N中的一列DJ列 好這是最優性檢驗的 第一步就是計算檢驗數 計算每個變量的檢驗數 σJ之後呢 假若每個σJ的符號都是小於等於零的 根據剛纔的分析 可知當前的解就是最優解 否則如果檢驗數σJ中 不滿足都小於等於零 也就是說這個解還可以改進 那麼當前這個解就不是最優 如果不是最優 則轉第三步 就是尋找下一個更好的解 剛纔已經說了 如果不是最優的話 那麼它的特徵是什麼呢 就是至少有一個檢驗數 某個檢驗數比如σK是大於零的 是最優的特徵是什麼 就是所有的σJ都小於等於零 這就是最優性條件 也就是我們這個步驟的主要結果 我們下面呢 把這一步稍加小節一下 咱們現在介紹的這個步驟 是單純刑法的第二個步驟 叫最優性檢驗 它的目的是要檢驗當前一個機可行解 是不是最優 具體方法是計算每個變量的檢驗數 每個變量相應的檢驗數 這個檢驗數的計算是用σJ-σB-πJ 這個符號是什麼意思呢 其中CJ就是這個變量XJ的價格係數 目標中的價格係數 那麼CB是相應於這個當前這個解 因爲每個解都相應於一個G 那麼這個解的相應那個G 它所相應的係數部分就是CB 這個B逆呢就是這個G的逆振 PJ是什麼呢 是這個變量XJ相應的係數列 這是檢驗數的計算 如果所有的檢驗數通通小於等於零 則當前解就是最優 否則呢就不是最優 還需要繼續迭代 繼續尋找下一個更好的解 那麼不是最優的特徵 就是至少有一個檢驗數是大於零的 假如不是最優 我們就需要繼續迭代計算 尋找一個更好的機可行解 由於機可行解是與G對應的 也就是尋找一個新的機可行解 相當於從上一個GB0變換爲下一個新的GB1 因此本步驟也可以稱爲機變換 我們呢這裏只是概要的介紹 機變換的原則和方法 機變換的具體依據的原則有兩點 第一點原則是要改善 也就是我從上一個G相應的解變換到下一個G相應的解 一定要使它改善 就是它的目標值上升 我們因爲是越大越優 具體表達式就是Z1要大於Z0 Z1是下一個新的解相應的目標值 Z0是上一個解的目標值 這是第一個原則 那麼機變換的第二個原則是可行 也就是經過變換的新的這個解新的這個GB1 要保證它相應的這個解是滿足可行性條件的 那麼具體來講就是它相應的這個G可行解 這個基本解B逆B 它的這個機變量部分的是要大於等於零的 就是它是一個可行的 基於這兩點原則 我們就可以來設置這個機變換的具體方法 機變換的方法 我們剛纔已經說過把係數矩陣A裏邊每一列可以表示成PJ 這就是下標序號 具體就是P1一直到PN 我們現在假設上一個機是由前M列所組成 由它變爲下一個機是怎樣變換的 形式呢 它的具體變換的形式 我們可以直觀的圖示一下 就是假設PL是上一個機中的裏邊的一列 一個機向量 而這個PK呢 是上一個機相應的一個非機向量 我們從上一個機變換到下一個機 它的方式是隻替換一個向量列 也就是原來屬於機向量的這個PL替換出去 成爲非機 而原來屬於非機行列裏頭那個PK換進來 替換掉PL 也就是機變換的這個思路 它每次只換一列 而不是全盤換掉 是這樣來換的 因此我們這個具體方法就是要確定誰進機 誰出機的問題 進機就是原來一個非機的一列 一個向量列PK進入到機向量列 替換掉那個PL 進機用什麼原則來決定呢 剛纔已經說過 我們的總體原則是要保證改善的 我們這個改善的這個原則呢 就用來確定進機的這個向量 剛纔不是說了嗎 經過最優性檢驗 假若非最優 一定是會有一個檢驗數 至少一個檢驗數 比如Sigma K是大於零的 假如Sigma都小於等於零 就沒有必要算這一步了 那已經都得到最優了 一定是上一步不是最優 才需要計算下一步 不是最優的特徵就是 它至少有一個檢驗數是大於零的 經過剛纔的分析也可以知道 只要令這個大於零的這個檢驗數 相應的那個 它的相應的那個原來的那個飛機變量 令它大於零的話 就可以使目標上升 所以呢 我們這個進機的方法就是 令大於零的這個檢驗數 對應的那個 原來的那個飛機向量PK進機 這是PK的確定 那麼初級也就是PL的確定 是怎樣確定的呢 怎樣的依據呢 我們根據剛纔總體原則 一個是改善一個是可行 剛纔的改善已經由進機來保證了 那麼可行這一點原則 這個基本原則 我們呢 要由初級的這個選擇 可以來保證 也就是說初級的確定 是基於爲了保證可行 什麼叫可行呢 剛纔已經說過了 就是要使得變換以後的新的解 還要滿足是大於等於零 那麼這個解的機變量部分的表達式 是XB等於B逆B減去B逆N XN 我們原來那個解呢 是XN都等於零 我們要替換到下一個解的時候呢 那麼這個XN可以取什麼樣的值 可以滿足可行呢 我們由這個向量不等式 這是一個矩陣向量的一個不等式 由它的分量式呢 我們經過計算和分析呢 就可以計算出啊 這個由誰來出擊呢 可以保證是可行的 具體的方法 也就是我們這個機變換 這一步的具體的方法是 首先決定進擊 決定進擊就是令大於零的檢驗數 所對應的PK進擊 假如有多個大於零的時候 就取其中最大的那個 因爲它越大 在當前的下一步中啊 可以使目標改善的最大幅度最大 然後決定出擊 出擊呢是基於剛纔爲了保證可行性 大於等於零的那個不等式 經過計算和分析得到的這個方法 那麼這個出擊的決定呢 是令θL等於最小的θI 所對應的那個向量PL出擊 那麼這個θI是什麼呢 是用B逆B的每個分量 比上B逆PK的每個分量 要求B逆PK這個做分母的這個分量呢 是要大於零 那麼這個K是什麼呢 PK是什麼呢 是剛纔進擊的那個 就是剛纔這裏邊這個分母的這個PK 就是剛纔進擊的 決定了進擊的那個PK 我們就稱呢 這個θK稱作檢驗比 也稱替換比 它的計算要決定出擊的向量 那麼在這一步計算之後 也就是得到了 也就是一進一出之後 這個新的擊就得到了產生了 也就是換了一個擊 這個換擊呢 就是出去一個進來一個 先決定進後決定出 決定進的時候 就是這個很簡單 就是檢驗數 大於零的那些檢驗數 其中最大的那個θK對應的那個 那一列向量進擊 而出擊的計算 就是要計算一系列的比值 θI稱作檢驗比 θI怎麼計算呢 就是用B逆B的每個分量 比上B逆PK的相應分量 一系列的比值 一共是m個 因爲這個B是m階的矩陣 要求分母是大於零的 對於分母 如果它這個B逆PK 因爲是一個向量 這裏邊的小於等於零的分量 就不予計算 只計算它大於零的分量 相應的這個θ值 所有θ值檢驗比計算之後 取一個最小的θ 計作θL 它對應的PL 出擊 換擊之後呢 得到新的一個擊可行解 轉第二步 也就是回到最優性檢驗 再對新的這個擊相應的解進行檢驗 如果滿足則停止 如果不滿足 則繼續再迭代 就是再尋找下一個新的解 直至滿足最優性條件 什麼是最優性條件呢 就是所有的檢驗數θJ 全都小於等於零 好 我們到這裏呢 把單純刑法的原理步驟 做了一個概括的介紹 同時呢 每一個步驟呢 都給出了具體的計算方法 依靠這些方法 可以對一個一般的線性規劃模型 進行求解了