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.

  • $\begingroup$ 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. $\endgroup$ – Dylan Y Oct 9 '19 at 20:46
  • $\begingroup$ 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). $\endgroup$ – callculus Oct 10 '19 at 4:53
  • $\begingroup$ 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. $\endgroup$ – callculus Oct 10 '19 at 5:05
  • $\begingroup$ 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? $\endgroup$ – Dylan Y Oct 11 '19 at 19:08
  • $\begingroup$ I thought the primal was maximizing a function? This is minimizing so doesn't that make it the dual? $\endgroup$ – Dylan Y Oct 11 '19 at 19:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.