Skip to content

An implementation of Simplex algorithm based on the UWaterloo CO250 textbook "A Gentle Introduction to Optimization" by Guenin, Konemann, and Tuncel

Notifications You must be signed in to change notification settings

bryanzang/UW-co250-Simplex

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

40 Commits
 
 
 
 

Repository files navigation

Note

This is only for educational purposes, all credits go towards the authors of the book

Currently Included Content

  • Formation of LP of form $Ax\text{ ? }b$ with objective function vector and equality constraints ($?$ can denote $=$, $\geq$, or $\leq$)
  • Canonical form computation for given LP and proposed basis
  • Simplex computation for given LP
  • Two-phase Simplex computation for given LP
  • Duality transformation for given LP

To be added

  • complementary slack conditions
  • other algorithms included in the textbook (?)

Example Usage

formulating an LP simple case:

$$\max\left\{z(x)=v^{\top} x:Ax=b,x\geq 0 \right\}$$

where

$$A=\begin{pmatrix} 1&1&-3&1&2\\ 0&1&-2&2&-2\\ -2&-1&4&1&0 \end{pmatrix},\quad b=\begin{pmatrix} 7\\ -2\\ -3 \end{pmatrix},\quad v=\begin{pmatrix} -1\\ 0\\ 3\\ 7\\ -1 \end{pmatrix}$$

A <- rbind(
  c(1,1,-3,1,2),
  c(0,1,-2,2,-2),
  c(-2,-1,4,1,0)
)
b <- c(7,-2,-3)
v <- c(-1,0,3,7,-1)
LP <- form.LP(b=b, A=A, v=v)

formulating an LP with basis $B=\{1,4\}$ and initial $z$ value of $3$:

$$\begin{aligned} &\max\qquad 3 + \begin{pmatrix}0 & -1 & -2 & 0 & -3\end{pmatrix}x\\ \text{s.t.}\qquad&\\ &\begin{pmatrix} 1 & -2 & 1 & 0 & 2\\ 0 & 1 & -1 & 1 & 3 \end{pmatrix}x=\begin{pmatrix} 2\\ 4 \end{pmatrix}\\ &\quad x \geq 0 \end{aligned}$$

B <- c(1,4)
A <- rbind(
  c(1,-2,1,0,2),
  c(0,1,-1,1,3)
)
b <- c(2,4)
v <- c(0,-1,-2,0,-3)
z <- 3
LP <- form.LP(B, b, A, v, z)

optimal solution exists for raw Simplex with given basis $B=\{3,5\}$:

$$\begin{aligned} &\max\qquad \begin{pmatrix}-1 & 3 & -5 & 9 & 3\end{pmatrix}x\\ \text{s.t.}\qquad&\\ &\begin{pmatrix} 4 & 1& 3 & -1 & -2\\ 3 & 1 & 2 & 0 & -1 \end{pmatrix}x=\begin{pmatrix} 2\\ 3 \end{pmatrix}\\ &\quad x \geq 0 \end{aligned}$$

B <- c(3,5)
A <- rbind(
  c(4,1,3,-1,-2),
  c(3,1,2,0,-1)
)
b <- c(2,3)
v <- c(-1,3,-5,9,3)
LP <- form.LP(B, b, A, v)
simplex(LP)

unbounded LP under raw Simplex with basis $B=\{2,3,5,6\}$:

$$\begin{aligned} &\max\qquad \begin{pmatrix}0 & 7 & -8 & -2 & -4 & -6\end{pmatrix}x\\ \text{s.t.}\qquad&\\ &\begin{pmatrix} 0 & -2 & 2 & 1 & 1 & 1 \\ 2 & -3 & 3 & 0 & 2 & 4 \\ 4 & -2 & 4 & -2 & 1 & 2 \\ 3 & 4 & -3 & -4 & -2 & -1 \end{pmatrix}x=\begin{pmatrix} 1\\ 9\\ 6\\ 2 \end{pmatrix}\\ &\quad x \geq 0 \end{aligned}$$

B <- c(2,3,5,6)
A <- rbind(
  c(0,-2,2,1,1,1),
  c(2,-3,3,0,2,4),
  c(4,-2,4,-2,1,2),
  c(3,4,-3,-4,-2,-1)
)
b <- c(1,9,6,2)
v <- c(0,7,-8,-2,-4,-6)
LP <- form.LP(B, b, A, v)
simplex(LP)

optimal solution exists under two-phase Simplex:

$$\begin{aligned} &\max\qquad \begin{pmatrix}2 & -1 & 2\end{pmatrix}x\\ \text{s.t.}\qquad&\\ &\begin{pmatrix} -1 & -2 & 1 \\ 1 & -1 & 1 \end{pmatrix}x=\begin{pmatrix} -1\\ 3 \end{pmatrix}\\ &\quad x \geq 0 \end{aligned}$$

A <- rbind(
  c(-1,-2,1),
  c(1,-1,1)
)
b <- c(-1,3)
v <- c(2,-1,2)
LP <- form.LP(b=b, A=A, v=v)
twophase(LP)

finding dual of given LP simple case:

$$\begin{aligned} &\max\qquad \begin{pmatrix}28 & -7 & 20\end{pmatrix}x\\ \text{s.t.}\qquad&\\ &\begin{pmatrix} 6 & -2 & 1 \\ -1 & 1 & 2 \\ 4 & -1 & 3 \end{pmatrix}x\leq\begin{pmatrix} 3\\ 3\\ 3 \end{pmatrix}\\ &\quad x \geq 0 \end{aligned}$$

A <- rbind(
  c(6,-2,1),
  c(-1,1,2),
  c(4,-1,3)
)
b <- c(3,3,3)
v <- c(28,-7,20)
LP <- form.LP(b=b, A=A, v=v, A.c=rep('<=',3))
dual(LP)

finding dual of given LP complex case:

$$\begin{aligned} &\min\qquad \begin{pmatrix}53 & 52 & 51 & 54 & 55\end{pmatrix}x\\ \text{s.t.}\qquad&\\ &\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 6 & 7 & 8 & 9 & 10 \\ 11 & 12 & 13 & 14 & 15 \end{pmatrix}x\text{ }\begin{matrix} =\\ \geq\\ \geq \end{matrix}\begin{pmatrix} 9\\ 15\\ 29 \end{pmatrix}\\ &\\ &\quad x_1\geq0,x_2\geq0,x_3\leq0,x_4\leq0,x_5\text{ free} \end{aligned}$$

A <- matrix(1:15, ncol=5, nrow=3, byrow=T)
b <- c(9, 15, 29)
v <- c(53, 52, 51, 54, 55)
LP <- form.LP(b=b, A=A, v=v, A.c=c('=','>=','>='), x.c=c('>=0','>=0','<=0','<=0','free'))
dual(LP, opt=0)

About

An implementation of Simplex algorithm based on the UWaterloo CO250 textbook "A Gentle Introduction to Optimization" by Guenin, Konemann, and Tuncel

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages