Chapter 7 Network Optimization Problems 7.1 Minimun- Cost flow Problen网络最优化间题 最小费用流问题一术语P244 最小费用流问题的构成(网络表示): 1节点 nodes)(供应点净流量为正、需求点净流量为负 转运点净流量为零) 2弧(arcs):可行的运输线路(节点j>节点j), 经常有最大流量(容量)的限制 3决策变量:x;-通过弧(节点>节点j)的流量 RuC Information School, Ye Xiang 2007
Chapter 7 Network Optimization Problems 网络最优化问题 RUC Information School ,Ye Xiang ,2007 7. 1 Minimum-Cost Flow Problem 最小费用流问题－术语 P244 最小费用流问题的构成（网络表示）： 1.节点(nodes)（供应点-净流量为正 、需求点-净流量为负 、转运点-净流量为零 ） 2.弧（arcs）：可行的运输线路（节点i->节点j）， 经常有最大流量（容量）的限制 3.决策变量：xij－通过弧（节点i->节点j）的流量
Chapter 7 Network Optimization Problems Assumptions of Minimum Cost Flow Problem 最小费用流问题的假设P244 网络最优化问题 1.至少一个供应点 2.至少一个需求点 3.剩下都是转运点 通过弧的流只允许沿着箭头方向流动,通过弧的最大 流量取决于该弧的容量 5.网络中有足够的弧提供足够容量,使得所有在供应点 中产生的流都能够到达需求点 6.在流的单位成本已知前提下,通过每一条弧的流的成 本和流量成正比(目标函数是线性的) 7.最小费用流问题的目标在满足给定需求条件下,使得 通过网络配送的总成本最小(或总利润最大化) RuC Information School, Ye Xiang 2007
Chapter 7 Network Optimization Problems 网络最优化问题 RUC Information School ,Ye Xiang ,2007 Assumptions of Minimum Cost Flow Problem 最小费用流问题的假设 P244 1. 至少一个供应点 2. 至少一个需求点 3. 剩下都是转运点 4. 通过弧的流只允许沿着箭头方向流动，通过弧的最大 流量取决于该弧的容量 5. 网络中有足够的弧提供足够容量，使得所有在供应点 中产生的流都能够到达需求点 6. 在流的单位成本已知前提下，通过每一条弧的流的成 本和流量成正比（目标函数是线性的） 7. 最小费用流问题的目标在满足给定需求条件下，使得 通过网络配送的总成本最小（或总利润最大化）
Chapter 7 Network Optimization Problems Characteristic of solution 网络最优化问题 解的特征P244 具有可行解的特征:在以上的假设下,当且仅 当供应点所提供的流量总和等于需求点所需要 的流量总和时,最小费用流问题有可行解(平 衡条件)。 具有整数解的特征:只要其所有的供应量、需 求量和弧的容量都是整数值,那么任何最小费 用流问题的可行解就一定有所有流量都是整数 的最优解。 RuC Information School, Ye Xiang 2007
Chapter 7 Network Optimization Problems 网络最优化问题 RUC Information School ,Ye Xiang ,2007 Characteristic of Solution 解的特征 P244 ▪ 具有可行解的特征：在以上的假设下，当且仅 当供应点所提供的流量总和等于需求点所需要 的流量总和时，最小费用流问题有可行解（平 衡条件） 。 ▪ 具有整数解的特征：只要其所有的供应量、需 求量和弧的容量都是整数值，那么任何最小费 用流问题的可行解就一定有所有流量都是整数 的最优解
Chapter 7 Network Optimization Problems 无限配送公司的最小费用流问题网络最优化问题 的线性规划数学模型(补充) 决策变量xn:通过弧(节点1到节点的流量 总运输成本最小化 Min cost=S700xmw+S300xm1DC+ S200xpCwI+$400 pC- w2+ $400F2-DC+S900xF2-w2 约束条件(节点净流量、弧的容量限制,非负) (由于80+70=60+90,即总供应=总需求,平衡) 供应点F1:xH1w1+xDc=80 供应点F2 e2 -dc +m2- w2=70 转运点DC:xpcw1+xpCw2-(xm1DC+x2Dc)=0 需求点W1 tx DC-W1 需求点W2:xDCw2+x2w2=90 弧的容量限制:xH1DC、xpCw1、xDcw2、xpDc≤50 且 x:≥0 RuC Information School, Ye Xiang 2007
Chapter 7 Network Optimization Problems 网络最优化问题 RUC Information School ,Ye Xiang ,2007 无限配送公司的最小费用流问题 的线性规划数学模型（补充） 决策变量xij：通过弧(节点i到节点j)的流量 总运输成本 最小化 Min Cost = $700xF1-W1 + $300xF1-DC + $200xDC-W1 + $400xDC-W2 + $400xF2-DC + $900xF2-W2 约束条件(节点净流量、弧的容量限制，非负） （由于80＋70＝60＋90，即总供应＝总需求，平衡） 供应点 F1: xF1-W1 + xF1-DC = 80 供应点 F2: xF2-DC + xF2-W2 = 70 转运点 DC: xDC-W1 + xDC-W2 - (xF1-DC + xF2-DC ) = 0 需求点 W1: xF1-W1 + xDC-W1 = 60 需求点 W2: xDC-W2 + xF2-W2 = 90 弧的容量限制： xF1-DC 、 xDC-W1 、 xDC-W2 、xF2-DC 50 且 xij 0
无限配送公司的最小费用流问题 Chapter 7 的电子表格模型P245 Network Optimization Problems 网络最优化问题 列出了网络中的弧和各弧所对应的容量、单位流量成本 决策变量(可变单元格)为通过弧的流量x 目标单元格:计算流量的总成本 每个节点的净流量(总流出一总流入)为约束条件。供应点的净 流量为正,需求点的净流量为负,而转运点的净流量为0 窍门:用两个SUMF函数的差来计算每个节点的净流量(快捷且 不容易犯错) Distribution unlimited co minimum cost Flow Problem 2P246无限配送公司的最小费用流问题 决策变量:通过孤节点到节点的流量 从 流量对 容量单位成本 节点净流量供应/需求 678 F1 5700 80 80 7 F1DC 300 70 70 0000 <=50 5200 DC 0 DCW2 50 400 F2 5400 W2 -9 11F2W2 590 总成本5110000 RuC Information School, Ye Xiang 2007
Chapter 7 Network Optimization Problems 网络最优化问题 RUC Information School ,Ye Xiang ,2007 无限配送公司的最小费用流问题 的电子表格模型P245 • 列出了网络中的弧和各弧所对应的容量、单位流量成本 • 决策变量（可变单元格）为通过弧的流量xij • 目标单元格：计算流量的总成本 • 每个节点的净流量（总流出－总流入）为约束条件。供应点的净 流量为正，需求点的净流量为负，而转运点的净流量为0 • 窍门：用两个SUMIF函数的差来计算每个节点的净流量（快捷且 不容易犯错）