• Author / Uploaded
• tratatrata12

Citation preview

I. SISTEMAS DE ECUACIONES LINEALES ¿PARA QUE? En esta sección se presentan cuatro problemas cuya solución requiere del planteamiento de un sistema de ecuaciones lineales.

Problema 1. Una compañía minera extrae mineral de dos minas, el cual contiene para la mina I el 1% de níquel y 2% de cobre, para la mina II el 2% de níquel y 5% de cobre. ¿Qué cantidad de mineral se deberá extraer de cada mina para obtener 4 toneladas de níquel y 9 toneladas de cobre? Solución: ¿Cuál es el problema? ¿Qué se busca? Queremos saber el número de toneladas de mineral que hay que extraer de cada mina, asignemos literales a esos números. Sean x el número de toneladas que se extrae de la mina I. y el número de toneladas que se extrae de la mina II. Establezcamos ahora relaciones algebraicas entre las literales. ¿Cuánto se obtiene de níquel de la mina I? 0.01x. ¿Y de la mina II? 0.02y luego: 0.01x + 0.02y = 4 Análogamente para el cobre tenemos: 0.02x + 0.05y = 9 Así, para saber cuantas toneladas hay que extraer de cada mina debemos resolver el sistema de dos ecuaciones lineales con dos incógnitas: 0.01x + 0.02y = 4 0.02x + 0.05y = 9

Problema 2. Luis y Víctor son dos amigos que invierten en acciones bursátiles, entre ellos se entabla el siguiente dialogo: Víctor- He comprado acciones de alfa, peñoles y vitro. Luis- ¿Qué cantidad tienes de cada una de ellas? 4

Víctor- ¡adivina! Luis- Dime el valor total de tus acciones en tres días diferentes y te diré cuantas tienes de cada una. Victor- El martes 21 de noviembre del 2000 a precio de cierre las acciones valían 138900, el 28 de noviembre valían 131220 y el 5 de diciembre 121280 pesos. Luis conoce la siguiente información: El 21 de noviembre el precio de alfa, peñoles y vitro era respectivamente 16.98, 9.0, 9.0; el 28 de noviembre 15.90, 8.72, 8.52 y el 5 de diciembre 14.08, 8.20, 8.76. ¿Qué cantidad de acciones tiene Víctor? Solución: ¿Cuál es el problema? El número de acciones que tiene Víctor de cada tipo. Asignemos literales, sean: A la cantidad de acciones que tiene de alfa. P la cantidad de acciones que tiene de peñoles. V la cantidad de acciones que tiene de vitro. Establezcamos relaciones algebraicas entre las literales. El martes 21 de noviembre las acciones de alfa que adquirió Víctor valían 16.98A, las de peñoles valían 9P, las de vitro valían 9V y todas juntas valían $138900 por lo tanto: 16.98 A + 9P + 9V = 138900 Análogamente para el 28 de noviembre se tiene: 15.90 A + 8.72P + 8.52V = 131220 Y el 5 de diciembre: 14.08 A + 8.20P + 8.76 V = 121280 Luis sabrá el número de acciones que tiene Víctor sí resuelve el sistema de tres ecuaciones con tres incógnitas: 16.98 A + 9P + 9V = 138900 15.90 A + 8.72P + 8.52V = 131220 14.08 A + 8.20P + 8.76 V = 121280

5

Problema 3. En una fabrica de ropa se producen tres estilos de camisas que llamaremos 1, 2, 3. Cada prenda pasa por el proceso de cortado, cosido, planchado y empaquetado. Las camisas se elaboran por lote. Para producir un lote de camisas del tipo 1 se necesitan 30 min para cortarlas, 40 min para coserlas y 50 min para plancharlas y empaquetarlas. Para el tipo 2, 50 min para cortar, 50 min para coser y 50 min para planchar y empaquetar. Para el tipo 3, 65 min para cortar, 40 min para coser y 15 min para planchar y empaquetar. ¿Cuántos lotes se pueden producir si se trabajan 8 horas en cortar, 8 horas en coser y 8 horas en planchar y empaquetar? Solución. Queremos saber cuantos lotes de cada tipo de camisa se pueden producir, asignemos literales. Sea x el número de lotes de camisas del tipo 1 que se pueden producir. Sea y el número de lotes de camisas del tipo 2 que se pueden producir. Sea z el número de lotes de camisas del tipo 3 que se pueden producir. Establezcamos relaciones algebraicas entre las variables. El número de minutos que se emplean en cortar una camisa del tipo 1 es 30x, del tipo 2 es 50y, y del tipo 3 es 65z. El número total de minutos que se emplea en cortar todas las camisas es: 30x + 50y + 65 z Y tiene que ser igual a 480 minutos que son las 8 horas que se trabajan en cortar .'. 30x + 50y + 65 z = 480 Análogamente en coser se tiene: 40x + 50y + 40 z = 480 En planchar y empaquetar tenemos: 50x + 50y +15 z = 480 Luego sí queremos resolver el problema hay que solucionar el sistema de tres ecuaciones lineales con tres incógnitas. 30x + 50y + 65 z = 480 40x + 50y + 40 z = 480 50x + 50y + 15z = 480 6

Problema 4. Tres compuestos se combinan para formar tres tipos de fertilizantes. Una unidad del fertilizante del tipo I requiere 10 kg del compuesto A, 30 kg del compuesto B y 60 kg del compuesto C. Una unidad del tipo II requiere 20 kg del A, 30 kg del B, y 50 kg del C. Una unidad del tipo III requiere 50 kg del A y 50 kg del C. Si hay disponibles 1600 kg del A, 1200 kg del B y 3200 del C. ¿Cuántas unidades de los tres tipos de fertilizantes se pueden producir si se usa todo el material químico disponible? Solución. Queremos saber cuantas unidades de cada tipo de fertilizante se pueden producir, asignemos literales. Sea x el número de unidades del fertilizante del tipo I. Sea y el número de unidades del fertilizante del tipo II. Sea z el número de unidades del fertilizante del tipo III. Establezcamos relaciones algebraicas entre las variables. La cantidad de kilogramos del compuesto A que contiene el fertilizante del tipo I es 10x, del tipo II es 20y, y del tipo III es 50z. El número total de kilogramos del compuesto A es: 10x + 20 y + 50 z Y tiene que ser igual a 1600 kg que son los kilogramos disponibles del compuesto A. .'. 10x + 20y + 50 z = 1600 Análogamente para el compuesto B se tiene 30x + 30y = 1200 Para el compuesto C se tiene 60x + 50y + 50 z = 3200 Así, para saber cuantas unidades de cada tipo de fertilizante se pueden producir , hay que resolver el sistema de tres ecuaciones lineales con tres incógnitas. 10x + 20 y + 50 z = 1600 30x + 30y = 1200 60x + 50y + 50 z = 3200 Al terminar la sección II el lector estará en condiciones de resolver los sistemas de ecuaciones lineales anteriores. 7

Clase de repaso 10 -Problemas 15.053 Introducción a la optimización 8 de a bri l de 2002

1. Planificación de producción La Ebel Mining Company es propietaria de dos minas de las que se extrae un determinado tipo de mineral. Una vez triturado, éste se clasifica en tres calidades: alta, media y baja. La compañía debe suministrar diariamente a su empresa matriz 12 toneladas de mineral de alta calidad, 8 de calidad media y 24 de calidad baja. Los costes diarios de explotación son ascienden a20.000 dólares para la primera mina y 16.000 para la segunda. La producción diaria de cada una de ellas en toneladas es la siguiente:

Mina 1 Mina 2

Alta

Media

Baja

6 2

2 2

4 12

¿Cómo puede Ebel cumplir las exigencias de su empresa matriz con el mínimo coste? Formule un programa lineal. 2. La Colorado Cattle Company* Colorado Cattle Company (CCC), una empresa ganadera, puede adquirir tres clases de ingredientes alimentarios en bruto a un distribuidor al por mayor. El ganado vacuno que posee la empresa necesita en su dieta cantidades específicas de grasa, proteínas, calcio y hierro. Cada vaca debe tomar diariamente un mínimo de 10 unidades de calcio, 12 de hierro y 15 de proteínas, y un máximo de 7,5 unidades de grasa. La siguiente tabla muestra las cantidades de estas sustancias que se hallan en una libra de cada uno de los tres ingredientes. Los costes de los alimentos (por libra) son: 0,25 dólares el de calidad 1; 0,10 dólares el de calidad 2 y 0,08 el de calidad 3. La empresa desea alimentar a su ganado con el menor coste posible, teniendo en cuenta que puede alimentarse con una mezcla de los tres tipos de alimento. Ingredientes alimentarios (unidades por libra) Calcio

Calidad 1 0,7

Calidad 2 0,8

Calidad 3 0

Hierro

0,9

0,8

0,8

Proteínas

0,8

1,5

0,9

Grasa

0,5

0,6

0,4

Formule el problema y resuélvalo utilizando Excel Solver. ¿Qué ocurriría si los costes por libra fueran 0,5; 0,75 y 0,2? ¿Y si cada vaca necesitara 20 unidades de calcio?

3. Cambio de divisas Joe Sweeney es el director general de operaciones en el extranjero de Loro Inc., una empresa multinacional que realiza actividades de fabricación y ventas en los Estados Unidos, Gran Bretaña, Europa continental y la India, por lo que a menudo necesita transferir dinero para satisfacer las necesidades de efectivo. Esta mañana, las divisiones de la compañía en Gran Bretaña y los Estados Unidos necesitan efectivo, mientras que las divisiones europea e india tienen excedentes. * Problema extraído de Camm, J.D. y Evans, J.R., M a n a g em e n t Science, M odeling, a n d In te r p r e ta r o n , South-Western Publishing Co., Cincinnati, Ohio, 1996. Moneda

Símbolo

Euro Libra esterlina Dólar USA Rupia india

A nalysis,

Exceso (en millones) Necesario (en millones)

EUR GBP USD INR

2,4 2,1 5 350

Joe suele realizar operaciones cambiarias de gran volumen con una serie de bancos. Pide a su asesor que le informe de los tipos de cambio más interesantes, y éste le facilita la siguiente tabla de tipos de cambio cruzados. EUR EUR GBP USD INR

1 1,6054 0,9935 0,02282

GBP 0,6223 1 0,6188 0,01422

USD 1,006 1,6152 1 0,02297

INR 43,7831 70,2967 43,522 1

La tabla muestra en cada fila los precios de venta de las divisas. Así, por ejemplo, al cambiar (es decir, al vender) un millón de libras esterlinas se recibirán 1,6152 millones de dólares, y 0,6188 millones de libras al cambiar un millón de dólares. Observe que, si cambia un millón de libras en dólares y, a continuación, vuelve a cambiar a libras, habrá perdido una fracción del valor inicial: 1 GBP = 1,6152 USD = (1,6152) (0,6188) GBP = 0,9994858 GBP Esta pequeña pérdida de valor se debe a las comisiones que cobran los bancos por las transacciones. Joe observa que se puede cubrir el déficit de dólares cambiando 270 millones de rupias por 6,202 millones de dólares, y que también puede cambiar los 80 millones de rupias restantes junto con los 2,4 millones de euros por 2,631 millones de libras. No obstante, Joe sabe que hay otras posibilidades de transferencia de divisas que también le sirven para cubrir sus necesidades. Puede, por ejemplo, cambiar todos los euros en dólares y cambiar la mitad de las rupias en libras y la otra mitad en dólares; pero no está seguro de qué posibilidad es mejor que otra. a) Construya un modelo de programación lineal que permita a Joe hallar el método de transferencia de divisas más conveniente, teniendo en cuenta que su objetivo consiste en maximizar el valor en dólares de la posición final (es decir, hallar el valor del

disponible en efectivo si todo él se cambia a dólares). b) Resuelva este programa lineal utilizando Microsoft Excel Solver. c) Formule un programa lineal a partir de la siguiente versión abreviada del problema: Azadhi, una empresa global, opera en un número K de países de todo el mundo. El tipo de cambio de la unidad monetaria del país n° k es ck. (Suponiendo que el dólar USA es la moneda 1, y que c i = 1). La compañía necesita realizar frecuentes transferencias de dinero para hacer frente a sus necesidades de efectivo. La situación de equilibrio de Azadhi en la moneda i viene expresada en unidades Bi. Suponemos que Bi es un valor no negativo para cada i. Para realizar sus transferencias de divisas, Azadhi se halla en contacto con una serie de entidades financieras de prestigio especializadas en operaciones bancarias internacionales, que ofrecen a la compañía tipos de cambio Rj Así, por ejemplo, al cambiar una unidad de la moneda i a la moneda j se obtienen Rij unidades de esta última. Dado que la empresa tiene su sede en los Estados Unidos, su objetivo consiste en maximizar el valor en dólares de la posición final; es decir, hallar el valor del disponible en efectivo si todo él se cambia a dólares. Recuerde que el dólar es la unidad monetaria 1. Indique claramente las variables de decisión y utilice la notación sumatoria para formular su programa lineal.

Clase de repaso 1 as lem rob 0-P 15.053 Introducción a la optimización 8 de a bri l de 2002 Temas: 1. Revisión de formulación y abstracción; temas del boletín de ejercicios 1. 2. Geometría de la programación lineal (incluye el análisis de sensibilidad). 3. Forma estándar. 4. Método simplex.

1

2

Programación de horarios de empleados de correos En una oficina de correos, los horarios de los empleados se hallan programados a lo largo de n periodos de tiempo, repitiéndose en cada uno de ellos. Hay un número n de posibles turnos, cada uno de los cuales comienza con cada periodo n. Sea aij = 1 cuando los empleados del turno j trabajan durante el periodo i, di la demanda de empleados en dicho periodo y ci el coste de cada empleado durante el mismo. Por lo tanto, el coste total de un turno será la suma de los costes de los empleados durante los periodos correspondientes al mismo. Exprese en forma de programa lineal el problema consistente en minimizar el coste de la plantilla de modo que cubra la demanda para cada periodo o la supere. Por lo que respecta a las variables de decisión, puede llamar xj al número de empleados que trabajan en el turno j y fj al coste por empleado en dicho turno. Indique claramente el valor de fj con relación a los costes c.

Planificación de producción La Ebel Mining Company es propietaria de dos minas de las que se extrae un determinado tipo de mineral. Una vez triturado, éste se clasifica en tres calidades: alta, media y baja. La compañía debe suministrar diariamente a su empresa matriz 12 toneladas de mineral de alta calidad, 8 de calidad media y 24 de calidad baja. Los costes diarios de explotación son 20.000 dólares para la primera mina y 16.000 para la segunda. La producción diaria de cada una de ellas en toneladas es la siguiente:

Mina 1 Mina 2

Alta

Media

Baja

6 2

2 2

4 12

a) ¿Cómo puede Ebel cumplir las exigencias de su empresa matriz con el mínimo coste? Formule un programa lineal. (Ya tratamos este mismo problema en la clase de repaso 1). b) Determine gráficamente un plan de producción que minimice los costes. c) ¿Qué costes máximo y mínimo de la mina 2 harían que la solución del apartado b siguiera siendo óptima, suponiendo que el resto de los datos permanecieran iguales? d) Supongamos que la empresa matriz necesita una cantidad 12 + A de toneladas de

mineral de alta calidad. ¿Cómo afectará este incremento al coste global, expresado como una función lineal de A? ¿Qué valor máximo puede alcanzar A sin que la respuesta deje de ser válida? e) Resuelva el problema utilizando Excel Solver. (Trabajo en casa). 3 BHM n° 3, pág. 84 (con algunas modificaciones) Reduzca el siguiente sistema de ecuaciones a forma canónica, indicando las variables adicionales y de beneficio: -2X 1 3X i 5Xi Xi 2X1 -3xi 3x1 Xi >=

+ + +

+ +

■

x2 4X2 9x2 x2 x2 X2 2X2

= =

>= >= < =

< =

4 2 8 0 - i -2 10

0

4 BHM n° 5, pág. 84 El camarero del pub local le pide que le ayude a encontrar la combinación de cócteles que maximice sus beneficios. Dispone de las siguientes bebidas: 1 cuarto (32 onzas) de Old Cambridge (whisky de calidad - coste = 8 dólares/cuarto) 1 cuarto de Joy Juice (también whisky de calidad - coste = 10 dólares/cuarto) 1 cuarto de vermut Ma's Wicked (10 dólares/cuarto) 2 cuartos de ginebra Gil-boy's Gin (6 dólares/cuarto) Al ser nuevo en la profesión, únicamente conoce estos cuatro cócteles: Cóctel

Ingredientes

Precio

Whisky sour Manhattan

2 oz. de whisky 2 oz. de whisky 1 oz. de vermut

1$ 2$

Martini

2 oz. de ginebra 1 oz. de vermut

2$

Especial

2 oz. de ginebra 2 oz. de whisky

3$

Aplique el método simplex a la maximización de los beneficios del pub.

Clase de repaso 10 -Problemas 15.053 Introducción a la optimización 10 de abri l de 2002

1. BHM n° 14, pág. 136 (incluye algunas modificaciones) Classic Stone Cutter Company es una empresa que fabrica cuatro tipos distintos de esculturas en piedra: figuras, estatuillas, formas libres y estatuas. La siguiente tabla muestra el número de horas de trabajo necesarias para el corte y cincelado de la piedra y el pulido del producto final de cada uno de estos tipos. Tipo de producto

Corte Cincelado Pulido Aportación/unidad

Figuras 30 20 0 280 $

Estatuillas 5 8 20 40 $

Formas libres 45 60 0 500 $

Estatuas 60 30 120 510 $

En la actualidad, la capacidad de producción de la fuerza de trabajo permite asignar semanalmente 300 horas a trabajos de corte, 180 al cincelado y otras 300 al pulido. La fórmula y la solución vienen expresadas del siguiente modo: TABLA INICIAL x1

x2

x3

x4

x5

x6

x7

Valor

-z

280

40

500

510

0

0

0

0

Corte Cincelado Pulido

30 20 0

5 8 20

45 60 0

60 30 120

1 0 0

0 1 0

0 0 1

300 180 300

x1

x2

x3

x4

x5

x6

x7

Valor

0 1 0 0

-30

-70 7.5 360 -3

0 0 0 1

-5

11/10 76 -7/15

-0.1 -8 1/15

0 0 1 0

-2700 6 60 2

TABLA FINAL -z

-6

0.2 12 -0.1

a) ¿Es única esta solución? ¿Por qué? b) Determine un rango de la capacidad de corte para el que la solución existente siga siendo óptima. c) La producción de bustos presenta las siguientes características: Corte 15 horas Cincelado 10 horas Pulido 20 horas Aportación/unidad 240 dólares ¿Debe la empresa mantener su actual gama de productos, o le convendría ampliarla a los bustos? d) La empresa puede adquirir de un proveedor externo 5 horas de capacidad de corte y otras cinco de capacidad de cincelado por un coste total de 75 dólares. ¿Le conviene realizar esta

adquisición? e) ¿En cuánto debería incrementarse la aportación de las formas libres para que su producción resultara rentable? f) Indique un rango de la aportación de las figuras en el que la solución existente siga siendo óptima. ¿Qué actividades entran en la base dentro de las cotas de dicho rango? g) Indique un rango de la aportación de las estatuillas en el que la solución existente siga siendo óptima. ¿Qué actividades entran en la base dentro de las cotas de dicho rango?

Clase de repaso 5 - Revisión 1erperiodo Reflexiones sobre los temas tratados hasta ahora (con la ayuda de BHM) ... Esta clase no pretende abarcar toda la m ateria. 8 de marzo de 2002 Primer consejo: CONTESTE A LO QUE SE LE PREGUNTA Segundo consejo: PROCURE NO DEJAR NINGUNA PREGUNTA EN BLANCO, ESCRIBA ALGO. Si no lo hace, no podremos a y u d a rle. Tercer consejo: asegúrese de entender la materia práctica del primer periodo Formulaciones • Un programa lineal consta de tres componentes: variables de decisión, función objetivo y restricciones. • Un sistema que suele funcionar (aunque no siempre) a la hora de saber cuántas variables de decisión son necesarias es fijarse en el objetivo y examinar los datos de coste / beneficio de los que se dispone. Cada dato de coste / beneficio debería llevar asociada una variable. • Tenga presente la no negatividad. • No haga el problema más complicado de lo que en realidad es (aunque no resulte fácil...). Grafos en dos dimensiones y obtención de la solución óptima • En primer lugar, represente las restricciones y determine la región factible. • Las soluciones óptimas sólo pueden estar en puntos extremos. • A continuación, represente el objetivo y ajústelo superior o inferiormente, dependiendo de si se trata de un problema de maximización o de minimización, para saber en qué punto extremo se encuentra la solución óptima. • A la hora de determinar los rangos en los coeficientes de la función objetivo, la pendiente de ésta deberá hallarse entre las pendientes de las dos restricciones obligatorias. Forma canónica y forma estándar • La función canónica exige las siguientes condiciones: 1. Todas las variables de decisión se hallan sujetas a la restricción de ser no negativas. 2. Todas las restricciones se expresan como igualdades, con excepción de la no negatividad de las variables de decisión. 3. Todos los coeficientes del lado derecho son no negativos. 4. Hay una variable de decisión aislada en cada restricción con un coeficiente +1. La variable aislada en una restricción dada no aparece en ninguna otra restricción, apareciendo con coeficiente cero en la función objetivo. • Los programas lineales en forma estándar cumplen las tres condiciones anteriores. • Un sistema de ecuaciones puede tener forma canónica, pero un PL en forma canónica debe tener además una función objetivo. (Véase el primer punto del apartado Formulaciones) • La solución factible básica de un PL en forma canónica se puede ver directamente en la tabla / fórmula.

Algoritmo simplex • Principio de optimalidad - Supongamos que, en un problema de maximización, todas las variables no básicas tienen un coeficiente no positivo en la función objetivo de una forma canónica. En tal caso, la solución factible básica proporcionada por esa forma canónica maximizará la función objetivo en toda la región factible. • Principio de no acotamiento - Supongamos que, en un problema de maximización, algunas variables no básicas tienen un coeficiente positivo en la función objetivo de una forma canónica. Si esa variable tiene en todas las restricciones coeficientes negativos o iguales a cero, la función objetivo será no acotada superiormente en la región factible. • Ratio y criterio de pivotaje - Al mejorar una forma canónica dada mediante la introducción de la variable xs en la base, aplique el pivotaje a una variable que proporcione la ratio mínima del coeficiente del lado derecho al coeficiente xs correspondiente. Calcule estas ratios únicamente para aquellas restricciones que tengan un coeficiente positivo para xs. • Principio de múltiples soluciones óptimas - Supongamos que el principio de optimalidad se mantiene y que una variable no básica tiene un coeficiente de función objetivo igual a cero en la forma canónica final. Dado que el valor de la función objetivo permanece fijo para los incrementos de esa variable, obtendremos una solución óptima alternativa siempre que podamos incrementar el valor de la variable por medio del pivotaje. • No factibilidad - Este principio puede referirse bien a las variables ficticias (véase más abajo), o bien al hecho de que se incumpla la no negatividad de las restricciones. Fase 1 del algoritmo simplex • La fase 1 se refiere al proceso que comienza por transformar un PL a forma canónica mediante la introducción de variables adicionales, ficticias o de superávit, así como mediante la sustitución de variantes libres. A continuación, se añade un objetivo que representa la suma de las variables ficticias. Este es el objetivo de la fase 1, orientado a maximizar la parte negativa de la suma, que aparece representada por w. • Si la solución al programa de la fase 1 (sin tener en cuenta el objetivo original) da como resultado w 0, quiere decir que el problema original es no factible. En cambio, si w = 0, se ha determinado una forma canónica para iniciar el programa original. • Para más información, consulte las páginas. 57-61 en BHM. Análisis de sensibilidad • El precio sombra asociado a una restricción es el incremento del valor objetivo óptimo de la función objetivo por incremento de unidad en el valor del lado derecho, siempre que los demás datos permanezcan invariables. • El coste reducido asociado a una restricción de no negatividad para cada variable es el precio sombra de esa restricción. • El precio sombra de las restricciones no obligatorias es igual a cero. • Los precios sombra son válidos en un intervalo, que viene dado por el informe de sensibilidad de Excel. • El coste reducido correspondiente a una variable es su coeficiente de coste en la tabla final.

•

Si xs es la variable adicional para una restricción, su coste reducido será el valor negativo del precio sombra correspondiente a esa restricción.

Pricing Out y multiplicadores simplex • El pricing out permite determinar costes reducidos. • Si la columna j de la tabla inicial es una combinación lineal de las demás columnas, coincidirá con la combinación lineal de las demás columnas en la tabla final. Este principio permite determinar los costes reducidos y los rangos de los precios sombra.

Clase de repaso 10 - Problemas 15.053 Introducción a la optimización 15 de abri l de 2002

1. Considere el siguiente programa lineal P: max s.a.

3x1 + 4x2 + x3 + 5x4 x 1 + 2x2 + x3 + 2x4