Linear Programming: M Method Explained
Uploaded by
ScribdTranslationsLinear Programming: M Method Explained
Uploaded by
ScribdTranslationsThere are linear programming problems that do not provide a
initial basic solution. This situation arises when at least
one of the constraints is of the type (<=) or (=). For this purpose, it
they develop 2 methods based on the use of artificial variables: The
method M or penalty method and the 2-phase technique.
M O D E L OF PENALIZATION.
The large M method is a derived form of the method
simplex, used to solve problems where the origin does not form
part of the feasible region of a linear programming problem.
To perform this algorithm, the same steps as in the
simplex method, but first we need to change the function
objective to include artificial variables. These
variables will have to to be multiplied by a number
sufficiently large so that it is not eliminated through the
operation, called M and that it should only leave when
whether it adds or subtracts with another M.
For the maximization case, we need to subtract the variables.
artificial along with their coefficients so that these variables do not
they enter the base, but if we minimize then we will have to
sum the artificial variables
The basic steps of method M are as follows:
1. Express the problem in standard form by transforming the
inequalities into equations by introducing slack variables.
2. Add non-negative variables to the left side of each of
the equations corresponding to the constraints of type (>=) or
These variables are called artificial variables and their addition
makes the corresponding restrictions.
This difficulty is eliminated by ensuring that the variables are 0 in the
final solution. This is achieved by assigning a very high penalty.
large per unit to these variables in the objective function. Such
penalization will be designated as -M for problems of
maximization and +M for minimization problems.
3. Use artificial variables in the initial basic solution; without
embargo, the objective function of the initial table is prepared
adequately to express themselves in terms of the variables not
only basic. This means that the coefficients of the
artificial variables in the objective function must be 0 a result
what can be achieved by summing appropriate multiples of the
constraint equations to the objective row.
4. Proceed with the regular steps of the simplex method.
EXAMPLE:
Minimize:
Subject to:
Minimize:
Subject to:
Minimize:
Subject to:
Minimize:
Subject to:
V.B. Z X1 X2 X3 S1 S2 R1 Solution
Z 1 -3 -2 -4 0 0 -M 0
R1 0 2 2 3 -1 0 1 15
S2 0 2 3 1 0 1 0 12
V.B. Z X1 X2 X3 S1 S2 R1 Solution
Z 1 - - - -M 0 0 15M
3+2M 2+2M 4+3M
R1 0 2 2 3 -1 0 1 15
S2 0 2 3 1 0 1 0 12
Criterion for selecting the entering variable:
Maximization: The highest negative value of row Z.
Minimization: The highest positive value of row Z.
V.B. Z X1 X2 X3 S1 S2 R1 Solution
Z 1 -1/3 2/3 0 -4/3 0 4/3-M 20
X3 0 2/3 2/3 1 -1/3 0 1/3 5
S2 0 4/3 7/3 0 1/3 1 -1/3 7
V.B. Z X1 X2 X3 S1 S2 R1 Solution
Z 1 -5/7 0 0 -10/7 -2/7 10/7-M 18
X3 0 2/7 0 1 -3/7 -2/7 3/7 3
X2 0 4/7 1 0 1/7 3/7 -1/7 3
EXAMPLE:
Maximize:
Subject to:
Maximize:
Subject to:
Maximize:
Subject to:
Maximize:
Subject to:
V.B. Z X1 X2 S1 S2 R1 R2 Solution
Z 1 -4 -1 0 0 M M 0
R1 0 3 1 0 0 0 0 3
R2 0 4 3 -1 0 1 1 6
S2 0 1 2 0 1 0 0 3
V.B. Z X1 X2 S1 S2 R1 R2 Solution
Z 1 -4-7M -1-4M M 0 0 0 -9M
R1 0 3 1 0 0 0 0 3
R2 0 4 3 -1 0 1 1 6
S2 0 1 2 0 1 0 0 3
V.B. Z X1 X2 S1 S2 R1 R2 Solution
Z 1 0 1/3-5/3M M 0 4/3 + 7/3M 0 4-2M
X1 0 1 1/3 0 0 1/3 0 1
R2 0 0 5/3 -1 0 -4/3 0 2
S2 0 0 5/3 0 1 -1/3 1 2
V.B. Z X1 X2 S1 S2 R1 R2 Solution
Z 1 0 0 1/5 0 8/5+M -1/5 + M May 18
X1 0 1 0 1/5 0 3/5 3/5
R2 0 0 1 -3/5 0 -4/5 3/5 6/5
S2 0 0 0 1 1 1 -1 1