def _linprog_simplex(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None,<EOL>bounds=None, maxiter=<NUM_LIT:1000>, disp=False, callback=None,<EOL>tol=<NUM_LIT>, bland=False, **unknown_options):
_check_unknown_options(unknown_options)<EOL>status = <NUM_LIT:0><EOL>messages = {<NUM_LIT:0>: "<STR_LIT>",<EOL><NUM_LIT:1>: "<STR_LIT>",<EOL><NUM_LIT:2>: "<STR_LIT>"<EOL>"<STR_LIT>",<EOL><NUM_LIT:3>: "<STR_LIT>",<EOL><NUM_LIT:4>: "<STR_LIT>"}<EOL>have_floor_variable = False<EOL>cc = np.asarray(c)<EOL>f0 = <NUM_LIT:0><EOL>n = len(c)<EOL>Aeq = np.asarray(A_eq) if A_eq is not None else np.empty([<NUM_LIT:0>, len(cc)])<EOL>Aub = np.asarray(A_ub) if A_ub is not None else np.empty([<NUM_LIT:0>, len(cc)])<EOL>beq = np.ravel(np.asarray(b_eq)) if b_eq is not None else np.empty([<NUM_LIT:0>])<EOL>bub = np.ravel(np.asarray(b_ub)) if b_ub is not None else np.empty([<NUM_LIT:0>])<EOL>L = np.zeros(n, dtype=np.float64)<EOL>U = np.ones(n, dtype=np.float64)*np.inf<EOL>if bounds is None or len(bounds) == <NUM_LIT:0>:<EOL><INDENT>pass<EOL><DEDENT>elif len(bounds) == <NUM_LIT:2> and not hasattr(bounds[<NUM_LIT:0>], '<STR_LIT>'):<EOL><INDENT>L = np.asarray(n*[bounds[<NUM_LIT:0>]], dtype=np.float64)<EOL>U = np.asarray(n*[bounds[<NUM_LIT:1>]], dtype=np.float64)<EOL><DEDENT>else:<EOL><INDENT>if len(bounds) != n:<EOL><INDENT>status = -<NUM_LIT:1><EOL>message = ("<STR_LIT>"<EOL>"<STR_LIT>")<EOL><DEDENT>else:<EOL><INDENT>try:<EOL><INDENT>for i in range(n):<EOL><INDENT>if len(bounds[i]) != <NUM_LIT:2>:<EOL><INDENT>raise IndexError()<EOL><DEDENT>L[i] = bounds[i][<NUM_LIT:0>] if bounds[i][<NUM_LIT:0>] is not None else -np.inf<EOL>U[i] = bounds[i][<NUM_LIT:1>] if bounds[i][<NUM_LIT:1>] is not None else np.inf<EOL><DEDENT><DEDENT>except IndexError:<EOL><INDENT>status = -<NUM_LIT:1><EOL>message = ("<STR_LIT>"<EOL>"<STR_LIT>"<EOL>"<STR_LIT>")<EOL><DEDENT><DEDENT><DEDENT>if np.any(L == -np.inf):<EOL><INDENT>n = n + <NUM_LIT:1><EOL>L = np.concatenate([np.array([<NUM_LIT:0>]), L])<EOL>U = np.concatenate([np.array([np.inf]), U])<EOL>cc = np.concatenate([np.array([<NUM_LIT:0>]), cc])<EOL>Aeq = np.hstack([np.zeros([Aeq.shape[<NUM_LIT:0>], <NUM_LIT:1>]), Aeq])<EOL>Aub = np.hstack([np.zeros([Aub.shape[<NUM_LIT:0>], <NUM_LIT:1>]), Aub])<EOL>have_floor_variable = True<EOL><DEDENT>for i in range(n):<EOL><INDENT>if(L[i] > U[i]):<EOL><INDENT>status = -<NUM_LIT:1><EOL>message = ("<STR_LIT>"<EOL>"<STR_LIT>" % (i, i))<EOL><DEDENT>if np.isinf(L[i]) and L[i] > <NUM_LIT:0>:<EOL><INDENT>status = -<NUM_LIT:1><EOL>message = ("<STR_LIT>"<EOL>"<STR_LIT>")<EOL><DEDENT>if np.isinf(U[i]) and U[i] < <NUM_LIT:0>:<EOL><INDENT>status = -<NUM_LIT:1><EOL>message = ("<STR_LIT>"<EOL>"<STR_LIT>")<EOL><DEDENT>if np.isfinite(L[i]) and L[i] > <NUM_LIT:0>:<EOL><INDENT>Aub = np.vstack([Aub, np.zeros(n)])<EOL>Aub[-<NUM_LIT:1>, i] = -<NUM_LIT:1><EOL>bub = np.concatenate([bub, np.array([-L[i]])])<EOL>L[i] = <NUM_LIT:0><EOL><DEDENT>if np.isfinite(U[i]):<EOL><INDENT>Aub = np.vstack([Aub, np.zeros(n)])<EOL>Aub[-<NUM_LIT:1>, i] = <NUM_LIT:1><EOL>bub = np.concatenate([bub, np.array([U[i]])])<EOL>U[i] = np.inf<EOL><DEDENT><DEDENT>for i in range(<NUM_LIT:0>, n):<EOL><INDENT>if L[i] < <NUM_LIT:0>:<EOL><INDENT>if np.isfinite(L[i]) and L[i] < <NUM_LIT:0>:<EOL><INDENT>beq[:] = beq[:] - Aeq[:, i] * L[i]<EOL>bub[:] = bub[:] - Aub[:, i] * L[i]<EOL>f0 = f0 - cc[i] * L[i]<EOL><DEDENT>else:<EOL><INDENT>Aeq[:, <NUM_LIT:0>] = Aeq[:, <NUM_LIT:0>] - Aeq[:, i]<EOL>Aub[:, <NUM_LIT:0>] = Aub[:, <NUM_LIT:0>] - Aub[:, i]<EOL>cc[<NUM_LIT:0>] = cc[<NUM_LIT:0>] - cc[i]<EOL><DEDENT><DEDENT>if np.isinf(U[i]):<EOL><INDENT>if U[i] < <NUM_LIT:0>:<EOL><INDENT>status = -<NUM_LIT:1><EOL>message = ("<STR_LIT>"<EOL>"<STR_LIT>")<EOL><DEDENT><DEDENT><DEDENT>mub = len(bub)<EOL>meq = len(beq)<EOL>m = mub+meq<EOL>n_slack = mub<EOL>n_artificial = meq + _count_nonzero(bub < <NUM_LIT:0>)<EOL>try:<EOL><INDENT>Aub_rows, Aub_cols = Aub.shape<EOL><DEDENT>except ValueError:<EOL><INDENT>raise ValueError("<STR_LIT>")<EOL><DEDENT>try:<EOL><INDENT>Aeq_rows, Aeq_cols = Aeq.shape<EOL><DEDENT>except ValueError:<EOL><INDENT>raise ValueError("<STR_LIT>")<EOL><DEDENT>if Aeq_rows != meq:<EOL><INDENT>status = -<NUM_LIT:1><EOL>message = ("<STR_LIT>"<EOL>"<STR_LIT>"<EOL>"<STR_LIT>")<EOL><DEDENT>if Aub_rows != mub:<EOL><INDENT>status = -<NUM_LIT:1><EOL>message = ("<STR_LIT>"<EOL>"<STR_LIT>"<EOL>"<STR_LIT>")<EOL><DEDENT>if Aeq_cols > <NUM_LIT:0> and Aeq_cols != n:<EOL><INDENT>status = -<NUM_LIT:1><EOL>message = ("<STR_LIT>"<EOL>"<STR_LIT>"<EOL>"<STR_LIT>")<EOL><DEDENT>if Aub_cols > <NUM_LIT:0> and Aub_cols != n:<EOL><INDENT>status = -<NUM_LIT:1><EOL>message = ("<STR_LIT>"<EOL>"<STR_LIT>")<EOL><DEDENT>if status != <NUM_LIT:0>:<EOL><INDENT>raise ValueError(message)<EOL><DEDENT>T = np.zeros([m+<NUM_LIT:2>, n+n_slack+n_artificial+<NUM_LIT:1>])<EOL>T[-<NUM_LIT:2>, :n] = cc<EOL>T[-<NUM_LIT:2>, -<NUM_LIT:1>] = f0<EOL>b = T[:-<NUM_LIT:2>, -<NUM_LIT:1>]<EOL>if meq > <NUM_LIT:0>:<EOL><INDENT>T[:meq, :n] = Aeq<EOL>b[:meq] = beq<EOL><DEDENT>if mub > <NUM_LIT:0>:<EOL><INDENT>T[meq:meq+mub, :n] = Aub<EOL>b[meq:meq+mub] = bub<EOL>np.fill_diagonal(T[meq:m, n:n+n_slack], <NUM_LIT:1>)<EOL><DEDENT>slcount = <NUM_LIT:0><EOL>avcount = <NUM_LIT:0><EOL>basis = np.zeros(m, dtype=int)<EOL>r_artificial = np.zeros(n_artificial, dtype=int)<EOL>for i in range(m):<EOL><INDENT>if i < meq or b[i] < <NUM_LIT:0>:<EOL><INDENT>basis[i] = n+n_slack+avcount<EOL>r_artificial[avcount] = i<EOL>avcount += <NUM_LIT:1><EOL>if b[i] < <NUM_LIT:0>:<EOL><INDENT>b[i] *= -<NUM_LIT:1><EOL>T[i, :-<NUM_LIT:1>] *= -<NUM_LIT:1><EOL><DEDENT>T[i, basis[i]] = <NUM_LIT:1><EOL>T[-<NUM_LIT:1>, basis[i]] = <NUM_LIT:1><EOL><DEDENT>else:<EOL><INDENT>basis[i] = n+slcount<EOL>slcount += <NUM_LIT:1><EOL><DEDENT><DEDENT>for r in r_artificial:<EOL><INDENT>T[-<NUM_LIT:1>, :] = T[-<NUM_LIT:1>, :] - T[r, :]<EOL><DEDENT>nit1, status = _solve_simplex(T, n, basis, phase=<NUM_LIT:1>, callback=callback,<EOL>maxiter=maxiter, tol=tol, bland=bland)<EOL>if abs(T[-<NUM_LIT:1>, -<NUM_LIT:1>]) < tol:<EOL><INDENT>T = T[:-<NUM_LIT:1>, :]<EOL>T = np.delete(T, np.s_[n+n_slack:n+n_slack+n_artificial], <NUM_LIT:1>)<EOL><DEDENT>else:<EOL><INDENT>status = <NUM_LIT:2><EOL><DEDENT>if status != <NUM_LIT:0>:<EOL><INDENT>message = messages[status]<EOL>if disp:<EOL><INDENT>print(message)<EOL><DEDENT>return OptimizeResult(x=np.nan, fun=-T[-<NUM_LIT:1>, -<NUM_LIT:1>], nit=nit1, status=status,<EOL>message=message, success=False)<EOL><DEDENT>nit2, status = _solve_simplex(T, n, basis, maxiter=maxiter-nit1, phase=<NUM_LIT:2>,<EOL>callback=callback, tol=tol, nit0=nit1,<EOL>bland=bland)<EOL>solution = np.zeros(n+n_slack+n_artificial)<EOL>solution[basis[:m]] = T[:m, -<NUM_LIT:1>]<EOL>x = solution[:n]<EOL>slack = solution[n:n+n_slack]<EOL>masked_L = np.ma.array(L, mask=np.isinf(L), fill_value=<NUM_LIT:0.0>).filled()<EOL>x = x + masked_L<EOL>if have_floor_variable:<EOL><INDENT>for i in range(<NUM_LIT:1>, n):<EOL><INDENT>if np.isinf(L[i]):<EOL><INDENT>x[i] -= x[<NUM_LIT:0>]<EOL><DEDENT><DEDENT>x = x[<NUM_LIT:1>:]<EOL><DEDENT>obj = -T[-<NUM_LIT:1>, -<NUM_LIT:1>]<EOL>if status in (<NUM_LIT:0>, <NUM_LIT:1>):<EOL><INDENT>if disp:<EOL><INDENT>print(messages[status])<EOL>print("<STR_LIT>".format(obj))<EOL>print("<STR_LIT>".format(nit2))<EOL><DEDENT><DEDENT>else:<EOL><INDENT>if disp:<EOL><INDENT>print(messages[status])<EOL>print("<STR_LIT>".format(nit2))<EOL><DEDENT><DEDENT>return OptimizeResult(x=x, fun=obj, nit=int(nit2), status=status, slack=slack,<EOL>message=messages[status], success=(status == <NUM_LIT:0>))<EOL>
Solve the following linear programming problem via a two-phase
simplex algorithm.

maximize:     c^T * x

subject to:   A_ub * x <= b_ub
              A_eq * x == b_eq

Parameters
----------
c : array_like
    Coefficients of the linear objective function to be maximized.
A_ub :
    2-D array which, when matrix-multiplied by x, gives the values of the
    upper-bound inequality constraints at x.
b_ub : array_like
    1-D array of values representing the upper-bound of each inequality
    constraint (row) in A_ub.
A_eq : array_like
    2-D array which, when matrix-multiplied by x, gives the values of the
    equality constraints at x.
b_eq : array_like
    1-D array of values representing the RHS of each equality constraint
    (row) in A_eq.
bounds : array_like
    The bounds for each independent variable in the solution, which can take
    one of three forms::
    None : The default bounds, all variables are non-negative.
    (lb, ub) : If a 2-element sequence is provided, the same
              lower bound (lb) and upper bound (ub) will be applied
              to all variables.
    [(lb_0, ub_0), (lb_1, ub_1), ...] : If an n x 2 sequence is provided,
              each variable x_i will be bounded by lb[i] and ub[i].
    Infinite bounds are specified using -np.inf (negative)
    or np.inf (positive).
maxiter : int
   The maximum number of iterations to perform.
disp : bool
    If True, print exit status message to sys.stdout
callback : callable
    If a callback function is provide, it will be called within each
    iteration of the simplex algorithm. The callback must have the
    signature `callback(xk, **kwargs)` where xk is the current solution
    vector and kwargs is a dictionary containing the following::
    "tableau" : The current Simplex algorithm tableau
    "nit" : The current iteration.
    "pivot" : The pivot (row, column) used for the next iteration.
    "phase" : Whether the algorithm is in Phase 1 or Phase 2.
    "bv" : A structured array containing a string representation of each
           basic variable and its current value.
tol : float
    The tolerance which determines when a solution is "close enough" to zero
    in Phase 1 to be considered a basic feasible solution or close enough
    to positive to to serve as an optimal solution.
bland : bool
    If True, use Bland's anti-cycling rule [3] to choose pivots to
    prevent cycling.  If False, choose pivots which should lead to a
    converged solution more quickly.  The latter method is subject to
    cycling (non-convergence) in rare instances.

Returns
-------
A scipy.optimize.OptimizeResult consisting of the following fields::
    x : ndarray
        The independent variable vector which optimizes the linear
        programming problem.
    slack : ndarray
        The values of the slack variables.  Each slack variable corresponds
        to an inequality constraint.  If the slack is zero, then the
        corresponding constraint is active.
    success : bool
        Returns True if the algorithm succeeded in finding an optimal
        solution.
    status : int
        An integer representing the exit status of the optimization::
         0 : Optimization terminated successfully
         1 : Iteration limit reached
         2 : Problem appears to be infeasible
         3 : Problem appears to be unbounded
    nit : int
        The number of iterations performed.
    message : str
        A string descriptor of the exit status of the optimization.

Examples
--------
Consider the following problem:

Minimize: f = -1*x[0] + 4*x[1]

Subject to: -3*x[0] + 1*x[1] <= 6
             1*x[0] + 2*x[1] <= 4
                        x[1] >= -3

where:  -inf <= x[0] <= inf

This problem deviates from the standard linear programming problem.  In
standard form, linear programming problems assume the variables x are
non-negative.  Since the variables don't have standard bounds where
0 <= x <= inf, the bounds of the variables must be explicitly set.

There are two upper-bound constraints, which can be expressed as

dot(A_ub, x) <= b_ub

The input for this problem is as follows:

>>> c = [-1, 4]
>>> A = [[-3, 1], [1, 2]]
>>> b = [6, 4]
>>> x0_bnds = (None, None)
>>> x1_bnds = (-3, None)
>>> res = linprog(c, A, b, bounds=(x0_bnds, x1_bnds), options={"disp":True})
>>> print(res)
Optimization terminated successfully.
     Current function value: 11.428571
     Iterations: 2
status: 0
success: True
fun: 11.428571428571429
x: array([-1.14285714,  2.57142857])
slack: array([], dtype=np.float64)
message: 'Optimization terminated successfully.'
nit: 2

References
----------
.. [1] Dantzig, George B., Linear programming and extensions. Rand
       Corporation Research Study Princeton Univ. Press, Princeton, NJ, 1963
.. [2] Hillier, S.H. and Lieberman, G.J. (1995), "Introduction to
       Mathematical Programming", McGraw-Hill, Chapter 4.
.. [3] Bland, Robert G. New finite pivoting rules for the simplex method.
       Mathematics of Operations Research (2), 1977: pp. 103-107.