8-線性規(guī)劃0934第二章24退化問題-26單純形法的幾何意義=第八次課(編輯修改稿)
2024-08-22 06:31 本頁面
【文章內(nèi)容簡介】 ，新基為 B6=( p3， p5， p1)。 并將 x4換為 x5，得新基 B6對應的單純 形表，見表 223： 對表 222作初等行變換， x3為新的基變量，則對應單位列向量 進基的選擇也 符合：最大檢 驗數(shù)規(guī)則 * 離基 進基 P48 Beale例子 —— 用 Bland法則求解 二、 退化問題中避免基循環(huán)的方法 退化情形的處理 解： 基 B6=( p3， p5， p1)對應的單純形表見表 223 。 ，最優(yōu)值為 f*=f(x*) 由表 223可知，檢驗數(shù)全部非正，故表 223為最優(yōu)解表。 檢驗數(shù)全部非正， 滿足定理 對應最優(yōu)解為 x* 最優(yōu)解表 T13( , 0, 1 , 0, , 0, 0 )25 10 0?為該基解的基分量的值 為該基解對應的目標函數(shù)值 120?? 。P48 Beale例子 —— 用 Bland法則求解 二、 退化問題中避免基循環(huán)的方法 解： 基 B4=( p3， p4， p7 )對應的單純形表見表 219 。 退化情形的處理 由 Bland規(guī)則， x1為進基變量； * 離基 進基 ★ 對比 ★ 由最大檢驗數(shù)規(guī)則， x5為進基變量； 進基 * 離基 x3為離基變量。 x7為離基變量。 采用 Bland規(guī)則后，目標函數(shù)值得到了改善， 也不在再現(xiàn)基的循環(huán)了，詳見表 220與 222. 二、退化問題中避免基循環(huán)的方法 退化情形的處理 ★ 對比 ★ 退化的 非退化的 采用 Bland規(guī) 則后，目標 函數(shù)值得到 了改善；也 不再現(xiàn)基的 循環(huán)了。 二、退化問題中避免基循環(huán)的方法 退化情形的處理 ① 雖然 Bland法則可避免循環(huán)，但一般說來求解 LP的 迭代效率較低 (長期的實際表明，退化經(jīng)常有，而循環(huán)極為罕見 ) 。 ② 一般方法： 用單純形法求解 LP問題時， 一般按照 (P37— 38)的 步驟與規(guī)則 (最大檢驗數(shù)規(guī)則 )來進行單純形迭代，對于 退化 問題萬一 遇到循環(huán)現(xiàn)象，再改用 Bland規(guī)則。 二、 退化問題中避免基循環(huán)的方法 ★ 說明 ★ 退化情形的處理 ① 問題無可行解 (當然就沒有最優(yōu)解 ) 。 ② 有可行解，但是目標函數(shù)在可行域上無下界 (此時也 無最優(yōu)解 ) 三、線性規(guī)劃問題 LP的解的情況 綜合定理 ，可得到如下結論： 線性規(guī)劃問題 LP(不管是否退化 )有且僅有如下三種可能情形： ③ 有最優(yōu)解，且必能在基可行解中找到最優(yōu)解。 可行域為空集 定理 若線性規(guī)劃問題 LP的可行域非空，且目標函數(shù)在可行域上 有下界 ，則 LP必有最優(yōu)解。 可行域非空 檢驗數(shù)全部 ≤0 時 為最優(yōu)解 全部 0 ? 唯一解。 存在 =0 ? 無窮多個解。 非基變量 檢驗數(shù) 單純形法的幾何意義 第二章 單純形方法 第二章 單純形方法 在 “ 圖解法 ” 已經(jīng)得到如下結論： 單純形法的幾何意義 線性規(guī)劃的可行域是一個什么形狀？ —— 多邊形，而且是“凸”的多邊形。 最優(yōu)解在什么位置獲得？ —— 在邊界，而且是在某個頂點獲得。 這些結論具有 普遍意義，對 于兩個以上變 量的線性規(guī)劃 問題也成立。 凸集 頂點 —— 基可行解 x(1) 單純形法的幾何意義 一、基本概念 凸集和凸組合 (1)、直線段： 并稱 x(1)， x(2)為線段的端點 (他們分別對應 α=0與 α=1)； x(2) (1 ) ( 2 )xx設 ， 稱集合 為 Rn中的直線段， ? ?(
教學教案相關推薦
鄂ICP備17016276號-1