6.5 0-1型整数规划【荐】.pptVIP

* §6.5 0-1型整数规划 0-1型整数规划是整数规划中的特殊情形,它的变量xi仅取值0或1.这时xi称为0-1变量. xi仅取值0或1这个条件可由下述约束条件: 所代替,是和一般整数规划的约束条件形式一致的. 6.5.1 0－1整数规划的实际问题 投资场所的选定 例1: 某公司拟在是东,西,南三区建立门市部.拟议中有7个位置(点)Ai(i=1,2,….,7)可供选择.规定 在东区,由A1,A2,A3三个点中至多选两个; 在西区,由A4,A5两个点中至少选一个; 在南区,由A6,A7两个点中至少选一个; 如选用Ai点,设备投资估计为bi元,每年可获利润估计为ci元,但投资总额不能超过B元.问应选择哪几个点可使年利润最大? 解:先引入xi(i=1,2,….,7) 于是 6.5.2 求解0－1整数规划的隐枚举法 隐枚举法的步骤： 1.找出任意一可行解，目标函数值为Z0 2.? 原问题求最大值时，则增加一个约束 当求最小值时，上式改为小于等于约束 3. 列出所有可能解，对每个可能解先检验式（*），若满足再检验其它约束，若不满足式（*），则认为不可行，若所有约束都满足，则认为此解是可行解，求出目标值 4. 目标函数值最大（最小）的解就是最优解 【例2】用隐枚举法求解下列BIP问题 【解】（1）不难看出，当所有变量等于0或1的任意组合时，第一个约束满足，说明第一个约束没有约束力，是多余的，从约束条件中去掉。还能通过观察得到X0＝(1，0，0，1)是一个可行解，目标值Z0=11是BIP问题的下界,增加下面约束 (2) 列出变量取值0和1的组合，共24＝16个，分别代入约束条件判断是否可行。首先判断式（3.9a）是否满足，如果满足，接下来判断其它约束，否则认为不可行，计算过程见表3－7所示。 　 × √ √ √ (1,1,1,1) 16 　 　 　 　 × (0,1,1,1) 8 　 　 　 × √ (1,1,1,0) 15 　 　 　 　 × (0,1,1,0) 7 13 √ √ √ √ (1,1,0,1) 14 　 　 　 　 × (0,1,0,1) 6 　 　 　 　 × (1,1,0,0) 13 　 　 　 　 × (0,1,0,0) 5 14 √ √ √ √ (1,0,1,1) 12 　 　 　 　 × (0,0,1,1) 4 　 　 　 　 × (1,0,1,0) 11 　 　 　 　 × (0,0,1,0) 3 11 √ √ √ √ (1,0,0,1) 10 　 　 　 　 × (0,0,0,1) 2 　 　 　 　 × (1,0,0,0) 9 　 　 　 　 × (0,0,0,0) 1 Zj 3.9d 3.9c 3.9b 3.9a Xj j Zj 3.9d 3.9c 3.9b 3.9a Xj j 表3－5 (3) 由表3-5知，BIP问题的最优解：X＝（1，0，1，1），最优值Z＝14 选择不同的初始可行解，计算量会不一样。一般地，当目标函数求最大值时，首先考虑目标函数系数最大的变量等于1。当目标函数求最小值时，先考虑目标函数系数最大的变量等于0。 在表3－7的计算过程中，当目标值等于14时，将其下界11改为14，可以减少计算量。 6.3.2 分枝－隐枚举法求解BIP问题 将分枝定界法与隐枚举法结合起来用，得到分枝－隐枚举法。计算步骤如下： （1）将BIP问题的目标函数的系数化为非负，如 当变量作了代换后，约束条件中的变量也相应作代换。 （3）求主枝：目标函数是max形式时令所有变量等于1，得到目标值的上界；目标函数是min形式时令所有变量等于0，得到目标值的下界；如果主枝的解满足所有约束条件则得到最优解，否则转下一步； （4）分枝与定界：从第一个变量开始依次取“1”或“0”，求极大值时其后面的变量等于“1”，求极小值时其后面的变量等于“0”，用分枝定界法有哪些信誉好的足球投注网站可行解和最优解。 分枝－隐枚举法是从非可行解中进行分枝有哪些信誉好的足球投注网站可行解，第（1）步到第（3）步用了隐枚举法的思路，第（4）步用了分枝定界法的思路。 (2)变量重新排序：变量依据目标函数系数值按升排序； 停止分枝和需要继续分枝的原则： （1）当某一子问题是可行解时则停止分枝并保留； （2）不是可行解但目标值劣于现有保留分枝的目标值时停止分枝并剪枝； （3）后续分枝变量无论取“1”或“0”都不能得到可行解时停止分枝并剪枝； （4）当某一子问题不可行