Results 1 to 12 of 12

Math Help - Formulate as a Linear programming problem

  1. #1
    Newbie
    Joined
    Jul 2009
    Posts
    7

    Formulate as a Linear programming problem

    Hi everyone,
    I really need help understanding how to formulate into a LP. here is one of the problems i'm struggling with:


    A company makes three different products: product A; product B; product C. Each product requires a piece of metal of the size:

    ∙ 90cm3m for product A;
    ∙ 70cm3m for product B; and
    ∙ 50cm3m for product C.

    The company receives metal sheets with size 2m3m, which needs to be cut into smaller
    pieces above. A large order has come in and the company needs to make at least
    ∙ 300 pieces of product A;
    ∙ 400 pieces of product B; and
    ∙ 1000 pieces of product C.

    The company wants to find out how to cut up the metal sheets so as to minimize waste.

    (a) There are 6 ways to cut a 2m3m metal sheet into pieces of sizes 90cm3m, 70cm3m and 50cm3m with a waste having the shorter side smaller than 50cm (so that no other pieces can cut out of the waste). What are they and how much metal does each one waste (list them in the order of most waste to least)?
    (b) Each of the ways of cutting a metal sheet wastes a certain amount of metal. Obviously
    we would like to minimize this waste while still producing enough products
    A, B and C.
    The cutting machine requires that there is some waste left after the
    cutting. This leaves only five cutting options. Write this as a linear programming problem.

    Hint. Use variables x1, . . . , x5, where xi denotes the number metal sheets cut using option i. Your goal is to satisfy the production requirements while minimizing the waste.


    I'd appreciate any help regarding this problem.
    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 ThineBlood View Post
    Hi everyone,
    I really need help understanding how to formulate into a LP. here is one of the problems i'm struggling with:


    A company makes three different products: product A; product B; product C. Each product requires a piece of metal of the size:

    ∙ 90cm3m for product A;
    ∙ 70cm3m for product B; and
    ∙ 50cm3m for product C.

    The company receives metal sheets with size 2m3m, which needs to be cut into smaller
    pieces above. A large order has come in and the company needs to make at least
    ∙ 300 pieces of product A;
    ∙ 400 pieces of product B; and
    ∙ 1000 pieces of product C.

    The company wants to find out how to cut up the metal sheets so as to minimize waste.

    (a) There are 6 ways to cut a 2m3m metal sheet into pieces of sizes 90cm3m, 70cm3m and 50cm3m with a waste having the shorter side smaller than 50cm (so that no other pieces can cut out of the waste). What are they and how much metal does each one waste (list them in the order of most waste to least)?
    (b) Each of the ways of cutting a metal sheet wastes a certain amount of metal. Obviously
    we would like to minimize this waste while still producing enough products
    A, B and C.
    The cutting machine requires that there is some waste left after the
    cutting. This leaves only five cutting options. Write this as a linear programming problem.

    Hint. Use variables x1, . . . , x5, where xi denotes the number metal sheets cut using option i. Your goal is to satisfy the production requirements while minimizing the waste.


    I'd appreciate any help regarding this problem.
    Before formulating this as a LP you need to do part (a). Have you done it, and what are the ways?

    CB
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jul 2009
    Posts
    7
    Quote Originally Posted by CaptainBlack View Post
    Before formulating this as a LP you need to do part (a). Have you done it, and what are the ways?

    CB

    I'm not sure if this is what i was supposed to do but i've got.

    2 (90cmx3m) + 20 cmx3m (waste)
    4 (50cmx3m) + 0 (waste)
    1 (90cmx3m) + 2 (50cmx3m) + 10 cmx3m (waste)
    2 (70cmx3m) + 1 (50cmx3m) + 10 cmx3m (waste)
    1 (90cmx3m) + 1 (70cmx3m) + 40 cmx3m (waste)
    1 (70cmx3m) + 2 (50cmx3m) + 30 cmx3m (waste)


    Thanks for your help CaptainBlack, I really appreciate it.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by ThineBlood View Post
    I'm not sure if this is what i was supposed to do but i've got.

    2 (90cmx3m) + 20 cmx3m (waste)
    4 (50cmx3m) + 0 (waste)
    1 (90cmx3m) + 2 (50cmx3m) + 10 cmx3m (waste)
    2 (70cmx3m) + 1 (50cmx3m) + 10 cmx3m (waste)
    1 (90cmx3m) + 1 (70cmx3m) + 40 cmx3m (waste)
    1 (70cmx3m) + 2 (50cmx3m) + 30 cmx3m (waste)


    Thanks for your help CaptainBlack, I really appreciate it.
    OK that is what we needed (other than the question requests them ordered form least to most waste.

    Also for the nest stage as the machine requires some waste you need a new list with the zero waste cutting method dropped.

    You are told (it is the hint) to use variables x_1,\ ...\ x_5 for the number of pieces cut using each of the cutting methods.

    Then we have to express each of the production rquirements as an inequality of the variables x_1,\ ...\ x_5, these are the constraints (together with the non-negativity constraints on the variables), and the objective to minimise the total waste.

    CB
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jul 2009
    Posts
    7
    Quote Originally Posted by CaptainBlack View Post
    OK that is what we needed (other than the question requests them ordered form least to most waste.

    Also for the nest stage as the machine requires some waste you need a new list with the zero waste cutting method dropped.

    You are told (it is the hint) to use variables x_1,\ ...\ x_5 for the number of pieces cut using each of the cutting methods.

    Then we have to express each of the production rquirements as an inequality of the variables x_1,\ ...\ x_5, these are the constraints (together with the non-negativity constraints on the variables), and the objective to minimise the total waste.

    CB
    so this is the part i don't entirely understand. what are x_1,\ ...\ x_5 represent. I don't understand what the number of sheets cut using option i mean. does it mean that if I cut a 2mx3m sheet once then i use the variable x_1?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by ThineBlood View Post
    so this is the part i don't entirely understand. what are x_1,\ ...\ x_5 represent. I don't understand what the number of sheets cut using option i mean. does it mean that if I cut a 2mx3m sheet once then i use the variable x_1?
    Order the cutting methods in increasing order of waste (like you have been asked to do in part (a)) and drop the one with zero waste.

    Lable these cut1 .. cut5. Now x_i represents the number of sheets of steel you will cut using cuti.

    CB
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Jul 2009
    Posts
    7
    Quote Originally Posted by CaptainBlack View Post
    Order the cutting methods in increasing order of waste (like you have been asked to do in part (a)) and drop the one with zero waste.

    Lable these cut1 .. cut5. Now x_i represents the number of sheets of steel you will cut using cuti.

    CB
    so would these be my constraints?

     x_1 + 2x_3 + x_5 >= 300,
    2x_2 + x_4 + x_5 >= 400,
    2x_1 + x_2 + x_4 >=1000,

    and objective function:

    Minimize 10x_1 + 10x_2 + 20x_3 + 30x_4 + 40x_5

    x_1,...x_5 >= 0
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by ThineBlood View Post
    so would these be my constraints?

     x_1 + 2x_3 + x_5 >= 300,
    2x_2 + x_4 + x_5 >= 400,
    2x_1 + x_2 + x_4 >=1000,

    and objective function:

    Minimize 10x_1 + 10x_2 + 20x_3 + 30x_4 + 40x_5

    x_1,...x_5 >= 0
    That looks OK-ish, its a bit difficult to check with the cuts unordered and in a different post.

    CB
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Jul 2009
    Posts
    7
    Quote Originally Posted by CaptainBlack View Post
    That looks OK-ish, its a bit difficult to check with the cuts unordered and in a different post.

    CB
    1 (90cmx3m) + 2 (50cmx3m) + 10 cmx3m (waste)
    2 (70cmx3m) + 1 (50cmx3m) + 10 cmx3m (waste)
    2 (90cmx3m) + 20 cmx3m (waste)
    1 (70cmx3m) + 2 (50cmx3m) + 30 cmx3m (waste)
    1 (90cmx3m) + 1 (70cmx3m) + 40 cmx3m (waste)

    x_1 + 2x_3 + x_5 >= 300,
    2x_2 + x_4 + x_5 >= 400,
    2x_1 + x_2 + x_4 >=1000,


    Thank you so much for all ur help, CaptainBlack. I really appreciate it.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by ThineBlood View Post
    1 (90cmx3m) + 2 (50cmx3m) + 10 cmx3m (waste)
    2 (70cmx3m) + 1 (50cmx3m) + 10 cmx3m (waste)
    2 (90cmx3m) + 20 cmx3m (waste)
    1 (70cmx3m) + 2 (50cmx3m) + 30 cmx3m (waste)
    1 (90cmx3m) + 1 (70cmx3m) + 40 cmx3m (waste)

    x_1 + 2x_3 + x_5 >= 300,
    2x_2 + x_4 + x_5 >= 400,
    2x_1 + x_2 + x_4 >=1000,


    Thank you so much for all ur help, CaptainBlack. I really appreciate it.
    ∙ 90cm3m for product A;
    ∙ 70cm3m for product B; and
    ∙ 50cm3m for product C.

    The company receives metal sheets with size 2m3m, which needs to be cut into smaller
    pieces above. A large order has come in and the company needs to make at least
    ∙ 300 pieces of product A;
    ∙ 400 pieces of product B; and
    ∙ 1000 pieces of product C.

    I make it:

    x_1 + 2x_3 + x_5 >= 300,
    2x_2 + x_4 + x_5 >= 400,
    2x_1 + x_2 + 2x_4 >=1000,

    CB
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Jul 2009
    Posts
    7
    Quote Originally Posted by CaptainBlack View Post
    ∙ 90cm3m for product A;
    ∙ 70cm3m for product B; and
    ∙ 50cm3m for product C.

    The company receives metal sheets with size 2m3m, which needs to be cut into smaller
    pieces above. A large order has come in and the company needs to make at least
    ∙ 300 pieces of product A;
    ∙ 400 pieces of product B; and
    ∙ 1000 pieces of product C.

    I make it:

    x_1 + 2x_3 + x_5 >= 300,
    2x_2 + x_4 + x_5 >= 400,
    2x_1 + x_2 + 2x_4 >=1000,

    CB

    oh yes, i wrote the same thing in my notes.

    Thanks for all ur help.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Member
    Joined
    Jul 2009
    Posts
    111
    Thanks
    1

    Thumbs up @Thine Blood and Captain Black

    Thanks for sharing the procedure of the LPP's formulation;
    It really helped:

    MAX
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Help to formulate a non linear least squares problem
    Posted in the Advanced Applied Math Forum
    Replies: 0
    Last Post: August 20th 2011, 01:51 AM
  2. Linear Programming Problem
    Posted in the Advanced Applied Math Forum
    Replies: 0
    Last Post: September 20th 2009, 08:01 PM
  3. Linear programming problem
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: June 11th 2008, 08:57 PM
  4. Linear Programming Problem
    Posted in the Business Math Forum
    Replies: 6
    Last Post: December 24th 2007, 12:20 PM
  5. Linear Programming Problem
    Posted in the Pre-Calculus Forum
    Replies: 5
    Last Post: June 22nd 2006, 01:57 AM

Search Tags


/mathhelpforum @mathhelpforum