Condiciones Del Metodo Simplex

Condición de Optimalidad.

La variable de entrada en un problema de maximización, es la variable no básica con el coeficiente objetivo más negativo en la fila z, para el caso de la minimización seria la variable no básica más positiva en la fila z. los vínculos se rompen arbitrariamente. El optimo se alcanza en la iteración en la cual los coeficientes en la fila z son no negativos (para maxi) y no positivos (para mini).

Condición de Factibilidad.

Tanto en problemas de maximización como de minimización, la variable de salida es la variable básica asociada con la relación mínima no negativa con el denominador estrictamente positivo. Los vínculos se rompen arbitrariamente.

Condiciones de Optimalidad y Factibilidad.

Como un ejemplo de los dos anteriores casos tomaremos un ejercicio visto en clase. Es el modelo de Reddy Mikks. Después de llevar a cabo la primera iteración existe la pregunta de si es optima esta solución inicial (z=0, s1=24, s2=6, s3=2, s4=1)? La función objetivo z=5x1+4x2 muestra que la solución puede mejorarse si se incrementa el valor de la variable x1 o de la x2 no básica por encima de cero, entonces x1 tiene que incrementarse porque tiene el coeficiente objetivo más positivo. De forma equivalente, en la tabla simplex donde la función objetivo aparece como z-5x1-4x2=0, la variable seleccionada es la variable no básica con el coeficiente más negativo en la ecuación objetivo. Esta regla define la llamada condición de Optimalidad simplex. En la terminología del algortimo simplex, x1 se conoce como la variable de entrada porque ingresa la solución básica.

Si x1 es la variable de entrada, una de las variables básicas actuales debe salir; es decir, se vuelve no básica a un nivel cero (recordando que la cantidad de variables no básicas debe ser siempre n-m). la mecánica para determinar la variable de salida implica calcular las relaciones del lado derecho de las ecuaciones (columna solución) con los coeficientes de restricción estrictamente positivos (imposibilitando asi el cero) bajo la variable de entrada, x1.

Pero como determinan las relaciones calculadas la variable de salida y el valor de la variable de entrada?, sabiendo que las relaciones calculadas son en realidad las intersecciones de las líneas de restricción con el eje x1 (variable de entrada). El valor de x1 debe de incrementarse hasta la intersección no negativa mínima con el eje x1 (=4), para alcanzar el punto de esquina B (punto de esquina del espacio de región de solución factible). Cualquier incremento mas allá de B no es factible, en el punto B la variable básica actual s1 asociada con la primera restricción del problema ya plantado asume un valor se cero y se transforma en la variable de salida. La Regla asociada con las relaciones calculadas se conoce como condición de factibilidad

...