数学建模协会简报

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 . 又