7運籌學(xué)之目標(biāo)規(guī)劃胡運權(quán)版

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

2、規(guī)劃的概念與數(shù)學(xué)模型，以解決經(jīng)濟(jì)管理中的多目標(biāo)決策問題。我們將通過幾個例子來說明在實際應(yīng)用中線性規(guī)劃存在一系列的局限性。例1 某廠生產(chǎn)A、B兩種產(chǎn)品每件所需的勞動力分別為4個人工和6個人工，所需設(shè)備的單位臺時均為1。已知該廠有10個單位機(jī)器臺時提供制造這兩種產(chǎn)品，并且至少能提供70個人工。又，A、B產(chǎn)品的利潤，每件分別為300元和500元。試問：該廠各應(yīng)生產(chǎn)多少件A、B產(chǎn)品，才能使其利潤值最大？解 設(shè)該廠能生產(chǎn)A、B產(chǎn)品的數(shù)量分別為件，則有 圖解法求解如下： 由上圖可得，滿足約束條件的可行解集為，即機(jī)時約束和人工約束之間產(chǎn)生矛盾，因而該問題無解。但在實際中，該廠要增加利潤，不可能不生產(chǎn)A、B兩

3、種產(chǎn)品，而由線性規(guī)劃模型無法為其找到一個合適的方案。例2 某廠為進(jìn)行生產(chǎn)需采購A、B兩種原材料，單價分別為70元/公斤和50元/公斤?，F(xiàn)要求購買資金不超過5000元，總購買量不少于80公斤，而A原材料不少于20公斤。問如何確定最好的采購方案（即花掉的資金最少，購買的總量最大）？解 這是一個含有兩個目標(biāo)的數(shù)學(xué)規(guī)劃問題。設(shè)分別為購買兩種原材料的公斤數(shù)，為花掉的資金，為購買的總量。建立該問題的數(shù)學(xué)模型形式如下： 對于這樣的多目標(biāo)問題，線性規(guī)劃很難為其找到最優(yōu)方案。極可能的結(jié)果是，第一個方案使第一目標(biāo)的結(jié)果值優(yōu)于第二方案，同時第二方案使第二目標(biāo)的結(jié)果值優(yōu)于第一方案。也就是說很難找到一個最優(yōu)方案，使兩個

4、目標(biāo)的函數(shù)值同時達(dá)到最優(yōu)。另外，對于多目標(biāo)問題，還存在有多個目標(biāo)存在有不同重要程度的因素，而這也是線性規(guī)劃所無法解決的。在線性規(guī)劃的基礎(chǔ)上，建立了一種新的數(shù)學(xué)規(guī)劃方法目標(biāo)規(guī)劃法，用于彌補(bǔ)線性規(guī)劃的上述局限性?？偟膩碚f，目標(biāo)規(guī)劃和線性規(guī)劃的不同之處可以從以下幾點反映出來：1、線性規(guī)劃只能處理一個目標(biāo)，而現(xiàn)實問題往往存在多個目標(biāo)。目標(biāo)規(guī)劃能統(tǒng)籌兼顧地處理多個目標(biāo)的關(guān)系，求得切合實際需求的解。2、線性規(guī)劃是求滿足所有約束條件的最優(yōu)解。而在實際問題中，可能存在相互矛盾的約束條件而導(dǎo)致無可行解，但此時生產(chǎn)還得繼續(xù)進(jìn)行。即使存在可行解，實際問題中也未必一定需要求出最優(yōu)解。目標(biāo)規(guī)劃是要找一個滿意解，即使在相

5、互矛盾的約束條件下也找到盡量滿足約束的滿意解，即滿意方案。3、線性規(guī)劃的約束條件是不分主次地等同對待，這也并不都符合實際情況。而目標(biāo)規(guī)劃可根據(jù)實際需要給予輕重緩急的考慮。§2 目標(biāo)規(guī)劃的基本概念與數(shù)學(xué)模型§2.1 基本概念在這一小節(jié)里介紹與目標(biāo)規(guī)劃有關(guān)的基本概念。1偏差變量對于例1，造成無解的關(guān)鍵在于約束條件太死板。設(shè)想把約束條件“放松”，比如占用的人力可以少于70人的話，機(jī)時約束和人工約束就可以不再發(fā)生矛盾。在此基礎(chǔ)上，引入了正負(fù)偏差的概念，來表示決策值與目標(biāo)值之間的差異。正偏差變量，表示決策值超出目標(biāo)值的部分，目標(biāo)規(guī)劃里規(guī)定；負(fù)偏差變量，表示決策值未達(dá)到目標(biāo)值的部分，目

6、標(biāo)規(guī)劃里規(guī)定。實際操作中，當(dāng)目標(biāo)值（也就是計劃的利潤值）確定時，所作的決策可能出現(xiàn)以下三種情況之一：（1）決策值超過了目標(biāo)值（即完成或超額完成計劃利潤值），表示為，；（2）決策值未達(dá)到目標(biāo)值（即未完成計劃利潤值），表示為，；（3）決策值恰好等于目標(biāo)值（即恰好完成計劃利潤指標(biāo)），表示為，。以上三種情況，無論哪種情況發(fā)生，均有 =0。2絕對約束與目標(biāo)約束絕對約束也稱系統(tǒng)約束，是指必須嚴(yán)格滿足的等式約束和不等式約束，它對應(yīng)于線性規(guī)劃模型中的約束條件。目標(biāo)約束是目標(biāo)規(guī)劃所特有的。當(dāng)確定了目標(biāo)值，進(jìn)行決策時，允許與目標(biāo)值存在正或負(fù)的偏差。因而目標(biāo)約束中加入了正、負(fù)偏差變量。如，例1中假定該企業(yè)計劃利潤值

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

8、量盡可能地小。此時構(gòu)造目標(biāo)函數(shù)為：（3）求超過目標(biāo)值，即超過量不限，負(fù)偏差變量盡可能地小。此時構(gòu)造目標(biāo)函數(shù)為：4優(yōu)先次序系數(shù)與權(quán)系數(shù)一個規(guī)劃問題往往有多個目標(biāo)。決策者在實現(xiàn)這些目標(biāo)時，存在有主次與輕重緩急的不同。對于有級目標(biāo)的問題，按照優(yōu)先次序分別賦予不同大小的大系數(shù)：，。，為無窮大的正數(shù)，并且，（“”符號表示“遠(yuǎn)大于”），這樣，只有當(dāng)某一級目標(biāo)實現(xiàn)以后（即目標(biāo)值為0） ，才能忽略大的影響，否則目標(biāo)偏離量會因為大的原因而無窮放大。并且由于，所以只有先考慮忽略影響（實現(xiàn)第級目標(biāo)）后，才能考慮第級目標(biāo)。實際上這里的大是對偏離目標(biāo)值的懲罰系數(shù)，優(yōu)先級別越高，懲罰系數(shù)越大。權(quán)系數(shù)用來區(qū)別具有相同優(yōu)先級

9、別的若干目標(biāo)。在同一優(yōu)先級別中，可能包含有兩個或多個目標(biāo)，它們的正負(fù)偏差變量的重要程度有差別，此時可以給正負(fù)偏差變量賦予不同的權(quán)系數(shù)和。各級目標(biāo)的優(yōu)先次序及權(quán)系數(shù)的確定由決策者按具體情況給出。§2.2 目標(biāo)規(guī)劃的數(shù)學(xué)模型綜上所述，目標(biāo)規(guī)劃模型由目標(biāo)函數(shù)、目標(biāo)約束、絕對約束以及變量非負(fù)約束等幾部分構(gòu)成。目標(biāo)規(guī)劃的一般數(shù)學(xué)模型為：目標(biāo)函數(shù) 目標(biāo)約束 絕對約束 非負(fù)約束 例3 在例1中，假定目標(biāo)利潤不少于15000元，為第一目標(biāo)；占用的人力可以少于70人，為第二目標(biāo)。求決策方案。解 按決策者的要求分別賦予兩個目標(biāo)大系數(shù)。列出模型如下： 例4 某紡織廠生產(chǎn)A、B兩種布料，平均生產(chǎn)能力均為1千

10、米/小時，工廠正常生產(chǎn)能力是80小時/周。又A布料每千米獲利2500元，B布料每千米獲利1500元。已知A、B兩種布料每周的市場需求量分別是70千米和45千米?，F(xiàn)該廠確定一周內(nèi)的目標(biāo)為：第一優(yōu)先級：避免生產(chǎn)開工不足；第二優(yōu)先級：加班時間不超過10小時；第三優(yōu)先級：根據(jù)市場需求達(dá)到最大銷售量；第四優(yōu)先級：盡可能減少加班時間。試求該問題的最優(yōu)方案。解 設(shè)分別為生產(chǎn)甲、乙布料的小時數(shù)。對于第三優(yōu)先級目標(biāo)，根據(jù)A、B布料利潤的比值，取二者達(dá)到最大銷量的權(quán)系數(shù)分別為5和3。該問題的目標(biāo)規(guī)劃模型為： 綜上所述，目標(biāo)規(guī)劃建立模型的步驟為：1、 根據(jù)問題所提出的各目標(biāo)與條件，確定目標(biāo)值，列出目標(biāo)約束與絕對約束

11、；2、根據(jù)決策者的需要將某些或全部絕對約束轉(zhuǎn)換為目標(biāo)約束，方法是絕對約束的左式加上負(fù)偏差變量和減去正偏差變量； 3、給各級目標(biāo)賦予相應(yīng)的懲罰系數(shù)（），為無窮大的正數(shù)，且； 4、對同一優(yōu)先級的各目標(biāo)，再按其重要程度不同，賦予相應(yīng)的權(quán)系數(shù)；5、根據(jù)決策者的要求，各目標(biāo)按三種情況取值：恰好達(dá)到目標(biāo)值，取允許超過目標(biāo)值，取不允許超過目標(biāo)值，??；然后構(gòu)造一個由懲罰系數(shù)、權(quán)系數(shù)和偏差變量組成的、要求實現(xiàn)極小化的目標(biāo)函數(shù)。§3 目標(biāo)規(guī)劃的求解3.1 圖解法只有兩個決策變量的目標(biāo)規(guī)劃數(shù)學(xué)模型，可以使用簡單直觀的圖解法求解。其方法與線性規(guī)劃圖解法類似，先在平面直角坐標(biāo)系第一象限內(nèi)作出各約束等式或不等式

12、的圖象，然后由絕對約束確定了可行域，由目標(biāo)約束和目標(biāo)函數(shù)確定最優(yōu)解或滿意解。對于絕對約束，與線性規(guī)劃中的約束條件畫法完全相同。對于目標(biāo)約束方程，除作出直線外，還要在直線上要標(biāo)出正負(fù)偏差變量的方向，其可行域方向取決于目標(biāo)函數(shù)中對應(yīng)目標(biāo)。另外，目標(biāo)規(guī)劃是在前一級目標(biāo)滿足的情況下再來考慮下一級目標(biāo)，很有可能盡可能滿足目標(biāo)的解不是可行解（即非可行解），而是權(quán)衡以后得出的最優(yōu)解滿意解。因而在目標(biāo)規(guī)劃里稱求得的解為滿意解。 注意在求解的時候，把絕對約束作最高級別考慮。例5 用圖解法求解目標(biāo)規(guī)劃問題 解 在平面直角坐標(biāo)系第一象限內(nèi)作出各約束條件的圖像，目標(biāo)約束要在直線旁標(biāo)上和di+。首先，絕對約束確定了可行

13、解范圍在三角形OEF內(nèi)；根據(jù)第一級目標(biāo)，要求實現(xiàn)（恰好），因而可行解范圍縮小到線段OC上；根據(jù)第二級目標(biāo)，要求實現(xiàn)（不少于），在線段OC上，取的點A，此時可行解范圍縮小到線段AC上；根據(jù)第三級目標(biāo)，要求實現(xiàn)，在線段AC上，取的點B，此時解的范圍縮小到線段AB上。所以，線段AB上的所有點為滿意解?？汕蟮肁(15/8,15/8)，B(24/7,24/7)。例6 用圖解法求解例4的目標(biāo)規(guī)劃模型。解 在平面直角坐標(biāo)系第一象限內(nèi)作出各約束條件對應(yīng)的圖象，并在目標(biāo)約束直線旁標(biāo)上和。 根據(jù)第一級目標(biāo)，目標(biāo)函數(shù)要求實現(xiàn)，解的范圍是線段AC的右上方區(qū)域；根據(jù)第二級目標(biāo)，目標(biāo)函數(shù)要求實現(xiàn)，解的范圍縮小到四邊形AB

14、DC內(nèi)的區(qū)域；根據(jù)第三級目標(biāo)，目標(biāo)函數(shù)要求實現(xiàn)，先考慮，解的范圍縮小為四邊形ABFE內(nèi)的區(qū)域，再考慮，四邊形ABFE內(nèi)的所有點，均無法滿足，此時在可行域ABFE內(nèi)考慮使達(dá)到最小的滿意點F，F(xiàn)點不滿足，但它是使第三級目標(biāo)最滿意的滿意解；根據(jù)第四級目標(biāo)，目標(biāo)函數(shù)要求實現(xiàn)，由于解的范圍已經(jīng)縮小到點F，所以唯一的點F也是使第四級目標(biāo)最滿意的滿意解。綜上所述，該問題的滿意解為點F，可求得F(70,20)。給出圖解法求解步驟如下：1、在直角坐標(biāo)系的第一象限作出絕對約束和目標(biāo)約束的圖象，絕對約束確定出可行解的區(qū)域，在目標(biāo)約束直線上用箭頭標(biāo)出正負(fù)偏差變量值增大的方向（正、負(fù)偏差變量增大的方向相反）；2、 在可

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

16、，但達(dá)到最優(yōu)的目標(biāo)值一定是優(yōu)先等級排在前面的，此時獲得的解為滿意解。如例4用單純形法求的滿意解為，目標(biāo)值為，可以看到求得的解并沒有使第三級和第四級目標(biāo)達(dá)到最優(yōu)，但已使第一、二級目標(biāo)達(dá)到最優(yōu)，這和前面用圖解法求得的結(jié)果一致。3.3 EXCEL電子表格法 目標(biāo)規(guī)劃同樣能由EXCEL求得其滿意解。關(guān)鍵在于如何建立電子表格模型。例7 用EXCEL求解例4的目標(biāo)規(guī)劃模型。解 我們來看一下如何為例4中的目標(biāo)規(guī)劃問題建立電子表格模型，見圖7-4。 圖7-4單元格（B5:C8），實際上是決策變量在目標(biāo)規(guī)劃數(shù)學(xué)模型中的系數(shù)，又可理解為對各對應(yīng)因素的單位貢獻(xiàn)。如單元格B5是產(chǎn)品1對開工時間這一因素的單位貢獻(xiàn)，即生

17、產(chǎn)1千米的A布料使開工時間增加1。D列計算了決策變量對每一因素的總貢獻(xiàn)值。如單元格D5為總的開工時間，由公式SUMPRODUCT(B5:C5,B9:C9)計算而得。 （B9:C9）為可變單元格，（G5:H8）為附加的可變單元格。G、H、I、K列是該模型微妙所在。G列和H列分別表示了實際的正負(fù)偏差的值。I列按照數(shù)學(xué)模型中目標(biāo)約束方程計算出的左端值。如單元格I5為第一個目標(biāo)約束方程的左端值，由D5-G5+H5計算而得。單元格G10為目標(biāo)單元格，它是各因素未達(dá)目標(biāo)的總偏差（總罰數(shù)）。但是要注意的是，比如第一級目標(biāo)，只有負(fù)偏差大于0時，才會產(chǎn)生罰數(shù)。同樣的第二級目標(biāo)只有正偏差大于0時才會產(chǎn)生罰數(shù)。依此

18、類推。在這里，決策者還要根據(jù)實際情況給出各級目標(biāo)的罰系數(shù)，本題給出的假定罰系數(shù)見單元格G10的計算公式。注意，目標(biāo)等級越高，罰系數(shù)越大。目標(biāo)是使總罰數(shù)最小。在規(guī)劃求解參數(shù)對話框里，給出目標(biāo)單元格、可變單元格和約束。約束是使目標(biāo)約束等式兩端相等。 由于依然屬于線性規(guī)劃問題，仍需在選項對話框里選擇“采用線性模型”和“假定非負(fù)”復(fù)選框。 可以看到圖7-4的計算結(jié)果與前面兩種方法相同。對于包含有絕對約束的目標(biāo)規(guī)劃模型，絕對約束的優(yōu)先等級高于任何目標(biāo)約束，因而要把它放入規(guī)劃求解的約束條件里。例8 將例3中的目標(biāo)利潤改為4000，試用EXCEL求解最優(yōu)方案。解 該問題包含有一個絕對約束：機(jī)時約束，把它定義

19、到規(guī)劃求解對話框的約束里。模型與求解結(jié)果見圖7-5。 圖7-5模型中對兩目標(biāo)的罰系數(shù)分別設(shè)為10和1。求解結(jié)果，利潤目標(biāo)實現(xiàn)了，人工也少于70，目標(biāo)偏離量為0。習(xí)題7.1 判斷以下目標(biāo)規(guī)劃的目標(biāo)函數(shù)是否正確。 （1） （2） （3） （4）7.2 用圖解法求解下列目標(biāo)規(guī)劃問題：（1） （2）（3）（4）7.3 某廠組裝兩種產(chǎn)品，有關(guān)數(shù)據(jù)如表7-1。要求確定兩種產(chǎn)品的日生產(chǎn)計劃，并滿足： （1）不得使裝配線超負(fù)荷生產(chǎn)； （2）不得有剩余產(chǎn)品； （3）日產(chǎn)值盡可能達(dá)到5000元。 試找出滿意解，并用圖示說明之。表7-1產(chǎn)品單件組裝工時日銷量（件）產(chǎn)值（元/件）日裝配能力A1.17040150B1.

20、360607.4 上題中，若將目標(biāo)要求改為： （1）盡可能發(fā)揮工廠的裝配能力； （2）盡可能滿足市場的需求，并使產(chǎn)量與銷量保持一致； （3）裝配生產(chǎn)線可加班，但時數(shù)不得超過30小時； （4）盡可能使日產(chǎn)值最大。試定出兩種產(chǎn)品滿意的日產(chǎn)計劃。 7.5 已知目標(biāo)規(guī)劃問題的約束條件如下： 求在下述各目標(biāo)函數(shù)下的滿意解：（1）（2）（3）（4）7.6 某公司要將一批貨從三個產(chǎn)地運到四個銷地，有關(guān)數(shù)據(jù)如表7-2?，F(xiàn)要求訂出調(diào)運計劃，且依次滿足：（1）B4要保證供應(yīng)；（2）其余銷地的供應(yīng)量不低于80%；（3）A2給B2的供應(yīng)量不低于150；（4）A2盡可能少給B1；（5）銷地B1、B2的供應(yīng)量盡可能保持平

21、衡。要求：（1）建立使總運費最小的目標(biāo)規(guī)劃模型？（2）建立該問題的電子表格模型，并用EXCEL規(guī)劃求解進(jìn)行求解。表7-2產(chǎn)地 銷地B1B2B3B4供應(yīng)量A17379560A226511400A36425750需求量3202404803807.7 某公司的管理層已經(jīng)為其公司的兩種新產(chǎn)品制定了各自的市場目標(biāo)，具體地說，產(chǎn)品1必須占據(jù)15%的市場份額，而產(chǎn)品2必須有10%的市場份額。為了獲得市場，準(zhǔn)備開展三次廣告活動，其中兩個廣告是分別針對產(chǎn)品1和產(chǎn)品2的，而廣告3是為了提高整個公司及其產(chǎn)品的聲譽。以分別表示分配在三個廣告上的資金（以百萬元為單位），相應(yīng)的兩種產(chǎn)品取得的市場份額估計值（以百分比表示）