第8章 整数规划ppt课件.pptVIP

§4　整数规划的分枝定界法 (四)修改整数规划的最优目标函数的上下界。 经分析，将上界 =14.66修改为 =14.58，z=13。 (五)在线性规划2和线性规划3中选择一个上界最大的线性规划，即线性规 划3，进行分枝。 线性规划3分解为线性规划4和线性规划5，如下： 线性规划4： Max 2x1+3x2 s.t. 195x1+273x2≤1365 4x1+ 40x2≤140 x1 ≤4 x1≥ 3 x2 ≤2 x1,x2≥ 0 解得z4=14,x1=4,x2=2 线性规划5： Max 2x1+3x2 s.t. 195x1+273x2≤1365 4x1+ 40x2≤140 x1 ≤4 x1≥ 3 x2≥ 3 x1,x2≥ 0 无可行解 * §4　整数规划的分枝定界法 (六)进一步修改整数规划最优目标函数值z*的上下界。 从线性规划2，4，5中修改z*的上下界。分析后，可得=14， z=14。都 取线性规划2，4，5中的整数可行解的目标函数值的最大值。 性质2： 当整数规划的最优目标函数值z*的上界 等于其下界z 时，该整数规划的最优解已经被求出。这个整数规划的最优解 即为其目标函数值取此下界的对应线性规划的整数可行解。 * §4　整数规划的分枝定界法 用图8-2表示例9的求解过程与求解结果 * 线性规划1 Z1=14.66 X1=2.44 X2=3.26 z=13, =14.66 线性规划2 Z2=13.90 X1=2 X2=3.30 线性规划3 Z3=14.58 X1=3 X2=2.86 线性规划4 Z4=14.00 X1=4 X2=2 线性规划5 无可行解 X1≤2 X1≥3 X2≤2 X2≥3 z=13, =14.58 z=14, =14 图8-2 §4　整数规划的分枝定界法 * 从以上解题过程可得用分枝定界法求解目标函数值最大的整数规划的步骤，我们将求解的整数规划问题称为A，将与其相对应的线性规划问题称为B： 第一步：求解问题B，可得以下情况之一： 1.B没有可行解，则A也没有可行解，求解过程停止。 2.B有最优解，且符合问题A的整数条件，则B的最优解即为A的最优解，求解过程停止。 3.B有最优解，但不符合A的整数条件，记其目标函数值为z1。 第二步：确定A的最优目标函数值z*的上下界，其上界即为z1, =z1,再用观察法找到A的一个整数可行解，求其目标函数值作为z*的下界，记为z 。 第三步：判断 是否等于z 。若相等，则整数规划最优解即为其目标函数值等于z的A的那个整数可行解；否则进行第四步。 §4　整数规划的分枝定界法 * 第四步：在B的最优解中选一个最远离整数要求的变量，不妨设此变量为xj =bj ，以[bj]表示小于bj的最大整数，构造以下两个约束条件，并加入问题B，得到B的两个分枝B1和B2。 xj ≤[bj]和xj ≥ [bj]+1 第五步：求解B1和B2 。修改A问题的最优目标函数值z*的上下界， 和z 。 第六步：比较和剪枝。各分枝的最优目标函数值中若有小于z者，则剪掉这枝（用打Х表示），即以后不再考虑了。若大于 ，则不符合整数条件，则重复第三步至第六步，直至 =z，求出最优解为止。 对于求目标函数值最小的整数规划的求解步骤与上述步骤基本相似。 * 画个表格 管 理 运 筹 学 管 理 运 筹 学 管 理 运 筹 学 管 理 运 筹 学 管 理 运 筹 学 管 理 运 筹 学 管 理 运 筹 学 管 理 运 筹 学 管 理 运 筹 学 管 理 运 筹 学 管 理 运 筹 学 管