A Gentle Introduction to Optimization

Possible outcomes

Consider an LP (P) with variables x1, …, xn. Recall that an assignment of values to each of x1, …, xn is a feasible solution if the constraints of (P) are satisfied. We can view a feasible solution to (P) as a vector x = (x1, …, xn)T. Given a vector x, by the value of x we mean the value of the objective function of (P) for x. Suppose (P) is a maximization problem. Then recall that we call a vector x an optimal solution if it is a feasible solution and no feasible solution has larger value. The value of the optimal solution is the optimal value. By definition, an LP has only one optimal value; however, it may have many optimal solutions. When solving an LP, we will be satisfied with finding any optimal solution. Suppose (P) is a minimization problem. Then a vector x is an optimal solution if it is a feasible solution and no feasible solution has smaller value.

If an LP (P) has a feasible solution, then it is said to be feasible, otherwise it is infeasible. Suppose (P) is a maximization problem and for every real number α there is a feasible solution to (P) which has value greater than α, then we say that (P) is unbounded. In other words, (P) is unbounded if we can find feasible solutions of arbitrarily high value. Suppose (P) is a minimization problem and for every real number α there is a feasible solution to (P) which has value smaller than α, then we say that (P) is unbounded.