&2 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(在流 的单位成本已的前提下,通过得 一条孤的流的成事和流量成元比) Copyright2007c深圳大学管理学院运筹学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. (最小卖用流问题的目标是在满足给 定需求的条件下,使得通过网络袋 应的总成本最小[我通过这祥做使得 总利润最大化] Copyright2007c深圳大学管理学院运筹学22
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 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。(具有可行解的 特红:在以上假设下,当且仅当供应点所 提侯的流量总和等于需求点所需要的流量 总和时,最小费用流问题有可行解) Copyright2007c深圳大学管理学院运筹学23
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。(具有整数解的特征 只要其所有的应、需求初弧的容量都是整 数值,那么任何最小费用流问题的可行解就 定有所有流量都是整数的最优解 Copyright2007c深圳大学管理学院运筹学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. (具有整数解的特征： 只要其所有的供应、需求和弧的容量都是整 数值，那么任何最小费用流问题的可行解就 一定有所有流量都是整数的最优解)
&e Spreadsheet Model H 3 From To Ship Capacity Unit Cost Nodes Net Flow Supply/Demand W 700 50 300 70 6 DC 30 200 9 D22 50 < $400 30 s400 W2 W2 40 900 10 11 Total Cost $110,000T Net flow 4FSUMIF(From. 4. Ship)-SUMIF(To. 4. Ship) 5FSUMF(From, 5, Ship)-SUMIF(To. 5, Ship) 6=SUMIF(From. 6, Ship)SUMIF(To, 6, Ship) 7=SUMIF(From, 17, Ship)-SUMIF(To. I 7, Ship) 8=SUMIF(From 18, Ship)-SUMIF(To, 18, Ship) Copyright2007c深圳大学管理学院运筹学25
Copyright 2007 © 深圳大学管理学院 运筹学 25 Spreadsheet Model