解先不考虑条件⑤,即解相应的线性规划B,①~④ (见图5-2),得最优解x1=4.81,x2=1.82,z0=356 可见它不符合整数条件⑤。 这时z0是问题A的最优目标函数值z 的上界,记作z=z。 而在x≠=0,x2=0时, x1+/x 显然是问题A的一个整数可行解, 这时z=0,是z米的一个下界 记作z=0,即0≤z米≤356 7x1+20x2=70 C 012345678910
解 先不考虑条件⑤，即解相应的线性规划B,①～④ (见图5-2)，得最优解x1 =4.81，x2 =1.82，z0 =356 可见它不符合整数条件⑤。 这时z0是问题A的最优目标函数值z* 的上界，记作z0 = 。 而在x1 =0，x2 =0时， 显然是问题A的一个整数可行解， 这时z=0，是z*的一个下界， 记作 =0，即0≤z*≤356 。 zz z z z
分支定界法的解法 首先注意其中一个非整数变量的解,如x1,在问题B的 解中x1-=4.81。于是对原问题增加两个约束条件x1≤4, x1≥5 可将原问题分解为两个子问题B和B2(即两支), 可题B1问题B2 z1=349z2=341 x1=4.00|x1=5.00 x2=2.10x2=1.57 给每支增加一个约束条件,如图5-3所示。这并不影 响问题A的可行域,不考虑整数条件解问题B1和B2,称 此为第一次迭代。得到最优解为:
分支定界法的解法 • 首先注意其中一个非整数变量的解，如x1，在问题B的 解中x1 =4.81。于是对原问题增加两个约束条件x1≤4， x1≥5 • 可将原问题分解为两个子问题B1和B2 (即两支)， • 给每支增加一个约束条件，如图5-3所示。这并不影 响问题A的可行域，不考虑整数条件解问题B1和B2，称 此为第一次迭代。得到最优解为： 问题 B1 问题 B2 z1=349 x1=4.00 x2=2.10 z2=341 x1=5.00 x2=1.57
图5-3 X1≤4,x1=5 问题B1 1问题B2 4 0123456x
图 5 - 3 • x 1 ≤ 4 ， x 1 ≥ 5
·显然没有得到全部变量是整数的解。因 z1>z2,故将2改为349,那么必存在最 优整数解,得到z*,并且0≤z米≤349
• 显然没有得到全部变量是整数的解。因 z1＞z2，故将 改为349，那么必存在最 优整数解，得到z*，并且0≤z*≤349 z
继续对问题B和B2进行分解 因z1> 2 故先分解B为两支。增加条件 x2≤2者,称为问题B;增加条件x2≥3者称为 问题B4。在图5-3中再舍去x2>2与x2<3之间 的可行域, 再进行第二次迭代 问题B 问题B2 34z 0123456
继续对问题B1和B2进行分解 • 因z1＞z2，故先分解B1为两支。增加条件 x2≤2者，称为问题B3；增加条件x2≥3者称为 问题B4。在图5-3中再舍去x2＞2与x3＜3之间 的可行域， • 再进行第二次迭代