METODO DUAL SIMPLEX

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étodo regular (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 nueva iteració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 la correspondiente 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.

Ejemplo:

Minimice z = 3x1 + 2x2

Sujeta a

3x1 + x2 " 3

4x1 + 3x2 " 6

x1 + x2 " 3

x1, x2 " 0

La tabla símplex inicial para el problema se da como

Solución básica

factible X1 X2 X3 X4 X5 Solución

z -3 -2 0 0 0 0

X3 -3 -1 1 0 0 -3

X4 -4 -3 0 1 0 -6

X5 1 1 0 0 1 3

Las variables X3 y X4 son superávit, mientras que X5, es una holgura

CALCULOS PRIMALES DUALES:

Al hacer el análisis de sensibilidad, nos interesamos en un resultado principal: si los cambios en los 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 ven afectadas 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 introducen aquí 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 que existe 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 caso 3 utilizamos el método símplex (primal) para obtener la nueva óptima. En el caso 4, utilizamos los métodos primal y dual para obtener la nueva solución. Los tres primeros pasos se investigan posteriormente. El curto caso, debido a que es una combinación del caso 2 y 3, se trata en Problemas integrales.

Cambios Que Afectan La Factibilidad

La factibilidad de la solución optima actual puede resultar afectada únicamente sí(1) se cambia al lado derecho de las restricciones b, o (2) si se añade una nueva restricción al modelo. En ambos casos la no factibilidad ocurre cuando por lo menos uno de los elementos B ¹ b se vuelve negativo, es decir, si una o mas variables básicas actuales se vuelve negativa.

Cambios discretos en el vector b del lado derecho.

Esta sección considera el caso en que se hacen cambios específicos discretos en uno o mas de los elementos del vector b.

PROGRAMACIÓN LINEAL PARAMETRICA

La programación lineal paramétrica, investiga los cambios en la solución óptima de la PL que son el resultado de variaciones continuas predeterminadas en los coeficientes de la función objetivo y en el lado derecho de las restricciones.

Algunas presentaciones de PL pueden dar la impresión de que la programación lineal paramétrica aplica únicamente a las variaciones lineales paramétricas. De hecho, el procedimiento se puede aplicar a cualquier función cuantificable, lineal o no lineal. La única dificultad con las funciones no lineales es que los cálculos pueden ser difíciles de manejar.

Suponga que PL se define como

n

Max z = { CX ø PjXj = b, X " 0}

j=1

El análisis paramétrico útil versa sobre hacer cambios paramétricos en la función objetivo y en el lado derecho de la restricción. Las funciones lineales paramétricas típicas son

C(t) = C + t C´

B(t) = b + t b´

Donde t es el parámetro de la variación y C´y b´ son los vectores dados. Por conveniencia, supondremos que t " 0.

La idea general del análisis paramétrico es empezar con la solución óptima en t = 0. después utilizando las condiciones de obtimadidad y de factibilidad del método símplex, determinamos el rango 0 " t " t1 para la cual la solución en t=0 sigue siendo óptima y factible. En este caso, se hace referencia a t1, como un valor critico. El proceso continua determinando los valores críticos sucesivos y sus soluciones óptimas factibles correspondientes y terminara en t = t, cuando hay una indicación ya sea de que la ultima solución permanecerá inalterada para t > t, o bien de que no existe una solución factible mas allá de ese punto.

CAMBIOS DE PARAMETROS EN C

Dejamos que XBi, Bi, CB (t) sean los elementos que definen la solución óptima asociada con la ti critica (los cálculos empiezan en t0 = 0 con B0 como su base óptima). Después se determina el valor critico t i+1, y su base óptima, si existe una. Debido a que los cambios en C solo pueden afectar la optimalidad del problema, la solución actual X Bi = B¹ b seguirá siendo óptima para algunas t " ti siempre y cuando la satisfaga la siguiente condición de optimalidad:

Z j (t) - c j (t) = CB j (t) B¹ i P j - C j (t) " 0, para todas las j

El valor de t i+1 es igual a t > t i más grande que satisface todas las condiciones de optimalidad.

Observe que no hay nada en las desigualdades que requiera que C (t) sean lineal en t. Cualquier función C(t), lineal o no lineal, es aceptable. Sin embargo, con la no linealidad, la manipulación numérica de las desigualdades resultantes puede ser difícil de manejar.

Restricciones De Desigualdad.

Estar sección muestra como un método Lagrangiano se puede extender para manejar restricciones de desigualdad. La principal contribución de la sección es desarrollar las condiciones de kuhn - tuckl que proporcionan la teoría básica para la programación no lineal.

Extensión Del Método Langrangiano.

Supongamos que el problema esta dado por un

Maximice z = f(x)

Sujeta

g (x) < 0 , i = 1,2 , .. , m

Las restricciones del no negatividad x mayor que 0 si hay alguna que incluya en la m restricciones. La idea general de extender el procedimiento Langrangiano es que si el optimo no restringido de f (x) no satisfacen todas las restricciones, el ultimo restringido debe ocurrir en un punto limite del espació de solución esto significa que una ,o mas de las M restricciones debe satisfacerse en forma de ecuación. El procedimiento implica los siguientes pasos.

Paso 1. Resuelve el problema no restringido:

Maximize z =f(x)

Si el ultimo resultante satisface todas las restricciones deténgase, porque todas las restricciones son redundantes. De otra forma, determine k = 1.

Paso 2: Activar cualesquiera restricciones (es decir, convertirlas en igualdades) y optimice con el método Langrangiano f(x) sujeta a las K restricciones activas.

Paso 3: Si K = M, deténgase; no existe ninguna solución factible. De otra forma determine K = K + 1.

Condiciones de Kuhn - Tucker.

Para identificar puntos estacionarios de un problema restringido no lineal sujeto a restricciones de desigualdad. Estas condiciones también son suficientes bajo ciertas reglas.

Una condición necesaria para la optimización es que sea no negativa (no positiva) para problemas de maximización (minimización). Esto se justifica como sigue. Considere el caso de maximización. Como mide la taza de variación de F con respecto a g.

Teoría De Optimización

Proporciona la teoría clásica para localizar los puntos de máximos y mínimos de problemas no lineales restringidos y no restringidos. La teoría por lo general no es adecuada para propósitos de calculo. Existen pocas excepciones donde la teoría de Kuhn - Tucker es la base para el desarrollo de algoritmos de calculo eficientes. La programación cuadrática, es un ejemplo del uso de las condiciones necesarias de Kuhn - Tucker.

No es posible establecer condiciones de suficiencia (similares a las de los problemas no restringidos y a los problemas con restricciones de igualdad) para programas no lineales con restricciones de desigualdad. No existe forma de verificar si un algoritmo de programación no lineal converge a un óptimo local o a uno global.

Optimización

La teoría de la optimización clásica usa el calculo diferencial en la optimización de los puntos máximos y mínimos para funciones con y sin restricciones. El método tal vez no sea adecuado para cálculos eficientes, la teoría que lo fundamenta proporciona las bases para desarrollar la mayor parte de los algoritmos, de programación lineal.

Problemas no restringido

Un punto extremo de una función F(x) define un máximo o un mínimo de la función. Matemáticamente, un punto X = (X , … , X … X) es un máximo sí.

F (x + h) < F (x)

Para toda h igual (h , … h , … h) de modo que h es suficientemente pequeño para toda j.

En otras palabras x un máximo si el valor de F en todo el punto de la vecindad de x no excede f (x). de manera similar, x es un mínimo si para h se definió.

F (x + h ) > F (x )

F de x se llama máximo global o absoluto y F ( x ) y F ( x )

Son máximo locales o relativos. Al respecto, X se llama máximo débil comparado con X; ejemplo de F (x) define un máximo fuerte.

Sin embargo esta propiedad también satisface punto de inflexión y de silla de motar, como en X.

Problemas con restricciones

Optimización de las funciones restringidas que presentan caso de restricciones de igualdad y de desigualdad.

Restricciones de igualdad

Son dos métodos. El Jacobiano y el Lagrangiano, el segundo se desarrolla de forma lógica a partir del método jacobiano.

Esta relación proporciona una interesante interpretación económica del método lagrangiano.

Método De Derivadas Restringidas ( Jacobiano)

La idea de utilizar derivadas restringidas es encontrar una expresión de forma cerrada para las primeras derivadas parciales de f (x) en todos puntos que satisfacen las restricciones g (x) = 0

Los correspondientes puntos estacionarios se identifican entre los puntos de las que están derivadas parciales se hacen 0.

Ahora el método se desarrolla de forma matemática mediante el problema de Tyler, para los puntos x y x

En vecindad factible de x, tenemos

f ( x + x ) - f (x ) = f x) x + 0 ( x )

Donde f representa el gradiente restringido de f con respecto a z así f ( y, z ), deben ser unos puntos estacionarios. Entre tanto, los elementos de la matriz deben ser de la segunda derivada restringida. Para mostrar como se obtiene.

Análisis de sensibilidad del método Jacobiano

Este método sirve para estudiar la sensibilidad del valor optimo de f debido a cambios pequeños en los lados derechos de las restricciones.

Este tipo de investigación se llama análisis de sensibilidad y de alguna manera es similar a lo que se lleva a cabo la programación lineal.

UNIVERSIDAD AUTONOMA ESPAÑA

DE DURANGO

INGENIERIA MECANICA AUTOMOTRIZ

MATEMATICAS V

OBTIMIZACIÓN

QUINTO SEMESTRE

Durango, Dgo, México Octubre 2002

INTRODUCCIÓN

En este trabajo se pueden apreciar los diferentes puntos de la ordenada, así como algunos problemas y ejemplos de los mismos con sus demostraciones, graficas y una breve explicación de los mismos para una mejor comprensión.

CONCLUSIONES

Esta investigación me sirvió para reforzar los conocimientos vistos en clase, así como una mejor comprensión del tema visto en la unidad con las diferentes explicaciones que aquí se muestran.