Linear programming (also called linear optimization) is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is a special case of mathematical programming (mathematical optimization).
Linear programming is an optimization technique for a system of linear constraints and a linear objective function. An objective function defines the quantity to be optimized, and the goal of linear programming is to find the values of the variables that maximize or minimize the objective function.
Linear programming is useful for many problems that require an optimization of resources. It could be applied to manufacturing, to calculate how to assign labor and machinery to minimize cost of operations. It could be applied in high-level business operations, to decide which products to sell and in what quantity in order to maximize profit. It could also be applied in logistics, to decide how to apply resources to get a job done in the minimum amount of time.
Linear programming can be used to solve a problem when the goal of the problem is to maximize some value and there is a linear system of inequalities that defines the constraints on the problem.
A constraint is an inequality that defines how the values of the variables in a problem are limited. In order for linear programming techniques to work, all constraints should be linear inequalities.
The libraries required for implementing linear programming in R are lpSolve and lpSolveAPI.
The syntax for the basic LP model is as follows:
lp (direction = "min", objective.in, const.mat, const.dir, const.rhs, transpose.constraints = TRUE, int.vec,
presolve=0, compute.sens=0, binary.vec, all.int=FALSE, all.bin=FALSE, scale = 196, dense.const, num.bin.solns=1, use.rw=FALSE)Arguments:
direction Character string giving direction of optimization: “min” (default) or “max.”
objective.in Numeric vector of coefficients of objective function
const.mat Matrix of numeric constraint coefficients, one row per constraint, one column per variable.
const.dir Vector of character strings giving the direction of the constraint: each value should be one of “<”, “<=”, “=”, “==”, “>”, or “>=”.
const.rhs Vector of numeric values for the right-hand sides of the constraints.
transpose.constraints By default each constraint occupies a row of const.mat, and that matrix needs to be transposed before being passed to the optimizing code. For very large constraint matrices it may be wiser to construct the constraints in a matrix column-by-column. In that case set transpose.constraints to FALSE.
int.vec Numeric vector giving the indices of variables that are required to be integer. The length of this vector will therefore be the number of integer variables.
presolve Numeric: presolve? Default 0 (no); any non-zero value means “yes.”
compute.sens Numeric: compute sensitivity? Default 0 (no); any non-zero value means “yes.”
binary.vec Numeric vector like int.vec giving the indices of variables that are required to be binary.
all.int Logical: should all variables be integer? Default: FALSE.
all.bin Logical: should all variables be binary? Default: FALSE.
scale Integer: value for lpSolve scaling. Details can be found in the lpSolve documentation. Set to 0 for no scaling. Default: 196
dense.const Three column dense constraint array. This is ignored if const.mat is supplied. Otherwise the columns are constraint number, column number, and value; there should be one row for each non-zero entry in the constraint matrix.
num.bin.solns Integer: if all.bin=TRUE, the user can request up to num.bin.solns optimal solutions to be returned.
use.rw Logical: if TRUE and num.bin.solns > 1, write the lp out to a file and read it back in for each solution after the first. This is just to defeat a bug somewhere. Although the default is FALSE, it is recommended to set this to TRUE if you need num.bin.solns > 1, until the bug is found.
Consider the following problem.
A car company produces 2 car models, model A and model B. Long-term projections indicate an expected demand of at least 100 model A cars and 80 model B cars each day. Because of limitations on production capacity, no more than 200 model A cars and 170 model B cars can be made daily. To satisfy a shipping contract, a total of at least 200 cars much be shipped each day. If each model A car sold results in a $2000 loss, but each model B car produces a $5000 profit, how many of each type should be made daily to maximize net profits?
Setup and initialization:
Consider the number of model A cars sold as a and that of model B as b.
According to the given constraints:
a >= 100
a <= 200
b >= 80
b <= 170
a+b >= 200And, the optimization function:
Maximize: 5000*b - 2000*aLet us rewrite our constraint inequalities in the normal form.
1*a + 0*b >= 100
1*a + 0*b <= 200
0*a + 1*b >= 80
0*a + 1*b <= 170
1*a + 1*b >= 200Let us now construct parameters for the LP model.
f.obj <- c(-2000, 5000)
f.dir <- c(">=", "<=", ">=", "<=")
f.rhs <- c(100, 200, 80, 170, 200)
f.con <- matrix (c(1, 0, 1, 0, 0, 1, 0, 1, 1, 1), nrow=5, byrow=TRUE)
f.dir <- c(">=", "<=", ">=", "<=", ">=")
lpSolve::lp("max", f.obj, f.con, f.dir, f.rhs)## Success: the objective function is 650000This gives the optimum value of the optimization function.
Let us retrieve the optimum values of a and b.
lpSolve::lp("max", f.obj, f.con, f.dir,f.rhs)$solution## [1] 100 170This result shows that the car company can make a maximum profit of $650,000 a day if it produces and sells 100 units of model A and 170 units of model B.
Linear programming and Optimization are used in various industries. Manufacturing and service industry uses linear programming on a regular basis.