深圳大学管理学院：《运筹学》课程教学资源（案例PPT）随机型动态规划问题

消防站选址问题 0-1型整数规划 书本P156 5.11

消防站选址问题 0-1型整数规划 书本P156 5.11

A 8

1 2 3 4 1 2 6 9 10 8 7 3 4 6 11

无法显示该图片。 1当某防火区域由第j消防站负责时 定义x 0当某防火区域由第消防站负责时 j=1,2,3,4 无法显示该图片。 4 可列如下条件:mnz=yx 4

当某防火区域由第 消防站负责时 当某防火区域由第 消防站负责时 定义 j j j 1,2,3,4 0 1 x j      = = = = 4 4 min j j 可列如下条件： Z x

A 8

1 2 4 3 1 2 6 9 10 8 7 3 4 6 11

x1+x2≥1 x1≥1 x1+x2≥1 x,+x,+x1≥1 st x1+x4≥1 x1+x2+x4≥1 12+x4≥1 ①③④⑤⑥⑦⑧9⑩ x2+x1≥1

                 s.t. x1 + x4 1 x1 + x2 1 x1 1 x1 + x3 1 x3 1 x1 + x3 + x4 1 x1 + x2 + x4 1 x2 + x4 1 x4 1 x3 + x4 1 1 2 3 4 5 6 7 8 9 10 11

由2,4,9判定x1x2x4=1 试出(1,0,1,1)T为可行解 ·MinZ=3 增加约束条件x1X2x3X<=3 列表计算,只有(1,0,1,1)T可行,所 以可关闭消防站2

• 由2，4，9判定x1 x2 x4 = 1 • 试出（1，0，1，1）T为可行解 • MinZ=3 • 增加约束条件x1x2x3x4<=3 • 列表计算，只有（1，0，1，1）T可行，所 以可关闭消防站2

The end

The end