 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

1. Total Investment in Year 1 ≤ 15 (we get this figure from the last row in the table which says capital funds available)
2. Total Investment in Year 2 ≤ 15
3. Investing in Project C requires us to invest in Project E and vice versa
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)
5. If Project F is invested in, then Project G must also be invested (note the difference between this constraint and constraint 3, where C and E must be invested together or not at all, whilst here, G can be invested by itself, or invested when F is undertaken)

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 Xi = If Project i is undertaken (i = A, B, C, D, E, F, G)

Xi = 1 : Project i is undertaken

Xi = 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 XA + 10 XB + 8 XC + 6 XD + 6 XE + 8 XF + 0 XG

You will note that if we didn’t invest in XE, then XE value will be 0, and thus its NPV value of 6 will not be accrued in the total NPV. XG 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 cross-reference 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 XA + 4 XB + 4 XC + 2 XD + 2 XE + 3 XF + 1 XG   ≤ 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 XA + 4 XB + 2 XC + 2 XD + 3 XE + 2 XF + 1 XG  ≤ 15            (Investment for Year 2)

3. Investing in Project C requires us to invest in Project E and vice versa

This means XC = XE

Therefore, if XE is not undertaken, i.e. XE = 0, then XC = 0, or also not undertaken.

To write this as a constraint:

XC – XE = 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 XA or XB or XD = 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

XA + XB + XD ≤ 1                                            (Projects A, B and D mutual exclusivity)

This will ensure, if XA = 1, then XB and XD 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 XF =1 (i.e. invested in) then XG = 1 (i.e. invested in) or XF = XG.

However, the constraint says nothing about what happens to XF, if XG = 1 (i.e. invested in) which could mean that F = 0 or XF = 1. We know that if XG = 0, this can only mean that XF = 0, since Project F cannot be undertaken unless Project G is also undertaken.

Therefore we have

 X­F XG 1 1 0 1

We can see that always XF ≤ XG

Therefore, writing this constraint

XF – XG ≤ 0                                                                  (Project F dependence on Project G)

Step 5. Write out the whole linear programming problem

 Max Z = 12 XA + 10 XB + 8 XC + 6 XD + 6 XE + 8 XF + 0 XG 5 XA + 4 XB + 4 XC + 2 XD + 2 XE + 3 XF +  XG ≤ 15 (Investment for Year 1) 5 XA + 4 XB + 2 XC + 2 XD + 3 XE + 2 XF +  XG ≤ 15 (Investment for Year 2) XC – XE = 0 (Projects C and E dependency) XA + XB + XD ≤ 1 (Projects A, B and D mutual exclusivity XF – XG ≤ 0 (Project F dependence on Project G) Xi = 0 or 1 (i= A, B, C, D, E, F, G)