2004信息《运筹学》期中复习 第7章网络最优化问题 1、最小费用流问题(决策变量:x1一弧(节点NM->V)上的流量 目标:MinC,约束:每个节点的净流量,弧的容量) 2、最大流问题(决策变量x一弧(节点V->V)上的流量 目标:MaxF,约束:转运点的净流量为0,弧的容量) 3、最短路问题(注意:虚拟起点和虚拟终点的应用)(决策变量 一弧(节点Ⅴ一>v)否走,目标:MinC,约束:每个节点的净流量) 要求:根据题目画网络图(确定网络图中的供应点 转运点和需求点) 重点:如何将以上三种写成相应的线性规划模型( 以P254图79为例子)、最短路问题的实际应用(设 备更新问题) RuC Information School, Ye Xiang, 2007,52004信息《运筹学》期中复习 RUC Information School ,Ye Xiang ,2007,5 第7章 网络最优化问题 1、最小费用流问题（决策变量：xij－弧（节点Vi－> Vj ）上的流量， 目标：Min C ，约束：每个节点的净流量，弧的容量） 2、最大流问题（决策变量：xij－弧（节点Vi－> Vj ）上的流量， 目标：Max F ，约束：转运点的净流量为0，弧的容量） 3、最短路问题（注意：虚拟起点和虚拟终点的应用） （决策变量： xij －弧（节点Vi－> Vj ）否走，目标：Min C，约束：每个节点的净流量） ➢ 要求：根据题目画网络图（确定网络图中的供应点 、转运点和需求点） ➢ 重点：如何将以上三种写成相应的线性规划模型（ 以P254图7.9为例子）、最短路问题的实际应用（设 备更新问题）