Results 1 to 5 of 5

Math Help - Linear Programming problem

  1. #1
    Newbie
    Joined
    Dec 2008
    Posts
    9

    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 13, 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 13)

    (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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by CheeseyChips View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Dec 2008
    Posts
    9
    thanks so much captainblack for your response. greatly appreciated.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Dec 2008
    Posts
    9
    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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Dec 2008
    Posts
    9
    Quote Originally Posted by CheeseyChips View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 6
    Last Post: August 16th 2011, 06:10 PM
  2. Linear Programming Problem
    Posted in the Algebra Forum
    Replies: 3
    Last Post: November 22nd 2010, 12:41 PM
  3. Need help with linear programming problem
    Posted in the Advanced Applied Math Forum
    Replies: 1
    Last Post: August 25th 2010, 09:43 PM
  4. Linear Programming Problem again
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: June 3rd 2009, 04:39 PM
  5. Linear Programming-Need help with one problem
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: November 17th 2007, 04:44 AM

Search Tags


/mathhelpforum @mathhelpforum