整数规划在实际中的应用
摘要： 主要介绍整数规划问题的数学模型、现行常用的求解方法。在对整数规划问题及其解法研究的基础上，介绍整数规划方法在制定科学的防灾预案中的应用。
关键词： 整数规划；分枝定界法；割平面法；0-1隐枚举法。
中图分类号：O22文献标识码：A文章编号：1671—7597（2011）0110123－01
1 整数规划及解法
在线性规划问题中，最优解的决策变量可能是非负的整数或小数。然而在一些问题中有时要求决策变量取整数值或部分要求整数，有这种要求的线性规划问题称为整数线性规划问题，简称整数规划（Integral Programming）。
整数规划问题数学模型的一般形式为
其中（i=1，2，⋯，n）为决策变量；为约束方程的系数；
（I=1，2，⋯，n）为目标函数的系数；（j=1，2，⋯，m）为约束方程的限值。 均为已知常数。
对有些整数规划问题可将其相应的线性规划问题的最优解“化整”。但这与原问题真正的最优解相比是有误差的，而且有时利用最优解“化整”的方法不能保证得到原问题的最优解。求解整数规划问题的常用方法有：分枝定界法、割平面法、隐枚举法和匈牙利法。
2 整数规划的应用
2.1 整数规划在制定防灾预案中的应用
例1：我国是世界上台风灾害最为严重的国家。近年来台风给我国东南沿海各省市造成极大损失，人民生命财产安全严重威胁，做好防台风灾害的工作是事关国家和人民生命安全的大事。某防台部门在制定进港避风船只的停靠预案时，遇到这样的情况：在某海港已停泊了10艘外轮，但还有20艘需要停泊这20艘中，50万吨级的2艘，10万吨级的3艘，5万吨级的10艘，其余小于1万吨级。现有空码头18个，其中50万吨级的4个，10万吨级的3个，10万吨级以下的11个。由于锚链桥上锚链泊位结构的限制，有如下规定：大级别的船只不可停小级别码头，小级别的船只可停大级别码头，1个50万吨的泊位可以停10万吨的2艘或10万艘以下的3艘。如何停靠可使避风船舶的总吨位最大?
这一问题就是如何将4类吨位的船只合理地停靠于三种码头。
设z为可停靠的避风船舶的总吨位；为第i类船只停靠到j种码头的数目（i=1，2，3，4；j=1，2，3）如表1所示：
表1
据问题的条件可得：
分析问题中的限制条件与决策变量间的关系：
这个整数规划问题的数学表达式为：
应用传统的求解方法不容易求得最优解，我们可用数学软件求得。
数学软件mathematic输入程序，运行结果为：
{185，{x11→2，x12→0，x13→0，x21→0，x22→3，x23→0，x31→1，x32→0，x33→9，x41→5，x42→0，x43→0}}
即最优整数解为：50万吨泊位停靠2艘50万吨级的船，1艘5万吨级的船，5艘1万吨级以下的船，10万吨泊位停靠10万吨级的船3艘，10万吨级以下的泊位停靠5万吨级的船9艘。避风船舶的总吨位最大为185万吨。
随着经济全球化的发展，面临的防灾环境越来越复杂，指挥员单凭经验难以做出最适当的决策，必须借助于定量方法和计算机技术的辅助。
参考文献：
[1]朱求长，运筹学及其应用[M].武汉：武汉大学出版社，2006.
[3]钱颂迪，运筹学[M].清华大学出版社，1990.
[4]程启月，作战指挥决策运筹分析[M].军事科学出版社，2004.
[5]郑国用，运筹学在消防部队决策指挥中的应用[J].北京教育学院学报，2006.（5）.
[6]刘来福，数学建模方法与分析[M].北京：机械工业出版社，2005.
[7]张最良，军事运筹学[M].北京：军事科学出版社，1994.
作者简介：
王丽，女，硕士，包头师范学院讲师，研究方向：金融数学。