Linear Programming

Linear Programming, using a tool such as CPlex or Gurobi, solves a system of inequalities while maximizing or minimizing an objective function. Sounds complicated but the average high school student solves simple systems of inequalities in high school.

You have $5. An apple costs $0.50 and a pear costs $1. Your grocery bag can only hold five pieces of fruit. Minimize the amount of money you spend. Assume then that A is the number of apples and P is the number of pears, then A + P <= 5 and .5A + 1B <=5 and Minimize (A+B).

Each variable is called a variable (surprise). Each inequality is called a constraint. And the function being minimized or maximized is called the objective function.

But in Linear Programming, we don’t solve the program. The tool, utilizing the simplex algorithm, solves the system. The engine simply needs to define the variables, constants, constraints, and objective functions and passes it to the solver. The solver solves it immediately. The engine then pulls the values out of the solution to find the number of apples and pears to buy.