运筹学讲义 ∫分派工人H从事工作 0,否则, ,i,j=1,2 则可建立0-1规划 nax二 Cix s.∑x1=1=12…,n x x=0,1,=12,…,n 注:分派问题实际上是一种特殊形式的运输问题(见§1.1例3) 例4(设施选址问题, facility location) 原有电厂 年用煤量年固定费用 今有m座煤矿 b 内1 2 h2 |要新建一个 年产量a单位运费40>厂址有个b b 问:应如何选址设厂并组织运输,才能既满足新旧电厂的用煤量,又使得年运行费用(包括固定 费用和运费)最少? ∫,厂址j被选中 解:令y-0,否则, x=每年煤矿i运往电厂j的煤的数量,i=1,2,…,m,j=1,2,…,n, 则可建立整数规划运 筹 学 讲 义 3 i j n W J x i j ij , , 1,2, , 0, , 1, , =     = 否则 分派工人 从事工作 ， 则可建立 0-1 规划            = = = = = = =    = = = = x i j n x j n st x i n z c x ij m i ij n j ij m i n j ij ij 0,1, , 1,2, , 1, 1,2, , . . 1, 1,2, , max 1 1 1 1    .▌ 注：分派问题实际上是一种特殊形式的运输问题（见§1.1 例 3）. 例 4（设施选址问题，facility location） 问：应如何选址设厂并组织运输，才能既满足新旧电厂的用煤量，又使得年运行费用（包括固定 费用和运费）最少？ 解：令 j n j y j , 1,2, , 0, 1, =     = 否则， 厂址 被选中， ， xij = 每年煤矿 i 运往电厂 j 的煤的数量， i = 1,2,  ,m, j = 1,2,  ,n ， 则可建立整数规划