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?
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
giving 20 wasted meters.