The basics of linear programming

LP algorithms are used in all areas where optimization, and therefore the economy of resources, is critical to the continuation of activities. To understand what this is all about, you need some basic math concepts. Let’s brush up on some of the geometric concepts we learned in college.

Linear equations and inequalities

We have all encountered the term linear equation at least once in our lives. A linear equation, in its simplest sense, is a mathematical relationship between two variables, x and y, of the form ax + by + c = 0, which identifies a straight line on the Cartesian plane:

Figure 14.1: Representation of the linear equation 2x + y = 2

Here, a and b are the coefficients that control the slope and direction of the line on the graph, determining how steep it is and whether it slopes up or down. c is the coefficient that adjusts the position of the line, determining where it crosses the vertical axis. Together, these...