solve_lin

subroutine solve_lin(x, c, A, b, numle, numge, numeq)

Description:

This subroutine applies the simplex algorithm to solve a linear programming problem of the form
$$
begin{split}
min_{x in mathbb{R}^{n}} enspace &c^T cdot x\
text{s.t.}enspace &A_1 cdot x leq b_1\
&A_2 cdot x geq b_2\
&A_3 cdot x = b_3.
end{split}
$$
We thereby have
$$
c in mathbb{R}^n , A_1 in mathbb{R}^{m_1times n} , b_1 in mathbb{R}^{m_1} , A_2 in mathbb{R}^{m_2times n} , b_2 in mathbb{R}^{m_2} , A_3 in mathbb{R}^{m_3times n} , b_3 in mathbb{R}^{m_3}.
$$
Next to the coefficient vector (c), the input to this subroutine is a stacked matrix and a stacked vector
$$
A = begin{bmatrix} A_1\ A_2\ A_3end{bmatrix} quad text{and} quad b = begin{bmatrix} b_1\ b_2\ b_3end{bmatrix}.
$$
Note that the matrix and vector need to be stacked in exactly this order, meaning first the set of lower than or equality constraints, then the set of greater than or equality constraints and last the strict equality constraints.

Input arguments:

• real*8 :: c(:)
  The coefficients (c) of the linear program. Note that this one-dimensional array needs to have exactly the same length as the array x.
• real*8 :: A(:, :)
  The stacked coefficient matrix for the total set of constraints. Note that this two-dimensional array needs to have the length (m_1 + m_2 + m_3) in the first dimension and the same length as the array x in the second dimension.
• real*8 :: b(:)
  The stacked vector for the total set of constraints. Note that this one-dimensional array needs to have the length (m_1 + m_2 + m_3).
• integer :: numle
  This integer scalar tells the subroutine how many lower than or equality constraints (m_1) the linear program has.
• integer :: numge
  This integer scalar tells the subroutine how many greater than or equality constraints (m_2) the linear program has.
• integer :: numeq
  This integer scalar tells the subroutine how many strict equality constraints (m_3) the linear program has.

Output arguments:

• real*8 :: x(:)
  A one-dimensional array into which the subroutine stores the solution vector of the linear program.

References

• For further reading refer to:
  • Dantzig, G.B. & Thapa, M. N. (1997). Linear Programming 1: Introduction. New York: Springer Series in Operations Research and Financial Engineering.
• This routine is used in the following programs:
  • prog02_20.f90