# Find the maximum of a linear function, given other linear equations with infinite solutions

$a_{1,1}x_1 + a_{1,2}x_2 + \dots + a_{1,20}x_{20}\leq b _1$

$a_{2,1}x_1 + a_{2,2}x_2 + \dots + a_{2,20}x_{20} \leq b_2$

$x_1 \geq 0, x_2 \geq 0, \dots, x_{20} \geq 0$

$f(x) = a_{3,1}x_1 + a_{3,2}x_2+ \dots + a_{3,20}x_{20}$

All $a$'s and $b$'s are known. There are infinite solutions. I want to find values for $x$'s that solve the linear equations that maximizes $f(x)$. Not sure how to go about this. Not sure if my title is a very good way to summarize the question.

-
Gigili, I was just working on cleaning up the latex myself, but you were faster. Thx! –  Ian Kelling Jul 6 '12 at 7:39

## 2 Answers

This is called Linear Programming problem, one famous method is Simplex Algorithm. For reference see here : http://en.wikipedia.org/wiki/Linear_programming

-
Perhaps add a link to the simplex method as well. It walks you right through a problem. –  crf Jul 6 '12 at 9:08

Linear Programming problems can be solved using various algorithms like Simplex Algorithm, interior point methods etc. but most popular method for simple linear programming problems is Simplex method. Here is a link that describes the method with example: http://www.phpsimplex.com/en/simplex_method_example.htm

-