ME30B Exam 2003
Question 1.1
1.1 The Project Engineer for New Business Development has prepared and designed seven (7) new projects for a company as follows:
Projects 
NPV ($M) 
Investment Required ($M) 

Year 1 
Year 2 

A 
12 
5 
5 
B 
10 
4 
4 
C 
8 
4 
2 
D 
6 
2 
2 
E 
6 
2 
3 
F 
8 
3 
2 
G 
0 
1 
1 
Capital Funds Available 
15 
15 
Projects C and E are dependent and must be implemented simultaneously
Projects A, B and D are mutually exclusive
When Project F is undertaken, Project G must also be undertaken.
Required
Formulate the problem as an LP model
Solution:
Step 1: List the constraints we know at this present moment
Step 2: Determine our decision variables
Let’s first examine our problem. Now, we first have to understand what the goal of the New Business Development is. When we examine the problem, we see that New Business Development needs to decide which of the seven projects to invest in.
(Ok this might get slightly different from what you are accustomed to since we are now going to use something call an integer or binary variable, which are used in integer linear programming problems)
Now, we wish to know “To Invest or Not to Invest” in a project. As you can see, this has only two possible outcomes. We can probably use a binary variable which has only two values: 0 or 1, to represent this situation. When we invest in a project, we can say it has a value of 1, and when we don’t invest we can say it has a value of 0.
Let’s put this mathematically
where X_{i} = If Project i is undertaken (i = A, B, C, D, E, F, G)
X_{i} = 1 : Project i is undertaken
X_{i} = 0: Project i is not undertaken
Step 3: Objective function
Next question, we ask ourselves by which criteria should New Business Development use to choose the projects for investment. We note that the Net Present Value (NPV) is given, which tells us the value of the project at this present moment. The criteria that the New Business Development can use for choosing the Projects, is to invest in Projects that maximizes or increases its NPV.
Therefore using the NPV values from the table, our objective function is
Max Z = 12 X_{A} + 10 X_{B} + 8 X_{C} + 6 X_{D} + 6 X_{E} + 8 X_{F} + 0 X_{G}_{ }
You will note that if we didn’t invest in X_{E}, then X_{E} value will be 0, and thus its NPV value of 6 will not be accrued in the total NPV. X_{G} does not have to be included in the objective function, but it is useful to do so for two reasons a) if you perform a sensitivity analysis you can get the range of its coefficient; b) Provides a crossreference for you to ensure all variables are accounted for (and also that the examiner knows you didn’t omit it from your thoughts).
Also, you may notice I used Z instead of P, since P refers to profit. Z is the standard letter use for referring to the objective function in optimization problems.
Step 4: Write your constraints in mathematical form.
Let’s look at our first constraint
1. Total Investment in Year 1 ≤ 15
Using the investment amount required for each project in year 1 from our table we can write
5 X_{A} + 4 X_{B} + 4 X_{C} + 2 X_{D} + 2 X_{E} + 3 X_{F} + 1 X_{G } ≤ 15 (Investment for Year 1)
2. Similarly we do the same thing for constraint 2, which is that the investment in year 2 must also be ≤ 15
5 X_{A} + 4 X_{B} + 2 X_{C} + 2 X_{D} + 3 X_{E} + 2 X_{F} + 1 X_{G}_{ }≤ 15 (Investment for Year 2)
3. Investing in Project C requires us to invest in Project E and vice versa
This means X_{C} = X_{E}
Therefore, if X_{E} is not undertaken, i.e. X_{E} = 0, then X_{C} = 0, or also not undertaken.
To write this as a constraint:
X_{C} – X_{E} = 0 (Projects C and E dependency)
4. Only one project from Projects A, B and D can be invested in or neither A, B and D (from my understanding this is what is meant by mutually exclusive)
This constraints mean either X_{A} or X_{B} or X_{D} = 1 (i.e. invested) or all equal to 0 (i.e. not invested in). This means, that only one of these projects can have a value of 1, thus if sum up their values, it has to be ≤ 1.
Therefore we can write this constraint as
X_{A} + X_{B} + X_{D} ≤ 1 (Projects A, B and D mutual exclusivity)
This will ensure, if X_{A} = 1, then X_{B} and X_{D} must be 0 to ensure the constraint holds. Being ≤ 1, also ensures that if neither are invested in, their sum of 0, will still hold for this constraint.
5. If Project F is invested in, then Project G must also be invested
This means if X_{F} =1 (i.e. invested in) then X_{G} = 1 (i.e. invested in) or X_{F} = X_{G}.
However, the constraint says nothing about what happens to X_{F}, if X_{G} = 1 (i.e. invested in) which could mean that X_{F} = 0 or X_{F} = 1. We know that if X_{G} = 0, this can only mean that X_{F} = 0, since Project F cannot be undertaken unless Project G is also undertaken.
Therefore we have
X_{F} 
X_{G} 
1 
1 
0 
1 
We can see that always X_{F} ≤ X_{G}
Therefore, writing this constraint
X_{F} – X_{G} ≤ 0 (Project F dependence on Project G)
Step 5. Write out the whole linear programming problem
Max Z = 
12 X_{A} 
+ 10 X_{B} 
+ 8 X_{C} 
+ 6 X_{D} 
+ 6 X_{E} 
+ 8 X_{F} 
+ 0 X_{G} 



5 X_{A} 
+ 4 X_{B} 
+ 4 X_{C} 
+ 2 X_{D} 
+ 2 X_{E} 
+ 3 X_{F} 
+ X_{G}_{ } 
≤ 15 
(Investment for Year 1) 

5 X_{A} 
+ 4 X_{B} 
+ 2 X_{C} 
+ 2 X_{D} 
+ 3 X_{E} 
+ 2 X_{F} 
+ X_{G}_{ } 
≤ 15 
(Investment for Year 2) 



X_{C} 

– X_{E} 


= 0 
(Projects C and E dependency) 

X_{A} 
+ X_{B} 

+ X_{D} 



≤ 1 
(Projects A, B and D mutual exclusivity 






X_{F} 
– X_{G} 
≤ 0 
(Project F dependence on Project G) 

X_{i} = 0 or 1 (i= A, B, C, D, E, F, G) 

