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.