【天津大學】《運籌學》（精品課） P12 - 12. 對偶問題與靈敏度分析 教學錄像（3）

我們以上介紹了對偶的性質和經濟解釋 接下來我們再來介紹一個內容 稱作對偶單純行法 我們先來回顧一下 原來在上一節中學過的單純行法 這個表是單純行表的一般表達式 我們回顧單純行法的求解過程 它是在保持可行性 也就是避逆避 保持總是大於等於零的條件下 逐步改善最優性 最優性就是檢驗術 逐步使得檢驗術都小於等於零 來達到最優的 那麼這個對偶單純行法就是 考慮嘗試對稱的思想 對稱的思想就是 能否在保持最優性的表達式 就是sigma小於等於零的條件下 逐步改善可行性的表達式 就是避逆避大於等於零 假如可以的話 那麼我們就可以得到另外一種 在一定條件下 可以適用的一種求解的方法 下面呢 我們對這個對偶單純行法進行簡單介紹 它的主要步驟 首先呢 第一步是要能夠確定一個初始的基 B0 這個初始基B0 只要使相應的檢驗術 sigma0小於等於零就可以 這是第一步 那麼接下來第二步進行檢驗 它這個檢驗呢 是用可行性來檢驗 假如這個基相應的避逆避已經滿足大於等於零了 也就是已經可行了 而剛纔檢驗術不是已經小於等於零了嗎 那麼這個避逆避又大於等於零 如果已經可行也滿足檢驗術 最優性也滿足的話 它就是最優了 否則的話 就是這個避逆避啊 當中不滿足都大於等於零 它這個分量裏邊 有小於零的話 我們就接着做第三步 第三步呢 也是稱爲基變換 但是它是先確定初級XL 再確定進級XK 怎樣決定初級和進級呢 決定初級很簡單 因爲它是爲了改善可行性 所以啊 決定這個初級的原則呀 就是在避逆避的這些分量中 有不滿足可行性的那個負分量 也就是這個避逆避的這個小於零的分量 它相應的那個變量初級 那麼假如有多個是小於零的分量的時候 我們就取一個最小的 它相應的這個相應的那個變量XL初級 也就是基變換呢 先決定初級 由避逆避的小於零的分量對應的變量初級 決定了初級XL之後 我們再來確定進級 進級怎樣確定呢 我們也是計算一些比值 把它也記作θJ 這個時候的θJ是怎樣計算的呢 它是在剛纔決定了進級的那個DL行 DL行中 它的係數分量中 小於零的這些分量 來除這個相應的檢驗數 那麼所得到的這個θ比值呢 是其中選一個最小值 它相應的這個變量呢 是這個進級就是XK 那麼完成了基變換 也就是一進一出了之後 我們還是和單純形表一樣 把它相應的那個交叉圓 做記號擴起來 作爲主圓 實行初等行變換 也就是進行基變換 基變換之後 得到新的基 再轉二 就是檢驗 也就是得到新的單純形表之後呢 還是要再來看一下 它的B逆B部分是不是都已經大於等於零了 如果還有小於零的 再接着進行基變換 令那個小於零的這個初級 同時呢 用初級的這一系數行 其中的小於零的那些係數 來除它相應的檢驗數 那麼這樣呢 我們呢就可以繼續得到下一個級 這樣進行的效果 是初級改善了可行性 而進擊的原則呢 是要保持sigma小於等於零 就是那個最優性的表達式 好 我們這個方法的簡介的步驟 它的主要步驟 我們就說到這裏了 在說完這個主要步驟之後 我們呢稍加做一點補充說明 就是在剛纔講的 決定進擊的這個計算中 它計算這個檢驗比的 這個定義啊 要求分母是小於零的 剛纔說了它的含義 就是決定了初級的那一行 的係數行中的小於零的 那些係數 來除這個相應的檢驗數 但是假若這個係數行中 都不滿足小於零怎麼辦呢 也就是有沒有可能這一行 都是大於等於零的 從而無法計算θ呢 我們說如果出現這種情況 則停止計算 因爲這種情況是屬於 無可行解的情況 好 我們這個對有單純型的方法呢 就主要步驟啊 我們就簡介到這裏 下面呢 舉一個例子計算一下 把它再來說明一下 我們請看這個例題 這個例題呢 是求解一個線性規劃 這個線性規劃的特點是 它的約數是大於等於約數 如果化爲標準型的話 也就是在每個約數減掉一個鬆弛變量 化爲了等式之後 它將出現a中不含i的情況 因爲它減每個約數減一個鬆弛變量 那麼相當於化成標準型以後啊 它的係數陣中是一個負i而不是i 這種情況下不能直接用單純型表求解 那麼就只能用大M法來求解 但是我們現在知道了對有單純型方法 我們就可以來想一下 假若這個問題滿足 它的初始機始得減延數都是小於等於零 那麼是不是就可以考慮用對有單純型法來計算呢 於是我們就分析 我們分析這個 先來分析這個約數 約數現在是大於等於約數 如果我把它兩端乘負號變成小於等於約數 那麼這樣的話我們通過添加鬆弛變量 就可以出現一個初始的單位陣 當然這樣化成的不是標準型 因爲它的右端像成了負號就變成負的了 可是對有單純型法 它恰好是處理初始的那個解不可行的情況 所以我們可以試着考慮一下 我們在這時呢再接着看這個目標 目標現在是極小型 如果化成極大型的話 它的所有的係數都添加了負號 而剛纔說的初始機是單位的情況下 那麼這個初始機的單位相應於的就是鬆弛變量 它在目標中的係數是零 這樣計算出來的檢驗數 也就是這些化成負號以後的這些個價格係數 那它恰好都是小於等於零的 經過這樣的分析啊 我們可以對這個例子呢試一下 能不能用對有單純型方法來計算 按照剛纔的分析 我們首先把約數兩端乘以負號化爲小於等於型 然後添加鬆弛變量x4和5 添加了鬆弛變量之後 這就出現了一個機 同時呢 我剛纔把目標的極小型呢化爲極大 它的係數呢都乘以了負號 這個模型的單純型表 如果列出來 我們看一下是什麼樣的 我們看到呢 這個初始單純型表 它的bdb啊 也就是右端項都是負的 那麼它的這個價格係數呢 也都是這幾個都是負的係數 鬆弛變量的係數是零 這樣的話計算檢驗數 因爲第一個機是x4和x5 它的價格係數是00 所以呢 我們計算的檢驗數的結果 就是這個初始的價格系 這個價格係數的這些係數 它都是小於等於零的 那麼這個呢 符合用對有單純型法求解的條件 也就是呢 它的初始機相應的檢驗數 都是小於等於零的 在這種前提下 我們該怎樣做呢 由剛纔的介紹的步驟可知 我們首先要決定一個初級 決定初級的時候 就是從這個bdb這裏來看 bdb裏邊的負值 如果兩個都是負的 我們就取最小的那個 那麼當這個bdb要是都是大於等於零了 那這個就是最優了 它現在就是可行性不滿足 而那個最優性那一塊呢 它是滿足那個檢驗數 小於等於零的條件的 好 那麼我們現在接着說這個 就是先決定初級 令這個-4對應的x5初級 然後接下來確定進級 誰進級呢 我們剛纔說了 就是決定初級的這一行 這一行係數行 當中所有的負值 負的係數 與它相應的檢驗數 進行計算比值 那就是說呢 比如說這個 就是檢驗數是負2 比上這個係數負2 然後呢 第三列的那個 就是拿-4比上-3 這兩個比值取一個最小的 就是這個相應於x1的這塊 所以呢 我們把這個就是x5的這個初級行 和x1的進級列的交叉元負2 把它擴起來 下一張表要實行 以它爲出發點的這個初等行變換 這個迭代的方法呢 和原來的這個單純型表是一樣的 也就是說呢 把這個 這個就是剛纔那張表 初表 也就是下一張表呢 要先把它消成1 再用這個1呢 把它所在列的其餘元消成0 這個消的方法和原來的單純型表是一樣的 我們看到比如說 這個負2 它首先消成1了 也就是它所在的這一行呢 通通乘以了負1分之1 就是除以了負2 那麼再拿這個1呢 把它所在列的其餘元 這個負1消成0 那就拿這個1呢 加到這個負1上 這個負1的位置不就消成0了嗎 那麼所在的這一行要一塊跟着變 它要通通加到剛纔的上面這第一行上 所得的結果寫到新表上 比如剛纔那個2加到負3上就得負1 這個時候呢 我們數據部分算完之後呢 它的這個 左邊的這個欄目就是XB和CB 我們要相應的把它填上 上一張表基變量是X4和5 這一張表呢是X4和1 因爲剛纔是5出1進 那麼相應的價格係數把它填上 那麼現在呢 得到第二張表以後 我們繼續進行這個判斷檢驗和 如果檢驗不是最優呢 還要進行繼續的迭代 檢驗就是看比尼幣是否都大於等於零了 現在還有一個負值 說明還不是最優解 因爲它不滿足可行性 於是呢還要按照剛纔的方法來進行換機 換機呢就是先決定出後決定進 我們現在只有一個負的比尼幣的值了 所以就是它出 它出決定了以後 用它的係數行的負值與檢驗數 負值去除這個相應的檢驗數 然後取最小值相應的這個X2 就是作爲進級 那麼一出一進的交源呢 我們把它擴起來 作爲下一張表迭代的主源 好 經過下一張表迭代了之後呢 我們發現這個時候的比尼幣的位置已經沒有負值了 而且檢驗數一直保持是小於等於零的 所以這張表就是最優了 這個時候的基變量是X1和X2 那麼我們最後呢 把這個相應的解寫出來 由剛纔的這個鐘錶 X1呢是等於五分之十一 X2呢等於五分之二 這裏沒出現的X345是非基變量 通通等於零 這些都是和我們原來的單純形法是一樣的 另外呢就是最優值Z星 最優值Z星呢可以在這裏用CBB尼幣來計算 計算出來是一個負值 但是呢要還原爲原問題的時候 我們要用它的相反數 也就是最後的Z星呢是一個正值五分之二十八 好 我們到這裏呢 把這個隊友單純形法進行了一個簡單的介紹 到這裏爲止呢 我們關於隊友問題的主要的內容 我們就呢進行了一個比較詳細的介紹 在歷史上呢將線性規劃和經濟問題相關聯 進行研究的早期貢獻者 我們這裏列舉的是庫普曼和康託羅維奇 這兩位學者呢 就是由於在這方面的早期的工作的貢獻 而共同分享了1975年的第七屆諾貝爾經濟學獎 我們在介紹了隊友問題的相關內容之後 我們接下來呢 再來介紹一個內容 叫靈敏度分析 靈敏度分析主要是討論模型的係數或變量的結構 發生小的變化擾動時 對原來求得的最優解的影響 我們主要討論呢 它們在什麼範圍內變化時 可使原最優解或最優積保持不變 那麼說到我們這個模型的一些變化 可以有很多方面 比如說係數部分有C的變化 B的變化 還有A也可能有變化 我們在這裏呢 主要討論C和B的變化 同時呢 還討論一個變量結構的變化 對解的影響 那麼說到這些係數或變量的變化 對解將產生影響 那麼產生怎樣的影響 對解的什麼方面產生影響呢 有解的概念可知 對解的影響 無非是可行性和最優性兩個方面 而可行性的表達式是B逆B大於等於零 最優性的表達式呢 是檢驗數小於等於零 我們由這個就可以分析了 比如說當B變化的時候 我們先來看這個 以B爲例 我們來考慮一下 當B變化的時候 它對解的影響是什麼呢 也就是B變化的時候 要對它的可行性還是最優性會產生影響呢 我們有可行性和最優性的表達式可知 B變化的時候 隻影響可行性 因爲最優性的表達式中 不含有B 所以我們就說 當資源限制向量B變化時候 我們只需要討論它對可行性的影響就可以了 如果它變化能夠在一定範圍內 使得可行性仍成立的話 那麼這個範圍就是使得原最優機仍適用的範圍 同樣可以分析C變化的時候 因爲C它在哪兒出現呢 我們顯然看到是在檢驗數中有C 而在可行性這個解的表達式裏沒有C 所以C變化的時候 它影響的是最優性 我們只需要考慮 當C在一個什麼範圍變化 能夠使得它變化了以後的這個檢驗數 能夠仍然滿足最優性小於等於零 那麼這個範圍就是我們要求的使原最優解保持最優的範圍 下面我們就基於這個思路來進行分析 首先我們來分析B變化時的分析 這個B就是右端項 也就是資源限制項量 我們現在假設在這個B 它的M個分量中 假設其中一種資源 B2 因爲這個B每一個分量表示一種資源的限量 我們假設它的第二個分量B2 發生了一個改變量 也就是B2變爲了B2加ΔB2 這個Δ這個符號 在數學中經常表示增量改變量 那麼由剛纔的分析已知 B變化的時候隻影響可行性 也就是我們只需要考慮 當它變化以後 在什麼範圍時 可使這個B逆乘以它 仍然保持大於等於零的可行性 那麼這個範圍呢 就是它的這個可以變化的 使原自由基不變的這個範圍 我們假設繼第二種資源 B2 發生改變量之後的 這個B 也就是隻B2這一個分量 加了Δ之後的這個新的這個B呢 即爲B1 那麼我們的這個分析的思路就是 由這個B1 B逆乘以它之後 大於等於零 來解除B1中這個Δ的範圍 具體來講就是 只要由B逆乘以B1 這個B逆呢 就是當前已經計算的自由基的逆徵 B1呢 就是剛纔說的 在原有的B當中 只有第二種資源B2 它變化的增加了一個改變量Δ 我們就是說呢 由這個B逆乘以B1 令它大於等於零 解除這個Δ的範圍即可 這個範圍呢 就是我們要分析計算的 使原自由基B保持仍適用的 這個第二種資源的變化範圍 比如說我們看一個例子 還是沒電油的這道題 它的鐘表我們前面已經知道 在這個前提下呢 我們想分析一下 油這種資源 它的限量在什麼範圍變化時 可使原自由基保持不變 油是第三種資源 我們因爲這個題目呢 是沒電油的例子 沒電油三種資源 油的限量原來是300 現在我想分析 這個300個單位的油 這個限量300 它如果發生一個小的改變量 那麼這個改變量的範圍 是什麼範圍的時候 可以使得原自由基仍適用呢 我們由剛纔的方法 可以進行分析 剛纔的方法我們已經說了 只需由B逆乘以B一槓 B一槓是什麼 就是在原來的B的基礎上 把油這個300 加上一個增量得它 這個B逆是什麼 B逆就是單純型鐘錶中的那個逆振 B的那個基的逆振 在剛纔的單純型表中 它就是後三列的位置所組成 這個在單純型表上是可以已知的 我們現在呢計算B逆和B一槓 由矩陣向量乘法 法則可以把它計算出來 矩陣乘法的法則就是左行右列 對應分量相乘再相加 由現代數的知識 我們經過計算 得到的是仍然一個向量 得到的這個向量呢 它的第一個分量84加1.16 就是拿剛纔的這個第一列第一行 乘以剛纔的這個B一槓這一列 它的對應元素相乘再相加得到的 這樣我們得到的這個B逆B一槓的結果 三個分量都含有得它 我們令這個向量大於等於零 那麼這樣呢 就是它每個分量都要大於等於零 這樣就形成一個不等式組 這個不等式組呢 就是B逆B一槓的每個分量大於等於零 很容易可以解除得它的範圍 有每個不等式分別都能解除一個得 它是這個大於等於多少或者小於等於多少 我們對這三個不等式解除的得它的範圍 求它的公共 就得到這個得它應該滿足的這個條件 這個範圍呢 是大於等於負的72 小於等於100 這個結果是什麼意思呢 這個結果就是說 由這種資源 它的改變量得它 只要是在負72到100的範圍內 不超過這個範圍 都可以使原來的最優積仍適用 因爲呢 它都可以使呢 原來的可行性沒有破壞 因爲我這得 它就是由這個令它大於等於零解出來的嘛 它肯定是使得原來的這個可行性仍然滿足的 好 這就是我們剛纔說的這個結果 我們最後把它寫出來 就是這個範圍的實際意義 就是由的限量 在增加100到減少72的範圍內變化時 原最優積保持不變 那麼原最優積不變是什麼意思呢 大家請注意當B變化的時候 我們這裏不是正在講這個靈敏度分析中的B變化時的情況 這個B變化的時候 它這個影響解的可行性 同時呢 這個解也發生了變化 我們只是討論它變化的時候 在什麼範圍 可使原最優積仍然適用 原最優積就是那個B 那麼最優積又是什麼意思呢 我們知道積變量是這個一般是大於零的 非積變量應該是等於零的 所以最優積假如不變 就是原來那些大於零的變量還是那些變量 它那個變量的取值 它可以發生變化 但是那些變量是哪些產品 哪些變量 那個不變 那也就是說 我們把這個變量看作是產品的產量的話 這個最優積不變的意思呢 就是投產的結構不變 比如說我原來生產一三五種產品 我現在呢 還是生產一三五種產品 好 這是我們關於B變化時的分析 接下來呢 我們再來介紹一下 當C變化時的靈敏度分析 這個C是什麼呢 C是目標中的係數 我們稱作價格係數 它的每個分量表示相應的一種產品 或者說一個變量的單位效應 比如說這個CJ 它就是XJ的係數 也可以把它看作是這種產品的價格 或者是單位效應 我們現在C變化時的分析和剛纔B變化時的分析 類似可以進行分析 也就是說呢 我們考慮某一個價格係數CJ發生了改變量 也就是CJ變爲了CJ加得CJ 前面已經分析過 C變化的時候影響的是最優性 因爲它要在檢驗數的公式中出現 所以呢 我們要想對這個C的變化範圍delta進行分析 也就是分析當delta在什麼範圍變化時 能夠使得這個檢驗數仍然保持小於等於零呢 那麼我們只要使得變化後的這個檢驗數 記作sigma這一槓 使得它呢 仍然保持小於等於零就可以了 這個思想和前面B變化時分析的思想是類似的 那麼下面我們就來對這個檢驗數當中C的出現的作用呢 再來說一下 我們有檢驗數的公式可知 它裏邊有兩個地方出現C 這個檢驗數的公式啊 是sigmaJ等於CJ減去CBBJ C呢 它在第一項 就是你算誰的檢驗數 它就要用誰的價格係數CJ 作爲第一項來減去後面一項 後面一項的前面一個表達式CB當中也要出現C 這個CB是什麼呢 CB是基變量的價格係數 那麼由這個表達式 我們不難可以得出C變化的時候啊 假若它是一個非基變量的價格係數 那麼在CB裏就不含有它 它只在前面這個CJ起作用 但是呢 如果這個CJ變化的這個CJ是基變量的價格係數 那麼它就要在CB裏面起作用 於是呢 我們呢 分別對這個價格係數啊 是非基變量還是基變量兩種情況呢 我們分別來進行這個討論 首先呢 是說如果CJ是非基價格係數時 剛纔說了 它隻影響自己的檢驗數 因爲在剛纔的檢驗數公式裏 CB那一項後邊那個CB不包含它 它隻影響前面這個CJ 那麼由於它變成了CJ加ΔCJ 所以啊 它變化之後帶來的這個檢驗數 變化之後的檢驗數呢 也就是Sigma這一槓的表達式 就是在原來Sigma的表達式基礎上 在前面CJ那兒加上一個ΔCJ 我們令這個Sigma這一槓仍然小於等於零 那麼由這個不等式就可以解除Δ的範圍了 什麼叫範圍 範圍就是一個不等式 就是它小於等於多少 或者大於等於多少 或者它既大於等於多少又小於等於多少 這個我們在前面B的變化時的分析已經看到了 好 這是第一種情況 就是當CJ是非基價格係數的時候 只需由自己的檢驗數 加上一個Δ令它小於等於零 解除Δ 就是所求的這個範圍 這個範圍呢 就是使得仍然自由性成立的 這個CJ的那個增量的變化範圍 這是一種情況 那麼但是如果CJ是基變量價格係數的時候 這個時候剛纔說過了 它要影響在CB中起作用 在後邊那個CB中起作用 所以這個時候呀 它要影響所有的檢驗數 我們由所有的檢驗數 這個的計算都要在原來CB的那個位置 加上一個Δ 這個變化後的計算仍然計算sigma i一槓的話 令它小於等於零 但是這時候注意呢 這是一組不等式 而不是一個不等式 這一組呢 是所有變量的檢驗數 它都要都要算一下 都要計算它的sigma一槓小於等於零 每個檢驗數sigma一槓 這個不等式都能解除一個Δ 最後由這一組解除分別Δ取它的公共範圍 就是呢 這個CJ它的這個增量的變化範圍 也就使得最優性仍然成立的 這個它的增量的變化範圍 好 下面呢 我們舉例說明 這道題呢 是前面在上一節 我們曾經做過的一個練習的單純形表 我們基於這個呀 我們來做一點靈敏度分析 我們的問題是 在下面的線性規劃問題中 請分析X2的係數C2 在什麼範圍變化時 可使圓最優解不變 好 我們看了這個題之後 回想剛纔 我們是介紹的怎樣的方法來分析呢 我們剛纔說過 C的變化要影響檢驗數 那麼如果C是個非基變量的價格係數的話 它隻影響自己的檢驗數 我們說的檢驗數指的是中表的檢驗數 但是呢 這個C如果是基變量的價格係數的話 它要影響所有的檢驗數 分析的方法就是 在原來檢驗數的這個計算式子中 你考慮誰的變化 就在原來誰的那個係數那 加上一個Δ 加上之後呢 令這個式子 令它小於等於零 就是令變化以後的這個檢驗數 σ一槓小於等於零 那麼這個不等式呢解除的Δ 就是這個範圍 現在我們這道題是C2的變化 C2在最終表中 我們看一下 基變量現在是S3和1 不包含C2 說明C2呢 是一個非基價格係數 它的變化隻影響 它自己的檢驗數 我們看到當前這個X2的在中表的檢驗數 是-4 那麼 我們的分析的方法 就很簡單了 只需要解這一個不等式 解除Δ就可以了 那麼這一個不等式呢 就是原來的檢驗數-4 實際上呢 就是加上那個Δ 令它仍然小於等於零 這樣很容易能夠解除 Δ的範圍 也就是由這個-4加Δ小於等於零 可解得 這個Δ呢 小於等於4 這個Δ小於等於4 這個結果 是什麼意思呢 因爲我們現在呢 是說這個 它相應的那個價格 的變化 的增量 就這個Δ小於等於4 就是C2這個價格的 使得原來 保持不變的 那個 的一個變化範圍 直觀上來講呢 就是 C2的價格上漲 不超過4的時候 原來的這個 解呢都不會發生改變 因爲原來這個 X2是非極變量 它原來是不投產的 它不投產的原因 是由於它的價格 收益太低了 那麼當它的收益 如果上漲 不超過4的時候 它都不會改變 它的不投產地位 只有當它的價格上漲 超過4了 大幅上漲了 這個時候呢 它纔有可能 由非極變爲近極 也就是有可能投產