linprog: Linear Programming Solver

View source: R/linprog.R

linprogR Documentation

Linear Programming Solver

Description

Solves simple linear programming problems, allowing for inequality and equality constraints as well as lower and upper bounds.

Usage

linprog(cc, A = NULL, b = NULL, Aeq = NULL, beq = NULL,
        lb = NULL, ub = NULL, x0 = NULL, I0 = NULL,
        bigM = 100, maxiter = 20, maximize = FALSE)

Arguments

cc

defines the linear objective function.

A

matrix representing the inequality constraints A x <= b.

b

vector, right hand side of the inequalities.

Aeq

matrix representing the equality constraints Aeq x <= beq.

beq

vector, right hand side of the inequalities.

lb

lower bounds, if not NULL must all be greater or equal 0.

ub

upper bounds, if not NULL must all be greater or equal lb.

x0

feasible base vector, will not be used at the moment.

I0

index set of x0, will not be used at the moment.

bigM

big-M constant, will be used for finding a base vector.

maxiter

maximum number of iterations.

maximize

logical; shall the objective be minimized or maximized?

Details

Solves linear programming problems of the form min cc' * x such that

A * x \le b

A_{eq} * x = b_{eq}

lb \le x \le ub

Value

List with

  • x the solution vector.

  • fval the value at the optimal solution.

  • errno, mesage the error number and message.

Note

This is a first version that will be unstable at times. For real linear programming problems use package lpSolve.

Author(s)

HwB <hwborchers@googlemail.com>

References

Vanderbei, R. J. (2001). Linear Programming: Foundations and Extensions. Princeton University Press.

Eiselt, H. A., and C.-L. Sandblom (2012). Operations Research: A Model-based Approach. Springer-Verlag, Berlin Heidelberg.

See Also

linprog::solveLP, lpSolve::lp

Examples

##  Examples from the book "Operations research - A Model-based Approach"
#-- production planning
cc <- c(5, 3.5, 4.5)
Ain <- matrix(c(3, 5, 4,
                6, 1, 3), 2, 3, byrow=TRUE)
bin <- c(540, 480)
linprog(cc, A = Ain, b = bin, maximize = TRUE)
# $x     20   0 120
# $fval  640

#-- diet problem
cc <- c(1.59, 2.19, 2.99)
Ain <- matrix(c(-250, -380, -257,
                 250,  380,  257,
                  13,   31,   28), 3, 3, byrow = TRUE)
bin <- c(-1800, 2200, 100)
linprog(cc, A = Ain, b = bin)

#-- employee scheduling
cc <- c(1, 1, 1, 1, 1, 1)
A <- (-1)*matrix(c(1, 0, 0, 0, 0, 1,
                   1, 1, 0, 0, 0, 0,
                   0, 1, 1, 0, 0, 0,
                   0, 0, 1, 1, 0, 0,
                   0, 0, 0, 1, 1, 0,
                   0, 0, 0, 0, 1, 1), 6, 6, byrow = TRUE)
b <- -c(17, 9, 19, 12, 5, 8)
linprog(cc, A, b)

#-- inventory models
cc <- c(1, 1.1, 1.2, 1.25, 0.05, 0.15, 0.15)
Aeq <- matrix(c(1, 0, 0, 0, -1,  0,  0,
                0, 1, 0, 0,  1, -1,  0,
                0, 0, 1, 0,  0,  1, -1,
                0, 0, 0, 1,  0,  0,  1), 4, 7, byrow = TRUE)
beq <- c(60, 70, 130, 150)
ub <- c(120, 140, 150, 140, Inf, Inf, Inf)
linprog(cc, Aeq = Aeq, beq = beq, ub = ub)

#-- allocation problem
cc <- c(1, 1, 1, 1, 1)
A <- matrix(c(-5,    0,    0,    0,    0,
               0, -4.5,    0,    0,    0,
               0,    0, -5.5,    0,    0,
               0,    0,    0, -3.5,    0,
               0,    0,    0,    0, -5.5,
               5,    0,    0,    0,    0,
               0,  4.5,    0,    0,    0,
               0,    0,  5.5,    0,    0,
               0,    0,    0,  3.5,    0,
               0,    0,    0,    0,  5.5,
              -5, -4.5, -5.5, -3.5, -5.5,
              10, 10.0, 10.0, 10.0, 10.0,
              0.2, 0.2,  0.2, -1.0,  0.2), 13, 5, byrow = TRUE)
b <- c(-50, -55, -60, -50, -50, rep(100, 5), -5*64, 700, 0)
# linprog(cc, A = A, b = b)
lb <- b[1:5] / diag(A[1:5, ])
ub <- b[6:10] / diag(A[6:10, ])
A1 <- A[11:13, ]
b1 <- b[11:13]
linprog(cc, A1, b1, lb = lb, ub = ub)

#-- transportation problem
cc <- c(1, 7, 4, 2, 3, 5)
Aeq <- matrix(c(1, 1, 1, 0, 0, 0,
                0, 0, 0, 1, 1, 1,
                1, 0, 0, 1, 0, 0,
                0, 1, 0, 0, 1, 0,
                0, 0, 1, 0, 0, 1), 5, 6, byrow = TRUE)
beq <- c(30, 20, 15, 25, 10)
linprog(cc, Aeq = Aeq, beq = beq)

pracma documentation built on Nov. 10, 2023, 1:14 a.m.