2-最優(yōu)化方法-線性規(guī)劃-單純形法(更新版)
【正文】 判斷原問題 不可行、或可行 → 可行時找到基本可行解及對應規(guī)范形 ⊙ 第 II階段：利用單純形法求原問題 →從上述 BFS出發(fā)，求解所給問題 →原問題 無界 或者 有解 例 2. 利用兩階段法求解下面的問題 輔助問題 第 I階段： 先構造輔助向量 z=x4+x5 輔助問題的 最后一張單純形表 原問題的 初始 表格： 得到輔助問題的最后一張單純形表后，去掉輔助變量，將原始問題的 z帶入表格，啟動單純形法 原問題的 最優(yōu)解 ： 6. 修正單純形法 (Revised simplex method) ◎ 重要事實： ⊙ 通常僅有少數(shù)列發(fā)生轉軸 (2m3m) ◎ 核心問題： 如何更新 當前基的逆 →新基的逆 理論上的表現(xiàn) 表格實現(xiàn) ⊙ 僅需原始數(shù)據(jù) (c, A, b)和基 B 的逆矩陣 7. 單純形法的矩陣形式 給定基 B 及對應 BFS (xB, 0), 其中 xB=B1b 用 非基 變量表示 目標函數(shù) ： 用 非基 變量表示 基 變量： 相對 費用向量 初始表格－單純形表 初始表格 通常不是單純形表！ 與基矩陣 B 對應的 單純形表 修正單純形法的計算步驟 步 2 選取 q 滿足 步 3 計算 yq=B1aq； 若 步 1 計算 。如果 停；得最優(yōu)解 . 步 0 給定 BFS及對應的 B1。計算 核心 計算： B1 涉及 到的計算： ， 停， 問題 無界 ；否則，選 p 滿足 步 4 更新 B1, B1b和 ，返步 1. 基的轉換定理 左乘 該矩陣等價于對矩陣進行 初等行變換 ！ 定理 不妨設 B= . 則 aq 進基，ap出基后所得新基 的逆 這里 ei 表示 n 維單位向量，向量 v 定義 為 相關數(shù)據(jù)的更新－ 初等行變換 設 轉軸元 是 ，即 aq 出基， ap進基 以 為轉軸元， 轉軸后 即得新基對應的數(shù)據(jù)！ 例 1 a2進基 ，計算 y2. 計算表格如下： 計算 a1進基 ，計算 y1. 得如下表格： 最優(yōu)值： 最優(yōu)解： 利用兩階段單純形過程求解 1 2 3 41 2 3 41 2 3 41 2 3 4m in 3 3. 2 0 2 2 3 3 9 2 6 0ix x x xs t x x x xx x x xx x x xx? ? ? ?? ? ? ?? ? ? ?? ? ? ??
公司管理相關推薦
鄂ICP備17016276號-1