M Method or Penalty Method in Linear Programming
M Method or Penalty Method
Introduction
This section explains how to adapt the simplex method for linear programming problems that are not in standard form. We will focus on handling equality constraints and constraints with ≥ signs. The adjustments are made in the initial step, allowing the rest of the simplex method to proceed as usual.
The Challenge of Non-Standard Forms
Non-standard forms pose a challenge in identifying an initial basic feasible solution. The standard approach involves the technique of artificial variables. This technique introduces dummy variables (called artificial variables) into constraints that need them. These variables serve as initial basic variables and are subject to non-negativity constraints. The objective function is modified to impose a penalty for artificial variables taking values greater than zero. The simplex method then iteratively forces these variables to become zero, eventually solving the real problem.
Handling Equality Constraints
Consider a linear programming model where the only non-standard aspect is the presence of one or more equality constraints. For example, let’s modify a problem where the third constraint, 3x1 + 2x2 ≤ 18, becomes an equality constraint:
3x1 + 2x2 = 18
We introduce a non-negative artificial variable (x5) into the equation:
3x1 + 2x2 + x5 = 18
In general, to convert an equality constraint to standard form, we simply add an artificial variable.
Handling ≥ Constraints
To illustrate how artificial variables handle ≥ constraints, consider the following example:
Minimize Z = 0.4x1 + 0.5x2
subject to:
0.3x1 + 0.1x2 ≤ 2.7
0.5x1 + 0.5x2 = 6
0.6x1 + 0.4x2 ≥ 6
x1 ≥ 0, x2 ≥ 0
To convert the third constraint to an equality, we subtract a surplus variable (x5) and add an artificial variable (x6):
0.6x1 + 0.4x2 – x5 + x6 = 6
The artificial variable ensures non-negativity when 0.6x1 + 0.4x2 is less than 6. If x1 = 0 and x2 = 0, then x5 = 0 and x6 = 6.
In summary, a ≥ constraint is converted to standard form by subtracting a surplus variable and adding an artificial variable.
The M Method
To solve a problem with non-standard constraints, we construct an artificial problem with the same optimal solution as the real problem by making two changes:
- Introduce artificial variables as needed.
- Assign a large penalty (M) to artificial variables in the objective function. For a maximization problem, the objective function becomes:
Z = 3x1 + 5x2 – Mx5
This M method forces x5 to zero in the optimal solution. For minimization problems, the artificial variable is added with a coefficient of +M.
Minimization with the Simplex Method
To minimize Z directly with the simplex method, we reverse the roles of positive and negative coefficients in the objective function row. The entering basic variable is chosen based on the smallest positive coefficient. The solution is optimal when all coefficients in the objective function row are non-positive. The process of selecting the outgoing basic variable remains the same (using the lowest ratio).
The Two-Phase Method
The two-phase method offers an alternative to the M method. It eliminates the need for the large M by using two objective functions:
Phase 1: Minimize Z = sum of all artificial variables (until all artificial variables are zero).
Phase 2: Minimize the original objective function (with all artificial variables set to zero).
Phase 1 finds a basic feasible solution to the real problem, which is then used as the starting point for Phase 2, where the simplex method solves the real problem with its original objective function.
Summary of the Two-Phase Method
- Initial Step: Introduce artificial variables to obtain an initial basic feasible solution.
- Phase 1: Solve the problem: Minimize Z = sum of artificial variables, subject to the revised constraints. The optimal solution (with Z = 0) provides a basic feasible solution for the real problem.
- Phase 2: Eliminate the artificial variables (now all zero). Starting with the solution from Phase 1, use the simplex method to solve the real problem.
Conclusion
Both the M method and the two-phase method are effective techniques for handling linear programming problems with non-standard constraints. They provide a systematic way to find optimal solutions by introducing and then eliminating artificial variables.
Note:
Regardless of whether the original problem is maximization or minimization, the first phase always involves minimizing the sum of all artificial variables.