運(yùn)籌學(xué)第一章 1.4 大M法和兩階段法ppt課件

四 單純形法的一般描述 1 初始可行解的確定 1 初始可行基的確定觀察法 系數(shù)矩陣中是否含有現(xiàn)成的單位陣 LP限制條件中全部是 類型的約束將新增的松弛變量作為初始基變量 對(duì)應(yīng)的系數(shù)列向量構(gòu)成單位陣 先將約束條件標(biāo)準(zhǔn)化 再引入非負(fù)的人工變量 以人工變量作為初始基變量 其對(duì)應(yīng)的系數(shù)列向量構(gòu)成單位陣 稱為 人造基 然后用大M法或兩階段法求解 線性規(guī)劃限制條件都是 或 類型的約束 等式約束左端引入人工變量的目的 使約束方程的系數(shù)矩陣中出現(xiàn)一個(gè)單位陣 用單位陣的每一個(gè)列向量對(duì)應(yīng)的決策變量作為 基變量 這樣 出現(xiàn)在單純形表格中的B i 列 即約束方程的右邊常數(shù) 值正好就是基變量的取值 注意 用非基變量表示基變量的表達(dá)式 如果限制條件中既有 類型的約束 又有 或 類型的約束 怎麼辦 構(gòu)造 不完全的人造基 討論 為什麼初始可行基一定要選單位陣 b列正好就是基變量的取值 檢驗(yàn)數(shù)行和b列交叉處元素也正好對(duì)應(yīng)目標(biāo)函數(shù)值 因此稱b列為解答列 2 寫出初始基本可行解 根據(jù) 用非基變量表示基變量的表達(dá)式 非基變量取0 算出基變量 搭配在一起構(gòu)成初始基本可行解 2 建立判別準(zhǔn)則 1 兩個(gè)基本表達(dá)式的一般形式LP限制條件中全部是 類型約束 新增的松弛變量作為初始基變量的情況來描述 此時(shí)LP的標(biāo)準(zhǔn)型為 非基變量基變量 初始可行基 初始基本可行解 一般 經(jīng)過若干次迭代 對(duì)于基B 用非基變量表出基變量的表達(dá)式為 用非基變量表示目標(biāo)函數(shù)的表達(dá)式 若是對(duì)應(yīng)于基B的基本可行解 是非基變量的檢驗(yàn)數(shù) 若對(duì)于一切非基變量的角指標(biāo)j 均有 0 則X 0 為最優(yōu)解 2 最優(yōu)性判別定理 3 無 有限最優(yōu)解 的判別定理 若為一基本可行解 有一非基變量xk 其檢驗(yàn)數(shù) 而對(duì)于i 1 2 m 均有 則該線性規(guī)劃問題沒有 有限最優(yōu)解 舉例 用非基變量表示基變量的表達(dá)式 代表兩個(gè)約束條件 x2對(duì)應(yīng)的系數(shù)列向量P2 1 3 T 設(shè) 當(dāng)前的換入變量是X2 按最小比值原則確定換出變量 要求 于是 如果x2的系數(shù)列變成P2 1 0 T 則用非基變量表示基變量的表達(dá)式就變成 可行性自然滿足 最小比值原則失效 意即x2的值可以任意增大 原線性規(guī)劃無 有限最優(yōu)解 3 進(jìn)行基變換 1 選擇進(jìn)基變量 原則 正檢驗(yàn)數(shù) 或最大正檢驗(yàn)數(shù) 所對(duì)應(yīng)的變量進(jìn)基 目的是使目標(biāo)函數(shù)得到改善 較快增大 進(jìn)基變量對(duì)應(yīng)的系數(shù)列稱為主元列 2 出基變量的確定 按最小比值原則確定出基變量 為的是保持解的可行性 出基變量所在的行稱為主元行 主元行和主元列的交叉元素稱為主元素 4 主元變換 旋轉(zhuǎn)運(yùn)算或樞運(yùn)算 按照主元素進(jìn)行矩陣的初等行變換 把主元素變成1 主元列的其他元素變成0 即主元列變?yōu)閱挝幌蛄?寫出新的基本可行解 返回最優(yōu)性檢驗(yàn) 例1 8的表格單純形法計(jì)算過程 表格單純形法求解步驟 第一步 將LP化為標(biāo)準(zhǔn)型 并加以整理 引入適當(dāng)?shù)乃神Y變量 剩余變量和人工變量 使約束條件化為等式 并且約束方程組的系數(shù)陣中有一個(gè)單位陣 這一步計(jì)算機(jī)可自動(dòng)完成 確定初始可行基 寫出初始基本可行解 第二步 最優(yōu)性檢驗(yàn) 計(jì)算檢驗(yàn)數(shù) 檢查 所有檢驗(yàn)數(shù)是否 0 是 結(jié)束 寫出最優(yōu)解和目標(biāo)函數(shù)最優(yōu)值 還有正檢驗(yàn)數(shù) 檢查相應(yīng)系數(shù)列 0 是 結(jié)束 該LP無 有限最優(yōu)解 不屬于上述兩種情況 轉(zhuǎn)入下一步 基變換 確定是停止迭代還是轉(zhuǎn)入基變換 選擇 最大 正檢驗(yàn)數(shù)對(duì)應(yīng)的系數(shù)列為主元列 主元列對(duì)應(yīng)的非基變量為換入變量 最小比值對(duì)應(yīng)的行為主元行 主元行對(duì)應(yīng)的基變量為換出變量 第三步 基變換 確定進(jìn)基變量和出基變量 利用矩陣的初等行變換把主元列變成單位向量 主元素變?yōu)? 進(jìn)基變量對(duì)應(yīng)的檢驗(yàn)數(shù)變成0 從而得到一張新的單純形表 返回第二步 第四步換基迭代 旋轉(zhuǎn)運(yùn)算 樞運(yùn)算 完成一次迭代 得到新的基本可行解和相應(yīng)的目標(biāo)函數(shù)值 該迭代過程直至下列情況之一發(fā)生時(shí)停止 檢驗(yàn)數(shù)行全部變?yōu)榉钦?得到最優(yōu)解 或 主元列 0 最優(yōu)解無界 停止迭代的標(biāo)志 停機(jī)準(zhǔn)則 依據(jù) 最優(yōu)性檢驗(yàn)的兩個(gè)定理最優(yōu)性判別定理 無 有限最優(yōu)解 判斷定理 五 各種類型線性規(guī)劃的處理1 分類及處理原則 1 類型一 目標(biāo)要求是 Max 約束條件是 類型 左邊加上非負(fù)松弛變量變成等式約束 約束條件標(biāo)準(zhǔn)化 將引入的松弛變量作為初始基變量 則初始可行基是一個(gè)單位陣 用原始單純形法求解 2 類型二 目標(biāo)要求是 Max 約束條件是 類型 左邊引入非負(fù)的人工變量 并將引入的人工變量作為初始基變量 則初始可行基是一個(gè)單位陣 然后用大M法或兩階段法求解 3 類型三 目標(biāo)要求是 Max 約束條件是 類型 約束條件標(biāo)準(zhǔn)化 左邊減去非負(fù)的剩余變量 變成等式約束 化為類型二 2 處理人工變量的方法 1 大M法 在約束條件中人為地加入非負(fù)的人工變量 以便使它們對(duì)應(yīng)的系數(shù)列向量構(gòu)成單位陣 問題 加入的人工變量是否合理 如何處理 在目標(biāo)函數(shù)中 給人工變量前面添上一個(gè)絕對(duì)值很大的負(fù)系數(shù) M M 0 迭代過程中 只要基變量中還存在人工變量 目標(biāo)函數(shù)就不可能實(shí)現(xiàn)極大化 懲罰 最優(yōu)表中 基變量不包含人工變量 則最優(yōu)解就是原線性規(guī)劃的最優(yōu)解 不影響目標(biāo)函數(shù)的取值 最優(yōu)表中 基變量中仍含有人工變量 表明原線性規(guī)劃的約束條件被破壞 線性規(guī)劃沒有可行解 也就沒有最優(yōu)解 結(jié)果 問題 結(jié)果 中求得的最優(yōu)解是哪個(gè)線性規(guī)劃的最優(yōu)解 為什麼 大M法舉例 加入松弛變量 剩余變量和人工變量 六 迭代過程中可能出現(xiàn)的問題及處理方法 1 為確定出基變量要計(jì)算比值 該比值 解答列元素 主元列元素 對(duì)于主元列的0元素或負(fù)元素是否也要計(jì)算比值 此時(shí)解的可行性自然滿足 不必計(jì)算 如果主元列元素全部為0元素或負(fù)元素 則最小比值失效 線性規(guī)劃無 有限最優(yōu)解 2 出現(xiàn)若干個(gè)相同的最小比值怎麼辦 說明出現(xiàn)了退化的基本可行解 即非0分量的個(gè)數(shù)小于約束方程的個(gè)數(shù) 按照 攝動(dòng)原理 所得的規(guī)則 從相同比值對(duì)應(yīng)的基變量中選下標(biāo)最大的基變量作為換出變量可以避免出現(xiàn) 死循環(huán) 現(xiàn)象 3 選擇進(jìn)基變量時(shí) 同時(shí)有若干個(gè)正檢驗(yàn)數(shù) 怎麼選 最大正檢驗(yàn)數(shù)或從左至右第1個(gè)出現(xiàn)的正檢驗(yàn)數(shù)所對(duì)應(yīng)的非基變量進(jìn)基 2 兩階段法第一階段 建立輔助線性規(guī)劃并求解 以判斷原線性規(guī)劃是否存在基本可行解 輔助線性規(guī)劃的結(jié)構(gòu) 目標(biāo)函數(shù)W為所有人工變量之和 目標(biāo)要求是使目標(biāo)函數(shù)極小化 約束條件與原線性規(guī)劃相同 求解結(jié)果 W最優(yōu)值 0 即所有人工變量取值全為0 為什麼 均為非基變量 最優(yōu)解是原線性規(guī)劃的一個(gè)基本可行解 轉(zhuǎn)入第二階段 W最優(yōu)值 0 但人工變量中有等于0的基變量 構(gòu)成退化的基本可行解 可以轉(zhuǎn)化為情況 如何轉(zhuǎn)化 選一個(gè)不是人工變量的非基變量進(jìn)基 把在基中的人工變量替換出來 W最優(yōu)值 0 至少有一個(gè)人工變量取