2-最優(yōu)化方法-線性規(guī)劃-單純形法-全文預(yù)覽
【正文】 第二張 單純形表 注意基變量整列包括末行 z在內(nèi)除了基變量其他元素都是 0 輔助問題的 最優(yōu)值是 0. 原問題的 BFS： 兩階段法－ 可求任一 線性規(guī)劃問題 ◎ 第 I階段：啟動單純形法 →構(gòu)造、求解輔助問題 →判斷原問題 不可行、或可行 → 可行時找到基本可行解及對應(yīng)規(guī)范形 ⊙ 第 II階段：利用單純形法求原問題 →從上述 BFS出發(fā)，求解所給問題 →原問題 無界 或者 有解 例 2. 利用兩階段法求解下面的問題 輔助問題 第 I階段： 先構(gòu)造輔助向量 z=x4+x5 輔助問題的 最后一張單純形表 原問題的 初始 表格： 得到輔助問題的最后一張單純形表后，去掉輔助變量，將原始問題的 z帶入表格，啟動單純形法 原問題的 最優(yōu)解 ： 6. 修正單純形法 (Revised simplex method) ◎ 重要事實： ⊙ 通常僅有少數(shù)列發(fā)生轉(zhuǎn)軸 (2m3m) ◎ 核心問題： 如何更新 當前基的逆 →新基的逆 理論上的表現(xiàn) 表格實現(xiàn) ⊙ 僅需原始數(shù)據(jù) (c, A, b)和基 B 的逆矩陣 7. 單純形法的矩陣形式 給定基 B 及對應(yīng) BFS (xB, 0), 其中 xB=B1b 用 非基 變量表示 目標函數(shù) ： 用 非基 變量表示 基 變量： 相對 費用向量 初始表格－單純形表 初始表格 通常不是單純形表！ 與基矩陣 B 對應(yīng)的 單純形表 修正單純形法的計算步驟 步 2 選取 q 滿足 步 3 計算 yq=B1aq； 若 步 1 計算 。如果 停；得最優(yōu)解 . 步 0 給定 BFS及對應(yīng)的 B1。實用優(yōu)化方法 線性規(guī)劃：單純形法 線性規(guī)劃 ： 目標函數(shù)是線性的，約束條件是 線性等式或不等式 線性規(guī)劃 線性規(guī)劃的歷史 ? 淵源要追溯到 Euler、 Liebnitz、 Lagrange等 ? Gee Dantzig, Von Neumann(Princeton)和Leonid Kantorovich在 1940’s創(chuàng)建了線性規(guī)劃 ? 1947年 , Gee Dantzig發(fā)明了單純形法 ? 1979年 ， L. Khachain找到了求解線性規(guī)劃的一種有效方法 (第一個多項式時間算法 －橢球內(nèi)點法 ) ? 1984年 ， Narendra Karmarkan發(fā)現(xiàn)了另一種求解線性規(guī)劃的有效方法，已證明是單純形法的強有力的競爭者 (投影內(nèi)點法 ) ? 現(xiàn)在求解大規(guī)模、退化問題最有效的是 原－對偶內(nèi)點法 ◎ 問題 ：確定食品數(shù)量，滿足營養(yǎng)需求，花費最??？ ◎ 變量： n種食品， m種營養(yǎng)成份； －第 j 種食品的單價 －每單位第 j 種食品所含第 i 種營養(yǎng)的數(shù)量 －食用第 j 種食品的數(shù)量 －為了健康，每天必須食用第 i 種營養(yǎng)的數(shù)量 ◎ 模型： 例 1. 食譜問題 例 2. 運輸
公司管理相關(guān)推薦
鄂ICP備17016276號-1