数学建模专题培训市公开课一等奖百校联赛特等奖课件.pptx

数数 学学 建建 模模 从自然走向理性之路 数学建模1规划模型第1页第五讲第五讲 规划模型规划模型【主要内容】【主要内容】介绍线性规划模型、非线性规划模介绍线性规划模型、非线性规划模型及动态规划模型型及动态规划模型 【主要目标】【主要目标】了解规划问题建模与求解，重点在了解规划问题建模与求解，重点在模型建立与结果分析模型建立与结果分析数学建模2规划模型第2页 线性规划模型线性规划模型(Linear Programming)建立模型建立模型 线性规划问题：求多变量线性规划问题：求多变量线性规划问题：求多变量线性规划问题：求多变量线性函数线性函数线性函数线性函数在在在在线性约束线性约束线性约束线性约束条件下最条件下最条件下最条件下最优值优值优值优值 线性规划问题普通形式：线性规划问题普通形式：线性规划问题普通形式：线性规划问题普通形式：数学建模3规划模型第3页 线性规划问题标准形式：线性规划问题标准形式：线性规划问题标准形式：线性规划问题标准形式：数学建模4规划模型第4页 说明说明说明说明 任意线性规划问题可化为标准形式。详细方式以下：任意线性规划问题可化为标准形式。详细方式以下：任意线性规划问题可化为标准形式。详细方式以下：任意线性规划问题可化为标准形式。详细方式以下：1.1.1.1.目标函数标准化目标函数标准化目标函数标准化目标函数标准化 ：2.2.2.2.约束条件标准化约束条件标准化约束条件标准化约束条件标准化：假设约束条件中有不等式约束假设约束条件中有不等式约束假设约束条件中有不等式约束假设约束条件中有不等式约束 或或或或 引入新变量引入新变量引入新变量引入新变量 （称为松弛变量），则以上两式等（称为松弛变量），则以上两式等（称为松弛变量），则以上两式等（称为松弛变量），则以上两式等价于以下两式：价于以下两式：价于以下两式：价于以下两式：数学建模5规划模型第5页 3.3.3.3.自由变量标准化自由变量标准化自由变量标准化自由变量标准化 若变量若变量若变量若变量 x xj j 无约束，可引入两个新变量无约束，可引入两个新变量无约束，可引入两个新变量无约束，可引入两个新变量 ，令，令，令，令 故以下我们只考虑标准形式。故以下我们只考虑标准形式。故以下我们只考虑标准形式。故以下我们只考虑标准形式。数学建模6规划模型第6页矩阵形式表示矩阵形式表示矩阵形式表示矩阵形式表示普通要求，普通要求，普通要求，普通要求，数学建模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页 耗煤量为耗煤量为耗煤量为耗煤量为 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页 例例2 2 设某工厂有甲、乙、丙、丁四个车间，生设某工厂有甲、乙、丙、丁四个车间，生产产A A、B B、C C、D D、E E、F F六种产品，依据机车性能六种产品，依据机车性能和以前生产情况，得知生产每单位产品所需各车和以前生产情况，得知生产每单位产品所需各车间工作时数、每个车间在一个季度工作时数上限间工作时数、每个车间在一个季度工作时数上限以及产品价格，以下表所表示。问：每种产品每以及产品价格，以下表所表示。问：每种产品每季度各应生产多少，才能使这个工厂每季度生产季度各应生产多少，才能使这个工厂每季度生产总值到达最大？总值到达最大？数学建模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页 解解解解 以以以以 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页引入松弛变量引入松弛变量x7 x10，化成标准型，化成标准型 数学建模13规划模型第13页 线性规划问题求解线性规划问题求解 1.1.可行域几何特征可行域几何特征 满足约束条件解称为满足约束条件解称为可行解可行解，全部可行解组成集，全部可行解组成集合称为合称为可行域可行域，满足目标式可行解称为，满足目标式可行解称为最优解最优解。n n线性规划问题可行域是一个凸多边形；线性规划问题可行域是一个凸多边形；n n线性规划问题假如存在最优解，则最优解必在可线性规划问题假如存在最优解，则最优解必在可行域顶点处到达。行域顶点处到达。数学建模14规划模型第14页 2.2.单纯形法单纯形法 基本思想：从可行域一个顶点（基本可行解）出基本思想：从可行域一个顶点（基本可行解）出发，转换到另一个顶点，而且使目标函数值逐步发，转换到另一个顶点，而且使目标函数值逐步减小，有限步后可得到最优解。减小，有限步后可得到最优解。数学建模15规划模型第15页 整数规划整数规划 自变量取整数线性规划称为整数（线性）自变量取整数线性规划称为整数（线性）规划。规划。割平面法，分支定界法割平面法，分支定界法 数学建模16规划模型第16页 0 01 1规划规划规划规划 例例例例3 3 3 3 （MCM-88BMCM-88BMCM-88BMCM-88B）要把七）要把七）要把七）要把七种不一样规格包装箱装到两辆铁种不一样规格包装箱装到两辆铁种不一样规格包装箱装到两辆铁种不一样规格包装箱装到两辆铁路平板车上去，各包装箱宽、高路平板车上去，各包装箱宽、高路平板车上去，各包装箱宽、高路平板车上去，各包装箱宽、高均相同，但厚度（厘米）与重量均相同，但厚度（厘米）与重量均相同，但厚度（厘米）与重量均相同，但厚度（厘米）与重量（千克）不一样。下表给出各包装箱厚度、重量及数量。（千克）不一样。下表给出各包装箱厚度、重量及数量。（千克）不一样。下表给出各包装箱厚度、重量及数量。（千克）不一样。下表给出各包装箱厚度、重量及数量。每辆平板车有每辆平板车有每辆平板车有每辆平板车有10.210.210.210.2米长地方可用来装包装箱，载重米长地方可用来装包装箱，载重米长地方可用来装包装箱，载重米长地方可用来装包装箱，载重40404040吨。由吨。由吨。由吨。由于当地货运限制，对于当地货运限制，对于当地货运限制，对于当地货运限制，对C C5 5,C,C6 6 ,C,C7 7 类包装箱总数有一个尤其限制：该类包装箱总数有一个尤其限制：该类包装箱总数有一个尤其限制：该类包装箱总数有一个尤其限制：该类箱子总厚度不超出类箱子总厚度不超出类箱子总厚度不超出类箱子总厚度不超出302.7302.7302.7302.7（厘米）。试把包装箱装到平板车上去（厘米）。试把包装箱装到平板车上去（厘米）。试把包装箱装到平板车上去（厘米）。试把包装箱装到平板车上去使得浪费空间最小。使得浪费空间最小。使得浪费空间最小。使得浪费空间最小。数学建模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页 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页 目标函数目标函数目标函数目标函数 例例例例4 4 4 4 分工问题分工问题分工问题分工问题 某车间有四项工作需要完成，现已找到四个人做这某车间有四项工作需要完成，现已找到四个人做这某车间有四项工作需要完成，现已找到四个人做这某车间有四项工作需要完成，现已找到四个人做这些工作，经过试用，得到这四个人做每一项工作相对生些工作，经过试用，得到这四个人做每一项工作相对生些工作，经过试用，得到这四个人做每一项工作相对生些工作，经过试用，得到这四个人做每一项工作相对生产率指数，列表以下产率指数，列表以下产率指数，列表以下产率指数，列表以下 。假定每个人只能分配一项工作，并希望分配后总生假定每个人只能分配一项工作，并希望分配后总生假定每个人只能分配一项工作，并希望分配后总生假定每个人只能分配一项工作，并希望分配后总生产率最高，应怎样分配工作？产率最高，应怎样分配工作？产率最高，应怎样分配工作？产率最高，应怎样分配工作？数学建模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页每个人做一项工作每个人做一项工作每个人做一项工作每个人做一项工作 每项工作有一人做每项工作有一人做每项工作有一人做每项工作有一人做目标函数目标函数目标函数目标函数 数学建模22规划模型第22页 非线性规划模型非线性规划模型 (Nonlinear Programming)例例例例5 5 5 5 飞行管理问题（飞行管理问题（飞行管理问题（飞行管理问题（CUMCM95A)CUMCM95A)CUMCM95A)CUMCM95A)在高空中一个边长为在高空中一个边长为在高空中一个边长为在高空中一个边长为160160160160公里正方形区域内，经常有若公里正方形区域内，经常有若公里正方形区域内，经常有若公里正方形区域内，经常有若干架飞机作水平飞行。区域内每架飞机位置和速度均由干架飞机作水平飞行。区域内每架飞机位置和速度均由干架飞机作水平飞行。区域内每架飞机位置和速度均由干架飞机作水平飞行。区域内每架飞机位置和速度均由计算机统计其数据。当一架欲进入该区域飞机抵达区域计算机统计其数据。当一架欲进入该区域飞机抵达区域计算机统计其数据。当一架欲进入该区域飞机抵达区域计算机统计其数据。当一架欲进入该区域飞机抵达区域边缘时，要马上计算并判断其是否会与区域内飞机碰撞。边缘时，要马上计算并判断其是否会与区域内飞机碰撞。边缘时，要马上计算并判断其是否会与区域内飞机碰撞。边缘时，要马上计算并判断其是否会与区域内飞机碰撞。假如会碰撞，则要计算怎样调整各架（包含新进入）飞假如会碰撞，则要计算怎样调整各架（包含新进入）飞假如会碰撞，则要计算怎样调整各架（包含新进入）飞假如会碰撞，则要计算怎样调整各架（包含新进入）飞机飞行方向角，以防止碰撞。现假定条件以下：机飞行方向角，以防止碰撞。现假定条件以下：机飞行方向角，以防止碰撞。现假定条件以下：机飞行方向角，以防止碰撞。现假定条件以下：数学建模23规划模型第23页n n不碰撞标准为任意两架飞机距离大于不碰撞标准为任意两架飞机距离大于不碰撞标准为任意两架飞机距离大于不碰撞标准为任意两架飞机距离大于8 8公里；公里；公里；公里；n n每架飞机飞行方向角调整幅度不应超出每架飞机飞行方向角调整幅度不应超出每架飞机飞行方向角调整幅度不应超出每架飞机飞行方向角调整幅度不应超出3030度；度；度；度；n n全部飞机飞行速度均为全部飞机飞行速度均为全部飞机飞行速度均为全部飞机飞行速度均为800800公里公里公里公里/小时；小时；小时；小时；n n欲进入飞机在抵达区域边缘时，与区域内飞机距离应在欲进入飞机在抵达区域边缘时，与区域内飞机距离应在欲进入飞机在抵达区域边缘时，与区域内飞机距离应在欲进入飞机在抵达区域边缘时，与区域内飞机距离应在6060公里以上；公里以上；公里以上；公里以上；n n最多需考虑最多需考虑最多需考虑最多需考虑6 6架飞机；架飞机；架飞机；架飞机；n n无须考虑飞机离开此区域后情况。无须考虑飞机离开此区域后情况。无须考虑飞机离开此区域后情况。无须考虑飞机离开此区域后情况。请你建立数学模型，对以下数据进行计算（方向角请你建立数学模型，对以下数据进行计算（方向角请你建立数学模型，对以下数据进行计算（方向角请你建立数学模型，对以下数据进行计算（方向角误差不超出误差不超出误差不超出误差不超出0.010.01度），要求飞机飞行方向角调整幅度尽度），要求飞机飞行方向角调整幅度尽度），要求飞机飞行方向角调整幅度尽度），要求飞机飞行方向角调整幅度尽可能小。（数据略）可能小。（数据略）可能小。（数据略）可能小。（数据略）数学建模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页 解法：能量梯度法、处罚函数法、序列无约束最小解法：能量梯度法、处罚函数法、序列无约束最小解法：能量梯度法、处罚函数法、序列无约束最小解法：能量梯度法、处罚函数法、序列无约束最小化方法、逐步迫近搜索法等化方法、逐步迫近搜索法等化方法、逐步迫近搜索法等化方法、逐步迫近搜索法等 模型二：模型二：模型二：模型二：模型三：模型三：模型三：模型三：数学建模26规划模型第26页 利用相对运动方法得到以上模型，再简化为线性规划利用相对运动方法得到以上模型，再简化为线性规划利用相对运动方法得到以上模型，再简化为线性规划利用相对运动方法得到以上模型，再简化为线性规划问题求解。问题求解。问题求解。问题求解。数学建模27规划模型第27页 动态规划模型动态规划模型(Dynamic Programming)动态规划是处理多阶段决议过程最优化一个方法。多动态规划是处理多阶段决议过程最优化一个方法。多动态规划是处理多阶段决议过程最优化一个方法。多动态规划是处理多阶段决议过程最优化一个方法。多阶段决议问题，是指一个问题能够分为若干个阶段，阶段决议问题，是指一个问题能够分为若干个阶段，阶段决议问题，是指一个问题能够分为若干个阶段，阶段决议问题，是指一个问题能够分为若干个阶段，每一阶段需要做出决议，而一个阶段决议，经常会影响每一阶段需要做出决议，而一个阶段决议，经常会影响每一阶段需要做出决议，而一个阶段决议，经常会影响每一阶段需要做出决议，而一个阶段决议，经常会影响下一个阶段决议。要在各个阶段决定一个最优决议，下一个阶段决议。要在各个阶段决定一个最优决议，下一个阶段决议。要在各个阶段决定一个最优决议，下一个阶段决议。要在各个阶段决定一个最优决议，使整个系统到达最正确效果。使整个系统到达最正确效果。使整个系统到达最正确效果。使整个系统到达最正确效果。经过以下一个经典例子，说明怎样建立动态规划模型。经过以下一个经典例子，说明怎样建立动态规划模型。经过以下一个经典例子，说明怎样建立动态规划模型。经过以下一个经典例子，说明怎样建立动态规划模型。数学建模28规划模型第28页 例例6 6 最短路线问题最短路线问题最短路线问题最短路线问题 数学建模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页 最短路问题动态规划最优化原理最短路问题动态规划最优化原理最短路问题动态规划最优化原理最短路问题动态规划最优化原理:假设一条最短路线经过状态假设一条最短路线经过状态假设一条最短路线经过状态假设一条最短路线经过状态 x xk k ，那么，这条路线上，那么，这条路线上，那么，这条路线上，那么，这条路线上从从从从 x xk k 到终点一段，是从到终点一段，是从到终点一段，是从到终点一段，是从 x xk k 出发到终点全部路线中最短。出发到终点全部路线中最短。出发到终点全部路线中最短。出发到终点全部路线中最短。逆序法逆序法逆序法逆序法（回溯法）：（回溯法）：（回溯法）：（回溯法）：从后向前逐步求出各点到终点最正确路线，最终得到从后向前逐步求出各点到终点最正确路线，最终得到从后向前逐步求出各点到终点最正确路线，最终得到从后向前逐步求出各点到终点最正确路线，最终得到由起点到终点最短路线。由起点到终点最短路线。由起点到终点最短路线。由起点到终点最短路线。数学建模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页最短路径：最短路径：最短路径：最短路径：最短路径：最短路径：最短路径：最短路径：数学建模33规划模型第33页最短路径：最短路径：最短路径：最短路径：最短路径：最短路径：最短路径：最短路径：数学建模34规划模型第34页 k k=2 =2 =2 =2 时时时时,有两个状态有两个状态有两个状态有两个状态B B1 1,B,B2 2，每个状态有，每个状态有，每个状态有，每个状态有3 3 3 3个决议可选。个决议可选。个决议可选。个决议可选。最短路径：最短路径：最短路径：最短路径：数学建模35规划模型第35页最短路径：最短路径：最短路径：最短路径：或者或者或者或者 k k=1=1 时，时，时，时，最短路径：最短路径：最短路径：最短路径：路径长为：路径长为：路径长为：路径长为：14 14 14 14 数学建模36规划模型第36页 Bellman Bellman 动态规划最优化原理动态规划最优化原理 整个过程最优策略应含有性质：不论过去状态整个过程最优策略应含有性质：不论过去状态和决议怎样，对当前状态而言，余下诸决议必须和决议怎样，对当前状态而言，余下诸决议必须组成最优策略。组成最优策略。数学建模37规划模型第37页 动态规划特点是将问题按时间或空间特征而分动态规划特点是将问题按时间或空间特征而分成若干个阶段，从而将整个决议过程转化为多阶成若干个阶段，从而将整个决议过程转化为多阶段决议问题。段决议问题。对一些静态决议问题能够引入时间原因，将问对一些静态决议问题能够引入时间原因，将问题转化为多阶段决议问题，然后利用动态规划方题转化为多阶段决议问题，然后利用动态规划方法求解。以上最短路问题处理就是这么一个例子，法求解。以上最短路问题处理就是这么一个例子，以下再举一个例子。以下再举一个例子。数学建模38规划模型第38页 资源分配问题资源分配问题资源分配问题资源分配问题 设有某种资源总数量为设有某种资源总数量为设有某种资源总数量为设有某种资源总数量为 a a ，用于生产，用于生产，用于生产，用于生产 n n 种产品。假如种产品。假如种产品。假如种产品。假如分配数量分配数量分配数量分配数量 x xk k 用于生产第用于生产第用于生产第用于生产第 k k 种产品，其效益为种产品，其效益为种产品，其效益为种产品，其效益为 g gk k(x xk k)。问。问。问。问应怎样分配资源使生产总效益最大？应怎样分配资源使生产总效益最大？应怎样分配资源使生产总效益最大？应怎样分配资源使生产总效益最大？静态模型为静态模型为静态模型为静态模型为 数学建模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页The End !Thanks!数学建模41规划模型第41页