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

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