Metodo simplex

Guía III: Método Simplex                                                                                    Investigación de Operaciones I  

EL METODO SIMPLEX PARA SOLUCIÓN DE PROBLEMAS DE PROGRAMACIÓNLINEAL El método del simplex fue creado en 1947 por el matemático George Dantzig. El método del simplex se utiliza, sobre todo, para resolver problemas de programación lineal en los queintervienen tres o más variables. El álgebra matricial y el proceso de eliminación de Gauss-Jordan para resolver un sistema de ecuaciones lineales constituyen la base del método simplex. Concepto: Es un procedimiento iterativo que permite ir mejorando la solución a cada paso. El proceso concluye cuando no es posible seguir mejorando más dicha solución. Partiendo del valor de la función objetivo en unvértice cualquiera, el método consiste en buscar sucesivamente otro vértice que mejore al anterior. La búsqueda se hace siempre a través de los lados del polígono (o de las aristas del poliedro, si el número de variables es mayor). Cómo el número de vértices (y de aristas) es finito, siempre se podrá encontrar la solución. El método del simplex se basa en la siguiente propiedad: “Si la función objetivo,f, no toma su valor máximo en el vértice A, entonces hay una arista que parte de A, a lo largo de la cual f aumenta”. Formas estándar y canónicas En el desarrollo que a continuación se presenta se usa la siguiente forma de la programación lineal, denominada forma canónica. Máx Z = cX Sujeto a

Cualquier otra forma es equivalente a la anterior. Esta equivalencia se prueba fácilmente por mediodel uso de cualquiera de las siguientes 5 reglas. Regla 1 Maximizar cX es equivalente a Minimizar –cX Minimizar cX es equivalente a Maximizar –cX Ejemplo: a) es equivalente a :

Es equivalente a : Regla 2 a. La desigualdad es equivalente a la desigualdad . 1

Ing(a). Analui Martínez de Gomez                                                   UNEFA:     Ingeniería de Sistemas Guía III: Método Simplex                                                                                    Investigación de Operaciones I  

b. La desigualdad Ejemplo:

es equivalente a la desigualdad -

.

es equivalente a

es equivalente a

Regla 3 Toda igualdad de la forma y desigualdades Ejemplo: es equivalente a , puede descomponerse como la intersección de dos

Regla 4 Toda desigualdad de la formapuede convertirse en igualdad mediante la adición de un vector Y, llamado de holgura. El vector columna Y tiene m componentes, todas ellas no negativas, es decir

puede convertirse en igualdad mediante la resta de un vector Toda desigualdad de la forma Z, llamado superfluo. El vector columna Z, tiene m componentes, todas no – negativas, es decir:

Ejemplo:

a)

es equivalente aIng(a). Analui Martínez de Gomez                                                   UNEFA:     Ingeniería de Sistemas 

2

Guía III: Método Simplex                                                                                    Investigación de Operaciones I  

Donde el vector de holgura es

b)

es equivalente a

Donde el vector de exceso o superfluo es

Regla 5 Una variable no restringida,o sea aquella que puede tomar toda clase de valores positivos, cero y negativos puede escribirse como la diferencia de dos variables no – negativas. Propiedades de la forma de PL Estándar Todas las restricciones son ecuaciones (con los segundos miembros no negativos, si el modelo se resuelve por medio del método símplex primal). Todas las variables son no negativas. La función objetivo puede serla maximización o minimización. Soluciones Básicas El modelo estándar de PL esta definido con m ecuaciones y n incógnitas, la solución básica asociada se determina haciendo n-m variables iguales a cero y luego resolviendo las m ecuaciones con las restantes variables, siempre que la solución resultante sea única. Ejemplo: 2X1+X2+4X3+X4=2 X1+2X2+2X3+X4=3 m=2 y n=4 Entonces una solución...