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 x3 ≥ 0 a slack variable and x4 ≥ 0 a surplus variable, the preceding problem, in
form, becomes

The associated simplex matrix thus appears as
Since this matrix does not contain within ...