# What would be a better way to solve this and how? with less waste.

A supplier for the construction industry must supply Its customers PVC pipes of certain lengths; manufacturers will sell the pipes in fixed lengths and he must cut them to satisfy the conditions demanded by customers, while at the same time ensuring that the waste is as small as possible.

If the pipes supplied by the manufacturer are 12 meters in length, Determine how many of them are required and how they should be cut to give compliance with the following order, looking for the least possible waste: • 60 tubes of 3 meters in length • 49 tubes of 4 meters in length • 12 tubes of 7 meters in length

Whay I've got so far is that in the first one (60 tubes of 3 meters in length) is just 15 pipes of 12 meters in length cut to make 4 pipes each and reach the 60 required. Then, 12 pipes of 12 meters in length to make 12 pipes of 7 meters. I use the 12 remaining pipes of 5m to make 12 of 4m and I ended up with 37 left to make and 12 pieces of 1m of waste. I get 3 pipes of 4m for each pipe of 12m, with the latter I created 36 pipes of 4m. Then, one more pipe to the one left and 8m of waste. That means 20m of waste. Is there any other way to do this? With less waste?

• The concepts that you wrote are yet to complex for me now. This is a problem that I got in a geometry class. Is it possible with geometry? – Scoofjeer Aug 20 '17 at 17:46
• Yes, you draw the simulteneous equations on a graph, i.e y = mx, and p = ts, with m and t as the gradients, you should obtain some constrained geometry and the maximal ratio for cutting should be evident. – McTaffy Aug 20 '17 at 18:07
• Thank you very much for your help, but, May I have an example? – Scoofjeer Aug 20 '17 at 18:10

This is likely an inelegant way to solve this problem using linear programming but it is the best I can do for now. We note that there are only so many ways you can cut a 12-meter pipe into segments of the given lengths; in particular,

\begin{align} 12 &= 3 && && && &+& 9 \tag{1} \\ &= 3 &+& 3 && && &+& 6 \tag{2} \\ &= 3 &+& 3 &+& 3 && &+& 3 \tag{3} \\ &= 3 &+& 3 &+& 3 &+& 3 &+& 0 \tag{4} \\ &= 3 &+& 4 && && &+& 5 \tag{5} \\ &= 3 &+& 4 &+& 3 && &+& 2 \tag{6} \\ &= 3 &+& 4 &+& 4 && &+& 1 \tag{7} \\ &= 3 &+& 7 && && &+& 2 \tag{8} \\ &= 4 && && && &+& 8 \tag{9} \\ &= 4 &+& 4 && && &+& 4 \tag{10} \\ &= 4 &+& 4 &+& 4 && &+& 0 \tag{11} \\ &= 4 &+& 7 && && &+&1 \tag{12} \end{align}

In each line above, the number to the far right (not in parentheses!) indicates the waste while the others are the segments. There are 12 possible ways to cut a pipe. Let us say we cut $x_1$ pipes in the 1st way, $x_2$ pipes in the 2nd way, ..., $x_{12}$ pipes in the 12th way. Now these $x_i$ must all be nonnegative and must further satisfy

\begin{align} 60 &= x_1 + 2x_2 + 3x_3 + 4x_4 + x_5 + 2x_6 + x_7 + x_8 \\ 49 &= x_5 + x_6 + 2x_7 + x_9 + 2x_{10} + 3x_{11} + x_{12} \\ 12 &= x_8 + x_{12} \end{align} (Do you see why?) And, we want to minimize the waste, which is given by the expression $$9x_1 + 6x_2 + 3x_3 + 5x_5 + 2x_6 + x_7 + 2x_8 + 8x_9 + 4x_{10} + x_{12}$$

This is now a typical linear programming problem and can be solved with a computer/calculator. I used the Sage program to solve it and got the answer as

• 15 pipes with the 4th way
• 2 pipes with the 10th way
• 11 pipes with the 11th way
• 12 pipes with the 12th way

giving 20 wasted meters.

• I'm sorry, I don't see why the 60=x1+2x2...and so on. Previous to that I understood everything. – Scoofjeer Aug 20 '17 at 19:34
• OK, hint: in the '60 = ...' equation the 60 actually represents the condition that you want 60 tubes of length 3 meters. Do you see it now? – shardulc says Reinstate Monica Aug 20 '17 at 19:35
• yep, I see it now. Thanks, that's an interesting way to see it. I thought that there was another way in which you waste less than 20m, but apparently there's not. – Scoofjeer Aug 20 '17 at 19:40
• Yes, this is the least wastage. If you like the answer please upvote and maybe accept! :) – shardulc says Reinstate Monica Aug 20 '17 at 19:57
• The solution is not unique: 13 the 4th way, 15 the 11th way, 8 the 8th way, 4 the 12th way, wasted 20 meters.... What is the difference between he 3rd & 4th way, or between the 10th& 11th way? – DanielWainfleet Aug 21 '17 at 0:45