数学建模8-动态规划和目标规划 一、动态规划 1.动态规划是求解决策过程最优化的数学方法，主要用于求解以时间划分阶段的动态过程的 优化问题。但是一些与时间无关的静态规划（如线性规划、非线性规划），只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。 2.基本概念、基本方程： （1）阶段 （2）状态 （3）决策 （4）策略 （5）状态转移方程： （6）指标函数和最优值函数： （7）最优策略和最优轨线 （8）递归方程： 3．计算方法和逆序解法（此处较为抽象，理解较为困难，建议结合例子去看）
4．动态规划与静态规划的关系：一些静态规划只需要引入阶段变量、状态、决策等就可以用动态规划方法求解（详见书中例4） 5．若干典型问题的动态规划模型： （1）最短路线问题： （2）生产计划问题:状态定义为每阶段开始时的储存量x k，决策为每个阶段的产量，记每个阶段的需求量（已知量）为d k，则状态转移方程为 （3）资源分配问题：详见例5
状态转移方程： 最优值函数： 自有终端条件： （4）具体应用实例：详见例6、例7。 二、目标规划 1．实际问题中，衡量方案优劣要考虑多个目标，有主要的，有主要的，也有次要的；有最大值的，也有最小值的；有定量的，也有定性的；有相互补充的，也有相互对立的，这时可用目标规划解决。其求解思路有加权系数法、优先等级法、有效解法等。 2．基本概念： （1）正负偏差变量： （2）绝对（刚性）约束和目标约束 ，次位赋（3）优先因子（优先等级）与权系数：凡要求第一位达到的目标赋予优先因子P 1……以此类推。 予P 2 （4）目标规划的目标函数： （5）一般数学模型：
第9章 多目标函数的优化设计方法 Chapter 9 Multi-object Optimal Design 在实际的机械设计中，往往期望在某些限制条件下，多项设计指标同时达到最优，这类问题称为多目标优化设计问题。与前面单目标优化设计不同的是，多目标优化设计有着多种提法和模式，即数学模型。因此，解决起来要比单目标问题复杂的多。 9.1 多目标最优化模型 9.1.1 问题举例 例9-1 生产计划问题 某工厂生产n （2≥n ）种产品：1号品、2号品、...、n 号品。 已知：该厂生产)...,,2,1(n i i =号品的生产能力是i a 吨/小时； 生产一吨)...,,2,1(n i i =号品可获利润i α元； 根据市场预测，下月i 号品的最大销售量为)...,,2(n i b i =吨； 工厂下月的开工能力为T 小时； 下月市场需要尽可能多的1号品。 问题：应如何安排下月的生产计划，在避免开工不足的条件下，使 工人加班时间尽可能的地少； 工厂获得最大利润； 满足市场对1号品尽可能多地要求。 为制定下月的生产计划，设该厂下月生产i 号品的时间为)...,,1(n i x i =小时。 9.1.2 基本概念 如图9.1所示，两个目标函数f 1,f 2中的若干个设计中，3，4称为非劣解，若 )(min{)(*x f x f j j ≤ S.t ．0)(≤x g u u=1,2,………….m 成立，则称* x 为非劣解。若不存在一个方向，同时满足： 0)(*≤*?s x f (目标函数值下降0)(*≤*?s x g (不破坏约束) 图9.1 则称* x 为约束多目标优化设计问题的K-T 非劣解。这样，多目标优化设计问题的求解过程为：先求出满足K-T 条件的非劣解，再从众多的非劣解确定一个选好解。 多目标优化的数学模型： T r x f x f x f X F V )](),........(),([)(m in 21=--
工厂资源规划问题 冉光明 2010070102019 信息与计算科学 指导老师：赵姣珍
目录 摘要 (1) 关键词 (1) 问题的提出 (2) 问题重述与分析 (3) 符号说明 (4) 模型假设 (4) 模型建立与求解 (5) 模型检验 (9) 模型推广 (10) 参考文献 (11) 附录 (12)
摘要：本问题是个优化问题。问题首先选择合适的决策变量即各种产品数，然后通过决策变量来表达约束条件和目标函数，再利用matlab或lingo编写程序，求得最优产品品种计划；最后通过优化模型对问题作以解释，得出当技术服务消耗33小时、劳动力消耗67小时、不消耗行政管理时，得到的是最优品种规划。 问题一回答：当技术服务消耗33小时、劳动力消耗67小时、不消耗行政管理时， 时，若使产品品产品III不值得生产。用matlab运算分析，当产品III的利润增加至25 3 种计划最优，此时需要消耗技术服务29h，劳动力消耗46h，行政管理消耗25h。 问题二回答：利用lingo得到当技术服务增加1h时，利润增加2.5元;劳动力增加1h，利润增加1元；行政管理的增减不会影响利润。 问题三回答：增加的决策变量，调整目标函数。当技术服务消耗33h，劳动力消耗17h，不消耗行政管理，新增量50h时，管理部门采取这样的决策得到最优的产品品种规划。 问题四回答：增加新的约束条件，此时当技术服务消耗32h，劳动力消耗58h，行政管理消耗10h时，得到最优产品品种规划。 本文对模型的求解给出在线性约束条件下的获利最多的产品品种规划。 关键词：线性规划；优化模型；最优品种规划
问题的提出 某工厂制造三种产品，生产这三种产品需要三种资源：技术服务、劳动力和行政管理。下表列出了三种单位产品对每种资源的需要量： 资源利润 技术服务劳动力行政管理 产品I 1 10 2 10 II 1 4 2 6 III 1 5 6 4 现有100h的技术服务、600h劳动力和300h的行政管理时间可使用，求最优产品品种规划。且回答下列问题： ⑴若产品III值得生产的话，它的利润是多少？假使将产品III的利润增加至25/3元，求获利最多的产品品种规划。 ⑵确定全部资源的影子价格。 ⑶制造部门提出建议，要生产一种新产品，该种产品需要技术服务1h、劳动力4h 和行政管理4h。销售部门预测这种产品售出时有8元的单位利润。管理部门应有怎样的决策？ ⑷假定该工厂至少生产10件产品III，试确定最优产品品种规划。
MATLAB 中文论坛讲义 多目标规划优化问题 Matlab 中常用于求解多目标达到问题的函数为fgoalattain.假设多目标函数问题的数学模型为： ub x lb beq x Aeq b x A x ceq x c goal weight x F t s y x ≤≤=≤=≤≤-**0 )(0 )(*)(..min ,γγ weight 为权值系数向量，用于控制对应的目标函数与用户定义的目标函数值的接近程度； goal 为用户设计的与目标函数相应的目标函数值向量； γ为一个松弛因子标量； F(x)为多目标规划中的目标函数向量。 综上，fgoalattain 的优化过程就是使得F 逼近goal; 工程应用中fgoalattain 函数调用格式如下： [x,fval]=fgoalattain (fun,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon) x0表示初值； fun 表示要优化的目标函数； goal 表示函数fun 要逼近的目标值，是一个向量，它的维数大小等于目标函数fun 返回向量F 的维数大小； weight 表示给定的权值向量，用于控制目标逼近过程的步长； 例1. 程序（利用fgoalattain 函数求解） 23222 12 3222132min )3()2()1(min x x x x x x ++-+-+- 0,,6 ..321321≥=++x x x x x x t s ①建立M 文件. function f=myfun(x) f(1)= x(1)-1)^2+(x(2)-2)^2+(x(3)-3)^2; f(2)= x(1)^2+2*x(2)^2+3*x(3)^2; ②在命令窗口中输入. goal=[1,1]; weight=[1,1];
第六章 最优化数学模型 §1 最优化问题 1．1 最优化问题概念 1．2 最优化问题分类 1．3 最优化问题数学模型 §2 经典最优化方法 2．1 无约束条件极值 2．2 等式约束条件极值 2．3 不等式约束条件极值 §3 线性规划 3．1 线性规划 3．2 整数规划 §4 最优化问题数值算法 4．1 直接搜索法 4．2 梯度法 4．3 罚函数法 §5 多目标优化问题 5．1 多目标优化问题 5．2 单目标化解法 5．3 多重优化解法 5．4 目标关联函数解法 5．5 投资收益风险问题 第六章 最优化问题数学模型 §1 最优化问题 1．1 最优化问题概念 （1）最优化问题 在工业、农业、交通运输、商业、国防、建筑、通信、政府机关等各部门各领域的实际工作中，我们经常会遇到求函数的极值或最大值最小值问题，这一类问题我们称之为最优化问题。而求解最优化问题的数学方法被称为最优化方法。它主要解决最优生产计划、最优分配、最佳设计、最优决策、最优管理等求函数最大值最小值问题。 最优化问题的目的有两个：①求出满足一定条件下，函数的极值或最大值最小值；②求出取得极值时变量的取值。 最优化问题所涉及的内容种类繁多，有的十分复杂，但是它们都有共同的关键因素：变量，约束条件和目标函数。 （2）变量 变量是指最优化问题中所涉及的与约束条件和目标函数有关的待确定的量。一般来说，它们都有一些限制条件（约束条件），与目标函数紧密关联。 设问题中涉及的变量为n x x x ,,,21 ；我们常常也用),,,(21n x x x X 表示。 （3）约束条件 在最优化问题中，求目标函数的极值时，变量必须满足的限制称为约束条件。 例如，许多实际问题变量要求必须非负，这是一种限制；在研究电路优化设
1 整数规划的MATLAB 求解方法 （一） 用MATLAB 求解一般混合整数规划问题 由于MATLAB 优化工具箱中并未提供求解纯整数规划和混合整数规划的函数，因而需要自行根据需要和设定相关的算法来实现。现在有许多用户发布的工具箱可以解决该类问题。这里我们给出开罗大学的Sherif 和Tawfik 在MATLAB Central 上发布的一个用于求解一般混合整数规划的程序，在此命名为intprog ，在原程序的基础上做了简单的修改，将其选择分枝变量的算法由自然序改造成分枝变量选择原则中的一种，即：选择与整数值相差最大的非整数变量首先进行分枝。intprog 函数的调用格式如下： [x,fval,exitflag]=intprog(c,A,b,Aeq,beq,lb,ub,M,TolXInteger) 该函数解决的整数规划问题为： ????? ??????∈=≥≤≤=≤=） 取整数（M j x n i x ub x lb b x A b Ax t s x c f j i eq eq T ) ,,2,1(0 ..min 在上述标准问题中，假设x 为n 维设计变量，且问题具有不等式约束1m 个，等式约束2m 个，那么：c 、x 均为n 维列向量，b 为1m 维列向量，eq b 为2m 维列向量，A 为n m ?1维矩阵，eq A 为n m ?2维矩阵。 在该函数中，输入参数有c,A,b,A eq ,b eq ,lb,ub,M 和TolXInteger 。其中c 为目标函数所对应设计变量的系数，A 为不等式约束条件方程组构成的系数矩阵，b 为不等式约束条件方程组右边的值构成的向量。Aeq 为等式约束方程组构成的系数矩阵，b eq 为等式约束条件方程组右边的值构成的向量。lb 和ub 为设计变量对应的上界和下界。M 为具有整数约束条件限制的设计变量的序号，例如问题中设计变量为621,,,x x x ，要求32,x x 和6x 为整数，则M=[2;3;6]；若要求全为整数，则M=1:6，或者M=[1;2;3;4;5;6]。TolXInteger 为判定整数的误差限，即若某数x 和最邻近整数相差小于该误差限，则认为x 即为该整数。
第六章最优化数学模型 §1最优化问题 1．1最优化问题概念 1．2最优化问题分类 1．3最优化问题数学模型 §2经典最优化方法 2．1无约束条件极值 2．2等式约束条件极值 2．3不等式约束条件极值 §3线性规划 3．1线性规划 3．2整数规划 §4最优化问题数值算法 4．1直接搜索法 4．2梯度法 4．3罚函数法 §5多目标优化问题 5．1多目标优化问题 5．2单目标化解法 5．3多重优化解法 5．4目标关联函数解法 5．5投资收益风险问题 第六章最优化问题数学模 §1最优化问题 1．1最优化问题概念 （1）最优化问题在工业、农业、交通运输、商业、国防、建筑、通信、政府机关等各部门各领域的实际工作中，我们经常会遇到求函数的极值或最大值最小值问题，这一类问题我们称之为最优化问题。而求解最优化问题的数学方法被称为最优化方法。它主要解决最优生产计划、最优分配、最佳设计、最优决策、最优管理等求函数最大值最小值问题。 最优化问题的目的有两个：①求出满足一定条件下，函数的极值或最大值最小值； ②求出取得极值时变量的取值。 最优化问题所涉及的内容种类繁多，有的十分复杂，但是它们都有共同的关键因素：变量，约束条件和目标函数。 （2）变量变量是指最优化问题中所涉及的与约束条件和目标函数有关的待确定的量。 一般来说，它们都有一些限制条件（约束条件），与目标函数紧密关联。 设问题中涉及的变量为x1,x2, , x n ；我们常常也用X （x1,x2, ,x n）表示。 3）约束条件 在最优化问题中，求目标函数的极值时，变量必须满足的限制称为约束条件例如，许多实际问题变量要求必须非负，这是一种限制；在研究电路优化设
优化与决策 ——多目标线性规划的若干解法及MATLAB 实现 摘要：求解多目标线性规划的基本思想大都是将多目标问题转化为单目标规划，本文介绍 了理想点法、线性加权和法、最大最小法、目标规划法，然后给出多目标线性规划的模糊数学解法，最后举例进行说明，并用Matlab 软件加以实现。 关键词：多目标线性规划 Matlab 模糊数学。 注：本文仅供参考，如有疑问，还望指正。 一．引言 多目标线性规划是多目标最优化理论的重要组成部分，由于多个目标之间的矛盾性和不可公度性,要求使所有目标均达到最优解是不可能的,因此多目标规划问题往往只是求其有效解(非劣解)。目前求解多目标线性规划问题有效解的方法,有理想点法、线性加权和法、最大最小法、目标规划法。本文也给出多目标线性规划的模糊数学解法。 二．多目标线性规划模型 多目标线性规划有着两个和两个以上的目标函数,且目标函数和约束条件全是线性函数,其数学模型表示为： 11111221221122221122max n n n n r r r rn n z c x c x c x z c x c x c x z c x c x c x =+++??=+++?? ??=+++? （1） 约束条件为： 1111221121122222112212,,,0 n n n n m m mn n m n a x a x a x b a x a x a x b a x a x a x b x x x +++≤??+++≤?? ??+++≤?≥?? （2） 若（1）式中只有一个1122i i i in n z c x c x c x =+++ ，则该问题为典型的单目标线性规划。我们记:()ij m n A a ?=,()ij r n C c ?=,12(,,,)T m b b b b = ,12(,,,)T n x x x x = ，
第六章最优化数学模型 §1 最优化问题 1．1 最优化问题概念 1．2 最优化问题分类 1．3 最优化问题数学模型 §2 经典最优化方法 2．1 无约束条件极值 2．2 等式约束条件极值2．3 不等式约束条件极值 §3 线性规划 3．1 线性规划 3．2 整数规划 §4 最优化问题数值算法4．1 直接搜索法 4．2 梯度法 4．3 罚函数法 §5 多目标优化问题 5．1 多目标优化问题 5．2 单目标化解法 5．3 多重优化解法 5．4 目标关联函数解法5．5 投资收益风险问题
第六章 最优化问题数学模型 §1 最优化问题 1．1 最优化问题概念 （1）最优化问题 在工业、农业、交通运输、商业、国防、建筑、通信、政府机关等各部门各领域的实际工作中，我们经常会遇到求函数的极值或最大值最小值问题，这一类问题我们称之为最优化问题。而求解最优化问题的数学方法被称为最优化方法。它主要解决最优生产计划、最优分配、最佳设计、最优决策、最优管理等求函数最大值最小值问题。 最优化问题的目的有两个：①求出满足一定条件下，函数的极值或最大值最小值；②求出取得极值时变量的取值。 最优化问题所涉及的内容种类繁多，有的十分复杂，但是它们都有共同的关键因素：变量，约束条件和目标函数。 （2）变量 变量是指最优化问题中所涉及的与约束条件和目标函数有关的待确定的量。一般来说，它们都有一些限制条件（约束条件），与目标函数紧密关联。 设问题中涉及的变量为n x x x ,,,21 ；我们常常也用),,,(21n x x x X =表示。 （3）约束条件 在最优化问题中，求目标函数的极值时，变量必须满足的限制称为约束条件。 例如，许多实际问题变量要求必须非负，这是一种限制；在研究电路优化设计问题时，变量必须服从电路基本定律，这也是一种限制等等。在研究问题时，这些限制我们必须用数学表达式准确地描述它们。 用数学语言描述约束条件一般来说有两种： 等式约束条件 m i X g i ,,2,1,0)( == 不等式约束条件 r i X h i ,,2,1, 0)( =≥ 或 r i X h i ,,2,1, 0)( =≤ 注：在最优化问题研究中，由于解的存在性十分复杂，一般来说，我们不考虑不等式约束条件0)(>X h 或0)( 四类基本模型 1 优化模型 1.1 数学规划模型 线性规划、整数线性规划、非线性规划、多目标规划、动态规划。 1.2 微分方程组模型 阻滞增长模型、SARS 传播模型。 1.3 图论与网络优化问题 最短路径问题、网络最大流问题、最小费用最大流问题、最小生成树问题(MST)、旅行商问题(TSP)、图的着色问题。 1.4 概率模型 决策模型、随机存储模型、随机人口模型、报童问题、Markov 链模型。 1.5 组合优化经典问题 ● 多维背包问题(MKP) 背包问题：n 个物品，对物品i ，体积为i w ，背包容量为W 。如何将尽可能多的物品装入背包。 多维背包问题：n 个物品，对物品i ，价值为i p ，体积为i w ，背包容量为W 。如何选取物品装入背包，是背包中物品的总价值最大。 多维背包问题在实际中的应用有：资源分配、货物装载和存储分配等问题。该问题属于NP 难问题。 ● 二维指派问题(QAP) 工作指派问题：n 个工作可以由n 个工人分别完成。工人i 完成工作j 的时间为ij d 。如何安排使总工作时间最小。 二维指派问题（常以机器布局问题为例）：n 台机器要布置在n 个地方，机器i 与k 之间的物流量为ik f ，位置j 与l 之间的距离为jl d ，如何布置使费用最小。 二维指派问题在实际中的应用有：校园建筑物的布局、医院科室的安排、成组技术中加工中心的组成问题等。 ● 旅行商问题(TSP) 旅行商问题：有n 个城市，城市i 与j 之间的距离为ij d ，找一条经过n 个城市的巡回（每个城市经过且只经过一次，最后回到出发点），使得总路程最小。 ● 车辆路径问题(VRP) 车辆路径问题（也称车辆计划）：已知n 个客户的位置坐标和货物需求，在 多目标规划训练例题 某音像商店有5名全职熟练货员和4名兼职售货员，全职售货员每月工作160h,兼职售货员每月工作80h ，根据过去的工作纪录，全职售货员每小时销售CD25张，平均每小时工资15元，加班工资每小时22.5元，兼职售货员每小时销售CD10张，平均工资每小时10元，加班工资每小时10元，现在预测下个月CD 销售量为27500张，商店每周开门营业6天，所以可能要加班，每出售一张CD 盈利1.5元， 商店经理认为，保持稳定的就业水平加上必要的加班，比不加班但就业水平不稳定要好，但全职售货员如果加班过多，就会因为疲劳过度而造成效益下降，因此，不允许每月加班超过100h,建立相应的目标规划模型，并应用Lingo 软件求解。 解：首先建立目标约束的优先级 1P ：下月的CD 销售量达到27500张 2P ：限制全职售货员加班时间不超过100h 3P ：保持全体售货员充分就业，因为充分工作是良好劳资关系的重要因素，但对全职售货 员要比兼职售货员加倍优先考虑 4P ：尽量减少加班时间，但对两种售货员区别对待，优先权因子由他们对利润的贡献而定。 第二，建立目标约束 （1）销售目标约束，设 1x ：全体售货员下月的工作时间； 2x ：全体兼职售货员下月的工作时间； - 1d ：达不到销售目标的偏差； +1d ：超过销售目标的偏差； 希望下月的销售超过27500张CD 片，因此销售目标为 ???=-+++ -- 27500 1025} min{11211d d x x d （2）正常工作时间约束，设 - 2d ：全体全职售货员下月的停工时间； + 2d ：全体全职售货员下月的加班时间； - 3d ：全体兼职售货员下月的停工时间； +3d ：全体兼职售货员下月的加班时间； 27. 多目标规划 一、线性规划的局限性 1. 线性规划要求所求解问题必须满足全部的约束，而实际问题中并非所有约束都需要严格的满足； 2. 线性规划只能处理单目标的优化问题，从而对一些次目标只能转化为约束处理，而实际问题中，目标和约束是可以相互转化的，处理时不一定要严格区分； 3. 线性规划在处理问题时，将各个约束（也可看成目标）的地位看成同等重要，实际问题中，各个目标的重要性有层次上的差别，在同一层次也可能有不同权重； 4. 线性规划寻找最优解，而许多实际问题只要找到满意解就可以了。 例1 (线性规划——生产安排问题) 某企业生产甲、乙两种产品，需要用到A,B,C三种设备，每天产品盈利与设备使用工时及限制如下表： 问：该企业应如何安排生产，能使总利润最大？ 解：设甲乙产品的产量分别为x 1, x 2，建立线性规划模型： 12 121212max 200300 s. t. 2212 416 515 ,0z x x x x x x x x =++≤≤≤≥ 用Lingo 可求得最优解：x 1=3, x 2=3, z *=1500. 但实际上，企业的经营目标不仅仅是利润，还需要考虑多个方面，比如：增加下列因素（目标） （1） 力求使利润不低于1500元； （2） 考虑市场需求，甲乙两种产品的产量比应尽量保持1:2； （3） 设备A 位贵重设备，严格禁止超时使用； （4）设备C 可以适当加班，但要控制，设备B 既要求充分利用，又尽可能不加班，在重要性上，设备B 是设备C 的3倍。 这就需要用目标规划。 二、目标规划的基本概念 1. 设置偏差变量 偏差变量——表示实际值与目标值之间的差异； d +——表示超出目标的差值，称为正偏差变量；当实际值超过目标值时，有d - = 0，d +> 0; d -——表示未达到目标的差值，称为负偏差变量；当实际值未达到目标值时，有d + = 0，d ->0. 注：若实际值与目标值一致，有d - = d += 0.数学建模 四大模型总结
目标规划程序(数学建模)
Matlab学习系列27. 多目标规划
相关主题
文本预览