I have added comments throughout your message and my original reply.
My comments are not preceeded by any characters while I have placed ***
before all the other lines.
***
***From guy@trofis.tfrc.csiro.au Tue Mar 24 21:42:42 1992
***Received: from [192.94.62.1] by orion.waterloo.edu with SMTP
***	id <AA09368>; Tue, 24 Mar 92 21:42:01 -0500
***Received: by trofis.tfrc.csiro.au id AA24625
***  (5.65c/IDA-1.4.4 for hwolkowi@orion.uwaterloo.ca); Wed, 25 Mar 1992 12:40:47 +1000
***Date: Wed, 25 Mar 1992 12:40:47 +1000
***From: Guy Carpenter <guy@trofis.tfrc.csiro.au>
***Message-Id: <199203250240.AA24625@trofis.tfrc.csiro.au>
***To: hwolkowi@orion
***Subject: Re: Convex Envelope in n-dimensions?
***Status: RO
***
***
***Late last year I posted a Q to the net asking about determining
***if a point was contained in the convex hull defined by a number
***of points.
***
***You were kind enough to formulate a comprehensive reply which
***directed me to Farkas lemma.
***
***At the time I was under pressure to get the code working, so I
***implemented a brute force solution.  It works.  It's very slow.
***But as the method shows promise, I am now trying to use your
***suggestions to write an efficient solution.
***
***I'm having a problem understanding the final step, and wonder if
***I could impose upon you for a little further direction.
***
***As a reminder, the problem as originally stated:
***
***>I have a set of points defined by coordinates in n-dimensional
***>space, where n varies, (no more than ~10).  I would like to be able
***>to define the smallest convex envelope which encloses those
***>points, so that I may check for inclusion/exclusion of points
***>from another set.
***
***Your solution, condensed here by me:
***
***> Let A denote the matrix with columns  a_i.
***> Let  the matrix B be A with the vector of ones    e^T   
***> adjoined as the last row.
***> Now suppose a point   y   is given.
***> Let b be the vector  y   with   1  adjoined as the last row.
***>
***> Then y is in the convex envelope if and only if
***>      b=Bx, x>=0
***> is a consistent system.
You can use the simplex method right here to find the vector x and so
see if y is in the convex envelope, i.e. solve the linear programming
problem:    min  0x  s.t.  Bx=b, x>=0
To solve this problem you have to use the two phase approach and phase I
is essentially equivalent to the Farkas lemma arguement I mentioned. So
if you need to actually find the vector x that gives the coordinates of
the convex combinations, then you should use the simplex method here,
i.e. phase I of the simplex method. The phase I approach identifies
infeasibility while if the problem is feasible, then the optimal value
of the phase I program is 0 and the optimal solution yields the vector x
and the basis tells you which columns of the matrix A are used in the
convex combination. The matrix B has n+1 rows and so there will be at
most n+1 columns that are needed in the basis. Less may be possible if
there is a degenerate basic feasible solution. NOte that the fact you
need at most n+1 is also a consequence of Caratheodory's theorem.
***>
***> Now Farkas Lemma states that this system is consistent if and only if
***>    B^Tz >= 0   implies  b^Tz >=0
***>
***> But this system can be checked using the simplex method, i.e. check
***> whether  0   is the solution of the linear program
***>      min  b^Tz    subject to   B^Tz >= 0
***> So, if  0 is the solution then the given point  y  is in the convex
***> envelope, otherwise it is not.
***
***I am using the simplex algorithm as presented in Sedgewick, Alogorithms
***in C.  Unfortunately Sedgewick doesn't persue the simplex alg very far,
***so I'm trying to work from his arm waving at the end of chapter.
***
***My fundamental problem is this:
***
***	Is the z vector constrained to z>=0 ?  This appears
No!!! You should not have z>=0. The standard trick is to do a
substitution, i.e. let z=z'-z'', where both z' and z'' are >=0. 
After this substitution you have a LP with nonnegative variables.
***	to be implicit in the method I am attempting to use,
***	and perhaps that is the start of my problem.  If it is not
***	so constrained, does the simplex code need to be changed?
***
***	Can I assume z=0 is a (possibly non-optimal) solution at
***	which to start the simplex driven pivoting?
***	It would appear to be the case, but I think this leads to
***	an inconsistant conclusion later on.
***
***To illustrate the approach, I will work a very simple problem and
***show how it fails:
***
***take 3 points in two dimensions : [1,2] [2,3] [0,4]
***and test for inclusion the point [20, 20], clearly outside.
***
***A = 1 2 0   B = 1 2 0  y = 20    b = 20 
***    2 3 4       2 3 4      20        20
***                1 1 1                 1
***
***B^T = 1 2 1   b^T = 20 20 1
***      2 3 1
***      0 4 1
***
***minimize b^Tz subject to B^Tz >=0
This is the correct LP here.
***
***Yields an objective function maximize (20 z1 + 20 z2 + z3)
Why maximize????? You mean minimze here????
***This is adjusted to fit the alg to minimize (-20 z1 - 20 z2 - z3).
***
***The set of constraints is:	Adding slack variables yields:
***
***1 z1 + 2 z2 + 1 z3 >=0        1 z1 + 2 z2 + 1 z3 + k1 = 0
***2 z1 + 3 z2 + 1 z3 >=0        2 z1 + 3 z2 + 1 z3 + k2 = 0
***0 z1 + 4 z2 + 1 z3 >=0        0 z1 + 4 z2 + 1 z3 + k3 = 0
You have added NEGATIVE slacks??? You need to add surplus variables
since the constraints were   >= 0.                    
1 z1 + 2 z2 + 1 z3 >=0        1 z1 + 2 z2 + 1 z3 - k1 = 0
2 z1 + 3 z2 + 1 z3 >=0        2 z1 + 3 z2 + 1 z3 - k2 = 0
0 z1 + 4 z2 + 1 z3 >=0        0 z1 + 4 z2 + 1 z3 - k3 = 0
I will not continue with example as I can see that it will not work due
to your assumptions that zi>=0 and since ki <= 0 in your formulation.
Please try solving the LP I mentioned above. I think that approach will
be easier and there is no need to worry about the nonnegativity of the
variables only adding artificial variables for phase I.
***
***Which produces the following matrix ala Sedgewick:
***
***20 20 -1  0  0  0  0	<- objective function coeff's negated
*** 1  2  1  1  0  0  0
*** 2  3  1  0  1  0  0
*** 0  4  1  0  0  1  0
***
***The simplex code will cause pivoting at (2,3)  (assuming top left is (1,1).)
***and consider the game over, since there will be no more negative
***coeffients in the objective function.  This yields the following:
***
***23 22  0  1  0  0  0	<- value of objective fn is still 0, implying
*** 3  2  1  1  0  0  0       that the point y is in the convex hull,
***-1  1  0 -1  1  0  0       which we know to be wrong.
***-5  2  0 -1  0  1  0
***
***I can clearly see that this last stage is meaningless.  Since all of the
***last column values are 0, the value of the objective function will always
***be zero.
***
***I though perhaps I needed to use the two phase method described briefly
***at the end of the chapter:
***
***	"Specifically, we add another set of artificial variables
***	s1.s2...sn and add variable si to the ith equation.  This is
***	done simply by adding to the matrix N columns filled with the
***	identity matrix.  This immediately gives a feasible basis for
***	this new linear probram.  The trick is to run the above program
***	algorithm with the objective function -s1-s2-...-sn.  If there
***	is a solution to the original linear program, then this
***	objective function can be maximized at zero."
***
***Oh my - that sounds very much like the lemma which is the basis of
***the method you described?!  Worse, if the objective function to 
***be minimised has all negative coefficients, Sedgewicks own code
***will refuse to do anything at all, as his code terminates as soon
***as row 0 contains no negative values.  (this row is initialized with
***the negative of the coefficients.)
***
***I am immensely grateful for the help you have already provided, and
***apologise for asking for more of your time. Any help will be much
***appreciated.
***
***Many thanks,
***Guy.
***----------------------------------------------------------------------
***CSIRO Tropical		P.O. Box 780             Work : (070) 91 1755
***      Forest		Atherton Q 4883          Fax  : (070) 91 3245
***      Research		Australia                Home : (070) 95 3309
***      Centre		guy@tfrc.csiro.au
***----------------------------------------------------------------------
***
***
***