linprog: Linear Programming Solver

In pracma: Practical Numerical Math Functions

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 <[e-mail]>

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.