目標規(guī)劃及目標規(guī)劃模型課件

目標規(guī)劃目標規(guī)劃1

在科學研究、經濟建設和生產實踐中，人們經常遇到一類含有多個目標的數學規(guī)劃問題，我們稱之為多目標規(guī)劃。本章介紹一種特殊的多目標規(guī)劃叫目標規(guī)劃(goalprogramming)，這是美國學者Charnes等在1952年提出來的。目標規(guī)劃在實踐中的應用十分廣泛，它的重要特點是對各個目標分級加權與逐級優(yōu)化，這符合人們處理問題要分別輕重緩急保證重點的思考方式。本章分目標規(guī)劃模型、目標規(guī)劃的幾何意義與圖解法和求解目標規(guī)劃的單純形方法等三個部分進行介紹。

在科學研究、經濟建設和生產實踐中，人們22.1目標規(guī)劃模型

2.1.1問題提出

為了便于理解目標規(guī)劃數學模型的特征及建模思路,我們首先舉一個簡單的例子來說明.

例2.1.1某公司分廠用一條生產線生產兩種產品A和B，每周生產線運行時間為60小時，生產一臺A產品需要4小時，生產一臺B產品需要6小時．根據市場預測，A、B產品平均銷售量分別為每周9、8臺，它們銷售利潤分別為12、18萬元。在制定生產計劃時，經理考慮下述4項目標：

2.1目標規(guī)劃模型2.1.1問題提32.1目標規(guī)劃模型2.1.1問題提出(續(xù))首先，產量不能超過市場預測的銷售量；其次，工人加班時間最少；第三，希望總利潤最大；最后，要盡可能滿足市場需求,當不能滿足時,市場認為B產品的重要性是A產品的2倍．試建立這個問題的數學模型．討論：

若把總利潤最大看作目標，而把產量不能超過市場預測的銷售量、工人加班時間最少和要盡可能滿2.1目標規(guī)劃模型2.1.1問題提出(續(xù))42.1目標規(guī)劃模型

2.1.1問題提出(續(xù))足市場需求的目標看作約束，則可建立一個單目標線性規(guī)劃模型

設決策變量x1，x2

分別為產品A，B的產量

MaxZ=12x1+18x2

s.t.4x1+6x260

x1

9

x28

x1,x20

2.1目標規(guī)劃模型2.1.1問題提出(續(xù))52.1目標規(guī)劃模型2.1.1問題提出(續(xù))容易求得上述線性規(guī)劃的最優(yōu)解為(9,4)T

到(3,8)T

所在線段上的點,最優(yōu)目標值為Z*=180,即可選方案有多種.在實際上,這個結果并非完全符合決策者的要求,它只實現了經理的第一、二、三條目標，而沒有達到最后的一個目標。進一步分析可知，要實現全體目標是不可能的。2.1目標規(guī)劃模型2.1.1問題提出(續(xù))62.1目標規(guī)劃模型2.1.2目標規(guī)劃模型的基本概念把例2.1.1的4個目標表示為不等式.仍設決策變量x1，x2

分別為產品A，B的產量.那麼,第一個目標為:x19，x28；

第二個目標為:4x1+6x260；

第三個目標為:希望總利潤最大，要表示成不等式需要找到一個目標上界，這里可以估計為252（=129+188），于是有12x1+18x2

252；

第四個目標為:x1

9，x2

8；

2.1目標規(guī)劃模型2.1.2目標規(guī)劃模型的基本概念7

2.1.2目標規(guī)劃模型的基本概念（續(xù)）下面引入與建立目標規(guī)劃數學模型有關的概念．

（1）、正、負偏差變量d

+，d-

我們用正偏差變量d

+表示決策值超過目標值的部分；負偏差變量d-表示決策值不足目標值的部分。因決策值不可能既超過目標值同時又未達到目標值，故恒有d

+d-＝0．

（2）、絕對約束和目標約束我們把所有等式、不等式約束分為兩部分：絕對約束和目標約束。2.1.2目標規(guī)劃模型的基本概念（續(xù)）82.1.2目標規(guī)劃模型的基本概念（續(xù)）絕對約束是指必須嚴格滿足的等式約束和不等式約束；如在線性規(guī)劃問題中考慮的約束條件，不能滿足這些約束條件的解稱為非可行解，所以它們是硬約束。設例2.1.1中生產A，B產品所需原材料數量有限制，并且無法從其它渠道予以補充，則構成絕對約束。目標約束是目標規(guī)劃特有的，我們可以把約束右端項看作要努力追求的目標值，但允許發(fā)生正式負偏差，用在約束中加入正、負偏差變量來表示，于是稱它們是軟約束。2.1.2目標規(guī)劃模型的基本概念（續(xù)）92.1目標規(guī)劃模型

2.1.2目標規(guī)劃模型的基本概念（續(xù)）

對于例2.1.1,我們有如下目標約束

x1

+d1--d1+=9(2.1.1)

x2+d2--d2+=8(2.1.2)

4x1+6x2

+d3--d3+=60(2.1.3)

12x1+18x2

+d4--d4+=252(2.1.4)2.1目標規(guī)劃模型2.1.2目標規(guī)劃模型的基本概102.1目標規(guī)劃模型2.1.2目標規(guī)劃模型的基本概念（續(xù)）(3)、優(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.2.1目標規(guī)劃模型2.1.2目標規(guī)劃模型的基本概念（續(xù)11

2.1.2目標規(guī)劃模型的基本概念（續(xù)）

即在計算過程中,首先保證P1級目標的實現，這時可不考慮次級目標；而P2級目標是在實現P1級目標的基礎上考慮的，以此類推。當需要區(qū)別具有相同優(yōu)先因子的若干個目標的差別時，可分別賦于它們不同的權系數wj。優(yōu)先因子及權系數的值，均由決策者按具體情況來確定．（4）、目標規(guī)劃的目標函效．目標規(guī)劃的目標函數是通過各目標約束的正、負偏差變量和賦于相應的優(yōu)先等級來構造的．2.1.2目標規(guī)劃模型的基本概念（續(xù)）12§2.1目標規(guī)劃模型2.1.2目標規(guī)劃模型的基本概念（續(xù)）決策者的要求是盡可能從某個方向縮小偏離目標的數值。于是，目標規(guī)劃的目標函數應該是求極?。簃inf＝f（d

+，d-)．其基本形式有三種：

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

++d-)；

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

+)；§2.1目標規(guī)劃模型2.1.2目標規(guī)劃模型的基本概念（13

2.1.2目標規(guī)劃模型的基本概念（續(xù)）③要求不低于目標值，即使相應目標約束的負偏差變量要盡可能地小。這時取min（d

-)；對于例2.1.1,我們根據決策者的考慮知第一優(yōu)先級要求min（d1++d2+)；

第二優(yōu)先級要求min（d3+)；

第三優(yōu)先級要求min（d4-)；第四優(yōu)先級要求min（d1-+2d2-)，這里,當不能滿足市場需求時,市場認為B產品的重要性是A產品的2倍．即減少B產品的影響是A產品的2倍，因此我們引入了2:1的權系數。

2.1.2目標規(guī)劃模型的基本概念（續(xù)）14§2.1目標規(guī)劃模型

2.1.2目標規(guī)劃模型的基本概念（續(xù)）綜合上述分析，我們可得到下列目標規(guī)劃模型

Minf=P1（d1++d2+)+P2d3++P3d4-+P4（d1-+2d2-)

s.t.x1

+d1--d1+=9

x2+d2--d2+=8

4x1+6x2

+d3--d3+=60(2.1.5)

12x1+18x2

+d4--d4+=252

x1,x2

,di-,di+0,i=1,2,3,4.

§2.1目標規(guī)劃模型2.1.2目標規(guī)劃模型的基本15§2.1目標規(guī)劃模型2.1.3目標規(guī)劃模型的一般形式

根據上面討論,我們可以得到目標規(guī)劃的一般形式如下§2.1目標規(guī)劃模型2.1.3目標規(guī)劃模型的一般形式16§2.1目標規(guī)劃模型2.1.3目標規(guī)劃模型的一般形式(續(xù))（LGP）中的第二行是K個目標約束，第三行是m個絕對約束，ckj

和gk

是目標參數?！?.2目標規(guī)劃的幾何意義及圖解法

對只具有兩個決策變量的目標規(guī)劃的數學模型，我們可以用圖解法來分析求解．通過圖解示例，可以看到目標規(guī)劃中優(yōu)先因子，正、負偏差變量及權系數等的幾何意義。

§2.1目標規(guī)劃模型2.1.3目標規(guī)劃模型的一般形式(17§2.2目標規(guī)劃的幾何意義及圖解法§2.2目標規(guī)劃的幾何意義及圖解法（續(xù)）下面用圖解法來求解例2.1.1

我們先在平面直角坐標系的第一象限內，作出與各約束條件對應的直線，然后在這些直線旁分別標上G-i，i=1，2，3，4。圖中x，y分別表示問題（2.1.5）的x1和x2；各直線移動使之函數值變大、變小的方向用+、-表示di+,di-（如圖2.1.1所示）．

§2.2目標規(guī)劃的幾何意義及圖解法§2.2目標規(guī)劃的幾何意18§2.2目標規(guī)劃的幾何意義及圖解法05101520y

x2015105+-G-1+-G-2+-G-4+-G-3圖2-1§2.2目標規(guī)劃的幾何意義及圖解法0519§2.2目標規(guī)劃的幾何意義及圖解法下面我們根據目標函數的優(yōu)先因子來分析求解．首先考慮第一級具有P1優(yōu)先因子的目標的實現，在目標函數中要求實現min（d1++d2+),取d1+=d2+=0.圖2–2中陰影部分即表示出該最優(yōu)解集合的所有點。

我們在第一級目標的最優(yōu)解集合中找滿足第二優(yōu)先級要求min（d3+)的最優(yōu)解.取d3+=0

,可得到圖2–3中陰影部分即是滿足第一、第二優(yōu)先級要求的最優(yōu)解集合。

§2.2目標規(guī)劃的幾何意義及圖解法下面我們20§2.2目標規(guī)劃的幾何意義及圖解法圖2-205101520yx2015105+-G-1+-G-2-+G-4+-G-3A(3,8)§2.2目標規(guī)劃的幾何意義及圖解法圖2-2021§2.2目標規(guī)劃的幾何意義及圖解法圖2–305101520yx2015105+-G-1+-G-2-+G-4+-G-3A(3,8)§2.2目標規(guī)劃的幾何意義及圖解法圖2–3022§2.2目標規(guī)劃的幾何意義及圖解法

第三優(yōu)先級要求min（d4-)，根據圖示可知，d4-不可能取0值，我們取使d4-最小的值72得到圖2–4中兩陰影部分的交線(紅色粗線)，其表示滿足第一、第二及第三優(yōu)先級要求的最優(yōu)解集合。最后，考慮第四優(yōu)先級要求min（d1-+2d2-)，即要在黑色粗線段中找出最優(yōu)解。由于d1-的權因子小于d2-，因此在這里可以考慮取d2-=0。于是解得d1-=5，最優(yōu)解為A點x=3，y=8。

§2.2目標規(guī)劃的幾何意義及圖解法第三優(yōu)先級要求min23§2.2目標規(guī)劃的幾何意義及圖解法圖2–405101520yx2015105+-G-1+-G-2-+G-4+-G-3A(3,8)§2.2目標規(guī)劃的幾何意義及圖解法圖2–4024§2.3求解目標規(guī)劃的單純形方法

目標規(guī)劃的數學模型,特別是約束的結構與線性規(guī)劃模型沒有本質的區(qū)別，只是它的目標不止是一個,雖然其利用優(yōu)先因子和權系數把目標寫成一個函數的形式,但在計算中無法按單目標處理,所以可用單純形法進行適當改進后求解。在組織、構造算法時，我們要考慮目標規(guī)劃的數學模型一些特點，作以下規(guī)定：(1)因為目標規(guī)劃問題的目標函數都是求最小化，所以檢驗數的最優(yōu)準則與線性規(guī)劃是相同的；§2.3求解目標規(guī)劃的單純形方法目標規(guī)25§2.3求解目標規(guī)劃的單純形方法(續(xù))

(2)因為非基變量的檢驗數中含有不同等級的優(yōu)先因子，Pi>>Pi+1，i=1,2,,L-1.于是從每個檢驗數的整體來看：Pi+1（i=1,2,,L-1）優(yōu)先級第k個檢驗數的正、負首先決定于P1

，P2，…，Pi

優(yōu)先級第k個檢驗數的正、負。若P1

級第k個檢驗數為0，則此檢驗數的正、負取決于P2級第k個檢驗數；若P2

級第k個檢驗數仍為0，則此檢驗數的正、負取決于P3級第k個檢驗數，依次類推。換一句話說，當某Pi級第k個檢驗數為負數時，計算中不必再考察Pj（j>I）級第k個檢驗數的正、負情況；

§2.3求解目標規(guī)劃的單純形方法(續(xù))26§2.3求解目標規(guī)劃的單純形方法(續(xù))（3）根據（LGP）模型特征，當不含絕對約束時，di-（i=1,2,…,K）構成了一組基本可行解。在尋找單純形法初始可行點時，這個特點是很有用的。解目標規(guī)劃問題的單純形法的計算步驟

(1)建立初始單純形表．在表中將檢驗數行按優(yōu)先因子個數分別列成K行。初始的檢驗數需根據初始可行解計算出來，方法同基本單純形法。當不含絕對約束時，di-（i=1,2,…,K）構成了一組基本可行解，這時只需利用相應單位向量把各級目標行中對應di-（i=1,2,…,K）的量消成0即可得到初始單純形表。置k＝1；

§2.3求解目標規(guī)劃的單純形方法(續(xù))（3）根據（LGP27§2.3求解目標規(guī)劃的單純形方法(續(xù))(2)檢查當前第k行中是否存在大于0，且對應的前k-1行的同列檢驗數為零的檢驗數。若有取其中最大者對應的變量為換入變量，轉(3)。若無這樣的檢驗數，則轉(5)；(3)按單純形法中的最小比值規(guī)則確定換出變量，當存在兩個和兩個以上相同的最小比值時，選取具有較高優(yōu)先級別的變量為換出變量，轉（4）；

§2.3求解目標規(guī)劃的單純形方法(續(xù))(228§2.3求解目標規(guī)劃的單純形方法(續(xù))(4)按單純形法進行基變換運算，建立新的單純形表，（注意：要對所有的行進行轉軸運算）返回(2)；(5)當k＝K時，計算結束。表中的解即為滿意解。否則置k=k+1，返回（2）。

§2.3求解目標規(guī)劃的單純形方法(續(xù))(29§2.3求解目標規(guī)劃的單純形方法(續(xù))例2.3.1試用單純形法來求解例2.1.1的目標規(guī)劃模型(2.1.5)

Minf=P1（d1++d2+)+P2d3++P3d4-+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.

§2.3求解目標規(guī)劃的單純形方法(續(xù))例2.3.1試用30§2.3求解目標規(guī)劃的單純形方法(續(xù))解:首先處理初始基本可行解對應的各級檢驗數。由于P1,P2

優(yōu)先級對應的目標函數中不含di-,所以其檢驗數只需取系數負值。分別為(0，0，0，-1，0，-1，0，0，0，0；0)和(0，0，0，0，0，0，0，-1，0，0；0)

§2.3求解目標規(guī)劃的單純形方法(續(xù))解:31

x1x2d1-d1+d2-d2+d3-d3+d4-d4+RHSP1000-10-100000

P20000000-1000

P300000000-100

P400-10-2000000

d1-101-10000009

d2-01001-100008d3-4600001-10060d4-12180000001-1252

x1x2d1-d1+d2-d2+d3-d3+d4-d4+32

x1x2d1-d1+d2-d2+d3-d3+d4-d4+RHSP1000-10-100000

P20000000-1000

P312180000000-1252

P400-10-2000000

d1-101-10000009

d2-0*1001-100008d3-4600001-10060d4-12180000001-1252

x1x2d1-d1+d2-d2+d3-d3+d4-d4+33§2.3求解目標規(guī)劃的單純形方法(續(xù))P3

優(yōu)先級對應的目標函數中含d4-,所以其檢驗數需要把第四個約束行加到取負值的這一行上，得到(12，18，0，0，0，0，0，0，0，-1；252)TP4

優(yōu)先級對應的目標函數中含（d1-+2d2-)，所以其檢驗數需要把第一個約束行與第二個約束行的2倍加到取系數負值的這一行上，得到(1，2，0，-1，0，-2，0，0，0，0；25)。列目標規(guī)劃的初始單純形表

§2.3求解目標規(guī)劃的單純形方法(續(xù))P3優(yōu)先級對應的34

x1x2d1-d1+d2-d2+d3-d3+d4-d4+RHSP1000-10-100000

P20000000-1000

P312180000000-1252

P4120-10-2000025

d1-101-10000009

d2-0*1001-1000088d3-4600001-1006010d4-12180000001-125214

x1x2d1-d1+d2-d2+d3-d3+d4-d4+35§2.3求解目標規(guī)劃的單純形方法(續(xù))（1）k=1，在初始單純形表中基變量為（d1-,d2-,d3-,d4-)T=（9，8,60，252)T；（2）因為P1與P2優(yōu)先級的檢驗數均已經為非正，所以這個單純形表對P1與P2優(yōu)先級是最優(yōu)單純形表；（3）下面考慮P3優(yōu)先級，第二列的檢驗數為18，此為進基變量，計算相應的比值bi/aij

寫在列。通過比較，得到d2-

對應的比值最小，于是取a22（標為*號）為轉軸元進行矩陣行變換得到新的單純形表；

§2.3求解目標規(guī)劃的單純形方法(續(xù))（1）k=1，36

x1x2d1-d1+d2-d2+d3-d3+d4-d4+RHSP1000-10-100000

P20000000-1000

P312000-1818000-1108

P4100-1-2000009

d1-101-100000099x201001-100008

d3-*4000-661-100123d4-12000-1818001-11089

x1x2d1-d1+d2-d2+d3-d3+d4-d4+37§2.3求解目標規(guī)劃的單純形方法(續(xù))（4）下面繼續(xù)考慮P3優(yōu)先級，第一列的檢驗數為18，此為進基變量，計算相應的比值bi/aij

寫在列。通過比較，得到d3-

對應的比值最小，于是取a31（標為*號）為轉軸元進行矩陣行變換得到新的單純形表；

§2.3求解目標規(guī)劃的單純形方法(續(xù))（4）下面繼續(xù)考慮38

x1x2d1-d1+d2-d2+d3-d3+d4-d4+RHSP1000-10-100000

P20000000-1000

P3000000-330-199

P4000-1-0.5-1.5-.25.25006

d1-001-11.5-1.5-.25.25006

x201001-100008

x11000-1.51.5.25-.25003

d4-000000-331-199

x1x2d1-d1+d2-d2+d3-d3+d4-d4+39§2.3求解目標規(guī)劃的單純形方法(續(xù))（5）當前的單純形表各優(yōu)先級的檢驗數均滿足了上述條件,故為最優(yōu)單純形表。我們得到最優(yōu)解x1=3，x2=8。

§2.3求解目標規(guī)劃的單純形方法(續(xù))（5）當前的單純形40舉例說明在實際中常用的分層加權線性目標規(guī)劃的解法。例2有一紡織廠生產尼龍和棉布，平均生產能力都是1千米/小時，工廠生產能力為每周80小時。根據市場預測，下周最大銷量為：尼龍布70千米，棉布45千米，尼龍布利潤為2.5元/米，棉布利潤為1.5元/米。工廠領導的管理目標如下，P1：保證職工正常上班，避免開工不足；P2：盡量達到最大銷售量；P3：盡量減少加班時間，限制加班時間不得超過10小時。舉例說明在實際中常用的分層加權線性目標規(guī)劃的解法。41707042目標規(guī)劃及目標規(guī)劃模型課件430000000001010000-3-1000

P3P2P10000000001010000-3-10-5-1

P3P2P1001000100001-1100-10011000[1]0100100

10x17045S1000010100-1001100010101[1]00

80

70

45S10Sx2x1XBB-1b0001000P3000100044-13000010-110001S000020000031000000

P3P2P10000201-30031000000

P3P2P100100010-1110000110-1010000100

x220x1702510-1110-101[1]10-1010000100

x210x170

35S10x2x1XBB-1b-1010S000000P300100045目標規(guī)劃及目標規(guī)劃模型課件46目標規(guī)劃目標規(guī)劃47

在科學研究、經濟建設和生產實踐中，人們經常遇到一類含有多個目標的數學規(guī)劃問題，我們稱之為多目標規(guī)劃。本章介紹一種特殊的多目標規(guī)劃叫目標規(guī)劃(goalprogramming)，這是美國學者Charnes等在1952年提出來的。目標規(guī)劃在實踐中的應用十分廣泛，它的重要特點是對各個目標分級加權與逐級優(yōu)化，這符合人們處理問題要分別輕重緩急保證重點的思考方式。本章分目標規(guī)劃模型、目標規(guī)劃的幾何意義與圖解法和求解目標規(guī)劃的單純形方法等三個部分進行介紹。

在科學研究、經濟建設和生產實踐中，人們482.1目標規(guī)劃模型

2.1.1問題提出

為了便于理解目標規(guī)劃數學模型的特征及建模思路,我們首先舉一個簡單的例子來說明.

例2.1.1某公司分廠用一條生產線生產兩種產品A和B，每周生產線運行時間為60小時，生產一臺A產品需要4小時，生產一臺B產品需要6小時．根據市場預測，A、B產品平均銷售量分別為每周9、8臺，它們銷售利潤分別為12、18萬元。在制定生產計劃時，經理考慮下述4項目標：

2.1目標規(guī)劃模型2.1.1問題提492.1目標規(guī)劃模型2.1.1問題提出(續(xù))首先，產量不能超過市場預測的銷售量；其次，工人加班時間最少；第三，希望總利潤最大；最后，要盡可能滿足市場需求,當不能滿足時,市場認為B產品的重要性是A產品的2倍．試建立這個問題的數學模型．討論：

若把總利潤最大看作目標，而把產量不能超過市場預測的銷售量、工人加班時間最少和要盡可能滿2.1目標規(guī)劃模型2.1.1問題提出(續(xù))502.1目標規(guī)劃模型

2.1.1問題提出(續(xù))足市場需求的目標看作約束，則可建立一個單目標線性規(guī)劃模型

設決策變量x1，x2

分別為產品A，B的產量

MaxZ=12x1+18x2

s.t.4x1+6x260

x1

9

x28

x1,x20

2.1目標規(guī)劃模型2.1.1問題提出(續(xù))512.1目標規(guī)劃模型2.1.1問題提出(續(xù))容易求得上述線性規(guī)劃的最優(yōu)解為(9,4)T

到(3,8)T

所在線段上的點,最優(yōu)目標值為Z*=180,即可選方案有多種.在實際上,這個結果并非完全符合決策者的要求,它只實現了經理的第一、二、三條目標，而沒有達到最后的一個目標。進一步分析可知，要實現全體目標是不可能的。2.1目標規(guī)劃模型2.1.1問題提出(續(xù))522.1目標規(guī)劃模型2.1.2目標規(guī)劃模型的基本概念把例2.1.1的4個目標表示為不等式.仍設決策變量x1，x2

分別為產品A，B的產量.那麼,第一個目標為:x19，x28；

第二個目標為:4x1+6x260；

第三個目標為:希望總利潤最大，要表示成不等式需要找到一個目標上界，這里可以估計為252（=129+188），于是有12x1+18x2

252；

第四個目標為:x1

9，x2

8；

2.1目標規(guī)劃模型2.1.2目標規(guī)劃模型的基本概念53

2.1.2目標規(guī)劃模型的基本概念（續(xù)）下面引入與建立目標規(guī)劃數學模型有關的概念．

（1）、正、負偏差變量d

+，d-

我們用正偏差變量d

+表示決策值超過目標值的部分；負偏差變量d-表示決策值不足目標值的部分。因決策值不可能既超過目標值同時又未達到目標值，故恒有d

+d-＝0．

（2）、絕對約束和目標約束我們把所有等式、不等式約束分為兩部分：絕對約束和目標約束。2.1.2目標規(guī)劃模型的基本概念（續(xù)）542.1.2目標規(guī)劃模型的基本概念（續(xù)）絕對約束是指必須嚴格滿足的等式約束和不等式約束；如在線性規(guī)劃問題中考慮的約束條件，不能滿足這些約束條件的解稱為非可行解，所以它們是硬約束。設例2.1.1中生產A，B產品所需原材料數量有限制，并且無法從其它渠道予以補充，則構成絕對約束。目標約束是目標規(guī)劃特有的，我們可以把約束右端項看作要努力追求的目標值，但允許發(fā)生正式負偏差，用在約束中加入正、負偏差變量來表示，于是稱它們是軟約束。2.1.2目標規(guī)劃模型的基本概念（續(xù)）552.1目標規(guī)劃模型

2.1.2目標規(guī)劃模型的基本概念（續(xù)）

對于例2.1.1,我們有如下目標約束

x1

+d1--d1+=9(2.1.1)

x2+d2--d2+=8(2.1.2)

4x1+6x2

+d3--d3+=60(2.1.3)

12x1+18x2

+d4--d4+=252(2.1.4)2.1目標規(guī)劃模型2.1.2目標規(guī)劃模型的基本概562.1目標規(guī)劃模型2.1.2目標規(guī)劃模型的基本概念（續(xù)）(3)、優(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.2.1目標規(guī)劃模型2.1.2目標規(guī)劃模型的基本概念（續(xù)57

2.1.2目標規(guī)劃模型的基本概念（續(xù)）

即在計算過程中,首先保證P1級目標的實現，這時可不考慮次級目標；而P2級目標是在實現P1級目標的基礎上考慮的，以此類推。當需要區(qū)別具有相同優(yōu)先因子的若干個目標的差別時，可分別賦于它們不同的權系數wj。優(yōu)先因子及權系數的值，均由決策者按具體情況來確定．（4）、目標規(guī)劃的目標函效．目標規(guī)劃的目標函數是通過各目標約束的正、負偏差變量和賦于相應的優(yōu)先等級來構造的．2.1.2目標規(guī)劃模型的基本概念（續(xù)）58§2.1目標規(guī)劃模型2.1.2目標規(guī)劃模型的基本概念（續(xù)）決策者的要求是盡可能從某個方向縮小偏離目標的數值。于是，目標規(guī)劃的目標函數應該是求極小：minf＝f（d

+，d-)．其基本形式有三種：

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

++d-)；

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

+)；§2.1目標規(guī)劃模型2.1.2目標規(guī)劃模型的基本概念（59

2.1.2目標規(guī)劃模型的基本概念（續(xù)）③要求不低于目標值，即使相應目標約束的負偏差變量要盡可能地小。這時取min（d

-)；對于例2.1.1,我們根據決策者的考慮知第一優(yōu)先級要求min（d1++d2+)；

第二優(yōu)先級要求min（d3+)；

第三優(yōu)先級要求min（d4-)；第四優(yōu)先級要求min（d1-+2d2-)，這里,當不能滿足市場需求時,市場認為B產品的重要性是A產品的2倍．即減少B產品的影響是A產品的2倍，因此我們引入了2:1的權系數。

2.1.2目標規(guī)劃模型的基本概念（續(xù)）60§2.1目標規(guī)劃模型

2.1.2目標規(guī)劃模型的基本概念（續(xù)）綜合上述分析，我們可得到下列目標規(guī)劃模型

Minf=P1（d1++d2+)+P2d3++P3d4-+P4（d1-+2d2-)

s.t.x1

+d1--d1+=9

x2+d2--d2+=8

4x1+6x2

+d3--d3+=60(2.1.5)

12x1+18x2

+d4--d4+=252

x1,x2

,di-,di+0,i=1,2,3,4.

§2.1目標規(guī)劃模型2.1.2目標規(guī)劃模型的基本61§2.1目標規(guī)劃模型2.1.3目標規(guī)劃模型的一般形式

根據上面討論,我們可以得到目標規(guī)劃的一般形式如下§2.1目標規(guī)劃模型2.1.3目標規(guī)劃模型的一般形式62§2.1目標規(guī)劃模型2.1.3目標規(guī)劃模型的一般形式(續(xù))（LGP）中的第二行是K個目標約束，第三行是m個絕對約束，ckj

和gk

是目標參數?！?.2目標規(guī)劃的幾何意義及圖解法

對只具有兩個決策變量的目標規(guī)劃的數學模型，我們可以用圖解法來分析求解．通過圖解示例，可以看到目標規(guī)劃中優(yōu)先因子，正、負偏差變量及權系數等的幾何意義。

§2.1目標規(guī)劃模型2.1.3目標規(guī)劃模型的一般形式(63§2.2目標規(guī)劃的幾何意義及圖解法§2.2目標規(guī)劃的幾何意義及圖解法（續(xù)）下面用圖解法來求解例2.1.1

我們先在平面直角坐標系的第一象限內，作出與各約束條件對應的直線，然后在這些直線旁分別標上G-i，i=1，2，3，4。圖中x，y分別表示問題（2.1.5）的x1和x2；各直線移動使之函數值變大、變小的方向用+、-表示di+,di-（如圖2.1.1所示）．

§2.2目標規(guī)劃的幾何意義及圖解法§2.2目標規(guī)劃的幾何意64§2.2目標規(guī)劃的幾何意義及圖解法05101520y

x2015105+-G-1+-G-2+-G-4+-G-3圖2-1§2.2目標規(guī)劃的幾何意義及圖解法0565§2.2目標規(guī)劃的幾何意義及圖解法下面我們根據目標函數的優(yōu)先因子來分析求解．首先考慮第一級具有P1優(yōu)先因子的目標的實現，在目標函數中要求實現min（d1++d2+),取d1+=d2+=0.圖2–2中陰影部分即表示出該最優(yōu)解集合的所有點。

我們在第一級目標的最優(yōu)解集合中找滿足第二優(yōu)先級要求min（d3+)的最優(yōu)解.取d3+=0

,可得到圖2–3中陰影部分即是滿足第一、第二優(yōu)先級要求的最優(yōu)解集合。

§2.2目標規(guī)劃的幾何意義及圖解法下面我們66§2.2目標規(guī)劃的幾何意義及圖解法圖2-205101520yx2015105+-G-1+-G-2-+G-4+-G-3A(3,8)§2.2目標規(guī)劃的幾何意義及圖解法圖2-2067§2.2目標規(guī)劃的幾何意義及圖解法圖2–305101520yx2015105+-G-1+-G-2-+G-4+-G-3A(3,8)§2.2目標規(guī)劃的幾何意義及圖解法圖2–3068§2.2目標規(guī)劃的幾何意義及圖解法

第三優(yōu)先級要求min（d4-)，根據圖示可知，d4-不可能取0值，我們取使d4-最小的值72得到圖2–4中兩陰影部分的交線(紅色粗線)，其表示滿足第一、第二及第三優(yōu)先級要求的最優(yōu)解集合。最后，考慮第四優(yōu)先級要求min（d1-+2d2-)，即要在黑色粗線段中找出最優(yōu)解。由于d1-的權因子小于d2-，因此在這里可以考慮取d2-=0。于是解得d1-=5，最優(yōu)解為A點x=3，y=8。

§2.2目標規(guī)劃的幾何意義及圖解法第三優(yōu)先級要求min69§2.2目標規(guī)劃的幾何意義及圖解法圖2–405101520yx2015105+-G-1+-G-2-+G-4+-G-3A(3,8)§2.2目標規(guī)劃的幾何意義及圖解法圖2–4070§2.3求解目標規(guī)劃的單純形方法

目標規(guī)劃的數學模型,特別是約束的結構與線性規(guī)劃模型沒有本質的區(qū)別，只是它的目標不止是一個,雖然其利用優(yōu)先因子和權系數把目標寫成一個函數的形式,但在計算中無法按單目標處理,所以可用單純形法進行適當改進后求解。在組織、構造算法時，我們要考慮目標規(guī)劃的數學模型一些特點，作以下規(guī)定：(1)因為目標規(guī)劃問題的目標函數都是求最小化，所以檢驗數的最優(yōu)準則與線性規(guī)劃是相同的；§2.3求解目標規(guī)劃的單純形方法目標規(guī)71§2.3求解目標規(guī)劃的單純形方法(續(xù))

(2)因為非基變量的檢驗數中含有不同等級的優(yōu)先因子，Pi>>Pi+1，i=1,2,,L-1.于是從每個檢驗數的整體來看：Pi+1（i=1,2,,L-1）優(yōu)先級第k個檢驗數的正、負首先決定于P1

，P2，…，Pi

優(yōu)先級第k個檢驗數的正、負。若P1

級第k個檢驗數為0，則此檢驗數的正、負取決于P2級第k個檢驗數；若P2

級第k個檢驗數仍為0，則此檢驗數的正、負取決于P3級第k個檢驗數，依次類推。換一句話說，當某Pi級第k個檢驗數為負數時，計算中不必再考察Pj（j>I）級第k個檢驗數的正、負情況；

§2.3求解目標規(guī)劃的單純形方法(續(xù))72§2.3求解目標規(guī)劃的單純形方法(續(xù))（3）根據（LGP）模型特征，當不含絕對約束時，di-（i=1,2,…,K）構成了一組基本可行解。在尋找單純形法初始可行點時，這個特點是很有用的。解目標規(guī)劃問題的單純形法的計算步驟

(1)建立初始單純形表．在表中將檢驗數行按優(yōu)先因子個數分別列成K行。初始的檢驗數需根據初始可行解計算出來，方法同基本單純形法。當不含絕對約束時，di-（i=1,2,…,K）構成了一組基本可行解，這時只需利用相應單位向量把各級目標行中對應di-（i=1,2,…,K）的量消成0即可得到初始單純形表。置k＝1；

§2.3求解目標規(guī)劃的單純形方法(續(xù))（3）根據（LGP73§2.3求解目標規(guī)劃的單純形方法(續(xù))(2)檢查當前第k行中是否存在大于0，且對應的前k-1行的同列檢驗數為零的檢驗數。若有取其中最大者對應的變量為換入變量，轉(3)。若無這樣的檢驗數，則轉(5)；(3)按單純形法中的最小比值規(guī)則確定換出變量，當存在兩個和兩個以上相同的最小比值時，選取具有較高優(yōu)先級別的變量為換出變量，轉（4）；

§2.3求解目標規(guī)劃的單純形方法(續(xù))(274§2.3求解目標規(guī)劃的單純形方法(續(xù))(4)按單純形法進行基變換運算，建立新的單純形表，（注意：要對所有的行進行轉軸運算）返回(2)；(5)當k＝K時，計算結束。表中的解即為滿意解。否則置k=k+1，返回（2）。

§2.3求解目標規(guī)劃的單純形方法(續(xù))(75§2.3求解目標規(guī)劃的單純形方法(續(xù))例2.3.1試用單純形法來求解例2.1.1的目標規(guī)劃模型(2.1.5)

Minf=P1（d1++d2+)+P2d3++P3d4-+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.

§2.3求解目標規(guī)劃的單純形方法(續(xù))例2.3.1試用76§2.3求解目標規(guī)劃的單純形方法(續(xù))解:首先處理初始基本可行解對應的各級檢驗數。由于P1,P2

優(yōu)先級對應的目標函數中不含di-,所以其檢驗數只需取系數負值。分別為(0，0，0，-1，0，-1，0，0，0，0；0)和(0，0，0，0，0，0，0，-1，0，0；0)

§2.3求解目標規(guī)劃的單純形方法(續(xù))解:77

x1x2d1-d1+d2-d2+d3-d3+d4-d4+RHSP1000-10-100000

P20000000-1000

P300000000-100

P400-10-2000000

d1-101-10000009

d2-01001-100008d3-4600001-10060d4-12180000001-1252

x1x2d1-d1+d2-d2+d3-d3+d4-d4+78

x1x2d1-d1+d2-d2+d3-d3+d4-d4+RHSP1000-10-100000

P20000000-1000

P312180000000-1252

P400-10-2000000

d1-101-10000009

d2-0*1001-100008d3-4600001-10060d4-12180000001-1252

x1x2d1-d1+d2-d2+d3-d3+d4-d4+79§2.3求解目標規(guī)劃的單純形方法(續(xù))P3

優(yōu)先級對應的目標函數中含d4-,所以其檢驗數需要把第四個約束行加到取負值的這一行上，得到(12，18，0，0，0，0，0，0，0，-1；252)TP4

優(yōu)先級對應的目標函數中含（d1-+2d2-)，所以其檢驗數需要把第一個約束行與第二個約束行的2倍加到取系數負值的這一行上，得到(1，2，0，-1，0，-2，0，0，0，0；25)。列目標規(guī)劃的初始單純形表

§2.3求解目標規(guī)劃的單純形方法(續(xù))P3優(yōu)先級對應的80

x1x2d1-d1+d2-d2+d3-d3+d4-d4+RHSP1000-10-100000

P20000000-1000

P312180000000-1252

P4120-10-2000025

d1-101-10000009

d2-0*1001-1000088d3-4600001-1006010d4-12180000001-125214

x1x2d1-d1+d2-d2+d3-d3+d4-d4+81§2.3求解目標規(guī)劃的單純形方法(續(xù))（1）k=1，在初始單純形表中基變量為（d1