Subject: Re: Linear Programming
Date: Thu, 27 Mar 1997 19:18:43 -0500
From: Alexander Bogomolny
You see James, the problem is I can't give you more than the book you are studying from. I wonder what is wrong with it. Have you ever opened it?
Another problem is that there are several ways to write the tableau. I can't know which one you actually need. What you wrote does not make a lot of sense in any event. I will make a certain assumption. If it's wrong - you'll have to make the effort of looking into a book.
And perhaps for once try also understand what you are trying to accomlish.
Do one thing at a time:
- Introduce slack variables:
s1 = 4 - x1 + x2 s2 = 4 + x1 - x2 s3 = 6 - x1 - x2 Obviously, s1,s2,s3>_ 0
Note, and this is important that x1=x2=0 gives you a feasible vector (x1,x2,s1,s2,s3)=(0,0,4,4,6). It would be extremely useful for you to draw the three lines (from the three inequalities) and figure out what your region actually looks like.
- Now, chances are that on this vector your function
is not yet maximized. You may want to increase x1
because its coefficient in Z is positive. From the
equation for s1 you may only increase x1 to 4 for
afterwards s1 will become negative. Rewrite the
first equation as
x1 = 4 + x2 - s1
Here you can start with x2=s1=0. To see what you get eliminate x1 from the other two equations:x1 = 4 + x2 - s1 s2 = 8 - s1 s3 = 2 - 2x2 + s1 Z = 2(4 + x2 - s1) - 6x2 = 8 - 4x2 - 2s1
- Now in Z all the coefficients are negative. Therefore, you can't to any better. With x2 = s1 = 0, x1 = 4. (s2 = 8, s3 = 2). And this solves the problem.
- What you have to understand is that regardless of how you write your tableau, all you do is solving a system of linear equations. Secondly, the tableau below reminds me of the two-step simplex methd. On the first step you find a feasible vector if such one exists. If that's the case, the variables on the left should not have been s1,s2,s3 but something else, say, z1,z2,z3. Your notations do not tell me anything.
- Look into the chapter for Gaussian elimination. The basic step of the simplex method is exactly the same.