数学建模.运筹学部分.ppt

《数学建模.运筹学部分.ppt》由会员分享，可在线阅读，更多相关《数学建模.运筹学部分.ppt（139页珍藏版）》请在三一文库上搜索。

1、全国大学生数学建模竞赛 China Undergraduate Mathematical Contest in Modeling (CUMCM) http:/ 国际大学生数学建模竞赛 The Mathematical Contest in Modeling (MCM) 往年数模试题 l1993年A题 非线性交调的频率设计 1993年B题 球队排名问题 l1994年A题 逢山开路 1994年B题 锁具装箱 l1995年A题 一个飞行管理模型 1995年B题 天车与冶炼炉的作业调度 l1996年A题 最优捕鱼策略 1996年B题 节水洗衣机 l1997年A题 零件的参数设计 1997年B题 截断切

2、割 l1998年A题 投资的收益和风险 1998年B题 灾情巡视路线 l1999年A题 自动化车床管理 1999年B题 钻井布局 l2000年A题 DNA序列分类 2000年B题 钢管定购和运输 l2001年A题 血管的三维重建 2001年B题 公交车调度 l2002年A题 车灯线光源的优化设计 2002年B题 彩票中的数学 l2003年A题 SARS的传播 2003年B题 露天矿生产的车辆安排 l2004年A题 奥运会临时超市网点设计 2004年B题 电力市场的输电阻塞 管理 l2005年A题 长江水质的评价和预测 2005年B题DVD在线租赁 l2006年A题 出版社的资源配置 2006年

3、B题艾滋病疗法评价及疗效预测 l2007年A题 人口预测 2007年B题 乘公交 看奥运 l2008年A题 高校学费标准 2008年B题 电子眼定位 l2009年A题 制动器试验台的控制方法分析 2009年B题眼科病床的合理安排 *3 单击此处编辑母版标题样式 单击此处编辑母版副标题样式 l运筹学中的优化模型 及辅助软件求解 数学建模步骤示意图 模型准备 模型假设 模型检验 模型应用 模型分析 模型求解 模型构成 优化问题与规划模型 l解决最优化问题的数学方法：运筹学 l运筹学主要分支： l线性规划、非线性规划、动态规划、 图与网络分析、存贮论、排队伦、 对策论、决策论。 l它们的特点就是：在

4、若干可能的方案中寻求某种 意义下的最优方案。数学上称为最优化问题,而研 究处理这种问题的方法叫最优化的方法。 实例：家具生产的安排 家具公司生产桌子和椅子，用于生产的劳力共 计450个工时，木材共有4立方米,每张桌子要使用15 个工时、0.2立方木材，售价80元。每张椅子使用10 个工时、0.05立方木材，售价45元。问为达到最大 的收益，应如何安排生产？ l分析： 1. 求什么？ 生产多少桌子？ x1 生产多少椅子？ x2 2. 优化什么？ 收益最大 Max f=80 x1+45 x2 3. 限制条件？ 原料总量 0.2 x1 +0.05 x2 4 劳力总数 15 x1 +10 x2 450

5、 模型：以产值为目标取得最大收益. 设：生产桌子 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）用EXC

6、ELSolver实现 模型中的数据直接输入EXCEL工作表中。其 中决策变量初始的值可以任意给出，它们是 可变的，软件最后将给出最优解的值。 SUMPRODUCT是EXCEL的一个内置函数，表示两 个向量或矩阵对应元素乘积的和。 引用工具规划求解（需要工具加载宏安装） 混合线性规划的EXCEL求解 求解模型步骤： l打开Microsoft Excel 的一个工作表； l把模型的目标函数系数矩阵置于A1至E4区域，约束常数 25000、30000和21000分别置于G6、G7和G8单元格； l选择A6至E9范围作可变单元，并输入初值1。其中A6至 E8区域对应变量xij(i=1,2,3; j=0

7、,1,2,3,4)，而B9至E9则分 别对应变量y1, y2, y3,和y4,A9则恒为1； l在F6、F7、F8和F9处分别输入“=SUM（A6：E6）”、 “=SUM（A7：E7）”、“=SUM（A8：E8）”、“=SUM（ B9：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”表 示约束等式的左边； l选择单元格A11, 输入“=A1*A6”,再把其引用至单元格 E14;即用鼠标按着单元格A11的右下角，

8、先拖至A14, 再 拖至E14; l以单元格F14作目标单元格，输入“=SUM(A11:E14)” 结果如图所示： l进入“规划求解”界面。“设置目标单元格” 处输入“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。再在“选项”中选择“采用线性模型 ”。 单击求解，即可得到此问题的解。 结

9、果： 目录 （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.6667 z = -8.6667 说明：x解为最优解，目标最大为8.6667。 （4）用LINDO/LINGO实现 我们可以直接在下面的窗口输入LP模型 输入后，用鼠标单击LIND

10、O软件工具栏中的图标 ，或从菜单 中选择SolveSolve(Ctrsl+S)命令，则LINDO开始编译这个 模型，编译没错误马上开始求解，求解时会显示如图（4） 2所示LINDO求解器运行状态窗口（里面的“Objective”就是 最优解，即：2200）。 图（4）2 “LP OPTIMUM FOUND AT STEP 2”表示单纯形法在两次迭代后 得到最优解。 “OBJECTIVE FUNCTION VALUE 1) 2200.000”表示最优目标值 为2200.000（在LINDO中目标函数所在的行总是被认为是第1 行，这就是这里“1）”的含义）。 返回 一般模型的建立 l某机器厂生产、

11、两种产品，需在A、B 、C三中不同的设备上加工。具体耗时如下 表： l问：如何生产使得利润最大？ ABC利润润 产产品2h402 产产品2053 能力时时限121615 建立模型 l模型假设： l设 和 分别表示、两种产品在计划期内的 产量，利润收入为 。 l模型建立： l目标函数： l约束条件： l 目标规划 线性规划问题的一般模型： s.t. 例 某部门有资金200万元，今后5年内考虑 给以下的项目投资。已知 l项目A：从第一年到第五年每年年初都可投 资，当年年末可收回本利110； l项目B：从第一年到第四年年初都可投资， 次年末可收回本利125，投资额 30万； l项目C：第三年初投资，

12、第五年末能收回本 利140，投资额 80万； l项目D：第二年初投资，第五年末能收回本 利155，投资额 100万； l问：如何投资使得第五年末资金额最大？ 1.模型假设 设 为第i年年初投入第j种方案的资金数。 2.模型分析 i年初1 2 3 4 5本利限量 A B C D 110% 125% 140% 155% 30 80 100 3.模型建立 l目标函数： l约束条件： l第一年年初： l第二年年初： l第三年年初： l第四年年初： l第五年年初： l各变量都要大于等于零，且在各方案投资 限量范围内。 l目标函数其实就是第五年的收益。 求解方法 l方法：图解法（只能求解两个变量的问题 ）

13、 l 单纯形法 l 大M法 l 两阶段法 l结合对偶单纯形法可以对线性规划问题进 行灵敏度分析及参数规划。 运输问题 l某糖果公司下面设有三个分工厂，每天的 糖果生产量分别为：A17t，A24t， A3 9t。该公司把这些糖果分别运往四个地区 的门市部销售，各地区每天的销售量为： B13t，B26t，B35t，B46t。已知 从每个加工厂到各销售门市部每吨糖果的 运价如下表所示，问该食品公司应如何调 运，在满足各门市部销售需要的情况下， 使总的运费支出为最少。 l 销销地 产产地 B1 B2 B3 B4产产量 A1 A2 A3 3 11 3 10 1 9 2 8 7 4 10 5 7 4 9

14、销销量 3 6 5 6 l模型假设： l设 代表从第i个产地调运给第j个销地的物 资的单位数量。 l模型建立： l目标函数 l约束条件 s.t. 一般模型 l方法：表上作业法（找初始解：最小元素 法、Vogel法;调整：闭回路法、位势法） s.t. 整数规划 l特点：在线性规划问题中加一个约束 变量取整数解。 l求解的方法有：匈牙利法、分枝定界法、 割平面法 动态规划模型的分类 以“时间”角度可分成： 离散型和连续型。 从信息确定与否可分成： 确定型和随机型。 从目标函数的个数可分成： 单目标型和多目标型。 动态规划 动态规划的基本原理 多阶段决策过程最优化 多阶段决策过程是指这样一类特殊 的

15、活动过程，他们可以按时间顺序 分解成若干相互联系的阶段，在每 个阶段都要做出决策，全部过程的 决策是一个决策序列，所以多阶段 决策问题也称为序贯决策问题。 例（一定阶段最短路问题） W先生每天驾车去公司上班。如 图，W先生的住所位于A，公司位 于F，图中的直线段代表公路，交 叉点代表路口，直线段上的数字 代表两路口之间的平均行驶时间 。现在W先生的问题是要确定一条 最省时的上班路线。 A 3 B1 4 C1 3 D1A 3 B1 4 C1 3 D1 4 5 3 24 5 3 2 B2 2 C2 3 D2 E1B2 2 C2 3 D2 E1 1 2 3 41 2 3 4 C3 4 D3 5 E2

16、 2 FC3 4 D3 5 E2 2 F A A B1B1 B2B2 C1C1 C2C2 C3C3 D1D1 D2D2 D3D3 E1E1 E2E2 F F 4 4 1 1 5 5 4 4 4 4 4 4 4 4 5 5 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 A A B B C C D D E E F F 1 1 阶段（Stage） 将所给问题的过程，按时间或 空间特征分解成若干个相互联系的 阶段，以便按次序去求每阶段的解 ，常用k表示阶段变量。 我们把从A到F看成一个五阶段问题 。 2 2 状态（状态（StateState） 各阶段开始时的客观条件各阶段开始

17、时的客观条件 叫做状态。描述各阶段状态的叫做状态。描述各阶段状态的 变量称为状态变量，常用变量称为状态变量，常用s s k k 表表 示第示第k k阶段的状态变量，状态阶段的状态变量，状态 变量的取值集合称为状态集合变量的取值集合称为状态集合 ，用，用S S k k 表示。表示。 动态规划中的状态具有如下性质：动态规划中的状态具有如下性质： 当某阶段状态给定以后，在这当某阶段状态给定以后，在这 阶段以后的过程的发展不受这段以阶段以后的过程的发展不受这段以 前各段状态的影响。即：过程的过前各段状态的影响。即：过程的过 去历史只能通过当前状态去影响它去历史只能通过当前状态去影响它 未来的发展，这称

18、为无后效性。如未来的发展，这称为无后效性。如 果所选定的变量不具备无后效性，果所选定的变量不具备无后效性， 就不能作为状态变量来构造动态规就不能作为状态变量来构造动态规 划模型。划模型。 3 3 决策和策略决策和策略 （Decision and PolicyDecision and Policy） 当各段的状态确定以后，就可当各段的状态确定以后，就可 以做出不同的决定（或选择），从以做出不同的决定（或选择），从 而确定下一阶段的状态，这种决定而确定下一阶段的状态，这种决定 称为决策。决策变量用称为决策。决策变量用d d k k (S(S k k ) )表示表示 ，允许决策集合用，允许决策集合用

19、D D k k (S(S k k ) )表示。表示。 各个阶段决策确定后，整个问各个阶段决策确定后，整个问 题的决策序列就构成一个策略，用题的决策序列就构成一个策略，用 p p 1,n1,n(d (d 1 1 ,d,d 2 2 ,d,d n n ) )表示。对每个实际表示。对每个实际 问题，可供选择的策略有一定的范问题，可供选择的策略有一定的范 围，称为允许策略集合，用围，称为允许策略集合，用P P表示表示 。使整个问题达到最优效果的策略。使整个问题达到最优效果的策略 就是最优策略。就是最优策略。 4 4 状态转移方程状态转移方程 动态规划中本阶段的状态往动态规划中本阶段的状态往 往是上一阶段

20、的决策结果。如果往是上一阶段的决策结果。如果 给定了第给定了第k k段的状态段的状态 S Sk k ，本阶段，本阶段 决策为决策为 d dk k (S(S k k) ) ，则第，则第k+1k+1段的状态段的状态 S S k+1k+1由公式： 由公式： S S k+1k+1=T =T k k （ S S k k， d dk k ） 确定，称为状态转移方程。确定，称为状态转移方程。 5 5 指标函数指标函数 用于衡量所选定策略优用于衡量所选定策略优 劣的数量指标称为指标函数劣的数量指标称为指标函数 。最优指标函数记为。最优指标函数记为 f fk k (S(S k k ) )。 动态规划的基本思想：

21、动态规划的基本思想： 从过程的最后一段开始，从过程的最后一段开始， 用逆序递推方法求解，逐步求用逆序递推方法求解，逐步求 出各段各点到终点出各段各点到终点E E最短路线，最短路线， 最后求出最后求出A A点到点到E E点的最短路线点的最短路线 。 动态规划的函数方程（动态规划的函数方程（DPDP） 建立建立DPDP函数方程是指确定过函数方程是指确定过 程的阶段及阶段数，规定状态变程的阶段及阶段数，规定状态变 量和决策变量的取法，给出各阶量和决策变量的取法，给出各阶 段的状态集合，允许决策集合，段的状态集合，允许决策集合， 状态转移方程和指标函数等。状态转移方程和指标函数等。 在上面的计算过程中

22、，利用了第在上面的计算过程中，利用了第 k k阶段与第阶段与第k+1k+1阶段的关系：阶段的关系： f f k k (S(S k k )= Min r(S)= Min r(S k k ,d,d k k (S(S k k )+f)+fk+1 k+1(S (Sk+1 k+1 ) ) d dk k (S(S k k ) ) k=1,2,3,4,5k=1,2,3,4,5 f f 6 6 (S(S 6 6 )=0)=0 这种递推关系，称为这种递推关系，称为动态规划的动态规划的 函数基本方程。函数基本方程。 贝尔曼贝尔曼( (BallmanBallman) )最优化原理最优化原理 作为整个过程的最优策略具

23、有作为整个过程的最优策略具有 这样的性质，即无论过去的状态和这样的性质，即无论过去的状态和 决策如何，对前面的决策所形成的决策如何，对前面的决策所形成的 状态而言，余下的诸决策必须构成状态而言，余下的诸决策必须构成 最优策略。这就是说，不管引导到最优策略。这就是说，不管引导到 这个现时状态的头一个状态和决策这个现时状态的头一个状态和决策 是什么，所有的未来决策应是最优是什么，所有的未来决策应是最优 的。的。 动态规划的优点：动态规划的优点： 可把一个可把一个N N维优化问题化成维优化问题化成N N个一维个一维 优化问题求解。优化问题求解。 DPDP方程中附加某些约束条件，可使方程中附加某些约束

24、条件，可使 求解更加容易。求解更加容易。 求得最优解以后，可得所有子问题求得最优解以后，可得所有子问题 的最优解。的最优解。 动态规划的缺点：动态规划的缺点： “一个一个”问题，问题，“一个一个”模型，模型， “一个一个”求解方法。且求解技巧求解方法。且求解技巧 要求比较高，没有统一处理方法要求比较高，没有统一处理方法 。 状态变量维数不能太高，一般要状态变量维数不能太高，一般要 求小于求小于6 6。 层次分析法 l在管理中，人们常常需要对一些情况作出 决策：例如企业的决策者要决定购置哪种 设备，上马什么产品；经理要从若干求职 者中决定录用哪些人员；地区、部门官员 要对人口、交通、经济、环境等

25、领域的发 展规划作出决策。 l在日常生活中也常会遇到，在多种类不同 特征的商品中选购。报考学校选择志愿。 毕业时选择工作岗位等。 lAHP法的特征：定性与定量相结合，把人 们的思维过程层次化，数量化。 l运用AHP法进行决策时，可以分4个步骤： （1）分析系统中各个因素的关系，建立系 统的递阶层次结构； （2）对同一层次的各元素关于上一层次中 某一准则的重要性进行两两比较，构造两 两比较判断矩阵； （3）由判断矩阵计算被比较元素对于该准 则的相对权重； （4） 计算各层元素对系统目标的合成权重 ，并进行排序。 建立层次分析的结构模型 用AHP分析问题，首先要把问题条理化、层次化， 构造层次分析

26、的结构模型。这些层次大体可分3类： 1、最高层：在这一层次中只有一个元素，一般是分 析问题的预定目标或理想结果，因此又称目标层 ； 2、中间层：这一层次包括了为实现目标所涉及的中 间环节，它可由若干个层次组成，包括所需要考 虑的准则，子准则，因此又称为准则层； 3、最底层：表示为实现目标可供选择的各种措施、 决策、方案等，因此又称为措施层或方案层。 决策目标 准则1 方案1 准则m1准则2 子准则1 方案2 子准则2 方案mr 子准则m2 层次分析结构图 目标层： 准则层： 方案层： 例1、某顾客选购电冰箱时，对市场上正在出 售的四种电冰箱考虑6项准则作为评价依据， 得到如下层次分析模型： 例

27、2 l设某港务局要改善一条河道的过河运输条 件，为此需要确定是否要建立桥梁或隧道 以代替现有轮渡。 l此问题中过河方式的确定取决于过河方式 的效益与代价（即成本）。通常我们用费 效比（效益/代价）作为选择方案的标准。 为此构造以下两个层次分析的结构模型。 准则层 过河的效益A 经济效益B1社会效益B2环境效益B3 桥梁D1隧道D2渡船D3 收入 c2 岸间商业 c3 节省时间 c1 当地商业 c4 建筑就业 c5 安全可靠 c6 交往沟通 c7 自豪感 c8 舒 适 c9 进出方便 c10 美 化 c11 层次分析 方案层 目标层 过河的代价A 经济代价B1社会代价B2环境代价B3 桥梁D1

28、投入资金 c1 操作维护 c2 冲击渡船业 c3 冲击生活方式 c4 交通拥挤 c5 居民搬迁 c6 汽车排废物 c7 对水的污染 c8 对生态的破坏 c9 隧道D2渡船D3 层次分析 目标层 准则层 方案层 多目标规划 l同时考虑多个决策目标时，称为多目标规 划问题。 目标规划 l问题仍为例1，但企业的经营目标不仅仅是利润， 而是考虑多个方面，如： l（1）力求使利润指标不低于15元； l（2）考虑到市场需求，、两种产品的生产量需 保持的比例； l（3）A为贵重设备，严格禁止超时使用； l（4）设备C可以适当加班，但要控制； l（5）设备B既要充分利用，又尽可能不加班； l（6）重要性上设备

29、B是C的3倍。 具体做法： l 设置偏差变量。用来表明实际值同目标 值之间的差异，偏差变量用下列符号表示 ： l ：超出目标的差值，称正偏差变量 l ：未达到目标的差值，称负偏差变量 l 与 有下面几种取值情况： 统一处理目标和约束。只对资源使用上 有严格限制的建立系统约束，数学形式上 为严格的等式或不等式，同线性规划中的 约束条件。 l因正负偏差不可能同时出现，故总有 l若要求：的2倍产量不低于的产量，即不 希望上式中 ，用目标约束可表示为： l若要求：的2倍产量低于的产量，即不希 望上式中 ，用目标约束可表示为： l若要求：的2倍产量恰好等于的产量，即 不希望上式中 ，又不希望出现 用 目

30、标约束可表示为： 目标的优先级与权系数。 l权系数：在一个目标规划的模型中，如果 两个不同目标重要程度相差悬殊，为达到 某一目标可牺牲其他一些目标，称这些目 标是属于不同层次的优先级。 l权系数：对属于同一层次优先级的不同目 标，按其重要程度可分别乘上不同的系数 ，这个系数称为权系数。 建立模型 l目标函数： l约束条件： 一般模型 s.t. 求解方法 l图解法 l单纯形法 l层次算法 数学规划模型的一般形式： 非线性规划模型 无约束一维搜索方法 t为实数 一维搜索问题指目标函数为单变量的非线性规划问题。 又称线性搜索问题。其模型为： 什么叫一维搜索问题？ 或 一般一维搜索问题有效一维搜索问题

31、 一维搜索问题的算法分类： 精确一维搜索（最优一维搜索） 非精确一维搜索（可接受一维搜索） 具体方法： 两种精确一维搜索方法：0.618法（近似黄金分割 法），Newton法。 两种非精确一维搜索方法：Goldstein法,Armijo法 。 无约束最优化方法 n元函数的无约束非线性规划问题： 求解此类模型(UMP)的方法称为无约束最优化方法。 无约束最优化方法通常有两类： 解析法：要使用导数的方法； 直接法：无须考虑函数是否可导，直接使用函数值。 方法：最速下降法或梯度法（一种解析法） 约束最优化方法 本节课讨论约束非线性规划问题MP 其中,x=(x1 ,x2, xn)T，f(x),gi(x

32、),hj(x)为x的实值函数 求解此类模型(MP)的方法称为约束最优化方法。 具体方法 惩罚函数法：罚函数法（外部惩罚法），障碍函数法（内 部惩罚法） 建模时需要注意的几个基本问题 l1、尽量使用实数优化，减少整数约束和整数 变量 l2、尽量使用光滑优化，减少非光滑约束的个 数 如：尽量少使用绝对值、符号函数、多个 变量求最大/最小值、四舍五入、取整函数等 l3、尽量使用线性模型，减少非线性约束和非 线性变量的个数 （如x/y =64); lmin=sum(feiji:abs(dzt); lend 优化赛题 钻井布局问题（1999年B题） 抢渡长江问题（ 2003年D题） 电力市场输电阻塞管理的优化（2004年B题） DVD在线租赁的优化管理（2005年B题） 出版社的资源配置（2006年A题） 乘公交，看奥运（2007年B题） 等等 l谢谢！