-

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

-

-

-

-

-

-

-

-