Form the dual of a linear program and certify a pair of solutions

No linear program is SOLVED here. Duality is a certificate: a feasible primal and dual with equal objectives are optimal, and gap is otherwise the exact distance from optimality. Complementary slackness is reported per constraint and per variable.

Usage

Lpdual(A, b, c, x = NULL, y = NULL)

Arguments

A

Constraint matrix.

b

Right-hand side.

c

Objective coefficients.

x

Candidate primal solution.

y

Candidate dual solution.

Value

List with dual_A, dual_b, dual_c, primal_objective, dual_objective, gap, primal_feasible, dual_feasible, optimal, slack, surplus, cs_constraint, cs_variable, m, n.

Details

Formula: primal max c'x s.t. A x <= b, x >= 0; dual min b'y s.t. A'y >= c, y >= 0; weak duality c'x <= b'y

References

von Neumann, J. (1947), Discussion of a maximum problem, Institute for Advanced Study, reprinted in Collected Works VI, 89-95 – the first statement of linear programming duality. Gale, Kuhn & Tucker (1951), Linear programming and the theory of games, 317-329, for the first published proof.

Examples

# maximise 3 x1 + 5 x2 s.t. x1 <= 4, 2 x2 <= 12, 3 x1 + 2 x2 <= 18; optimum x = (2, 6), y = (0, 1.5, 1)
A <- rbind(c(1, 0), c(0, 2), c(3, 2))
Lpdual(A, b = c(4, 12, 18), c = c(3, 5), x = c(2, 6), y = c(0, 1.5, 1))[c("gap", "optimal")]
#> $gap
#> [1] 0
#> 
#> $optimal
#> [1] 1
#>