# A State of the Art Review of Systems of Linear Inequalities and Related Observability Problems
## 5 Linear Programming
### Illustrative Examples  
**Example 1** (**Problem 1)**. : _Consider the linear programming problem: Maximize \(Z_{1}=x_{1}+x_{2}+x_{3}\) subject to the constraints:_  
\[ \begin{array}{c}0\leq x_{1}\leq 2\\ 0\leq x_{2}\leq 2\\ 0\leq x_{3}\leq 2\\ x_{1}+x_{2}\leq 3\end{array}  \tag{66}\]  
_which is equivalent to the polytope_  
\[\left( \begin{array}{c}x_{1}\\ x_{2}\\ x_{3}\end{array} \right)=\left( \begin{array}{cccccccccccc}0&2&0&0&2&2&0&2&2&1 \\ 0&0&2&0&2&0&2&2&1&2\\ 0&0&0&2&0&2&2&1&2&2\\ \end{array} \right)_{\lambda}\]  
_Before dealing with the optimization problem it is worthwhile indicating that, using the gamma algorithm, we can obtain the dual of the cone associated with this polytope, that is, the cone generated by the columns of the matrix:_  
\[\left( \begin{array}{cccccccccccc}0&2&2&0&0&2&0&2&1&2\\ 0&0&2&2&0&0&2&1&2&2\\ 0&0&0&0&2&2&2&2&2&1\\ 1&1&1&1&1&1&1&1&1&1\end{array} \right),\]  
_and then, we obtain in the final table the set of facets in its lower part, as shown in Table 4._  
_In this case, the set of feasible values of the objective function is the polytope of real numbers:_  
\[Z_{1}=\left( \begin{array}{cccccccccccc}1&1&1\end{array} \right)\left( \begin{array} []{cccccccccccc}0&2&0&0&2&2&0&2&2&1\\ 0&0&2&0&2&0&2&2&1&2\\ 0&0&0&2&0&2&1&2&2\end{array} \right)=\left( \begin{array}{cccccccccccc}0&2&2&2 &4&4&5&5&5\end{array} \right)_{\lambda}\]  
_whose maximum corresponds to the maximum value \(5\), and then, the set of all possible solutions of Problem 1 is the polytope:_  
\begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline  & \(\boldsymbol{w_{1}}\) & \(\boldsymbol{w_{2}}\) & \(\boldsymbol{w_{3}}\) & \(\boldsymbol{w_{4}}\) & \(\boldsymbol{w_{5}}\) & \(\boldsymbol{w_{6}}\) & \(\boldsymbol{w_{7}}\) \\ \hline  & \(0\) & \(0\) & \(-1\) & \(1\) & \(0\) & \(0\) & \(1\) \\  & \(-1\) & \(0\) & \(0\) & \(0\) & \(0\) & \(1\) & \(1\) \\  & \(0\) & \(-1\) & \(0\) & \(0\) & \(1\) & \(0\)_Note that all solutions have been obtained._  
**Example 2** (**Problem 2)**. : _Consider the linear programming problem:_  
_Maximize \(Z_{2}=x_{1}+x_{2}\)_  
_In this case, the set of feasible values of the objective function is the polytope of real numbers:_  
\[Z_{2}=( \begin{array}{cccccccccccc}1&1&0\end{array} )\left( \begin{array}{ ccccccccc}0&2&0&0&2&2&0&2&2&1\\ 0&0&2&0&2&0&2&2&1&2\\ 0&0&0&2&0&2&2&1&2&2\end{array} \right)=( \begin{array}{cccccccccccc}0&2&2&0&4&2& 2&4&3&3\end{array} )_{\lambda} \tag{67}\]  
_whose maximum corresponds to the maximum value \(4\), and then, the set of all possible solutions of Problem 2 is the polytope:_  
_Note that all solutions have been obtained._  
**Example 3** (**Problem 3)**. : _Consider the linear programming problem:_  
_Maximize \(Z_{3}=x_{1}\)_  
_In this case, the set of feasible values of the objective function is the polytope of real numbers:_  
\[Z_{3}=( \begin{array}{cccccccccccc}1&0&0\end{array} )\left( \begin{array}{ ccccccccc}0&2&0&0&2&2&0&2&2&1\\ 0&0&2&0&2&0&2&2&1&2\\ 0&0&0&2&0&2&2&1&2&2\end{array} \right)=( \begin{array}{cccccccccccc}0&2&0&0&2& 2&0&2&2&1\end{array} )_{\lambda} \tag{68}\]  
_whose maximum corresponds to the maximum value \(2\), and then, the set of all possible solutions of Problem 3 is the polytope:_A particular case is the case of the objective function being one of the variables, in which case one can obtain very easily the upper and lower bounds of the variable. For example, consider the feasible region defined in (33). Then, one can premultiply the vector of the variables \(\mathbf{x}\) by the identity matrix to obtain:  
\[\left( \begin{array}{c}x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\end{array} \right)=\left( \begin{array}{cccc}1&0&0&0\\ 0&1&0&0\\ 0&0&1&0\\ 0&0&0&1\end{array} \right)\left( \begin{array}{c}x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\end{array} \right)=\left( \begin{array}{c}1\\ 0\\ 0\\ 0\end{array} \right)_{\rho}+\left( \begin{array}{ccc}-1&-1&0\\ 2&-1&1\\ 0&0&0\\ 0&1&1\end{array} \right)_{\pi}+\left( \begin{array}{cc}1&1\\ -1&1\\ 0&0\\ 0&0\end{array}