Metodo Simplex Trabajo De Investigacion De Operaciones
Páginas: 12 (2985 palabras)
Publicado: 15 de octubre de 2012
Método Simplex
El mejor método para resolver un problema de programación lineal es el método simplex, ya que es un método de fácil aplicación, de tipo algorítmico y conduce a una eficiente solución del problema.
Este método Simplex, consiste en un proceso iterativo a partir de una solución básica factible inicial que llevará, si existe, a una solución optima moviéndose del vérticecorrespondiente a la solución actual a un vértice adyacente que mejore al anterior. Precisaremos un problema en forma estándar luego si el problema no es de Maximizar o si las restricciones circunstanciales son inecuaciones tendremos que Modificarlo previamente a afrontar su resolución. Si el programa pide minimizar una función objetivo z, bastará tomar como función objetivo z0 = −z manteniendo lasrestricciones, ya que el máximo de esa función será el opuesto del mínimo de z.
Si una restricción circunstancial es una inecuación de menor o igual añadiremos una nueva variable a la restricción de modo que alcanzara la igualdad. Dicha variable, que se denominara variable de holgura, no deberá influir en el valor de la función en el punto óptimo. Para ello la incluiremos en la función objetivo concoeficiente nulo. Si la inecuación fuese de mayor o igual restaremos una nueva variable de holgura a la restricción 1 y añadiremos una variable artificial sumando. Tanto esta variable artificial como la de holgura no han de influir en el valor de la función en el ´optimo. Entonces les daremos en la función objetivo los valores cero (para la de holgura) y −M con M un numero positivo muy grande. De estemodo la Variable artificial abandonara la base rápidamente pues su presencia reduce el valor de la función objetivo a maximizar.
El enfoque propuesto aquí, es utilizar la computadora como una herramienta de apoyo para resolver problemas de Programación Lineal de cualquier tamaño. Sin embargo, se deben estudiar primero los fundamentos de estos métodos de solución para posteriormente utilizar lacomputadora para este fin. Algunos de los paquetes de software comercial más conocidos son: el Storm, el WinQSB, Lindo, Eureka, etc.
Los pasos para resolver un problema por el método simplex
1. Elaborar la tabla simplex inicial.
Existen cuatro variables de holgura, S1, S2, S3, y S4; una para cada restricción.
2. Si todos los indicadores del último renglón son no negativos, entonces Z tieneun máximo cuando X1=0, X2=0 y X3=0. El valor máximo es 0. Si existen indicadores negativos, localizar la columna en la que aparezca el indicador más negativo. Esta columna señala la variable entrante.
3. Dividir cada uno de los elementos de la columna de b que se encuentran por encima de la recta punteada entre el correspondiente elemento de la columna de la variable entrante. Se debe realizaresta división solo en los casos en los que el elemento de la variable que entra sea positivo.
4. encerrar en un círculo el elemento de la columna de la variable entrante que corresponde al menor cociente del paso 3. Este es un elemento pivote. La variable saliente es la que se encuentra al lado izquierdo del renglón del elemento pivote.
5. Utilizar operaciones elementales sobre renglonespara transformar la tabla en otra tabla equivalente que tenga un 1 en donde se encuentra el elemento pivote y 0 en las demás posiciones de esa columna.
6. la variable entrante debe reemplazar a la variable saliente en el lado izquierdo de esta nueva tabla.
7. si todos los indicadores de la tabla nueva son no negativos, ya se tiene una solución óptima. El valor máximo de Z es el elemento delúltimo renglón y la última columna. Ocurre esto cuando las variables se encuentran del lado izquierdo de la tabla son iguales a lo elementos correspondiente de la última columna. Todas las demás variables son ceros. Si cuando menos uno de los indicadores es negativo, se debe repetir el mismo proceso con la nueva tabla, comenzando con el paso 2.
Teoría de Dualidad
A nuestro programa lineal lo...
El mejor método para resolver un problema de programación lineal es el método simplex, ya que es un método de fácil aplicación, de tipo algorítmico y conduce a una eficiente solución del problema.
Este método Simplex, consiste en un proceso iterativo a partir de una solución básica factible inicial que llevará, si existe, a una solución optima moviéndose del vérticecorrespondiente a la solución actual a un vértice adyacente que mejore al anterior. Precisaremos un problema en forma estándar luego si el problema no es de Maximizar o si las restricciones circunstanciales son inecuaciones tendremos que Modificarlo previamente a afrontar su resolución. Si el programa pide minimizar una función objetivo z, bastará tomar como función objetivo z0 = −z manteniendo lasrestricciones, ya que el máximo de esa función será el opuesto del mínimo de z.
Si una restricción circunstancial es una inecuación de menor o igual añadiremos una nueva variable a la restricción de modo que alcanzara la igualdad. Dicha variable, que se denominara variable de holgura, no deberá influir en el valor de la función en el punto óptimo. Para ello la incluiremos en la función objetivo concoeficiente nulo. Si la inecuación fuese de mayor o igual restaremos una nueva variable de holgura a la restricción 1 y añadiremos una variable artificial sumando. Tanto esta variable artificial como la de holgura no han de influir en el valor de la función en el ´optimo. Entonces les daremos en la función objetivo los valores cero (para la de holgura) y −M con M un numero positivo muy grande. De estemodo la Variable artificial abandonara la base rápidamente pues su presencia reduce el valor de la función objetivo a maximizar.
El enfoque propuesto aquí, es utilizar la computadora como una herramienta de apoyo para resolver problemas de Programación Lineal de cualquier tamaño. Sin embargo, se deben estudiar primero los fundamentos de estos métodos de solución para posteriormente utilizar lacomputadora para este fin. Algunos de los paquetes de software comercial más conocidos son: el Storm, el WinQSB, Lindo, Eureka, etc.
Los pasos para resolver un problema por el método simplex
1. Elaborar la tabla simplex inicial.
Existen cuatro variables de holgura, S1, S2, S3, y S4; una para cada restricción.
2. Si todos los indicadores del último renglón son no negativos, entonces Z tieneun máximo cuando X1=0, X2=0 y X3=0. El valor máximo es 0. Si existen indicadores negativos, localizar la columna en la que aparezca el indicador más negativo. Esta columna señala la variable entrante.
3. Dividir cada uno de los elementos de la columna de b que se encuentran por encima de la recta punteada entre el correspondiente elemento de la columna de la variable entrante. Se debe realizaresta división solo en los casos en los que el elemento de la variable que entra sea positivo.
4. encerrar en un círculo el elemento de la columna de la variable entrante que corresponde al menor cociente del paso 3. Este es un elemento pivote. La variable saliente es la que se encuentra al lado izquierdo del renglón del elemento pivote.
5. Utilizar operaciones elementales sobre renglonespara transformar la tabla en otra tabla equivalente que tenga un 1 en donde se encuentra el elemento pivote y 0 en las demás posiciones de esa columna.
6. la variable entrante debe reemplazar a la variable saliente en el lado izquierdo de esta nueva tabla.
7. si todos los indicadores de la tabla nueva son no negativos, ya se tiene una solución óptima. El valor máximo de Z es el elemento delúltimo renglón y la última columna. Ocurre esto cuando las variables se encuentran del lado izquierdo de la tabla son iguales a lo elementos correspondiente de la última columna. Todas las demás variables son ceros. Si cuando menos uno de los indicadores es negativo, se debe repetir el mismo proceso con la nueva tabla, comenzando con el paso 2.
Teoría de Dualidad
A nuestro programa lineal lo...
Leer documento completo
Regístrate para leer el documento completo.