mm05-规划模型.ppt

1、数学建模,规划模型,1,数 学 建 模,从自然走向理性之路,数学建模,2,规划模型,第五讲 规划模型,【主要内容】 介绍线性规划模型、非线性规划模型及动态规划模型 【主要目的】 了解规划问题的建模与求解，重点在模型的建立与结果的分析,数学建模,3,规划模型,线性规划模型(Linear Programming) 建立模型 线性规划问题：求多变量线性函数在线性约束条件下的 最优值 线性规划问题的一般形式：,数学建模,4,规划模型,线性规划问题的标准形式：,数学建模,5,规划模型,说明 任意线性规划问题可化为标准形式。具体方式如下： 1. 目标函数标准化 ： 2. 约束条件标准化 ： 假设约束条件中

2、有不等式约束 或 引入新变量 （称为松弛变量），则以上两式等价于以下两式：,数学建模,6,规划模型,3. 自由变量标准化 若变量 xj 无约束，可引入两个新变量 ，令 故以下我们只考虑标准形式。,数学建模,7,规划模型,矩阵形式表示 一般要求，,数学建模,8,规划模型,例1 某工厂制造A,B两种产品，制造产品A每吨需用煤9吨，用电4千瓦，3个工作日；制造产品B每吨需用煤5吨，用电5千瓦，10个工作日。已知制造产品A和B每吨分别获利7000元和12000元。现该厂只有煤360吨，电200千瓦，工作日300个可以利用，问A,B两种产品各应生产多少吨才能获利最大？ 解 x1, x2 分别表示A, B

3、两种产品的计划生产数（单位：吨），f 表示利润（单位：千元），则 f = 7 x1 + 12 x2,数学建模,9,规划模型,耗煤量为 9 x1 + 5 x2 耗电量为 4 x1 + 5 x2 耗工作日 3x1 + 10 x2 于是得到线性规划模型为：,数学建模,10,规划模型,例2 设某工厂有甲、乙、丙、丁四个车间，生产A、B、C、D、E、F六种产品，根据机车性能和以前的生产情况，得知生产每单位产品所需各车间的工作时数、每个车间在一个季度工作时数的上限以及产品的价格，如下表所示。问：每种产品每季度各应生产多少，才能使这个工厂每季度生产总值达到最大？,数学建模,11,规划模型,数学建模,12,规

4、划模型,解 以 x1 x6 分别表示每季度生产产品A、B、C、D、E、F的单位数，于是它们需满足 目标函数为,数学建模,13,规划模型,引入松弛变量x7 x10 ，化成标准型,数学建模,14,规划模型,线性规划问题求解 1. 可行域几何特征 满足约束条件的解称为可行解，所有可行解构成的集合称为可行域，满足目标式的可行解称为最优解。 线性规划问题的可行域是一个凸多边形； 线性规划问题如果存在最优解，则最优解必在可行域的顶点处达到。,数学建模,15,规划模型,2. 单纯形法 基本思想：从可行域的一个顶点（基本可行解）出发，转换到另一个顶点，并且使目标函数值逐步减小，有限步后可得到最优解。,数学建模

5、,16,规划模型,整数规划 自变量取整数的线性规划称为整数（线性）规划。 割平面法，分支定界法,数学建模,17,规划模型,01规划 例3 （MCM-88B）要把七 种不同规格的包装箱装到两辆铁 路平板车上去，各包装箱宽、高 均相同，但厚度（厘米）与重量 （公斤）不同。下表给出各包装箱的厚度、重量及数量。 每辆平板车有10.2米长的地方可用来装包装箱，载重40吨。由 于当地货运限制，对C5 , C6 , C7 类包装箱总数有一个特别限制：该 类箱子总厚度不超过302.7（厘米）。试把包装箱装到平板车上去使 得浪费空间最小。,数学建模,18,规划模型,1. 问题分析 题中所有的包装箱共重89吨，而

6、两辆平板车只能载80吨，因此不能都装下，问题是装哪些箱子，使剩余空间最小。,数学建模,19,规划模型,2. 模型建立 设 xij = 第i 辆车装 Cj 类箱子的个数， i =1,2 j =1, ,7 自然约束： 箱数约束： 重量约束： 厚度约束： 特别约束：,数学建模,20,规划模型,目标函数 例4 分工问题 某车间有四项工作需要完成，现已找到四个人做这些工作，经过试用，得到这四个人做每一项工作的相对生产率指数，列表如下 。 假定每个人只能分派一项工作，并希望分派后总的生产率最高，应如何分派工作？,数学建模,21,规划模型,令,数学建模,22,规划模型,每个人做一项工作 每项工作有一人做 目

7、标函数,数学建模,23,规划模型,非线性规划模型 (Nonlinear Programming) 例5 飞行管理问题（CUMCM95A) 在高空中一个边长为160公里的正方形区域内，经常有若干架飞机作水平飞行。区域内每架飞机的位置和速度均由计算机记录其数据。当一架欲进入该区域的飞机到达区域边缘时，要立即计算并判断其是否会与区域内的飞机碰撞。如果会碰撞，则要计算如何调整各架（包括新进入的）飞机飞行的方向角，以避免碰撞。现假定条件如下：,数学建模,24,规划模型,不碰撞的标准为任意两架飞机的距离大于8公里； 每架飞机飞行方向角调整的幅度不应超过30度； 所有飞机飞行速度均为800公里/小时； 欲进

8、入飞机在到达区域边缘时，与区域内飞机的距离应在60公里以上； 最多需考虑6架飞机； 不必考虑飞机离开此区域后的状况。 请你建立数学模型，对以下数据进行计算（方向角误差不超过0.01度），要求飞机飞行方向角调整的幅度尽量小。（数据略）,数学建模,25,规划模型,模型建立与求解 模型一：设第 i 架飞机在调整时的 方向角为i ,调整角度为 i （ i 1，2，6）。设任意两架飞机在区域内的最短距离为dij(i , j )，那么问题的非线性规划模型为,数学建模,26,规划模型,解法：能量梯度法、惩罚函数法、序列无约束最小 化方法、逐步逼近搜索法等 模型二： 模型三：,数学建模,27,规划模型,利用相

9、对运动的方法得到以上模型，再简化为线性规划问题求解。,数学建模,28,规划模型,动态规划模型(Dynamic Programming) 动态规划是解决多阶段决策过程最优化的一种方法。多阶段决策问题，是指一个问题可以分为若干个阶段， 每一阶段需要做出决策，而一个阶段的决策，常常会影响下一个阶段的决策。要在各个阶段决定一个最优决策， 使整个系统达到最佳的效果。 通过以下一个典型例子，说明如何建立动态规划模型。,数学建模,29,规划模型,例6 最短路线问题,数学建模,30,规划模型,先引入几个概念 状态每一阶段的起点位置 决策由一个状态变到另一个状态的选择 xk 第 k 阶段的状态，称为状态变量 u

10、k（ xk ）从 xk 出发所作出的决策，称为决策变量 Dk（ xk ）第 k 阶段中所有允许决策的集合 状态转移方程 xk+1 = Tk ( xk , uk ) dk ( xk , uk ）从状态 xk 出发，采取决策uk ，转移到状态 xk+1 的效益 fk（ xk ）从状态 xk 出发到终点的最优效益,数学建模,31,规划模型,最短路问题的动态规划最优化原理 : 假设一条最短路线经过状态 xk ，那么，这条路线上从 xk 到终点的一段，是从 xk 出发到终点的所有路线中最短的。 逆序法（回溯法）： 从后向前逐步求出各点到终点的最佳路线，最后得到由起点到终点的最短路线。,数学建模,32,规

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