Linear Programming Question

Hey, first question here. Heard this forum is very helpful!
Here's one of the problems I was recently given to do as an assignment.
Basically, I can't formulate constraints and everything is just going around in my head like crazy. I am presuming you would need to use some sort of programme to solve it like LINGO/LINDO/excel?

Any hints on where to start formulating?

-
The National Roads Authority (NRA) have identified three major road infrastructure projects which are required over the next 15 years. Project 1 is the completion of a motorway linking A-town and C-town. Project 2 is the linkage of the Project 1 motorway to B-Town. Project 3 is the completion of a motorway linking A-town and D-town. The required delivery dates and costs of the three projects are as given in Table 1.

Project 1 Project 2 Project 3
Required delivery date 2013 2018 2024
Cost (millions) 500 300 400
Table 1. (Required delivery date and cost of NRA projects)

For simplicity (though it is not very realistic), it may be assumed that the cost of each project is paid in a single lump sum to the contractor, at the date of delivery of that project. It may further be assumed that each project will be delivered on time and at the given cost.

The NRA and Departments of Transport and Finance wish to have sufficient
funds available to pay for each project on its delivery date. To this end, they have negotiated with major international banks that they may make use of up to four investment opportunities, each of which requires a single investment up front (that is, today: 2009) and each of which will return, for every euro invested, certain fixed amounts in each of the three project delivery years 2013, 2018 and 2024, as given in
Table 2. These options are the only investments available in the current climate.

Option 1 Option 2 Option 3 Option 4
2013 0.90 0.70 0.00 1.20
2018 0.60 0.60 0.50 0.00
2024 0.00 0.50 2.00 1.00
Table 2. (Return in euro from investments, by year, for each euro invested)

Any excess return above the minimum required for each project delivery date will be ploughed back into the national pension fund: it may not be reinvested, or even kept for the next project delivery date.

The objective is to find the mix of investments in these options (that is, the
amount invested in each option) which will meet the costs of the projects at the required times, and which will minimise the total amount to be invested today.

Formulate the problem in either LP or (mixed) IP terms, as appropriate, for
each of the following three situations.
Solve for each situation (if your computer package does not support IPs, it is enough to formulate the IPs).

(a) Any amount in euro may be invested in each of the four options (for example, 74,341,982.46 could be invested in Option 1, and so on).

(b) Any amount may be invested in Option 4, but for each of Options 1–3, the
amount invested must be either 0 or as given in Table 3.

Option 1 Option 2 Option 3
Required Investment 250,000,000 300,000,000 350,000,000
Table 3. (Required investment amount for Options 1–3)

(c) This situation is the same as (b) except that now at most one of Options 2 and 3 may be invested in.
- - - -

I've been trying to formulate constraints for this question now for quite a bit and it's fairly confusing. I'm not sure if I'm trying to minimise or maximise the thing in the first place.

Do I use linear programming for (a) and (c) and integer programming for (b) ??

Need help badly with this one!

Thanks.

Any ideas anyone?

Originally Posted by ScabbyDog

Any ideas anyone?

actually, i think this question is solved by integer programming, not linear.

Originally Posted by Leith Ross

Hello ScabbyDog,

I believe you haven't received an answer to your question because it doesn't relate to Excel and it is not clear what you want to do. When requesting help, you need to present your question in a clear and succinct way. Any code you have written should be posted as well. It is better to post the entire workbook whenever possible. You should look through the list of available forums before posting your question. Posting it in the correct forum will insure a faster response.

I had a look there and this is the most related forum I have found. There are a few other questions on linear programming in this forum as well.

What I've posted is all the question I was given and I just need to find out the constraints I need to use for it and then I should be able to solve it!

Thanks.

Ok, this is what I have so far:

The descision variables are the amounts invested in each option lets call them x_1, x_2, x_3 and x_4.

The objective to be minimised is:

O=x1+x2+x3+x4

the constraints on the availability of sufficient funds at the required dates:

2013: 0.9 x1+0.7 x2+1.3 x4 >= 500

2018: 0.6 x1+ 0.6 x2 + 0.5 x3 >= 300

2024: 0.5 x2+ x2+2 x4 >= 400

positivity: x1>= 0, x2 >= 0, x3 >= 0, x4 >= 0

I think the above should be all I need for part (a) but I know part (b) is mixed IP, as is part (c).

I think the way to handle part (b) is instead of using the amount of the investment use 0-1 variables u1, u2 and u3 and multiply these by the allowed investment amounts. Then for part (c) I have to use an additional constraint?:

-u2-u3 >= -1

Is this all correct?

Thanks.