Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
r""" Interactive Simplex Method
This module, meant for **educational purposes only**, supports learning and exploring of the simplex method.
Do you want to solve Linear Programs efficiently? use :class:`MixedIntegerLinearProgram` instead.
The methods implemented here allow solving Linear Programming Problems (LPPs) in a number of ways, may require explicit (and correct!) description of steps and are likely to be much slower than "regular" LP solvers. 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:
- Andrey Novoseltsev (2013-03-16): initial version.
- Matthias Koeppe, Peijun Xiao (2015-07-05): allow different output styles.
EXAMPLES:
Most of the module functionality is demonstrated on the following problem.
.. admonition:: Corn & Barley
A farmer has 1000 acres available to grow corn and barley. Corn has a net profit of 10 dollars per acre while barley has a net profit of 5 dollars per acre. The farmer has 1500 kg of fertilizer available with 3 kg per acre needed for corn and 1 kg per acre needed for barley. The farmer wants to maximize profit. (Sometimes we also add one more constraint to make the initial dictionary infeasible: the farmer has to use at least 40% of the available land.)
Using variables `C` and `B` 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 = InteractiveLPProblem(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
.. MATH::
\begin{array}{l} \begin{array}{lcrcrcl} \max \mspace{-6mu}&\mspace{-6mu} \mspace{-6mu}&\mspace{-6mu} 10 C \mspace{-6mu}&\mspace{-6mu} + \mspace{-6mu}&\mspace{-6mu} 5 B \mspace{-6mu} \\ \mspace{-6mu}&\mspace{-6mu} \mspace{-6mu}&\mspace{-6mu} C \mspace{-6mu}&\mspace{-6mu} + \mspace{-6mu}&\mspace{-6mu} B \mspace{-6mu}&\mspace{-6mu} \leq \mspace{-6mu}&\mspace{-6mu} 1000 \\ \mspace{-6mu}&\mspace{-6mu} \mspace{-6mu}&\mspace{-6mu} 3 C \mspace{-6mu}&\mspace{-6mu} + \mspace{-6mu}&\mspace{-6mu} B \mspace{-6mu}&\mspace{-6mu} \leq \mspace{-6mu}&\mspace{-6mu} 1500 \\ \end{array} \\ C, B \geq 0 \end{array}
Since it has only two variables, we can solve it graphically::
sage: P.plot() Graphics object consisting of 19 graphics primitives
The simplex method can be applied only to :class:`problems in standard form <InteractiveLPProblemStandardForm>`, which can be created either directly ::
sage: InteractiveLPProblemStandardForm(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() \begin{equation*} ... The optimal value: $6250$. An optimal solution: $\left(250,\,750\right)$.
(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
.. MATH::
\renewcommand{\arraystretch}{1.5} \begin{array}{|rcrcrcr|} \hline x_{3} \mspace{-6mu}&\mspace{-6mu} = \mspace{-6mu}&\mspace{-6mu} 1000 \mspace{-6mu}&\mspace{-6mu} - \mspace{-6mu}&\mspace{-6mu} C \mspace{-6mu}&\mspace{-6mu} - \mspace{-6mu}&\mspace{-6mu} B\\ x_{4} \mspace{-6mu}&\mspace{-6mu} = \mspace{-6mu}&\mspace{-6mu} 1500 \mspace{-6mu}&\mspace{-6mu} - \mspace{-6mu}&\mspace{-6mu} 3 C \mspace{-6mu}&\mspace{-6mu} - \mspace{-6mu}&\mspace{-6mu} B\\ \hline z \mspace{-6mu}&\mspace{-6mu} = \mspace{-6mu}&\mspace{-6mu} 0 \mspace{-6mu}&\mspace{-6mu} + \mspace{-6mu}&\mspace{-6mu} 10 C \mspace{-6mu}&\mspace{-6mu} + \mspace{-6mu}&\mspace{-6mu} 5 B\\ \hline \end{array}
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 :meth:`feasible sets <InteractiveLPProblem.feasible_set>` and :meth:`final dictionaries <InteractiveLPProblemStandardForm.final_dictionary>` of problems, work with :class:`revised dictionaries <LPRevisedDictionary>`, and use the dual simplex method!
.. NOTE::
Currently this does not have a display format for the terminal.
Classes and functions --------------------- """
#***************************************************************************** # Copyright (C) 2013 Andrey Novoseltsev <novoselt@gmail.com> # # Distributed under the terms of the GNU General Public License (GPL) # as published by the Free Software Foundation; either version 2 of # the License, or (at your option) any later version. # http://www.gnu.org/licenses/ #*****************************************************************************
identity_matrix, matrix, random_matrix) cached_function, cached_method, latex, randint, random)
# We produce rather complicated LaTeX code which needs some tweaks to be # displayed nicely by MathJax, which make it look slightly different from real # LaTeX. We use our own variable as it may be convenient to override it. # Hopefully, some day there will be no need in it at all and only "if" parts # will have to be left.
r""" Return ``lines`` assembled in a left-justified array.
INPUT:
- ``lines`` -- a list of strings suitable for math mode typesetting
- ``stretch`` -- (default: None) if given, a command setting ``\arraystretch`` to this value will be added before the array
OUTPUT:
- a :class:`LatexExpr`
EXAMPLES::
sage: from sage.numerical.interactive_simplex_method \ ....: import _assemble_arrayl sage: lines = ["1 + 1", "2"] sage: print(_assemble_arrayl(lines)) %notruncate \begin{array}{l} 1 + 1\\ 2 \end{array} sage: print(_assemble_arrayl(lines, 1.5)) %notruncate \renewcommand{\arraystretch}{1.500000} \begin{array}{l} 1 + 1\\ 2 \end{array} """ # Even simple LP problems tend to generate long output, so we prohibit # truncation in the notebook cells and hope for the best! ("" if stretch is None else "\\renewcommand{\\arraystretch}{%f}\n" % stretch) + "\\begin{array}{l}\n" + "\\\\\n".join(lines) + "\n\\end{array}")
separator=None, head=None, tail=None, drop_plus=True, allow_empty=False): r""" Generate LaTeX code for a linear function.
This function is intended for internal use by LaTeX methods of LP problems and their dictionaries.
INPUT:
- ``coefficients`` -- a list of coefficients
- ``variables`` -- a list of variables
- ``separator`` -- (default: ``"&"`` with some extra space adjustment) a string to be inserted between elements of the generated expression
- ``head`` -- either ``None`` (default) or a list of entries to be added to the beginning of the output
- ``tail`` -- either ``None`` (default) or a list of entries to be added to the end of the output
- ``drop_plus`` -- (default: ``True``) whether to drop the leading plus sign or not
- ``allow_empty`` -- (default: ``False``) whether to allow empty output or produce at least "0"
OUTPUT:
- A string joining ``head``, each sign and coefficient-variable product, and ``tail`` using ``separator``. Strings in ``head`` and ``tail`` are used as is except for "<=", "==", and ">=", which are replaced by LaTeX commands. Other elements in ``head`` in ``tail`` are processed by :func:`latex`.
TESTS::
sage: from sage.numerical.interactive_simplex_method import \ ....: _latex_product sage: var("x, y") (x, y) sage: print(_latex_product([-1, 3], [x, y])) - \mspace{-6mu}&\mspace{-6mu} x \mspace{-6mu}&\mspace{-6mu} + \mspace{-6mu}&\mspace{-6mu} 3 y """ else: t = r"\left( " + t + r" \right)" entries[-1] = "0" e = latex_relations[e] separator = " & " else:
def variable(R, v): r""" Interpret ``v`` as a variable of ``R``.
INPUT:
- ``R`` -- a polynomial ring
- ``v`` -- a variable of ``R`` or convertible into ``R``, a string with the name of a variable of ``R`` or an index of a variable in ``R``
OUTPUT:
- a variable of ``R``
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 """ else:
"UAlberta": { "primal decision": "x", "primal slack": "x", "dual decision": "y", "dual slack": "y", "primal objective": "z", "dual objective": "z", "auxiliary objective": "w", }, "Vanderbei": { "primal decision": "x", "primal slack": "w", "dual decision": "y", "dual slack": "z", "primal objective": "zeta", "dual objective": "xi", "auxiliary objective": "xi", }, }
r""" Return default variable name for the current :func:`style`.
INPUT:
- ``variable`` - a string describing requested name
OUTPUT:
- a string with the requested name for current style
EXAMPLES::
sage: sage.numerical.interactive_simplex_method.default_variable_name("primal slack") 'x' sage: sage.numerical.interactive_simplex_method.style('Vanderbei') 'Vanderbei' sage: sage.numerical.interactive_simplex_method.default_variable_name("primal slack") 'w' sage: sage.numerical.interactive_simplex_method.style('UAlberta') 'UAlberta' """
r""" Set or get the current style of problems and dictionaries.
INPUT:
- ``new_style`` -- a string or ``None`` (default)
OUTPUT:
- a string with current style (same as ``new_style`` if it was given)
If the input is not recognized as a valid style, a ``ValueError`` exception is raised.
Currently supported styles are:
- 'UAlberta' (default): Follows the style used in the Math 373 course on Mathematical Programming and Optimization at the University of Alberta, Edmonton, Canada; based on Chvatal's book.
- Objective functions of dictionaries are printed at the bottom.
Variable names default to
- `z` for primal objective
- `z` for dual objective
- `w` for auxiliary objective
- `x_1, x_2, \dots, x_n` for primal decision variables
- `x_{n+1}, x_{n+2}, \dots, x_{n+m}` for primal slack variables
- `y_1, y_2, \dots, y_m` for dual decision variables
- `y_{m+1}, y_{m+2}, \dots, y_{m+n}` for dual slack variables
- 'Vanderbei': Follows the style of Robert Vanderbei's textbook, Linear Programming -- Foundations and Extensions.
- Objective functions of dictionaries are printed at the top.
Variable names default to
- `zeta` for primal objective
- `xi` for dual objective
- `xi` for auxiliary objective
- `x_1, x_2, \dots, x_n` for primal decision variables
- `w_1, w_2, \dots, w_m` for primal slack variables
- `y_1, y_2, \dots, y_m` for dual decision variables
- `z_1, z_2, \dots, z_n` for dual slack variables
EXAMPLES::
sage: sage.numerical.interactive_simplex_method.style() 'UAlberta' sage: sage.numerical.interactive_simplex_method.style('Vanderbei') 'Vanderbei' sage: sage.numerical.interactive_simplex_method.style('Doesntexist') Traceback (most recent call last): ... ValueError: Style must be one of: UAlberta, Vanderbei sage: sage.numerical.interactive_simplex_method.style('UAlberta') 'UAlberta' """ global current_style ", ".join(available_styles.keys())))
r""" Construct an LP (Linear Programming) problem.
.. NOTE::
This class is for **educational purposes only**: if you want to solve Linear Programs efficiently, use :class:`MixedIntegerLinearProgram` instead.
This class supports LP problems with "variables on the left" constraints.
INPUT:
- ``A`` -- a matrix of constraint coefficients
- ``b`` -- a vector of constraint constant terms
- ``c`` -- a vector of objective coefficients
- ``x`` -- (default: ``"x"``) a vector of decision variables or a string giving the base name
- ``constraint_type`` -- (default: ``"<="``) a string specifying constraint type(s): either ``"<="``, ``">="``, ``"=="``, or a list of them
- ``variable_type`` -- (default: ``""``) a string specifying variable type(s): either ``">="``, ``"<="``, ``""`` (the empty string), or a list of them, corresponding, respectively, to non-negative, non-positive, and free variables
- ``problem_type`` -- (default: ``"max"``) a string specifying the problem type: ``"max"``, ``"min"``, ``"-max"``, or ``"-min"``
- ``base_ring`` -- (default: the fraction field of a common ring for all input coefficients) a field to which all input coefficients will be converted
- ``is_primal`` -- (default: ``True``) whether this problem is primal or dual: each problem is of course dual to its own dual, this flag is mostly for internal use and affects default variable names only
- ``objective_constant_term`` -- (default: 0) a constant term of the objective
EXAMPLES:
We will construct the following problem:
.. MATH::
\begin{array}{l} \begin{array}{lcrcrcl} \max \mspace{-6mu}&\mspace{-6mu} \mspace{-6mu}&\mspace{-6mu} 10 C \mspace{-6mu}&\mspace{-6mu} + \mspace{-6mu}&\mspace{-6mu} 5 B \mspace{-6mu} \\ \mspace{-6mu}&\mspace{-6mu} \mspace{-6mu}&\mspace{-6mu} C \mspace{-6mu}&\mspace{-6mu} + \mspace{-6mu}&\mspace{-6mu} B \mspace{-6mu}&\mspace{-6mu} \leq \mspace{-6mu}&\mspace{-6mu} 1000 \\ \mspace{-6mu}&\mspace{-6mu} \mspace{-6mu}&\mspace{-6mu} 3 C \mspace{-6mu}&\mspace{-6mu} + \mspace{-6mu}&\mspace{-6mu} B \mspace{-6mu}&\mspace{-6mu} \leq \mspace{-6mu}&\mspace{-6mu} 1500 \\ \end{array} \\ C, B \geq 0 \end{array}
::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblem(A, b, c, ["C", "B"], variable_type=">=")
Same problem, but more explicitly::
sage: P = InteractiveLPProblem(A, b, c, ["C", "B"], ....: constraint_type="<=", variable_type=">=")
Even more explicitly::
sage: P = InteractiveLPProblem(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. """
constraint_type="<=", variable_type="", problem_type="max", base_ring=None, is_primal=True, objective_constant_term=0): r""" See :class:`InteractiveLPProblem` for documentation.
TESTS::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblem(A, b, c, ["C", "B"], variable_type=">=") sage: TestSuite(P).run() """ raise ValueError("A and b have incompatible dimensions") raise ValueError("A and c have incompatible dimensions") else: raise ValueError("A and x have incompatible dimensions")
else: raise ValueError("wrong number of constraint types")
else: raise ValueError("unknown variable type") raise ValueError("wrong number of variable types")
else: raise ValueError("unknown problem type")
r""" Check if two LP problems are equal.
INPUT:
- ``other`` -- anything
OUTPUT:
- ``True`` if ``other`` is an :class:`InteractiveLPProblem` with all details the same as ``self``, ``False`` otherwise.
TESTS::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblem(A, b, c, ["C", "B"], variable_type=">=") sage: P2 = InteractiveLPProblem(A, b, c, ["C", "B"], variable_type=">=") sage: P == P2 True sage: P3 = InteractiveLPProblem(A, c, b, ["C", "B"], variable_type=">=") sage: P == P3 False """ self.Abcx() == other.Abcx() and self._constant_term == other._constant_term and self._problem_type == other._problem_type and self._is_negative == other._is_negative and self._constraint_types == other._constraint_types and self._variable_types == other._variable_types)
r""" Return a LaTeX representation of ``self``.
OUTPUT:
- a string
TESTS::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblem(A, b, c, ["C", "B"], variable_type=">=") sage: print(P._latex_()) \begin{array}{l} \begin{array}{lcrcrcl} \max \mspace{-6mu}&\mspace{-6mu} \mspace{-6mu}&\mspace{-6mu} 10 C \mspace{-6mu}&\mspace{-6mu} + \mspace{-6mu}&\mspace{-6mu} 5 B \mspace{-6mu}&\mspace{-6mu} \mspace{-6mu}&\mspace{-6mu} \\ \mspace{-6mu}&\mspace{-6mu} \mspace{-6mu}&\mspace{-6mu} C \mspace{-6mu}&\mspace{-6mu} + \mspace{-6mu}&\mspace{-6mu} B \mspace{-6mu}&\mspace{-6mu} \leq \mspace{-6mu}&\mspace{-6mu} 1000 \\ \mspace{-6mu}&\mspace{-6mu} \mspace{-6mu}&\mspace{-6mu} 3 C \mspace{-6mu}&\mspace{-6mu} + \mspace{-6mu}&\mspace{-6mu} B \mspace{-6mu}&\mspace{-6mu} \leq \mspace{-6mu}&\mspace{-6mu} 1500 \\ \end{array} \\ C, B \geq 0 \end{array} """ lines[-1] += r" \setlength{\arraycolsep}{0.125em}" self._problem_type)] elif latex(self._constant_term).strip().startswith("-"): tail = ["-", - self._constant_term] else: tail = ["+", self._constant_term] r" \\") else: lines.append(r",\ ".join(r"{} {} 0".format( latex(xj), r"\geq" if vt == ">=" else r"\leq") for xj, vt in zip(x, self._variable_types) if vt))
r""" Return a string representation of ``self``.
OUTPUT:
- a string
TESTS::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblem(A, b, c, ["C", "B"], variable_type=">=") sage: print(P._repr_()) LP problem (use typeset mode to see details) """
r""" Return ``x`` as a normalized solution of ``self``.
INPUT:
- ``x`` -- anything that can be interpreted as a solution of this problem, e.g. a vector or a list of correct length or a single element list with such a vector
OUTPUT:
- ``x`` as a vector
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblem(A, b, c, variable_type=">=") sage: P._solution([100, 200]) (100, 200) sage: P._solution([[100, 200]]) (100, 200) sage: P._solution([1000]) Traceback (most recent call last): ... TypeError: given input is not a solution for this problem """
def _solve(self): r""" Return an optimal solution and the optimal value of ``self``.
OUTPUT:
- A pair consisting of a vector and a number. If the problem is infeasible, both components are ``None``. If the problem is unbounded, the first component is ``None`` and the second is `\pm \infty`.
This function uses "brute force" solution technique of evaluating the objective at all vertices of the feasible set and taking into account its rays and lines.
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblem(A, b, c, ["C", "B"], variable_type=">=") sage: P._solve() ((250, 750), 6250) """ M, S = 0, F.vertices()[0] any(c * vector(R, line) != 0 for line in F.lines()): M, S = Infinity, None else: any(c * vector(R, line) != 0 for line in F.lines()): M, S = -Infinity, None else:
r""" Return `A`, `b`, `c`, and `x` of ``self`` as a tuple.
OUTPUT:
- a tuple
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblem(A, b, c, ["C", "B"], variable_type=">=") sage: P.Abcx() ( [1 1] [3 1], (1000, 1500), (10, 5), (C, B) ) """
r""" Return a new LP problem by adding a constraint to``self``.
INPUT:
- ``coefficients`` -- coefficients of the new constraint
- ``constant_term`` -- a constant term of the new constraint
- ``constraint_type`` -- (default: ``"<="``) a string indicating the constraint type of the new constraint
OUTPUT:
- an :class:`LP problem <InteractiveLPProblem>`
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblem(A, b, c) sage: P1 = P.add_constraint(([2, 4]), 2000, "<=") sage: P1.Abcx() ( [1 1] [3 1] [2 4], (1000, 1500, 2000), (10, 5), (x1, x2) ) sage: P1.constraint_types() ('<=', '<=', '<=') sage: P.Abcx() ( [1 1] [3 1], (1000, 1500), (10, 5), (x1, x2) ) sage: P.constraint_types() ('<=', '<=') sage: P2 = P.add_constraint(([2, 4, 6]), 2000, "<=") Traceback (most recent call last): ... TypeError: number of columns must be the same, not 2 and 3 sage: P3 = P.add_constraint(([2, 4]), 2000, "<") Traceback (most recent call last): ... ValueError: unknown constraint type """ problem_type = "-" + self.problem_type() else: constraint_type=self._constraint_types + (constraint_type,), variable_type=self.variable_types(), problem_type=problem_type, base_ring=self.base_ring(), is_primal=self._is_primal, objective_constant_term=self.objective_constant_term())
r""" Return the base ring of ``self``.
.. NOTE::
The base ring of LP problems is always a field.
OUTPUT:
- a ring
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblem(A, b, c, ["C", "B"], variable_type=">=") sage: P.base_ring() Rational Field
sage: c = (10, 5.) sage: P = InteractiveLPProblem(A, b, c, ["C", "B"], variable_type=">=") sage: P.base_ring() Real Field with 53 bits of precision """
r""" Return constant terms of constraints of ``self``, i.e. `b`.
OUTPUT:
- a vector
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblem(A, b, c, ["C", "B"], variable_type=">=") sage: P.constant_terms() (1000, 1500) sage: P.b() (1000, 1500) """
r""" Return coefficients of constraints of ``self``, i.e. `A`.
OUTPUT:
- a matrix
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblem(A, b, c, ["C", "B"], variable_type=">=") sage: P.constraint_coefficients() [1 1] [3 1] sage: P.A() [1 1] [3 1] """
r""" Return a tuple listing the constraint types of all rows.
OUTPUT:
- a tuple of strings
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblem(A, b, c, ["C", "B"], variable_type=">=", constraint_type=["<=", "=="]) sage: P.constraint_types() ('<=', '==') """
r""" Return decision variables of ``self``, i.e. `x`.
OUTPUT:
- a vector
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblem(A, b, c, ["C", "B"], variable_type=">=") sage: P.decision_variables() (C, B) sage: P.x() (C, B) """
r""" Construct the dual LP problem for ``self``.
INPUT:
- ``y`` -- (default: depends on :func:`style`) a vector of dual decision variables or a string giving the base name
OUTPUT:
- an :class:`InteractiveLPProblem`
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblem(A, b, c, ["C", "B"], variable_type=">=") sage: DP = P.dual() sage: DP.b() == P.c() True sage: DP.dual(["C", "B"]) == P True
TESTS::
sage: DP.standard_form().objective_name() -z sage: sage.numerical.interactive_simplex_method.style("Vanderbei") 'Vanderbei' sage: P.dual().standard_form().objective_name() -xi sage: sage.numerical.interactive_simplex_method.style("UAlberta") 'UAlberta' sage: P.dual().standard_form().objective_name() -z """ "dual decision" if self.is_primal() else "primal decision") vt == "<=" and problem_type == "max"): vt == ">=" and problem_type == "max"): else: constraint_type.append("==") ct == "<=" and problem_type == "max"): variable_type.append("<=") ct == ">=" and problem_type == "max"): else: variable_type.append("") problem_type = "-" + problem_type constraint_type, variable_type, problem_type, is_primal=not self.is_primal(), objective_constant_term=self._constant_term)
def feasible_set(self): r""" Return the feasible set of ``self``.
OUTPUT:
- a :mod:`Polyhedron <sage.geometry.polyhedron.constructor>`
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblem(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 """ elif r == ">=": ieqs.append([-b] + list(a)) else: eqns.append([-b] + list(a)) else:
r""" Check if ``self`` is bounded.
OUTPUT:
- ``True`` is ``self`` is bounded, ``False`` otherwise
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblem(A, b, c, ["C", "B"], variable_type=">=") sage: P.is_bounded() True
Note that infeasible problems are always bounded::
sage: b = (-1000, 1500) sage: P = InteractiveLPProblem(A, b, c, variable_type=">=") sage: P.is_feasible() False sage: P.is_bounded() True """
r""" Check if ``self`` or given solution is feasible.
INPUT:
- (optional) anything that can be interpreted as a valid solution for this problem, i.e. a sequence of values for all decision variables
OUTPUT:
- ``True`` is this problem or given solution is feasible, ``False`` otherwise
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblem(A, b, c, variable_type=">=") sage: P.is_feasible() True sage: P.is_feasible(100, 200) True sage: P.is_feasible(1000, 200) False sage: P.is_feasible([1000, 200]) False sage: P.is_feasible(1000) Traceback (most recent call last): ... TypeError: given input is not a solution for this problem """
r""" Return `True` when the problem is of type ``"-max"`` or ``"-min"``.
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblem(A, b, c, ["C", "B"], variable_type=">=") sage: P.is_negative() False sage: P = InteractiveLPProblem(A, b, c, ["C", "B"], variable_type=">=", problem_type="-min") sage: P.is_negative() True """
r""" Check if we consider this problem to be primal or dual.
This distinction affects only some automatically chosen variable names.
OUTPUT:
- boolean
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblem(A, b, c, ["C", "B"], variable_type=">=") sage: P.is_primal() True sage: P.dual().is_primal() False """
r""" Check if given solution is feasible.
INPUT:
- anything that can be interpreted as a valid solution for this problem, i.e. a sequence of values for all decision variables
OUTPUT:
- ``True`` is the given solution is optimal, ``False`` otherwise
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (15, 5) sage: P = InteractiveLPProblem(A, b, c, variable_type=">=") sage: P.is_optimal(100, 200) False sage: P.is_optimal(500, 0) True sage: P.is_optimal(499, 3) True sage: P.is_optimal(501, -3) False """ self.is_feasible(*x))
r""" Return the number of constraints of ``self``, i.e. `m`.
OUTPUT:
- an integer
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblem(A, b, c, ["C", "B"], variable_type=">=") sage: P.n_constraints() 2 sage: P.m() 2 """
r""" Return the number of decision variables of ``self``, i.e. `n`.
OUTPUT:
- an integer
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblem(A, b, c, ["C", "B"], variable_type=">=") sage: P.n_variables() 2 sage: P.n() 2 """
r""" Return coefficients of the objective of ``self``, i.e. `c`.
OUTPUT:
- a vector
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblem(A, b, c, ["C", "B"], variable_type=">=") sage: P.objective_coefficients() (10, 5) sage: P.c() (10, 5) """
r""" Return the constant term of the objective.
OUTPUT:
- a number
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblem(A, b, c, ["C", "B"], variable_type=">=") sage: P.objective_constant_term() 0 sage: P.optimal_value() 6250 sage: P = InteractiveLPProblem(A, b, c, ["C", "B"], ....: variable_type=">=", objective_constant_term=-1250) sage: P.objective_constant_term() -1250 sage: P.optimal_value() 5000 """
r""" Return the value of the objective on the given solution.
INPUT:
- anything that can be interpreted as a valid solution for this problem, i.e. a sequence of values for all decision variables
OUTPUT:
- the value of the objective on the given solution taking into account :meth:`objective_constant_term` and :meth:`is_negative`
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblem(A, b, c, variable_type=">=") sage: P.objective_value(100, 200) 2000 """
r""" Return **an** optimal solution of ``self``.
OUTPUT:
- a vector or ``None`` if there are no optimal solutions
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblem(A, b, c, ["C", "B"], variable_type=">=") sage: P.optimal_solution() (250, 750) """
r""" Return the optimal value for ``self``.
OUTPUT:
- a number if the problem is bounded, `\pm \infty` if it is unbounded, or ``None`` if it is infeasible
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblem(A, b, c, ["C", "B"], variable_type=">=") sage: P.optimal_value() 6250 """
r""" Return a plot for solving ``self`` graphically.
INPUT:
- ``xmin``, ``xmax``, ``ymin``, ``ymax`` -- bounds for the axes, if not given, an attempt will be made to pick reasonable values
- ``alpha`` -- (default: 0.2) determines how opaque are shadows
OUTPUT:
- a plot
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 = InteractiveLPProblem(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: InteractiveLPProblem(A, b, (0, 0), ["C", "B"], variable_type=">=").plot() Graphics object consisting of 8 graphics primitives """ else [xmin + (xmax-xmin)/2, ymin + (ymax-ymin)/2]) (ymax, 0, -1), (- ymin, 0, 1)] thickness=2) else: linestyle="--")
alpha=0.2): r""" Return a plot of the feasible set of ``self``.
INPUT:
- ``xmin``, ``xmax``, ``ymin``, ``ymax`` -- bounds for the axes, if not given, an attempt will be made to pick reasonable values
- ``alpha`` -- (default: 0.2) determines how opaque are shadows
OUTPUT:
- a plot
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 :meth:`feasible_set` is not empty and at least part of it is in the given boundaries, it will be shaded gray and `F` will be placed in its middle.
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblem(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() """ raise ValueError("only problems with 2 variables can be plotted") # Either we use QQ or crash (ymax, 0, -1), (- ymin, 0, 1)] b, colors[:-2]): continue elif ri == ">=": ieqs = [[-bi] + list(Ai), [bi+pad*Ai.norm().n()] + list(-Ai)] else: continue # Same for variables, but no legend colors[-2:]): continue ieqs = [[0] + list(-ni), [pad] + list(ni)] else: continue fontsize=20, color="black", zorder=5) shadow=True)
r""" Return the problem type.
Needs to be used together with ``is_negative``.
OUTPUT:
- a string, one of ``"max"``, ``"min"``.
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblem(A, b, c, ["C", "B"], variable_type=">=") sage: P.problem_type() 'max' sage: P = InteractiveLPProblem(A, b, c, ["C", "B"], variable_type=">=", problem_type="-min") sage: P.problem_type() 'min' """
r""" Construct the LP problem in standard form equivalent to ``self``.
INPUT:
- ``transformation`` -- (default: ``False``) if ``True``, a map converting solutions of the problem in standard form to the original one will be returned as well
- you can pass (as keywords only) ``slack_variables``, ``auxiliary_variable``,``objective_name`` to the constructor of :class:`InteractiveLPProblemStandardForm`
OUTPUT:
- an :class:`InteractiveLPProblemStandardForm` by itself or a tuple with variable transformation as the second component
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblem(A, b, c, variable_type=">=") sage: DP = P.dual() sage: DPSF = DP.standard_form() sage: DPSF.b() (-10, -5) sage: DPSF.slack_variables() (y3, y4) sage: DPSF = DP.standard_form(slack_variables=["L", "F"]) sage: DPSF.slack_variables() (L, F) sage: DPSF, f = DP.standard_form(True) sage: f Vector space morphism represented by the matrix: [1 0] [0 1] Domain: Vector space of dimension 2 over Rational Field Codomain: Vector space of dimension 2 over Rational Field
A more complicated transformation map::
sage: P = InteractiveLPProblem(A, b, c, variable_type=["<=", ""], ....: objective_constant_term=42) sage: PSF, f = P.standard_form(True) sage: f Vector space morphism represented by the matrix: [-1 0] [ 0 1] [ 0 -1] Domain: Vector space of dimension 3 over Rational Field Codomain: Vector space of dimension 2 over Rational Field sage: PSF.optimal_solution() (0, 1000, 0) sage: P.optimal_solution() (0, 1000) sage: P.is_optimal(PSF.optimal_solution()) Traceback (most recent call last): ... TypeError: given input is not a solution for this problem sage: P.is_optimal(f(PSF.optimal_solution())) True sage: PSF.optimal_value() 5042 sage: P.optimal_value() 5042
TESTS:
Above also works for the equivalent minimization problem::
sage: c = (-10, -5) sage: P = InteractiveLPProblem(A, b, c, variable_type=["<=", ""], ....: objective_constant_term=-42, ....: problem_type="min") sage: PSF, f = P.standard_form(True) sage: PSF.optimal_solution() (0, 1000, 0) sage: P.optimal_solution() (0, 1000) sage: PSF.optimal_value() -5042 sage: P.optimal_value() -5042
""" self._variable_types, A.columns(), c, x, f):
"primal objective" if self.is_primal() else "dual objective")))
r""" Return a tuple listing the variable types of all decision variables.
OUTPUT:
- a tuple of strings
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblem(A, b, c, ["C", "B"], variable_type=[">=", ""]) sage: P.variable_types() ('>=', '') """
# Aliases for the standard notation
r""" Construct an LP (Linear Programming) problem in standard form.
.. NOTE::
This class is for **educational purposes only**: if you want to solve Linear Programs efficiently, use :class:`MixedIntegerLinearProgram` instead.
The used standard form is:
.. MATH::
\begin{array}{l} \pm \max cx \\ Ax \leq b \\ x \geq 0 \end{array}
INPUT:
- ``A`` -- a matrix of constraint coefficients
- ``b`` -- a vector of constraint constant terms
- ``c`` -- a vector of objective coefficients
- ``x`` -- (default: ``"x"``) a vector of decision variables or a string the base name giving
- ``problem_type`` -- (default: ``"max"``) a string specifying the problem type: either ``"max"`` or ``"-max"``
- ``slack_variables`` -- (default: depends on :func:`style`) a vector of slack variables or a string giving the base name
- ``auxiliary_variable`` -- (default: same as ``x`` parameter with adjoined ``"0"`` if it was given as a string, otherwise ``"x0"``) the auxiliary name, expected to be the same as the first decision variable for auxiliary problems
- ``base_ring`` -- (default: the fraction field of a common ring for all input coefficients) a field to which all input coefficients will be converted
- ``is_primal`` -- (default: ``True``) whether this problem is primal or dual: each problem is of course dual to its own dual, this flag is mostly for internal use and affects default variable names only
- ``objective_name`` -- a string or a symbolic expression for the objective used in dictionaries, default depends on :func:`style`
- ``objective_constant_term`` -- (default: 0) a constant term of the objective
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c)
Unlike :class:`InteractiveLPProblem`, 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) """
slack_variables=None, auxiliary_variable=None, base_ring=None, is_primal=True, objective_name=None, objective_constant_term=0): r""" See :class:`InteractiveLPProblemStandardForm` for documentation.
TESTS::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: TestSuite(P).run() """ raise ValueError("problems in standard form must be of (negative) " "maximization type") A, b, c, x, problem_type=problem_type, constraint_type="<=", variable_type=">=", base_ring=base_ring, is_primal=is_primal, objective_constant_term=objective_constant_term) "primal slack" if is_primal else "dual slack") for i in indices] else: raise ValueError("wrong number of slack variables") "primal objective" if is_primal else "dual objective")
r""" Return a new LP problem by adding a constraint to``self``.
INPUT:
- ``coefficients`` -- coefficients of the new constraint
- ``constant_term`` -- a constant term of the new constraint
- ``slack_variable`` -- (default: depends on :func:`style`) a string giving the name of the slack variable of the new constraint
OUTPUT:
- an :class:`LP problem in standard form <InteractiveLPProblemStandardForm>`
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: P.Abcx() ( [1 1] [3 1], (1000, 1500), (10, 5), (x1, x2) ) sage: P.slack_variables() (x3, x4) sage: P1 = P.add_constraint(([2, 4]), 2000) sage: P1.Abcx() ( [1 1] [3 1] [2 4], (1000, 1500, 2000), (10, 5), (x1, x2) ) sage: P1.slack_variables() (x3, x4, x5) sage: P2 = P.add_constraint(([2, 4]), 2000, slack_variable='c') sage: P2.slack_variables() (x3, x4, c) sage: P3 = P.add_constraint(([2, 4, 6]), 2000) Traceback (most recent call last): ... TypeError: number of columns must be the same, not 2 and 3 """ problem_type = "-" + self.problem_type() else: "primal slack" if self._is_primal else "dual slack") index = self.m() + 1 A, b, c, x, problem_type=problem_type, slack_variables=tuple(self.slack_variables()) + (slack_variable,), auxiliary_variable=self.auxiliary_variable(), base_ring=self.base_ring(), is_primal=self._is_primal, objective_name=self._objective_name, objective_constant_term=self.objective_constant_term())
r""" Construct the auxiliary problem for ``self``.
INPUT:
- ``objective_name`` -- a string or a symbolic expression for the objective used in dictionaries, default depends on :func:`style`
OUTPUT:
- an :class:`LP problem in standard form <InteractiveLPProblemStandardForm>`
The auxiliary problem with the auxiliary variable `x_0` is
.. MATH::
\begin{array}{l} \max - x_0 \\ - x_0 + A_i x \leq b_i \text{ for all } i \\ x \geq 0 \end{array}\ .
Such problems are used when the :meth:`initial_dictionary` is infeasible.
EXAMPLES::
sage: A = ([1, 1], [3, 1], [-1, -1]) sage: b = (1000, 1500, -400) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: AP = P.auxiliary_problem() """ raise ValueError("auxiliary variable is already among decision " "ones") A, self.b(), c, X[:-m], slack_variables=X[-m:], auxiliary_variable=X[0], objective_name=objective_name)
r""" Return the auxiliary variable of ``self``.
Note that the auxiliary variable may or may not be among :meth:`~InteractiveLPProblem.decision_variables`.
OUTPUT:
- a variable of the :meth:`coordinate_ring` of ``self``
EXAMPLES::
sage: A = ([1, 1], [3, 1], [-1, -1]) sage: b = (1000, 1500, -400) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(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) """
r""" Return the coordinate ring of ``self``.
OUTPUT:
- a polynomial ring over the :meth:`~InteractiveLPProblem.base_ring` of ``self`` in the :meth:`auxiliary_variable`, :meth:`~InteractiveLPProblem.decision_variables`, and :meth:`slack_variables` with "neglex" order
EXAMPLES::
sage: A = ([1, 1], [3, 1], [-1, -1]) sage: b = (1000, 1500, -400) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(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) """
r""" Construct a dictionary for ``self`` with given basic variables.
INPUT:
- basic variables for the dictionary to be constructed
OUTPUT:
- a :class:`dictionary <LPDictionary>`
.. 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 = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.dictionary("x1", "x2") sage: D.basic_variables() (x1, x2) """ raise ValueError("basic variables must be given explicitly")
r""" Construct a feasible dictionary for ``self``.
INPUT:
- ``auxiliary_dictionary`` -- an optimal dictionary for the :meth:`auxiliary_problem` of ``self`` with the optimal value `0` and a non-basic auxiliary variable
OUTPUT:
- a feasible :class:`dictionary <LPDictionary>` for ``self``
EXAMPLES::
sage: A = ([1, 1], [3, 1], [-1, -1]) sage: b = (1000, 1500, -400) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(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) """ # It is good to have sanity checks in this function, but they are a bit # problematic with numerical dictionaries, so we do only few. raise ValueError("the auxiliary variable must be non-basic") raise ValueError("the auxiliary dictionary must be feasible") else:
r""" Return the final dictionary of the simplex method applied to ``self``.
See :meth:`run_simplex_method` for the description of possibilities.
OUTPUT:
- a :class:`dictionary <LPDictionary>`
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.final_dictionary() sage: D.is_optimal() True
TESTS::
sage: P.final_dictionary() is P.final_dictionary() False """ # Since dictionaries are "highly mutable", forget the returned one.
r""" Return the final dictionary of the revised simplex method applied to ``self``.
See :meth:`run_revised_simplex_method` for the description of possibilities.
OUTPUT:
- a :class:`revised dictionary <LPRevisedDictionary>`
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(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 """ # Since dictionaries are "highly mutable", forget the returned one.
r""" Construct the initial dictionary of ``self``.
The initial dictionary "defines" :meth:`slack_variables` in terms of the :meth:`~InteractiveLPProblem.decision_variables`, i.e. it has slack variables as basic ones.
OUTPUT:
- a :class:`dictionary <LPDictionary>`
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.initial_dictionary() """ self.objective_name())
r""" Inject variables of ``self`` into ``scope``.
INPUT:
- ``scope`` -- namespace (default: global)
- ``verbose`` -- if ``True`` (default), names of injected variables will be printed
OUTPUT:
- none
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: P.inject_variables() Defining x0, x1, x2, x3, x4 sage: 3*x1 + x2 x2 + 3*x1 """ except AttributeError: pass
r""" Return the objective name used in dictionaries for this problem.
OUTPUT:
- a symbolic expression
EXAMPLES::
sage: A = ([1, 1], [3, 1], [-1, -1]) sage: b = (1000, 1500, -400) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: P.objective_name() z sage: sage.numerical.interactive_simplex_method.style("Vanderbei") 'Vanderbei' sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: P.objective_name() zeta sage: sage.numerical.interactive_simplex_method.style("UAlberta") 'UAlberta' sage: P = InteractiveLPProblemStandardForm(A, b, c, objective_name="custom") sage: P.objective_name() custom """
r""" Construct a revised dictionary for ``self``.
INPUT:
- basic variables for the dictionary to be constructed; if not given, :meth:`slack_variables` will be used, perhaps with the :meth:`auxiliary_variable` to give a feasible dictionary
OUTPUT:
- a :class:`revised dictionary <LPRevisedDictionary>`
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(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 = InteractiveLPProblemStandardForm(A, b, c) sage: P.initial_dictionary().is_feasible() False sage: P.revised_dictionary().basic_variables() (x3, x4, x0) """
r""" Apply the revised simplex method and return all steps.
OUTPUT:
- :class:`~sage.misc.html.HtmlFragment` with HTML/`\LaTeX` code of all encountered dictionaries
.. NOTE::
You can access the :meth:`final_revised_dictionary`, which can be one of the following:
- an optimal dictionary with the :meth:`auxiliary_variable` among :meth:`~LPRevisedDictionary.basic_variables` and a non-zero optimal value indicating that ``self`` is infeasible;
- a non-optimal dictionary that has marked entering variable for which there is no choice of the leaving variable, indicating that ``self`` is unbounded;
- an optimal dictionary.
EXAMPLES::
sage: A = ([1, 1], [3, 1], [-1, -1]) sage: b = (1000, 1500, -400) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: P.run_revised_simplex_method() \begin{equation*} ... \end{equation*} Entering: $x_{1}$. Leaving: $x_{0}$. \begin{equation*} ... \end{equation*} Entering: $x_{5}$. Leaving: $x_{4}$. \begin{equation*} ... \end{equation*} Entering: $x_{2}$. Leaving: $x_{3}$. \begin{equation*} ... \end{equation*} The optimal value: $6250$. An optimal solution: $\left(250,\,750\right)$. """ output.append("The problem is infeasible.") else: "An optimal solution: ${}$.").format( latex(v), latex(d.basic_solution())))
r""" Apply the simplex method and return all steps and intermediate states.
OUTPUT:
- :class:`~sage.misc.html.HtmlFragment` with HTML/`\LaTeX` code of all encountered dictionaries
.. NOTE::
You can access the :meth:`final_dictionary`, which can be one of the following:
- an optimal dictionary for the :meth:`auxiliary_problem` with a non-zero optimal value indicating that ``self`` is infeasible;
- a non-optimal dictionary for ``self`` that has marked entering variable for which there is no choice of the leaving variable, indicating that ``self`` is unbounded;
- an optimal dictionary for ``self``.
EXAMPLES::
sage: A = ([1, 1], [3, 1], [-1, -1]) sage: b = (1000, 1500, -400) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: P.run_simplex_method() \begin{equation*} ... \end{equation*} The initial dictionary is infeasible, solving auxiliary problem. ... Entering: $x_{0}$. Leaving: $x_{5}$. ... Entering: $x_{1}$. Leaving: $x_{0}$. ... Back to the original problem. ... Entering: $x_{5}$. Leaving: $x_{4}$. ... Entering: $x_{2}$. Leaving: $x_{3}$. ... The optimal value: $6250$. An optimal solution: $\left(250,\,750\right)$. """ "solving auxiliary problem.") # Phase I output.append("The original problem is infeasible.") self._final_dictionary = ad else: # Phase II v = - v "An optimal solution: ${}$.").format( latex(v), latex(d.basic_solution())))
r""" 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:
- a tuple
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: P.slack_variables() (x3, x4) sage: P = InteractiveLPProblemStandardForm(A, b, c, ["C", "B"], ....: slack_variables=["L", "F"]) sage: P.slack_variables() (L, F) """
r""" Abstract base class for dictionaries for LP problems.
Instantiating this class directly is meaningless, see :class:`LPDictionary` and :class:`LPRevisedDictionary` for useful extensions. """
r""" Initialize internal fields for entering and leaving variables.
TESTS::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.initial_dictionary() # indirect doctest """
r""" Return an HTML representation of ``self``.
OUTPUT:
- a string
TESTS::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.initial_dictionary() sage: print(D._html_()) \begin{equation*} ... \end{equation*} """ latex(self), r"\end{equation*}"]))
r""" Return auxiliary output before the update step.
Called from :meth:`run_simplex_method`.
INPUT:
- ``direction`` -- a string specifying the type of the simplex method used, either "primal" or "dual"
OUTPUT:
- :class:`~sage.misc.html.HtmlFragment`.
TESTS::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.initial_dictionary() sage: D.enter(1) sage: D.leave(4) sage: D._preupdate_output("primal") Entering: $x_{1}$. Leaving: $x_{4}$. sage: D._preupdate_output("dual") Leaving: $x_{4}$. Entering: $x_{1}$. """ else: raise ValueError("direction must be either primal or dual")
r""" Return a string representation of ``self``.
OUTPUT:
- a string
TESTS::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.initial_dictionary() sage: print(D._repr_()) LP problem dictionary (use typeset mode to see details) sage: D = P.revised_dictionary() sage: print(D._repr_()) LP problem dictionary (use typeset mode to see details) """
r""" Return a dictionary with an additional row based on a given dictionary.
INPUT:
- ``nonbasic_coefficients``-- a list of the coefficients for the new row (with which nonbasic variables are subtracted in the relation for the new basic variable)
- ``constant``-- the constant term for the new row
- ``basic_variable``-- (default: depends on :func:`style`) a string giving the name of the basic variable of the new row
OUTPUT:
- a new dictionary of the same class
EXAMPLES::
sage: A = ([-1, 1, 7], [8, 2, 13], [34, 17, 12]) sage: b = (2, 17, 6) sage: c = (55/10, 21/10, 14/30) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.dictionary("x1", "x2", "x4") sage: D1 = D.add_row([7, 11, 19], 42, basic_variable='c') sage: D1.row_coefficients("c") (7, 11, 19) """
r""" Return the base ring of ``self``, i.e. the ring of coefficients.
OUTPUT:
- a ring
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(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 """
def basic_variables(self): r""" Return the basic variables of ``self``.
OUTPUT:
- a vector
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.initial_dictionary() sage: D.basic_variables() (x3, x4) """
r""" Return the basic solution of ``self``.
The basic solution associated to a dictionary is obtained by setting to zero all :meth:`~LPDictionary.nonbasic_variables`, in which case :meth:`~LPDictionary.basic_variables` have to be equal to :meth:`~LPDictionary.constant_terms` in equations. It may refer to values of :meth:`~InteractiveLPProblem.decision_variables` only or include :meth:`~InteractiveLPProblemStandardForm.slack_variables` as well.
INPUT:
- ``include_slack_variables`` -- (default: ``False``) if ``True``, values of slack variables will be appended at the end
OUTPUT:
- a vector
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(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) """ v if include_slack_variables else v[:len(N)])
def column_coefficients(self, v): r""" Return the coefficients of a nonbasic variable.
INPUT:
- ``v`` -- a nonbasic variable of ``self``, can be given as a string, an actual variable, or an integer interpreted as the index of a variable
OUTPUT:
- a vector of coefficients of a nonbasic variable
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.revised_dictionary() sage: D.column_coefficients(1) (1, 3) """
def constant_terms(self): r""" Return the constant terms of relations of ``self``.
OUTPUT:
- a vector.
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.initial_dictionary() sage: D.constant_terms() (1000, 1500) """
r""" Return the coordinate ring of ``self``.
OUTPUT:
- a polynomial ring in :meth:`~InteractiveLPProblemStandardForm.auxiliary_variable`, :meth:`~InteractiveLPProblem.decision_variables`, and :meth:`~InteractiveLPProblemStandardForm.slack_variables` of ``self`` over the :meth:`base_ring`
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(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 """
r""" Return ratios used to determine the entering variable based on leaving.
OUTPUT:
- A list of pairs `(r_j, x_j)` where `x_j` is a non-basic variable and `r_j = c_j / a_{ij}` is the ratio of the objective coefficient `c_j` to the coefficient `a_{ij}` of `x_j` in the relation for the leaving variable `x_i`:
.. MATH::
x_i = b_i - \cdots - a_{ij} x_j - \cdots.
The order of pairs matches the order of :meth:`~LPDictionary.nonbasic_variables`, but only `x_j` with negative `a_{ij}` are considered.
EXAMPLES::
sage: A = ([1, 1], [3, 1], [-1, -1]) sage: b = (1000, 1500, -400) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(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)] """ self.leaving_coefficients(), self.nonbasic_variables()) if a < 0]
r""" Set ``v`` as the entering variable of ``self``.
INPUT:
- ``v`` -- a non-basic variable of ``self``, can be given as a string, an actual variable, or an integer interpreted as the index of a variable. It is also possible to enter ``None`` to reset choice.
OUTPUT:
- none, but the selected variable will be used as entering by methods that require an entering variable and the corresponding column will be typeset in green
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(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) """ raise ValueError("entering variable must be non-basic")
r""" Return the currently chosen entering variable.
OUTPUT:
- a variable if the entering one was chosen, otherwise ``None``
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.initial_dictionary() sage: D.entering() is None True sage: D.enter(1) sage: D.entering() x1 """
r""" Return coefficients of the entering variable.
OUTPUT:
- a vector
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.initial_dictionary() sage: D.enter(1) sage: D.entering_coefficients() (1, 3) """ raise ValueError("entering variable must be chosen to compute " "its coefficients")
r""" Check if ``self`` is dual feasible.
OUTPUT:
- ``True`` if all :meth:`~LPDictionary.objective_coefficients` are non-positive, ``False`` otherwise
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(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 """
r""" Check if ``self`` is feasible.
OUTPUT:
- ``True`` if all :meth:`~LPDictionary.constant_terms` are non-negative, ``False`` otherwise
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.initial_dictionary() sage: D.is_feasible() True sage: D = P.revised_dictionary() sage: D.is_feasible() True """
r""" Check if ``self`` is optimal.
OUTPUT:
- ``True`` if ``self`` :meth:`is_feasible` and :meth:`is_dual_feasible` (i.e. all :meth:`~LPDictionary.constant_terms` are non-negative and all :meth:`~LPDictionary.objective_coefficients` are non-positive), ``False`` otherwise.
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(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 """
r""" Set ``v`` as the leaving variable of ``self``.
INPUT:
- ``v`` -- a basic variable of ``self``, can be given as a string, an actual variable, or an integer interpreted as the index of a variable. It is also possible to leave ``None`` to reset choice.
OUTPUT:
- none, but the selected variable will be used as leaving by methods that require a leaving variable and the corresponding row will be typeset in red
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(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) """ raise ValueError("leaving variable must be basic")
r""" Return the currently chosen leaving variable.
OUTPUT:
- a variable if the leaving one was chosen, otherwise ``None``
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.initial_dictionary() sage: D.leaving() is None True sage: D.leave(4) sage: D.leaving() x4 """
r""" Return coefficients of the leaving variable.
OUTPUT:
- a vector
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.dictionary(2, 3) sage: D.leave(3) sage: D.leaving_coefficients() (-2, -1)
The same works for revised dictionaries as well::
sage: D = P.revised_dictionary(2, 3) sage: D.leave(3) sage: D.leaving_coefficients() (-2, -1) """ raise ValueError("leaving variable must be chosen to compute " "its coefficients")
def nonbasic_variables(self): r""" Return non-basic variables of ``self``.
OUTPUT:
- a vector
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.initial_dictionary() sage: D.nonbasic_variables() (x1, x2) """
def objective_coefficients(self): r""" Return coefficients of the objective of ``self``.
OUTPUT:
- a vector
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.initial_dictionary() sage: D.objective_coefficients() (10, 5) """
def objective_name(self): r""" Return the objective name of ``self``.
OUTPUT:
- a symbolic expression
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.initial_dictionary() sage: D.objective_name() z """
def objective_value(self): r""" Return the value of the objective at the :meth:`~LPAbstractDictionary.basic_solution` of ``self``.
OUTPUT:
- a number
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.initial_dictionary() sage: D.objective_value() 0 """
r""" Return possible dual simplex method steps for ``self``.
OUTPUT:
- A list of pairs ``(leaving, entering)``, where ``leaving`` is a basic variable that may :meth:`leave` and ``entering`` is a list of non-basic variables that may :meth:`enter` when ``leaving`` leaves. Note that ``entering`` may be empty, indicating that the problem is infeasible (since the dual one is unbounded).
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(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])] """ raise ValueError("dual simplex method steps are applicable to " "dual feasible dictionaries only")
r""" Return possible entering variables for ``self``.
OUTPUT:
- a list of non-basic variables of ``self`` that can :meth:`enter` on the next step of the (dual) simplex method
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(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] """ self.nonbasic_variables()) if c > 0] "dictionaries or for dual feasible dictionaries " "with a set leaving variable")
r""" Return possible leaving variables for ``self``.
OUTPUT:
- a list of basic variables of ``self`` that can :meth:`leave` on the next step of the (dual) simplex method
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(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] """ self.basic_variables()) if b < 0] "dictionaries with a set entering variable " "or for dual feasible dictionaries")
r""" Return possible simplex method steps for ``self``.
OUTPUT:
- A list of pairs ``(entering, leaving)``, where ``entering`` is a non-basic variable that may :meth:`enter` and ``leaving`` is a list of basic variables that may :meth:`leave` when ``entering`` enters. Note that ``leaving`` may be empty, indicating that the problem is unbounded.
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(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])] """ raise ValueError("simplex method steps are applicable to feasible " "dictionaries only")
r""" Return ratios used to determine the leaving variable based on entering.
OUTPUT:
- A list of pairs `(r_i, x_i)` where `x_i` is a basic variable and `r_i = b_i / a_{ik}` is the ratio of the constant term `b_i` to the coefficient `a_{ik}` of the entering variable `x_k` in the relation for `x_i`:
.. MATH::
x_i = b_i - \cdots - a_{ik} x_k - \cdots.
The order of pairs matches the order of :meth:`~LPDictionary.basic_variables`, but only `x_i` with positive `a_{ik}` are considered.
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(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)] """ self.entering_coefficients(), self.basic_variables()) if a > 0]
def row_coefficients(self, v): r""" Return the coefficients of the basic variable ``v``.
These are the coefficients with which nonbasic variables are subtracted in the relation for ``v``.
INPUT:
- ``v`` -- a basic variable of ``self``, can be given as a string, an actual variable, or an integer interpreted as the index of a variable
OUTPUT:
- a vector of coefficients of a basic variable
EXAMPLES::
sage: A = ([-1, 1], [8, 2]) sage: b = (2, 17) sage: c = (55/10, 21/10) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.final_dictionary() sage: D.row_coefficients("x1") (1/10, -1/5)
We can also use indices of variables::
sage: D.row_coefficients(1) (1/10, -1/5)
Or use variable names without quotes after injecting them::
sage: P.inject_variables() Defining x0, x1, x2, x3, x4 sage: D.row_coefficients(x1) (1/10, -1/5) """
r""" Apply the dual simplex method and return all steps/intermediate states.
If either entering or leaving variables were already set, they will be used.
OUTPUT:
- :class:`~sage.misc.html.HtmlFragment` with HTML/`\LaTeX` code of all encountered dictionaries
EXAMPLES::
sage: A = ([1, 1], [3, 1], [-1, -1]) sage: b = (1000, 1500, -400) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.initial_dictionary() sage: D.run_dual_simplex_method() Traceback (most recent call last): ... ValueError: leaving variables can be determined for feasible dictionaries with a set entering variable or for dual feasible dictionaries
Let's start with a dual feasible dictionary then::
sage: D = P.dictionary(2, 3, 5) sage: D.is_dual_feasible() True sage: D.is_optimal() False sage: D.run_dual_simplex_method() \begin{equation*} ... \end{equation*} Leaving: $x_{3}$. Entering: $x_{1}$. \begin{equation*} ... \end{equation*} sage: D.is_optimal() True
This method detects infeasible problems::
sage: A = ([1, 0],) sage: b = (-1,) sage: c = (0, -1) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.initial_dictionary() sage: D.run_dual_simplex_method() \begin{equation*} ... \end{equation*} The problem is infeasible because of $x_{3}$ constraint. """ "${}$ constraint.".format(latex(self.leaving())))
r""" Apply the simplex method and return all steps and intermediate states.
If either entering or leaving variables were already set, they will be used.
OUTPUT:
- :class:`~sage.misc.html.HtmlFragment` with HTML/`\LaTeX` code of all encountered dictionaries
EXAMPLES::
sage: A = ([1, 1], [3, 1], [-1, -1]) sage: b = (1000, 1500, -400) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.initial_dictionary() sage: D.run_simplex_method() Traceback (most recent call last): ... ValueError: entering variables can be determined for feasible dictionaries or for dual feasible dictionaries with a set leaving variable
Let's start with a feasible dictionary then::
sage: D = P.dictionary(1, 3, 4) sage: D.is_feasible() True sage: D.is_optimal() False sage: D.run_simplex_method() \begin{equation*} ... \end{equation*} Entering: $x_{5}$. Leaving: $x_{4}$. \begin{equation*} ... \end{equation*} Entering: $x_{2}$. Leaving: $x_{3}$. \begin{equation*} ... \end{equation*} sage: D.is_optimal() True
This method detects unbounded problems::
sage: A = ([1, 0],) sage: b = (1,) sage: c = (0, 1) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.initial_dictionary() sage: D.run_simplex_method() \begin{equation*} ... \end{equation*} The problem is unbounded in $x_{2}$ direction. """ .format(latex(self.entering())))
def update(self): r""" 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 = InteractiveLPProblemStandardForm(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 """
r""" Construct a dictionary for an LP problem.
A dictionary consists of the following data:
.. MATH::
\begin{array}{|l|} \hline x_B = b - A x_N\\ \hline z = z^* + c x_N\\ \hline \end{array}
INPUT:
- ``A`` -- a matrix of relation coefficients
- ``b`` -- a vector of relation constant terms
- ``c`` -- a vector of objective coefficients
- ``objective_value`` -- current value of the objective `z^*`
- ``basic_variables`` -- a list of basic variables `x_B`
- ``nonbasic_variables`` -- a list of non-basic variables `x_N`
- ``objective_name`` -- a "name" for the objective `z`
OUTPUT:
- a :class:`dictionary for an LP problem <LPDictionary>`
.. NOTE::
This constructor does not check correctness of input, as it is intended to be used internally by :class:`InteractiveLPProblemStandardForm`.
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 = InteractiveLPProblemStandardForm(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 """
basic_variables, nonbasic_variables, objective_name): r""" See :class:`LPDictionary` for documentation.
TESTS::
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: D = LPDictionary(A, b, c, 0, R.gens()[2:], R.gens()[:2], "z") sage: TestSuite(D).run() """ # We are going to change stuff while InteractiveLPProblem has immutable data.
r""" Check if two LP problem dictionaries are equal.
INPUT:
- ``other`` -- anything
OUTPUT:
- ``True`` if ``other`` is an :class:`LPDictionary` with all details the same as ``self``, ``False`` otherwise.
TESTS::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.initial_dictionary()
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
sage: D3 = LPDictionary(A, b, c, 0, R.gens()[2:], R.gens()[:2], "w") sage: D2 == D3 False """ self._AbcvBNz == other._AbcvBNz)
r""" Return a LaTeX representation of ``self``.
OUTPUT:
- a string
TESTS::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.initial_dictionary() sage: print(D._latex_()) \renewcommand{\arraystretch}{1.5} %notruncate \begin{array}{|rcrcrcr|} \hline x_{3} \mspace{-6mu}&\mspace{-6mu} = \mspace{-6mu}&\mspace{-6mu} 1000 \mspace{-6mu}&\mspace{-6mu} - \mspace{-6mu}&\mspace{-6mu} x_{1} \mspace{-6mu}&\mspace{-6mu} - \mspace{-6mu}&\mspace{-6mu} x_{2}\\ x_{4} \mspace{-6mu}&\mspace{-6mu} = \mspace{-6mu}&\mspace{-6mu} 1500 \mspace{-6mu}&\mspace{-6mu} - \mspace{-6mu}&\mspace{-6mu} 3 x_{1} \mspace{-6mu}&\mspace{-6mu} - \mspace{-6mu}&\mspace{-6mu} x_{2}\\ \hline z \mspace{-6mu}&\mspace{-6mu} = \mspace{-6mu}&\mspace{-6mu} 0 \mspace{-6mu}&\mspace{-6mu} + \mspace{-6mu}&\mspace{-6mu} 10 x_{1} \mspace{-6mu}&\mspace{-6mu} + \mspace{-6mu}&\mspace{-6mu} 5 x_{2}\\ \hline \end{array} """ lines[-1] += r" \setlength{\arraycolsep}{0.125em}" drop_plus=False, allow_empty=True) + r"\\" for xi, bi, Ai in zip(B, b, A.rows())] drop_plus=False, allow_empty=True) + r"\\" lines.append(r"\begin{array}{rcr%s}" % ("cr"*len(N))) lines.append(objective) lines.append(r"\hline") lines.extend(relations) # Highlight the entering variable column # Highlight the leaving variable row l += 4
r""" Perform the Enter-Leave-LaTeX-Update-LaTeX step sequence on ``self``.
INPUT:
- ``entering`` -- the entering variable
- ``leaving`` -- the leaving variable
OUTPUT:
- a string with LaTeX code for ``self`` before and after update
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.initial_dictionary() sage: D.ELLUL("x1", "x4") doctest:...: DeprecationWarning: ELLUL is deprecated, please use separate enter-leave-update and output commands See http://trac.sagemath.org/19097 for details. \renewcommand{\arraystretch}{1.5} %notruncate \begin{array}{|rcrcrcr|} \hline x_{3} \mspace{-6mu}&\mspace{-6mu} = \mspace{-6mu}&\mspace{-6mu} 1000 \mspace{-6mu}&\mspace{-6mu} - \mspace{-6mu}&\color{green}\mspace{-6mu} x_{1} \mspace{-6mu}&\mspace{-6mu} - \mspace{-6mu}&\mspace{-6mu} x_{2}\\ \color{red}x_{4} \mspace{-6mu}&\color{red}\mspace{-6mu} = \mspace{-6mu}&\color{red}\mspace{-6mu} 1500 \mspace{-6mu}&\color{red}\mspace{-6mu} - \mspace{-6mu}&\color{blue}\mspace{-6mu} 3 x_{1} \mspace{-6mu}&\color{red}\mspace{-6mu} - \mspace{-6mu}&\color{red}\mspace{-6mu} x_{2}\\ \hline z \mspace{-6mu}&\mspace{-6mu} = \mspace{-6mu}&\mspace{-6mu} 0 \mspace{-6mu}&\mspace{-6mu} + \mspace{-6mu}&\color{green}\mspace{-6mu} 10 x_{1} \mspace{-6mu}&\mspace{-6mu} + \mspace{-6mu}&\mspace{-6mu} 5 x_{2}\\ \hline \\ \hline x_{3} \mspace{-6mu}&\mspace{-6mu} = \mspace{-6mu}&\mspace{-6mu} 500 \mspace{-6mu}&\mspace{-6mu} + \mspace{-6mu}&\mspace{-6mu} \frac{1}{3} x_{4} \mspace{-6mu}&\mspace{-6mu} - \mspace{-6mu}&\mspace{-6mu} \frac{2}{3} x_{2}\\ x_{1} \mspace{-6mu}&\mspace{-6mu} = \mspace{-6mu}&\mspace{-6mu} 500 \mspace{-6mu}&\mspace{-6mu} - \mspace{-6mu}&\mspace{-6mu} \frac{1}{3} x_{4} \mspace{-6mu}&\mspace{-6mu} - \mspace{-6mu}&\mspace{-6mu} \frac{1}{3} x_{2}\\ \hline z \mspace{-6mu}&\mspace{-6mu} = \mspace{-6mu}&\mspace{-6mu} 5000 \mspace{-6mu}&\mspace{-6mu} - \mspace{-6mu}&\mspace{-6mu} \frac{10}{3} x_{4} \mspace{-6mu}&\mspace{-6mu} + \mspace{-6mu}&\mspace{-6mu} \frac{5}{3} x_{2}\\ \hline \end{array}
This is how the above output looks when rendered:
.. MATH::
\renewcommand{\arraystretch}{1.5} \begin{array}{|rcrcrcr|} \hline x_{3} \mspace{-6mu}&\mspace{-6mu} = \mspace{-6mu}&\mspace{-6mu} 1000 \mspace{-6mu}&\mspace{-6mu} - \mspace{-6mu}&\color{green}\mspace{-6mu} x_{1} \mspace{-6mu}&\mspace{-6mu} - \mspace{-6mu}&\mspace{-6mu} x_{2}\\ \color{red}x_{4} \mspace{-6mu}&\color{red}\mspace{-6mu} = \mspace{-6mu}&\color{red}\mspace{-6mu} 1500 \mspace{-6mu}&\color{red}\mspace{-6mu} - \mspace{-6mu}&\color{blue}\mspace{-6mu} 3 x_{1} \mspace{-6mu}&\color{red}\mspace{-6mu} - \mspace{-6mu}&\color{red}\mspace{-6mu} x_{2}\\ \hline z \mspace{-6mu}&\mspace{-6mu} = \mspace{-6mu}&\mspace{-6mu} 0 \mspace{-6mu}&\mspace{-6mu} + \mspace{-6mu}&\color{green}\mspace{-6mu} 10 x_{1} \mspace{-6mu}&\mspace{-6mu} + \mspace{-6mu}&\mspace{-6mu} 5 x_{2}\\ \hline \\ \hline x_{3} \mspace{-6mu}&\mspace{-6mu} = \mspace{-6mu}&\mspace{-6mu} 500 \mspace{-6mu}&\mspace{-6mu} + \mspace{-6mu}&\mspace{-6mu} \frac{1}{3} x_{4} \mspace{-6mu}&\mspace{-6mu} - \mspace{-6mu}&\mspace{-6mu} \frac{2}{3} x_{2}\\ x_{1} \mspace{-6mu}&\mspace{-6mu} = \mspace{-6mu}&\mspace{-6mu} 500 \mspace{-6mu}&\mspace{-6mu} - \mspace{-6mu}&\mspace{-6mu} \frac{1}{3} x_{4} \mspace{-6mu}&\mspace{-6mu} - \mspace{-6mu}&\mspace{-6mu} \frac{1}{3} x_{2}\\ \hline z \mspace{-6mu}&\mspace{-6mu} = \mspace{-6mu}&\mspace{-6mu} 5000 \mspace{-6mu}&\mspace{-6mu} - \mspace{-6mu}&\mspace{-6mu} \frac{10}{3} x_{4} \mspace{-6mu}&\mspace{-6mu} + \mspace{-6mu}&\mspace{-6mu} \frac{5}{3} x_{2}\\ \hline \end{array}
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. """ "enter-leave-update and output commands") # Make an empty line in the array result += "\n" r"\multicolumn{2}{c}{}\\[-3ex]" "\n" else:
r""" Return a dictionary with an additional row based on a given dictionary.
INPUT:
- ``nonbasic_coefficients``-- a list of the coefficients for the new row (with which nonbasic variables are subtracted in the relation for the new basic variable)
- ``constant``-- the constant term for the new row
- ``basic_variable``-- (default: depends on :func:`style`) a string giving the name of the basic variable of the new row
OUTPUT:
- a :class:`dictionary <LPDictionary>`
EXAMPLES::
sage: A = ([-1, 1, 7], [8, 2, 13], [34, 17, 12]) sage: b = (2, 17, 6) sage: c = (55/10, 21/10, 14/30) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.dictionary("x1", "x2", "x4") sage: D1 = D.add_row([7, 11, 19], 42, basic_variable='c') sage: D1.row_coefficients("c") (7, 11, 19) sage: D1.constant_terms()[-1] 42 sage: D1.basic_variables()[-1] c """
basic_variable = default_variable_name("primal slack") if style() == "UAlberta": index = n + m + 1 elif style() == 'Vanderbei': index = m + 1 basic_variable = "{}{:d}".format(basic_variable, index) basic_variable = str(basic_variable)
BR, list(B.base_ring().variable_names()) + [basic_variable], order="neglex")
r""" Return the basic variables of ``self``.
OUTPUT:
- a vector
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.initial_dictionary() sage: D.basic_variables() (x3, x4) """
r""" Return coefficients of a nonbasic variable.
INPUT:
- ``v`` -- a nonbasic variable of ``self``, can be given as a string, an actual variable, or an integer interpreted as the index of a variable
OUTPUT:
- a vector
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.initial_dictionary() sage: D.column_coefficients(1) (1, 3) """ raise ValueError("variable must be nonbasic")
r""" Return the constant terms of relations of ``self``.
OUTPUT:
- a vector.
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.initial_dictionary() sage: D.constant_terms() (1000, 1500) """
r""" Return non-basic variables of ``self``.
OUTPUT:
- a vector
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.initial_dictionary() sage: D.nonbasic_variables() (x1, x2) """
r""" Return coefficients of the objective of ``self``.
OUTPUT:
- a vector
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.initial_dictionary() sage: D.objective_coefficients() (10, 5) """
r""" Return the objective name of ``self``.
OUTPUT:
- a symbolic expression
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.initial_dictionary() sage: D.objective_name() z """
r""" Return the value of the objective at the :meth:`~LPAbstractDictionary.basic_solution` of ``self``.
OUTPUT:
- a number
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.initial_dictionary() sage: D.objective_value() 0 """
r""" Return the coefficients of the basic variable ``v``.
These are the coefficients with which nonbasic variables are subtracted in the relation for ``v``.
INPUT:
- ``v`` -- a basic variable of ``self``, can be given as a string, an actual variable, or an integer interpreted as the index of a variable
OUTPUT:
- a vector of coefficients of a basic variable
EXAMPLES::
sage: A = ([-1, 1], [8, 2]) sage: b = (2, 17) sage: c = (55/10, 21/10) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.final_dictionary() sage: D.row_coefficients("x1") (1/10, -1/5)
We can also use indices of variables::
sage: D.row_coefficients(1) (1/10, -1/5)
Or use variable names without quotes after injecting them::
sage: P.inject_variables() Defining x0, x1, x2, x3, x4 sage: D.row_coefficients(x1) (1/10, -1/5) """ raise ValueError("variable must be basic")
r""" 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 = InteractiveLPProblemStandardForm(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 """ raise ValueError("entering variable must be set before updating") raise ValueError("leaving variable must be set before updating") raise ValueError("incompatible choice of entering and leaving " "variables") # Variables # "The Changing Relation" # Other relations # Objective
r""" Construct a random dictionary.
INPUT:
- ``m`` -- the number of constraints/basic variables
- ``n`` -- the number of decision/non-basic variables
- ``bound`` -- (default: 5) a bound on dictionary entries
- ``special_probability`` -- (default: 0.2) probability of constructing a potentially infeasible or potentially optimal dictionary
OUTPUT:
- an :class:`LP problem dictionary <LPDictionary>`
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) """ else: # Allow infeasible dictionary b = random_vector(ZZ, m, x=-bound, y=bound).change_ring(QQ) else: # Make dual feasible dictionary c = random_vector(ZZ, n, x=-bound, y=0).change_ring(QQ)
r""" Construct a revised dictionary for an LP problem.
INPUT:
- ``problem`` -- an :class:`LP problem in standard form <InteractiveLPProblemStandardForm>`
- ``basic_variables`` -- a list of basic variables or their indices
OUTPUT:
- a :class:`revised dictionary for an LP problem <LPRevisedDictionary>`
A revised dictionary encodes the same relations as a :class:`regular dictionary <LPDictionary>`, but stores only what is "necessary to efficiently compute data for the simplex method".
Let the original problem be
.. MATH::
\begin{array}{l} \pm \max cx \\ Ax \leq b \\ x \geq 0 \end{array}
Let `\bar{x}` be the vector of :meth:`~InteractiveLPProblem.decision_variables` `x` followed by the :meth:`~InteractiveLPProblemStandardForm.slack_variables`. Let `\bar{c}` be the vector of :meth:`~InteractiveLPProblem.objective_coefficients` `c` followed by zeroes for all slack variables. Let `\bar{A} = (A | I)` be the matrix of :meth:`~InteractiveLPProblem.constraint_coefficients` `A` augmented by the identity matrix as columns corresponding to the slack variables. Then the problem above can be written as
.. MATH::
\begin{array}{l} \pm \max \bar{c} \bar{x} \\ \bar{A} \bar{x} = b \\ \bar{x} \geq 0 \end{array}
and any dictionary is a system of equations equivalent to `\bar{A} \bar{x} = b`, but resolved for :meth:`basic_variables` `x_B` in terms of :meth:`nonbasic_variables` `x_N` together with the expression for the objective in terms of `x_N`. Let :meth:`c_B` and :meth:`c_N` be vectors "splitting `\bar{c}` into basic and non-basic parts". Let :meth:`B` and :meth:`A_N` be the splitting of `\bar{A}`. Then the corresponding dictionary is
.. MATH::
\begin{array}{|l|} \hline x_B = B^{-1} b - B^{-1} A_N x_N\\ \hline z = y b + \left(c_N - y^T A_N\right) x_N\\ \hline \end{array}
where `y = c_B^T B^{-1}`. 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 `B^{-1}`, 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 = InteractiveLPProblemStandardForm(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:
.. MATH::
\renewcommand{\arraystretch}{1.500000} \begin{array}{l} \begin{array}{l|r|rr||r||r} x_B & c_B & & \mspace{-16mu} B^{-1} & y & B^{-1} b \\ \hline x_{1} & 10 & -\frac{1}{2} & \frac{1}{2} & \frac{5}{2} & 250 \\ x_{2} & 5 & \frac{3}{2} & -\frac{1}{2} & \frac{5}{2} & 750 \\ \end{array}\\ \\ \begin{array}{r|rr} x_N & x_{3} & x_{4} \\ \hline c_N^T & 0 & 0 \\ \hline y^T A_N & \frac{5}{2} & \frac{5}{2} \\ \hline c_N^T - y^T A_N & -\frac{5}{2} & -\frac{5}{2} \\ \end{array} \end{array}
More details will be shown if entering and leaving variables are set, but in any case the top table shows `B^{-1}` and a few extra columns, while the bottom one shows several rows: these are related to columns and rows of dictionary entries. """
r""" See :class:`LPRevisedDictionary` for documentation.
TESTS::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: from sage.numerical.interactive_simplex_method \ ....: import LPRevisedDictionary sage: D = LPRevisedDictionary(P, [1, 2]) sage: TestSuite(D).run() """ raise ValueError("revised dictionaries should not be constructed " "for auxiliary problems")
r""" Check if two revised LP problem dictionaries are equal.
INPUT:
- ``other`` -- anything
OUTPUT:
- ``True`` if ``other`` is an :class:`LPRevisedDictionary` for the same :class:`InteractiveLPProblemStandardForm` with the same :meth:`basic_variables`, ``False`` otherwise
TESTS::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: from sage.numerical.interactive_simplex_method \ ....: import LPRevisedDictionary sage: D1 = LPRevisedDictionary(P, [1, 2]) sage: D2 = LPRevisedDictionary(P, [1, 2]) sage: D1 is D2 False sage: D1 == D2 True sage: D3 = LPRevisedDictionary(P, [2, 0]) sage: D1 == D3 False """ self._problem == other._problem and self._x_B == other._x_B)
r""" Return a LaTeX representation of ``self``.
OUTPUT:
- a string
TESTS::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.revised_dictionary() sage: D.enter(1) sage: D.leave(3) sage: print(D._latex_()) %notruncate \renewcommand{\arraystretch}{1.500000} \begin{array}{l} \begin{array}{l|r|rr||r||r|r|r} x_B & c_B & & \mspace{-16mu} B^{-1} & y & B^{-1} b & B^{-1} A_{x_{1}} & \hbox{Ratio} \\ \hline \color{red} x_{3} & \color{red} 0 & \color{red} 1 & \color{red} 0 & 0 & \color{red} 1000 & \color{red} 1 & \color{red} 1000 \\ x_{4} & 0 & 0 & 1 & 0 & 1500 & 3 & 500 \\ \end{array}\\ \\ \begin{array}{r|rr} x_N & \color{green} x_{1} & x_{2} \\ \hline c_N^T & \color{green} 10 & 5 \\ \hline y^T A_N & \color{green} 0 & 0 \\ \hline c_N^T - y^T A_N & \color{green} 10 & 5 \\ \end{array} \end{array} """ "|r" if entering is not None else "", "|r" if show_ratios else "")) headers.append(r"\multicolumn{%d}{c||}{B^{-1}}" % m) else:
lines.append(r"\hline") make_line("B^{-1}_{%s} A_N" % latex(leaving), self.leaving_coefficients()) lines.append(r"\hline") ratios = self.dual_ratios() make_line(r"\hbox{Ratio}", [ratios.pop(0)[0] if ratios and ratios[0][1] == x else "" for x in x_N])
r""" Return auxiliary output before the update step.
In addition to generic output, show matrices for updating B-inverse.
INPUT:
- ``direction`` -- a string specifying the type of the simplex method used, either "primal" or "dual"
OUTPUT:
- :class:`~sage.misc.html.HtmlFragment`.
TESTS::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.revised_dictionary() sage: D.enter(1) sage: D.leave(4) sage: D._preupdate_output("primal") Entering: $x_{1}$. Leaving: $x_{4}$. \begin{equation*} B_\mathrm{new}^{-1} = E^{-1} B_\mathrm{old}^{-1} = \left(\begin{array}{rr} 1 & -\frac{1}{3} \\ 0 & \frac{1}{3} \end{array}\right) \left(\begin{array}{rr} 1 & 0 \\ 0 & 1 \end{array}\right) \end{equation*} """ super(LPRevisedDictionary, self)._preupdate_output(direction), r"\begin{equation*}", r"B_\mathrm{new}^{-1} = E^{-1} B_\mathrm{old}^{-1} = ", latex(self.E_inverse()), latex(self.B_inverse()), r"\end{equation*}"]))
r""" Return the column of constraint coefficients corresponding to ``v``.
INPUT:
- ``v`` -- a variable, its name, or its index
OUTPUT:
- a vector
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(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) """ else:
r""" Return the `A_N` matrix, constraint coefficients of non-basic variables.
OUTPUT:
- a matrix
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.revised_dictionary() sage: D.A_N() [1 1] [3 1] """ [self.A(x) for x in self.x_N()])
r""" Return the `B` matrix, i.e. constraint coefficients of basic variables.
OUTPUT:
- a matrix
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.revised_dictionary(1, 2) sage: D.B() [1 1] [3 1] """ [self.A(x) for x in self._x_B])
r""" Return the inverse of the :meth:`B` matrix.
This inverse matrix is stored and computed during dictionary update in a more efficient way than generic inversion.
OUTPUT:
- a matrix
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.revised_dictionary(1, 2) sage: D.B_inverse() [-1/2 1/2] [ 3/2 -1/2] """
r""" Return the eta matrix between ``self`` and the next dictionary.
OUTPUT:
- a matrix
If `B_{\mathrm{old}}` is the current matrix `B` and `B_{\mathrm{new}}` is the `B` matrix of the next dictionary (after the update step), then `B_{\mathrm{new}} = B_{\mathrm{old}} E`.
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.revised_dictionary() sage: D.enter(1) sage: D.leave(4) sage: D.E() [1 1] [0 3] """ raise ValueError("entering variable must be set to compute the " "eta matrix") raise ValueError("leaving variable must be set to compute the " "eta matrix")
r""" Return the inverse of the matrix :meth:`E`.
This inverse matrix is computed in a more efficient way than generic inversion.
OUTPUT:
- a matrix
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(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] """ raise ValueError("eta matrix is not invertible due to incompatible " "choice of entering and leaving variables")
r""" Return a dictionary with an additional row based on a given dictionary.
The implementation of this method for revised dictionaries adds a new inequality constraint to the problem, in which the given `basic_variable` becomes the slack variable. The resulting dictionary (with `basic_variable` added to the basis) will have the given `nonbasic_coefficients` and `constant` as a new row.
INPUT:
- ``nonbasic_coefficients``-- a list of the coefficients for the new row (with which nonbasic variables are subtracted in the relation for the new basic variable)
- ``constant``-- the constant term for the new row
- ``basic_variable``-- (default: depends on :func:`style`) a string giving the name of the basic variable of the new row
OUTPUT:
- a :class:`revised dictionary <LPRevisedDictionary>`
EXAMPLES::
sage: A = ([-1, 1111, 3, 17], [8, 222, 7, 6], ....: [3, 7, 17, 5], [9, 5, 7, 3]) sage: b = (2, 17, 11, 27) sage: c = (5/133, 1/10, 1/18, 47/3) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.final_revised_dictionary() sage: D1 = D.add_row([7, 11, 13, 9], 42) sage: D1.row_coefficients("x9") (7, 11, 13, 9) sage: D1.constant_terms()[-1] 42 sage: D1.basic_variables()[-1] x9
sage: A = ([-9, 7, 48, 31, 23], [5, 2, 9, 13, 98], ....: [14, 15, 97, 49, 1], [9, 5, 7, 3, 17], ....: [119, 7, 121, 5, 111]) sage: b = (33, 27, 1, 272, 61) sage: c = (51/133, 1/100, 149/18, 47/37, 13/17) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.revised_dictionary("x1", "x2", "x3", "x4", "x5") sage: D2 = D.add_row([5 ,7, 11, 13, 9], 99, basic_variable='c') sage: D2.row_coefficients("c") (5, 7, 11, 13, 9) sage: D2.constant_terms()[-1] 99 sage: D2.basic_variables()[-1] c
sage: D = P.revised_dictionary(0, 1, 2, 3, 4) sage: D.add_row([1, 2, 3, 4, 5, 6], 0) Traceback (most recent call last): ... ValueError: the sum of coefficients of nonbasic slack variables has to be equal to -1 when inserting a row into a dictionary for the auxiliary problem sage: D3 = D.add_row([1, 2, 3, 4, 5, -15], 0) sage: D3.row_coefficients(11) (1, 2, 3, 4, 5, -15) """ # Split nonbasic_coefficients into decision and slack parts # Extra -1 is due to the auxiliary variable at index 0 else: "the sum of coefficients of nonbasic slack variables has to " "be equal to -1 when inserting a row into a dictionary for " "the auxiliary problem") constant - nbc_slack * P.b(), basic_variable)
r""" Return the basic indices of ``self``.
.. NOTE::
Basic indices are indices of :meth:`basic_variables` in the list of generators of the :meth:`~InteractiveLPProblemStandardForm.coordinate_ring` of the :meth:`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:
- a list.
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.revised_dictionary() sage: D.basic_indices() [3, 4] """
r""" Return the basic variables of ``self``.
OUTPUT:
- a vector
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.revised_dictionary() sage: D.basic_variables() (x3, x4) """
r""" Return the `c_B` vector, objective coefficients of basic variables.
OUTPUT:
- a vector
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.revised_dictionary(1, 2) sage: D.c_B() (10, 5) """ else:
r""" Return the `c_N` vector, objective coefficients of non-basic variables.
OUTPUT:
- a vector
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.revised_dictionary() sage: D.c_N() (10, 5) """ else: for k in self.nonbasic_indices()))
r""" Return the coefficients of a nonbasic variable.
INPUT:
- ``v`` -- a nonbasic variable of ``self``, can be given as a string, an actual variable, or an integer interpreted as the index of a variable
OUTPUT:
- a vector
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.revised_dictionary() sage: D.column_coefficients(1) (1, 3) """ raise ValueError("variable must be nonbasic")
r""" Return constant terms in the relations of ``self``.
OUTPUT:
- a vector
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.revised_dictionary() sage: D.constant_terms() (1000, 1500) """
r""" Return a regular LP dictionary matching ``self``.
OUTPUT:
- an :class:`LP dictionary <LPDictionary>`
EXAMPLES::
sage: A = ([1, 1], [3, 1], [-1, -1]) sage: b = (1000, 1500, -400) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.revised_dictionary() sage: D.dictionary() LP problem dictionary (use typeset mode to see details) """ self.constant_terms(), self.objective_coefficients(), self.objective_value(), self.basic_variables(), self.nonbasic_variables(), self.problem().objective_name())
r""" Return the non-basic indices of ``self``.
.. NOTE::
Non-basic indices are indices of :meth:`nonbasic_variables` in the list of generators of the :meth:`~InteractiveLPProblemStandardForm.coordinate_ring` of the :meth:`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:
- a list
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.revised_dictionary() sage: D.nonbasic_indices() [1, 2] """
r""" Return non-basic variables of ``self``.
OUTPUT:
- a vector
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.revised_dictionary() sage: D.nonbasic_variables() (x1, x2) """
r""" Return coefficients of the objective of ``self``.
OUTPUT:
- a vector
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 = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.revised_dictionary() sage: D.objective_coefficients() (10, 5) """
r""" Return the objective name of ``self``.
OUTPUT:
- a symbolic expression
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.revised_dictionary() sage: D.objective_name() z """
r""" Return the value of the objective at the basic solution of ``self``.
OUTPUT:
- a number
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.revised_dictionary() sage: D.objective_value() 0 """ self.problem().objective_constant_term())
r""" Return the original problem.
OUTPUT:
- an :class:`LP problem in standard form <InteractiveLPProblemStandardForm>`
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.revised_dictionary() sage: D.problem() is P True """
r""" Return the coefficients of the basic variable ``v``.
These are the coefficients with which nonbasic variables are subtracted in the relation for ``v``.
INPUT:
- ``v`` -- a basic variable of ``self``, can be given as a string, an actual variable, or an integer interpreted as the index of a variable
OUTPUT:
- a vector of coefficients of a basic variable
EXAMPLES::
sage: A = ([-1, 1], [8, 2]) sage: b = (2, 17) sage: c = (55/10, 21/10) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.revised_dictionary() sage: D.row_coefficients("x3") (-1, 1)
We can also use indices of variables::
sage: D.row_coefficients(3) (-1, 1)
Or variable names without quotes after injecting them::
sage: P.inject_variables() Defining x0, x1, x2, x3, x4 sage: D.row_coefficients(x3) (-1, 1) """ raise ValueError("variable must be basic")
r""" 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 = InteractiveLPProblemStandardForm(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 """ # Update the inverse of B first, in case it is impossible # Now update the rest and clear settings
r""" Return the `y` vector, the product of :meth:`c_B` and :meth:`B_inverse`.
OUTPUT:
- a vector
EXAMPLES::
sage: A = ([1, 1], [3, 1]) sage: b = (1000, 1500) sage: c = (10, 5) sage: P = InteractiveLPProblemStandardForm(A, b, c) sage: D = P.revised_dictionary() sage: D.y() (0, 0) """
# Aliases for the standard notation |