Metodo SIMPLEX primal

3) Metodo SIMPLEX primal

El método símplex primal parte de una solución básica factible (punto extremo) y se continúa iterando a través de soluciones básicas factibles sucesivas hasta alcanzar el óptimo. La figura 3-1 ilustra la aplicación de este proceso al modelo Reddy Mikks. El proceso comienza en el origen extremo (punto A) y se mueve a lo largo del borde AB del espacio de soluciones hasta el punto extremo adyacente B (iteración 1). De 5B se mueve a lo largo del borde BC hasta el punto extremo adyacente C (iteración

2), que es el óptimo. Obsérvese que el procedimiento no es capaz de cortar a través del espacio de soluciones (por ejemplo, de A a C) sino que siempre debe moverse a lo largo de bordes entre puntos extremos adyacentes.

¿Cómo se expresa algebraicamente el procedimiento iterativo indicado antes? Todo foque tenemos que hacer es mostrar cómo se identifican los puntos extremos, tales como el A, B y C, sin utilizar la gráfica de] espacio de soluciones. Consideremos el modelo Reddy Mikks dado enseguida en su forma estándar:

Maximizar Z= 3x5 + 2x1 + Os3 + 0.s + Os, + 054

El método simplex dual resulta ser una estrategia algoritmica eficiente cuando luego de llevar un modelo de programación lineal a su forma estándar, la aplicación del método simplex no es inmediata o más bien compleja, por ejemplo, puede requerir la utilización del método simplex de 2 fases.

Una aplicación típica del método simplex dual es en la resolución de problemas con una función objetivo de minimización, con restricciones del tipo mayor o igual y donde las variables de decisión son mayores o iguales a cero.

Ejemplo Simplex Dual

Ejemplo Simplex Dual

Considere el siguiente modelo de Programación Lineal:

ejemplo_simplex_dualTodas

las restricciones deben ser del tipo menor o igual que, con el lado derecho positivo, la función objetivo debe ser de maximización y todas las variables son no negativas.

Se introducen las variables holgura se seleccionan las variables de decisión como las variables no básicas iníciales, y as variables holgura como las variables básicas iníciales.

Paso 1: Se lleva el modelo a su forma estándar. En nuestro ejemplo esto se logra agregando variables de exceso en cada una de las restricciones (3 primeras: S1, S2, S3, respectivamente). Luego, se multiplica cada fila de las restricciones por -1 de modo de disponer una solución básica inicial (infactible) en las variables de exceso S1, S2 y S3. De esta forma se obtiene la siguiente tabla inicial.

Paso 2: Se selecciona el lado derecho "más negativo" lo cual indicará cuál de las actuales variables básicas deberá abandonar la base. En el ejemplo el lado derecho más negativo se encuentra en la primera fila, por tanto S1 deja la base. Para determinar cual de las actuales variables no básicas (A, B, C) entrará a la base se busca el mínimo de {-Yj/aij} donde aij es el coeficiente de la respectiva variable no básica en la fija i (del lado derecho más negativo, marcado en verde) y donde Yj es el costo reducido de la respectiva variable no básica. De esta forma se obtiene: Min {-315/-15, -110/-2, -50/-1} = 21, donde el pivote (marcado en rojo) se encuentra al hacer el primer cuociente, por tanto A entra a la base.

Paso 3: Se actualiza la tabla anterior siguiendo un procedimiento similar al utilizado en el Método Simplex. En el ejemplo se debe dejar a la variable A como básica y S1 como no básica. La tabla que resulta es la siguiente:

arte de una solución óptima infactible, la diferencia con el

método simplex primal está en las condiciones para la

variable que entra y la variable que sale:

Condición de Factibilidad: La variable que sale es aquella

variable básica con valor más negativo, si todas son no

negativas el proceso termina.

Condición

...