整数线性规划问题解法探究.pdfVIP

2005 年第 4 期 湖 州 职 业 技 术 学 院 学 报 2005 年 12 月 　　 No . 4 . 2005 　　 J our nal of Huzhou Vocational and Technolo gical College 　　 　　　　　 Dec . 2005 整数线性规划问题解法探究 张 天 鹤 (无锡商业职业技术学院 基础部 ,无锡 2 14063) 摘要 :整数线性规划是线性规划问题的重要组成部分 , 由于整数线性规划问题还没有找到一种有效的解法 , 目前只能求解中小规 模的整数线性规划问题 ,而建立在线性规划理论基础上的整数解集筛选法是求解整数线性规划问题的一种比较简洁而有效的方 法 。 关键词 :整数线性规划 ;松弛问题 ;整数点;整数解集筛选法 中图分类号 :O22 1. 1 文献标识码 :A 文章编号 :1672 2388 (2005) 0074 03 On Solutions to Integer Linear Progra mming Z HAN G Tianhe ( Wuxi Vocational In stit ut e of Commercial Technology , Wuxi 2 14063 , China) Abstract :Int eger liner p rogramming i s an import ant p art of linear p rogramming . A s no effective solution to int eger linear p rogramming ha s been found , we only can solve such medium scale or small scale p roblems. Int egral solution s set screening , which i s ba sed on Linear Pro gramming Theory , i s a more convenient and effective solution to such p roblems. Key words :int eger linear p rogramming ; relaxation ; int eger point ; int egral solution set screening 1 引言 整数线性规划是线性规划问题的重要组成部分 , 自 1947 年美国数学家 G. B . Dantziy 提出线性规划 问题的单纯形方法以来 ,线性规划理论获得了迅速发展 。然而 , 由于整数线性规划问题还没有找到一种 有效的解法 , 以致整数线性规划问题仍是规划论中较弱的一个分支 , 目前 ,只能求解中小规模的整数线性 [ 1] ( P71) ( ) 规划问题 。尽管如此 , 自1959 年柯莫瑞 R . E. Gomory 提出割平面法后 ,整数线性规划问题逐渐成 为运筹学的一个独立分支 。现有的整数现行规划问题的解法有 :穷举变量法 、隐枚举法 、分支界定法 、割 平面法 、分解法 、群论方法 、动态规划法 、匈牙利法等 ,而建立在线性规划理论基础上的整数解集筛选法是 求解整数线性规划问题的一