You have two types of crops x and y, where crop x gives you 20 dollars per acre, and crop y gives you 30 dollars per acre. In addition, crop x takes two hours of time per acre to harvest, while crop y takes four hours per acre to harvest. You have 200 acres of land, and 70 working hours to spare. Which combination of crops gives you the highest profits?Sounds like a lot of combinations to try out, right? But luckily a trial-and-error approach isn't needed. With Linear Programming, this problem can be rewritten as a linear functions with restrictions as hyperplanes.
First of all, we need a function to maximize for. In our example above, it becomes:
Z = 20x+30y.
And the number of acres of land we have, together with the working hours become our constraints. For example, the number of acres we want to plant must be less than the number of acres we have for disposition:
x+y <= 200
The total time it takes to harvest the crops needs to be less than 70:
2x+4y <= 70
And we can't plant a negative area:
x >= 0
y >= 0
What happens is that if we plot this on a 2D graph, we get four lines/planes that define a convex polygon where they intersect. This is called the 'feasible region'. The optimal result is always one of the vertices, where the origin is a part of the vertex set. When you have the vertices, you can plug the x and y values into your profit function and find the biggest one. For this example, the maximum profits are found at the vertex x=35, y=0, and the result from our function becomes 20 * 35 + 30 * 0 = 700.
I said that these are kind of like planes, but how? Wait, doesn't the constraints look like scalar products? In fact, they do look like ax+by = d, or some prefer ax+by-d = 0. And finding the intersection between two lines, or three planes (3D) is fairly trivial. But what about higher dimensions than 3D, if you have a lot of unknowns? That's the problem I initially had. I suck at math, so unknown to me, you can generalize plane intersection tests in k dimensions with a system of linear equations. To algorithmically solve such a system you can use gauss elimination, which does a series of identity transformations on the matrix. The matrix simply consists of all the coefficients for the unknows, with the 'd' on as the last element in each row. I made a gaussian solver, which can now be found on GitHub as a part of a larger library I have in the works: http://github.com/Madsy/LGML
