# linprog_simplex¶

Contain a Numba-jitted linear programming solver based on the Simplex Method.

class quantecon.optimize.linprog_simplex.PivOptions

Bases: tuple

namedtuple to hold tolerance values for pivoting

Attributes: fea_tol tol_piv tol_ratio_diff

Methods

 count(value, /) Return number of occurrences of value. index(value[, start, stop]) Return first index of value.
fea_tol
tol_piv
tol_ratio_diff
class quantecon.optimize.linprog_simplex.SimplexResult

Bases: tuple

namedtuple containing the result from linprog_simplex.

Attributes: fun lambd num_iter status success x

Methods

 count(value, /) Return number of occurrences of value. index(value[, start, stop]) Return first index of value.
fun
lambd
num_iter
status
success
x
quantecon.optimize.linprog_simplex.get_solution[source]

Fetch the optimal solution and value from an optimal tableau.

Parameters: tableau : ndarray(float, ndim=2) ndarray of shape (L+1, n+m+L+1) containing the optimal tableau, where L=m+k. basis : ndarray(int, ndim=1) ndarray of shape (L,) containing the optimal basis. x : ndarray(float, ndim=1) Empty ndarray of shape (n,) to store the primal solution. Modified in place. lambd : ndarray(float, ndim=1) Empty ndarray of shape (L,) to store the dual solution. Modified in place. b_signs : ndarray(bool, ndim=1) ndarray of shape (L,) whose i-th element is True iff the i-th element of the vector (b_ub, b_eq) is positive. fun : float The optimal value.
quantecon.optimize.linprog_simplex.linprog_simplex[source]

Solve a linear program in the following form by the simplex algorithm (with the lexicographic pivoting rule):

maximize:

c @ x


subject to:

A_ub @ x <= b_ub
A_eq @ x == b_eq
x >= 0

Parameters: c : ndarray(float, ndim=1) ndarray of shape (n,). A_ub : ndarray(float, ndim=2), optional ndarray of shape (m, n). b_ub : ndarray(float, ndim=1), optional ndarray of shape (m,). A_eq : ndarray(float, ndim=2), optional ndarray of shape (k, n). b_eq : ndarray(float, ndim=1), optional ndarray of shape (k,). max_iter : int, optional(default=10**6) Maximum number of iteration to perform. piv_options : PivOptions, optional PivOptions namedtuple to set the following tolerance values: fea_tol : float Feasibility tolerance (default=1e-06). tol_piv : float Pivot tolerance (default=1e-07). tol_ratio_diff : float Tolerance used in the the lexicographic pivoting (default=1e-13). tableau : ndarray(float, ndim=2), optional Temporary ndarray of shape (L+1, n+m+L+1) to store the tableau, where L=m+k. Modified in place. basis : ndarray(int, ndim=1), optional Temporary ndarray of shape (L,) to store the basic variables. Modified in place. x : ndarray(float, ndim=1), optional Output ndarray of shape (n,) to store the primal solution. lambd : ndarray(float, ndim=1), optional Output ndarray of shape (L,) to store the dual solution. res : SimplexResult namedtuple consisting of the fields: x : ndarray(float, ndim=1) ndarray of shape (n,) containing the primal solution. lambd : ndarray(float, ndim=1) ndarray of shape (L,) containing the dual solution. fun : float Value of the objective function. success : bool 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 apperas to be unbounded  num_iter : int The number of iterations performed.

References

1. Border, “The Gauss–Jordan and Simplex Algorithms” 2004.
quantecon.optimize.linprog_simplex.nt
quantecon.optimize.linprog_simplex.solve_tableau[source]

Perform the simplex algorithm on a given tableau in canonical form.

Used to solve a linear program in the following form:

maximize:

c @ x


subject to:

A_ub @ x <= b_ub
A_eq @ x == b_eq
x >= 0


where A_ub is of shape (m, n) and A_eq is of shape (k, n). Thus, tableau is of shape (L+1, n+m+L+1), where L=m+k, and

• tableau[np.arange(L), :][:, basis] must be an identity matrix, and
• the elements of tableau[:-1, -1] must be nonnegative.
Parameters: tableau : ndarray(float, ndim=2) ndarray of shape (L+1, n+m+L+1) containing the tableau. Modified in place. basis : ndarray(int, ndim=1) ndarray of shape (L,) containing the basic variables. Modified in place. max_iter : int, optional(default=10**6) Maximum number of pivoting steps. skip_aux : bool, optional(default=True) Whether to skip the coefficients of the auxiliary (or artificial) variables in pivot column selection. piv_options : PivOptions, optional PivOptions namedtuple to set the tolerance values. success : bool True if the algorithm succeeded in finding an optimal solution. status : int An integer representing the exit status of the optimization. num_iter : int The number of iterations performed.