# Introduction to Linear Programming

A linear program (LP) is a problem that can be expressed as linear functions. As you probably already know, a linear function is the one whose graph is always a straight line. Thus each variable of it appears in a separate term with its coefficient. There must be no products or quotients of these variables. In addition, the exponent of each term must be one. No logarithmic, exponential, trigonometric terms are allowed. Especially note that functions like ABS, IF, MAX, and MIN are not linear. Here are a few examples of linear functions:

```    3x + y - 5z
-3.23x + 0.33y
-0.3x + 4y - 2z + 1.2m
```

The linear problem has a so called objective function which is to be minimized or maximized and constraints. The objective function is the one whose value we would like to optimize. Typically, this function could determine the profit generated by the expected sales of the given model (maximization problem), or, the cost of the production in the given environment (minimization problem). Anyway, on purely mathematical point of view, we could examine the following objective function:

```    Maximize 2x + 3y - z
```

In linear programming the variables of this functions are not allowed to take any values (otherwise the maximum of any objective function would be infinity). The problem also has constraints. The constraints are a set of linear functions and a set of their right hand side values (RHS). For example, for the previously defined objective function we have the following constraints:

```    x + y <= 5           (#1)
3x - y + z <= 9      (#2)
x + y >= 1           (#3)
x + y + z = 4        (#4)
x, y, z >= 0         (non-negativity assumption)
```

This constraint set consists of three inequality constraints (#1-#3) and one equality constraint (#4). Their RHS values are 5, 9, 1, and 4. In addition, we also have the non-negativity assumption. That is, all the variables (x, y, and z) have to take only positive numbers. The idea is to find the optimal values for the variables (x, y, and z) but also to satisfy all the given constraints.