Metodo Simplex
Páginas: 4 (851 palabras)
Publicado: 10 de octubre de 2012
EL MÉTODO DUAL SIMPLEX
Como sabemos, el método simplex es un algoritmo iterativo que iniciando en una solución básica factible pero no óptima, genera soluciones básicas factibles cada vez mejoreshasta encontrar la solución óptima (sí esta existe). Nótese que la base de su lógica es mantener la factibilidad, mientras busca la optimalidad. Pero surge la posibilidad de usar otro esquemaigualmente iterativo, que como contraparte del simplex, comienza en una solución básica óptima, pero no factible y mantiene la inmejorabilidad mientras busca la factibilidad. Con este procedimiento se llegaigualmente a la solución óptima.
El nuevo algoritmo fue desarrollo en 1954 por C. E. Lemke y se conoce con el nombre de Método Dual-Simplex. A continuación se presenta su estructura y un ejemplo parailustrar su aplicación.
Es importante destacar que este proceso es muy útil ya que en muchos modelos evita la inclusión de variables artificiales en el momento de transformar un modelo a formatoestándar.
Cada variable del dual está asociada a una restricción del programa primal, y su valor óptimo represente al incremento de la función objetivo del primal por cada unidad que aumente el términoindependiente de dicha restricción, siempre que este último aumento no suponga un cambio de base. Es, por tanto, el precio adicional máximo que estamos dispuestos a pagar por el incremento del recurso.Los valores de estas variables se denominan precios sombra. De manera analítica, podemos escribir que la variable dual de la restricción i representará:
ui*=∆z∆bi
Los precios sobra obtenidos apartir del óptimo dual serán válidos siempre que no varíe la base óptima. En consecuencia, los resultados obtenidos del dual están íntimamente ligados al análisis de la sensibilidad de los términosindependientes.
El algoritmo para resolver un modelo de maximización es el siguiente:
Paso 1: Hallar una solución básica inicial infactible e inmejorable
Escribir el tablero inicial tomando a las...
Como sabemos, el método simplex es un algoritmo iterativo que iniciando en una solución básica factible pero no óptima, genera soluciones básicas factibles cada vez mejoreshasta encontrar la solución óptima (sí esta existe). Nótese que la base de su lógica es mantener la factibilidad, mientras busca la optimalidad. Pero surge la posibilidad de usar otro esquemaigualmente iterativo, que como contraparte del simplex, comienza en una solución básica óptima, pero no factible y mantiene la inmejorabilidad mientras busca la factibilidad. Con este procedimiento se llegaigualmente a la solución óptima.
El nuevo algoritmo fue desarrollo en 1954 por C. E. Lemke y se conoce con el nombre de Método Dual-Simplex. A continuación se presenta su estructura y un ejemplo parailustrar su aplicación.
Es importante destacar que este proceso es muy útil ya que en muchos modelos evita la inclusión de variables artificiales en el momento de transformar un modelo a formatoestándar.
Cada variable del dual está asociada a una restricción del programa primal, y su valor óptimo represente al incremento de la función objetivo del primal por cada unidad que aumente el términoindependiente de dicha restricción, siempre que este último aumento no suponga un cambio de base. Es, por tanto, el precio adicional máximo que estamos dispuestos a pagar por el incremento del recurso.Los valores de estas variables se denominan precios sombra. De manera analítica, podemos escribir que la variable dual de la restricción i representará:
ui*=∆z∆bi
Los precios sobra obtenidos apartir del óptimo dual serán válidos siempre que no varíe la base óptima. En consecuencia, los resultados obtenidos del dual están íntimamente ligados al análisis de la sensibilidad de los términosindependientes.
El algoritmo para resolver un modelo de maximización es el siguiente:
Paso 1: Hallar una solución básica inicial infactible e inmejorable
Escribir el tablero inicial tomando a las...
Leer documento completo
Regístrate para leer el documento completo.