1.4 PROBLEMAS POR EL METODO SIMPLEX

1 El Método Simplex

Es un procedimiento iterativo que permite mejorar la solución de la función objetivo en cada paso. El proceso concluye cuando no es posible continuar mejorando dicho valor, es decir, se ha alcanzado la solución óptima. Partiendo del valor de la función objetivo en un punto cualquiera, el procedimiento consiste en buscar otro punto que mejore el valor anterior (puntos del polígono de zona factible) El método Simplex únicamente trabaja con restricciones del problema cuyas inecuaciones sean del tipo "≤" (menor o igual) y sus coeficientes independientes sean mayores o iguales a 0. Estandarizar las restricciones para que cumplan estos requisitos antes de iniciar el algoritmo del Simplex.

2. Estandarización del Modelo PL a Simplex Modelo PL Forma Estándar del Modelo PL Función Objetivo:

 Maximizar o Minimizar Todas las restricciones deben ser ecuaciones de igualdad. Todas las variables (xi) deben tener valor positivo o nulo (condición de no negatividad). Los términos independientes (bi) de cada ecuación deben ser no negativos.

3. Tipo de Optimización Maximización Condición de parada

Cuando en la fila Z no aparece ningún valor negativo. Condición de entrada a la base: El menor valor negativo en la fila Z (mayor valor absoluto entre los negativos) indica la variable Pj que entra a la base. Condición de salida de la base: Una vez obtenida la variable entrante, la variable que sale se determina mediante el menor cociente P0/Pj de los estrictamente positivos. Minimización Condición de parada: Cuando en la fila Z no aparece ningún valor positivo. Condición de entrada a la base: El mayor valor positivo en la fila Z indica la variable Pj que entra a la base. Condición de salida de la base: Una vez obtenida la variable entrante, la variable que sale se determina mediante el menor cociente P0/Pj de los estrictamente negativos.

4. Observaciones con la Minimización

 Es posible normalizar el objetivo del problema con el fin de aplicar siempre los mismos criterios en lo referente a la condición de parada del algoritmo y a las condiciones de entrada y salida de las variables de la base. Si el objetivo es minimizar la solución, se puede cambiar el problema a otro equivalente de maximización simplemente multiplicando la función objetivo por "-1". Minimizar Z = Maximizar (-1) •Z. Una vez obtenida la solución será necesario multiplicarla también por (-1). Ventajas: No hay que preocuparse por nuevos criterios de parada, condición de entrada y salida de la base ya que se mantienen. Inconvenientes: En el caso de que la función tenga todos los coeficientes de sus variables básicas positivos, y además las restricciones sean del tipo de desigualdad "≤", al hacer el cambio dichos coeficientes quedan negativos cumpliéndose la condición de parada en la primera iteración (en la fila del valor de la función objetivo todos los valores son positivos o cero). Obteniéndose en este caso por defecto un valor óptimo para la función igual a 0. Solución: Realmente no existe este problema dado que para que la solución sea superior a 0 es necesario que alguna restricción tenga impuesta la condición "≥" (y se trataría de un modelo para el método de las Dos Fases). En el caso planteado, la solución real debe ser cero.

5. Cambio de signo de los términos independientes

Si alguna de las restricciones presenta un término independiente menor que 0 habrá que multiplicar por "-1" ambos lados de la inecuación. Los términos independientes (bi) de cada ecuación deben ser no negativos para poder emplear el método Simplex. • Con ésta simple modificación de signos en las restricciones correspondientes se posibilita la aplicación del método Simplex al problema modelado. Ventajas: • Puede resultar que en las restricciones donde tengamos que modificar los signos de las constantes, los tipos de desigualdad fueran "≤" (quedando tras la operación del tipo "≥") siendo necesario desarrollar el método de las Dos Fases. Inconvenientes:

6. Normalización de Restricciones

Todas las restricciones sean ecuaciones de igualdad, por lo que hay que convertir las desigualdades en igualdades. La condición de no negatividad de las variables (x1,..., xn ≥ 0) es la única excepción y se mantiene tal cual. Tipo de Desigualdad Tipo de Variable que aparece ≥ - exceso + artificial = + artificial ≤ + holgur

7. Algoritmo Simplex

Ejemplo

Siendo Xi la cantidad a producir del producto i.

Maximizar Z = X1 + X2  {Ganancia total en soles}

S.A.

5X1 + 3X2 <= 15           {Horas disponibles dep. A}

3X1 + 5X2 <= 15           {Horas disponibles dep. B}

Xj >= 0 ; j = 1, 2

Los problemas de Maximización, con todas sus restricciones <= y con la condición de no negatividad, se le llama Forma Estándar o Forma Normal

Aquí debemos conseguir una solución básica factible, empleando las variables de holgura y/o artificiales, quedando el sistema de ecuaciones así:

Maximizar Z = X1 + X2

S.A.

5X1 + 3X2 + X3             = 15

3X1 + 5X2 +      X4        = 15

Xj >= 0 ; j = 1,2,3,4

Las variables básicas son aquellas cuyos coeficientes forman la matriz unitaria.

En este caos accidentalmente son las variables de holgura X3 y X4.

El valor de la función objetivo Z, se encuentra frente a la casilla de Zj – Cj , en éste caso vale cero (0) y se calcula multiplicando el vector fila (en la tabla es la columna inmediatamente anterior a la de las variables básica V.B.) que contiene los coeficientes de las variables básicas en la función objetiva original por el vector columna de los términos independientes b

CX_B = Vector fila de los coeficientes en la función objetivo original de las variables básicas actuales, sus valores se encuentran en la primera columna del tablero.

b = Vector columna de los términos independientes de las restricciones, que al mismo tiempo son los valores de las variables básicas actuales, sus valores se encuentran bajo la columna denominada b

CX_B = (0,0) ; b = (15,15)’           Z = CX_B * b = (0)(15) + (0)(15) = 0

El valor de los Zj – Cj se calcula multiplicado el vector fila CX_B por el vector apuntador aj dela columna de la variable j-ésima, menos el Cj, esto es:

Zj – Cj = CX_B. aj – Cj ;

Los cálculos se efectúan así:

Z1 – C1 = CX_B a1 – C1 = (0,0).(5,3)’ – 1 = (0)(5)+(0)(3) – 1 = -1

Z2 – C2 = CX_B a2 – C2 = (0,0).(3,5)’ – 1 = (0)(3)+(0)(5) – 1 = -1

Z3 – C3 = CX_B a3 – C3 = (0,0).(1,0)’ – 0 = (0)(1)+(0)(0) – 0 = 0

Z4 – C4 = CX_B a4 – C4 = (0,0).(0,1)’ – 0 = (0)(0)+(0)(1) – 0 = 0

A continuación se indican la variable que sale y la variable que entra:

Cj			1	1	0	0	b/a a>0
	V.B.	B	X1	X2	X3	X4
0	X3	15	5	3	1	0	15/5=3
0	X4	15	3	5	0	1	15/3=5
Zj – Cj		0	-1	-1	0	0

Variable que entra X1

Variable que sale X3

La variable que tiene Zj-Cj más negativo es ó X1 ó X2. Se escoge al azar X1.

En esta iteración b/a da: 15/5 = 3 y 15/3 = 5;

Lo que significa que la variable básica X3 restringe el crecimiento de la variable que entra, X1, hasta 3 (no la deja tomar valores superiores a 3) y la variable básica X4 restringe el crecimiento de la variable que entra X1 hasta 5 (no la deja tomar valores superiores a 5).

Conclusión del método simplex

El método simplex es un algoritmo eficiente y confiable para resolver problemas de programación lineal. También proporciona la base para llevar a cabo, en forma muy eficiente, las distintas etapas del análisis pos óptimo.

Aunque tiene una interpretación geométrica útil, el método simplex es un procedimiento algebraico. En cada iteración se mueve de la solución básica factible actual a una adyacente mejor eligiendo tanto la variable básica entrante como la que sale y después usando la eliminación de Gauss para resolver el sistema de ecuaciones lineales. Cuando la solución actual no tiene una solución básica factible adyacente que sea mejor, la solución actual es óptima y el algoritmo se detiene.

Se presentó la forma algebraica completa del método simplex para establecer su lógica y se llevó el método a una forma tabular más conveniente. Para preparar el inicio del método simplex, algunas veces es necesario obtener una solución básica factible inicial para un problema revisado. En este caso se puede usar el método de la M, o bien, el método de las dos fases, para asegurar que el método símplex obtenga una solución óptima para el problema original.

Los paquetes de software para computadoras personales basados en el método simplex están ampliamente difundidos y al alcance, para manejar problemas de tamaño modesto. Los programas para computadoras grandes se usan por rutina para resolver y analizar problemas con muchos cientos y aun miles de funciones de restricción y variables.

El algoritmo de puntos interiores de Karmarkar proporciona una nueva herramienta poderosa para resolver problemas muy grandes.