The GLPK problem form, minimise c'x subject to Ax <= b and x >= 0, solved by the textbook primal simplex on the slack tableau with Bland's rule so the iteration cannot cycle. A row with a negative right-hand side is multiplied by -1 and given an artificial variable; phase one minimises the sum of the artificials, and a positive minimum means no x satisfies the constraints (status "infeasible"). Artificials left in the basis at zero are pivoted out where the row allows, then phase two minimises c'x from that feasible basis. When every b is non-negative the origin is feasible and phase one is skipped. The final objective row carries the simplex multipliers (negated, since the row is updated by subtraction): y = -z on the slack columns, the same for flipped rows because their slack column is flipped too, so strong duality c'x = b'y is available as a check.
Value
List with estimate, x, objective,
dual, dual_objective, iterations,
status ("optimal", "unbounded", "infeasible" or
"iteration_limit"), n, method. x and the
objective are NA unless the status is "optimal".
Details
Formula: phase one min 1'a over (sA | sI | I_flip)(x; s; a) = s b; phase two pivots until every reduced cost is non-negative; x* from the basis, y* from the objective row.
References
Makhorin, GNU Linear Programming Kit reference manual; Bland (1977), Mathematics of Operations Research 2(2):103-107. doi:10.1287/moor.2.2.103 ; Dantzig, Orden and Wolfe (1955), Pacific Journal of Mathematics 5(2):183-195 (the two-phase method).
Examples
Glpopt(c = c(-1, -2), A = matrix(c(1, 1, 1, 0, 0, 1), 3, 2, byrow = TRUE),
b = c(4, 2, 3))
#> $estimate
#> [1] -7
#>
#> $x
#> [1] 1 3
#>
#> $objective
#> [1] -7
#>
#> $dual
#> [1] -1 0 -1
#>
#> $dual_objective
#> [1] -7
#>
#> $iterations
#> [1] 3
#>
#> $status
#> [1] "optimal"
#>
#> $n
#> [1] 2
#>
#> $method
#> [1] "two-phase primal simplex with Bland's rule"
#>
#> attr(,"class")
#> [1] "morie_rich_result" "list"
# x1 + x2 >= 2 written as -x1 - x2 <= -2 needs phase one
Glpopt(c = c(1, 3), A = rbind(c(-1, -1), c(1, 0)), b = c(-2, 5))$x
#> [1] 2 0