Expert: Scott A Wilson - 9/5/2008

Question
QUESTION: Hi Scott, I need to "maximise a+b+c" subject to
7a-6b-5c is < or = 0 &
-9a +8b + 7c < or = 0
where a,b,c are all > or = 0

I tried multiplying one equation & then adding to another to remove one variable and so on, but find Im going round in circles. Any help on this would be appreciated.
Thanks

ANSWER: This is a linear programming problem with the top row as a+b+c.
It would be written as such with an articficial variable added to each equation.

You would have maximize a+b+c subject to 7a-6b-5c+d=0 and
-9a+8b+7c+e=0, where d and e are the artificial variables.  The first row should be multiplied by -1.

Now each of the variable should be replaced with two variables, like a=a1-a2, where a1 and a2 have the condition that they are both nonnegative.

The starting tableau (tablo, with a short and o long) would look like
-1  1 -1  1 -1  1
7 -7 -6  6 -5  5 1 0 0
-9  9  8 -8  7 -7 0 1 0.

After only two iterations, it comes down to a tableau that has a negative in the first row and all negatives below it, which means it can't be solved.

This is the original tableau:
-1.00   1.00   -1.00   1.00   -1.00   1.00   0.00   0.00   
7.00   -7.00   -6.00   6.00   -5.00   5.00   1.00   0.00   
-9.00   9.00   8.00   -8.00   7.00   -7.00   0.00   1.00   
         
Choose the first variable and the first constraint equation, then you have
0.00   0.00   -1.86   1.86   -1.71   1.71   0.14   0.00   0.00
1.00   -1.00   -0.86   0.86   -0.71   0.71   0.14   0.00   0.00
0.00   0.00   0.29   -0.29   0.57   -0.57   1.29   1.00   0.00.

Choose the variable with the -1.71 (since that is not so negative as -1.86), and you get
0.00   0.00   -1.00   1.00   0.00   0.00   4.00   3.00   0.00
1.00   -1.00   -0.50   0.50   0.00   0.00   1.75   1.25   0.00
0.00   0.00   0.50   -0.50   1.00   -1.00   2.25   1.75   0.00

Take the -1 as the only remaining negative and you get
0   0   0   0   2   -2   8.5   6.5   0
1   -1   0   0   1   -1   4   3   0
0   0   1   -1   2   -2   4.5   3.5   0
         
The next variable to choose would be the one with the -2 in the top row (the row of constraints), but it only has negatives below it, so that says there is no solution.


---------- FOLLOW-UP ----------

QUESTION: ok, so could you tell me what the maximum value could be
for each of three variables? this is actually a small part
of something else im working on but i need to find what the
highest number can be for each of the variables.
thanks again

Answer
I thought that using operations research would provide an initial answer so that I could see what a solution was, but it doesn't.  The only solution immdeiately apparent is (0,0,0).

Since the variables are non-negative,  a simple problem could be done to find a non-zero solution.
-1 -1 -1
7 -6 -5  1 0  0
-9  8  7  0 1  0

Using this approach, it comes out with two of the variables still being 0.