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  

Evaluating polynomial functions for specific variables

Octave scripts use a vector of the coefficients in descending order to represent a polynomial function. Afterwards, the command polyval() can be used to evaluate the function for specific variables. For example, consider this function:

• y = 3x² - 3x - 6

# Display the y value when x is 3 p = [3 -3 -6]; polyval( p, 3 ) # Put the variables into a vector to calculate over several x variables p = [3 -3 -6]; x = -3:3; polyval( p, x )

Plotting polynomial functions

Octave uses a vector of the coefficients in descending order to represent a polynomial function. For example, consider this function:

• y = 3x² - 3x - 6

Polynomial functions can be plotted in an Octave script by using the polyval and plot commands.

p = [3 -3 -6]; x = -2:3; y = polyval( p, x ); plot( x, y );

Finding roots of polynomial functions

A common task in many business and computing subjects is the calculation of minima and maxima values. This task requires finding the roots of first and second order derivatives, which can be done conveniently using Maxima or Octave scripts. For example, consider this function:

• y = 3x² - 3x - 6

Polynomial functions are expressed quite literally in Maxima scripts. They use the realroots() command to calculate real valued roots.

p: 3*x^2-3*x-6; realroots( p );

Alternatively, an Octave script could also find the real valued roots. The main difference is that Octave uses a vector of the coefficients in descending order to represent a polynomial function.

p = [3 -3 -6]; roots( p )