[管理学]运筹学课件 第四章整数规划清华大学出版社.ppt

OR3 OR3 第四章 整数规划 本章要求 理解整数规划的含义 掌握分枝定界法的思想和方法 掌握0-1变量的含义和用法 掌握指派问题的算法 4.1 整数规划问题的提出 决策问题中经常有整数要求，如人数、件数、机器台数、货物箱数……如何解决？四舍五入不行，枚举法太慢 问题分类：纯整数规划、混合整数规划、0-1整数规划 专门方法：分枝定界法、割平面法、隐枚举法、匈牙利法 例1（整数规划模型）p114 某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如下表： 4.2 整数规划图解法 图解法的启示 A（4.8，0）点是LP问题的可行解，不是IP问题的可行解，B（4，1）才是IP的最优解; 纯整数规划的可行解就是可行域中的整数点； 非整数点不是可行解，对于求解没有意义，故切割掉可行域中的非可行解，不妨碍整数规划问题的优化； IP问题的最优解不优于LP问题的最优解。 4.3 分枝定界法 思路：切割可行域，去掉非整数点。一次分枝变成两个可行域，分别求最优解。 分枝定界法的步骤： ①先不考虑整数约束，变成一般的LP问题，求其最优解，记为X*(0). ②若求得的最优解X*(0)刚好就是整数解，则该整数解就是原IP的最优解，否则，转入下一步。 ③对原问题进行分枝，寻求整数最优解。 选取非整数解X*(0)的一个非整数分量xi*＝bi，其小数部分为di，以该非整数分量的相邻整数bi－ di和bi－ di＋1为边界将原问题分枝为两个子问题，并抛弃这两个整数之间的非整数区域： ?在原LP模型中添加分枝约束xi≤ bi－ di,构成第一个子问题；?在在原LP模型中添加分枝约束xi≥ bi－ di＋1，构成第二个子问题。 ④对上面两个子问题按照LP方法求最优解。若某个子问题的解是整数解，则停止该子问题的分枝，并且把它的目标值与上一步求出的最优整数解相比较以决定取舍。 ⑤重复③④步直至获得原问题最优整数解为 止。 例题p116 例2. maxZ=40x1+90x2 9x1+7x2≤56 7x1+20x2 ≤70 x1，x2 ≥0且为整数 4.3 割平面法 基本思想：新增加一些线性(不等式）约束条件，称为割平面，去“切割”相应的LP的可行域，并使切掉部分都是非整数解，所有整数解都被保留下来。当这种割平面足够多时，使相应LP和原IP具有相同的最优解。那么，相应LP的最优解也就是原IP的最优解。 割平面法求解步骤 ①先不考虑整数约束，变成一般的LP问题，求其最优解，记为X*(0)。 ②若求得的最优解X*(0)刚好是整数解，则该整数解就是原IP的最优解，否则，转下步。 ③寻求割平面方程： ?从最优表中抄下非整数解的约束方程： ?将该约束方程所有系数和常数分解为整数和正分数之和； ?将整系数项归写于方程左边，真分数项写于右边； ? 考虑整数条件约束。以上方程左边为整数，右边为非正数，即方程右边≤0。这就是所求的割平面方程。 ④将割平面方程标准规范化，加到原最优表中，用对偶单纯形法求新的最优解。 ⑤重复第3，4步，直至获得原问题最优整数解为止。 例3p118 例3：求解整数规划： maxZ=x1+x2 -x1+x2≤1 3x1+x2 ≤ 4 x1,x2≥0,且为整数 解法如下： 1、先去掉整数约束条件，当成一般LP问题求解，得最优解：x1=3/4,x2=7/4,z=5/2. 最终单纯形表如下： 2、该解不是整数解，转入下一步； 3、?从最优表中抄下非整数解的约束方程： x1-1/4x3+1/4x4=3/4; x2+3/4x3+1/4x4=7/4 ?将该约束方程所有系数和常数分解为整数和正分数之和，并将整系数项归写于方程左边，真分数项写于右边； x1-x3=3/4-(3/4x3+1/4x4) x2-1=3/4-(3/4x3+1/4x4) ?考虑整数条件约束。以上方程左边为整数，右边为非正数，即方程右边≤0。这就是所求的割平面方程。即 3/4-(3/4x3+1/4x4) ≤0，即-3x3－x4 ≤-3 4、将割平面方程标准规范化，加到原最优表中。 4.4 0—1整数规划问题 某些特殊问题，只做是非选择，故变量设置简化为0或1，1代表选择，0代表不选择。 例3. 家乐福拟在某城市东、西、南三个区域建超市，各地区都有几个具体的地点可供选择。要求不超过总投资100万元的条件下，做出盈利最大的决策。 求解0—1规划的隐枚举法 隐枚举法：不需要列出所有组合，只需关心目标函数值得最优可行组合。按目标值从优到劣依次列出组合，