Objectives
-
Definition of a Linear Optimization Problem and related problems.
-
Definition of the Standard Form of an LOP
-
How to put a minimum problem into standard form
-
General Form of an LOP
Section 2.2 Linear Optimization Problems
In the previous two sections of this chapter we have seen applied problems as well as feasible sets. In this section, we will summarize all of these and determine a method to put applied problems into a mathematical formulation.
Subsection 2.2.1 Definitions and Conventions
Definition 2.2.1.
A Linear Optimization Problem consists of
1
This is not the most general form of such a problem. We will see a general linear optimization problem in Chapter 7.
-
A linear objective function that is to be minimized or maximized.
-
A set of linear inequalities.
-
A set of nonnegative constraints on all of the variables.
In short, we will call such problems LOPs and if the variables are constrained to be integers, then such problems are Integer Linear Optimization Problems or ILOPs and if the variables are constrained to be binary, then the problems are Binary Linear Optimization Problems or BLOPs .
Let’s take a look at an purely mathematical example of an LOP.
Problem 2.2.2.
\begin{equation*}
\begin{aligned} \text{Maximize} \amp \amp z = x_1 + 3x_2, \amp \\ \text{subject to} \amp \amp 4x_1 + 3x_2 \amp \leq 120, \\ \amp \amp x_1 + 2x_2 \amp \leq 40, \\ \amp \amp x_2 \amp \leq 16, \\ \text{and} \amp \amp x_1, x_2 \amp \geq 0.
\end{aligned}
\end{equation*}
A few conventions that we will use in this book:
-
This is a maximum problem, so we will use the variable \(z\) for the objective and \(x_i\) for each of the variables.
-
If instead we have a minimum problem, then we will use \(w\) for the objective and \(y_i\) for the variables. We will see another problem like this later.
-
The variables (either \(x_i\) or \(y_i\)) need to have the non-negative constraint that is the last line of the LOP in Problem 2.2.2.
Note 2.2.3.
Many LOPs naturally have the nonnegative constraint, because they arise from realistic problems in which variables cannot be negative. however, more abstract problems or mathematical problems may not have such constraints. We will learn in Chapter 7 how to either take such problems and both add nonnegative constraints and then solve them without such constraints.
An example of a minimum problem is the following.
Problem 2.2.4.
\begin{equation*}
\begin{aligned} \text{Minimize} \amp \amp w = 4y_1 + 3y_2, \amp \\ \text{subject to} \amp \amp y_1 + y_2 \amp \geq 40, \\ \amp \amp 3y_1 + 2y_2 \amp \geq 95, \\ \amp \amp y_1 + 4 y_2 \amp \geq 55, \\ \text{and} \amp \amp y_1, y_2 \amp \geq 0.
\end{aligned}
\end{equation*}
As you can see, we have use the variable \(w\) for the objective function and \(y_i\) for the variable. Another difference with Problem 2.2.2 is that the first three constraints are of the form \(\geq\text{.}\) Although this is not necessary, it is common. We will graph this feasible set in the next section and the characteristics of this set often are paired with a minimum problem.
Subsection 2.2.2 Standard Form
The LOP that we have been working on the past two section is in a special form that is needed for solving these problems using a technique we will develop in Chapter 3. We define it below and then explain how to get other problems into this form.
Definition 2.2.5.
A Linear Optimization Problem is in standard form if the following are conditions are met:
-
It is a maximum problem.
-
All the constraints are of the form \(\leq b\text{,}\) some constant.
-
All variables are nonnegative.
Not all LOPs are in standard form. Clearly Problem 2.2.4 and many in Section 2.1 as well. However, there is a systematic way to put such problems in standard form.
-
If the problem is a minimize problem in the form \(w = c_1 y_1 + c_2 y_2 + \cdots c_n y_n\text{,}\) define \(z=-(c_1 y_1 + c_2 y_2 + \cdots + c_n y_n)\text{.}\)
-
Any inequality in the form \(a_1 x_1 + a_2 x_2 + \cdots + a_n x_n \geq b_n \) should be multiplied by \(-1\) to get\begin{equation*} -a_1 x_1 - a_2 x_2 - \cdots a_n x_n \leq -b_n \end{equation*}
-
There are techniques to handle cases when the nonnegative constraint is not satisfied. We will see how to handle these cases in Chapter 7.
The following example shows how to put an LOP that is not in Standard Form into one that is.
Example 2.2.6.
Put Problem 2.2.4 in standard form.
Solution.
First, if the objective is a minimum problem, then we can make it a maximum problem by writing \(z=-w\text{.}\) In this case, \(z=-3y_1-2y_2\text{.}\)
Next, to get the inequalities in the proper form, multiply by \(-1\) and recall that changes a \(\geq\) to a \(\leq\text{.}\) In this problems
\begin{align*}
-y_1 - y_2 \amp \leq -40,\\
-3y_1-2y_2 \amp \leq -95,\\
-y_1-4y_2 \amp \leq -55.
\end{align*}
Therefore the problem in Standard Form is
\begin{equation*}
\begin{aligned} \text{Maximize}\amp \amp z = -3 y_1 - 2y_2,\amp \\ \text{subject to}\amp\amp -y_1 - y_2 \amp \leq -40, \\ \amp \amp-3y_1-2y_2 \amp \leq -95, \\ \amp \amp -y_1-4y_2 \amp \leq -55,\\ \text{and}\amp\amp y_1, y_2 \amp \geq 0.
\end{aligned}
\end{equation*}
Subsection 2.2.3 General and Matrix Forms of an LOP
In this section, we write the General Form of an Linear Optimization problem. Assume that there are \(n\) variables. If we have a maximum problem, we will use the variables \(x_i\) and a general constraint can be written
\begin{equation*}
\sum_{j=1}^n a_{i,j} x_j \leq b_i,
\end{equation*}
\begin{equation*}
\begin{aligned} \text{Maximize} \amp \amp z = \sum_{j=1}^n c_j x_j \amp \\ \text{subject to} \amp \amp \sum_{j=1}^n a_{i,j} x_j \leq b_i \amp \qquad \text{where $i=1,2,\ldots,n$}, \\ \text{and} \amp \amp x_j \geq 0, \amp \qquad\text{where $j=1,2, \ldots,n$}. \end{aligned}
\end{equation*}
These problems can be written in Matrix Form in the following way:
\begin{equation*}
\begin{aligned}
\text{Maximize} \amp \amp z = \boldsymbol{c}^{\intercal}\boldsymbol{x}, \amp \\
\text{subject to} \amp \amp A \boldsymbol{x} \leq \boldsymbol{b}, \\
\text{and} \amp \amp \boldsymbol{x} \geq \boldsymbol{0}.
\end{aligned}
\end{equation*}
where the inequalities must hold for each element of the vector.
