please see this simple linear programming exercise and its solution from my textbook. The task is to convert the prose and matrix to a formal linear programming problem.

My answer matched theirs except I got different constraints:

$2.5x_A + 3x_B + 2x_C + 4x_D + r = 1400$ (This one is OK)

$10x_A + 12x_B + 8x_C + 15x_D + s = 150$ (apparently 150 is incorrect)

$5x_A + 7x_B + 4x_C + 9x_D + t = 80$ (apparently 80 is incorrect)

$x_A + x_B + x_C + x_D + u = 500$ (this is not in the solution at all: I wrote this because they say "market research says they will sell at most 500 each week")

Could someone explain to me where I have gone wrong? Why are 150 and 80 incorrect? Why is my last constraint not actually a constraint?

I have highlighted the areas of confusion in green below. Thanks!

Linear programming exercise

  • 2
    $\begingroup$ 150 hours is 9000 minutes. $\endgroup$ – lhf Apr 28 '11 at 11:57
  • $\begingroup$ Ahhh thank you! I should have seen that, sorry. Any ideas on my extra constraint? $\endgroup$ – Danny King Apr 28 '11 at 11:59
  • $\begingroup$ I would agree with including your extra constraint. But that is problem interpretation, not mathematics. It would bias you to make more D if you were hitting your head, which would be reasonable if you can sell an arbitrary collection of 500. $\endgroup$ – Ross Millikan Apr 28 '11 at 12:59

So this question is officially answered...

I would say that the constraint $x_A + x_B + x_C + x_D + u = 500$ is necessary and that the textbook solution is incorrect. The only reason to exclude it is if it is redundant. But it is not redundant, as you can easily check by stuffing both models into your favorite LP solver. Without the constraint, the optimal solution is to make 560 of type A for a weekly profit of 4480 pounds. However, with the constraint, the optimal solution is to make 400 of type A and 100 of type D for a weekly profit of 4100 pounds. As Ross Millikan notes, since you can't make as much of type A as you would otherwise want, the constraint biases you to shift some of your production to type D.

Sometimes a textbook's web site (or the author's web site) will list errata for the book. You could check if leaving out this constraint is listed as one of those errors.


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.