《数学建模培训之数学规划模型演示课件》由会员分享，可在线阅读，更多相关《数学建模培训之数学规划模型演示课件（40页珍藏版）》请在金锄头文库上搜索。
1、1,数 学 建 模,Mathematical Modelling,2,第一讲 数学规划模型,3,优化问题： 现实世界当中经常遇到的一类问题。,最优化方法： 解决优化问题的数学方法。,解决优化问题的基本步骤： 1)建立优化模型; 2)利用优化方法辅以计算机求解 优化模型。,4,优化模型： 1) 数学规划：线性规划 非线性规划 整数规划 动态规划 多目标规划,生产与服务业的运作管理：计划问题、调度问题、运输问题、下料问题，,经济与金融领域：经济均衡问题、投资组合问题、市场营销问题， ,5,2)图与网络的优化模型 运输问题 指派问题 最大匹配问题 最小覆盖问题 最短路问题 最小树问题 行遍性问题(旅
2、行商问题/中国邮递员问题) 网络流问题(最大流/最小费用流) 计划网络图优化问题,6,3)对策论（博弈论）,4)排队论,5)存贮论,参考书：,运筹学(第3版)，运筹学教材编写组编，清华大学出版社,2005,优化建模与LINDO/LINGO软件，谢金星、薛毅 编著，清华大学出版社,2006,7,例1 某公司的甲、乙两个蔬菜生产基地，产量分别为1200kg和900kg，同时供应A、B、C 、D 四个大型超市，其需要量分别为800kg、500kg、500kg、300kg，而从各基地到各超市运送蔬菜的费用为：,试制定一个调运方案，使总的运费最小.,例2 某食品厂有 n 种产品 A1,A2,An，每种产
3、品的单位利润分别为 r1,r2, , rn. 而生产每种产品所需设备数分别为 a1,a2, , an，所需原料的消耗分别为 b1,b2, , bn，所需劳动力分别为 c1, c2, ,cn. 该厂现有的设备、原料和劳动力的总数分别为a,b,c，产品在市场上的需求量分别不超过q1, q2, , qn . 该厂若要获得最大利润，应如何制定生产计划？,数学规划 (Mathematical Programming),8,例3. 某加工厂制作一批钢架，需 50 根 4 m，20 根 6 m 和 15 根 8 m 的同型号钢管，而从钢管厂购进的该型号的原料钢管长度均为 19m. 问应如何下料能最节省 ？,
4、例4. 某建筑公司有6个工地同时开工，每个工地的位置 ( 用平面坐标系 (ai,bi) 表示，距离单位:km ) 及水泥日用量di (单位: t )为,目前位于A(5,1)和B(2,7)处有两个临时料场，日储量各20 t.假定从料场到各工地均为直线道路. (1)对A,B两料场，制定每天的供应计划，使总的吨千米数最小；(2)舍弃A,B两料场，修建两个新料场，日储量不变，问应建于何处？总的吨千米数减少了多少？,9,线性规划( Linear Programming, LP ),其中 c = (c1, , cn)T, x = (x1, , xn)T ，,b = (b1, , bm)T .,10,线性规
5、划的求解,例1,11,线性规划的基本性质,（1）若 LP 存在可行域，则其可行域为凸集（凸多面体）；,（2）x 为 LP 的基可行解的充分必要条件是 x 为其可行域的极点（顶点）；,（3）若 LP 存在最优解，则其最优解一定在其可行域的极点上得到。,求解线性规划：,（1）求基可行解（可行域的极点）；,（2）在基可行解中寻找最优解。,从某个基可行解出发，通过迭代法沿目标函数值下降最快的方向求另一个基可行解。经有限次迭代，便可得到 LP 的最优解。,12,，x1, x2为整数,整数规划( Integer Programming, IP ),13,其中 x = (x1, , xn)T, g(x)=
6、(g1( x ), , gm( x) ) T, 而 S= x | g(x) 0 Rn 为该数学规划的可行域。,非线性规划( Nonlinear Programming, NLP ),或,14,设 x*S，而 xS 有 f (x) f (x*)，则称 x* 为NLP的全局最优解， f (x*) 为NLP的全局最优值(全局极小值)。,非线性规划,设 x*S，若 U(x*) 使 x U(x*)S，有 f (x) f (x*)， 则称 x* 为NLP的局部最优解， f (x*) 为NLP的局部最优值(局部极小值) 。,设SRn，x*S ， f (x) 在 x* 处取得局部极值的必要条件为 f (x*)
7、 = = 0；,f (x) 在 x* 处取得局部极小值的充分条件为 f (x*) = 0，且2f (x*) = 正定。,15,数值迭代法,无约束NLP的求解,Step2 对于第k次迭代解 x(k)，确定一个搜索方向p(k)Rn，并在此方向上确定搜索步长 tk R，令 x(k+1) = x(k) + tk p(k)， 使 f (x(k+1) ) f (x(k) )；,若可行域 S= Rn：无约束NLP ；否则S Rn ：带约束NLP。,Step1 选择初始解 x(0)；,Step3 若 x(k+1)满足给定的迭代终止准则，停止迭代，最优解 x*= x(k+1)；否则，转Step2。,非线性规划,
8、16,搜索方向的选择,1. 最速下降法（梯度法）： 取 p(k)= f (x(k),2. Newton法： 取 p(k)= 2f (x(k)1 f (x(k),拟Newton法、共轭梯度法,搜索步长的确定,搜索方向 p(k) 确定后，确定步长成为一维优化问题：即求 tk 使,一维搜索方法（线性搜索）,黄金分割法、Fibonacci法、求根法，插值法（二次、三次）,直接搜索方法,步长加速法、方向加速法、单纯形法,17,带约束NLP的求解,两种途径：,可行域内直接寻优,约束问题化为无约束问题求解,1. 可行方向法：,可行方向：设 x S ，若 0 ，使 t 0, 均有 x+t p S , 则方向
9、p 称为 x 的一个可行方向；,迭代时取 p(k) 为可行下降方向 ，即取 p(k)同时满足,下降方向：设 x S ，若 0 ，使 t 0, 均有 f (x+t p ) f (x), 则方向 p 称为 x 的一个下降方向；,f (x(k)T p(k) 0,gj (x(k)T p(k) 0，j j| gj (x(k)=0,1 j m,18,2. 罚函数法：,利用目标函数 f (x)和约束函数 g (x) 构造带参数的“增广”目标函数 ，将约束NLP 转化为一系列无约束NLP来求解： min F(x) = f (x) + Pk(x) 其中Pk(x)为由g (x)构成的“惩罚”函数。,外部罚函数法：
10、取Pk(x)= Mk,内部罚函数法：取Pk(x)= rk,其中 0 M1 M2 Mk 为选取的单增趋于无穷的数列,其中 r1r2 rk 0 为选取的单减趋于0的数列,19,现代优化的计算方法：,（除经典的规划求解方法外）,局部搜索和禁忌搜索算法 模拟退火算法 遗传算法 蚁群算法 人工神经网络,20,例1. 投资的收益与风险(CUMCM98A).,市场上有 n 种资产(股票、债券、) Si (i=1,2,n).,某公司有一笔相当大的资金(数额为 M )可作一个时期的投资.,该公司的评估和预测:投资 Si 的平均收益率 ri , 风险损失率 qi .,投资越分散, 总体风险越低. 总体风险可用所投
11、资的 Si 中最大的一个风险来度量.,购买 Si 的交易费率 pi , 且购买量不超过 ui 时按购买 ui 计算.,同期银行存款利率 r0 (取 5%) ,无交易费用无风险.,给该公司设计一种投资组合方案，使净收益尽可能大，总体风险尽可能小.,21,基本假设,1.投资数额M相当大；,2.投资越分散总的风险越小；,3.总体风险用所投资项目Si中最大的风险来度量；,4.n种资产Si之间相互独立；,5.在投资期间，ri, pi, qi 为定值，不受意外因素影响；,6.净收益和总体风险只受 ri,pi,qi 影响，不受其他因素干扰.,22,23,例2. 洗衣机的节水设计(CUMCM96B).,我国淡
12、水资源有限，节约用水人人有责。洗衣在家庭用水中占有相当大的份额，节约洗衣机的用水十分重要。假设在放入衣物和洗涤剂后洗衣机的运行过程为：加水漂洗脱水加水漂洗脱水加水漂洗脱水(称“加水漂洗脱水”为运行“一轮”)。请为洗衣机设计一种程序(包括运行多少轮，每轮加水量等)，使得在满足一定洗涤效果的条件下，总的用水量最少。选用合理的数据进行计算。,24,问题分析,洗衣的基本原理：将吸附在衣物上的污物溶于水中，通过脱去污水而带走污物，即 溶污物脱污水,洗衣的过程：通过加水来实现溶污物脱污水动作的反复进行，使得残留在衣物上的污物越来越少，直至达到满意程度。,溶污物“洗涤”（首轮）和“漂洗”,脱污水“排水” 和
13、“甩干”,问题的要点：,1）污物溶解的情况？,2）每轮洗涤后污物减少的情况？,3）由一系列“加水漂洗脱水”构成的节水洗涤程序？,25,基本假设,1）仅考虑离散的洗涤方案，即“加水漂洗脱水”三个环节是分离的，这三个环节构成一个洗涤周期，称为“一轮”；,2）节水洗涤程序设计只考虑洗涤的轮数和加水量；,3）每轮用水量不能低于L，以保证洗衣机工作，不能高于H，否则水会溢出，显然不节水；,4）每轮漂洗时间足够，以使衣物上的污物充分溶解水中，使每轮的加水被充分利用；,5）每轮脱水时间足够，以使污水充分脱出，即衣物中所含的污水量达到一个低限c，设0cL ；,变量,1）漂洗共进行n 轮，k =0,1,2,n1
14、；,2）第k轮用水量为uk，k =0,1,2,n1；,3）衣物上的初始污物量为x0，第k轮脱水后衣物上附着的污物量为xk+1，k =0,1,2,n1.,26,仿真计算,数据：取 =103，L/H=0.25，c/H=105,结果：,27,第二讲 概率及其 分布模型,28,随机现象:由一系列随机因素影响所造成的不确定现象,随机现象规律性的刻画： 概率 和概率分布,随机事件概率的计算,随机事件: 随机现象的具体表象,古典概率 几何概率 统计概率,全概率公式：,加法公式：P(AB)= P(A)+ P(B)P(AB),乘法公式：P(AB)= P(A) P(B|A),贝叶斯公式：,二项概率公式：,29,随
15、机变量的概率分布, r 项分布, 泊松分布, 超几何分布, 几何分布, 均匀分布, 指数分布, 正态分布（高斯分布）, 巴斯卡分布, 伽玛分布, 贝塔分布, 对数正态分布, 威布尔分布,概率分布的实例, 一段时间内，电话交换机接收到的用户呼叫次数，公共汽车站来到的候车乘客数，超市中排队等待付款的顾客数，随机服务窗口接待的人数，某种放射性物质放射的粒子数，显微镜下落在某区域的微生物数目，昆虫的产卵数目，事故、故障、灾害性事件的数目，一个产品的疵点数等都服从泊松分布；,泊松分布是二项分布的极限分布；,30,贝努利概型是二项分布的实际背景，例如有限总体的有放回抽样的次品数目服从二项分布；而不放回抽样
16、的次品数目服从超几何分布；,随机到达车站的乘客的候车时间，定点数值计算中四舍五入的舍入误差等服从均匀分布；,贝努利试验中事件A首次发生时的试验次数服从几何分布；,无线电元器件和玻璃器皿等的寿命，动物的寿命，电话问题中的通话时长，随机服务窗口的服务时间等服从指数分布；,工业中机电产品（如轴承、刀具等）的寿命常服从威布尔分布；,31,测量误差，工业产品的尺寸、强度等质量指标，人体的身高、体重，农作物的产量，炮弹的弹落点的分布，气象中的月气温、月湿度、月降水量，考试的成绩分布等都服从正态分布；,二项分布的极限分布是正态分布；一般地，众多独立的影响因素的综合作用结果往往服从或近似服从正态分布；,绝缘材料的寿命，设备故障的维修时间，一个家庭中两个孩子的年龄之差等服从对数正态
