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$

2 Answers 2

Reset to default
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$
1
  • $\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$ Commented Sep 22, 2016 at 14:21

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.