用于求解0-1型整数规划问题的新算法研究

《用于求解0-1型整数规划问题的新算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第２１卷第５期运筹与管理Ｖｏｌ．２１，Ｎｏ．５２０１２年１０月ＯＰＥＲＡＴＩＯＮＳＲＥＳＥＡＲＣＨＡＮＤＭＡＮＡＧＥＭＥＮＴＳＣＩＥＮＣＥＯｃｔ．２０１２用于求解０－１型整数规划问题的新算法研究赵宁，　宓为建，　王东胜（上海海事大学，上海２０１３０６）摘要：本文针对０－１型整数规划问题的求解算法进行研究，在分析了常用典型算法的求解原理和过程的基础上，提出了一种新的算法———Ｃａｒｄｓ-ｆｌｉｐｐｉｎｇ算法。该算法在此类问题的计算上具有通用性，其可靠性与精度等效于枚举法，求解过程中无需遍历各中间解的目标值即可按照最优顺序

2、依次检验中间解，找到的第一个可行解即为最优解，因此求解效率较高。通过对该算法的数学证明以及大量的算例分析，证明了算法的有效性和实用性。关键词：运筹学；Ｃａｒｄｓ-ｆｌｉｐｐｉｎｇ算法；翻牌序列；０－１型整数规划中图分类号：Ｏ２２１．４　　　文章标识码：Ａ文章编号：１００７-３２２１（２０１２）０５-０１０７-０８ANewAlgorithmforZero-oneIntegerLinearProgrammingＺＨＡＯＮｉｎｇ，ＭＩＷｅｉ-ｊｉａｎ，ＷＡＮＧＤｏｎｇ-ｓｈｅｎｇ（LogisticsEngineeringSc

3、hool，ShanghaiMaritimeUniversity，Shanghai２０１３０６，China）Abstract：Ｔｈｉｓｐａｐｅｒｄｉｓｃｕｓｓｅｓｔｈｅｐｒｏｂｌｅｍｏｆｓｏｌｖｉｎｇｚｅｒｏ-ｏｎｅｉｎｔｅｇｅｒｌｉｎｅａｒｐｒｏｇｒａｍｍｉｎｇｍｏｄｅｌｓ．Ｂａｓｅｄｏｎｔｈｅａｎａｌｙｓｉｓｏｆｄｉｆｆｅｒｅｎｔｃｏｍｍｏｎｌｙｕｓｅｄａｌｇｏｒｉｔｈｍｓ，ｗｅｐｕｔｆｏｒｗａｒｄａｎｅｗａｌｇｏｒｉｔｈｍｎａｍｅｄｃａｒｄｓ-ｆｌｉｐｐｉｎｇａｌｇｏｒｉｔｈｍｗｈｉｃｈｄｅｍｏｎｓｔｒａｔｅｓｒｅ

4、ｌｉａｂｉｌｉｔｙａｎｄａｃｃｕｒａｃｙｅｑｕｉｖａｌｅｎｔｔｏｅｎｕｍｅｒａｔｉｏｎｍｅｔｈｏｄｓ．Ｔｈｅｃｏｒｒｅｃｔｎｅｓｓａｎｄｔｈｅｐｒａｃｔｉｃａ-ｂｉｌｉｔｙｏｆｔｈｅｍｅｔｈｏｄａｒｅｖｅｒｉｆｉｅｄｗｉｔｈｍａｔｈｅｍａｔｉｃａｌｐｒｏｏｆｓａｎｄａｇｒｅａｔｄｅａｌｏｆｅｘａｍｐｌｅｓ．Keywords：ｏｐｅｒａｔｉｏｎｒｅｓｅａｒｃｈ；ｃａｒｄｓ-ｆｌｉｐｐｉｎｇａｌｇｏｒｉｔｈｍ；ｆｌｉｐｓｅｒｉａｌｎｕｍｂｅｒ；ｚｅｒｏ-ｏｎｅｉｎｔｅｇｅｒｌｉｎｅａｒｐｒｏｇｒａｍｍｉｎｇ０　引言０－１规

5、划在整数规划中占有重要地位，一方面因为许多实际问题，例如指派问题、选地问题、送货问［１］题都可归结为此类规划。０－１变量作为逻辑变量常被用来表示系统是否处于某个待定状态，或者决策时是否取某个待定方案。求解０－１规划的常用方法是分支定界法，对各种特殊问题还有一些特殊方法，例如求解指派问题用匈牙利方法就比较方便。然而实际应用中决策模型求解规模都比较大，所以像分支［２！～４］定界法、目标排序法等传统的算法往往无法满足企业对求解速度的要求，因此，不少学者通过增加辅助决策变量和辅助约束等手段改造模型并编写专用算法求解模型，然而这

6、类算法往往只能得到较优解，其可靠性有待实际检验。本文提出了一种求解０－１型整数规划模型的新算法———Ｃａｒｄｓ-ｆｌｉｐｐｉｎｇ算法（简称ＣＦＡｌｇｏｒｉｔｈｍ），其可靠性等效于枚举法，且求解效率相对较高。１　求解０－１型整数规划的常用算法分析０－１型整数规划的数学模型可表示如下：收稿日期：２０１１-１２-１２基金项目：国家８６３计划重点项目（２００９ＡＡ０４３００１）；上海市教委项目（Ｊ５０６０４＆０９ＺＺ１６３）作者简介：赵宁（１９８１-），男，讲师，博士研究生。１０８运筹与管理　　　　　　　　　　　２０１２年第２

7、１卷n目标函数：ｍａｘ（orｍｉｎ）Z＝∑aixi（１）i＝１约束条件：n∑cjixi≤bj，　（j＝１，２，⋯，m）i＝１xi＝０or１，　（j＝１，２，⋯，n）（２）对于任意一个０－１问题，若其决策变量有n个，那么其解的个数就是２的n次方个，如图１所示。如果按照这些解的目标函数值从最优到最差排序，假设最优解出现在第i个，对于任意一种算法，为保证第i个解的最优性，则必须遍历目标更优的前i－１个解是不可行解。关键问题在于中间解的优越序列是未知的，因此传统算法在迭代过程中大量地检验第i个后面的非最优图１　n个决策变量对应

8、的解空间示意图解，导致计算规模极大，各算法的计算量分析如下：n（１）穷举法显然是要计算所有２个解的目标函数值，并一一进行约束检验，其计算量是最大的。［５］（２）过滤隐枚举法是以穷举法为基础，通过建立过滤条件而减少计算工作量。该算法首先用试算法找到一个可行解，求得初始目标函数Z０，接着使用建立辅助约束条件，若是求最大化则令目标函数方