數(shù)學(xué)建模線性和非線性規(guī)劃學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1數(shù)學(xué)數(shù)學(xué)(shxu)建模線性和非線性規(guī)劃建模線性和非線性規(guī)劃第一頁，共60頁。第2頁/共60頁第二頁，共60頁。第3頁/共60頁第三頁，共60頁。大阪的Hanshin高速的最優(yōu)安排(npi)每年節(jié)約一千七百萬人小時(shí) .第4頁/共60頁第四頁，共60頁。 為說明最優(yōu)化的價(jià)值,建立了專門的網(wǎng)站,列舉了哪些公司的什么問題,運(yùn)用最優(yōu)化方法節(jié)約和增加了多少金額. 有可選的行業(yè)(hngy),考察的方面,受益的方式,希望同學(xué)們各選擇其中的一個(gè),提一份報(bào)告,以說明最優(yōu)化的價(jià)值.第5頁/共60頁第五頁，共60頁。第6頁/共60頁第六頁，共60頁。表述？第7頁/共60頁第七頁，共60頁。引例(yn l)1

2、,動(dòng)物飼料配置問題 美國一家公司(n s)以專門飼養(yǎng)并出售一種實(shí)驗(yàn)用的動(dòng)物而聞名。這種動(dòng)物的生長對(duì)飼料中的三種營養(yǎng)成分特別敏感，即蛋白質(zhì)、礦物質(zhì)和維生素。需要的營養(yǎng)量蛋白質(zhì)：70克礦物質(zhì)：3克維生素：9.1毫克 現(xiàn)有五種飼料，公司希望找出滿足動(dòng)物(dngw)營養(yǎng)需要使成本達(dá)到最低的混合飼料配置。 第8頁/共60頁第八頁，共60頁。飼料蛋白質(zhì)(克)礦物質(zhì)(克)維生素(毫克)1(x1)2(x2)3(x3)4(x4)5(x5)需要量0.302.001.000.601.80700.100.050.020.200.0530.050.100.020.200.089.1每一種(y zhn)飼料每磅所含的營養(yǎng)

3、成分每種飼料(slio)每磅的成本飼料12345成本(美元)0.020.070.040.030.05第9頁/共60頁第九頁，共60頁。引例(yn l)2:供應(yīng)與選址a1.258.750.55.7537.25b1.250.754.7556.57.75d3547611第10頁/共60頁第十頁，共60頁。第11頁/共60頁第十一頁，共60頁。第12頁/共60頁第十二頁，共60頁。第13頁/共60頁第十三頁，共60頁。題.而在實(shí)際問題中,決策變量帶有約束是普遍的. 第14頁/共60頁第十四頁，共60頁。第15頁/共60頁第十五頁，共60頁。John Von Neumann 約翰馮諾依曼(1903195

4、7),美藉匈牙利人.20世紀(jì)最杰出的數(shù)學(xué)家之一,被譽(yù)為”計(jì)算機(jī)之父”,”博弈論之父”.被認(rèn)為(rnwi)是數(shù)學(xué)規(guī)劃的三大創(chuàng)始人之一.以下的三個(gè)人物和線性規(guī)劃(xin xn u hu)的出現(xiàn)有重要的關(guān)系.第16頁/共60頁第十六頁，共60頁。George B. Dantzig George B. Dantzig(1914-2005),美國人,線性規(guī)劃單純形法的創(chuàng)始人,被譽(yù)為”線性規(guī)劃之父”.美國科學(xué)院三院院士,美國軍方數(shù)學(xué)顧問,教授.并以其名字設(shè)立Dantzig獎(jiǎng).數(shù)學(xué)規(guī)劃的三大創(chuàng)始人之一.發(fā)現(xiàn)算法時(shí)非常年輕,以至到日本(r bn)時(shí),人們以為”線性規(guī)劃之父”是個(gè)老人,而對(duì)他無人問津.第17頁/

5、共60頁第十七頁，共60頁。Leonid Vitalyevich Kantorovich Kantorovich(1912-1986)蘇聯(lián)人,著名數(shù)學(xué)家和經(jīng)濟(jì)學(xué)家,教授,年僅18歲獲博士學(xué)位.因在經(jīng)濟(jì)學(xué)上提出稀缺資源的最優(yōu)配置(pizh)獲諾貝爾獎(jiǎng).線性規(guī)劃對(duì)偶理論的提出者,數(shù)學(xué)規(guī)劃的三大創(chuàng)始人之一.第18頁/共60頁第十八頁，共60頁。目標(biāo)規(guī)劃,決策論等等.第19頁/共60頁第十九頁，共60頁。 美國一家公司以專門飼養(yǎng)并出售一種實(shí)驗(yàn)用的動(dòng)物而聞名。這種動(dòng)物的生長對(duì)飼料(slio)中的三種營養(yǎng)成分特別敏感，即蛋白質(zhì)、礦物質(zhì)和維生素。需要的營養(yǎng)量蛋白質(zhì)：70克礦物質(zhì)：3克維生素：9.1毫克 現(xiàn)有

6、五種飼料，公司希望找出滿足動(dòng)物營養(yǎng)需要使成本達(dá)到最低的混合(hnh)飼料配置。 四,線形規(guī)劃問題的解法(ji f)及舉例第20頁/共60頁第二十頁，共60頁。飼料蛋白質(zhì)(克)礦物質(zhì)(克)維生素(毫克)1(x1)2(x2)3(x3)4(x4)5(x5)需要量0.302.001.000.601.80700.100.050.020.200.0530.050.100.020.200.089.1每一種(y zhn)飼料每磅所含的營養(yǎng)成分每種飼料(slio)每磅的成本飼料12345成本(美元)0.020.070.040.030.05第21頁/共60頁第二十一頁，共60頁。建立(jinl)數(shù)學(xué)模型決策(ju

7、c)變量：在混合飼料中，每天所需第j種飼料的磅數(shù)xj，j = 1，2，3，4，5； 約束條件： 蛋白質(zhì)：0.30 x1+2x2+x3+0.6x4+1.8x570 礦物質(zhì)：0.10 x1+0.05x2+0.02x3+0.2x4+0.05x53 維生素：0.05x1+0.1x2+0.02x3+0.2x4+0.08x510自然(zrn)約束條件：xi0 確定目標(biāo)：混合飼料的成本最低 0.02x1+0.07x2+0.04x3+0.03x4+0.05x5min第22頁/共60頁第二十二頁，共60頁。完整的線性規(guī)劃(xin xn u hu)模型：min 0.02x1+0.07x2+0.04x3+0.03x

8、4+0.05x5s.t. 0.30 x1+2x2+x3+0.6x4+1.8x570 0.10 x1+0.05x2+0.02x3+0.2x4+0.05x53 0.05x1+0.1x2+0.02x3+0.2x4+0.08x510 xj0 j = 1,2,3,4,5;min cTxs.t. Axb x010370,08. 02 . 002. 01 . 005. 005. 02 . 002. 005. 01 . 08 . 16 . 0123 . 005. 0,03. 0,04. 0,07. 0,02. 0bAcT歸納(gun)：返 回第23頁/共60頁第二十三頁，共60頁。第24頁/共60頁第二十四頁

9、，共60頁。原油類別原油類別 買入價(jià)買入價(jià)(元元/桶桶)買入量買入量(桶桶/天天) 辛烷值辛烷值(%) 硫含量硫含量(%)A455000120.5B35500062.0C25500083.0汽油類別汽油類別賣出價(jià)賣出價(jià)(元元/桶桶)需求量需求量(桶桶/天天) 辛烷值辛烷值(%) 硫含量硫含量(%)甲甲703000101.0乙乙60200082.0丙丙50100061.01:1 加工費(fèi): 4元/桶 能力(nngl): = 14000桶/天I: 安排生產(chǎn)計(jì)劃，在滿足需求(xqi)的條件下使利潤最大 第25頁/共60頁第二十五頁，共60頁。決策(juc)變量：目標(biāo)(mbio)：甲甲(3000)乙乙(

10、2000)丙丙(1000)A/45X1X2X3B/35X4X5X6C/25X7X8X9fxxxxxxxxxzmin35600025354560004100050200060300070max987654321約束(yush)：987654321253545minxxxxxxxxxf總利潤最大 需求限制； 原料限制； 含量限制； 非負(fù)限制 第26頁/共60頁第二十六頁，共60頁。含量(hnling)限制非負(fù)限制(xinzh) 原料(yunlio)限制需求限制約束1000325 . 020002325 . 03000325 . 01000686122000886123000108612500050

11、005000100020003000963852741963852741987654321963852741xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx0 x第27頁/共60頁第二十七頁，共60頁?？傆傆?yn l)：126000元元 c=454545353535252525;a1=100100100; 010010010; 001001001;a2=111000000; 000111000; 000000111; -1200-600-800; 0-1200-600-80; 00-1200-600-8; 0.500200300; 00.50020030; 0

12、00.5002003;b1=3000 20001000;b2=5000 50005000-30000-16000-6000300040001000;v1=zeros(1,9);x f=linprog(c,a2,b2,a1,b1,v1)z=356000-f甲甲(3000)乙乙(2000)丙丙(1000)A/452400800800B/35000C/256001200200第28頁/共60頁第二十八頁，共60頁。II: 通過廣告增加(zngji)銷售(1元廣告費(fèi)：增加(zngji)10桶銷售)決策(juc)變量：目標(biāo)(mbio)：甲甲(3000+)乙乙(2000+)丙丙(1000+) A/45X1

13、X2X3B/35X4X5X6C/25廣告廣告銷售銷售X7X103000+10X10X8X112000+10X11X9X121000+10X12fxxxxxxxxxxxxxxziiiimin3800004253545)101000(50)102000(60)103000(70max121091987654321121110約束：121110987654321499599699293949minxxxxxxxxxxxxf總利潤最大需求限制； 原料限制； 產(chǎn)量限制；含量限制； 非負(fù)限制 第29頁/共60頁第二十九頁，共60頁。含量(hnling)限制非負(fù)限制(xinzh) 產(chǎn)量限制(xinzh)原料

14、(yunlio)限制需求限制約束129631185210741)129631185210741987654321129631185210741101000325 . 0)102000(2325 . 0103000325 . 0101000(68612)102000(88612)103000(108612500050005000101000102000103000 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx0 x8001210iix第30頁/共60頁第三十頁，共60頁?？傆傆?yn l)：287750元元 c=49 49 49 39 39 3

15、9 29 2929-699-599-499;a1=1 00 100100 -100 0; 0 10 010010 0 -10 0; 0 01 001001 00 -10;a2=1110000 0 0 0 0 0; 0001110 0 0 0 0 0; 0000001 1 1 0 0 0; -1200-600-8 0 0 1000 0; 0-1200-600 -8 0080 0; 00-1200-60 0 -800 60; 0.5002003 0 0-100 0; 00.500200 3 00-20 0; 000.50020 0 300 -10 000000 0 001 1 1;b1=30002

16、0001000;b2=500050005000-30000-16000-6000 3000 40001000800;v1=zeros(1,12);x f=linprog(c,a2,b2,a1,b1,v1)z=380000-f甲甲(3000)乙乙(2000)丙丙(1000)A/452121.82185.3692.9B/35695.54036.8267.6C/25廣告廣告182.703277.9750 39.40第31頁/共60頁第三十一頁，共60頁。某公司有某公司有6個(gè)建筑工地，位置坐標(biāo)為個(gè)建筑工地，位置坐標(biāo)為(ai, bi) (單位：公里單位：公里(n l),水泥日用量水泥日用量di (單位：

17、噸）單位：噸）ia1.258.750.55.7537.25b1.250.754.7556.57.75d35476111)現(xiàn)有 2 料場，位于 A (5, 1), B (2, 7),記(xj,yj),j=1,2, 日儲(chǔ)量 ej各有 20 噸。假設(shè)假設(shè)(jish)：料場和工：料場和工地之間有直地之間有直線道路線道路目標(biāo)：制定每天的供應(yīng)計(jì)劃，即從 A, B 兩料場分別向各工地運(yùn)送多少噸水泥，使總的噸公里數(shù)最小。第32頁/共60頁第三十二頁，共60頁。用例中數(shù)據(jù)(shj)計(jì)算，最優(yōu)解為i1234561ic（料料場場 A）3507012ic（料料場場 B）00406102 , 1,6,.,1,. .)(

18、)(min612121612/122jecidctsbyaxcjijiiijjjiijijij線性規(guī)劃線性規(guī)劃(xin xn u hu)模模型型決策決策(juc)變變量：量：ci j (料場料場j到工地到工地i的運(yùn)量的運(yùn)量）12維維Shili084lin.m第33頁/共60頁第三十三頁，共60頁。2）改建兩個(gè)新料場，需要確定新料場位置）改建兩個(gè)新料場，需要確定新料場位置(wi zhi)(xj,yj)和運(yùn)量和運(yùn)量cij ，在其它條件不變下使總噸公，在其它條件不變下使總噸公里數(shù)最小。里數(shù)最小。2 , 1,6,.,1,. .)()(min612121612/122jecidctsbyaxcjijii

19、ijjjiijijij決策決策(juc)變變量：量：ci j，(xj,yj)16維維非線性規(guī)劃模型非線性規(guī)劃模型結(jié)果：結(jié)果：總噸公里數(shù)總噸公里數(shù)為為85.3，但局部最優(yōu)，但局部最優(yōu)解問題嚴(yán)重解問題嚴(yán)重Shili084.m: shili084fun.m第34頁/共60頁第三十四頁，共60頁。2611612/12222612/12121)(,6, 1,. .)()()()(minecdecidctsbyaxcdbyaxciiiiiiiiiiiiiii決策決策(juc)變量：變量：ci ，(xj,yj)10維維 計(jì)算方法的改善計(jì)算方法的改善(gishn)局部(jb)最優(yōu)解問題有所改進(jìn)第35頁/共60

20、頁第三十五頁，共60頁。i123456新新料料場場位位置置（),jjyx1ic304760（3.2552 5.6528）2ic0500011（7.2497 7.7499）+為工地(gngd), 數(shù)字為用量; *為新料場, 數(shù)字為供應(yīng)量。012345678901234567835476112016第36頁/共60頁第三十六頁，共60頁。約束非線性規(guī)劃約束非線性規(guī)劃(guhu)情形情形;,0)(, 0)(. .)(min2121GGGULGGtsfnRxxxxx標(biāo)準(zhǔn)標(biāo)準(zhǔn)(biozhn)模型模型fmincon語句的具體語句的具體(jt)用法用法ULbeqAeqbAGGtsfnRxxxxxx,x,0)

21、(, 0)(. .)(min21x,fval,exitflag,output=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,con)第37頁/共60頁第三十七頁，共60頁。 建立建立(jinl)m(jinl)m文件函數(shù)文件函數(shù) function f,G=fun(x) function f,G=fun(x) f=f(x); f=f(x); G=G1(x),G2(x); G=G1(x),G2(x); 選項(xiàng)選項(xiàng)optionsoptions 輸出參數(shù)輸出參數(shù)options(8)=options(8)=目標(biāo)函數(shù)最優(yōu)值；目標(biāo)函數(shù)最優(yōu)值； 輸入?yún)?shù)輸入?yún)?shù)options(13)=opti

22、ons(13)=等式約束的個(gè)數(shù)等式約束的個(gè)數(shù)(m)(m)； L L，U U是決策變量的下界是決策變量的下界(xi ji)(xi ji)和上界；和上界；2、fmincon語句的具體語句的具體(jt)用法用法第38頁/共60頁第三十八頁，共60頁。max f(x) = x12+ x22-x1x2-2x1-5x2 s.t. -(x1 1)2+ x2 0 2 x1-3x2+60, x0=0, 1例2fmincon語句語句(yj)的具體用法的具體用法轉(zhuǎn)化成標(biāo)準(zhǔn)轉(zhuǎn)化成標(biāo)準(zhǔn)(biozhn)形形min f(x) =- x12- x22+x1x2+2x1+5x2 s.t. (x1 1)2 - x2 0 -2 x

23、1+3x2 60, x0=0, 1第39頁/共60頁第三十九頁，共60頁。 function f=fun22(x) f=-x(1)2-x(2)2+x(1)*x(2)+2*x(1)+5*x(2); function G,Geq = cont2(x) G=(x(1)-1)2 - x(2); Geq=; x0=0 1; A=-2,3;b=6; Aeq=;beq=; lb=;ub=; fun22x,fval=fmincon(fun22,x0,A,b,Aeq,beq,lb,ub,cont2) x = 1.0e+008*-0.0006 -2.7649 fval = -7.6432e+016fun22= -

24、x(1)2-x(2)2+x(1)*x(2)+2*x(1)+5*x(2)fmincon語句的具體語句的具體(jt)用法用法第40頁/共60頁第四十頁，共60頁。例179.22,662.26708.101 .24986.14.721.24914. 5054.34164.17089. 610,.,1,10,.,1,101212222. .)/ln()(min61098737654106321101101，是常數(shù)，其值分別為：其中jcjxxxxxxxxxxxxxxxtsxxcxxfjjiijjjjfmincon語句語句(yj)的具體用法的具體用法第41頁/共60頁第四十一頁，共60頁。function

25、 fm=ex02(x)n=10;c=-6.089,-17.164,-34.054,-5.914, -24.721, -14.986,-24.1,-10.708, -26.662,-22.179;sx=0;for i=1:n sx=sx+x(i); %endfm=0;for i=1:n fm=fm+x(i)*(c(i)+log(x(i)/sx);endniix1計(jì)算1) 建立目標(biāo)建立目標(biāo)(mbio)函數(shù)函數(shù) ex02.m第42頁/共60頁第四十二頁，共60頁。供應(yīng)(gngyng)與選址a1.258.750.55.7537.25b1.250.754.7556.57.75d3547611第43頁/共

26、60頁第四十三頁，共60頁。供應(yīng)(gngyng)與選址第44頁/共60頁第四十四頁，共60頁。范例：供應(yīng)(gngyng)與選址(a1, b1), d1 = 3(a2, b2), d2 =5(a6, b6), d6= 11A(x1, y1)e1 = 20B(x2, y2)e2 = 20 x11x12x16x21x26x22目標(biāo)：使得噸公里min第45頁/共60頁第四十五頁，共60頁。建立(jinl)規(guī)劃模型02 , 1,6 , 1,. .)()(min6121222161ijjiijijijijijjiijxjexidxtsbyaxxf20噸噸第46頁/共60頁第四十六頁，共60頁。第47頁/共

27、60頁第四十七頁，共60頁。其中其中a，b，d，e 都是常數(shù)向量（數(shù)組）。都是常數(shù)向量（數(shù)組）。 當(dāng)料場位置為當(dāng)料場位置為(xj, yj)為已知時(shí)為已知時(shí), 上述模型為線性規(guī)上述模型為線性規(guī)劃模型。從料場劃模型。從料場j向工地運(yùn)送向工地運(yùn)送(yn sn)量為量為xij（決（決策變量）。策變量）。02 , 1,6 , 1,. .)()(min6121222161ijjjijiiijijijijijxjexidxtsbyaxxf思考： 矩陣(j zhn)形式第48頁/共60頁第四十八頁，共60頁。 當(dāng)料場位置為當(dāng)料場位置為(xi, yi)為未知時(shí)為未知時(shí), 上述上述(shngsh)模型為非線性規(guī)劃

28、模型。對(duì)決策模型為非線性規(guī)劃模型。對(duì)決策變量變量(xi, yi)而言。而言。線性規(guī)劃求解線性規(guī)劃求解(qi ji)結(jié)果：結(jié)果：最優(yōu)目標(biāo)值最優(yōu)目標(biāo)值f = 136.23（噸千米）（噸千米）j123456x1j(料場A)350701x2j(料場B)0040610程序程序(chngx)liaocx.m第49頁/共60頁第四十九頁，共60頁。function f,g=liaoch(x)a=1.25 8.75 0.5 5.75 3 7.25 ;b=1.25 0.75 4.75 5 6.5 7.75 ;d=3 5 4 7 6 11;e=20 20; f1=0;for j=1:6s(j)=sqrt(x(13

29、)-a(j)2+(x(14)-b(j)2);f1= f1 + s(j)*x(j);%A(x13,x14)到各工地到各工地(gngd)的噸公里數(shù)的噸公里數(shù)endf2=0;第50頁/共60頁第五十頁，共60頁。for i=7:12s(i)=sqrt(x(15)-a(i-6)2+(x(16)-b(i-6)2);f2= f2 + s(i)*x(i);%B(x15,x16)到各工地的噸公里數(shù)到各工地的噸公里數(shù)endf=f1+f2;% 總的目標(biāo)總的目標(biāo)(mbio)函數(shù)函數(shù)for i=1:6 g(i)=x(i)+x(i+6)-d(i);%第一組約束條件第一組約束條件endg(7)=sum(x(1:6)-e(

30、1);g(8)=sum(x(7:12)-e(2); %第二組約束條件第二組約束條件6 , 1,21idxiiij2, 1,61jexjjij第51頁/共60頁第五十一頁，共60頁。x0=ones(1,12);L=zeros(1,12);opt(13)=6;x,opt=constr(liaoch,x0,opt,L)f=opt(8),n=opt(10)MATLAB運(yùn)行運(yùn)行(ynxng)程序程序(liaochj.m)i123456ABCi1(料場A)0507085.906x3xCi2(料場B)3040635.073y6.5y計(jì)算結(jié)果：最優(yōu)目標(biāo)值計(jì)算結(jié)果：最優(yōu)目標(biāo)值f = 93.14（噸千米（噸千米(qin m)）新料場位置的改變，目標(biāo)值比原來新料場位置的改變，目標(biāo)值比原來(yunli)減少了減少了43.1噸千噸千米。米。原最優(yōu)目標(biāo)值原最優(yōu)目標(biāo)值f = 136