运筹学 第04章 整数规划课件.ppt

《运筹学 第04章 整数规划课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运筹学第四章整数规划本章重点分枝定界法Gomory割平面法隐枚举法整数规划问题的提出线性规划问题中经常有整数要求，如人数、件数、机器台数、货物箱数……如何解决？四舍五入不行枚举法太慢提出了整数规划的概念整数规划的概念对于我们前面介绍的线性规划问题，若要求变量xj(j=1,2,…,n)取整数值时，则称之为纯整数规划若只要求一部分变量取整数值，则称之为混合整数规划对应整数规划的没有整数解要求的线性规划称之为该整数规划的松弛问题若变量只取0或1时，则称之为0-1规划整数规划的性质整数规划和线性规划的区别仅在于最后一个取整约束条件，因此，整数规划

2、的解集是其松弛问题解集的子集整数规划的最优解不会优于其松弛问题的最优解整数规划的解的个数一般是可数的整数规划的最优解不一定在其松弛问题可行域的极点上整数规划的模型整数规划(IntegerLinearProgramming，简记为ILP)一般可表示为整数规划的求解增加了对变量取“整”的限制，使得整数规划的求解难度比一般线性规划大大增加有两种方法求解整数规划分枝定界法Gomory割平面法分枝定界法原理设有极大化的整数规划问题(A)，用(B0)表示(A)的松弛问题求解(B0)，若其最优解是整解，则已得到(A)的最优解，否则(B0)的最优目标值必

3、是(A)的最优目标值Z*的上界而(A)的任意可行解的目标函数值必是Z*的一个下界（也可将-∞作为下界）分枝定界法就是将可行域分成子区域(称为分枝)，逐步增大下界(定界)，最终求出Z*的方法分枝定界法步骤(1)设有极大化的整数规划问题(A)，用(B0)表示(A)的松弛问题求解(B0)，可能产生下列情况之一(B0)没有可行解，这时A也没有可行解，停止(B0)有无界最优解，则A也是有无界最优解，停止(B0)有整数最优解，则B0的最优解即为A的最优解，停止(B0)有最优解，但不符合问题A的整数约束，记它的目标函数值为，进入下一步分枝定界法步骤(2

4、)在(B0)的最优解中任选一个取值不符合整数条件的变量xj，其值为βj，构造两个约束条件xj≤[βj]和xj≥[βj]+1，将这两个约束条件分别加入(B0)中，得到两个后继子规划(B1)和(B2)找出(A)的任一整的可行解，其目标函数值记作(也可取=-∞)，这时有分枝定界法步骤(3)对每一后继问题(Bi)，设其解为Xi若Xi全为整数，停止分枝，此时若对应目标值Zi＞，则令=Zi若Xi非整且Zi≤，停止分枝若Xi非整且Zi＞，则按上一步中的方式进行分枝当所有子问题均不能再分枝时，即为最优目标值Z*，对应的解即是最优解X*若(Bi)无可行解，

5、停止分枝示例(4.1-1)求解下述整数规划问题(A)示例(4.1-2)先用单纯形法求解(A)的松弛问题(B0)示例(4.1-3)得(B0)的最优表为630/1311020/131-7/131238/13101-7/1319/131-4662/13100-17/131-53/131得最优解X0=(4.81，1.82)T，Z0=35.6，此解不符合整数要求这里的Z0=35.6是问题(A)的一个上界，记作=Z0示例(4.1-4)在(B0)的最优解中任选一个取值非整的变量，比如我们选x01，对(B0)分别增加约束条件：x1≤[x01]=4，x1≥

6、[x01]+1=5，得到两个子问题(B1)和(B2)又x1=0，x2=0显然是A的一个可行解，对应的目标函数值Z=0是A的一个下界，记=0，因此有0≤Z*≤35.6示例(4.1-5)求解(B1)得最优表为41000121/100101/20-7/2053/10001-7/20-131/20-349/10000-9/20-17/20得最优解X1=(4，2.1)T，Z1=34.9，此解不符合整数要求示例(4.1-6)求解(B2)得最优表为51000-111/7011/709/725/700-20/71-131/7-239/700-9/70-5

7、3/7得最优解X2=(5，1.57)T，Z2=34.1，此解不符合整数要求示例(4.1-7)在(B1)中选x12进行分枝，即对(B1)分别增加约束条件：x2≤[x12]=2，x2≥[x12]+1=3，得到两个子问题(B3)和(B4)X1和X2均非整，且Z1＞、Z2＞，故下界不变，(B1)和(B2)可以进行分枝示例(4.1-8)求解(B3)得最优表为4100010201000160010-9-720001-7-20-340000-4-9得最优解X3=(4，2)T，Z3=34，此解符合整数要求示例(4.1-9)求解(B4)得最优表为10/71

8、001/7020/7301000-1155/7001-9/70-131/718/7000-1/71-20/7-229/7000-4/70-17/7得最优解X4=(1.43，3)T，Z4=32.