Question

Mercer Development is considering the potential of four different development projects. Each project would be completed in at most three years. The required cash outflow for each project is given in the table below, along with the net present value (NPV) of each project and the budget cash that is available to spend for each year.

	Cash Outflow Required ($ million)				Budget Cash Available ($ million)
	Project 1	Project 2	Project 3	Project 4
Year 1	10	9	6	12	35
Year 2	4	5	4	2	12
Year 3	7	0	3	0	10
NPV	30	28	20	14

The management of Mercer development wants to develop a linear programming model to find the optimal decisions on which projects to participate in. Suppose that for each project, Mercer Development can either fully participate or not at all. The objective of the management is to maximize the total NPV obtained by participating selected projects.

1. Assume that the budget cash not used in one year will not be carried over to the next year, and that you are not allowed to spend more than the budget cash available for each year. Formulate this problem as a linear programming problem.

2. If the management indicates that they may want to participate in Project 2 only if they have also decided to participate in Project 1, and that they should participate in at least one of project 2, 3, and 4. How can you formulate these requirements as two linear constraints?

3. Re-consider the problem stated in part a) and ignore the requirements in part b), now assume that the budget cash not used in one year is allowed to carry over to the next year.

Formulate this problem as a linear programming problem.

Answer 1

Let's define the decision variable Xi such that

Xi = 1 if the project i is selected or 0 otherwise

i = 1, 2, 3, 4

All Xi ∈ {0, 1}

Part (a)

Objectiv function: Max z = 30X1 + 28X2 + 20X3 +14X4 (Maximize NPV)

Subject to:

10X1 + 9X2 + 6X3 + 12X4 ≤ 35 (Cash budget for year 1 constraint)
4X1 + 5X2 + 4X3 + 2X4 ≤ 12 (Cash budget for year 2 constraint)
7X1 + 0X2 + 3X3 + 0X4 ≤ 10 (Cash budget for year 3 constraint)

X1, X2, X3, X4 ∈ {0, 1}

Part (b)

Management may want to participate in Project 2 only if they have also decided to participate in Project 1,

Hence, if X1 = 0 then X2 = 0; if X1 = 1 then X2 = 0 or 1

Define X1 - X2 then it can only take two values 0 or 1.

Hence the liner constraint for this will be: X1 - X2 ≥ 0

Management should participate in at least one of project 2, 3, and 4

At least one of the three variables X1, X2 and X3 should be 1

Hence the linear constraint for this will be: X2 + X3 + X4 ≥ 1

Part (c)

the constraints will now be on cumulative. That means:

• in year 2, total spend in year 1 + spend in year 2 should not exceed the budget for year 1 + budget for year 2
• in year 3, total spend in year 1 + spend in year 2 + spend in year 3 should not exceed the budget for year 1 + budget for year 2 + budget for year 3

Hence the formulation will now be:

Objectiv function: Max z = 30X1 + 28X2 + 20X3 +14X4 (Maximize NPV)

Subject to:

10X1 + 9X2 + 6X3 + 12X4 ≤ 35 (Cash budget for year 1 constraint)
14X1 + 14X2 + 10X3 + 14X4 ≤ 47 (Cumulative Cash budget for year 2 constraint)
21X1 + 14X2 + 13X3 + 14X4 ≤ 57 (Cumulative Cash budget for year 3 constraint)

X1, X2, X3, X4 ∈ {0, 1}