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

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

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

4、標函數在各極點處的值，經比較后，取最值點為最優解。命題3 當兩個變量的線性規劃問題的目標函數取不同的目標值時，構成一族平行直線,目標值的大小描述了直線離原點的遠近。于是穿過可行域的目標直線組中最遠離(或接近)原點的直線所穿過的凸多邊形的頂點即為取的極值的極點最優解。單純形法 : 通過確定約束方程組的基本解, 并計算相應目標函數值, 在可行解集的極點中搜尋最優解. 正則模型: 決策變量: x1,x2,xn. 目標函數: Z=c1x1+c2x2+cnxn. 約束條件: a11x1+a1nxnb1, am1x1+amnxnbm,模型的標準化1. 引入松弛變量將不等式約束變為等式約束. 若有 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. 將目標函數的優化變為目標函數的極大化. 若求 min Z, 令 Z=Z, 則問題變為 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求解：標準的線性規劃的模型： min f=cTxs.t. Ax £ b A1x=b1 LB £ x £ UBMatlab求解程序: x,f=linprog(c,A,b,A1,b1,LB,UB)還有軟件Excel 也可應用于解優化問題。例 2 供貨問題一家公司生產某種商品。現有n個客戶,第j個客戶需要貨物量至少為bj,可在m各不同地點設廠供貨.在地區i設廠的費用為di ,供貨能力為hi ,向第j個客戶供應單位數量的貨物費用為

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

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

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

10、最大?建模: 記 xj為旅行者攜帶第 j 件物品的件數, 取值只能為 0 或 1.求目標函數 f=x 1 +1.2x 2 +0.9x 3 +1.1x 4 在約束條件 2x 1 +3x 2 +3x 3 +4x 4 £ 6下的最大值. 用Lingo 軟件求解0-1規劃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 多目標線性規劃目標函數 fk=c (k)T x k=1,2, ¼, m,s.t. Ax £ b A1x=b1 LB £ x £ UB有最優解 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有最佳妥協解習題:1.資源的最優配置策略某工廠有1000臺機器, 生產兩種產品 A, B, 若投入 y 臺機器生產A 產品, 則純收入為 5y .若投入 y 臺機器生產B 產品, 則純收入為 4y . 又