第 3步 通过选择最好 ( zjk - cjk )的进基变量 j, 使得 2个 变量仅当它们相邻时可取正值, 不 断重复这一过程直到最优性条件 满足, 或者直到 不违反限制基条件就不可能引入新的 jk时为止。
第 4步 终止计算, 输出最优解。
2. 2 算例分析 用上述方法求解下列问题
m ax z = x1 + x2 4 3x1 + 2x2 2 % 9
1 1/10 1 /10
0 - 1 /10 9 /10
0 13 /2 22. 5
由表 3~ 4可知, 21和 22是候选进 基变量。 由于 21 与基变量 23 或 24不 相邻, 因 此不能进 基。类似地, 由于 24不能 离基, 因此 22 不能进 基, 因此最终的单纯形表就是近似问题的最好解, 即原问题的最优解是
徐裕生, 杜英阁, 王佳佳
(西安建筑科技大学 理学院, 西安 710055)
摘
要: 提出了一种针对目标函数、约束条件都是非线性的非线性规划问题的新算法。此算
法主要是利用可分离函数和近似求解的思想来求解问题。数值计算结果显示, 该方法是可行和
有效的。
关 键 词: 非线性规划; 可分离函数; 近似模型; 单纯形法
( Co llege o f Science, X ia'n U niversity of A rchitecture and T echnology, Shaanx i 710055, Ch ina)
Abstract: T h is article describes a new algo rithm fo r so lving non linear programm ing problem s w hose target funct ions and constraints are non linear. T his a lgorithm uses separable functions and approx im ate solutions to so lve the problem s. Num erical resu lts show that the algorithm is feasible and effective. K ey w ord s: nonlinear programm ing; separab le funct ion; approx im at ion m ode;l sim plex
[ 5] 袁亚湘. 非线性 优化计 算方 法 [ M ]. 北 京: 科学 出版 社, 2008.
[ 6] 运筹学 (修订版 ) [M ]. 北京: 清华大学出版社, 1990.
( 责任编辑 刘 舸 )
第 24卷 第 6期 V o .l 24 N o. 6
重 庆 理 工 大 学 学 报 ( 自然科学 ) Journa l of Chongqing U niversity of T echnology( N atural Science)
2010年 6月 Jun. 2010
*
求解有约束非线性规划问题的新算法
x1 = 0
x2 ! 2
23 + 3
24 =
2
& 190+
3
&
1 10
=
2.
1
z = 0+ 2. 14 = 19. 45 x2 = 2. 1近似等于真正的最优值 2. 121 32。
用 AMPL 或 Excel规划求解得到该问题的 精
确解是
x1 = 0 x2 = 2. 121 32 z* = 20. 25
3 结束语
表 3 新表 1
x1
21
22
23
24
s1
s1
3 - 8 - 6 0 [ 10] 1
1
23
0
1
1
1
1
0
1
z - 1 16 15 0 - 65 0 16
由新算法可以看出, 该算法只能保证局部 最 优解, 近似解 对于原 问题来 说可 能是不 可行的。 事实上, 近似模型可能给出不是原问题解空间 里 的其他点, 但是该算法却提供了一种求解非线 性 规划问题的新思路。
目前, 对求解非 线性规划问题已经有很多的 算法, 通常可分为间接算法和 直接算法。间接算 法通过处理从原问题中得到的若干个线性规划来 求解非线性问题, 而直接算法则直接处理原问题。 F rank和 W olfe曾于 1956 年提出了求解非线性规 划问题的算法 (简称为 F rank W o lfe方法 ), 此算法 的基本思想是: 在每次迭代中, 将目标函数 f ( x )线 性化, 解线性规划求出下降可行方向, 进而沿此方 向在可行域内作一维搜索, 然后对目标函数利用 一阶 T ay lor多项式展开线性逼近 f ( x )。本文介绍 的这种新算法则是从另外一个角度对此问题进行 求解 [ 1- 6] 。该算法主要是利用可分离函数将非线
k
f ( x ) ! f ( ak ) k
k= 1
k
x=
ak k
k= 1
其中: k 是关于第 k 个间断点的非负权值, 并且有
k
k = 1, k ∀0, k = 1, 2, k。
k= 1
满足以下 2个条件时, 这样近似是合理的: #
最多有 2个 k 是正的; ∃ 若 k 为正, 则仅有一个
邻近的 k + 1或者 k - 1可取正值。此 2个条件也可
22 + 16 23 + 81 24
同理有 g2 ( x2 ) ! 2 22 + 8 23 + 18 24。因而原问 题近似转化为求下列线性22 + 16 23 + 81 24 3x1 + 2 22 + 8 23 + 18 24 % 9
s. .t
21 + 22 + 23 + 24 = 1
24是进基变量, 由于 行的, 由单纯形方法中的 建立新表如表 4所示。
23是正的, 因此这是可 规则知 s1 将离基。再
表 4 新表 2
x1
21
22
23
24 3 /10 - 8 /10- 6 /10 0
23 - 3 /10 18 /10 16 /10 1
z 37/2 - 36 - 24 0
24
s1
中图分类号: O22
文献标识码: A
文章编号: 1674- 8425( 2010) 06- 0094- 03
N ew a lgorithm for solving constra ined nonlinear programm ing problem s
XU Yu sheng, DU Y ing ge, W ANG J ia jia
作为限制基的条件。
2 算法步骤及算例分析
2. 1 算法步骤 第 1步 将非线性规划问题通过可分离函数
转化为近似的线性规划问题。 第 2步 对第 1步所得的近似的线性规划问
题, 通过对 i 的值是否满足上述所提的限制基的 条件, 利用单纯形方法进行求解。若满足, 则所得 的单纯形表给出该问题的近似最优解; 否则, 转入 第 3步。
在区间上如何近似表达一元函数呢? 假设要 在区间 [ a, b ] 上近似 f ( x ), 定义 ak ( k = 1, 2, k ) 为 x 上的第 k 个间断点, 使得 a1 < a2 < < ak, a1 和 ak 恰好是指定区间的端点 a 和 b, 这样 f ( x )被 近似 (采用线性加权和法线性近似 )表示为
s. .t x1, x2 ∀ 0
首先考虑可分离函数
f1 (x 1 ) = x1 , g1 ( x1 ) = 3x 1 ,
f2 (x2 ) = x2 4 g2 ( x2 ) = 2x2 2
显然 f 1 ( x1 ), g1 (x 1 )一致都是线性的, 在这种 情况下, x 1 被看成是所要的变量之一。现在考 虑 f2 ( x2 )和 g2 (x 2 ), 将其变为线性的。设置 4个间断 点: a2k = 0, 1, 2, 3, 分别对应 k = 1, 2, 3, 4。由于 x2 的值不能超过 3, 则可得表 1的情形。
表 1 x2 的值不能超过 3时的情形
k
a 2k
f2 ( a2k ) = a2k4
g2 ( a2k ) = 2a2k2
1
0
0
0
2
1
1
2
3
2
16
8
4
3
81
18
故有
f2 ( x2 ) ! 21f 2 ( a21 ) + 22f 2 ( a22 ) + 23 f2 ( a23 ) + 24f 2 ( a24 ) ! 0 & 21 + 1 & 22 + 16 & 23 + 81 24 =
显然 线 性 函 数 g ( x1, x2 xn ) = a1 x1 +
* 收稿日期: 2009- 12- 18 基金项目: 陕西省教育厅专项 科研基金资助项目 ( 03 jk065); 西安建筑科技大学基础研究基金资助项目 ( 02BR01) 作者简介: 徐裕生 ( 1950 ) , 男, 安徽怀远人, 教授, 主要从事最优化理论与算法研究。
x1 ∀0, 2k ∀ 0, ( k = 1, 2, 3, 4)
其中 2k的值必须满足限制基条件。表 2为初表, 其中 s1 为松弛变量。
96
重庆理工大学学报
表 2 初表
x1
21
22
23
24
s1
s1
3
0
2
8 18 1
9
21
0
1