8 Assumptions of a Minimum-Cost Flow Problem 6. The cost of the flow through each arc is proportional to the amount of that flow where the cost per unit flow is known。(在流 的单包厉已知的前提下,通过每 一条孤的流的成本和流量成五比) Copyrigh2007c深圳大学管理学院运筹学21
Copyright 2007 © 深圳大学管理学院 运筹学 21 Assumptions of a Minimum-Cost Flow Problem 6. The cost of the flow through each arc is proportional to the amount of that flow, where the cost per unit flow is known. (在流 的单位成本已知的前提下，通过每 一条弧的流的成本和流量成正比)
&2 Assumptions of a Minimum-Cost Flow Problem 7. The objective is to minimize the total cost of sending the available supply through the network to satisfy the given demand.(An alternative objective is to maximize the total profit from doing this.) 最小费用流问题的国标是在滴足给 定需求的条件下,使得通过网络偿 应的总成布最小感通过这祥做使得 总利润最大化] Copyrigh2007c深圳大学管理学院运筹学2
Copyright 2007 © 深圳大学管理学院 运筹学 22 Assumptions of a Minimum-Cost Flow Problem 7. The objective is to minimize the total cost of sending the available supply through the network to satisfy the given demand. (An alternative objective is to maximize the total profit from doing this.) (最小费用流问题的目标是在满足给 定需求的条件下，使得通过网络供 应的总成本最小[或通过这样做使得 总利润最大化])
e Properties of Minimum-Cost Flow Problems e The Feasible Solutions Property Under the previous assumptions, a minimum-cost flow problem will have feasible solutions if and only if the sum of the supplies from its supply nodes equals the sum of the demands at its demand nodes。(具有可行解的 特红。在以上假设下,当且仅当偿应点所 提偿的流量总初等于需求点所需要的流量 总和时,最小费用流问题有可行解) Copyrigh2007c深圳大学管理学院运筹学3
Copyright 2007 © 深圳大学管理学院 运筹学 23 Properties of Minimum-Cost Flow Problems The Feasible Solutions Property: Under the previous assumptions, a minimum-cost flow problem will have feasible solutions if and only if the sum of the supplies from its supply nodes equals the sum of the demands at its demand nodes. (具有可行解的 特征：在以上假设下，当且仅当供应点所 提供的流量总和等于需求点所需要的流量 总和时，最小费用流问题有可行解)
e Properties of Minimum-Cost Flow Problems The Integer Solutions Property: As long as all the supplies, demands, and arc capacities have integer values, any minimum-cost flow problem with feasible solutions is guaranteed to have an optimal solution with integer values for all its flow quantities.,(具有整数解的特 只要其所有的侯应、求初孤的客量都是整 数值,那么任何最小费用流问题的可行解就 定有所有流量都是整数的最优) Copyrigh2007c深圳大学管理学院运筹学24
Copyright 2007 © 深圳大学管理学院 运筹学 24 Properties of Minimum-Cost Flow Problems The Integer Solutions Property: As long as all the supplies, demands, and arc capacities have integer values, any minimum-cost flow problem with feasible solutions is guaranteed to have an optimal solution with integer values for all its flow quantities. (具有整数解的特征： 只要其所有的供应、需求和弧的容量都是整 数值，那么任何最小费用流问题的可行解就 一定有所有流量都是整数的最优解)
: Spreadsheet Model B D F GHI 3 From To ship I Capacity Unit Cost Nodes Net Flow Supply/ Demand $700 DC 30 <≤ 50 200 069 0 50 =50 400 400 W2 90 $900 10 Total Cost $110,000 Net Flow 4=SUMIF(From, 14, Ship)-SUMIF(To, 4, Ship 5=SUMIF(From, 15, Ship)-SUMIF(To, 5, Ship) 6=SUMIF(From. 6. Ship)-SUMIF(To 6. Ship) 7=SUMIF(From, I7, Ship)-SUMIF(To, I 7 Ship) 8SUMIF(From, 8, Ship)-SUMIF(To, 18, Ship Copyrigh2007c深圳大学管理学院运筹学25
Copyright 2007 © 深圳大学管理学院 运筹学 25 Spreadsheet Model