Marketing
Páginas: 6 (1381 palabras)
Publicado: 25 de noviembre de 2011
“Simplex Dual”
Aejandro Teyssier Montufar 9101037
Vinny Yeudiel Romero Vela 9101090
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 mejores hasta encontrar la solución óptima (sí esta existe). Nótese que la base de su lógica es mantener la factibilidad, mientras busca laoptimalidad. Pero surge la posibilidad de usar otro esquema igualmente 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 llega igualmente a la solución óptima.
El nuevo algoritmo fue desarrollo en 1954 por C. E. Lemke y se conoce con el nombre de MétodoDual-Simplex. A continuación se presenta su estructura y un ejemplo para ilustrar su aplicación.
En el algoritmo dual símplex, el problema empieza optimo y no factible. Las iteraciones sucesivas están diseñadas para avanzar hacía la factibilidad, sin violar la optimalidad. En iteración, cuando se restaura la factibilidad, el algoritmo termina.
El método dual símplex contrasta con el métodoregular (primal simplex), en el sentido de que las iteraciones empiezan factibles y no optimas y no continúan siendo factibles hasta que se logra la factibilidad.
En el método dual símplex, el cuadro simplex inicial debe tener un renglón objetivo optimo por lo menos con una variable básica no factible (< 0). Para mantener la optimalidad y, simultáneamente, avanzar hacia la factibilidad en cada nuevaiteración, se emplearan las dos condiciones siguientes:
Condición Dual de Factibilidad: La variable de salida, x, es la variable básica que tiene el valor más negativo, con empates que se rompen arbitrariamente. Si todas las variables básicas son no negativas, el algoritmo termina.
Condición Dual de Optimalidad : La variable de entrada esta determinada entre las variables no básicas como lacorrespondiente a
min {øzj - cj ø, rj < 0}
no básicas =rj
Donde = rj
es el coeficiente de restricción de la tabla símplex asociada con el renglón de la variable de salida x, y la columna de la variable de entrada Xj. Los empates se rompen arbitrariamente.
CALCULOS PRIMALES DUALES:
Al hacer el análisis de sensibilidad, nos interesamos en un resultado principal: si los cambios enlos coeficientes del modelo cambiaran (la optimilida o la factibilidad) de la solución actual. De ser así ¿ Cómo es posible determinar la nueva optima (sí existe una)?.
Para obtener los resultados deseados de una manera eficiente, necesitamos comprender como los cálculos símplex se ven afectados cuando se hacen cambios en los coeficientes originales del modelo. En particular, ¿Cómo se venafectadas la optimalidad (coeficientes del renglón objetivo) y la factibilidad lado derecho de la tabla símplex cuando se hacen estos cambios?
Una forma compacta de seguir los cálculos símplex es utilizando matrices, solo se necesitan tres operaciones elementales de matriz que son: (vector de renglón) X (matriz), (matriz) X (vector de columna) y (escalar) X (matriz). Estas operaciones se introducenaquí por conveniencia. Primero empezamos con algunas definiciones.
ANALISIS POSTÓPTIMO O DE SENSIBILIDAD
El análisis de sensibilidad se hace después de obtener la solución óptima (actual) de un modelo de PL. La meta es determinar si los cambios en los coeficientes del modelo dejaran inalterada la solución actual y, de no ser así, como obtener con eficiencia una manera optima (suponiendo queexiste una).
En general los cambios en el modelo dan por resultado uno de cuatro casos.
1.-La solución actual (básica) permanece inalterada.
2.-La solución actual se vuelve no factible.
3.-La solución actual se vuelve no básica.
4.-La solución actual se vuelve no optima así como no factible.
En el caso 2, utilizamos el método dual simplex para recuperar la factibilidad, y en el...
Aejandro Teyssier Montufar 9101037
Vinny Yeudiel Romero Vela 9101090
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 mejores hasta encontrar la solución óptima (sí esta existe). Nótese que la base de su lógica es mantener la factibilidad, mientras busca laoptimalidad. Pero surge la posibilidad de usar otro esquema igualmente 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 llega igualmente a la solución óptima.
El nuevo algoritmo fue desarrollo en 1954 por C. E. Lemke y se conoce con el nombre de MétodoDual-Simplex. A continuación se presenta su estructura y un ejemplo para ilustrar su aplicación.
En el algoritmo dual símplex, el problema empieza optimo y no factible. Las iteraciones sucesivas están diseñadas para avanzar hacía la factibilidad, sin violar la optimalidad. En iteración, cuando se restaura la factibilidad, el algoritmo termina.
El método dual símplex contrasta con el métodoregular (primal simplex), en el sentido de que las iteraciones empiezan factibles y no optimas y no continúan siendo factibles hasta que se logra la factibilidad.
En el método dual símplex, el cuadro simplex inicial debe tener un renglón objetivo optimo por lo menos con una variable básica no factible (< 0). Para mantener la optimalidad y, simultáneamente, avanzar hacia la factibilidad en cada nuevaiteración, se emplearan las dos condiciones siguientes:
Condición Dual de Factibilidad: La variable de salida, x, es la variable básica que tiene el valor más negativo, con empates que se rompen arbitrariamente. Si todas las variables básicas son no negativas, el algoritmo termina.
Condición Dual de Optimalidad : La variable de entrada esta determinada entre las variables no básicas como lacorrespondiente a
min {øzj - cj ø, rj < 0}
no básicas =rj
Donde = rj
es el coeficiente de restricción de la tabla símplex asociada con el renglón de la variable de salida x, y la columna de la variable de entrada Xj. Los empates se rompen arbitrariamente.
CALCULOS PRIMALES DUALES:
Al hacer el análisis de sensibilidad, nos interesamos en un resultado principal: si los cambios enlos coeficientes del modelo cambiaran (la optimilida o la factibilidad) de la solución actual. De ser así ¿ Cómo es posible determinar la nueva optima (sí existe una)?.
Para obtener los resultados deseados de una manera eficiente, necesitamos comprender como los cálculos símplex se ven afectados cuando se hacen cambios en los coeficientes originales del modelo. En particular, ¿Cómo se venafectadas la optimalidad (coeficientes del renglón objetivo) y la factibilidad lado derecho de la tabla símplex cuando se hacen estos cambios?
Una forma compacta de seguir los cálculos símplex es utilizando matrices, solo se necesitan tres operaciones elementales de matriz que son: (vector de renglón) X (matriz), (matriz) X (vector de columna) y (escalar) X (matriz). Estas operaciones se introducenaquí por conveniencia. Primero empezamos con algunas definiciones.
ANALISIS POSTÓPTIMO O DE SENSIBILIDAD
El análisis de sensibilidad se hace después de obtener la solución óptima (actual) de un modelo de PL. La meta es determinar si los cambios en los coeficientes del modelo dejaran inalterada la solución actual y, de no ser así, como obtener con eficiencia una manera optima (suponiendo queexiste una).
En general los cambios en el modelo dan por resultado uno de cuatro casos.
1.-La solución actual (básica) permanece inalterada.
2.-La solución actual se vuelve no factible.
3.-La solución actual se vuelve no básica.
4.-La solución actual se vuelve no optima así como no factible.
En el caso 2, utilizamos el método dual simplex para recuperar la factibilidad, y en el...
Leer documento completo
Regístrate para leer el documento completo.