数学建模运筹学部分

,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,全国大学生数学建模竞赛 China Undergraduate Mathematical Contest in Modeling (CUMCM),国际大学生数学建模竞赛,The Mathematical Contest in Modeling (MCM),往年数模试题,1993年A题 非线性交调的频率设计 1993年B题 球队排名问题,1994年A题 逢山开路 1994年B题 锁具装箱,1995年A题 一个飞行管理模型 1995年B题 天车与冶炼炉的作业调度,1996年A题 最优捕鱼策略 1996年B题 节水洗衣机,1997年A题 零件的参数设计 1997年B题 截断切割,1998年A题 投资的收益和风险 1998年B题 灾情巡视路线,1999年A题 自动化车床管理 1999年B题 钻井布局,2000年A题 DNA序列分类 2000年B题 钢管定购和运输,2001年A题 血管的三维重建 2001年B题 公交车调度,2002年A题 车灯线光源的优化设计 2002年B题 彩票中的数学,2003年A题 SARS的传播 2003年B题 露天矿生产的车辆安排,2004年A题 奥运会临时超市网点设计 2004年B题 电力市场的输电阻塞管理,2005年A题 长江水质的评价和预测 2005年B题DVD在线租赁,2006年A题 出版社的资源配置 2006年B题艾滋病疗法评价及疗效预测,2007年A题 人口预测 2007年B题 乘公交 看奥运,2021年A题 高校学费标准 2021年B题 电子眼定位,2021年A题 制动器试验台的控制方法分析 2021年B题眼科病床的合理安排,运筹学中的优化模型及辅助软件求解,数学建模步骤示意图,模型准备,模型假设,模型检验,模型应用,模型分析,模型求解,模型构成,优化问题与规划模型,解决最优化问题的数学方法：运筹学,运筹学主要分支：,线性规划、非线性规划、动态规划、,图与网络分析、存贮论、排队伦、,对策论、决策论。,它们的特点就是：在假设干可能的方案中寻求某种意义下的最优方案。数学上称为最优化问题,而研究处理这种问题的方法叫最优化的方法。,实例：家具生产的安排 家具公司生产桌子和椅子，用于生产的劳力共计450个工时，木材共有4立方米,每张桌子要使用15个工时、0.2立方木材，售价80元。每张椅子使用10个工时、0.05立方木材，售价45元。问为到达最大的收益，应如何安排生产？,分析：,1. 求什么？,生产多少桌子？ x1 生产多少椅子？ x2,2. 优化什么？,收益最大 Max f=80 x1+45 x2,3. 限制条件？,原料总量 0.2 x1 +0.05 x2 4 劳力总数 15 x1 +10 x2 450,模型：以产值为目标取得最大收益. 设：生产桌子 x1张, 椅子 x2张,(决策变量) 将目标优化为：max f=80x1+45x2 对决策变量的约束： 0.2x1+0.05x24 15x1+10x2 450, x1 0, x2 0,模型求解：1图解法用于决策变量是二维,15x1+10x2=450,x1,x2,0.2x1+0.05x2=4,线性规划问题的目标函数(关于不同的目标值是一族平行直线)目标值的大小描述了直线离原点的远近,并且最优解一定在可行解集的某个极点上到达(穿过可行域的目标直线组中最远离(或接近)原点的直线所穿过的凸多边形的顶点).,2用EXCELSolver实现模型中的数据直接输入EXCEL工作表中。其中决策变量初始的值可以任意给出，它们是可变的，软件最后将给出最优解的值。SUMPRODUCT是EXCEL的一个内置函数，表示两个向量或矩阵对应元素乘积的和。,引用工具规划求解需要工具加载宏安装,混合线性规划的EXCEL求解,求解模型步骤：,翻开Microsoft Excel 的一个工作表；,把模型的目标函数系数矩阵置于A1至E4区域，约束常数25000、30000和21000分别置于G6、G7和G8单元格；,选择A6至E9范围作可变单元，并输入初值1。其中A6至E8区域对应变量xij(i=1,2,3; j=0,1,2,3,4)，而B9至E9那么分别对应变量y1, y2, y3,和y4,A9那么恒为1；,在F6、F7、F8和F9处分别输入“=SUMA6：E6、“=SUMA7：E7、“=SUMA8：E8、“=SUMB9：E9,再在A10至E10处分别输入“=A6+A7+A8、 “=B6+B7+B8-41000*B9、 “=C6+C7+C8-41000*C9、 “=D6+D7+D8-41000*D9、“=E6+E7+E8-41000*E9表示约束等式的左边；,选择单元格A11, 输入“=A1*A6,再把其引用至单元格E14;即用鼠标按着单元格A11的右下角，先拖至A14, 再拖至E14;,以单元格F14作目标单元格，输入“=SUM(A11:E14),结果如下图：,进入“规划求解界面。“设置目标单元格处输入“F14,然后选“最小值，再在“可变单元格处输入“A6:E9,在“约束处添加12个约束：“A6：E8=0、“A9=1、“B9：E9二进制、“A10=35000、“B10=0、 “C10=0、 “D10=0、 “E10=0、“F6=G6、 “F7=G7、 “F8=G8、 “F9=1。最后，规划求解参数界面如图8。再在“选项中选择“采用线性模型。,单击求解，即可得到此问题的解。,结果：,目录,3用Matlab实现- lp 线性优化函数线性优化问题即目标函数和约束条件均为线性函数的问题。其标准形式为：,化为,程序如下：,c=-2，-1,1;A=1，4，-1；2，-2，1;b=4,12;Aeq=1，1，2;beq=6;LB0,0,-inf; UB=inf,inf,5;x,z=,linprog,(c,A,b,Aeq,beq,LB,UB) 运行结果：x = 4.6667 0.0000 0.6667z = -8.6667说明：,x解为最优解,，目标最大为8.6667。,4用LINDO/LINGO实现我们可以直接在下面的窗口输入LP模型,输入后，用鼠标单击LINDO软件工具栏中的图标 ，或从菜单中选择SolveSolve(Ctrsl+S)命令，那么LINDO开始编译这个模型，编译没错误马上开始求解，求解时会显示如图42所示LINDO求解器运行状态窗口里面的“Objective就是最优解，即：2200。,图42,“LP OPTIMUM FOUND AT STEP 2表示单纯形法在两次迭代后得到最优解。,“OBJECTIVE FUNCTION VALUE 1) 2200.000表示最优目标值为2200.000在LINDO中目标函数所在的行总是被认为是第1行，这就是这里“1的含义。,返回,一般模型的建立,某机器厂生产、两种产品，需在A、B、C三中不同的设备上加工。具体耗时如下表：,问：如何生产使得利润最大？,A,B,C,利润,产品,2h,4,0,2,产品,2,0,5,3,能力时限,12,16,15,建立模型,模型假设：,设 和 分别表示、两种产品在方案期内的产量，利润收入为 。,模型建立：,目标函数：,约束条件：,目标规划,线性规划问题的一般模型：,s.t.,例 某部门有资金200万元，今后5年内考虑给以下的工程投资。,工程A：从第一年到第五年每年年初都可投资，当年年末可收回本利110；,工程B：从第一年到第四年年初都可投资，次年末可收回本利125，投资额 30万；,工程C：第三年初投资，第五年末能收回本利140，投资额 80万；,工程D：第二年初投资，第五年末能收回本利155，投资额 100万；,问：如何投资使得第五年末资金额最大？,1.模型假设,设 为第i年年初投入第j种方案的资金数。,2.模型分析,i年初,1 2 3 4 5,本利,限量,A,B,C,D,110%,125%,140%,155%,30,80,100,3.模型建立,目标函数：,约束条件：,第一年年初：,第二年年初：,第三年年初：,第四年年初：,第五年年初：,各变量都要大于等于零，且在各方案投资限量范围内。,目标函数其实就是第五年的收益。,求解方法,方法：图解法只能求解两个变量的问题,单纯形法,大M法,两阶段法,结合对偶单纯形法可以对线性规划问题进行灵敏度分析及参数规划。,运输问题,某糖果公司下面设有三个分工厂，每天的糖果生产量分别为：A17t，A24t， A39t。该公司把这些糖果分别运往四个地区的门市部销售，各地区每天的销售量为：B13t，B26t，B35t，B46t。从每个加工厂到各销售门市部每吨糖果的运价如下表所示，问该食品公司应如何调运，在满足各门市部销售需要的情况下，使总的运费支出为最少。,销地,产地,B1 B2 B3 B4,产量,A1,A2,A3,3 11 3 10,1 9 2 8,7 4 10 5,7,4,9,销量,3 6 5 6,模型假设：,设 代表从第i个产地调运给第j个销地的物资的单位数量。,模型建立：,目标函数,约束条件,s.t.,一般模型,方法：表上作业法找初始解：最小元素法、Vogel法;调整：闭回路法、位势法,s.t.,整数规划,特点：在线性规划问题中加一个约束变量取整数解。,求解的方法有：匈牙利法、分枝定界法、割平面法,动态规划模型的分类,以“时间角度可分成：,离散型和连续型。,从信息确定与否可分成：,确定型和随机型。,从目标函数的个数可分成：,单目标型和多目标型。,动态规划,动态规划的根本原理,多阶段决策过程最优化,多阶段决策过程是指这样一类特殊的活动过程，他们可以按时间顺序分解成假设干相互联系的阶段，在每个阶段都要做出决策，全部过程的决策是一个决策序列，所以多阶段决策问题也称为序贯决策问题。,例一定阶段最短路问题,W先生每天驾车去公司上班。如图，W先生的住所位于A，公司位于F，图中的直线段代表公路，交叉点代表路口，直线段上的数字代表两路口之间的平均行驶时间。现在W先生的问题是要确定一条最省时的上班路线。,A 3 B1 4 C1 3 D1,4 5 3 2,B2 2 C2 3 D2 E1,1 2 3 4,C3 4 D3 5 E2 2 F,A,B1,B2,C1,C2,C3,D1,D2,D3,E1,E2,F,4,1,5,4,4,4,4,5,3,3,3,3,3,2,2,2,2,A,B,C,D,E,F,1 阶段Stage,将所给问题的过程，按时间或空间特征分解成假设干个相互联系的阶段，以便按次序去求每阶段的解，常用k表示阶段变量。,我们把从A到F看成一个五阶段问题。,2 状态State,各阶段开始时的客观条件叫做状态。描述各阶段状态的变量称为状态变量，常用sk表示第k阶段的状态变量，状态变量的取值集合称为状态集合，用Sk表示。,动态规划中的状态具有如下性质：,当某阶段状态给定以后，在这阶段以后的过程的开展不受这段以前各段状态的影响。即：过程的过去历史只能通过当前状态去影响它未来的开展，这称为无后效性。如果所选定的变量不具备无后效性，就不能作为状态变量来构造动态规划模型。,3 决策和策略,Decision and Policy,当各段的状态确定以后，就可以做出不同的决定或选择，从而确定下一阶段的状态，这种决定称为决策。决策变量用dk(Sk)表示，允许决策集合用Dk(Sk)表示。,各个阶段决策确定后，整个问题的决策序列就构成一个策略，用p1,n(d1,d2,dn)表示。对每个实际问题，可供选择的策略有一定的范围，称为允许策略集合，用P表示。使整个问题到达最优效果的策略就是最优策略。,4 状态转移方程,动态规划中本阶段的状态往往是上一阶段的决策结果。如果给定了第k段的状态Sk ，本阶段决策为dk(Sk) ，那么第k+1段的状态Sk+1由公式： Sk+1=Tk Sk， dk,确定，称为状态转移方程。,5 指标函数,用于衡量所选定策略优劣的数量指标称为指标函数。最优指标函数记为,f,k,(S,k,)。,动态规划的根本思想：,从过程的最后一段开始，用逆序递推方法求解，逐步求出各段各点到终点E最短路线，最后求出A点到E点的最短路线。,动态规划的函数方程DP,建立DP函数方程是指确定过程的阶段及阶段数，规定状态变量和决策变量的取法，给出各阶段的状态集合，允许决策集合，状态转移方程和指标函数等。,在上面的计算过程中，利用了第k阶段与第k+1阶段的关系：,fk(Sk)= Min r(Sk,dk(Sk)+fk+1(Sk+1),dk(Sk) k=1,2,3,4,5,f6(S6)=0,这种递推关系，称为动态规划的函数根本方程。,贝尔曼(,Ballman,)最优化原理,作为整个过程的最优策略具有这样的性质，即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。这就是说，不管引导到这个现时状态的头一个状态和决策是什么，所有的未来决策应是最优的。,动态规划的优点：,可把一个,N,维优化问题化成,N,个一维优化问题求解。,DP,方程中附加某些约束条件，可使求解更加容易。,求得最优解以后，可得所有子问题的最优解。,动态规划的缺点：,“一个问题，“一个模型，“一个求解方法。且求解技巧要求比较高，没有统一处理方法。,状态变量维数不能太高，一般要求小于6。,层次分析法,在管理中，人们常常需要对一些情况作出决策：例如企业的决策者要决定购置哪种设备，上马什么产品；经理要从假设干求职者中决定录用哪些人员；地区、部门官员要对人口、交通、经济、环境等领域的开展规划作出决策。,在日常生活中也常会遇到，在多种类不同特征的商品中选购。报考学校选择志愿。毕业时选择工作岗位等。,AHP法的特征：定性与定量相结合，把人们的思维过程层次化，数量化。,运用AHP法进行决策时，可以分4个步骤：,1分析系统中各个因素的关系，建立系统的递阶层次结构；,2对同一层次的各元素关于上一层次中某一准那么的重要性进行两两比较，构造两两比较判断矩阵；,3由判断矩阵计算被比较元素对于该准那么的相对权重；,4计算各层元素对系统目标的合成权重，并进行排序。,建立层次分析的结构模型,用AHP分析问题，首先要把问题条理化、层次化，,构造层次分析的结构模型。这些层次大体可分3类：,1、最高层：在这一层次中只有一个元素，一般是分析问题的预定目标或理想结果，因此又称目标层；,2、中间层：这一层次包括了为实现目标所涉及的中间环节，它可由假设干个层次组成，包括所需要考虑的准那么，子准那么，因此又称为准那么层；,3、最底层：表示为实现目标可供选择的各种措施、决策、方案等，因此又称为措施层或方案层。,决策目标,准那么1,方案1,准那么m1,准那么2,子准那么1,方案2,子准那么2,方案,m,r,子准那么m2,方案层,准则层,目标层,层次分析结构图,目标层：,准那么层：,方案层：,例1、某顾客选购电冰箱时，对市场上正在出售的四种电冰箱考虑6项准那么作为评价依据，得到如下层次分析模型：,例2,设某港务局要改善一条河道的过河运输条件，为此需要确定是否要建立桥梁或隧道以代替现有轮渡。,此问题中过河方式确实定取决于过河方式的效益与代价即本钱。通常我们用费效比效益/代价作为选择方案的标准。为此构造以下两个层次分析的结构模型。,准那么层,过河的效益,A,经济效益,B,1,社会效益,B,2,环境效益,B,3,桥梁,D,1,隧道,D,2,渡船,D,3,收入,c,2,岸间商业,c,3,节省时间,c,1,当地商业,c,4,建筑就业,c,5,平安可靠,c,6,交往沟通,c,7,自豪感,c,8,舒 适,c,9,进出方便,c,10,美 化,c,11,层次分析,方案层,目标层,过河的代价,A,经济代价,B,1,社会代价,B,2,环境代价,B,3,桥梁,D,1,投入资金,c,1,操作维护,c,2,冲击渡船业,c,3,冲击生活方式,c,4,交通拥挤,c,5,居民搬迁,c,6,汽车排废物,c,7,对水的污染,c,8,对生态的破坏,c,9,隧道,D,2,渡船,D,3,层次分析,目标层,准那么层,方案层,多目标规划,同时考虑多个决策目标时，称为多目标规划问题。,目标规划,问题仍为例1，但企业的经营目标不仅仅是利润，而是考虑多个方面，如：,1力求使利润指标不低于15元；,2考虑到市场需求，、两种产品的生产量需保持的比例；,3A为贵重设备，严格禁止超时使用；,4设备C可以适当加班，但要控制；,5设备B既要充分利用，又尽可能不加班；,6重要性上设备B是C的3倍。,具体做法：, 设置偏差变量。用来说明实际值同目标值之间的差异，偏差变量用以下符号表示：,：超出目标的差值，称正偏差变量,：未到达目标的差值，称负偏差变量,与 有下面几种取值情况：, 统一处理目标和约束。只对资源使用上有严格限制的建立系统约束，数学形式上为严格的等式或不等式，同线性规划中的约束条件。,因正负偏差不可能同时出现，故总有,假设要求：的2倍产量不低于的产量，即不希望上式中 ，用目标约束可表示为：,假设要求：的2倍产量低于的产量，即不希望上式中 ，用目标约束可表示为：,假设要求：的2倍产量恰好等于的产量，即不希望上式中 ，又不希望出现 用目标约束可表示为：, 目标的优先级与权系数。,权系数：在一个目标规划的模型中，如果两个不同目标重要程度相差悬殊，为到达某一目标可牺牲其他一些目标，称这些目标是属于不同层次的优先级。,权系数：对属于同一层次优先级的不同目标，按其重要程度可分别乘上不同的系数，这个系数称为权系数。,建立模型,目标函数：,约束条件：,一般模型,s.t.,求解方法,图解法,单纯形法,层次算法,数学规划模型的一般形式：,非线性规划模型,无约束一维搜索方法,t为实数,一维搜索问题指目标函数为单变量的非线性规划问题。又称线性搜索问题。其模型为：,什么叫一维搜索问题？,或,一般一维搜索问题,有效一维搜索问题,一维搜索问题的算法分类：,精确一维搜索最优一维搜索,非精确一维搜索可接受一维搜索,具体方法：,两种精确一维搜索方法：0.618法近似黄金分割法，Newton法。,两种非精确一维搜索方法：Goldstein法,Armijo法。,无约束最优化方法,n,元函数的无约束非线性规划问题：,求解此类模型,(UMP),的方法称为,无约束最优化方法,。,无约束最优化方法通常有两类：,解析法：,要使用导数的方法；,直接法：,无须考虑函数是否可导，直接使用函数值。,方法：最速下降法或梯度法一种解析法,约束最优化方法,本节课讨论约束非线性规划问题,MP,其中,x=(x,1,x,2,x,n,),T,，,f(x),g,i,(x),h,j,(x),为,x,的实值函数,求解此类模型,(MP),的方法称为,约束最优化方法,。,具体方法,惩罚函数法：罚函数法外部惩罚法，障碍函数法内部惩罚法,建模时需要注意的几个根本问题,1、尽量使用实数优化，减少整数约束和整数变量,2、尽量使用光滑优化，减少非光滑约束的个数 如：尽量少使用绝对值、符号函数、多个变量求最大/最小值、四舍五入、取整函数等,3、尽量使用线性模型，减少非线性约束和非线性变量的个数 如x/y 5 改为x5y,4、合理设定变量上下界，尽可能给出变量初始值,5、模型中使用的参数数量级要适当,能用最简浅的数学方法解决别人用高深理论才能解决的答卷是更优秀的答卷 目录,应用实例： 供给与选址,某公司有6个建筑工地要开工，每个工地的位置用平面坐标系a，b表示，距离单位：千米 及水泥日用量d(吨)由下表给出。目前有两个临时料场位于A(5,1)，B(2,7)，日储量各有20吨。假设从料场到工地之间均有直线道路相连。,1试制定每天的供给方案，即从A，B两料场分别向各工地运送多少吨水泥，使总的吨千米数最小。,2为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为20吨，问应建在何处，节省的吨千米数有多大？,一、建立模型,记工地的位置为(ai，bi)，水泥日用量为di，i=1,6;料场位置为(xj，yj)，日储量为ej，j=1,2；从料场j向工地i的运送量为Xij。,当用临时料场时决策变量为：X,ij,，,当不用临时料场时决策变量为：X,ij,，x,j,，y,j,。,二使用临时料场的情形,使用两个临时料场A(5,1)，B(2,7).求从料场j向工地i的运送量为X,ij,，在各工地用量必须满足和各料场运送量不超过日储量的条件下，使总的吨千米数最小，这是线性规划问题. 线性规划模型为：,设X,11,=X,1, X,21,= X,2, X,31,= X,3, X,41,= X,4, X,51,= X,5, X,61,= X,6,X,12,= X,7, X,22,= X,8, X,32,= X,9, X,42,= X,10, X,52,= X,11, X,62,= X,12,计算结果为：,x = 3.0000 5.0000 0.0000 7.0000 0.0000 1.0000 0.0000,0.0000 4.0000 0.0000 6.0000 10.0000,fval = 136.2275,三改建两个新料场的情形,改建两个新料场,要同时确定料场的位置(xj,yj)和运送量Xij，在同样条件下使总吨千米数最小.这是非线性规划问题。非线性规划模型为：,设 X,11,=X,1, X,21,= X,2, X,31,= X,3, X,41,= X,4, X,51,= X,5, X,61,= X,6,X,12,= X,7, X,22,= X,8, X,32,= X,9, X,42,= X,10, X,52,= X,11, X,62,= X,12,x,1,=X,13, y,1,=X,14, x,2,=X,15, y,2,=X,16,1先编写M文件liaoch.m定义目标函数。,(2) 取初值为线性规划的计算结果及临时料场的坐标:,x0=3 5 0 7 0 1 0 0 4 0 6 10 5 1 2 7;,编写主程序gying2.m.,(3) 计算结果为：,x= 3.0000 5.0000 0.0707 7.0000 0 0.9293 0 0 3.9293 0 6.0000,10.0707 6.3875 4.3943 5.7511 7.1867,fval = 105.4626,exitflag = 1,(4) 假设修改主程序gying2.m, 取初值为上面的计算结果:,x0= 3.0000 5.0000 0.0707 7.0000 0 0.9293 0 0 3.9293 0 6.0000 10.0707 6.3875 4.3943 5.7511 7.1867,得结果为:,x=3.0000 5.0000 0.3094 7.0000 0.0108 0.6798 0 0 3.6906 0 5.9892 10.3202 5.5369 4.9194 5.8291 7.2852,fval =103.4760,exitflag = 1,总的吨千米数比上面结果略优.,(5) 假设再取刚得出的结果为初值, 却计算不出最优解.,(6) 假设取初值为:,x0=3 5 4 7 1 0 0 0 0 0 5 11 5.6348 4.8687 7.2479 7.7499,那么计算结果为:,x=3.0000 5.0000 4.0000 7.0000 1.0000 0 0 0 0 0 5.0000 11.0000 5.6959 4.9285 7.2500 7.7500,fval =89.8835,exitflag = 1,总的吨千米数89.8835比上面结果更好.,通过此例可看出fmincon函数在选取初值上的重要性.,钢管订购及运输优化模型,2000年“网易杯全国大学生数学建模竞赛B题,符号说明：,1、铺设总费用：,2、本钱及运输总费用：,总费用=铺设总费用+本钱及运输总费用=C+W,模型的分析与建立,建立模型,模型求解,利用MATLAB软件包求解得：,订购和运输方案表,建模实例与求解,下料问题,露天矿的运输问题2003年B题,钢管运输问题2000年B题,飞行管理问题1995年A题,问题1. 如何下料最节省 ?,例 钢管下料,问题2. 客户增加需求：,原料钢管:每根,19,米,4,米,50,根,6,米,20,根,8,米,15,根,客户需求,节省的标准是什么？,由于采用不同切割模式太多，会增加生产和管理本钱，规定切割模式不能超过3种。如何下料最节省？,5,米,10,根,按照客户需要在一根原料钢管上安排切割的一种组合。,切割模式,余料1米,4,米,1,根,6,米,1,根,8米1根,余料3米,4米1根,6米1根,6米1根,合理切割模式,的余料应小于客户需要钢管的最小尺寸,余料3米,8米1根,8米1根,钢管下料,为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？,合理切割模式,2. 所用原料钢管总根数最少,模式,4米钢管根数,6米钢管根数,8米钢管根数,余料(米),1,4,0,0,3,2,3,1,0,1,3,2,0,1,3,4,1,2,0,3,5,1,1,1,1,6,0,3,0,1,7,0,0,2,3,钢管下料问题1,两种标准,1. 原料钢管剩余总余量最小,x,i,按第,i,种模式切割的原料钢管根数(,i,=,1,2,7,),约束,满足需求,决策变量,目标1总余量,按模式,2,切割,12,根,按模式,5,切割,15,根，余料,27,米,模,式,4米,根数,6米,根数,8米,根数,余,料,1,4,0,0,3,2,3,1,0,1,3,2,0,1,3,4,1,2,0,3,5,1,1,1,1,6,0,3,0,1,7,0,0,2,3,需,求,50,20,15,最优解：,x,2,=12,x,5,=15,其余为0；,最优值：,27,整数约束：,x,i,为整数,当余料没有用处时，,通常以总根数最少为目标,目标2总根数,钢管下料问题1,约束条件不变,最优解：,x,2,=15,x,5,=5,x,7,=5,其余为0；,最优值：,25。,x,i,为整数,按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米,虽余料增加8米，但减少了2根,与目标1的结果“共切割27根，余料27米 相比,钢管下料问题2,对大规模问题，用模型的约束条件界定合理模式,增加一种需求：,5,米,10,根；切割,模式不超过3种。,现有4种,需求：,4,米,50,根，,5,米,10,根，,6,米,20,根，,8,米,15,根，用枚举法确定合理切割模式，过于复杂。,决策变量,x,i,按第,i,种模式切割的原料钢管根数(,i,=,1,2,3,),r,1,i,r,2,i,r,3,i,r,4,i, 第,i,种切割模式下，每根原料钢管生产4米、5米、6米和8米长的钢管的数量,满足需求,模式合理：每根余料不超过3米,整数非线性规划模型,钢管下料问题2,目标函数总根数,约束条件,整数约束：,x,i,r,1,i,r,2,i,r,3,i,r,4,i,(,i,=,1,2,3,),为整数,增加约束，缩小可行域，便于求解,原料钢管总根数下界：,特殊生产方案：对每根原料钢管,模式1：切割成4根4米钢管，需13根；,模式2：切割成1根5米和2根6米钢管，需10根；,模式3：切割成2根8米钢管，需8根。,原料钢管总根数上界：31,模式排列顺序可任定,钢管下料问题2,需求：,4,米,50,根，,5,米,10,根，,6,米,20,根，,8,米,15,根,每根原料钢管长19米,LINGO求解整数非线性规划模型,Local optimal solution found at iteration: 12211,Objective value: 28.00000,Variable Value Reduced Cost,X1,10.00000,0.000000,X2,10.00000,2.000000,X3 8.000000 1.000000,R11,3.000000,0.000000,R12,2.000000,0.000000,R13 0.000000 0.000000,R21,0.000000,0.000000,R22,1.000000,0.000000 R23 0.000000 0.000000 R31,1.000000,0.000000 R32,1.000000,0.000000 R33 0.000000 0.000000 R41,0.000000,0.000000 R42,0.000000,0.000000 R43 2.000000 0.000000,模式1：每根原料钢管切割成3根4米和1根6米钢管，共10根；,模式2：每根原料钢管切割成2根4米、1根5米和1根6米钢管，共10根；,模式3：每根原料钢管切割成2根8米钢管，共8根。,原料钢管总根数为28根。,板材,规格2：,长方形，,32,28cm，,2万张。,易拉罐下料,每周工作40小时，每只易拉罐利润0.10元，原料余料损失0.001元 / cm2不能装配的罐身、盖、底也是余料,模式1：1.5秒,模式2：2秒,模式3：1秒,模式4：3秒,上盖,下底,罐,身,罐身高,10cm,，上,盖,、下底直径均,5cm,。,板材规格,1：,正方形，边长,24cm，5,万张。,如何安排每周生产？,罐身个数,底、盖,个数,余料损失,（,cm,2,）,冲压时间（秒）,模式1,1,10,222.6,1.5,模式2,2,4,183.3,2,模式3,0,16,261.8,1,模式4,4,5,169.5,3,模式1:,正方形,边长,24cm,问题分析,计算各种模式下的余料损失,上、下底直径,d,=5cm，罐身高,h,=10cm。,模式1,余料损失 24,2,-10,d,2,/4,- dh,=222.6,cm,2,问题分析,目标:,易拉罐利润扣除原料余料损失后的净利润最大,约束：每周工作时间不超过40小时；,原料数量：规格1模式1 35万张，,规格2模式42万张；,罐身和底、盖的配套组装 。,注意：不能装配的罐身、上下底也是余料,决策变量,x,i,按照第,i,种模式的生产张数(,i,=,1,2,3,4,)；,y,1,一周生产的易拉罐个数；,y,2,不配套的罐身个数；,y,3,不配套的底、盖个数。,模型建立,目标,约束条件,时间约束,原料约束,产量,余料,时间,x,1,222.6,1.5,x,2,183.3,2,x,3,261.8,1,x,4,169.5,3,模型建立,y,1,易拉罐个数；,y,2,不配套的罐身；,y,3,不配套的底、盖。,每只易拉罐利润0.10元，余料损失0.001元 / cm,2,罐身,面积,dh=,157.1,cm,2,底盖,面积,d,2,/4=19.6,cm,2,(40小时),约束条件,配套约束,y,1,易拉罐个数；,y,2,不配套的罐身；,y,3,不配套的底、盖。,罐身,底、盖,1,10,2,4,0,16,4,5,产量,x,1,x,2,x,3,x,4,虽然,x,i,和,y,1,，,y,2,，,y,3,应是整数，但是因生产量很大，可以把它们看成实数，从而用线性规划模型处理 。,将所有决策变量扩大10000倍xi 万张，yi 万件,LINDO发出警告信息：“数据之间的数量级差异太大，建议进行预处理，缩小数据之间的差异,模式,2,生产,40125,张，,模式,3,生产,3750,张，,模式,4,生产,20000,张，,共产易拉罐,160250,个,(罐身和底、盖无剩余)，,净利润为,4298,元,模型求解,OBJECTIVE FUNCTION VALUE,1) 0.4298337,VARIABLE VALUE REDUCED COST,Y1 16.025000 0.000000,X1 0.000000 0.000050,X2 4.012500 0.000000,X3 0.375000 0.000000,X4 2.000000 0.000000,Y2 0.000000 0.223331,Y3 0.000000 0.036484,下料问题的建模,确定下料模式,构造优化模型,规格不太多，可枚举下料模式，建立整数线性规划模型，否那么要构造整数非线性规划模型，求解困难，可用缩小可行域的方法进行化简，但要保证最优解的存在。,一维问题如钢管下料,二维问题如易拉罐下料,具体问题具体分析比较复杂 ,露天矿里铲位已分成矿石和岩石: 平均铁含量不低于25%的为矿石，否那么为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量称为品位都是的。每个铲位至多安置一台电铲，电铲平均装车时间5分钟,卡车在等待时所消耗的能量也是相当可观的，原那么上在安排时不应发生卡车等待的情况。,露天矿生产的车辆安排,(CUMCM-2003B),矿石卸点需要的铁含量要求都为29.5%1%(品位限制，搭配量在一个班次8小时内满足品位限制即可。卸点在一个班次内不变。卡车载重量为154吨，平均时速28km,平均卸车时间为3分钟。,问题：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次 ?,平面示意图,问题数据,距离,铲位1,铲位,2,铲位3,铲位4,铲位5,铲位6,铲位7,铲位,8,铲位9,铲位10,矿石漏,5.26,5.19,4.21,4.00,2.95,2.74,2.46,1.90,0.64,1.27,倒装,1.90,0.99,1.90,1.13,1.27,2.25,1.48,2.04,3.09,3.51,岩场,5.89,5.61,5.61,4.56,3.51,3.65,2.46,2.46,1.06,0.57,岩石漏,0.64,1.76,1.27,1.83,2.74,2.60,4.21,3.72,5.05,6.10,倒装,4.42,3.86,3.72,3.16,2.25,2.81,0.78,1.62,1.27,0.50,铲位1,铲位2,铲位3,铲位4,铲位5,铲位6,铲位7,铲位,8,铲位9,铲位10,矿石量,095,105,100,105,110,125,105,130,135,125,岩石量,125,110,135,105,115,135,105,115,135,125,铁含量,30%,28%,29%,32%,31%,33%,32%,31%,33%,31%,问题分析,与典型的运输问题明显有以下不同：,这是运输矿石与岩石两种物资的问题；,属于产量大于销量的不平衡运输问题；,为了完成品位约束，矿石要搭配运输；,产地、销地均有单位时间的流量限制；,运输车辆只有一种，每次满载运输，,154,吨,/,车次；,铲位数多于铲车数意味着要最优的选择不多于,7,个产地作为最后结果中的产地；,最后求出各条路线上的派出车辆数及安排。,近似处理：,先求出产位、卸点每条线路上的运输量,(MIP,模型,),然后求出各条路线上的派出车辆数及安排,模型假设,卡车在一个班次中不应发生等待或熄火后再启动的情况；,在铲位或卸点处由两条路线以上造成的冲突问题面前，我们认为只要平均时间能完成任务，就认为不冲突。我们不排时地进行讨论；,空载与重载的速度都是28km/h，耗油相差很大；,卡车可提前退出系统，等等。,如理解为严格不等待，难以用数学规划模型来解,个别参数队找到了可行解 略,符号,xij ：从i铲位到j号卸点的石料运量 车 单位： 吨；,cij ：从i号铲位到j号卸点的距离 公里；,Tij :从i号铲位到号j卸点路线上运行一个周期平均时间 分；,Aij ：从号铲位到号卸点最多能同时运行的卡车数 辆；,Bij ：从号铲位到号卸点路线上一辆车最多可运行的次数 次；,pi：i号铲位的矿石铁含量 p=(30,28,29,32,31,33,32,31,33,31) %,qj : j号卸点任务需求，q=(1.2,1.3,1.3,1.9,1.3)*10000 吨,cki ：i号铲位的铁矿石储量 万吨,cyi ：i号铲位的岩石储量 万吨,fi :描述第i号铲位是否使用的0-1变量，取1为使用；0为关闭。,(近似),优化模型,1道路能力(卡车数)约束,2电铲能力约束,3卸点能力约束,4铲位储量约束,5产量任务约束,6铁含量约束,7电铲数量约束,8整数约束,.,x,ij,为非负整数,f,i,为0-1整数,计算结果LINGO软件,铲位1,铲位2,铲位3,铲位4,铲位5,铲位6,铲位7,铲位8,铲位9,铲位10,矿漏,13,54,11,倒,42,43,岩场,70,15,岩漏,81,43,倒,13,2,70,铲位1,铲位2,铲位3,铲位4,铲位5,铲位6,铲位7,铲位8,铲位9,铲位,10,矿石漏,0.867,1.862,0.314,倒场,1.077,1.162,岩场,1.892,0.326,岩石漏,1.841,1.229,倒场,0.684,0.1,1.489,计算结果派车,铲位1,铲位2,铲位3,铲位4,铲位5,铲位6,铲位7,铲位8,铲位9,铲位,10,矿石漏,1 (29),倒场,1 (39),1 (37),岩场,1 (37),岩石漏,1(44),1 (35),倒场,1 (47),结论：,铲位1、2、3、4、8、9、10处各放置一台电铲。,一共使用了13辆卡车；总运量为85628.62吨公里；,岩石产量为32186吨；矿石产量为38192吨。,此外：6辆联合派车方案略,最大化产量,结论：,略,目标函数变化,此外：车辆数量20辆限制其实上面的模型也应该有,A,1,3,2,5,80,10,10,31,20,12,42,70,10,88,10,70,62,70,30,20,20,30,450,104,301,750,606,194,205,201,680,480,300,220,210,420,500,600,3060,195,202,720,690,520,170,690,462,160,320,160,110,290,1150,1100,1200,A,2,A,3,A,4,A,5,A,6,A,7,A,8,A,9,A,10,A,11,A,12,A,13,A,14,A,15,S,1,S,2,S,3,S,4,S,5,S,6,S,7,铁路运价表,里程,300,301350,351400,401450,451500,运价,20,23,26,29,32,钢管运输问题CUMCM-2000B),常用解法: 二次规划,先计算最小运费矩阵,两种运输方式铁路公路混合最短路问题,是普通最短路问题的变种，需要自己设计算法,钢管运输问题CUMCM-2000B),f,i,表示钢厂,i,是否使用；,x,ij,是从钢厂,i,运到节点,j,的钢管量,y,j,是从节点,j,向左铺设的钢管量；,z,j,是向右铺设的钢管量,钢管运输问题CUMCM-2000B),一个飞行管理模型,问题：在约10,000米高空的某边长160公里的正方形区域内, 经常有假设干架飞机作水平飞行。区域内每架飞机的位置和速度均由计算机记录其数据，以便进行飞行管理。当一架欲进入该区域的飞机到达区域边缘, 记录其数据后，要立即计算并判断是否会与区域内的飞机发生 碰撞。如果会碰撞，那么应计算如何调整各架(包括新进入的)飞机飞行方向角，以防止碰撞。,现假定条件如下:,1) 不碰撞的标准为任意两架飞机的距离大于8公里; 2) 飞机飞行方向角调整的幅度不应超过30度; 3) 所有飞机飞行速度均为每小时800公里; 4) 进入该区域的飞机在到达区域边缘时, 与区域内飞机的距离应在60公里以上; 5) 最多需考虑6架飞机; 6) 不必考虑飞机离开此区域后的状况。请你对这个防止碰撞的飞行管理问题建立数学模型，列出计算步骤，对以下数据进行计算(方向角误差不超过0.01度)，要求飞机飞行方向角调整的幅度尽量小。设该区域4个顶点的座标为(0,0)，(160,0)，(160,160)，(0,160)。,记录数据为:,飞机编号 横座标x 纵座标y 方向角(度) 1 150 140 243 2 85 85 236 3 150 155 220.5 4 145 50 159 5 130 150 230 新进入 0 0 52注: 方向角指飞行方向与x轴正向的夹角。试根据实际应用背景对你的模型进行评价与推广。,符号规定,：代表第i架飞机，新进入为第6架；,：第i架飞机的位置坐标，它们都是时间t的函数； 是它们的初始值；,：飞行速度，此题为常数800km/h；,：第i架飞机的飞行方向角， 是其初始值；,：第i架飞机的飞行方向角的调整值；,：第i架飞机与第j架飞机之间的距离，它是时间t的函数。,用matlab画出各架飞机再时间t0时的位置和飞行方向：,画图程序：,x=150,85,150,145,130,0;y=140,85,155,50,150,0;,scatter(x,y,30,r,filled);axis(-10,195,-10,170);,grid on;hol