[理学]第六章 网络优化.ppt

第六章 网络优化 网络的基本概念 网络最小费用流问题 网络最大流问题 最短路径问题 网络的基本概念 节点与（有向）边 每一条边和两个节点关联，一条边可以用两个节点的标号表示（i，j） 网络最小费用流问题 初始基础可行解—生成树 确定非基变量x24和x34 求x24的检验数z24-c24 圈法 求x34的检验数z34 -c34 圈法 变量x34进基，确定离基变量 确定非基变量x24和x56 计算x24和x56的检验数z24 -c24 、z56-c56 最优解 网络最大流问题 5 2 1 3 4 w1=4 w2=1 w3=8 w4=12 w5=0 c14=2 c12=3 c13=5 c43=4 c54=7 c23=6 c35=8 c25=1 w3-w5=8 w4-w3=4 w2-w5=1 w1-w2=3 检验数= w1-w3-c13=-9 检验数= w2-w3-c23=-13 检验数= w1-w4-c14=-10 检验数= w5-w4-c54=-19 最优解。x12=8, x25=5, x43=5, x35=1, min z=57 x14=5 x12=8 x43=5 x35=1 最小费用流问题在物流配送优化中的应用 一家公司在济南、成都和长沙设有3个生产厂，在北京、武汉、上海设有3个配送中心。 产品在哈尔滨、长春、呼和浩特、乌鲁木齐、兰州、西安、南京、南昌、拉萨、昆明、广州、海口等12个城市销售。 生产地所在的3个城市、配送中心所在的3个城市也同时销售这种产品。 生产地、配送中心和销售地的运输网络如下图所示。 生产厂 配送中心 海口 昆明 广州 南昌 上海 南京 武汉 长沙 西安 成都 兰州 北京 呼和浩特 长春 哈尔滨 济南 拉萨 乌鲁木齐 销售地 4500 1800 1500 1200 生产能力 合计 长沙 成都 济南 生产厂 18个城市的需求量（单位：吨）如下表: 50 30 450 220 10 250 440 330 120 需求量 乌鲁木齐 海口 广州 昆明 拉萨 南昌 南京 西安 兰州 城市 130 170 280 400 350 400 300 280 290 需求量 呼和浩特 长春 哈尔滨 上海 武汉 北京 长沙 成都 济南 城市 合计需求为4500吨。这些城市的净供求量以及城市之间的运输价格（单位：元/吨公里）如下表所示： 3个生产厂的生产能力（单位：吨）如下表: -50 -30 -450 -220 -10 -250 -440 -330 -120 供求量 R Q P O N M L K J 编号 乌鲁木齐 海口 广州 昆明 拉萨 南昌 南京 西安 兰州 城市 -130 -170 -280 -400 -350 -400 1500 1220 910 供求量 I H G F E D C B A 编号 呼和浩特 长春 哈尔滨 上海 武汉 北京 长沙 成都 济南 城市 bQ=-30 bD=-400 bF=-400 bC=1500 bP=-450 bB=1220 bE=-350 bK=-330 bN=-10 bH=-170 bG=-280 bR=-50 bA=910 bL=-440 bI=-130 bO=-220 bM=-250 bJ=-120 B C E D A F K J R N O Q P M L I G H 225 130 30 190 200 70 185 155 160 185 95 190 45 150 120 130 115 75 55 30 95 40 配送网络、城市的供应量和需求量、城市之间的运价 A bG=-280 45 城市及代码 供应/需求量 运价 这个问题的线性规划模型如下： min z=40xAD + 185xAE + 160xAF + 55xBE + 200xBN + 185xBO + 70xCE + 130xCO + 120xCP + 150xCQ + 190xDH + 30xDI + 190xKD + 95xEK + 155xEM + 30xFL+ 75xFM + 45xHG + 225xJR+ 130xKJ+ 115xMP + 95xPQ s.t. xAD+xAE+xAF=910 节点A（济南） xBE+xBN+xBO=1220 节点B（成都） xCE+xCO+xCP+xCQ=1500 节点C（长沙） -xAD-xKD+xDI+xDH=-400 节点D（北京） -xAE-xBE-xCE+xEK+xEM =-350 节点E（武汉） -xAF+xFL+xFM=-400 节点F（上海） -xHG=-280 节点G（哈尔滨） -xDH+xHG =-170 节点H（长春） -xDI=-130 节点I（呼和浩特） -xKJ+xJR=-120 节点J（