Linear Programming and Resource Allocation Modeling

3Introduction to Linear Programming

3.1 Canonical and Standard Forms

We may depict the basic structure of a linear programming problem in what is termed canonical form as

(3.1)

Here f is the objective function (a hyperplane), the first m inequalities are the structural constraints, and the last p inequalities are simply called nonnegativity conditions. Taken altogether, the structural constraints and the nonnegativity conditions constitute a set of closed half‐planes that will be called the constraint system. This system forms the p‐dimensional feasible regionK, i.e. the area within which an admissible solution to (3.1) lies.

In matrix form, (3.1) may be rewritten as

(3.2)

where

Any X that satisfies AX ≤ b is called a solution to the linear programming problem while if such an X also satisfies X ≥ O, i.e. X ε K = {X|AX ≤ b, X ≥ O}, then it is termed a feasible solution. Moreover, if X₀ is feasible and f(X₀) ≥ f(X), where X is any other feasible solution, then X₀ is an optimal solution to 3.1 (or (3.2)).

Rather than deal with the structural constraints as a set of inequalities, we may transform them into a set of equalities (called the augmented structural constraint system ...