\(\newcommand{\W}[1]{ \; #1 \; }\) \(\newcommand{\R}[1]{ {\rm #1} }\) \(\newcommand{\B}[1]{ {\bf #1} }\) \(\newcommand{\D}[2]{ \frac{\partial #1}{\partial #2} }\) \(\newcommand{\DD}[3]{ \frac{\partial^2 #1}{\partial #2 \partial #3} }\) \(\newcommand{\Dpow}[2]{ \frac{\partial^{#1}}{\partial {#2}^{#1}} }\) \(\newcommand{\dpow}[2]{ \frac{ {\rm d}^{#1}}{{\rm d}\, {#2}^{#1}} }\)

simplex_method

View page source

abs_normal: Solve a Linear Program Using Simplex Method

Syntax

ok = simplex_method ( level , b , A , c , maxitr , xout )

Prototype

template <class Vector>
bool simplex_method(
   size_t        level   ,
   const Vector& A       ,
   const Vector& b       ,
   const Vector& c       ,
   size_t        maxitr  ,
   Vector&       xout    )

Source

This following is a link to the source code for this example: simplex_method.hpp .

Problem

We are given \(A \in \B{R}^{m \times n}\), \(b \in \B{R}^m\), \(c \in \B{R}^n\). This routine solves the problem

\[\begin{split}\begin{array}{rl} \R{minimize} & g^T x \; \R{w.r.t} \; x \in \B{R}_+^n \\ \R{subject \; to} & A x + b \leq 0 \end{array}\end{split}\]

Vector

The type Vector is a simple vector with elements of type double .

level

This value is less than or equal two. If level == 0 , no tracing is printed. If level >= 1 , a trace \(x\) and the corresponding objective \(z\) is printed at each iteration. If level == 2 , a trace of the simplex Tableau is printed at each iteration.

A

This is a row-major representation of the matrix \(A\) in the problem.

b

This is the vector \(b\) in the problem.

c

This is the vector \(c\) in the problem.

maxitr

This is the maximum number of simplex iterations to try before giving up on convergence.

xout

This argument has size is n and the input value of its elements does no matter. Upon return it is the primal variables corresponding to the problem solution.

ok

If the return value ok is true, a solution has been found.

Example

The file simplex_method.cpp contains an example and test of simplex_method .