# Formulate as a Linear programming problem

Printable View

• Jul 21st 2009, 09:15 PM
ThineBlood
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:

∙ 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.
• Jul 21st 2009, 10:39 PM
CaptainBlack
Quote:

Originally Posted by ThineBlood
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
• Jul 22nd 2009, 06:02 PM
ThineBlood
Quote:

Originally Posted by CaptainBlack
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.
• Jul 22nd 2009, 07:38 PM
CaptainBlack
Quote:

Originally Posted by ThineBlood
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 \$\displaystyle 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 \$\displaystyle 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
• Jul 23rd 2009, 09:10 PM
ThineBlood
Quote:

Originally Posted by CaptainBlack
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 \$\displaystyle 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 \$\displaystyle 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 \$\displaystyle 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 \$\displaystyle x_1\$?
• Jul 23rd 2009, 10:54 PM
CaptainBlack
Quote:

Originally Posted by ThineBlood
so this is the part i don't entirely understand. what are \$\displaystyle 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 \$\displaystyle 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
• Jul 24th 2009, 03:27 AM
ThineBlood
Quote:

Originally Posted by CaptainBlack
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?

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

and objective function:

Minimize \$\displaystyle 10x_1 + 10x_2 + 20x_3 + 30x_4 + 40x_5\$

\$\displaystyle x_1,...x_5 >= 0 \$
• Jul 24th 2009, 05:43 AM
CaptainBlack
Quote:

Originally Posted by ThineBlood
so would these be my constraints?

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

and objective function:

Minimize \$\displaystyle 10x_1 + 10x_2 + 20x_3 + 30x_4 + 40x_5\$

\$\displaystyle 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
• Jul 24th 2009, 06:48 AM
ThineBlood
Quote:

Originally Posted by CaptainBlack
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)

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

Thank you so much for all ur help, CaptainBlack. I really appreciate it.
• Jul 24th 2009, 06:59 AM
CaptainBlack
Quote:

Originally Posted by ThineBlood
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)

\$\displaystyle x_1 + 2x_3 + x_5 >= 300,\$
\$\displaystyle 2x_2 + x_4 + x_5 >= 400,\$
\$\displaystyle 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:

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

CB
• Jul 24th 2009, 09:23 PM
ThineBlood
Quote:

Originally Posted by CaptainBlack
∙ 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:

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

CB

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

Thanks for all ur help.
• Jul 31st 2009, 03:08 AM
MAX09
@Thine Blood and Captain Black
Thanks for sharing the procedure of the LPP's formulation;
It really helped:

MAX