數(shù)學(xué)建模協(xié)會(huì)簡(jiǎn)報(bào)

1、數(shù)學(xué)建模協(xié)會(huì)簡(jiǎn)報(bào)校數(shù)學(xué)建模協(xié)會(huì)主辦總第十期 2007年12月3日 星期一 肖鑫 吳小兵我校2007年“高教社”杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽獲獎(jiǎng)名單全國(guó)二等獎(jiǎng)：劉 凱 林 偉 曾祥波王曉龍 張保華 楊 廣秦 偉 張召霞 程 坤張宏捷 苗 棟 牛志鵬江蘇省一等獎(jiǎng)：徐云龍 陳玲熙 李劍英張 瑩 李紅波 金 晨王碩朋 周紅偉 劉舒然王旭東 余祥慧 楊應(yīng)俠江蘇省二等獎(jiǎng)：李志高 肖 鑫 趙國(guó)貞馬 丹 白慶升 陳 龍劉季超 韓兆磊 李 理劉 超 宋露露 夏 波王 翼 羅晨旭 余 良江蘇省三等獎(jiǎng)：張 鵬 白慶昌 張守明李志鋒 劉丙鐲 王信信沈繼虎 曹先鵬 周延超李豐剛 趙純純 蔣元博張念超 劉 萌 江丙友傅睿卿

2、張 超 張文濤陳介華 邵小麗 張 彪?yún)f(xié)會(huì)新聞：一年一度的“高教社杯”全國(guó)大學(xué)生數(shù)學(xué)建模比賽結(jié)束了，我校取得了驕人的成績(jī)。共組織30個(gè)隊(duì)參加比賽，共有二十個(gè)隊(duì)獲省級(jí)以上獎(jiǎng)。全國(guó)二等獎(jiǎng)四隊(duì)、江蘇省一等獎(jiǎng)四隊(duì)、江蘇省二等獎(jiǎng)五隊(duì)、江蘇省三等獎(jiǎng)七隊(duì)。模型介紹：為了使同學(xué)們更加容易了解數(shù)學(xué)建模，在以后的簡(jiǎn)報(bào)中我們將相繼介紹規(guī)劃問(wèn)題、層次分析法、主成分分析法，lingo,matlab等軟件的簡(jiǎn)單用法。本期介紹優(yōu)劃問(wèn)題 優(yōu)化問(wèn)題與規(guī)劃模型 與最大、最小、最長(zhǎng)、最短等等有關(guān)的問(wèn)題都是優(yōu)化問(wèn)題。 解決優(yōu)化問(wèn)題形成管理科學(xué)的數(shù)學(xué)方法： 運(yùn)籌學(xué)。運(yùn)籌學(xué)主要分支：（非）線性規(guī)劃、動(dòng)態(tài)規(guī)劃、圖與網(wǎng)絡(luò)分析、存貯學(xué)、排隊(duì)倫、

3、對(duì)策論、決策論。1.1 線性規(guī)劃例1 作物種植安排 一個(gè)農(nóng)場(chǎng)有50畝土地, 20個(gè)勞動(dòng)力, 計(jì)劃種蔬菜,棉花和水稻. 種植這三種農(nóng)作物每畝地分別需要?jiǎng)趧?dòng)力 1/2 1/3 1/4, 預(yù)計(jì)每畝產(chǎn)值分別為 110元, 75元, 60元. 如何規(guī)劃經(jīng)營(yíng)使經(jīng)濟(jì)效益最大. 模型 I : 設(shè)決策變量：種植蔬菜 x1 畝, 棉花 x2 畝, 水稻 x3 畝，求目標(biāo)函數(shù) f=110x1+75x2+60x3在約束條件x1+x2+x3 £ 50 1/2x1+1/3x2+1/4x3 £20 下的最大值1.1.1 線性規(guī)劃問(wèn)題求解方法 圖解法： 解兩個(gè)變量的線性規(guī)劃問(wèn)題，在平面上畫出可行域，計(jì)算目

4、標(biāo)函數(shù)在各極點(diǎn)處的值，經(jīng)比較后，取最值點(diǎn)為最優(yōu)解。命題3 當(dāng)兩個(gè)變量的線性規(guī)劃問(wèn)題的目標(biāo)函數(shù)取不同的目標(biāo)值時(shí)，構(gòu)成一族平行直線,目標(biāo)值的大小描述了直線離原點(diǎn)的遠(yuǎn)近。于是穿過(guò)可行域的目標(biāo)直線組中最遠(yuǎn)離(或接近)原點(diǎn)的直線所穿過(guò)的凸多邊形的頂點(diǎn)即為取的極值的極點(diǎn)最優(yōu)解。單純形法 : 通過(guò)確定約束方程組的基本解, 并計(jì)算相應(yīng)目標(biāo)函數(shù)值, 在可行解集的極點(diǎn)中搜尋最優(yōu)解. 正則模型: 決策變量: x1,x2,xn. 目標(biāo)函數(shù): Z=c1x1+c2x2+cnxn. 約束條件: a11x1+a1nxnb1, am1x1+amnxnbm,模型的標(biāo)準(zhǔn)化1. 引入松弛變量將不等式約束變?yōu)榈仁郊s束. 若有 ai1x

5、1+ainxnbi, 則引入 xn+i 0, 使得 ai1x1+ainxn+ xn+i =bi 若有 aj1x1+ajnxnbj, 則引入 xn+j 0, 使得 aj1x1+ajnxn- xn+j =bj. 且有 Z=c1x1+c2x2+cnxn+0xn+1+0xn+m. 2. 將目標(biāo)函數(shù)的優(yōu)化變?yōu)槟繕?biāo)函數(shù)的極大化. 若求 min Z, 令 Z=Z, 則問(wèn)題變?yōu)?max Z 3. 引入人工變量,使得所有變量均為非負(fù). 若 xi 沒(méi)有非負(fù)的條件,則引入 xi 0 和 xi0, 令 xi= xi xi, 則可使得問(wèn)題的全部變量均非負(fù). 標(biāo)準(zhǔn)化模型 求變量 x1, x2, xn, max Z = c

6、1x1+ cnxn, s. t. a11x1+ a1nxn= b1, am1x1+ amnxn= bm, x1 0, xn 0, 用Matlab求解：標(biāo)準(zhǔn)的線性規(guī)劃的模型： min f=cTxs.t. Ax £ b A1x=b1 LB £ x £ UBMatlab求解程序: x,f=linprog(c,A,b,A1,b1,LB,UB)還有軟件Excel 也可應(yīng)用于解優(yōu)化問(wèn)題。例 2 供貨問(wèn)題一家公司生產(chǎn)某種商品。現(xiàn)有n個(gè)客戶,第j個(gè)客戶需要貨物量至少為bj,可在m各不同地點(diǎn)設(shè)廠供貨.在地區(qū)i設(shè)廠的費(fèi)用為di ,供貨能力為hi ,向第j個(gè)客戶供應(yīng)單位數(shù)量的貨物費(fèi)用為

7、cij。如何設(shè)廠與供貨使總費(fèi)用最小。模型： 設(shè)決策變量：xij 為在地區(qū) i 向第 j個(gè)客戶供貨數(shù)量, 在地區(qū) i 設(shè)廠，記 yi =1 , 否則 記 yi =0 求 目標(biāo)函數(shù) f= å i (åj cij xij + yi di )在約束條件 åi xij = bj, åj xij -hi yi £0, xij³0, yi Î0，1 下的最小值1.2 整數(shù)規(guī)劃如果要求決策變量取整數(shù), 或部分取整數(shù)的線性規(guī)劃問(wèn)題,稱為整數(shù)規(guī)劃.例 4 . 飛船裝載問(wèn)題設(shè)有n種不同類型的科學(xué)儀器希望裝在登月飛船上, 令cj>0表示每件第

8、 j 類儀器的科學(xué)價(jià)值; aj >0表示每件第 j 類儀器的重量. 每類儀器件數(shù)不限, 但裝載件數(shù)只能是整數(shù). 飛船總載荷不得超過(guò)數(shù) b. 設(shè)計(jì)一種方案, 使得被裝載儀器的科學(xué)價(jià)值之和最大建模 記 xj 為第 j 類儀器的裝載數(shù). 求 目標(biāo)函數(shù) f= åj cj xj 在約束條件 åjaj xj £ b, xj 為正整數(shù), 下的最大值.用分枝定界法求解整數(shù)規(guī)劃問(wèn)題基本思想:反復(fù)劃分可行域并確定最優(yōu)值的界限,將原問(wèn)題不斷地分枝為若干個(gè)子問(wèn)題, 且縮小最優(yōu)質(zhì)的取值范圍,直到求得最優(yōu)解. 例:求目標(biāo)函數(shù) f=3x1+2x2 在約束條件: 2x1+3x2 £

9、;14, 2x1+x 2 £ 9, x1 x 2為自然數(shù)下的最大值.用Lindo軟件求解整數(shù)規(guī)劃max 3x1+2x2 s.t.2x1+3x2<=142x1+x2<=9endgin x1gin x26.3 0-1規(guī)劃 如果要求決策變量只取0 或 1的線性規(guī)劃問(wèn)題, 稱為0-1規(guī)劃. 0-1 約束不一定是由變量的性質(zhì)決定的, 更多地是由于邏輯關(guān)系引進(jìn)問(wèn)題的例5 背包問(wèn)題一個(gè)旅行者的背包最多只能裝 6 kg 物品. 現(xiàn)有4 件物品的重量和價(jià)值分別為 2 kg , 3 kg, 3 kg, 4 kg, 1 元, 1.2元, 0.9元, 1.1元. 應(yīng)攜帶那些物品使得攜帶物品的價(jià)值

10、最大?建模: 記 xj為旅行者攜帶第 j 件物品的件數(shù), 取值只能為 0 或 1.求目標(biāo)函數(shù) f=x 1 +1.2x 2 +0.9x 3 +1.1x 4 在約束條件 2x 1 +3x 2 +3x 3 +4x 4 £ 6下的最大值. 用Lingo 軟件求解0-1規(guī)劃Model: Max=x1+1.2*x2+0.9*x3+1.1*x4;2*x1+3*x2+3*x3+4*x4<=6;int(x1);int(x2);int(x3);int(x4);end6.4 多目標(biāo)線性規(guī)劃目標(biāo)函數(shù) fk=c (k)T x k=1,2, ¼, m,s.t. Ax £ b A1x=b1 LB £ x £ UB有最優(yōu)解 x (k), 記 f (k) =f(x (k)整體評(píng)價(jià)法min S=S(f (k) - c(k)T x)/ f (k) （使相對(duì)偏差最?。﹕.t. Ax £ b A1x=b1 LB £ x £ UB有最佳妥協(xié)解習(xí)題:1.資源的最優(yōu)配置策略某工廠有1000臺(tái)機(jī)器, 生產(chǎn)兩種產(chǎn)品 A, B, 若投入 y 臺(tái)機(jī)器生產(chǎn)A 產(chǎn)品, 則純收入為 5y .若投入 y 臺(tái)機(jī)器生產(chǎn)B 產(chǎn)品, 則純收入為 4y . 又