Linear programming (LP) 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. source
I.e. linear programming is a technique in which we maximize or minimize a function. Every linear programming problem can be written in the following standard form
Here is a vector of n unknowns, with n typically much larger than m, the coefficient vector of the objective function, and the expression signifies for . For simplicity, we assume that rank A = m, i.e., that the rows of A are linearly independent.
The Simplex Method (developed by George Dantzig in 1946) is the earliest solution algorithm for solving LP problems. It is an efficient implementation of solving a series of systems of linear equations. By using a greedy strategy while jumping from a feasible vertex of the next adjacent vertex, the algorithm terminates at an optimal solution.
Simplex method uses row operations to obtain the maximum or minimum values of function. The simplex method moves from one extreme point to one of its neighboring extreme point.
Typical uses of the simplex algorithm are to find the right mix of ingredients at the lowest cost (the goal). If the ingredients are food, the constraints would be having at least so many calories, so much protein, fats, carbohydrates, vitamins, minerals, etc.
Maximize subject to the following constraints:
# install.packages("linprog") library("linprog") c = c(3,2) b = c(30,60) A = rbind(c(1,2), c(5,1)) res = solveLP(c, b, A, maximum=TRUE) print(res) Results of Linear Programming / Linear Optimization Objective function (Maximum): 50 Iterations in phase 1: 0 Iterations in phase 2: 2 Solution opt 1 10 2 10 Basic Variables opt 1 10 2 10 Constraints actual dir bvec free dual dual.reg 1 30 <= 30 0 0.777778 18 2 60 <= 60 0 0.444444 45 All Variables (including slack variables) opt cvec min.c max.c marg marg.reg 1 10 3 1.0 10.000000 NA NA 2 10 2 0.6 6.000000 NA NA S 1 0 0 -Inf 0.777778 -0.777778 18 S 2 0 0 -Inf 0.444444 -0.444444 45