规划论方法包括线性、非线性、等

规划论

综述：规划论是研究如何用最合理的方式有效地利用或调配有限的人力、物力、财力、和时间，以期更好地达到预期目标的数学方法。它是运筹学的一个分支，研究在所给定的条件下，如何按某一衡量指标来寻求计划管理工作中的最优方案。通常称必须满足的条件为“约束条件”，衡量指标为“目标函数”。包括线性规划、非线性规划、整数规划、动态规划、组合规划、随机规划、多目标规划等。在经济管理、工程设计和过程控制等方面有广泛应用。 1. 线性规划

1.1 线性规划起源

研究线性规划最早的是苏联的П.В.канторович（康脱洛维奇），1939年，他发表了《生产组织与计划中的数学方法》一书。主要讨论了机床、负荷、下料运输等问题。但他提出的问题在当时并未引起人们的注意。他自己也未能提出一个统一的求解方法。在第二次世界大战期间，由于军事运输的需要，提出线性问题的解法，美国的经济学家柯普曼（Koupman）也研究了运输问题。直到1947年，美国的G.B.Dantzig提出了求解线性规划的单纯形法，才使线性规划这门学科在理论上趋于成熟，并成功地运用到了工业、交通、农业、军事等各个领域内，使线性规划的理论与方法成为管理科学的重要内容。在当今电子技术高度发展的信息社会中，线性规划给人类在经济管理、生产管理、人才事务管理等方面发挥了巨大作用。现在对于成千上万个约束条件、成千上万个变量的线性规划问题在计算上已没有任何问题。据20世纪80年代末美国一个杂志对全美500家大公司的调查，线性规划的应用范围名列前茅，有85%的公司频繁使用线性规划。 1.2 基础理论

线性规划问题是在一组线性约束条件的限制下，求一线性目标函数最大或最小的问题。 在解决实际问题时，把问题归结成一个线性规划数学模型是很重要的一步，但往往 也是困难的一步，模型建立得是否恰当，直接影响到求解。而选适当的决策变量，是我 们建立有效模型的关键之一。 建立数学模型的步骤：

（1）分析实际问题；（2）确定决策变量；（3）找出约束条件；（4）确定目标函数；（5）整理写出数学模型。

一般线性规划问题的（数学）标准型为

maxz??cjxjj?1n?n??aijxj?bis.t?j?1?x?0,j?1,2,...,n?j

可用Lingo软件进行求解 1.3 线性规划的应用

线性规划主要应用在以下几个方面：

（1）在某一企业内部，如何配合产品的销售时间，在各部门的原料，产品的存储，分配的数量等最为合理。

（2）在某一企业生产的产品数量（或产值），如何使现有的设备，人力，原料等条件限制下，合理组织生产，使经济效益最高。

（3）在某地的交通网中，如何合理组织运输，使运费最小。

1

（4）在市场上产品的（或原料）价格变动时，对于这些变动，企业如何做出最优决策。 （5）合理下料问题，即利用某种原料下料时，如何达到既满足要求，又使原料最少。 （6）配料问题，即生产由各种原料生产的的产品时（如混合饲料等）时，如何既满足规定的质量的标准，又使产品的成本最低。

（7）库存问题，在仓库的容量及其他条件的限制下，确定库存物资的品种，数量，期限，使库存的效益最高。

（8）在投入产出问题中，引进某一目标函数，制定最优的企业（或地区）经济计划。 现以运输问题举例说明：

某商品有m个产地、n个销地，各产地的产量分别为

a1,...am ，各销地的需求量分别为

b1,...bm。若该商品由i产地运到j销地的单位运价为cij，问应该如何调运才能使总运费最

省？ 解：引入变量

xij，其取值为由i产地运往j销地的该商品数量，数学模型为

min??cijxiji?1j?1nn?n??xij?ai,i?1,...m?j?1??ns.t??xij?bj,j?1,...m?i?1?xij?0???

显然是一个线性规划问题，当然可以用单纯形法求解，也可以用Lingo软件求解

对产销平衡的运输问题，由于有以下关系式存在：

?b??aj?1ji?1nmm

其约束条件的系数矩阵相当特殊，可用比较简单的计算方法，习惯上称为表上作业法（由 康托洛维奇和希奇柯克两人独立地提出，简称康—希表上作业法）。在这里就不赘述了。 1.4 灵敏度分析

在以前讨论线性规划问题时，假定预测值。如市场条件一变，

aij,bi,cj都是常数。但实际上这些系数往往是估计值和

cj值就会变化；

aij往往是因工艺条件的改变而改变；

bi是根据资源投入后的经济效果决定的一种决策选择。因此提出这样两个问题：当这

些系数有一个或几个发生变化时，已求得的线性规划问题的最优解会有什么变化；或者 这些系数在什么范围内变化时，线性规划问题的最优解或最优基不变。可在模型推广中运用。 二 非线性规划

2.1非线性规划的起源

非线性规划是具有非线性约束条件或目标函数的数学规划，是运筹学的一个重要分支。非线

2

性规划是20世纪50年代才开始形成的一门新兴学科。70年代又得到进一步的发展。非线性规划在工程、管理、经济、科研、军事等方面都有广泛的应用，为最优设计提供了有力的工具。非线性规划研究一个 n元实函数在一组等式或不等式的约束条件下的极值问题，且目标函数和约束条件至少有一个是未知量的非线性函数。

非线性规划是20世纪50年代才开始形成的一门新兴学科。1951年H.W.库恩和A.W.塔克发表的关于最优性条件（后来称为库恩－塔克条件）的论文是非线性规划正式诞生的一个重要标志。在50年代还得出了可分离规划和二次规划的n种解法，它们大都是以G.B.丹齐克提出的解线性规划的单纯形法为基础的。50年代末到60年代末出现了许多解非线性规划问题的有效的算法，70年代又得到进一步的发展。非线性规划在工程、管理、经济、科研、军事等方面都有广泛的应用，为最优设计提供了有力的工具。20世纪80年代以来，随着计算机技术的快速发展，非线性规划方法取得了长足进步，在信赖域法、稀疏拟牛顿法、并行计算、内点法和有限存储法等领域取得了丰硕的成果。 2.2非线性规划的算法

对于一个实际问题，在把它归结成非线性规划问题时，一般要注意如下几点：

（i）确定供选方案：首先要收集同问题有关的资料和数据，在全面熟悉问题的基础上，确认什么是问题的可供选择的方案，并用一组变量来表示它们。

（ii）提出追求目标：经过资料分析，根据实际需要和可能，提出要追求极小化或极大化的目标。并且，运用各种科学和技术原理，把它表示成数学关系式。

（iii）给出价值标准：在提出要追求的目标之后，要确立所考虑目标的“好”或 “坏”的价值标准，并用某种数量形式来描述它。 （iv）寻求限制条件：由于所追求的目标一般都要在一定的条件下取得极小化或极大化效果，因此还需要寻找出问题的所有限制条件，这些条件通常用变量之间的一些不等式或等式来表示。

0-1规划模型

例 某企业有n个项目可供选择投资，并且至少要对其中一个项目投资。已知该企业拥有总

ab资金A元，投资于第i（i?1,...,n）个 , i个项目需花资金ij元，并预计可收益i元。试

选择最佳投资方案。

解 设投资决策变量为

?1,决定投资第i个项目xi??，i?1,...n?0，决定不投资第i个项目

则投资总额为

?axii?1ni，投资总收益为

?bxii?1nni。因为该公司至少要对一个项目投资，并且

总的投资金额不能超过总资金A ，故有限制条件

0??aixi?Ai?1

另外，由于

xi(i?1,...,n)只取值 0 或1，所以还有

xi(1?xi)?0,i?1,...,n

最佳投资方案应是投资额最小而总收益最大的方案，所以这个最佳投资决策问题归

3

结为总资金以及决策变量（取0 或1）的限制条件下，极大化总收益和总投资之比。因 此，其数学模型为：

maxQ??bxi?1ni?1nii?axni?1iis..0t??aixi?Axi(1?xi)?0,i?1,...,n

上面例题是在一组等式或不等式的约束下，求一个函数的最大值（或最小值）问

题，其中至少有一个非线性函数，这类问题称之为非线性规划问题。可概括为一般形式

minf(x)

s..thj(x)?0,j?1,...,qgi(x)?0,i?1,...p

Tg(i?1,...,p)和x?[x,...,x]1n其中称为模型（NP）的决策变量，f 称为目标函数，ihj(j?1,...,q)束,

称为约束函数。另外，

gi(x)?0(i?1,...p) 称为等式约

hj(x)?0(j?1,...,q)称为不等式的约束。

1.3 非线性规划的Matlab 解法

Matlab 中非线性规划的数学模型写成以下形式

minf(x)?Ax?B?Aeq.x?Beq???C(x)?0??Ceq(x)?0

其中 f (x)是标量函数，A, B, Aeq, Beq是相应维数的矩阵和向量，C(x),Ceq(x)是非

线性向量函数。 Matlab 中的命令是

X=FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON,OPTIONS)

它的返回值是向量x，其中 FUN 是用M 文件定义的函数 f (x)；X0是x的初始值； A,B,Aeq,Beq 定义了线性约束 A* X ≤ B, Aeq * X = Beq ，如果没有线性约束，则 A=[],B=[],Aeq=[],Beq=[]；LB 和UB 是变量x 的下界和上界，如果上界和下界没有约 束，则LB=[]，UB=[]，如果x 无下界，则LB 的各分量都为-inf，如果x 无上界，则UB 的各分量都为 inf；NONLCON 是用M 文件定义的非线性向量函数C(x),Ceq(x)；OPTIONS 定义了优化参数，可以使用Matlab 缺省的参数设置。 计算下面函数在区间(0，1)内的最小值。 解：

4

f(x)?x3?cosx?xlogxex

[x,fval,exitflag,output]

=fminbnd('(x^3+cos(x)+x*log(x))/exp(x)',0,1) x =

0.5223 fval =

0.3974 exitflag = 1 output =

iterations: 9 funcCount: 9

algorithm: 'golden section search, parabolic interpolation'

2.3 非线性规划问题求解

(n)非线性规划分为两大类：1 无约束非线性规划 表达式为minf(x) x?E

2 有约束非线性规划 表达式为

minf(x),?gi(x)?0,(i?1,2,...,m)??hj(x)?0,(j?1,2,...,l)?n?x?R

2.3.1 无约束非线性规划问题求解

2.3.1.1 凸函数概念：设 f (x)为定义在 n 维欧氏空间E对任何实数

α (0 <α <1)以及R中的任意两点x和x(1)(2)(n)中某个凸集 R 上的函数，若

，恒有

f(?x(1)?(1??)x(2))??f(x(1))?(1??)f(x(2))

则称 f (x)为定义在R上的凸函数。

(1)(2)xx若对每一个α (0 <α <1)和 ≠∈R恒有

f(?x(1)?(1??)x(2))??f(x(1))?(1??)f(x(2))

则称 f (x)为定义在R上的严格凸函数。

考虑非线性规划

?minf(x),x?R??R?{x/gj(x)?0,j?1,2,...,l}

5

假定其中 f (x)为凸函数，

gj(x)(j?1,2,...,l)为凸函数，这样的非线性规划称为凸规划。

可以证明，凸规划的可行域为凸集，其局部最优解即为全局最优解，而且其最优

解的集合形成一个凸集。当凸规划的目标函数 f (x)为严格凸函数时，其最优解必定唯 一（假定最优解存在）

2.3.1.2无约束非线性规划问题求解

直接法：一维搜索法（0.618法），爬山法，座标轮换法 解析法：梯度法，牛顿法，共轭梯度法

现只介绍一维搜索法（0.618法），牛顿法两种。 （1）一维搜索法（0.618法）

当用迭代法求函数的极小点时，常常用到一维搜索，即沿某一已知方向求目标函数

的极小点。一维搜索的方法很多，常用的有：（1）试探法（“成功—失败”，斐波那契法， 0.618 法等）；（2）插值法（抛物线插值法，三次插值法等）；（3）微积分中的求根法（切 线法，二分法等）。 （2）考虑一维极小化问题

minf(t)a?t?b

若 f (t)是[a,b]区间上的下单峰函数，我们介绍通过不断地缩短[a,b]的长度，来 搜索得（2）的近似最优解的两个方法。为了缩短区间[a,b]，逐步搜索得（2）的最优解t*的近似值，我们可以采用以下途径：在[a,b]中任取两个关于[a,b]是对称的点 1 t 和2 t （不妨设

t2?t1，并把它们叫做搜索点），计算f(t1) 和f(t2) 并比较它们的大小。对于单峰

??f(x)???(x)??1?4x?2x?*t?a,tf(t)f(t)??11212< 1，则必有???函数，若，因而?f(x)?? 是???f(x)???1?2x1?2x2???(x)??2?*t??t2,b?f(t)f(t)?t,b? 是缩短了的单2则有1< 缩短了的单峰区间；若t* ∈ t b ，故2峰区间；若

f?t2??f?t1?，则

?a,t1? 和?t2,b? 都是缩短了的单峰。因此通过两个搜索点

处目标函数值大小的比较，总可以获得缩短了的单峰区间。对于新的单峰区间重复上述做法，

显然又可获得更短的单峰区间。如此进行，在单峰区间缩短到充分小时，我们可以取最后的搜索点作为（2）最优解的近似值。 Fibonacci 法

如用Fn 表示计算n 个函数值能缩短为单位长区间的最大原区间长度，可推出Fn 满 足关系F = F =1

Fn?Fn?2?Fn?1,n?2,3.....

数列{ F n } 称为Fibonacci 数列，F n 称为第n 个Fibonacci 数，相邻两个Fibonacci 数之 比

Fn?1称为 Fibonacci 分数。 Fn 6

当用斐波那契法以n 个探索点来缩短某一区间时，区间长度的第一次缩短率为

Fn?1，，其Fn后各次分别为?a0,b0?，

Fn?3Ft，……,，1。，若1和t2 (t1 < t2) 是单峰区间[a,b] Fn?2F2中第1 个和第2 个探索点的话，那么应有比例关系

t1?aFn?1t2?aFn?2?,?b?aFb?aFn n

从而：

t1?a?Fn?1F(b?a),t2?a?n?2(b?a)FnFn (3)

它们关于[a,b]确是对称的点。

如果要求经过一系列探索点搜索之后，使最后的探索点和最优解之间的距离不超 过精度δ > 0，这就要求最后区间的长度不超过δ ，即

b?a??Fn (4)

据此，我们应按照预先给定的精度δ ，确定使（4）成立的最小整数n 作为搜索次数， 直到进行到第n 个探索点时停止。

用上述不断缩短函数 f (t)的单峰区间[a,b]的办法，来求得问题（2）的近似解， 是Kiefer(1953 年)提出的，叫做Finbonacci 法，具体步骤如下：

k?n?11o 选取初始数据，确定单峰区间f1?f(t1),f2?f?t2? ，给出搜索精度δ > 0，由（4）

if确定搜索次数n 。

2o k = 1,a =a0 ,b = b0 ，计算最初两个搜索点，按（3）计算 和t1, t2。 while

k?n?1f1?f(t1),f2?f?t2?

f1?f(t1)a?t2;t2?t1;t1?a?If else

F(n?1?k)(b?a)F?n?k?

b?t1;t1?t2;t2?b?

F(n?1?k)(a?b)F?n?k?

7

end k=k+1 end

4o 当进行至k = n ?1时，

t1?t2?1(a?b)2

这就无法借比较函数值f?t1? 和f?t2? 的大小确定最终区间，为此，取

1?t?(a?b)2?2??t1?a?(1??)(b?a)?2

其中ε 为任意小的数。在t1 和t2 这两点中，以函数值较小者为近似极小点，相应的函数

值为近似极小值。并得最终区间[a , t1 ] 或[t 2 , b ] 。

由上述分析可知，斐波那契法使用对称搜索的方法，逐步缩短所考察的区间，它能 以尽量少的函数求值次数，达到预定的某一缩短率。

例 3 试用斐波那契法求函数 f (t) = t ? t + 2的近似极小点，要求缩短后的区间 不大于区间[?1,3]的 0.08 倍。 程序留作习题。 2.1.2 0.618法

若ω > 0，满足比例关系

2?1?1???

称之为黄金分割数，其值为 0.6180339887 。

黄金分割数ω 和Fibonacci 分数之间有着重要的关系

??limn??Fn?1Fn。

现用不变的区间缩短率 0.618，代替斐波那契法每次不同的缩短率，就得到了黄金

分割法（0.618 法）。这个方法可以看成是斐波那契法的近似，实现起来比较容易，效果 也相当好，因而易于为人们所接受。

用 0.618 法求解，从第2 个探索点开始每增加一个探索点作一轮迭代以后，原单 峰区间要缩短 0.618 倍。计算n个探索点的函数值可以把原区间[a0,b0] 连续缩短n ?1 次，因为每次的缩短率均为μ ，故最后的区间长度为

n?1(b?a)?0 0

这就是说，当已知缩短的相对精度为δ 时，可用下式计算探索点个数n ：

?n?1??

当然，也可以不预先计算探索点的数目n ，而在计算过程中逐次加以判断，看是否已满

足了提出的精度要求。

0.618 法是一种等速对称进行试探的方法，每次的探索点均取在区间长度的0.618

8

倍和0.382 倍处。 2.2 二次插值法

对极小化问题（2），当 f(t)在[a,b]上连续时，可以考虑用多项式插值来进行一

维搜索。它的基本思想是：在搜索区间中，不断用低次（通常不超过三次）多项式来近 似目标函数，并逐步用插值多项式的极小点来逼近（2）的最优解。 2.3 无约束极值问题的解法 无约束极值问题可表述为

minf?x?,x?E(n) （5）

求解问题（5）的迭代法大体上分为两点：一是用到函数的一阶导数或二阶导数， 称为解析法。另一是仅用到函数值，称为直接法。 2.3.1 解析法

2.3.1.1 梯度法（最速下降法） 对基本迭代格式

xk?1?xk?tkpk （6）

我们总是考虑从点xk出发沿哪一个方向 pk ，使目标函数 f 下降得最快。微积分的知识 告诉我们，点xk的负梯度方向

pk=-?f?xk?,k

k是从点x出发使 f 下降最快的方向。为此，称负梯度方向??f (x)为 f 在点xk处的 最速下降方向。

按基本迭代格式（6），每一轮从点x出发沿最速下降方向??f （x)作一维搜索，

kk来建立求解无约束极值问题的方法，称之为最速下降法。

这个方法的特点是，每轮的搜索方向都是目标函数在当前点下降最快的方向。同

k时，用?f (x) = 0或x??作为停止条件。其具体步骤如下：

k1°选取初始数据。选取初始点x0，给定终止误差，令k := 0。

2°求梯度向量。计算?f (xk )， 若 ?f (x ) ≤ ε ，停止迭代，输出xk。否则， 进行3°。 3° 构造负梯度方向。取

kkpk= ??f (xk) .

(三)最速下降法应用举例

例 1

(1)T2 给定初始点X?(0,0) minf(x)?x1?x2?2x12?2x1x2?x2??f(x)???(x)??1?4x?2x?112???解：目标函数 f (x)的梯度?f(x)?? ???f(x)???1?2x1?2x2???(x)??2?

9

?1??f(x(1))???令搜索方向d(1)???f(x(1))再从x(1)出发，d(1)方向作一维寻优，令

??1?步长变量为l ，最优步长为1 l ，则有x(1)0?1????????d(1)?????01????????故

f(x)?f(x(1)??d(1))?(??)???2(??)2?2(??)???2??2?2??1(?)

(2)(1)(1)0?1?1(2)???????x令?1(?)?2??2?0可得?1?1 x?x??1d?? 求出点之011??????后，与上类似地，进行第二次迭代：?f(x令步长变量为l ，最优步长为l2 ，则有x(2)?11(2)(2)??令=d???f(x))=??1???1??

(2)?11??1??d(2)???1??????1???????1??

故

f(x)?f(x(2)??d(2))?(??1)?(??1)?2(??1)2?2(??1)(??1)?(??1)2?5?2?2??1??2(?)

令?2(?)?10??2?0可得 ?2?1(3)2)((2)?111?0.8??????? x?x??2d?? 111.2??????550.2(3)?f(x(3))???0.2?? 此时所达到的精度?f(x)?0.2828

本题最优解 x???1.5??,f(x)??1.25

*?1*4° 进行一维搜索。求tk，使得

f(xk?tkpk)?minf(xk?tkpk)t?0

令xk?1?xk?tkpk,k:?k?1,转 2°。 例4 用最速下降法求解无约束非线性规划问题

2minf(x)?x12?25x2

其中x?(x1,x2)T，要求选取初始点x?(2,2)。

解V?{v1,v1,v3,v4,v5},E?{(v1,,v1,),(v3,v4),(v3,v5),(v1,,v5),(v5,v5)} 编写 M 文件detaf.m，定义函数 f (x)及其梯度列向量如下 function [f,df]=detaf(x); f=x(1)^2+25*x(2)^2; df=[2*x(1) 50*x(2)];

（ii）编写主程序文件zuisu.m如下： clc

x=[2;2];

[f0,g]=detaf(x);

0T 10

while norm(g)>0.000001 p=-g/norm(g);

t=1.0;f=detaf(x+t*p); while f>f0 t=t/2;

f=detaf(x+t*p); end

x=x+t*p;

[f0,g]=detaf(x); end x,f0

11

本文来源：https://www.bwwdw.com/article/wua5.html