2

The problem is: Beth works a maximum of 20 hours/week programming computers and tutoring math. She receives 25 dollars/hour for programming and 20 dollars/hour for tutoring. She works between 3 and 8 hours/week programming, but always gives more time to tutoring. How many hours should she work at each job to maximize her income?

Let x = # hours programming and y = # hours tutoring.

My constraints are:

Total hours: x+y≤20
Hours programming: 3≤x≤8
Hours tutoring: y>x

My objective function is: 

25x + 20y = maximum profit

Here is my graph:

Here is my graph:

And from looking at the corner points, I can say that the answer is 8 hours programming and 12 tutoring. Is this plus all my other work correct?

Someone
  • 167
  • 5

1 Answers1

1

Yes, your optimal value is correct (even MATLAB agree). Althougt constraints with strict inequalities doesn't make a very good sense in LP (your hour tutoring constraint), there should be >= to make it LP problem. In this formulation the optimal value would not be on the corner of the polytope.

qmsource
  • 286
  • 2
  • 9
  • What is a sharp inequality? – Someone Dec 09 '12 at 20:59
  • Sorry, I meant strict inequality. – qmsource Dec 09 '12 at 21:01
  • So sorry, I don't really understand why it doesn't make sense. – Someone Dec 09 '12 at 21:02
  • For example the value of the x would not be bounded. You could make it go infinitely close to y value, so there would not be a final value. Because of this, the LP problems dont allow sharp inequalities (see http://en.wikipedia.org/wiki/Linear_programming) – qmsource Dec 09 '12 at 21:06
  • So what exactly should I change? – Someone Dec 09 '12 at 21:09
  • Hours tutoring: y>x to Hours tutoring: y>=x. That is it. – qmsource Dec 09 '12 at 21:10
  • Sorry if I'm not understanding this, but since y always has to be greater, wouldn't it still be y > x? – Someone Dec 09 '12 at 21:12
  • Yes, you are of course right. But in this formulation it is not technicaly a LP problem. LP can not contain strict inequalities in the constrains. Since optimal solution of your problem satisfy even the strict inequality, you dont have to really bother. I just noted above to be mathematicaly correct. – qmsource Dec 09 '12 at 21:17
  • Okay, thanks! You've been a great help. – Someone Dec 09 '12 at 21:23
  • 1
    @Someone just to make it clear, the reason is that when you say "$y>x$", you're saying "$y\ne x$". That's no good as we can see from the following ridiculous LPP: $\max z$ subject to $z<1$. As you can see, there is no solution. Why? Well $z$ can't be 1 cause $z<1$. But there is no next smallest number under 1, at least not in the real numbers. So strict inequalities make LPP's impossible to solve. – crf Dec 09 '12 at 22:03
  • So then why shouldn't I change my answer if it's impossible to solve? – Someone Dec 09 '12 at 23:31