Encontrar El óptimo De Un Problema De Optimización.docx

UNIVERSIDAD CENTRAL DE VENEZUELA FACULTAD DE CIENCIAS ECONÓMICAS Y SOCIALES ESCUELA DE ESTADÍSTICA Y CIENCIAS ACTUARIALES INVESTIGACIÓN DE OPERACIONES I

ANÁLISIS DE SENSIBILIDAD

Integrante: Misel, Darwin C.I.24.666.146

Caracas, marzo 2019

Índice

Introducción………………………………………………...

3

Análisis de Sensibilidad Cambios que afectan la factibilidad ………………………

4

a.- Cambios en la disponibilidad de los recursos………...

4

b.- Adición de una nueva restricción………………….…..

7

Cambios que afectan la Optimalidad……………………..

9

a.- Cambios en la Función Objetivo………………….…

9

b.- Adición de una nueva actividad……………………..

10

Conclusión……………..…………………………………

11

Bibliografía citada ……………………………………….

12

2

Introducción

Cualquier modelo de una situación es una simplificación de la situación real. Por lo tanto, existe cierta incertidumbre en la determinación de los valores de todos los parámetros involucrados. Debido a ello, es importante estudiar la variabilidad de la solución del problema planteado de acuerdo a eventuales modificaciones de los valores de los parámetros, o bien, debido a la incorporación de nuevos elementos a la situación. Llamaremos Análisis de Sensibilidad al estudio de la variación del óptimo de un PL (Programación lineal) producto de modificaciones de ciertos parámetros como coeficientes de variables en la función objetivo, coeficientes del lado derecho de restricciones, etc. La idea general consiste en determinar rangos de variación de los parámetros del PL de forma de mantener una cierta base óptima, teniendo en cuenta que una solución básica es factible sólo si todas las variables basales tienen un valor no negativo. Debido a que el estudio de la variación simultánea de varios parámetros puede ser difícil, nos centraremos en primer lugar en modificaciones de un parámetro a la vez manteniendo los restantes fijos

3

ANÁLISIS DE SENSIBILIDAD El análisis de sensibilidad busca determinar los efectos que se producen en la solución óptima al realizar cambios en cualquiera de los parámetros del modelo de programación lineal planteado inicialmente. Entre los cambios que se investigan están: los cambios en los coeficientes de las variables en la función objetivo tanto para variables básicas como para las variables no básicas, cambios en los recursos disponibles de las restricciones, variación de los coeficientes de utilización en las restricciones e introducción de una nueva restricción. El objetivo principal del análisis de sensibilidad es identificar el intervalo permisible de variación en los cuales las variables o parámetros pueden fluctuar sin que cambie la solución óptima. Sin embargo, así mismo se identifica aquellos parámetros sensibles, es decir, los parámetros cuyos valores no pueden cambiar sin que cambie la solución óptima. Los investigadores de operaciones tienden a prestar bastante atención a aquellos parámetros con holguras reducidas en cuanto a los cambios que pueden presentar, de forma que se vigile su comportamiento para realizar los ajustes adecuados según corresponda y evitar que estas fluctuaciones puedan desembocar en una solución no factible.

CAMBIOS QUE AFECTAN LA FACTIBILIDAD La factibilidad ocurre cuando por lo menos uno de los elementos de B^(-1) b se vuelve negativo, es decir, si una o más de las variables básicas actuales se vuelven negativas. En los modelos de programación lineal, las restricciones representan el uso de recursos limitados, ya sea en forma directa o indirecta. En este caso, se puede imaginar que el lado derecho representa límites de disponibilidad de los recursos. En esta sección se investigará la sensibilidad de la solución óptima a cambios en la cantidad de los recursos disponibles.

a) Cambios en la disponibilidad de los recursos

En los modelos de programación lineal, las restricciones representan el uso de recursos limitados, ya sea de forma directa e indirecta. En este caso, se puede imaginar que el lado derecho representa límites de disponibilidad de los recursos.

4

 Ejercicio resuelto Supóngannos que el Kiosko del señor Alfredo produce un volumen X de café que se vende a BsS. 5/litros y otro volumen Y de leche que se vende a BsS. 3/litro. Dos tipos de restricciones que se consideran son el personal y el costo de producción. En lo que se refiere a la primera restricción se tiene un máximo de 15 personas, mientras en lo segundo se tiene un máximo de BsS. 10/hora de trabajo. Los coeficientes tecnológicos están dados por

CAFÉ 3 DE 5

PERSONAL COSTO PRODUCCION

LECHE 5 2

La variable 𝑋1 representa el número de litros de café a ser producidos por horas y 𝑋2 el de leche, el programa lineal original es: Máx. Z = 5𝑋1 + 3𝑋2 Sujeto a 3𝑋1 + 5𝑋2 ≤ 15 5𝑋1 + 2𝑋2 ≤ 10 𝑋1≥0, 𝑋2≥ 0. La tabla original es 𝑋1

Z 1 0 0

𝑎3 𝑎4

-5 3 5

𝑋2 -3 5 2

𝑋3

𝑋4

0 1 0

0 0 1

0 15 10

𝑋3 5/19 5/19 -2/19

𝑋4 16/19 -3/19 5/19

235/19 45/19 20/19

La tabla óptima será 𝑋1

Z 1 0 0

𝑎2 𝑎1

0 0 1

𝑋2 0 1 0

O sea, 𝑋

𝑋2 𝑋

45/19

𝑋4

0

X = (𝑋𝐵 ) =( 𝑋13 ) = ( 20/19 0 ) 𝑁

5

Z= 235/19 5/19 𝐵 −1 = ( −2/19

−3/19 ) 5/19

Ahora supongamos que debido a la situación económica del país, el número de empleados debe reducirse a 5 y el costo máximo de producción a Bs.5/hora. El nuevo vector de disponibilidad de recurso es −10 15 5 )+ ( )= ( ) −5 10 5

b + ∆ b= (

El nuevo programa lineal a resolver seria Max Z = 5𝑋1 + 3𝑋2 Sujeto a 3𝑋1 + 5𝑋2 ≤ 5 5𝑋1 + 2𝑋2 ≤ 5 𝑋1≥0, 𝑋2≥ 0. No es necesario resolver el programa desde el principio, sino que utilizando el análisis de sensibilidad se estudia el cambio 𝐵 −1 (b+∆b) y se determina si el nuevo vector 𝑋𝐵 =𝐵 −1 (b+∆b) es factible o no. Si no lo es, habrá que restablecer la factibilidad y la optimalizadad, utilizando el dual simplex a partir de la tabla optima

̂𝐵 = 𝐵 −1 (b + ∆b) = ( 5/19 𝑋 −2/19

=[

−3/19 5 )( ) 5/19 5

10/19 0 ] ≥ ( ) 15/19 0

̂𝐵 Y por lo tanto el nuevo vector 𝑋 ̂𝐵 = 𝐵 −1 (b + ∆b) 𝑋 𝑋𝐵 = [

10/19 𝑋2 ]=[ ], 𝑋1 15/19

Es óptimo. La nueva utilidad óptima es Z= 𝑐𝐵 + 𝑋𝐵

6

= (𝑐2+ 𝑐1 ) [ (3, 5) [

𝑋2 ] 𝑋1

10/19 ] 15/19

=BsS. 105/19 =BsS 5,33 Notamos que una reducción en la disponibilidad de recursos ha causado una disminución en la producción óptima de ambos productos (café y leche), así como en la utilidad.

b) Adición de una nueva restricción Una vez resuelto un modelo de Programación Lineal puede resultar de interés si la actual solución óptima y valor óptimo se conservaran si se decide incorporar una nueva restricción al problema. Esta restricción generalmente representa una condición que en primera instancia se omite de forma voluntaria para dar una mayor flexibilidad a la resolución del modelo original o alternativamente su no inclusión en el modelo original puede también deberse a una simple omisión (involuntaria). Muchas veces es necesario analizar la sensibilidad de la solución óptima, cuando se agrega al modelo una restricción que no se consideró inicialmente, ya sea por olvido o por decisión de quien planteó el modelo. El primer paso en el análisis de los cambios que sufre la solución óptima actual al considerar una nueva restricción, es determinar si esta se cumple para la solución óptima.

 Ejercicio resuelto Con el ejercicio anterior, ahora supongamos una nueva restricción que los litros de leches producidos por hora debe ser menor a 1, entonces 𝑋2 ≤ 1 Reemplazando el valor de la variable 𝑋2 45 19

≥1

7

Es obvio que la solución óptima del problema original viola la nueva restricción, ya que no es menor o igual que uno. Entonces, el problema nuevo a resolver es Máx. Z = 5𝑋1 + 3𝑋2 Sujeto a 3𝑋1 + 5𝑋2 ≤ 15 5𝑋1 + 2𝑋2 ≤ 10 𝑋2 ≤ 1 𝑋1≥0, 𝑋2≥ 0 De esta manera, el tableau óptimo del problema original queda: Z 1 0 0 0

X2 X1 X5

X1 0 0 1 0

X2 0 1 0 1

X3 5/19 5/19 -2/19 0

X4 16/19 -3/19 5/19 0

X5 0 0 0 1

Z0 235/19 45/19 20/19 1

Como el vector columna de Y2 no es el vector unitario, por medio de operaciones matriciales elementales se vuelve a generar la identidad (factibilidad):

X2 X1 X5

Z 1 0 0 0

X1 0 0 1 0

X2 0 1 0 0

X3 5/19  5/19 -2/19 -5/19

X4 16/19 -3/19 5/19 3/19

X5 0 0 0 1

Z0 235/19 45/19 20/19 -26/19 

Aplicando el método dual simplex, se obtiene el tableau óptimo:

X2 X1 X3

Z 1 0 0 0

X1 0 0 1 0

X2 0 1 0 0

X3 0 0 0 1

X4 1 0 1/5 -3/5

X5 1 1 -2/5 -19/5

Z0 11 1 8/5 26/5

8

La nueva solución óptima es:  X2   1       X1   8 / 5  X  X   B    X 3    26 / 5  X     N  X   0    4 X   0    5  Z  11 Con la nueva restricción, tenemos un resultado de 11. Es decir BsS.11 es la maximización con la nueva restricción, es decir con menos de un litro de leche podremos obtener Bss. 11 CAMBIOS QUE AFECTAN LA OPTIMALIDAD

a) Cambios en los coeficientes de la función objetivo. Estos cambios afectan sólo la optimalidad de la solución y requieren que se calculen de nuevo los coeficientes de la fila z (costos reducidos) de acuerdo con el siguiente procedimiento: 1. Calcule los valores duales aplicando el método 2 de La matriz inversa óptima. 2. Sustituya los nuevos valores duales, para determinar los nuevos costos reducidos (coeficientes de la fila z). Si la nueva fila z satisface la condición de optimalidad, la solución no cambia (sin embargo, el valor objetivo óptimo puede cambiar). Si no la satisface, se utiliza el simplex primal para recuperar la optimalidad.  Ejercicio resuelto El kiosko del señor Alfredo tiene una nueva política de fijación de precios para enfrentar la competencia. Los ingresos unitarios son $2, $3 y $4 por café, leche y jugos, en ese orden. La nueva función objetivo es Maximizar z = 2x1 + 3x2 + 4x3 Así, (Nuevos coeficientes objetivo de las variables básicas x2, x3 y x6) = (3, 4, 0) Las nuevas variables duales se calculan como 9

1⁄2 (𝑦1 , 𝑦2, 𝑦3 ) = (3, 4,0) ( 0 −2

− 1⁄4 1⁄ 2 1

0 3 5 0) = ( ⁄2 ⁄4 1

0)

Los coeficientes de la fila z se determinan como la diferencia entre el lado izquierdo y derecho de las restricciones duales (fórmula 2, sección 4.2.4). No es necesario calcular de nuevo los coeficientes de fila objetivo de las variables básicas (x2, x3 y x6) porque siempre son cero, independientemente de cualquier cambio realizado en los coeficientes objetivo Costo reducido de x1 = y1 + 3y2 + y3 - 2 = 3⁄2+ 3(5⁄4) + 0 – 2 = 13⁄4 Costo reducido de x4 = y1 - 0 = 3⁄2 Costo reducido de x5 = y2 - 0 = 5⁄4 b) Adición de una nueva actividad Una nueva actividad supone agregar una nueva variable al modelo. Por intuición, agregar una nueva actividad es deseable sólo si es rentable. Esta condición puede verificarse aplicando la fórmula 2, sección 4.2.4, para calcular el costo reducido de la nueva variable. La nueva actividad no es rentable si satisface la condición de optimalidad. De lo contrario, la nueva actividad incrementará el ingreso.

10

Conclusión

La asignación de probabilidades a los eventos es una tarea difícil que muchos gerentes pueden mostrarse difícil a hacer, por lo menos con cierto grado de exactitud. En algunos casos prefieren decir “creo que la probabilidad de que este evento ocurra está entre 0.5 y 0.7”. Bajo estas circunstancias, como en cualquier aspecto de decisión gerencial, es útil realizar un análisis de sensibilidad para determinar cómo afecta a la

decisión la asignación de probabilidades.

El análisis de sensibilidad concierne al estudio de posibles cambios en la solución óptima disponible como resultado de hacer cambios en el modelo original. Se estudia el análisis de sensibilidad, tema fundamental de la programación lineal, vinculada a la búsqueda de información económica acerca del valor de recursos que son escaso y cómo se utilizan. Encontrar el óptimo de un problema de optimización, es solo una parte del proceso de solución. Muchas veces nos interesara saber cómo varía la solución si varía alguno de los parámetros del problema que frecuentemente se asumen como determinísticos, pero que tienen un carácter intrínsecamente aleatorio. Más específicamente nos interesara saber para qué rango de los parámetros que determinan el problema sigue siendo válida la solución encontrada.

11