miércoles, 30 de abril de 2014

Análisis de sensbilidad sistemático - Programación paramétrica (V)

Una investigación algebraica de estos cambios simultáneos en b2 y b3 implica de nuevo usar las fórmulas de la tabla 6.17 para calcular los cambios resultantes en la tabla símplex final (parte media de la tabla 6.18). Las únicas cantidades que pueden cambiar son las de la columna de lados derechos, a saber,
para θ lo suficientemente pequeño para que esta solución siga siendo factible, es decir, para θ ≤ 2. Sin embargo, el hecho de que Z disminuya su valor al aumentar el de θ indica que la mejor elección para θ es θ = 0, así que no debe hacerse ningún cambio en la producción.

martes, 29 de abril de 2014

Análisis de sensbilidad sistemático - Programación paramétrica (IV)

Por ejemplo, es posible trasladar cierta parte de la producción de un producto actual de la Wyndor Glass Co. de la planta 2 a la 3, si se aumenta b2 y se disminuye b3. Supóngase que b3 disminuye al doble de lo que crece b2. Entonces.

b2 = 12 + θ
b3 = 18 - 2θ

en donde el valor e θ (no negativo) mide la cantidad de producción transferida. (Así, en este caso, α1 = 0, α2 = 1 y α3= -2). Haciendo referencia a la figura 6.3, la interpretación geométrica es que conforme θ aumenta su valor, la línea de restricción 2x2 = 12 se mueve hacia arriba hasta 2x2 = 12 + θ (ignórese la línea 2x2 = 24) y simultáneamente la línea de restricción 3x1 + 2x2 = 18 se mueve hacia abajo hasta 3x1 + 2x2 = 18 - 2θ. La solución factible en un vértice óptima original (2,6) se encuentra en el cruce entre líneas 2x2 = 12 y 3x1 + 2x2 =18, así que al moverse estas lineas, la solución en un vértice cambia. No obstante, con la función objetivo Z = 3x1 + 5x2, la solución en el vértice permanecerá óptima mientras que sea factible (x1 ≥ 0).

lunes, 28 de abril de 2014

Análisis de sensbilidad sistemático - Programación paramétrica (III)

De la misma manera se puede investigar el efecto que tiene, en la solución óptima variar más de un parámetro a la vez. Cuando se varían sólo los parámetros bi, se expresa el nuevo valor bi en términos del valor original bi como sigue

bi = bi + αθi para i = 1, 2,.......,m.

donde las αi son constantes de entrada que especifican la tasa de incremento deseada (positivo o negativo) para los lados derechos correspondientes, al aumentar el valor de θ.

domingo, 27 de abril de 2014

Análisis de sensbilidad sistemático - Programación paramétrica (II)

Los cálculos algebraicos del efecto de tener Δb2 = θ son directamente análogos a los del ejemplo del caso 1 en donde Δb2 = 12. En particular, si se emplean las expresiones para Z* y b* dadas en la tabla 6.17, la tabla símplex en la parte media de la tabla 6.18 indica que la solución óptima correspondiente es


para valores de θ lo suficientemente pequeños para que esta solución permanezcan factible, esto es, para θ ≤6. Para valores de θ > 6, el método dual símplex conduce a la tabla que se muestra en la tabla 6.20 con Z = 45, x3 = 4, x2 = 9, pero x4 = -6 + θ (x1 =0, x5 = 0). Esta información se puede usar (junto con otros datos no incorporados al modelo sobre los efectos de incrementar b2) para decidir si conviene conservar la solución óptima original, y sí no, cuánto se debe incrementar b2.

sábado, 26 de abril de 2014

Análisis de sensbilidad sistemático - Programación paramétrica (I)

Hasta aquí se ha descrito cómo verificar cambios específicos en los parámetros del modelo. Otro enfoque común del análisis de sensibilidad es variar de manera continua uno o más parámetros sobre un intervalo (o intervalos) para ver cuándo cambia la solución óptima.

Por ejemplo, en el problema de la Wyndor Glass Co., en lugar de comenzar a probar el cambio específico de b2 =12 a b2 = 24, se puede establecer

b2 = 12 + θ

y variar θ continuamente de 0 a 12 (valor máximo de interés). La interpretación geométrica en la figura 6.3 es que la línea de restricción 2x2 = 12 se está moviendo hacia arriba hasta 2x2 =12 + θ, con el valor de θ aumentando de 0 a 12. El resultado es que la solución factible en un vértice óptimo original (2,6) mueve la línea de restricción 3x1 + 2x2 = 18 hacia el punto (-2,12). Esta solución en un vértice sigue siendo óptima mientras siga siendo factible (x1 ≥ 0), después de lo cual (0,9) se convierte en la solución óptima.

viernes, 25 de abril de 2014

Ejemplo Introducción de una nueva restricción

Como ejemplo de este caso, supóngase que se introduce la nueva restricción.

2x1 + 3x2 ≤ 24

al modelo dado en la tabla 6.20. El efecto gráfico se muestra en la figura 6.5. La solución óptima anterior (0,9) viola la nueva restricción, por lo que la solución óptima cambia a (0,8).

Para analizar este ejemplo algebraicamente, obsérvese que (0,9) lleva a que 2x1 + 3x2 = 27 > 24, entonces esta solución óptima anterior ya no es factible. Para encontrar la nueva solución óptima, se agrega esta restricción a la tabla símplex final actual, tal como se describió, con la variable de holgura x6 como su variable básica inicial. Esto lleva a la primera tabla que se muestra en la tabla 6.23. El paso de conversión a la forma apropiada de eliminación de Gauss requiere restar el renglón 2 multiplicado por 3 del nuevo renglón, con lo que se identifica la solución básica actual: x3 = 4, x2 = 9, x4 = 6, x6 = -3 (x1 = 0, x5 = 0), como se muestra en la segunda tabla. Cuando se aplica el método dual símplex se obtiene en una sola iteración (algunas veces se necesitan más) la nueva solución óptima en la tabla final de la tabla 6.23.

jueves, 24 de abril de 2014

Introducción de una nueva restricción (II)

Igual que para algunos de los casos anteriores, este procedimiento para el caso 4 es una versión simplificada del procedimiento general resumido al final de la sección 6.6. La única pregunta que hay que hacerse en este caso es sí la solución óptima anterior es todavía factible así que el paso 5 (prueba de optimalidad) se ha eliminado. El paso 4 (prueba de factibilidad) se ha reemplazado por una prueba de factibilidad mucho más rápida (la solución óptima anterior satisface la nueva restricción?) que debe realizarse justo después del paso 1 (revisión del modelo). Sólo cuando la respuesta a esta prueba es negativa y se quiere reoptimizar, se usan los pasos 2, 3 y 6 (revisión de la tabla símplex final, conversión a la forma apropiada de eliminación de Gauss, y reoptimización).

miércoles, 23 de abril de 2014

Introducción de una nueva restricción (I)

El último caso es aquel en el que debe introducirse al modelo una nueva restricción, después de que ya se ha resuelto. Este caso puede ocurrir porque se pasó por alto la restricción en un principio o porque surgieron nuevas consideraciones después de la formulación original. Otra posibilidad es que a propósito se haya eliminado la restricción para disminuir el esfuerzo computacional por parecer menos restrictiva que otras ya planteadas en el modelo, pero ahora es necesario verificar esta impresión con la solución óptima que se obtuvo.

Para ver si la nueva restricción afecta a la solución óptima actual, todo lo que tiene que hacerse es verificar directamente si esa solución óptima satisface la restricción. Si es así, todavia sería la mejor solución básica factible (es decir, sería la solución óptima) , aun cuando se agregara la restricción del modelo. La razón es que una nueva restricción sólo puede eliminar algunas de las soluciones factibles anteriores sin agregar ninguna.

Si la nueva restricción elimina la solución óptima actual, y si se quiere encontrar la nueva solución, se introduce esta restricción a la tabla símplex final (como un renglón adicional) como si fuera la tabla inicial, en la que se designa la variable usual (de holgura o artificial) como la variable básica que corresponde a este nuevo renglón. Como éste tal vez tenga coeficientes distintos de cero para algunas otras variables básicas, se debe aplicar la conversión a la forma apropiada de eliminación de Gauss y después el resto del procedimiento general.

martes, 22 de abril de 2014

Ejemplo Caso 3 - Cambios en los coeficientes de una variable básica (IV)

La tabla 6.22 muestra cómo se calcula este intervalo permitido para c2 en forma algebraica; esta tabla incluye sólo las partes relevante de la tabla símplex (renglón 0 y renglón para x2). El punto de partida (primera tabla que se muestra) es la tabla símplex final de la parte inferior de la tabla 6.21.Lo que se hace es aplicar los pasos 1,2,3 y 5 del procedimiento de análisis de sensbilidad (Sec. 6.6) cuando c2 =3 aumenta o disminuye en una cantidad pequeña, donde Δc2 = ±1 es la cantidad conveniente. La segunda y tercera tablas símplex de la tabla 6.22 muestran el efecto de Δc2 = 1, mientras que la cuarte y quinta tablas símplex repiten el procedimiento para Δc2 = -1. (Obsérvese que la segunda y cuarta tablas símplex difieren de la primera sólo en el coeficiente e x2 en el renglón 0 que cambia de 0 a -Δc2). Con Δc2 = 1, el coeficiente de x3 en el renglón 0 disminuye e 3/2 (primera tabla símplex) a 0 (tercera tabla símplex), lo que indica que Δc2 = 1 es el punto de cambio más allá del cual la solución básica actual ya no sería óptima. Con Δc2 = -1, el único número en el renglón 0 que disminuye es el coeficiente de x5. El cambio es de 3/4 (primera tabla símplex) a 1/2 (quinta tabla símplex) que está sólo a un tercio de la distancia hasta 0. Mediante extrapolación lineal, Δc2 = -3 es el punto de cambio debajo del cual la solución básica actual deja de ser óptima. Por lo tanto, -3 ≤ Δc2 ≤ 1 (o 0 ≤ c2 ≤ 4) es el intervalo de valores permitidos sin que cambie la solución óptima.

Este análisis sugiere que c2, a22 y a32 son parámetros relativamente sensibles. Sin embargo, los datos adicionales para estimarlos con más cuidado sólo pueden obtenerse si se realiza una prueba piloto. Por lo tanto, el departamento de investigación de operaciones recomienda que se inicie de inmediato la producción del producto 2 en pequeña escala (x2 = 3/2) y que se use esta experiencia como guía para la decisión acerca de si la capacidad e producción restante debe asignarse al producto 2 o al 1.

lunes, 21 de abril de 2014

Ejemplo Caso 3 - Cambios en los coeficientes de una variable básica (III)

La tabla final revisada que resulta se muestra en la parte superior de la tabla 6.21. Nótese que los nuevos coeficientes de esta variable básica x2 no tienen los valores requeridos y se tiene que aplicar la conversión a la forma apropiada con eliminación de Gauss. Este paso exige dividir el renglón 2 entre 2, restar el nuevo renglón 2 multiplicado por 7 del renglón 0 y sumar el nuevo renglón 2 al renglón 3.

La segunda tabla símplex de la tabla 6.21 da los nuevos valores de la solución básica actual, a saber, x3 = 4, x2 = 9/2, x4 = 21/2, (x1 = 0, x5 = 0). Como todas estas variables son no negativas, la solución todavia es factible. Sin embargo, el coeficiente negativo de x1 en el renglón 0 indica que la solución y a no es óptima. Entonces, se aplicará el método símplex a esta tabla tomando esta solución como solución inicial factible básica, para encontrar la nueva solución óptima . La variable entrante básica inicial es x1, con x3, como la variable básica que sale. Se necesita sólo una iteración en este caso para llegar a la nueva solución óptima: x1 =4, x2 = 3/2, x4 = 29/2 (x3=0, x5=0), como se muestra en la tabla 6.21.

Ahora vuélvase a observar esta nueva solución óptima (4, 3/2) en la figura 6.4. Esta solución es óptima para la estimación actual pesimista de que c2 =3, es decir, Z = 3x1 + 3x2. Sin embargo, con la estimación original de c2 = 5, la solución (0, 9/2) seria óptima. Debido a la línea de restricción 3x1 + 4x2 = 18, el punto de cambio de una solución óptima a otra está en c2 = 4. Si c2 fuera menor que 3, entonces (4, 3/2) permanecería óptima siempre y cuando c2 ≥ 0. Así, el intervalo permitido para c2 sin que cambie la solución óptima (4, 3/2) es 0 ≤ c2 ≤ 4.

domingo, 20 de abril de 2014

Ejemplo Caso 3 - Cambios en los coeficientes de una variable básica (II)

Ahora veamos cómo se puede llegar a estas mismas conclusiones algebraicamente. Dado que los únicos cambios en el modelo ocurren en los coeficientes de x2, las únicas modificaciones que resultan en la tabla símplex final (tabla 6.20) están en la columna de x2. Entonces, se usan las fórmulas de la tabla 6.17 para volver a calcular nada más esta columna.

(De manera equivalente, se puede usar el análisis incremental con Δc2 = -2, Δa22 = 1 y Δa32 = 2 para obtener esta columna)

sábado, 19 de abril de 2014

Ejemplo Caso 3 - Cambios en los coeficientes de una variable básica (I)

Como x2 es una variable básica en la tabla 6.20 para el problema de la Wyndor Glass Co., el análisis de sensibilidad sobre sus coeficientes se ajusta al caso 3. Dada la solución óptima actual (x1 = 0, x2 = 9), el producto 2 es el único producto nuevo que debe introducirse, y su tasa de producción será relativamente grande. Por ello, la pregunta importante es si las estimaciones iniciales que llevaron a los coeficientes de x2 en el modelo actual pudieron haber sobreestimado tanto las cualidades del producto 2 que invaliden esta conclusión. Para responder a esta pregunta se debe verificar el conjunto más pesimista de estimaciones razonables para estos coeficientes, que resulta ser c2 = 3, a22 = 3 y a32 = 4.

El efecto gráfico de estos cambios es la modificación en la región factible de la que se ve muestra en la figura 6.3 a la de la figura 6.4. La solución óptima en la figura 6.3 es (x1, x2) = (0,9), que corresponde a la solución en el vértice en donde se cruzan las fronteras de restricción x1 = 0 y 3x1 + 2x2 =18. Al revisar las restricciones, la solución en un vértice en la figura 6.4 es (0, 9/2). No obstante, esta solución ya no es óptima, puesto que la función objetivo revisada, Z = 3x1 + 3x2, conduce ahora a la nueva solución óptima (x1, x2) = (4, 3/2).

viernes, 18 de abril de 2014

Caso 3 - Cambios en los coeficientes de una variable básica

Ahora supóngase que la variable xj (con j fija) que se está estudiando es una variable básica en la solución óptima que se muestra en la tabla símplex final (o sea que xj aparece en la primera columna de esta tabla). El caso 3 supone que los únicos cambios del modelo actual ocurren en los coeficientes de esta variable.

El caso 3 difiere del 2a debio al requisito de que la tabla símplex debe estar en la forma apropiada de eliminación de Gauss. esta forma permite cualesquiera elementos en la columna de una variable no básica, así que no afecta en el caso 2a. Sin embargo, para el caso 3 se requiere que la variable básica xj tenga coeficiente 1 en su renglón de la tabla símplex y coeficiente cero en todos los demás renglones (incluyendo el renglón 0). Por lo tanto, una vez que se han calculado los cambios en la columna xj de la tabla símplex final es probable que sea necesario aplicar el método de eliminación de Gauss para restaurar la forma apropiada, tal y como se ejemplificó en la tabla 6.19. Este paso, a su vez, quizá cambie los valores de la solución básica actual, y puede hacerla no factible no factible o no óptima. Así, el caso 3 requiere todos los pasos del procedimiento general resumido al final de la sección 6.6.

jueves, 17 de abril de 2014

Caso 2b - Introducción de una nueva variable (I)

Una vez obtenida la solución óptima se puede descubrir que la formulación de programación lineal no tomó en cuenta todas las actividades que pudieran ser atractivas. Considerar una nueva actividad requiere introducir una nueva variable a la función objetivo y a las restricciones con los coeficientes apropiados, éste es el caso 2b.

La manera conveniente de manejar este caso es tratarlo como si fuera el 2a! Para realizar esto se presume que la nueva variable xj ya formaba parte el modelo original con todos sus coeficientes iguales a cero (por lo que todavía son cero en la tabla final) y que xj es una variable no básica en la solución básica factible actual. Entonces,si se cambian estos coeficientes a sus valores actuales para la nueva variable, sin duda el procedimiento (que incluye la reoptimización) se vuelve idéntico al del caso 2a.

De hecho, todo lo que se tiene que hacer para comprobar si la solución actual es todavía óptima es verificar si la solución básica complementaria y* satisface la nueva restricción dual que corresponde a la nueva variable en el problema primal. Este enfoque ya se describió y después se ejemplificó para el problema de la Wyndor Glass Co. en la sección 6.5.

miércoles, 16 de abril de 2014

Ejemplo Caso 2a - Cambios en los coeficientes de una variable no básica (II)

Este enfoque que examina la restricción dual revisada facilita encontrar cuánto se pueden cambiar los parámetros involucrados antes de que la solución acutal deje de ser óptima. Por ejemplo, si a31 = 2 de manera que y*1 + 2y*3 = 5, el intervalo de valores permitidos para c1 sin que cambie la solución óptima es c1 ≤ 5. En forma similar, con el valor original de a31 (a31 = 3), de manera que y*1 + 3y*3 = 15/2, el intervalo de valores permitidos es c1 ≤ 15/2, por lo que c1 se puede incrementar hasta en 9/2 (Δc1 ≤ 9/2) por encima de su valor original de c1 = 3. Este último intervalo permitido también se puede obtener directamente de la tabla 6.20 en donde el coeficiente de x1 en el renglón 0 de la tabla símplex final es 9/2. Cuando el único cambio en los parámetros de la tabla 6.20 es un incremento en c1, la tabla 6.17 indica que el único cambio que resulta en la tabla símplex es que este coeficiente se convierte en 9/2 - Δc1, de manera que Δc1 ≤ 9/2 es el intervalo permitido por la prueba de optimalidad y c1 ≤ 3 + 9/2 = 15/2 es el intervalo permitido para los valores de c1. (Éste es el método que usan muchos paquetes de programación para obtener el intervalo de valores permitidos para las cj correspondientes a las variables no básicas)

Como sería poco realista hacer cambios mayores en las estimaciones originales de los coeficientes de x1, el departamento de investigación de operaciones llegó a la conclusión de que estos coeficientes son parámetros no sensibles para el modelo actual. Por lo tanto, se dejarán fijos con el valor de sus mejores estimaciones, mostrados en la tabla 6.20, c1 =3 y a31 = 3 para lo que resta del análisis de sensibilidad.

martes, 15 de abril de 2014

Ejemplo Caso 2a - Cambios en los coeficientes de una variable no básica (I)

Como x1 es no básica en la solución óptima actual (véase la tabla 6.20) para el problema de la Wyndor Glass Co., el siguiente paso en el análisis de sensibilidad es comprobar si cualquier cambio razonable en la estimación de los coeficientes de x1 puede aconsejar que se introduzca el producto 1. El conjunto de cambios que pueden ser realistas para hacer el producto 1 más atractivo sería restablecer c1 = 4 y a31 = 2 (como se hizo en la sección 6.6).

Este cambio en a31 hace que la región factible cambie de la que se muestra en la figura 6.3 a la región correspondiente de la figura 6.2, cuando 3x1 + 2x2 = 18 se sustituye por 2x1 + 2x2 = 18. (La recta 2x2 = 12 se ignora porque la restricción 2x2 ≤ 12 ya se sustituyó por 2x2 ≤ 24) El cambio c1 hace que la función Z = 3x1 + 5x2 cambie a Z = 4x1 + 5x2. Si se dibuja la recta de la función objetivo Z = 45 = 4x1 + 5x2 en la figura 6.2, que pasa por la solución óptima actual (0,9) se puede verificar que este punto sigue siendo óptimo después de los cambios en a31 y c1.

Para emplear la teoría de dualidad para llegar a esta misma conclusión, obsérvese que los cambios en c1 y a31 llevan a una sola restricción revisada en el problema dual (véase la tabla 6.1). Tanto esta restricción revisada como la y* actual (coeficientes de las variables de holgura en el renglón 0 de la tabla 6.20) se muestran en seguida.

Nótese que y* todavía satisface la restricción revisada por lo que la solución primal actual (tabla 6.20) todavía es óptima.

lunes, 14 de abril de 2014

Caso 2a - Cambios en los coeficientes de una variable no básica (II)

Si la solución óptima cambió y si se desea encontrar la nueva, es fácil hacerlo. Sólo debe aplicarse la idea fundamental a la columna xj revisada (la única que cambia) en la tabla símplex final. Con la solución básica actual que ya no es óptima, el nuevo valor de (zj* - cj) será ahora el que tiene coeficiente negativo en el renglón 0, así que se inicia el método símplex con xj como la variable básica entrante inicial.

Obsérvese que este procedimiento es una versión simplificada del procedimiento general que se resumió al final de al sección 6.6. Los pasos 3 y 4 (conversión a la forma apropiada de eliminación de Gauss y prueba de optimalidad) se eliminaron por no ser relevantes, ya que la única columna que se está cambiando en la revisión de la tabla simpléx final (antes de reoptimizar) es la de la variable no básica xj. El paso 5 (prueba de optimalidad) se sustituyó por una prueba más rápida que debe realizarse después del paso 1 (revisión del modelo). Sólo cuando esta prueba revele que la solución óptima ha cambiado, y quiera encontrarse la nueva solución tendrán que aplicarse los pasos 2 y 6 (revisión de la tabla símplex final y reoptimización).

domingo, 13 de abril de 2014

Caso 2a - Cambios en los coeficientes de una variable no básica (I)

Considérese una variable específica xj (j fija) que sea no básica en la solución óptima dada en la tabla símplex final (de manera que xj no esté incluida en la lista de variables básicas en la primera columna de esta tabla símplex). El caso 2a es aquel en el que los únicos cambios al modelo actual ocurren en uno o más de los coeficientes de esta variable, cj, a1j, a2j,......., amj.

Como se decribió al principio de la sección 6.5, la teoría de dualidad proporciona una manera muy conveniente de verificar estos cambios. En particular, si la solución básica complementaria y* en el problema dual todavía satisface la restricción dual que cambia, entonces la solución óptima original en el problema primal sigue siendo óptima tal y como está. Por el contrario, si y* viola esta restricción dual, entonces esta solución primal ya no es óptima.

sábado, 12 de abril de 2014

Ejemplo de Cambios en la bi (VI)

Así, 6 ≤ b2 ≤ 18 es le intervalo permitido para b2 en el cual la solución básica final original (con los nuevos valores de las variables básicas) permanece factible y, por lo tanto, óptima, siempre que éste sea el único cambio en el modelo original. (Muchos paquetes de programación líneal emplean esta técnica para generan en forma automática el intervalo permitido para cada bi y una técnica parecida para cada cj.)

Con base en estos resultados, b2 = 24, se descontinuará el producto antiguo, relativamente no redituable y las 6 unidades no utilizadas del recurso 2 se guardarán para algún uso futuro. Como y3* todavía es positivo, se hace un estudio similar de la posibilidad de cambiar la asignación del recurso 3, pero la decisión a la que se llega es la de conservar la asignación actual. Por tanto, el modelo de programación líneal en este punto tiene los parámetros y la solución óptima que se muestran en la tabla 6.20.

viernes, 11 de abril de 2014

Ejemplo de Cambios en la bi (V)

Aunque Δb2 = 12 resultó ser un incremento de b2 demasiado grande para mantener la factibilidad (y por tanto la optimalidad) con la solución básica en la que x1, x2 y x3 son las variables básicas (parte media de la tabla 6.18), el análisis incremental anterior encontro de inmediato qué tan grande puede ser el incremento para seguir siendo factible. En particular obsérvese que




en donde estas tres cantidades son los valores de x3, x2 y x1, respectivamente, para esta solución básica. La solución permanece factible y, por lo tanto, óptima, siempre y cuando las tres cantidades sigan siendo no negativas. Para determinar el intervalo de valore de b2 en el cual las tres cantidades permanecen no negativas, se iguala cada cantidad a cero, se despeja Δb2 y se eligen los valores positivos y negativos de Δb2 más cercanos a cero, a saber.

- 6 ≤ Δb2 ≤ 6 o 6 ≤ b2 ≤ 18

jueves, 10 de abril de 2014

Ejemplo de Cambios en la bi (IV)

Por lo tanto, la solución básica actual (antes óptima) se ha convertido en

(x1, x2, x3, x4, x5) = (-2, 12, 6, 0, 0)

que no pasa la prueba de factibilidad porque tiene una valor negativo. Ahora se puede aplicar el método símplex dual a partir de esta tabla revisada, para encontrar la nueva solución óptima. Este método conduce, en una sola iteración, a la nueva tabla símplex final que se muestra en la tabla 6.20 (En forma alternativa, se pudo haber aplicado el método símplex desde el principio y en este caso, también se hubiera llegado a esta tabla final en una sola iteración.) esta tabla símplex índica que la nueva solución óptima es

(x1, x2, x3, x4, x5) = (0, 9, 4, 6, 0)

con Z = 45, proporcionando así un incremento en la ganancia de $9/minuto por los nuevos productos, sobre el valor anterior Z =36. El hecho de que x4 = 6 indica que 6 de las 12 unidades adicionales del recurso 2 quedan sin usarse con esta solución.

miércoles, 9 de abril de 2014

Ejemplo de Cambios en la bi (III)

DE manera similar, como el único cambio en el modelo original es Δb2 = 24-12 = 12, se puede usar el análisis incremental para calcular estos mismos valores con mayor rapidez, como sigue:
en dode los valores originales de estas cantidades se obtienen de la columna del lado derecho en la tabla símplex inicial (parte media de la tabla 6.18). La tabla símplex revisada final que resulta corresponde a la tabla símplex final original, excepto por la columna del lado derecho que tiene estos nuevos valores.

martes, 8 de abril de 2014

Ejemplo de Cambios en la bi (II)

Cuando se aplica la idea fundamental (tabla 6.17), se encuentra que el efecto de este cambio sobre la tabla símplex original final (parte media de la tabla 6.18) es que los elementos de la columna del lado derecho cambian a los siguientes valores:

lunes, 7 de abril de 2014

Ejemplo de Cambios en la bi (I)

El análisis de sensibilidad para el problema original de la Wyndor Glass Co. de la sección 3.1 comienza por examinar los valores óptimos de las variables duales yi (yi* = 0, y2* = 3/2, y3* = 1). Estos precios sombra dan el valor marginal de cada recurso i para las actividades (dos nuevos productos) bajo consideración. Como se dijo en la sección 4.7 (véase la figura 4.3), se puede aumentar la ganancia total debida a estas actividades en $1.50/minuto por cada unidad adicional del recurso 2 (capacidad de producción en la planta 2) que quede disponible. Este aumento en las ganancia es válido para cambios relativamente pequeños que no afecten la factibilidad de la solución básica actual (y por tanto, que no afecten los valores yi*).

En consecuencia, el departamento de investigación de operaciones ha investigado la ganancia marginal posible debida a los otros usos actuales de este recurso para determina si alguna es menor que $1.50/minuto. Esta investigación puso de manifiesto que uno de los productos antiguos es mucho menos redituable. LA tasa e producción para este producto ya se redujo a la cantidad mínima que justifica sus gastos de comercialización, pero se puede descontinuar, lo que proporcionarí 12 unidades adicionales del recurso 2 para los nuevos productos. Entonces, el siguiente paso es determinar qué ganancia se podría obtener de los nuevos productos si se hiciera esta transferencia, que cambia b2 de 12 a 24 en el modelo de programación líneal. La figura 6.3 muestra el efecto de este cambio, incluso el cambio en la solución en un vértice final de (2,6) a (-2,12).

domingo, 6 de abril de 2014

Caso 1 - Cambios en las bi

Supóngase que los únicos cambios al modelo actual consisten en el cambio de uno o más de los parámetros bi (i = 1,2,.....,m). En este caso, los únicos cambios que resultan en la tabla símplex final se encuentran en la columna del lado derecho, por lo cual, se pueden omitir del procedimiento general tanto la conversión a la forma apropiada de eliminación de Gauss como la prueba de optimalidad.

sábado, 5 de abril de 2014

Aplicación del análisis de sensibilidad

El análisis de sensibilidad casi siempre comienza con la investigación del efecto de los cambios en las bi, la cantidad del recurso i (i = 1,2,....., m) que se encuentra disponible para las actividades bajo consideración. La razón es que en general existe mayor flexibilidad al establecer y ajustar estos valores que los otros parámetros del modelo. Como ya se dijo en las secciones 4.7 y 6.2, la interpretación económica de las variables duales (las yi) como precios sombra es extremadamente útil para decidir cuáles son los cambios que debe estudiarse.

jueves, 3 de abril de 2014

Resumen del procedimiento para análisis de sensibilidad


  1. Revisión del modelo: se hacen los cambios deseados en el modelo que se va a investigar
  2. Revisión de la tabla símplex final: se emplea la idea fundamental para determinar los cambios que resultan en la tabla símplex final.
  3. Conversión a la forma apropiada: se escribe esta tabla en la forma apropiada para identificar y evaluar la solución básica actual aplicando (según sea necesario) la eliminación de Gauss.
  4. Prueba de factibilidad: se prueba la factibilidad de esta solución verificando que todas las variables básicas sigan teniendo valores no negativos en la columna del lado derecho de la tabla.
  5. Prueba de optimalidad: se verifica si esta solución es óptima  (si es factible), comprobando que todos los coeficientes de las variables no básicas en el renglón 0 sigan siendo no negativos.
  6. Reoptimización: si esta solución no pasa cualquiera de estas pruebas, se pueden  obtener (si se desea) la nueva solución óptima partiendo de la tabla actual como tabla símplex inicial (haciendo las conversiones necesarias) para el método símplex o del método símplex dual.
En la siguiente sección se presentará e ilustrará la aplicación de este procedimiento a cada una de las categorías más importantes de revisiones del modelo original. Este estudio incluye, en parte, la extensión sobre el ejemplo que se introdujo en esta sección para investigar cambios en el modelo de la Wyndor Glass Co. De hecho, se debe comenzar por verificar individualmente cada uno de los cambios anteriores. Al mismo tiempo, se integrarán al análisis de sensibilidad algunas de las de las aplicaciones de la teoría de dualidad que se mencionaron en la sección 6.5.

miércoles, 2 de abril de 2014

Esencia del análisis de sensibilidad (XI)

Si esta solución básica (-3, 12, 7, 0, 0) no hubiera sido factible ni superóptima (esto es, si la tabla hubiera tenido números negativos tanto en el lado derecho como en el renglón 0), se hubiera podido introducir variables artificiales para convertirla en la forma apropiada para una tabla símplex inicia.

Cuando se realizan pruebas para detectar cuán sensible es la solución óptima original a los distintos parámetros del modelo, el enfoque común es verificar cada parámetro en forma individual, y cambiar su valor de estimación inicial a otras posibilidades dentro del intervalo de valores probables (incluyendo los extremos de este intervalo). Una vez identificados los parámetros más sensibles, se pueden investigar algunas combinaciones de cambios simultáneos. Cada vez que se cambia uno o más parámetros, se debe aplicar el procedimiento que acaba de describirse. Se resumirá ahora este procedimiento.

martes, 1 de abril de 2014

Esencia del análisis de sensibilidad (X)

Para el ejemplo, la tabla símplex final revisada que se muestra en la parte superior de la tabla 6.19 no está en la forma apropiada de eliminación gaussiana causa de la columna de la variable básica x1. En particular, el coeficiente x1 en su renglón (el 3) es 2/3 en lugar de 1, y tiene coeficientes distintos de cero (-2 y 1/3) en los renglones 0 y 1. Para restablecer la forma apropiada se multiplica el renglón 3 por 3/2, después este nuevo renglón 3 multiplicado por 2  se suma al renglón 0; por último 1/3 de dicho renglón 3 se resta el renglón 1. Esto lleva a la forma apropiada de eliminación de Gauss que se muestra en la parte inferior de la tabla 6.19, que ahora se puede usar para identificar los nuevos valores de la solución básica actual (antes óptima).

(x1, x2, x3, x4, x5) = (-3, 12, 7, 0, 0).

como x1 es negativa, esta solución básica ya no es factible, pero es superóptima (véase la tabla 6.10) por que todos los coeficientes en el renglón 0 son no negativos. Entonces, el método símplex dual puede ser útil para reoptimizar (si se desea), comenzando con esta solución básica. Si se hace referencia la figura 6.2 (y se ignoran las variables de holgura), el método símplex dual lleva a cabo sólo una iteración para moverse de la solución en el vértice (-3, 12) a la solución factible óptima en el vértice (0,9).