In dirkdegel/simplexR: Simplex Algorithm

library(simplexR)

source("_gMOIP_functions.R")

Standard Case

--- Werners, Brigitte - Grundlagen des Operations Research (p. 60)

$$ \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 \ & x_1,& & x_2 & \geq & 0 \end{array} $$

# standard case
# optimal solution: x = (7, 8), z = 37

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

b <- c(22, 23, 40)
c <- c(3, 2)

simplexR(A, b, c)

# visualisation
plot_linear_program(A = A, b = b, obj = c, crit = "max", plotOptimum = TRUE, labels = "coord")

Standard Case---Exponential Time Complexity

$$ \begin{array}{rrcrcr} \max & 2x_1 & + & 1x_2 & \ s.t. & 1x_1 & & & \leq & 5 \ & 4x_1 & + & 1x_2 & \leq & 25 \ & x_1,& & x_2 & \geq & 0 \end{array} $$

# standard case
# optimal solution: x = (0, 25), z = 25

A <- matrix(c(
  1, 0,
  4, 1
), nrow = 2, ncol = 2, byrow = TRUE, dimnames = list(c("R1", "R2"), c("x1", "x2")))

b <- c(5, 25)
c <- c(2, 1)

simplexR(A, b, c)

# visualisation
plot_linear_program(A = A, b = b, obj = c, crit = "max", plotOptimum = TRUE, labels = "coord")

Unbounded Feasible Region, Optimal Solution

$$ \begin{array}{rrcrcr} \max &-2x_1 & + & 3x_2 & \ s.t. &-1x_1 & + & 1x_2 & \leq & 2 \ &-1x_1 & + & 2x_2 & \leq & 6 \ & & & 1x_2 & \leq & 5 \ & x_1,& & x_2 & \geq & 0 \end{array} $$

# unbounded feasible region, optimal solution exists
# optimal solution: x = (2, 4), z = 8

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

b <- c(2, 6, 5)
c <- c(-2, 3)

simplexR(A, b, c)

# visualisation is a bit wrong!
plot_linear_program(A = A, b = b, obj = c, crit = "max", plotOptimum = TRUE, labels = "coord")

Unbounded Feasible Region, no Optimal Solution

--- Werners, Brigitte - Grundlagen des Operations Research (p. 60)

$$ \begin{array}{rrcrcr} \max & 2x_1 & + & 4x_2 & \ s.t. &-2x_1 & + & 3x_2 & \leq & 12 \ &-1x_1 & + & 3x_2 & \leq & 18 \ & x_1,& & x_2 & \geq & 0 \end{array} $$

# unbounded feasible region, no optimal solution exists

A <- matrix(c(
  -2, 3,
  -1, 3
), nrow = 2, ncol = 2, byrow = TRUE, dimnames = list(c("R1", "R2"), c("x1", "x2")))

b <- c(12, 18)
c <- c(2, 4)

simplexR(A, b, c)

Dual Degeneracy

--- Werners, Brigitte - Grundlagen des Operations Research (p. 62)

$$ \begin{array}{rrcrcr} \max & 3x_1 & + &1.5x_2 & \ s.t. & 2x_1 & + & 1x_2 & \leq & 22 \ & 1x_1 & + & 2x_2 & \leq & 23 \ & 4x_1 & + & 1x_2 & \leq & 40 \ & x_1,& & x_2 & \geq & 0 \end{array} $$

# dual degeneracy
# optimal solution: x = (9, 4), z = 33
# optimal solution: x = (7, 8), z = 33

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

b <- c(22, 23, 40)
c <- c(3, 1.5)

simplexR(A, b, c)

# visualisation
plot_linear_program(A = A, b = b, obj = c, crit = "max", plotOptimum = TRUE, labels = "coord")

Primal Degeneracy

--- Werners, Brigitte - Grundlagen des Operations Research (p. 65)

$$ \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 \ & 2x_1 & + & 0.75x_2 & \leq & 21 \ & x_1,& & x_2 & \geq & 0 \end{array} $$

# primal degeneracy
# optimal solution: x = (7, 8), z = 37

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

b <- c(22, 23, 40, 21)
c <- c(3, 2)

simplexR(A, b, c)

# visualisation
plot_linear_program(A = A, b = b, obj = c, crit = "max", plotOptimum = TRUE, labels = "coord")

dirkdegel/simplexR documentation built on Feb. 22, 2020, 11:25 a.m.