Subcontracting $($Assignment Problem$)$

Your company needs to subcontract nine projects to other companies. Six subcontractors submitted their cost estimates $($in $$1000)$ for all projects, which are shown in the table below.

Cost in $$1000$ Projects

Subcontractors $123456789$

A $294945554449504559$

B $465759563034423649$

C $55424446949292234$

D $565511352432574038$

E $373754442252471022$

F $345138343743365844$

Your task is to assign projects to subcontractors such that each project is assigned to exactly one subcontractor, each subcontractor is assigned at least one and at most two projects, and the total cost is minimized.

$1.$ Draw a network flow model for this problem.

$2.$ Formulate an LP model for this problem.

$3.$ Create a spreadsheet implementation of the LP model and solve it using the Solver Add$-$in$.$

$4.$ What is the optimal assignment of projects to subcontractors? What is the total cost?

$5.$ How much is each subcontractor paid for the assigned projects? What are the highest and the lowest payment per subcontractor?

$6.$ Advanced: Suppose that in addition to minimizing the cost, we would also like to minimize the maximum payment per subcontractor. Formulate an updated LP model, create an updated spreadsheet implementation, and determine a new assignment of projects to subcontractors that reduces the maximum payment per subcontractor.