目標(biāo)規(guī)劃單純形法

1、2.2.3 目標(biāo)規(guī)劃的圖解法,例某企業(yè)生產(chǎn)兩種產(chǎn)品，在單件利潤等有關(guān)數(shù)據(jù)已知條件下，要求制定一個獲利最大的生產(chǎn)計(jì)劃： 目標(biāo)，第一級：允許加班，加班時間每周不超過10小時；第二級：產(chǎn)品產(chǎn)量滿足市場需求,2.2.3 目標(biāo)規(guī)劃的圖解法,例，某電視機(jī)廠裝配黑白和彩色電視，每裝配一臺占用裝配線1小時，裝配線每周計(jì)劃開動40小時。預(yù)計(jì)市場每周彩色電視機(jī)的銷售量為24臺，每臺獲利80元，黑白電視機(jī)銷售量30臺，每臺可獲利40元，該廠目標(biāo)為： 第一級：充分利用裝配線每周開動40小時 第二級：允許裝配加班，但每周盡量不超過10小時 第三級：允許裝配電視機(jī)的數(shù)量盡量滿足市需要，因彩色利潤高，故其權(quán)系數(shù)為2,2.2

2、.4 目標(biāo)規(guī)劃的基本概念,線性規(guī)劃目標(biāo) 可行解 可接受解與不可接受解 達(dá)成函數(shù) 最優(yōu)解 多重最優(yōu)解 無界解,2.2.5 目標(biāo)規(guī)劃的單純形法,一般形式：,2.2.5 目標(biāo)規(guī)劃的單純形法,單純形法的計(jì)算步驟 1、建立初始單純形表 一般假定初始解在原點(diǎn)，即以約束條件中的所有負(fù)偏差變量或松弛變量為初始基變量，按目標(biāo)優(yōu)先等級從左至右分別計(jì)算出各列的檢驗(yàn)數(shù)，填入表下半部的K行中，置 k=1 。,2.2.5 目標(biāo)規(guī)劃的單純形法,2、檢驗(yàn)是否為滿意解 若Pk這一行某些負(fù)檢驗(yàn)數(shù)的同列上面（較高優(yōu)先等級）沒有正檢驗(yàn)數(shù)，說明未得到滿意解，應(yīng)繼續(xù)改進(jìn)，轉(zhuǎn)到第3步；若Pk這一行全部負(fù)檢驗(yàn)數(shù)的同列上面（較高優(yōu)先等級）都有

3、正檢驗(yàn)數(shù)，說明目標(biāo)雖沒達(dá)到，但已不能改進(jìn)，故得滿意解，轉(zhuǎn)到第6步。,2.2.5 目標(biāo)規(guī)劃的單純形法,3、確定進(jìn)基變量 在Pk行，從那些上面沒有正檢驗(yàn)數(shù)的負(fù)檢驗(yàn)數(shù)中，選絕對值最大者，對應(yīng)的變量xs就是進(jìn)基變量。若Pk行中有幾個相同的絕對值最大者，則依次比較它們各列下部的檢驗(yàn)數(shù)，取其絕對值最大的負(fù)檢驗(yàn)數(shù)的所在列的xs為進(jìn)基變量。假如仍無法確定，則選最左邊的變量（變量下標(biāo)小者）為進(jìn)基變量，轉(zhuǎn)第4步。否則，轉(zhuǎn)第6步。,2.2.5 目標(biāo)規(guī)劃的單純形法,4、確定出基變量 其方法同線性規(guī)劃，即依據(jù)最小比值法則 故確定xr為出基變量，ers為主元素。若有幾個相同的行可供選擇時，選最上面那一行所對應(yīng)得變量為xr

4、 。,2.2.5 目標(biāo)規(guī)劃的單純形法,5、旋轉(zhuǎn)變換（變量迭代） 以ers為主元素進(jìn)行變換，得到新的單純形表，獲得一組新解，返回到第2步。 6、對求得的解進(jìn)行分析 當(dāng)k=K時，計(jì)算結(jié)束，停止運(yùn)算；表中的解即為最終解。若不滿意，需修改模型，即調(diào)整目標(biāo)優(yōu)先等級和權(quán)系數(shù)，或者改變目標(biāo)值，重新進(jìn)行第1步。否則置k=k+1，返回第2步。,例 用單純形法求解下列目標(biāo)規(guī)劃問題,= min2500/30,140/2,60/1=60 ,故 為換出變量。,2.2.5 目標(biāo)規(guī)劃的單純形法,= min700/30,20/2, =10 ,故 為換出變量。,2.2.5 目標(biāo)規(guī)劃的單純形法,= min400/15, =10 ,故 為換出變量。,2.2.5 目標(biāo)規(guī)劃的單純形法,= min,350/6,1250/6,100/1=75 ,故 為換出變量。,2.2.5 目標(biāo)規(guī)劃的單純形法,表中P3行仍有負(fù)數(shù)，說明P3 優(yōu)先等級目標(biāo)沒有實(shí)現(xiàn)，但已無法改進(jìn)，得到滿意解 x1 60， x2 175/3， 115/3， 125/3。,2.2.5 目標(biāo)規(guī)劃的單純形法,課堂練習(xí)：用單純形法求解下列目標(biāo)規(guī)劃問題,2.2.5 目標(biāo)規(guī)劃的單純