1. 非线性规划
我们讨论过线性规划,其目标函数和约束条件都是自变量的线性函数。如果目标函数是非线性函数或至少有一个约束条件是非线性等式(不等式),则这一类数学规划就称为非线性规划。在科学管理和其他领域中，很多实际问题可以归结为线性规划，但还有另一些问题属于非线性规划。由于非线性规划含有深刻的背景和丰富的内容，已发展为运筹学的重要分支，并且在最优设计,管理科学,风险管理,系统控制,求解均衡模型,以及数据拟合等领域得到越来越广泛的应用。
非线性规划的研究始于三十年代末,是由W.卡鲁什首次进行的，40年代后期进入系统研究，1951年H.W.库恩和A.W.塔克提出带约束条件非线性规划最优化的判别条件,从而奠定了非线性规划的理论基础,后来在理论研究和实用算法方面都有很大的发展。
非线性规划求解方法可分为无约束问题和带约束问题来讨论，前者实际上就是多元函数的极值问题，是后一问题的基础。无约束问题的求解方法有最陡下降法、共轭梯度法、变尺度法和鲍威尔直接法等。关于带约束非线性规划的情况比较复杂，因为在迭代过程中除了要使目标函数下降外，还要考虑近似解的可行性。总的原则是设法将约束问题化为无约束问题；把非线性问题化为线性问题从而使复杂问题简单化。求解方法有可行方向法、约束集法、制约函数法、简约梯度法、约束变尺度法、二次规划法等。虽然这些方法都有较好的效果，但是尚未找到可以用于解决所有非线性规划的统一算法。
1.1 非线性规划举例
[库存管理问题] 考虑首都名酒专卖商店关于啤酒库存的年管理策略。假设该商店啤酒的年销售量为A 箱,每箱啤酒的平均库存成本为H 元,每次订货成本都为F 元。如果补货方式是可以在瞬间完成的,那么为了降低年库存管理费用,商店必须决定每年需要定多少次货,以及每次订货量。
我们以Q 表示每次定货数量,那么年定货次数可以为
Q A ,年订货成本为Q
A
F ?。由于平均库存量为
2Q ,所以,年持有成本为2
Q
H ?,年库存成本可以表示为: Q H
Q A F Q C ?+?
=2
)( 将它表示为数学规划问题:
min Q H Q A F Q C ?+?
=2
)( ..t s 0≥Q
其中Q 为决策变量,因为目标函数是非线性的,约束条件是非负约束,所以这是带约束条件的非线性规划问题。
[数据拟合问题] 假设一年期国债利率在市场中的波动符合下述模型
εααα+++=---332211n n n n R R R R
其中n R 表示一年期国债利率在周期n 开始时的利率,误差ε服从),0(2
σN 。利率的历史观察数据为:
表1.9:一年期国债利率历史样本数据 1 2
3
4
5
6
7
8
9
10
11
12
13
4.28 4.14 3.85 4.07 4.18 4.66 4.51 4.54 4.59 4.48 4.47 4.47 4.72
利用最小二乘法估算3,2,1,=i i α
由于在周期t 回归误差的平方为 23322112)(---++-=t t t t t R R R R e ααα,N t ,...5,4=
比如说,当4=t 时,2
32124)28.414.485.307.4(ααα++-=e
总回归误差为
∑==N
t t e e 4
22
我们需要求解下述数学规划问题:
min ∑=---++-=N
t t t t t R R R R e 4
23322112
)(ααα
..t s 3,2,1),,(=+∞-∞∈i i α
其中i α3,2,1,=i 为决策变量,显然,这是无约束非线性规划问题。
[投资组合管理问题] 假设首都基金管理公司拥有大批量股票S ,并且希望在未来的N 天中将其全部卖出。股票S 在未来N 天的总期望价值为:
∑==N
t t t q p S V 1
)(
其中,N t q t ,...,2,1,=是基金公司在第t 日卖出股票S 的数量,N t p t ,...,2,1,=是在t 日股票S 的平均价格。同时,我们假设价格t p 具有下述动态特性:
N t q p p t t t ,...,2,1,1=?+=-α
那么基金管理公司应当如何确定股票S 每日卖出数量?
很显然,不同的卖出方案,基金管理公司获得的收益是不同的。所以目标函数是最大化股票S 的总期望价值。约束条件为N 日内卖出数量之和应当等于总持有量S ,价格动态特征,
以及每日卖出数量大于等于零。
我们可以把它表示为最优化问题:
max ∑==N
t t t q p S V 1
)(
..t s ???
?
?
??
=≥=+==-=∑N t q N t q p p S q t t t t N
t t ,...,2,1,0,...,3,2,11
α
其中t q ,N t ,...,2,1=,这是目标函数为非线性函数,约束条件是线性等式约束条件的非线性规划问题。
[生产管理问题] 首都电器制造厂生产二款电视机,A 和B 。已知电视机A 每月最大的销售量为500台,电视机B 每月的最大销售量为400台。工厂采用随销售量增加而递减销售价格的定价方式对电视机进行定价,那么单台电视机的利润是随着销售量的增加而递减。
我们分别以A X 和B X 表示电视机A 和B 的月销售量,那么电视机A 的销售收入可以表示为:
2
)150(300A A X X -
它说明第一部A 型电视机的利润为300元,最后一部(第500)A 型电视机的利润为150元。
电视机B 的销售收入可以表示为:
2
)400100(200B B X X -
电视机的生产受到下下述条件限制:
)1(
装配工时限制:每月最多可供使用的工时是1200小时,而装配一台电视机A 需要2工时,装配一台电视机B 需要1工时。
)2( 机器加工能力限制:每日最多可供使用的机时是1350小时,加工一台电视机A 需
要1机时,加工一台电视机B 需要3机时。
那么,如何决定每种电视机的月产量,使月销售收入最大。
如果我们以二款电视机的月销售收入之和作为目标函数,则电视机生产管理的最优化问题被表示为:
max 2
225.02003.0300B B A A X X X X S -+-=
..t s ?????
???
?≥≤≤≤+≤+0
,4005001350312002B A B A B A B A X X X X X X X X 这是目标函数为二次可分离函数,约束条件为线性不等式的非线性规划问题。
1.2 非线性规划模型
现在,我们非线性规划问题的应用进行归纳,建立非线性规划通用数学模型。非线性规划的数学模型可表示为:
)(min x f X
x ∈
)1.1(
其中:R R f n
→:是具有n 个自变量的连续(通常存在一阶导数)函数;n
R X ?,是n
R 的
子集合。通常称X 为非线性规划问题)1.1(的可行域,如果n
R X =,则非线性规划问题)1.1(就变为无约束条件的非线性规划问题;如果n
R X ?,则非线性规划问题)1.1(为带约束非线性规划问题。
如果点X x ∈,则称x 为可行点。称)(x f 为非线性规划问题)1.1(的目标函数,使)
(x f 在可行域X 上达到最小值的点*
x 为最优解(极小点),对应的目标函数值)(*
x f 为最优值
(极小值)。如果)(x f 是线性函数并且X 是n 维空间中的单纯形,非线性规划)1.1(就变成了线性规划问题。我们通常将非线性规划和线性规划区别对待,非线性规划的求解方法比线性规划复杂许多。
为了方便讨论,我们定义带约束条件的非线性规划的标准模型如下:
min )(x f
..t s .,...,2,1,0)(,...,2,1,0)(??
?=≤==s
j x g m
i x h j i )2.1(
其中:R R h n i →:和R R g n
j →:都是连续,可导函数。第一组约束,m i x h i ,...,2,1),(=称
为等式约束;第二组约束,s j x g j ,...,2,1),(=称为不等式约束。非线性规划模型)2.1(的可行域可以表示为:
},...,2,1,0)(,,...,2,1,0)(|{s j x g m i x h R x X j i n =≥==∈=∶
不难看出,带约束非线性规划模型)2.1(的可行域是n
R 的子集合,所以它也是非线性规划模
型)1.1(的一个特例。
我们将根据非线性规划的标准模型)1.1(,给出非线性规划解的定义。
[定义1.1] 设X x ∈*
,n
R X ?,R R f n
→:
)1( 如果X x ∈*,并且存在*x 的邻域}0,||:||{)(**≥≤-∈=δδx x R x x N n 使得:
)()(*x f x f ≤ )(*x N X x ?∈?
则*
x 是非线性规划)1.1(的局部最优解或局部极小点,称)(*
x f 是非线性规划)1.1(的局部
最优值或局部极小值。 )2( 如果X x ∈*,并且存在*x 的邻域}0,||:||{)(**≥≤-∈=δδx x R x x N n 使得:
)()(*x f x f < }{))((**x ＼x N X x ?∈?
则*
x 是非线性规划)1.1(的严格局部最优解或严格局部极小点,称)(*
x f 是非线性规划
)1.1(的严格局部最优值或严格局部极小值。
[定义1.2] 设X x ∈*
,n
R X ?,R R f n
→:
)1( 如果X x ∈*,使得:)()(*x f x f ≤ X x ∈?,则*x 是非线性规划)1.1(的全局最
优解或全局极小点,称)(*
x f 是非线性规划)1.1(的全局最优值或全局极小值。
)2( 如果X x ∈*,使得:)()(*x f x f ≤ X x ∈?,则*x 是非线性规划)1.1(的严格全
局最优解或严格全局极小点,称)(*
x f 是非线性规划)1.1(的严格全局最优值或严格全局极小值。 图)1.1(从几何上说明了局部极小点,严格局部极小点,和严格全局极小点之间的关系。
严格局部极小点 局部极小点 严格全局极小点
图)1.1(
可以看出,对于非线性规划)1.1(,局部或严格局部极小点不是全局或严格全局极小点,
反之全局或严格全局极小点一定是局部或严格局部极小点。
对于只有两个决策变量的非线性规划问题,我们可以通过图解法进行求解。考虑下述带等式约束的非线性规划问题:
min 21)(x x x f +=
..t s 022
2
21=-+x x
)3.1(
其可行域X 是以原点为中心,半径等于2的圆周长上的所有点,见图)2.1(:
图)2.1(
显然,由于非线性规划)3.1(的目标函数是直线,与可行域X 的最小相交点为)1,1(*--=x ,它是非线性规划)3.1(的全局最优解,全局最优值为2)(*-=x f 。
再考虑下述带等式约束的非线性规划问题:
max 21)(x x x f =
..t s 221=+x x
)4.1(
显然,非线性规划)4.1(的可行域X 是连接点)0,2(和点)2,0(直线上的所有点,参见图
)3.1(:
图)3.1(
非线性规划)4.1(的目标函数与可行域X 的交点为)1,1(*
=x ,它是非线性规划)4.1(的全局最优解,全局最优值为1)(*
=x f 。
1.3 凸集和凸函数
凸集合,以及凸,凹函数在非线性规划的研究中具有特别重要的作用. [定义1.3] 设n
R S ?,如果S y x ∈?,,并且有:
S y x ∈+-λλ)1( 10≤≤λ
则称S 为凸集。 图)4.1(给出了凸集和非凸集的例子.
凸集 非凸集
图)4.1(
不难看出,凸集的几何意义为,如果点S y x ∈,,那么连接点x 和y 的线段也属于S ,即
S y x ∈],[。
[定义1.4] 函数R R x f n
→:)(,如果n
R y x ∈?,,都有:
)()()1())1((y f x f y x f λλλλ+-≤+- 10≤≤λ
则称)(x f 为凸函数。 如果)(x f -是凸函数,则称)(x f 为凹函数。
)(a 凸函数
)(b 凹函数
)(c 非凸,凹函数
图)5.1(
对于凸函数,)(z f 的取值位于连接)(x f 和)(y f 连线的下方,见图)5.1(的)(a ;对于凹函数,)(z f 的取值位于连接)(x f 和)(y f 连线的上方,见图)5.1(的)(b 。
凸(凹)函数具有以下性质:
[定理1.1] 设n
R C ?是凸集,n i R C x f i ,...,2,1,:)(=→是凸(凹)函数
)1( 对于n i i ,...,2,1,0=≥α,函数∑==n
i i i x f x f 1
)()(α也是凸(凹)函数。
)2( 如果n i x f i ,...,2,1),(=是凸函数,则)}({max )(1x f x f i n
i ≤≤=一定是凸函数; 如
果n i x f i ,...,2,1),(=是凹函数,则)}({min )(1x f x f i n
i ≤≤=一定是凹函数。 证明 我们只证明)2(的第一部分。对于任意C x x x n ∈,...,,21,我们有:
∑∑∑∑====≤≤=n
i i i n
i i i i
n i i
i i
n i i
i x f x f x f x f 1
1
1
1
)()()()(
αα
αα,n i ,...,2,1=?
那么)(x f 是凸函数,证毕。
[定义1.5] 函数R R x f n
→:)(,如果)(x f 是连续函数,且存在一阶偏导数,则称向量
T
n
x x f x x f x x f x f ))(,...,)(,)((
)(21??????=? 为)(x f 在点x 处的一阶偏导数或梯度。
[定理1.2] 设函数R R x f n
→:)(在凸集n
R X ?上一阶可微
)1( )(x f 是凸函数的充分必要条件是X y x ∈?,:
)()()()(x y x f x f y f T -?+≥
)2( )(x f 是凹函数的充分必要条件是X y x ∈?,:
)()()()(x y x f x f y f T -?+≤
定理]2.1[是判断可微函数)(x f 是否为凸(凹)函数的一个判别定理。从几何上来说, 函
数)(x f 是凸函数的充分必要条件是)(x f 在图形上任一点处的切线都在曲线的下方,见图
)6.1(。
[定理1.3] )1( 设R R x f n
→:)(是凸函数,*x 是局部极小点,那么*
x 一定是全局极小点。)2(R R x f n
→:)(是凹函数,*x 是局部极大点,那么*
x 一定是全局极大点。
证明 我们只证明)(x f 为凸函数的情况)1(。如果*
x 不是全局极小点,则存在x 使得
)()(*x f x f <。根据凸函数性质,对于所有)1,0(∈λ,
)()()1()())1((***x f x f x f x x f <-+≤-+λλλλ
这表明在*x 和x 的连线上的点,其取值严格小于)(*
x f ,所以*
x 不可能是局部极小点。)
2(证明过程与)1(类似,请大家自己完成,证毕。
)x y -
图)6.1(
[定义1.6] 函数R R x f n
→:)(,如果)(x f 存在二阶偏导数,则称矩阵
??
???????
?
?????????????
??????????????????????????????????????????=?222
2
1
222222122
122122
122
)()()()()
()
()()
()()(n n n n n x x f x x x f x x x f x x x f x x f x
x x f x x x f x x x f x x f x f
为)(x f 在点x 处的二阶偏导数矩阵,通常称其为Hessian 矩阵。 [定理1.4] 设R R x f n
→:)(是在凸集n
R X ?上二阶可微
)1( )(x f 是凸函数的充分必要条件是)(x f 的二阶Hessian 矩阵)(2x f ?是半正
定的。
)2( )(x f 是凹函数的充分必要条件是)(x f 的二阶Hessian 矩阵)(2x f ?是半负
定的。
[例1.1] 判断下述函数的凸凹性:
)1(x e x f =)(,R x ∈
)2(21)(x x f =,R x ∈
)3(22
2121212),(x x x x x x f --++=,2
R x ∈ 解: )1( 0)(''≥=x
e x
f ,所以)(x f 函数是凸集R 上的的凸函数.
)2( 04
1
)(23''≤-=-x x f ,所以)(x f 函数是凸集R 上的的凹函数.
)3( ),(21x x f 的Hessian 矩阵为:
?
?
?
???--=?2002)(2x f 为了判断)(2
x f ?的半正(负)定性,计算:
??
????----=-?λλ
λ2002))((2
def I x f def
0)2(2=--=λ
那么, 221-==λλ,所以矩阵)(2
x f ?为负定矩阵,)(x f 为凸集R 上的凹函数. 下面的定理说明了凸,凹函数与凸集,及凸集与凸集之间的关系. [定理1.5]
)1( 如果R R x f n →:)(是凸函数,对于任何R c ∈,集合})(:{c x f x L c ≤=是凸集。 )2( 如果R R x f n →:)(是凹函数,对于任何R c ∈,集合})(:{c x f x L c ≥=是凸集。
)3( 如果n i C i ,...,2,1,=是凸集,那么i i
C C I =也是凸集。
证明 我们只证明)1(。如果)(x f 是凸函数,对于任意c L x x ∈21,,有
c x f ≤)(1,c x f ≤)(2。这表明:
c x f x f x x f ≤-+≤-+)()1()())1((2121λλλλ
所以L x x ∈-+))1((21λλ,根据21,x x 的任意性,c L 是凸集,证毕。
如果非线性规划问题的目标函数为凸或凹函数,约束条件的可行集为凸集,则这类非线性规划称为凸规划。
[定义1.7] 设R C x f →:)(是凸函数,n
R C ?是凸集,考虑下述两类非线性规划问题
min )(x f
max -)(x f
..t s C x ∈
..t s C x ∈
那么,它们都是凸规划问题。
接下来,考虑带约束条件的非线性规划模型:
min )(x f
..t s .,...,2,1,0)(,...,2,1,0)(??
?=≤==s j x g m
i x h j
i
)5.1(
非线性规划模型)5.1(是凸规划的必要条件为:
)1( R C x f →:)(是凸函数
)2( R R h n i →:,m i ,...,2,1=都是线性函数 )3( R R g n j →:,s j ,...,2,1=都是凸函数。
1.4 非线性规划应用
非线性规划模型在许多领域中都获得广泛应用,在本节中,我们将介绍非线性规划在生
产管理,金融投资方面的应用.
1.4.1选址问题
首都电视机厂的产品在n 个城市中销售。为了提供优质服务,现在打算建立服务中心,希望选择地址的位置使所有城市到服务中心的距离最短。以坐标),(b a 表示服务中心的位置,设第i 个城市的地址坐标为),(i i y x ,n i ,...,2,1=,该问题等价于找到能够覆盖所有城市半径最小的园,其几何意义见下图:
图)7.1(
数学规划模型为:
min r
..t s ?
?
?≥=≤-+-0,...,2,1,)()(22r n
i r b y a x i i 这是非线性规划问题。
1.4.2投资组合管理
设n i x i ,...,2,1,=为持有第i 种证券品种的比例,满足
∑==n
i i
x
1
1,n i r i ,...,2,1,= 为第i
种证券品种的收益率,ρ为投资组合的收益率,Q 为证券品种的方差-协方差矩阵,等于:
?
?
???
????????????????????????????=nn n n n n q q q q q q q q q Q 2
1
22221
11211 数学规划模型为:
min ∑∑==n
j n
i j i ij x x q 11
..t s ???
?
?
????
=≥=≥∑∑==n i x x x r i n i i n
i i i ,...,2,1,0111ρ 这是目标函数为二次函数,约束条件为线性函数的非线性规划问题。
1.4.3指数化投资
指数化投资是根据目标指数中的成份证券的权重创建跟踪投资组合的投资方法。设B 为预算投资额,n i x i ,...,2,1,=为投资在第i 种证券品种的投资额,那么:
B x
n
i i
≤∑=1
设初始投资组合为n i x i ,...,2,1,00
=≥,C 为现金,则:
∑=+=n
i i x C B 1
设),(0i
i x x F 为从初始投资组合
∑=n
i i
x
10到投资组合
∑=n
i i
x
1
的交易成本,所以:
B x
n
i i
≤∑=1
),(0i i x x F -
设投资组合与目标指数的跟踪误差为:
∑=-=
T
t t t s r T
E 1
2
)(1 其中t r 是跟踪组合的收益率,t s 为目标指数的收益率。它们的计算方法是根据过去一个阶段的历史指数点位和成份证券价格:
)/ln(1-=t t t I I s
)ln(
11
,1,∑∑=-==n
i t i n
i t
i t y
y r
)/(,,,T i i t i t i P x P y =
其中t I 是指数的价格,t i P ,是第i 种证券在时刻t 的价格。T i i P x ,/是第i 种证券的数量。
指数化投资中最小化跟踪误差的数学规划模型为:
min ∑=-=
T
t t t
s r
T
E 1
2)(1
.st ?????=≥-≤∑=n
i x x x F B x i i i n
i i ,...,2,1,0)
,(01
1.5 无约束优化问题
考虑无约束的非线性规划问题:
)(min x f n
R
x ∈
)6.1(
一般来说,求解无约束非线性规划问题)6.1(将涉及到以下三个方面,首先,确定极小点
n R x ∈*必须满足的条件,其次设计某种迭代算法来搜寻极小点*x ,最后,求解的最终目标
一般是求全局极小点,而极小点*
x 满足的必要条件只能保证它是局部极小点,所以需要找出局部极小点也是全局极小点的条件。
1.5.1 无约束优化问题的最优性条件
如果R R x f →:)(是二次可微的一元函数,设R x ∈0,对于接近0x 的所有x ,有:
200''00'0))(())(()()(x x x f x x x f x f x f -+-+≈
显然,极值点存在的条件为:
)1( 必要条件: 0)(0'=x f
)2( 充分条件:如果0)(0'=x f 且0)(0''>x f ,0x 为极小点; 如果0)(0'=x f 且0)(0'' 设R R x f n →:)(为二次可微的多元函数,极值点存在的条件为: [定理1.6] (一阶,二阶必要条件) )1( 一阶必要条件: 对于点n R x ∈*,如果*x 是)(x f 的局部极值点,则0)(*=?x f 。 )2( 二阶必要条件: 对于点n R x ∈*,如果*x 是)(x f 的局部极值点,则)(*2x f ?为半 第四章 非线性规划 ???? ???? 无约束最优化问题线性规划约束最优化问题非线性规划 ?? ?凸规划约束最优化问题非凸规划 ?? ?直接解法约束最优化问题求解方法间接解法 间接解法是将约束优化问题转化为一系列无约束优化问题来解的一种方法。由于这类方法可以选用有效的无约束优化方法，且易于处理同时具有不等式约束和等式约束的问题，因而在工程优化中得到了广泛的应用。 直接解法是在满足不等式约束的可行设汁区域内直接按索问题的约束最优解。 第一节 目标函数的约束极值问题 所谓约束优化设计问题的最优性条件．就是指在满足等式和不等式约束条件下，其目标函数值最小的点必须满足的条件，须注意的是，这只是对约束的局部最优解而言。 对于带有约束条件的目标函数，其求最优解的过程可归结为： 一、约束与方向的定义 一）起作用约束与松弛约束 对于一个不等式约束()0g X ≤来说，如果所讨论的设计点() k X 使该约束()0g X =(或 者说() k X 当时正处在该约束的边界上)时，则称这个约束是() k X 点的一个起作用约束或紧约 束，而其他满足()0g X <的约束称为松弛约束。 冗余约束 40g ≤ 当一个设计点同时有几个约束起作用时，即可定义起作用约束集合为 {}()()()|()0,1,2, ,k k u I X u g X u m === 其意义是对() k X 点此时所有起作用约束下标的集合。 二）冗余约束 如果一个不等式约束条件的约束面(即()0g X =)对可行域的大小不发生影 响，或是约束面不与可行域D 相交，即此约束称为冗余约束。 三）可行方向 可行方向：一个设计点()k X 在可行域内，沿某一个方向S 移动，仍可得到一个属于可行域的新点，则称该方向为可行方向。 1）设计点为自由点 设计点() k X 在可行域内是一个自由点，在各个方 向上都可以作出移动得到新点仍属于可行域，如图所示。 2）设计点为约束边界点 当设计点()k X 处于起作用约束i g 上时，它的移动就会受到可行性的限制。此时，()k X 点的可行方向S 必满足条件： ()0T k i S g X ?≤ （解释：()()cos ,()T k k T k i i i S g X S g X S g X ?=??，,()90T k i S g X ?≥?）） 当,()90T k i S g X ?=?时，方向S 是约束函数i g 在()k X 点处的切线方向，即()0T k i S g X ?=。 当某个设计点x 同时有几个约束起作用时(如 实验7：线性规划与非线性规划 班级：2015级电科班，学号：222015333210187，姓名：吴京宣，第1组 ====================================================================== 一、实验目的： 1. 了解线性规划的基本内容。 2. 直观了解非线性规划的基本内容。 3. 掌握用数学软件求解优化问题。 二、实验内容 1. 两个引例. 2. 用数学软件包MATLAB求解线性规划与非线性规划问题. 3. 用数学软件包LINDO、LINGO求解线性规划问题. 4. 建模案例：投资的收益与风险. 5. 非线性规划的基本理论 6. 钢管订购及运输优化模型． 三、实验步骤 对以下问题,编写M文件: 1.某厂生产甲乙两种口味的饮料,每百箱甲饮料需用原料6千克,工人10名,可获利10万元;每百箱乙饮料需用原料5千克,工人20名,可获利9万元.今工厂共有原料60千克,工人150名,又由于其他条件所限甲饮料产量不超过800箱.问如何安排生产计划,即两种饮料各生产多少使获利最大.进一步讨论: 1)若投资0.8万元可增加原料1千克,问应否作这项投资. 2)若每100箱甲饮料获利可增加1万元,问应否改变生产计划. 2.某厂向用户提供发动机，合同规定，第一、二、三季度末分别交货40台、60 台、80台．每季度的生产费用为（单位:元）, 其中x 是该季度生产的台数．若交货后有剩余，可用于下季度交货，但需支付存储费，每台每季度c元．已知工厂每季度最大生产能力为100台，第一季度开始时无存货，设a=50、b=0.2、c=4，问:工厂应如何安排生产计划，才能既满足合同又使总费用最低．讨论a、b、c变化对计划的影响，并作出合理的解释． 第5讲整数规划、非线性规划、多目标规划 一、整数规划 1、概念 数学规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。 整数规划的分类:如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类：1）变量全限制为整数时，称纯（完全）整数规划。 2）变量部分限制为整数的，称混合整数规划。 2、整数规划特点 (i)原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况： ①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。 ②整数规划无可行解。 例1原线性规划为 2 1min x x z +=s.t. ?? ?≥≥=+0 ,05422121x x x x 其最优实数解为：01=x ，4 52=x ， 4 5min = z ③有可行解（当然就存在最优解），但最优值变差。例2原线性规划为 2 1min x x Z +=s.t. ?? ?≥≥=+0 ,06422121x x x x 其最优实数解为：01=x ，2 32=x ，2 3min = z 若限制整数得：11=x ，12=x ， 2 min =z 。 （ii ）整数规划最优解不能按照实数最优解简单取整而获得。 3、0-1整数规划 0?1型整数规划是整数规划中的特殊情形，它的变量 j x 仅取值 0或1。这时 j x 称为 0?1变量，或 称二进制变量。j x 仅取值0或1这个条件可由下述约束条件： 1 0≤≤j x ，且为整数 所代替，是和一般整数规划的约束条件形式一致的。在实际问题中，如果引入0?1变量，就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中讨论了。 引入10-变量的实际问题： （1）投资场所的选定——相互排斥的计划 例3某公司拟在市东、西、南三区建立门市部。拟议中有7个位置（点）)7,,2,1( =i A i 可供选择。规定 在东区：由321,,A A A 三个点中至多选两个；在西区：由54,A A 两个点中至少选一个； 第四章 约束非线性规划 § 4.3 可行方向法 作者：黄希勇 2013.5.28 引入： 对于非线性规划问题，如果不存在约束，从任一个初始点 )0(x 出发，沿)(x f 的负梯度方向进行一维收索，便可求得目标函数的无约束极小值；而对有约束的极小化问题来说，除要使目标函数在每次迭代有所下降之外，还要注意解的可行性问题，为此，在求解约束非线性规划迭代法的设计中，应在每个迭代点)(k x 出构造一个可行下降方向 )(k d 。 引入：有效约束和可行下降方向的概念 考虑非线性规划 ?? ???=≥==m i x g l j x h t s x f i j .....2,10)(......2,10)(.) (min （4.3.1） 其中，)(),(),(x g x h x f i j 均为实值连续函数，且具有二阶连续偏导数。 设)0(x 是非线性规划的一个可行解。现考虑某一不等式约束条件 0)(≥x g i 满足它有两种可能：其一为0)(>x g i ，这时，点)0(x 不是处于由这一约束条件形成的可行域边界上，因而这一约束对)0(x 点的微小摄动不起限制作用，从而称这个约束条件是)0(x 点的不起作用约束(或无效约束)；其二是0)(=x g i ，这时)0(x 点处于该约束条件形成的可行域边界上， 它对)0(x 的摄动起到了某种限制作用，故称这个约束是点的起作用约束(有效约束)。 显而易见，等式约束对所有可行点来说都是起作用约束。 1.1 D e f ： 设可行域是非空集，D x ∈，若对某非零向量n R d ∈，存在0>δ，使对任意),0(δ∈t 均有D td x ∈+,则称d 为从x 出发的可行方向。 若非线性规划的某一可行点)0(x ，对该点的任一方向d 来说，若存在实数't ，使对任意 ]',0[t t ∈均有 )()()0()0(x f td x f <+ 就称方向d 为)0(x 点的一个下降方向。 如果方向d 既是)0(x 点的可行方向，又是这个点的下降方向，就称它是该点的可行下降方向。 Eg 4.4: 略 现考虑非线性规划（4.3.1）式，设)(k x 是它的一个可行解，但不是要求的极小点。为了求它的极小点或近似极小点，根据以前所说，应在)(k x 点的可行下降方向中选取某一方向)(k d ，并确定步长k t ，使 ???<+=++) ()() ()1() ()()1(k k k k k k x f x f d t x x （4.3.2） 若满足精度要求，迭代停止，)1(+k x 就是所要的点。否则，从)1(+k x 出发继续进行迭代，直到满足要求为止。上述方法称为可行方向法； 其特点是：迭代过程中采用的搜索方向为可行方向，所产生的迭代 非线性规划模型 在上一次作业中，我们对线性规划模型进行了相应的介绍及优缺点，然而在实际问题中并不是所有的问题都可以利用线性规划模型求解。实际问题中许多都可以归结为一个非线性规划问题，即如果目标函数和约束条件中包含有非线性函数，则这样的问题称为非线性规划问题。一般来说，解决非线性的问题要比线性的问题难得多，不像线性规划有适用于一般情况的单纯形法。对于线性规划来说，其可行域一般是一个凸集，只要存在最优解，则其最优解一定在可行域的边界上达到；对于非线性规划，即使是存在最优解，却是可以在可行域的任一点达到，因此，对于非线性规划模型，迄今为止还没有一种适用于一般情况的求解方法，我们在本文中也只是介绍了几个比较常用的几个求解方法。 一、非线性规划的分类 1无约束的非线性规划 当问题没有约束条件时，即求多元函数的极值问题，一般模型为 ()min 0 x R f X X ∈??? ≥?? 此类问题即为无约束的非线性规划问题 1.1无约束非线性规划的解法 1.1.1一般迭代法 即为可行方向法。对于问题()min 0x R f X X ∈??? ≥?? 给出)(x f 的极小点的初始值)0(X ，按某种规律计算出一系列的 ),2,1()( =k X k ，希望点阵}{)(k X 的极限*X 就是)(x f 的一个极小点。 由一个解向量) (k X 求出另一个新的解向量)1(+k X 向量是由方向和长度确定的，所以),2,1()1( =+=+k P X X k k k k λ 即求解k λ和k P ，选择k λ和k P 的原则是使目标函数在点阵上的值逐步减小，即 .)()()(10 ≥≥≥≥k X f X f X f 检验}{)(k X 是否收敛与最优解，及对于给定的精度0>ε，是否 ε≤?+||)(||1k X f 。 1.1.2一维搜索法 当用迭代法求函数的极小点时，常常用到一维搜索，即沿某一已知方向求目标函数的极小点。一维搜索的方法很多，常用的有： （1）试探法（“成功—失败”，斐波那契法，0.618法等）； （2）插值法（抛物线插值法，三次插值法等）； 第四章 数学规划模型 【教学目的】：深刻理解线性规划，非线性规划，动态规划方法建模的基本特点，并能熟练建立一些实际问题的数学规划模型；熟练掌握用数学软件（Matlab ，Lindo ，Lingo 等）求解优化问题的方法。 【教学重点难点】： 教学重点：线性规划和非线性规划的基本概念和算法，解决数学规划问题的一般思路和 方法，线性规划模型、整数规划模型、非线性规划模型的构建及其Matlab 与Lingo 实现。 教学难点：区分线性规划模型和非线性模型适用的实际问题，以及何时采用线性模型， 何时采用非线性模型，线性模型与非线性模型的转化。 【课时安排】：10学时 【教学方法】：采用多媒体教学手段，配合实例教学法，通过对典型例题的讲解启发学生思维，并给与学生适当的课后思考讨论的时间，加深知识掌握的程度。安排一定课时的上机操作。 【教学内容】： 在众多实际问题中，常常要求决策（确定）一些可控制量的值，使得相关的量（目标）达到最佳（最大或最小）。这些问题就叫优化问题，通常需要建立规划模型进行求解。称这些可控制量为决策变量，相关的目标量为目标函数；一般情况下，决策变量x 的取值是受限制的，不妨记为x ∈Ω，Ω称为可行域，优化问题的数学模型可表示为 Max(或Min)f(x), x ∈Ω 一般情况下，x 是一个多元变量，f(x)为多元函数，可行域比较复杂，一般可用一组不等式组来表示，这样规划问题的一般形式为 () x Min f x . ()0,1,2,,i st g x i m ≤= 虽然，该问题属于多元函数极值问题，但变量个数和约束条件比较多，一般不能用微分法进行解决，而通过规划方法来求解；这里讨论的不是规划问题的具体算法，主要是讨论如何将一个实际问题建立优化模型，并利用优化软件包进行求解。 根据目标函数和约束函数是否为线性，将规划模型分为线性规划和非线性规划。 4.1线性规划 线性规划(LP)研究的实际问题多种多样的，它在工农业生产、经济管理、优化设计与控 第四章 非线性规划 教学重点：凸规划及其性质，无约束最优化问题的最优性条件及最速下降法，约束最优化问题的最优性条件及简约梯度法。 教学难点：约束最优化问题的最优性条件。 教学课时：24学时 主要教学环节的组织：在详细讲解各种算法的基础上，结合例题，给学生以具体的认识，再通过大量习题加以巩固，也可以应用软件包解决一些问题。 第一节 基本概念 教学重点：非线性规划问题的引入，非线性方法概述。 教学难点：无。 教学课时：2学时 主要教学环节的组织：通过具体问题引入非线性规划模型，在具体讲述非线性规划方法的求解难题。 1、非线性规划问题举例 例1 曲线最优拟合问题 已知某物体的温度? 与时间t 之间有如下形式的经验函数关系： 3 12c t c c t e φ=++ （*） 其中1c ，2c ，3c 是待定参数。现通过测试获得n 组?与t 之间的实验数据),(i i t ?， i=1，2，…,n 。试确定参数1c ，2c ，3c ，使理论曲线(*)尽可能地与n 个测试点 ),(i i t ?拟合。 ∑=++-n 1i 221)]([ min 3i t c i i e t c c ? 例 2 构件容积问题 通过分析我们可以得到如下的规划模型： ??? ????≥≥=++++=0 ,0 2 ..)3/1( max 212 121222211221x x S x x x x a x x t s x x a V ππππ 基本概念 设n T n R x x x ∈=),...,(1，R R q j x h p i x g x f n j i α:,...,1),(;,...,1),();(==, 如下的数学模型称为数学规划(Mathematical Programming, MP)： ?? ? ??===≤q j x h p i x g t s x f j i ,...,1,0)( ,...,1,0)( ..) ( min 约束集或可行域 X x ∈? MP 的可行解或可行点 MP 中目标函数和约束函数中至少有一个不是x 的线性函数，称(MP)为非线性规划 令 T p x g x g x g ))(),...,(()(1= T p x h x h x h ))(),...,(()(1=， 其中，q n p n R R h R R g αα:,:，那么(MP )可简记为 ?? ? ??≤≤ 0)( 0 ..)( min x h g(x)t s x f 或者 )(min x f X x ∈ 当p=0,q=0时，称为无约束非线性规划或者无约束最优化问题。 否则，称为约束非线性规划或者约束最优化问题。 定义4.1.1 对于非线性规划(MP )，若X x ∈*，并且有 X ),()(*∈?≤x x f x f 设计一个右图所示的由圆锥和圆柱面 围成的构件，要求构件的表面积为S ， 圆锥部分的高h 和圆柱部分的高x 2之 比为a 。确定构件尺寸，使其容积最 大。 摘要 本文旨在对非线性规划的算法和应用进行研究。非线性规划是20世纪50年代才开始形成的一门新兴学科。1951年库恩和塔克发表的关于最优性条件(后来称为库恩－塔克条件，又称为K-T条件)的论文是非线性规划正式诞生的一个重要标志。非线性规划在管理、工程、科研、军事、经济等方面都有广泛的应用，并且为最优设计提供了有力的工具。 在第一章我们主要介绍了非线性规划的基础知如非线性规划的数学模型，凸函数和凹函数，极值问题以及下降迭代算法等。 在第二章我们主要对约束条件的线性规划进行了具体介绍。在无约束非线性规划中主要讨论了一维搜索法和多变量函数极值的下降方法。 第三章介绍了求解非线性规划的计算机软件并通过一些基本的例子，从而进一步加深对非线性规划进行理解。 关键词：非线性规划；约束非线性规划；最优解 第一章绪论 1.1非线性规划综述 非线性规划是具有非线性目标函数或约束条件的数学规划，是运筹学的一个重要分支[1]。非线性规划属于最优化方法的一种，是线性规划的延伸。早在17世纪，Newton和Leibniz发明微积分的时代，已经提出函数的极值问题，后来又出现了Lagrange乘子法，Cauchy的最速下降法。但直到20世纪30年代，最优化的理论和方法才得以迅速发展，并不断完善，逐步成为一门系统的学科[2]。 1939年，Kantorovich和Hitchcock等人在生产组织管理和制定交通运输方案方面首先研究和应用了线性规划。 1947年，Dantzig提出了求解线性规划的单纯形法，为线性规划的理论和算法奠定了基础，单纯形法被誉为“20世纪最伟大的创造之一”。 1951年，由Kuhn和Tucker完成了非线性规划的基础性工作 [3]。 1959—1963年，由三位数学家共同研究成功求解无约束问题的DFP变尺度法(该算法是由英国数学家W．C．Davidon提出，由法国数学家R．Fletcher和美国数学家M．J．D.Powell加以简化)，该算法的研究成功是无约束优化算法的一个大飞跃，引起了一系列的理论工作，并陆续出现了多种新的算法[4]。 1965年，德国数学家C．G Broyden提出了求解非线性方程组的拟牛顿算法，并且该算法还包含了DFP算法。 1970年，四位数学家以不同角度对变尺度算法进行了深入研究，提出了BFGS 公式 (C．G Broyden，R Fletcher，D．Goldfarb，D．E Shanno) 。实践表明该算法较之DFP算法和拟Newton法具有更好的数值稳定性。 1970年，无约束优化方法的研究出现了引入注目的成果，英国数学家L．C．W Dixon和美籍华人H．Y．Huang提出了关于“二阶收敛算法的统一研究”的研究成果，提出了一个令三个自由参数的公式族．Huang族和拟牛顿公式，它可包容前面所介绍的所有无约束优化算法。 20世纪70年代，最优化无论在理论和算法上，还是在应用的深度和广度上都有了进一步的发展。随着电子计算机的飞速发展，最优化的应用能力越来越强，从而成为一门十分活跃的学科[5]。 近代最优化方法的形成和发展过程中最重要的事件有： 1、以苏联康托罗维奇和美国丹齐克为代表的线性规划； 2、以美国库恩和塔克尔为代表的非线性规划； 第四章 非线性规划 ?? ?? ???? 无约束最优化问题线性规划约束最优化问题非线性规划 ?? ?凸规划约束最优化问题非凸规划 ?? ?直接解法约束最优化问题求解方法间接解法 间接解法是将约束优化问题转化为一系列无约束优化问题来解的一种方法。由于这类方法可以选用有效的无约束优化方法，且易于处理同时具有不等式约束和等式约束的问题，因而在工程优化中得到了广泛的应用。 直接解法是在满足不等式约束的可行设汁区域内直接按索问题的约束最优解。 第一节 目标函数的约束极值问题 所谓约束优化设计问题的最优性条件．就是指在满足等式和不等式约束条件下，其目标函数值最小的点必须满足的条件，须注意的是，这只是对约束的局部最优解而言。 对于带有约束条件的目标函数，其求最优解的过程可归结为： 一、约束与方向的定义 一）起作用约束与松弛约束 对于一个不等式约束()0g X ≤来说，如果所讨论的设计点() k X 使该约束()0g X =(或 者说() k X 当时正处在该约束的边界上)时，则称这个约束是() k X 点的一个起作用约束或紧约 束，而其他满足()0g X <的约束称为松弛约束。 冗余约束 4 0g ≤ 当一个设计点同时有几个约束起作用时，即可定义起作用约束集合为 {}()()()|()0,1,2, ,k k u I X u g X u m === 其意义是对() k X 点此时所有起作用约束下标的集合。 二）冗余约束 如果一个不等式约束条件的约束面(即()0g X =)对可行域的大小不发生影 响，或是约束面不与可行域D 相交，即此约束称为冗余约束。 三）可行方向 可行方向：一个设计点()k X 在可行域内，沿某一个方向S 移动，仍可得到一个属于可行域的新点，则称该方向为可行方向。 1）设计点为自由点 设计点() k X 在可行域内是一个自由点，在各个方 向上都可以作出移动得到新点仍属于可行域，如图所示。 2）设计点为约束边界点 当设计点()k X 处于起作用约束i g 上时，它的移动就会受到可行性的限制。此时，()k X 点的可行方向S 必满足条件： ()0T k i S g X ?≤ （解释：()()cos ,()T k k T k i i i S g X S g X S g X ?=??，,()90T k i S g X ?≥?）） 当,()90T k i S g X ?=?时，方向S 是约束函数i g 在()k X 点处的切线方向，即()0T k i S g X ?=。 当某个设计点x 同时有几个约束起作用时(如 第三章 非线性规划 §1 非线性规划 1.1 非线性规划的实例与定义 如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非线性规划问题。一般说来，解非线性规划要比解线性规划问题困难得多。而且，也不象线性规划有单纯形法这一通用方法，非线性规划目前还没有适于各种问题的一般算法，各个方法都有自己特定的适用范围。 下面通过实例归纳出非线性规划数学模型的一般形式，介绍有关非线性规划的基本概念。 例 1 （投资决策问题）某企业有n 个项目可供选择投资，并且至少要对其中一个项目投资。已知该企业拥有总资金A 元，投资于第),,1(n i i 个项目需花资金i a 元，并预计可收益i b 元。试选择最佳投资方案。 解 设投资决策变量为 个项目 决定不投资第，个项目决定投资第i i x i 0,1，n i ,,1 ， 则投资总额为 n i i i x a 1 ，投资总收益为 n i i i x b 1。因为该公司至少要对一个项目投资，并且总的投资金额不能超过总资金A ，故有限制条件 n i i i A x a 10 另外，由于),,1(n i x i 只取值0或1，所以还有 .,,1,0)1(n i x x i i 最佳投资方案应是投资额最小而总收益最大的方案，所以这个最佳投资决策问题归结为总资金以及决策变量（取0或1）的限制条件下，极大化总收益和总投资之比。因此，其数学模型为： n i i i n i i i x a x b Q 11 max s.t. n i i i A x a 10 .,,1,0)1(n i x x i i 上面例题是在一组等式或不等式的约束下，求一个函数的最大值（或最小值）问题，其中至少有一个非线性函数，这类问题称之为非线性规划问题。可概括为一般形式 )(min x f q j x h j ,,1,0)(s.t. (NP) p i x g i ,,1,0)( 实验六数学建模—非线性规划 实验目的： 1．直观了解非线性规划的基本内容． 2．掌握用数学软件求解优化问题． 实验内容： 1、某厂向用户提供发动机，合同规定，第一、二、三季度末分别交货40台、60台、80台．每季度的生产费用为()2bx ax x f+ =（单位:元）, 其中x是该季度生产的台数．若交货后有剩余，可用于下季度交货，但需支付存储费，每台每季度c元．已知工厂每季度最大生产能力为100台，第一季度开始时无存货，设a=50、b=0.2、c=4，问:工厂应如何安排生产计划，才能既满足合同又使总费用最低．讨论a、b、c变化对计划的影响，并作出合理的解释． 2、一基金管理人的工作是: 每天将现有的美元、英镑、马克和日元四种货币按当天汇率相互兑换，使在满足需要的条件下，按美元计算的价值最高．设某天的汇率、现有货币和当天需求如下： 问该天基金管理人应如何操作. (“按美元计算的价值”指兑入、兑出汇率的平 均值，如1英镑相当于 () 2 58928 .0 1 697 .1+=1.696993美元.) 实验过程与结果： 1、（1）模型建立 决策变量：设第1，2，3季度分别生产x1，x2，x3台发动机，第1，2季度末分别有存货40-x1，x1+x2-100台，第3季度末无存货 目标函数：设总费用为 z=a(x1+x2+x3)+b(x1^2+x2^2+x3^2)+c[(x1-40)+(x1+x2-100)] 约束条件：生产的发动机应该在第3季度末全部卖出，则有x1+x2+x3=180；同时要保证第1，2季度能供货且有能力生产，要求x1≥40，x1+x2≥100,100≥x1,100≥x2,100≥x3 非负约束：x1,x2,x3≥0 综上可得： Maxz=a(x1+x2+x3)+b(x1^2+x2^2+x3^2)+c[(x1-40)+(x1+x2-100)] s.t．x1+x2+x3=180 x1+x2≥100 x1≥40 0≤x1,x2,x3≤100 （2）模型求解 结果为： 即工厂应第一季度生产50台发动机，第二季度生产60台发动机，第三季度生产70台发动机，才能既满足合同又使总费用最低。 进一步讨论参数a，b，c对生产计划的影响： 由于生产总量是恒定的，即x1+x2+x3=180，而z=a(x1+x2+x3)+b(x1^2+ x2^2 +x3^2)+c[(x1-40)+(x1+x2-100)]，故a的变化不会影响生产计划；b是x的二 多目标非线性规划程序 M a t l a b Document serial number【NL89WT-NY98YT-NC8CB-NNUUT-NUT108】 f u n c t i o n[e r r m s g,Z,X,t,c,f a i l]= BNB18(fun,x0,xstat,xl,xu,A,B,Aeq,Beq,nonlcon,setts,options1,options2,maxSQPit,varargin ); %·Dêy1￡Díóa·§¨μü′ú·¨￡úDê1ó￡DèOptimization toolbox §3 % Minimize F(x) %subject to: xlb <= x <=xub % A*x <= B % Aeq*x=Beq % C(x)<=0 % Ceq(x)=0 % % x(i)éaáD±á￡êy￡ò1ì¨μ % ê1óê %[errmsg,Z,X]=BNB18('fun',x0,xstat,xl,xu,A,B,Aeq,Beq,'nonlcon',setts) %fun￡o Mt￡±íê×Dˉ±êoˉêyf=fun(x) %x0: áDòá￡±íê±á3μ %xstat￡o áDòá￡xstat(i)=0±íêx(i)aáD±á￡1±íêêy￡2±íê1ì¨μ %xl￡o áDòá￡±íê±á %xu: áDòá￡±íê±áé %A: ó, ±íêD2μèêêμêy %B: áDòá, ±íêD2μèêêé %Aeq: ó, ±íêDμèêêμêy %Beg: áDòá, ±íêD2μèêêóòμ %nonlcon: Mt￡±íê·Dêoˉêy[C,Ceq]=nonlin(x),DC(x)a2μèêê, % Ceq(x)aμèêê %setts: ·¨éè %errmsq: ·μ′íóìáê %Z: ·μ±êoˉêy×Dμ %X: ·μ×óa % %àyìa % max x1*x2*x3 % -x1+2*x2+2*x3>=0 % x1+2*x2+2*x3<=72 % 10<=x2<=20 % x1-x2=10 % èD′ Moˉêy % function f=discfun(x) % f=-x(1)*x(2)*x(3); %óa % clear;x0=[25,15,10]';xstat=[1 1 1]'; % xl=[20 10 -10]';xu=[30 20 20]'; % A=[1 -2 -2;1 2 2];B=[0 72]';Aeq=[1 -1 0];Beq=10; % [err,Z,X]=BNB18('discfun',x0,xstat,xl,xu,A,B,Aeq,Beq); % XMAX=X',ZMAX=-Z % 实验5 线性规划 分1 黄浩 43 一、实验目的 1.掌握用MATLAB工具箱求解线性规划的方法 2.练习建立实际问题的线性规划模型 二、实验内容 1.《数学实验》第二版（问题6） 问题叙述： 某银行经理计划用一笔资金进行有价证券的投资，可供购进的证券以及其信用等级、到期年限、收益如下表所示。按照规定，市政证券的收益可以免税，其他证券的收益需按50%的税率纳税。此外还有如下限制： (1).政府及代办机构的证券总共至少要购进400万元； (2).所购证券的平均信用等级不超过1.4(信用等级数字越小，信用程度越高)； (3).所购证券的平均到期年限不超过5年 I.若该经理有1000万元资金，该如何投资？ II.如果能够以2.75%的利率借到不超过100万元资金，该经理应如何操作？ III.在1000万元资金情况下，若证券A的税前收益增加为4.5%，投资应否改变？若证券C的税前收益减少为4.8%，投资应否改变？ 模型转换及实验过程： I. 设经理对于上述五种证券A、B、C、D、E的投资额分别为：、、、、(万 元)，全部到期后的总收益为z万元。 由题目中的已知条件，可以列出约束条件为： 而决策变量的上下界约束为： 目标函数 将上述条件转变为matlab的要求形式： 使用matlab解上述的线性规划问题（程序见四.1），并整理成表格： 得出结论： 当经理对A、B、C、D、E五种证券分别投资218.18、0、736.36、0、45.45万元时，在全部收回时可得到29.836万元的税后收益，而且这种投资方式所得收益是最大的。 讨论： 尝试输出该约束条件下的拉格朗日乘子： 该乘子表示，第一个约束条件对目标函数的取值不起作用，而剩余三个约束条件取严格等号的时候，目标函数达到最优解。下面验证之： 由解得的x值，代入四个约束条件中，得： 实验9 非线性规划 实验目的： 1）掌握用matlab优化工具箱解非线性规划的方法 2）练习建立实际问题的非线性规划模型 实验内容： 4.某公司将3种不同含硫量的液体原料（分别记为甲、乙、丙）混合生产两种产品（分别记为A，B）.按照生产工艺的要求，原料甲、乙必须首先倒入混合池中混合，混合后的液体再分别于原料丙生产A，B.已知原料甲、乙、丙的含硫量分别是3%，1%，2%，进货价格分别为6千元/t，16千元/t，10千元/t；产品A,B的含硫量分别不能超过2.5%，1.5%，售价分别为9千元/t，15千元/t.根据市场信息，原料甲、乙、丙的供应量都不能超过500t;产品A，B的最大市场需求量分别为100t，200t. （1）应如何安排生产？ （2）如果产品A的最大市场需求量增长为600t，应如何安排生产？ （3）如果乙的进货价格下降为13千元/t，应如何安排生产？分别对（1）、（2）两种情况进行讨论. 解：（1） 问题的建模 设利用x1吨甲，x2吨乙，x3吨丙制造y1吨A；利用x2吨甲，x4吨乙，x6吨丙制造y2吨B；总收益是z千元。 则有以下方程与不等式： 质量守恒： y1=x1+x3+x5 y2=x2+x4+x6 总收益： z=9y1+15y2-6(x1+x2)-16(x3+x4)-10(x5+x6) 化简得： z=3x1+9x2+3x3+9x4-x5+5x6 含硫量约束： 3%x1+1%x3+2%x5≤2.5%y1 3%x2+1%x4+2%x6≤1.5%y2 化简得： 0.5 x1-1.5x3-0.5x5≤0 1.5x2-0.5x4+0.5x6≤0 供应量约束： （x1+x2）,(x3+x4),(x5+x6)≤500 需求量约束： y1≤100；y2≤200 化简得： function [errmsg,Z,X,t,c,fail] = BNB18(fun,x0,xstat,xl,xu,A,B,Aeq,Beq,nonlcon,setts,options1,options2,ma xSQPit,varargin); %·???D???êy1????￡Dí?ó?a·??§?¨??μü′ú??·¨?￡?úMATLAB5.3?Dê1ó?￡?DèOptimizat ion toolbox 2.0?§3?? % Minimize F(x) %subject to: xlb <= x <=xub % A*x <= B % Aeq*x=Beq % C(x)<=0 % Ceq(x)=0 % % x(i)?é?aá?D?±?á?￡???êy￡??ò1ì?¨?μ % ê1ó???ê? %[errmsg,Z,X]=BNB18('fun',x0,xstat,xl,xu,A,B,Aeq,Beq,'nonlcon',setts) %fun￡o M???t??￡?±íê?×?D??ˉ??±êoˉêyf=fun(x) %x0: áD?òá?￡?±íê?±?á?3??μ %xstat￡o áD?òá?￡?xstat(i)=0±íê?x(i)?aá?D?±?á?￡?1±íê???êy￡?2±íê?1ì?¨?μ %xl￡o áD?òá?￡?±íê?±?á????? %xu: áD?òá?￡?±íê?±?á?é??? %A: ???ó, ±íê???D?2?μèê???ê??μêy %B: áD?òá?, ±íê???D?2?μèê???ê?é??? %Aeq: ???ó, ±íê???D?μèê???ê??μêy %Beg: áD?òá?, ±íê???D?2?μèê???ê?óò???μ %nonlcon: M???t??￡?±íê?·???D???ê?oˉêy[C,Ceq]=nonlin(x),???DC(x)?a2?μèê???ê?, % Ceq(x)?aμèê???ê? %setts: ??·¨éè?? %errmsq: ·μ??′í?óìáê? %Z: ·μ????±êoˉêy×?D??μ %X: ·μ??×?ó??a % %àyìa % max x1*x2*x3 % -x1+2*x2+2*x3>=0 % x1+2*x2+2*x3<=72 % 10<=x2<=20 % x1-x2=10 % ?èD′ Moˉêydiscfun.m % function f=discfun(x) % f=-x(1)*x(2)*x(3); %?ó?a % clear;x0=[25,15,10]';xstat=[1 1 1]'; % xl=[20 10 -10]';xu=[30 20 20]'; % A=[1 -2 -2;1 2 2];B=[0 72]';Aeq=[1 -1 0];Beq=10; % [err,Z,X]=BNB18('discfun',x0,xstat,xl,xu,A,B,Aeq,Beq); % XMAX=X',ZMAX=-Z % % BNB18 Finds the constrained minimum of a function of several possibly integer variables. % Usage: [errmsg,Z,X,t,c,fail] = % BNB18(fun,x0,xstatus,xlb,xub,A,B,Aeq,Beq,nonlcon,settings,options1,opti ons2,maxSQPiter,P1,P2,...) % % BNB solves problems of the form: % Minimize F(x) subject to: xlb <= x0 <=xub 第五节可行方向法(FDM ) 可行方向法是用梯度去求解约束非线性最优化问题的一种有代表性的直接探索方法，也是求解大型约束优化设计问题的主要方法之一。其收敛速度快，效果较好，适用于大中型约 束最优化问题，但程序比较复杂。 可行方向法(Feasible Direction Method)是一种直接搜索方法，其搜索方向的获取利用了目标函数和约束函数的梯度信息。用目标函数的梯度可以得到目标函数值的下降方向，而利用约束函数的梯度则可以得到可行的搜索方向。因此，可行方向法的搜索方向实质上是既使 目标函数值下降，同时又可行的方向，即可行下降方向。满足这一条件的方法就称为可行方 向法。 一、基本原理 当求解目标函数的极小值 min f (X) X R n s.t g u(X)M0 u =1,2,3川,m 当设计点X(k)处于起作用约束g i 上时，下降可行方向S必须同时满足条件： S“g(X k)乞0 S^f (X k) ：：0 由于于多数非线性规划的最优点都处在可行区的约束边界上或者几个约束边界的交点 上，因此最优搜索如能沿着约束边界附近进行，就有可能加速最优化搜索的进程。按照这一基本思路，在任意选定一初始点后到最后得到最优点必须解决三个问题：一是如何尽快使最优搜索从初始点到达约束边界 二是到达边界后怎样判断所找到的边界点是否是最优点； 三是如果边界点经判断不是最优点，那么下一步应如何进行最优搜索。 二、如何从初始点尽快到达边界 在任意选定初始点X0之后，首先判断X0是否为可行点，若是可行点，则选择目标函数的负梯度方向作为下一步的搜索方向。若是非可行点，则选择目标函数的梯度方 向为搜索方向。 搜索的步长可采用试探的方法逐步缩小，直到最后到达边界。 如图5-13表示了初始点为可行点时的搜索过程。 从初始点X0出发沿-\f(X°)方向，取步长为t，进行搜索，得到 X1 x1=X° -r f (X0) 若X1仍在可行区内，则把步长加大一倍继续搜索 得到 團银门 初始負到达 边界过理 实 验 报 告 解无约束非线性规划实验（运筹学与最优化方法，4学时） 一 实验目的 1．掌握迭代算法的思想。 2．掌握0.618法。 3．掌握最速下降法、共轭梯度法和拟牛顿法。 二 实验内容 1．用0.618法解下列问题： 2min ()21f x x x =-- 初始区间为：11[,][1,1],0.16a b ε=-=。 2．用最速下降法、共轭梯度法和拟牛顿法分别解下列问题： 221212 min (,)4f x x x x =+ 取(0)(0)12(,)(1,1)x x = 三 实验步骤（算法）与结果 1. 解:首先建立一个黄金分割计算最优值的函数文件并保存为HJFG ， 可供调用： x(1)=input('a='); y(1)=input('b='); k=input('k='); n=1;m=1; p(1)=x(1)+0.382*(y(1)-x(1)); q(1)=x(1)+0.618*(y(1)-x(1)); while y(n)-x(n)>=k if g(p(n))>g(q(n)) n=n+1; x(n)=p(n-1);y(n)=y(n-1);p(n)=q(n-1); q(n)=x(n)+0.618*(y(n)-x(n)); elseif g(p(n))<=g(q(n)) n=n+1; x(n)=x(n-1);y(n)=q(n-1);q(n)=p(n-1); p(n)=x(n)+0.382*(y(n)-x(n)); end end x(n),y(n),min=1/2*(x(n)+y(n)) 参数说明：x(1)：计算区间的左极限； y(1)：计算区间的右极限； k：计算要求达到的精度； p(n)，q(n)：黄金分割的计算公式； g(x)：输入的计算函数； min=1/2*(x(n)+y(n))：满足条件的最优解. 实际使用： 首先建立函数文件并保存： function G=g(x) G=2*x^2-x-1; 然后调用上面的函数 输出结果为： ans =0.1672 ans =0.2787 min =0.2229 也就是满足条件的解的存在区间之一是[0.1672,0.2787]，取平均值0.2229作为近似最优解. 2.解： -32- 第三章 非线性规划 §1 非线性规划 1.1 非线性规划的实例与定义 如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非线性规划问题。一般说来，解非线性规划要比解线性规划问题困难得多。而且，也不象线性规划有单纯形法这一通用方法，非线性规划目前还没有适于各种问题的一般算法，各个方法都有自己特定的适用范围。 下面通过实例归纳出非线性规划数学模型的一般形式，介绍有关非线性规划的基本概念。 例1 （投资决策问题）某企业有n 个项目可供选择投资，并且至少要对其中一个项目投资。已知该企业拥有总资金A 元，投资于第),,1(n i i L =个项目需花资金i a 元，并预计可收益i b 元。试选择最佳投资方案。 解 设投资决策变量为 ?? ?=个项目 决定不投资第，个项目 决定投资第i i x i 0,1，n i ,,1L =， 则投资总额为 ∑=n i i i x a 1，投资总收益为 ∑=n i i i x b 1 。因为该公司至少要对一个项目投资，并 且总的投资金额不能超过总资金A ，故有限制条件 ∑=≤< n i i i A x a 1 另外，由于),,1(n i x i L =只取值0或1，所以还有 .,,1,0)1(n i x x i i L ==? 最佳投资方案应是投资额最小而总收益最大的方案，所以这个最佳投资决策问题归结为总资金以及决策变量（取0或1）的限制条件下，极大化总收益和总投资之比。因此，其数学模型为： ∑∑=== n i i i n i i i x a x b Q 11max s.t. ∑=≤< n i i i A x a 1 .,,1,0)1(n i x x i i L ==? 上面例题是在一组等式或不等式的约束下，求一个函数的最大值（或最小值）问题，其中至少有一个非线性函数，这类问题称之为非线性规划问题。可概括为一般形式 )(min x f q j x h j ,,1, 0)(s.t. L =≤ (NP) p i x g i ,,1, 0)(L ==第四章 非线性规划1-约束极值问题
数学建模线性规划与非线性规划
第5讲 整数规划、非线性规划、多目标规划1
第四章 约束非线性规划
非线性规划模型
第四章 数学规划模型
第四章 非线性规划 山大刁在筠 运筹学讲义教学内容
非线性规划的论文
第四章 非线性规划约束极值问题
第三章 非线性规划[001]
数学建模—非线性规划实验报告
多目标非线性规划程序Matlab完整版
数学实验——线性规划
清华大学数学实验_实验9 非线性规划1
多目标非线性规划程序(Matlab)
第四章非线性规划5-可行方向法
实验2_解无约束非线性规划
数学建模-非线性规划
相关主题
文本预览