11.2.1. Linear Programming

Try these first

1. 1.

   What is the purpose of linear programming?

   Hint

   Think about optimization in terms of resources.

2. 2.

   Define a bipartite graph in simple terms.

   Hint

   Consider how people and jobs might be matched.

3. 3.

   What is linear programming primarily used for?

   • Maximizing profits
   • Finding shortest paths
   • Simulating network traffic

   Hint

   Think about business applications.

4. 4.

   True or False: A bipartite graph can have edges connecting vertices within the same set.

   • True
   • False

   Hint

   Visualize the structure of bipartite graphs.

5. 5.

   Given 5 teachers and 4 courses, design a flow network to illustrate maximum matching. Consider some teachers have preferences for more than one course.

   Hint

   Think about how to ensure the flow meets the allocation constraints.

6. 6.

   If a new constraint is added where teachers can teach a maximum of two courses, re-evaluate the original matching model and discuss the implications on the network flow.

   Hint

   Consider how this relaxation of constraints alters the network structure.