Problem about maximize profit

Question

A company has 20 pair of shoes and 60 shirts to sell together in two different ways:

• A: one pair of shoes and one shirt for \$20
• B: one pair of shoes and five shirts for \$80

I have to find out how many types of A and B I have to sell to maximize the profit.

I tried to find the solution of the system $$\left\{\begin{array}{l} x+y=20 \\ x+4y=80 \end{array}\right.$$ but it doesn't work.

What am I supposed to do?

Answer 1

Define $x_1$ and $x_2$ as the number type $A$ and $B$ deals, respectively, then the problem can be formulated as the following LP: \begin{align} \text{maximize} &\quad 20x_1 + 80x_2,\\ \text{subject to} &\quad x_1+x_2 \leq 20,\\ &\quad x_1 + 5x_2 \leq 60,\\ &\quad x_1,x_2\geq 0. \end{align}

Converting this to standard form: \begin{align} \text{minimize} &\quad -20x_1 - 80x_2,\\ \text{subject to} &\quad x_1+x_2 +x_3 = 20,\\ &\quad x_1 + 5x_2 +x_4= 60,\\ &\quad x_1,x_2,x_3, x_4\geq 0, \end{align} then we can solve this using the simplex algorithm.

First, form the tableau: $$ T = \begin{pmatrix} 1 & 1 & 1 & 0 & 20\\ 1 & 5 & 0 & 1 & 60\\ -20 & -80 & 0 & 0 & 0 \end{pmatrix}, $$ then apply pivoting (the pivots are indicated by squares): $$ \begin{pmatrix} 1 & 1 & 1 & 0 & 20\\ 1 & \fbox{5} & 0 & 1 & 60\\ -20 & -80 & 0 & 0 & 0 \end{pmatrix} \to \begin{pmatrix} 1 & 1 & 1 & 0 & 20\\ 1/5 & 1 & 0 & 1/5 & 12\\ -20 & -80 & 0 & 0 & 0 \end{pmatrix} \to \begin{pmatrix} \fbox{4/5} & 0 & 1 & -1/5 & 8\\ 1/5 & 1 & 0 & 1/5 & 12\\ -4 & 0 & 0 & 16 & 960 \end{pmatrix} \to \begin{pmatrix} 1 & 0 & 5/4 & -1/4 & 10\\ 1/5 & 1 & 0 & 1/5 & 12\\ -4 & 0 & 0 & 16 & 960 \end{pmatrix} \to \begin{pmatrix} 1 & 0 & 5/4 & -1/4 & 10\\ 0 & 1 & -1/4 & 1/4 & 10\\ 0 & 0 & 5 & 15 & 1000 \end{pmatrix}, $$ so the number of type $A$ and $B$ deals that maximize profit is $x_1=x_2=10$, respectively, with a profit of $1000$.

Answer 2

Let $x$ be the number of bundles A sold and $y$ be the number of bundles B sold. You want to maximize the function $f(x,y)=20x+80y$ subject to some constraints on the available stock. Obviously, $x,y\geq0$. The number of shirts sold is $x+5y$. Since there are 60 shirts available, we have $x+5y\leq 60$. Similarly, $x+y\leq20$. If you plot these constraints, you'll see the region enclosed is closed and bounded. Since the gradient of $f$ is constant and non-zero, the global maximum will be on the boundary of the region (for example $x+y=20$ subject to the other constraints which imply $x\geq 10$). By direct computation, you can find that the max occurs at $x=y=10$ for a profit of $1000.