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 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 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 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 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

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