优化方法在数学建模中的应用精选.ppt

* 最后， 希望我的这点点经验之谈能够帮助到往后的一些参赛队员，也祝愿准备参加美赛的同学都能取得好的成绩,以及在往后的学习道路上都能拿出参加美赛的精神不断努力，有所收获！ * * * * * * * * * * * * * * 一. 典型的运输问题 某种物资由m个产地运往n个销地，在满足各产地的供应和各销地的需求的条件下，使总运量（吨公里）最小，制订运输计划。 记号：cij ~ 产地i到销地j的距离（公里），i=1,2,?,m, j=1,2,?,n xij ~ 产地i到销地j的运量（吨），i=1,2,?, m, j=1,2,? , n ai ~ 产地i的供应量（吨），i=1,2,?, m, bj ~ 销地j的需求量（吨），j=1,2,?, n 模型： * 二. 问题分析 典型的运输问题的约束条件外，还有以下约束条件： （1）车辆满载运输（154吨/车次）； （2）运输矿石与岩石两种物资，矿石有品位约束，各铲位的矿石需搭配运输； （3）各个铲位、卸点还有一个班次内运输车次的限制； （4）每条路线上有一个班次内运输车次的限制； （5）铲位数10大于电铲数7，要从10个中选择不大于7个铲位； （6）用最少的车辆（不超过20）给出各条路线上的车辆安排（几辆车，跑几次）。 * 仍用以上符号，其中m =10，n=5, j=1,2, 5为矿石卸点，j=3,4为岩石卸点。 xij的单位是车次，只取整数，于是问题化为50个变量的整数线性规划。 记铲位i的矿石铁含量为pi，矿石的品位约束表示为 * 3. 各个铲位至多一台电铲，5分钟装一车，所以一个铲位一个班次（8小时）内的最大运输车次为8?60/5=96，即 类似地，3分钟卸一车，一个卸点一个班次中的最大运输车次为8?60/3=160，即 * 4. 记平均车速v=28(公里/时)=0.47(公里/分)，从铲位i到卸点j车辆运行一个周期的平均时间为tij=2cij/v +5+3（分），这条路线上在卡车不等待条件下最多能运行的卡车数为rij=[tij/5], 每辆卡车一个班次中在这条路线上最多可以运行的次数sij=[8?60/tij]（这里假定若有两辆车在同一路线上，则上班晚装车的那辆也晚下班）。于是各铲位、卸点一个班次内运输车次的限制为 * 5. 处理的办法如： 1）用枚举法从 个整数规划中取最优的一个； 2）先不考虑电铲数量7的约束，运行整数线性规划，再逐步去掉解中运量最少的几个铲位，直到不超过7个铲位； 3）增加10个0-1变量来标志电铲放在哪个铲位，问题为50个整数变量和10个0-1变量的线性规划。 6. 不超过20辆车的约束可写作 （5）铲位数10大于电铲数7，要从10个中选择不大于7个铲位； * * * * * * B题： DVD在线租赁 05 随着信息时代的到来，网络成为人们生活中越来越不可或缺的元素之一。许多网站利用其强大的资源和知名度，面向其会员群提供日益专业化和便捷化的服务。例如，音像制品的在线租赁就是一种可行的服务。这项服务充分发挥了网络的诸多优势，包括传播范围广泛、直达核心消费群、强烈的互动性、感官性强、成本相对低廉等，为顾客提供更为周到的服务。 * 考虑如下的在线DVD租赁问题。顾客缴纳一定数量的月费成为会员，订购DVD租赁服务。会员对哪些DVD有兴趣，只要在线提交订单，网站就会通过快递的方式尽可能满足要求。会员提交的订单包括多张DVD，这些DVD是基于其偏爱程度排序的。网站会根据手头现有的DVD数量和会员的订单进行分发。每个会员每个月租赁次数不得超过2次，每次获得3张DVD。会员看完3张DVD之后，只需要将DVD放进网站提供的信封里寄回（邮费由网站承担），就可以继续下次租赁。请考虑以下问题： * 1）网站正准备购买一些新的DVD，通过问卷调查1000个会员，得到了愿意观看这些DVD的人数（表1给出了其中5种DVD的数据）。此外，历史数据显示，60%的会员每月租赁DVD两次，而另外的40%只租一次。假设网站现有10万个会员，对表1中的每种DVD来说，应该至少准备多少张，才能保证希望看到该DVD的会员中至少50%在一个月内能够看到该DVD？如果要求保证在三个月内至少95%的会员能够看到该DVD呢？ 2）表2中列出了网站手上100种DVD的现有张数和当前需要处理的1000位会员的在线订单（表2的数据格式示例如下表2，具体数据请从/mcm05/problems2005c.asp下载），如何对这些DVD进行分配，才能使会员获得最大的满意度？请具体列出前30位会员（即C0001~C0030）分别获得哪些D