五千年(敝帚自珍)

主题:【整理】管理科学简单概念介绍1 -- wqnsihs

共:💬108 🌺498
全看分页树展 · 主题 跟帖
家园 【整理】管理科学简单概念介绍3

三、管理科学经常使用的最优化方法

从数学意义上说,最优化方法是一种求极值的方法,即在一组约束为等式或不等式的条件下,使系统的目标函数达到极值,即最大值或最小值。

从经济意义上说,是在一定的人力、物力和财力资源条件下,使经济效果达到最大(如产值、利润),或者在完成规定的生产或经济任务下,使投入的人力、物力和财力等资源为最少。

在微积分出现以前,已有许多学者开始研究用数学方法解决最优化问题。例如阿基米德证明:给定周长,圆所包围的面积为最大。这就是欧洲古代城堡几乎都建成圆形的原因。但是最优化方法真正形成为科学方法则在17世纪以后。17世纪,I.牛顿和G.W.莱布尼茨在他们所创建的微积分中,提出求解具有多个自变量的实值函数的最大值和最小值的方法。以后又进一步讨论具有未知函数的函数极值,从而形成变分法。这一时期的最优化方法可以称为古典最优化方法。

第二次世界大战前后,由于军事上的需要和科学技术和生产的迅速发展,许多实际的最优化问题已经无法用古典方法来解决,这就促进了近代最优化方法的产生。近代最优化方法的形成和发展过程中最重要的事件有:以苏联康托罗维奇和美国丹齐克为代表的线性规划;以美国库恩和塔克尔为代表的非线性规划;以美国贝尔曼为代表的动态规划;以苏联庞特里亚金为代表的极大值原理等。这些方法后来都形成体系,成为近代很活跃的学科,对促进运筹学、控制论和管理科学等学科的发展起了重要作用。

1、工作步骤

用最优化方法解决实际问题,一般可经过下列步骤:

(1)、提出最优化问题,收集有关数据和资料;

(2)、建立最优化问题的数学模型,确定变量,列出目标函数

和约束条件;

(3)、分析模型,选择合适的最优化方法;

(4)、求解,一般通过编制程序,用计算机求最优解;

(5)、最优解的检验和实施。

上述 5个步骤中的工作相互支持和相互约束,在实践中常常是反复交叉进行。

2、模型的基本要素

最优化模型一般包括变量、约束条件和目标函数三要素:

(1)、变量:指最优化问题中待确定的某些量。变量可用x=(x1,x2…,xn)t表示。

(2)、约束条件:指在求最优解时对变量的某些限制,包括技术上的约束、资源上的约束和时间上的约束等。列出的约束条件越接近实际系统,则所求得的系统最优解也就越接近实际最优解。约束条件可用 gi(x)≤0表示1=1,2,…,m,m 表示约束条件数;或 x∈R(R表示可行集合)。

(3)、目标函数:最优化有一定的评价标准。目标函数就是这种标准的数学描述,一般可用f(x)来表示,即f(x)=f(x1,x2,…,xn)。要求目标函数为最大时可写成maxx∈Rf(x);要求最小时则可写成minx∈Rf(x)。目标函数可以是系统功能的函数或费用的函数。它必须在满足规定的约束条件下达到最大或最小。

3、问题的分类

最优化问题根据其中的变量、约束、目标、问题性质、时间因素和函数关系等不同情况,可分成多种类型。

4、最优化方法

不同类型的最优化问题可以有不同的最优化方法,即使同一类型的问题也可有多种最优化方法。反之,某些最优化方法可适用于不同类型的模型。最优化问题的求解方法一般可以分成解析法、直接法、数值计算法和其他方法。

(1)、解析法

这种方法只适用于目标函数和约束条件有明显的解析表达式的情况。求解方法是:先求出最优的必要条件,得到一组方程或不等式,再求解这组方程或不等式,一般是用求导数的方法或变分法求出必要条件,通过必要条件将问题简化,因此也称间接法。

(2)、直接法

当目标函数较为复杂或者不能用变量显函数描述时,无法用解析法求必要条件。此时可采用直接搜索的方法经过若干次迭代搜索到最优点。这种方法常常根据经验或通过试验得到所需结果。对于一维搜索(单变量极值问题),主要用消去法或多项式插值

法;对于多维搜索问题(多变量极值问题)主要应用爬山法。

(3)、数值计算法

这种方法也是一种直接法。它以梯度法为基础,所以是一种解析与数值计算相结合的方法。

(4)、其他方法

如网络最优化方法等。

根据函数的解析性质,还可以对各种方法作进一步分类。例如,如果目标函数和约束条件都是线性的,就形成线性规划。线性规划有专门的解法,诸如单纯形法、解乘数法、椭球法和卡马卡法等。当目标或约束中有一非线性函数时,就形成非线性规划。当目标是二次的,而约束是线性时,则称为二次规划。二次规划的理论和方法都较成熟。如果目标函数具有一些函数的平方和的形式,则有专门求解平方和问题的优化方法。目标函数具有多项式形式时,可形成一类几何规划。

5、最优解的概念

最优化问题的解一般称为最优解。如果只考察约束集合中某一局部范围内的优劣情况,则解称为局部最优解。如果是考察整个约束集合中的情况,则解称为总体最优解。

对于不同优化问题,最优解有不同的含意,因而还有专用的名称。例如,在对策论和数理经济模型中称为平衡解;在控制问题中称为最优控制或极值控制;在多目标决策问题中称为非劣解(又称帕雷托最优解或有效解)。

在解决实际问题时情况错综复杂,有时这种理想的最优解不易求得,或者需要付出较大的代价,因而对解只要求能满足一定限度范围内的条件,不一定过分强调最优。

50年代初,在运筹学发展的早期就有人提出次优化的概念及其相应的次优解。提出这些概念的背景是:最优化模型的建立本身就只是一种近似,因为实际问题中存在的某些因素,尤其是一些非定量因素很难在一个模型中全部加以考虑。另一方面,还缺乏一些求解较为复杂模型的有效方法。

1961年H.A.西蒙进一步提出满意解的概念,即只要决策者对解满意即可。

6、最优化方法的应用

最优化一般可以分为最优设计、最优计划、最优管理和最优控制等四个方面。

(1)、最优设计

世界各国工程技术界,尤其是飞机、造船、机械、建筑等部门都已广泛应用最优化方法于设计中,从各种设计参数的优选到最佳结构形状的选取等,结合有限元方法已使许多设计优化问题得到解决。一个新的发展动向是最优设计和计算机辅助设计相结合。电子线路的最优设计是另一个应用最优化方法的重要领域。配方配比的优选方面在化工、橡胶、塑料等工业部门都得到成功的应用,并向计算机辅助搜索最佳配方、配比方向发展。

(2)、最优计划

现代国民经济或部门经济的计划,直至企业的发展规划和年度生产计划,尤其是农业规划、种植计划、能源规划和其他资源、环境和生态规划的制订,都已开始应用最优化方法。一个重要的发展趋势是帮助领导部门进行各种优化决策。

(3)、最优管理

一般在日常生产计划的制订、调度和运行中都可应用最优化方法。随着管理信息系统和决策支持系统的建立和使用,使最优管理得到迅速的发展。

(4)、最优控制

主要用于对各种控制系统的优化。例如,导弹系统的最优控制,能保证用最少燃料完成飞行任务,用最短时间达到目标;再如飞机、船舶、电力系统等的最优控制,化工、冶金等工厂的最佳工况的控制。计算机接口装置不断完善和优化方法的进一步发展,还为计算机在线生产控制创造了有利条件。最优控制的对象也将从对机械、电气、化工等硬系统的控制转向对生态、环境以至社会经济系统的控制。

7、线性规划

研究线性约束条件下线性目标函数的极值问题,是运筹学的一个重要分支,广泛应用于军事作战、经济分析、经营管理和工程技术等方面。

(1)、简史

法国数学家傅里叶和 C.瓦莱-普森分别于1832和1911年独立地提出线性规划的想法,但未引起注意。1939年苏联数学家康托罗维奇在《生产组织与计划中的数学方法》一书中提出线性规划问题,也未引起重视。1947年美国数学家丹齐克提出线性规划的一般数学模型和求解线性规划问题的通用方法----单纯形法,为这门学科奠定了基础。1947年美国数学家J.von诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域,扩大了它的应用范围和解题能力。

1951年美国经济学家T.C.库普曼斯把线性规划应用到经济领域,为此与康托罗维奇一起获1975年诺贝尔经济学奖。50年代后对线性规划进行大量的理论研究,并涌现出一大批新的算法。例如,1954年C.莱姆基提出对偶单纯形法,1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题,1956年A.塔克提出互补松弛定理,1960年G.B.丹齐克和P.沃尔夫提出分解算法等。线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。由于数字电子计算机的发展,出现了许多线性规划软件,如MPSX,OPHEIE,UMPIRE等,可以很方便地求解几千个变量的线性规划问题。1979年苏联数学家哈奇扬提出解线性规划问题的椭球算法,并证明它是多项式时间算法。1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。现已形成线性规划多项式算法理论。

50年代后线性规划的应用范围不断扩大。

(2)、模型

要对实际规划问题作定量分析,必须先加以抽象,建立数学模型。在建立线性规划模型时,需要有关的专业知识,并要有一定的经验和技巧。建立线性规划模型包括:

①明确问题的目标和划定决策实施的范围(包括时间界限),并将目标表达成决策变量的线性函数,称为目标函数。

②选定决策变量和参数。决策变量就是待决定的问题的未知量,一组决策变量的取值即构成一个规划方案。决策变量的选定往往需要对问题进行仔细的分析。

③建立约束条件。问题的各种限制条件称为约束条件。每一个约束条件均表达成决策变量的线性函数应满足的等式或不等式。约束条件往往不止一个,通常表达成一组线性等式或不等式。线性规划问题就是在决策变量满足一组约束条件的情况下使目标函数达到极大值或极小值。

一般线性规划模型的形式请上网查看。

(3)、 算法

求解线性规划问题的基本方法是单纯形法,现在已有单纯形法的标准软件,可在电子计算机上求解约束条件和决策变量数达 10000个以上的线性规划问题。为了提高解题速度,又有改进单纯形法、对偶单纯形法、原始对偶方法、分解算法和各种多项式时间算法。对于只有两个变量的简单的线性规划问题,也可采用图解法求解。这种方法仅适用于只有两个变量的线性规划问题。它的特点是直观而易于理解,但实用价值不大。通过图解法求解可以理解线性规划的一些基本概念。

(4)、应用

在工业、农业、商业、行政、军事、公用事业等各个领域,存在着大量的线性规划问题。有些规划问题本身是非线性的,但往往可以通过改变标度或采用分段线性化等方法,转化为线性规划模型。

用线性规划求解的典型问题有运输问题、生产计划问题、配套生产问题、下料和配料问题等。

①运输问题:某产品有N个产地,M个销地。已知各产地的产量和各销地的销量,以及各产地到各销地的单位运价,问如何安排各产地到各销地的运量,使总的运费为最少?

②生产计划问题:用M种资源生产N种产品。已知各种产品每生产一单位可得的利润和所需的各种资源的数,以及各种资源的限额。问如何计划各种产品的生产量,使总的利润为最大?

③配套生产问题:用若干台机床加工某种产品的各种零件。已知各机床加工不同零件的效率。问如何分配各机床的任务,在零件配套的前提下使一个生产周期内的产量最高?

④下料问题:将一批固定规格的条材或板材裁剪成具有规定尺寸的若干种毛坯,并已设计出若干种下料方式。问采用哪种下料方式,能使各种毛坯满足所需数量,又使总的用料最省?

⑤混合配料问题:用M种原料配制某些含有N种成分的产品。已知各种成分在各种原料中的单位含量,以及各种原料的单价和限额。问怎样混合调配,在满足产量要求和产品所含各种成分的要求下使成本为最低?


本帖一共被 1 帖 引用 (帖内工具实现)
全看分页树展 · 主题 跟帖


有趣有益,互惠互利;开阔视野,博采众长。
虚拟的网络,真实的人。天南地北客,相逢皆朋友

Copyright © cchere 西西河