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?
Best Answer
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.