Finite Mathematics Quiz: Network Flow And Optimization
8 questions · exam conditions
0:00
Network Flow And OptimizationQuestion 1 of 8

A manufacturing network has production facilities (nodes) connected by transportation links (edges) with daily shipping capacities. The current network configuration achieves optimal flow allocation. If production costs increase by 20% at facility B, but transportation costs remain constant, how should the optimal flow allocation be modified?

Reduce flow through node B proportionally to maintain cost balance across all facilities
The flow allocation should remain unchanged since network flow optimization depends only on edge capacities, not node costs
Redirect 20% of the flow from paths involving facility B to alternative paths
Recalculate the entire flow network using facility B's capacity reduced by 20%
← Back to quizzes

Finite Mathematics Quiz

Finite Mathematics Quiz: Network Flow And Optimization

Practice Network Flow And Optimization in Finite Mathematics with focused quiz questions that help you check what you know, review explanations, and build confidence with test-style prompts.

What this quiz covers

This quiz focuses on Network Flow And Optimization, giving you a quick way to practice the rules, question types, and explanations that matter most for Finite Mathematics.

How to use this quiz

Try each quiz question before looking at the correct answer. Use the explanations to review missed ideas, then come back to similar questions until the pattern feels familiar.

All questions

Question 1

A manufacturing network has production facilities (nodes) connected by transportation links (edges) with daily shipping capacities. The current network configuration achieves optimal flow allocation. If production costs increase by 20% at facility B, but transportation costs remain constant, how should the optimal flow allocation be modified?

  1. Reduce flow through node B proportionally to maintain cost balance across all facilities
  2. The flow allocation should remain unchanged since network flow optimization depends only on edge capacities, not node costs (correct answer)
  3. Redirect 20% of the flow from paths involving facility B to alternative paths
  4. Recalculate the entire flow network using facility B's capacity reduced by 20%
Explanation: Maximum flow problems in network optimization focus on edge capacities and network topology, not production costs at individual nodes. The optimal flow allocation maximizes throughput subject to capacity constraints, regardless of production costs at nodes. Node costs affect economic optimization but not the maximum flow solution. Choice A incorrectly applies cost considerations to flow optimization. Choice C arbitrarily assigns a 20% flow reduction. Choice D confuses production cost increases with capacity reductions.

Question 2

A distribution network uses dynamic routing where flow can be adjusted in real-time. The network has three parallel paths from source to sink with capacities 15, 12, and 8 units respectively. Due to reliability requirements, no single path can carry more than 60% of the total flow. If the system needs to route exactly 30 units while satisfying this constraint, what is the optimal distribution strategy?

  1. Route 18, 12, and 0 units through the three paths respectively, maximizing usage of highest-capacity paths
  2. Route 15, 12, and 3 units through the three paths respectively, using each path at maximum efficiency (correct answer)
  3. Route 12, 10, and 8 units through the three paths respectively, balancing load across all paths
  4. The routing is impossible since 60% of 30 units is 18, which exceeds the capacity of two paths
Explanation: With 30 total units and a 60% constraint, no path can carry more than 18 units. Path 1 (capacity 15) carries 15 units, Path 2 (capacity 12) carries 12 units, Path 3 (capacity 8) carries 3 units, totaling exactly 30 units. Each path operates within both its capacity and the 60% constraint (15 < 18, 12 < 18, 3 < 18). Choice A violates the constraint (18 > 60% of 30). Choice C doesn't utilize full capacity efficiently. Choice D incorrectly concludes impossibility.

Question 3

A supply chain network experiences a temporary shutdown of edge C→D, reducing its capacity from 12 to 0 units. The original maximum flow was 28 units. After implementing an augmenting path algorithm starting from the current flow state, the new maximum flow is found to be 22 units. What can be concluded about edge C→D's role in the original network?

  1. Edge C→D was carrying 12 units of flow, but alternative routing could accommodate 6 units
  2. Edge C→D was part of the minimum cut, and no alternative paths could compensate for its full capacity
  3. Edge C→D was carrying exactly 6 units of flow in the original maximum flow solution (correct answer)
  4. Edge C→D was a redundant edge since the flow decrease (6 units) is less than its capacity (12 units)
Explanation: When you encounter maximum flow problems with edge capacity changes, focus on the relationship between the capacity reduction and the actual flow decrease to determine how much flow was originally using that edge. The key insight is that when edge C→D's capacity drops from 12 to 0, the maximum flow decreases from 28 to 22 units—a reduction of exactly 6 units. This tells us that in the original maximum flow solution, exactly 6 units of flow were passing through edge C→D. When this edge becomes unavailable, those 6 units cannot be rerouted through alternative paths, causing the total flow to drop by precisely that amount. Looking at the wrong answers: Choice A incorrectly suggests that C→D was carrying 12 units (its full capacity) and that 6 units could be rerouted elsewhere. If this were true, the flow would have decreased by 6 units, but C→D would have been at full capacity. Choice B claims C→D was part of the minimum cut with no alternative routing possible. While the second part is correct (no alternative routing), this doesn't necessarily make it part of the minimum cut. Choice D incorrectly interprets the relationship between capacity and actual flow usage—the fact that the flow decrease (6) is less than capacity (12) doesn't make the edge redundant; it simply means the edge wasn't operating at full capacity. Remember: In flow network problems, when an edge's capacity is eliminated, the decrease in maximum flow equals exactly the amount of flow that was originally using that edge.

Question 4

In a transportation network, the minimum cut separating source S from sink T has a capacity of 42 units. Three edges cross this cut with capacities 18, 15, and 9 units respectively. If we want to increase the maximum flow by exactly 8 units using the minimum cost approach, and the costs to increase capacity by 1 unit are $300, $200, and $150 for these three edges respectively, what is the optimal strategy?

  1. Increase the first edge by 8 units at a total cost of $2,400
  2. Increase the second edge by 5 units and third edge by 3 units at a total cost of $1,450
  3. Increase the third edge capacity by 8 units at a total cost of $1,200 (correct answer)
  4. Increase the third edge by 8 units, but the actual flow increase will be less than 8 due to network constraints
Explanation: When you encounter transportation network problems involving minimum cuts and flow increases, remember that the max-flow min-cut theorem tells us the maximum flow equals the minimum cut capacity. Here, the current maximum flow is 42 units, determined by the bottleneck cut with total capacity 18 + 15 + 9 = 42. To increase maximum flow by exactly 8 units, you need to increase the minimum cut's total capacity by 8 units. Since this is the bottleneck, any capacity increase here directly translates to flow increase. The key insight is that you want to achieve this 8-unit increase at minimum cost. Looking at the costs per unit: Edge 1 costs $300/unit, Edge 2 costs $200/unit, and Edge 3 costs $150/unit. Since Edge 3 is cheapest, the optimal strategy is to increase its capacity by the full 8 units at a total cost of 8 × $150 = $1,200. This makes answer C correct. Answer A is wrong because using only the most expensive edge ($300/unit) gives the highest total cost of $2,400. Answer B is incorrect because the mixed approach of 5 units on Edge 2 and 3 units on Edge 3 costs (5 × $200) + (3 × $150) = $1,450, which is more expensive than using Edge 3 alone. Answer D incorrectly suggests the flow increase would be constrained by other network factors, but since we're told this is the minimum cut, increasing its capacity directly increases maximum flow. Study tip: Always identify the cheapest resource first when optimizing costs, and remember that increasing minimum cut capacity directly increases maximum flow in transportation networks.

Question 5

A shipping network has nodes representing cities and directed edges representing shipping routes with maximum daily capacity (in tons). The network has a source node S with outgoing capacities: S→A (15), S→B (20), S→C (10). All paths eventually lead to sink node T. If the maximum flow from S to T is 35 tons per day, and we increase the capacity of edge S→A from 15 to 25, what is the most likely explanation for why the maximum flow might remain at 35 tons?

  1. The bottleneck constraint occurs at intermediate edges between the cities and sink node T, not at the source edges (correct answer)
  2. The algorithm requires recalculation from scratch, so the previous flow value is temporarily maintained until optimization
  3. The increase in S→A capacity violates the conservation of flow principle at node A
  4. Maximum flow is determined by the sum of source capacities, which changed from 45 to 55 tons
Explanation: In network flow problems, the maximum flow is limited by the minimum cut in the network. If increasing the capacity of S→A doesn't change the maximum flow, it means the bottleneck (minimum cut) occurs elsewhere in the network, likely at edges closer to the sink T or at intermediate nodes. Choice B is wrong because algorithms give immediate results. Choice C is wrong because increasing capacity doesn't violate conservation. Choice D is wrong because maximum flow isn't simply the sum of source capacities—it depends on the entire network structure.

Question 6

In a flow network with source S and sink T, an engineer finds a valid flow ff with value V(f)=42V(f) = 42. In a separate analysis, a cut (VS,VT)(V_S, V_T) is found with capacity C(VS,VT)=42C(V_S, V_T) = 42. Based on the max-flow min-cut theorem, which of the following statements must be true?

  1. Every edge in the network must be saturated.
  2. The cut (VS,VT)(V_S, V_T) is the only minimum cut in the network.
  3. The flow ff is a maximum flow, and (VS,VT)(V_S, V_T) is a minimum cut. (correct answer)
  4. Any flow from S to T must have a value of exactly 42.
Explanation: The max-flow min-cut theorem states that the maximum value of an S-T flow is equal to the minimum capacity of an S-T cut. A key corollary is that for any flow ff and any cut (VS,VT)(V_S, V_T), the value of the flow is less than or equal to the capacity of the cut, i.e., V(f)≤C(VS,VT)V(f) \le C(V_S, V_T). Equality holds if and only if ff is a maximum flow and (VS,VT)(V_S, V_T) is a minimum cut. Since we are given that V(f)=C(VS,VT)=42V(f) = C(V_S, V_T) = 42, it must be that the flow is maximal and the cut is minimal.

Question 7

A company transports products from two factories, F1 and F2, to a market, T, via two intermediate warehouses, W1 and W2. Factory F1 can supply up to 300 units per week, and F2 can supply up to 400 units. The shipping links have the following weekly capacities: F1 to W1 is 200; F1 to W2 is 150; F2 to W1 is 180; F2 to W2 is 250; W1 to T is 400; W2 to T is 350. This system is modeled as a flow network with a source S connected to F1 and F2.

In the flow network model for this problem, what is the capacity of the cut that separates the factories and warehouses from the market, defined by the partition VS={S,F1,F2,W1,W2}V_S = \{S, F1, F2, W1, W2\} and VT={T}V_T = \{T\}?

  1. 380
  2. 700
  3. 750 (correct answer)
  4. 780
Explanation: The problem describes a flow network. The cut specified partitions the vertices into VS={S,F1,F2,W1,W2}V_S = \{S, F1, F2, W1, W2\} and VT={T}V_T = \{T\}. The capacity of this cut is the sum of the capacities of all edges that start in VSV_S and end in VTV_T. The only edges that fit this description are those connecting the warehouses to the market T.
  • Edge from W1 to T has capacity 400.
  • Edge from W2 to T has capacity 350. The capacity of the cut is the sum of these capacities: 400+350=750400 + 350 = 750. The factory production limits and the capacities from factories to warehouses do not cross this specific cut, so they are not included in this calculation.

Question 8

A logistics company uses a flow network to optimize delivery routes. The network currently achieves maximum flow of 45 packages per hour. Management wants to determine which single edge, if upgraded to unlimited capacity, would provide the greatest increase in maximum flow. The current minimum cut consists of edges with capacities 12, 18, and 15. If upgrading one edge to unlimited capacity increases the maximum flow to 63 packages per hour, which edge was most likely upgraded?

  1. An edge with capacity 15, since removing this constraint allows 18 additional units of flow
  2. An edge with capacity 18, since it has the highest capacity in the current minimum cut
  3. An edge with capacity 12, since eliminating the smallest bottleneck provides maximum benefit
  4. An edge outside the current minimum cut, since the new bottleneck occurs at a different location (correct answer)
Explanation: If upgrading a single edge increases flow from 45 to 63 (an increase of 18), but the current minimum cut has total capacity 45 (12+18+15), then upgrading any edge in the current cut would allow flow equal to the remaining edges. Upgrading the 12-capacity edge would allow maximum flow of 18+15=33, the 18-capacity edge would allow 12+15=27, and the 15-capacity edge would allow 12+18=30. None of these reach 63, so the upgraded edge must be outside the current minimum cut, and the new bottleneck is elsewhere in the network.