05 Ejemplos

Universidad Nacional Experimental PolitcnicaAntonio Jos de Sucre

Vicerectorado Barquisimeto.Direccin de Investigacin y Postgrado

Ejercicios. Mtodos de Optimizacin (II-51053).Prof: Victor Bernal

1. Pedro Prez fabrica cable elctrico de alta calidad usando dos tipos de aleaciones metlicas, A y B. Laaleacin A contiene un 80% de cobre y un 20% de aluminio, mientras que la B incluye un 68% decobre y un 32% de aluminio. La aleacin A tiene un precio de 80 euros por tonelada, y la B, 60 eurospor tonelada. Cules son las cantidades que Pedro Prez debe usar de cada aleacin para producir unatonelada de cable que contenga a lo mas un 25% de aluminio y cuyo costo de produccin sea el menorposible?

Solucin: Las variables de decisin son las cantidades x1, x2 de las aleaciones A y B, respectivamente.La funcin objetivo es el costo 80x1 + 60x2. Las restricciones son x1 + x2 = 1 pues se elabora unatonelada y 0.2x1+0.32x2 0.25 por el mximo porcentaje de aluminio que debe contener. El cdigopara el programa LINGO es entonces:

!Funcion objetivo ;

MIN = 80*x1+60*x2;

! Restricciones ;

x1+x2=1; !Debe ser una tonelada;

0.2*x1 + 0.32*x2 < 0.25; !Porcentaje maximo de aluminio;

La solucin proporcionada es:

Objective value: 71.66667

Variable Value Reduced Cost

X1 0.5833333 0.000000

X2 0.4166667 0.000000

PROF. VICTOR BERNAL I2013 Ejercicios. Pg. 1 de 14

2. Tres empleados deben realizar seis tareas distintas. El empleado i puede hacer ai j partes de la tarea jen una hora y se le paga ci j por hora. El nmero total de horas de trabajo para el empleado i es b1i yel nmero de partes que requiere la tarea j es b2 j . Se desea determinar el plan de trabajo que da lugara un costo mnimo

C =3

i=1

6j=1

ci j xi j

donde xi j representa el nmero de horas empleadas en la tarea j por el empleado i . Plantear esteproblema como uno de programacin lineal.

Solucin: La funcin objetivo est ya definida en el problema junto con las variables de decisin xi j .

Ahora se plantean las restricciones, para cada empleado i , i = 1,2,3 y cada trabajo j , j = 1,2,3,4,5,6:

6j=1

xi j = b1i , i = 1,2,3.

3i=1

ai j xi j = b2 j , j = 1,2,3,4,5,6.

La primera por las horas disponibles y la segunda por la cantidad de partes que requiere cada tarea.

3. Una compaa de fabricacin de muebles necesita determinar cuntas mesas, sillas, pupitres y biblio-tecas debe hacer para optimizar el uso de sus recursos. Estos productos utilizan dos tipos diferentes depaneles, y la compaa dispone de 1500 tableros de un tipo y 1000 de otro tipo. Por otro lado cuentacon 800 horas de mano de obra. Las predicciones de venta as como los pedidos atrasados exigen lafabricacin de al menos 40 mesas, 130 sillas, 30 pupitres y como mximo 10 bibliotecas. Cada mesa,silla, pupitre y biblioteca necesita 5, 1, 9, y 12 tableros, respectivamente, del primer tipo de panel y 2,3, 4, y 1 tableros del segundo. Una mesa requiere 3 horas de trabajo; una silla, 2; un pupitre, 5; y unabiblioteca 10. La compaa obtiene un beneficio de 12 dlares en cada mesa, 5 dlares en cada silla,15 dlares en un pupitre, y 10 dlares en una biblioteca. Plantear el modelo de programacin linealpara maximizar los beneficios totales. Modificar el problema si ahora deben fabricarse cuatro sillaspor cada mesa.

Solucin: Las variables de decisin son las cantidades de mesas, x1, de sillas, x2, de pupitres, x3 y debibliotecas, x4. La funcin objetivo, que expresa el total de beneficios, es,

z = 12x1+ 5x2+ 15x3+ 10x4

Las restricciones se deben a la disponibilidad de tableros y horas de trabajo, junto con los pedidosactuales y los atrasados.

5x1+ x2+ 9x3+ 12x4 15002x1+ 3x2+ 4x3+ x4 1000

3x1+ 2x2+ 5x3+ 10x4 800x1 40, x2 130, x3 30, x4 10.

La formulacin en el programa LINGO es,


! Problema 3

Fabricacion de mesas, silla, pupitres y bibliotecas

x1: mesas, x2: sillas, x3: pupitres, x4: bibliotecas;

! Funcion objetivo ;

MAX=12*x1+5*x2+15*x3+10*x4;

! Restricciones ;

5*x1 +x2 +9*x3 +12*x4 30; x4 < 10; ! Ventas y pedidos pendientes;

La solucin dada por el programa LINGO es,

Objective value: 2660.000

Variable Value Reduced Cost

X1 130.0000 0.000000

X2 130.0000 0.000000

X3 30.00000 0.000000

X4 0.000000 30.00000

4. Una empresa que produce un cierto producto P consta de dos plantas. Cada planta produce 90 tone-ladas de P al mes, y el producto se distribuye en tres mercados distintos. La tabla muestra los preciosunitarios del envo de una tonelada de P desde cada planta a cada mercado. La empresa desea enviar elmismo nmero de toneladas a cada mercado y minimizar el costo total. Formular el problema comouno de programacin lineal.

Plantas Mercado1 Mercado2 Mercado3

Planta1 1 3 5

Planta2 2 5 4

Solucin: El problema anterior sigue el modelo del problema de transporte, la formulacin en LIN-GO se puede tomar como gua para formular otros similares.

MODEL: !Problema 4;

! Definicion de las variables;

SETS:

PLANTAS/P1,P2/:CAP;

MERCADOS/M1,M2,M3/:DEM;

RUTAS(PLANTAS,MERCADOS):COSTO,CARGA;

ENDSETS

! Funcion objetivo ;

MIN=@SUM(RUTAS:COSTO*CARGA);

! Restricciones por demandas ;


@FOR(MERCADOS(J):

@SUM(PLANTAS(I):CARGA(I,J))>DEM(J));

! Restricciones por capacidades ;

@FOR(PLANTAS(I):

@SUM(MERCADOS(J):CARGA(I,J))

predecirse con garantas y se consideran conocidos. La energa mnima que el productor puede ge-nerar en cada hora es cero y el mximo es una cantidad fija. La diferencia de produccin en horasconsecutivas no puede exceder un determinado lmite. El costo de generacin de energa es lineal.Formular este problema como uno de programacin lineal.

Solucin: Si se tiene un horizonte de n horas para la produccin. Las variables de decisin son lascantidades ei , i = 1, . . . ,n producidas en cada hora, y el costo unitario ci en cada hora, produce uncosto total ci ei para cada hora, por la linealidad. Igualmente, M es el mximo de energa permitido.Las restricciones se deben al mximo permitido y la mxima diferencia L entre horas consecutivas.

La funcin objetivo esni=1

ci ei y las restricciones,

0 ei M , i = 1, . . . ,nL ei+1 ei L, i = 1, . . .n 1

6. Suponga que hay m refineras y que la refinera i tiene capacidad para proporcionar ai litros de gaso-lina. Hay n ciudades que requieren de tal combustible y la demanda en la ciudad j es de b j litros. Sifi j la fraccin de litro de combustible que se dedica al transporte cuando 1 litro de gasolina va desdela refinera i a la ciudad j en un transporte. Encontrar una forma factible de despachar el combustiblede tal forma que la cantidad consumida por los transportes sea la menor posible.

Solucin: Las variables de decisin xi j son la cantidad de litros enviados desde la refinera i hasta laciudad j , i = 1, . . . ,m, j = 1, . . .n. Las restricciones se deben a las capacidades ai de las refineras y lasdemandas di de las ciudades. El planteamiento puede ser entonces,

mn z =mi=1

nj=1

xi j fi j

Sujeto a:mj=1

xi j ai , i = 1, . . . ,mni=1

xi j b j , j = 1, . . . ,n

7. Dos pozos petroleros, A y B , producen, cada uno, 10000 barriles diarios que se quieren vender en sutotalidad. Dos compaas, C y D ofrecen comprar, de acuerdo con la tabla siguiente:

Oferente Pozo Mximo deseado Bono por barril

C A 10000 $ 0.10

B 10000 $ 0.09

D A 10000 $ 0.20

B 10000 $ 0.15

El bono es una cantidad que la compaa accede a pagar sobre el precio base mnimo anunciado,por barril. Las regulaciones gubernamentales prohben vender ms de 15000 barriles diarios de estos


dos pozos a un slo comprador. Se requiere determinar la cantidad de crudo que se debe vender acada una de las compaas C y D de cada uno de los pozos, A y B de tal manera que la cantidadobtenida por los bonos sea mxima sujeto a las restricciones dadas. Formular este problema comouno de programacin lineal.

Solucin: Las variables de decisin son las cantidades vendidas a cada compaa, de cada pozo. Senotan xCA, xCB , xDA, xDB , las restricciones se deben a la capacidad de los pozos y las restriccionesgubernamentales, el planteamiento del problema es,

max z = 0.10xCA+ 0.09xCB + 0.20xDA+ 0.15xDBSujeto a:

Capacidades de los pozos

xCA+ xDA 10000xCB + xDB 10000

Regulaciones gubernamentales

xCA+ xCB 15000xDA+ xDB 15000

xCA, xCB , xDA, xDB 0.La formulacin en LINGO es,

! Problema 7;

!Venta de petroleo;

!Funcin objetivo;

MAX = 0.10*xCA+0.09*xCB+0.20*xDA+0.15*xDB ;

!Restricciones;

!Capacidades de los pozos;

xCA + xDA

8. Se desea obtener la mezcla de petrleo a partir de crudos de distinta procedencia, cada uno de loscuales tienen distintas caractersticas. En la tabla adjunta se detallan los distintos crudos - cuatro entotal - y sus caractersticas ms importantes: el tanto por ciento de azufre, la densidad y el precio porTm. medido en dlares.

Origen % Azufre Densidad Precio($)

1Kuwait 0.45 0.91 806

2Arabia 0.40 0.95 714

3Noruega 0.38 0.89 898

4Venezuela 0.41 0.92 783

Se exige a la mezcla que tenga unas caractersticas concretas, que se traducen en un porcentaje del0.40% de contenido de azufre y una densidad igual a 0.91. Se desea que el precio de la mezcla seamnimo.

Solucin: Las variables de decisin son las proporciones xi de los crudos que intervienen en la mezcla,de cada uno de los disponibles. La funcin objetivo es el costo de una unidad de mezcla. Las restric-ciones se refieren al porcentaje de azufre y la densidad. Su formulacin en el programa LPSOLVE esentonces,

/* Mezcla de petroleo */

/* Funcion objetivo */

min: 806 x1 + 714 x2 + 898 x3 + 783 x4 ;

/* Restricciones */

x1 + x2 + x3 + x4 = 1 ; /* Las proporciones deben sumar 1 */

0.45 x1 + 0.40 x2 + 0.38 x3 + 0.41 x4 = 0.40 ; /* Contenido de azufre */

0.91 x1 + 0.95 x2 + 0.89 x3 + 0.92 x4 = 0.91 ; /* Densidad de la mezcla */

La solucin es un mnimo de 821.33333, de acuerdo con el reporte del programa LPSOLVE.

Primal variables:

Column name Value

-----------------------------------------

x1 0

x2 0

x3 0.333333

x4 0.666667

Optimal solution 821.333333333 after 4 iter.

Excellent numeric accuracy ||*|| = 2.44249e-015

El resultado se puede interpretar como un costo mnimo unitario de $821 13 con una mezcla de13 de

crudo de Noruega y 23 de crudo de Venezuela.


9. En un centro de nutricin se desea obtener la dieta de costo mnimo con unos determinados requisitosvitamnicos, para un grupo de nios que van a asistir a campamentos de verano. El especialista estimaque la dieta debe contener entre 26 y 32 unidades de vitamina A, al menos 25 unidades de vitaminaB y 30 de C, y a lo sumo 14 de vitamina D. La tabla nos da el nmero de unidades de las distintasvitaminas por unidad de alimento consumido para seis alimentos elegidos, denominados 1, 2, 3, 4, 5y 6, as como su costo por unidad.

Vitaminas Costo por unidad

Alimentos A B C D

1 1 1 0 1 10

2 1 2 1 0 14

3 0 1 2 0 12

4 3 1 0 1 18

5 2 1 2 0 20

6 1 0 2 1 16

Se desea construir un modelo de programacin lineal para conocer la cantidad de cada alimento quese debe preparar de manera que satisfaga los requisitos propuestos con costo mnimo.

Solucin: El problema es una variacin del problema de la dieta, es por esto que lo formulamosdirectamente en el programa LPSOLVE como sigue,

/* Problema de la dieta */

/* Funcion objetivo */

min: 10x1 + 14x2 + 12x3 + 18x4 + 20x5 + 16x6 ;

/* Restricciones */

/* 26


Excellent numeric accuracy ||*|| = 0

10. Los materiales tales como papel, textiles, celofn, vidrio y papel de aluminio se fabrican en rollos olminas de gran anchura. Estos rollos, llamados primarios, se cortan luego en rollos, llamados finales,de menor anchura. Cada fabricante produce rollos primarios en ciertos anchos estndar, las anchurasde los finales son especificadas por los diferentes clientes y pueden variar ampliamente. El corte serealiza en las mquinas por cuchillas que cortan a travs de los rodillos de la misma manera como uncuchillo hace rebanadas de pan. Por ejemplo, un rollo primario de 100cm de ancho se puede cortaren dos finales de 31cm y uno de 36cm, con 2cm sobrantes. Cuando llegan pedidos muy variados, lamanera ms econmica de reducir los primarios existentes a finales casi nunca es evidente. El problemade encontrar tal manera se conoce como problema del corte (cuttingstock problem).

Por ejemplo, una industria que fabrica papel y lo distribuye en rollos debe determinar la mejor formade realizar el proceso de corte. Los rollos de papel que se producen tienen un ancho de 100cm y unlargo fijo. Los clientes demandan rollos de 30cm, 45cm y 50cm de ancho. Al cortar los rollos de 100cmse puede incurrir en prdida de material. Se tiene un pedido de 800 rollos de 30cm de ancho, 500 rollosde 45cm y 1000 rollos de 50cm.

Se desea determinar la forma de efectuar el corte de manera que se satisfaga la demanda y se minimicela prdida total de material.

Solucin: Existen 6 alternativas diferentes de corte de un rollo de 100cm de ancho que tienen sentido,en este caso, y se pueden resumir en la siguiente tabla:

Rollos de ancho

Esquema 30 45 50 Prdida

1 3 10

2 1 1 25

3 2 10

4 1 1 5

5 2 0

6 1 1 20

De esta manera, las variables de decisin xi son las cantidades de rollos cortados bajo el esquema i ,i = 1, ..6. Por lo tanto, la funcin objetivo, que mide las prdidas totales, es,

mn z = 10x1+ 25x2+ 10x3+ 5x4+ 20x6.

Las restricciones son el resultado de la demanda,

Rollos de 30: 3x1+ x2+ x6 = 800

Rollos de 45: x2+ 2x3+ x4 = 500

Rollos de 50: x4+ 2x5+ x6 = 1000


El siguiente es el cdigo para resolver el problema con LPSOLVE.

/* Funcion objetivo: minimizar las perdidas */

min: 10x1 +25x2 +10x3 +5x4 +20x6 ;

/* Restricciones por los pedidos de 30, 45 y 50 */

3x1 + x2 + x6 = 800 ;

x2 + 2x3 + x4 = 500 ;

x4 + 2x5 + x6 = 1000 ;

/* int x1, x2, x3, x4, x5 ,x6 ;*/

/* Esta restriccion opcional exige que los valores de

las variables sean enteros */

La solucin es,

Primal variables:

Column name Value

-----------------------------------------

x1 266.667

x2 0

x3 250

x4 0

x6 0

x5 500



El valor de x1 es fraccionario. Si se agrega la restriccin opcional de que las variables sean enteras seobtiene,

Column name Value

-------------------------------------------

x1 266

x2 2

x3 249

x4 0

x6 0

x5 500

Optimal solution 5200 after 4 iter, 2 nodes (gap 0.6%).


Ahora los valores son enteros y las prdidas, 5200, son menores, pero el esfuerzo computacional esmayor. En general se acepta la solucin con valores fraccionarios como una buena aproximacin a losvalores enteros ptimos.


Los problemas ms frecuentes en la industria del papel pueden implicar gran cantidad de variables.Por ejemplo, si los rollos primarios son 200cm de ancho y si los finales se ordenan en 40 longitudesdiferentes que van desde 20cm a 80cm, entonces el nmero de patrones diferentes puede superar fcil-mente los 10 o incluso 100 millones. La cantidad de tiempo y espacio requerido slo para generar estospatrones (por no hablar de la posterior solucin del problema) pueden ser imposibles de obtener.

Una ingeniosa manera de resolver esta dificultad fue descubierta por P. C. Gilmore y R. E. Gomory(1961). El truco, en definitiva, es trabajar con slo unos pocos modelos a la vez y generar nuevospatrones slo cuando sean realmente necesarios.

11. Considere una situacin recurrente en la que los empleados tienen que ser asignados a diversos turnos.El nmero de empleados que deban estar en el trabajo vara a lo largo del da en una variedad desegmentos de tiempo. Por ejemplo, una ruta de autobs requerir servicio importante durante lamadrugada y las horas pico de la tarde, mientras que no habr mucho servicio durante la hora delalmuerzo o por la noche. Existen requisitos similares para las enfermeras, los pilotos, los cajeros ensupermercados, y escenarios similares.

La dificultad de este problema es que, en general, no se puede contratar mano de obra ocasional cuandosea necesaria y por lo tanto se deben contratar empleados permanentes. As, el objetivo del problemaes utilizar el menor nmero de empleados y todava ser capaz de dotar de personal la(s) posicin(es)durante todo el da. En nuestro ejemplo numrico, supongamos que un turno normal es de 8 horas y sesupone que hay segmentos de 4 horas durante los que se han observado los requisitos de personal. Lasnecesidades de personal durante los intervalos de tiempo de 4 horas se muestran en la Tabla, usandoun reloj de 24 horas.

Tabla de requerimientos de personal (4 horas)Turno 06:0010:00 10:0014:00 14:0018:00 18:0022:00 22:0002:00 02:0006:00

Empleados 17 9 19 12 5 8

Supongamos que los turnos pueden empezar cada 4 horas, a las 6am, las 10am, y as sucesivamente.Las variables de decisin son entonces el nmero de empleados a contratar en cada uno de estos pun-tos en el tiempo. Esto significa que podemos definir las variables x06, x10, x14, x18, x22 y x02 como elnmero de empleados que comienzan su jornada a las 6am 10am, 2pm y as sucesivamente. El nmerototal de trabajadores requerido corresponde a la suma de todas estas variables. En cuanto a las restric-ciones, se debe pedir que un nmero suficiente de empleados est presente durante cada intervalo detiempo. Por ejemplo, en el intervalo de tiempo entre las 14:00 y y las 18:00 se necesitan al menos 19empleados, los que trabajan durante este intervalo de tiempo son aquellos cuyo turno comienza a las10:00 ms los que empiezan a trabajar a las 14:00, esto significa que durante este intervalo de tiempovan a trabajar x10 + x14 empleados, una cifra que debe ser por lo menos 19. Restricciones similarestienen que ser formulada para todos los seis rangos de tiempo. La formulacin se puede escribir de la


siguiente manera, pasando por alto que las variables sean enteras, por razones de simplicidad.

mn z = x06+ x10+ x14+ x18+ x22+ x02s.a. x06+ x02 17

x06+ x10 9x10+ x14 19x14+ x18 12x18+ x22 5x22+ x02 8x06, x10, x14, x18, x22, x02 0

La formulacin en LPSOLVE es como sigue:

/* Problema 11. Asignacion de empleados a horarios */

/* Funcion objetivo: Minimizar el total de empleados */

/* xij: numero de empleados que comienzan turno a las ij:00 horas */

min: x06 + x10 +x14 +x18 +x22 +x02 ;

/* Restricciones por horario de los turnos */

x06 + x02 >= 17 ;

x06 + x10 >= 9 ;

x10 + x14 >= 19 ;

x14 + x18 >= 12 ;

x18 + x22 >= 5 ;

x22 + x02 >= 8 ;

/* La no-negatividad se supone en LPSOLVE */

/* No se exige que sean valores enteros */

La solucin da un valor de 41 empleados y los turnos son,

Column name Value

------------------------------------------

x06 9

x10 12

x14 7

x18 5

x22 0

x02 8

Optimal solution 41 after 5 iter.



Hay que tener en cuenta que esta solucin tiene el nmero exacto de empleados requeridos durantetodas las franjas horarias, excepto en el rango 10:0014:00, donde slo se necesitan 9 empleados, mien-tras que estn disponibles 21 empleados. En otras palabras, hay 12 empleados ociosos de las 10am alas 2pm.

En una variacin del modelo anterior, se supone que ahora es posible iniciar los turnos cada 2 horasen vez de cada 4 horas. Del mismo modo, los requisitos de tiempo son conocidos por cada 2 horas enlugar de cada 4 horas durante todo el da. Por ejemplo, los 17 empleados que en el problema anteriorse necesitaban de 6am a 10am ahora slo se necesitan de 6am a 8am, mientras que de 8am a 10am slose requieren 11 empleados. Las necesidades de personal durante los intervalos de tiempo de 2 horas semuestran en la siguiente tabla,

Tabla de requerimientos de personal (2 horas)Turno 06:00 - 08:00 08:00 -10:00 10:00 - 12:00 12:00 - 14:00 14:00 - 16:00 16:00 - 18:00

Empleados 17 11 9 7 13 19

Turno 18:00 - 20:00 20:00 - 22:00 22:00 - 00:00 00:00 -02:00 02:00 - 04:00 04:00 -06:00

Empleados 12 8 5 3 3 8

Su formulacin en LPSOLVE es,

/* Funcion objetivo: Minimizar el total de empleados */

/* xij: numero de empleados que comienzan turno a las ij:00 horas */

min:x06 +x08 +x10 +x12 +x14 +x16 +x18 +x20 +x22 +x00 +x02 +x04 ;

/* Restricciones por horario de los turnos */

x06 +x00 +x02 +x04 >= 17 ;

x06 +x08 +x02 +x04 >= 11 ;

x06 +x08 +x10 +x04 >= 9 ;

x06 +x08 +x10 +x12 >= 7 ;

x08 +x10 +x12 +x14 >= 13 ;

x10 +x12 +x14 +x16 >= 19 ;

x12 +x14 +x16 +x18 >= 12 ;

x14 +x16 +x18 +x20 >= 8 ;

x16 +x18 +x20 +x22 >= 5 ;

x18 +x20 +x22 +x00 >= 3 ;

x20 +x22 +x00 +x02 >= 3 ;

x22 +x00 +x02 +x04 >= 8 ;






La solucin ptima es de 36 empleados y los turnos son,

Column name Value

---------------------------------------------

x06 9

x08 0

x10 7

x12 4

x14 3

x16 5

x18 0

x20 0

x22 0

x00 6

x02 2

x04 0

Optimal solution 36 after 7 iter.


Se destaca el 12% de ahorro en el nmero de empleados que deben contratarse. En general, no es deextraar que rangos ms finos proporcionen una solucin que es al menos tan buena como la que seobtiene con intervalos de tiempo de 4 horas. La razn es que la solucin anterior todava se puedeimplementar y adems es una solucin factible. Sin embargo, con las horas de inicio aumentadas segeneran posibilidades adicionales que pueden permitir, y en este caso nos permiten, encontrar unamejor solucin.


05 Ejemplos

Documents

Transcript of 05 Ejemplos