第八章整数规划 58.2整数规划解法概述(续) 、松弛: 问题(P),把约束条件放宽(删去某些约束)可得到松弛问题(P)。 设问题(P)是求mmn,那么,有下列性质: IS(P)三S(P)特别若(P)无可行解,则(P)无可行解; 2(P)最优值是(P)最优值f的一个下界,即f≤f 3若(P)的optx∈S(P.则是(P)的opt
第八章 整数规划 §8.2整数规划解法概述(续） ( ) . ~ ( ), ~ ) . ~ 3 ( ; ~ ( ) ~ ) ~ 2 ( ( ) ~ ), ~ 1 ( ) ( ( ) min, ~ ( ) ( ) P opt x S P x P opt P f P f f f S P S P P P P P P 若 的 则 是 的 最优值 是 最优值 的一个下界，即 特别若（ ）无可行解，则 无可行解； 设问题 是求 那么，有下列性质： 问题 ，把约束条件放宽 删去某些约束 可得到松弛问题（ ）。 二、松弛：
第八章整数规划 58.2整数规划解法概述(续) 剪枝 设问题(P)分解为子问题(P(P2)…(P各子间题(P)2i=12,…,m 记(P)的最优值f,(P)及(P)的最优值为f (P)及(P)最优目标值的上、下界为f,f,,f 1问题(P)分解之后的上下界问题: 0≥7(可计算,方27新/下界=m(1=12…m27= 子问题是原问题上增加约束得到的)
第八章 整数规划 §8.2整数规划解法概述(续） ( ) ~ | 1,2, , } ~ min{ ~ ~ ( ) ~ 1. ( ) ( ) ( ) , , , ) , ~ ( ) ,( ) ( , 1,2, , . ~ ( ) ( ),( ), ,( ), 1 2 子问题是原问题上增加约束得到的 可计算 ， 新 下界＝ 问题 分解之后的上下界问题： 及 最优目标值的上、下界为 记 的最优值 及 的最优值为 设问题 分解为子问题 各子问题（ ） 三、剪枝： f f f f f f j m f f P P P f f f f P f P P f P P P P P i m j j j j j j j j j j m j = = =
第八章整数规划 58.2整数规划解法概述(续) ∽可取各子问题P)可行解对应目标值。有 新的∫上界=min{f,f1,…,fn}≤f 2以下几种情况,不必粉解,即称剪枝: 计算整数规划问题常潲用逐步分解子问题的斌进行 1若(P)无可行解,即(P)=①,说明S(P)=Φ 在分解是增加约束,定子问题解集均为 若(P)的optx∈S(P); 当前=∫,=∫,再分解只能使目标值墩大 3∫≥∫,再分解只能使目标值墩
第八章 整数规划 §8.2整数规划解法概述(续） 再分解只能使目标值增大 。 当 前 再分解只能使目标值增大 。 若 的 在分解是增加约束，故肯定子问题解集均为 。 若 无可行解，即 说 明 计算整数规划问题常采用逐步分解子问题的方式进行。 以下几种情况，不必再分解，即称剪枝： 新 的 上 界 可取各子问题 可行解对应目标值。有 , ~ 3 , ( ); ~ ) . ~ 2 ( ) , ( ) , ~ ) ( ~ 1 ( 2. min{ , , , } ( ) 1 j j j j j j j j j j m j j j f f f f f P opt x S P P S P S P f f f f f f f f P = = = = =
第八章整数规划 §83整数规划的分枝定界法 设线性整数规划问题: mn f=C X s t AX=b ≥0 x,为整数,j=1,2,…,n minf=C7XA的松弛 (B) st.AX=b问题 X≥0标准LP
第八章 整数规划 §8.3整数规划的分枝定界法 = = = = = X LP st AX b f C X A B x j n X st AX b f C X A T j T 标准 问题 的松弛 为整数， 设线性整数规划问题： 0 . . min ( ) 1,2, , 0 . . min ( )
第八章整数规划 s83整数规划的分枝定界法(续) 分枝定界法:(一般步) 1°求解(B), i)若(B)无可行解,则停(剪枝)说明(4)无可行解 i)若(B)有最优解x,且x∈SA,则停(剪枝 得到(4)的解 i)若(B)有最优解x,而xgS(A),f=f(x 为(④)最优值的的下界,转2 2°找(A)最优值的一个下界:可取任一X∈SA,那么 f=f(x)
第八章 整数规划 §8.3整数规划的分枝定界法 （续） ( ) 2 ( ) , ( ) 2 ) ( ) , ( ), ( ) ( ) ) (B) , , ) ( ) ( ) 1 ( ), f f x A x S A iii B x x S A f f x A ii x x S i B A B A A = = 找 最优值的一个下界：可取任一 那么 为 最优值的的下界，转 若 有最优解 而 得到 的解。 若 有最优解 且 则停（剪枝） 若 无可行解，则停（剪枝）说明 无可行解； 求解 分枝定界法：（一般步）