© 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
第 17 卷 第 3 期
Vol. 17 No. 3
控 制 与 决 策
Control and D ecision
2002 年 5 月
M ay 2002
文章编号: 100120920
(
2002
)
0320310205
一种求解整数规划与
混合整数规划非线性罚函数方法
孟志青
1
, 胡奇英
1
, 杨晓琪
2
(
1. 西安电子科技大学 经济管理学院, 陕西 西安 710071; 2. 香港理工大学 应用数学系, 香港
)
摘 要: 证明了任何一个变量有界的整数规划问题
(
IP
)
和混合整数规划问题
(
M IP
)
都可以转化为一个
等价的非整数
(
或连续化
)
规划问题
(
N IP
)
, 并给出一个用非线性精确罚函数法来求解该等价
N IP
的方
法, 从而达到求解
IP
或
M IP
的目的, 数值实验表明了算法的可行性。该方法可广泛用于各应用领域里
IP
和
M IP
的求解, 特别是为非线性
IP
和
M IP
问题提供了一条通用的求解途径, 对解决许多实际优化
问题具有重要意义。
关键词: 整数规划; 混合整数规划; 非整数规划; 非线性罚函数
中图分类号:
O
122. 2 文献标识码:
A
A method of non
-
linear penalty function
for solving integer programm ing and m ixed integer programm ing
M EN G Zh i
2
qing
1
,
H U Q i
2
y ing
1
,
YA N G X iao
2
qi
2
(
1.
School of Econom ics andM anagem ent
,
Xidian U niversity
,
Xi
′
an
710071,
China
; 2.
Depart
2
m ent of App lied M athem atics
,
The Hong Kong Polytechnic U niversity
,
Hong Kong
,
China
)
Abstract
:
Integer p rogramm ing
(
IP
)
p roblem s and m ixed integer programm ing
(
M IP
)
p roblem s w ith
bounded variables are transfo rm ed into equivalent non
2
integer
(
or continuous
)
p rogramm ing
(
N IP
)
p roblem s
.
IP and M IP are so lved by using non
2
linear exact penalty functions op tim ization w ith the
algorithm of gradient o r genetic algo rithm
.
Thism ethod can be used to so lve many p roblem s of IPs and
M IPs in the app lication fields
,
including p ractical p roblem s in the engineering and m anagem ent
.
N um erical examp les illustrate the feasibility of the algo rithm
.
Key words
:
integer p rogramm ing
;
m ixed integer programm ing
;
non
2
integer p rogramm ing
;
non
2
linear
penalty function
1
引 言
整数规划
(
IP
)
和混合整数规划
(
M IP
)
问题是当
今国际上最优决策与应用领域里的一个极为重要的
分支
[1～ 10 ]
, 机械、化工、计算机、经济、生物、军事、社
会等各领域里的许多优化问题均可归结为
IP
或
M IP
问题, 并且大多数的组合优化问题都可以写成
一 个
IP
或
M IP
问题
[1]
, 如背包问题、旅行商问题、
收稿日期: 2001204205; 修回日期: 2001206208
基金项目: 国家自然科学基金项目; 高等学校骨干教师资助项目
作者简介: 孟志青
(
1962—
)
, 男, 上海人, 副教授, 博士生, 从事最优决策与最优控制等研究; 胡奇英
(
1965—
)
, 男, 浙江诸暨
人, 教授, 博士生导师, 从事随机决策与随机控制等研究。
资源评论
