Método de 2 Fases

Z=7 x 1−2 x 2 →min;

x 1 + x 2 ≤5 ,
2 x1 −3 x 2≤6 ,
3 x 1 + x 2≥3 ,
x 1 + x 2 ≥2 ,
x 1−x 2 ≥−3 ,
x 1 , x2 ≥0 .

SOLUCIÓN POR EL MÉTODO DE DOS FASES

Se lleva el modelo a la forma estándar y se obtiene la solución básica inicial:

Forma Estándar Solución Básica Inicial

x1 + x2 + S1= 5 variables no b á sicas : x 1 , x 2=0

2x1 - 3x2 + S2= 6 variables básicas: S1=5

3x1 + x2 – S3= 3 S2=6
x1 + x2 – S4= 2 S3=-3 (infactible)
-x1 + x2 + S5= 3 S4=-2 (infactible)
S1, S2, S3, S4, S5 >= 0 S5=3

Se puede observar que la solución básica inicial obtenida es infactible, lo que amerita introducción
de las variables artificiales en las ecuaciones que producen inconvenientes (como infactibilidad o
inconsistencia). En el caso del modelo en cuestión la tercera y la cuarta ecuaciones requieren la
introducción de la variable artificial. Entonces, se obtiene la solución básica inicial artificial:

Forma Estándar Solución Básica Inicial Artificial

x1 + x2 + S1= 5 variables no básicas: x1, x2, S3, S4=0
2x1 - 3x2 + S2= 6 variables básicas: S1 = 5, S2 = 6, S5 =3, R3 = 3, R4 = 2
3x1 + x2 – S3 +R3= 3
x1 + x2 – S4 + R4= 2 ESTA SOLUCIÓN INICIAL ES FACTIBLE!
-x1 + x2 + S5= 3
S1, S2, S3, S4, S5, R3, R4 >= 0

Las variables artificiales son ajenas al modelo. Su uso es un truco artificial para obtener una
solución básica de partida que es factible. Para llegar a la solución factible propia del modelo, se
debe llegar a la solución donde todas las variables artificiales se volvieran “no básicas”, o sea, con
valores 0. Para lograr esto en el método de 2 Fases en la primera fase se plantea el objetivo:
“Volver las variables artificiales no básicas con los valores 0”. Para esto se plantea la
función-objetivo propia de la primera fase como la minimización de la suma de todas las
variables artificiales introducidas. (Con la consideración de las restricciones de “no negatividad”
el mínimo posible 0 se logra cuando todas las variables tengan valores 0).
 FASE I

r = R3 + R4  min ; r - R3 - R4 = 0 ; pero de acuerdo a la solución inicial r=5

Pero por la notación de la tabla simplex se debe considerar que r tiene valor 0 correspondiente a
la solución actual, lo que no es cierto (r = R 3 + R4= 3+2 = 5). Para subsanar este desajuste se
puede resolver de las ecuaciones de la forma estándar las variables artificiales (estas están con
valor diferente de 0) y sustituyendo las Ri en la expresión de Z, realizar el ajuste de la misma:

r – 3 + 3x1 + x2 – S3 – 2 + x1 + x2 – S4 = 0
r + 4x1 + 2x2 – S3 – S4 = 5

Otra manera de realizar el ajuste (que es más fácil de algoritmizar) son las operaciones elementales
matriciales: La fila por ajustarse se llena en la tabla simplex (función objetivo de la primera fase r) y
se seleccionan las variables que deben participar en la operación (variables que tienen los
coeficientes diferentes de 0 en la fila que se debe ajustar y que tienen valores diferentes de 0 en la
solución actual). En el caso actual en la fila de r las variables R 3 y R4 tienen coeficientes diferentes
de 0 y tienen valores diferentes de 0, entonces estas serán utilizadas en el ajuste. Las filas
correspondientes a las ecuaciones con R3 y R4 se llenan en la tabla. El esquema de cálculo es la
siguiente: las filas de las variables se multiplican por sus coeficientes respectivos que estas tienen
en la fila que se debe ajustar y el resultado de multiplicación se resta en correspondencia de la fila
que se ajusta:

VAR
BASICAS X1 X2 S1 S2 S3 S4 S5 R3 R4 SOL

r 0 0 0 0 0 0 0 -1 -1 0
(-)
R3*(-1) -3 -1 0 0 1 0 0 -1 0 -3

R4*(-1) -1 -1 0 0 0 1 0 0 -1 -2

r 4 2 0 0 -1 -1 0 0 0 5

Ahora se llena la tabla simplex completamente, con la r ajustada y todas las ecuaciones de la forma
estándar y se procede con el algoritmo de simplex:
 VAR
BASICAS X1 X2 S1 S2 S3 S4 S5 R3 R4 SOL
4 1 1/3 0 0 -1 1/3 0 0 1 1/3 0 4
r 4 2 0 0 -1 -1 0 0 0 5

R3 3 1 0 0 -1 0 0 1 0 3 1
1 1/3 0 0 - 1/3 0 0 1/3 0 1
R4 1 1 0 0 0 -1 0 0 1 2 2
1 1/3 0 0 - 1/3 0 0 1/3 0 1
 S1 1 1 1 0 0 0 0 0 0 5 5
2 2/3 0 0 - 2/3 0 0 2/3 0 2
S2 2 -3 0 1 0 0 0 0 0 6 3
-1 - 1/3 0 0 1/3 0 0 - 1/3 0 -1
S5 -1 1 0 0 0 0 1 0 0 3
0 2/3 0 0 1/3 -1 0 - 1/3 1 1
r 0 2/3 0 0 1/3 -1 0 -1 1/3 0 1
0 1/3 0 0 1/6 - 1/2 0 - 1/6 1/2 1/2
X1 1 1/3 0 0 - 1/3 0 0 1/3 0 1 3

R4 0 2/3 0 0 1/3 -1 0 - 1/3 1 1 1 1/2

0 2/3 0 0 1/3 -1 0 - 1/3 1 1
S1 0 2/3 1 0 1/3 0 0 - 1/3 0 4 6
0 -3 2/3 0 0 1 5/6 5 1/2 0 1 5/6 -5 1/2 -5 1/2
S2 0 -3 2/3 0 1 2/3 0 0 - 2/3 0 4
0 1 1/3 0 0 2/3 -2 0 - 2/3 2 2
S5 0 1 1/3 0 0 - 1/3 0 1 1/3 0 4 3

r 0 0 0 0 0 0 0 -1 -1 0

X1 1 0 0 0 -½ 1/2 0 1/2 - 1/2 1/2

X2 0 1 0 0 ½ -1 1/2 0 - 1/2 1 1/2 1 1/2

S1 0 0 1 0 0 1 0 0 -1 3

S2 0 0 0 1 2½ -5 1/2 0 -2 1/2 5 1/2 9 1/2

S5 0 0 0 0 -1 2 1 1 -2 2

Se pueden observar el cumplimiento de criterio de optimalidad para el caso de minimización y el

logro del objetivo de la primera fase, que es eliminación de las variables artificiales. Ahora se tiene
la solución factible propia del modelo en cuestión que se puede considerar como la solución inicial
de la Fase 2:

FASE II

Volviendo a la función objetivo del modelo se puede observar el desajuste con la solución inicial
obtenida en la primera fase (las variables ya no están con valores 0).
Z = 7X1 – 2X2  min
Z – 7X1 +2X2 = 0; pero de acuerdo a la solución inicial Z=7*(1/2)-2*(3/2)=7/2-3=1/2

Así que se realiza el ajuste con las operaciones elementales matriciales (ver condiciones arriba):

VAR X1 X2 S1 S2 S3 S4 S5 SOL
 BASICA
S
Z -7 2 0 0 0 0 0 0
X1 1 0 0 0 -½ 1/2 0 1/2
(-) X2 0 1 0 0 ½ -1 1/2 0 1 1/2
X1*(-7) -7 0 0 0 7/2 -7/2 0 -7/2
X2*2 0 2 0 0 1 -3 0 3
Z 0 0 0 0 -4 ½ 6 1/2 0 1/2

Ahora se llena la tabla simplex completamente, con la Z ajustada y todas las ecuaciones de la
forma estándar y se procede con el algoritmo de simplex:

VAR
BASICA
S X1 X2 S1 S2 S3 S4 S5 SOL
13 0 0 0 -6 5/6 6 1/2 0 6 1/2
Z 0 0 0 0 -4 ½ 6 1/2 0 1/2

x1 1 0 0 0 -½ 1/2 0 1/2 1
-3 0 0 0 1½ -1 1/2 0 -1 1/2
x2 0 1 0 0 ½ -1 1/2 0 1 1/2
2 0 0 0 -1 1 0 1
S1 0 0 1 0 0 1 0 3 3
-11 0 0 0 5½ -5 1/2 0 -5 1/2
S2 0 0 0 1 2½ -5 1/2 0 9 1/2
4 0 0 0 -2 2 0 2
S5 0 0 0 0 -1 2 1 2 1
-8 0 0 0 2 0 2 0
Z -13 0 0 0 2 0 0 -6
4 0 0 0 -1 0 -1 0
S4 2 0 0 0 -1 1 0 1
4 0 0 0 -1 0 -1 0
x2 3 1 0 0 -1 0 0 3
-4 0 0 0 1 0 1 0
S1 -2 0 1 0 1 0 0 2 2
12 0 0 0 -3 0 -3 0
S2 11 0 0 1 -3 0 0 15

S5 -4 0 0 0 1 0 1 0 0

Z -5 0 0 0 0 0 -2 -6

S4 -2 0 0 0 0 1 1 1

X2 -1 1 0 0 0 0 1 3
 S1 2 0 1 0 0 0 -1 2

S2 -1 0 0 1 0 0 3 15

S3 -4 0 0 0 1 0 1 0

Logrando las condiciones de optimalidad para la minimización de la función-objetivo Z se tiene

SOLUCIÓN ÓPTIMA:

X1 = 0 X2 =3 S1=2 S2=15 S3=0 S4=1 S5 = 0

Z=-6

Para verificar el resultado el modelo se soluciona con el método gráfico:

SOLUCIÓN GRÁFICA
 X2

X1

De la solución gráfica se tiene la solución óptima: X1 = 0, X2 = 3, Z = -6