目標規(guī)劃目標規(guī)劃的圖解法目標規(guī)劃的單純形法目標規(guī)劃的層次算法問題的提出與目標規(guī)劃的數學模型一、問題的提出與目標規(guī)劃的數學模型(一)問題的提出

在科學研究、經濟建設和生產實踐中，人們經常遇到一類含有多個目標的數學規(guī)劃問題，我們稱之為多目標規(guī)劃。本章介紹一種特殊的多目標規(guī)劃叫目標規(guī)劃(goalprogramming)，這是美國學者Charnes等在1961年提出來的。目標規(guī)劃在實踐中的應用十分廣泛，它的重要特點是對各個目標分級加權與逐級優(yōu)化，這符合人們處理問題要分別輕重緩急保證重點的思考方式。例1、（背景材料）常山機器廠基本生產資料如下：III可用工時A2212B4016C0515單位利潤23產品設備為了便于理解目標規(guī)劃數學模型的特征及建模思路,我們首先舉一個簡單的例子來說明.

該廠過去一直以如何計劃兩種產品的生產量才能獲得最大總利潤為其生產、經營的唯一目標。然而，市場經濟環(huán)境下新的問題出現了，它迫使該廠老板不得不考慮…...（1）力求使利潤指標不低于15元；（2）考慮到市場需求，I，II兩種產品的生產量需保持1：2的比例；（3）

A為貴重設備，嚴格禁止超時使用；（4）設備C可以適當加班，但要控制；設備B既要求充分利用，又盡可能不加班，又在重要性上設備B是設備C的3倍。常山機器廠遇到的新問題討論：若把總利潤最大看作目標，而把需要滿足設備的要求看作約束，則可建立一個單目標線性規(guī)劃模型最優(yōu)解：（

3，3）,最大利潤15元。

在實際上,這個結果并非完全符合決策者的要求,它只實現了第一條目標，而沒有達到其余的目標。進一步分析：第一目標：總利潤不低于15元

第二目標：產品I、II的產量盡可能保持1：2的比例

第三目標：設備B的重要性是設備C的3倍；設備B既要求充分利用，又盡可能不加班；設備C可以適當加班。

目標規(guī)劃通過引入目標值和偏差變量，可以將目標函數轉化為目標約束。目標值：是指預先給定的某個目標的一個期望值。實現值或決策值：是指當決策變量xj

選定以后，目標函數的對應值。偏差變量（事先無法確定的未知數）：是指實現值和目標值之間的差異,記為

d

。正偏差變量：表示實現值超過目標值的部分，記為d+。負偏差變量：表示實現值未達到目標值的部分，記為d－?；靖拍睿?、目標值和偏差變量當完成或超額完成規(guī)定的指標則表示：d＋≥0,d－＝0

當未完成規(guī)定的指標則表示：d＋＝0,d－≥0

當恰好完成指標時則表示：d＋＝0,d－＝0∴d＋×d－

＝0成立。在一次決策中，實現值不可能既超過目標值又未達到目標值，故有d＋×d－

＝0,并規(guī)定d＋≥0,d－≥02、目標約束和絕對（剛性、硬）約束絕對約束是指必須嚴格滿足的等式約束和不等式約束；如在線性規(guī)劃問題中考慮的約束條件，不能滿足這些約束條件的解稱為非可行解，所以它們是硬約束。設例1中生產I，II產品必須滿足三個設備的最大可用工時限制，構成絕對約束。目標約束是目標規(guī)劃特有的，我們可以把約束右端項看作要努力追求的目標值，但允許發(fā)生正或負偏差，用在約束中加入正、負偏差變量來表示，于是稱它們是軟約束。權系數ωi

區(qū)別具有相同優(yōu)先因子的兩個目標的差別，決策者可視具體情況而定。3、優(yōu)先因子（優(yōu)先等級）與優(yōu)先權系數

對于多目標問題，設有L個目標函數f1,f2,,fL,決策者在要求達到這些目標時，一般有主次之分。為此，我們引入優(yōu)先因子Pi，i=1,2,,L.無妨設預期的目標函數優(yōu)先順序為f1,f2,,fL,我們把要求第一位達到的目標賦于優(yōu)先因子P1，次位的目標賦于優(yōu)先因子P2、…，并規(guī)定Pi>>Pi+1，i=1,2,,L-1.

4、達成函數（即目標規(guī)劃中的目標函數）目標規(guī)劃的目標函數是通過各目標約束的正、負偏差變量和賦于相應的優(yōu)先等級來構造的．

決策者的要求是盡可能從某個方向縮小偏離目標的數值。于是，目標規(guī)劃的目標函數應該是求極小：minf＝f（d

+，d-)．

其基本形式有三種：

①要求恰好達到目標值，即使相應目標約束的正、負偏差變量都要盡可能地小。這時取

min(d

++d-)；

②要求不超過目標值，即使相應目標約束的正偏差變量要盡可能地小。這時取min(d

+)；③要求不低于目標值，即使相應目標約束的負偏差變量要盡可能地小。這時取min（d

-

)；對于這種解來說，前面的目標可以保證實現或部分實現，而后面的目標就不一定能保證實現或部分實現，有些可能就不能實現。

5、滿意解（具有層次意義的解）題目有三個目標層次，包含四個目標值。第一目標：總利潤不低于15元例1、分析：

第二目標：產品I、II的產量盡可能保持1：2的比例

第三目標：設備B的重要性是設備C的3倍；設備B既要求充分利用，又盡可能不加班；設備C可以適當加班。常山機器廠的目標規(guī)劃數學模型目標約束剛性約束（二）目標規(guī)劃模型的一般形式（三）建模的步驟

1、根據要研究的問題所提出的各目標與條件，確定目標值，列出目標約束與剛性約束；

4、對同一優(yōu)先等級中的各偏差變量，若需要可按其重要程度的不同，賦予相應的權系數。

3、給各目標賦予相應的優(yōu)先因子Pk（k=1.2…K）。

2、可根據決策者的需要，將某些或全部剛性約束轉化為目標約束。這時只需要給剛性約束加上負偏差變量和減去正偏差變量即可。

5、根據決策者的要求，按下列情況之一構造一個由

優(yōu)先因子和權系數相對應的偏差變量組成的，要求實現極小化的目標函數，即達成函數。⑴恰好達到目標值，取。⑵允許超過目標值，取。⑶不允許超過目標值，取。練習：1、一個企業(yè)需要同一種原材料生產甲乙兩種產品，它們的單位產品所需要的原材料的數量及所耗費的加工時間各不相同，從而獲得的利潤也不相同（如下表）。那么，該企業(yè)應如何安排生產計劃，才能使獲得的利潤達到最大？如何安排生產，使利潤達到最大。用單純形法求得最優(yōu)解最優(yōu)值=200（百元）設甲、乙的產量分別為：數學模型為：問題：該廠提出如下目標（1）利潤達到280百元；（2）鋼材不超過100噸，工時不超過120小時；

（權數之比5：1）如何安排生產？解：第一目標：利潤達到280百元；第二目標：鋼材不超過100噸，工時不超過120小時；（權數之比5：1）數學模型：練習2：某車間有A、B兩條設備相同的生產線，它們生產同一種產品。A生產線每小時可制造2件產品，B生產線每小時可制造1.5件產品。如果每周正常工作時數為45小時，要求制定完成下列目標的生產計劃：

（1）生產量達到210件/周；（2）A生產線加班時間限制在15小時內；（3）充分利用工時指標，并依A、B產量的比例確定重要性。解：設A，B生產線每周工作時間為x1，x2。A，B的產量比例2：1.5=4:3

第一目標：生產量達到210件/周；第二目標：A生產線加班時間限制在15小時內；第三目標：充分利用工時指標，并依A、B產量的比例確定重要性。充分利用A的工時指標充分利用B的工時指標A，B的產量比例2:1.5=4:3目標函數：練習3：某電器公司經營的唱機和錄音機均有車間A、B流水作業(yè)組裝。數據見下表。要求按以下目標制訂月生產計劃：（1）庫存費用不超過4600元；（2）每月銷售唱機不少于80臺；（3）不使A、B車間停工（權數由生產費用確定）；（4）A車間加班時間限制在20小時內；（5）每月銷售錄音機為100臺；（6）兩車間加班時數總和要盡可能小（權數由生產費用確定）；圖解法同樣適用兩個變量的目標規(guī)劃問題，但其操作簡單，原理一目了然。同時，也有助于理解一般目標規(guī)劃的求解原理和過程。圖解法解題步驟如下：

1、確定各約束條件的可行域，即將所有約束條件（包括目標約束和剛性約束，暫不考慮正負偏差變量）在坐標平面上表示出來；

2、在目標約束所代表的邊界線上，用箭頭標出正、負偏差變量值增大的方向；二、目標規(guī)劃的圖解法

3、求滿足最高優(yōu)先等級目標的解；

4、轉到下一個優(yōu)先等級的目標，在不破壞所有較高優(yōu)先等級目標的前提下，求出該優(yōu)先等級目標的解；

5、重復4，直到所有優(yōu)先等級的目標都已審查完畢為止；

6、確定最優(yōu)解和滿意解。x1x204681021342x1+2x26例2x1x204681021342x1+x24x1x204681021342x1x204681021342x1x204681021342x1+2x2=105d1+d1-AB(2,2)x1x204681021342x1+2x2=105d1+d1-AB(2,2)當MinZ=d1+達到時d1+=0x1x204681021342x1+2x2=105d1-AB(2,2)當MinZ=d1+達到時d1+=0x1x204681021342x1+2x2+d1-=10d1-=25d1-AB(2,2)當MinZ=d1+達到時d1+=0x1x204681021342x1+2x2+d1-=10d1-=45d1-AB(2,2)有無窮多解：點（0，3）和點（2，2）連線上的點都是最優(yōu)解。(0,3)x1x204681021342x1+2x2+d1-=10d1-=65d1-AB(2,2)有無窮多解：點（4，0）和點（0，2）連線上的點都是最優(yōu)解。(0,3)(4,0)(0,2)x1x204681021342x1+2x2+d1-=10d1-=75d1-AB(2,2)有無窮多解：點（1，1）和點（0，3/2）（3，0）連線上的點都是最優(yōu)解。(0,3)(4,0)(1,1)例3、用圖解法求解例1中的目標規(guī)劃模型目標約束剛性約束x2

x1因為EF上的點都不能使現求在EF上的極小值。E(1.875,3.75)，F(2,4)，因為在EF上：由約束條件(4),(5)得到故F點為滿意解。四、目標規(guī)劃的單純形法目標規(guī)劃的模型實際上是求min型的線性規(guī)劃，因此，也可以用單純形法求解。在采用單純形法求解目標規(guī)劃時，檢驗數是各優(yōu)先因子的線性組合。因此，在判別各檢驗數的正負及大小時，關鍵是要注意到優(yōu)先因子的級別。當檢驗數按優(yōu)先級別從高到低已滿足最優(yōu)性條件時，且無法進一步優(yōu)化時，從單純形表上就可以得到目標規(guī)劃的最優(yōu)解或滿意解。

1、建立初始單純形表

一般假定初始解在原點，即以約束條件中的所有負偏差變量或松弛變量為初始基變量，按目標優(yōu)先等級從左至右分別計算出各列的檢驗數，填入表的下半部。（一）單純形法的計算步驟

2、確定換入基變量

在Pk行，從那些上面沒有正檢驗數的負檢驗數中，選絕對值最大者，對應的變量xs就是換入基變量。若Pk行中有幾個相同的絕對值最大者，則依次比較它們各列下部的檢驗數，取其絕對值最大的負檢驗數的所在列的xs為換入變量。

3、確定換出基變量

其方法同線性規(guī)劃，即依據最小比值法則故確定xr為換出基變量，ers為主元素。若有幾個相同的行可供選擇時，選最上面那一行所對應得變量為xr

。

4、用換入基變量替換基變量中的換出基變量，然后施行行初等變換。

5、重復以上第2步至第4步的運算，直到找到最優(yōu)解（滿意解）。

★

判斷的標準：例4：用單純形法求解下列目標規(guī)劃問題Cj

00P10

0

P1P2

0CBXBbx1x2P110101－1000004021001－100

P2

1003200001－1σkjP1

P2

51Cj

00P10

0

P1P2

0CBXBbx1x2P110101－1000004021001－100

P2

1003200001－1σkjP1

－10010100P2

－3－2000001θ=min｛10,20,100/3｝=10,故為換出變量。為換入基變量Cj

00P100

P1P2

0CBXBbx1x20x110101－1000002001－221－100

P2

7002－33001－1σkjP1

00100100P2

0－23－30001θ=min｛—,10,70/3｝=10,故為換出變量。Cj

00P100

P1P2

0CBXBbx1x20x12011/2001/2-1/20001001/2－111/2-1/200

P2

4001/200-3/23/21－1σkjP1

00100100P2

0-1/2000-3/201θ=min｛40,20,80｝=20,故為換出變量。Cj

00P100

P1P2

0CBXBbx1x20x110101-1000002001－221-100

P2

30001-1-221－1σkjP1

00100100P2

00-112-201

該問題的最優(yōu)解為四、求解目標規(guī)劃問題的層次算法例5、用層次算法求解例1中的目標規(guī)劃模型目標約束剛性約束【解】

本例P1層次的優(yōu)化模型為x1x2LP11.8753.7500008.5003.750LP21.8753.7500008.5003.750LP32.04.001.0008.0005.029每步的詳細計算結果見下表

目標規(guī)劃是在線性規(guī)劃的基礎上，為適應經濟管理中多目標決策的需要而逐步發(fā)展起來的一個分支。

2、線性規(guī)劃求最優(yōu)解；目標規(guī)劃是找到一個滿意解。

1、線性規(guī)劃只討論一個線性目標函數在一組線性約束條件下的極值問題；而目標規(guī)劃是多個目標決策，可求得更切合實際的解。小結目標規(guī)劃與線性規(guī)劃的比較

4、線性規(guī)劃的最優(yōu)解是絕對意義下的最優(yōu)，但需花去大量的人力、物力、財力才能得到；實際過程中，只要求得滿意解，就能滿足需要（或更能滿足需要）。

3、線性規(guī)劃中的約束條件是同等重要的，是硬約束；而目標規(guī)劃中有輕重緩急和主次之分，即有優(yōu)先權。目前，已經在經濟計劃、生產管理、經營管理、市場分析、財務管理等方面得到了廣泛的應用。某廠生產Ⅰ、Ⅱ兩種產品，有關數據如表所示。試求獲利最大的生產方案？ⅠⅡ擁有量原材料2111設備(臺時)1210單件利潤810在此基礎上考慮：

1、產品Ⅱ的產量不低于產品Ⅰ的產量；

2、充分利用設備有效臺時，不加班；

3、利潤不小于56元。分析：第一目標：即產品Ⅰ的產量不大于Ⅱ的產量。練習1：第二目標：充分利用設備有效臺時，不加班；第三目標：利潤不小于56元規(guī)劃模型：練習2、用圖解法求解目標規(guī)劃問題012345678123456⑴⑵⑶Ax2

x1BC

B(0.6250,4.6875)C(0,5.2083)，B、C

線段上的所有點均是該問題的解（無窮多最優(yōu)解）。練習3：用圖解法求解下列目標規(guī)劃問題⑴⑵⑶⑷CD結論：有無窮多最優(yōu)解。C（2，4）D（10/3，10/3）練習4、用單純形法求解下列目標規(guī)劃問題Cj00P100P302.5P20P2CBXBbx1x2P1250030121－1000000014021001－100000601000001－1000100010000001－1σkjP1

－30－1201000000P2

00000002.501P3

0000010000θ=min｛2500/30,140/2,60/1,--｝=60,故為換出變量。Cj

00P100P302.5P20P2CBXBbx1x2P17000121－100－30300002001001－1－22000x1601000001－1000100010000001－1σkjP1

0－12010030－3000P2

00000002.501P3

0000010000θ=min｛700/30,20/2,－,－｝=10,故為換出變量。Cj

00P100P302.5P20P2CBXBbx1x2P14000-31-1-151500002.5P21001/2001/2-1/2-11000x17011/2001/2-1/200000100010000001-1σkjP1

030115-150000P2

0-5/400-5/45/45/2001P3

0000010000θ=min｛400/15,－,－,－｝=10,故為換出變量。Cj

00P100P302.5P20P2CBXBbx1x2P380/30-1/51/15-1/15-1100002.5P270/302/51/30-1/3000-11000x1250/312/51/30-1/300000000100010000001－1σkjP1

0010000000P2

0-1-