于一组等式和不等式条件的最优化问题。许多经济、管理、交通、通信和工程中
的最优化问题都可以用整数规划来建模。
整数规划的历史可以追溯到 20 世纪 50 年代,运筹学创始人和线性规划单纯
型算法发明者 Dantzig 首先发现可以用 0-1 变量来刻画最优化模型中的固定费用、
变量上界、非凸分片线性函数等。他和Fulkerson及Johnson对旅行售货员问题(TSP)
的研究成为后来的分支——割方法和现代混合整数规划算法的开端。1958 年,
Gomory发现了第一个一般线性整数规划的收敛算法——割平面方法。随着整数规
划理论和算法的发展,整数规划已成为最广泛的最优化方法之一,特别是近年来
整数规划算法技术和软件系统(如 CPLEX)的发展和推广,整数规划在生产企业、
服务、运营管理、交通、通信等领域得到了极大的应用和发展。
整数规划(IP)和混合整数规划(MIP)问题是当今国际上最优决策与应用领域里
的一个极为重要的分支[1~5]
,因此如何求解IP和MIP问题是一个重要的研究领域。由于问题的可行解区域为离散点,所以一般不能用连续区域的求解算法,而只能
用特殊方法求解,因此这方面的研究非常困难。随着计算技术的快速发展,人们
已研究出许多快速求解非整数规划的算法,如变尺度法、内点法、罚函数法、信
赖域法等[1]
,这些算法具有良好的收敛性和收敛速度快等特点,可用于大规模问
题的求解,但遗憾的是不能将这些方法用于求解 IP 和MIP 问题。然而,如果我们
能将IP和MIP转化成等价的非整数规划问题(NIP),便可以使用这些方法来求解,
显然这是非常有意义的工作。如文献[4]对0-1 整数规划的转化做了这方面的工作,
文献[5]研究了线性 0-1 整数规划的转化并给出了一个代数求解算法,但这方面研
国内外还很少,并未引起人们的重视。
1.2.2整数规划问题的挑战性[6]
很多整数规划问题看上去很简单,数学模型也不复杂,如 0-1 背包问题,最
大割问题等,但求解这类问题其实非常困难。绝大部分整数规划问题的可行域都
只有有限多个可行点,一个简单幼稚的想法是枚举所有的可行点。设X = {0,1}�是
某问题的可行域,计算每个可行点的目标函数值所需的基本运算次数是常数。假
设有一个超级计算机,其每秒基本运算次数是 1 亿次。则计算机通过枚举 X 计算
问题的最优解所需时间是下列时间的常数倍:
n = 30, |X| = 230 ≈ 109, 10s
n = 60, |X| = 260 ≈ 1018, 360y
n = 100, |X| = 2100 ≈ 1030, 4 × 1014y
我们看到,文数n 每增加1,则可行点个数增加 1倍,即可行点的个数随着 n
成指数增长。故完全枚举法只适用于文数很小的问题,对一般整数规划问题是行
不通的。大部分整数规划问题的困难在于:我们本质上只能使用枚举法或隐枚举
法的思想来求解问题的最优解,故当问题的规模越来越大时,算法的计算时间急
剧增加。一个朴素的想法是“四舍五入”:求解相应的连续优化问题(丢掉整数约
束),然后对求得的解进行四舍五入,得到一个整数解。这个方法有两个问题:(1)
一般很难通过四舍五入得到一个满足约束条件的可行解;(2)即使求得一个可行
解,其质量往往很差,即可能离最优解的距离很远,甚至和随机产生的可行解差
不多。
尽管整数规划的研究有了很大的进展,许多原来不能解决的大规模整数规划
问题现在可以在合理的时间内使用新的算法和更快速的计算机解决。然而,由于
上一篇:关系代数在数据集成中的应用+文献综述
下一篇:凸分析及其在经济学中的应用+文献综述

高中不等式的教学和解题研究

元认知和自我效能感训练...

变式教学在中学数学的应...

中韩小学数学教材文本结...

调和函数的性质和应用

投资的收益和风险

捕获再捕获的认识和应用

10万元能开儿童乐园吗,我...

承德市事业单位档案管理...

医院财务风险因素分析及管理措施【2367字】

公寓空调设计任务书

志愿者活动的调查问卷表

国内外图像分割技术研究现状

AT89C52单片机的超声波测距...

C#学校科研管理系统的设计

神经外科重症监护病房患...

中国学术生态细节考察《...