Linear Programming and Resource Allocation Modeling

5Variations of the Standard Simplex Routine

This chapter presents a variety of computational devices which can be employed to solve linear programming problems which depart from the basic structure depicted in Chapter 3 (3.1). In particular, we shall consider “≥” as well as “=” structural constraints, the minimization of the objective, and problems involving unrestricted variables.

5.1 The M‐Penalty Method

Let us assume that we are faced with solving a linear program whose structural constraint system involves a mixture of structural constraints, e.g. the said problem with its mixed structural constraint system (involving “≤,” “≥,” and “=” structural constraints) might appear as

We noted in Chapter 3 that to convert a “≤” structural constraint to standard form (i.e. to an equality) we must add a nonnegative slack variable to its left‐hand side. A similar process holds for “≥” structural constraints – this time we will subtract a nonnegative surplus variable from its left‐hand side. So for x₃ ≥ 0 a slack variable and x₄ ≥ 0 a surplus variable, the preceding problem, in form, becomes

The associated simplex matrix thus appears as

Since this matrix does not contain within ...