所代替,是和一般整数规划的约束条件形式一致的。在实际问题中,如果引入0-1变 量,就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中讨论了。我们 先介绍引入0-1变量的实际问题,再研究解法。 3.1引入0-1变量的实际问题 3.1.1投资场所的选定—相互排斥的计划 例4某公司拟在市东、西、南三区建立门市部。拟议中有7个位置(点) A(=1,2,…7)可供选择。规定 在东区。由A1,A2,A3三个点中至多选两个 在西区。由A4,A3两个点中至少选一个; 在南区,由A6,A1两个点中至少选一个。 如选用A点,设备投资估计为b元,每年可获利润估计为c1元,但投资总额不能 超过B元。问应选择哪几个点可使年利润为最大? 解题时先引入0-1变量x(=1,2,…,7) x=当4点被选中, i=1,2,…,7 0,当A点没被选中 于是问题可列写成: Max b.x. <B x1+x2+x3≤2 x4+x52 x6+x7≥1,x1=0或1 3.12相互排斥的约束条件 有两个相互排斥的约束条件 x1+3x2 为了统一在一个问题中,引入0-1变量y,则上述约束条件可改写为 5x,+4x,≤24+yM 7x1+3x2≤45+(1-y) 其中M是充分大的数。 约束条件 x1=0或500≤x1≤800 可改写为 500y≤x1≤800y V=-19- 所代替，是和一般整数规划的约束条件形式一致的。在实际问题中，如果引入 0 −1变 量，就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中讨论了。我们 先介绍引入0 −1变量的实际问题，再研究解法。 3.1 引入0 −1变量的实际问题 3.1.1 投资场所的选定——相互排斥的计划 例 4 某公司拟在市东、西、南三区建立门市部。拟议中有 7 个位置（点） A (i = 1,2,L,7) i 可供选择。规定 在东区。由 1 2 3 A , A , A 三个点中至多选两个； 在西区。由 4 5 A , A 两个点中至少选一个； 在南区，由 6 7 A , A 两个点中至少选一个。 如选用 Ai 点，设备投资估计为bi 元，每年可获利润估计为 i c 元，但投资总额不能 超过 B 元。问应选择哪几个点可使年利润为最大？ 解题时先引入0 −1变量 x (i =1,2,L,7) i 令 ⎩ ⎨ ⎧ = 0 . 1, 当 点没被选中 当 点被选中 ， ， i A i A i x i = 1,2,L,7 . 于是问题可列写成： i i i z ∑c x = = 7 1 Max ⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎨ ⎧ + ≥ = + ≥ + + ≤ ∑ ≤ = 1, 0 1 1 2 6 7 4 5 1 2 3 7 1 i 或 i i i x x x x x x x x b x B 3.1.2 相互排斥的约束条件 有两个相互排斥的约束条件 5 4 24 x1 + x2 ≤ 或 7 3 45 x1 + x2 ≤ 。 为了统一在一个问题中，引入0 −1变量 y ，则上述约束条件可改写为： ⎪ ⎩ ⎪ ⎨ ⎧ = + ≤ + − + ≤ + 0 1 7 3 45 (1 ) 5 4 24 1 2 1 2 y 或 x x y M x x yM 其中 M 是充分大的数。 约束条件 0 x1 = 或 500 800 ≤ x1 ≤ 可改写为 ⎩ ⎨ ⎧ = ≤ ≤ 0 1 500 800 1 y 或 y x y