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