解 0—1 规划的隐枚举法

温柔似野鬼°
690次浏览
2021年02月19日 21:22
最佳经验
本文由作者推荐

-

2021年2月19日发(作者:我立足于美利坚合众国)


(5)



解


0


—


1


规划的隐枚举法



解


0


—


1


规划的隐枚举法有其独特的工作程序,具体过程如下。



a.



模型转化为求极小的问题



b.



变量替换。极小问 题模型的目标函数中所有变量系数为负的


0


—

< br>1


变量,可利用变量替换


x


k< /p>


=1


-


x


'


k


(


x


'


k


< /p>


是引入的新的


0


—


1


变量


)


,将目标函数中所有变量系 数化为正数。



c.


< /p>


目标函数中变量按系数大小排列,约束条件中变量排列顺序也相应调整。

< br>


d.



按目标函 数值由小到大的顺序依次排列可能的解,并予以可行性检验。



e.



发现求极小问题的最优解并停止。



f.



转化为原问题的最优解。



例


4


用隐枚举法求解下列

< p>
0


—


1


规划问题



Max Z=3


x


1


+


2


x


2< /p>


-


5


x


3


-


2


x


4

< p>
+


3


x


5



x


1


+


x



2


+



x


3


+


2


x


4


+



x


5


≤


4


7



x


1



+


3


x


3


-


4


x



4


+


3


x


5


≤


8


11


x


1


-

< br>6


x


2


+


3


x


4 < /p>


+


5


x


5


≥


3


x


j


=0, 1,


j


=1, 2, 3, 4, 5.



解:



①



转化为求极小的问题



Min Z=


-


3


x


1


-


2


x


2


+


5


x


3


+


2


x


4

< br>-


3


x


5



-



x


1


-



x



2


-



x


3


-


2


x


4


-



x


5


≥-


4


-


7


x


1




-


3


x


3


+


4


x



4


-


3


x


5


≥-


8


11



x


1


-


6


x


2


+


3


x


4 < /p>


+


5


x


5


≥


3

-


-


-


-


-


-


-


-