Optimization is a technique for finding out the best possible solution for a given problem for all the possible solutions. Optimization uses a rigorous mathematical model to find out the most efficient solution to the given problem.
What is optimization?
Optimization is a technique for finding out the best possible solution for a given problem for all the possible solutions. Optimization uses a rigorous mathematical model to find out the most efficient solution to the given problem. To start with an optimization problem, it is important to first identify an objective. An objective is a quantitative measure of performance. For example: to maximize profits, minimize time, minimize costs, maximize sales.
There are a variety of optimization techniques –
Unconstrained optimization
In certain cases the variable can be freely selected within it’s full range. The optim() function in R can be used for 1- dimensional or n-dimensional problems. The general format for the optim() function is –
optim(objective, constraints, bounds = NULL, types= NULL, maximum = FALSE)
We start off with an example, let’s define the objective function what we are looking to solve –
> f <- function(x) 4 * (x[1]-1)^2 + 7 * (x[2]-3)^2 + 30 > f function(x) 4 * (x[1]-1)^2 + 7 * (x[2]-3)^2 + 30
Setting up the constraints next
> c <- c(1, 1) > c [1] 1 1
The optimization function is invoked
> r <- optim(c, f) > r $par [1] 0.9999207 3.0001660 $value [1] 30 $counts function gradient 69 NA $convergence [1] 0 $message NULL
Next we check if the optimization converged to a minimum or not. The easy way to do this is to check if
> r$convergence == 0 [1] TRUE
The optimization has converged to minimum. Finding out the input arguments for the optimization function can be obtained by
> r$par [1] 0.9999207 3.0001660
The value of objective function at the minimum is obtained by
> r$value [1] 30
Linear programming
Here is a good definition from technopedia – “Linear programming is a mathematical method that is used to determine the best possible outcome or solution from a given set of parameters or list of requirements, which are represented in the form of linear relationships. It is most often used in computer modeling or simulation in order to find the best solution in allocating finite resources such as money, energy, manpower, machine resources, time, space and many other variables. In most cases, the “best outcome” needed from linear programming is maximum profit or lowest cost.”
An example of a LP problem is –
Maximize or Minimize objective function: f(y1, y2) = g1.y1 + g2.y2
Subjected to inequality constraints:
- g11.y1 + g12.y2 <= p1
- g21.y1 + g22.y2 <= p2
- g31.y1 + g32.y2 <= p3
- y1 >= 0, y2 >=0
Example 1
A company wants to maximize the profit for two products A and B which are sold at $ 25 and $ 20 respectively. There are 1800 resource units available every day and product A requires 20 units while B requires 12 units. Both of these products require a production time of 4 minutes and total available working hours are 8 in a day. What should be the production quantity for each of the products to maximize profits?
A LP problem can either be a maximization problem or a minimization problem. The Above problem is a maximization problem. Some of the steps that should be followed while defining a LP problem are –
- Identify the decision variables
- Write the objective function
- Mention the constraints
- Explicitly state the non-negativity restriction
Lets walk through the above example –
As already defined this is a maximization problem, first we define the objective function.
max(Sales) = max(25 y1 + 20 y2)
where,
- y1 is the units of Product A produced
- y2 is the units of Product B produced
- y1 and y2 are called the decision variables
- 25 and 20 are the selling price of the products
We are trying to maximize the sales while finding out the optimum number of products to manufacture. Now we set the constraints for this particular LP problem. We are dealing with both resource and time constraints.
20y1 + 12 y2 <= 1800 (Resource Constraint)
4y1 + 4y2 <= 8*60 (Time constraint)
There are two ways to solve a LP problem
- Graphical Method
- Simplex Method
We will be solving this problem using the simplex method but in R. We shall also explain another example with excel’s solver. There are a couple of packages in R to solve LP problems. Some of the popular ones are –
- lpsolve
- lpsolveAPI
Implementation in R using Lpsolve
Let’s use lpsolve for this problem. First we need to set the objective function, this has already been defined.
> require(lpSolve) Loading required package: lpSolve > objective.in <- c(25, 20) > objective.in [1] 25 20
Creating a matrix for the constraints, we create a 2 by 2 matrix for this. And then setting constraints.
> const <- matrix(c(20, 12, 4, 4), nrow=2, byrow=TRUE) > const [,1] [,2] [1,] 20 12 [2,] 4 4 > time_constraints <- (8*60) > resource_constraints <- 1800 > time_constraints [1] 480 > resource_constraints [1] 1800
Now we are basically creating the equations that we have already defined by setting the rhs and the direction of the constraints.
> rhs <- c(resource_constraints, time_constraints)
> rhs
[1] 1800 480
> direction <- c("<=", "<=")
> direction
[1] "<=" "<="
The final step is to find the optimal solution. The syntax for the lpsolve package is –
lp(direction , objective, const.mat, const.dir, const.rhs)
> optimum <- lp(direction="max", objective.in, const, direction, rhs) > optimum Success: the objective function is 2625 > summary(optimum) Length Class Mode direction 1 -none- numeric x.count 1 -none- numeric objective 2 -none- numeric const.count 1 -none- numeric constraints 8 -none- numeric int.count 1 -none- numeric int.vec 1 -none- numeric bin.count 1 -none- numeric binary.vec 1 -none- numeric num.bin.solns 1 -none- numeric objval 1 -none- numeric solution 2 -none- numeric presolve 1 -none- numeric compute.sens 1 -none- numeric sens.coef.from 1 -none- numeric sens.coef.to 1 -none- numeric duals 1 -none- numeric duals.from 1 -none- numeric duals.to 1 -none- numeric scale 1 -none- numeric use.dense 1 -none- numeric dense.col 1 -none- numeric dense.val 1 -none- numeric dense.const.nrow 1 -none- numeric dense.ctr 1 -none- numeric use.rw 1 -none- numeric tmp 1 -none- character status 1 -none- numeric
Now we get the optimum values for y1 and y2, i.e the number of product A and product B that should be manufactured.
> optimum$solution [1] 45 75
The maximum sales figure is –
> optimum$objval [1] 2625
Example 2
Below is good example taken from lpsolve’s sourceforge website –
“Suppose a farmer has 75 acres on which to plant two crops: wheat and barley. To produce these crops, it costs the farmer (for seed, fertilizer, etc.) $120 per acre for the wheat and $210 per acre for the barley. The farmer has $15000 available for expenses. But after the harvest, the farmer must store the crops while awaiting avourable market conditions. The farmer has storage space for 4000 bushels. Each acre yields an average of 110 bushels of wheat or 30 bushels of barley. If the net profit per bushel of wheat (after all expenses have been subtracted) is $1.30 and for barley is $2.00, how should the farmer plant the 75 acres to maximize profit?”
As we did in the previous example, let’s define the optimization function and the constraints.
maximize
g = (110)(1.30)x + (30)(2.00)y = 143x + 60y
subject to
120x + 210y <= 15000
110x + 30y <= 4000
x + y <= 75
x >= 0
y >= 0
We will be solving this problem in both excel and R.
Excel Solver
There is a way to solve LP problems using Excel. Firstly we have to define the number of acres to plant for both these crops.
Initially they are zero, the optimum values can be obtained by using the solver plugin in excel. Next we need to define the constraints, the equations for the constraints have already been defined.
Subject to,
The initial values for the number of used resources is set at zero initially. The main workhorse behind these LP problems is to use the sumproduct equation.
The sumproduct equation is basically a product of cost multiplied by the number of acres.
Now we define the maximization equation. In this case the profit needs to be maximized. The total profit cell that is seen in the below image.
The same sumproduct formula that was previously used is repeated again.
Now try changing the values for the wheat and Barley cells. Just put some random number for both the cells. Observe the total profit cell and the used cell for all the constraints.
As seen we get a total profit figure, however have a look at the used resources. Clearly the values in the cell are more than the values in the available cells. We can try to decrease the number of acres and see what the resulting values will be.
The values are low indeed, but it is not the optimum solution. To get the optimum values for total profit. We use the solver plugin to solve this. Navigate to the data and see if there is the solver option under the analysis tab.
If it is not present, follow these steps to install it –
- Navigate for the file tab and then click on options
- Click on the Add-ins button, and then go next to the manage
Once this is done, a popup should appear.
Select the Solver add-in and press OK.
There you go now the solver option should show up. Before we proceed further, let’s set the number of acres to zero.
Now, set the objective to total profit
Set the –
- Solving method to simplex LP.
- The objective to max
Next add the three constraints,
Once done press solve, the following popup should show up along with the optimized values for the profit cell.
Press OK, now we have the number of acres to plant for Wheat and Barley. Along with the profit value.
Implementation in R using LpsolveAPI
We previously used the Lpsolve package, in this example we illustrate how to use LpsolveAPI package. We start off by calling the lpsolveapi package.
> require(lpSolveAPI) Loading required package: lpSolveAPI > lprec <- make.lp(0, 2) > lprec Model name: C1 C2 Minimize 0 0 Kind Std Std Type Real Real Upper Inf Inf Lower 0 0
Next we set the objective function to maximization.
> lp.control(lprec, sense="max") $anti.degen [1] "none" $basis.crash [1] "none" $bb.depthlimit [1] -50 $bb.floorfirst [1] "automatic" $bb.rule [1] "pseudononint" "greedy" "dynamic" "rcostfixing" $break.at.first [1] FALSE $break.at.value [1] 1e+30 $epsilon epsb epsd epsel epsint epsperturb epspivot 1e-10 1e-09 1e-12 1e-07 1e-05 2e-07 $improve [1] "dualfeas" "thetagap" $infinite [1] 1e+30 $maxpivot [1] 250 $mip.gap absolute relative 1e-11 1e-11 $negrange [1] -1e+06 $obj.in.basis [1] TRUE $pivoting [1] "devex" "adaptive" $presolve [1] "none" $scalelimit [1] 5 $scaling [1] "geometric" "equilibrate" "integers" $sense [1] "maximize" $simplextype [1] "dual" "primal" $timeout [1] 0 $verbose [1] "neutral"
We define the objective function and the constraints
> set.objfn(lprec, c(143, 60)) > add.constraint(lprec, c(120, 210), "<=", 15000) > add.constraint(lprec, c(110, 30), "<=", 4000) > add.constraint(lprec, c(1, 1), "<=", 75)
Let’s have a look at the LP problem that we have defined.
> lprec Model name: C1 C2 Maximize 143 60 R1 120 210 <= 15000 R2 110 30 <= 4000 R3 1 1 <= 75 Kind Std Std Type Real Real Upper Inf Inf Lower 0 0
Solving
> solve(lprec) [1] 0
Getting the optimized profit value
> get.objective(lprec) [1] 6315.625
Let’s finally get the values for how many acres of Wheat and Barley to be planted.
> get.variables(lprec) [1] 21.875 53.125
Thus, to achieve the maximum profit ($6315.625), the farmer should plant 21.875 acres of wheat and 53.125 acres of barley.
Conclusion
Now that we have figured out how to solve LP problems using excel solver as well as the packages in R, namely Lpsolve and LpsolveAPI. Go ahead and start solving your own Linear Programming problems.
LP Problem sources –