Linear programming

Linear programming is a technique to identify maximum and minimum solutions for problems, often referred to as optimization. It is a common technique because a surprising number of real world problems can be described or estimated using linear equations. For example, in manufacturing:

• Programming is a synonym for planning, or more specifically, planning of manufacturing activities, resources and products
• The linear objective function describes the potential amount of profit, loss, revenue or cost
• Variables are the resources (input) and/or products (output) related to the manufacturing activities
• Linear equality and inequality constraints describe requirements or restrictions caused by manufacturing activities
• Maximization is concerned with profit, revenue or output quantities
• Minimization is concerned with loss, costs or input quantities

Linear programming has very specific terms:

• A solution is any specification of values for x₁, x₂, ... , x_n
• A feasible solution is one such that all constraints are satisfied
• The feasible region is the collection of all feasible solutions
  • It is possible for a problem to have an empty feasible region, e.g. no feasible solution
• An optimal solution is a feasible solution that has the most favorable value of the objective function
  • When maximizing the objective function, the most favorable value is the largest value
  • When minimizing the objective function, the most favorable value is the smallest value

As an example, consider the following linear programming problem:

Such that,

The Octave script below uses the glpk() function to solve the example problem.

# matrix notation of problem c = [20; 40]; a = [4, 6; 2, 6; 0, 1]; b = [120; 72; 10]; #empty vector because the default lower bound on the variables is zero lb = []; #empty vector because there is no upper bound on the variables ub = []; #indicates that each variable is continuous type vartype = "CC"; #indicates the sense of each constraint as having an upper bound ctype = "UUU"; #indicates that it is a maximization problem s = -1; # the command below displays: # xopt = the optimal variables # fopt = the optimal value # status = 180 if solution is optimal # status = 181 if solution is feasible, but, not optimal # status = 182 if solution is not feasible # status = 183 if there are no feasible solutions [xopt, fopt, status ] = glpk (c, a, b, lb, ub, ctype, vartype, s )

Average rating is