礦業(yè)信息技術(shù)基礎(chǔ)第二章規(guī)劃論

1、電子表格系統(tǒng)電子表格系統(tǒng)第二章第二章 規(guī)劃論規(guī)劃論多媒體教學課件2.1 線性規(guī)劃線性規(guī)劃333323213123232221211313212111bxaxaxabxaxaxabxaxaxa 333231232221131211333323123222113121123332323222131211333231232221131211baabaabaadabaabaabadaabaabaabdaaaaaaaaad 2.1 線性規(guī)劃線性規(guī)劃2.1 線性規(guī)劃線性規(guī)劃nnxaxaxaxaxf.)(3322112.1 線性規(guī)劃線性規(guī)劃min(max) (, ). .0torforst c xaxbxa

2、axbcc xax 24334260224032800,1,2,32j f = x + xxx + xxx +xx s.t. x + xx xj 2.1 線性規(guī)劃線性規(guī)劃maxxxxf2124)(032243/812121ixxxxxx2.1 線性規(guī)劃線性規(guī)劃2.1 線性規(guī)劃線性規(guī)劃2.1 線性規(guī)劃線性規(guī)劃 7 7）在）在excelexcel中自動增加一頁中自動增加一頁“運算結(jié)果報告運算結(jié)果報告1”1”，報告中記錄，報告中記錄了運算日期、目標單元格、可變單了運算日期、目標單元格、可變單元格、約束等內(nèi)容。元格、約束等內(nèi)容。 8 8）保存、打印運算結(jié)果，見）保存、打印運算

3、結(jié)果，見圖圖2-52-5。 2.1 線性規(guī)劃線性規(guī)劃例例2 2 求求 f(x)=5x1+4x2+3x3 f(x)=5x1+4x2+3x3 的最大值的最大值 約束條件約束條件 2.1 線性規(guī)劃線性規(guī)劃012003/1023/850020012032132121ixxxxxxxxx解：解：1) 1) 打開打開excel, excel, 另將另將sheet2sheet2空白頁命名空白頁命名為為“線性線性2”2”。2) 2) 在在b5-b10b5-b10中分別輸入目標函數(shù)中分別輸入目標函數(shù)f(x)f(x)及約束條件及約束條件g(x)g(x)的表達式，見圖的表達式，見圖2-62-6。3 3）分別在）分別

4、在b12b12、c12c12、d12d12、e12e12中輸入中輸入x1x1、x2x2、x3x3、f(x), f(x), 在在b13b13、c13c13、d13d13、e13e13中分別輸入中分別輸入1 1、1 1、1 1、=5=5* *b13+4b13+4* *c13+3c13+3* *d13, d13, 此時此時e13e13中顯示出中顯示出1212，見圖，見圖2-62-6。2.1 線性規(guī)劃線性規(guī)劃4 4）光標放在）光標放在e13e13上，單擊上，單擊“工具工具 規(guī)劃求解規(guī)劃求解”菜單，出現(xiàn)菜單，出現(xiàn)“規(guī)劃求規(guī)劃求解參數(shù)解參數(shù)”對話框?qū)υ捒颍? 1）在）在“設(shè)置目標單元格設(shè)置目標單元格”中輸

5、入中輸入e13e13（2 2）在）在“等于等于”中選中選“最大值最大值”( (自動默認自動默認) )（3 3）在）在“可變單元格可變單元格”中選中選“b13:d13”b13:d13”（4 4）單擊）單擊“添加添加”按鈕，出現(xiàn)按鈕，出現(xiàn)“添加約束添加約束”對話框，對話框，在此框中在此框中“單元格引用位置單元格引用位置”輸入輸入b13,b13,在運算符選擇框中選在運算符選擇框中選“=”=”，在在“約束值約束值”中輸入中輸入 120120，單擊，單擊“添加添加”按鈕，在按鈕，在“約束值約束值”中輸中輸入入 500-c13-d13500-c13-d13，再次單擊，再次單擊“添加添加”按鈕按鈕“單元格引

6、用位置單元格引用位置”輸入輸入c13,c13,在在“約束值約束值”中輸入中輸入200200，單擊，單擊“添添加加”按鈕，在按鈕，在“約束值約束值”中輸入中輸入600-4/3600-4/3* *b13-5/3b13-5/3* *c13c13，單擊，單擊“確確定定”按鈕，返回按鈕，返回“添加約束添加約束”對話框，見圖對話框，見圖2-72-7。2.1 線性規(guī)劃線性規(guī)劃2.1 線性規(guī)劃線性規(guī)劃2.1 線性規(guī)劃線性規(guī)劃解：設(shè)解：設(shè)1#1#煤層的年產(chǎn)量為煤層的年產(chǎn)量為x1x1，2#2#煤層的年產(chǎn)量為煤層的年產(chǎn)量為x2x2則：求則：求f(x)= x1+ x2 f(x)= x1+ x2 的最大值的最大值約束條

7、件：約束條件：用用excelexcel軟件的求解過程與以上兩例相似，結(jié)果為：軟件的求解過程與以上兩例相似，結(jié)果為：x1=50x1=50，x2=6.67 x2=6.67 。 00123 . 02 . 0205021122121xxxxxxxx2.1 線性規(guī)劃線性規(guī)劃例例2 2 某礦有三個采區(qū)，根據(jù)生產(chǎn)技術(shù)條件，一、二、三某礦有三個采區(qū)，根據(jù)生產(chǎn)技術(shù)條件，一、二、三采區(qū)工人的勞動生產(chǎn)率分別為采區(qū)工人的勞動生產(chǎn)率分別為5 t/5 t/工、工、4 t/4 t/工、工、3t/3t/工，工，一、二采區(qū)工人分別不超過一、二采區(qū)工人分別不超過120120人、人、200200人，三個采區(qū)總?cè)耍齻€采區(qū)總?cè)藬?shù)不超

8、過人數(shù)不超過500500人。按通風要求，三個采區(qū)每人所需風量人。按通風要求，三個采區(qū)每人所需風量分別為分別為8m3/min8m3/min、6m3/min6m3/min、10m3/min10m3/min，供給三個采區(qū)的，供給三個采區(qū)的總風量為總風量為3600m3 /min3600m3 /min。問：如何安排三個采區(qū)的日產(chǎn)量，。問：如何安排三個采區(qū)的日產(chǎn)量，使得礦井得日產(chǎn)量達到最大？使得礦井得日產(chǎn)量達到最大？ 2.1 線性規(guī)劃線性規(guī)劃解：設(shè)三個采區(qū)所需的工人數(shù)分別為解：設(shè)三個采區(qū)所需的工人數(shù)分別為x1x1、x2x2、x3x3則：則：f(x)=5 x1+4 x2+3 x3 max f(x)=5 x1

9、+4 x2+3 x3 max 約束條件：約束條件：用用excelexcel軟件的求解，結(jié)果為：軟件的求解，結(jié)果為：x1=120x1=120，x2=200x2=200，x3=144x3=144。 03600106850020012032132121ixxxxxxxxx2.1 線性規(guī)劃線性規(guī)劃2.1 線性規(guī)劃線性規(guī)劃在線性規(guī)劃問題中，在線性規(guī)劃問題中， f(x) max f(x) max 或或 minmin 滿足于滿足于 g(x)g(x) 0 0 x xi i= 0 = 0 或或 1 1此類問題稱此類問題稱0-10-1規(guī)劃。規(guī)劃。實際生產(chǎn)、生活及工程問題中，包含：實際生產(chǎn)、生活及工程問題中，包含：

10、 yes, yes, 開，開， 工程建設(shè)，工程建設(shè)， 成功。成功。 no, no, 關(guān)，關(guān)， 不建，不建， 失敗。失敗。 2.2 0-1規(guī)劃規(guī)劃1 1窮舉法窮舉法 將將x xi i=0 or 1 =0 or 1 全部代入全部代入f(x)f(x)，所得到的，所得到的n n個值進行比個值進行比較，得到較，得到f(xf(x0 0) )。2 2 隱枚舉法隱枚舉法 只檢查部分結(jié)果，不檢查全部。只檢查部分結(jié)果，不檢查全部。3 3 用用excelexcel軟件求解軟件求解 用用excelexcel的的“工具工具 規(guī)劃求解規(guī)劃求解”菜單解菜單解0-10-1規(guī)劃問題。規(guī)劃問題。同線性規(guī)劃，區(qū)別在于約束條件為同線

11、性規(guī)劃，區(qū)別在于約束條件為xi=0 or 1.xi=0 or 1.2.2 0-1規(guī)劃規(guī)劃用用excelexcel軟件求解基本過程軟件求解基本過程: :1 1）打開）打開excel, sheet5excel, sheet5空白頁，命名為空白頁，命名為“0-10-1規(guī)劃規(guī)劃” ” 2 2）在）在b5-b10b5-b10中分別輸入目標函數(shù)中分別輸入目標函數(shù)f(x)f(x)及約束條件及約束條件g(x)g(x)的表達式的表達式3 3）分別在）分別在b11b11、c11c11、d11d11、1111中輸入中輸入x1x1、x2x2、x3x3、f(x), f(x), 在在b12b12、c12c12、d12d1

12、2、e12e12中分別輸入中分別輸入1 1、1 1、1 1、=2=2* *b12-2b12-2* *c12+4c12+4* *d12, d12, 此時此時e12e12中顯示出中顯示出5 5，如圖，如圖2-102-10。2.2 0-1規(guī)劃規(guī)劃4 4）光標放在）光標放在e12e12上，單擊上，單擊“工具工具 規(guī)劃求解規(guī)劃求解”菜單，出現(xiàn)菜單，出現(xiàn)“規(guī)劃規(guī)劃求解參數(shù)求解參數(shù)”對話框?qū)υ捒?（1 1）在）在“設(shè)置目標單元格設(shè)置目標單元格”中輸入中輸入e12e12。 （2 2）在）在“等于等于”中選中選“最大最大值值”( (自動默認自動默認) )。 （3 3）在）在“可變單元格可變單元格”中選中選“b1

13、2:d12”b12:d12”如圖如圖2-112-11。2.2 0-1規(guī)劃規(guī)劃（4 4）單擊）單擊“添加添加”按鈕，出現(xiàn)按鈕，出現(xiàn)“添加約束添加約束”對話框，如圖對話框，如圖2-122-12。在此框中在此框中“單元格引用位置單元格引用位置”輸入輸入b12b12，選，選“=0=0，=1=0=0，=1=0=0，=1=1，整數(shù)，整數(shù)”, ,單擊單擊“確確定定”按鈕，返回按鈕，返回“添加約束添加約束”對話框如圖對話框如圖2-132-13。 2.2 0-1規(guī)劃規(guī)劃（5 5）單擊）單擊“求解求解”按鈕，在按鈕，在“線性線性1”1”頁的頁的b12b12、c12c12、d12d12中分別中分別出現(xiàn)出現(xiàn)1 1、0

14、 0、1 1、6 6（6 6）同時出現(xiàn)）同時出現(xiàn)“規(guī)劃求解結(jié)果規(guī)劃求解結(jié)果”對話框，選對話框，選“保存規(guī)劃求解結(jié)果保存規(guī)劃求解結(jié)果( (默認默認)”)”，在，在“報告報告”攔中選攔中選“運算結(jié)果報告運算結(jié)果報告”后，單擊后，單擊“確定確定”按鈕按鈕（7 7）在）在excelexcel中自動增加一頁中自動增加一頁“運算結(jié)果報告運算結(jié)果報告1”1”，報告中記錄了，報告中記錄了運算日期、目標單元格、可變單元格、約束等內(nèi)容運算日期、目標單元格、可變單元格、約束等內(nèi)容（8 8）保存、打印運算結(jié)果。）保存、打印運算結(jié)果。2.2 0-1規(guī)劃規(guī)劃2.2 0-1規(guī)劃規(guī)劃 表表2-1 工程工程 費用費用(萬元萬元

15、) 收入收入(萬元萬元) 第1年 第2年 第3年 15182024710403392204741155861030可用資金25252525解解: : 設(shè)設(shè)xi=1, xi=1, 第第i i項工程施工；項工程施工；xi=0, xi=0, 第第i i項工程不施工項工程不施工滿足于：滿足于： 用用excelexcel的的“工具工具 規(guī)劃求解規(guī)劃求解”菜單求解此菜單求解此0-10-1規(guī)劃問題，規(guī)劃問題，結(jié)果為：結(jié)果為：x1=1, x2=1, x3=1, x4=1, x5=0x1=1, x2=1, x3=1, x4=1, x5=0， f(x)=95f(x)=95。 1or 0x2510xx2x10x8x

16、256x4x9x7xx 258x7x3x4x5x max 30x15x20x40x20xf(x)i543215432154321543212.2 0-1規(guī)劃規(guī)劃2.2 0-1規(guī)劃規(guī)劃表表2-2 原材料原材料 費用費用(萬元萬元) 收入收入(萬元萬元)12345可用資金第1月2.5311.5410第2月172.52110第3月523.51310第4月21.543.54101215251830解解: : 設(shè)設(shè)xi=1, xi=1, 購買第購買第i i種原料；種原料；xi=0, xi=0, 不購買第不購買第i i種原料種原料 滿足于：滿足于：2.2 0-1規(guī)劃規(guī)劃 1or 0x014xx5 . 3x

17、4x5 . 12x013xxx5 . 32x5x101x2xx5 . 27xx 014xx5 . 1x3x2.5x max 30xx18x5215x12xf(x)i54321543215432154321543212.3 非線性規(guī)劃非線性規(guī)劃2.3 非線性規(guī)劃非線性規(guī)劃2.3 非線性規(guī)劃非線性規(guī)劃2.3 非線性規(guī)劃非線性規(guī)劃2.3 非線性規(guī)劃非線性規(guī)劃2.3 非線性規(guī)劃非線性規(guī)劃2.3 非線性規(guī)劃非線性規(guī)劃2.3 非線性規(guī)劃非線性規(guī)劃2.3 非線性規(guī)劃非線性規(guī)劃2.3 非線性規(guī)劃非線性規(guī)劃2.3 非線性規(guī)劃非線性規(guī)劃2.3 非線性規(guī)劃非線性規(guī)劃81iiz8765432181zzzzzzzzzi

18、i2.3 非線性規(guī)劃非線性規(guī)劃2.3 非線性規(guī)劃非線性規(guī)劃2.3 非線性規(guī)劃非線性規(guī)劃 , 2 , 1;),(minmin810kjznlnsfiij2.3 非線性規(guī)劃非線性規(guī)劃ldc1v0 h = n ( l + l0 ) ，m j000k vlk mnna01ks h)ss ( l nk2.3 非線性規(guī)劃非線性規(guī)劃2.3 非線性規(guī)劃非線性規(guī)劃2.3 非線性規(guī)劃非線性規(guī)劃 sinsinh2.3 非線性規(guī)劃非線性規(guī)劃 rshk)sh(mrsjjsinsinjrshsinsinhjrshh21122.3 非線性規(guī)劃非線性規(guī)劃2.3 非線性規(guī)劃非線性規(guī)劃 rsh2nnsj42.3 非線性規(guī)劃非線性

19、規(guī)劃rsh2nnsj)jsa-1)(s(n43002.3 非線性規(guī)劃非線性規(guī)劃sinhhm0)sin(hhm00ss2.3 非線性規(guī)劃非線性規(guī)劃5000j)lsin(sr)hhm2(500050000j)sin(1sin1lsrhhmj)sin(hhmsinhhmslr1ss)sin(sin)sin(2sinarcsin6.522.3 非線性規(guī)劃非線性規(guī)劃 700jls2r|-|)tgl1)(l(n2.3 非線性規(guī)劃非線性規(guī)劃arhs2.3 非線性規(guī)劃非線性規(guī)劃aslr202.3 非線性規(guī)劃非線性規(guī)劃5000500000wlvr2nswlsrvs2ns2.3 非線性規(guī)劃非線性規(guī)劃0010vas

20、vas00)(asllr2.3 非線性規(guī)劃非線性規(guī)劃2.3 非線性規(guī)劃非線性規(guī)劃 2.3 非線性規(guī)劃非線性規(guī)劃,15. 1230qflpah 2.3 非線性規(guī)劃非線性規(guī)劃，扇102hqn ,f300102023. 0f102023. 030333303扇扇alclqnf2.3 非線性規(guī)劃非線性規(guī)劃，3303023003083303033003034)sin()(2)(1045.10)sin()(2)(7 . 0300102023. 024365afnacahhmlasnlhafnacahhmlasnlhazff2.3 非線性規(guī)劃非線性規(guī)劃5006 . 06 . 0000lrnnlknmqd2.

21、3 非線性規(guī)劃非線性規(guī)劃,sin0ahhm2.3 非線性規(guī)劃非線性規(guī)劃,22)(8076yaskyhkkzccg2.3 非線性規(guī)劃非線性規(guī)劃),()(060060yjsrnyjslrnl),(2)(2060060yjsrnyjslrnl),(06007jjsrnaz2.3 非線性規(guī)劃非線性規(guī)劃,0000nlvrlvknm),(350)(35021002100laavrnbalalvrnb2.3 非線性規(guī)劃非線性規(guī)劃,6013603000000avbrgnknlvravblvgkf2.3 非線性規(guī)劃非線性規(guī)劃),(3322110tletleterlvn,)(60)(350332211000210

22、08tstctletleterlvnavbrgnkalalvrnbz2.3 非線性規(guī)劃非線性規(guī)劃2.3 非線性規(guī)劃非線性規(guī)劃2.3 非線性規(guī)劃非線性規(guī)劃2.3 非線性規(guī)劃非線性規(guī)劃2.3 非線性規(guī)劃非線性規(guī)劃2.3 非線性規(guī)劃非線性規(guī)劃2.3 非線性規(guī)劃非線性規(guī)劃2.3 非線性規(guī)劃非線性規(guī)劃) 元m( 1023652433年fqp2.3 非線性規(guī)劃非線性規(guī)劃0(f)yf0pwf(f)圖2.3.10的最優(yōu)解可求得0)(dffd2.3 非線性規(guī)劃非線性規(guī)劃fp79. 32.3 非線性規(guī)劃非線性規(guī)劃2.3 非線性規(guī)劃非線性規(guī)劃mfmfffdfdffdfd212)2(06.125 . 3561.609

23、7561.6097000164. 0, 0238.32478334. 5295.1299125334. 527272727取使)/(85 . 41254秒mfqv2.3 非線性規(guī)劃非線性規(guī)劃fp79. 32.3 非線性規(guī)劃非線性規(guī)劃2.3 非線性規(guī)劃非線性規(guī)劃),(yxfz 00 xxxz00yyyz2.3 非線性規(guī)劃非線性規(guī)劃),( yxfz0),(yx),(),(),(yxyxfyx0 x0y0),(yx 2.3 非線性規(guī)劃非線性規(guī)劃)()()(hfff0fhh )(2.3 非線性規(guī)劃非線性規(guī)劃2.3 非線性規(guī)劃非線性規(guī)劃5 . 22fclqhfpc/miiiiiifqlch15 . 22

24、)( 2.3 非線性規(guī)劃非線性規(guī)劃5 . 325 . 225 . 25 . 305 . 325 . 2)()5 . 22q()()()()(ikiqiciifikiqiciififiqiliciikiliffifiliciiiikifilfhfff即(2-41) 2.3 非線性規(guī)劃非線性規(guī)劃iiiiiiiiikqcqlch5.35.25.225.22)()5.2()()42.3.2()(5.21)5.2(:)5.2()(:)(:)()5.2()5.2()(4.14.114.115.35.225.35.224.115.35.25.35.25.25.32hbhbhbhkqclbkqclkqcliiiiiiiiiiiiiiiiii即則令)43. 3 . 2()(5 . 34 . 12hbkqcfiiiii2.3 非線性規(guī)劃非線性規(guī)劃2,1000,10