线性整数规划习题(隐枚举法)

三、线形整数规划习题（隐枚举法）

某长输管道泵站配有6台输油泵，串联使用。现要求泵站工作点为Q=2000m/h,H=550m.当输量Q=2000m/h时，各台泵的扬程及相应的电耗见下表：

3

3

试确定一个最优泵组合方案，使所耗的总功率最小。 解 ：该问题的数学模型如下：

min s =365x 1+530x 2+1000x 3+1020x 4+1100x 5+1150x 6 ⎧60x 1+90x 2+180x 3+180x 4+200x 5+200x 6≥550

s . t . ⎨

x =0, 1j =1-6j ⎩

按约束条件的系数由达到小的顺序将相应的变量排列起来：

min s =1150x 1+1100x 2+1020x 3+1000x 4+530x 5+365x 6 ⎧200x 6+2000x 5+180x 4+180x 3+90x 2+60x 1≥550

s . t . ⎨

x =0, 1j =1-6j ⎩

用隐枚举法求解，步骤如下：

1. NFREE={+6}，FREE={5,4,3,2,1}，X=(0,0,0,0,0,1),S=1150,R(X)=200

X 不可行。令=+∞

2. NFREE={+6,+5}，FREE={4,3,2,1}，X=(0,0,0,0,1,1),S=2250,R(X)=400

T T

X 不可行。

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

从这可知, 每一个可行的泵组合中至少应有三台泵. 4. 因已得到可行解, 故应从NFREE 中退出+4,则:

NFREE={+6,+5-4},FREE={3,2,1},X=(0,0,0,0,1,1),S=2250, Bound=-S=1020

5. 因C 3=1000

T T

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

6. 因已得到可行解, 故应从NFREE 中退出+3,则:

NFREE={+6,+5,-4,-3},FREE={2,1},X=(0,0,0,0,1,1),S=2250, Bound=-S=1000 7. 因C 2=530

NFREE={+6,+5,-4,-3,+2},FREE={1},X=(0,1,0,0,1,1),S=2780,R(X)=490

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

9. 因已得到可行解, 故应从NFREE 中退出+5,因要满足三台泵的要求则:

NFREE={+6,-5,+4,+3}，FREE={2,1}，X=(0,0,1,1,0,1),S=3170>,X 不可行. 10. 故应从NFREE 中退出+3:

NFREE={+6,-5,+4,-3},FREE={2,1},X=(0,0,0,1,0,1),S=2170, Bound=-S=1000 11. 因C 2=530

NFREE={+6,-5,+4,-3,+2},FREE={1},X=(0,1,0,1,0,1),S=2900,R(X)=470

12. NFREE={+6,-5,+4,-3,+2,+1}，FREE=Ф，X=(1,1,0,1,0,1),S=3265>, X不可行.

13. 故应从NFREE 中退出+4, 因要满足三台泵的要求:

NFREE={+6,-5,-4,+3,+2},FREE={1},X=(0,1,1,0,0,1),S=2680,R(X)=470

14. NFREE={+6,-5,-4,+3,+2,+1},FREE=Ф，X=(1,1,1,0,0,1),S=3045,R(X)=530

故应从NFREE 中退出+6, 因要满足三台泵的要求:

15. NFREE={-6,+5,+4,+3}，FREE={2,1}，X=(0,0,1,1,1,0),S=3120,R(X)=560>550, X可行. 因S

-T

T T

T

T T

T T T T

-

T

NFREE={-6,+5,+4,-3},FREE={2,1},X=(0,0,0,1,1,0),S=2120, Bound=-S=1000

17. 因C 2=530

NFREE={-6,+5,+4,-3,+2},FREE={1},X=(0,1,0,1,1,0),S=2650,R(X)=470

18. NFREE={-6,+5,+4,-3,+2,+1},FREE=Ф, X=(1,1,0,1,1,0),S=3015,R(X)=530

19. 故应从NFREE 中退出+4, 因要满足三台泵的要求:

NFREE={-6,+5,-4,+3,+2},FREE={1},X=(0,1,1,0,1,0),S=2630,R(X)=470

20. NFREE={-6,+5,-4,+3,+2,+1}, FREE=Ф, X=(1,1,1,0,1,0),S=2995,R(X)=530

21. 故应从NFREE 中退出+4, 因要满足三台泵的要求:

NFREE={-6,-5,+4,+3,+2},FREE={1},X=(0,1,1,1,0,0),S=2550,R(X)=450

22. NFREE={-6,-5,+4,+3,+2,+1},FREE=Ф, X=(1,1,1,1,0,0),S=2915,R(X)=510

综上:最优解为: X=(0,0,1,1,1,0) S=3120

T

T T

T

T

T T

T