三、线形整数规划习题（隐枚举法）
某长输管道泵站配有6台输油泵，串联使用。

现要求泵站工作点为Q=2000m 3
/h,H=550m.当输量Q=2000m 3
/h 时，各台泵的扬程及相应的电耗见下表：
试确定一个最优泵组合方案，使所耗的总功率最小。

解 ：该问题的数学模型如下：
6543211150110010201000530365m in x x x x x x s +++++=
⎩
⎨
⎧-==≥+++++611,0550
2002001801809060..654321j x x x x x x x t s j 按约束条件的系数由达到小的顺序将相应的变量排列起来：
6543213655301000102011001150m in x x x x x x s +++++=
⎩
⎨
⎧-==≥+++++611,0550
60901801802000200..123456j x x x x x x x t s j
用隐枚举法求解，步骤如下：
1. NFREE={+6}，FREE={5,4,3,2,1}，X=(0,0,0,0,0,1)T
,S=1150,R(X)=200<550,
X 不可行。

令S =+∞
2. NFREE={+6,+5}，FREE={4,3,2,1}，X=(0,0,0,0,1,1)T ,S=2250,R(X)=400<550,
X 不可行。

3. NFREE={+6,+5,+4},FREE={3,2,1},X=(0,0,0,1,1,1)T
,S=3270,R(X)=580>550, X 可行。

因S<S ,故令S =S=3270.
从这可知,每一个可行的泵组合中至少应有三台泵. 4. 因已得到可行解,故应从NFREE 中退出+4,则:
NFREE={+6,+5-4},FREE={3,2,1},X=(0,0,0,0,1,1)T ,S=2250, Bound=S -S=1020
5. 因C 3=1000<Bound,故将+3进入到NFREE:
NFREE={+6,+5,-4,+3},FREE={2,1},X=(0,0,1,0,1,1)T,S=3250,R(X)=580>550,
X可行。

因S<S,故令S-=S=3250.
6.因已得到可行解,故应从NFREE中退出+3,则:
NFREE={+6,+5,-4,-3},FREE={2,1},X=(0,0,0,0,1,1)T,S=2250, Bound=S-S=1000 7.因C2=530<Bound,故将+2进入到NFREE:
NFREE={+6,+5,-4,-3,+2},FREE={1},X=(0,1,0,0,1,1)T,S=2780,R(X)=490<550,
X不可行。

8.NFREE={+6,+5,-4,-3,+2,+1},FREE=Ф, X=(1,1,0,0,1,1)T, S=3145,R(X)=550=550, X可行。

因S<S,故令S=S=3145.
9.因已得到可行解,故应从NFREE中退出+5,因要满足三台泵的要求则:
NFREE={+6,-5,+4,+3}，FREE={2,1}，X=(0,0,1,1,0,1)T,S=3170>S,X不可行. 10.故应从NFREE中退出+3:
NFREE={+6,-5,+4,-3},FREE={2,1},X=(0,0,0,1,0,1)T,S=2170, Bound=S-S=1000 11.因C2=530<Bound,故将+2进入到NFREE:
NFREE={+6,-5,+4,-3,+2},FREE={1},X=(0,1,0,1,0,1)T,S=2900,R(X)=470<550,
X不可行.
12.NFREE={+6,-5,+4,-3,+2,+1}，FREE=Ф，X=(1,1,0,1,0,1)T,S=3265>S,
X不可行.
13.故应从NFREE中退出+4, 因要满足三台泵的要求:
NFREE={+6,-5,-4,+3,+2},FREE={1},X=(0,1,1,0,0,1)T,S=2680,R(X)=470<550,
X不可行.
14.NFREE={+6,-5,-4,+3,+2,+1},FREE=Ф，X=(1,1,1,0,0,1)T,S=3045,R(X)=530<550, X不可行.
故应从NFREE中退出+6, 因要满足三台泵的要求:
15.NFREE={-6,+5,+4,+3}，FREE={2,1}，X=(0,0,1,1,1,0)T,S=3120,R(X)=560>550,
X可行. 因S<S,故令S-=S=3120.
16.故应从NFREE中退出+3,
NFREE={-6,+5,+4,-3},FREE={2,1},X=(0,0,0,1,1,0)T,S=2120,
Bound=S-S=1000
17.因C2=530<Bound,故将+2进入到NFREE:
NFREE={-6,+5,+4,-3,+2},FREE={1},X=(0,1,0,1,1,0)T,S=2650,R(X)=470<550,
X不可行.
18.NFREE={-6,+5,+4,-3,+2,+1},FREE=Ф, X=(1,1,0,1,1,0)T,S=3015,R(X)=530<550, X不可行.
19.故应从NFREE中退出+4, 因要满足三台泵的要求:
NFREE={-6,+5,-4,+3,+2},FREE={1},X=(0,1,1,0,1,0)T,S=2630,R(X)=470<550,
X不可行.
20.NFREE={-6,+5,-4,+3,+2,+1}, FREE=Ф, X=(1,1,1,0,1,0)T,S=2995,R(X)=530<550, X不可行.
21.故应从NFREE中退出+4, 因要满足三台泵的要求:
NFREE={-6,-5,+4,+3,+2},FREE={1},X=(0,1,1,1,0,0)T,S=2550,R(X)=450<550,
X不可行.
22.NFREE={-6,-5,+4,+3,+2,+1},FREE=Ф, X=(1,1,1,1,0,0)T,S=2915,R(X)=510<550, X不可行.
综上:最优解为: X=(0,0,1,1,1,0)T S=3120。