Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

3 Answers 3

up vote 2 down vote accepted

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.

share|improve this answer
    
Thanks for the insight. –  user42538 Oct 23 '12 at 19:37

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.

share|improve this answer
    
Thanks for the insight. –  user42538 Oct 23 '12 at 19:36

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....

share|improve this answer
    
What do you mean by "clearly this"? –  Travis Sep 23 at 13:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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