2. 340 B,,;x,=1.43,X,=3.00 327.14 再定界:340≤2≤341,并海B12剪枝。 (iv)对问题B2再进行分枝得问题B21和B2,它们的最优解为 B x1=544 Xn=1.00.z,,=308 B2无可行解。 将B21,B2剪杖 」是可以断定原问题的最优解为 4,x2=2,z=340 从以上鲜题过程可得用分枝定界法求解整数规划(最大化)问题的步骤为 开始,将要求解的整数规划问题称为问题A,将与它相应的线性规划问题称为问 题B (i)解问题B可能得到以下情况之一: (a)B没有可行解,这时A也没有可行解,则停止 (b)B有最优解,并符合问题A的整数条件,B的最优解即为A的最优解,则 停止 (c)B有最优解,但不符合问题A的整数条件,记它的目标函数值为z i)用观察法找问题A的一个整数可行解,般可取x;=0,j=1,...,n,试探, 求得其目标函数值,并记作z。以z表示问题A的最优目标函数值;这时有 进行迭代。 第一步:分枝,在B的最优解中仁选一个不符合整数条件的变量x,其值为b, 以[b]表示小于b,的最大整数。构造两个约束条件 x;≤[b;和x≥[b+1 将这两个约束条件,分别加入问题B,求两个后继规划问题B和B2。不考虑整数条件 求解这两个后继问题。 定界,以每个后继问题为一分枝标明求解的结果,与其它问题的解的结果中,找出 最优日标函数值最大者作为新的上界2。从已符合整数条件的各分支中,找出日标函数 值为最大者作为新的下界z,若无作用z不变。 第二步:比较与剪枝,各分枝的最优目标函数中若有小于z者,则剪揮这枝,即 以后不再考虑了。若大于z,且不符合整数条件,则重复第一步骤。一直到最后得到 z=z为止。得最优整数解x,j=1,...,n 30-1型整数规划 0-1型整数规划是整数规划中的特殊情形,它的变量x,仅取值0或1。这时x,称 为0-1变量,或称二进制变量。x仅取值0或1这个条件可由下述约束条件 0≤x;≤1,整数 所代替,是和一般整数规划的约束条件形式一致的。在实际问题中,如果引入0-1变 量,就可以把有寳和情况需要分别讨论的线性规划问题统一在一个问题中讨论了。我们 先介绍引入0-1变量的实际问题,再研究解法。 3.1引入0-1变量的实际问题 3.1.1投资场所的选定—相互排斥的计划 例4某公司拟在市东、西、南三区建立门市部。拟议中有7个位置(点) A 37)可供选择。规定 在东区。由A1,A2,A3三个点中至多选两个 在西区。由A,A3两个点中全少选一个; 在南区,由A,A,两个点中至少选一个。 如选用A点,设备投资估计为b元,每年可获利润估计为c,元,但投资总额不能 超过B元。问应选择哪几个点可使年利润为最人? 解题时先引入0-1变量x(i=1,2 令 1,当A点被选中, i=1,2,...,7 0,当A,点没被选中 于是问题可列写成: Max z X x1+x2+x2≤2 +x5≥1 +x7≥1,x=0或 3.1.2相互排斥的约束条件 有两个相互排压的约束条件 5x1+4x2≤24或7x1+3x2≤45。 为了统·在个问题中,引入0-1变量y,则上述约束条件可改写为: 5x1+4x2≤24+M 7x1+3x2≤45+(1-y)M y=0或1 其中M是充分大的数 约束条件 x1=0或500≤x1≤800 改写为 500y≤x1≤800y 如果有m个互相排斥的约束条件: 1x1+...+ a x ··,m1 为了保业这m个约束条件只有一个起作用,我们引入m个0-1变量y(=,2,...,m) 和个充分大的常数M,而下面这组m+1个约束条件 a11+...+anxn≤b+yMi=1,2,...,m y1+...+yn=m2-1 (2) 就合于上述的要求,这是因为,由于(2),m个y中只有一个能取0值,设y=0, 代入(1),就只有i=i"的约束条件起作用,而别的式子都是多余的 3.1.3关于固定费用的问题( Fixed Cost problem) 在讨论线性规划吋,有些问题是要求使成本为最小。那时总设固定成本为常数,并 在线性规划的模型中不必明显列出。但有些固定费用(固定成本)的问题不能用一般线 性规划来描述,但可改变为混合整数规划来解决,见下例。 例5某工厂为了生产某种产品,有几种不同的生产方式叮供选择,如选定的生产 方式投资高(选购自动化程度高的设备),由于产量大,因而分配到每件产品的变动成 本貮降低;反之,如选定的生产方式投资低,将来分配到每件产品的变动成本可能增加。 所以必须全面考虑。今设有三种方式可供选择,令 x;表示采用第j种方式时的产量 C,衣示采用第j种方式时每件产品的变动成本 k表示采用第j种方式时的固定成本 为了说明成本的特点,暂不考虑其它约束条件。采用各种生产方式的总成本分别为 当x:>0 1.2.3 当x:=0 在构成目标函数时,为了统一在一个问题中讨论,现引入0-1变量y,令 当采用第种作产方式,即x;>O (3) 0.当不采用第种生产方式,即xr=0时 于是目标函数 minz=(k1y1+c1x1)+(k2y2+c2x2)+(k2y3+c3x3) (3)式这个规定可表为下述3个线性约束条件 yE≤xsy l,2,3 其中E是一个充分小的正常数,M是个充分大的正常数。(4)式说明,当x>0时y 必须为1;当x;=0时只有y;为0时才有意义,所以(4)式完全可以代替(3)式 3.20-1型*数规划解法之一(过滤隐枚举法) 解0-1型整数规划最容易想到的方法,和一般整数规划的情形一样,就是穷举法: 即检査变量取值为0或1的钶种组合,比较目标函数值以求得最优解,这就需要检查 变量取值的2′′个组合。对于变量个数n较大(例如n>100),这几乎是不可能的。因 此常设计—些方法,只检查变量取值的组合的一部分,就能求到问题的最优解。这样的 方法称为隐枚举法( Implicit Enumeration),分枝定界法也是一种隐枚举汯。当然,对 有些问题隐枚举法并不适用,所以有时穷举法还是必要的。 下面举例说明一种解0-1型整数规划的隐枚举法。 例6Maxz=3x1-2x2+5x3 +2x 2 x1+4x,+x2≤4 +x,≤3 4x2+x3≤6 x1,x2,x3=0或1 求解思路及改进措施: (i)先试探性求一个可行解,易看出(x1,x2,x3)=(1,00满足约束条作,故为 个可行解,且z=3 (i)因为是求极大值问题,故求最优解时,凡是目标值z