Terminology

Simplex Algorithm Terminology

Linear Programming Problem:

  • Identify a linear programming problem as a mathematical optimization problem where the objective function and the constraints are all linear.
  • Understand that a linear programming model consists of decision variables, an objective function, and constraints.

Objective Function:

  • Note the objective function is the function that is subject to maximization or minimization in a linear programming problem.

Decision Variables:

  • Recognise the decision variables as the variables that decision makers can control or adjust to achieve an optimal solution.

Constraints:

  • Understand constraints as the set of restrictions or limits defined by the problem that the solution must satisfy.

Feasible Region:

  • Define the feasible region as the set of all points that satisfy all the given constraints.
  • Realise even though there may be infinite points in the feasible region, the optimal solution to a linear programming problem occurs at an extreme point, or a vertex, of the feasible region.

Basis and Basic Variables:

  • Know that a basis of a system of linear equations is a list of minimum number of linearly independent solutions which could be used to find any solution of the system.
  • Learn that the basic variables are the variables with non-zero coefficients in the basic solution associated with the particular basis.
  • Recognize that non-basic variables are those which are not included in the basis and have zero coefficients in the solution associated with that basis.

Pivot Column and Pivot Row:

  • Understand the pivot column is the column in the tableau selected to improve the solution, often selected as the column in the last row with the most negative number.
  • Recognize the pivot row is determined according to the ratio test and is used to transform the tableau so that we get a better solution.

Optimal Solution:

  • Define the optimal solution as the solution that maximizes or minimizes the objective function subject to the constraints of the problem. The optimal solution is achieved when all the numbers in the last row of the simplex tableau are non-negative.