linProg¶

Solves a linear programming problem using the revised simplex algorithm.

NOTE: The function linProg has generally been superseded by the function linearProgramming. Function linProg remains in place to ensure compatibility of existing calls.

Synopsis¶

linProg (a, b, c)

Required Arguments¶

float a[[]] (Input): Array of size m × n containing a matrix with coefficients of the m constraints.
float b[] (Input): Array with m components containing the right-hand side of the constraints; if there are limits on both sides of the constraints, then b contains the lower limit of the constraints.
float c[] (Input): Array with n components containing the coefficients of the objective function.

Return Value¶

The solution x of the linear programming problem. If no solution can be computed, then None is returned.

Optional Arguments¶

upperLimit, float[] (Input)

Array with m components containing the upper limit of the constraints that have both the lower and the upper bounds. If no such constraint exists, then upperLimit is not needed.

constrType, int[] (Input)

Array with m components indicating the types of general constraints in the matrix a. Let \(r_i=a_{i1} x_1+\ldots+a_{in} x_n\). Then, the value of constrType(i) signifies the following:

`constrType(i)`	Constraint
0	\(r_i=b_i\)
1	\(r_i\leq upperLimit_i\)
2	\(r_i\geq b_i\)
3	\(b_i\leq r_i\leq upperLimit_i\)

Default: constrType = 0

lowerBound, float[] (Input)

Array with n components containing the lower bound on the variables. If there is no lower bound on a variable, then \(10^{30}\) should be set as the lower bound.

Default: lowerBound = 0

upperBound, float[] (Input)

Array with n components containing the upper bound on the variables. If there is no upper bound on a variable, then \(-10^{30}\) should be set as the upper bound.

Default: upperBound = ∞

maxItn, int (Input)

Maximum number of iterations.

Default: maxItn = 10000

obj (Output)

Optimal value of the objective function.

dual (Output)

An array with m components containing the dual solution. On return, the necessary space is allocated by linProg.

Description¶

The function linProg uses a revised simplex method to solve linear programming problems, i.e., problems of the form

\[\begin{split}\begin{array}{llc} \min\limits_{x \in R^n} c^T x & \text{ subject to } & b_l \leq A_x \leq b_u \\ & & x_l \leq x \leq x_u \\ \end{array}\end{split}\]

where c is the objective coefficient vector, A is the coefficient matrix, and the vectors \(b_l\), \(b_u\), \(x_l\), and \(x_u\) are the lower and upper bounds on the constraints and the variables, respectively.

For a complete description of the revised simplex method, see Murtagh (1981) or Murty (1983).

Examples¶

Example 1¶

The linear programming problem in the standard form

\[\begin{split}\text{subject to } \begin{array}{l} \min f(x) = -x_1 -3_{x_2} \\ \begin{array}{lrrrrr} x_1 & +x_2 & +x_3 & & & & =1.5 \\ x_1 & +x_2 & & -x_4 & & & =0.5\\ x_1 & & & & +x_5 & & =1.0 \\ & x_2 & & & & +x_6 & =1.0 \\ \end{array} \\ x_i \geq 0, \text{ for } i = 1, \ldots, 6 \end{array}\end{split}\]

is solved.

from numpy import *
from pyimsl.math.linProg import linProg
from pyimsl.math.writeMatrix import writeMatrix


m = 4
n = 6
a = [[1., 1., 1., 0., 0., 0.],
     [1., 1., 0., -1., 0., 0.],
     [1., 0., 0., 0., 1., 0.],
     [0., 1., 0., 0., 0., 1.]]
b = [1.5, 0.5, 1.0, 1.0]
c = [-1., -3., 0., 0., 0., 0.]

# Solve the LP problem
x = linProg(a, b, c)

# Print x
writeMatrix("x", x)

Output¶

 
                                      x
          1            2            3            4            5            6
        0.5          1.0          0.0          1.0          0.5          0.0

Example 2¶

The linear programming problem in the previous example can be formulated as follows:

\[\begin{split}\begin{array}{l} \min f(x) = -x_1 - 3x_2 \\ \text{subject to } \begin{array}[t]{l} 0.5 \leq x_1 + x_2 \leq 1.5 \\ 0 \leq x_1 \leq 1.0 \\ 0 \leq x_2 \leq 1.0 \\ \end{array} \\ \end{array}\end{split}\]

This problem can be solved more efficiently.

from __future__ import print_function
from numpy import *
from pyimsl.math.linProg import linProg
from pyimsl.math.writeMatrix import writeMatrix


irtype = (3,)
m = 1
n = 2
xub = (1.0, 1.0)
a = [[1.0, 1.0]]
b = (0.5,)
bu = [1.5]
c = (-1.0, -3.0)
d = []
obj = []

# Solve the LP problem
x = linProg(a, b, c,
            upperLimit=bu,
            constrType=irtype,
            upperBound=xub,
            dual=d,
            obj=obj)

# Print x
writeMatrix("x", x)

# Print d
writeMatrix("d", d)
print("obj = %g" % (obj[0]))

Output¶

obj = -3.5
 
            x
          1            2
        0.5          1.0
 
     d
         -1

Warning Errors¶

`IMSL_PROB_UNBOUNDED`	The problem is unbounded.
`IMSL_TOO_MANY_ITN`	Maximum number of iterations exceeded.
`IMSL_PROB_INFEASIBLE`	The problem is infeasible.

Fatal Errors¶

`IMSL_NUMERIC_DIFFICULTY`	Numerical difficulty occurred (moved to a vertex that is poorly conditioned). If float is currently being used, using double precision may help.
`IMSL_BOUNDS_INCONSISTENT`	The bounds are inconsistent.