线性规划法属于(线性规划法属于什么决策方法)

qq745048485 2024-11-14 阅读:7

定量决策方法。

线性规划法属于(线性规划法属于什么决策方法)
(图片来源网络,侵删)

目标成本预测方法:

1、定量预测法

定量预测法:是指根据历史资料以及成本与影响因素之间的数量关系,通过建立数学模型来预计推断未来成本的各种预测方法的统称。

2、趋势预测法

趋势预测法:是按时间顺序排列有关的历史成本资料,运用一定的数学模型和方法进行加工计算并预测的各类方法。趋势预测法包括简单平均法、平均法和指数平滑法等。

3、因果预测法

因果预测法:是根据成本与其相关之间的内在联系,建立数学模型并进行分析预测的各种方法。因果预测法包括本量利分析法、投入产出分析法、回归分析法等。

4、定性预测法

定性预测法:是预测者根据掌握的专业知识和丰富的实际经验,运用逻辑思维方法对未来成本进行预计推断的方法的统称。

5、成本预测的高低点法

成本预测的高低点法是指根据企业一定期间产品成本的历史资料,按照成本习性原理和y=a+bx直线方程式,选用最高业务量和最低业务量的总成本之差(△y),同两种业务量之差(△x-)进行对比,先求b的值,然后再代入原直线方程,求出a的值,从而估计推测成本发展趋势。

线性规划法是解决多变量最优决策的方法,是在各种相互关联的多变量约束条件下,解决或规划一个对象的线性目标函数最优的问题,即给与一定数量的人力、物力和资源,如何应用而能得到最大经济效益.其中目标函数是决策者要求达到目标的数学表达式,用一个极大或极小值表示.约束条件是指实现目标的能力资源和内部条件的限制因素,用一组等式或不等式来表示.

线性规划是决策系统的静态最优化数学规划方法之一.它作为经营管理决策中的数学手段,在现代决策中的应用是非常广泛的,它可以用来解决科学研究、工程设计、生产安排、军事指挥、经济规划;经营管理等各方面提出的大量问题.

线性规划法一般采取三个步骤:

第一步,建立目标函数.

第二步,加上约束条件.在建立目标函数的基础上,附加下列约束条件

第三步,求解各种待定参数的具体数值.在目标最大的前提下,根据各种待定参数的约束条件的具体限制便可找出一组最佳的组合.

在前面第3章介绍的最小二乘法是L2范数解,数据满足高斯分布。当地球物理数据d在统计学上满足双边指数分布时,数据的指数概率分布密度函数[2]为

地球物理反演教程

其中:σ为高斯分布的标准差;

为数据的平均值。

数据的指数概率分布函数[4]为

地球物理反演教程

P1(d)表示取值在(-∞,d]的概率,其中要求

。由于分布密度是对称的,求大于

的[d1,∞)的概率用关于

的对称值计算:

地球物理反演教程

而高斯概率分布密度函数[4]为

地球物理反演教程

数据的高斯概率分布函数为

地球物理反演教程

注意:概率分布密度函数和概率分布函数的区别。概率分布函数就是通常所说的概率,所有取值的概率之和为1,即100%,没有一个取值的概率超过100%。而概率密度则不同,它与标准差有关,标准差越小,概率密度越大,它不是概率,所以它的值可能会超过1。

取σ=0.01,

,在相同的σ和

条件下的概率分布密度曲线如图6.1所示,其中实线为指数分布概率密度函数,虚线为高斯分布概率密度函数。概率分布函数如图6.2所示,其中实线为指数分布概率函数,虚线为高斯分布概率函数。

从图6.2中可见,指数分布出现远离均值的数据的概率比高斯分布大。这说明指数分布容易出现个别数据较坏的情况,这时可以用L1范数解进行反演,这对数据集中极少数坏数据具有较大的韧性[1,2]。

L1范数反演可以转化为线性规划问题,然后再利用线性规划的方法求解[7,12]。线性规划问题是首先在经济和企业管理中发展起来的并已经被深入研究过的问题,目前有很多成熟的解法,其中求解线性规划问题最常用的是单纯形法。因此L1范数反演思路如下:首先将具体地球物理反演问题转化为线性规划问题,然后用单纯形法求解。

图6.1指数和高斯概率分布密度函数曲线

图6.2指数和高斯概率分布函数曲线

线性规划问题的数学模型为[2]

目标函数:

ψ=cTx=max(6.6)

约束条件:

地球物理反演教程

其中:c,x,b为列向量;c称为价值系数;x称为决策变量;A为矩阵。线性规划的优化问题是:在满足约束条件的前提下使得目标函数取极大值(有的书取极小值[7])。

式(6.6)和式(6.7)不是线性规划的标准形式。在实际应用中,各种线性规划问题都可以变换为如式(6.8)和式(6.9)的标准形式后求解。

线性规划问题的标准形式:

目标函数:

ψ=cTx=max(6.8)

约束条件:

Ax=b,x≥0(6.9)

下面仍然以一维直流电测深反演为例说明如何将地球物理反演问题转化为线性规划问题。

假设视电阻率数据满足指数分布,则可以用L1范数进行反演。

因此建立L1范数曲线拟合目标函数:

地球物理反演教程

其中:M为视电阻率曲线中数据个数;ρai为实测视电阻率;

为理论计算视电阻率。

式(6.10)写成向量形式为

地球物理反演教程

其中:d为观测电测深视电阻率数据;d*为计算机模拟的视电阻率数据,都为列向量。

采用泰勒近似:

d*≈d0+J·(m-m0)

地球物理反演教程

要想使ψ=min,则有

地球物理反演教程

式(6.13)可以作为约束条件,而目标函数可以采用模型参数的L1范数最小:

地球物理反演教程

其中:N为模型参数的个数。由于模型参数都是正的,所以有

地球物理反演教程

其中:

地球物理反演教程

这样地球物理反演问题化为线性规划问题(在满足约束条件的前提下使得目标函数取极小值):

目标函数:

L1=cTm=min(6.17)

约束条件:

地球物理反演教程

注意:这里是要使目标函数取极小而不是极大,所以不是线性规划的标准形式。需要化成标准形式来求解。下面介绍变换的四种情况:

(1)目标函数的极小问题改为极大问题。只要令ψ'=-ψ,可以把minψ变为maxψ'。

(2)如果有负的决策变量,可令x'k=-xk将其改为非负的决策变量。

(3)如果约束条件中有决策变量取值无约束,可以把它改为有约束的变量。如:令xk=x'k-x″k,其中x'k和x″k是非负的松弛变量。

(4)约束条件中的不等号改为等号。对于<或≤符号,在左端加入一个非负松弛变量;对于>或≥符号,在右端减去一个非负的剩余变量。

任何形式的线性规划数学模型都可以化为标准形式,下面用例子说明。

对于式(6.17)和式(6.18)的线性规划问题,只要令L1=-cTm=max即可。

设有一个非标准形式的线性规划问题:

地球物理反演教程

将这个问题化为标准形式的过程如下:

(1)令z'=-z;

(2)令x'2=-x2;

(3)令x3=x4-x5,其中x4≥0,x5≥0;

(4)在第(1)和第(2)个约束不等式的左端分别加入、减去松弛变量x6和剩余变量x7,其中x6≥0,x7≥0。

这时我们得到如下标准形式的线性规划问题:

地球物理反演教程

解式(6.20)的线性规划问题可以采用单纯形法求解[7,12]。限于篇幅本文不详细介绍单纯形法的具体步骤,有兴趣的读者可以参考相关的书籍。下面仅仅对单纯形法做简单的介绍。

单纯形法是美国数学家丹齐克于1947年首先提出来的。它的理论根据是:线性规划问题的可行域是n维向量空间Rn中的多面凸集,其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是:先找出一个基本可行解,对它进行鉴别,看是否是最优解;若不是,则按照一定法则转换到另一改进的基本可行解,再鉴别;若仍不是,则再转换,按此重复进行。因基本可行解的个数有限,故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。

单纯形法的一般解题步骤可归纳如下:

(1)把线性规划问题的约束方程组表达成标准型方程组,找出基本可行解作为初始基本可行解。

(2)若基本可行解不存在,即约束条件有矛盾,则问题无解。

(3)若基本可行解存在,从初始基本可行解作为起点,根据最优性条件和可行性条件,引入非基变量取代某一基变量,找出目标函数值更优的另一基本可行解。

(4)按步骤(3)进行迭代,直到对应检验数满足最优性条件(这时目标函数值不能再改善),即得到问题的最优解。

(5)若迭代过程中发现问题的目标函数值无界,则终止迭代。用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数。

数学优化中,由George Dantzig发明的单纯形法是线性规划问题的数值求解的流行技术。有一个算法与此无关,但名称类似,它是Nelder-Mead法或称下山单纯形法,由Nelder和Mead(1965)发现,这是用于优化多维无约束问题的一种数值方法,属于更一般的搜索算法的类别。这二者都使用了单纯形的概念,它是N维中的(N+1)个顶点的凸包、直线上的一个线段、平面上的一个三角形、三维空间中的一个四面体等。在何宝侃等所著《地球物理反问题中的最优化方法》一书中有下山单纯形法的详细公式及反演步骤[3]。

此法的特点是:(1)目标只有1个:最大利润、最多产量或最高效率等,即求取最大值;最低成本或最少耗费等,即求取最小值。(2)至少存在两个变量:产品品种或各种生产设备能力等。(3)约束条件多项:决策期内可用的总工时、总机器台时和可销售的各产品总量等。