0

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

Gooby
  • 497

1 Answers1

2

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.

callculus42
  • 30,550
Pete
  • 36
  • 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. – Gooby Oct 09 '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). – callculus42 Oct 10 '19 at 04: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. – callculus42 Oct 10 '19 at 05: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? – Gooby 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? – Gooby Oct 11 '19 at 19:09
  • "I thought the primal was maximizing a function?" No I can guess where that idea comes from (90% of dual primal explanations using a maximize as primal) but primal is, how to put it, your actual problem. In this case a minimization problem. If it was just about shifting between minimization and maximization you could just flip the signs of the cost function. – Pete Oct 11 '19 at 19:15
  • Okay I’m confused on how the dual to this is a correct representation on this as a maximization problem. Would you mind explaining it to me? – Gooby Oct 11 '19 at 21:13
  • Ah sorry it has been too long since I learned/used it for me to feel confident in explaining duals to someone so I must decline. I can say that if you want it as a maximization problem (to have the standard form?) you don't apply the methods to create the dual you do something like this https://econweb.ucsd.edu/~jsobel/172aw02/notes5.pdf – Pete Oct 13 '19 at 23:27