Take two pieces of wood one 84 inches the other 74 inches. Need to cut equal amounts of 12.5 inches and 7.75 inches. How to solve?

Question

So the system would look something like this.

74" < 12.5x + 7.75y < 84"
60" < 12.5w + 7.75z < 74"
y + z = x + w
where x, y, w, z are natural numbers 

Is this right? So i made a computer program and was able to solve the question by iterating through all the numbers. There are three answers. I am wondering if there is a mathematical way of solving this without using a computer program? And how would you do this. Is there a way like with pivoting or Gaussian reduction? I'm looking for the most efficient way of cutting, so i need to compare answers. Thank you

Answer 1

Well we could work in units of one quarter of an inch. The pieces we have are then $336$ units and $296$ units long respectively, a total of $632$ units.

The pieces we want to cut are $50$ units and $31$ units.

Now, we want equal numbers of the two sizes - so each pair comes to $81$ units.

$632=7\times 81 +65$. If we can, therefore, we want seven pieces of each length.

To get a solution, note that $336=6\times 50 + 31 +5$ gives seven pieces with little waste. We then have $296=50+6\times 31 +60$.

I did this by trying to cut as many long pieces as possible from the longest piece of wood. But there is enough spare here to allow for lots of other possibilities. There is room for seven short pieces from the second piece. Then try five $50$s from the first piece etc.

Answer 2

The model, which is usually used is the following:

First you have to find which combinations of small pieces (12.5 inches and 7.75 inches) can be made out of the big pieces (84,74):

84 Inches

$$\begin{array}{|m{cm}|m{1cm}|} \hline \text{combination} & 12.5 &7.75 & \text{remaining wood} & \text{length} &\text{variable} \\ \hline \hline \hline1& 0&10&6.5 & 84 &x_1\\ \hline 2& 1&9&1.75 &84 & x_2 \\ \hline 3& 2&7& 4.75&84 &x_3 \\ \hline 4& 3&6&0 &84 &x_4 \\ \hline 5&4&4&3&84&x_5 \\ \hline 6& 5&2&6 & 84 & x_6 \\ \hline \hline 7& 6&1&1.25 & 84 & x_7 \\ \hline \end{array}$$

Example for calculating the remaining wood (combination 3): $84-2\cdot 12.5-7\cdot 7.75=4.75$ There is not enough wood to cut additional a piece of 7.75 inches.

74 Inches

$$\begin{array}{|m{cm}|m{1cm}|} \hline \text{combination} & 12.5 &7.75 & \text{remaining wood} & \text{length} &\text{variable} \\ \hline \hline \hline1& 5&1&3.75 & 74 &y_1\\ \hline 2& 4&3&0.75 &74 & y_2 \\ \hline 3& 3&4& 5.5&74 &y_3 \\ \hline 4& 2&6&2.5 &74 &y_4 \\ \hline 5&1&7&7.25&74&y_5 \\ \hline 6&0&9&4.25&74&y_6 \\ \hline \end{array}$$

MODEL

variables

$x_i$:Number of pieces with a length of 84 with the combination i

$y_i$:Number of pieces with a length of 74 with the combination i

objective function

The remaining wood has to be minimized. Thus the objective function is

$\text{Min} \ \ 6.5x_1+1.75x_2+4.75x_3+0x_4+3x_5+6x_6+1.25x_7+3.75y_1+0.75y_2+5.5y_3+2.5y_4+7.25y_5+4.25y_6$

restrictions

I suppose, that we need 50 pieces with a length of 12.5 inches and 50 pieces with a length of 7.75 inches.

$$0x_1+x_2+2x_3+3x_4+4x_5+5x_6+6x_7+5y_1+4y_2+3y_3+2y_4+y_5+0y_6\geq 50$$

$$10x_1+x_9+7x_3+6x_4+4x_5+2x_6+1x_7+1y_1+3y_2+4y_3+6y_4+7y_5+9y_6\geq 50$$

$$x_i\in \mathbb N \ \forall \ i=1..7$$

$$y_i\in \mathbb N \ \forall \ i=1..6$$

This problem can be solved by applying the branch and bound algorithm.