运筹学__五章(整数规划).ppt

《运筹学__五章(整数规划).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、运筹学——管理科学与工程系经济与管理学院第五章整数规划5.1整数规划数学模型和解的特点5.2割平面法和分支定界法5.30-1整数规划5.4隐枚举法5.5匈牙利法7/21/20212浙江科技学院经济管理学院管工系本章学习要求熟悉分支定界法和割平面法的原理及其应用掌握求解0-1规划问题的隐枚举法掌握求解指派问题的匈牙利法7/21/20213浙江科技学院经济管理学院管工系5.1整数规划数学模型和解的特点整数规划的类型整数规划的数学模型实例整数规划解的特点7/21/20214浙江科技学院经济管理学院管工系1.整数线性规划（ILP）的类型纯ILP：Xj全

2、为整数混合ILP：部分Xj为整数0-1ILP：Xj为0或17/21/20215浙江科技学院经济管理学院管工系线性规划模型maxz=x1+4x2s.t.14x1+42x2≤196-x1+2x2≤5x1,x2≥0整数规划模型maxz=x1+4x2s.t.14x1+42x2≤196-x1+2x2≤5x1,x2≥0x1,x2为整数0123456784321A(2.6,3.8)B(5,3)2.整数线性规划（ILP）实例7/21/20216浙江科技学院经济管理学院管工系线性规划的最优解A(x1,x2)=(2.6,3.8)不是整数解，目标函数值为z=17.8

3、。整数规划的最优解B(x1,x2)=(5,3)目标函数值为z=17。线性规划最优解A(2.6,3.8)四舍五入得到的解为(3,4)，不是可行解；舍去尾数取整的解为(2,3)，目标函数值z=14。因此整数规划的最优解一般不能由线性规划的最优解通过简单的取整得到。0123456784321A(2.6,3.8)B(5,3)7/21/20217浙江科技学院经济管理学院管工系3.整数线性规划（ILP）解的特点ILP是其中LP的一个子问题，所有解也是LP的可行解，所以如果LP的最优解满足ILP的整数条件，则已得最优解。7/21/20218浙江科技学院经济管

4、理学院管工系5.2割平面法和分支定界法割平面法（Gomory法）分支定界法7/21/20219浙江科技学院经济管理学院管工系1.割平面法基本原理：根据单纯形法求得其松弛问题的最优解，若不满足整数条件，则由最优解中选取具有最大真分数部分的非整分量所在行构造割平面约束，将其加入原松弛问题中形成一个新的线性规划求解，逐渐缩小解的范围，又不去掉整数解，直至找到最优解为整数解结束。7/21/202110浙江科技学院经济管理学院管工系1.割平面法割平面束构造：设具有最大真分数部分的非整分量所在行为：将该约束方程所在系数和常数分解为整数N和正真分数f之和，即

5、：则该约束方程等价于：7/21/202111浙江科技学院经济管理学院管工系1.割平面法例：Cj1100CBXBbx1x2x3x4Θ0x3621100x4204501δj1100[][]35x1入x3出1x1311/21/200x4803-21δj01/2-1/20[][]68/3x2入x4出1x28/301-2/31/31x15/3105/6-1/6δj00-1/6-1/6由右边结果构造割平面束7/21/202112浙江科技学院经济管理学院管工系例（接上）：由上面结果构造割平面束cj11000CBXBbx1x2x3x4x51X15/3105/6

6、-1/601X28/301-2/31/300x5-2/300-5/6-5/61δj00-1/6-1/60θ--1/51/5-1X11100-111X216/50101-4/50x34/50011-6/5δj0000-1/5cj110000CBXBbx1x2x3x4x5x61X11100-1101X216/50101-4/500x34/50011-6/500x6-4/50000-4/51δj0000-1/501X10100-105/41X2401010-10X3200110-3/20x5100001-5/4δj00000-1/47/21/2021

7、13浙江科技学院经济管理学院管工系2.分支定界法原理：首先，不考虑变量的整数约束，求解松弛问题线性规划的最优解。如果线性规划的最优解恰好是整数解，则这个解就是整数规划的最优解。如果线性规划的最优解中至少有一个变量不是整数，把线性规划的可行域切割成两部分，分别求解两个线性规划的最优解。如果这两个线性规划的最优解还不是整数解，分别把每一个可行域再进行分割。这个过程，叫做“分支”。分支过程得到的整数解中，目标函数值最优的一个叫做整数规划目标函数值的“界”。分支过程中非整数的线性规划的最优解，如果目标函数值劣于或等于这个“界”，就停止继续分支。这个过程

8、，叫做“定界”。7/21/202114浙江科技学院经济管理学院管工系步骤：解整数规划问题（ILP）的松弛问题，结果可能有三种：松弛问题没有可行解，IL