第3章目標(biāo)規(guī)劃杜

1、第三章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃是在線性規(guī)劃的基礎(chǔ)上，為適應(yīng)經(jīng)濟(jì)管理中多目標(biāo)決策的需要而逐步發(fā)展起來的一個(gè)運(yùn)籌學(xué)分支，是實(shí)現(xiàn)目標(biāo)管理的這種現(xiàn)代化技術(shù)的一個(gè)有效工具。第一節(jié) 目標(biāo)規(guī)劃問題的提出及其數(shù)學(xué)模型目標(biāo)規(guī)劃的有關(guān)概念和模型最早在1961年由美國學(xué)者A.查恩斯和W.庫伯在他們合著的管理模型和線性規(guī)劃的工業(yè)應(yīng)用一書中提出，以后這種模型又先后經(jīng)尤吉艾里斯等人不斷完善改進(jìn)。1976年伊格尼齊奧發(fā)表了目標(biāo)規(guī)劃及其擴(kuò)展一書，系統(tǒng)歸納總結(jié)了目標(biāo)規(guī)劃的理論和方法，下面我們通過例子來說明什么是目標(biāo)規(guī)劃。一、目標(biāo)規(guī)劃問題的提出例1某工廠生產(chǎn)兩種化工產(chǎn)品，受到原材料供應(yīng)和設(shè)備工時(shí)的限制。在單件利潤等有關(guān)數(shù)據(jù)已知的條件下

2、，要求制訂一個(gè)獲利最大的生產(chǎn)計(jì)劃。具體數(shù)據(jù)見表3-l。 表3-1 產(chǎn)品限量原料(千克)51060設(shè)備工時(shí)(小時(shí)/件)4440利潤(元/件)68解：設(shè)產(chǎn)品I和的產(chǎn)量分別為和，當(dāng)用線性規(guī)劃來描述和解決這個(gè)問題時(shí)，其數(shù)學(xué)模型為:用圖解法或單純形法求解，解得：最優(yōu)生產(chǎn)計(jì)劃為，。從線性規(guī)劃的角度來看，問題已經(jīng)得到了圓滿的解決。但如果站的角度不同，決策的目標(biāo)也可能不同。例2在例 l 的基礎(chǔ)上，要求考慮如下意見：(1)由于產(chǎn)品銷售疲軟，故希望產(chǎn)品的產(chǎn)量不超過產(chǎn)品I的一半；(2)原材料嚴(yán)重短缺，生產(chǎn)中應(yīng)避免過量消耗；(3)最好能節(jié)約4小時(shí)設(shè)備工時(shí)；(4)計(jì)劃利潤不少于48元。面對這些意見，計(jì)劃人員需要會同有關(guān)

3、各方作進(jìn)一步的協(xié)調(diào)，最后達(dá)成了一致意見：原材料使用限額不得突破；產(chǎn)品產(chǎn)量要求必須優(yōu)先考慮；設(shè)備工時(shí)問題其次考慮；最后考慮計(jì)劃利潤的要求。要考慮上述多方面的目標(biāo)，就需要借助目標(biāo)規(guī)劃的方法。目標(biāo)規(guī)劃與線性規(guī)劃相比有以下優(yōu)點(diǎn)：(1) 線性規(guī)劃立足于求滿足所有約束條件的最優(yōu)解，而在實(shí)際問題中，可能存在相互矛盾的約束條件。目標(biāo)規(guī)劃可以在相互矛盾的約束條件下找到滿意解。(2) 線性規(guī)劃只能處理一個(gè)目標(biāo)，而現(xiàn)實(shí)問題往往要處理多個(gè)目標(biāo)。目標(biāo)規(guī)劃就能統(tǒng)籌兼顧地處理多個(gè)目標(biāo)的關(guān)系，求得更切合實(shí)際要求的解。(3) 線性規(guī)劃的約束條件是不分主次地同等對待，而目標(biāo)規(guī)劃可根據(jù)實(shí)際的需要給予輕重緩急的考慮。(4) 目標(biāo)規(guī)劃

4、的最優(yōu)解指的是盡可能地達(dá)到或接近一個(gè)或若干個(gè)已給定的指標(biāo)值。二、目標(biāo)規(guī)劃的基本概念（1）偏差變量對每一個(gè)決策目標(biāo)，引入正、負(fù)偏差變量和，分別表示決策值超過或不足目標(biāo)值的部分。按定義應(yīng)有，。（2）絕對約束和目標(biāo)約束絕對約束是指必須嚴(yán)格滿足的約束條件，如線性規(guī)劃中的約束條件都是絕對約束。絕對約束是硬約束，對它的滿足與否，決定了解的可行性。目標(biāo)約束是目標(biāo)規(guī)劃特有的概念，是一種軟約束，目標(biāo)約束中決策值和目標(biāo)值之間的差異用偏差變量表示。（3）目標(biāo)的優(yōu)先級和權(quán)系數(shù)不同目標(biāo)的主次輕重有兩種差別。一種差別是絕對的，可用優(yōu)先因子來表示。只有在高級優(yōu)先因子對應(yīng)的目標(biāo)已滿足的基礎(chǔ)上，才能考慮較低級優(yōu)先因子對應(yīng)的目標(biāo)

5、；在考慮低級優(yōu)先因子對應(yīng)的目標(biāo)時(shí)，絕不允許違背已滿足的高級優(yōu)先因子對應(yīng)的目標(biāo)。如優(yōu)先因子間的關(guān)系為，即所對應(yīng)的目標(biāo)比所對應(yīng)的目標(biāo)具有絕對的優(yōu)先性。另一種差別是相對的，這些目標(biāo)具有相同的優(yōu)先因子,它們的重要程度可用權(quán)系數(shù)的不同來表示。（4）目標(biāo)規(guī)劃的目標(biāo)函數(shù)目標(biāo)規(guī)劃的目標(biāo)函數(shù)由各目標(biāo)約束的偏差變量及相應(yīng)的優(yōu)先因子和權(quán)系數(shù)構(gòu)成。由于目標(biāo)規(guī)劃追求的是盡可能接近各既定目標(biāo)值,也就是使各有關(guān)偏差變量盡可能小，所以其目標(biāo)函數(shù)只能是極小化即：。有三種基本表達(dá)式：要求恰好達(dá)到目標(biāo)值。這時(shí)，決策值超過或不足目標(biāo)值都是不希望的，因此有：要求不超過目標(biāo)值，但允許不足目標(biāo)值。這時(shí)，不希望決策值超過目標(biāo)值，因此有：要求

6、不低于目標(biāo)值，但允許超過目標(biāo)值。這時(shí)，不希望決策值低于目標(biāo)值，因此有：對于每一個(gè)具體目標(biāo)規(guī)劃問題，可根據(jù)決策者的要求和個(gè)目標(biāo)的優(yōu)先因子來構(gòu)造目標(biāo)函數(shù)，下面舉例說明。例3假設(shè)在例 l 的基礎(chǔ)上，若工廠提出的管理目標(biāo)按優(yōu)先級排列如下：級目標(biāo)：希望產(chǎn)品的產(chǎn)量不超過產(chǎn)品I的一半；級目標(biāo)：最好能節(jié)約4小時(shí)設(shè)備工時(shí)；級目標(biāo)：計(jì)劃利潤不少于48元。由于原材料嚴(yán)重短缺，故原材料約束作為絕對約束，試建立目標(biāo)規(guī)劃模型。解：引入偏差變量三個(gè)目標(biāo)約束：按優(yōu)先級確定目標(biāo)函數(shù)。級目標(biāo)要求；級目標(biāo)要求；級目標(biāo)要求，則該問題的數(shù)學(xué)模型為：其中(a)為絕對約束，（b）（c）(d)為目標(biāo)約束。該問題也可以這樣處理，把絕對約束(a

7、)化為目標(biāo)約束，則該問題的數(shù)學(xué)模型為：目標(biāo)規(guī)劃的一般數(shù)學(xué)模型為：式中：為第級優(yōu)先因子；，為分別賦予第個(gè)目標(biāo)約束的正負(fù)偏差變量的權(quán)系數(shù)。為第個(gè)目標(biāo)的預(yù)期目標(biāo)值。用目標(biāo)規(guī)劃處理問題的難點(diǎn)在于構(gòu)造模型時(shí)需要實(shí)現(xiàn)擬定目標(biāo)值、優(yōu)先級和權(quán)系數(shù)。而這些信息來自人的主觀判斷，往往帶有模糊性，很難定出一個(gè)絕對的數(shù)值。用目標(biāo)規(guī)劃求解問題的過程參見下面圖3-1： 圖3-1第二節(jié) 目標(biāo)規(guī)劃的圖解法對于只有兩個(gè)決策變量的目標(biāo)規(guī)劃問題，可以用圖解方法來求解。在用圖解法解目標(biāo)規(guī)劃時(shí)，首先必須滿足所有絕對約束。在此基礎(chǔ)上，再按照優(yōu)先級從高到低的順序，逐個(gè)地考慮各個(gè)目標(biāo)約束。一般地，若優(yōu)先因子對應(yīng)的解空間為，則優(yōu)先因子對應(yīng)的解

8、空間只能在中考慮。即:,若，而，則中的解為目標(biāo)規(guī)劃的滿意解，它只能保證滿足級目標(biāo)。而不保證滿足其后的各級目標(biāo)。例4某小型空調(diào)廠家生產(chǎn)普通和變頻兩種空調(diào)，每生產(chǎn)一臺空調(diào)需占用生產(chǎn)線1小時(shí)，生產(chǎn)線每周計(jì)劃生產(chǎn)40小時(shí)。預(yù)計(jì)市場每周變頻空調(diào)的銷量是24臺，每臺可獲利潤80元，普通空調(diào)的銷量是30臺，每臺可獲利潤40元，該廠確定的目標(biāo)為：充分利用成產(chǎn)險(xiǎn)每周計(jì)劃工時(shí)開動40小時(shí)；：允許生產(chǎn)線加班，但加班時(shí)間每周盡量不超過10小時(shí)；：生產(chǎn)空調(diào)的數(shù)量盡量滿足市場需要，由于變頻空調(diào)的利潤高，取其權(quán)系數(shù)為2.試建立該問題的目標(biāo)規(guī)劃模型，并求解普通和變頻空調(diào)的產(chǎn)量。解：設(shè)分別表示普通和變頻空調(diào)的產(chǎn)量，則該問題的目

9、標(biāo)規(guī)劃模型為:用圖解法求解：在具有，的目標(biāo)實(shí)現(xiàn)后，的取值范圍為.考慮的目標(biāo)要求時(shí)，因的權(quán)系數(shù)大于，故先考慮；這時(shí)的取值范圍縮小為區(qū)域。接著考慮，因在中無法滿足，所以只能在中取一點(diǎn)，使盡可能小，即找到點(diǎn)為滿意解，其坐標(biāo)為：，即：每周生產(chǎn)變頻空調(diào)24臺，普通空調(diào)26臺。注意：在用圖解法解目標(biāo)規(guī)劃時(shí)，可能會遇到下面兩種情況：1、最后一級目標(biāo)的解空間非空。這時(shí)得到的解能滿足所有目標(biāo)的要求。當(dāng)解不唯一時(shí)決策者在作實(shí)際決策時(shí)究竟選擇哪一個(gè)解，完全取決于決策者自身的考慮。2、另一種情況是像例4那樣，得到的解不能滿足所有目標(biāo)。這時(shí)，我們要做的是尋找滿意解，使它盡可能滿足高級別的目標(biāo)，同時(shí)又使它對那些不能滿足的

10、較低級別目標(biāo)的偏離程度盡可能地小。第三節(jié) 目標(biāo)規(guī)劃的單純形法目標(biāo)規(guī)劃的數(shù)學(xué)模型本質(zhì)上與線性規(guī)劃沒有區(qū)別，可以用單純形法求解。在用單純形法解目標(biāo)規(guī)劃時(shí)，檢驗(yàn)數(shù)是各優(yōu)先因子的線性組合。因此，在判別各檢驗(yàn)數(shù)的正負(fù)及大小時(shí)，必須注意。當(dāng)所有檢驗(yàn)數(shù)都已滿足最優(yōu)性條件()時(shí)，從最終單純形表上就可以得到目標(biāo)規(guī)劃的解。一、單純形法的計(jì)算步驟1、單純形法的計(jì)算步驟（求）(1)找出初始可行基，確定初始基可行解，建立初始單純形表(2)檢驗(yàn)各非基變量的檢驗(yàn)數(shù)，若，則已得到最優(yōu)解，可停止計(jì)算，否則轉(zhuǎn)入下一步。(3)在中，若有某個(gè)對應(yīng)的系數(shù)列向量，則此問題是無界解，停止計(jì)算。否則，轉(zhuǎn)入下一步。(4)根據(jù)，確定為換入變量，

11、按規(guī)則計(jì)算可確定第l行的基變量為換出變量。轉(zhuǎn)入下一步.(5)以為主元素進(jìn)行迭代(即用高斯消去法)，把所對應(yīng)的列向量變換為，將列中的第l個(gè)基變量換為，得到新的單純形表，返回(2)。2、單純形法的計(jì)算步驟（求）(1)找出初始可行基，確定初始基可行解，建立初始單純形表(2)檢驗(yàn)各非基變量的檢驗(yàn)數(shù)，若，則 已得到最優(yōu)解，可停止計(jì)算，否則轉(zhuǎn)入下一步。(3)在中，若有某個(gè)對應(yīng)的系數(shù)列向量，則此問題是無界解，停止計(jì)算。否則，轉(zhuǎn)入下一步。(4)根據(jù)，確定為換入變量，按 規(guī)則計(jì)算可確定第l行的基變量為換出變量。轉(zhuǎn)入下一步.(5)以為主元素進(jìn)行迭代(即用高斯消去法)，把所對應(yīng)的列向量變換為，將列中的第l個(gè)基變量換

12、為，得到新的單純形表，返回(2)。例1用單純性法求解目標(biāo)規(guī)劃問題的滿意解。解：將上述目標(biāo)規(guī)劃轉(zhuǎn)化成如下形式：其中為松弛變量。對此問題用單純形法計(jì)算，見表3-1表3-1由表3-1得為原問題的滿意解。而非基變量的檢驗(yàn)數(shù)為0，故原問題存在多重解。在表3-1基礎(chǔ)上以為換入變量，為換出變量再迭代一步，得表3-2。表3-2由表3-2可得，也為滿意解。由線性規(guī)劃的性質(zhì)可得：和這兩點(diǎn)之間的線段上的所有點(diǎn)均為原問題的滿意解。第四節(jié) 目標(biāo)規(guī)劃應(yīng)用舉例例1 友誼農(nóng)場有3萬畝（每畝等于666.66平方米）農(nóng)田，欲種植玉米、大豆和小麥三種農(nóng)作物。各種作物每畝需施化肥分別為0.12、0.20、0.15噸。預(yù)計(jì)秋后玉米每畝

13、可收獲500公斤，售價(jià)為0.24元/公斤，大豆每畝可收獲200公斤，售價(jià)為1.20元/公斤，小麥每畝可收獲300公斤，售價(jià)為0.70元/公斤。農(nóng)場年初規(guī)劃時(shí)考慮如下幾方面：年終收益不低于350萬元；：總產(chǎn)量不低于1.25萬噸；：小麥產(chǎn)量以0.5萬噸為宜；：大豆產(chǎn)量不少于0.2萬噸；：玉米產(chǎn)量不超過0.6萬噸；：農(nóng)場現(xiàn)能提供5000噸化肥；若不夠，可在市場高價(jià)購買，但希望高價(jià)采購量愈少愈好。試就該農(nóng)場生產(chǎn)計(jì)劃建立數(shù)學(xué)模型。解：設(shè)種植玉米畝，大豆畝，小麥畝，則該問題的數(shù)學(xué)模型為：例2 某化工產(chǎn)品是用3種材料經(jīng)化學(xué)反應(yīng)合成的。若這三種材料每天供應(yīng)量和單位成本如表3-3所示表3-3材料日供應(yīng)量(kg)

14、成本（元/千克）1500620004.510003設(shè)該種化工產(chǎn)品有三種規(guī)格（甲乙丙），各種規(guī)格的產(chǎn)品對原料的混合比及其售價(jià)見表3-4，表3-4規(guī)格混合要求售價(jià)甲少于10%5.5多余50%乙少于70%5多余20%丙少于50%4.8多余100%決策者規(guī)定：首先必須嚴(yán)格按規(guī)定比例合成各規(guī)格的產(chǎn)品；其次是獲利最大；再次是甲規(guī)格的產(chǎn)品每天至少生產(chǎn)2000kg，試建立該問題的數(shù)學(xué)模型。解：設(shè)分別表示生產(chǎn)甲、乙、丙三種規(guī)格的產(chǎn)品所用材料、的數(shù)量，則該問題的數(shù)學(xué)模型為：其中：最大利潤的數(shù)學(xué)模型：例3 已知三個(gè)工廠生產(chǎn)的同一種產(chǎn)品須供應(yīng)四個(gè)客戶，各廠產(chǎn)量、各戶需量，以及廠戶間單位運(yùn)費(fèi)（元/噸）如下表3-5所示：用表上作業(yè)法試行