Subsection 3.1.2 The Dictionary for an LOP
Now that slack variables have been added to each inequality in an LOP, we look at the set of equations produced and see if we can develop a way to find the optimum solution to the LOP.
Returning to
(3.1.1), solve for
\(x_3, x_4\) and
\(x_5\text{,}\) we can write the LOP as
\begin{equation}
\begin{aligned} \text{Maximize}\amp \amp z \amp = x_1 + 3x_2, \\ \text{such that}\amp \amp x_3 \amp = 120 - 4 x_1 -3x_2, \\ \amp \amp x_4 \amp = 40 - x_1 - 2x_2, \\ \amp \amp x_5 \amp = 16 - x_2, \\ \text{and}\amp\amp \amp x_1, x_2, x_3, x_4, x_5 \geq 0.
\end{aligned}\tag{3.1.2}
\end{equation}
This is called the
dictionary form of the LOP. Note that the variables on the right of the equals signs are only
\(x_1\) and
\(x_2\text{.}\) These are called the
nonbasic variables or
parameters of the problem. If we have values for these variables, then we can determine the values of the other variables,
\(z, x_3, x_4, x_5\text{.}\) The three
\(x\) variables are called the
basic variables and the set of these are called the
basis of the problem. When a problem is originally written in dictionary form, the basic variables are the slack variables and the parameters are the original variables.
We will develop a solution algorithm which moves variables from the basis to the parameters. The
basic and
nonbasic variables are often distinguished from one another using the variables
\(\beta\) and
\(\pi\) respectively. For example, in the dictionary above,
\(\beta=\{3,4,5\}\) and
\(\pi=\{1,2\}\text{.}\)
Note also, that when
\(x_1, x_2, x_3, x_4\) and
\(x_5\) are 0, these are the 5 lines that define the feasible set as seen in
Figure 3.1.2. Note that the original variables are zero on the coordinate axes. You can also notice that the vertices of the feasible set occur where two of the variables are zero. There are 5 of these. Also, other intersection points occur between lines where the variables are 0, like
\((24,8)\text{.}\) Four of these sets of points are not within the feasible set, such as such as
\((40,0)\) and
\((56/3,16)\text{.}\)
Recall that from the previous chapter, that the optimal point occurs on one of the vertices of the feasible set. We will see here in this chapter how to walk from vertex to vertex without leaving the feasible set and also stopping when reaching the maximum of the objective.
Subsection 3.1.3 Basic Solutions
A
solution to either the dictionary or the tableau is any set of values for
\(\boldsymbol{x}\) that satisfy the problem constraints written as equalities. For example,
\begin{equation}
\boldsymbol{x}=\left[\begin{array}{rr|rrr}10 \amp 5 \amp 65 \amp 20 \amp 11\end{array}\right]^{\intercal}\tag{3.1.3}
\end{equation}
is a solution to the LOP above. This is because if we substitute these values of
\(\boldsymbol{x}\text{,}\) then each equation of the dictionary is satisfied. The vertical line in
(3.1.3) between the variables
\(x_2\) and
\(x_3\) is used to separate out the original variables from the slack variables and is helpful for readability.
To see that
(3.1.3) is a solution, substitute the values of
\(x_1\) and
\(x_2\) into the dictionary.
\begin{align*}
x_3 \amp = 120 - 4(10) - 3(5) = 65 \\
x_4 \amp = 40 - (10) - 2(5) = 20\\
x_5 \amp = 16 - (5) = 11
\end{align*}
Also, we can find the value of
\(z\) that corresponds to is solution is
\(z=x_1+3x_2 = 10 + 3(5) = 25\text{.}\)
A solution is
basic if the parameters are all zero. In the LOP problem above, the solution
\begin{equation}
\boldsymbol{x}=\left[\begin{array}{rr|rrr}0 \amp 0 \amp 120 \amp 40 \amp 16\end{array}\right]^{\intercal}\tag{3.1.4}
\end{equation}
is basic with value
\(z=0\text{.}\) If we have a problem in dictionary form, we will set the parameters to 0 and the basic variables will be constants on right side of the equations.
In the example where
\(x_1 =0\) and
\(x_2=0\) is a basic solution with the basis
\(\beta = \{3, 4, 5\}\text{.}\) Recall that we mention above that when two variables (in this case, not in general) are zero, then we are at a vertex of the feasible set. This vertex is at the origin.
Another basic solution is
\begin{equation}
\boldsymbol{x}=\left[\begin{array}{rr|rrr} 0 \amp 16 \amp 72 \amp 8 \amp 0\end{array}\right]^{\intercal},\tag{3.1.5}
\end{equation}
and is basic because the two variables
\(x_1\) and
\(x_5\) are 0. Thus for this case,
\(\beta=\{2,3,4\}\) and
\(\pi=\{1,5\}.\)
A dictionary or tableau is
feasible if its corresponding basic solution is feasible. The solutions
(3.1.3),
(3.1.4) and
(3.1.5) are feasible solutions because all of the variables are non-negative. (Note: you would need to check that they are solutions.). The solution
\begin{equation}
\boldsymbol{x}=\left[\begin{array}{rr|rrr} 18 \amp 16 \amp 0 \amp -10 \amp 0 \end{array}\right]^{\intercal}\tag{3.1.6}
\end{equation}
is not because
\(x_4=-10\) does not satisfy the nonnegative constraint.
Checkpoint 3.1.4.
Hint.
For each of the solutions, the numbers to the left of the vertical line are the original variables and those are the variables to plot on the feasible set.
Solution.
Replotting the feasible set with the solutions:
We are now going to develop the
Simplex Method to solve the LOP using the dictionary. This technique will be systematically going from vertex to vertex of the feasible set until the optimal solution is reached.
Lastly, the dictionary is
optimal if its basic solution is optimal. The simplex method will stop when we reach an optimal solution.
Subsection 3.1.4 Developing the Simplex Method
Returning to the dictionary in
(3.1.2), consider the objective function
\begin{equation*}
z = x_1 + 3x_2
\end{equation*}
and notice that if either
\(x_1\) or
\(x_2\) increases in value then
\(z\) increases. Since we are seeking a maximum of
\(z\text{,}\) we want to increase either
\(x_1\text{,}\) \(x_2\) or both. We must be careful however, because as
\(x_1\) and
\(x_2\) increases,
\(x_3, x_4\) and
\(x_5\) decrease and we need to ensure that they must stay nonnegative. Before increasing these variables, recall that the basis is
\(\beta=\{3,4,5\}\) indicating that these three variables are in the basis (which are on the left side of all of the equations in a dictionary).
We can select one of the parameters,
\(\pi=\{1,2\}\text{,}\) to increase its value. As we will typically do, we will increase the first one and keep the others as 0, so the variable
\(x_1\) will be increased, so will set
\(x_2=0\) in the constraints of
(3.1.2):
\begin{align*}
x_3\amp= 120-4x_1 \\
x_4\amp= 40 -x_1, \\
x_5\amp= 16.
\end{align*}
If we increase
\(x_1\text{,}\) and keep
\(x_3\) and
\(x_4\) nonnegative, we require that
\begin{align*}
120 -4x_1\amp\geq 0,\amp40-x_1\amp\geq 0.
\end{align*}
The largest value of
\(x_1\) that ensure both of these stay true is
\(x_1=30\text{.}\) If we let
\(x_1=30\) in
(3.1.2), notice that when
\(x_2=0,\) the variable
\(x_3\) becomes zero, therefore it appears that we have interchanged
\(x_1\) and
\(x_3\) between basic and nonbasic variables. Thus the new basis is
\(\beta=\{1,4,5\}\) and the parameters is
\(\pi = \{2,3\}\text{.}\) This switch of variables is called a
pivot and is denoted
\(1 \mapsto 3\text{,}\) where the first number 1 is the variable entering the basis and the second number is the one leaving.
If we want
\(x_3\) to be in the basis and
\(x_1\) to leave we use the 2nd equation (first equation coming from a constraint) in the dictionary in
(3.1.2) and solve for
\(x_1\) or
\begin{equation*}
x_1= 30 -\frac{1}{4}x_3 - \frac{3}{4}x_2.
\end{equation*}
To get
\(x_3\) a basic variable for the rest of the dictionary, we plug this in the other equations in
(3.1.2), resulting in the new dictionary:
\begin{align*}
z\amp= \left(30 -\frac{1}{4}x_3 - \frac{3}{4}x_2\right) + 3 x_2 = 30+\frac{9}{4}x_2 - \frac{1}{4}x_3 \\
x_1\amp = 30 - \frac{3}{4}x_2 - \frac{1}{4}x_3 \\
x_4\amp= 40 - \left(30 -\frac{1}{4}x_3 - \frac{3}{4}x_2\right) - 2x_2 = 10-\frac{5}{4}x_2 +\frac{1}{4}x_3\\
x_5\amp= 16-x_2
\end{align*}
and for simplicity, if we multiply each row each by 4 to get:
\begin{equation}
\begin{aligned} 4z\amp= 120 +9x_2-x_3 \\ 4x_1\amp=120 -3x_2-x_3 \\ 4x_4\amp= 40 -5x_2+x_3 \\ 4x_5\amp= 64-4x_2.
\end{aligned}\tag{3.1.7}
\end{equation}
(Note: there was no reason to multiply the last row by 4 since there are no fractions in the equation, but you will see later why we want to do this.)
Also, we have a new basic solution for the dictionary in
(3.1.7) as
\begin{equation*}
\boldsymbol{x}^{(1)}= \frac{1}{4}\left[\begin{array}{rr|rrr} 120 \amp 0 \amp 0 \amp 40 \amp 64 \end{array}\right]^{\intercal} =
\left[\begin{array}{rr|rrr} 30 \amp 0 \amp 0 \amp 10 \amp 16\end{array}\right]^{\intercal}.
\end{equation*}
where the superscript
\((1)\) denotes the first step of the simplex method. Also, this dictionary corresponds to the basis of
\(\beta=\{1,4,5\}\) and parameters
\(\pi=\{2,3\}\text{.}\) The notation
\(1 \mapsto 3\) shows that 1 has left the
\(\pi\) parameter set to become a basic variable replacing 3.
The objective in the first row of
(3.1.7) is
\(z = 120/4=30\text{,}\) when setting the parameters to 0. Thus, the objective has increased from the initial dictionary, but also that if we increase
\(x_2\text{,}\) then
\(z\) will increase. Because of this, we also know that the current solution is not optimal. We can increase
\(x_2\) (and set
\(x_3=0\)) so long that it satisfies:
\begin{align*}
120-3x_2\amp\geq 0,\amp 40-5x_2\amp\geq 0,\amp64-4x_2\amp\geq 0.
\end{align*}
\begin{equation*}
x_2= \min(120/3, 40/5,64/4) = 8
\end{equation*}
Because the 8 came from the the 3rd equation of
(3.1.7), we are going to solve for
\(x_2\) (or actually
\(5x_2\)) in this equation or
\begin{equation}
5 x_2 = 40 + x_3 - 4x_4\tag{3.1.8}
\end{equation}
We now take the other three equations in
(3.1.7) and multiply by 5 because of the coefficient of the variable
\(x_2\) above to get:
\begin{align*}
20 z \amp = 600 + 9 (5x_2) - 5 x_3 \\
20 x_1 \amp = 600 - 3 (5x_2) - 5 x_3\\
5x_2 \amp =40 + x_3 - 4x_4 \\
20 x_5 \amp =320 - 4 (5 x_2)
\end{align*}
and then in each of the terms in the parentheses substitute
(3.1.8), to get
\begin{align*}
20 z \amp = 600 + 9 (40 + x_3-4x_4) - 5 x_3 = 960 + 4x_3 - 36 x_4 \\
20 x_1 \amp = 600 - 3 (40 + x_3-4x_4) - 5 x_3 = 480 - 8x_3 + 12 x_4\\
5x_2 \amp =40 + x_3 - 4x_4 \\
20 x_5 \amp =320 - 4 (40 + x_3-4x_4) = 160 - 4x_3 + 16 x_4
\end{align*}
If we note that each of the first, second and fourth equations above are factors of 4 (the previous coefficient of all parameters), if we divide these three equations by 4 to get:
\begin{equation}
\begin{aligned} 5 z \amp = 240 + x_3 - 9 x_4 \\ 5 x_1 \amp = 120 - 2x_3 + 3 x_4 \\ 5x_2 \amp =40 + x_3 - 4x_4 \\ 5 x_5 \amp = 40 - x_3 + 4 x_4 \end{aligned}\tag{3.1.9}
\end{equation}
which is the current dictionary. Note that
\(x_4\) is now a parameter and
\(x_2\) is now a basic variable. This means that we have done the pivot:
\(2\mapsto 4\) and the parameter set is
\(\beta = \{3,4\}\) and basis is
\(\beta = \{1,2,5\}\text{.}\) The basic solution of this dictionary is
\begin{equation*}
\boldsymbol{x}= \frac{1}{5}\left[\begin{array}{rr|rrr} 120 \amp 4 \amp 0 \amp 0 \amp 40\end{array}\right]^{\intercal}
\end{equation*}
with objective function value
\(z=240/5=48\text{.}\)
If we look at the dictionary, the top row is
\(5z=240+x_3-9x_4\text{.}\) If we increase the variable
\(x_3\text{,}\) then the objective function will be increased. We will increase
\(x_3\text{,}\) but in order to ensure that we remain in the feasible set, we required that
\begin{align*}
120-2x_3\amp\geq 0,\amp40+x_3\amp\geq 0,\amp40-x_3\amp\geq 0.
\end{align*}
We wish to increase
\(x_3\) by the maximum amount with these constraints and this occurs when
\begin{equation*}
x_3 = \min(120/2,40/1) = 40
\end{equation*}
where the second inequality has been ignored because it is automatically satisfied for any positive value of
\(x_3\text{.}\) Since the minimum value is associated with the 4th equation, we will solve for
\(x_3\) in this equation or
\begin{equation*}
x_3 = 40 + 4x_4 - 5 x_5
\end{equation*}
We then substitute this into the other equations or
\begin{align*}
5 z \amp = 240 + (40+4x_4-5x_5) - 9 x_4 = 280 - 5x_4 - 5 x_5,\\
5 x_1 \amp = 120 - 2(40+4x_4-5x_5) + 3 x_4 = 40 - 5x_4 + 10 x_5,\\
5x_2 \amp =40 + (40+4x_4-5x_5) - 4x_4 = 80 - 5x_5, \\
x_3 \amp = 40+4x_4-5x_5.
\end{align*}
The first three equations are all multiples of 5, the previous constant, so we can divide each equation by 5 to get
\begin{equation}
\begin{aligned} z \amp = 56 - x_4 - x_5 \\ x_1 \amp = 8 - x_4 + 2 x_5 \\ x_2 \amp = 16 - x_5 \\ x_3 \amp = 40+4x_4-5x_5 \end{aligned}\tag{3.1.10}
\end{equation}
The basic solution of this tableau is
\begin{equation*}
\boldsymbol{x} = \left[\begin{array}{rr|rrr} 8 \amp 16 \amp 40 \amp 0 \amp 0 \end{array} \right]^{\intercal}
\end{equation*}
with the objective function taking on the value
\(z=56\text{.}\) This solution has basis variables
\(\beta=\{1,2,3\}\) and parameters
\(\pi=\{4,5\}.\) Lastly, looking at the objective equation, increasing our either of the parameters
\(x_4\) or
\(x_5\) decreases the objective value, so this means that this solution is
optimal.
These set of steps form part of the
simplex method for solving LOPs. In the next section, we repeat this example with a matrix form of the dictionary, called a tableau. This will make all of the calculations easier to do and with some software can simplify the steps tremendously.
