Problem Statement: A television manufacturer has decided to produce and sell two different types of TV sets, small and big. They assure that the small will give a profit of \$300 per unit and the big a profit of \$500 per unit. They have one production plant with four departments: molding, soldering, assembly and inspection. Each TV set is processed in sequence through these four departments. Each department has a limited capacity given by a maximum number of working hours per year. We assume that they can sell all the TV sets they are able to produce and the market is not a restriction.

Objective function:

  1. Maximize $$Z \equiv 300 x_1+500 x_2 $$ subject to the following constraints:

  2. $x_1+5x_2 \leq 4000\qquad$ [Molding capacity]

  3. $x_1+x_2 \leq 1200\qquad $ [Soldering capacity]
  4. $2x_1+x_2\leq 2000\qquad $ [Assembly capacity]
  5. $2x_1+5x_2 \leq 5000\qquad $ [Inspection capacity]
  6. $x_1,x_2 \geq 0 \qquad $ [Non-negativity]

The dual is given by:

  1. Minimize $$Z^\prime = 4000u_1+1200u_2+2000u_3+5000u_4$$ subject to
  2. $u_1+u_2+2u_3+2u_4 \geq 300\qquad$ [Small TV Sets]
  3. $5u_1+u_2+u_3+5u_4 \geq 500\qquad$ [Big TV Sets]
  4. $u_1,u_2,u_3,u_4 \geq 0$.

My question is: What is the physical interpretation of the dual variables ($u_i$)? Is it cost/hr or profit/hr for a specific operation? If I consider cost, then the objective function is OK. But in case of constraints, cost cannot be greater than profit. Again, if I consider profit, then the constraints are OK. But in the objective function profit cannot be minimized.

  • $\begingroup$ My suspicion at this point is that those voting to close this question thought that it presents a linear programming problem and asks how to solve it. $\endgroup$ – Michael Hardy Aug 5 '17 at 22:58
  • $\begingroup$ $5u_1 + \cdots \ge 500.$ The number $500$ is a number of sets. The units in which the coefficient $5$ is measured are units of molding per set. So $$ \Big( \text{molding per set} \times u_1 \Big) = \text{sets}. $$ So the units of $u_1$ must be $\dfrac{\text{sets}^2}{\text{units of molding}}.$ At this point I don't see how to give that a physical interpretation. $\qquad$ $\endgroup$ – Michael Hardy Aug 5 '17 at 23:32

The original problem asks to maximize profits, given that you make a certain amount of profit for each of the different TV types you manufacture, and given that each TV type costs a certain amount to make, in terms of hours spent in each department, and that total costs (in hours) per department are limited.

There are several ways to interpret the dual problem, which is about determining the value of each hour in each department. One way of interpreting the value of each hour in each department is imagining how much you'd have to "sell" each hour for in order to make as much profit (\$300 for the hours spent on a small TV; \$500 for the hours spent on a large TV) as you currently do using those departmental hours yourself.

The dual problem is a minimization problem because the true value of the departmental hours is equal to the amount of money you make when you when you sell departmental hours for just the amount it takes to make exactly \$300 on the hours spent per small TV, etc.— no more.

Here's a story to go with the dual problem:

You are a television manufacturer who sells two types of TVs, small and big. Your goal is to make a profit of \$300 on small TVs and \$500 on large TVs, and so you must set your operational costs accordingly. Your constraints come from the manufacturing pipeline, where the number of work hours are limited per year.

You are considering selling the use of your departmental facilities to other companies, for an hourly fee. When others are using your facilities, you are not making any television-based profit—and so in order to avoid losing money, you must charge rent so that you make at least as much money as you would making televisions. This requires determining the value of each hour in each department $u_i$. (Assume that all hours you offer will be taken up; the market is not a factor.) How much should you charge per hour?

  1. Consider the hours spent to make a small television. If someone rents those hours from you, you should make at least \$300 from them, otherwise you'd be better off spending those hours to make a small television yourself. The same goes for large televisions and \$500. Hence,

    \begin{align*} u_1 + u_2 + 2u_3 + 2u_4 &\geq 300\\ 5u_1 + u_2 + u_3 + 5u_4 &\geq 500 \end{align*}

  2. The rents should all be non-negative: $u_i \geq 0$.

  3. You would like to determine the minimum amount you could charge in rent and still make a profit; this minimum limit will tell you the the break-even value of each hour in each department. We are assuming that all hours you make available will be taken up; hence you want to find the minimum, subject to the above constraints, of the total amount of money you'd make for selling all your hours: $$Z^\prime = 4000u_1 + 1200u_2 + 2000u_3 + 5000u_4$$

More generally, if the original problem asks you to maximize some objective function $Z$, where you get a certain amount of $Z$ for each of the things $x_1,\ldots, x_m$ you have, and each of the things requires a certain amount of limited $(\leq)$ ingredients/resources to make, ...

...the dual problem asks you to determine the value of each of your ingredients/resources. To do so, you can imagine selling off the ingredients/resources at certain rates. The fact that you can spend those resources to make the things $x_1,\ldots, x_m$ provides lower bounds $(\geq)$ on the value of those ingredients/resources. (To put it another way, you would only sell your resources at competitive rates, where it makes sense to sell them instead of spending them to make things.) You find the break-even value of those resources by finding values that minimize how much money you'd make if you sold off all of your resources instead of using them to make things, subject to the constraints that you sell them at rates that make sense given what else you could use them for.

  • $\begingroup$ Thank you so much for such nice explanation. Now it is clear. So, u= rent for operation/hr/unit. $\endgroup$ – user3553918 Aug 7 '17 at 14:17
  • $\begingroup$ @user3553918 Yes, or in other words $u_i$ is a measure of the value of an hour of runtime in each department, given what you can make with them. (Dollars per hour, a.k.a. hourly rate) $\endgroup$ – user326210 Aug 7 '17 at 18:12
  • $\begingroup$ Thank you so much, sir. This is a nice lucid explanation. $\endgroup$ – user3553918 Aug 10 '17 at 13:59
  • $\begingroup$ @user3553918 Glad to help. If this answer solves your problem, will you mark it as accepted? $\endgroup$ – user326210 Aug 11 '17 at 15:00
  • $\begingroup$ Yes, of course. But how to mark? $\endgroup$ – user3553918 Nov 7 '17 at 15:26

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.