運(yùn)籌學(xué)概論 第4章 目標(biāo)規(guī)劃ppt課件

1、第第4章章 目的規(guī)劃目的規(guī)劃 n目的規(guī)劃問題的提出目的規(guī)劃問題的提出 n目的規(guī)劃數(shù)學(xué)模型目的規(guī)劃數(shù)學(xué)模型n目的規(guī)劃的圖解法目的規(guī)劃的圖解法 (1) (1)線性規(guī)劃是單目的最優(yōu)化問題線性規(guī)劃是單目的最優(yōu)化問題 (2)(2)線性規(guī)劃有最優(yōu)解的必要條件是其可行解集非空，線性規(guī)劃有最優(yōu)解的必要條件是其可行解集非空，即各約束條件彼此相容即各約束條件彼此相容 (3)(3)線性規(guī)劃數(shù)學(xué)模型是相對于實(shí)踐問題的近似線性規(guī)劃數(shù)學(xué)模型是相對于實(shí)踐問題的近似 1.線性規(guī)劃問題的局限性一、目的規(guī)劃問題的提出一、目的規(guī)劃問題的提出 例例1 1 某工廠消費(fèi)兩種產(chǎn)品，遭到原資料供應(yīng)和設(shè)備工時的某工廠消費(fèi)兩種產(chǎn)品，遭到原資料供

2、應(yīng)和設(shè)備工時的限制。在單件利潤等有關(guān)數(shù)據(jù)知的條件下，要求制定一個限制。在單件利潤等有關(guān)數(shù)據(jù)知的條件下，要求制定一個獲利最大的消費(fèi)方案。詳細(xì)數(shù)據(jù)見表。獲利最大的消費(fèi)方案。詳細(xì)數(shù)據(jù)見表。產(chǎn)品產(chǎn)品限量限量原資料原資料kg/件件51060設(shè)備工時設(shè)備工時h/件件4440利潤元利潤元/件件682186maxxxz0,404460105212121xxxxxx最優(yōu)消費(fèi)方案為最優(yōu)消費(fèi)方案為x1x18 8件，件，x2x22 2件，件，max zmax z6464元。元。2. 目的規(guī)劃問題的提出 在處置實(shí)踐問題時，線性規(guī)劃存在著由其在處置實(shí)踐問題時，線性規(guī)劃存在著由其“剛性本剛性本質(zhì)所注定的某些固有的局限性質(zhì)所

3、注定的某些固有的局限性(目的獨(dú)一、能夠域?yàn)榭?、目的?dú)一、能夠域?yàn)榭铡⒔菩越菩??，F(xiàn)代決策強(qiáng)調(diào)定量分析和定性分析相結(jié)合。線?，F(xiàn)代決策強(qiáng)調(diào)定量分析和定性分析相結(jié)合。線性規(guī)劃無法勝任這樣的要求。性規(guī)劃無法勝任這樣的要求。 1961年，查恩斯年，查恩斯(A.Charnes)和庫柏和庫柏(W.W.Cooper)提出目的規(guī)劃提出目的規(guī)劃(goal programming)。在處置實(shí)踐決策問。在處置實(shí)踐決策問題時，成認(rèn)各項(xiàng)決策要求題時，成認(rèn)各項(xiàng)決策要求(即使是沖突的即使是沖突的)的存在有其合理的存在有其合理性；在作最終決策時，不強(qiáng)調(diào)其絕對意義上的最優(yōu)性。目性；在作最終決策時，不強(qiáng)調(diào)其絕對意義上的最優(yōu)性。

4、目的規(guī)劃被以為是一種較之線性規(guī)劃更接近于實(shí)踐決策過程的規(guī)劃被以為是一種較之線性規(guī)劃更接近于實(shí)踐決策過程的決策工具。的決策工具。例例2 2 假設(shè)在例假設(shè)在例 l l 的根底上，要求思索如下意見：的根底上，要求思索如下意見： (1) (1)由于產(chǎn)品由于產(chǎn)品銷售疲軟，故希望產(chǎn)品銷售疲軟，故希望產(chǎn)品的產(chǎn)量不超越產(chǎn)品的產(chǎn)量不超越產(chǎn)品I I的一半；的一半； (2) (2)原資料嚴(yán)重短缺，消費(fèi)中應(yīng)防止過量耗費(fèi)；原資料嚴(yán)重短缺，消費(fèi)中應(yīng)防止過量耗費(fèi)； (3) (3)最好能節(jié)約最好能節(jié)約4 4小時設(shè)備工時；小時設(shè)備工時； (4) (4)方案利潤不少于方案利潤不少于4848元。元。4886440446010502

5、12186max212121221221xxxxxxxxxxxx 面對這些意見，方案人員需求會同有關(guān)各方作進(jìn)一步的協(xié)調(diào)，最后達(dá)面對這些意見，方案人員需求會同有關(guān)各方作進(jìn)一步的協(xié)調(diào)，最后達(dá)成了一致意見：原資料運(yùn)用限額不得突破；產(chǎn)品成了一致意見：原資料運(yùn)用限額不得突破；產(chǎn)品產(chǎn)量要求必需優(yōu)先思索；產(chǎn)量要求必需優(yōu)先思索；設(shè)備工時問題其次思索；最后思索方案利潤的要求。設(shè)備工時問題其次思索；最后思索方案利潤的要求。 類似這樣的多目的決策問題是典型的目的規(guī)劃問題。類似這樣的多目的決策問題是典型的目的規(guī)劃問題。 332211,mindPdPdP3 , 2 , 10,4886364402601052133212

6、221112121iddxxddxxddxxddxxxxii線性規(guī)劃線性規(guī)劃目的規(guī)劃目的規(guī)劃 3.目的規(guī)劃與線性規(guī)劃相比的優(yōu)點(diǎn) 1 1線性規(guī)劃只能處置一個目的，而現(xiàn)實(shí)問題往往要線性規(guī)劃只能處置一個目的，而現(xiàn)實(shí)問題往往要處置多個目的。目的規(guī)劃就能統(tǒng)籌兼顧地處置多個目的的處置多個目的。目的規(guī)劃就能統(tǒng)籌兼顧地處置多個目的的關(guān)系，求得更切合實(shí)踐要求的解。關(guān)系，求得更切合實(shí)踐要求的解。 2 2線性規(guī)劃立足于求滿足一切約束條件的最優(yōu)解，線性規(guī)劃立足于求滿足一切約束條件的最優(yōu)解，而在實(shí)踐問題中，能夠存在相互矛盾的約束條件。目的規(guī)而在實(shí)踐問題中，能夠存在相互矛盾的約束條件。目的規(guī)劃可以在相互矛盾的約束條件下找

7、到稱心解。劃可以在相互矛盾的約束條件下找到稱心解。 3 3目的規(guī)劃的最優(yōu)解指的是盡能夠地到達(dá)或接近一目的規(guī)劃的最優(yōu)解指的是盡能夠地到達(dá)或接近一個或假設(shè)干個已給定的目的值。個或假設(shè)干個已給定的目的值。 4 4線性規(guī)劃的約束條件是不分主次地同等對待，而線性規(guī)劃的約束條件是不分主次地同等對待，而目的規(guī)劃可根據(jù)實(shí)踐的需求給予輕重緩急的思索。目的規(guī)劃可根據(jù)實(shí)踐的需求給予輕重緩急的思索。二、目的規(guī)劃的數(shù)學(xué)模型二、目的規(guī)劃的數(shù)學(xué)模型1偏向變量偏向變量 對每一個決策目的，引入正、負(fù)偏向變量對每一個決策目的，引入正、負(fù)偏向變量d+和和d，分別表，分別表示決策值超越或缺乏目的值的部分。按定義應(yīng)有示決策值超越或缺乏

8、目的值的部分。按定義應(yīng)有d+0，d0，d+d0。2 2絕對約束和目的約束絕對約束和目的約束 絕對約束是指必需嚴(yán)厲滿足的約束條件，如線性規(guī)劃中的絕對約束是指必需嚴(yán)厲滿足的約束條件，如線性規(guī)劃中的約束條件都是絕對約束。絕對約束是硬約束，對它的滿足與約束條件都是絕對約束。絕對約束是硬約束，對它的滿足與否，決議了解的可行性。否，決議了解的可行性。 目的約束是目的規(guī)劃特有的概念，是一種軟約束，目的約目的約束是目的規(guī)劃特有的概念，是一種軟約束，目的約束中決策值和目的值之間的差別用偏向變量表示。束中決策值和目的值之間的差別用偏向變量表示。 3 3優(yōu)先因子和權(quán)系數(shù)優(yōu)先因子和權(quán)系數(shù) 不同目的的主次輕重有兩種差別

9、。一種差別是絕對的，不同目的的主次輕重有兩種差別。一種差別是絕對的，可用優(yōu)先因子可用優(yōu)先因子 來表示。只需在高級優(yōu)先因子對應(yīng)的目的已來表示。只需在高級優(yōu)先因子對應(yīng)的目的已滿足的根底上，才干思索較低級優(yōu)先因子對應(yīng)的目的；在思滿足的根底上，才干思索較低級優(yōu)先因子對應(yīng)的目的；在思索低級優(yōu)先因子對應(yīng)的目的時，絕不允許違背已滿足的高級索低級優(yōu)先因子對應(yīng)的目的時，絕不允許違背已滿足的高級優(yōu)先因子對應(yīng)的目的。優(yōu)先因子間的關(guān)系為優(yōu)先因子對應(yīng)的目的。優(yōu)先因子間的關(guān)系為 ，即，即對應(yīng)的目的比對應(yīng)的目的比 對應(yīng)的目的有絕對的優(yōu)先性。對應(yīng)的目的有絕對的優(yōu)先性。 另一種差別是相對的，這些目的具有一樣的優(yōu)先因子另一種差別

10、是相對的，這些目的具有一樣的優(yōu)先因子, ,它們的重要程度可用權(quán)系數(shù)的不同來表示。它們的重要程度可用權(quán)系數(shù)的不同來表示。 lPlPlP1lP1lP 4 4目的規(guī)劃的目的函數(shù)目的規(guī)劃的目的函數(shù) 目的規(guī)劃的目的函數(shù)由各目的約束的偏向變量及相應(yīng)的目的規(guī)劃的目的函數(shù)由各目的約束的偏向變量及相應(yīng)的優(yōu)先因子和權(quán)系數(shù)構(gòu)成。由于目的規(guī)劃追求的是盡能夠接優(yōu)先因子和權(quán)系數(shù)構(gòu)成。由于目的規(guī)劃追求的是盡能夠接近各既定目的值近各既定目的值, ,也就是使各有關(guān)偏向變量盡能夠小，所也就是使各有關(guān)偏向變量盡能夠小，所以其目的函數(shù)只能是極小化。以其目的函數(shù)只能是極小化。 有三種根本表達(dá)式：有三種根本表達(dá)式： 要求恰好到達(dá)目的值。

11、這時，決策值超要求恰好到達(dá)目的值。這時，決策值超越或缺乏目的值都是不希望的，因此有：越或缺乏目的值都是不希望的，因此有： 要求不超越目的值，但允許缺乏目的值。這時，不希望要求不超越目的值，但允許缺乏目的值。這時，不希望決策值超越目的值，因此有：決策值超越目的值，因此有： )(min ddf)(mindf 要求不低于目的值，但允許超越目的值。這時，不希要求不低于目的值，但允許超越目的值。這時，不希望決策值低于目的值，因此有：望決策值低于目的值，因此有： )(mindf例例2 (1)2 (1)產(chǎn)品產(chǎn)品的產(chǎn)量不超越產(chǎn)品的產(chǎn)量不超越產(chǎn)品I I的一半；的一半； (2) (2)原資料嚴(yán)重短缺，消費(fèi)中應(yīng)防止

12、過量耗費(fèi)；原資料嚴(yán)重短缺，消費(fèi)中應(yīng)防止過量耗費(fèi)； (3) (3)最好能節(jié)約最好能節(jié)約4 4小時設(shè)備工時；小時設(shè)備工時； (4) (4)方案利潤不少于方案利潤不少于4848元。元。一致意見：一致意見：1.1.原資料運(yùn)用限額不得突破；原資料運(yùn)用限額不得突破；2.2.產(chǎn)品產(chǎn)品產(chǎn)量要求必需優(yōu)先思索；產(chǎn)量要求必需優(yōu)先思索；3.3.設(shè)備工時問題其次思索；設(shè)備工時問題其次思索；4.4.最后思索方案利潤的要求。最后思索方案利潤的要求。332211,mindPdPdP3 , 2 , 10,)1 . 6(4886)1 . 6(3644)1 . 6(02)1 . 6(601052133212221112121idd

13、xxdddxxcddxxbddxxaxxii產(chǎn)品限量原資料kg/件51060設(shè)備工時h/件4440利潤元/件68目的規(guī)劃數(shù)學(xué)模型的普通方式為目的規(guī)劃數(shù)學(xué)模型的普通方式為 ： 模型中模型中g(shù)kgk為第為第k k個目的約束的預(yù)期目的值，個目的約束的預(yù)期目的值， 和和 為為 優(yōu)先因優(yōu)先因子對應(yīng)各目的的權(quán)系數(shù)。子對應(yīng)各目的的權(quán)系數(shù)。 在建立目的規(guī)劃數(shù)學(xué)模型時，需求確定預(yù)期目的值、優(yōu)先級和權(quán)在建立目的規(guī)劃數(shù)學(xué)模型時，需求確定預(yù)期目的值、優(yōu)先級和權(quán)系數(shù)等，該當(dāng)綜合運(yùn)用各種決策技術(shù)系數(shù)等，該當(dāng)綜合運(yùn)用各種決策技術(shù), ,盡能夠地減少客觀片面性。盡能夠地減少客觀片面性。 LldWdWPkkklkklkl,2,1

14、,)(min1KkddnjxmibxaKkgddxckkjnjijijnjkkkjkj,2, 10,2, 10,2, 1),(,2, 111lkWlkWlPn習(xí)題習(xí)題:n1、公司決議運(yùn)用、公司決議運(yùn)用1000萬元新產(chǎn)品開發(fā)基金開發(fā)萬元新產(chǎn)品開發(fā)基金開發(fā)A，B，C三種新產(chǎn)品，對應(yīng)的投資利潤率分別為三種新產(chǎn)品，對應(yīng)的投資利潤率分別為5%、7%和和10%。公司制定如下的優(yōu)先順序目的：公司制定如下的優(yōu)先順序目的：n 第一，第一，A產(chǎn)品至少投資產(chǎn)品至少投資300萬元；萬元；n 第二，為分散投資風(fēng)險(xiǎn)，任何一種新產(chǎn)品的開發(fā)投資第二，為分散投資風(fēng)險(xiǎn)，任何一種新產(chǎn)品的開發(fā)投資不超越開發(fā)基金總額的不超越開發(fā)基金總

15、額的35%；n 第三，應(yīng)至少留有第三，應(yīng)至少留有10%的開發(fā)基金，以備急用；的開發(fā)基金，以備急用；n 第四，使總的投資利潤最大。第四，使總的投資利潤最大。n建立投資分配方案的目的規(guī)劃模型。建立投資分配方案的目的規(guī)劃模型。n2、某彩色電視機(jī)組裝工廠，消費(fèi)、某彩色電視機(jī)組裝工廠，消費(fèi)A、B、C三種規(guī)格電視三種規(guī)格電視機(jī)。裝配任務(wù)在同一消費(fèi)線上完成，三種產(chǎn)品每件裝配時機(jī)。裝配任務(wù)在同一消費(fèi)線上完成，三種產(chǎn)品每件裝配時的工時耗費(fèi)分別為的工時耗費(fèi)分別為6小時、小時、8小時和小時和10小時，消費(fèi)線每月小時，消費(fèi)線每月正常任務(wù)時間為正常任務(wù)時間為200小時；三種規(guī)格電視機(jī)銷售后，每臺小時；三種規(guī)格電視機(jī)銷售

16、后，每臺可獲利分別為可獲利分別為500元、元、650元和元和800元。每月銷量估計(jì)分別元。每月銷量估計(jì)分別為為12臺、臺、10臺和臺和6臺。該廠運(yùn)營目的如下：臺。該廠運(yùn)營目的如下：nP1：利潤目的定為至少每月：利潤目的定為至少每月1.6104元；元；nP2：充分利用消費(fèi)才干；：充分利用消費(fèi)才干；nP3：加班時間不超越：加班時間不超越24小時；小時；nP4：產(chǎn)量恰好可以滿足估計(jì)銷量；：產(chǎn)量恰好可以滿足估計(jì)銷量；n為確定消費(fèi)方案，試建立該問題的目的規(guī)劃模型為確定消費(fèi)方案，試建立該問題的目的規(guī)劃模型 三、目的規(guī)劃的圖解法三、目的規(guī)劃的圖解法 只需兩個決策變量的目的規(guī)劃問題可以用圖解方法來求解。只需兩

17、個決策變量的目的規(guī)劃問題可以用圖解方法來求解。 在用圖解法解目的規(guī)劃時，首先必需滿足一切絕對約束。在在用圖解法解目的規(guī)劃時，首先必需滿足一切絕對約束。在此根底上，再按照優(yōu)先級從高到低的順序，逐個地思索各個此根底上，再按照優(yōu)先級從高到低的順序，逐個地思索各個目的約束。普通地，假設(shè)優(yōu)先因子目的約束。普通地，假設(shè)優(yōu)先因子Pj對應(yīng)的解空間為對應(yīng)的解空間為Rj，那，那么優(yōu)先因子么優(yōu)先因子Pj+1對應(yīng)的解空間只能在對應(yīng)的解空間只能在Rj中思索。即中思索。即 :jjRR1 假設(shè)假設(shè)Rj，而，而Rj+1=，那么，那么Rj中的解為目的規(guī)劃的稱中的解為目的規(guī)劃的稱心解，它只能保證滿足心解，它只能保證滿足P1，P2

18、，Pj級目的。而不保證級目的。而不保證滿足其后的各級目的。滿足其后的各級目的。例例3 3 用圖解法解例用圖解法解例2 2的目的規(guī)劃模型。的目的規(guī)劃模型。解：解題過程見圖解：解題過程見圖6-l6-l。 F D d3 d1 d2+ x2 x1 12 9 8 0 6 9 E C 3 , 2 , 10,4886364402601052133212221112121iddxxddxxddxxddxxxxii332211,mindPdPdPAB圖圖6-16-1中，中，OABOAB區(qū)域是滿足絕對約區(qū)域是滿足絕對約束束(6.1a)(6.1a)和非負(fù)條件的解空間。對和非負(fù)條件的解空間。對于一切目的約束，去掉偏向

19、變量，于一切目的約束，去掉偏向變量，畫出相應(yīng)直線，然后標(biāo)出偏向變量畫出相應(yīng)直線，然后標(biāo)出偏向變量變化時直線平移方向變化時直線平移方向 。 按優(yōu)先級高低，首先思索按優(yōu)先級高低，首先思索p1p1，此時要求，此時要求 ，因此，因此解空間解空間R1R1為為OACOAC區(qū)域；再思索區(qū)域；再思索P2P2，此時要求，此時要求 ，因此，因此解空間解空間R2R2為為ODCODC區(qū)域；最后思索區(qū)域；最后思索P3P3，此時要求，此時要求 ，因，因此解空間此解空間R3R3為四邊形為四邊形EDCFEDCF區(qū)域。容易求得區(qū)域。容易求得E E，D D，C C，F(xiàn) F四點(diǎn)的四點(diǎn)的坐標(biāo)分別為坐標(biāo)分別為(8,0)(8,0)、(9

20、,0)(9,0)、(6,3)(6,3)、(4.8,2.4)(4.8,2.4)，故問題的解，故問題的解可表示為可表示為 ：1mind1mind3mind)4 . 23 ,8 . 4698()4 . 2 , 8 . 4()3 , 6()0 , 9()0 , 8(4343214321其中：其中：0,432114321 此題解能滿足式此題解能滿足式6.16.1的一切目的的要求，即能使的一切目的的要求，即能使min min z=0z=0，這種情況并不總是出現(xiàn)，即很多目的規(guī)劃問題只能滿，這種情況并不總是出現(xiàn)，即很多目的規(guī)劃問題只能滿足前面足前面PjPj級目的的要求。見下一個例子。級目的的要求。見下一個例子

21、。 例例4 4 用圖解法解下面的目的規(guī)劃。用圖解法解下面的目的規(guī)劃。 144332211),35(,mindPddPdPdP4 , 3 , 2 , 10,242926221442332122211121iddxxddxddxxddxxddxxii d2+ d4 d3 d1 d1+ F A B E G C D 6 9 0 3 4.5 x1 x2 圖 6-2 4 , 3 , 2 , 10,2429262),35(,min21442332122211121144332211iddxxddxddxxddxxddxxdPddPdPdPii從圖從圖6-26-2可見，在思索可見，在思索P1P1和和P2P2的

22、目的后，解的目的后，解空間空間R2R2為四邊形為四邊形ABCDABCD區(qū)域。在思索區(qū)域。在思索P3P3的目的的目的時，由于時，由于 的權(quán)系數(shù)比的權(quán)系數(shù)比 的大，所以先的大，所以先思索思索 。此時，。此時，x1x1和和x2x2的取值范圍減的取值范圍減少為四邊形少為四邊形ABEFABEF區(qū)域；然后思索區(qū)域；然后思索 。但在四邊形但在四邊形ABEFABEF區(qū)域內(nèi)無法滿足區(qū)域內(nèi)無法滿足 0 0，所以，只能退一步，要求在四邊形區(qū)域所以，只能退一步，要求在四邊形區(qū)域ABEFABEF中找一點(diǎn)，使中找一點(diǎn)，使 盡能夠小，這一點(diǎn)就是點(diǎn)盡能夠小，這一點(diǎn)就是點(diǎn)E(6.5,1.25)E(6.5,1.25)。所以，問題的稱心解為。所以，問題的稱心解為x1x16.56.5，x2x21.251.25。 4d