Examples --- Primal Simplex, Generic Form of LP • simplexR

Arbitrary Linear Programs

— Werners, Brigitte - Grundlagen des Operations Research (page 79)

\[ \begin{array}{rrcrcr} \max & 3x_1 & + & 2x_2 & \\ s.t. & 2x_1 & + & 1x_2 & \leq & 22 \\ & 1x_1 & + & 2x_2 & \leq & 23 \\ & 4x_1 & + & 1x_2 & \leq & 40 \\ & 1x_1 & + & 1x_2 & \geq & 5 \\ & 1x_1 & - & 1/3x_2 & = & 6 \\ & x_1,& & x_2 & \geq & 0 \end{array} \]

# See:  Werners Brigitte,  page 79
# optimal solution: x = (8, 6), z = 36

A <- matrix(c(
  2, 1,
  1, 2,
  4, 1,
  1, 1,
  1, -1/3
), nrow = 5, ncol = 2, byrow = TRUE, dimnames = list(c("R1", "R2", "R3", "R4", "R5"), c("x1", "x2")))

b <- c(22, 23, 40, 5, 6)
c <- c(3, 2)
sense <- 1
relation <- c("<=", "<=", "<=", ">=", "=")

canonical_tableau <- construct_tableau(A, b, c, sense, relation)

## [1] "Start constructing Simplex Tableau"
## [1] "Tableau constructed"
## [1] "Artificial variable 'v' added at column  7 and row  4  -> phase I algorithm required"
## [2] "Artificial variable 'v' added at column  8 and row  5  -> phase I algorithm required"
## [1] "BigM-method is used, with bigM = 1000"

canonical_tableau

##       x1           x2 s s s    s v v      b
## R1     2    1.0000000 1 0 0    0 0 0     22
## R2     1    2.0000000 0 1 0    0 0 0     23
## R3     4    1.0000000 0 0 1    0 0 0     40
## R4     1    1.0000000 0 0 0   -1 1 0      5
## R5     1   -0.3333333 0 0 0    0 0 1      6
## z  -2003 -668.6666667 0 0 0 1000 0 0 -11000

simplex(tableau = canonical_tableau)

## [1] "Initial Tableau (Tableau 0)"
##       x1           x2 s s s    s v v      b
## R1     2    1.0000000 1 0 0    0 0 0     22
## R2     1    2.0000000 0 1 0    0 0 0     23
## R3     4    1.0000000 0 0 1    0 0 0     40
## R4     1    1.0000000 0 0 0   -1 1 0      5
## R5     1   -0.3333333 0 0 0    0 0 1      6
## z  -2003 -668.6666667 0 0 0 1000 0 0 -11000
## [1] "--------------------------------------------------------------------"
## [1] "Iteration 1"
## [1] "--------------------------------------------------------------------"
## [1] "Pivot column: 1"
## [1] "Pivot row: 4"
## [1] "New tableau at the end of iteration 1"
##    x1          x2 s s s     s    v v    b
## R1  0   -1.000000 1 0 0     2   -2 0   12
## R2  0    1.000000 0 1 0     1   -1 0   18
## R3  0   -3.000000 0 0 1     4   -4 0   20
## R4  1    1.000000 0 0 0    -1    1 0    5
## R5  0   -1.333333 0 0 0     1   -1 1    1
## z   0 1334.333333 0 0 0 -1003 2003 0 -985
## [1] "--------------------------------------------------------------------"
## [1] "Iteration 2"
## [1] "--------------------------------------------------------------------"
## [1] "Pivot column: 6"
## [1] "Pivot row: 5"
## [1] "New tableau at the end of iteration 2"
##    x1         x2 s s s s    v    v  b
## R1  0  1.6666667 1 0 0 0    0   -2 10
## R2  0  2.3333333 0 1 0 0    0   -1 17
## R3  0  2.3333333 0 0 1 0    0   -4 16
## R4  1 -0.3333333 0 0 0 0    0    1  6
## R5  0 -1.3333333 0 0 0 1   -1    1  1
## z   0 -3.0000000 0 0 0 0 1000 1003 18
## [1] "--------------------------------------------------------------------"
## [1] "Iteration 3"
## [1] "--------------------------------------------------------------------"
## [1] "Pivot column: 2"
## [1] "Pivot row: 1"
## [1] "New tableau at the end of iteration 3"
##    x1 x2    s s s s    v     v  b
## R1  0  1  0.6 0 0 0    0  -1.2  6
## R2  0  0 -1.4 1 0 0    0   1.8  3
## R3  0  0 -1.4 0 1 0    0  -1.2  2
## R4  1  0  0.2 0 0 0    0   0.6  8
## R5  0  0  0.8 0 0 1   -1  -0.6  9
## z   0  0  1.8 0 0 0 1000 999.4 36
## [1] "--------------------------------------------------------------------"
## [1] "Status: End"
## [1] "--------------------------------------------------------------------"

Primal Degeneracy — Stalling and Cycling

— Examples from: Operations Research - Deterministische Modelle und Methoden - Stephan Dempe, Heiner Schreier, 1. Auflage September 2006, Wiesbaden

# See: Dempe/Schreier,  page 34
# primal degeneracy: stalling and cycling
# based on Beale (1955)

A <- matrix(c(
  1/4, -8, -1, 9,
  1/2, -12, -1/2, 3,
  0, 0, 1, 0
), nrow = 3, ncol = 4, byrow = TRUE, dimnames = list(c("R1", "R2", "R3"), c("x1", "x2", "x3", "x4")))

b <- c(0, 0, 1)
c <- c(3/4, -20, 1/2, -6)
sense <- 1
relation <- c("<=", "<=", "<=")

cycling_case <- construct_tableau(A, b, c, sense, relation)

## [1] "Start constructing Simplex Tableau"
## [1] "Tableau constructed"

cycling_case

##       x1  x2   x3 x4 s s s b
## R1  0.25  -8 -1.0  9 1 0 0 0
## R2  0.50 -12 -0.5  3 0 1 0 0
## R3  0.00   0  1.0  0 0 0 1 1
## z  -0.75  20 -0.5  6 0 0 0 0

simplex(tableau = cycling_case, max_iter = 7)

## [1] "Initial Tableau (Tableau 0)"
##       x1  x2   x3 x4 s s s b
## R1  0.25  -8 -1.0  9 1 0 0 0
## R2  0.50 -12 -0.5  3 0 1 0 0
## R3  0.00   0  1.0  0 0 0 1 1
## z  -0.75  20 -0.5  6 0 0 0 0
## [1] "--------------------------------------------------------------------"
## [1] "Iteration 1"
## [1] "--------------------------------------------------------------------"
## [1] "Pivot column: 1"
## [1] "Pivot row: 1"
## [1] "New tableau at the end of iteration 1"
##    x1  x2   x3  x4  s s s b
## R1  1 -32 -4.0  36  4 0 0 0
## R2  0   4  1.5 -15 -2 1 0 0
## R3  0   0  1.0   0  0 0 1 1
## z   0  -4 -3.5  33  3 0 0 0
## [1] "--------------------------------------------------------------------"
## [1] "Iteration 2"
## [1] "--------------------------------------------------------------------"
## [1] "Pivot column: 2"
## [1] "Pivot row: 2"
## [1] "New tableau at the end of iteration 2"
##    x1 x2     x3     x4     s    s s b
## R1  1  0  8.000 -84.00 -12.0 8.00 0 0
## R2  0  1  0.375  -3.75  -0.5 0.25 0 0
## R3  0  0  1.000   0.00   0.0 0.00 1 1
## z   0  0 -2.000  18.00   1.0 1.00 0 0
## [1] "--------------------------------------------------------------------"
## [1] "Iteration 3"
## [1] "--------------------------------------------------------------------"
## [1] "Pivot column: 3"
## [1] "Pivot row: 1"
## [1] "New tableau at the end of iteration 3"
##           x1 x2 x3       x4       s      s s b
## R1  0.125000  0  1 -10.5000 -1.5000  1.000 0 0
## R2 -0.046875  1  0   0.1875  0.0625 -0.125 0 0
## R3 -0.125000  0  0  10.5000  1.5000 -1.000 1 1
## z   0.250000  0  0  -3.0000 -2.0000  3.000 0 0
## [1] "--------------------------------------------------------------------"
## [1] "Iteration 4"
## [1] "--------------------------------------------------------------------"
## [1] "Pivot column: 4"
## [1] "Pivot row: 2"
## [1] "New tableau at the end of iteration 4"
##       x1         x2 x3 x4          s          s s b
## R1 -2.50  56.000000  1  0  2.0000000 -6.0000000 0 0
## R2 -0.25   5.333333  0  1  0.3333333 -0.6666667 0 0
## R3  2.50 -56.000000  0  0 -2.0000000  6.0000000 1 1
## z  -0.50  16.000000  0  0 -1.0000000  1.0000000 0 0
## [1] "--------------------------------------------------------------------"
## [1] "Iteration 5"
## [1] "--------------------------------------------------------------------"
## [1] "Pivot column: 5"
## [1] "Pivot row: 1"
## [1] "New tableau at the end of iteration 5"
##            x1 x2         x3 x4 s          s s b
## R1 -1.2500000 28  0.5000000  0 1 -3.0000000 0 0
## R2  0.1666667 -4 -0.1666667  1 0  0.3333333 0 0
## R3  0.0000000  0  1.0000000  0 0  0.0000000 1 1
## z  -1.7500000 44  0.5000000  0 0 -2.0000000 0 0
## [1] "--------------------------------------------------------------------"
## [1] "Iteration 6"
## [1] "--------------------------------------------------------------------"
## [1] "Pivot column: 6"
## [1] "Pivot row: 2"
## [1] "New tableau at the end of iteration 6"
##       x1  x2   x3 x4 s s s b
## R1  0.25  -8 -1.0  9 1 0 0 0
## R2  0.50 -12 -0.5  3 0 1 0 0
## R3  0.00   0  1.0  0 0 0 1 1
## z  -0.75  20 -0.5  6 0 0 0 0
## [1] "--------------------------------------------------------------------"
## [1] "Status: End"
## [1] "--------------------------------------------------------------------"

Examples — Primal Simplex, Generic Form of LP

Arbitrary Linear Programs

Primal Degeneracy — Stalling and Cycling

Contents