線性規(guī)劃的圖解法與單純形解法.ppt

運籌學OperationsResearch 吳清烈 東南大學經(jīng)濟管理學院電子商務(wù)系暨管理工程研究所02583795358wql 線性規(guī)劃的圖解法與單純形解法 線性規(guī)劃問題的圖解法線性規(guī)劃單純形解法的原理線性規(guī)劃單純形解法的計算步驟單純形法計算的矩陣描述線性規(guī)劃單純形求解的大M法線性規(guī)劃單純形求解的兩階段法線性規(guī)劃單純形求解可能的循環(huán)現(xiàn)象線性規(guī)劃單純形法的改進 線性規(guī)劃問題的圖解法 圖解法 就是用作圖的方法求解線性規(guī)劃問題 簡單 直觀的圖解法一般只適用于具有兩個決策變量的線性規(guī)劃問題 用圖解法求解實際線性規(guī)劃問題 一般按照如下基本步驟 Step1畫直坐標系 Step2根據(jù)約束條件畫出可行域 Step3畫過坐標原點的目標函數(shù)線 Step4確定目標函數(shù)值的增大方向 目標函數(shù)線法線方向 Step5目標函數(shù)線沿著增大方向平行移動 與可行域相交且有最大目標函數(shù)值的頂點 即為線性規(guī)劃問題的最優(yōu)解 線性規(guī)劃問題的圖解法舉例 maxz 2x1 x2 3x1 x2 12x1 x2 5x2 3x1 x2 0 線性規(guī)劃問題求解的幾種可能結(jié)局 存在唯一最優(yōu)解 如上例 存在無窮多個最優(yōu)解 如在上例中 將目標函數(shù)改為maxz 3x1 x2 這時Q1與Q2以及Q1與Q2之間的所有點均為最優(yōu)解 存在無界解 有可行解但無有界最優(yōu)解 如在上例中 只含有x2 3一個約束 可行域為無界 z的取值可無窮大 無解或無可行解 如下述線性規(guī)劃問題maxz 2x1 x2x1 x2 2 x1 x2 5x1 x2 0 約束條件矛盾 因而無可行解 由圖解法得到的啟示 線性規(guī)劃問題求解的基本依據(jù)是 線性規(guī)劃問題的最優(yōu)解總可在可行域的頂點中尋找 尋找線性規(guī)劃問題的最優(yōu)解只需比較有限個頂點處的目標函數(shù)值 線性規(guī)劃問題求解時可能出現(xiàn)四種結(jié)局 唯一最優(yōu)解 無窮多個最優(yōu)解 無有界解 無解或無可行解 如果某一線性規(guī)劃問題有最優(yōu)解 我們可以按照這樣的思路來求解 先找可行域中的一個頂點 計算頂點處的目標函數(shù)值 然后判別是否有其它頂點處的目標函數(shù)值比這個頂點處的目標函數(shù)值更大 如有 轉(zhuǎn)到新的頂點 重復(fù)上述過程 直到找不到使目標函數(shù)值更大的新頂點為止 線性規(guī)劃單純形解法的原理 單純形方法的基本思想從可行域中的一個基可行解出發(fā) 判別它是否已經(jīng)是最優(yōu)解 如不是 尋找下一個基可行解 并且同時努力使目標函數(shù)得到改進 如此迭代下去 直到找到最優(yōu)解或判定問題無解為止 單純形算法必須解決三個方面的問題 1 如何確定初始的基可行解 2 如何進行解的最優(yōu)性判別 3 如何尋找改進的基可行解 確定初始的基可行解 標準型的線性規(guī)劃問題 系數(shù)矩陣中存在一個單位陣 以單位陣為一初始可行基 令非基變量取值為零 便得到一基可行解 最優(yōu)性檢驗和解的判別 對標準型的一般線性規(guī)劃問題 經(jīng)過變換 迭代總可將線性規(guī)劃約束條件中非基變量移至 方程右邊 得如下形式 最優(yōu)性檢驗和解的判別 將上式代入目標函數(shù)式中 整理得 令 最優(yōu)性檢驗和解的判別 再令 稱為檢驗數(shù) 在線性規(guī)劃模型中 可以用檢驗數(shù)替代目標函數(shù)中的價值系數(shù)cj 最優(yōu)解的判別定理 定理1最優(yōu)解的判別定理 定理2有無窮多最優(yōu)解的判別定理 最優(yōu)解的判別定理 定理3有無界解的判別定理 尋找改進的基可行解 當檢驗?zāi)硞€基可行解不是最優(yōu) 也非無界 那么就應(yīng)該從該頂點 基可行解 處出發(fā) 尋找一個新的能使目標函數(shù)值改進的相鄰頂點 基可行解 注 稱兩個基可行解為相鄰的 是指它們之間變換且僅變換一個基變量 具體的方法是 在基變量中 選出一個 讓它變?yōu)榉腔兞?同時 從非基變量中 選出一個 讓它變?yōu)榛兞?從而構(gòu)造一個新基 我們希望 每變換一次 就得到一個新的基可行解 并且是盡可能使目標函數(shù)值改進的基可行解 換入變量的確定 如果存在多個 j 0 則取 假定存在一個 我們?nèi)?為換入變量 換出變量的確定 換出變量的確定 若 我們選 為換出變量 尋找改進的基可行解 可以證明 x1 x2 xl 1 xl 1 xm xm k 所對應(yīng)的m個列向量P1 P2 Pl 1 Pl 1 Pm Pm k線性無關(guān) 因而B P1 P2 Pl 1 Pl 1 Pm Pm k 是一個新基 最佳換入換出變量確定 單純形表 單純形算法的計算步驟 將線性規(guī)劃問題化成標準型 找出或構(gòu)造一個m階單位矩陣作為初始可行基 建立初始單純形表 計算各非基變量xj的檢驗數(shù) j 若所有 j 0 則問題已得到最優(yōu)解 停止計算 否則轉(zhuǎn)入下步 在大于0的檢驗數(shù)中 若某個 k所對應(yīng)的系數(shù)列向量Pk 0 則此問題是無界解 停止計算 否則轉(zhuǎn)入下步 根據(jù)max j j 0 k原則 確定xk為換入變量 進基變量 再按 規(guī)則計算 min bi aik aik 0 bl aik確定xl為換出變量 建立新的單純形表 此時基變量中xk取代了xl的位置 以aik為主元素進行迭代 把xk所對應(yīng)的列向量變?yōu)閱挝涣邢蛄?即aik變?yōu)? 同列中其它元素為0 轉(zhuǎn)第 步 單純形算法計算舉例 單純形法計算舉例 P1P2P3P4P5b 單純形法計算舉例 單純形法計算舉例 單純形法計算舉例 單純形法計算的矩陣描述 單純形法計算的矩陣描述 單純形法計算的矩陣描述 單純形法計算的矩陣描述 單純形法計算的矩陣描述 單純形法計算的矩陣描述 單純形法計算的矩陣描述 線性規(guī)劃求解的人工變量法 人工變量法引用人工變量是用單純形法求解線性規(guī)劃問題時解決可行解問題的常用方法 人工變量法的基本思路是 若原線性規(guī)劃問題的系數(shù)矩陣中沒有單位向量 則在每個約束方程中加入一個人工變量便可在系數(shù)矩陣中形成一個單位向量 由于單位陣可以作為基陣 因此 可選加入的人工變量為基變量 然后 再通過基變換 使得基變量中不含非零的人工變量 如果在最終單純形表中還存在非零的人工變量 這表示無可行解 線性規(guī)劃求解的人工變量法 線性規(guī)劃求解的人工變量法 為了使加入人工變量后線性規(guī)劃問題的最優(yōu)目標函數(shù)值不受影響 我們賦予人工變量一個很大的負價值系數(shù) M M為任意大的正數(shù) 由于人工變量對目標函數(shù)有很大的負影響 單純形法的尋優(yōu)機制會自動將人工變量趕到基外 從而找到原問題的一個可行基 這種方法我們通常稱其為大M法 線性規(guī)劃求解的大M法 線性規(guī)劃求解的大M法 線性規(guī)劃求解的大M法舉例 線性規(guī)劃求解的大M法舉例 線性規(guī)劃求解的大M法舉例 線性規(guī)劃求解的兩階段法 線性規(guī)劃求解的兩階段法 然后用單純形法求解所構(gòu)造的新模型 若得到w 0 這時 若基變量中不含人工變量 則說明原問題存在基可行解 可進行第二步計算 否則 原問題無可行解 應(yīng)停止計算 第二階段 單純形法求解原問題第一階段計算得到的最終單純形表中除去人工變量 將目標函數(shù)行的系數(shù) 換成原問題的目標函數(shù)后 作為第二階段計算的初始表 繼續(xù)求解 線性規(guī)劃求解兩階段法舉例 線性規(guī)劃求解兩階段法舉例 線性規(guī)劃求解兩階段法舉例 單純形法計算可能的循環(huán)現(xiàn)象 單純形法計算可能的循環(huán)現(xiàn)象 在求解線性規(guī)劃單純形方法的計算過程循環(huán)極少出現(xiàn) 但還是可能的 為防止出現(xiàn)循環(huán)現(xiàn)象 先后有人提出了一些方法 如 勃蘭特法