# Converting minimizing wasted string when partitioning 200cm into 90,70 and 50cm to Linear Programming problem

Say you have 3 products that require x amount of string to make:
Product A: requires 90 cm of string
Product B: requires 70 cm of string
Product C: requires 50 cm of string
String comes to you from your suppler in sizes of 200 cm only.
You get a large order:
300 of A
400 of B
1000 of C

You generate 6 ways of cutting 200 cm string to minimize waste. Ordered by most wasteful to least
(90,70) with a waste of 40 cm
(50,50,70) with a waste of 30 cm
(90,90) with a waste of 20 cm
(90,50,50) with a waste of 10 cm
(70,70,50) with a waste of 10 cm
(50,50,50,50) with a waste of 0 cm

You are informed that your machine can't cut the string into 4 equal pieces so you have to ignore (50,50,50,50).

Convert this to an LP. Label the variables($$y_1,y_2,...,y_5$$) s.t. ribbon wasted is ordered from greatest to least

This sounds like a question for learning the subject, in which case trying it yourself first and at least asking specific questions would help you actually learn it. But that is your business I guess.

You have three constraints (getting enough of each product) (beside the $$\geq 0$$ ones ) and wasted string creates the cost function. Look at each one how much they gives as product.

$$y_1+2\cdot y_3+y_4\geq 300$$ because a needs $$90$$ and $$1$$ gives $$1$$ $$90$$ cm, $$3$$ gives $$2\cdot 90$$ cm and $$y_4$$ gives $$1$$ $$90$$ cm.

similarly: $$y_1+y_2+2y_5\geq 400$$

$$2\cdot y_2+2\cdot y_4+y_5\geq 1000$$

also of course $$y_1,...y_5\geq 0$$

For costs just multiply each variable with the corresponding string waste.

• I think that's supposed to be $y_1+2y_3+y_5$, yes? I really like this solution except if you turn it into the primal I don't know if it makes sense? Because the first constraint for the primal becomes $x_1+x_2\le 40$ and I'm not entirely sure that makes sense? Cause in my head the primal should be making as much $x_1, x_2$ and $x_3$ as possible for each machine less than 200. So shouldn't the constraint be $90x_1+70x_2 \le 200$? Maybe I'm thinking about it wrong. – Dylan Y Oct 9 '19 at 20:46
• No, $\large{1y_1+2y_3+1y_4\geq 300}$ is correct. The combination $4$ contains one string of $90$ cm ($\color{red}{90}$, 50,50). – callculus Oct 10 '19 at 4:53
• This is the primal problem. The first constraint ($y_1$) of the dual is $x_1+x_2+2x_3\leq 40$. You have for each constraint of the primal (3) a variable at the dual. – callculus Oct 10 '19 at 5:05
• So you want to make less than 40 of $x_1+x_2+2x_3$? That sounds off no? Shouldn't be maximizing making the product but you want less than 200 because the string is 200? – Dylan Y Oct 11 '19 at 19:08
• I thought the primal was maximizing a function? This is minimizing so doesn't that make it the dual? – Dylan Y Oct 11 '19 at 19:09