mm05-规划模型.ppt

数学建模,*,单击此处编辑母版标题样式,规划模型,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,数学建模,规划模型,1,数 学 建 模,从自然走向理性之路,数学建模,2,规划模型,第五讲,规划模型,【,主要内容,】,介绍线性规划模型、非线性规划模型及动态规划模型,【,主要目的,】,了解规划问题的建模与求解，重点在模型的建立与结果的分析,数学建模,3,规划模型,线性规划模型,(,Linear Programming),建立模型,线性规划问题：求多变量,线性函数,在,线性约束,条件下的,最优值,线性规划问题的一般形式：,数学建模,4,规划模型,线性规划问题的标准形式：,数学建模,5,规划模型,说明,任意线性规划问题可化为标准形式具体方式如下：,1.,目标函数标准化：,2.,约束条件标准化,：,假设约束条件中有不等式约束,或,引入新变量 （称为松弛变量），则以上两式等价于以下两式：,数学建模,6,规划模型,3.,自由变量标准化,若变量,x,j,无约束，可引入两个新变量 ，令,故以下我们只考虑标准形式数学建模,7,规划模型,矩阵形式表示,一般要求，,数学建模,8,规划模型,例,1,某工厂制造,A,B,两种产品，制造产品,A,每吨需用煤,9,吨，用电,4,千瓦，,3,个工作日；制造产品,B,每吨需用煤,5,吨，用电,5,千瓦，,10,个工作日。

已知制造产品,A,和,B,每吨分别获利,7000,元和,12000,元现该厂只有煤,360,吨，电,200,千瓦，工作日,300,个可以利用，问,A,B,两种产品各应生产多少吨才能获利最大？,解,x,1,x,2,分别表示,A,B,两种产品的计划生产数（单位：吨），,f,表示利润（单位：千元），则,f,=7,x,1,+12,x,2,数学建模,9,规划模型,耗煤量为,9,x,1,+5,x,2,耗电量为,4,x,1,+5,x,2,耗工作日,3,x,1,+10,x,2,于是得到线性规划模型为：,数学建模,10,规划模型,例,2,设某工厂有甲、乙、丙、丁四个车间，生产,A,、,B,、,C,、,D,、,E,、,F,六种产品，根据机车性能和以前的生产情况，得知生产每单位产品所需各车间的工作时数、每个车间在一个季度工作时数的上限以及产品的价格，如下表所示问：每种产品每季度各应生产多少，才能使这个工厂每季度生产总值达到最大？,数学建模,11,规划模型,产品,车间,A,B,C,D,E,F,每个车间每季度,工作时数上限,甲,乙,丙,丁,0.01,0.02,0.01,0.02,0.01,0.03,0.030.05,0.03,0.05,0.03,0.08,850,700,100,900,单价（元）,0.40,0.28,0.32,0.72,0.64,0.60,数学建模,12,规划模型,解,以,x,1,x,6,分别表示每季度生产产品,A,、,B,、,C,、,D,、,E,、,F,的单位数，于是它们需满足,目标函数为,数学建模,13,规划模型,引入松弛变量,x,7,x,10,，化成标准型,数学建模,14,规划模型,线性规划问题求解,1.,可行域几何特征,满足约束条件的解称为,可行解,，所有可行解构成的集合称为,可行域,，满足目标式的可行解称为,最优解,。

线性规划问题的可行域是一个凸多边形；,线性规划问题如果存在最优解，则最优解必在可行域的顶点处达到数学建模,15,规划模型,2.,单纯形法,基本思想：从可行域的一个顶点（基本可行解）出发，转换到另一个顶点，并且使目标函数值逐步减小，有限步后可得到最优解数学建模,16,规划模型,整数规划,自变量取整数的线性规划称为整数（线性）规划割平面法，分支定界法,数学建模,17,规划模型,0,1,规划,例,3,（,MCM-88B,）要把七,种不同规格的包装箱装到两辆铁,路平板车上去，各包装箱宽、高,均相同，但厚度（厘米）与重量,（公斤）不同下表给出各包装箱的厚度、重量及数量每辆平板车有,10.2,米长的地方可用来装包装箱，载重,40,吨由,于当地货运限制，对,C,5,C,6,C,7,类包装箱总数有一个特别限制：该,类箱子总厚度不超过,302.7,（厘米）试把包装箱装到平板车上去使,得浪费空间最小数学建模,18,规划模型,C,1,C,2,C,3,C,4,C,5,C,6,C,7,厚度,t,48.7,52.0,61.3,72.0,48.7,52.0,64.0,重量,w,2000,3000,1000,500,4000,2000,1000,件数,n,8,7,9,6,6,4,8,1.,问题分析,题中所有的包装箱共重,89,吨，而两辆平板车只能载,80,吨，因此不能都装下，问题是装哪些箱子，使剩余空间最小。

数学建模,19,规划模型,2.,模型建立,设,x,ij,=,第,i,辆车装,C,j,类箱子的个数，,i,=1,2,j,=1,7,自然约束：,箱数约束：,重量约束：,厚度约束：,特别约束：,数学建模,20,规划模型,目标函数,例,4,分工问题,某车间有四项工作需要完成，现已找到四个人做这些工作，经过试用，得到这四个人做每一项工作的相对生产率指数，列表如下假定每个人只能分派一项工作，并希望分派后总的生产率最高，应如何分派工作？,数学建模,21,规划模型,令,工作,人员,1,2,3,4,1,2,3,4,5,3,4,1,7,6,3,4,10,8,6,2,3,4,2,10,数学建模,22,规划模型,每个人做一项工作,每项工作有一人做,目标函数,数学建模,23,规划模型,非线性规划模型,(Nonlinear Programming),例,5,飞行管理问题（,CUMCM95A),在高空中一个边长为,160,公里的正方形区域内，经常有若干架飞机作水平飞行区域内每架飞机的位置和速度均由计算机记录其数据当一架欲进入该区域的飞机到达区域边缘时，要立即计算并判断其是否会与区域内的飞机碰撞如果会碰撞，则要计算如何调整各架（包括新进入的）飞机飞行的方向角，以避免碰撞。

现假定条件如下：,数学建模,24,规划模型,不碰撞的标准为任意两架飞机的距离大于,8,公里；,每架飞机飞行方向角调整的幅度不应超过,30,度；,所有飞机飞行速度均为,800,公里,/,小时；,欲进入飞机在到达区域边缘时，与区域内飞机的距离应在,60,公里以上；,最多需考虑,6,架飞机；,不必考虑飞机离开此区域后的状况请你建立数学模型，对以下数据进行计算（方向角误差不超过,0.01,度），要求飞机飞行方向角调整的幅度尽量小数据略）,数学建模,25,规划模型,模型建立与求解,模型一：设第,i,架飞机在调整时的 方向角为,i,调整角度为,i,（,i,1,，,2,，,，,6,）,设任意两架飞机在区域内的最短距离为,d,ij,(,i,j,),，那么问题的非线性规划模型为,数学建模,26,规划模型,解法：能量梯度法、惩罚函数法、序列无约束最小,化方法、逐步逼近搜索法等,模型二：,模型三：,数学建模,27,规划模型,利用相对运动的方法得到以上模型，再简化为线性规划问题求解数学建模,28,规划模型,动态规划模型,(,Dynamic Programming,),动态规划是解决多阶段决策过程最优化的一种方法。

多阶段决策问题，是指一个问题可以分为若干个阶段，每一阶段需要做出决策，而一个阶段的决策，常常会影响下一个阶段的决策要在各个阶段决定一个最优决策，使整个系统达到最佳的效果通过以下一个典型例子，说明如何建立动态规划模型数学建模,29,规划模型,例,6,最短路线问题,数学建模,30,规划模型,先引入几个概念,状态,每一阶段的起点位置,决策,由一个状态变到另一个状态的选择,x,k,第,k,阶段的状态，称为状态变量,u,k,（,x,k,）,从,x,k,出发所作出的决策，称为决策变量,D,k,（,x,k,）,第,k,阶段中所有允许决策的集合,状态转移方程,x,k+1,=,T,k,(,x,k,u,k,),d,k,(,x,k,u,k,）,从状态,x,k,出发，采取决策,u,k,，转移到状态,x,k+1,的效益,f,k,（,x,k,）,从状态,x,k,出发到终点的最优效益,数学建模,31,规划模型,最短路问题的动态规划最优化原理,:,假设一条最短路线经过状态,x,k,，那么，这条路线上从,x,k,到终点的一段，是从,x,k,出发到终点的所有路线中最短的逆序法,（回溯法）：,从后向前逐步求出各点到终点的最佳路线，最后得到由起点到终点的最短路线。

数学建模,32,规划模型,最短路问题的动态规划模型，归纳为下述递推公式：,从最后一段开始，,k,=4,有三个状态,D,1,D,2,D,3,k,=3,，,有,4,个状态,C,i,i=,1,2,3,4.,每个状态有两个决策可选择分别,计算各状态出发到终点的效益,f,3,(,C,i,),：,数学建模,33,规划模型,最短路径：,最短路径：,数学建模,34,规划模型,最短路径：,最短路径：,数学建模,35,规划模型,k,=2,时,有两个状态,B,1,B,2,，每个状态有,3,个决策可选最短路径：,数学建模,36,规划模型,最短路径：,或者,k,=1,时，,最短路径：,路径长为：,14,数学建模,37,规划模型,Bellman,动态规划最优化原理,整个过程的最优策略应具有性质：无论过去的状态和决策如何，对当前状态而言，余下的诸决策必须构成最优策略数学建模,38,规划模型,动态规划的特点是将问题按时间或空间特征而分成若干个阶段，从而将整个决策过程转化为多阶段的决策问题对某些静态决策问题可以引入时间因素，将问题转化为多阶段的决策问题，然后利用动态规划方法求解以上最短路问题的解决就是这样的一个例子，以下再举一个例子。

数学建模,39,规划模型,资源分配问题,设有某种资源总数量为,a,，用于生产,n,种产品如果分配数量,x,k,用于生产第,k,种产品，其效益为,g,k,(,x,k,),问应如何分配资源使生产总效益最大？,静态模型为,数学建模,40,规划模型,非线性规划问题，应用动态规划方法求解令,s,k,表示分配用于生产第,k,种至第,n,种产品的资源数量，即状态转移方程,s,k,1,s,k,x,k,（,s,1,a,，,s,n,1,0,），,f,k,(,s,k,),为最大效益则逆序递推方程为,数学建模,41,规划模型,The End !,Thanks!,。