Optimization Problem(Linear Programming Model)

[sigh1342]

Homework Statement

A factory has stocked a lot of pipes (sufficient). Each standard pipe is 5-meter long. But this kind of pipe cannot be used directly. We should cut them into three types: 140cm, 95cm and 65cm. In addition, the proportion of these three types of pipes must be 2:4:1. In other words, each product needs two 140cm-long pipes, four 95cm-long pipes and one 65cm-long pipe. It is assumed that the pipes we cut down must be proportional. Now, this factory wants to manufacture K products with least pipes. Formulate this problem as an linear programming model.

Homework Equations

The Attempt at a Solution

I have got a problem on letting the decision variable. I have tried to let there are i 140cm part, j 95cm part and g 65cm part, so that the remaining part of a standard pipe would be 500-x_ijg. But I don't know x_ijg is relevant to the total number of pipes or not.

Hope someone helps. Thanks.

 

[Ray Vickson]

Homework Statement

A factory has stocked a lot of pipes (sufficient). Each standard pipe is 5-meter long. But this kind of pipe cannot be used directly. We should cut them into three types: 140cm, 95cm and 65cm. In addition, the proportion of these three types of pipes must be 2:4:1. In other words, each product needs two 140cm-long pipes, four 95cm-long pipes and one 65cm-long pipe. It is assumed that the pipes we cut down must be proportional. Now, this factory wants to manufacture K products with least pipes. Formulate this problem as an linear programming model.

Homework Equations

The Attempt at a Solution

I have got a problem on letting the decision variable. I have tried to let there are i 140cm part, j 95cm part and g 65cm part, so that the remaining part of a standard pipe would be 500-x_ijg. But I don't know x_ijg is relevant to the total number of pipes or not.

Hope someone helps. Thanks.

Look at the different cutting patterns. For example, one pattern would be to cut 3 140cm + 1 65 cm length from the standard pipe, leaving 15 cm of waste. Another pattern is to cut 2 140's + 2 95's, leaving 30 cm waste. Still another pattern is to cut 2 140's + 1 95 + 1 65, leaving 60 cm waste, etc. So, the first step is to enumerate all the possible patterns that leave < 65 cm of waste. Then, the variables are the number of times you use a pattern; that is, they are x_i = number of times to use pattern i, for i = 1,2,..., N, where N = total number of patterns.

Such cutting-stock problems give LPs that can sometimes have non-integer solutions, so sometimes we need to use the more time-consuming tool of integer programming.

 

[sigh1342]

Thanks Ray.

Following your approach, I've found there are 14 patterns in total. So is that the total number of pipes, z = sum(i = 1 to 14) x_i and my objective is to minimize z on x_i's?

And how about the constraints? I don't know how to make use of the proportion(2:4:1) to establish my inequality.

 

[Ray Vickson]

Thanks Ray.

Following your approach, I've found there are 14 patterns in total. So is that the total number of pipes, z = sum(i = 1 to 14) x_i and my objective is to minimize z on x_i's?

And how about the constraints? I don't know how to make use of the proportion(2:4:1) to establish my inequality.

To produce K items you need to have at least 2K 140cm lengths, at least 4K 95cm lengths and at least K 65 cm lengths. From the variables x1,...,x14, how many 140's , 95's and 65's do you get altogether?

Your objective is fine: it captures exactly what the problem asked for.

Note: in this type of problem it is unavoidable to sometimes produce excess small pipes, so if we need only 400 95's we might end up producing 500. You often cannot meet exact ratios; all you can do is produce *at least enough* of each.