Question

1. Four workers are available to perform tasks 1-4. However, worker 1 can't do tasks 2, 3, or 4. Also, worker 2 can't do tasks 3 or 4 and worker 3 can't do tasks 1, 3, or 4. Worker 4 can do any task. Each worker can do at most one task, and each task should be performed at most once.

a) Draw the network for the maximum flow problem that can be used to determine whether all tasks can be assigned to a suitable worker. (Please specify the source and sink nodes, arc directions and arc capacities)

b) Formulate this problem as a linear program. Clearly define all variables and constraints

c) Solve the model using Ford-Fulkerson algorithm (Please show all the iterations)

d) Use the final iteration of Ford-Fulkerson algorithm to find a minimum cut for this network and verify the strong duality (i.e, maximum flow = total capacity of the minimum cut).

2. During the next 4 months, a construction firm must complete 3 projects. Project 1 must be completed within 3 months and requires 8 months of labor. (8 workers working for 1 month = 8 months of labor.) Project 2 must be completed within 4 months and requires 10 months of labor. Project 3 must be completed in 2 months and requires 12 months of labor. Each month, 8 workers are available. During a given month, no more than 6 workers can work on a single job.

a) Draw the network for the maximum flow problem that can be used to determine whether all tasks can be assigned to a suitable worker. (Please specify the source and sink nodes, arc directions and arc capacities)

b) Formulate this problem as a linear program. Clearly define all variables and constraints

c) Solve the model using Ford-Fulkerson algorithm (Please show all the iterations) and answer the following question: can all 3 projects can be completed on time?

d) Use the final iteration of Ford-Fulkerson algorithm to find a minimum cut for this network and verify the strong duality (i.e, maximum flow = total capacity of the minimum cut).

Answer 1

1)

a) Network model is following

In the above network model, we see that task nodes 3 and 4 are both connected to the same worker node. Therefore, any one of these nodes will remain unassigned.

b) Formulate a Linear Program model

Let Xij be a binary variable such that Xij=1 indicates that worker i is assigned to task j

Max Xij

s.t.

XA1 + XB1 + XC1 + XD1 = 1

XA2 + XB2 + XC2 + XD2 = 1

XA3 + XB3 + XC3 + XD3 = 1

XA4 + XB4 + XC4 + XD4 = 1

XA1 + XA2 + XA3 + XA4 = 1

XB1 + XB2 + XB3 + XB4 = 1

XC1 + XC2 + XC3 + XC4 = 1

XD1 + XD2 + XD3 + XD4 = 1

Xij {0,1}