3 Replies - 1686 Views - Last Post: 22 August 2011 - 10:10 AM Rate Topic: -----

#1 Booley  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 20-January 11

Integer Solutions to Simplex Algorithm

Posted 20 August 2011 - 02:12 PM

Hello, I've recently learned the simplex algorithm for standard maximization, and I've been practicing it on some cases I made myself (by hand, not with code just yet). I can use it correctly, but sometimes I get a decimal answer that can't be used in the context of the problem. For instance, if a farmer wanted to maximize profit by selling a mix of eggs and meat given some restrictions on resources, I would get something like 5.5 eggs and 6.25 pieces of meat, which isn't feasible.

When I get a decimal answer for a problem that requires integer solutions, what should I do? Rounding down doesn't seem to work all the time, since the leftover resources might become large enough for me to employ a different resource instead. Am I supposed to round down and evaluate other possibilities like that? (I've tried finding examples of this online, but all the tutorials have integer solutions for their "nice" examples.)

Is This A Good Question/Topic? 0
  • +

Replies To: Integer Solutions to Simplex Algorithm

#2 Fuzzyness  Icon User is offline

  • Comp Sci Student
  • member icon

Reputation: 669
  • View blog
  • Posts: 2,438
  • Joined: 06-March 09

Re: Integer Solutions to Simplex Algorithm

Posted 20 August 2011 - 02:17 PM

If you only use integers throughout the entire thing that should work smoother. Also try casting it if you don't wan't to use just integers. Post up some code buddy and i'm sure we could be of more help.
Was This Post Helpful? 0
  • +
  • -

#3 Booley  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 20-January 11

Re: Integer Solutions to Simplex Algorithm

Posted 20 August 2011 - 04:25 PM

Oh, actually, I'm just trying to work the algorithm out on problems by hand to see if I understand it, so I don't have any code. I'm not asking for any, either; I plan to write some as soon as I get this algorithm down. My issue is that when dealing with standard optimization problems in linear programming using the simplex method I'm just not sure what to do with non-integer answers when the problem requires integers (like having 1 human as compared to 1.5 humans). For instance, here is a problem I found online:

Given:
100x + 125y + 50z <= 500
50y + 100z <= 400
and x, y, z are non-negative integers.
Maximize 10x + 20y + 15z.

After running through the simplex algorithm, the answer I obtained was 97.5 for the max, y = 3, and z = 2.5. However, the real answer is 95; I think that's because x, y, and z are integers, whereas my z is a decimal. If I round my solution to (0, 3, 2) my new maximum is 90, so apparently I have to do something other than rounding. (I know 97.5 is correct for the decimal answer because I checked using a simplex calculator here). Even if on the off chance that 95 was actually the wrong answer for this particular problem, what should I do with my decimal quantities/maximums if the next problem I see only asks for integers?

This post has been edited by Booley: 20 August 2011 - 04:27 PM

Was This Post Helpful? 0
  • +
  • -

#4 Booley  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 20-January 11

Re: Integer Solutions to Simplex Algorithm

Posted 22 August 2011 - 10:10 AM

After some more research, I discovered that this was an integer programming problem, so the simplex algorithm by itself cannot solve it; something more general like a backtracking algorithm must be used instead, apparently. For anybody who stumbles across this thread in the future, here are some materials that could shed some light on these kinds of problems.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1