数学建模专题培训市公开课金奖市赛课一等奖课件.pptx

数数 学学 建建 模模 从自然走向理性之路 数学建模1规划模型第1页第1页第五讲第五讲 规划模型规划模型【主要内容】【主要内容】简介线性规划模型、非线性规划模简介线性规划模型、非线性规划模型及动态规划模型型及动态规划模型 【主要目的】【主要目的】理解规划问题建模与求解，重点在理解规划问题建模与求解，重点在模型建立与结果分析模型建立与结果分析数学建模2规划模型第2页第2页 线性规划模型线性规划模型(Linear Programming)建立模型建立模型 线性规划问题：求多变量线性规划问题：求多变量线性规划问题：求多变量线性规划问题：求多变量线性函数线性函数线性函数线性函数在在在在线性约束线性约束线性约束线性约束条件下最条件下最条件下最条件下最优值优值优值优值 线性规划问题普通形式：线性规划问题普通形式：线性规划问题普通形式：线性规划问题普通形式：数学建模3规划模型第3页第3页 线性规划问题原则形式：线性规划问题原则形式：线性规划问题原则形式：线性规划问题原则形式：数学建模4规划模型第4页第4页 阐明阐明阐明阐明 任意线性规划问题可化为原则形式。详细方式下列：任意线性规划问题可化为原则形式。详细方式下列：任意线性规划问题可化为原则形式。详细方式下列：任意线性规划问题可化为原则形式。详细方式下列：1.1.1.1.目的函数原则化目的函数原则化目的函数原则化目的函数原则化 ：2.2.2.2.约束条件原则化约束条件原则化约束条件原则化约束条件原则化：假设约束条件中有不等式约束假设约束条件中有不等式约束假设约束条件中有不等式约束假设约束条件中有不等式约束 或或或或 引入新变量引入新变量引入新变量引入新变量 （称为松弛变量），则以上两式等（称为松弛变量），则以上两式等（称为松弛变量），则以上两式等（称为松弛变量），则以上两式等价于下列两式：价于下列两式：价于下列两式：价于下列两式：数学建模5规划模型第5页第5页 3.3.3.3.自由变量原则化自由变量原则化自由变量原则化自由变量原则化 若变量若变量若变量若变量 x xj j 无约束，可引入两个新变量无约束，可引入两个新变量无约束，可引入两个新变量无约束，可引入两个新变量 ，令，令，令，令 故下列我们只考虑原则形式。故下列我们只考虑原则形式。故下列我们只考虑原则形式。故下列我们只考虑原则形式。数学建模6规划模型第6页第6页矩阵形式表示矩阵形式表示矩阵形式表示矩阵形式表示普通要求，普通要求，普通要求，普通要求，数学建模7规划模型第7页第7页 例例例例1 1 1 1 某工厂制造某工厂制造某工厂制造某工厂制造A,BA,BA,BA,B两种产品，制造产品两种产品，制造产品两种产品，制造产品两种产品，制造产品A A A A每吨需用每吨需用每吨需用每吨需用煤煤煤煤9 9 9 9吨，用电吨，用电吨，用电吨，用电4 4 4 4千瓦，千瓦，千瓦，千瓦，3 3 3 3个工作日；制造产品个工作日；制造产品个工作日；制造产品个工作日；制造产品B B B B每吨需用煤每吨需用煤每吨需用煤每吨需用煤5 5 5 5吨，用电吨，用电吨，用电吨，用电5 5 5 5千瓦，千瓦，千瓦，千瓦，10101010个工作日。已知制造产品个工作日。已知制造产品个工作日。已知制造产品个工作日。已知制造产品A A A A和和和和B B B B每吨每吨每吨每吨分别赢利分别赢利分别赢利分别赢利7000700070007000元和元和元和元和1 1 1 1元。现该厂只有煤元。现该厂只有煤元。现该厂只有煤元。现该厂只有煤360360360360吨，电吨，电吨，电吨，电200200200200千瓦，千瓦，千瓦，千瓦，工作日工作日工作日工作日300300300300个能够利用，问个能够利用，问个能够利用，问个能够利用，问A,BA,BA,BA,B两种产品各应生产多少吨两种产品各应生产多少吨两种产品各应生产多少吨两种产品各应生产多少吨才干赢利最大？才干赢利最大？才干赢利最大？才干赢利最大？解解解解 x x1 1,x x2 2 分别表示分别表示分别表示分别表示A,BA,BA,BA,B两种产品计划生产数（单位：吨）两种产品计划生产数（单位：吨）两种产品计划生产数（单位：吨）两种产品计划生产数（单位：吨），f f 表示利润（单位：千元），则表示利润（单位：千元），则表示利润（单位：千元），则表示利润（单位：千元），则 f f =7=7 x x1 1 +12+12 x x2 2 数学建模8规划模型第8页第8页 耗煤量为耗煤量为耗煤量为耗煤量为 9 9 x x1 1 +5+5 x x2 2 耗电量为耗电量为耗电量为耗电量为 4 4 x x1 1+5+5 x x2 2 耗工作日耗工作日耗工作日耗工作日 3 3 3 3x x1 1+10+10 x x2 2 于是得到线性规划模型为：于是得到线性规划模型为：于是得到线性规划模型为：于是得到线性规划模型为：数学建模9规划模型第9页第9页 例例2 2 设某工厂有甲、乙、丙、丁四个车间，生设某工厂有甲、乙、丙、丁四个车间，生产产A A、B B、C C、D D、E E、F F六种产品，依据机车性能六种产品，依据机车性能和以前生产情况，得知生产每单位产品所需各车和以前生产情况，得知生产每单位产品所需各车间工作时数、每个车间在一个季度工作时数上限间工作时数、每个车间在一个季度工作时数上限以及产品价格，下列表所表示。问：每种产品每以及产品价格，下列表所表示。问：每种产品每季度各应生产多少，才干使这个工厂每季度生产季度各应生产多少，才干使这个工厂每季度生产总值达到最大？总值达到最大？数学建模10规划模型第10页第10页 产品产品产品产品车间车间车间车间A A A AB B B BC C C CD DD DE E E EF F F F 每个车间每季度每个车间每季度每个车间每季度每个车间每季度 工作时数上限工作时数上限工作时数上限工作时数上限 甲甲甲甲乙乙乙乙丙丙丙丙丁丁丁丁0.010.010.010.010.02 0.02 0.02 0.02 0.010.010.010.010.02 0.02 0.02 0.02 0.010.010.010.010.03 0.03 0.03 0.03 0.030.0.030.0.030.0.030.050505050.030.030.030.030.05 0.05 0.05 0.05 0.030.030.030.030.08 0.08 0.08 0.08 850850850850700700700700100100100100900 900 900 900 单价（元）单价（元）单价（元）单价（元）0.40 0.40 0.40 0.40 0.280.280.280.280.32 0.32 0.32 0.32 0.72 0.72 0.72 0.72 0.64 0.64 0.64 0.64 0.600.600.600.60数学建模11规划模型第11页第11页 解解解解 以以以以 x x1 1 x x6 6 分别表示每季度生产产品分别表示每季度生产产品分别表示每季度生产产品分别表示每季度生产产品A A A A、B B B B、C C C C、D DD D、E E E E、F F F F单位数，于是它们需满足单位数，于是它们需满足单位数，于是它们需满足单位数，于是它们需满足目的函数为目的函数为目的函数为目的函数为数学建模12规划模型第12页第12页引入松弛变量引入松弛变量x7 x10，化成原则型，化成原则型 数学建模13规划模型第13页第13页 线性规划问题求解线性规划问题求解 1.1.可行域几何特性可行域几何特性 满足约束条件解称为满足约束条件解称为可行解可行解，所有可行解构成集，所有可行解构成集合称为合称为可行域可行域，满足目的式可行解称为，满足目的式可行解称为最优解最优解。n n线性规划问题可行域是一个凸多边形；线性规划问题可行域是一个凸多边形；n n线性规划问题假如存在最优解，则最优解必在可线性规划问题假如存在最优解，则最优解必在可行域顶点处达到。行域顶点处达到。数学建模14规划模型第14页第14页 2.2.单纯形法单纯形法 基本思想：从可行域一个顶点（基本可行解）出基本思想：从可行域一个顶点（基本可行解）出发，转换到另一个顶点，并且使目的函数值逐步发，转换到另一个顶点，并且使目的函数值逐步减小，有限步后可得到最优解。减小，有限步后可得到最优解。数学建模15规划模型第15页第15页 整数规划整数规划 自变量取整数线性规划称为整数（线性）自变量取整数线性规划称为整数（线性）规划。规划。割平面法，分支定界法割平面法，分支定界法 数学建模16规划模型第16页第16页n n 01规划 n n 例3（MCM-88B）要把七n n种不同规格包装箱装到两辆铁n n路平板车上去，各包装箱宽、高n n均相同，但厚度（厘米）与重量n n（千克）不同。下表给出各包装箱厚度、重量及数量。n n每辆平板车有10.2米长地方可用来装包装箱，载重40吨。由n n于当地货运限制，对C5,C6 ,C7 类包装箱总数有一个尤其限制：该n n类箱子总厚度不超出302.7（厘米）。试把包装箱装到平板车上去n n使得浪费空间最小。数学建模17规划模型第17页第17页C C1 1C C2 2C C3 3C C4 4C C5 5C C6 6C C7 7厚度厚度t t 48.7 48.7 52.0 52.0 61.3 61.3 72.0 72.0 48.7 48.7 52.0 52.0 64.0 64.0 重量重量w w n n 3000 3000 1000 1000 500 500 4000 4000 n n 1000 1000 件数件数n n8 87 79 96 66 64 48 8 1.问题分析问题分析 题中所有包装箱共重题中所有包装箱共重89吨，而两辆平板车只能载吨，而两辆平板车只能载80吨，因此不能都装下，问题是装哪些箱子，使剩余空间吨，因此不能都装下，问题是装哪些箱子，使剩余空间最小。最小。数学建模18规划模型第18页第18页 2.2.2.2.模型建立模型建立模型建立模型建立 设设设设 x xij ij =第第第第i i 辆车装辆车装辆车装辆车装 C Cj j 类箱子个数，类箱子个数，类箱子个数，类箱子个数，i i=1,2 =1,2 j j=1,=1,7,7自然约束：自然约束：自然约束：自然约束：箱数约束：箱数约束：箱数约束：箱数约束：重量约束：重量约束：重量约束：重量约束：厚度约束：厚度约束：厚度约束：厚度约束：尤其约束：尤其约束：尤其约束：尤其约束：数学建模19规划模型第19页第19页 目的函数目的函数目的函数目的函数 例例例例4 4 4 4 分工问题分工问题分工问题分工问题 某车间有四项工作需要完毕，现已找到四个人做这某车间有四项工作需要完毕，现已找到四个人做这某车间有四项工作需要完毕，现已找到四个人做这某车间有四项工作需要完毕，现已找到四个人做这些工作，通过试用，得到这四个人做每一项工作相对生些工作，通过试用，得到这四个人做每一项工作相对生些工作，通过试用，得到这四个人做每一项工作相对生些工作，通过试用，得到这四个人做每一项工作相对生产率指数，列表下列产率指数，列表下列产率指数，列表下列产率指数，列表下列 。假定每个人只能分派一项工作，并希望分派后总生假定每个人只能分派一项工作，并希望分派后总生假定每个人只能分派一项工作，并希望分派后总生假定每个人只能分派一项工作，并希望分派后总生产率最高，应如何分派工作？产率最高，应如何分派工作？产率最高，应如何分派工作？产率最高，应如何分派工作？数学建模20规划模型第20页第20页 令令令令 工作工作人员人员1 12 23 34 41 12 23 34 45 53 34 41 17 76 63 34 410108 86 62 23 34 42 21010数学建模21规划模型第21页第21页每个人做一项工作每个人做一项工作每个人做一项工作每个人做一项工作 每项工作有一人做每项工作有一人做每项工作有一人做每项工作有一人做目的函数目的函数目的函数目的函数 数学建模22规划模型第22页第22页 非线性规划模型非线性规划模型 (Nonlinear Programming)例例例例5 5 5 5 飞行管理问题（飞行管理问题（飞行管理问题（飞行管理问题（CUMCM95A)CUMCM95A)CUMCM95A)CUMCM95A)在高空中一个边长为在高空中一个边长为在高空中一个边长为在高空中一个边长为160160160160公里正方形区域内，经常有若公里正方形区域内，经常有若公里正方形区域内，经常有若公里正方形区域内，经常有若干架飞机作水平飞行。区域内每架飞机位置和速度均由干架飞机作水平飞行。区域内每架飞机位置和速度均由干架飞机作水平飞行。区域内每架飞机位置和速度均由干架飞机作水平飞行。区域内每架飞机位置和速度均由计算机统计其数据。当一架欲进入该区域飞机到达区域计算机统计其数据。当一架欲进入该区域飞机到达区域计算机统计其数据。当一架欲进入该区域飞机到达区域计算机统计其数据。当一架欲进入该区域飞机到达区域边沿时，要马上计算并判断其是否会与区域内飞机碰撞。边沿时，要马上计算并判断其是否会与区域内飞机碰撞。边沿时，要马上计算并判断其是否会与区域内飞机碰撞。边沿时，要马上计算并判断其是否会与区域内飞机碰撞。假如会碰撞，则要计算如何调整各架（包括新进入）飞假如会碰撞，则要计算如何调整各架（包括新进入）飞假如会碰撞，则要计算如何调整各架（包括新进入）飞假如会碰撞，则要计算如何调整各架（包括新进入）飞机飞行方向角，以避免碰撞。现假定条件下列：机飞行方向角，以避免碰撞。现假定条件下列：机飞行方向角，以避免碰撞。现假定条件下列：机飞行方向角，以避免碰撞。现假定条件下列：数学建模23规划模型第23页第23页n n不碰撞标准为任意两架飞机距离大于8公里；n n每架飞机飞行方向角调整幅度不应超出30度；n n全部飞机飞行速度均为800公里/小时；n n欲进入飞机在抵达区域边沿时，与区域内飞机距离应在60公里以上；n n最多需考虑6架飞机；n n无须考虑飞机离开此区域后情况。n n 请你建立数学模型，对以下数据进行计算（方向角误差不超出0.01度），要求飞机飞行方向角调整幅度尽也许小。（数据略）数学建模24规划模型第24页第24页 模型建立与求解模型建立与求解 模型一：设第模型一：设第模型一：设第模型一：设第 i i 架飞机在调整时架飞机在调整时架飞机在调整时架飞机在调整时 方向角为方向角为方向角为方向角为 i i,调整角度调整角度调整角度调整角度为为为为 i i （i i 1 1，2 2，6 6）。设任意两架飞机在区域内。设任意两架飞机在区域内。设任意两架飞机在区域内。设任意两架飞机在区域内最短距离为最短距离为最短距离为最短距离为d dij ij(i i,j j)，那么问题非线性规划模型为，那么问题非线性规划模型为，那么问题非线性规划模型为，那么问题非线性规划模型为 数学建模25规划模型第25页第25页 解法：能量梯度法、处分函数法、序列无约束最小解法：能量梯度法、处分函数法、序列无约束最小解法：能量梯度法、处分函数法、序列无约束最小解法：能量梯度法、处分函数法、序列无约束最小化办法、逐步迫近搜索法等化办法、逐步迫近搜索法等化办法、逐步迫近搜索法等化办法、逐步迫近搜索法等 模型二：模型二：模型二：模型二：模型三：模型三：模型三：模型三：数学建模26规划模型第26页第26页 利用相对运动办法得到以上模型，再简化为线性规划利用相对运动办法得到以上模型，再简化为线性规划利用相对运动办法得到以上模型，再简化为线性规划利用相对运动办法得到以上模型，再简化为线性规划问题求解。问题求解。问题求解。问题求解。数学建模27规划模型第27页第27页 动态规划模型动态规划模型(Dynamic Programming)动态规划是处理多阶段决议过程最优化一个办法。多动态规划是处理多阶段决议过程最优化一个办法。多动态规划是处理多阶段决议过程最优化一个办法。多动态规划是处理多阶段决议过程最优化一个办法。多阶段决议问题，是指一个问题能够分为若干个阶段，阶段决议问题，是指一个问题能够分为若干个阶段，阶段决议问题，是指一个问题能够分为若干个阶段，阶段决议问题，是指一个问题能够分为若干个阶段，每一阶段需要做出决议，而一个阶段决议，经常会影响每一阶段需要做出决议，而一个阶段决议，经常会影响每一阶段需要做出决议，而一个阶段决议，经常会影响每一阶段需要做出决议，而一个阶段决议，经常会影响下一个阶段决议。要在各个阶段决定一个最优决议，下一个阶段决议。要在各个阶段决定一个最优决议，下一个阶段决议。要在各个阶段决定一个最优决议，下一个阶段决议。要在各个阶段决定一个最优决议，使整个系统达到最佳效果。使整个系统达到最佳效果。使整个系统达到最佳效果。使整个系统达到最佳效果。通过下列一个典型例子，阐明如何建立动态规划模型。通过下列一个典型例子，阐明如何建立动态规划模型。通过下列一个典型例子，阐明如何建立动态规划模型。通过下列一个典型例子，阐明如何建立动态规划模型。数学建模28规划模型第28页第28页 例例6 6 最短路线问题最短路线问题最短路线问题最短路线问题 数学建模29规划模型第29页第29页先引入几种概念先引入几种概念先引入几种概念先引入几种概念 n n状态状态状态状态每一阶段起点位置每一阶段起点位置每一阶段起点位置每一阶段起点位置 n n决议决议决议决议由一个状态变到另一个状态选择由一个状态变到另一个状态选择由一个状态变到另一个状态选择由一个状态变到另一个状态选择 n nx xk k 第第第第 k k 阶段状态，称为状态变量阶段状态，称为状态变量阶段状态，称为状态变量阶段状态，称为状态变量 n nu uk k（x xk k ）从从从从 x xk k 出发所作出决议，称为决议变量出发所作出决议，称为决议变量出发所作出决议，称为决议变量出发所作出决议，称为决议变量 n nD Dk k（x xk k ）第第第第 k k 阶段中所有允许决议集合阶段中所有允许决议集合阶段中所有允许决议集合阶段中所有允许决议集合 n n状态转移方程状态转移方程状态转移方程状态转移方程 x xk+1 k+1=T Tk k (x xk k,u,uk k)n nd dk k (x xk k,u,uk k ）从状态从状态从状态从状态 x xk k 出发，采用决议出发，采用决议出发，采用决议出发，采用决议u uk k ，转移，转移，转移，转移到状态到状态到状态到状态 x xk+1 k+1 效益效益效益效益 n nf fk k（x xk k ）从状态从状态从状态从状态 x xk k 出发到终点最优效益出发到终点最优效益出发到终点最优效益出发到终点最优效益 数学建模30规划模型第30页第30页 最短路问题动态规划最优化原理最短路问题动态规划最优化原理最短路问题动态规划最优化原理最短路问题动态规划最优化原理:假设一条最短路线通过状态假设一条最短路线通过状态假设一条最短路线通过状态假设一条最短路线通过状态 x xk k ，那么，这条路线上，那么，这条路线上，那么，这条路线上，那么，这条路线上从从从从 x xk k 到终点一段，是从到终点一段，是从到终点一段，是从到终点一段，是从 x xk k 出发到终点所有路线中最短。出发到终点所有路线中最短。出发到终点所有路线中最短。出发到终点所有路线中最短。逆序法逆序法逆序法逆序法（回溯法）：（回溯法）：（回溯法）：（回溯法）：从后向前逐步求出各点到终点最佳路线，最后得到由从后向前逐步求出各点到终点最佳路线，最后得到由从后向前逐步求出各点到终点最佳路线，最后得到由从后向前逐步求出各点到终点最佳路线，最后得到由起点到终点最短路线。起点到终点最短路线。起点到终点最短路线。起点到终点最短路线。数学建模31规划模型第31页第31页 最短路问题动态规划模型，归纳为下述递推公式：最短路问题动态规划模型，归纳为下述递推公式：最短路问题动态规划模型，归纳为下述递推公式：最短路问题动态规划模型，归纳为下述递推公式：从最后一段开始，从最后一段开始，从最后一段开始，从最后一段开始，k k=4=4,有三个状态有三个状态有三个状态有三个状态D D1 1,D D2 2,D D3 3,k k=3=3，有有有有4 4 4 4 个状态个状态个状态个状态C Ci i,i=i=1,2,3,4.1,2,3,4.每个状态有两个决每个状态有两个决每个状态有两个决每个状态有两个决议可选择。分别议可选择。分别议可选择。分别议可选择。分别计算各状态出发到终点效益计算各状态出发到终点效益计算各状态出发到终点效益计算各状态出发到终点效益 f f 3 3(C Ci i )：数学建模32规划模型第32页第32页最短路径：最短路径：最短路径：最短路径：最短路径：最短路径：最短路径：最短路径：数学建模33规划模型第33页第33页最短路径：最短路径：最短路径：最短路径：最短路径：最短路径：最短路径：最短路径：数学建模34规划模型第34页第34页 k k=2 =2 =2 =2 时时时时,有两个状态有两个状态有两个状态有两个状态B B1 1,B,B2 2，每个状态有，每个状态有，每个状态有，每个状态有3 3 3 3个决议可选。个决议可选。个决议可选。个决议可选。最短路径：最短路径：最短路径：最短路径：数学建模35规划模型第35页第35页最短路径：最短路径：最短路径：最短路径：或者或者或者或者 k k=1=1 时，时，时，时，最短路径：最短路径：最短路径：最短路径：路径长为：路径长为：路径长为：路径长为：14 14 14 14 数学建模36规划模型第36页第36页 Bellman Bellman 动态规划最优化原理动态规划最优化原理 整个过程最优策略应含有性质：无论过去状态整个过程最优策略应含有性质：无论过去状态和决议如何，对当前状态而言，余下诸决议必须和决议如何，对当前状态而言，余下诸决议必须构成最优策略。构成最优策略。数学建模37规划模型第37页第37页 动态规划特点是将问题按时间或空间特性而分动态规划特点是将问题按时间或空间特性而分成若干个阶段，从而将整个决议过程转化为多阶成若干个阶段，从而将整个决议过程转化为多阶段决议问题。段决议问题。对一些静态决议问题能够引入时间原因，将问对一些静态决议问题能够引入时间原因，将问题转化为多阶段决议问题，然后利用动态规划办题转化为多阶段决议问题，然后利用动态规划办法求解。以上最短路问题处理就是这样一个例子，法求解。以上最短路问题处理就是这样一个例子，下列再举一个例子。下列再举一个例子。数学建模38规划模型第38页第38页 资源分派问题资源分派问题资源分派问题资源分派问题 设有某种资源总数量为设有某种资源总数量为设有某种资源总数量为设有某种资源总数量为 a a ，用于生产，用于生产，用于生产，用于生产 n n 种产品。假如种产品。假如种产品。假如种产品。假如分派数量分派数量分派数量分派数量 x xk k 用于生产第用于生产第用于生产第用于生产第 k k 种产品，其效益为种产品，其效益为种产品，其效益为种产品，其效益为 g gk k(x xk k)。问。问。问。问应如何分派资源使生产总效益最大？应如何分派资源使生产总效益最大？应如何分派资源使生产总效益最大？应如何分派资源使生产总效益最大？静态模型为静态模型为静态模型为静态模型为 数学建模39规划模型第39页第39页 非线性规划问题，应用动态规划办法求解。非线性规划问题，应用动态规划办法求解。非线性规划问题，应用动态规划办法求解。非线性规划问题，应用动态规划办法求解。令令令令 s sk k 表示分派用于生产第表示分派用于生产第表示分派用于生产第表示分派用于生产第 k k 种至第种至第种至第种至第 n n 种产品资源数量，种产品资源数量，种产品资源数量，种产品资源数量，即状态转移方程即状态转移方程即状态转移方程即状态转移方程 s sk k1 1 s sk k x xk k（s s1 1a a，s sn n1 1 0 0 ），），），），f f k k (s sk k)为最大效益。则逆序递推方程为为最大效益。则逆序递推方程为为最大效益。则逆序递推方程为为最大效益。则逆序递推方程为数学建模40规划模型第40页第40页The End !Thanks!数学建模41规划模型第41页第41页