Problemas Programación Lineal Continua

Transcript

MCOI. Métodos Cuantitativos de Organización Industrial 3º GITI PROBLEMAS PROGRAMACIÓN LINEAL CONTINUA 1. Sea el problema: Max. 3 x1 + 4 x2 + 2 x3 + x4 s.a. 4 x1 + 3 x 2 + 4 x3 + x 4 ≥ 5 2 x1 + x 2 + 5 x3 + 2 x 4 ≤ 6 x1≥6, 0 ≤ x2 ≤ 3, x3 libre, x4 ≤ 0 a) Ponerlo en forma estándar. b) Ponerlo en forma canónica. c) Resolverlo. 2. Considere los problemas: 2.1. Max. –3 x1 + 4 x2 – x3 s.a. – x1 2 x1 – 3 x2 + 5 x3 = 50 ≥ 12 x1 ≥ 0, x2 ≥ -5, x3 libre 2.2. Min. x+y s.a. x+y≤1 2x–y=3 x, y libres a) Obtenga su forma estándar b) Realice la fase 1 para obtener una solución básica inicial. -1- MCOI. Métodos Cuantitativos de Organización Industrial 3º GITI 3. Resolver el siguiente problema: Max. 2 x1 - x2 s.a. - 2 x 2 - x3 ≤ 1 x1 + x 2 + x3 ≥ 2 2 x2 - x 3 = 2 x1≥ 0, x2 libre, x3 ≤ 0 4. Max. 2 x1 + x2 s.a. 5 x1 + 3x2 = 6 2 x1 + x2 = 2 x1 , x 2 ≥ 0 Resolver el problema propuesto usando el método de las dos fases. Hacer los comentarios oportunos acerca de la solución del mismo. En caso de empate, al calcular ε para decidir qué variable entra en la base, pivotee en un elemento de la segunda fila. 5. Dado el problema: Max. - x1 - x2 s.a. x1 + 3x2 ≥ 12 2x1 + x2 ≤ 10 x1 , x 2 ≥ 0 1) Resolverlo aplicando Fase I y Fase II (por forma matricial del simplex). 2) ¿Qué valor deberían tomar los coeficientes de la función objetivo de las variables no básicas para poder introducirlas en la base? Calcule dichos valores. ¿Hay alguna relación entre estos nuevos valores y la última fila de la tabla final? 6. Sea un problema lineal en el que intervienen las cinco variables y tres restricciones. a) Escríbase una tabla genérica de manera que sea el único óptimo la solución x1 = 2, x2 = 1, x3 = 4, x4 = 0 y x5 = 0 y la función objetivo valga 9. b) Escríbase la tabla de manera que sea óptima la solución del apartado a) y que, además, deben existir soluciones alternativas con x1, x2 y x4 básicas. c) Que en el óptimo x1, x2 y x3 sean básicas con valores (2,1,4), la función objetivo valga 9 y que existan soluciones óptimas alternativas con coordenadas tan grandes como se quiera para las variables x1, x2, x3 y x4. d) Idem, en cuanto al número de variables y restricciones pero el problema sea no acotado en la función objetivo. e) En el apartado a) describa ∂x2/∂x4 y ∂Z/∂x5. Explique sus significados. -2- MCOI. Métodos Cuantitativos de Organización Industrial 3º GITI 7. Sea un problema lineal en el que intervienen las seis variables y tres restricciones. a) Construya una tabla del simplex que represente el vértice x* = (3,5,0,0,0,0) en la que haya un coste relativo negativo, pero a pesar de ello la solución admisible x* = (3,5,0,0,0,0) sea óptima. b) Construya una tabla del simplex en la que la solución admisible x = (4,6,7,1,0,0) sea solución óptima. c) Para la tabla que construya en b) discuta el significado de la expresión genérica ∂xi /∂xk en el contexto de la programación lineal aplicándolo a dicha tabla. Escriba los valores numéricos que toma dicha expresión ∂xi / ∂xk en la tabla, para las variables xi y xk para las que tenga sentido la expresión, interpretándolos. 8. Sea el problema siguiente: Min. 3/2 x1 + x2 -x1 + 4 x2 ≤ 4 s.a. x1 + 2 x 2 = 2 x1 , x 2 ≥ 0 a) Resuelva el problema. b) A partir de la forma matricial del símplex, identificar la matriz básica en el óptimo y calcular la inversa. Obténganse las nuevas soluciones óptimas para los vectores b = (-2,-1) y b = (-1,1). Aplique el método símplex-dual si es necesario. Discuta si las soluciones son únicas o no, degeneradas o no. 9. Considérese la tabla del simplex que corresponde a la solución óptima de un problema de minimización con restricciones originales de ≤. Tabla a) x1 x2 x3 x4 h1 h2 h3 b 1 1 0 -2/7 2 0 1 2 0 0 1 -3/7 1 0 4 3/2 0 -2 0 11/7 1 1 6 1 0 0 0 3 4 0 9 --- Describa la solución óptima del problema. -3- MCOI. Métodos Cuantitativos de Organización Industrial 3º GITI b) Siendo Z la función objetivo, encontrar ∂Z/∂h1. c) Calcular ∂x1/∂h3. Interpretar verbalmente el resultado. d) ¿Existen soluciones óptimas alternativas? Describa todas ellas en caso de que existan. e) Suponiendo que la tabla escrita corresponda al problema original de minimizar cx, sujeto a Ax=b, con las variables no negativas (donde las variables hi ya no son holguras sino variables propias del problema), describa el rango de valores de b1 (que en la tabla original es 2) para los que se mantiene la solución óptima actual. f) Para la misma interpretación de la tabla que en el apartado anterior, describa el rango de valores del coste marginal c4 asociado a la variable x4 (que inicialmente es 3), de forma que se mantenga la solución óptima actual. 10. Dado el problema Min. s.a. x1 + x2 + 2 x3 + 10 x4 + x5 – x 3 + x4 + x5 = 2 2 x1 x1 + x2 – x3 + 2 x4 + x5 = 1 – x1 + x3 – x5 = 3 xj ≥ 0 En la solución óptima las variables básicas son x1, x2 y x3, es decir:  2 0 − 1 B =  1 1 − 1 − 1 0 1  1 0 1 donde B = 0 1 1 1 0 2 -1 Resolver el problema primal. Formular el dual y resolverlo. Resolver el problema original si b pasa a valer (5, 1, 3). Caso de ser necesaria alguna iteración aplicar el algoritmo símplex-dual. Resolver el problema original si c pasa a valer (1, 1, 2, 10, -3). Caso de ser necesaria alguna iteración aplicar el símplex a partir de la tabla de la solución óptima del apartado a). Idem con c = (1, 1, 2, 4, 1). 11. Considere el problema Min -5x1 - 8x2 s.a. 5x1 + 2x2 x1 + 2x2 4x1 + 6x2 x1 , x 2 ≥ 0 ≤5 ≤4 ≤ 12 -4- MCOI. Métodos Cuantitativos de Organización Industrial 3º GITI cuya tabla óptima es, x1 0 0 1 0 x2 0 1 0 0 h1 1 0 0 0 h2 11 2 -3 1 h3 -4 -.5 1 1 b 1 2 0 a) Identifique xB, el vector de las variables básicas en el óptimo. Identifique B, la matriz de vectores de las variables básicas en los datos iniciales y cB, el vector de costes iniciales de las variables básicas. Identifique B-1 en la tabla final. Escriba el problema dual. Identifique una solución óptima del problema dual. Todo ello sin realizar operaciones. b) A partir del problema inicial, en el caso de que el coste de x1 pase de ser -5 a ser -3, actualice la solución óptima del problema. Si requiere iteraciones utilice el algoritmo simplex. c) Se ha realizado una modificación en los costes del problema primal inicial que conduce a la nueva tabla óptima. x1 4 .5 1 1 x2 0 1 0 0 h1 1 0 0 0 h2 -1 .5 -3 4 h3 0 0 1 0 b 1 2 0 Describa la modificación que se efectuó. 12. Considérese el problema: Max. x1 + 3 x 2 – x3 s.a. 2 x1 + 4 x2 + 20/3 x3 ≤ 30 3 x1 + 3 x2 + x3 = 18 x1 ≥ 5, x2 ≥0, x3 ≥ 0 a) Póngase en forma estándar. b) Aplíquese la fase 1 para obtener una solución básica admisible inicial. c) Resuelva el problema aplicando el método símplex. d) Formule el problema dual. e) ¿Puede saberse la solución óptima del problema dual escrito en el apartado d) a partir de la última tabla del símplex, correspondiente a la solución óptima del primal? ¿Puede saberse al menos el valor óptimo de alguna de las variables del problema dual? ¿Por qué?. -5- MCOI. Métodos Cuantitativos de Organización Industrial 3º GITI f) Obtenga el valor óptimo de la (o las) variables del dual que no se conozcan en el apartado e) sin necesidad de resolverlo. g) ¿Cuál es la solución óptima del primal si la función objetivo es max. x1 + 3 x2 + 5 x3?. Emplee la representación matricial del símplex para comprobar si la solución anterior sigue siendo óptima. Parta de la actualización de dicha tabla final para continuar con el símplex en las iteraciones que pueden ser necesarias en la obtención del nuevo óptimo. h) Lo mismo que en el apartado h) pero cambiando el vector de restricciones a (b1, b2) = (30, -9). Empléese el método símplex-dual si son necesarias más iteraciones. Recuérdese que x1 ≥ 5. Nota: en los apartados g) y h) parta del problema original. 13. La aplicación del método símplex a la resolución del problema Max. 4 x1 + 5 x2 + 9 x3 + 11 x4 s.a. x1 + x2 + x3 + x4 ≤ 15 7 x1 + 5 x2 + 3 x3 + 2 x4 ≤ 120 3 x1 + 5 x2 + 10 x3 + 15 x4 ≤ 100 xi ≥ 0 da lugar a la siguiente tabla óptima: x1 1 0 0 0 x2 5/7 -6/7 2/7 3/7 x3 0 0 1 0 x4 -5/7 13/7 12/7 11/7 h1 10/7 -61/7 -3/7 13/7 h2 0 1 0 0 h3 -1/7 4/7 1/7 5/7 b 50/7 325/7 55/7 695/7 a) Identifique la solución óptima del problema dual, el valor de la función objetivo en el óptimo y que ecuaciones se cumplen con signo de igualdad en el primal y en el dual. b) Si c = (3, 5, 9, 11), calcular la solución óptima de ambos problemas. c) Cambiando b = (9, 120, 100) repetir el apartado anterior. 1  d) ¿Y si A’2 = 7 ? 5 -6- MCOI. Métodos Cuantitativos de Organización Industrial 3º GITI 14. Considere el problema Max. 5 x1 + 8 x2 5 x1 + 2 x2 ≤ 5 x1 + 2 x2 ≤ 4 4 x1 + 6 x2 ≤ 12 x1 , x 2 ≥ 0 s.a. cuya tabla óptima es x1 x2 h1 h2 h3 b 0 0 1 11 -4 1 0 1 0 2 -1/2 2 1 0 0 -3 1 0 0 0 0 -1 -1 Dado que el problema primal es degenerado, el problema dual tiene soluciones óptimas alternativas. Calcule la solución óptima del dual y todas las soluciones óptimas alternativas. Para ello no emplee el método símplex aplicado al problema dual ni el método símplexdual. Realícelo mediante las condiciones de complementariedad entre las soluciones óptimas primales y duales. Específicamente: Modele el problema dual. Escriba la relación entre costes relativos de las variables en el dual y holguras de las ecuaciones del primal. Escriba que variables del dual son básicas y cuales no. Observe que variable no básica del dual tiene coste relativo nulo. Escriba las relaciones del dual interviniendo solo las variables del dual con coste relativo nulo. Escriba la ecuación de la arista óptima del dual como combinación convexa de sus puntos extremos. Indique que variables del dual son óptimas en cada uno de los extremos de la arista óptima. 15. Una empresa textil puede producir tres productos (x1, x2, x3). Su plan de producción para el mes siguiente debe satisfacer las restricciones x1 + 2 x2 + 2 x3 ≤12 2 x1 + 4 x2 + x3 ≤f xj ≥ 0 La primera restricción está determinada por la disponibilidad del equipo y es fija. La segunda restricción está determinada por la disponibilidad de algodón. Los beneficios netos unitarios de los productos son 2, 3 y 3, respectivamente, sin tener en cuenta el coste del algodón y los costes fijos. -7- MCOI. Métodos Cuantitativos de Organización Industrial 3º GITI a) Halle el precio indicativo λ2 del algodón como una función de f. (Sugerencia: utilice el método símplex dual). Evalúe los valores de la variable del dual λ2 (f). Evalúe el beneficio neto Z(f), sin tener en cuenta el coste del algodón. Represente gráficamente el beneficio neto Z(f) en función de f. En el mismo gráfico, represente el valor de λ2 (f). b) La empresa puede comprar algodón en el mercado libre al precio de 1/6 u.m./unidad. Además, puede adquirir una cantidad limitada S a un precio de 1/12 u.m./unidad de un proveedor con el que mantiene una relación especial. Determine el beneficio neto óptimo de la empresa π(S), como una función de S, teniendo en cuenta el coste del algodón. Represente gráficamente el beneficio neto óptimo π(S) en función de S. 16. Considere el problema primal Min. -5x1 - 8x2 s.a. 5 x1 + 2 x2 + h1 = 10 x1 + 2 x2 + h2 = 4 4 x1 + 6 x2 + h3 = 14 x1, x2, h1, h2, h3 ≥ 0 cuya tabla con costes relativos positivos, pero que corresponde a una solución inadmisible es, x1 0 x2 0 h1 1 h2 11 h3 -4 b -2 0 1 1 0 0 0 2 -3 -(1/2) 1 1 2 0 0 0 1 1 El dual puede escribirse como max λb, sujeto a λA≤c, λ libre. A la solución de la tabla le corresponde una solución admisible para el dual λ0. En este caso, el método simplex-dual, donde λN= λ0 - ∈ Y1, siendo Y1 = (1, 11, -4) la primera fila de la matriz inversa de la formada por los vectores columna de las variables básicas (h1, x2, x1) y ∈ > 0, es adecuado. Se le pide a usted que considere una modificación del método simplex-dual (nos referimos a él como MSD) a partir de otra fila de la inversa: la definición de la nueva solución admisible para el dual es λN= λ0 + ∈ Y2, siendo Y2 = (0, 2, -1/2) la segunda fila de la matriz inversa de la formada por los vectores columna de las variables básicas (h1, x2, x1) y ∈ > 0. -8- MCOI. Métodos Cuantitativos de Organización Industrial 3º GITI a) Describa λ0. Justifique que la dirección elegida es adecuada, pues la función objetivo del dual mejora en 1∈. b) El algoritmo MSD selecciona el mayor valor positivo de , que mantiene la admisibilidad en el dual para λN. Sea ese valor ∈*. El algoritmo emplea como nueva solución admisible para el dual λN= λ0 + ∈* Y2. Para determinar ∈* calcule las nuevas holguras del dual para λN en función de las antiguas holguras del dual con λ0 (las que aparecen en la tabla) y de ∈. c) Aplique el método MSD en la tabla del símplex del enunciado mediante el método que ha desarrollado. ¿Cuál es el valor de ∈* que le resulta? ¿Cuál es la nueva λN? ¿Cuál es la correspondiente solución admisible del primal para λN ? d) Generalice el resultado a la elección de dirección de modificación de la solución admisible para el dual λN= λ0 + ∈* Yi, siendo Yi la fila i-ésima de la inversa. Discuta el resultado general en base a la elección de Yi. 17. Considere el problema primal Max s.a. 5x1 + 8x2 5x1 + 2x2 x1 + 2x2 4x1 + 6x2 x1 , x 2 ≥ 0 ≤5 ≤4 ≤ 12 cuya tabla óptima, que corresponde a una solución degenerada es, x1 x2 h1 h2 h3 b 0 0 1 11 -4 1 0 1 0 2 -.5 2 1 0 0 -3 1 0 0 0 0 -1 -1 El dual puede escribirse como min λb, sujeto a λA≥c, λ≥0. Llamando hi a las holguras de las restricciones del primal e yj a las holguras de las restricciones del dual, conteste a las siguientes preguntas: 1. Escriba explícitamente el problema primal con sus holguras hi y las restricciones como igualdades. Haga lo mismo con el problema dual, incluyendo las holguras yj así como las restricciones escritas con igualdades. Exprese la solución óptima del problema dual correspondiente a la solución óptima del primal de la tabla indicando los valores de las variables λi e yj. Indique cuales de las variables λi e yj son variables básicas y cuales no, expresando sus costes relativos. -9- MCOI. Métodos Cuantitativos de Organización Industrial 3º GITI 2. Identifique que variable no básica del dual tiene coste relativo nulo. Explique que conjunto de variables del dual pueden ser simultáneamente positivas sin que la solución deje de ser óptima para el dual. Escriba la ecuación de la arista del dual a partir del vértice óptimo del dual que corresponde a la solución óptima de la tabla del primal que se incluye. Escriba el otro vértice óptimo de la arista. Escriba el conjunto de soluciones óptimas alternativas del dual como combinación convexa de ambos vértices óptimos. Nota: El enfoque de la contestación a esta pregunta debe evitar el uso de los métodos simplex primal, simplex-dual y el simplex aplicado directamente al problema dual. 18. A. Considere un problema lineal cuya tabla inicial para la fase 1 tiene la estructura que se muestra, que proviene de que la tercera restricción tenga signo de igualdad. x1 x2 x3 h1 h2 w3 b 1. Construya una tabla del final de la fase 1 en la que se muestre que el problema original es compatible y tiene un vértice admisible x1 = 1, x2 = 2, x3 = 0, h1 = 0, h2 = 4. Argumente el coste relativo que deben tener todas las variables en dicha tabla. 2. Construya una tabla del final de la fase 1 en la que se muestre que el problema original es incompatible. B. Considere ahora un problema lineal cuya tabla inicial para la fase 1 tiene la estructura que se muestra, que proviene de que la tercera y cuarta restricción tengan signo de igualdad. x1 x2 x3 h1 h2 w3 w4 b 1. Construya una tabla del final de la fase 1 en la que se muestre que el problema original es compatible y tiene un vértice admisible x1 = 2, x2 = 0, x3 = 1, h1 = 3, - 10 - MCOI. Métodos Cuantitativos de Organización Industrial 3º GITI h2 = 0. Además, se observa que una de las cuatro restricciones es redundante. Argumente los costes relativos de todas las variables. 19. Considere los problemas primal y dual a partir de la forma estándar del primal, min cx min cx s a. Ax ≤ b ≡ s a. Ax + Ih = b x ≥0 x, h ≥ 0 dual max λ b max λ b s a. λ A ≤ c ≡ s a. λ A + I H = c λ ≤ 0, H ≥ 0 λ ≤ 0 En este ejercicio el problema primal correspondiente a la estructura de la tabla que se muestra. x1 x2 x3 h1 h2 h3 b 1. Escriba una tabla que refleje la solución óptima del primal que corresponde al vértice x1 = 0, x2 = 1, x3 = 2, h1 = 0, h2 = 0, h3 = 1. Y la solución óptima del dual compuesta por H1 = 1, H2 = 0, H3 = 0, λ1 = -1, λ2 = -2, λ3 = 0. 2. Escriba una tabla que refleje la solución de un vértice no óptimo del primal que corresponde a otro vértice del apartado anterior con x1 = 2, x2 = 1, x3 = 0, h1 = 1, h2 = 0, h3 = 0. Y la solución correspondiente del dual (λ = cBB-1) compuesta por H1 = 0, H2 = 0, H3 = -1, λ1 = 0, λ2 = +2, λ3 = -1. Realice una iteración de forma que alcance el óptimo. Se le pide ahora la construcción de una tabla canónica inicial siguiendo instrucciones y la realización de iteraciones mediante el algoritmo simplex-dual. La tabla canónica inicial debe tener todos los costes relativos no negativos, por lo que la solución básica que contiene es en ese sentido, óptima. Sin embargo, se le pedirá que sea inadmisible, con alguna variable negativa. 3. Mostrando la solución básica inadmisible del primal x1 = 6, x2 = 0, x3 = 1, h1 = 0, h2 = 0, h3 = -2. Y la solución correspondiente del dual (λ = cBB-1) compuesta por H1 = 0, H2 = 2, H3 = 0, λ1 = -1, λ2 = -4, λ3 = 0. 4. Aplique una iteración del método simplex-dual a la tabla del apartado anterior, de forma que alcance la solución óptima del primal x1 = 0, x2 = 0, x3 = 3, h1 = 2, h2 = 0, h3 = 0. Señale las variables básicas y las no básicas. Y que la solución correspondiente del dual (λ = cBB-1) esté compuesta por H1 = 0, H2 = 3, H3 = 0, λ1 = 0, λ2 = -6, λ3 = -1. Aplique una iteración del método simplex-dual a la tabla del apartado anterior, de forma que pueda calcular todas las soluciones óptimas alternativas del problema dual. Escriba el vértice óptimo nuevo y la expresión explícita de todas las soluciones óptimas del dual. - 11 - MCOI. Métodos Cuantitativos de Organización Industrial 3º GITI 20. Considérese el problema modelado de la siguiente forma: Max. s.a. x1 - 3 x 2 – x3 2 x1 + 4 x2 + 22/3 x3 ≤ 30 3 x1 + 3 x2 + x3 = 18 x2 ≥0, x3 ≥ 0, x1 ≥ 5 1. Plantee claramente el problema en las formas estándar y canónica. 2. Encuentre una solución admisible inicial del problema. A continuación encuentre la solución óptima del modelo aplicando Simplex Primal. 3. Compruebe si la solución anterior sigue siendo óptima para la nueva función objetivo Max x1 + 3 x2 + 5. Busque el nuevo óptimo si así fuera necesario. A partir de la forma canónica en el óptimo obtenida en el apartado 2, Compruebe si la solución sigue siendo óptima en caso que x2 fuera una variable libre. Actualice para ello la tabla óptima a esta nueva situación empleando para el menor esfuerzo posible. Intente proporcionar una nueva solución óptima si fuera necesario. 4. 21. La fabricación de ciertos productos (x1, x2, x3) tiene unos beneficios en el mercado de (100, 200, 300) respectivamente. En su fabricación se emplean: materia prima (MP), líquido refrigerante (LR) y lubricante (LU). Disponiéndose de un total de 1000 kgs de MP, 100 litros de LR y 50 litros de LU. Siendo la cantidades necesarias para la fabricación de cada tipo de producto las siguientes:


Para x1: 25 kgs de MP, 1 litro de LR y ½ litro de LU. Para x2: 15 kgs de MP, 2 litros de LR y 1 litro de LU. Para x3: 100 kgs de MP, 5 litros de LR y 10 litros de LU. Teniendo en cuenta que una solución admisible no óptima del problema es: (x 0 1 ) , x 20 , x30 , sobrante de MP, sobrante de LR, sobrante de LU = (0 , 0 , 5 , 500 , 75 , 0 ) Se pide: max  1. Formule el problema indicado como un problema del tipo s.a.   cx Ax = b x≥0      2. Formule su correspondiente problema dual como un problema del tipo λb min    s.a. λA ≥ c   λ libre   - 12 - MCOI. Métodos Cuantitativos de Organización Industrial 3º GITI 3. Determine como valoraría los recursos asociados a la solución básica admisible señalada. 4. A partir del apartado anterior, si decidiera ahora fabricar producto 1 adicionalmente, ¿cómo valora esa opción? Compárela con el beneficio que el producto le proporciona en el mercado. ¿Qué decidiría en tal caso? 5. Teniendo en cuenta que la siguiente solución es óptima: x , x 2* , x3* , sobrante de MP * , sobrante de LR * , sobrante de LU * = (0 , 50 , 0 , 250 , 0 , 0 ) determine todas las posibles valoraciones que se puedan hacer de los recursos. ¿Cómo explica que haya varias? ( ) * 1 NOTA: Para el problema no haga uso de los algoritmos Simplex o Simplex-Dual PROBLEMAS DE MODELADO CONTINUO 1. Problema.- Para hacer cuatro trabajos se dispone de tres operarios: un carpintero, un fontanero y un mecánico. La tabla recoge los costes de realización según el trabajo que se les encomiende a cada operario. También se indica mediante “X” la imposibilidad de realizar un trabajo por un operario. Soldar Enmarcar Trazar Alambrar Carpintero X 2 5 3 Fontanero 1 X 4 2 Mecánico 3 3 1 X Se pretende decidir los trabajos encomendados a cada operario de forma que ningún trabajador realice más de dos trabajos, que todos los trabajos se realicen y que el coste total acumulado de realizar los cuatro trabajos sea mínimo. a) Modele el problema mediante programación lineal. b) Demuestre que si el carpintero realiza el enmarcado, el mecánico el trazado y el fontanero suelda y alambra, el coste total es mínimo. 2. Problema.- COMIDAS RÁPIDAS Un negocio de servicio de comidas ha contratado cuatro banquetes para los próximos cuatro días, requiriendo 150 manteles de mesa limpios para el primer banquete, 100 para el segundo, 140 para el tercero y 130 para el cuarto. En la actualidad dispone de 200 manteles, todos limpios, y puede adquirir los que necesite, a un coste de 12 u.m/mantel con un plazo de entrega inmediato a partir del segundo día. Además, una lavandería cercana le ofrece el siguiente servicio: - 13 - MCOI. Métodos Cuantitativos de Organización Industrial 3º GITI Rápido. Los manteles limpios para el día siguiente, a un coste de 6 u.m/mantel. Lento. Los manteles limpios para dentro de dos días, a un coste de 4 u.m/mantel. Suponga que los manteles nuevos comprados el día t pueden emplearse en el banquete del día t, los sucios enviados a lavar en servicio rápido tras el banquete del día t pueden emplearse para el banquete del día t+1, y finalmente, que los sucios enviados a lavar en servicio lento tras el banquete del día t pueden emplearse para el banquete del día t+2. a) Modele el problema: represente el problema mediante un grafo, indicando que significan los nodos y los arcos. Y los datos del ejemplo asociados a los nodos y arcos. b) Proporcione una solución admisible intuitiva al ejemplo. c) Argumente la bondad de la solución admisible intuitiva al ejemplo propuesta en el apartado anterior. d) Describa las variables del problema dual e interprete su significado. ¿En que unidades se describen cada una de las variables del dual? 3. Problema.- TRATAMIENTO DE CRUDOS Una refinería de petróleo adquiere dos tipos de crudos (tipo 1 y tipo 2). Estos crudos pasan a través de cuatro procesos: destilación, reforming, cracking y mezcla, obteniéndose distintos productos para el mercado. 1.- PROCESO DESTILACIÓN Por medio de ella se separan los crudos en fracciones conocidas como nafta ligera, nafta media, nafta pesada, aceites pesados y residuos, según sus puntos de ebullición. El octanaje de las naftas ligeras, medias y pesadas es de 90, 80 y 70, respectivamente. Las fracciones que se obtienen a partir de un barril de crudo son: Crudo Tipo 1 Crudo Tipo 2 Nafta Ligera Nafta Media 0.1 0.2 0.15 0.25 Nafta Pesada Aceite Ligero 0.2 0.12 0.18 0.08 Aceite Pesado 0.2 0.19 Residuos 0.13 0.12 2.- PROCESO REFORMING Las naftas pueden emplearse inmediatamente para mezclarse en distintos productos para el mercado o someterse al proceso de reforming. Este proceso da lugar a gasolinas con un octanaje del 115. La cantidad obtenible, por barril es: - 14 - MCOI. Métodos Cuantitativos de Organización Industrial 3º GITI Nafta Ligera Nafta Media Nafta Pesada 0.6 0.52 0.45 3.- PROCESO CRACKING Los aceites ligeros y pesados pueden mezclarse directamente en Jet-fuel y fuel-oil o someterse al proceso de cracking. El cracker catalítico da lugar a cracked oil y cracked gasolina que tiene un octanaje de 105. La productividad es la siguiente: Aceite Ligero Aceite Pesado Cracked oil 0.68 0.75 Cracked gasoline 0.28 0.2 El cracked oil se emplea para mezclarlo en fuel-oil y jet-oil, mientras que el cracked gasolina se emplea para la obtención de gasolina de motor. Los residuos se emplean para producir lube-oil o mezclados en fuel-oil y jet-fuel. Un barril de residuos da lugar a 0.5 barriles de lube-oil. 4.- PROCESO MEZCLA - Gasolinas de Motor: Son de dos tipos, normal y superior, obtenidas a partir de las naftas, gasolina de reforming y gasolina de cracking. La única especificación es que la normal tenga un octanaje de al menos 84, y la superior de 94. Se supone que el octanaje se comporta linealmente en relación al volumen. - Jet fuel (para avión): La especificación es que la presión de vapor no exceda de 1 Kg/cm2. Las presiones de vapor de los aceites ligeros, pesados, de cracking y residuos son de 1; 0.6;1.5; y 0.05 Kg/cm2 respectivamente. De nuevo, se supone que la presión de vapor se comporta linealmente con el volumen. - Fuel-oil: Para su obtención deben mezclarse aceite ligero, pesado, cracked y residuos según la relación 10:4:3:1. LIMITACIONES Existen las siguientes limitaciones debido a las instalaciones actuales: Disponibilidad de crudo • Disponibilidad diaria de Crudo tipo 1: 20.000 barriles. • Disponibilidad diaria de Crudo tipo 2: 30.000 barriles. Limitaciones de los procesos • Máximo de 45.000 barriles de crudo destilado/día. • Máximo de 10.000 barriles de nafta reforming/día. - 15 - MCOI. Métodos Cuantitativos de Organización Industrial 3º GITI • Máximo de 8.000 barriles de aceite cracked/día. Imposiciones en la producción • La producción diaria de lube-oil entre 500 y 1.000 barriles. • La gasolina de motor tipo superior debe ser al menos el 40% del normal. Beneficios por barril de productos finales • Gasolina de Motor Superior 700 pts/barril • Gasolina de Motor Normal 600 pts/barril • Jet-fuel 400 pts/barril • Fuel-oil 350 pts/barril • Lube-oil 150 pts/barril Determinar los niveles de producción de los productos finales de la refinería desde el punto de vista de máximos beneficios. DEFINICIÓN DE VARIABLES - Crudo tipo 1: T1 - Crudo tipo 2: T2 - Nafta ligera: NFL - Nafta media: NFM - Nafta pesada: NFP - Aceite ligero: ACL - Aceite pesado: ACP - Residuos: RES - Nafta ligera para gasolina: NFLG - Nafta media para gasolina: NFMG - Nafta pesada para gasolina: NFPG - Nafta ligera para reforming: NFLRE - Nafta media para reforming: NFMRE - Nafta pesada para reforming: NFPRE - Nafta ligera para gasolina normal: NFLGN - Nafta ligera para gasolina superior: NFLGS - Nafta media para gasolina normal: NFMGN - Nafta media para gasolina superior: NFMGS - Nafta pesada para gasolina normal: NFPGN - Nafta pesada para gasolina superior: NFPGS - Aceite ligero para cracking: ACLCR - Aceite pesado para cracking: ACPCR - Aceite ligero para fuel-oil: ACLF - Aceite pesado para fuel-oil: ACPF - Aceite ligero para jet-fuel: ACLJF - Aceite pesado para jet-fuel: ACPJF - Cracked oil: COIL - Cracked oil para fuel-oil: COILF - Cracked oil para jet-fuel: COILJF - Cracked gasolina: CG - Cracked gasolina para normal: CGN - 16 - MCOI. Métodos Cuantitativos de Organización Industrial 3º GITI - Cracked gasolina para superior: CGS Gasolina de 115 octanos: REFG Gasolina de 115 octanos para gasolina normal: REFGN Gasolina de 115 octanos para gasolina superior: REFGS Residuos para lube-oil: RESLB Residuos para fuel-oil: RESF Residuos para jet-fuel: RESJF Gasolina normal: GSNOR Gasolina superior: GSSUP Jet fuel: JETFL Fuel-oil: FOIL Lube-oil: LUBOIL Holgura de crudo tipo 1: HT1 Holgura de crudo tipo 2: HT2 Holgura en reforming: HREF Holgura en cracking: HCR Holgura en destilación: HDEST Pérdidas en destilación: PERDES Modele y resuelva, usando el módulo SOLVER de EXCEL. http://io.us.es/asignat/MCOP/mcop(ii).html - 17 - MCOI. Métodos Cuantitativos de Organización Industrial 3º GITI PROBLEMAS DE MODELADO CON VARIABLES ENTERAS 1. Problema.- ASIGNACIÓN Un grupo de n hombres y n mujeres viven aislados en una isla. La cantidad de felicidad que logra el i-ésimo hombre y la j-ésima mujer viviendo juntos la fracción xij de sus vidas es cijxij, donde cij es un indicador de felicidad asociado a la convivencia ij durante el resto de sus vidas. Suponiendo que todos son solteros cuando se analiza la situación y que todos vivan el mismo tiempo, modele el problema de determinar qué fracción de su vida han de convivir cada par ij. a) Bajo el criterio de maximizar la felicidad colectiva. b) Bajo el criterio de que sea máxima la felicidad de aquel que en el emparejamiento le corresponda la felicidad mínima. 2. Problema.- SELECCIÓN DE PERSONAL A un proceso de selección para un grupo de trabajo se han presentado seis candidatos, de los que se van a contratar a cuatro. Las características de los candidatos se reflejan en la tabla. Candidato Tipo Puntuación indicadora 1 A 10 2 A 9 3 B 6 4 B 6 5 C 4 6 C 1 Los condicionantes de la contratación, tras las entrevistas son: - Al menos ha de contratarse un candidato tipo C. - Los candidatos 2 y 5 son incompatibles. - Solo un candidato del tipo A podría ser contratado. - Si se contratara a los candidatos 2 y 4, no podría contratarse al candidato 6. Modele la situación como un problema lineal con variables 0-1, empleando como criterio la maximización del indicador acumulado de los candidatos seleccionados. 3. Problema.- ENVÍOS Un servicio de mensajería tiene la oportunidad de contratar para su transporte a Nueva Zelanda de hasta 50 Kg. de envíos, por cada uno de los cuales la empresa ingresa 40 - 18 - MCOI. Métodos Cuantitativos de Organización Industrial 3º GITI u.m./Kg. El coste fijo por contratar el envío a Nueva Zelanda es de 1.300 u.m., más 10 u.m. por cada Kg de peso que transporte en exceso de 20 Kg y otro suplemento extra de 20 u.m. por cada Kg. de peso en exceso de 40 Kg. Modele el estudio de la decisión de la empresa de mensajería sobre si debe realizar el viaje a Nueva Zelanda y, en su caso, cuantos Kg. de envíos transportar. 4. Problema.- CENTRALES ELÉCTRICAS Un número de centrales eléctricas están encargadas de dar servicio a la siguiente demanda media eléctrica diaria prevista, vea la tabla 12.1. Tabla 12.1. Demanda de potencia 12 p.m. a 6 a.m. 6 a.m. a 9 a.m. 9 a.m. a 3 p.m. 3 p.m. a 6 p.m. 6 p.m. a 12 p.m. 15.000 megavatios 30.000 megavatios 25.000 megavatios 40.000 megavatios 27.000 megavatios Existen tres tipos de centrales de generación disponibles: 12 de tipo 1, 10 de tipo 2 y 5 de tipo 3. Cada generador tiene que trabajar entre un nivel mínimo y un nivel máximo. Se conoce el coste por hora cuando el generador trabaja al mínimo, así como el extracoste por hora y por megavatio por encima del mínimo (hasta el máximo posible). Poner en marcha un generador también tiene un coste. Todos los costes se observan en la tabla 12.2. Tabla 12.2. Características de las centrales de generación Generador Tipo 1 Generador Tipo 2 Generador Tipo 3 Nivel mínimo Nivel máximo Coste por hora al mínimo 850 MW 2000 MW 1000 Coste por hora y megavatio por encima del mínimo 2 Coste de arranque 1250 MW 1500 MW 1750 MW 2600 1,30 1000 4000 MW 3000 3 500 2000 Además la carga posible a suministrar por las generadoras debe ser tal que permita dar respuesta a puntas de carga de hasta el 15% por encima del máximo estimado en la tabla 12.1. 1. Identifique las variables y datos del problema y construya un modelo de forma que permita determinar los generadores que deben funcionar en cada periodo del día. Determine cual es el coste marginal de producción de electricidad en cada periodo del día y discuta que sistema de tarifas aconsejaría fijar para los clientes. - 19 -