The purpose of this module is to support learning and exploring of the simplex method. While it does allow solving Linear Programming Problems (LPPs) in a number of ways, it may require explicit (and correct!) description of steps and is likely to be much slower than “regular” LP solvers. Therefore, do not use this module if all you want is the result. If, however, you want to learn how the simplex method works and see what happens in different situations using different strategies, but don’t want to deal with tedious arithmetic, this module is for you!
Historically it was created to complement the Math 373 course on Mathematical Programming and Optimization at the University of Alberta, Edmonton, Canada.
AUTHORS:
EXAMPLES:
Most of the module functionality is demonstrated on the following problem.
Using variables and
for land used to grow corn and barley respectively,
in acres, we can construct the following LP problem:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: P
LP problem (use typeset mode to see details)
It is recommended to copy-paste such examples into your own worksheet, so that you can run these commands with typeset mode on and get
Since it has only two variables, we can solve it graphically:
sage: P.plot()
The simplex method can be applied only to problems in standard form, which can be created either directly
sage: LPProblemStandardForm(A, b, c, ["C", "B"])
LP problem (use typeset mode to see details)
or from an already constructed problem of “general type”:
sage: P = P.standard_form()
In this case the problem does not require any modifications to be written in standard form, but this step is still necessary to enable methods related to the simplex method.
The simplest way to use the simplex method is:
sage: P.run_simplex_method()
'...'
(This method produces quite long formulas which have been omitted here.) But, of course, it is much more fun to do most of the steps by hand. Let’s start by creating the initial dictionary:
sage: D = P.initial_dictionary()
sage: D
LP problem dictionary (use typeset mode to see details)
Using typeset mode as recommended, you’ll see
With the initial or any other dictionary you can perform a number of checks:
sage: D.is_feasible()
True
sage: D.is_optimal()
False
You can look at many of its pieces and associated data:
sage: D.basic_variables()
(x3, x4)
sage: D.basic_solution()
(0, 0)
sage: D.objective_value()
0
Most importantly, you can perform steps of the simplex method by picking an entering variable, a leaving variable, and updating the dictionary:
sage: D.enter("C")
sage: D.leave(4)
sage: D.update()
If everything was done correctly, the new dictionary is still feasible and the objective value did not decrease:
sage: D.is_feasible()
True
sage: D.objective_value()
5000
If you are unsure about picking entering and leaving variables, you can use helper methods that will try their best to tell you what are your next options:
sage: D.possible_entering()
[B]
sage: D.possible_leaving()
Traceback (most recent call last):
...
ValueError: leaving variables can be determined
for feasible dictionaries with a set entering variable
or for dual feasible dictionaries
It is also possible to obtain feasible sets and final dictionaries of problems, work with revised dictionaries, and use the dual simplex method!
Note
Currently this does not have a display format for the terminal.
Bases: sage.structure.sage_object.SageObject
Abstract base class for dictionaries for LP problems.
Instantiating this class directly is meaningless, see LPDictionary and LPRevisedDictionary for useful extensions.
Return the base ring of self, i.e. the ring of coefficients.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.initial_dictionary()
sage: D.base_ring()
Rational Field
sage: D = P.revised_dictionary()
sage: D.base_ring()
Rational Field
Return the basic solution of self.
The basic solution associated to a dictionary is obtained by setting to zero all nonbasic_variables(), in which case basic_variables() have to be equal to constant_terms() in equations. It may refer to values of decision_variables() only or include slack_variables() as well.
INPUT:
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.initial_dictionary()
sage: D.basic_solution()
(0, 0)
sage: D.basic_solution(True)
(0, 0, 1000, 1500)
sage: D = P.revised_dictionary()
sage: D.basic_solution()
(0, 0)
sage: D.basic_solution(True)
(0, 0, 1000, 1500)
Return the coordinate ring of self.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.initial_dictionary()
sage: D.coordinate_ring()
Multivariate Polynomial Ring in x0, x1, x2, x3, x4
over Rational Field
sage: D = P.revised_dictionary()
sage: D.coordinate_ring()
Multivariate Polynomial Ring in x0, x1, x2, x3, x4
over Rational Field
Return ratios used to determine the entering variable based on leaving.
OUTPUT:
A list of pairs where
is a non-basic variable and
is the ratio of the objective coefficient
to the coefficient
of
in the relation for the leaving
variable
:
The order of pairs matches the order of
nonbasic_variables(),
but only with negative
are considered.
EXAMPLES:
sage: A = ([1, 1], [3, 1], [-1, -1])
sage: b = (1000, 1500, -400)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.dictionary(2, 3, 5)
sage: D.leave(3)
sage: D.dual_ratios()
[(5/2, x1), (5, x4)]
sage: D = P.revised_dictionary(2, 3, 5)
sage: D.leave(3)
sage: D.dual_ratios()
[(5/2, x1), (5, x4)]
Set v as the entering variable of self.
INPUT:
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.initial_dictionary()
sage: D.enter("x1")
We can also use indices of variables:
sage: D.enter(1)
Or variable names without quotes after injecting them:
sage: P.inject_variables()
Defining x0, x1, x2, x3, x4
sage: D.enter(x1)
The same works for revised dictionaries as well:
sage: D = P.revised_dictionary()
sage: D.enter(x1)
Check if self is dual feasible.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.initial_dictionary()
sage: D.is_dual_feasible()
False
sage: D = P.revised_dictionary()
sage: D.is_dual_feasible()
False
Check if self is feasible.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.initial_dictionary()
sage: D.is_feasible()
True
sage: D = P.revised_dictionary()
sage: D.is_feasible()
True
Check if self is optimal.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.initial_dictionary()
sage: D.is_optimal()
False
sage: D = P.revised_dictionary()
sage: D.is_optimal()
False
sage: D = P.revised_dictionary(1, 2)
sage: D.is_optimal()
True
Set v as the leaving variable of self.
INPUT:
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.initial_dictionary()
sage: D.leave("x4")
We can also use indices of variables:
sage: D.leave(4)
Or variable names without quotes after injecting them:
sage: P.inject_variables()
Defining x0, x1, x2, x3, x4
sage: D.leave(x4)
The same works for revised dictionaries as well:
sage: D = P.revised_dictionary()
sage: D.leave(x4)
Return possible dual simplex method steps for self.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.dictionary(2, 3)
sage: D.possible_dual_simplex_method_steps()
[(x3, [x1])]
sage: D = P.revised_dictionary(2, 3)
sage: D.possible_dual_simplex_method_steps()
[(x3, [x1])]
Return possible entering variables for self.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.initial_dictionary()
sage: D.possible_entering()
[x1, x2]
sage: D = P.revised_dictionary()
sage: D.possible_entering()
[x1, x2]
Return possible leaving variables for self.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.initial_dictionary()
sage: D.enter(1)
sage: D.possible_leaving()
[x4]
sage: D = P.revised_dictionary()
sage: D.enter(1)
sage: D.possible_leaving()
[x4]
Return possible simplex method steps for self.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.initial_dictionary()
sage: D.possible_simplex_method_steps()
[(x1, [x4]), (x2, [x3])]
sage: D = P.revised_dictionary()
sage: D.possible_simplex_method_steps()
[(x1, [x4]), (x2, [x3])]
Return ratios used to determine the leaving variable based on entering.
OUTPUT:
A list of pairs where
is a basic variable and
is the ratio of the constant term
to the
coefficient
of the entering variable
in the relation
for
:
The order of pairs matches the order of
basic_variables(),
but only with positive
are considered.
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.initial_dictionary()
sage: D.enter(1)
sage: D.ratios()
[(1000, x3), (500, x4)]
sage: D = P.revised_dictionary()
sage: D.enter(1)
sage: D.ratios()
[(1000, x3), (500, x4)]
Bases: sage.numerical.interactive_simplex_method.LPAbstractDictionary
Construct a dictionary for an LP problem.
A dictionary consists of the following data:
INPUT:
OUTPUT:
Note
This constructor does not check correctness of input, as it is intended to be used internally by LPProblemStandardForm.
EXAMPLES:
The intended way to use this class is indirect:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.initial_dictionary()
sage: D
LP problem dictionary (use typeset mode to see details)
But if you want you can create a dictionary without starting with an LP problem, here is construction of the same dictionary as above:
sage: A = matrix(QQ, ([1, 1], [3, 1]))
sage: b = vector(QQ, (1000, 1500))
sage: c = vector(QQ, (10, 5))
sage: R = PolynomialRing(QQ, "x1, x2, x3, x4", order="neglex")
sage: from sage.numerical.interactive_simplex_method \
....: import LPDictionary
sage: D2 = LPDictionary(A, b, c, 0, R.gens()[2:], R.gens()[:2], "z")
sage: D2 == D
True
Perform the Enter-Leave-LaTeX-Update-LaTeX step sequence on self.
INPUT:
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.initial_dictionary()
sage: D.ELLUL("x1", "x4")
\renewcommand{\arraystretch}{1.5} \setlength{\arraycolsep}{0.125em}
\begin{array}{|rcrcrcr|}
\hline
x_{3} & = & 1000 & - &\color{green} x_{1} & - & x_{2}\\
\color{red}x_{4} &\color{red} = &\color{red} 1500 &\color{red} - &\color{blue} 3 x_{1} &\color{red} - &\color{red} x_{2}\\
\hline
z & = & 0 & + &\color{green} 10 x_{1} & + & 5 x_{2}\\
\hline
\multicolumn{2}{c}{}\\[-3ex]
\hline
x_{3} & = & 500 & + & \frac{1}{3} x_{4} & - & \frac{2}{3} x_{2}\\
x_{1} & = & 500 & - & \frac{1}{3} x_{4} & - & \frac{1}{3} x_{2}\\
\hline
z & = & 5000 & - & \frac{10}{3} x_{4} & + & \frac{5}{3} x_{2}\\
\hline
\end{array}
This is how the above output looks when rendered:
The column of the entering variable is green, while the row of the leaving variable is red in the original dictionary state on the top. The new state after the update step is shown on the bottom.
Return the basic variables of self.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.initial_dictionary()
sage: D.basic_variables()
(x3, x4)
Return the constant terms of relations of self.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.initial_dictionary()
sage: D.constant_terms()
(1000, 1500)
Return coefficients of the entering variable.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.initial_dictionary()
sage: D.enter(1)
sage: D.entering_coefficients()
(1, 3)
Return coefficients of the leaving variable.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.dictionary(2, 3)
sage: D.leave(3)
sage: D.leaving_coefficients()
(-2, -1)
Return non-basic variables of self.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.initial_dictionary()
sage: D.nonbasic_variables()
(x1, x2)
Return coefficients of the objective of self.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.initial_dictionary()
sage: D.objective_coefficients()
(10, 5)
Return the value of the objective at the basic_solution() of self.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.initial_dictionary()
sage: D.objective_value()
0
Update self using previously set entering and leaving variables.
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.initial_dictionary()
sage: D.objective_value()
0
sage: D.enter("x1")
sage: D.leave("x4")
sage: D.update()
sage: D.objective_value()
5000
Bases: sage.structure.sage_object.SageObject
Construct an LP (Linear Programming) problem.
This class supports LP problems with “variables on the left” constraints.
INPUT:
EXAMPLES:
We will construct the following problem:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblem(A, b, c, ["C", "B"], variable_type=">=")
Same problem, but more explicitly:
sage: P = LPProblem(A, b, c, ["C", "B"],
....: constraint_type="<=", variable_type=">=")
Even more explicitly:
sage: P = LPProblem(A, b, c, ["C", "B"], problem_type="max",
....: constraint_type=["<=", "<="], variable_type=[">=", ">="])
Using the last form you should be able to represent any LP problem, as long as all like terms are collected and in constraints variables and constants are on different sides.
Return coefficients of constraints of self, i.e. .
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: P.constraint_coefficients()
[1 1]
[3 1]
sage: P.A()
[1 1]
[3 1]
Return ,
,
, and
of self as a tuple.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: P.Abcx()
(
[1 1]
[3 1], (1000, 1500), (10, 5), (C, B)
)
Return constant terms of constraints of self, i.e. .
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: P.constant_terms()
(1000, 1500)
sage: P.b()
(1000, 1500)
Return the base ring of self.
Note
The base ring of LP problems is always a field.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: P.base_ring()
Rational Field
sage: c = (10, 5.)
sage: P = LPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: P.base_ring()
Real Field with 53 bits of precision
Return coefficients of the objective of self, i.e. .
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: P.objective_coefficients()
(10, 5)
sage: P.c()
(10, 5)
Return constant terms of constraints of self, i.e. .
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: P.constant_terms()
(1000, 1500)
sage: P.b()
(1000, 1500)
Return coefficients of constraints of self, i.e. .
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: P.constraint_coefficients()
[1 1]
[3 1]
sage: P.A()
[1 1]
[3 1]
Return decision variables of self, i.e. .
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: P.decision_variables()
(C, B)
sage: P.x()
(C, B)
Construct the dual LP problem for self.
INPUT:
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: DP = P.dual()
sage: DP.b() == P.c()
True
sage: DP.dual(["C", "B"]) == P
True
Return the feasible set of self.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: P.feasible_set()
A 2-dimensional polyhedron in QQ^2
defined as the convex hull of 4 vertices
Check if self is bounded.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: P.is_bounded()
True
Check if self is feasible.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: P.is_feasible()
True
Return the number of constraints of self, i.e. .
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: P.n_constraints()
2
sage: P.m()
2
Return the number of decision variables of self, i.e. .
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: P.n_variables()
2
sage: P.n()
2
Return the number of constraints of self, i.e. .
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: P.n_constraints()
2
sage: P.m()
2
Return the number of decision variables of self, i.e. .
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: P.n_variables()
2
sage: P.n()
2
Return coefficients of the objective of self, i.e. .
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: P.objective_coefficients()
(10, 5)
sage: P.c()
(10, 5)
Return an optimal solution of self.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: P.optimal_solution()
(250, 750)
Return the optimal value for self.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: P.optimal_value()
6250
Return a plot for solving self graphically.
INPUT:
OUTPUT:
This only works for problems with two decision variables. On the plot the black arrow indicates the direction of growth of the objective. The lines perpendicular to it are level curves of the objective. If there are optimal solutions, the arrow originates in one of them and the corresponding level curve is solid: all points of the feasible set on it are optimal solutions. Otherwise the arrow is placed in the center. If the problem is infeasible or the objective is zero, a plot of the feasible set only is returned.
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: p = P.plot()
sage: p.show()
In this case the plot works better with the following axes ranges:
sage: p = P.plot(0, 1000, 0, 1500)
sage: p.show()
TESTS:
We check that zero objective can be dealt with:
sage: LPProblem(A, b, (0, 0), ["C", "B"], variable_type=">=").plot()
Return a plot of the feasible set of self.
INPUT:
OUTPUT:
This only works for a problem with two decision variables. The plot
shows boundaries of constraints with a shadow on one side for
inequalities. If the feasible_set() is not empty and at least
part of it is in the given boundaries, it will be shaded gray and
will be placed in its middle.
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: p = P.plot_feasible_set()
sage: p.show()
In this case the plot works better with the following axes ranges:
sage: p = P.plot_feasible_set(0, 1000, 0, 1500)
sage: p.show()
Construct the LP problem in standard form equivalent to self.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: DP = P.dual()
sage: DPSF = DP.standard_form()
sage: DPSF.b()
(-10, -5)
Return decision variables of self, i.e. .
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: P.decision_variables()
(C, B)
sage: P.x()
(C, B)
Bases: sage.numerical.interactive_simplex_method.LPProblem
Construct an LP (Linear Programming) problem in standard form.
The used standard form is:
INPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
Unlike LPProblem, this class does not allow you to adjust types of constraints (they are always "<=") and variables (they are always ">="), and the problem type may only be "max" or "-max". You may give custom names to slack and auxiliary variables, but in most cases defaults should work:
sage: P.decision_variables()
(x1, x2)
sage: P.slack_variables()
(x3, x4)
Construct the auxiliary problem for self.
OUTPUT:
The auxiliary problem with the auxiliary variable is
Such problems are used when the initial_dictionary() is infeasible.
EXAMPLES:
sage: A = ([1, 1], [3, 1], [-1, -1])
sage: b = (1000, 1500, -400)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: AP = P.auxiliary_problem()
Return the auxiliary variable of self.
Note that the auxiliary variable may or may not be among decision_variables().
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1], [-1, -1])
sage: b = (1000, 1500, -400)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: P.auxiliary_variable()
x0
sage: P.decision_variables()
(x1, x2)
sage: AP = P.auxiliary_problem()
sage: AP.auxiliary_variable()
x0
sage: AP.decision_variables()
(x0, x1, x2)
Return the coordinate ring of self.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1], [-1, -1])
sage: b = (1000, 1500, -400)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: P.coordinate_ring()
Multivariate Polynomial Ring in x0, x1, x2, x3, x4, x5
over Rational Field
sage: P.base_ring()
Rational Field
sage: P.auxiliary_variable()
x0
sage: P.decision_variables()
(x1, x2)
sage: P.slack_variables()
(x3, x4, x5)
Construct a dictionary for self with given basic variables.
INPUT:
OUTPUT:
Note
This is a synonym for self.revised_dictionary(x_B).dictionary(), but basic variables are mandatory.
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.dictionary("x1", "x2")
sage: D.basic_variables()
(x1, x2)
Construct a feasible dictionary for self.
INPUT:
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1], [-1, -1])
sage: b = (1000, 1500, -400)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: AP = P.auxiliary_problem()
sage: D = AP.initial_dictionary()
sage: D.enter(0)
sage: D.leave(5)
sage: D.update()
sage: D.enter(1)
sage: D.leave(0)
sage: D.update()
sage: D.is_optimal()
True
sage: D.objective_value()
0
sage: D.basic_solution()
(0, 400, 0)
sage: D = P.feasible_dictionary(D)
sage: D.is_optimal()
False
sage: D.is_feasible()
True
sage: D.objective_value()
4000
sage: D.basic_solution()
(400, 0)
Return the final dictionary of the simplex method applied to self.
See run_simplex_method() for the description of possibilities.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.final_dictionary()
sage: D.is_optimal()
True
TESTS:
sage: P.final_dictionary() is P.final_dictionary()
False
Return the final dictionary of the revised simplex method applied to self.
See run_revised_simplex_method() for the description of possibilities.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.final_revised_dictionary()
sage: D.is_optimal()
True
TESTS:
sage: P.final_revised_dictionary() is P.final_revised_dictionary()
False
Construct the initial dictionary of self.
The initial dictionary “defines” slack_variables() in terms of the decision_variables(), i.e. it has slack variables as basic ones.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.initial_dictionary()
Inject variables of self into scope.
INPUT:
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: P.inject_variables()
Defining x0, x1, x2, x3, x4
sage: 3*x1 + x2
x2 + 3*x1
Construct a revised dictionary for self.
INPUT:
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.revised_dictionary("x1", "x2")
sage: D.basic_variables()
(x1, x2)
If basic variables are not given the initial dictionary is constructed:
sage: P.revised_dictionary().basic_variables()
(x3, x4)
sage: P.initial_dictionary().basic_variables()
(x3, x4)
Unless it is infeasible, in which case a feasible dictionary for the auxiliary problem is constructed:
sage: A = ([1, 1], [3, 1], [-1,-1])
sage: b = (1000, 1500, -400)
sage: P = LPProblemStandardForm(A, b, c)
sage: P.initial_dictionary().is_feasible()
False
sage: P.revised_dictionary().basic_variables()
(x3, x4, x0)
Apply the revised simplex method to solve self and show the steps.
OUTPUT:
Note
You can access the final_revised_dictionary(), which can be one of the following:
EXAMPLES:
sage: A = ([1, 1], [3, 1], [-1, -1])
sage: b = (1000, 1500, -400)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: P.run_revised_simplex_method()
\renewcommand{\arraystretch}{1.500000}
\begin{array}{l}
...
\text{Entering: $x_{1}$. Leaving: $x_{0}$.}\\
...
\text{Entering: $x_{5}$. Leaving: $x_{4}$.}\\
...
\text{Entering: $x_{2}$. Leaving: $x_{3}$.}\\
...
\text{The optimal value: $6250$. An optimal solution: $\left(250,\,750\right)$.}
\end{array}
Apply the simplex method to solve self and show the steps.
OUTPUT:
Note
You can access the final_dictionary(), which can be one of the following:
EXAMPLES:
sage: A = ([1, 1], [3, 1], [-1, -1])
sage: b = (1000, 1500, -400)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: P.run_simplex_method() # not tested
You should use the typeset mode as the command above generates long
code:sage: print P.run_simplex_method()
\begin{gather*}
...
\text{The initial dictionary is infeasible, solving auxiliary problem.}\displaybreak[0]\\
...
\text{Entering: $x_{0}$. Leaving: $x_{5}$.}\displaybreak[0]\\
...
\text{Entering: $x_{1}$. Leaving: $x_{0}$.}\displaybreak[0]\\
...
\text{Back to the original problem.}\displaybreak[0]\\
...
\text{Entering: $x_{5}$. Leaving: $x_{4}$.}\displaybreak[0]\\
...
\text{Entering: $x_{2}$. Leaving: $x_{3}$.}\displaybreak[0]\\
...
\text{The optimal value: $6250$. An optimal solution: $\left(250,\,750\right)$.}
\end{gather*}
Return slack variables of self.
Slack variables are differences between the constant terms and left hand sides of the constraints.
If you want to give custom names to slack variables, you have to do so during construction of the problem.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: P.slack_variables()
(x3, x4)
sage: P = LPProblemStandardForm(A, b, c, ["C", "B"],
....: slack_variables=["L", "F"])
sage: P.slack_variables()
(L, F)
Bases: sage.numerical.interactive_simplex_method.LPAbstractDictionary
Construct a revised dictionary for an LP problem.
INPUT:
OUTPUT:
A revised dictionary encodes the same relations as a regular dictionary, but stores only what is “necessary to efficiently compute data for the simplex method”.
Let the original problem be
Let be the vector of decision_variables()
followed by the slack_variables().
Let
be the vector of objective_coefficients()
followed by zeroes for all slack variables.
Let
be the matrix of
constraint_coefficients()
augmented by the identity
matrix as columns corresponding to the slack variables. Then the problem
above can be written as
and any dictionary is a system of equations equivalent to
, but resolved for basic_variables()
in
terms of nonbasic_variables()
together with the expression for
the objective in terms of
. Let c_B() and c_N() be vectors
“splitting
into basic and non-basic parts”. Let B() and
A_N() be the splitting of
. Then the corresponding dictionary
is
where . To proceed with the simplex method, it is not
necessary to compute all entries of this dictionary. On the other hand, any
entry is easy to compute, if you know
, so we keep track of it
through the update steps.
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: from sage.numerical.interactive_simplex_method \
....: import LPRevisedDictionary
sage: D = LPRevisedDictionary(P, [1, 2])
sage: D.basic_variables()
(x1, x2)
sage: D
LP problem dictionary (use typeset mode to see details)
The same dictionary can be constructed through the problem:
sage: P.revised_dictionary(1, 2) == D
True
When this dictionary is typeset, you will see two tables like these ones:
More details will be shown if entering and leaving variables are set, but in
any case the top table shows and a few extra columns, while the
bottom one shows several rows: these are related to columns and rows of
dictionary entries.
Return the column of constraint coefficients corresponding to v.
INPUT:
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.revised_dictionary()
sage: D.A(1)
(1, 3)
sage: D.A(0)
(-1, -1)
sage: D.A("x3")
(1, 0)
Return the matrix, constraint coefficients of
non-basic variables.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.revised_dictionary()
sage: D.A_N()
[1 1]
[3 1]
Return the matrix, i.e. constraint coefficients of
basic variables.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.revised_dictionary(1, 2)
sage: D.B()
[1 1]
[3 1]
Return the inverse of the B() matrix.
This inverse matrix is stored and computed during dictionary update in a more efficient way than generic inversion.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.revised_dictionary(1, 2)
sage: D.B_inverse()
[-1/2 1/2]
[ 3/2 -1/2]
Return the eta matrix between self and the next dictionary.
OUTPUT:
If is the current matrix
and
is the
matrix of the next dictionary (after the update step), then
.
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.revised_dictionary()
sage: D.enter(1)
sage: D.leave(4)
sage: D.E()
[1 1]
[0 3]
Return the inverse of the matrix E().
This inverse matrix is computed in a more efficient way than generic inversion.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.revised_dictionary()
sage: D.enter(1)
sage: D.leave(4)
sage: D.E_inverse()
[ 1 -1/3]
[ 0 1/3]
Return the basic indices of self.
Note
Basic indices are indices of basic_variables() in the list of generators of the coordinate_ring() of the problem() of self, they may not coincide with the indices of variables which are parts of their names. (They will for the default indexed names.)
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.revised_dictionary()
sage: D.basic_indices()
[3, 4]
Return the basic variables of self.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.revised_dictionary()
sage: D.basic_variables()
(x3, x4)
Return the vector, objective coefficients of basic variables.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.revised_dictionary(1, 2)
sage: D.c_B()
(10, 5)
Return the vector, objective coefficients of non-basic variables.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.revised_dictionary()
sage: D.c_N()
(10, 5)
Return constant terms in the relations of self.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.revised_dictionary()
sage: D.constant_terms()
(1000, 1500)
Return a regular LP dictionary matching self.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1], [-1, -1])
sage: b = (1000, 1500, -400)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.revised_dictionary()
sage: D.dictionary()
LP problem dictionary (use typeset mode to see details)
Return coefficients of the entering variable.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.revised_dictionary()
sage: D.enter(1)
sage: D.entering_coefficients()
(1, 3)
Return coefficients of the leaving variable.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.revised_dictionary(2, 3)
sage: D.leave(3)
sage: D.leaving_coefficients()
(-2, -1)
Return the non-basic indices of self.
Note
Non-basic indices are indices of nonbasic_variables() in the list of generators of the coordinate_ring() of the problem() of self, they may not coincide with the indices of variables which are parts of their names. (They will for the default indexed names.)
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.revised_dictionary()
sage: D.nonbasic_indices()
[1, 2]
Return non-basic variables of self.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.revised_dictionary()
sage: D.nonbasic_variables()
(x1, x2)
Return coefficients of the objective of self.
OUTPUT:
These are coefficients of non-basic variables when basic variables are eliminated.
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.revised_dictionary()
sage: D.objective_coefficients()
(10, 5)
Return the value of the objective at the basic solution of self.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.revised_dictionary()
sage: D.objective_value()
0
Return the original problem.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.revised_dictionary()
sage: D.problem() is P
True
Update self using previously set entering and leaving variables.
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.revised_dictionary()
sage: D.objective_value()
0
sage: D.enter("x1")
sage: D.leave("x4")
sage: D.update()
sage: D.objective_value()
5000
Return the basic variables of self.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.revised_dictionary()
sage: D.basic_variables()
(x3, x4)
Return non-basic variables of self.
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.revised_dictionary()
sage: D.nonbasic_variables()
(x1, x2)
Return the vector, the product of c_B() and
B_inverse().
OUTPUT:
EXAMPLES:
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = LPProblemStandardForm(A, b, c)
sage: D = P.revised_dictionary()
sage: D.y()
(0, 0)
Construct a random dictionary.
INPUT:
OUTPUT:
EXAMPLES:
sage: from sage.numerical.interactive_simplex_method \
....: import random_dictionary
sage: random_dictionary(3, 4)
LP problem dictionary (use typeset mode to see details)
Interpret v as a variable of R.
INPUT:
OUTPUT:
EXAMPLES:
sage: from sage.numerical.interactive_simplex_method \
....: import variable
sage: R = PolynomialRing(QQ, "x3, y5, x5, y")
sage: R.inject_variables()
Defining x3, y5, x5, y
sage: variable(R, "x3")
x3
sage: variable(R, x3)
x3
sage: variable(R, 3)
x3
sage: variable(R, 0)
Traceback (most recent call last):
...
ValueError: there is no variable with the given index
sage: variable(R, 5)
Traceback (most recent call last):
...
ValueError: the given index is ambiguous
sage: variable(R, 2 * x3)
Traceback (most recent call last):
...
ValueError: cannot interpret given data as a variable
sage: variable(R, "z")
Traceback (most recent call last):
...
ValueError: cannot interpret given data as a variable