Explicit LP Solving Functions#

Each explicit LP solving function takes four arguments to represent an LP problem in \(n\) variables with \(m\) constraints:

1: LHS : \(m \times n\) matrix, representing the left-hand-side coefficients of the \(m\) constraints.
2: relations : \(m \times 1\) matrix over the same ring as LHS, representing the relations for each constraint, with a positive entry representing \(\ge\), a zero entry representing \(=\), and a negative entry representing \(\le\).
3: RHS : \(m \times 1\) matrix over the same ring as LHS, representing the right-hand-side values of the \(m\) constraints.
4: objective : \(1 \times n\) matrix over the same ring as LHS, representing the coefficients of the objective function to be optimised.

Each function returns a vector representing an optimal solution to the problem, and an integer indicating the state of the solution, as described in the introduction.

MaximalSolution(LHS, relations, RHS, objective): Mtrx, Mtrx, Mtrx, Mtrx -> Mtrx, RngIntElt#: The vector maximising the LP problem, with an integer describing the state of the solution.

MinimalSolution(LHS, relations, RHS, objective): Mtrx, Mtrx, Mtrx, Mtrx -> Mtrx, RngIntElt#: The vector minimising the LP problem, with an integer describing the state of the solution.

MaximalIntegerSolution(LHS, relations, RHS, objective): Mtrx, Mtrx, Mtrx, Mtrx -> Mtrx, RngIntElt#: The integer vector maximising the LP problem, with an integer describing the state of the solution.

MinimalIntegerSolution(LHS, relations, RHS, objective): Mtrx, Mtrx, Mtrx, Mtrx -> Mtrx, RngIntElt#: The integer vector minimising the LP problem, with an integer describing the state of the solution.

MaximalZeroOneSolution(LHS, relations, RHS, objective): Mtrx, Mtrx, Mtrx, Mtrx -> Mtrx, RngIntElt#: The vector with each entry either zero or one maximising the LP problem, with an integer describing the state of the solution.

MinimalZeroOneSolution(LHS, relations, RHS, objective): Mtrx, Mtrx, Mtrx, Mtrx -> Mtrx, RngIntElt#: The vector with each entry either zero or one minimising the LP problem, with an integer describing the state of the solution.

Example: Explicit LP Solutions One (ex-807d41)#

We solve the LP maximising \(F(x, y) = 8x + 15y \quad x, y \in {\bf R}\) subject to the constraints \(10x + 21y \le 156\) \(2x + y \le 22\)

> R := RealField( );
> lhs := Matrix(R, 2, 2, [10, 21, 2, 1]);
> rhs := Matrix(R, 2, 1, [156, 22]);
> rel := Matrix(R, 2, 1, [-1, -1]); // negative values - less-or-equal relation
> obj := Matrix(R, 1, 2, [8, 15]);
> MaximalSolution(lhs, rel, rhs, obj);
[9.562500000000000000 2.875000000000000888]
0

Run in calculator

Example: Explicit LP Solutions Two (ex-33e772)#

We find solutions to the LP maximising \(F(x_1, \cdots, x_7) = 592x_1 + 381x_2 + 273x_3 + 55x_4 + 48x_5 + 37x_6 + 23x_7\) subject to the constraint \(3534x_1 + 2356x_2 + 2767x_3 + 589x_4 + 528x_5 + 451x_6 + 304x_7 \le 119567\) with \((x_1, \cdots, x_7)\) taking real values, integer values, and zero/one values.

> R := RealField( );
> lhs := Matrix(R, 1, 7, [3534, 2356, 2767, 589, 528, 451, 304]);
> rhs := Matrix(R, 1, 1, [119567]);
> rel := Matrix(R, 1, 1, [-1]);
> obj := Matrix(R, 1, 7, [592, 381, 273, 55, 48, 37, 23]);
> MaximalSolution(lhs, rel, rhs, obj);
[33.83333333333333570 0.E-92 0.E-92 0.E-92 0.E-92 0.E-92 0.E-92]
0
> MaximalIntegerSolution(lhs, rel, rhs, obj);
[33.00000000000000000 1.000000000000000000 0.E-92 1.000000000000000000 0.E-92
    0.E-92 0.E-92]
0
> MaximalZeroOneSolution(lhs, rel, rhs, obj);
[1.000000000000000000 1.000000000000000000 1.000000000000000000
    1.000000000000000000 1.000000000000000000 1.000000000000000000
    1.000000000000000000]
0

Run in calculator