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.)
Integer Solutions to Simplex Algorithm
Page 1 of 13 Replies  2184 Views  Last Post: 22 August 2011  10:10 AM
Replies To: Integer Solutions to Simplex Algorithm
#2
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.
#3
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 noninteger 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 nonnegative 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?
Given:
100x + 125y + 50z <= 500
50y + 100z <= 400
and x, y, z are nonnegative 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
#4
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.
Page 1 of 1
