課件實(shí)驗(yàn)04目標(biāo)

目標(biāo)規(guī)劃

Goal

Programming（GP）第四章目標(biāo)規(guī)劃——多目標(biāo)線性規(guī)劃目標(biāo)規(guī)劃

Goal

Programming（GP）目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型目標(biāo)規(guī)劃（

Goal

Programming

）方法是Charnes和Cooper于1961年提出的，目前已成為一種簡單、實(shí)用的處理多目標(biāo)決策問題的方法，是多目標(biāo)決策中應(yīng)用最為廣泛的一種方法。為了學(xué)習(xí)和初步掌握目標(biāo)規(guī)劃與線性規(guī)劃在處理問題的方法上的區(qū)別，我們分析如下案例——目標(biāo)規(guī)劃

Goal

Programming（GP）家具制造問題——王老板遇到的新問題背景材料：王老板過去一直從事專業(yè)家具制造，主要生產(chǎn)桌子、椅子兩種家具，王老板的經(jīng)營環(huán)境主要受到兩種資源——木工和油漆工每天的有效工作時(shí)間的限制。王老板過去的經(jīng)營環(huán)境條件如下：1、每天木工和油漆工的總有效工作時(shí)間分別為11小時(shí)和10小時(shí)。2、每生產(chǎn)一把椅子需要2小時(shí)的木工、1小時(shí)的油漆工。3、每生產(chǎn)一張桌子需要1小時(shí)的木工、2小時(shí)的油漆工。4、每生產(chǎn)一把椅子和一張桌子分別可獲利潤8元、10元。為了追求最大利潤，王老板建立了此問題的線性規(guī)劃模型并解得最優(yōu)方案：每天生產(chǎn)椅子4

把，桌子3

張，獲最大利潤62

元。目標(biāo)規(guī)劃

Goal

Programming（GP）家具制造問題——王老板遇到的新問題王老板過去一直以如何計(jì)劃兩種家具的生產(chǎn)量才能獲得最大總利潤為其生產(chǎn)、經(jīng)營的唯一目標(biāo)。然而，市場經(jīng)濟(jì)環(huán)境下新的問題出現(xiàn)了，它迫使王老板不得不考慮…...首先，根據(jù)市場信息，椅子的銷售量已有下降的趨勢，故應(yīng)果斷決策減少椅子的產(chǎn)量，其產(chǎn)量最好不大于桌子的產(chǎn)量。其次，市場上找不到符合生產(chǎn)質(zhì)量要求的木工了，因此決不可能考慮增加木工這種資源來增加產(chǎn)量，并且由于某種原因現(xiàn)有木工決不可能加班。再其次，應(yīng)盡可能充分利用油漆工的現(xiàn)有有效工作時(shí)間，但油漆工希望最好不加班。最后，新王老板考慮最好達(dá)到并超過預(yù)計(jì)利潤指標(biāo)56元。目標(biāo)規(guī)劃

Goal

Programming（GP）家具制造問題——王老板遇到的新問題討論——1、王老板現(xiàn)在的生產(chǎn)、經(jīng)營問題——多個(gè)目標(biāo)的生產(chǎn)問題2、決策變量——椅子、桌子的生產(chǎn)量x1，x2引入一種新的變量——正、負(fù)偏差變量d

+、d

-，d

+、d

-≥0。目標(biāo)規(guī)劃

Goal

Programming（GP）家具制造問題——王老板遇到的新問題討論——3、約束條件——絕對約束、目標(biāo)約束——硬約束、軟約束。4、目標(biāo)函數(shù)——優(yōu)先因子（優(yōu)先等級）P1，P2，…，規(guī)定Pk>>Pk+1，k=1，2，…。表示Pk比Pk+1有更大的優(yōu)先權(quán)。這意味著當(dāng)目標(biāo)與目標(biāo)之間發(fā)生沖突時(shí)應(yīng)按其優(yōu)先等級來實(shí)現(xiàn)。目標(biāo)規(guī)劃

Goal

Programming（GP）家具制造問題——王老板遇到的新問題目標(biāo)規(guī)劃獨(dú)特的目標(biāo)函數(shù)（準(zhǔn)則函數(shù)）是按各目標(biāo)約束的正、負(fù)偏差變量和賦予相應(yīng)的優(yōu)先因子而構(gòu)造的。當(dāng)每一目標(biāo)值確定后，決策者的要求是盡可能縮小偏離目標(biāo)值。因此，目標(biāo)規(guī)劃的目標(biāo)函數(shù)只能是min Z=f（

d+，d-

）。其基本形式有三種：目標(biāo)規(guī)劃

Goal

Programming（GP）家具制造問題——王老板遇到的新問題要求恰好達(dá)到目標(biāo)值，即正、負(fù)偏差變量都要盡可能地小min

Z

=

f（

d

++

d

-

）要求不超過目標(biāo)值，即允許達(dá)不到目標(biāo)值，即正偏差變量要盡可能地小min

Z

=

f（

d

+）要求超過目標(biāo)值，即超過量不限，但必須是即負(fù)偏差變量要盡可能地小min

Z

=

f（

d

-）目標(biāo)規(guī)劃

Goal

Programming（GP）家具制造問題——王老板遇到的新問題歸納上面的分析——新王老板應(yīng)在木工每天的有效工作時(shí)間受到嚴(yán)格限制的基礎(chǔ)上按順序考慮其他目標(biāo)的實(shí)現(xiàn)。目標(biāo)優(yōu)先等級：P1——椅子的產(chǎn)量最好不大于桌子的產(chǎn)量。P2——盡可能充分利用油漆工的有效工作時(shí)間，但希望不加班。P3——總利潤最好不小于56元。多個(gè)目標(biāo)！每個(gè)目標(biāo)都帶有柔性！目標(biāo)規(guī)劃

Goal

Programming（GP）家具制造問題——王老板遇到的新問題決策變量：x1——椅子的產(chǎn)量，

x2——桌子的產(chǎn)量。各個(gè)目標(biāo)偏的差變量：P

等級正、負(fù)偏差變量——d

+、d

-1

1

1P

等級正、負(fù)偏差變量——d

+、d

-2

2

2P

等級正、負(fù)偏差變量——d

+、d

-3

3

3x

、x

、d

+、d

-、d

+、d

-

、d

+、d

-

≥

01

2

1

1

2

2

3

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

Goal

Programming（GP）家具制造問題——王老板遇到的新問題約束條件：（1）絕對約束——

2x1+

x2

≤

11（2）目標(biāo)約束——

x

-

x +

d

-

-

d

+

=

01

2

1

11x

+

2x +

d

-

-

d

+

=

101

2

2

221

2

3

38x

+10x +

d

-

-

d

+

=

563（

P

）（

P

）（

P

）目標(biāo)函數(shù)：+

-

+

-min

Z

=

P1

d1

+

P2（

d2

+

d2

）+

P3

d3目標(biāo)規(guī)劃

Goal

Programming（GP）家具制造問題——王老板遇到的新問題王老板的多目標(biāo)線性規(guī)劃問題——目標(biāo)規(guī)劃問題：+

-

+minZ

=

P1d1

+

P2（

d2

+

d2

）+

P3

d3-s.t.2x1+

x2

≤

11x1

- x2

+

d1-

+-

d1

=

0-

+x1

+ 2x2

+

d28x1

+10x2

+

d3+-

d2

=

10-

-

d

=

563x

+

-

+

-

+

-1

、x2

、d1

、d1

、d2

、d2

、d3

、d3

≥

0目標(biāo)規(guī)劃

Goal

Programming（GP）目標(biāo)規(guī)劃的圖解法如何求解多目標(biāo)線性規(guī)劃問題，其方法與求解線性規(guī)劃問題的方法相似——目標(biāo)線性規(guī)劃單純形法。但是，對于只有兩個(gè)決策變量的目標(biāo)線性規(guī)劃問題同樣可以采用圖解的方法來揭示問題的解的某種特征。在用圖解法解目標(biāo)規(guī)劃時(shí)，首先必須滿足所有絕對約束條件。在此基礎(chǔ)上，再按照目標(biāo)優(yōu)先級別從高到低的順序，逐個(gè)地考慮各個(gè)目標(biāo)約束條件。目標(biāo)規(guī)劃

Goal

Programming（GP）目標(biāo)規(guī)劃的圖解法王老板的目標(biāo)規(guī)劃新問題圖解+

-

+

-min

Z=

P1

d1

+

P2（

d2

+

d2

）+

P3d3s.t.

2x1+

x2

≤

11x

- x

+

d

-

-

d

+=

01

2

1

1x

-

+1

+

2x2+

d2

-

d2

=

108x

-

+1

+10x2

+

d3

-

d3

=

56x

+

-

+

-

+

-1

、x2

、d1

、d1

、d2

、d2

、d3

、d3

≥08x1

+10x2

=

56x1

+

2x2=

102x1+

x2

=11絕對約束域2d

++d33d

-d2-1d

-1x1

-

x2

=

0d

+（10/3，10/3）（2，4）目標(biāo)規(guī)劃

Goal

Programming（GP）目標(biāo)規(guī)劃的圖解法案例——電視機(jī)廠裝配彩色和黑白兩種電視機(jī)，每裝配一臺電視機(jī)需占用裝配線1小時(shí)，裝配線每周計(jì)劃開動40小時(shí)。預(yù)計(jì)市場每周彩色電視機(jī)的銷量是24臺，每臺可獲利80元；每周黑白電視機(jī)的銷量是

30臺，每臺可獲利40元。決策者的目標(biāo)為：第一優(yōu)先級目標(biāo)：充分利用裝配線每周計(jì)劃開動的40小時(shí)；第二優(yōu)先級目標(biāo)：允許裝配線加班；但加班時(shí)間每周盡量不超過10小時(shí)；第三優(yōu)先級目標(biāo)：裝配電視機(jī)的數(shù)量盡量滿足市場需求。因?yàn)椴噬娨暀C(jī)的利潤更高（是黑白電視機(jī)利潤的2倍），取其市場需求滿足權(quán)系數(shù)為2。目標(biāo)規(guī)劃

Goal

Programming（GP）1

2

1

1x +

x +

d

-

-

d

+=

40-

+x1

+

x2

+

d2

-

d2

=

40+10=50-

+-

+x1

+

d3

-

d3

=

24x2+

d4

-

d4

=

30x

+

-

+

-

+

-

+

-1

、x2

、d1

、d1

、d2

、d2

、d3

、d3

、d4

、d4

≥0目標(biāo)規(guī)劃的圖解法目標(biāo)線性規(guī)劃模型：x1

——彩色電視機(jī)的生產(chǎn)量x2

——黑白電視機(jī)的生產(chǎn)量min

Z

=

P

d

-+

P

d

++

P

（2d

-

+1d

-）1

1

2

2

3

3

4s.t.目標(biāo)規(guī)劃

Goal

Programming（GP）3d

-d1-3d

+4d

++d2+d1d4--x1d2x1

+

x2

=

40x1

+

x2

=

50目標(biāo)規(guī)劃的圖解法電視機(jī)廠的目標(biāo)線性規(guī)劃問題——圖解：x2x1

=

24x2

=

30滿意解（24，26）目標(biāo)規(guī)劃

Goal

Programming（GP）目標(biāo)規(guī)劃模型的一般形式：l

lk

klk

kMin

Z

=∑

P

（∑（

w

-d

-

+

w

+d

+

））k=1l

=1L

Kn∑cx +

d

-

-

d

+

=

gkj

j

k

k

k，

k

=1，2，…，Kj

=1∑aij

xj

≤（=，≥）

bi，

i

=1，2，…，mj

=1nxj

≥

0

,j

=1，2，…，n-+dk

，dk

≥

0

,k

=1，2，…，KS.t.目標(biāo)規(guī)劃

Goal

Programming（GP）目標(biāo)規(guī)劃的單純形解法目標(biāo)規(guī)劃的模型實(shí)際上是求min型的線性規(guī)劃，因此，也可以用單純形法求解。在采用單純形法求解目標(biāo)規(guī)劃時(shí)，檢驗(yàn)數(shù)是各優(yōu)先因子的線性組合。因此，在判別各檢驗(yàn)數(shù)的正負(fù)及大小時(shí)，關(guān)鍵是要注意到優(yōu)先因子的級別。當(dāng)檢驗(yàn)數(shù)按優(yōu)先級別從高到低已滿足最優(yōu)性條件時(shí)，且無法進(jìn)一步優(yōu)化時(shí)，從單純形表上就可以得到目標(biāo)規(guī)劃的最優(yōu)解或滿意解。目標(biāo)規(guī)劃

Goal

Programming（GP）目標(biāo)規(guī)劃的單純形解法例

現(xiàn)有如下目標(biāo)規(guī)劃問題Min Z

=

P1d1-

+P2d2+

+P3d3-5x1

+

10x2

+

x3x1

–

2x24x1

+

4x26x1

+

8x2=

60+

d1-

–

d1+

=

0+

d2-

–

d2+

=

36+

d3-

–

d3+

=48xj

，

di-

，di+

≥

0當(dāng)前基變量：x3

，d1-，d2-，d3-。目標(biāo)規(guī)劃

Goal

Programming（GP）目標(biāo)規(guī)劃的單純形解法例

目標(biāo)規(guī)劃問題的典式Min Z

=

P1（

–

x1

+

2x2

+

d1+

）+

P2

d2++

P3（48

–

6x1

–

8x2

+

d3+

）5x1

+

10x2

+

x3=

60x1

–

2x2+

d1-

–

d1+=

04x1

+

4x2+

d2-

–

d2+=

366x1

+

8x2+

d3-

–

d3+=

48xj

，

di-

，di+

≥

0目標(biāo)規(guī)劃

Goal

Programming（GP）目標(biāo)規(guī)劃的單純形解法例

目標(biāo)規(guī)劃問題的單純形表P1

1P3

1cj000P100P2P30CB基解x1x2x3-d1+d1-d2+d2-d3+d30x3605101000000P1-d101-201-100000-d236440001-100P3-d34868000001-1sj

fiP1-121P21P3-6-81目標(biāo)規(guī)劃

Goal

Programming（GP）目標(biāo)規(guī)劃的單純形解法例cj

0

0

0

P1

0

0

P2

P3

0-

+

-

+

-

+CB

基

解

x1

x2

x3

d1

d1

d2

d2

d3

d30x3605

10

1

0

0

0

0

0

0P1-d101

-2

0

1

-1

0

0

0

00-d2364

4

0

0

0

1

-1

0

0P3-d3486

8

0

0

0

0

0

1

-1P1

-1

2

1P2

1P3

-6

-8

1cj000P100P2P30CB基解x1x2x3-d1+d1-d2+d2-d3+d30x3600201-5500000x101-201-100000-d2360120-441-100P3-d3480200-66001-1sj

fiP11P21P3-206-61目標(biāo)規(guī)劃

Goal

Programming（GP）目標(biāo)規(guī)劃的單純形解法例cj

0

0

0

P1

0

0

P2

P3

0-

+

-

+

-

+CB

基

解

x1

x2

x3

d1

d1

d2

d2

d3

d30x3600

20

1 -5

5

0

0

0

00x101 -2

0

1 -1

0

0

0

00-d2360

12

0 -4

4

1 -1

0

0P3-d3480

20

0 -6

6

0

0

1 -1P1

1P2

1P3

-20

6 -6

1cj000P100P2P30CB基解x1x2x3-d1+d1-d2+d2-d3+d30x3120011-100-110x124/51002/5-2/5001/10-1/100-d236/5000-2/52/51-1-3/53/50x212/5010-3/103/10001/20-1/20sj

fiP11P21P31目標(biāo)規(guī)劃

Goal

Programming（GP）目標(biāo)規(guī)劃的靈敏度分析目標(biāo)規(guī)劃的靈敏度分析主要針對優(yōu)先級別進(jìn)行，其原因是目標(biāo)優(yōu)先級別和權(quán)系數(shù)的確定往往帶有一定的主觀性。分析的方法主要是通過改變優(yōu)先級別的順序來觀察解的變化情況。目標(biāo)規(guī)劃Goal

Programming（GP）目標(biāo)規(guī)劃應(yīng)用問