Reglas lexicográficas
# Reglas lexicográficas

En programación lineal comúnmente se usa el método Simplex, el cual permite optimizar determinados modelos. Sin embargo, frecuentemente existen problemas al aplicarlo ya que se puede generar un ciclo en el momento de escoger la fila pivote.

Frente a esto aparecen las reglas lexicográficas o el método lexicográfico que aseguran la no formación de bucles en los tableros del Simplex y la selección correcta de la fila pivote en caso de empate.

## Definición

Un vector es lexicográficamente positivo si el primer valor de la columna (que no sea la columna pivote) es igual o mayor a cero . De esta forma:

Min Z = $X_b$ / $a_{ik}$ con $a_{ik}$ > 0

De la misma forma:

Min Z = $a_{1k}$ / $a_{ik}$ con $a_{ik}$ > 0

Siendo $a_{ik}$ el vector lexicográficamente positivo y $X_b$ el componente de la base.

## Aplicación

Al existir empate entre dos filas de la columna pivote simplemente se toma las componentes $a_{ik}$ correspondientes a cada una de las filas y se dividen con la respectiva componente de la columna pivote $(a_{ij}),$ de la siguiente forma:

| $a_{11}/a_{1j}$ | $a_{12}/a_{1j}$ | ... | 1 | ... | $a_{1m}/a_{1j}$ |
| - | - | - | - | - | - |
| $a_{21}/a_{2j}$ | $a_{22}/a_{2j}$ | ... | 1 | ... | $a_{2m}/a_{2j}$ |
| $a_{31}/a_{3j}$ | $a_{32}/a_{3j}$ | ... | 1 | ... | $a_{3m}/a_{3j}$ |

Como las filas son linealmente independientes ningún par de filas divididas son idénticas. Se debe encontrar la primera columna donde se rompa el empate ignorando todas las filas que no tengan el valor más bajo. Si únicamente una fila queda, esta será la fila pivote, si quedan más se deberán probar en las columnas adicionales .

