運(yùn)籌目標(biāo)規(guī)劃素材_第1頁
運(yùn)籌目標(biāo)規(guī)劃素材_第2頁
運(yùn)籌目標(biāo)規(guī)劃素材_第3頁
運(yùn)籌目標(biāo)規(guī)劃素材_第4頁
運(yùn)籌目標(biāo)規(guī)劃素材_第5頁
已閱讀5頁,還剩34頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

2024/11/71運(yùn)籌學(xué)

OPERATIONSRESEARCH

2024/11/72第五章目標(biāo)規(guī)劃

目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃的圖解法目標(biāo)規(guī)劃的單純形解法目標(biāo)規(guī)劃的層次算法目標(biāo)規(guī)劃的應(yīng)用2024/11/73§1目標(biāo)規(guī)劃的提出與數(shù)學(xué)模型

§1.1引例例1生產(chǎn)計劃問題

Ⅱ能力設(shè)備A2212設(shè)備B4

016設(shè)備C0515利潤23Ⅰ,Ⅱ各生產(chǎn)多少,可獲最大利潤?2024/11/74解:設(shè)產(chǎn)品Ⅰ,Ⅱ產(chǎn)量分別為變量最優(yōu)解:這里的目標(biāo)只有一個!2024/11/75有時目標(biāo)不只一個,例如考慮下列要求:1、力求利潤指標(biāo)不低于15元;2、Ⅰ、Ⅱ兩種產(chǎn)品的產(chǎn)量保持1:2;3、A為貴重設(shè)備,嚴(yán)格禁止超時使用;4、設(shè)備C可適當(dāng)加班,但要控制;5、設(shè)備B既要充分利用,又要盡量不加班,在重要性上,設(shè)備B是設(shè)備C的3倍。

要解決這樣的問題,將上述的要求都加以考慮,就要用目標(biāo)規(guī)劃的方法解決。2024/11/76目標(biāo)規(guī)劃是在線性規(guī)劃的基礎(chǔ)上,為適應(yīng)企業(yè)經(jīng)營管理中多目標(biāo)決策的需要而逐步發(fā)展起來的。目標(biāo)規(guī)劃是一種數(shù)學(xué)方法?;竞x:在一定約束條件下,要求多個目標(biāo)達(dá)到或盡可能接近于給定的對應(yīng)目標(biāo)值。特點:既保持了線性規(guī)劃易于計算的特點,又克服了線性規(guī)劃只能解決單一目標(biāo)優(yōu)化問題的局限性。2024/11/77目標(biāo)規(guī)劃產(chǎn)生與發(fā)展目標(biāo)規(guī)劃的有關(guān)概念和數(shù)學(xué)模型是在1961年由美國學(xué)者查恩斯(A.Charnes)和庫伯(W.W.Cooper)首次在《管理模型及線性規(guī)劃的工業(yè)應(yīng)用》一書中提出。當(dāng)時是作為解一個沒有可行解的線性規(guī)劃而引入的一種方法。這種方法把規(guī)劃問題表達(dá)為盡可能地接近預(yù)期的目標(biāo)。1965年,尤吉·艾吉里(Yuji·Ijiri)在處理多目標(biāo)問題,分析各類目標(biāo)的重要性時,引入了賦予各目標(biāo)一個優(yōu)先因子及加權(quán)系數(shù)的概念;并進(jìn)一步完善了目標(biāo)規(guī)劃的數(shù)學(xué)模型。表達(dá)和求解目標(biāo)規(guī)劃問題的方法是由杰斯基萊恩(Jashekilaineu)和桑李(SangLi)給出并加以改進(jìn)的。2024/11/78§1.2

目標(biāo)規(guī)劃的有關(guān)概念1、正、負(fù)偏差變量:

等是決策變量;

是正偏差變量,表決策值超過目標(biāo)值的部分;是負(fù)偏差變量,表決策值未達(dá)目標(biāo)值的部分。

且有。2、絕對約束和目標(biāo)約束

絕對約束:必須滿足的等式約束或不等式約束。

如:A設(shè)備嚴(yán)格禁止超時使用,則

2024/11/79目標(biāo)約束:對于不嚴(yán)格限定的約束,在達(dá)到此目標(biāo)時允許發(fā)生正或負(fù)的偏差,可在這些約束中加入正負(fù)偏差變量,成為目標(biāo)約束。如:(1)“Ⅰ、Ⅱ兩種產(chǎn)品的產(chǎn)量保持1:2”可表示為●當(dāng)允許此比例時,即,則引入負(fù)偏差,則該條件可表示為:●類似地有,表示允許此比例?!癖硎尽傲η螈瘛ⅱ騼煞N產(chǎn)品的產(chǎn)量比例不”2024/11/710(2)目標(biāo)函數(shù)也可轉(zhuǎn)化為目標(biāo)約束:如:“力求利潤指標(biāo)不低于15元”可表示為(3)“設(shè)備C可適當(dāng)加班,但要控制”可表示為(4)“設(shè)備B既要充分利用,又要盡量不加班”可表示為2024/11/7113、目標(biāo)的優(yōu)先級和權(quán)系數(shù)

不同的目標(biāo)重要程度不同,優(yōu)先級不同;同一層次優(yōu)先級的不同目標(biāo),重要程度不同,權(quán)重不同優(yōu)先級因子:,且權(quán)重系數(shù):,數(shù)值的大小決定目標(biāo)的重要程度。假設(shè):第一優(yōu)先級:利潤不低于15元;第二優(yōu)先級:Ⅰ、Ⅱ產(chǎn)品的數(shù)量盡量保持1:2;第三優(yōu)先級:C、B的工作時間控制,且B的重要性是C的3倍。4、目標(biāo)函數(shù):目標(biāo)函數(shù)是要盡量縮小偏離目標(biāo)值2024/11/712于是按照上例中的有關(guān)要求,該目標(biāo)規(guī)劃的目標(biāo)函數(shù)約束條件:2024/11/713目標(biāo)規(guī)劃特點:可以同時考慮多個目標(biāo);可以區(qū)分不同目標(biāo)的優(yōu)先程度及重要程度;更加切合實際,更加靈活目標(biāo)規(guī)劃中的優(yōu)先級及權(quán)重系數(shù)的確定往往需要靠人的主觀判斷,是定性的,常常是模糊的,不是一個確定的數(shù)值,但現(xiàn)在也有很多將其定量化的方法,如層次分析法等這是處理目標(biāo)規(guī)劃時的一個難點。2024/11/714一般的目標(biāo)規(guī)劃數(shù)學(xué)模型剛性約束柔性約束2024/11/715§2目標(biāo)規(guī)劃的圖解分析法求解目標(biāo)規(guī)劃的思路:剛性約束必須嚴(yán)格滿足;按優(yōu)先級次序,從高層到低層逐層優(yōu)化;在不增加高層偏差值的情況下,使本層的偏差達(dá)到最小。只有兩個決策變量的目標(biāo)規(guī)劃可用圖解法分析。以上例為例,圖解分析如下。2024/11/716滿意解F2024/11/717§3目標(biāo)規(guī)劃的單純形解法單純形法求解目標(biāo)規(guī)劃的思路:1.求解步驟與一般線性規(guī)劃問題的單純形法基本相同;2.根據(jù)目標(biāo)函數(shù)中的優(yōu)先級次序,從高層到低層逐層優(yōu)化;3.單純形表中,檢驗數(shù)按優(yōu)先級次序分行表示。例:2024/11/71800P100P1P20CBXBbx1X2d1-d1+d2-d2+d3-d3+P1d1-10[1]01-10d2-40211-1P2d3-100321-1P1-111P2-3-21第一步:列初始單純形表2024/11/719第二步:確定進(jìn)基變量。按照優(yōu)先級次序,檢查P1,P2,…,Pk行檢驗數(shù)是否仍有負(fù)值(<0)若有,找優(yōu)先級最高一行的負(fù)值最小檢驗數(shù)對應(yīng)變量作為進(jìn)基變量。此例中選x1第三步:確定出基變量。按照最小比值規(guī)則確定出基變量,此例中選d1-第四步:迭代運(yùn)算,得到新的基可行解,判斷是否最優(yōu)。本例中,P2行仍有負(fù)檢驗數(shù),轉(zhuǎn)到第二步。2024/11/72000P100P1P20CBXBbx1X2d1-d1+d2-d2+d3-d3+0x110[1]01-10d2-2001-2[2]1-1P2d3-7002-331-1P111P2-23-3100P100P1P20CBXBbx1X2d1-d1+d2-d2+d3-d3+0x12011/2001/2-1/20d1+100[1/2]-111/2-1/2P2d3-4001/200-3/23/21-1P111P2-1/23/2-3/212024/11/72100P100P1P20CBXBbx1X2d1-d1+d2-d2+d3-d3+0x110101-1000X22001-221-1P2d3-30001-1-221-1P111P2-112-21注意:此時,P2行仍有負(fù)檢驗數(shù),要選X2進(jìn)基,因為d2+的檢驗數(shù)是。此時,已達(dá)最優(yōu)。2024/11/722說明:1、進(jìn)行優(yōu)化是按照優(yōu)先級進(jìn)行的,當(dāng)高一級的目標(biāo)行的檢驗數(shù)全部非負(fù)時,可進(jìn)行下一級的優(yōu)化;2、判別迭代終止的準(zhǔn)則:

(1)所有級別的檢驗數(shù)行均非負(fù),迭代終止;(2)若行檢驗數(shù)均非負(fù),而行有負(fù)檢驗數(shù),但這些負(fù)檢驗數(shù)對應(yīng)的上面行中有正檢驗數(shù),迭代終止。2024/11/723§4目標(biāo)規(guī)劃的層次算法(思想同前)第一步:先對目標(biāo)函數(shù)中的層次進(jìn)行優(yōu)化。建立第一層次的線性規(guī)劃模型,記為LP1.目標(biāo)函數(shù):由第一優(yōu)先級的偏差變量構(gòu)成約束條件:由原約束構(gòu)成。設(shè)第一級優(yōu)化的最優(yōu)目標(biāo)值是2024/11/724第二步:對目標(biāo)函數(shù)中的層次進(jìn)行優(yōu)化。建立第二層次的線性規(guī)劃模型,記為LP2.目標(biāo)函數(shù):由第二優(yōu)先級的偏差變量構(gòu)成約束條件:在原約束基礎(chǔ)上增加新約束:設(shè)第二級優(yōu)化的最優(yōu)目標(biāo)值是。以此類推。2024/11/725§5目標(biāo)規(guī)劃應(yīng)用舉例例1:某電子廠生產(chǎn)錄音機(jī)和電視機(jī)兩種產(chǎn)品,分別經(jīng)由甲、乙兩個車間生產(chǎn)。已知除外構(gòu)件外,生產(chǎn)一臺錄音機(jī)需甲車間加工2h,乙車間裝配1h;生產(chǎn)一臺電視機(jī)需甲車間加工1h,乙車間裝配3h;檢驗銷售環(huán)節(jié):一臺錄音機(jī)檢驗銷售費(fèi)用50元;一臺電視機(jī)檢驗銷售費(fèi)用30元;2024/11/726工時及管理費(fèi)用:甲車間每月可用生產(chǎn)工時120h,車間管理費(fèi)用80元/h;乙車間每月可用生產(chǎn)工時150h,車間管理費(fèi)用20元/h;利潤及銷量:每臺錄音機(jī)利潤100元,平均每月可銷售50臺;每臺電視機(jī)利潤75元,平均每月可銷售80臺;月度計劃的目標(biāo)如下:2024/11/7271、第一優(yōu)先級:檢驗和銷售費(fèi)用每月不超過4600元;2、第二優(yōu)先級:每月銷售錄音機(jī)不少于50臺;3、第三優(yōu)先級:兩車間的工時得到充分利用(重要性權(quán)系數(shù)按每小時的管理費(fèi)用比);4、第四優(yōu)先級:甲車間加班不超過20小時;5、第五優(yōu)先級:每月銷售電視機(jī)不少于80臺;6、第六優(yōu)先級:兩車間的加班總時間要控制(權(quán)系數(shù)分配如3)試確定該廠為達(dá)到上述目標(biāo)的最優(yōu)月度生產(chǎn)計劃。2024/11/728解:假設(shè)每月生產(chǎn)錄音機(jī)臺,電視機(jī)臺。1、兩車間可用工時:2、檢驗和銷售費(fèi)用:3、每月銷售量:4、加班限制:于是模型如下2024/11/729約束:目標(biāo)函數(shù)2024/11/730例2:書P143例5解:設(shè)是i工廠調(diào)配給j用戶的產(chǎn)品數(shù)量。約束如下1、供應(yīng)量約束:2、需求量約束:3、用戶1需要量中工廠3的產(chǎn)品數(shù)量不少于100:2024/11/7314、各用戶滿足率不低于80%:5、運(yùn)費(fèi)限制:6、道路通過限制:7、用戶1和3的滿足率保持平衡:2024/11/7328、力求總運(yùn)費(fèi)減小:目標(biāo)函數(shù):2024/11/733例3:某單位領(lǐng)導(dǎo)在考慮本單位職工的升級調(diào)資方案時,依次遵守以下規(guī)定:1、年工資總額不超過120萬元;2、每級的人數(shù)不超過定編規(guī)定的人數(shù);3、Ⅱ、Ⅲ級的升級面盡可能達(dá)到現(xiàn)有人數(shù)的20%;4、Ⅲ級不足編制的人數(shù)可錄用新職工,又Ⅰ級的職工中有10%要退休。有關(guān)資料匯總于下表,請為該單位領(lǐng)導(dǎo)制定一個滿意的方案。2024/11/734等級工資額(元/年)現(xiàn)有人數(shù)編制人數(shù)Ⅰ400001012Ⅱ300001215Ⅲ200001515合計3742解:設(shè)分別表示提升到Ⅰ、Ⅱ級和錄用到Ⅲ級的職工人數(shù)。則模型如下:目標(biāo)函數(shù)各目標(biāo)約束:2024/11/735(1)年工資總額不超過120萬元;(2)每級的人數(shù)不超過編制規(guī)定的人數(shù);(3)Ⅱ、Ⅲ級的升級面盡可能達(dá)到現(xiàn)有人數(shù)的20%;例4:某農(nóng)場有3萬畝農(nóng)田,欲種植玉米、大豆和小麥。各種作物每畝需施化肥分別為0.12,0.20,0.15噸。預(yù)計秋后玉米每畝可收獲500公斤,售價為0.24元/公斤;大豆每畝可收獲200公斤,售價為1.20元/公斤;小麥每畝可收獲300公斤,售價為0.70元/公斤。農(nóng)場年初規(guī)劃時需考慮以下幾個方面:P1:年終收益不低于350萬元; P2:總產(chǎn)量不低于1.25萬噸;P3:小麥產(chǎn)量

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論