Universidad de Santiago de Chile Departamento de Ingeniera en Minas Ayudanta de Optimizacin

GUIA N1 DE EJERCICIOS OPTIMIZACIN

Preparado por Felipe Quezada Castaeda

Universidad de Santiago de Chile Departamento de Ingeniera en Minas Ayudanta de Optimizacin

EJERCICIOS PEP 1
PROBLEMA #1 Una fbrica de jugos de 1 litro (1000 cc) desea lanzar al mercado una nueva variedad de jugo. Para ello, disponen de 4 ingredientes base. La nueva variedad apuntar a conservar un balance alimenticio, debiendo contener al menos un 15% de vitamina C, y a lo ms un 30% de potasio. Existe adems una relacin entre los betacarotenos y la vitamina A que impone lo siguiente: la cantidad de vitamina A debe ser, cuando menos, un tercio de los betacarotenos. Adems, la vitamina A no puede superar el 35% del contenido del jugo. El costo por adquirir los ingredientes, los lmites de los pedidos por da, y los aportes porcentuales de cada componente a los ingredientes por unidad se resumen en la siguiente tabla:
Potasi o 20% 5% 35% 15% Vitamina C 15% 40% 20% 25% Vitamina A 30% 10% 25% 35% Betacarotenos 35% 45% 20% 25% Costo [$/u] 25 13 10 20 Lmite [u] 6 9 8 5

Ingrediente 1 Ingrediente 2 Ingrediente 3 Ingrediente 4

FORMULAR (NO RESOLVER) un modelo de programacin lineal que permita minimizar los costos, cumpliendo con todos los requerimientos. Considere, para tal caso, que cada unidad son 100 cc. Defina claramente variables, funcin objetivo y restricciones. SOLUCIN: Primero formulamos las variables del modelo. Sea la cantidad de unidades del ingrediente para la nueva variedad ( ). Como se desea minimizar los costos, la funcin objetivo estar dada por: ( ) Ahora veamos las restricciones. En la nueva variedad, la combinacin de los 4 ingredientes debe conformar una unidad de jugo, por lo cual la primera restriccin se define de la siguiente manera: ( ) ( )

En el caso de la mezcla separamos por ingrediente. Para la vitamina C, la suma de las cantidades de los ingredientes conforma, por lo menos, un 15% del juego (que son 150 cc). Por lo tanto:

Para el potasio, la suma de las cantidades de cada ingrediente no puede superar el 30% del total del juego (que son 300 cc). Luego:

Para la vitamina A, esta suma debe ser al menos 1/3 de los betacarotenos. Por lo tanto: 1

Universidad de Santiago de Chile Departamento de Ingeniera en Minas Ayudanta de Optimizacin

( De manera simplificada:

Adems, la contribucin de la vitamina A no debe superar el 35% del jugo (350 cc). Por ende:

Por ltimo, para los lmites diarios, tenemos:

Naturalmente.

. El modelo es entonces el siguiente: ( ) ( )

PROBLEMA #2 Formule y resuelva adecuadamente el siguiente problema de programacin lineal. La primera iteracin debe ser realizada mediante el algoritmo smplex. La segunda y siguientes efectuarlas empleando el mtodo smplex revisado o matricial:

( )

Universidad de Santiago de Chile Departamento de Ingeniera en Minas Ayudanta de Optimizacin

SOLUCIN: Primero hacemos el cambio de variable , a fin de tener slo variables no negativas. Reescribiendo el PPL en forma estndar, se tiene: ( )

El problema debe resolverse en dos fases. La fase 1 minimizar la funcin objetivo ( ) . Procedemos en la primera iteracin mediante el algoritmo smplex. La tabla de inicio para este problema es la siguiente. Observe que se han marcado en la tabla la inversa respectiva, as como el elemento pvot para la respectiva iteracin: V.B -4 3 1 5 0 3 Entra V.B -4 11 1 1 -1 Entra , sale . 1 0 0 0 0 -7 16 4 -8 -4 -3 10 2 -4 -2 0 0 -1 0 1 1 -2 0 1 1 0 1 0 0 0 0 0 1 0 0 50 50 10 50 -10 ; sale 1 2 0 -1 0 -1 -7 2 4 -1 0 3 -3 4 2 -1 0 1 0 0 -1 0 0 1 1 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 1 0 50 150 10 0 0 -60 ( ) 50 75 ---

. Primera iteracin: ( ) 50/7 25/8 5/2

Las siguientes iteraciones deben hacerse mediante el algoritmo smplex revisado. De la tabla anterior reconocemos la matriz inversa de esta primera iteracin: ( )

Como ya definimos el pvot y las variables de entrada y salida a partir de la tabla anterior, podemos calcular inmediatamente la matriz :

) 3

Universidad de Santiago de Chile Departamento de Ingeniera en Minas Ayudanta de Optimizacin

Calculamos

para dar inicio a la segunda iteracin:

( ( )

) ( )

Construimos una pequea tabla para verificar el orden de las variables bsicas: V.B. ( ) ( )

Calculamos los valores duales para esta iteracin:

) ( )

Calculamos los coeficientes (o costos) reducidos para esta iteracin: ( Luego: ( Por lo tanto: ( ) ( ) ) ( ) ( ) ( ) )

Como todos los coeficientes reducidos de la funcin objetivo w son nulos, hemos llegado al ptimo para la fase 1. Como y son no bsicas, y por tanto nulas, se tiene que ( ) , por lo que existe un espacio de soluciones factible para el PPL original en la fase 2. Ahora debemos calcular los valores duales para la funcin objetivo z en la fase 2 (iteracin 2). Verificando el orden de las variables bsicas: V.B. ( ) ( )

Universidad de Santiago de Chile Departamento de Ingeniera en Minas Ayudanta de Optimizacin

Por lo tanto: ( ) ( ) ( Calculamos los costos reducidos: ( Luego: ( ) ( ) ( ) ( ) ) ) ( )

Por lo tanto: ( ) ( )

Como el coeficiente reducido de en la funcin objetivo es negativo, an no estamos en el ptimo. Se tiene que es la variable de entrada para la tercera iteracin, porque tiene el coeficiente ms negativo en la fila objetivo. Calculamos entonces las columnas y ( ) para determinar la variable de salida y el elemento pvot: ( ) ( ) ( )

( )

( )

Por lo tanto: V.B. 135/2 10 5/2 ( ) -7/4 (135/2):(-7/4) = -270/7 Ignorar 4 10/4 = 5/2 Mnimo -1/4 (5/2):(-1/4) = -10 Ignorar . El pvot corresponde a 4.

La variable de salida es entonces Calculamos la matriz inversa :

Donde: 5

Universidad de Santiago de Chile Departamento de Ingeniera en Minas Ayudanta de Optimizacin

( Entonces:

Verificamos el orden de las variables bsicas: V.B. ( ) ( )

Calculamos los valores duales:

) ( )

Calculamos los costos reducidos: ( Luego: ( ) ( ) ( ) ( ) )

Por lo tanto: ( ) ( )

Universidad de Santiago de Chile Departamento de Ingeniera en Minas Ayudanta de Optimizacin

Como ahora todos los coeficientes reducidos son no negativos, hemos llegado al ptimo. Calculamos entonces para encontrar la solucin ptima de este problema: ( ) ( ) ( )

Por lo tanto, la solucin ptima es y . El resto de las variables son ( ) nulas. Reemplazando estos valores en la funcin objetivo se obtiene , con ( ) lo cual . PROBLEMA #3 Considere el problema de programacin lineal cuyo tableau final (ptimo) es el siguiente. Asuma que Si es la variable de holgura para la restriccin i. V.B. X1 S1 -Z a) b) c) d) X1 1 0 0 X2 -5 2 3 X3 4 1 1 X4 13 6 8 S1 5 10 4 S2 0 1 0 b 7 3 76

Cules son las variables bsicas? Cules son las variables no bsicas? Cul es la solucin ptima? Qu puede decir acerca de las restricciones 1 y 2? Cules son las unidades adicionales?

SOLUCIN: Tenemos: a) Las variables bsicas son y .

b) Las variables no bsicas estn conformadas por el resto de variables que no se encuentran en la base: son no bsicas. c) La solucin ptima es . Su valor es ( ) . d) En ambas restricciones hay variables de holgura asociadas. El recurso asociado a la primera restriccin se considera abundante, porque no se ha consumido del todo, ya que la variable de holgura asociada, , es mayor que cero. El recurso asociado a la segunda restriccin se considera escaso, porque su holgura es nula.

PROBLEMA #4 Una fbrica de ropa produce tres lneas de trajes: jeans, franela y amasado. La ropa es vendida en lotes de 100 trajes de cada tipo. Cada lote pasa a travs de tres procesos: corte, cosido y empaque. La planta dispone de 16 cortadores como mximo, 41 mquinas de coser como mximo y debe ocupar a 10 empacadores (no ms no menos). Los

Universidad de Santiago de Chile Departamento de Ingeniera en Minas Ayudanta de Optimizacin

requerimientos para producir un lote de 100 trajes de cada tipo y las utilidades asociadas, se presenta a continuacin: Requerimientos de Produccin y Utilidad Cortadores [Personas/Lote] Mquinas de Coser [Mquinas/Lote] Empacadores [Personas/Lote] Utilidad [$/Lote] Jeans Franelas Amasados 4 2 1 1 2 1 1 1 1 400 200 300

FORMULE un modelo de programacin lineal que permite maximizar las utilidades de la fbrica. Defina claramente variables, funcin objetivo y restricciones. A continuacin, RESUELVA el modelo que plante utilizando el mtodo que ms le acomode. SOLUCIN: El objetivo de la fbrica es determinar las cantidades de cada lote de ropa a fabricar, de tal forma que stos maximicen las utilidades. Sea la cantidad de lotes de ropa a fabricar del tipo . De la tabla, podemos obtener inmediatamente la funcin objetivo: ( ) Las restricciones del problema estn asociadas al lmite de recursos impuesto por la fbrica en funcin de la cantidad de cortadores, mquinas de coser y personal encargado de empacar. As, se tiene lo siguiente: Cortadores:

Mquinas de coser:

Personal de empaque:

El modelo completo es entonces: ( )

El modelo puede resolverse utilizando cualquier mtodo. En este caso particular, podemos hacer un arreglo algebraico sencillo que permita solucionarlo mediante el mtodo grfico. De la tercera restriccin, despejamos, con lo cual resulta ( ). Reemplazando en el PPL, obtenemos: 8

Universidad de Santiago de Chile Departamento de Ingeniera en Minas Ayudanta de Optimizacin

( )

El espacio de soluciones factible (ESF) de este problema es el siguiente:

Figura 1: ESF del problema anterior Notemos que los nicos puntos candidatos a solucin ptima de este problema son A y B. Evaluando la funcin objetivo se obtiene que el punto esquina ptimo es B, dado por lotes de jeans, resultando no rentable fabricar lotes de franela (porque ). Reemplazando lo anterior en el modelo original, se obtiene que lotes de amasados. ( ) La utilidad mxima que percibe la fbrica es de unidades monetarias.

PROBLEMA #5 Escriba el DUAL del siguiente problema. Verifique que el dual del dual es el problema original. ( )

) 9

Universidad de Santiago de Chile Departamento de Ingeniera en Minas Ayudanta de Optimizacin

SOLUCIN: Del primal, tenemos que:

Debemos hacer entonces dos cambios de variable: en , se tiene:

. Reemplazando

La ltima expresin podemos fragmentar en dos restricciones independientes: . Adems, la expresin independientes:

tambin podemos fragmentarla en dos restricciones .

Escribimos entonces el problema primal en forma cannica (primal simtrico): ( )

Construimos ahora el problema dual. Notemos que, a partir de la definicin, el dual tendr 8 variables y 5 restricciones. Adems, la variable dual es no restringida, mientras que el resto son no negativas. ( )

La comprobacin de que el dual del dual es el primal es obvia, y se deja como ejercicio al lector.

10

Universidad de Santiago de Chile Departamento de Ingeniera en Minas Ayudanta de Optimizacin

PROBLEMA #6 La compaa minera FERROJAC CHILE tiene dos operaciones mineras que alimentan de mineral de hierro a una sola planta. Cada mina tiene dos reas de las cuales puede extraer el mineral. La ley alimentada a planta debe ser mayor que 35% Fe, y debe ser menor que 12% Si. La planta requiere al menos 45.000 toneladas, pero no puede manejar ms de 60.000. El mercado interno requiere que al menos 12.000 toneladas de Fe deben estar disponibles para el consumo asumir un 90% de recuperacin en el proceso. La razn promedio de estril/mineral determinada para las operaciones de extraccin mineral tiene un valor de 3,5. Dado los datos que se indican, FORMULAR (no RESOLVER) un modelo de programacin lineal, el cual permita obtener un plan minero de produccin que cumpla las restricciones operacionales y permita minimizar la desviacin de la razn estril/mineral total. Mina Cerro GRANATE Lomas BAYAS rea Norte Lomas Sur Sur Alberta Reservas (toneladas) 20.000 10.000 15.000 30.000 % Fe 40 30 40 35 % Si 17 10 11 13 Razn Estril/Mineral 3,0 2,0 4,0 5,0

SOLUCIN: Primero definimos las variables del problema: : Produccin Cerro Granate, rea Norte : Produccin Cerro Granate, rea Lomas : Produccin Lomas Bayas, rea Sur Sur : Produccin Lomas Bayas, rea Alberta Para este problema, es muy til la elaboracin de un diagrama que muestre el proceso en cuestin:

Ley de Fe 35% Ley de Si 12%

Planta

Figura 2: Esquema del proceso que se debe modelar en Problema #6 Ahora veamos las restricciones del problema. En cuanto a las capacidades de la planta, como sta debe recibir al menos 45.000 toneladas y no ms 60.000 toneladas, se tendr: 11

Universidad de Santiago de Chile Departamento de Ingeniera en Minas Ayudanta de Optimizacin

Si el mercado interno requiere de, al menos, 12.000 toneladas de Fe, entonces el 90% de la produccin que llega a planta, en trminos del Fe, debe conformar como mnimo, este tonelaje. Luego: ( )

Se debe agregar que los sectores de produccin tienen como limitante a sus reservas totales. Luego:

Por ltimo, la planta debe recibir como mnimo una ley del 35% de Fe y, a lo ms, una ley del 12% de Si. Luego, tenemos lo siguiente: ( ( ) )

Ahora veamos la funcin objetivo. Como se requiere minimizar la desviacin de la razn estril mineral, se tendr: ( ) ( ) ( )

El modelo completo es entonces: ( )

( ,

) ( )

PROBLEMA #7 Resuelva el siguiente problema de programacin lineal, empleando el mtodo smplex para la fase 1, y el mtodo smplex revisado para la fase 2: ( )

12

Universidad de Santiago de Chile Departamento de Ingeniera en Minas Ayudanta de Optimizacin

SOLUCIN: Se debe reescribir el PPL en forma estndar. Se tiene entonces: ( )

El problema debe resolverse en dos fases. La fase 1 minimizar la funcin objetivo ( ) . Procedemos en la primera fase mediante el algoritmo smplex. La tabla de inicio para este problema es la siguiente: V.B. -3 -3 1 -2 0 2 Entra V.B. -3 3 1 -5 -1 Entra V.B. -7/4 0 1/4 -7/2 0 1 0 0 0 0 0 0 1 0 0 -1/2 4 1/2 -1 0 1 -2 0 1 1 0 1 0 0 0 5/4 -3 1/4 3/2 1 -5/4 3 -1/4 -3/2 0 550 340 30 580 0 , sale 1 0 0 0 0 -5 12 4 -6 -4 -3 10 2 -4 -2 1 -2 0 1 1 0 1 0 0 0 0 0 1 0 0 0 0 -1 0 1 400 700 120 400 -120 , sale 1 2 0 -1 0 -1 -5 2 4 -1 0 1 -3 4 2 -1 0 1 1 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 -1 0 0 1 400 1500 120 0 0 -520 ( ) 400 750 ---

. Primera iteracin. ( ) --175/3 30

. Segunda iteracin. ( ) ----120

( ) Entra , sale . Como , con , entonces existe un ESF para el PPL en la fase 2. Procedemos entonces mediante el mtodo smplex revisado en dicha fase. La matriz inversa de la presente iteracin es:

13

Universidad de Santiago de Chile Departamento de Ingeniera en Minas Ayudanta de Optimizacin

Como ya definimos el pvot y las variables de entrada y salida a partir de la tabla anterior, podemos calcular inmediatamente la matriz :

( ( Luego calculamos )

para dar inicio a la cuarta iteracin:

) ( )

Construimos una pequea tabla para verificar el orden de las variables bsicas: V.B. ( ) ( )

Calculamos los valores duales para esta iteracin: ( ) ( ) ( ) ( )

Calculamos los costos reducidos: ( Luego: ( Por lo tanto: ) ( ) ( ) ( ) )

Como el coeficiente reducido de en la funcin objetivo es negativo, an no estamos en el ptimo. Se tiene que es la variable de entrada para la tercera iteracin, porque tiene el coeficiente ms negativo en la fila objetivo. Calculamos entonces las columnas y ( ) para determinar la variable de salida y el elemento pvot:

14

Universidad de Santiago de Chile Departamento de Ingeniera en Minas Ayudanta de Optimizacin

( )

( )

Por lo tanto: V.B. 760 340 120 La variable de salida es entonces Calculamos la matriz inversa : ( ) -3 760:(-3) = -253.33 Ignorar 3 340:3 = 113.33 Mnimo -1 120:(-1) = -120 Ignorar . El pvot corresponde a 3.

Donde:

( Entonces:

( ( )

) ( )

Verificamos el orden de las variables bsicas: ( ( ) )

V.B.

Calculamos los valores duales:

15

Universidad de Santiago de Chile Departamento de Ingeniera en Minas Ayudanta de Optimizacin

Calculamos los costos reducidos: ( Luego: ( Por lo tanto: ( ) ( ) ) ( ) ( ) )

Como ahora todos los coeficientes reducidos son no negativos, hemos llegado al ptimo. Calculamos entonces para encontrar la solucin ptima de este problema: ( ) ( ) ( )

Por lo tanto, la solucin ptima es estos valores en la funcin objetivo se obtiene .

. Reemplazando ( ) , con lo cual

PROBLEMA #8 Un florista sabe hacer slo dos tipos de arreglos florales, para los cuales dispone de 3 tipos distintos de flores: rosas, tulipanes e ibizcos. Los requerimientos de flores para cada arreglo, la disponibilidad de flores y los requerimientos de cada arreglo vienen dados en la siguiente tabla: FLORES Arreglo 1 Arreglo 2 DISPONIBILIDAD Rosas 3 1 300 Tulipanes 1 1 140 Ibizcos 1 3 300 PRECIO [$] 2000 1000 a) FORMULE un PPL que resuelva el problema de maximizacin de ingresos por ventas sujeto a la disponibilidad de recursos. b) Cul es el problema DUAL asociado? Qu situacin podra estar optimizando? Justifique. c) Usando el teorema de holguras complementarias, encuentre la solucin ptima del problema dual una vez resuelto el problema primal utilizando el mtodo smplex. 16

Universidad de Santiago de Chile Departamento de Ingeniera en Minas Ayudanta de Optimizacin

d) Suponga que retorna frustrado despus que una bella dama le cerrara la puerta cuando usted le llevaba amablemente una rosa, un tulipn y un ibizco. Si se encuentra con el florista Cunto cree que estara dispuesto a pagar l por sus flores? SOLUCIN: Tenemos lo siguiente: a) Sean y los dos tipos de arreglos que puede hacer el florista. De la tabla, y en forma inmediata, se obtiene el PPL deseado: ( )

b) Es posible formular inmediatamente el problema dual a partir del primal, sin utilizar la transformacin de primal simtrico, invirtiendo las situaciones presentadas en la definicin de ambos problemas. Se tiene entonces: ( )

El modelo dual resuelve el problema de un agente externo que desea saber el precio unitario que puede ofrecer por cada una de las flores, en el caso de ste quiera comprarle todas las flores al florista. As, y son los precios unitarios asociados a las rosas, tulipanes e ibizcos, respectivamente. c) Reescribiendo el primal en forma estndar: ( )

Tabla de inicio: V.B. 3 1 1 -2000 Entra , sale 1 1 3 -1000 1 0 0 0 0 1 0 0 0 0 1 0 300 140 300 0 ( ) 100 140 300

. Procedemos con la primera iteracin:

17

Universidad de Santiago de Chile Departamento de Ingeniera en Minas Ayudanta de Optimizacin

V.B. 1 0 0 0 Entra V.B. 1 0 0 0 0 1 0 0 1/2 -1/2 1 500 -1/2 3/2 -4 500 0 0 1 0 80 60 40 -220000 , sale 1/3 2/3 8/3 -1000/3 1/3 -1/3 -1/3 2000/3 0 1 0 0 0 0 1 0 100 40 200 -200000

( ) 300 60 75

. Procedemos con la segunda iteracin:

Como todos los coeficientes de las variables en la funcin objetivo son no negativas, hemos llegado al ptimo. La utilidad mxima que puede percibir el florista es de $220.000, con arreglos florales del tipo 1, y arreglos florales del tipo 2. En este punto ptimo, es vlido el teorema de holguras complementarias. Por lo tanto: Para el primal: [ [ [ Para el dual: [ [ ( ( )] )] ( ( ( )] )] )]

Reemplazando los valores obtenidos en la solucin primal ptima en las holguras complementarias, se obtiene el siguiente sistema de ecuaciones:

Con lo cual se obtiene y . Este valor es correcto, porque si lo ( ) remplazamos en la funcin objetivo dual, resulta , que es equivalente a la funcin objetivo primal en el ptimo. Por lo tanto, el florista vender rosas y tulipanes a un precio de $500 c/u, y entregar como oferta los ibizcos gratis, siempre y cuando venda todo como un paquete. Esto tiene sentido, porque si vende slo las rosas y tulipanes, dado que slo sabe hacer los arreglos florales descritos, no le sacar provecho a los ibizcos. d) Si tuviramos tan desgraciada suerte, entonces, idealmente, el valor mximo que nos pagar el florista por las flores es el descrito con anterioridad: $500 por cada rosa y tulipn, y $0 por los ibizcos.

18

Universidad de Santiago de Chile Departamento de Ingeniera en Minas Ayudanta de Optimizacin

PROBLEMA #9 Dado el programa lineal: ( )

Se pide: a) Determinar el programa DUAL b) Representar grficamente este ltimo programa para mostrar su conjunto de soluciones factibles c) A partir de esta representacin, describir un proceso por el que tras dos, y slo dos operaciones de pivotado a partir del origen, se alcance la solucin. Estas operaciones de pivotado no tienen por qu seguir las reglas del smplex. d) Por medio de las relaciones que pueden establecerse a merced del principio de holgura complementaria, determinar la solucin del problema primal SOLUCIN: A partir del enunciado, se tiene: a) Se debe obtener el modelo lineal estndar (MLE) del problema. Para ello, hacemos los cambios de variable y , con lo cual el problema se re-escribe de la siguiente forma: ( )

Ahora podemos formular el problema dual: ( )

b) El espacio de soluciones factibles (ESF) del problema dual es el siguiente:

19

Universidad de Santiago de Chile Departamento de Ingeniera en Minas Ayudanta de Optimizacin

Figura 3: ESF del problema dual En el grfico anterior, los puntos esquina del ESF estn dados por los siguientes pares: Punto esquina Valor de G 4/3 B 3 C 36/7 J 6 Valor de 5/3 5 36/7 4 Valor objetivo -1/3 -2 -4/7 2 , y se cumple cuando estamos

Por tanto, el valor mximo del problema dual es en el punto esquina J.

c) Si el proceso de resolucin del problema dual no tiene por qu seguir las reglas del smplex, entonces basta que, a partir del origen, el algoritmo ignore la regla dada por el criterio de optimalidad en un problema de maximizacin, la cual dicta que se escoja siempre el coeficiente ms negativo en la fila objetivo del tableau smplex. Por tanto, si partimos desde el origen, podemos comenzar en el punto E, y luego llegar de inmediato al punto J utilizando el hecho de que, en este punto, se encuentra la solucin. Notemos que, adems, este nuevo proceso ignora la subdivisin del problema en dos fases, ya que se cuenta de inmediato con una solucin bsica de inicio (el origen). d) Utilizando el teorema de holguras complementarias (THC), se obtiene: Para el primal: [ [ Para el dual: ( ( )] )]

20

Universidad de Santiago de Chile Departamento de Ingeniera en Minas Ayudanta de Optimizacin

[ [ [ [

( ( ( (

)] )] )] )]

De las holguras complementarias para el primal, se obtiene:

Con lo cual se obtiene y , lo que conforma la solucin ptima del problema primal. Todas las dems variables son nulas. El valor de la solucin ptima ( ) es .

PROBLEMA #10 La Compaa Minera ASIOP S.A. (ASIOPSA) produce dos tipos distintos de concentrado, cobre y zinc. La siguiente tabla muestra las demandas mensuales esperadas para cada producto (en toneladas):

Concentrado Mes 1 Mes 2 Mes 3 Cu 1000 3000 5000 Zn 1000 500 3000 Adems, la gerencia de ASIOPSA ha determinado lo siguiente: El costo de produccin por tonelada del concentrado de cobre es de 20 USD, y el del concentrado de zinc es de 10 USD El costo de mantener una cantidad arbitraria de concentrado a la espera de ser comercializado es de 0,3 USD por tonelada en inventario para el concentrado de cobre, y de 1,5 USD por tonelada en inventario para el concentrado de zinc El costo de tener mano de obra extra con respecto al mes anterior es de 10 USD/hora El costo de trabajar menos horas con respecto al mes anterior es de 2,5 USD/hora Estos dos ltimos costos se refieren a las fluctuaciones en los niveles de produccin, ya que ASIOPSA tiene como poltica trabajar todos los meses la misma cantidad de horas. Al comienzo de los tres meses existen en inventario 50 toneladas del concentrado de cobre y 200 del concentrado de zinc. Al final de los tres meses, el inventario mnimo debe ser de 400 toneladas de concentrado de cobre y 200 toneladas de concentrado de zinc. Ambos concentrados se guardan en una planta en depsitos comunes. Cada depsito permite guardar hasta dos componentes de concentrado de cobre, y hasta tres componentes de concentrado de zinc. La envergadura de la planta permite guardar hasta 1000 depsitos. Los requerimientos de fabricacin de cada concentrado se resumen en la siguiente tabla:

21

Universidad de Santiago de Chile Departamento de Ingeniera en Minas Ayudanta de Optimizacin

Concentrado Maquinaria [hr/ton] Mano de obra [hr/ton] Cu 0,10 0,05 Zn 0,08 0,07 La capacidad de fabricacin mensual es de 400 horas de maquinaria y 300 horas de mano de obra. Adems, se sabe que el ltimo mes slo se usaron 225 horas de mano de obra para la fabricacin de ambos componentes. FORMULAR (NO RESOLVER) un modelo de programacin lineal que permita determinar el plan de produccin mensual que minimiza los costos de satisfaccin de la demanda esperada. Defina claramente variables, funcin objetivo y restricciones. SOLUCIN: Definimos primeramente las variables del problema: : Cantidad de concentrado del tipo (con o el mes (con ) : Inventario de concentrado del tipo al trmino del mes : Horas de mano de obra empleadas al mes : Aumento del empleo de mano de obra al mes : Disminucin del empleo de mano de obra al mes : Nmero de depsitos requeridos al mes ) producido en

Veamos ahora la funcin objetivo. Como el objetivo de ASIOPSAL es minimizar los costos, es posible definir dicha funcin directamente partir de los datos entregados en el enunciado: ( ) ( ( ) ( ) ) ) ( ( ) )

La funcin objetivo puede escribirse de forma ms abreviada como sigue: ( )

Ahora veamos las restricciones. Lo ms sencillo es verificar primero las limitaciones de satisfaccin, demanda e inventario de ASIOPSAL. En este caso, para cada mes, se tiene lo siguiente: Mes 1:

Mes 2:

22

Universidad de Santiago de Chile Departamento de Ingeniera en Minas Ayudanta de Optimizacin

Mes 3:

Con respecto a la maquinaria, se tiene:

Adems, para la mano de obra, se tiene que para cada mes: Mes 1:

Mes 2:

Mes 3:

Finalmente, de las limitaciones impuestas por la planta:

Naturalmente, todas las variables consideradas para este problema son no negativas. El modelo completo (simplificado) es el siguiente:

23

Universidad de Santiago de Chile Departamento de Ingeniera en Minas Ayudanta de Optimizacin

( )

, , ,

PROBLEMA #11 Al comienzo del mes 1, la financiera ARCOS dispone de 400 USD en efectivo. Al comienzo de los meses 1, 2, 3 y 4, la financiera recibir ingresos y, adems, deber realizar pagos como se indica en la siguiente tabla: Mes Ingresos (US$) Pagos (US$) 1 400 600 2 800 500 3 300 500 4 300 250 El dinero restante en cada mes, una vez realizados los pagos, puede ser invertido durante un mes a una tasa del 0,1% mensual; durante dos meses a una tasa del 052% mensual; durante tres meses a una tasa del 1,0% mensual; o durante cuatro meses a una tasa del 2,0% mensual. FORMULAR (NO RESOLVER) un modelo de programacin lineal que permita determinar una estrategia de inversin que maximiza el dinero en efectivo al comienzo del quinto ao. Defina claramente variables, funcin objetivo y restricciones. 24

Universidad de Santiago de Chile Departamento de Ingeniera en Minas Ayudanta de Optimizacin

SOLUCIN: Lo primero es definir las variables de este problema. Sea la cantidad de dinero invertido al comienzo del mes durante un perodo de meses. La funcin objetivo queda entonces definida como sigue: ( ) Las restricciones del modelo naturalmente representan la distribucin del dinero. As, stas se definen por las siguientes desigualdades:

Naturalmente, todas las variables consideradas en el modelo son no negativas. PROBLEMA #12 La Compaa FERROSUR debe decidir cuntas toneladas de acero puro X y cuntas de chatarra Y se deben utilizar en la preparacin de una aleacin para un cliente. El costo por tonelada de acero puro es de 3, y el de chatarra 6 (por las impurezas); la demanda del cliente es de por lo menos 5, y l aceptara ms si as se requiere. La disponibilidad de X es de 4 toneladas y 7 la de Y. La relacin entre chatarra y acero puro no puede exceder 7/8. La fundicin tiene 18 horas disponibles para derretir y fundir; una tonelada de acero puro requiere 3 horas, mientras que la de chatarra slo 2 horas. Se pide: a) Escribir el problema de programacin lineal b) Resolverlo grficamente SOLUCIN: Se tiene lo siguiente: a) Las variables del problema ya haban sido definidas en el enunciado: : Toneladas de acero puro : Toneladas de chatarra Como se trata de un problema de costos, se debe minimizar la funcin objetivo, que define los costos de fabricacin de cada material. Luego, dicha funcin viene dada por la siguiente expresin: ( ) Ahora veamos las restricciones. De la demanda del cliente y la disponibilidad de cada recurso, tenemos:

De la relacin entre tonelajes, tenemos: 25

Universidad de Santiago de Chile Departamento de Ingeniera en Minas Ayudanta de Optimizacin

De forma simplificada, que:

. Finalmente, de la disponibilidad horaria, se tiene

Naturalmente, ( )

. Por lo tanto, el modelo completo es el siguiente:

b) El ESF de este modelo se muestra en Figura 9:

Figura 4: ESF del problema La tabla siguiente evala el valor de las variables del PPL en cada uno de los puntos esquina del ESF: Punto Esquina Valor de x Valor de y Funcin objetivo B 1,25 0 3,75 C 0,494 0,432 4,074 D 3,789 3,316 31,263 F 6 0 18 Por lo tanto, el punto esquina B es el ptimo, porque es aquel donde la funcin objetivo alcanza su mnimo valor. Se concluye entonces que FERROSUR debe fabricar 1,25 toneladas de acero puro, a un costo mnimo de 3,75 unidades monetarias. La chatarra no es rentable de producir.

26

Universidad de Santiago de Chile Departamento de Ingeniera en Minas Ayudanta de Optimizacin

PROBLEMA #13 Un importador de whisky est planificando su negocio considerando que, en las prximas temporadas, tendr las siguientes demandas (en miles de botellas): Temporadas 1 2 3 4 Seco 10 12 14 8 Frutoso 13 15 17 19 Aejo 21 25 9 11 Tipo El whisky seco lo vende a 34 dlares por botella, el frutoso a 28,8 y el aejo a 22,5 en la primera temporada. En las siguientes se espera poder venderlos a un 5% ms caro. Cada tipo de whisky es elaborado mezclando tres materias primas, A, B y C, de las cuales se puede importar un mximo de 2000, 2500 y 1200 botellas por temporada a un costo de 35, 25 y 20 dlares, respectivamente. Estos costos, vlidos para la primera temporada, deberan aumentar un 2% en cada temporada. El whisky seco debe contener por lo menos un 60% de la materia prima A y no ms de un 20% de la materia prima C. El whisky frutoso debe contener por lo menos un 15% de la materia prima A y no ms de un 60% de la materia prima C. El whisky aejo debe contener por lo menos un 50% de la materia prima B. Cada botella de whisky fabricada en una temporada puede ser vendida en dicha temporada o almacenada a un costo unitario por temporada de 0,5 dlares para ser vendidas posteriormente. FORMULAR (NO RESOLVER) un modelo de programacin lineal que permita optimizar las actividades del importador. Defina claramente variables, funcin objetivo y restricciones del problema. SOLUCIN: Las variables a considerar para este problema son las siguientes: : Cantidad de materia prima k para fabricar whisky i en la temporada j : Cantidad de whisky tipo i vendido en la temporada j : Cantidad de whisky tipo i almacenado en la temporada j La funcin objetivo se subdivide en tres partes, y , donde representa los ingresos que obtiene el importador a partir de la venta de whisky en cada temporada, representa los costos de importacin de whisky de cada tipo, y representa los costos de almacenaje de whisky. Definimos entonces: ( ( ))( )

))(

27

Universidad de Santiago de Chile Departamento de Ingeniera en Minas Ayudanta de Optimizacin

Por lo tanto, la funcin objetivo ser: ( ) Las restricciones del problema vienen dadas por la disponibilidad de materia prima para producir cada tipo de whisky, la cantidad mxima de ventas por temporada, la proporcin de uso de las materias primas en la elaboracin de cada tipo de whisky, y la produccin, ventas y almacenaje por temporada. Luego, se tiene lo siguiente: Para la disponibilidad de materia prima: A partir de la tabla entregada en el enunciado del problema, se obtienen las restricciones de venta mxima por temporada:

Adems, considerando las proporciones de materias primas requeridas en la elaboracin de cada tipo de whisky, se obtiene:

28

Universidad de Santiago de Chile Departamento de Ingeniera en Minas Ayudanta de Optimizacin

Las restricciones anteriores se cumplen para todo

Finalmente, a partir de los datos entregados en el enunciado del problema con respecto a la produccin, ventas y almacenaje por temporada, se obtienen las siguientes expresiones:

Naturalmente, todas las variables consideradas en la formulacin de este problema son positivas o nulas.

29