數(shù)學(xué)建模協(xié)會簡報

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

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

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

4、標函數(shù)在各極點處的值，經(jīng)比較后，取最值點為最優(yōu)解。命題3 當兩個變量的線性規(guī)劃問題的目標函數(shù)取不同的目標值時，構(gòu)成一族平行直線,目標值的大小描述了直線離原點的遠近。于是穿過可行域的目標直線組中最遠離(或接近)原點的直線所穿過的凸多邊形的頂點即為取的極值的極點最優(yōu)解。單純形法 : 通過確定約束方程組的基本解, 并計算相應(yīng)目標函數(shù)值, 在可行解集的極點中搜尋最優(yōu)解. 正則模型: 決策變量: x1,x2,xn. 目標函數(shù): Z=c1x1+c2x2+cnxn. 約束條件: a11x1+a1nxnb1, am1x1+amnxnbm,模型的標準化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. 將目標函數(shù)的優(yōu)化變?yōu)槟繕撕瘮?shù)的極大化. 若求 min Z, 令 Z=Z, 則問題變?yōu)?max Z 3. 引入人工變量,使得所有變量均為非負. 若 xi 沒有非負的條件,則引入 xi 0 和 xi0, 令 xi= xi xi, 則可使得問題的全部變量均非負. 標準化模型 求變量 x1, x2, xn, max Z = c

6、1x1+ cnxn, s. t. a11x1+ a1nxn= b1, am1x1+ amnxn= bm, x1 0, xn 0, 用Matlab求解：標準的線性規(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)化問題。例 2 供貨問題一家公司生產(chǎn)某種商品?，F(xiàn)有n個客戶,第j個客戶需要貨物量至少為bj,可在m各不同地點設(shè)廠供貨.在地區(qū)i設(shè)廠的費用為di ,供貨能力為hi ,向第j個客戶供應(yīng)單位數(shù)量的貨物費用為

7、cij。如何設(shè)廠與供貨使總費用最小。模型： 設(shè)決策變量：xij 為在地區(qū) i 向第 j個客戶供貨數(shù)量, 在地區(qū) i 設(shè)廠，記 yi =1 , 否則 記 yi =0 求 目標函數(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ī)劃問題,稱為整數(shù)規(guī)劃.例 4 . 飛船裝載問題設(shè)有n種不同類型的科學(xué)儀器希望裝在登月飛船上, 令cj>0表示每件第

8、 j 類儀器的科學(xué)價值; aj >0表示每件第 j 類儀器的重量. 每類儀器件數(shù)不限, 但裝載件數(shù)只能是整數(shù). 飛船總載荷不得超過數(shù) b. 設(shè)計一種方案, 使得被裝載儀器的科學(xué)價值之和最大建模 記 xj 為第 j 類儀器的裝載數(shù). 求 目標函數(shù) f= åj cj xj 在約束條件 åjaj xj £ b, xj 為正整數(shù), 下的最大值.用分枝定界法求解整數(shù)規(guī)劃問題基本思想:反復(fù)劃分可行域并確定最優(yōu)值的界限,將原問題不斷地分枝為若干個子問題, 且縮小最優(yōu)質(zhì)的取值范圍,直到求得最優(yōu)解. 例:求目標函數(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ī)劃問題, 稱為0-1規(guī)劃. 0-1 約束不一定是由變量的性質(zhì)決定的, 更多地是由于邏輯關(guān)系引進問題的例5 背包問題一個旅行者的背包最多只能裝 6 kg 物品. 現(xiàn)有4 件物品的重量和價值分別為 2 kg , 3 kg, 3 kg, 4 kg, 1 元, 1.2元, 0.9元, 1.1元. 應(yīng)攜帶那些物品使得攜帶物品的價值

10、最大?建模: 記 xj為旅行者攜帶第 j 件物品的件數(shù), 取值只能為 0 或 1.求目標函數(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 多目標線性規(guī)劃目標函數(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)整體評價法min S=S(f (k) - c(k)T x)/ f (k) （使相對偏差最小）s.t. Ax £ b A1x=b1 LB £ x £ UB有最佳妥協(xié)解習題:1.資源的最優(yōu)配置策略某工廠有1000臺機器, 生產(chǎn)兩種產(chǎn)品 A, B, 若投入 y 臺機器生產(chǎn)A 產(chǎn)品, 則純收入為 5y .若投入 y 臺機器生產(chǎn)B 產(chǎn)品, 則純收入為 4y . 又