Linear Programming Problem Using the Two-Phase Method

I have been given the following LP problem and asked to use the two phase simplex method to solve it.

I believe there isn't a solution, but would anyone be able to confirm this for me? Thanks.

max

$-x_1 + 2x_2 -3x_3 - x_4$

s.t.

$2x_1 - x_2 - 3x_3 + 4x_4 = -2$

$2x_1 + 3x_2 + 4x_3 - x_4 = 1$

$x_1,x_2,x_3,x_4 ≥ 0$

Thanks.

• Do you mean you think the objective function is not bounded from above given the conditions? If so you are correct. Just solve the conditions using row reduction, get in parametric form, and plug into your objective function. When I did this just now, I got the result $-57/8*s+1/8*t+17/8$ which by puttint $s=0$ is unbounded as $t \to \infty$, – coffeemath Oct 21 '12 at 0:33

The feasible set is empty.

A rather clumsy way of showing this is as follows:

Write the equality constraints as $A \pmatrix{x_1 \\ x_2} - B \pmatrix{x_3 \\ x_4} =\pmatrix{-2 \\ 1}$, where $A=\pmatrix{ 2 & -1 \\ 2 & 3}$, $B=\pmatrix{3 & -4 \\ -4 & 1}$. Since $A^{-1} = \frac{1}{8}\pmatrix{ 3 & 1 \\ -2 &2}$, we can write the equality constraints as $\pmatrix{x_1 \\ x_2} = A^{-1}(B \pmatrix{x_3 \\ x_4} + \pmatrix{-2 \\ 1}) =\frac{1}{8}(\pmatrix{ 5 & -11 \\ -14 & 10} \pmatrix{x_3 \\ x_4} +\pmatrix{-5 \\ 6} )$.

Consequently, the feasible set can be described by the constraints $$x_3 \geq 0 \\ x_4 \geq 0 \\ x_1 =5 x_3-11 x_4 -5 \geq 0 \\ x_2 = -14 x_3 + 10 x_4 +6 \geq 0$$ Consider the equation $14 x_1+5 x_2$ (which must be non-negative), this gives $-104 x_4 -40 \geq 0$, which is impossible.

Let me preface this by saying I only include it since a beginner knowing row reduction could apply the method.

The constraints are two equations in four unknowns. I set up the augmented matrix and row reduced it. The first two terms in rows 1 and 2 make up the 2x2 identity matrix, so we let $x_3 = s$ and $x_4$ = t and express all four variables in terms of $s$ and $t$.

$x_1 = -5/8+(5/8)s-(11/8)t$

$x_2=(3/4)-(7/4)s+(5/4)t$,

$x_3=s$,

$x_4=t.$

For a nonempty feasible region we need the first two variables to be nonnegative provided $s,t$ are nonnegative. But a graph (using $s,t$ axes) shows the inequalities on the first two variables give a pair of lines intersecting in the fourth quadrant, with the "shaded part" going off away from quadrant 1. So we have an empty feasible region, as already noted by copper.hat and D. Nehme.

I just read in a book, Linear Programming and Network Flows, which says that after phase one, if at optimality at least one of the artificial variables is nonzero, then the original problem has no feasible solution.

I hope you can do phase I table and clearly this....

• What do you mean by "clearly this"? – Travis Sep 23 '14 at 13:12