1、第六章 多目的規(guī)劃前面討論線性規(guī)劃、整數(shù)規(guī)劃都只有一個(gè)目的函數(shù)。但實(shí)際問題中往往需要考慮多個(gè)目的，并且在諸多目的中尚有主、次之分，有互相補(bǔ)充，有互相對(duì)立。問題是如何處理復(fù)雜甚至互相矛盾多個(gè)目的，即在一定約束條件下，要從眾多方案中選擇一個(gè)或幾種較好方案，使多個(gè)目的都能達(dá)到滿意結(jié)果。比如，設(shè)計(jì)一個(gè)新產(chǎn)品工藝過程，希望產(chǎn)量高、成本低、質(zhì)量好、利潤大。由于需要同時(shí)考慮多個(gè)目的，這類問題比單目的問題要復(fù)雜得多。多目的規(guī)劃是上個(gè)世紀(jì)60年代初發(fā)展起來運(yùn)籌學(xué)一個(gè)分支。 第1頁第1頁6.1 多目的規(guī)劃數(shù)學(xué)模型6.2 多目的規(guī)劃解集和象集6.3 處理多目的規(guī)劃一些辦法6.4 目的規(guī)劃第六章 多目的規(guī)劃第2頁第2

2、頁例6-1建立數(shù)學(xué)模型：對(duì)第i個(gè)公司投資對(duì)第i個(gè)公司不投資設(shè)總投資為總收益為第3頁第3頁6.1 多目的規(guī)劃數(shù)學(xué)模型6.2 多目的規(guī)劃解集和象集6.3 處理多目的規(guī)劃一些辦法6.4 目的規(guī)劃第六章 多目的規(guī)劃第4頁第4頁第四節(jié) 目的規(guī)劃目的規(guī)劃辦法是當(dāng)前處理多目的規(guī)劃問題成功辦法之一，它是在(LP)基礎(chǔ)上發(fā)展起來。這種辦法基本思想是：對(duì)每一個(gè)目的函數(shù)，預(yù)先給定一個(gè)盼望值(目的值)，在既有約束條件下，這組盼望值也許能夠達(dá)到，也許達(dá)不到。我們?nèi)蝿?wù)是求出盡量靠近這組預(yù)定盼望值解。 第六章 多目的規(guī)劃多目的規(guī)劃6-4第5頁第5頁第四節(jié) 目的規(guī)劃線性目的規(guī)劃數(shù)學(xué)模型線性目的規(guī)劃求解辦法 序列法多階段法單純

3、形法 第六章 多目的規(guī)劃第6頁第6頁 某企業(yè)在計(jì)劃期內(nèi)計(jì)劃生產(chǎn)甲、乙、丙三種產(chǎn)品。這些產(chǎn)品分別需要在設(shè)備A,B上加工,需要消耗材料C,D，單件產(chǎn)品在不同設(shè)備上加工工時(shí)、所需要材料及現(xiàn)有資源、可得利潤以下表所表示。建立使企業(yè)總利潤最大線性規(guī)劃模型。例1產(chǎn)品甲乙丙資源設(shè)備A312200工時(shí)設(shè)備B224200工時(shí)材料C451360公斤材料D235300公斤利潤(元/件)403050設(shè)甲乙丙三種產(chǎn)品產(chǎn)量為 件，則數(shù)學(xué)模型為：一.線性目的規(guī)劃數(shù)學(xué)模型：多目的規(guī)劃6-4第7頁第7頁例1產(chǎn)品甲乙丙資源設(shè)備A312200工時(shí)設(shè)備B224200工時(shí)材料C451360公斤材料D235300公斤利潤(元/件)403

4、050 現(xiàn)在公司決議者依據(jù)實(shí)際情況和市場需求，需要重新制定經(jīng)營目的，目的優(yōu)先順序下列：(1)利潤不少于3200元；(2)產(chǎn)品甲乙產(chǎn)量百分比盡也許不超出1.5；(3)丙產(chǎn)量達(dá)到30件；(4)最好不加班；(5)受到資金限制，只能使用既有材料而不能再購進(jìn)。 問公司如何安排生產(chǎn)計(jì)劃才干達(dá)到經(jīng)營目的？多目的規(guī)劃6-4第8頁第8頁例1產(chǎn)品甲乙丙資源設(shè)備A312200工時(shí)設(shè)備B224200工時(shí)材料C451360公斤材料D235300公斤利潤(元/件)403050(1)利潤不少于3200元；(2)產(chǎn)品甲乙產(chǎn)量百分比盡也許不超出1.5；(3)丙產(chǎn)量達(dá)到30件；(4)最好不加班；(5)受到資金限制，只能使用既有材

5、料而不能再購進(jìn)。解：最優(yōu)解是求下列一組不等式解:多目的規(guī)劃6-4第9頁第9頁例1(1)利潤不少于3200元；(2)產(chǎn)品甲乙產(chǎn)量百分比盡也許不超出1.5；(3)丙產(chǎn)量達(dá)到30件；(4)最好不加班；(5)受到資金限制，只能使用既有材料而不能再購進(jìn)。解：通過計(jì)算不等式無解。但在實(shí)際問題中，生產(chǎn)方案總是存在，無解只能闡明在既有資源條件下，不也許完全滿足5個(gè)經(jīng)營目的。目標(biāo)規(guī)劃是按事先制訂目標(biāo)次序逐項(xiàng)檢驗(yàn)，盡也許使得結(jié)果達(dá)到預(yù)定目標(biāo)，即使不能達(dá)到目標(biāo)，也要使得結(jié)果離目標(biāo)差距為最小。這就是目標(biāo)規(guī)劃求解思緒。對(duì)應(yīng)解稱為滿意解。最優(yōu)解是求下列一組不等式解。多目的規(guī)劃6-4第10頁第10頁例1(1)利潤不少于32

6、00元；(2)產(chǎn)品甲乙產(chǎn)量百分比盡也許不超出1.5；(3)丙產(chǎn)量達(dá)到30件；(4)最好不加班；(5)受到資金限制，只能使用既有材料而不能再購進(jìn)。解：下面建立目的規(guī)劃數(shù)學(xué)模型：建立目的規(guī)劃數(shù)學(xué)模型辦法：1.引入偏差變量將目的轉(zhuǎn)化為目的約束；2.極小化偏差變量實(shí)現(xiàn)目的。多目的規(guī)劃6-4第11頁第11頁例1(1)利潤不少于3200元；解：引入一對(duì)偏差變量：負(fù)偏差變量d1- = 利潤不足目的值差額值正偏差變量d1+ = 利潤超出目的值超出值當(dāng)利潤0且d1+=0 ，有3200利潤當(dāng)利潤 3200時(shí)， d1+0且d1-=0 ，有3200利潤當(dāng)利潤= 3200時(shí)， d1+=0且d1-=0 ，有實(shí)際情況只有一

7、個(gè)情況發(fā)生，因此將三式合并為一個(gè)等式：目的約束：含有更大彈性，允許結(jié)果與所制定目的值存在正或負(fù)偏差。多目的規(guī)劃6-4第12頁第12頁例1(1)利潤不少于3200元；解：分析：1.引入偏差變量將目的轉(zhuǎn)化為目的約束；2.極小化偏差變量實(shí)現(xiàn)目的。目的約束性能指標(biāo)目的值(盼望值)多目的規(guī)劃6-4第13頁第13頁(2)甲乙產(chǎn)量百分比盡也許不超出1.5；例1負(fù)偏差變量d2- = 不足產(chǎn)品百分比要求差額值正偏差變量d2+ = 超出產(chǎn)品百分比要求超出值分析：1.引入偏差變量將目的轉(zhuǎn)2.極小化偏差變量實(shí)現(xiàn)目的?；癁槟康募s束；性能指標(biāo)目的值(盼望值)多目的規(guī)劃6-4第14頁第14頁(3)丙產(chǎn)量達(dá)到30件；例1負(fù)偏

8、差變量d3- = 丙產(chǎn)量不足目的值30件差額值正偏差變量d3+ = 丙產(chǎn)量超出目的值30件超出值分析：1.引入偏差變量將目2.極小化偏差變量實(shí)標(biāo)轉(zhuǎn)化為目的約束；現(xiàn)目的。性能指標(biāo)目的值(盼望值)多目的規(guī)劃6-4第15頁第15頁多目的規(guī)劃6-4目的值(盼望值)(4)最好不加班；例1產(chǎn)品甲乙丙資源設(shè)備A312200工時(shí)設(shè)備B224200工時(shí)材料C451360公斤材料D235300公斤負(fù)偏差變量d4- = 設(shè)備A工作時(shí)間不足目的值200工時(shí)差額值正偏差變量d4+ = 設(shè)備A工作時(shí)間超出目的值200工時(shí)超出值1.引入偏差變量將目的轉(zhuǎn)化為目的約束；2.極小化偏差變量實(shí)現(xiàn)目的。負(fù)偏差變量d5- = 設(shè)備B工

9、作時(shí)間不足目的值200工時(shí)差額值正偏差變量d5+ = 設(shè)備B工作時(shí)間超出目的值200工時(shí)超出值工作時(shí)間不超出額定工時(shí)數(shù)性能指標(biāo)第16頁第16頁目的值(盼望值)(4)最好不加班；例1負(fù)偏差變量d4- = 設(shè)備A工作時(shí)間不足目的值200工時(shí)差額值正偏差變量d4+ = 設(shè)備A工作時(shí)間超出目的值200工時(shí)超出值1.引入偏差變量將目的轉(zhuǎn)化為目的約束；2.極小化偏差變量實(shí)現(xiàn)目的。負(fù)偏差變量d5- = 設(shè)備B工作時(shí)間不足目的值200工時(shí)差額值正偏差變量d5+ = 設(shè)備B工作時(shí)間超出目的值200工時(shí)超出值工作時(shí)間不超出額定工時(shí)數(shù)性能指標(biāo)多目的規(guī)劃6-4第17頁第17頁多目的規(guī)劃6-4例1產(chǎn)品甲乙丙資源設(shè)備A3

10、12200工時(shí)設(shè)備B224200工時(shí)材料C451360公斤材料D235300公斤負(fù)偏差變量d6- =材料C消耗量不足目的值360公斤差額值正偏差變量d6+ =材料C消耗量超出目的值360公斤超出值1.引入偏差變量將目的轉(zhuǎn)化為目的約束；2.極小化偏差變量實(shí)現(xiàn)目的。負(fù)偏差變量d7- =材料D消耗量不足目的值300公斤差額值正偏差變量d7+ =材料D消耗量超出目的值300公斤超出值(5) 材料不再購進(jìn)第18頁第18頁例1負(fù)偏差變量d6- =所使用材料C不足目的值360公斤差額值正偏差變量d6+ =所使用材料C超出目的值360公斤超出值1.引入偏差變量將目的轉(zhuǎn)化為目的約束；2.極小化偏差變量實(shí)現(xiàn)目的。

11、負(fù)偏差變量d7- =所使用材料D不足目的值300公斤差額值正偏差變量d7+ =所使用材料D超出目的值300公斤超出值(5) 材料不再購進(jìn)多目的規(guī)劃6-4第19頁第19頁例1目的規(guī)劃數(shù)學(xué)模型：稱為目的優(yōu)先因子表示目的優(yōu)先順序，其含義是依次求目的最小值。首先求 最小值，在此基礎(chǔ)上求 最小值，最后求 最小值。多目的規(guī)劃6-4第20頁第20頁多目的規(guī)劃6-4將例1中建立數(shù)學(xué)模型辦法推廣到普通：將該目的轉(zhuǎn)化成目的約束：1.引入偏差變量將目的轉(zhuǎn)化為目的約束；2.極小化偏差變量實(shí)現(xiàn)目的。假設(shè)性能指標(biāo) 目的值為引入一對(duì)偏差變量：d - = 性能指標(biāo) f (X) 不足 f0 差額值d + = 性能指標(biāo) f (X

12、) 超出 f0 超出值一.線性目的規(guī)劃數(shù)學(xué)模型：第21頁第21頁多目的規(guī)劃6-4目的規(guī)劃有下列五種形式目的函數(shù)：1.單目的目的規(guī)劃數(shù)學(xué)模型：1.引入偏差變量將目的轉(zhuǎn)化為目的約束；2.極小化偏差變量實(shí)現(xiàn)目的。1. 若要求 ，則目的函數(shù)為 min (d - + d + )2. 若要求 ，則目的函數(shù)為 min d -3. 若要求 ，則目的函數(shù)為 min d +4. 若要求 ，則目的函數(shù)為 min (d + - d - )第22頁第22頁目的規(guī)劃有下列五種形式目的函數(shù)：1.單目的目的規(guī)劃數(shù)學(xué)模型：1. 若要求 ，則目的函數(shù)為 min (d - + d + )2. 若要求 ，則目的函數(shù)為 min d -

13、3. 若要求 ，則目的函數(shù)為 min d +4. 若要求 ，則目的函數(shù)為 min (d + - d - )5. 若要求 ，則目的函數(shù)為 min (d - - d + )多目的規(guī)劃6-4第23頁第23頁例2某廠生產(chǎn)兩種型號(hào)產(chǎn)品：產(chǎn)品甲和乙,產(chǎn)品信息下列表：產(chǎn)品工時(shí)(小時(shí)/件)產(chǎn)值(元/件)計(jì)劃產(chǎn)量(件/周)甲0.18030乙0.212015在制定最優(yōu)生產(chǎn)計(jì)劃時(shí)有下列 4 級(jí)目的：第一級(jí)目的盡也許達(dá)到計(jì)劃產(chǎn)值4000元/周；第二級(jí)目的第三級(jí)目的第四級(jí)目的避免加班；產(chǎn)量不要低于計(jì)劃值(產(chǎn)品乙為新型號(hào),更含有競爭力,故主要程度比為甲:乙=1:2)；又知該廠工作時(shí)間為40小時(shí)/周5小時(shí)/周。假如提前完畢

14、任務(wù),早下班時(shí)間也不要多于多目的規(guī)劃6-4第24頁第24頁設(shè)甲乙一周產(chǎn)量為例2產(chǎn)品工時(shí)產(chǎn)值計(jì)劃值甲0.18030乙0.212015第一級(jí)目的盡也許達(dá)到計(jì)劃產(chǎn)值4000元/周第二級(jí)目的第三級(jí)目的第四級(jí)目的避免加班產(chǎn)品數(shù)量不要低于計(jì)劃值5小時(shí)/周早下班時(shí)間不要多于甲:乙=1:2性能指標(biāo)目的值40早下班時(shí)間超出5超出值早下班時(shí)間不足5差額值乙產(chǎn)量超出15超出值乙產(chǎn)量不足15差額值甲產(chǎn)量超出30超出值甲產(chǎn)量不足30差額值工作時(shí)間超出40超出值工作時(shí)間不足40差額值產(chǎn)值超出4000超出值產(chǎn)值不足4000差額值甲產(chǎn)量 x1乙產(chǎn)量 x2早下班時(shí)間工作時(shí)間產(chǎn)值多目的規(guī)劃6-4第25頁第25頁例2產(chǎn)品工時(shí)產(chǎn)值計(jì)

15、劃值甲0.18030乙0.212015第一級(jí)目的盡也許達(dá)到計(jì)劃產(chǎn)值4000元/周第二級(jí)目的第三級(jí)目的第四級(jí)目的避免加班產(chǎn)品數(shù)量不要低于計(jì)劃值5小時(shí)/周早下班時(shí)間不要多于甲:乙=1:2設(shè)甲乙一周產(chǎn)量為多目的規(guī)劃6-4第26頁第26頁例2產(chǎn)品工時(shí)產(chǎn)值計(jì)劃值甲0.18030乙0.212015第一級(jí)目的盡也許達(dá)到計(jì)劃產(chǎn)值4000元/周第二級(jí)目的第三級(jí)目的第四級(jí)目的避免加班產(chǎn)品數(shù)量不要低于計(jì)劃值5小時(shí)/周早下班時(shí)間不要多于甲:乙=1:2設(shè)甲乙一周產(chǎn)量為多目的規(guī)劃6-4第27頁第27頁設(shè)甲乙一周產(chǎn)量為例2產(chǎn)品工時(shí)產(chǎn)值計(jì)劃值甲0.18030乙0.212015第一級(jí)目的盡也許達(dá)到計(jì)劃產(chǎn)值4000元/周第二級(jí)目

16、的第三級(jí)目的第四級(jí)目的避免加班產(chǎn)品數(shù)量不要低于計(jì)劃值5小時(shí)/周早下班時(shí)間不要多于甲:乙=1:2性能指標(biāo)目的值甲產(chǎn)量 x1乙產(chǎn)量 x2早下班時(shí)間工作時(shí)間產(chǎn)值四級(jí)目的目的規(guī)劃數(shù)學(xué)模型多目的規(guī)劃6-4第28頁第28頁設(shè)甲乙一周產(chǎn)量為例2第一級(jí)目的盡也許達(dá)到計(jì)劃產(chǎn)值4000元/周第二級(jí)目的第三級(jí)目的第四級(jí)目的避免加班產(chǎn)品數(shù)量不要低于計(jì)劃值5小時(shí)/周早下班時(shí)間不要多于甲:乙=1:2注釋:若各級(jí)目的偏差變量能達(dá)到極小值0,則各級(jí)目的被完全實(shí)現(xiàn).但多目的規(guī)劃中,由于各級(jí)目的之間也許是互補(bǔ),也也許是矛盾.因此在既有約束條件下各級(jí)目的也許能達(dá)到,也許不能達(dá)到.我們?nèi)蝿?wù)是使各級(jí)目的偏差變量達(dá)到最小.各級(jí)目的偏差變

17、量極小化程度反應(yīng)了各級(jí)目的被實(shí)現(xiàn)程度.四級(jí)目的目的規(guī)劃數(shù)學(xué)模型多目的規(guī)劃6-4第29頁第29頁例6-11 已知三個(gè)工廠生產(chǎn)產(chǎn)品供應(yīng)四個(gè)用戶需要, 各工廠產(chǎn)量, 用戶需求量及從各工廠到各用戶單位產(chǎn)品運(yùn)價(jià)下列表:1234產(chǎn)量130022003400銷量20010045025012341300220034004100200100450250最優(yōu)調(diào)運(yùn)方案上述方案只考慮了總運(yùn)費(fèi)最小.但在實(shí)際問題中,在制定最優(yōu)調(diào)運(yùn)方案時(shí),所追求目的及受到客觀限制往往是多方面。比如考慮下列7個(gè)目的：總產(chǎn)量=900總需求量=1000多目的規(guī)劃6-4第30頁第30頁目的1性能指標(biāo)目的值1234產(chǎn)量130022003400銷量2

18、00100450250用戶4是主要部門,需求量必須滿足目的2供應(yīng)用戶1產(chǎn)量中,工廠3產(chǎn)量不少于100目的3為兼顧普通,每個(gè)用戶需求量滿足率不低于80%80%16080360200多目的規(guī)劃6-4第31頁第31頁目的4性能指標(biāo)目的值新方案總運(yùn)費(fèi)不超出原方案10%目的5因道路限制,從工廠2到用戶4路線應(yīng)盡也許避免運(yùn)輸任務(wù)目的6用戶1和用戶3需求量滿足率盡也許保持平衡1234產(chǎn)量130022003400銷量200100450250多目的規(guī)劃6-4第32頁第32頁目的7性能指標(biāo)目的值1234產(chǎn)量130022003400銷量200100450250力爭減少新方案總費(fèi)用多目的規(guī)劃6-4第33頁第33頁性能指標(biāo)目的值目的2目的1目的3目的5目的6目的7目的4多目的規(guī)劃6-4第34頁第34頁目的7性能指標(biāo)目的值1234產(chǎn)量130022003400銷量200100450250力爭減少新方案總費(fèi)