Setting up a linear programming word problem

Question

Problem: A metalworking shop needs to cut at least 32 large disks and 219 small ones. There are three cutting patterns for the standard size metal rectangle. One cutting pattern produces two large disks with 14% waste. A second cutting pattern produces five small disks with 29% waste. The third cutting pattern produces one large and three small disks with 24% waste. What is the minimum waste way to make the required disks?

Having trouble setting up the objective function and constraints. The percentage makes me think that I cannot use large disks and small disks as my x1,x2.

Answer 1

The thing you have direct control over is:
number of pattern 1s, number of pattern 2s, number of pattern 3s.
I think they should be your $x1,$ $x2$, $x3$

Answer 2

$% Predefined Typography \newcommand{\paren} [1]{\left({#1}\right)} \newcommand{\bparen}[1]{\bigg({#1}\bigg)} \newcommand{\brace} [1]{\left\{{#1}\right\}} \newcommand{\bbrace}[1]{\bigg\{{#1}\bigg\}} \newcommand{\floor} [1]{\left\lfloor{#1}\right\rfloor} \newcommand{\bfloor}[1]{\bigg\lfloor{#1}\bigg\rfloor} \newcommand{\ceil} [1]{\left\lceil{#1}\right\rceil} \newcommand{\bceil} [1]{\bigg\lceil{#1}\bigg\rceil} \newcommand{\mag} [1]{\left\lVert{#1}\right\rVert} \newcommand{\bmag} [1]{\bigg\Vert{#1}\bigg\Vert} \newcommand{\abs} [1]{\left\vert{#1}\right\vert} \newcommand{\babs} [1]{\bigg\vert{#1}\bigg\vert} % \newcommand{\labelt}[2]{\underbrace{#1}_{\text{#2}}} \newcommand{\label} [2]{\underbrace{#1}_{#2}} \newcommand{\ulabelt}[2]{\overbrace{#1}_{\text{#2}}} \newcommand{\ulabel} [2]{\overbrace{#1}_{#2}} % \newcommand{\setcomp}[2]{\left\{~{#1}~~\middle \vert~~ {#2}~\right\}} \newcommand{\bsetcomp}[2]{\bigg\{~{#1}~~\bigg \vert~~ {#2}~\bigg\}} % \newcommand{\iint}[2]{\int {#1}~{\rm d}{#2}} \newcommand{\dint}[4]{\int_{#3}^{#4}{#1}~{\rm d}{#2}} \newcommand{\pred}[2]{\frac{\rm d}{{\rm d}{#2}}#1} \newcommand{\ind} [2]{\frac{{\rm d} {#1}}{{\rm d}{#2}}} \newcommand{\predp}[2]{\frac{\partial}{\partial {#2}}#1} \newcommand{\indp} [2]{\frac{{\partial} {#1}}{\partial {#2}}} \newcommand{\predn}[3]{\frac{\rm d}^{#3}{{\rm d}{#2}^{#3}}#1} \newcommand{\indn} [3]{\frac{{\rm d}^{#3} {#1}}{{\rm d}{#2}^{#3}}} % \newcommand{\ii}{{\rm i}} \newcommand{\ee}{{\rm e}} \newcommand{\exp}[1] { {\rm e}^{\large{#1}} } % \newcommand{\and} {~\text{and}~} \newcommand{\xor} {~\text{xor}~} \newcommand{\or} {~\text{or}~} \newcommand{\T} {\text{True}} \newcommand{\F} {\text{False}} % \newcommand{\red} [1]{\color{red}{#1}} \newcommand{\blue} [1]{\color{blue}{#1}} \newcommand{\green}[1]{\color{green}{#1}} $ $$p_x \ge 0$$ $$2p_1 + 0p_2 + 1p_3 \ge 32$$ $$0p_1 + 5p_2 + 3p_3 \ge 219$$

$$.14 p_1 + .29 p_2 + .24 p_3 = W$$

Minimize $W$. Upper bounds can be inferred: $p_1 < 17$, $p_2 \le \floor{\frac {219}{5} }$ so $p_2 < 44$, and $p_3 \le {\rm Min}\paren{\floor{ \frac {32}{1} }, \floor{ \frac {219}{3} }}$ so $p_3 \le 32$.

An approach that doesn't use programming is to write $W$ in terms of $p_3$.

$$\ceil{ \frac{32 - p_3}{2} } = p_1$$ $$\ceil{ \frac{219 - 3p_3}{5} } = p_2$$ $$W = .14 \ceil {\frac{32 - p_3}{2} } + .29 \ceil{ \frac{219 - 3p_3}{5}\ } + .24 p_3$$

Now using $\ceil {a/b } = \floor{ (a - 1)/b } + 1$ and $\floor{ a/b } b + a ~{\rm mod}~ b = a$:

$$W = .14 \floor{ \frac{31 - p_3}{2} } + .29 \floor{ \frac{218 - 3p_3}{5} } + .24 p_3 + 0.43$$

$$W = 15.244 - 0.07\bparen{(31 - p_3)~{\rm mod}~ 2} - 0.058\bparen{(218 - 3p_3) ~{\rm mod}~ 5} - 0.004 p_3$$

$$W = \label{14.942 - 0.004 p_3}{x} + \label{0.07\bparen{p_3~{\rm mod}~ 2} + 0.058\bparen{(3p_3 + 1) ~{\rm mod}~ 5}}{y}$$ (In the last line using $a ~{\rm mod}~ b = b - 1 - \bparen{(b - 1 - a) ~{\rm mod}~ b}$)

From expression $x$ minimizing $W$ means maximizing $p_3$ under $p_3 \le 32$, and expression $y$ suggests that want $p_3 \equiv 0 \pmod 2$ and $3p_3 + 1 \equiv 0 \pmod 5$, which is $p_3 = 3 + 5k$. The largest value which meets these requirements is $p_3 = 28$, giving the optimal value:

$$\begin{cases} p_1 = 2 \\ p_2 = 27 \\ p_3 = 28 \\ W = 14.83 \end{cases}$$