1. Define any additional parameters and/or variables you want to use. State clearly what they represent.

2. Write down the objective function using the decision variables. If you wish, you can write the first term and the last term and use . . . to represent the missing similar terms in any expression involving the same group of variables

3. Write the constraints of the integer linear programming model. For each type of constraint, first state its purpose, then give the constraint(s).

4. PennDOT does not want to spend more than $4M in total (including the certification cost if needed) for the expenses related to company C. Write down the corresponding linear constraint(s) that will ensure this requirement.

5. Either company A is contracted to complete at least two projects or it is not contracted at all. Write down the corresponding linear constraint(s) that will ensure this requirement

6. Solve using Excel the objective value.

7. Both projects 1 and 2 require construction around the CMU campus. Because of the coordination concerns, they thus have to be assigned to the same company. Write down the corresponding linear constraint(s) that will ensure this requirement.

The Pennsylvania Department of Transportation (PennDOT) has five construction projects that needs to be completed this summer. Three companies (A,B, and C) have placed their bids (in millions of dollars) to complete these projects as follows: In this table, a dash '-' indicates that the corresponding company is not qualified to do the given project. For instance, company C cannot complete projects 1 and 2 , and it will cost PennDOT $1.4M to contract company C to complete project 3. None of these companies has done any work with government before. Therefore, if they are assigned to complete any project for PennDOT, there will be an additional one time cost of $0.5M for the certification of the corresponding company to work on government projects. This certification fee is independent of the number of projects assigned to the company, and it will be covered by PennDOT for the particular company whenever they are contracted to complete at least one project. That is, if company A is contracted to do projects 1 and 2 , and company C is contracted to complete projects 3,4 and 5 , then PennDOT will pay $1M in total for their certification in addition to their requested prices to complete the projects. Each project needs to be completed by exactly one company. Moreover, these companies have limited workforce which results in some capacity restrictions. Company A can complete up to three projects, and so does company C. But, company B can complete at most two projects. PennDOT would like to have all five projects completed while minimizing the total cost (including payments to the contracted companies and certification costs) and respecting the restrictions stated above. We will model this problem as an integer linear program. As variables, you can use: xi,j : whether company i is contracted to complete project j(xi,j=1) or not (xi,j=0) for company i=A,B, or C, and project j=1,,5