7運籌學之目標規(guī)劃(胡運權(quán)版)

1、第七章目標規(guī)劃§1目標規(guī)劃的提由線性規(guī)劃問題是討論一個給定的線性目標函數(shù)在一組線性約束條件下的最大值或最小值問題。對于一個實際問題， 管理科學者根據(jù)管理層決策目標的要求，首先確定一個目標函數(shù)以衡量不同決策的優(yōu)劣，且根據(jù)實際問題中的資源、資金和環(huán)境等因素對決策的限制提出相應的約束條件以建立線性規(guī)劃模型；然后用計算機軟件求出最優(yōu)方案并作靈敏度分析以供管理層決策之用。而在一些問題中，決策目標往往不只一個，且模型中有可能存在一些互相矛盾的約束條件的情況，用已有的線性規(guī)劃的理論和方法無法解決這些問題。因此，1961年美國學者查恩斯(A.Charnes)和庫柏(W.W.Coopor)提出了目標規(guī)

2、劃的概念與數(shù)學模型， 以解決經(jīng)濟管理中的多目標決策問題。我們將通過幾個例子來說明在實際應用中線性規(guī)劃存在一系列的局限性。例1某廠生產(chǎn)A、B兩種產(chǎn)品每件所需的勞動力分別為4個人工和6個人工，所需設備的單位臺時均為1。已知該廠有10個單位機器臺時提供制造這兩種產(chǎn)品，并且至少能提供70個人工。又，A、B產(chǎn)品的利潤，每件分別為300元和500元。試問：該廠各應生產(chǎn)多少件A、B產(chǎn)品，才能使其利潤值最大？解 設該廠能生產(chǎn) A、B產(chǎn)品的數(shù)量分別為 x1,x2件，則有max z 300x1 500x2 x1 x2 10st 4x1 6x2 70X 0, j 1.2.圖解法求解如下：玉+西=10由上圖可得，滿足

3、約束條件的可行解集為，即機時約束和人工約束之間產(chǎn)生矛盾，因而該問題無解。但在實際中，該廠要增加利潤，不可能不生產(chǎn)A、B兩種產(chǎn)品，而由線性規(guī)劃模型無法為其找到一個合適的方案。例2某廠為進行生產(chǎn)需采購 A、B兩種原材料，單價分別為 70元/公斤和50元/公斤。現(xiàn) 要求購買資金不超過 5000元，總購買量不少于 80公斤，而A原材料不少于20公斤。問如何確定最好的采購方案（即花掉的資金最少，購買的總量最大）？解 這是一個含有兩個目標的數(shù)學規(guī)劃問題。設x1, x2 分別為購買兩種原材料的公斤數(shù)，f1 x1 ,x2 為花掉的資金，f2 x1 ,x2 為購買的總量。建立該問題的數(shù)學模型形式如下：min f

4、1 x1, x270x1 50x2max f2 x1 ,x2x1x21570x1 50x2 5000s.t.x1 x2 80x1 20x1, x2 0對于這樣的多目標問題，線性規(guī)劃很難為其找到最優(yōu)方案。極可能的結(jié)果是，第一個方案使第一目標的結(jié)果值優(yōu)于第二方案，同時第二方案使第二目標的結(jié)果值優(yōu)于第一方案。也就是說很難找到一個最優(yōu)方案，使兩個目標的函數(shù)值同時達到最優(yōu)。另外， 對于多目標問題，還存在有多個目標存在有不同重要程度的因素，而這也是線性規(guī)劃所無法解決的。在線性規(guī)劃的基礎上，建立了一種新的數(shù)學規(guī)劃方法目標規(guī)劃法，用于彌補線性規(guī)劃的上述局限性?？偟膩碚f，目標規(guī)劃和線性規(guī)劃的不同之處可以從以下幾

5、點反映出來：1、線性規(guī)劃只能處理一個目標，而現(xiàn)實問題往往存在多個目標。目標規(guī)劃能統(tǒng)籌兼顧地處理多個目標的關系，求得切合實際需求的解。2、線性規(guī)劃是求滿足所有約束條件的最優(yōu)解。而在實際問題中，可能存在相互矛盾的約束條件而導致無可行解，但此時生產(chǎn)還得繼續(xù)進行。即使存在可行解，實際問題中也未必一定需要求出最優(yōu)解。目標規(guī)劃是要找一個滿意解，即使在相互矛盾的約束條件下也找到盡量滿足約束的滿意解，即滿意方案。3、線性規(guī)劃的約束條件是不分主次地等同對待，這也并不都符合實際情況。而目標規(guī)劃可根據(jù)實際需要給予輕重緩急的考慮。2 目標規(guī)劃的基本概念與數(shù)學模型2.1 基本概念在這一小節(jié)里介紹與目標規(guī)劃有關的基本概念

6、。1 偏差變量對于例 1，造成無解的關鍵在于約束條件太死板。設想把約束條件“放松”，比如占用的人力可以少于70 人的話，機時約束和人工約束就可以不再發(fā)生矛盾。在此基礎上，引入了正負偏差的概念，來表示決策值與目標值之間的差異。di 正偏差變量，表示決策值超出目標值的部分，目標規(guī)劃里規(guī)定 di 0；di 負偏差變量，表示決策值未達到目標值的部分，目標規(guī)劃里規(guī)定 di 0。實際操作中，當目標值（也就是計劃的利潤值）確定時，所作的決策可能出現(xiàn)以下三種情況之一：（ 1） 決策值超過了目標值（即完成或超額完成計劃利潤值）， 表示為 d i 0 ， di 0 ；（ 2）決策值未達到目標值（即未完成計劃利潤值

7、），表示為di0 ， di 0 ；（ 3）決策值恰好等于目標值（即恰好完成計劃利潤指標），表示為di0， di 0。以上三種情況，無論哪種情況發(fā)生，均有di ? di =0。2絕對約束與目標約束絕對約束也稱系統(tǒng)約束，是指必須嚴格滿足的等式約束和不等式約束，它對應于線性規(guī)劃模型中的約束條件。目標約束是目標規(guī)劃所特有的。當確定了目標值，進行決策時，允許與目標值存在正或負的偏差。因而目標約束中加入了正、負偏差變量。如，例 1 中假定該企業(yè)計劃利潤值為5000 元，那么對于目標函數(shù)maxz 300x1 500 x2 ，可變換為300x1 500x2 di di5000 。該式表示決策值與目標值5000

8、 之間可能存在正或負的偏差（請讀者分別按照上面所講的三種情況來理解）。絕對約束也可根據(jù)問題的需要變換為目標約束。此時將約束右端項看作所追求的目標值。如，例1 中絕對約束x1 x2 10，可變換為目標約束x1 x2 didi10 。3目標規(guī)劃的目標函數(shù)對于滿足絕對約束與目標約束的所有解，從決策者的角度來看，判斷其優(yōu)劣的依據(jù)是決策值與目標值的偏差越小越好。因此目標規(guī)劃的目標函數(shù)是與正、負偏差變量密切相關的函數(shù)，我們表示為min z f di ,di 。它有如下三種基本形式：（ 1）要求恰好達到目標值，即正、負偏差變量都盡可能地小。此時，構(gòu)造目標函數(shù)為： min z didi（ 2）要求不超過目標值

9、，即允許達不到目標值，正偏差變量盡可能地小。此時構(gòu)造目標函數(shù)為：min z di（ 3）求超過目標值，即超過量不限，負偏差變量盡可能地小。此時構(gòu)造目標函數(shù)為： min z di4優(yōu)先次序系數(shù)與權(quán)系數(shù)一個規(guī)劃問題往往有多個目標。決策者在實現(xiàn)這些目標時，存在有主次與輕重緩急的M 系數(shù)：M1 , M2 ,不同。又于有 K級目標的問題，按照優(yōu)先次序分別賦予不同大小的大，Mk。Mi , M2 ,，M k為無窮大的正數(shù)，并且， MiM2Mk ： 符號表示“遠大于”），這樣，只有當某一級目標實現(xiàn)以后 （即目標值為0），才能忽略大 M 的影響，否則目標偏離量會因為大 M的原因而無窮放大。 并且由于M kM k

10、 1 ,所以只有 先考慮忽略Mk影響（實現(xiàn)第k級目標）后，才能考慮第 k 1級目標。實際上這里的大 M 是對偏離目標值的懲罰系數(shù)，優(yōu)先級別越高，懲罰系數(shù)越大。權(quán)系數(shù)i用來區(qū)別具有相同優(yōu)先級別的若干目標。在同一優(yōu)先級別中，可能包含有兩個或多個目標，它們的正負偏差變量的重要程度有差別，此時可以給正負偏差變量賦予不同 的權(quán)系數(shù)i和i。各級目標的優(yōu)先次序及權(quán)系數(shù)的確定由決策者按具體情況給出。§ 2.2目標規(guī)劃的數(shù)學模型綜上所述，目標規(guī)劃模型由目標函數(shù)、目標約束、絕對約束以及變量非負約束等幾部 分構(gòu)成。目標規(guī)劃的一般數(shù)學模型為：目標函數(shù)min ZKLM kkdkdk 1l 1目標約束nGjXj

11、 j idi di gil 1,2,| L絕對約束naijxj j 1,b i 1,2,| m非負約束xj0j 1,2，|ndk 40 k 1,2,|,K例3在例1中，假定目標利潤不少于15000元，為第一目標；占用的人力可以少于70人,為第二目標。求決策方案。解 按決策者的要求分別賦予兩個目標大M系數(shù)M1,M 2o列出模型如下：min z M1d1M2d2300x 500x2 d1 d1150004x1 6x2 d2 d270s.tx1 x2 10x1,x2,di ,di0 i 1,2,3.例4某紡織廠生產(chǎn) A、B兩種布料，平均生產(chǎn)能力均為1千米/小時，工廠正常生產(chǎn)能力是80小時/周。又A布

12、料每千米獲利 2500元，B布料每千米獲利 1500元。已知A、B兩種布 料每周的市場需求量分別是 70千米和45千米。現(xiàn)該廠確定一周內(nèi)的目標為：第一優(yōu)先級：避免生產(chǎn)開工不足；第二優(yōu)先級：加班時間不超過10小時；第三優(yōu)先級：根據(jù)市場需求達到最大銷售量；第四優(yōu)先級：盡可能減少加班時間。試求該問題的最優(yōu)方案。解 設x1,x2分別為生產(chǎn)甲、乙布料的小時數(shù)。對于第三優(yōu)先級目標，根據(jù) A、B布料利潤的比值2500:1500 5:3 ,取二者達到最大銷量的權(quán)系數(shù)分別為5和3。該問題的目標規(guī)劃模型為：min z M 1d1M 2d2 M3 5d3 3d4M 4d1x1 x2 d1 d180x1 x2 d2

13、d290s.tx1 d3 d3 70x2 d4 d445x1,x2,di ,di 0綜上所述，目標規(guī)劃建立模型的步驟為：1、根據(jù)問題所提出的各目標與條件，確定目標值，列出目標約束與絕對約束；2、根據(jù)決策者的需要將某些或全部絕對約束轉(zhuǎn)換為目標約束，方法是絕對約束的左式 加上負偏差變量和減去正偏差變量；3、給各級目標賦予相應的懲罰系數(shù)Mk (k 1,2,|K ), Mk為無窮大的正數(shù)，且M1M2M k ;4、對同一優(yōu)先級的各目標，再按其重要程度不同，賦予相應的權(quán)系數(shù)h；5、根據(jù)決策者的要求，各目標按三種情況取值：恰好達到目標值，取di di允許超過目標值，取di不允許超過目標值，取 di ;然后構(gòu)

14、造一個由懲罰系數(shù)、權(quán)系數(shù)和偏差變量組成的、要求實現(xiàn)極小化的目標函數(shù)。§ 3目標規(guī)劃的求解3. 1圖解法只有兩個決策變量的目標規(guī)劃數(shù)學模型，可以使用簡單直觀的圖解法求解。其方法與線性規(guī)劃圖解法類似， 先在平面直角坐標系第一象限內(nèi)作出各約束等式或不等式的圖象，然后由絕對約束確定了可行域，由目標約束和目標函數(shù)確定最優(yōu)解或滿意解。對于絕對約束，與線性規(guī)劃中的約束條件畫法完全相同。對于目標約束方程，除作出直線外，還要在直線上要標出正負偏差變量的方向，其可行域方向取決于目標函數(shù)中對應目標。另外，目標規(guī)劃是在前一級目標滿足的情況下再來考慮下一級目標，很有可能盡可能滿足目標的解不是可行解（即非可行解

15、）,而是權(quán)衡以后得出的最優(yōu)解一一滿意解。因而在目標規(guī)劃里稱求得的解為滿意解。注意在求解的時候，把絕對約束作最高級別考慮。例5用圖解法求解目標規(guī)劃問題min z M 1d1d1M 2d2 M 3d3x1 x2 d1d103x15x2d2d215s.t4x13x2d3d324x1 x2 7x1,x2,di ,di0 i 1,2,3.解 在平面直角坐標系第一象限內(nèi)作出各約束條件的圖像，目標約束要在直線旁標上di和 di+。首先，絕對約束x1 x2 7確定了可行解范圍在三角形 OEF內(nèi);根據(jù)第一級目標，要求實現(xiàn)min d1d1(恰好)，因而可行解范圍縮小到線段OC上；根據(jù)第二級目標，要求實現(xiàn)mind?

16、(不少于)，在線段 OC上，取d2 0的點A,此時可行解范圍縮小到線段 AC上；根據(jù)第三級目標，要求實現(xiàn)min d3 ,在線段AC上，取d30的點B,此時解的范圍縮小到線段AB上。所以，線段AB上的所有點為滿意解。可求得 A(15/8,15/8) , B(24/7,24/7)。例6用圖解法求解 例4的目標規(guī)劃模型。解在平面直角坐標系第一象限內(nèi)作出各約束條件對應的圖象，并在目標約束直線旁標上di 和 di目標函數(shù)要求實現(xiàn)min di ,解的范圍是線段 AC的右上方區(qū)域;根據(jù)第一級目標,根據(jù)第二級目標,目標函數(shù)要求實現(xiàn) min d2 ,解的范圍縮小到四邊形 ABDC內(nèi)的區(qū)域;根據(jù)第三級目標，目標函

17、數(shù)要求實現(xiàn)min 5d3 3d4 ,先考慮min 5d3 ,解的范圍縮 小為四邊形 ABFE內(nèi)的區(qū)域，再考慮 min 3d4 ,四邊形 ABFE內(nèi)的所有點，均無法滿足d4 0,此時在可行域 ABFE內(nèi)考慮使d4達到最小的滿意點 F, F點不滿足d4 0,但它是使第三級目標最滿意的滿意解；根據(jù)第四級目標，目標函數(shù)要求實現(xiàn)mind1 ,由于解的范圍已經(jīng)縮小到點F,所以唯一的點F也是使第四級目標最滿意的滿意解。綜上所述，該問題的滿意解為點F,可求得F(70,20)。給出圖解法求解步驟如下：1、在直角坐標系的第一象限作出絕對約束和目標約束的圖象，絕對約束確定出可行解的區(qū)域，在目標約束直線上用箭頭標出正

18、負偏差變量值增大的方向(正、 負偏差變量增大的方向相反)；2. 在可行解的區(qū)域內(nèi)，求滿足最高優(yōu)先等級目標的解；3、轉(zhuǎn)到下一個優(yōu)先等級的目標，在滿足上一優(yōu)先等級目標的前提下，求出滿足該等級目標的解；4、重復3，直到所有優(yōu)先等級目標都審查完畢；5、確定最優(yōu)解或滿意解。3. 2 單純形法目標規(guī)劃是線性規(guī)劃的推廣與發(fā)展，其數(shù)學模型結(jié)構(gòu)與線性規(guī)劃的數(shù)學模型結(jié)構(gòu)沒有本質(zhì)的區(qū)別，求解線性規(guī)劃的單純形法，同樣也是目標規(guī)劃的求解方法。在目標規(guī)劃里加入了大 M 懲罰系數(shù)，可用大M 法來進行求解。這里不再舉例。用單純形法求解目標規(guī)劃，迭代結(jié)束有兩種情況。一種所有檢驗數(shù)均已非負時，所獲得的解使所有目標偏離量為0，此解

19、為最優(yōu)解。另一種情況是所有檢驗數(shù)均已非負時，并沒有使所有目標達到最優(yōu)值，但達到最優(yōu)的目標值一定是優(yōu)先等級排在前面的，此時獲得的解為滿意解。如 例4用單純形法求的滿意解為70,20 T,目標值為z 75M3 10M4 ,可以看到求得的解并沒有使第三級和第四級目標達到最優(yōu)，但已使第一、二級目標達到最優(yōu)，這和前面用圖解法求得的結(jié)果一致。4. 3 EXCEL 電子表格法目標規(guī)劃同樣能由EXCEL 求得其滿意解。關鍵在于如何建立電子表格模型。例 7 用 EXCEL 求解 例 4的目標規(guī)劃模型。解 我們來看一下如何為例4 中的目標規(guī)劃問題建立電子表格模型，見圖7-4?？贗S二 SUMP 閱 DUCT 胱:

20、快 B9：C9)二D5寸品展6= SWJWDUCT(B6:CGaB9;C9)=D6Y&iH6T=SUMPRODUCT(B7:CT, 59:C幻司 7fT+H78=stmpR)ODUCT能: c亂斑：cq)=D8-G8+HB10 =5*H5+4*GE+3, 5*HT*2, L小Hg+G5蛻知軍就選通田*用情號注型 P脖京豐余國ABCDEFc1某坊織廠最優(yōu)產(chǎn)品型合何題2各產(chǎn)品對各因考t3的單位商耐的需右4因素產(chǎn)品1產(chǎn)品2目標圖正面差負偏差總和端常數(shù)5開工時間11>=80100 .80=8D 16加班時間隈制119 口<=go0090二9。17A布料銷售量107070007070

21、 I0口布米辟善量0120>=02S4B=噩g決策變量702?？偲坪?2, 5胡劃煢靜基群iSS目3福；Ijgiic 2d 等于廣量文倒篁后曼卜債用 可芟曲元崎'U I用舐 其行.為并,刑專 由可明pus：皿 & g：m圖7-4單元格（B5:C8）,實際上是決策變量在目標規(guī)劃數(shù)學模型中的系數(shù)，又可理解為對各 對應因素的單位貢獻。如單元格B5是產(chǎn)品1對開工時間這一因素的單位貢獻，即生產(chǎn) 1千米的A布料使開工時間增加 1。D列計算了決策變量對每一因素的總貢獻值。如單元格 D5為總的開工時間，由公式 SUMPRODUCT（B5:C5,B9:C9）計算而得。（B9:C9）為可變

22、單元格，（G5:H8）為附加的可變單元格。G、H、I、K列是該模型微妙所在。G列和H列分別表示了實際的正負偏差的值。I列按照數(shù)學模型中目標約束方程計算出的左端值。如單元格I5為第一個目標約束方程的左端值，由D5-G5+H5計算而得。單元格G10為目標單元格，它是各因素未達目標的總偏差（總罰數(shù)）。但是要注意的是，比如第一級目標，只有負偏差大于 0時，才會產(chǎn)生罰數(shù)。同樣的第二級目標只有正偏差大于 0時才會產(chǎn)生罰數(shù)。依此類推。在這里，決策者還要根據(jù)實際情況給出各級目標的罰系數(shù)， 本題給出的假定罰系數(shù)見單元格G10的計算公式。注意，目標等級越高，罰系數(shù)越大。目標是使總罰數(shù)最小。在規(guī)劃求解參數(shù)對話框里，

23、給出目標單元格、可變單元格和約束。約束是使目標約束等 式兩端相等。由于依然屬于線性規(guī)劃問題，仍需在選項對話框里選擇“采用線性模型”和“假定非負” 復選框?？梢钥吹綀D7-4的計算結(jié)果與前面兩種方法相同。對于包含有絕對約束的目標規(guī)劃模型，絕對約束的優(yōu)先等級高于任何目標約束，因而要把它放入規(guī)劃求解的約束條件里。例8將例3中的目標利潤改為 4000,試用EXCEL求解最優(yōu)方案。解 該問題包含有一個絕對約束：機時約束x1 x2 10 ,把它定義到規(guī)劃求解對話框的約JI束里。模型與求解結(jié)果見圖7-5。保證絕對約束問麴各產(chǎn)品對各國素因索利潤人工機時 決策變量的單位靈植產(chǎn)品1產(chǎn)品230Qq500息克秋唱4Q0

24、Q488>=>-c=口標值正隔差負偏差40007010022總和41m70右湍常數(shù)鈍gTODI5三 SUffPRDDUCTtSS :C5t BE:C8)-D5-G5+H56:£UNPR0DUCT(M=C6m B8：C8)=D6H6+H67=EUHPRODUCT(B7：C7,BE:C8)總偏離量0F褒用續(xù)性模里V g騰定率貨10=10*強467.1判斷以下目標規(guī)劃的目標函數(shù)是否正確。(1) maxz dd(3) maxz dd(4)7.2用圖解法求解下列目標規(guī)劃問題:min z M1d1M 2d3M 3d2；x1 2x2 d1 d14;(1)x1 2x2 d2 d24;s.

25、tx 2x2 d3 d38;X,x2,di,di0(i 1,2,3).min z ddmin z ddmin z M1d3M2d2M3 d1d13336x1 2x2 d1d124;),X x2 d2 d25;s.t5x2 d3 d315;為公"© 0(i 1,2,3).10理置目標單元施皂u iMiJil等于；r最大n中仃金小值0D 可支單元喳£班舊醛的SHJSG妁榮如:皿 0 (K7pm srfia = *小 £中圖7-5模型中對兩目標的罰系數(shù)分別設為10和1。求解結(jié)果，利潤目標實現(xiàn)了，人工也少于70,目標偏離量為 0。習題min z M1d1M 2d

26、2 M3d3min z M1(d1d1 ) M2(d2 d2)X X2 4;x1 2x2 6;(3)s.t 2x1 3x2 d1d118;3x1 2x2 d2 d2 18;為©40(i 1,2).2x1x2 d1d1210;2x1 d2 d260;(4) 122s.tx2 d3 d345;x2 80;x1,x2,di ,di0.并滿足:7.3某廠組裝兩種產(chǎn)品，有關數(shù)據(jù)如表7-1。要求確定兩種產(chǎn)品的日生產(chǎn)計劃,(1)不得使裝配線超負荷生產(chǎn)；(2)不得有剩余產(chǎn)品；(3)日產(chǎn)值盡可能達到 5000元。試找出滿意解，并用圖示說明之。表7-1產(chǎn)品單件組裝工時日銷量(件)產(chǎn)值(元/件)日裝配能力

27、A1.17040150B1.360607.4上題中，若將目標要求改為：(1)盡可能發(fā)揮工廠的裝配能力；(2)盡可能滿足市場的需求，并使產(chǎn)量與銷量保持一致;(3)裝配生產(chǎn)線可加班，但時數(shù)不得超過30小時;(4)盡可能使日產(chǎn)值最大。試定出兩種產(chǎn)品滿意的日產(chǎn)計劃。7.5已知目標規(guī)劃問題的約束條件如下：2x1 x2 d1 d12;2x1 3x2 d2 d26;s.tx 6;x1,x2,di ,di0(i 1,2)求在下述各目標函數(shù)下的滿意解：(1) min z M1(d1 d1 d2 d2)(2) min z 2M1(d1 d1 ) M2(d2 d2)(3) min z M1(d1d1 ) 2M2(d2 d2)(4) min z M1(d1d1 ) M2(d2 d2)7.6 某公司要將一批貨從三個產(chǎn)地運到四個銷地，有關數(shù)據(jù)如表7-2。現(xiàn)要求訂出調(diào)運計劃，且依次滿足：(1) B4要保證供應；(2) 其余銷地的供應量不低于80%;(3) A2給B2的供應量不低于150;(4) A2盡可能少給Bi;(5) 銷地Bi、B2的供應量盡可能保持平衡。要求：(6) 建立使總運費最小的目標規(guī)劃模型？(7) 建立該問題的電子表格模型，并用 EXCEL規(guī)劃求解進行求解。表7-2B1B2B3B4供應量A17379560A226511400A36425750需求重3202404803807.7 某公司的