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

1、第第 四四 章章目目 標(biāo)標(biāo) 規(guī)規(guī) 劃劃 在科學(xué)研究、經(jīng)濟(jì)建設(shè)和生產(chǎn)實(shí)踐中，人們經(jīng)常在科學(xué)研究、經(jīng)濟(jì)建設(shè)和生產(chǎn)實(shí)踐中，人們經(jīng)常遇到一類含有多個目標(biāo)的數(shù)學(xué)規(guī)劃問題，我們稱之遇到一類含有多個目標(biāo)的數(shù)學(xué)規(guī)劃問題，我們稱之為多目標(biāo)規(guī)劃。本章介紹一種特殊的多目標(biāo)規(guī)劃叫為多目標(biāo)規(guī)劃。本章介紹一種特殊的多目標(biāo)規(guī)劃叫目標(biāo)規(guī)劃目標(biāo)規(guī)劃(goal programming)，這是美國學(xué)者這是美國學(xué)者Charnes等在等在1952年提出來的。目標(biāo)規(guī)劃在實(shí)踐中的年提出來的。目標(biāo)規(guī)劃在實(shí)踐中的應(yīng)用十分廣泛，它的重要特點(diǎn)是對各個目標(biāo)分級加應(yīng)用十分廣泛，它的重要特點(diǎn)是對各個目標(biāo)分級加權(quán)與逐級優(yōu)化，這符合人們處理問題要分別輕重緩

2、權(quán)與逐級優(yōu)化，這符合人們處理問題要分別輕重緩急保證重點(diǎn)的思考方式。急保證重點(diǎn)的思考方式。 本章分目標(biāo)規(guī)劃模型、目標(biāo)規(guī)劃的幾何意義與圖本章分目標(biāo)規(guī)劃模型、目標(biāo)規(guī)劃的幾何意義與圖解法和求解目標(biāo)規(guī)劃的單純形方法等三個部分進(jìn)行解法和求解目標(biāo)規(guī)劃的單純形方法等三個部分進(jìn)行介紹。介紹。 4.1.1 問題提出問題提出 為了便于理解目標(biāo)規(guī)劃數(shù)學(xué)模型的特征及建為了便于理解目標(biāo)規(guī)劃數(shù)學(xué)模型的特征及建模思路模思路, 我們首先舉一個簡單的例子來說明我們首先舉一個簡單的例子來說明. 例例4.1.1 某公司分廠用一條生產(chǎn)線生產(chǎn)兩某公司分廠用一條生產(chǎn)線生產(chǎn)兩種產(chǎn)品種產(chǎn)品A和和B ，每周生產(chǎn)線運(yùn)行時間為每周生產(chǎn)線運(yùn)行時間為6

3、0小時，小時，生產(chǎn)一臺生產(chǎn)一臺A產(chǎn)品需要產(chǎn)品需要4小時，生產(chǎn)一臺小時，生產(chǎn)一臺B產(chǎn)品需產(chǎn)品需要要6小時根據(jù)市場預(yù)測，小時根據(jù)市場預(yù)測，A、B產(chǎn)品平均銷售產(chǎn)品平均銷售量分別為每周量分別為每周9、8臺，它們銷售利潤分別為臺，它們銷售利潤分別為12、18萬元。在制定生產(chǎn)計(jì)劃時，經(jīng)理考慮下述萬元。在制定生產(chǎn)計(jì)劃時，經(jīng)理考慮下述4項(xiàng)項(xiàng)目標(biāo)：目標(biāo)： 4.1.1 問題提出問題提出 (續(xù)續(xù))首先，產(chǎn)量不能超過市場預(yù)測的銷售量；首先，產(chǎn)量不能超過市場預(yù)測的銷售量； 其次，工人加班時間最少；其次，工人加班時間最少； 第三，希望總利潤最大；第三，希望總利潤最大； 最后，要盡可能滿足市場需求最后，要盡可能滿足市場需求

4、, 當(dāng)不能滿足時當(dāng)不能滿足時, 市場認(rèn)為市場認(rèn)為B產(chǎn)品的重要性是產(chǎn)品的重要性是A產(chǎn)品的產(chǎn)品的2倍倍 試建立這個問題的數(shù)學(xué)模型試建立這個問題的數(shù)學(xué)模型討論：討論： 若把總利潤最大看作目標(biāo)，而把產(chǎn)量不能超過市場預(yù)測若把總利潤最大看作目標(biāo)，而把產(chǎn)量不能超過市場預(yù)測4.1.1 問題提出問題提出 (續(xù)續(xù))的銷售量、工人加班時間最少和要盡可能滿足市場需求的銷售量、工人加班時間最少和要盡可能滿足市場需求的目標(biāo)看作約束，則可建立一個單目標(biāo)線性規(guī)劃模型的目標(biāo)看作約束，則可建立一個單目標(biāo)線性規(guī)劃模型 設(shè)決策變量設(shè)決策變量 x1，x2 分別為產(chǎn)品分別為產(chǎn)品A，B的產(chǎn)量的產(chǎn)量 Max Z = 12x1 + 18x2

5、s.t. 4x1 + 6x2 60 x1 9 x2 8 x1 , x2 0 4.1.1 問題提出問題提出 (續(xù)續(xù)) 容易求得上述線性規(guī)劃的最優(yōu)解為容易求得上述線性規(guī)劃的最優(yōu)解為(9,4)T 到到 (3,8)T 所所在線段上的點(diǎn)在線段上的點(diǎn), 最優(yōu)目標(biāo)值為最優(yōu)目標(biāo)值為Z* = 180, 即可選方案有即可選方案有多種多種. 實(shí)際上實(shí)際上, 這個結(jié)果并非完全符合決策者的要求這個結(jié)果并非完全符合決策者的要求, 它只實(shí)它只實(shí)現(xiàn)了經(jīng)理的第一、二、三條目標(biāo)，而沒有達(dá)到最后現(xiàn)了經(jīng)理的第一、二、三條目標(biāo)，而沒有達(dá)到最后的一個目標(biāo)。進(jìn)一步分析可知，要實(shí)現(xiàn)全體目標(biāo)是的一個目標(biāo)。進(jìn)一步分析可知，要實(shí)現(xiàn)全體目標(biāo)是不可能

6、的。不可能的。4.1.2 目標(biāo)規(guī)劃模型的基本概念目標(biāo)規(guī)劃模型的基本概念 把例把例4.1.1的的4個目標(biāo)表示為不等式個目標(biāo)表示為不等式.仍設(shè)決策變?nèi)栽O(shè)決策變量量 x1，x2 分別為產(chǎn)品分別為產(chǎn)品A，B的產(chǎn)量的產(chǎn)量. 那麼那麼, 第一個目標(biāo)為第一個目標(biāo)為: x1 9 ，x2 8 ； 第二個目標(biāo)為第二個目標(biāo)為: 4x1 + 6x2 60 ； 第三個目標(biāo)為第三個目標(biāo)為: 希望總利潤最大，要表示成不等式希望總利潤最大，要表示成不等式需要找到一個目標(biāo)上界，這里可以估計(jì)為需要找到一個目標(biāo)上界，這里可以估計(jì)為252（=12 9 + 18 8），于是有），于是有 12x1 + 18x2 252； 第四個目標(biāo)為第

7、四個目標(biāo)為: x1 9，x2 8； 4.1.2 目標(biāo)規(guī)劃模型的基本概念目標(biāo)規(guī)劃模型的基本概念 （續(xù)）（續(xù)） 下面引入與建立目標(biāo)規(guī)劃數(shù)學(xué)模型有關(guān)的概念下面引入與建立目標(biāo)規(guī)劃數(shù)學(xué)模型有關(guān)的概念 （1）、正、負(fù)偏差變量）、正、負(fù)偏差變量d +，d - 我們用正偏差變量我們用正偏差變量d + 表示決策值超過目標(biāo)值的部分；表示決策值超過目標(biāo)值的部分；負(fù)偏差變量負(fù)偏差變量d - 表示決策值不足目標(biāo)值的部分。因決表示決策值不足目標(biāo)值的部分。因決策值不可能既超過目標(biāo)值同時又末達(dá)到目標(biāo)值，故策值不可能既超過目標(biāo)值同時又末達(dá)到目標(biāo)值，故恒有恒有 d + d - 0 （2）、）、絕對約束和目標(biāo)約束絕對約束和目標(biāo)約束

8、 我們把所有等式、不等式約束分為兩部分：絕對約我們把所有等式、不等式約束分為兩部分：絕對約束和目標(biāo)約束。束和目標(biāo)約束。4.1.2 目標(biāo)規(guī)劃模型的基本概念目標(biāo)規(guī)劃模型的基本概念 （續(xù)）（續(xù)） 絕對約束是指必須嚴(yán)格滿足的等式約束和不等式約絕對約束是指必須嚴(yán)格滿足的等式約束和不等式約束。束。如在線性規(guī)劃問題中考慮的約束條件，不能滿如在線性規(guī)劃問題中考慮的約束條件，不能滿足這些約束條件的解稱為非可行解，所以它們是硬足這些約束條件的解稱為非可行解，所以它們是硬約束。設(shè)例約束。設(shè)例4.1.1 中生產(chǎn)中生產(chǎn)A，B產(chǎn)品所需原材料數(shù)量有產(chǎn)品所需原材料數(shù)量有限制，并且無法從其它渠道予以補(bǔ)充，則構(gòu)成絕對限制，并且無

9、法從其它渠道予以補(bǔ)充，則構(gòu)成絕對約束。約束。 目標(biāo)約束是目標(biāo)規(guī)劃特有的，我們可以把約束右端目標(biāo)約束是目標(biāo)規(guī)劃特有的，我們可以把約束右端項(xiàng)看作要努力追求的目標(biāo)值，但允許發(fā)生正式負(fù)偏項(xiàng)看作要努力追求的目標(biāo)值，但允許發(fā)生正式負(fù)偏差，用在約束中加入正、負(fù)偏差變量來表示，于是差，用在約束中加入正、負(fù)偏差變量來表示，于是稱它們是軟約束。稱它們是軟約束。 4.1.2 目標(biāo)規(guī)劃模型的基本概念目標(biāo)規(guī)劃模型的基本概念 （續(xù)）（續(xù)） 對于例對于例4.1.1, 我們有如下目標(biāo)約束我們有如下目標(biāo)約束 x1 + d1- -d1+ = 9 (4.1.1) x2 + d2- -d2+ = 8 (4.1.2) 4x1 + 6x

10、2 + d3- -d3+ = 60 (4.1.3) 12x1+18x2 + d4- -d4+ =252 (4.1.4)4.1.2 目標(biāo)規(guī)劃模型的基本概念目標(biāo)規(guī)劃模型的基本概念 （續(xù)）（續(xù)）(3)、優(yōu)先因子與權(quán)系數(shù)優(yōu)先因子與權(quán)系數(shù) 對于多目標(biāo)問題，設(shè)有對于多目標(biāo)問題，設(shè)有L個目標(biāo)函數(shù)個目標(biāo)函數(shù)f1,f2,fL, 決策決策者在要求達(dá)到這些目標(biāo)時，一般有主次之分。為此，者在要求達(dá)到這些目標(biāo)時，一般有主次之分。為此，我們引入優(yōu)先因子我們引入優(yōu)先因子Pi ，i = 1,2,L.無妨設(shè)預(yù)期的目無妨設(shè)預(yù)期的目標(biāo)函數(shù)優(yōu)先順序?yàn)闃?biāo)函數(shù)優(yōu)先順序?yàn)閒1,f2,fL,我們把要求第一位達(dá)到我們把要求第一位達(dá)到的目標(biāo)賦于

11、優(yōu)先因子的目標(biāo)賦于優(yōu)先因子P1，次位的目標(biāo)賦于優(yōu)先因子次位的目標(biāo)賦于優(yōu)先因子P2、，并規(guī)定并規(guī)定 Pi Pi+1，i = 1,2,L-1. 4.1.2 目標(biāo)規(guī)劃模型的基本概念目標(biāo)規(guī)劃模型的基本概念 （續(xù)）（續(xù)） 即在計(jì)算過程中即在計(jì)算過程中, 首先保證首先保證P1級目標(biāo)的實(shí)現(xiàn)，這時可級目標(biāo)的實(shí)現(xiàn)，這時可不考慮次級目標(biāo)；而不考慮次級目標(biāo)；而P2級目標(biāo)是在實(shí)現(xiàn)級目標(biāo)是在實(shí)現(xiàn)P1級目標(biāo)的基級目標(biāo)的基礎(chǔ)上考慮的，以此類推。當(dāng)需要區(qū)別具有相同優(yōu)先因礎(chǔ)上考慮的，以此類推。當(dāng)需要區(qū)別具有相同優(yōu)先因子的若干個目標(biāo)的差別時，可分別賦于它們不同的權(quán)子的若干個目標(biāo)的差別時，可分別賦于它們不同的權(quán)系數(shù)系數(shù)wj 。優(yōu)先

12、因子及權(quán)系數(shù)的值，均由決策者按具體優(yōu)先因子及權(quán)系數(shù)的值，均由決策者按具體情況來確定情況來確定 （4）、目標(biāo)規(guī)劃的目標(biāo)函效）、目標(biāo)規(guī)劃的目標(biāo)函效 目標(biāo)規(guī)劃的目標(biāo)函數(shù)是通過各目標(biāo)約束的正、負(fù)偏目標(biāo)規(guī)劃的目標(biāo)函數(shù)是通過各目標(biāo)約束的正、負(fù)偏差變量和賦于相應(yīng)的優(yōu)先等級來構(gòu)造的差變量和賦于相應(yīng)的優(yōu)先等級來構(gòu)造的4.1.2 目標(biāo)規(guī)劃模型的基本概念目標(biāo)規(guī)劃模型的基本概念 （續(xù)）（續(xù)） 決策者的要求是盡可能從某個方向縮小偏離目標(biāo)決策者的要求是盡可能從某個方向縮小偏離目標(biāo)的數(shù)值。于是，目標(biāo)規(guī)劃的目標(biāo)函數(shù)應(yīng)該是求極小：的數(shù)值。于是，目標(biāo)規(guī)劃的目標(biāo)函數(shù)應(yīng)該是求極?。簃in f f （d +，d -) 其基本形式有三種

13、：其基本形式有三種： 要求恰好達(dá)到目標(biāo)值，即使相應(yīng)目標(biāo)約束的要求恰好達(dá)到目標(biāo)值，即使相應(yīng)目標(biāo)約束的正、負(fù)偏差變量都要盡可能地小。這時取正、負(fù)偏差變量都要盡可能地小。這時取 min （d + + d - )； 要求不超過目標(biāo)值，即使相應(yīng)目標(biāo)約束的正要求不超過目標(biāo)值，即使相應(yīng)目標(biāo)約束的正偏差變量要盡可能地小。這時取偏差變量要盡可能地小。這時取 min （d + )； 4.1.2 目標(biāo)規(guī)劃模型的基本概念目標(biāo)規(guī)劃模型的基本概念 （續(xù)）（續(xù)） 要求不低于目標(biāo)值，即使相應(yīng)目標(biāo)約束的負(fù)偏差要求不低于目標(biāo)值，即使相應(yīng)目標(biāo)約束的負(fù)偏差變量要盡可能地小。這時取變量要盡可能地小。這時取 min （d - )； 對于

14、例對于例4.1.1, 我們根據(jù)決策者的考慮知我們根據(jù)決策者的考慮知 第一優(yōu)先級要求第一優(yōu)先級要求 min（d1+ + d2+ )； 第二優(yōu)先級要求第二優(yōu)先級要求 min（d3+ )； 第三優(yōu)先級要求第三優(yōu)先級要求 min（d4- )； 第四優(yōu)先級要求第四優(yōu)先級要求 min（d1- + 2d2- )，這里這里, 當(dāng)不能滿足當(dāng)不能滿足市場需求時市場需求時, 市場認(rèn)為市場認(rèn)為B產(chǎn)品的重要性是產(chǎn)品的重要性是A產(chǎn)品的產(chǎn)品的2倍即減少倍即減少B產(chǎn)品的影響是產(chǎn)品的影響是A產(chǎn)品的產(chǎn)品的2倍，因此我們引倍，因此我們引入了入了2:1的權(quán)系數(shù)。的權(quán)系數(shù)。 4.1.2 目標(biāo)規(guī)劃模型的基本概念目標(biāo)規(guī)劃模型的基本概念 （

15、續(xù)）（續(xù)）綜合上述分析，我們可得到下列目標(biāo)規(guī)劃模型綜合上述分析，我們可得到下列目標(biāo)規(guī)劃模型 Min f = P1（d1+ + d2+ ) + P2 d3+ + P3 d4- + P4（d1- + 2d2- ) s.t. x1 + d1- -d1+ = 9 x2 + d2- -d2+ = 8 4x1 + 6x2 + d3- -d3+ = 60 (4.1.5) 12x1 + 18x2 +d4- -d4+ =252 x1 , x2 , di- ,di+ 0 , i = 1,2,3,4. 4.1.3 目標(biāo)規(guī)劃模型的一般形式目標(biāo)規(guī)劃模型的一般形式 根據(jù)上面討論根據(jù)上面討論,我們可以得到目標(biāo)規(guī)劃的一般形式

16、如我們可以得到目標(biāo)規(guī)劃的一般形式如下下1111min(). .,1,2,()( , ) ,1,2,0,1,2, ,1,2,LKllkklkklknkjjkkkjnijjijjkkPddstc xddgkKLGPa xbimx ddjn kK 4.1.3 目標(biāo)規(guī)劃模型的一般形式目標(biāo)規(guī)劃模型的一般形式 (續(xù)續(xù))（LGP）中的第二行是中的第二行是K個目標(biāo)約束，第三行是個目標(biāo)約束，第三行是m個絕對約束，個絕對約束，ckj 和和gk 是目標(biāo)參數(shù)。是目標(biāo)參數(shù)。4.2 目標(biāo)規(guī)劃的幾何意義及圖解法目標(biāo)規(guī)劃的幾何意義及圖解法 對只具有兩個決策變量的目標(biāo)規(guī)劃的數(shù)學(xué)對只具有兩個決策變量的目標(biāo)規(guī)劃的數(shù)學(xué)模型，我們可以

17、用圖解法來分析求解通過模型，我們可以用圖解法來分析求解通過圖解示例，可以看到目標(biāo)規(guī)劃中優(yōu)先因子，圖解示例，可以看到目標(biāo)規(guī)劃中優(yōu)先因子，正、負(fù)偏差變量及權(quán)系數(shù)等的幾何意義。正、負(fù)偏差變量及權(quán)系數(shù)等的幾何意義。 下面用圖解法來求解例下面用圖解法來求解例4.1.1 我們先在平面直角坐標(biāo)系的第一象限內(nèi)，我們先在平面直角坐標(biāo)系的第一象限內(nèi)，作出與各約束條件對應(yīng)的直線，然后在這些直作出與各約束條件對應(yīng)的直線，然后在這些直線旁分別標(biāo)上線旁分別標(biāo)上 G-i ，i = 1，2，3，4。圖中圖中x，y分別表示問題（分別表示問題（7.1.5）的）的x1和和x2；各直線移動各直線移動使之函數(shù)值變大、變小的方向用使之函

18、數(shù)值變大、變小的方向用 +、- 表示表示 di+ ,di- （如圖如圖4.1.1所示）所示） 下面我們根據(jù)目標(biāo)函數(shù)的優(yōu)先因子來分析求下面我們根據(jù)目標(biāo)函數(shù)的優(yōu)先因子來分析求解首先考慮第一級具有解首先考慮第一級具有P1優(yōu)先因子的目標(biāo)的實(shí)現(xiàn)，優(yōu)先因子的目標(biāo)的實(shí)現(xiàn)，在目標(biāo)函數(shù)中要求實(shí)現(xiàn)在目標(biāo)函數(shù)中要求實(shí)現(xiàn)min（d1+ d2+ ),取取d1+=d2+ =0.圖圖 4 2 中陰影部分即表示出該最優(yōu)解集合的所有點(diǎn)。中陰影部分即表示出該最優(yōu)解集合的所有點(diǎn)。 我們在第一級目標(biāo)的最優(yōu)解集合中找滿足第二優(yōu)我們在第一級目標(biāo)的最優(yōu)解集合中找滿足第二優(yōu)先級要求先級要求min（d3+ )的最優(yōu)解的最優(yōu)解.取取d3+= 0

19、 ,可得到圖可得到圖 4 3 中陰影部分即是滿足第一、第二優(yōu)先級要求的最中陰影部分即是滿足第一、第二優(yōu)先級要求的最優(yōu)解集合。優(yōu)解集合。 圖4 - 20 5 10 15 20 yx2015105+-G-1+-G-2-+G-4+-G-3A(3,8)圖4 3 0 5 10 15 20 yx2015105+-G-1+-G-2-+G-4+-G-3A(3,8)第三優(yōu)先級要求第三優(yōu)先級要求 min（d4- )，根據(jù)圖示可知，根據(jù)圖示可知，d4- 不可不可能取能取0值，我們?nèi)∈怪?，我們?nèi)∈筪4- 最小的值最小的值72得到圖得到圖44 中兩陰中兩陰影部分的交線影部分的交線(黑色粗線黑色粗線)，其表示滿足第一、第

20、二及，其表示滿足第一、第二及第三優(yōu)先級要求的最優(yōu)解集合。第三優(yōu)先級要求的最優(yōu)解集合。最后，考慮第四優(yōu)先級要求最后，考慮第四優(yōu)先級要求 min（d1- + 2d2- ) ，即要在即要在黑色粗線段中找出最優(yōu)解。由于黑色粗線段中找出最優(yōu)解。由于d1- 的權(quán)因子小于的權(quán)因子小于d2- ，因此在這里可以考慮取因此在這里可以考慮取d2- =0。于是解得于是解得d1-=5，最優(yōu)最優(yōu)解為解為A點(diǎn)點(diǎn)x = 3，y = 8。 圖4 4 0 5 10 15 20 yx2015105+-G-1+-G-2-+G-4+-G-3A(3,8)基本思想：基本思想：遵循優(yōu)先級的次序，將目標(biāo)規(guī)劃模型依次分解為遵循優(yōu)先級的次序，將目

21、標(biāo)規(guī)劃模型依次分解為一系列的單目標(biāo)線性規(guī)劃問題分別求解。一系列的單目標(biāo)線性規(guī)劃問題分別求解。以例以例4.1.1為例，目標(biāo)規(guī)劃模型為：為例，目標(biāo)規(guī)劃模型為： Min f = P1（d1+ + d2+ ) + P2 d3+ + P3 d4- + P4（d1- + 2d2- ) s.t. x1 + d1- -d1+ = 9 x2 + d2- -d2+ = 8 4x1 + 6x2 + d3- -d3+ = 60 12x1 + 18x2 +d4- -d4+ =252 x1 , x2 , di- ,di+ 0 , i = 1,2,3,4. step1:求解第一優(yōu)先級對應(yīng)的模型求解第一優(yōu)先級對應(yīng)的模型 Mi

22、n f = d1+ + d2+ s.t. x1 + d1- -d1+ = 9 x2 + d2- -d2+ = 8 x1 , x2 , di- ,di+ 0 , i = 1,2. 0 5 10 15 20 yx2015105+-G-1+-G-2-+G-4+-G-3A(3,8)求得求得d1+d2+=0Step2 求解第二優(yōu)先級目標(biāo)模型求解第二優(yōu)先級目標(biāo)模型 Min f = d3+ s.t. x1 + d1- -d1+ = 9 x2 + d2- -d2+ = 8 4x1 + 6x2 + d3- -d3+ = 60 d1+ + d2+ = 0 x1 , x2 , di- ,di+ 0 , i = 1,

23、2,3. 0 5 10 15 20 yx2015105+-G-1+-G-2-+G-4+-G-3A(3,8)求得求得d3+=0Step3 求解第三優(yōu)先級目標(biāo)模型求解第三優(yōu)先級目標(biāo)模型 Min f = d4- s.t. x1 + d1- -d1+ = 9 x2 + d2- -d2+ = 8 4x1 + 6x2 + d3- -d3+ = 60 12x1 + 18x2 +d4- -d4+ =252 d1+ + d2+= 0 d3+= 0 x1 , x2 , di- ,di+ 0 , i = 1,2,3,4.0 5 10 15 20 yx2015105+-G-1+-G-2-+G-4+-G-3A(3,8)

24、求得求得d4-=72Step4 求解第四個目標(biāo)求解第四個目標(biāo) Min f = d1- + 2d2- s.t. x1 + d1- -d1+ = 9 x2 + d2- -d2+ = 8 4x1 + 6x2 + d3- -d3+ = 60 12x1 + 18x2 +d4- -d4+ =252 d1+ + d2+= 0 d3+= 0 d4-=72 x1 , x2 , di- ,di+ 0 , i = 1,2,3,4.由于d1- 的權(quán)因子小于d2- ，因此在這里可以考慮取d2- =0。于是解得d1- = 5，最優(yōu)解為A點(diǎn)x = 3，y = 8。 目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃的數(shù)學(xué)模型,特別是約束的結(jié)構(gòu)與線

25、性特別是約束的結(jié)構(gòu)與線性規(guī)劃模型沒有本質(zhì)的區(qū)別，只是它的目標(biāo)不止是一規(guī)劃模型沒有本質(zhì)的區(qū)別，只是它的目標(biāo)不止是一個個,雖然其利用優(yōu)先因子和權(quán)系數(shù)把目標(biāo)寫成一個函雖然其利用優(yōu)先因子和權(quán)系數(shù)把目標(biāo)寫成一個函數(shù)的形式數(shù)的形式, 但在計(jì)算中無法按單目標(biāo)處理但在計(jì)算中無法按單目標(biāo)處理, 所以可用所以可用單純形法進(jìn)行適當(dāng)改進(jìn)后求解。在組織、構(gòu)造算法單純形法進(jìn)行適當(dāng)改進(jìn)后求解。在組織、構(gòu)造算法時，我們要考慮目標(biāo)規(guī)劃的數(shù)學(xué)模型一些特點(diǎn)，作時，我們要考慮目標(biāo)規(guī)劃的數(shù)學(xué)模型一些特點(diǎn)，作以下規(guī)定：以下規(guī)定： (1) 因?yàn)槟繕?biāo)規(guī)劃問題的目標(biāo)函數(shù)都是求最小化，因?yàn)槟繕?biāo)規(guī)劃問題的目標(biāo)函數(shù)都是求最小化，所以檢驗(yàn)數(shù)的最優(yōu)準(zhǔn)則

26、與線性規(guī)劃是相同的；所以檢驗(yàn)數(shù)的最優(yōu)準(zhǔn)則與線性規(guī)劃是相同的； (2) 因?yàn)榉腔兞康臋z驗(yàn)數(shù)中含有不同等級的優(yōu)先因因?yàn)榉腔兞康臋z驗(yàn)數(shù)中含有不同等級的優(yōu)先因子，子， Pi Pi+1，i = 1,2,L-1. 于是從每個檢驗(yàn)數(shù)的整體于是從每個檢驗(yàn)數(shù)的整體來看：來看： Pi+1（i = 1,2,L-1）優(yōu)先級第優(yōu)先級第k個檢驗(yàn)數(shù)的正、個檢驗(yàn)數(shù)的正、負(fù)首先決定于負(fù)首先決定于 P1 ，P2 ， ，Pi 優(yōu)先級第優(yōu)先級第k個檢驗(yàn)數(shù)的個檢驗(yàn)數(shù)的正、負(fù)。若正、負(fù)。若P1 級第級第k個檢驗(yàn)數(shù)為個檢驗(yàn)數(shù)為0，則此檢驗(yàn)數(shù)的正、負(fù)，則此檢驗(yàn)數(shù)的正、負(fù)取決于取決于P2級第級第k個檢驗(yàn)數(shù)；若個檢驗(yàn)數(shù)；若P2 級第級第k個

27、檢驗(yàn)數(shù)仍為個檢驗(yàn)數(shù)仍為0，則此檢驗(yàn)數(shù)的正、負(fù)取決于則此檢驗(yàn)數(shù)的正、負(fù)取決于P3級第級第k個檢驗(yàn)數(shù)，依次類個檢驗(yàn)數(shù)，依次類推。換一句話說，當(dāng)某推。換一句話說，當(dāng)某Pi 級第級第k個檢驗(yàn)數(shù)為負(fù)數(shù)時，計(jì)個檢驗(yàn)數(shù)為負(fù)數(shù)時，計(jì)算中不必再考察算中不必再考察Pj（ j I ）級第級第k個檢驗(yàn)數(shù)的正、負(fù)情個檢驗(yàn)數(shù)的正、負(fù)情況；況； （3）根據(jù)（）根據(jù)（LGP）模型特征，當(dāng)不含絕對約束時，模型特征，當(dāng)不含絕對約束時，di- （i=1,2, ,K）構(gòu)成了一組基本可行解。在尋找單純形構(gòu)成了一組基本可行解。在尋找單純形法初始可行點(diǎn)時，這個特點(diǎn)是很有用的。法初始可行點(diǎn)時，這個特點(diǎn)是很有用的。 解目標(biāo)規(guī)劃問題的單純形法的

28、計(jì)算步驟解目標(biāo)規(guī)劃問題的單純形法的計(jì)算步驟 (1)建立初始單純形表在表中將檢驗(yàn)數(shù)行按優(yōu)先因建立初始單純形表在表中將檢驗(yàn)數(shù)行按優(yōu)先因子個數(shù)分別列成子個數(shù)分別列成K行。初始的檢驗(yàn)數(shù)需根據(jù)初始可行行。初始的檢驗(yàn)數(shù)需根據(jù)初始可行解計(jì)算出來，方法同基本單純形法。當(dāng)不含絕對約束解計(jì)算出來，方法同基本單純形法。當(dāng)不含絕對約束時，時，di- （i=1,2, ,K）構(gòu)成了一組基本可行解，這時構(gòu)成了一組基本可行解，這時只需利用相應(yīng)單位向量把各級目標(biāo)行中對應(yīng)只需利用相應(yīng)單位向量把各級目標(biāo)行中對應(yīng)di- （i=1,2, ,K）的量消成的量消成0即可得到初始單純形表。置即可得到初始單純形表。置k 1； (2)檢查當(dāng)前第

29、檢查當(dāng)前第k行中是否存在大于行中是否存在大于0，且對應(yīng)，且對應(yīng)的前的前k-1行的同列檢驗(yàn)數(shù)為零的檢驗(yàn)數(shù)。若有取行的同列檢驗(yàn)數(shù)為零的檢驗(yàn)數(shù)。若有取其中最大者對應(yīng)的變量為換入變量，轉(zhuǎn)其中最大者對應(yīng)的變量為換入變量，轉(zhuǎn)(3)。若。若無這樣的檢驗(yàn)數(shù)，則轉(zhuǎn)無這樣的檢驗(yàn)數(shù)，則轉(zhuǎn)(5)； (3)按單純形法中的最小比值規(guī)則確定換出變按單純形法中的最小比值規(guī)則確定換出變量，當(dāng)存在兩個和兩個以上相同的最小比值時，量，當(dāng)存在兩個和兩個以上相同的最小比值時，選取具有較高優(yōu)先級別的變量為換出變量，轉(zhuǎn)選取具有較高優(yōu)先級別的變量為換出變量，轉(zhuǎn)（4）；）； (4)按單純形法進(jìn)行基變換運(yùn)算，建立新的按單純形法進(jìn)行基變換運(yùn)算，建

30、立新的單純形表，（注意：要對所有的行進(jìn)行轉(zhuǎn)軸單純形表，（注意：要對所有的行進(jìn)行轉(zhuǎn)軸運(yùn)算）返回運(yùn)算）返回(2)； (5)當(dāng)當(dāng)k K 時，計(jì)算結(jié)束。表中的解即為時，計(jì)算結(jié)束。表中的解即為滿意解。否則置滿意解。否則置k = k+1，返回（返回（2）。）。 例例4.4.1 試用單純形法來求解例試用單純形法來求解例4.1.1的目標(biāo)規(guī)劃的目標(biāo)規(guī)劃模型模型(4.1.5) Min f = P1（d1+ + d2+ ) + P2 d3+ + P3 d4- + P4（d1- + 2d2- ) s.t. x1 + d1- -d1+ = 9 x2 + d2- -d2+ = 8 4x1 + 6x2 + d3- -d3+

31、 = 60 12x1 + 18x2 +d4- -d4+ =252 x1 , x2 , di- ,di+ 0 , i = 1,2,3,4. 解解: 首先處理初始基本可行解對應(yīng)的各級檢驗(yàn)首先處理初始基本可行解對應(yīng)的各級檢驗(yàn)數(shù)。數(shù)。 由于由于P1 , P2 優(yōu)先級對應(yīng)的目標(biāo)函數(shù)中不含優(yōu)先級對應(yīng)的目標(biāo)函數(shù)中不含di- , 所以其檢驗(yàn)數(shù)只需取系數(shù)負(fù)值。分別為所以其檢驗(yàn)數(shù)只需取系數(shù)負(fù)值。分別為 ( 0，0，0，-1，0，-1，0，0，0，0 ；0)和和 ( 0，0，0， 0，0，0，0，-1，0，0 ；0) x1x2d1-d1+d2-d2+d3-d3+d4-d4+RHS P1000-10-100000 P

32、20000000-1000 P300000000-100 P400-10-2000000 d1-101-10000009 d2-01001-100008d3-4600001-10060d4-12180000001-1252 x1x2d1-d1+d2-d2+d3-d3+d4-d4+RHS P1000-10-100000 P20000000-1000 P312180000000-1252 P400-10-2000000 d1-101-10000009 d2-0*1001-100008d3-4600001-10060d4-12180000001-1252P3 優(yōu)先級對應(yīng)的目標(biāo)函數(shù)中含優(yōu)先級對應(yīng)的目標(biāo)

33、函數(shù)中含d4- ,所以其檢驗(yàn)數(shù)所以其檢驗(yàn)數(shù)需要把第四個約束行加到取負(fù)值的這一行上，需要把第四個約束行加到取負(fù)值的這一行上，得到得到 ( -12，-18，0，0，0，0，0，0，0，1；-252 )TP4 優(yōu)先級對應(yīng)的目標(biāo)函數(shù)中含（優(yōu)先級對應(yīng)的目標(biāo)函數(shù)中含（d1- + 2d2- )，所所以其檢驗(yàn)數(shù)需要把第一個約束行與第二個約以其檢驗(yàn)數(shù)需要把第一個約束行與第二個約束行的束行的2倍加到取系數(shù)負(fù)值的這一行上，得到倍加到取系數(shù)負(fù)值的這一行上，得到 ( -1，-2，0，1，0，2，0，0，0，0；-25 )。列目標(biāo)規(guī)劃的初始單純形表列目標(biāo)規(guī)劃的初始單純形表 x1x2d1-d1+d2-d2+d3-d3+d4-d4+RHS P10001010000