2-最優(yōu)化方法-線性規(guī)劃-單純形法-展示頁
2024-08-10 03:52本頁面
【正文】 題 ⊙ 什么時候可以替換？ ⊙ 替換后 新 規(guī)范形 是什么？ ◎ 替換問題 假設(shè)在上述規(guī)范形中，想用 轉(zhuǎn)軸 (pivot) ◎ 當(dāng)且僅當(dāng) ，可以替換 ◎ 替換后，新規(guī)范形的系數(shù) 轉(zhuǎn)軸公式 －轉(zhuǎn)軸元 (pivot element) 轉(zhuǎn)軸 例 1. 求下列方程組以 為基變量的基本解 轉(zhuǎn)軸 轉(zhuǎn)軸 轉(zhuǎn)軸 x=(0,0,0,4,2,1) 2. BFS→相鄰 BFS(極點 →相鄰 極點 ) ◎ 問題： 確定出基變量，使轉(zhuǎn)軸后 新規(guī)范形 對應(yīng) BFS？ 設(shè) x是 BFS, 且規(guī)范形如前，且 假設(shè) aq 進(jìn)基 因為 令 可否選取合適的 使得 是 BFS ？ 所以 確定離基變量 至少有一個正元 例 3. 考慮線性方程組 a4進(jìn)基 轉(zhuǎn)軸 B=(a1,a2,a3) X=(4,3,1,0,0,0) x=(0,1,3,2,0,0) 3. BFS→目標(biāo)值減小的相鄰 BFS ⊙ 將 Ax=b的任一解 用非基變量 表示； 設(shè) x是 BFS，且規(guī)范形如前，則有 ◎ 問題： 確定進(jìn)基變量，轉(zhuǎn)軸后使 新 BFS的目標(biāo)值 變小 ？ 用非基變量表示 . —— 選取進(jìn)基變量的依據(jù) ⊙ 將 目標(biāo)函數(shù) 相對 /既約費用系數(shù) (relative/reduced cost coefficients) 將 Ax=b 的任一解 x 用非基變量表示為 度量變量相對于給定基的費用 確定進(jìn)基變量 ◎ 最優(yōu)性定理 ◎ 定理 (BFS的提高 ) ◎ 相對費用系數(shù)的 經(jīng)濟(jì)解釋 ！ (合成價格、相對價格 ) 給定目標(biāo)值為 z0的 非退化 基本可行解，且假定存在 j 使得 rj 0，則 i) 如果用 aj 替換基中某列得到了新的 BFS，則新解處的目標(biāo)值比 z0 嚴(yán)格小 . ii) 如果任何替換都產(chǎn)生不了新的 BFS，則問題無界 . ◆ 退化 基本可行解：某個或某些基變量取零的基本可行解！ 問題： 基本可行解與基的對應(yīng)關(guān)系？ 4. 計算過程－單純形法 單純形表： BFS對應(yīng)規(guī)范形的表格＋ 既約費用系數(shù)和 BFS目標(biāo)值的 相反數(shù) 單純形法的步驟 步 0 形成與初始 BFS對應(yīng)的 初始 表格 . 通過行變換求出 第一張 單純形表 . 步 1 若對 每個 j 都有 ，停；當(dāng)前 BFS是最優(yōu)的 . 步 2 選取 q 滿足 步 4 以 為轉(zhuǎn)軸元進(jìn)行 轉(zhuǎn)軸 ，更新單純形表，返步 1. 步 3 若 ，停，問題 無界 ； 否則，選 p 滿足 轉(zhuǎn)軸規(guī)則： 進(jìn)基變量：最小相對費用系數(shù)規(guī)則；出基變量：最小指標(biāo)規(guī)則！ 例 1. 化標(biāo)準(zhǔn)形 轉(zhuǎn)軸 得標(biāo)準(zhǔn)形的 初始 表格 /第一張 單純形表 轉(zhuǎn)軸 0 ↓ 2 ↓ 4 ↓ 27/5
公司管理相關(guān)推薦
鄂ICP備17016276號-1