0
$\begingroup$

I want to solve a minimizing linear programming problem with simplex method.

$$min \quad 2x_1+3x_2+x_3 \\ \text{subject to: }x_1+4x_2 \le 3 \\ x_2+4x_3 \le 2 \\ x_1+2x_2+3x_3=5 \\ x_2+x_3=1 $$

In order to solve this problem with simplex method it needs to be converted to standard form: $$ max \; -2x_1-3x_2-x_3 \\ x_1+4x_2+u=3 \\ x_2+4x_3+v=2 \\ x_1+2x_2+3x_3=5 \\ x_2+x_3=1 \\ x_1, x_2, x_3, u, v \ge 0 $$

For simplex tableau, the objective function should be an equation: $$ P=-2x_1-3x_2-x_3 \Rightarrow P+2x_1+3x_2+x_3=0 $$

The set of basic variables is composed of slack variables $u,v$. Therefore, non-basic variables $x_1, x_2, x_3$ are initialized to $0$. This violates the equality constraints of the original problem and at the same time the objective equation states that the first basic solution is the optimal solution since all coefficients of the objective equation are non-negative. This means the optimal solution is infeasible!

Does it mean simplex method cannot be used to solve this problem or I am missing some important aspects?

$\endgroup$
1
$\begingroup$

There is such aspect. Consider system of equations $$ \begin{cases} (1):x_1+4x_2 \le 3 \\ (2):x_2+4x_3 \le 2 \\ (3):x_1+2x_2+3x_3=5 \\ (4):x_2+x_3=1 \end{cases} $$ Make some substitutions: $$ \begin{align} (4)\to (2)&: x_3\le\frac{1}{3}\\ (4)\to (3)&: x_1=3-x_3 \quad(5)\\ (4)&: x_2=1-x_3 \quad(6)\\ (5),(6)\to(1)&: x_3\ge\frac{4}{5} \end{align} $$

Notice that $x_3\le\frac{1}{3}$ and $x_3\ge\frac{4}{5}$ contradict each other, hence system is incompatible.

$\endgroup$
0
$\begingroup$

An artificial, rather than slack, variable in each equality constraint should do it. These will be removed in Phase 1 to leave a BFS to begin Phase 2.

Much easier is to use each equality constraint to remove one of the original variables - with two such constraints and three variables, the problem then reduces to the trivial case of one variable.

$\endgroup$
  • $\begingroup$ Can we say the process of removing original variables by each equality is like pivoting operation? I want to see if I can apply that algorithm for the elimination operation. $\endgroup$ – Masoud Sep 22 '16 at 14:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.