

   SSiimmpplleexx MMeetthhoodd ffoorr LLiinneeaarr PPrrooggrraammmmiinngg PPrroobblleemmss

        simplex(a, A1=NULL, b1=NULL, A2=NULL, b2=NULL, A3=NULL,
                b3=NULL, maxi=F, n.iter=NULL, eps=1e-06)

   AArrgguummeennttss::

          a: A vector of length `n' which gives the coeffi-
             cients of the objective function.

         A1: An `m1' by `n' matrix of coefficients for the "<="
             type of constraints.

         b1: A vector of length `m1' giving the right hand side
             of the "<=" constraints.  This argument is
             required if `A1' is given and ignored otherwise.
             All values in `b1' must be non-negative.

         A2: An `m2' by `n' matrix of coefficients for the ">="
             type of constraints.

         b2: A vector of length `m2' giving the right hand side
             of the ">=" constraints.  This argument is
             required if `A2' is given and ignored otherwise.
             All values in `b2' must be non-negative.  Note
             that the constraints `x >= 0' are included auto-
             matically and so should not be repeated here.

         A3: An `m3' by `n' matrix of coefficients for the
             equality constraints.

         b3: A vector of length `m3' giving the right hand side
             of equality constraints.  This argument is
             required if `A3' is given and ignored otherwise.
             All values in `b3' must be non-negative.

       maxi: A logical flag which specifies minimization if
             `FALSE' (default) and maximization otherwise.  If
             `maxi' is `TRUE' then the maximization problem is
             recast as a minimization problem by changing the
             objective function coefficients to their nega-
             tives.

     n.iter: The maximum number of iterations to be conducted
             in each phase of the simplex method.  The default
             is `n+2*(m1+m2+m3)'.

        eps: The floating point tolerance to be used in tests
             of equality.

   DDeessccrriippttiioonn::

        This function will optimize the linear function `a%*%x'
        subject to the constraints `A1%*%x <= b1', `A2%*%x >=
        b2', `A3%*%x = b3' and `x >= 0'.  Either maximization
        or minimization is possible but the default is mini-
        mization.

   DDeettaaiillss::

        The method employed by this function is the two phase
        tableau simplex method.  If there are ">=" or equality
        constraints an initial feasible solution is not easy to
        find.  To find a feasible solution an artificial vari-
        able is introduced into each ">=" or equality con-
        straint and an auxiliary objective function is defined
        as the sum of these artificial variables.  If a feasi-
        ble solution to the set of constraints exists then the
        auxiliary objective will be minimized when all of the
        artificial variables are 0.  These are then discarded
        and the original problem solved starting at the solu-
        tion to the auxiliary problem.  If the only constraints
        are of the "<=" form, the origin is a feasible solution
        and so the first stage can be omitted.

   VVaalluuee::

        An object of class `"simplex"'.

   NNOOTTEE::

        The method employed here is suitable only for rela-
        tively small systems.  Also if possible the number of
        constraints should be reduced to a minimum in order to
        speed up the execution time which is approximately pro-
        portional to the cube of the number of constraints.  In
        particular if there are any constraints of the form
        `x[i] >= b2[i]' they should be omitted by setting `x[i]
        = x[i]-b2[i]', changing all the constraints and the
        objective function accordingly and then transforming
        back after the solution has been found.

   RReeffeerreenncceess::

        Gill, P.E., Murray, W. and Wright, M.H. (1991) Numeri-
        cal Linear Algebra and Optimization Vol. 1. Addison-
        Wesley.

        Press, W.H., Teukolsky, S.A., Vetterling, W.T. and
        Flannery, B.P. (1992) Numerical Recipes: The Art of
        Scientific Computing (Second Edition).  Cambridge Uni-
        versity Press.

   EExxaammpplleess::

        #  This example is taken from Exercise 7.5 of Gill, Murray,
        #  and Wright (1991).
        enj <- c(200, 6000, 3000, -200)
        fat <- c(800, 6000, 1000, 400)
        vitx <- c(50, 3, 150, 100)
        vity <- c(10, 10, 75, 100)
        vitz <- c(150, 35, 75, 5)
        simplex(a=enj, A1=fat, b1=13800, A2=rbind(vitx, vity, vitz),
                b2=c(600, 300, 550), maxi=T)

