運籌學(xué)第四章目標(biāo)規(guī)劃課件

1、第四章 目標(biāo)規(guī)劃一、目標(biāo)規(guī)劃的數(shù)學(xué)模型二、目標(biāo)規(guī)劃的圖解法三、解目標(biāo)規(guī)劃的單純形法四、應(yīng)用舉例一、目標(biāo)規(guī)劃的數(shù)學(xué)模型例1：產(chǎn)品III限量原材料（kg/件）51060設(shè)備工時（h/件）4440利潤（元/件）68解得：最優(yōu)生產(chǎn)計劃為： x1=8件， x2=2件， max z=64元。LP： max z=6x1 + 8x2 5x1+10 x2 604x1+4x2 40 x1 , x2 0 s.t.x1 x2 但如果站在企業(yè)高層領(lǐng)導(dǎo)者的角度看：一個計劃要滿足多方面的要求。財務(wù)、物資、銷售、計劃。線性規(guī)劃問題有最優(yōu)解的必要條件是其可行解集非空。但實際問題有時不能滿足這樣的要求。線性規(guī)劃解的可行性和最優(yōu)性

2、具有十分明確的意義。實際問題中往往還會作某種調(diào)整和修改。一、目標(biāo)規(guī)劃的數(shù)學(xué)模型1961年，查恩斯（A. Charnes）和庫柏（W. W. Cooper）提出了目標(biāo)規(guī)劃（Goal Programming，簡稱GP）。目標(biāo)規(guī)劃在處理實際決策問題時，承認(rèn)各項決策要求的存在有其合理性；在作最終決策時，不強調(diào)其絕對意義上的最優(yōu)性。一、目標(biāo)規(guī)劃的數(shù)學(xué)模型例2 假設(shè)計劃人員還被要求考慮如下的意見：由于產(chǎn)品II銷售疲軟，故希望產(chǎn)品II的產(chǎn)量不超過產(chǎn)品I的一半；原材料嚴(yán)重短缺，生產(chǎn)中應(yīng)避免過量消耗；最好能節(jié)約4小時設(shè)備工時；計劃利潤不少于48元。最后達(dá)成了一致意見：（目標(biāo)）原材料使用限額不得突破；產(chǎn)品II產(chǎn)量

3、要求必須優(yōu)先考慮；設(shè)備工時問題其次考慮（節(jié)約4個）；最后考慮計劃利潤的要求。一、目標(biāo)規(guī)劃的數(shù)學(xué)模型1、偏差變量對每一個決策目標(biāo)，引入正、負(fù)偏差變量d+和d- 。d+ : 決策值超過目標(biāo)值的部分。d- ：決策值未達(dá)到目標(biāo)值的部分。d+ 0和d- 0 d+d- 0目標(biāo)規(guī)劃數(shù)學(xué)模型涉及的基本概念一、目標(biāo)規(guī)劃的數(shù)學(xué)模型2絕對約束和目標(biāo)約束絕對約束：必須嚴(yán)格滿足的等式或不等式約束。目標(biāo)約束：目標(biāo)規(guī)劃所特有的約束，約束右端項看作要追求的目標(biāo)值，在達(dá)到目標(biāo)值時，允許發(fā)生正或負(fù)的偏差。絕對約束是硬約束。目標(biāo)約束是一種軟約束，目標(biāo)約束中決策值和目標(biāo)值之間的差異用偏差變量表示。必為等式。一、目標(biāo)規(guī)劃的數(shù)學(xué)模型3優(yōu)

4、先因子和權(quán)系數(shù)不同目標(biāo)的主次輕重有兩種差別。一種差別是絕對的，可用優(yōu)先因子Pt來表示。優(yōu)先因子間的關(guān)系為PtPt+1，即Pt對應(yīng)的目標(biāo)比Pt+1對應(yīng)的目標(biāo)有絕對的優(yōu)先性。另一種差別是相對的，這些目標(biāo)具有相同的優(yōu)先因子，它們的重要程度可用權(quán)系數(shù)的不同來表示。一、目標(biāo)規(guī)劃的數(shù)學(xué)模型 4目標(biāo)規(guī)劃的目標(biāo)函數(shù)目標(biāo)規(guī)劃的目標(biāo)函數(shù)(又稱為準(zhǔn)則函數(shù)或達(dá)成函數(shù))由各目標(biāo)約束的偏差變量及相應(yīng)的優(yōu)先因子和權(quán)系數(shù)構(gòu)成。其目標(biāo)函數(shù)只能是極小化。有三種基本表達(dá)式：(1)要求恰好達(dá)到目標(biāo)值。 minf(d+d- )(2)要求不超過目標(biāo)值，但允許不足目標(biāo)值。 minf(d+ )(3)要求不低于目標(biāo)值，但允許超過目標(biāo)值。 mi

5、nf(d- )一、目標(biāo)規(guī)劃的數(shù)學(xué)模型5x1+10 x2 602x2 x1 +d1- -d1+=04x1 +4x2 +d2- -d2+=366x1 +8x2 +d3- -d3+=48x1 , x2 , di- , di+ 0 di- . di+ =0 i=1,2,3 minZ=P1d1+ +P2(d2+) + P3(d3-)一、目標(biāo)規(guī)劃的數(shù)學(xué)模型s.t.(1)原材料使用限額不得突破；(2)產(chǎn)品II產(chǎn)量要求必須優(yōu)先考慮；(3)設(shè)備工時問題其次考慮（節(jié)約4個）；(4)最后考慮計劃利潤的要求。（不少于48）LP： maxZ=6x1 + 8x2 5x1+10 x2 604x1+4x2 40 x1 , x

6、2 0 s.t.例2一、目標(biāo)規(guī)劃的數(shù)學(xué)模型s.t.例3 資源擁有量原材料(公斤) 2 1 11設(shè)備(小時) 1 2 10利潤(千元/件) 8 10 (1)、原材料價格上漲，超計劃要高價購買，所以要嚴(yán)格控制。 (2)、市場情況，產(chǎn)品銷售量下降，產(chǎn)品的產(chǎn)量不大于產(chǎn)品的產(chǎn)量。(3)、充分利用設(shè)備，不希望加班。(4)、盡可能達(dá)到并超過利潤計劃指標(biāo)56千元。一、目標(biāo)規(guī)劃的數(shù)學(xué)模型設(shè)X1 ，X2為產(chǎn)品，產(chǎn)品產(chǎn)量。目標(biāo)函數(shù) minZ=P1d1+P2(d2-+d2+)+P3(d3-) 一、目標(biāo)規(guī)劃的數(shù)學(xué)模型2X1+X2 11X1 -X2 +d1- -d1+=0X1 +2X2 +d2- -d2+=108X1 +

7、10X2 +d3- -d3+=56X1 , X2 , di- , di+ 0 di- . di+ =0s.t.例4、電視機(jī)廠裝配25寸和21寸兩種彩電，每臺電視機(jī)需裝備時間1小時，每周裝配線計劃開動40小時，預(yù)計每周25寸彩電銷售24臺，每臺可獲利80元，每周21寸彩電銷售30臺，每臺可獲利40元。該廠目標(biāo)：1、充分利用裝配線，避免開工不足。2、允許裝配線加班，但盡量不超過10小時。3、盡量滿足市場需求。一、目標(biāo)規(guī)劃的數(shù)學(xué)模型解：設(shè)X1 , X2 分別表示25寸，21寸彩電產(chǎn)量minZ=P1d1-+P2d2+P3(2d3-+d4-)一、目標(biāo)規(guī)劃的數(shù)學(xué)模型X1+X2 +d1- -d1+=40X1

8、 +X2+d2- -d2+=50X1+d3- -d3+=24X2 +d4- -d4+=30X1 , X2 , di- , di+ 0 (i=1,2,3,4)s.t.小結(jié)：1、約束條件： 硬約束(絕對約束) 軟約束 (目標(biāo)約束)，引入d-, d+2、目標(biāo)優(yōu)先級： P1 P2 PL 同一級中可以有若干個目標(biāo)：P21 , P22 ,P23 其重要程度用權(quán)重系數(shù)W21 ,W22 ,W23 表示一、目標(biāo)規(guī)劃的數(shù)學(xué)模型3、目標(biāo)函數(shù)：(1)、恰好達(dá)到目標(biāo)： minZ= f (d -+d+)(2)、超過目標(biāo)： minZ= f (d -) (3)、不超過目標(biāo)： minZ= f (d+)一、目標(biāo)規(guī)劃的數(shù)學(xué)模型4、

9、目標(biāo)規(guī)劃的目標(biāo)：求一組決策變量的滿意值，使決策結(jié)果與給定目標(biāo)總偏差最小。 目標(biāo)函數(shù)中只有偏差變量。 目標(biāo)函數(shù)總是求偏差變量最小。 Z=0：各級目標(biāo)均已達(dá)到 Z0：部分目標(biāo)未達(dá)到。一、目標(biāo)規(guī)劃的數(shù)學(xué)模型二、目標(biāo)規(guī)劃的圖解法例1minZ= d- 100X1+80X2 -d+d- =100004X1+2X2 4002X1+4X2 500X1 , X2 , d- , d+ 0 d+.d- =0s.t.X1O50100X250100125E100X1+80X2 = 100002X1+4X2 = 500C4X1+2X2 = 400Bd+(1)、絕對約束可行域OBEC(2)、目標(biāo)約束滿意域CBE(3)、多個

10、可行滿意解： (60,50),10000; (70,50),11000; E(50,100),13000。(4)、Zmin =0二、目標(biāo)規(guī)劃的圖解法minZ= d- 100X1+80X2 -d+d- =100004X1+2X2 4002X1+4X2 500X1 , X2 , d- , d+ 0 d+.d- =0s.t.例2：用圖解法求解。s.t.二、目標(biāo)規(guī)劃的圖解法X243X1ABOED問題的解為：線段DE二、目標(biāo)規(guī)劃的圖解法例3minZ=P1d1+P2(d2-+d2+)+P3(d3-)2X1+X2 11X1 -X2+d1- -d1+=0X1 +2X2 +d2- -d2+=108X1 +10X

11、2 +d3- -d3+=56X1 , X2 , di- , di+ 0CDEd2+X1+2X2 = 10d1-X1 -X2=07FGd3+8X1+10X2=56A11B2X1+X2 =11105X2510X1OminZ=P1d1+P2(d2-+d2+)+P3(d3-)2X1+X2 11X1 -X2+d1- -d1+=0X1 +2X2 +d2- -d2+=108X1 +10X2 +d3- -d3+=56X1 , X2 , di- , di+ 0解： 可行域OAB 目標(biāo)1： OBC 目標(biāo)2：ED線段 目標(biāo)3：GD線段例4minZ=P1d1-+P2d2+P3(2d3-+d4-)X1+X2 +d1-

12、-d1+=40 X1 +X2+d2- -d2+=50 X1 +d3- -d3+=24 X2+d4- -d4+=30 30304050X2X1OADd1+X1+X2 =40d2-BCX1+X2 =50d4+X2 =30EFd3+X1 =24解：minZ=P1d1-+P2d2+P3(2d3-+d4-)X1+X2 +d1- -d1+=40 X1 +X2+d2- -d2+=50 X1 +d3- -d3+=24 X2+d4- -d4+=30 (1)、滿足目標(biāo)、的滿意域為ABCD(2)、先考慮的滿意域為ABEF再考慮，無公共滿意域。(4)、Zmin =d4- =30 - X2 + d4+=30-26=40

13、(3)、取EX1+X2=50X1=24E(24,26)獲利2960應(yīng)用案例紅星制藥廠生產(chǎn)A、B兩種藥品，有關(guān)數(shù)據(jù)如下： A B 電力 2 3 100(百度) 煤 4 2 120(百噸)利潤 6 4 (萬元)（1）求最優(yōu)生產(chǎn)計劃（2）電力可多供應(yīng)20（百度），利潤能否達(dá)240（萬元）？（3）若（2）達(dá)不到，改為以下目標(biāo)規(guī)劃 目標(biāo)1：保證利潤不低于240萬元 目標(biāo)2：耗電量、耗煤量應(yīng)盡量少地超過120二、目標(biāo)規(guī)劃的圖解法解：用單純形法求解，得解為：x1 =20， x2=20 ，Zmax =200(萬元)(2)、用靈敏度分析，可得：x1 =15，x2=30 ，Zmax =210(3)、建立目標(biāo)規(guī)劃模

14、型(1)、max Z=6x1+4x22x1+3x2 1004x1+2x2 120 x1 , x2 0s.t.minZ=P1(d1-)+P2(d2+d3+)6x1+4x2 +d1- -d1+=2402x1 +3x2+d2- -d2+=120 4x1 +2x2 +d3- -d3+=120 xi , di- , di+ 0s.t.二、目標(biāo)規(guī)劃的圖解法1010 x2x1DCBAd3-d1+d2-4x1+2x2 =1206x1+4x2 =2402x1+3x2 =120OEA(40，0)， B(60，0)C(24，24)， D(0，60)二、目標(biāo)規(guī)劃的圖解法分析：滿足P1，部分滿足P2的點有A,B,C,D

15、(如果不考慮A，B產(chǎn)品均需生產(chǎn))由解方程可得：A(40，0)， B(60，0) C(24，24)， D(0，60)比較與目標(biāo)的偏差A(yù)點：ZA = P1d1- + P2d2+ P2d3+ = 0+0+ P2d3+ = (4x1+ 2x2 + d3- - 120) P2 = (440 -120） P2=40P2B點：ZB = 120P2 C點：ZC = 24P2 D點：ZD = 60P2結(jié)論：取C點二、目標(biāo)規(guī)劃的圖解法三、解目標(biāo)規(guī)劃的單純形法計算步驟：建立初始單純形表。在表尾將檢驗數(shù)行按優(yōu)先因子個數(shù)分別列成k行，置k=1。檢驗該行中是否存在負(fù)數(shù)且對應(yīng)的前k-1行的系數(shù)為0。若有取其中最小者對應(yīng)的變

16、量為換入變量，轉(zhuǎn)3）。若無負(fù)數(shù)，轉(zhuǎn)5）。按最小比值規(guī)則確定換出變量，當(dāng)存在兩個及兩個以上相同的最小比值時，選取具有較高級別的變量為換出變量。按單純形法進(jìn)行基變換運算，建立新計算表，返2）。當(dāng)k=K時，計算結(jié)束。其中的解即為滿意解。 否則置k=K+1,返2）。例6 用單純形法解下列問題minZ=P1d1+P2(d2-+d2+)+P3(d3-)2X1+X2 11X1 -X2+d1- -d1+=0X1 +2X2 +d2- -d2+=108X1 +10X2 +d3- -d3+=56X1 , X2 , di- , di+ 0s.t.三、解目標(biāo)規(guī)劃的單純形法CjCBXBbx1x2x3d1-d1+d2-d2

17、+d3-d3+ j=cj-zjP1P2P3minZ=P1d1+P2(d2-+d2+)+P3(d3-)2X1 +X2 +X3 = 11X1 -X2+d1- -d1+=0X1 +2X2 +d2- -d2+=108X1 +10X2 +d3- -d3+=56X1 , X2 , di- , di+ 0Cj0000P1P2P2P30CBXBbx1x2x3d1-d1+d2-d2+d3-d3+0X3112110000000d1-01-101-10000P2d2-10120001-100P3d3-56810000001-1 j=cj-zjP1000010000P2-1-20000200P3-8-10000000

18、1minZ=P1d1+P2(d2-+d2+)+P3(d3-)2X1 +X2 +X3 = 11X1 -X2+d1- -d1+=0X1 +2X2 +d2- -d2+=108X1 +10X2 +d3- -d3+=56X1 , X2 , di- , di+ 0Cj0000P1P2P2P30CBXBbx1x2x3d1-d1+d2-d2+d3-d3+0X3112110000000d1-01-101-10000P2d2-10120001-100P3d3-56810000001-1 j=cj-zjP1000010000P2-1-20000200P3-8-100000001解：化標(biāo)準(zhǔn)形。列初始單純形表三、解目標(biāo)

19、規(guī)劃的單純形法Cj0000P1P2P2P30CBXBbx1x2x3d1-d1+d2-d2+d3-d3+0X363/20100-1/21/2000d1-53/2001-11/2-1/2000 x251/21000-1/200P3d3-630000-551-1 j=cj-zjP1000010000P2000001100P3-300005-501三、解目標(biāo)規(guī)劃的單純形法Cj0000P1P2P2P30CBXBbx1x2x3d1-d1+d2-d2+d3-d3+0X33001002-2-1/21/20d1-20001-13-3-1/21/20 x24010004/3-4/3-1/61/60 x121000

20、0-5/35/31/3-1/3 j=cj-zjP1000010000P2000001100P3000000010相當(dāng)G x=(2 , 4) 利潤為56三、解目標(biāo)規(guī)劃的單純形法說明：1，還可以再做一步，d3+ d1-,可得 X=(10/3，10/3)，對應(yīng)于D點；2，初始表中檢驗數(shù)行：要注意化為非基變 量表示式再填入。三、解目標(biāo)規(guī)劃的單純形法例7：用單純形法求解minZ=P1d1-+P2d2+P3(2d3-+d4-)X1+X2 +d1- -d1+=40 X1 +X2+d2- -d2+=50 X1 +d3- -d3+=24 X2+d4- -d4+=30 s.t.三、解目標(biāo)規(guī)劃的單純形法Cj00P1

21、00P22P30P30CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+P1d1-40111-10d2-50111-12P3d3-24101-1P3d4-30011-1 j=cj-zjP1P2P3解：列初始單純形表三、解目標(biāo)規(guī)劃的單純形法Cj00P100P22P30P30CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+P1d1-40111-10d2-50111-12P3d3-24101-1P3d4-30011-1 j=cj-zjP1-1-101000000P20000010000P3-2-100000201三、解目標(biāo)規(guī)劃的單純形法Cj00P100P22P30P

22、30CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+P1d1-16011-1-11000d2-26011-1-11000 x124101-1P3d4-30011-1 j=cj-zjP10-101001000P20000010000P30-100002001三、解目標(biāo)規(guī)劃的單純形法Cj00P100P22P30P30CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+0 x216011-1-11000d2-1000-111-100000 x124101-1P3d4-1400-111-11-1 j=cj-zjP10010000000P20000010000P3001-

23、1001101三、解目標(biāo)規(guī)劃的單純形法Cj00P100P22P30P30CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+0 x22601001-1-11000d1+1000-111-100000 x124101-1P3d4-40000-111-11-1 j=cj-zjP10010000000P20000010000P300001-11101所以，原問題的解為：X124，X226。d4- 4，所以市場需求沒有滿足，每周21寸彩電只生產(chǎn)26臺。三、解目標(biāo)規(guī)劃的單純形法1、友誼農(nóng)場有3萬畝農(nóng)田，欲種植玉米、大豆和小麥三種農(nóng)作物。各種作物每畝需施化肥分別為012噸、020噸、015噸

24、。預(yù)計秋后玉米每畝可收獲500千克，售價為024元千克，大豆每畝可收獲200千克，售價為120元千克，小麥每畝可收獲350千克，售價為0.70元千克。農(nóng)場年初規(guī)劃時考慮如下幾個方面： p1：年終收益不低于350萬元； p2：總產(chǎn)量不低于125萬噸； p3：小麥產(chǎn)量以05萬噸為宜； p4：大豆產(chǎn)量不少于02萬噸； p5：玉米產(chǎn)量不超過06萬噸； p6：農(nóng)場現(xiàn)能提供5000噸化肥；若不夠，可在市場高價購買，但希望高價采購量愈少愈好。試就該農(nóng)場生產(chǎn)計劃建立數(shù)學(xué)模型。四、 應(yīng)用舉例解：設(shè)種植玉米x1畝，大豆x2畝，小麥x3畝，則該問題的數(shù)學(xué)模型為:minZ=P1d1-+ P2d2-+P3(d3-+d3

25、+)+P4d4+ +P5d5+ +P6(d6+)X1+X2 +X3 3104120X1 +240X2 +245X3 +d1- -d1+=350 104500X1 +200X2 +350X3 +d2- -d2+=1250 104350X3 +d3- -d3+=500 104200X2 +d4- -d4+=200 1041000X3 +d5- -d5+=600 1040.12X1 + 0. 2X2 + 0.15X3 + d6- -d6+=5000X1 , X2 , di- , di+ 0s.t.四、 應(yīng)用舉例2： 某電子公司生產(chǎn)錄音機(jī)和收音機(jī)兩種產(chǎn)品，它們均需經(jīng)過兩個工廠加工，每一臺錄音機(jī)在第一個

26、工廠加工2小時，然后送到第二個工廠裝配試驗25小時才變?yōu)槌善?；每一臺收音機(jī)需在第一個工廠加工4小時，在第二個工廠裝配試驗15小時才變?yōu)槌善?。錄音機(jī)與收音機(jī)每臺廠內(nèi)的每月儲存成本分別為8元和15元。 第一個工廠有12部制造機(jī)器，每部每天工作8小時，每月正常工作天數(shù)為25天，第二個工廠有7部裝配試驗設(shè)備，每部每天工作16小時，每月正常工作天數(shù)仍為25天。每部機(jī)器每小時的運轉(zhuǎn)成本是：第一個工廠為18元，第二個工廠為15元。每臺錄音機(jī)的銷售利潤為20元，收音機(jī)為23元。依市場預(yù)測，次月的錄音機(jī)與收音機(jī)的銷售量估計分別為1500臺和1000臺。 四、 應(yīng)用舉例該公司依下列次序為目標(biāo)優(yōu)先次序，以實現(xiàn)下月的

27、生產(chǎn)與銷售目標(biāo)。P1：廠內(nèi)的儲存成本最少。P2：錄音機(jī)銷售量必須完成1500臺。P3：第一、二工廠的生產(chǎn)設(shè)備應(yīng)全力運轉(zhuǎn)，避免有空閑時間。兩廠的運轉(zhuǎn)成本當(dāng)作它們間的權(quán)系數(shù)。P4：第一個工廠的超時作業(yè)時間全月份不宜超出30小時。P5：收音機(jī)銷售量必須完成l000臺。P6；兩個工廠的超時工作時間總和應(yīng)予限制，其限制的比率依各廠每小時運轉(zhuǎn)成本為準(zhǔn)。 試建立這個問題的目標(biāo)規(guī)劃模型。四、 應(yīng)用舉例該公司依下列次序為目標(biāo)優(yōu)先次序，以實現(xiàn)下月的生產(chǎn)與銷售目標(biāo)。 P1：廠內(nèi)的儲存成本最少。 P2：錄音機(jī)銷售量必須完成1500臺。 P3：第一、二工廠的生產(chǎn)設(shè)備應(yīng)全力運轉(zhuǎn)，避免有空閑時間。兩廠的運轉(zhuǎn)成本當(dāng)作它們間的權(quán)系數(shù)。 P4：第一個工廠的超時作業(yè)時間全月份