优化模型在生产计划制定中的应用毕业论文
题目(中文) : 优化模型在生产计划制定中的应用
(英文) : The Application of Optimization Model
目 录
绪论 . ............................................................... 4
1优化模型的提出背景及实际意义 ...................................... 5
1.1优化模型的提出背景 . .......................................... 6
1.2优化模型的实际意义 . .......................................... 7
2优化模型的基本要素及分类 .......................................... 7
2.1优化模型的基本要素 . .......................................... 8
2.1.1优化变量 ............................................... 8
2.1.2目标函数 ............................................... 8
2.1.3约束条件 ............................................... 8
2.2优化模型的分类 . .............................................. 9
3生产计划制定及其求解方法 .......................................... 9
3.1多阶段转化 . ................................................. 10
3.1.1多阶段转化动态规划的提出 .............................. 10
3.1.2最优化原则 ............................................ 11
3.1.3多阶段转化对生产计划的应用 ............................ 12
3.2 变分法 ..................................................... 18
3.2.1问题的提出 ............................................ 19
3.2.2 模型的假设 . ........................................... 19
3.2.3建模与求解 ............................................ 20
3.2.4 实 例 . ............................................... 23
结束语 . ............................................................ 24
参考文献 . .......................................................... 25
致 谢 . ............................................................. 26
优化模型在生产计划制定中的应用
摘 要
优化问题是在工程技术、生产计划、经济管理和科学研究等领域中最常遇到的一类问题. 而优化模型作为数学模型中的一种常见模型, 是数学建模在这些领域中的成功应用. 本文在给出优化模型的一些定理和相关概念之后, 介绍了优化问题的几种分类, 如有约束的优化问题, 无约束优化问题, 线性优化问题, 动态优化问题及其相关内容, 并对优化模型做了简单的分析和说明. 同时重点整理了动态优化问题的两种解法——多阶段转化和变分法, 并分别对它们在动态优化中各自的应用范围和具体作用做了分析;接着根据对生产计划制定的研究, 运用两种方法对其具体问题进行定量分析;最后用优化模型解决了在生产计划中遇到的一些问题.
【关键词】 数学建模 优化模型 生产计划 多阶段转化 生产率 变分法
The Application of Optimization Model in the Draft of Production Plan
Abstract
Optimization problem is a class of problems most commonly encountered in the engineering, production planning, economic management and scientific research. The optimization model as a common model of mathematical model is successful application of mathematical modeling in these areas. The paper introduces several kinds of classification of optimization problems in this article, such as constrained optimization problems, unconstrained optimization problems, linear optimization problems,dynamic optimization problems and related content after some theorems and related concepts are given. The paper also do a simple analysis and explanation for the optimization model and address sorting two solutions of the dynamic optimization problems----multi-stage transformation and the variational method at the same time. What’s more,it respectively analyzes their applicating range and specific role in the dynamic optimization. Then according to the resarch of producting plan, it uses two kinds of methods to conduct quantitative analysis for its specific issues.Finally,it solves some problems of producting plan through optimization model.
【Key words】 Mathematical Modeling Optimization Model Program Production Multistage Conversion Productivity The Variational Method
绪论
一般地说, 数学模型可以描述为, 对于现实世界的一个特定对象, 为了一个特
定目的, 根据特有的内在规律, 做出一些必要的简化假设, 运用适当的数学工具, 得到的一个数学结构[1]. 现实生活中运用数学建模来解决实际问题是十分常见的, 可以说数学模型是将数学和现实生活联系起来的一座桥梁, 而优化模型作为一种最常见且得到广泛应用的模型, 正是数学建模在生产经济管理领域中的典型应用.
优化问题是人们最常遇到的一类问题.设计师要在满足强度要求等条件下选择材料的尺寸, 使结构总量最轻;公司经理要根据生产成本和市场需求确定产品价格, 使所获利润最高;投资者要选择一些股票、债券“下注”, 使收益最大, 而风险最小.
用数学建模的方法来处理优化问题, 即建立和求解所谓优化模型. 虽然由于建模时要做适当的简化, 可能使得结果不一定完全可行或达到实际上的最优, 但是它基于客观规律和数据, 又不需要多大的费用. 如果在建模的基础上再辅之以适当的经验和试验, 就可以期望得到实际问题的一个比较圆满的回答. 在决策科学化、定量化的呼声日益高涨的今天, 这无疑是符合时代潮流和形势发展需要的.
在市场经济中有关产品的效益是由生产的现实条件和需求者的需求量关系来决定的, 由于产量与费用的这种波动关系, 从而抽象出了优化模型. 优化模型是在生产中是供应者在最节省能源的情况下获得最大的效益, 对企业追求最大利润起到了相当重要的作用. 它要求企业在生产中对原材料做到充分利用, 正确把握产品产量和费用间的规律, 最终又快又好的完成产量, 使企业获得最大利润.
优化模型是生产计划和经济管理中的一个经典模型, 在对寻求最大效益方面的应用非常广泛. 例如公司经理要根据生产成本和市场需求确定产品价格和生产计划, 使利润达到最大;调度人员要在满足物质需求和装载条件下安排从各需求点的运量和路线, 使运输总费用达到最低. 然而简单优化模型假设提供的原材料、生产环境以及人力资源都是静态的, 且需求者要求的产量一定, 但假设条件在现实的经济系统中不可能都是静态的, 因此本文我们在分析了简单的优化模型后, 又介绍了更加符合现实经济条件的动态优化模型, 并对该模型进行了分析.
随着国内外对优化模型的不断研究和改进, 其应用领域已不仅仅局限于单领域范围, 也将其运用在石油开采、城市规划、人力资源分配等问题的分析上. 当前全球经济正处于金融危机的严重影响下, 如何在当前形势下制定出比较有利的生产计划对一个企业来说是非常重要的, 本文我们将主要运用优化模型来研究生产计划的制定方案, 并研究结果来确定比较合理的计划方案.
1优化模型的提出背景及实际意义
优化模型工作是利用现有的条件规划出各种“最优”方案为现代生产计划和管理工作中的经济利益预估服务. 这里通过变分法作出的求极限值的模型被称为优化模型. 优化模型在现代企业管理中有很多的应用, 如物流、生产计划、原材料采购、劳动力的分配、广告促销、运输、成本控制、项目择优、信贷投放、企业的资产负债情况等方面的问题都可以用线性规划来解决.
1.1优化模型的提出背景
数学模型是对于一个现实对象, 为了一个特定目的, 根据特有的内在规律, 做出一些必要的简化假设, 运用适当的数学工具, 得到的一个数学结构. 数学模型是将数学和现实生活联系起来的桥梁, 在众多领域有着广泛的应用.
求解实际的最优化问题一般要进行两项工作. 第一是将实际问题抽象地用数学模型来描述, 包括选择优化变量, 确定目标函数, 给出约束条件;第二是对数学模型进行必要的简化, 并采用适当的最优化方法求解数学模型. 建立优化数学模型是求解优化问题的基础, 有了正确、合理的模型, 才能选择适当的方法来求解. 数学模型的建立要求具备与实际问题有关的专业技术知识, 确定优化追求的目标, 并推导出相应的目标函数;分析影响目标函数的因素有哪些, 它们之间的相互关系如何, 选择哪些参数作为优化变量, 同时又受到哪些约束条件的限制. 优化变量、目标函数和约束条件是最优化问题数学模型的三个基本要素. 这是优化模型简单的要素.
针对生产计划制定中的具体要求, 最常用的两种优化方法是多阶段转化和变分法. 根据实际情况和两种方法的特点, 对不同的生产计划采取不同的方法.
多阶段转化是动态规划中解决多阶段决策过程最优化的一种方法. 它把困难的多阶段决策问题变换成一系列互相联系比较容易的单阶段问题, 解决了这一系列比较容易的单阶段问题, 也就解决了这困难的多阶段决策问题. 多阶段决策问题, 是指这样一类活动的过程:在它的每个阶段都需要做出决策, 并且一个阶段的决策确定以后, 常影响下一个阶段的决策, 从而影响整个过程决策的效果. 多阶段转化就是使问题要在允许的各阶段的决策范围内, 选择一个最优决策, 使整个系统在预定的标准下达到最佳的效果. 有时阶段可以用时间表示, 在各个时间段, 采用不同决策转化, 它随时间而变动, 这就有“动态”的含意. 动态规划就是要在时间的推移过程中, 在每个时间阶段选择适当的决策, 以便整个系统达到最优. 用动态规划可以解决管理中的最短路问题、装载问题、库存问题、资源分配、生产计划制定等最优化问题.
而变分法作为数学问题中求极值的一种方法, 是动态优化模型在生产计划制定中的典型应用. 变分法是泛函分析(如果变量J 对应于某一函数类中的每一个函数y (x )都有一个确定的值, 那么就称变量J 为函数y (x )的泛函, 记为
J =J [y (x )]式中, J 为泛函, 函数y 为泛函J 的宗量, x 为函数y 的自变量.) 中的一种方法[4]. 如果连续泛函J [y (x )]的改变量为∆J =J [y (x ) +δy ]-J [y (x )]式总可以表示为∆J =L [y (x ), δy ]+β(y (x ), δy ) ⋅max δy 式中, L [y (x ), δy ]是δy 的线性形式;max δy 是δy 的最大值. 当上式中的max y →0时, β(y (x ), δy ) →0, 称L [y (x ), δy ]为泛函J [y (x )]的变分, 记作δy , 写成δy =∂J [y (x ) +αδy ]=0=J y dy ∂α
式中, J y 是泛函J 对其宗量y 的偏微分, J y =∂J . 所谓生产计划这里简单的看作∂y
是到每一刻为止的累积产量. 变分法是生产计划的制定进行建立模型的数学方法, 使得在生产中获得最大的效益.
变分法是处理函数的函数的数学领域, 和处理数的函数的普通微积分相对. 变分法的关键定理是欧拉-拉格朗日方程. 它对应于泛函的临界点. 在寻找函数的极大和极小值时, 在一个解附近的微小变化的分析给出一阶的一个近似. 18世纪是变分法的草创时期, 建立了极值应满足的欧拉方程并据此解决了大量具体问题. 1964年, 钱伟长教授明确提出了引进拉格朗日成子(Lagrange multiplier)把有约束条件的变分原理化为较少(或没有)约束条件的变分原理的方法. 日本的鹫津一郎教授、中国科学院院士钱伟长教授和刘高联教授等都是这方面的世界级大师. 在生产计划制定中, 如何选择使费用最省而经济利益最大, 变分法是生产最优化最成功的方法.
1.2优化模型的实际意义
优化模型工作的一个很重要任务就是利用现有的条件规划出各种“最优”方案为现代生产计划和管理工作中的经济利益预估服务. 这里通过变分法作出的求极限值的模型被称为优化模型. 优化模型在现代企业管理中有很多的应用, 如物流、生产计划、原材料采购、劳动力的分配、广告促销、运输、成本控制、项目择优、信贷投放、企业的资产负债情况等方面的问题都可以用线性规划来解决. 基于优化模型在多方面的实际应用, 我认为各个领域的人才尤其是企业生产管理者都应在这方面有着坚实的基础, 因为它不仅提高我们自身的素质和逻辑思维能力 ,还能指导企业家提高企业的生产效率, 使企业获得最大的利益以便更好的适应市场激烈的竞争.
2优化模型的基本要素及分类
2.1优化模型的基本要素
2.1.1优化变量
一个实际的优化方案可以用一组参数(如几何参数、物理参数、工作性能参数等)来表示. 在这些参数中, 有些根据要求在优化过程中始终保持不变, 这类参数称为常量. 而另一些参量的取值则需要在优化过程中进行调整和优选, 一直处于变化的状态, 这类参数称为优化变量(或称为决策变量、设计变量). 优化变量必须是独立的参数. 例如, 如果将举行的长和宽作为优化变量, 则其面积就不是独立参数, 不能再作为优化变量了.
优化变量的全体可以用向量来表示. 包含n 个优化变量的优化问题称为n 维优化问题, 这些变量可以表示成一个n 维列向量, 即x =[x 1, x 2, , x n ]
个优化方案.
2.1.2目标函数
目标函数是用优化变量来表示的优化目标的数学表达式, 是方案好坏的评价标准, 故又称为评价函数[7]. 怒表函数通常表示为f (x ) =f (x 1, x 2, , x n )
求解优化问题的实质, 就是通过改变优化变量获得不同的目标函数值, 通过目标函数值的大小来衡量方案的优劣, 从而找出最优方案. 目标函数的最优值可能是最大值, 也可能是最小值, 在建立优化问题的数学模型时, 一般将目标函数的优化表示为极大或极小.
目标函数的极小化可以表示为f (x ) →min 或min f (x )
目标函数的极大化可以表示为f (x ) →max 或max f (x )
求目标函数f (x ) 的极大化等效于求目标函数——f (x ) 的极小化. 为规范起见, 将求目标函数的极值统一表示为求其极小值.
在优化问题中, 如果只有一个目标函数, 则其为单目标函数优化问题;如果有两个或两个以上目标函数, 则其为多目标函数优化问题. 目标函数越多, 对优化的评价越周全, 综合效果也越好, 但是问题的求解也越复杂.
一个优化向量x 确定n 维空间中的一个方案点, 每一个方案点都有一个相应的目标函数值f (x ) 与其对应;但是对于目标函数值f (x ) 的某一定值C , 却可能有无穷多个方案点与其对应. 目标函数值相等的所有方案点组成的集合称为目标函数的等值曲面. 对于二维问题, 这个点集为等值曲线;对于三维问题, 这个点集为等值曲面;对于多维问题, 这个点集为超平面.
2.1.3约束条件
T 中, x i (i =1, 2, 3, ⋯, n ) 表示第i 个优化变量. 当x i 的值都确定之后, 向量x 就表示一
约束条件是在优化中对优化变量取值的限制条件, 可以是等式约束, 也可以是不等式约束.
等式约束的形式为
h l (x ) =0, l =1, 2, ⋯,L
不等式约束更为普遍, 形式为
g m (x ) ≤0, m =1, 2, ⋯,M
式中, L 和M 分别表示等式约束和不等式约束的个数. 其中, 等式约束的个数L 必须小于优化变量的个数n , 如果相等, 则该优化问题就成了没有优化余地的既定系统. 等式约束h l (x ) =0也可以用h l (x ) ≤0和-h l (x ) ≤0两个不等式约束来代替. 不等式约束g m (x ) ≥0可以用-g m (x ) ≤0的等价形式代替.
根据约束性质的不同, 约束可以分为边界约束和性能约束两类. 边界约束直接用来限制优化变量的取值范围, 如长度变化的范围. 性能约束则是根据某种性能指标要求推导出来的限制条件, 如零件的强度条件.
2.2优化模型的分类
最优化问题的类别很多, 可以从不同角度分类. 以下是一些常见的分类和名称:
(1)按照优化约束条件的有无, 可分为无约束优化问题和有约束优化问题.
(2)按照优化变量的个数, 可分为一维优化问题和多维优化问题.
(3)按照目标函数的数目, 可分为单目标优化问题和多目标优化问题.
(4)根据目标函数与约束条件线性与否, 可分为线性规划问题和非线性规划问题.
(5)当目标函数f (x ) 为优化变量的二次函数, h l (x ) 和g m (x ) 均为线性函数时, 则该优化问题称为二次规划问题.
(6)当优化变量中有一个或一些只能取整数时, 称为整数规划;如果只能取0或1, 则称为0-1规划;如果只能取某些离散值, 则称为离散规划.
(7)当优化变量随机取值时, 称为随机规划.
(8)当目标函数为凸函数, 可行域为凸集时, 该优化问题为凸规划问题.
(9)优化目标是一个数值, 最优策略是函数, 该优化问题为动态优化问题.
3生产计划制定及其求解方法
生产计划就是企业为了生产出符合市场需要或顾客要求的产品, 所确定的在
什么时候生产, 在哪个车间生产以及如何生产的总体计划. 企业的生产计划是根据销售计划制定的, 它又是企业制定物资供应计划、设备管理计划和生产作业计划的主要依据. 生产计划工作的主要内容包括:调查和预测社会对产品的需求、核定企业的生产能力、确定目标、制定策略、选择计划方法、正确制定生产计划、库存计划、生产进度计划和计划工作程序、以及计划的实施与控制工作.
由上面优化变量、目标函数和约束条件三要素所组成的最优化问题的数学模型可以表述为:在满足约束条件的前提下, 寻求一组优化变量, 使目标函数达到最优值. 一般约苏优化问题数学模型的表达方式为:
min f (x ),
s . t
x ∈D ⊂R n
h l (x ) =0, l =1, 2, ⋯, L g m (x ) ≤0, m =1, 2, ⋯, M
式中, s . t . 为“subject to ”的缩写, 表示“受约束于”或“满足于”的意思. 当L =0时即为不等式约束优化问题;当M =0时即为等式约束优化问题;当L =0, M =0时便退化为无约束优化问题.
根据生产计划制定的特点和实际情况, 所以这里只提出针对它的两种求解方法——多阶段转化和变分法, 并且利用这两种方法对具体问题进行分析与解决. 3.1多阶段转化
多阶段转化是指将动态优化的一种, 它将多阶段决策问题转化成一系列简单的最优化问题. 首先将复杂的问题分解成相互联系的若干阶段, 每个阶段都是一个最优化子问题, 然后逐阶段进行决策(确定于下端的关联), 当所有阶段都确定了, 整个阶段的决策也就确定了. 3.1.1多阶段转化动态规划的提出
令x 为表示系统状态的n 维列矢量, 用x k 描述在时刻k (k =1, 2, ⋯,N +1) 的N 阶段系统状态. 对N 阶段决策过程, 系统状态由状态x 1通过决策u 1变换到另一个状态x 2=g (x 1, u 1) , 在这一过程中产生的效益或损益统称为收益, 记为r (x 1, u 1) ;然后再由状态x 2通过决策u 2变换到状态x 3=g (x 2, u 2) , 并产生效益r (x 2, u 2) „„最后从状态x N 通过决策u N 变换到状态x N +1=g (x N , u N ) , 并产生效益r (x N , u N ) . 要求选择该N 阶段中的N 个决策
{u 1, u 2, ⋯, u N }∈U
使下式的效益最大或最小(统称为最优效益): R N =∑r (x k , u k )
k =1N
因为N 阶段过程的最优效益只是初始状态x 1与阶段长度N 的函数, 所以可以用f N (x 1) 表示
⎧N ⎫
f N (x 1) =opt ⎨∑r (x k , u k ) ⎬
{u i }∈U ⎩k =1⎭
式中, x 1为初始状态;N 为阶段长度;opt 是优化的意思, 根据给定问题取最
*
}称为最优决策[7]. 大值max 或最小值min . 使效益取极值f N (x 1) 的决策{u k
3.1.2最优化原则
一个过程的最优决策具有这样的性质, 即无论其初始状态及其初始决策如何, 其以后诸决策对以第一个决策所形成的状态作为初始状态都必须构成最优决策.
最优化原则描述了最优控制决策的基本性质, 它建立在不变嵌入原则的基本概念上. 当求解一个特殊的最有决策问题时, 可以把原来的问题嵌入一个较容易解的类似问题之中. 如多阶段决策过程, 可以将原来的多阶段最优化问题用求解一系列但各阶段决策问题来代替. 根据最优化原则, N 阶段决策过程的总收益可以写成
R N =opt {r (x 1, u 1) +f N -1[g (x 1, u 1) ]}
u 1∈U
式中, r (x 1, u 1) 第一阶段的收益, f N -1[g (x 1, u 1)]=f N -1(x 2) 则代表初始状态x 2的后N -1个阶段的最优效益.
利用上式最有效益的式子又可写成
f N (x 1)=opt {r (x 1, u 1) +f N -1[g (x 1, u 1) ]}
u 1∈U 1
上式中右端的函数f N -1可以继续分解下去, 它对阶段数N ≥2的过程都成立. 当阶段数为N =1时, 最优效益为
f 1(x 1)=opt {r (x 1, u 1) }
u 1∈U 1
所以也可以把N 阶段决策过程的总效益写成 R N =f N -1(x 1)+r (x N , u N ) 从而最优效益可最终归结为
f N (x 1)=opt {f N -1(x 1)+r (x N , u N ) }
u N ∈U N
并一步步展开.
应用最优化原则, 一个N 阶段决策过程就处理为一个N 个单阶段决策过程的序列, 因此使这个最优化问题可以采用系统迭代的方式得到解决. 前两个式子分别是动态优化中的逆序解法和顺序解法基本公式. 3.1.3多阶段转化对生产计划的应用 3.1.3.1问题的提出
工厂制定生产计划, 要考虑设备、市场容量和收益三方面因素 某厂设备情况见表1. 生产P 1~P 7 七种产品的单价收益和加工工时见表2, 机床修理安排见表3. 市场容量见表4. 有如下限制:每种产品存货最多100件;存费每件每月0.5元;6月份末每种产品有50件存货;每天2班, 每班8小时. 盈利规定为收益减去存费, 试安排1~6月份里各个月每种产品的产量, 以使上半年盈利最多. 讨论该厂设备结构的合理性, 并作改进.
表1 设备情况
表3 停工维修安排(时间1个月)
3.1.3.2 问题分析
本问题的难点是同时考虑七种产品的优化产量, 如果只有一种产品, 运用动态规划可以方便地得出它的最优产量计划, 于是我们先将系统分解成单种产品的子问题, 再综合工时、收益进行局部调整以达产量整体最优. 但分解决策思想没有充分把握整体关系, 因此用动态规划处理才是最科学的, 其实质是逆序推算. 为判断设备结构是否合理, 我们计算了按市场容量进行生产所需的工时, 见表5.
表5 市场容量所需的工时数(小时)
3.1.3.3 基本假设
1)不考虑排队等候加工问题.
2)可同时维修的机器的种类和数目不受限制. 3)在检修期间外, 机床均能连续地正常工作. 4)“市场需求”数据来自科学的预测, 稳定可信. 1至6月的产量安排是一个多阶段决策问题, 设第n 月盈利为S n .
S n =∑C R ⋅m R . n -0. 5∑L R . n (n =1, 2, ⋯,6)
R =1
R =1
77
(1)
其中C R 为第R 种产品的单件收益, L R . n 为该产品在n 月份的存贮量, 需求
⎧6⎫ max(s ) =max ⎨∑S n ⎬
⎩n =1⎭
3.1.3.4 化模型的提出 3.1.3.4.1 模型I
本问题变量和约束条件多达几十个, 我们采用分解决策法. 基本步骤是:
(1) 单独考虑产品PR , 根据各月的市场容量, 综合收益和存费, 得出l ~6月最优产量列, 这一步动用动态规划.
(2) 把7个最优产量列合并起来, 逐月检验各项工序的工时. 遇到超时情况, 衡量产品收益的大小和工时多少, 一方面降低收益小、耗时大的产品产量, 一方面把减少的该月产量尽可能推延到下一个月去完成. 这一步是能否达到最优的关键.
在步骤2中, 把“减少的该月产量”变动到哪些月份中去, 又是一个动态规划问题. 为了计算的简便及存贮费小的目的, 我们把它尽量推延到下一月, 未必就是最优, 但这个较优的结果与最优的目标很接近, 而且实际的市场需求变动频繁.需要简单的方法与之适应, 所以这种方法是可取的.
第R 种产品在n 月内总盈利
S R . n =C R ⋅m R . n -0. 5L R . n 动态规划的逆推关系式为
x S R . n +f R . n +1) f R . n =m a (
其中, f R . n 是第R 种产品n 月后的总盈利(包括第n 月). 边界条件是L R . 6=50
运用以上方法求出P 1至P 7七种产品各自的最优产量, 见表6
表6 七种产品各自的最优产量
分析表6 1月的磨床、2月的卧式钻床工作超时.根据假设3, 最优产量应尽量接近全月工时, 即一月睹床11522时, 二月卧式钻床384工时. 以第一月为例.P 2需要0.7小时, 收益6元, 需磨0.5小时, 收益仅3元, 自然以减少产量为宜. 由此得出产量m 2. 1=888, m 7. 1=0, 留到第二月的产量是P 2=112件, P 7=100件. 得到上半年各产品的合理产量见表7.
3.1.3.4.2 模型Ⅱ
模型I 实质是一种从局部到整体逐步探索优化的过程, 模型Ⅱ提出了整体规划方案.
根据动态优化原理,
⎛6⎫
⎪s =m a x m a ⋯x m a x S m a x ∑n ⎪U 1U 2U 6
⎝U 1⎭
(2)
其中U n 是第n 月的最优产量组合.
若已知第n +1月库容量L k . n +1, 市场容量O k . n +1, 可得第n 月第k 种产品最大库存量L k . n 为:
⎧0m k , n +1=L k , n +1+O k , n +1⎪
L k , n ⎨L k , n +1+O k , n +1-m k , n +1L k , n +1+O k , n +1-100≤m k , n +1 ⎪100m k , n +1≤L k , n +1+O k , n +1-100⎩
根据式(2),可得第n +1月后的盈利与第n 月后盈利间的递推关系:
f n =m a (x S n +f n +1)
并且满足约束条件:
⎧n ⎤⎡m 1, n ⎤⎡T 磨, ⎪⎥⎢m , n ⎥⎢T ,n ⎪A ⎢2⎥⎥≤⎢垂直钻孔⎪5, 7⎢
, n ⎥⎢ , n ⎥⎨
⎥⎢⎥⎢⎪m , n n ⎥⎣7⎦⎢⎣T 刨,⎦⎪
⎪⎩m k , n ≤O k , n +L k , n
(3)
求解步骤:
(1) 对5月由3.1.3.4.2式(3)求最优, 因为6月产量会约束5月的库存量, 所以这—步确定了5月产量的限制条件.
(2) 对5月进行优化处理.
(3) 再对5、6月整体优化, 以下工作以此类推.
按以上步骤推算, 我们发现5、6月的整体优化恰是3.1.3.4.2步骤(1)、(2)作出的结果向前推算到3月, 这4个月的局部最优又共同达到了整体最优. 对l 、2月产量, 用数学软件对3.1.3.4.2中式(3)进行计算, 该结果与其后3至6月的优化产量能衔接起来. 于是, 我们用逆序算法较轻松地得出了六个月的最优安排.
模型II 的结果估于模型I 相同, 见表7, 总盈利93648元 .
分析表7.3至6月充分达到了市场需求,2月和1月也是在工时约束下的最优结果, 因此得到的确是考虑每月生产成品的最优产量安排. 3.1.3.5 模型分析
生产计划随着下列因素变化:市场需求量、产品价格, 设备结构和停工维修机床的日程安排.
市场需求和产品价格变动必然带来生产计划的重新安排, 求解模型就可得到不同形势下的最优生产计划.3至6月的生产计划并不受价格波动的影响. 在设备所能提供的工时范围内, 产量只随市场需求变动.
价格因素的作用:以一月的优化为例, 模型Ⅱ中用到的线性规划, 即求下列问题:
7
⎧
⎪max S 1=max ∑C R m k , 1
k =1
⎪⎪⎡m 1, 1⎤⎪⎢m , 1⎥⎡T 磨⎤⎪⎢⎥ ⎨A 工时⎢2⎥≤⎢^⎥
⎢⎥^, 1⎪T 刨⎥⎢⎥⎢⎣⎦⎪⎣m 7, 1⎦⎪
⎪m R , 1≤O R , 1+100⎪⎩
价格波动带来单位收益C R 的变化, 直接影响一月份的生产计划. 作定性分析得:若产品P R 的单件收益C R 增大, 则m R . n 也变大.
问题分析时, 我们列出了表5. 市场容量的工时要求, 进一步算出按市场需求量生产所需机床台数.列于表8.
表8 按市场容量生产所需机床数
分析表8可知该厂设备结构明显不合理. 表现在 (1) 卧式钻床只需2台, 可以减少一台.
(2) 镗床、刨床利用率不高(分别为32.3%和10.9%),但停工维修会导致多种成品不能生产.
于是, 我们对厂方有如下建议: (1) 卖出一台卧式钻床.
(2) 如果每月只生产成品, 重新安排检修时间, 所有机床在四月集体大修, 则其余五个月均能按市场容量生产, 这样, 总盈利达到109030元, 增加了15382元.
(3) 提高镗、刨床的利用率, 方法是生产半成品, 在不考虑半成品存货限制情况下, 重新作出停工检修安排如表9
表9 重新安排后的维修日程
这样1月至6月均按市场需求量生产, 此时, 总盈利为116630元.
(4) 因为该厂的机床利用率都不超过60%很有潜力可挖, 厂家应积极宣传促销, 扩大市场需求量, 以此获得更多的利益. 3.1.3.6 模型评价
(1) 模型I 简化了问题的处理, 是一种向最优化逼近的简便方法, 但考虑的因素较多时, 不一定能实现最优化.
(2) 模型Ⅱ为生产安排提供了科学思路, 设计了逆序推算这一探索途径, 但未能给出一般性的通用算法.
(3) 对设备结构和维修安排进行了改进, 工厂的盈利和设备的利用率大大提高.
(4) 本模型没有对工序进行优化安排, 不适于解决工序复杂, 加工时间长的问题. 3.2 变分法
最早的泛函 最简单的一类泛函表示为
J [x (t )]=⎰t t 12F (t , x , x ' )dt
被积函数F 包含自变量t ,未知函数x 及导数x ' .
t 1
(1)
泛函的极值[3] 设d (x (t ), x 0(t ))=max x (t )-x 0(t ), x ' (t )-x ' (t ), 如果对于任意
x (t ), 当d →0 时, 都有J (x (t ))≥J (x 0(t )) ,则称泛函J (x (t ))在x 0(t )取得极小值.
}
类似可以定义极大值. 极小值和极大值统称为极值.
泛函的变分 函数x (t )在x 0(t )的增量记作δx (t )=x (t )-x 0(t )称其为函数的变分, 由它引起的泛函增量记作∆J =J (x 0(t )+δx (t ))-J (x 0(t )), 如果∆J 可表示为
∆J =L (x 0(t ), δx (t ))+g (x 0(t ), δx (t )) ,其中L 是δx (t ) 的线性项, g 是δx (t )的高阶项, 称L 为泛函在x 0(t ) 的变分, 记作δJ (x 0(t )) . 同样可以定义泛函在x (t )的变分
δJ (x (t )).
若泛函J (x (t ))在x 0(t )变分存在并且取到极值, 则变分δJ (x 0(t ))=0
(2)
泛函极值的必要条件——欧拉方程[3] 讨论泛函在固定端点条件下取得极值
的必要条件. 泛函和端点条件表示为
J (x (t ))=⎰t t 12F (t , x (t ), x ' (t ))dt x (t 1)=x 1, x (t 2)=x 2
其中F 具有二阶连接偏导数.
设3.2中泛函(3)在x (t ) 取得极值, x (t )满足3.2中式(4),则
d '
(5) F x -F X =0
dt 3.2中式(5)被称为欧拉方程[7].
如果容许函数x (t )的一个端点如t =t 2不固定, 而是在一条给定的曲线
x =ψ(t )上变动, 于是端点条件表示为
(3)
(4)
x (t 1)=x 1, x (t 2)=ψ(t 2)
(t 2可变)
(6) (7) (8)
设3.2中泛函(3)在x (t ) 取得极值, x (t )满足上式(6) , 则
d '
F x -F X =0
dt
ψ' -x ' )F x F +(3.2.1问题的提出
(
'
t =t 2
=0
工厂与客户签订了一项在某时刻提交一定数量产品的合同, 在制定生产计划
时要考虑生产和贮存2种费用. 生产费用通常取决于生产率(单位时间的产量), 生产率越高费用越大; 贮存费用自然由已经生产出来的产品数量决定, 数量越多费用越大. 所谓生产计划这里简单的看作是到每一刻为止的累积产量. 它与每单位时间(如每天)的产量可以互相推算. 建模目的是寻求优化的生产计划, 使完成合同所需的总费用(生产与贮存费用之和)最小或尽可能的小. 在文献[1,2]中给出
k 2T 2k 2T 2
了数量Q ≥且生产率无限制时的生产计划. 讨论Q
4k 14k 1
时的生产计划, 以及生产率有一个上界限制的情况下的优化生产计划.
3.2.2 模型的假设
开始生产时刻记为t =0, 按照合同应在t =T 提交数量为Q 的产品. 到时刻t 为止的累积产量记作x (t ) ,即x (t )是生产计划. 设单位时间生产的产量为生产率, 记为x ' (t ) ,所以工厂单位时间的生产费用可以是生产率的函数f (x ' (t )), 而单位时间的贮存费用则与产量x (t )有关, 记为g (x (t )). 于是从t =0到t =T 时间段的总