A firm produces two different models of heavy machines; say (A) and (B). The market demand implies that the final profit of each model is 1200 and 2500, respectively. The production of each car (of both models) is organized in three different factories (engine, (E), skeleton (S), complements (C)). The following table explain the days needed for each model in each factory to produce the cars: (A,E)=2, (A,S)=1, (A,C)=1, (B,E)=4, (B,S)=4, (B,C)=7

Because of safety reasons and the agreements between the company and the workers, the engine factory is open no more than 350 days per a year, the skeleton factory is open no more than 280 days per a year while complements factory may work up to 320 days per a year. Find the linear program to optimize the profits, and solve it. Write the dual problem. Is it possible to determine the shadow prices of the three factories?

  • $\begingroup$ @Brian I had removed "functional-analysis" in the suggested edit, but it says that I removed linear-programming. This tag is actually correct, so the edit can be rejected. $\endgroup$ – jonsca Oct 21 '13 at 23:57

The following is a pedestrian solution intended for high-schoolers.

A production plan is a pair $(a,b)$ of nonnegative numbers encoding the intention to produce $a$ units of product $A$ and $b$ units of product $B$. Given such a production plan the expected profit $p$ in hundreds of dollars is $$p=12a+25b\ .$$ The conditions given in the text amount to $$2a+4b\leq 350,\quad a+4b\leq 280,\quad a+7b\leq 320\ .$$ Each of these conditions together with $a\geq0$, $\>b\geq0$ defines a triangle in the first quadrant of the $(a,b)$-plane. A plan is admissible if it belongs to all three triangles; see the following figure.

enter image description here

The figure shows a line $p={\rm const.}$ as well. All such lines are parallel, and lines shifted north-east correspond to higher profits. Moving the red line towards the red quadrilateral of admissible plans shows that the optimal plan is at the point $P=(117,29)$ where the $(E)$- and the $(C)$-line intersect. We were lucky that $P$ has integer coordinates, because otherwise we would run into an "integer programming problem", which is another matter.


You may start defining the integer variables $x_{ij}$ as the quantity of component $j \in \{E,S,C\}$ manufactured for machine-type $i \in \{A,B\}$ (or, similarly, the number of machine-type $i$ manufactured in the factory $j$. In the following, I prefer to talk about components, but the reasoning is the same).

So, for example $x_{AE}$ is the number of engines produced in the factory $E$ for type $A$ machines. Then, you can write the constraint about the opening days:

$$ \sum_{i \in \{A,B\}} d_{ij}\cdot x_{ij} \leq O_j\;\;\;\;\forall j \in \{E,S,C\} $$

where $d_{ij}$ is the time required to manufacture one unit of component $j$ for a machine type $i$, and $O_j$ is the number of opening days for each factory $j \in \{E,S,C\}$ (that is $d_{AE} = 2, d_{AS} = 1$ and so forth).

To express the objective function, you have to evaluate the number of machines produced. Assuming that each machine uses exactly one engine, you can write:

$$ \max \sum_{i \in \{A,B\}}\pi_i \cdot x_{iE} $$

where $\pi_i$ is the profit for one machine type $i$.

You finally add the non-negative constraints:

$$ x_{ij} \geq 0 \,\,\,\,\, integer$$

I have assumed integrity of the variables, I let you discuss whether it can be relaxed or not.

  • $\begingroup$ I have some problems to understand this: If I can ask you more again, now we must find: $max 1200X_{AE} + 2500x_{BE}$ subject $x_{AE}, x_{BE} >=0$ $\endgroup$ – Johny Oct 22 '13 at 11:50
  • $\begingroup$ I think @Christian Blatter's answer is far more accurate, direct and simple than mine. For short, his answer is better. $\endgroup$ – Libra Oct 22 '13 at 13: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.