# How to solve this equality-constrained linear program?

Solve the linear programming

Objective function: $x_1+x_2+x_3 \rightarrow \text{max}$

$\left\{\begin{matrix} x_1+3x_2+x_3=3\\ x_1-2x_2-2x_3=4\\ x_1 \geq 0, x_2 \geq 0, x_3 \geq 0 \end{matrix}\right.$

I have always used simplex algorithm for solving linear programming tasks but this one is only made up of equations so there is no need for slack variables. I wonder how you could solve such tasks?

As noted by Rodrigo de Azevedo, the problem is infeasible. If you subtract the second constraint from the first, you get $5x_2 + 3x_3 = -1$, which is clearly inconsistent with the nonnegativity requirement for the variables.

As to the general approach to solving it, there are at least two well-known (or should I say "well worn") choices, two-phase simplex or dual simplex.

With the two-phase simplex method, you insert nonnegative "artificial variables" $s_1$ and $s_2$ (essentially equivalent to slack variables) into the constraints. So the first constraint becomes $x_1 + 3x_2 + x_3 + s_1 = 3$ and similarly with the second constraint. In phase 1, the starting basis consists of the artificial variables (or the slack and artificial variables, if you also have inequality constraints), and you minimize the sum of the artificial variables. At the end of phase 1, if all the artificials are zero, you have a feasible basis for the original problem consisting of a subset of the original variables. You remove the artificials and solve the problem starting from that basis. If the minimum value of the phase 1 objective is strictly positive, the problem is infeasible.

With the dual simplex method, you start with a basic solution to the original problem that is "superoptimal" (objective value at least as good as an optimal solution but probably better than optimal) but infeasible. The corresponding dual solution with be feasible in the dual but suboptimal. You then apply dual simplex pivots (equivalent to regular pivots if you were solving the dual problem) until a feasible solution is found. I'm too lazy to go into greater detail, but both dual simplex and the two-phase method should be explained in most introductory in texts on LP.

Essentially, we intersect two planes, so the valid points are on a line. Use the two equations to express $x_2$ and $x_3$ in terms of $x_1$, for example. Use this to express the objective function in terms of $x_1$ only. $x_2 \ge 0$ and $x_3 \ge 0$ also become inequalities for $x_1$. You will end up with a linear function for $x_1$ as objective function and a closed interval of valid $x_1$. One of the end points of that interval will be optimal.

>>> from sympy import *
>>> M = Matrix([[ 1, 3, 1, 3],
[ 1,-2,-2, 4]])
>>> M.rref()
(Matrix([
[1, 0, -4/5, 18/5],
[0, 1,  3/5, -1/5]]), [0, 1])


Hence, the intersection of the two planes is the line parameterized as follows

$$\begin{bmatrix} x_1\\ x_2\\ x_3\end{bmatrix} = \begin{bmatrix} \frac{18}{5}\\ -\frac{1}{5}\\ 0\end{bmatrix} + t \begin{bmatrix} \frac{4}{5}\\ -\frac{3}{5}\\ 1\end{bmatrix}$$

Imposing nonnegativity constraints, $x_1, x_2, x_3 \geq 0$, we obtain

$$\begin{array}{rl} t &\geq -\frac 92\\ t &\leq -\frac 13 \\ t &\geq 0\end{array}$$

which is clearly infeasible. The line does not intersect the nonnegative octant. Thus, the given linear program is infeasible. There is no maximum.