大学数学建模电子教案.ppt

数学建模电子教案 重庆邮电大学数理学院沈世云 第二篇规划论模型 第二章线性规划第三章整数规划第四章无约束非线性规划第五章约束非线性规划第六章规划模型的matlab解法第七章动态规划 第五章约束非线性规划 5 1最优性条件 5 2非线性规划案例 本章主要考察带有约束条件的非线性规划问题 称问题 mp 为数学规划 mathematicalprogramming mp 称为不等式约束 为等式约束 称集合为问题 mp 的可行域 若问题 mp 中的是凸函数 是线性函数 则称问题 mp 为凸规划 5 1 1不等式约束问题的最优性条件 5 1最优性条件 定义5 1 1设 若对某个有 称为点处的起作用约束 也称为有效约束 积极约束 activeconstraint 记为起作用约束下标集 简记为 5 1最优性条件 若 则称为点处的不起作用约束 其几何意义如图所示 在处 是起作用约束 是不起作用约束 在处均是不起作用约束 5 1最优性条件 例5 1用图解法求下列问题的最优解 指出最优解处的起作用约束及目标函数的最优值 1 2 解 1 原问题可以化为 5 1最优性条件 最优解 最优值 在处是起作用约束 如图所示 5 1最优性条件 2 原问题可化为 最优解 最优值 在处是起作用约束 5 1最优性条件 定理5 1 1 fritz john必要条件 设在处可微 在处连续 若是不等式约束问题 1 的最优解 则存在不全为零的数使 5 1最优性条件 解 在处是起作用约束 即 且 取 便有fritz john条件成立 5 1最优性条件 在fritz john必要条件中 若则fritz john条件中就没有目标函数的信息了 这样的fritz john条件就没有多大的价值 为了保证 需对约束条件加以适当的限制条件 称之为约束规格 constraintqualification 在非线性规划的研究中 有着各种不同的约束规格 如果增加起作用约束的梯度向量线性无关的约束规格 就得出著名kuhn tucker条件 它是kuhn和tucker在1951年提出的 简称为k t条件 5 1最优性条件 定理5 1 2 kuhn tucker必要条件 设在处可微 在处连续 线性无关 若是不等式约束问题 5 1 1 的局部最优解 则存在使 5 1最优性条件 解 经验证是可行点 由于在处只有是起作用约束 此时有 5 1最优性条件 在处 均是起作用约束 且是线性无关 由 有方程组 解之有 故是k t点 5 1最优性条件 证明 由定理的条件 显然可行域是凸集 由是凸函数 再由定理1 3 2 有 又由k t条件 存在 使 5 1最优性条件 由是凸函数有 即 即是 5 1 1 的全局最优解 5 1最优性条件 5 1 2等式约束问题的最优性条件 5 1 1 的结论可平移到 5 1 3 中来 并得到 5 1 2 的相应结论 5 1 2 也可采用lagrange乘数法来求解 5 1最优性条件 定义5 1 3对等式约束问题 5 1 2 设存在数称 为等式约束问题 5 1 2 的lagrange函数 其中称为lagrange乘子 记 5 1最优性条件 称为的jacobi矩阵 5 1最优性条件 定义5 1 4若满足 则称为等式约束问题 5 3 的lagrange点 定理5 1 4 必要条件 设等式约束问题 5 1 2 中在处的某个邻域内可微 的jacobi矩阵在处的秩为 若是 5 1 2 的局部最优解 则存在使 5 1最优性条件 定理5 1 5 充分条件 设等式约束问题 5 1 2 中二阶连续可微 若存在使得 其中 则是等式约束问题 5 1 2 的严格局部最优解 5 1最优性条件 例5 1 4求解 解 原问题可化为 有 5 1最优性条件 令有 设向量满足 则有 而此时 由定理4 5知是问题的严格局部最优解 4 1最优性条件 5 1 3混合约束问题的最优性条件 记 5 1最优性条件 5 1最优性条件 在定理4 1 6中 若还有条件 在点处可微 则fritz john条件可改写为 4 1最优性条件 定理5 1 7 kuhn tucker必要条件 设混合约束问题中的在点处可微 在点处连续 在点处连续可微 且线性无关 若是的局部最优解 则存在使 5 1最优性条件 在定理5 1 7中若还有条件在点处可微 则k t条件可改写为 5 1最优性条件 定理5 1 8 充分条件 设混合约束问题 5 1 4 中的在点处可微 若满足 5 1 4 的k t条件 并且是凸函数 是线性函数 则是 5 1 4 的全局最优解 5 1最优性条件 例4 5求解 解 4 1最优性条件 由k t条件有 5 1最优性条件 解此方程组有解 由于是凸函数 是线性函数 而且是k t点 故由定理4 1 8知是问题的全局最优解 5 1最优性条件 5 2非线性规划建模实例 飞行管理问题 1 问题提出 在约10000m高空的某边长为160km的正方形区域内 经常有若干架飞机作水平飞行 区域内每架飞机的位置和速度均由计算机记录其数据 以便进行飞行管理 当一架欲进入该区域的飞机到达区域边缘时 记录其数据后 要立即计算并判断是否会与区域内的飞机发生碰撞 如果会碰撞 则应计算如何调整各架 包括新进入的 飞机飞行的方向角 以避免碰撞 现假定条件如下 1 不碰撞的标准为任意两架飞机的距离大于8km 2 飞机飞行方向角调整的幅度不应超过 3 所有飞机飞行速度均为800km每小时 4 进入该区域的飞机在到达区域边缘时 与区域内飞机的距离应在60km以上 5 最多需考虑6架飞机 6 不必考虑飞机立刻此区域后的状况 5 计算结果 第六章规划模型的matlab求解 6 1用matlab优化工具箱解线性规划 命令 x linprog c a b 2 模型 minz cx 命令 x linprog c a b aeq beq 注意 若没有不等式 存在 则令a b 命令 1 x linprog c a b aeq beq vlb vub 2 x linprog c a b aeq beq vlb vub x0 注意 1 若没有等式约束 则令aeq beq 2 其中x0表示初始点 4 命令 x fval linprog 返回最优解 及 处的目标函数值fval 解编写m文件xxgh1 m如下 c 0 4 0 28 0 32 0 72 0 64 0 6 a 0 010 010 010 030 030 03 0 02000 0500 00 02000 050 000 03000 08 b 850 700 100 900 aeq beq vlb 0 0 0 0 0 0 vub x fval linprog c a b aeq beq vlb vub tomatlab xxgh1 解 编写m文件xxgh2 m如下 c 634 a 010 b 50 aeq 111 beq 120 vlb 30 0 20 vub x fval linprog c a b aeq beq vlb vub tomatlab xxgh2 例3 编写m文件xxgh3 m如下 f 1391011128 a 0 41 110000000 51 21 3 b 800 900 aeq 100100010010001001 beq 400600500 vlb zeros 6 1 vub x fval linprog f a b aeq beq vlb vub tomatlab xxgh3 结果 x 0 0000600 00000 0000400 00000 0000500 0000fval 1 3800e 004即在甲机床上加工600个工件2 在乙机床上加工400个工件1 500个工件3 可在满足条件的情况下使总加工费最小为13800 6 2用matlab解无约束优化问题 其中 3 4 5 的等式右边可选用 1 或 2 的等式右边 函数fminbnd的算法基于黄金分割法和二次插值法 它要求目标函数必须是连续函数 并可能只给出局部最优解 常用格式如下 1 x fminbnd fun x1 x2 2 x fminbnd fun x1 x2 options 3 x fval fminbnd 4 x fval exitflag fminbnd 5 x fval exitflag output fminbnd tomatlab wliti1 主程序为wliti1 m f 2 exp x sin x fplot f 0 8 作图语句 xmin ymin fminbnd f 0 8 f1 2 exp x sin x xmax ymax fminbnd f1 0 8 例2对边长为3米的正方形铁板 在四个角剪去相等的正方形以制成方形无盖水槽 问如何剪法使水槽的容积最大 解 先编写m文件fun0 m如下 functionf fun0 x f 3 2 x 2 x 主程序为wliti2 m x fval fminbnd fun0 0 1 5 xmax xfmax fval 运算结果为 xmax 0 5000 fmax 2 0000 即剪掉的正方形的边长为0 5米时水槽的容积最大 最大容积为2立方米 tomatlab wliti2 命令格式为 1 x fminunc fun x0 或x fminsearch fun x0 2 x fminunc fun x0 options 或x fminsearch fun x0 options 3 x fval fminunc 或 x fval fminsearch 4 x fval exitflag fminunc 或 x fval exitflag fminsearch 5 x fval exitflag output fminunc 或 x fval exitflag output fminsearch 2 多元函数无约束优化问题 标准型为 minf x 3 fminunc为中型优化算法的步长一维搜索提供了两种算法 由options中参数linesearchtype控制 linesearchtype quadcubic 缺省值 混合的二次和三次多项式插值 linesearchtype cubicpoly 三次多项式插 使用fminunc和fminsearch可能会得到局部最优解 说明 fminsearch是用单纯形法寻优 fminunc的算法见以下几点说明 1 fminunc为无约束优化提供了大型优化和中型优化算法 由options中的参数largescale控制 largescale on 默认值 使用大型算法largescale off 默认值 使用中型算法 2 fminunc为中型优化算法的搜索方向提供了4种算法 由options中的参数hessupdate控制 hessupdate bfgs 默认值 拟牛顿法的bfgs公式 hessupdate dfp 拟牛顿法的dfp公式 hessupdate steepdesc 最速下降法 例3minf x 4x12 2x22 4x1x2 2x2 1 exp x1 tomatlab wliti3 1 编写m 文件fun1 m functionf fun1 x f exp x 1 4 x 1 2 2 x 2 2 4 x 1 x 2 2 x 2 1 2 输入m文件wliti3 m如下 x0 1 1 x fminunc fun1 x0 y fun1 x 3 运行结果 x 0 5000 1 0000y 1 3028e 10 tomatlab wliti31 tomatlab wliti32 1 为获得直观认识 先画出rosenbrock函数的三维图形 输入以下命令 x y meshgrid 2 0 1 2 1 0 1 3 z 100 y x 2 2 1 x 2 mesh x y z 2 画出rosenbrock函数的等高线图 输入命令 contour x y z 20 holdonplot 1 2 2 o text 1 2 2 startpoint plot 1 1 o text 1 1 solution 3 用fminsearch函数求解 tomatlab wliti41 输入命令 f 100 x 2 x 1 2 2 1 x 1 2 x fval exitflag output fminsearch f 1 22 运行结果 x 1 00001 0000fval 1 9151e 010exitflag 1output iterations 108funccount 202algorithm nelder meadsimplexdirectsearch 用matlab软件求解 其输入格式如下 1 x quadprog h c a b 2 x quadprog h c a b aeq beq 3 x quadprog h c a b aeq beq vlb vub 4 x quadprog h c a b aeq beq vlb vub x0 5 x quadprog h c a b aeq beq vlb vub x0 options 6 x fval quaprog 7 x fval exitflag quaprog 8 x fval exitflag output quaprog 1 二次规划 例1minf x1 x2 2x1 6x2 x12 2x1x2 2x22s t x1 x2 2 x1 2x2 2x1 0 x2 0 matlab youh1 1 写成标准形式 2 输入命令 h 1 1 12 c 2 6 a 11 12 b 2 2 aeq beq vlb 0 0 vub x z quadprog h c a b aeq beq vlb vub 3 运算结果为 x 0 66671 3333z 8 2222 s t 1 首先建立m文件fun m 定义目标函数f x functionf fun x f f x 2 一般非线性规划 其中x为n维变元向量 g x 与ceq x 均为非线性函数组成的向量 其它变量的含义与线性规划 二次规划中相同 用matlab求解上述问题 基本步骤分三步 3 建立主程序 非线性规划求解的函数是fmincon 命令的基本格式如下 1 x fmincon fun x0 a b 2 x fmincon fun x0 a b aeq beq 3 x fmincon fun x0 a b aeq beq vlb vub 4 x fmincon fun x0 a b aeq beq vlb vub nonlcon 5 x fmincon fun x0 a b aeq beq vlb vub nonlcon options 6 x fval fmincon 7 x fval exitflag fmincon 8 x fval exitflag output fmincon 输出极值点 m文件 迭代的初值 参数说明 变量上下限 注意 1 fmincon函数提供了大型优化算法和中型优化算法 默认时 若在fun函数中提供了梯度 options参数的gradobj设置为 on 并且只有上下界存在或只有等式约束 fmincon函数将选择大型算法 当既有等式约束又有梯度约束时 使用中型算法 2 fmincon函数的中型算法使用的是序列二次规划法 在每一步迭代中求解二次规划子问题 并用bfgs法更新拉格朗日hessian矩阵 3 fmincon函数可能会给出局部最优解 这与初值x0的选取有关 1 写成标准形式 s t 2x1 3x26s tx1 4x25x1 x20 例2 2 先建立m 文件fun3 m functionf fun3 x f x 1 2 x 2 1 2 x 1 2 1 2 x 2 2 matlab youh2 3 再建立主程序youh2 m x0 1 1 a 23 14 b 6 5 aeq beq vlb 0 0 vub x fval fmincon fun3 x0 a b aeq beq vlb vub 4 运算结果为 x 0 76471 0588fval 2 0294 1 先建立m文件fun4 m 定义目标函数 functionf fun4 x f exp x 1 4 x 1 2 2 x 2 2 4 x 1 x 2 2 x 2 1 x1 x2 0s t 1 5 x1x2 x1 x20 x1x2 100 例3 2 再建立m文件mycon m定义非线性约束 function g ceq mycon x g x 1 x 2 1 5 x 1 x 2 x 1 x 2 x 1 x 2 10 3 主程序youh3 m为 x0 1 1 a b aeq 11 beq 0 vlb vub x fval fmincon fun4 x0 a b aeq beq vlb vub mycon matlab youh3 3 运算结果为 x 1 22501 2250fval 1 8951 例4 1 先建立m 文件fun m定义目标函数 functionf fun x f 2 x 1 x 2 2 再建立m文件my2 m定义非线性约束 function g ceq mycon2 x g x 1 2 x 2 2 25 x 1 2 x 2 2 7 3 主程序fxx m为 x0 3 2 5 vlb 00 vub 510 x fval exitflag fmincon fun x0 vlb vub my2 matlab fxx fun 4 运算结果为 x 4 00003 0000fval 11 0000exitflag 1output iterations 4funccount 17stepsize 1algorithm 1x44char firstorderopt cgiterations 返回 牛顿迭代法 例1用牛顿迭代法求方程在x 0 5附近的近似根 误差不超过 牛顿迭代法的迭代函数为 牛顿迭代法 相应的matlab代码为 nddd m clear x 0 5 fori 1 3x x x 3 x 2 x 1 3 x 2 2 x 1 end可算的迭代数列的前3项0 5455 0 5437 0 5437 经三次迭代 就大大超过了精度要求 牛顿迭代法 相应的matlab代码为 nddd1 m clear x x 1 0 9 fori 1 6x i 1 x i x i 3 x i 2 x i 1 3 x i 2 2 x i 1 ifabs x i 1 x i 0 0001x i 1 breakendend 第7章动态规划 chapter7dynamicprogramming 7 1动态规划的基本概念 7 3动态规划的应用举例 7 2动态规划的最优性原理与数学模型 1951年美国数学家r bellman等人创建了动态规划 基本思想 将一个复杂问题分解成若干个阶段 每一个阶段作为一个小问题进行处理 从而决定整个过程的决策 求解过程分两步 先按整体最优化递序地求出各个可能状态的最优化决策 再顺序地求出整个问题的最优策略和最优路线 7 1动态规划的基本概念 例7 1最短路径问题 图7 1表示从a到e之间各点的距离 求a到e的最短路径 7 1 1引例 如果用穷举法 a到e 3 3 2 18条路径 求从a到e的最短路径问题 可以转化为三个性质完全相同 但规模较小的子问题 即分别从b1 b2 b3到e的最短路径问题 计算每条路径的长度 总共4 18 72次加法计算 对18条路径的长度比较 总共18 1 17次比较 如果从a到c的站点有k个 总共3k 1 2条路径 求最短路总共 k 1 3k 1 2次加法 3k 1 2 1次比较 当k值增加 需要进行的加法和比较次数将迅速增加 例如当k 10时 加法次数为433026次 比较39365次 记从bi i 1 2 3 到e的最短路径为s bi 则从a到e的最短距离s a 可表示 计算s b1 又可归结为性质完全相同 但规模更小的问题 即分别求c1 c2 c3到e的最短路径问题s ci i 1 2 3 而求s ci 又可以归结为求s d1 和s d2 这两个子问题 从图7 1看出 在这个问题中 s d1 和s d2 是已知的 它们分别是 s d1 5 s d2 2从这两个值开始 逆向递归计算s a 的值 计算过程如下 s c1 8且如果到达c1 则下一站应到达d1 s c2 7且如果到达c2 则下一站应到达d2 s c3 12且如果到达c3 则下一站应到达d2 计算s bi s b1 20且如果到达b1 则下一站应到达c1 计算s a 从a到e的最短路径为 a b2 c1 d1 e s b2 14且如果到达b2 则下一站应到达c1 s b3 19且如果到达b3 则下一站应到达c2 计算过程及结果用下图表示 从图中任一点到e的最短路径 仅用了18次加法 11次比较 7 1 2动态规划的基本概念 1 阶段 2 状态和状态变量 把所要处理的问题合理地划分成若干个相互联系的阶段 通常用表示阶段变量 如例7 1中 第3阶段集合可记为 每一个阶段的起点 称为该阶段的状态 描述过程状态的变量 称为状态变量 它可以用一个数 一组数或一个向量来描述 常用表示第阶段的某一状态 第阶段状态的集合 3 决策和决策变量 决策就是在某一阶段给定初始状态的情况下 从该状态演变到下一阶段某状态的选择 即确定系统过程发展的方案 用一个变量来描述决策 称这个变量为决策变量 设表示第阶段初始状态为的决策变量 表示初始状态为的允许决策集合 有 4 策略和子策略 由每段的决策组成的整个过程的决策变量序列称为策略 记为 即 从阶段到阶段依次进行的阶段决策构成的决策序列称为子策略 记为 即 时的子策略就是策略 如例7 1中 选取路径就是一个子策略 从允许策略集中选出的具有最佳效果的策略称为最优策略 5 状态转移方程 系统在阶段处于状态 执行决策的结果是系统状态的转移 即由阶段的状态转移到阶段的状态适用于动态规划方法求解的是一类具有无后效性的多段决策过程 无后效性又称马尔科夫性 指系统从某个阶段往后的发展 完全由本阶段所处的状态及其往后的决策决定 与系统以前的状态及决策无关 对于具有无后效性的多阶段决策过程 系统由阶段到阶段的状态转移方程为 7 1 3 即只与有关 而与前面状态无关 称为变换函数或算子 6 指标函数和最优指标函数 在多阶段决策中 可用一个数量指标来衡量每一个阶段决策的效果 这个数量指标就是指标函数 为该阶段状态变量及其以后各阶段的决策变量的函数 设为 即 最常见的指标函数取各阶段效果之和的形式 即 7 1 4 指标函数的最优值 称为相应的最优指标函数 记为 式中opt是最优化之意 根据问题的要求取min或max 7 2动态规划的最优性原理与数学模型 7 2 1最优性原理 多阶段决策过程的特点是每个阶段都要进行决策 段决策过程的策略是由个相继进行的阶段决策构成的决策序列 由于前一阶段的终止状态又是后一阶段的初始状态 因此 确定阶段最优决策不能只从本阶段的效应出发 必须通盘考虑 整体规划 r bellman指出 作为整个过程的最优策略具有这样的性质 即无论过去的状态和决策如何 对前面的决策所形成的状态而言 余下的诸决策必须构成最优策略 7 2 2动态规划的数学模型 设在阶段的状态执行了任意选定的决策后的状态是 这时后部子过程就缩小为后部子过程 根据最优性原理 对后部子过程采用最优策略 由于无后效性 后部子过程的目标函数值为 就某个而言必有 根据条件最优目标函数的定义有 一般表示为 7 2 1 其中 7 2 1 称为动态规划基本方程 亦称bellman方程 当目标函数为阶段效应求和形式时 动态规划的基本方程也可以直接由条件最优目标函数的定义导出 即 其中 动态规划基本方程是最优性原理的体现 即不论初始状态和初始决策是什么 余下的决策对于由初始状态及初始决策造成的状态 必须构成最优策略 由之得到相应的条件最优目标函数值 练习1 a b1 b2 c1 c2 c3 c4 d1 d2 d3 e1 e2 e3 f1 f2 g 5 3 1 3 6 8 7 6 3 6 8 5 3 3 8 4 2 2 2 1 3 3 3 5 2 5 6 6 4 最优路线为 a b1 c2 d1 e2 f2 g路长 18 求从a到g的最短路径 3 k 5 出发点e1 e2 e3 k 2 f2 b1 13u2 b1 c2f2 b2 16u2 b2 c3 759 u5 e2 f2 u6 f2 g 最优策略 a b1 b2 c1 c2 c3 c4 d1 d2 d3 e1 e2 e3 f1 f2 g 5 3 1 3 6 8 7 6 3 6 8 5 3 3 8 4 2 2 2 1 3 3 3 5 2 5 6 6 4 3 求从a到e的最短路径 路线为a b2 c1 d1 e 最短路径为19 a b2 b1 b3 c1 c3 d1 d2 e c2 5 2 14 1 12 6 10 10 4 3 12 11 13 9 6 5 8 10 5 2 练习2 1 7 3动态规划应用举例 1 投资分配问题2 背包问题3 机器负荷分配问题4 设备更新问题 现有数量为a 万元 的资金 计划分配给n个工厂 用于扩大再生产 假设 xi为分配给第i个工厂的资金数量 万元 gi xi 为第i个工厂得到资金后提供的利润值 万元 问题是如何确定各工厂的资金数 使得总的利润为最大 据此 有下式 一 投资分配问题 令 fk x 以数量为x的资金分配给前k个工厂 所得到的最大利润值 用动态规划求解 就是求fn a 的问题 当k 1时 f1 x g1 x 因为只给一个工厂 当1 k n时 其递推关系如下 设 y为分给第k个工厂的资金 其中0 y x 此时还剩x y 万元 的资金需要分配给前k 1个工厂 如果采取最优策略 则得到的最大利润为fk 1 x y 因此总的利润为 gk y fk 1 x y 如果a是以万元为资金分配单位 则式中的y只取非负整数0 1 2 x 上式可变为 所以 根据动态规划的最优化原理 有下式 例题 设国家拨给60万元投资 供四个工厂扩建使用 每个工厂扩建后的利润与投资额的大小有关 投资后的利润函数如下表所示 解 依据题意 是要求f4 60 按顺序解法计算 第一阶段 求f1 x 显然有f1 x g1 x 得到下表 第二阶段 求f2 x 此时需考虑第一 第二个工厂如何进行投资分配 以取得最大的总利润 最优策略为 40 20 此时最大利润为120万元 同理可求得其它f2 x 的值 最优策略为 30 20 此时最大利润为105万元 最优策略为 20 20 此时最大利润为90万元 最优策略为 20 10 此时最大利润为70万元 最优策略为 10 0 或 0 10 此时最大利润为20万元 f2 0 0 最优策略为 0 0 最大利润为0万元 得到下表 最优策略为 20 0 此时最大利润为50万元 第三阶段 求f3 x 此时需考虑第一 第二及第三个工厂如何进行投资分配 以取得最大的总利润 最优策略为 20 10 30 最大利润为155万元 同理可求得其它f3 x 的值 得到下表 第四阶段 求f4 60 即问题的最优策略 最优策略为 20 0 30 10 最大利润为160万元 练习 求投资分配问题得最优策略 其中a 50万元 其余资料如表所示 例 某公司打算在3个不同的地区设置4个销售点 根据市场部门估计 在不同地区设置不同数量的销售点每月可得到的利润如表所示 试问在各地区如何设置销售点可使每月总利润最大 x1 2 x2 1 x3 1 f3 4 47 有一个徒步旅行者 其可携带物品重量的限度为a公斤 设有n种物品可供他选择装入包中 已知每种物品的重量及使用价值 作用 问此人应如何选择携带的物品 各几件 使所起作用 使用价值 最大 这就是背包问题 类似的还有工厂里的下料问题 运输中的货物装载问题 人造卫星内的物品装载问题等 二 背包问题 设xj为第j种物品的装件数 非负整数 则问题的数学模型如下 用动态规划方法求解 令fx y 总重量不超过y公斤 包中只装有前k种物品时的最大使用价值 其中y 0 k 1 2 n 所以问题就是求fn a 其递推关系式为 当k 1时 有 例题 求下面背包问题的最优解 解 a 5 问题是求f3 5 所以 最优解为x 1 1 0 最优值为z 13 练习1 某厂生产三种产品 各种产品重量与利润的关系如表所示 现将此三种产品运往市场出售 运输能力总重量不超过6吨 问如何安排运输 使总利润最大 最优方案 x1 0 2 0 x2 1 0 1 z 260 练习2 求下列问题的最优解 x 2 1 0 最优值为z 13 三 机器负荷分配问题某种机器可以在高 低两种负荷下生产 高负荷生产条件下机器完好率为0 7 即如果年初有u台完好机器投入生产 则年末完好的机器数量为0 7u台 系数0 7称为完好率 年初投入高负荷运行的u台机器的年产量为8u吨 系数8称为单台产量 低负荷运行时 机器完好率为0 9 单台产量为5吨 设开始时有1000台完好机器 要制订五年计划 每年年初将完好的机器一部分分配到高负荷生产 剩下的机器分配到低负荷生产 使五年的总产量为最高 构造动态规划模型如下 阶段 运行年份 其中表示第一年初 依次类推 表示第五年末 即第六年初 状态变量 第年初完好的机器数 其中表示第五年末 即第六年初 的完好机器数 决策变量 第年投入高负荷运行的机器数 状态转移方程 决策允许集合 阶段指标 递推方程 终端条件 注 根据题意 本题的决策允许集合应该是一个整数集合 但由于决策允许集合中可取的决策数量很大 一一列举计算量很大 不妨认为状态变量和决策变量都是连续的 得到最优解后 再作取整处理 由此可以得到 用代入 得到五年最大产量为 每年投入高负荷运行的机器数以及每年初完好的机器数为 在这个例子中 状态变量的终端值是未加约束的 如果要求在第五年末 即第六年初 完好的机器数不少于500台 这时决策变量的决策允许集合将成为 即 或 容易想象 这时的最大产量将比是自由的情况下小 推广到一般情况 设高负荷生产时机器的完好率为 单台产量为 低负荷完好率为 单台产量为 若有满足 则从年 年初将全部完好机器投入低负荷运行 从年 年初将全部完好机器投入高负荷运行 这样的决策 将使总产量达到最大 阶段 月份 状态变量 第个月初 发货以前 的库存量 决策变量 第个月的生产量 状态转移方程 决策允许集合 阶段指标 终端条件 递推方程 递推方程为 而 因此有 也是唯一的决策 因此递推方程为 对于 因为 因此 决策允许集合可以简化为 递推方程成为 对于 由于在的表达式中的系数是 3 因此在决策允许集合中应取集合中的最大值 即 由此 对于 由此 对于 因为 所以 由此 对于 根据题意 所以 由此 将以上结果总结成下表 四设备更新问题一台设备的价格为 运行寿命为年 每年的维修费用是设备役龄的函数 记为 新设备的役龄为 旧设备出售的价格是设备役龄的函数 记为 在年末 役龄为的设备残值为 现有一台役龄为的设备 在使用过程中 使用者每年都面临 继续使用 或 更新 的策略 阶段 运行年份 状态变量 设备的役龄 决策变量 状态转移方程 阶段指标 递推方程 终端条件 设具体数据如下 且 终端条件为 由计算可知 本问题有两个决策 它们对应的最小费用都是115 这两个决策是 四旅行商问题设有个城市 其中每两个城市之间都有道路相连 城市和城市之间的距离为 从某城市出发周游所有城市 经过每个城市一次且仅一次 最后回到出发地 求总行程最短的周游路线 对于一般的情况可以假设两城市之间往返距离不相等 在此例中 为了简化问题 设往返距离相等 即 问题的动态规划模型构造如下 阶段 已经历过的城市个数 包括当前所在的城市 表示出发时位于起点 表示结束时回到终点 状态变量 其中表示当前所在的城市 表示尚未访问过的城市的集合 很明显其中表示空集 并且有 决策变量 其中为当前所在的城市 为下一站将要到达的城市 状态转移方程 若当前的状态为 采取的决策为 则下一步到达的状态为 阶段指标 最优指标函数 表示从城市出发 经过中每个城市一次且仅一次 最后返回城市1的最短距离 终端条件 对于如图所示的一个五个城市的货郎担问题 求解步骤如下 的值列表如下 对于 有 对于 有 对于 有 由状态开始回朔 得到 两条回路的图示如下 容易验证 两条回路的长度都是15 4 7求解数学规划问题 解 设为状态变量 为决策变量 它们满足 第一步 时 第二步 时 令 则由 得驻点 所以 第三步 时 可以求得 回代 由知原问题的最优值为 并可以递推求出 原问题的最优解为 露天矿里铲位已分成矿石和岩石 平均铁含量不低于25 的为矿石 否则为岩石 每个铲位的矿石 岩石数量 以及矿石的平均铁含量 称为品位 都是已知的 每个铲位至多安置一台电铲 电铲平均装车时间5分钟 卡车在等待时所耗费的能量也是相当可观的 原则上在安排时不应发生卡车等待的情况 露天矿生产的车辆安排 cumcm 2003b 矿石卸点需要的铁含量要求都为29 5 1 品位限制 搭配量