Formulate as a Linear programming problem

ThineBlood · #1 $Old$ July 21st, 2009, 10:15 PM

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:

∙ 90cm×3m for product A;
∙ 70cm×3m for product B; and
∙ 50cm×3m for product C.

The company receives metal sheets with size 2m×3m, 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 2m×3m metal sheet into pieces of sizes 90cm×3m, 70cm×3m and 50cm×3m 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.

CaptainBlack · #2 $Old$ July 21st, 2009, 11:39 PM

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:

∙ 90cm×3m for product A;
∙ 70cm×3m for product B; and
∙ 50cm×3m for product C.

The company receives metal sheets with size 2m×3m, 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 2m×3m metal sheet into pieces of sizes 90cm×3m, 70cm×3m and 50cm×3m 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

ThineBlood · #3 $Old$ July 22nd, 2009, 07:02 PM

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.

CaptainBlack · #4 $Old$ July 22nd, 2009, 08:38 PM

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

ThineBlood · #5 $Old$ July 23rd, 2009, 10:10 PM

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

CaptainBlack · #6 $Old$ July 23rd, 2009, 11:54 PM

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

ThineBlood · #7 $Old$ July 24th, 2009, 04:27 AM

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$

CaptainBlack · #8 $Old$ July 24th, 2009, 06:43 AM

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

ThineBlood · #9 $Old$ July 24th, 2009, 07:48 AM

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.

CaptainBlack · #10 $Old$ July 24th, 2009, 07:59 AM

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.

∙ 90cm×3m for product A;
∙ 70cm×3m for product B; and
∙ 50cm×3m for product C.

The company receives metal sheets with size 2m×3m, 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

ThineBlood · #11 $Old$ July 24th, 2009, 10:23 PM

Quote:

Originally Posted by CaptainBlack $View Post$

∙ 90cm×3m for product A;
∙ 70cm×3m for product B; and
∙ 50cm×3m for product C.

The company receives metal sheets with size 2m×3m, 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.

MAX09 · #12 $Old$ July 31st, 2009, 04:08 AM

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

MAX