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

玛丽莲梦兔
515次浏览
2021年02月19日 21:22
最佳经验
本文由作者推荐

-

2021年2月19日发(作者：贺卡怎么做简单又漂亮)


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



某长输管 道泵站配有


6


台输油泵，


串联使用。< /p>


现要求泵站工作点为


Q=2000m


/h ,H=550m.


当输量


Q=2000m


/h


时，各台泵的扬程及相应的电耗见下表：



泵号



1


2


90


530


3


180


1000


4


180


1020


5


200


1100


6


200


1150


3


3


扬程（


m


）



60


功率（


km


）



365


试确定一个最优泵组合方案，使所耗的总功率最小。



解



：该问题的数学模型如下：



min< /p>


s



365


x< /p>


1



530


x< /p>


2



1000


x


3



1020


x


4



1100


x


5



1150

x


6




60


x


1



9 0


x


2



18 0


x


3



18 0


x


4



20 0


x


5



20 0


x


6



55 0


s


.


t


.< /p>




x



0


,


1


j

< p>


1



6


j



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



min


s

< br>


1150


x


1



1100


x


2



1020


x


3

< p>


1000


x


4



530


x


5



365


x


6




200


x


6



2000


x


5



180


x


4



180


x


3



90


x


2



60


x

< p>
1



550


s

< p>
.


t


.




x



0

,


1


j



1



6


j


< /p>



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



1.



NFREE={+6}


，


FREE={5,4,3,2,1}


，


X=(0,0,0,0,0,1)


,S=1150,R(X)=200 <550,


X


不可行。令


S


=+


∞



2.



NFREE={+6,+5}< /p>


，


FREE={4,3,2,1}


，


X=(0,0,0,0,1,1)


,S=2250,R(X)=40 0<550,


T


T


X


不可行。



3.


< p>
NFREE={+6,+5,+4},FREE={3,2,1},X=(0,0,0,1,1,1 )


,S=3270,R(X)=580>550,


X


可行。因


S<


S

,


故令


S


=S=3270.



从这可知


,


每一个可行的泵组合中至少应有三台泵


.


4.



因已得到可行解


,


故应从


NFREE


中退出< /p>


+4,


则


:


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


,S=2250,


Bound=


S


-S=1020


5.



因


C


3


=1000


故将


+3


进入到


NFREE:


T


T

-


-


-


-


-


-


-


-