Linear programming is a simple technique where we depict complex relationships through linear functions and then find the optimum points. The important word in previous sentence is depict. The real relationships might be much more complex - but we can simplify them to linear relationships.
Applications of linear programming are every where around you. You use linear programming at personal and professional fronts. You are using linear programming when you are driving from home to work and want to take the shortest route. Or when you have a project delivery you make strategies to make your team work efficiently for on time delivery.
Let us define some terminologies used in Linear Programming using the above example.
Decision Variables: The decision variables are the variables which will decide my output. They represent my ultimate solution. To solve any problem, we first need to identify the decision variables.
Objective Function: It is defined as the objective of making decisions.
Constraints: The constraints are the restrictions or limitations on the decision variables. They usually limit the value of the decision variables.
The constraints of the Linear Program define some set of values that satisfy all constants. i.e., For n variables, the feasible region is a n-dimensional matrix form. The LP formulation can also be expressed in a matrix form.
Most R packages(for example, lpSolve) are used to solve LP by implementing solvers as functions, whose input variables are:
A car company produces 2 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?
For Above Problem, Let x be number of model A car and y be the number of model B car
z=5000y-2000x
And the constraints are
x>=100 {Demand of Model A}
y>=80 {Demand of Model B}
x<=200 {Model A’s Production Limit}
y<=170 {Model B’s Production Limit}
x+y>=200
library(lpSolve)
# parameters are defined
obj.fun <- c(5000, -2000) # Objective function
constr <- matrix (c(0,1 , 1,0 , 0,1 , 1,0 , 1,1) , ncol=2, byrow =TRUE) # Constraints
constr.dir <- c( ">=", ">=","<=", "<=", ">=")
rhs <- c(100, 80, 200, 170 , 200)
# solving model
max.sol <- lp ("max", obj.fun, constr, constr.dir, rhs, compute.sens = TRUE)max.sol$ solution## [1] 170 100The optimal solution for above problem is, 100 model A cars and 170 model B cars should be made daily and then the maximum profit will be 650000 dollars.