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:

a11/a1j	a12/a1j	...	1	...	a1m/a1j
a21/a2j	a22/a2j	...	1	...	a2m/a2j
a31/a3j	a32/a3j	...	1	...	a3m/a3j

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 .​

Véase también

• Programación lineal
• Algoritmo símplex
• George Dantzig

Enlaces externos

• El Método Simplex
• El método Simplex Revisado
• Método lexicográfico

• Datos: Q48784857