Question 1 (11 marks). There are 6 cities in Kilroy County. The county must determine where to build central fire stations. The county wants to build the minimum number of central fire stations needed to ensure that at least two fire stations are within 25 minutes (driving time) of each city. The times (in minutes) required to drive between the cities in Kilroy County are given in the table. Formulate a model that will tell Kilroy how many fire stations should be built and where they should be located.

Cities within 25 mins of each city

Decision variables:

Objective function:

Constraints

Additional constraint 1Either City 1 or City 2 (or both) must be selected to build a fire station in if either City 3 or City 4 (or both) is selected to build a fire station in.

Additional constraint 2Both City 3 and City 4 must be selected to build fire stations in ifeither City 5or City 6(or both) is selected to buildafire station in.

Question 3 (12 marks)A company is attempting to decide the mix of products which it should produce next week. It has six products, each with a unit profit (unit profit =selling price -variable cost per unit) and a unit production time as shown below:

Product	Profit ($/unit)	Production time (hours/unit)
1	10	1
2	22	2
3	35	1.7
4	19	2.4
5	55	4.5
6	115	9.5

The company has 720 hours available next week. The company has the following additional linear constraints:

• For each product, if it is produced, a fixed cost of $1000 is incurred.
• If product 2 is produced, 40 hours are needed for production setup.

Formulate an integer programming model to find next week's production schedule that maximizes profit with linear objective function and all linear constraints.

Decision variables :

Objective function :

Constraiint:

Additional constraint :Product 1 must be produced if any two of Product 2, 3 and 4 are produced.

Additional constraint 2:Product 1 can be produced only if at least two of Product 2, 3 and 4 are produced.

Question 4 In the planning of the monthly production for the next four months, in each month a company must operate either a normal shift or an extended shift (but not both) if it produces. It may choose not to produce in a month. A normal shift costs $100,000 per month and can produce up to 5,000 units per month. An extended shift costs $140,000 per month and can produce up to 7,500 units per month.

The cost of holding inventory is estimated to be $2 per unit per month (based on the average inventory held during each month) and the initial inventory is 3,000 units (i.e., inventory at the beginning of Month 1). The inventory at the end of month 4 should be at least 2,000 units. The demand for the company's product in each of the next four months is estimated to be as shown below:

Month	1	2	3	4
Demand	6000	6500	7500	7000

Production constraints are such that if the company produces anything in a particular month it must produce at least 3,000 units. The company wants a production plan for the next four months to meet its demands. Formulate an integer programming model to solve the problem at minimum cost.

Decision variables :

Objective function :

Constraint:

Additional constraint 1:The company can operate an extended shift in Month 1 only if it operates a normal shift in each of Month 2, Month 3 and Month 4.

Additional constraint 2 :The company must produce in either Month 1 or Month 2 (or both) if it does not produce in Month 3.

Additional constraint 3 :The company cannot operate an extended shift in a month if it operates one in the previous month.