Tag Archives: Fundamental Theorem of Linear Programming

Fundamental Theorem of Linear Programming and its Properties

In this following article we will address properties set by the Fundamental Theorem of Linear Programming through a conceptual discussion and practical and simple examples. These properties are essential when taking into consideration algorithmic resolutions of this kind of mathematical optimization models, among them is what we call the Simplex Method.

Every Linear Programming (LP) problem in standard form complies with the following three properties:

  • Property 1: “If the problem has no optimal solution then it’s unbounded or infeasible”

Note that a linear problem with a domain of unbounded feasible solutions may (or may not) allow optimal solution, i.e. facing a model with these features does not determine the presence (or absence) of an optimal solution a priori.

In the implementation of the Simplex Method there is a detection of an unbounded problem without optimal solution when calculating the variable that leaves the base index of a variable, all elements of the J column in the table, are negative, for J the index of a non basic with negative reduced cost. For example, we will consider the following linear programming problem:

unbounded lp

After standardizing the previous model, adding X3 and X4 as slack variables for constraint 1 and 2, respectively, the following initial table is obtained.

unbounded simplex

X2 is a non-basic variable with a negative reduced cost and therefore must be incorporated into the base. However it is not practical to estimate the feasibility criteria or the minimum quotient because the entries in the column X2 are negative or zero. This shows clearly that the problem is unbounded and with no optimal solution.

Moreover a linear model is infeasible (The domain of feasible solutions is empty and therefore has no supported solution) if the value of the objective function at the end of Phase I of the The Two-Phase Simplex Method is not zero.

  • Property 2: “If it has a feasible solution, it has a basic feasible solution”

A basic property of linear programming models is that in case of admitting optimal solution, it will necessarily find a vertex or segment on the boundary of the domain of feasible solutions.

In this context the implementation of the Simplex Method as an algorithmic resolution strategy; we seek to provide solutions that meets the Ax=b (Standard restrictions) and x≥0 criteria defining a (not necessarily optimal) basic feasible solution.

For example the following graph represents a linear model in two variables that show that points A, B, C, D and E are feasible basic solutions.

linear-programing-two-decis
graphical-linear-programmin

  • Property 3: “If the problem has an optimal solution, then it has an optimal basic feasible solution”

Continuing with the same example, vertex C is not only a basic feasible solution but also an optimal basic feasible solution. If all reduced costs (of non-basic variables: S1 and S3) are greater than or equal to zero and we are in presence of a basic feasible solution (X=100, S2=400, Y=350 all ≥0), we meet the stopping criterion of the Simplex Method and consequently the current basic feasible solution is optimal.

optimal-tableau-simplex-method