0
$\begingroup$

I have a homework question :

enter image description here

I figured out that the profit for keyboard $1$ is €$3$ ($k_1 = 25-(5+5+12) = 3$) and for keyboard $2$ its €$2$ ($k_2 = 22 - (4+10+6)$)

Therefore we want to maximize $p = 3k_1+2k_2$, right? So I think the contraints are:

$k1 \leq 10$ .. because then employee number $2$ has worked $20$ hours

$k_2 \leq 20$ .. because then employee number $2$ has worked $20$ hours

I think I need more constraints... but I can't figure out which. Just producing $10$ keyboards of type one seems to simple. Am I missing something ?

$\endgroup$
2
  • $\begingroup$ All three answers so far seem to arrive at the same optimal solution. Enjoy. $\endgroup$
    – mvw
    Nov 22, 2015 at 4:08
  • $\begingroup$ @mvw Because this is a linear optimization problem, the solution (if unique) will be in a corner. That and a probably purposeful coincidence on the parameters of the problem leads to the equivalence. But, if, say, employee $1$ had $20$ working hours available, I suspect the solutions would differ. Then, the fact that the hours worked by each employee are complements not substitutes would matter. $\endgroup$
    – mzp
    Nov 22, 2015 at 12:34

2 Answers 2

Reset to default
2
$\begingroup$

Let $x_{ij}$ be the number of hours worker $i$ spends producing product $j$. Then, the problem can be written as

$$ \max_{x_{11},x_{12},x_{21},x_{22}} (25-5)\min\left\{x_{11},\frac{x_{21}}{2}\right\} + (22-4)\min\left\{\frac{x_{12}}{2},x_{22}\right\} - 5(x_{11}+x_{12}) - 6(x_{21}+x_{22})$$

subject to

\begin{align} x_{11}+x_{12} &\leq 40 \\[1.5ex] x_{21}+x_{22} &\leq 20 \end{align}

Notice that the $\min$'s in the objective function appear because to produce a good you need both worker $1$ and worker $2$. Another way to incorporate this restriction is to add more constraints, then, the problem becomes

$$ \max_{x_{11},x_{12},x_{21},x_{22}} (25-5)x_{11} + (22-4)x_{22} - 5(x_{11}+x_{12}) - 6(x_{21}+x_{22})$$

subject to

\begin{align} x_{11}+x_{12} &\leq 40 \\[1.5ex] x_{21}+x_{22} &\leq 20 \\[1.5ex] x_{21}&=2x_{11}\\[1.5ex] x_{12}&=2x_{22} \end{align}

$\endgroup$
3
  • $\begingroup$ Does it really matter? Since there is a relationship shop between how many hours each employee spends on each product and how many of each product are produced, there should be transformation from one specification to the other, I think... Now the constraints in his problem... I would think he should try specifying hours worked in terms of how many of each product is produced. This is all just conjecture, though; I haven't worked any of this out and this is not an area I am very familiar with. $\endgroup$
    – majmun
    Nov 22, 2015 at 1:49
  • $\begingroup$ @majmun I edited the answer. Let me know if it makes more sense now. $\endgroup$
    – mzp
    Nov 22, 2015 at 2:14
  • $\begingroup$ This gives the solution $(x_{11}, x_{22}, x_{12}, x_{21})^\top = (0,20,40,0)^\top$ with objective $40$. $\endgroup$
    – mvw
    Nov 22, 2015 at 4:07
0
$\begingroup$

Profit = Sales - Costs - Salaries $$ 25 x_1 + 22 x_2 - 5 x_1 - 4 x_2 - 5 h_1 - 6 h_2 = 20 x_1 + 18 x_2 - 5 h_1 - 6 h_2 $$ Constraints: $$ h_1 \le 40 \\ h_2 \le 20 \\ h_1 = x_1 + 2 x_2 \iff x_1 + 2 x_2 - h_1 = 0\\ h_2 = 2 x_1 + x_2 \iff 2 x_1 + x_2 - h_2 = 0 $$ This leads to the linear program: $$ \begin{array}{ll} \max & c^\top x \\ \text{w.r.t.} & A x = 0 \\ & B x \le b \\ & x \ge 0 \end{array} $$ where we rename the hours $h_1$ to $x_3$ and $h_2$ to $x_4$, with $$ c = (20, 18, -5, -6) \\ x = (x_1, x_2, x_3, x_4) \\ A = \left( \begin{array}{rr} 1 & 2 & -1 & 0 \\ 2 & 1 & 0 & -1 \end{array} \right) \\ B = \left( \begin{array}{rr} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array} \right) \quad b = \left( \begin{array}{l} 40 \\ 20 \end{array} \right) $$ Note that units and hours are non-negative integer values, so $x \in \mathbb{Z}^4$, this is an integer linear program.

Solution

Running this through lpsolve, I get the solution $$ (x_1, x_2, x_3, x_4)^\top = (0,20,40,20)^\top $$ with profit $40$.

$\endgroup$
2
  • $\begingroup$ This would be correct if to produce keyboard $1$, for instance, you needed $1$ hour from employee $1$ OR $2$ hour from employee $2$. $\endgroup$
    – mzp
    Nov 22, 2015 at 2:50
  • $\begingroup$ @mzp I think your statement is wrong. $\endgroup$
    – mvw
    Nov 22, 2015 at 3:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .