第4章目標(biāo)2單純型應(yīng)用

第四章目標(biāo)規(guī)劃GoalProgramming4.1目標(biāo)規(guī)劃問題及其建模4.2目標(biāo)規(guī)劃的圖解法4.3

目標(biāo)規(guī)劃的單純形法4.4

目標(biāo)規(guī)劃應(yīng)用第4章目標(biāo)規(guī)劃第2章單純形法2求解下列目標(biāo)規(guī)劃問題第4章目標(biāo)規(guī)劃3求解線性規(guī)劃的單純形法的過程基本一致，只是在檢驗(yàn)數(shù)處理時(shí)，需要考慮優(yōu)先次序的影響。而且，目標(biāo)規(guī)劃的目標(biāo)函數(shù)是求最小化，所以當(dāng)檢驗(yàn)數(shù)均為大于等于零時(shí)為滿意解。例4-3用單純形法求解例4-24.3目標(biāo)規(guī)劃的單純形法第4章目標(biāo)規(guī)劃4Step(0):初始單純形表Step(1):x2入基，d4-出基第4章目標(biāo)規(guī)劃5Step(2):d4+

入基，d1-出基Step(3):x1入基，d4+出基第4章目標(biāo)規(guī)劃6Step(4):d4-

入基，d3-出基Step(5):d1+

入基，d2-出基第第4章目標(biāo)規(guī)劃7這時(shí)，所有非基變量的檢驗(yàn)數(shù)都大于零，所以有唯一最優(yōu)解。X*=（13/2，5/4）Z*=9/4P3+3P4例：用單純形法求解下列目標(biāo)規(guī)劃問題Cj

000P1

P2

P2P3

00CBXBbx1x2

x3

001－11－100000P21012001－1000

P3

5681000001－100

x3

11210000001σkjP1

0000100000P2

-10－1－20002000P3

-56－8－100000010Cj

000P1

P2

P2P3

00CBXBbx1x2

x3

053/201－11/2-1/20000x251/21001/2-1/2000

P3

63000-551－100

x3

63/2000-1/21/2001σkjP1

0000100000P2

0000011000P3

-6－30005-5010θ=min｛10/3,10,6/3,12/3｝=2,故為換出變量。Cj

000P1

P2

P2P3

00CBXBbx1x2x3

02001－13-3-1/21/200x2401004/3-4/3-1/61/600x121000-5/35/31/3-1/300

x3

300002-2-1/21/21σkjP1

0000100000P2

0000011000P3

0000000100最優(yōu)解為x1＝2，x2＝4。但非基變量的檢驗(yàn)數(shù)為零，故此題有無(wú)窮多最優(yōu)解。θ=min｛4,24,－,6｝=4,故為換出變量。Cj

000P1

P2

P2P3

00CBXBbx1x2

x3

04002-26-6-1100x210/301-1/31/31/3-1/30000x110/3102/3-2/31/3-1/30000

x3

100-1－1-11001σkjP1

0000100000P2

0000011000P3

000000100最優(yōu)解為x1＝10/3,，x2=10/3。則這兩個(gè)解得凸組合都是本例的滿意解。目標(biāo)規(guī)劃的應(yīng)用目標(biāo)規(guī)劃在人事管理中的應(yīng)用

[例4]某研究所現(xiàn)有科研人員38名，定編人數(shù)42名，人員的工資級(jí)別與各級(jí)人員定編數(shù)如下表所示。級(jí)別年工資額(萬(wàn)元/人)現(xiàn)有人數(shù)定編人數(shù)Ⅳ.實(shí)習(xí)研究員Ⅲ.助理研究員Ⅱ.副研究員Ⅰ.研究員1.01.21.52.018107315158413.3

目標(biāo)規(guī)劃的應(yīng)用現(xiàn)擬進(jìn)行工資與人員調(diào)整,調(diào)整的原則與目標(biāo)如下：（1）工資總額不超過50萬(wàn)元/年；（2）各級(jí)人員數(shù)不超過定編人數(shù)；（3）升入Ⅰ、Ⅱ、Ⅲ級(jí)的人數(shù)分別不低于各定編人數(shù)的20%,25%，40%；并且規(guī)定Ⅳ級(jí)人員的缺額由外調(diào)或招聘增補(bǔ),其余各級(jí)人員應(yīng)從原有次低級(jí)別的人員中晉升。已知Ⅰ、Ⅱ級(jí)人員即將離休各一人。應(yīng)如何確定各級(jí)人員調(diào)整人數(shù)？

一、決策變量

設(shè)xj(j=1,2,3,4)為第j級(jí)人員增補(bǔ)數(shù)。

二、目標(biāo)約束

(1)工資總額的目標(biāo)約束

10(18-x3+x4)+12(10-x2+x3)+15(7-1-x1+x2)+20(3-1+x1)≤500化簡(jiǎn)得

5x1+3x2+2x3+10x4≤70故有

5x1+3x2+2x3+10x4+d1--

d1+=70

13.3

目標(biāo)規(guī)劃的應(yīng)用z1

=d1+級(jí)別年工資額(萬(wàn)元/人)現(xiàn)有人數(shù)定編人數(shù)Ⅳ.實(shí)習(xí)研究員Ⅲ.助理研究員Ⅱ.副研究員Ⅰ.研究員1.01.21.52.0181073151584目標(biāo)規(guī)劃的應(yīng)用(2)

各級(jí)定編人數(shù)的目標(biāo)約束

Ⅳ級(jí):18-x3+x4≤15

即x3-x4

≥3Ⅲ級(jí):10-x2+x3≤15

即-x2+x3

≤5Ⅱ級(jí):6-x1+x2≤8

即-x1+x2

≤2Ⅰ級(jí):2+x1≤4

即x1≤2故有

x3

-x4

+d2--

d2+=3-x2

+x3

+d3--

d3+=5-x1

+x2

+d4--

d4+=2

x1+d5--

d5+=2z2

=d2-

+d3++

d4++d5+級(jí)別年工資額(萬(wàn)元/人)現(xiàn)有人數(shù)定編人數(shù)Ⅳ.實(shí)習(xí)研究員Ⅲ.助理研究員Ⅱ.副研究員Ⅰ.研究員1.01.21.52.0181073151584目標(biāo)規(guī)劃的應(yīng)用(3)晉級(jí)人數(shù)的目標(biāo)約束

晉入Ⅲ級(jí):x3

≥15×0.40=6

晉入Ⅱ級(jí):x2

≥8×0.25=2

晉入Ⅰ級(jí):x1

≥4×0.20≈

1故有

x3+d6--

d6+=

6

x2+d7--

d7+=

2

x1+d8--

d8+=

1z3

=d6-

+d7-

+d8-級(jí)別年工資額(萬(wàn)元/人)現(xiàn)有人數(shù)定編人數(shù)Ⅳ.實(shí)習(xí)研究員Ⅲ.助理研究員Ⅱ.副研究員Ⅰ.研究員1.01.21.52.0181073151584目標(biāo)規(guī)劃的應(yīng)用

三.目標(biāo)函數(shù)

P1級(jí)：z1=d1+

P2級(jí)：z2=

d2-+d3++

d4++d5+

P3級(jí)：z3=d6-+d7-+d8-這樣，本例的目標(biāo)規(guī)劃模型為

minz=P1d1++P2(d2-+d3++d4++d5+)+P3(d6-+d7-+d8-)5x1+3x2+2x3+10x4+d1--d1+=70

x3-x4+d2--d2+=3-x2+x3+

d3--d3+=5

-x1+x2+

d4--d4+=2

x1+

d5--d5+=2

x3+

d6--d6+=6

x2+

d7--d7+=2

x1+

d8--d8+=1

xj≥0整數(shù)，j=1,2,3,4

di-,di+

≥0,i=1,2,3,···，8s.t.目標(biāo)規(guī)劃在庫(kù)存管理中的應(yīng)用

[例5]

某副食品批發(fā)商店預(yù)測(cè)其經(jīng)營(yíng)的某種商品今后4個(gè)月購(gòu)進(jìn)與銷出價(jià)格（萬(wàn)元/噸）如下表所示。目標(biāo)規(guī)劃的應(yīng)用該店經(jīng)營(yíng)此種商品肯定能批發(fā)銷售出去，但最大銷量受到倉(cāng)庫(kù)容量的限制，而正常庫(kù)容量為3噸，必要時(shí)還可占用機(jī)動(dòng)庫(kù)容量2噸。該店每月初批發(fā)銷貨，每月中旬采購(gòu)進(jìn)貨，進(jìn)貨所需錢款完全依賴銷售收入。月1234購(gòu)價(jià)2.62.52.72.8銷價(jià)2.92.73.13.3假設(shè)該店第1個(gè)月初庫(kù)存量為2噸，其成本價(jià)格為2.5萬(wàn)元/噸，而且該月初無(wú)現(xiàn)金。該店預(yù)計(jì)今后4個(gè)月的經(jīng)營(yíng)目標(biāo)如下：（1）每個(gè)月都使用正常庫(kù)容量,盡量不要超貯;

（2）每月下旬都應(yīng)儲(chǔ)存1萬(wàn)元以備急用；

（3）力求今后4個(gè)月總盈利達(dá)到最大。應(yīng)如何擬訂購(gòu)銷計(jì)劃？目標(biāo)規(guī)劃的應(yīng)用目標(biāo)規(guī)劃的應(yīng)用

一、決策變量

設(shè)

xj=第j月的采購(gòu)量(噸)

，j=1,2,3,4yj

=第j月的銷售量(噸)

二、約束條件

(1)各月銷量的約束

y1≤2y2≤2-y1+x1y3≤2-y1+x1-y2+x2y4≤2-y1+x1-y2+x2-y3+x3

y1

+s1

=2y1+y2-x1

+s2

=2y1+y2+y3-x1-x2

+s3=2y1+y2+y3+y4

–x1

–x2–x3

+s4

=2(2)各月采購(gòu)量的約束2.6x1

≤2.9y12.5x2

≤2.9y1-2.6x1+2.7y22.7x3

≤2.9y1-2.6x1+2.7y2-2.5x2+3.1y32.8x4

≤2.9y1-2.6x1+2.7y2-2.5x2+3.1y3-2.7x3+3.3y4目標(biāo)規(guī)劃的應(yīng)用月1234購(gòu)價(jià)2.62.52.72.8銷價(jià)2.92.73.13.3目標(biāo)規(guī)劃的應(yīng)用-2.9y1+2.6x1+s5=0-2.9y1-2.7y2

+2.6x1+2.5x2+s6=0-2.9y1-2.7y2-3.1y3

+2.6x1+2.5x2+2.7x3

+s7=0-2.9y1-2.7y2-3.1y3-3.3y4+2.6x1+2.5x2+2.7x3+2.8x4+s8=0(3)正常庫(kù)容量的目標(biāo)約束2-y1+x1≤3-y1

+x1+d1--d1+=1-y1-y2+x1+x2

+d2--d2+=1

-y1-y2-y3

+x1+x2+x3+d3--d3+

=1-y1-y2-y3-y4+x1+x2+x3+x4+d4--d4+=1-y1+x1≤1(2-y1+x1)-y2+x2≤3-y1+x1-y2+x2≤1目標(biāo)規(guī)劃的應(yīng)用

(4)各月儲(chǔ)備金的目標(biāo)約束

2.9y1

-2.6x1

+d5--d5+

=1

2.9y1+2.7y2

-2.6x1-2.5x2

+d6--d6+

=1

2.9y1+2.7y2+3.1y3

-2.6x1-2.5x2-2.7x3

+d7--d7+

=1

2.9y1+2.7y2+3.1y3+3.3y4-2.6x1-2.5x2-2.7x3-2.8x4+d8--d8+

=1

(5)總盈利的目標(biāo)約束

估計(jì)利潤(rùn)上界：(3.3-2.5)(3+2)×4

=16

第一月銷售成本：2.5×2

=5

2.9y1

+2.7y2

+3.1y3

+3.3y4

-5

-2.6x1-2.5x2-2.7x3≥162.9y1+2.7y2+3.1y3+3.3y4-2.6x1-2.5x2-2.7x3+d9--d9+

=

21目標(biāo)規(guī)劃的應(yīng)用

三、目標(biāo)函數(shù)

P1級(jí)目標(biāo)為不超過正常庫(kù)容，故有

z1=d1++d2++d3++d4+

P2級(jí)目標(biāo)為每月下旬至少儲(chǔ)備1萬(wàn)元，故有

z2=d5-+d6-+d7-+d8-

P3級(jí)目標(biāo)為4個(gè)月積累利潤(rùn)不低于16萬(wàn)元，故有

z3=d9-因此可得目標(biāo)函數(shù)

minz=P1z1+P2z2+P3z3目標(biāo)規(guī)劃的應(yīng)用目標(biāo)規(guī)劃在目標(biāo)管理中的應(yīng)用

[例]

一個(gè)生產(chǎn)能力為每天140工時(shí)的工廠生產(chǎn)甲、乙兩種產(chǎn)品，每噸甲、乙產(chǎn)品分別消耗20工時(shí)，10工時(shí)，利潤(rùn)分別為5百元，2百元。由于產(chǎn)品需求量的限制，甲、乙產(chǎn)品每天最多只能生產(chǎn)6噸，10噸。

一、為獲得最大利潤(rùn)，每天應(yīng)生產(chǎn)甲、乙產(chǎn)品各多少噸？

設(shè)每天分別生產(chǎn)甲、乙產(chǎn)品

x1，x2

噸，總利潤(rùn)為z百元,則LP模型如下：

maxz=5x1+2x220x1+10x2≤140

x1≤6

x2≤10

x1，

x2≥0

目標(biāo)規(guī)劃的應(yīng)用s.t.x1*

=6噸，x2*

=2噸，z*

=34百元若該廠提出以下經(jīng)營(yíng)目標(biāo)：

P1:總利潤(rùn)不低于40百元；

P2

:充分利用生產(chǎn)能力,盡量不超過140工時(shí).minz=P1d1-+P2(d2-+

d2+)

x1≤6

x2

≤10

5x1+

2x2+d1--

d1+=

40

20x1+

10x2+d2--

d2+=

140

x1,

x2

,

di-,

di+≥0目標(biāo)規(guī)劃的應(yīng)用s.t.29目標(biāo)規(guī)劃的應(yīng)用04422866810x1x2①②d1-d1+③d2-d2+④B(6,5)A(6,2)C(6,10)D(4,10)Eminz=P1d1-+P2(d2-+d2+)

x1≤6

x2≤105x1+2x2+d1--d1+=4020x1+10x2+d2--d2+=140

x1,x2,di-,di+≥0目標(biāo)規(guī)劃的應(yīng)用

B點(diǎn)為次優(yōu)解:x1=6

噸x2=5

噸由于該方案需要的生產(chǎn)能力為

20

×6+10

×5=170

工時(shí)而實(shí)際生產(chǎn)能力只有140

工時(shí)≈0.82

20

×0.82=16.4（工時(shí)/噸）

10

×0.82=8.2

（工時(shí)/噸）

16.4x1+8.2

x2+d2--d2+=14016.4

×6+8.2×5=139.4(工時(shí))140170

LP解:

x1=6噸，x2

=2噸，設(shè)單位利潤(rùn)增加

△c1,△c2,成為c1′=5+△c1,c2′=2+△c2,則6c1′+2c2′=406(5+△c1)+2(2+△c2)=40即3△c1+△c2

=3

若保持c1′,

c2′仍為原比例,則△c1:△c2=5:2聯(lián)立求解，得目標(biāo)規(guī)劃的應(yīng)用

c1′=5.88,c2′=2.36,還可取線段AB上的任一點(diǎn):(6,

x2),2

≤

x2≤

5類似可得:

13.3

目標(biāo)規(guī)劃的應(yīng)用25-5x215+x2c1′=5+c2′

=2+25-5x215+x2單位利潤(rùn)單位消耗

28012+x2a1′=

14012+x2a2′=13.3

目標(biāo)規(guī)劃的應(yīng)用生產(chǎn)管理部門會(huì)計(jì)部門生產(chǎn)部門廠長(zhǎng)主管者2+5+2≤x2≤56403.綜合方案10202.365.8826402.線性規(guī)劃8.216.42556401.目標(biāo)規(guī)劃乙甲乙甲乙甲單耗(工時(shí)/噸)單位利潤(rùn)(百元/噸)日產(chǎn)量(噸)每天利潤(rùn)(百元)

目標(biāo)方案25-5x215+x210-2x215+x228012+

x214012+

x2目標(biāo)規(guī)劃的應(yīng)用廠長(zhǎng)每天總利潤(rùn)4000元甲：500元/噸乙：200元/噸生產(chǎn)部門日產(chǎn)量產(chǎn)品甲：6噸

產(chǎn)品乙：5噸

生產(chǎn)管理部門應(yīng)用工業(yè)工程提高生產(chǎn)效率降低消耗(工時(shí)/噸)：

產(chǎn)品甲由20降為16.4

產(chǎn)品乙由10降為8.2

每月核計(jì)成本核算利潤(rùn)：

產(chǎn)品甲：500元/噸

產(chǎn)品乙：200元/噸

會(huì)計(jì)部門例英特集團(tuán)在大連和上海各設(shè)一個(gè)分公司，本年度擬在全國(guó)招聘170名優(yōu)秀大學(xué)畢業(yè)生分別到生產(chǎn)、營(yíng)銷和財(cái)務(wù)部門工作。兩家分公司各部門的人才需求如表1所示。目前集團(tuán)經(jīng)過前幾輪面試，已選出180名候選人，根據(jù)每個(gè)人適合從事的部門以及希望工作的部門和城市，可以將這些候選人分為6個(gè)類別，如表2所示。集團(tuán)確定人才錄用與分配的原則及優(yōu)先序如下：部門分公司生產(chǎn)營(yíng)銷財(cái)務(wù)大連203040上海252035表1各分公司的人才需求表

類別人數(shù)適合的部門希望工作部門希望工作城市130生產(chǎn)、營(yíng)銷生產(chǎn)大連230營(yíng)銷、財(cái)務(wù)營(yíng)銷大連330生產(chǎn)、財(cái)務(wù)生產(chǎn)上海430生產(chǎn)、財(cái)務(wù)財(cái)務(wù)上海530營(yíng)銷、財(cái)務(wù)財(cái)務(wù)大連630財(cái)務(wù)財(cái)務(wù)上海表2候選人類別與意愿

P1：集團(tuán)恰好錄用到需要并且適合從事各個(gè)部門工作的人才；P2：80%以上的錄用員工分配到本人希望工作的部門；P3：80%以上的錄用員工分配到本人希望工作的城市；請(qǐng)你幫助建立該問題的數(shù)學(xué)規(guī)劃模型，并請(qǐng)回答：（1）你所建立的模型中有多少個(gè)決策變量？（2）你所建立的模型中有多少條約束條件（除變量取值約束之外）？企業(yè)計(jì)劃生產(chǎn)甲、乙兩種產(chǎn)品，這些產(chǎn)品需要使用兩種原材料，要在兩種不同的設(shè)備上加工，工藝資料如下表所示。企業(yè)應(yīng)該如何安排生產(chǎn)計(jì)劃，并盡可能的滿足下列目標(biāo)：例產(chǎn)品資源甲乙丙可用量（單位）材料I材料II設(shè)備A設(shè)備B

365435122355