# Linear Programming problem

• Mar 4th 2009, 02:14 AM
CheeseyChips
Linear Programming problem
Hey, Heard this forum is very helpful!
Here's one of the problems I recently encountered.
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.
• Mar 5th 2009, 01:09 AM
CaptainBlack
Quote:

Originally Posted by CheeseyChips
Hey, Heard this forum is very helpful!
Here's one of the problems I recently encountered.
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.

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=x_1+x_2+x_3+x_4$

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

2013: $0.9 x_1+0.7 x_2+1.3 x_4 \ge 500$

2018: $0.6 x_1+ 0.6 x_2 + 0.5 x_3 \ge 300$

2024: $0.5 x_2+ x_2+2 x_4\ge 400$

positivity: $x_1\ge 0$, $x_2 \ge 0$, $x_3 \ge 0$, $x_4 \ge 0$

The above should be all you need for part (a), part (b) is mixed IP, as is part (c).

The way to handle part (b) is instead of using the amount of the investment use 0-1 variables $u_1$, $u_2$ and $u_3$ and multiply these by the allowed investment amounts. Then for part (c) you gave an additional constraint:

$-u_2-u_3 \ge -1$

CB
• Mar 5th 2009, 05:57 AM
CheeseyChips
thanks so much captainblack for your response. greatly appreciated.
• Mar 5th 2009, 07:57 AM
CheeseyChips
Would I enter all those constraints together now?

Or do I enter one of those constraints, eg the 2013 constraint to the objective function to get the answer for 2013?
• Mar 5th 2009, 11:20 AM
CheeseyChips
Quote:

Originally Posted by CheeseyChips
Would I enter all those constraints together now?

Or do I enter one of those constraints, eg the 2013 constraint to the objective function to get the answer for 2013?

never mind...got it all sorted. SOLVED.