EJEMPLO 1. - unizar.es

1 Programaci n Lineal para la Ingenier a T cnica 115 EJEMPLO 1. En una granja agr cola se desea criar conejos y pollos como complemento en su econom a, de forma que no se superen en conjunto las 180 horas mensuales destinadas a esta actividad. Su almac n s lo puede albergar un m ximo de 1000 kilogramos de pienso. Si se supone que un conejo necesita 20 kilogramos de pienso al mes y un pollo 10 kilogramos al mes, que las horas mensuales de cuidados requeridos por un conejo son 3 y por un pollo son 2 y que los beneficios que reportar a su venta ascienden a 500 y 300 pesetas por cabeza respectivamente, hallar el n mero de animales que deben criarse para que el beneficio sea m ximo.

2 Soluci n: Definimos las variables originales como: 1x = n mero de conejos. 2x = n mero de pollos. La funci n a maximizar, beneficio obtenido, ser : ()2121300500,xxxxf+= Las restricciones lineales del problema se formulas como: 1000102021 +xx (para la disponibilidad del pienso) 1802321 +xx (para la disponibilidad de horas) Finalmente, tenemos las restricciones de no negatividad de las variables: 0,21 xx Programaci n Lineal para la Ingenier a T cnica 116 El planteamiento del problema queda, por tanto, de la siguiente manera: max ()2121300500,xxxxf+= : 1000102021 +xx 1802321 +xx 0,21 xx El siguiente paso consistir en pasar a la forma est ndar, esto es, introducimos variables de holgura en las dos restricciones verdaderas, obteniendo, una vez realizadas las simplificaciones oportunas: max 21300500xx+ : 1002321=++Hxxx 18023421=++Hxxx 0,,,4321 HHxxxx La soluci n factible b sica inicial es: 021==xx, 1003=Hx, 1804=Hx As , obtenemos la tabla inicial del algoritmo del Simplex.

3 1x 2x Hx3 Hx4 Hx3 100 2 3 1 0 Hx4 180 3 2 0 1 500 300 0 0 Continuamos con las siguientes iteraciones: 1x 2x Hx3 Hx4 1x 50 1 1/2 1/2 0 Hx4 30 0 1/2 -3/2 1 0 50 -250 0 Programaci n Lineal para la Ingenier a T cnica 117 1x 2x Hx3 Hx4 1x 20 1 0 2 -1 2x 60 0 1 -3 2 0 0 -100 -100 Obtenemos, por tanto, la soluci n ptima cuyo valor es: 20*1=x conejos, 60*2=x pollos, 28000*=Z pesetas.

4 Este problema puede ser resuelto tambi n gr ficamente: Ahora, calculamos los v rtices y el valor que toma en ellos la funci n objetivo: A = (0,0), B = (50,0), C = (20,60), D = (0,90) f (A) = 0, f(B) = 25000, f(C) = 28000, f(D) = 27000 Por tanto, obtenemos la misma soluci n: 20 conejos y 60 pollos, con un beneficio m ximo de 28000 pesetas. 500x + 300y = 0 D C B A 3x + 2y = 180 20x + 10y = 1000 Programaci n Lineal para la Ingenier a T cnica 118 EJEMPLO 2. En una f brica de dulces navide os se preparan dos surtidos para lanzarlos al mercado. El primero se vende a 450 pesetas y contiene 150 gramos de polvorones, 100 gramos de mantecados y 80 gramos de roscos de vino.

5 El segundo surtido se vende a 560 pesetas y contiene 200 gramos de polvorones, 100 gramos de mantecados y 100 gramos de roscos de vino. Se dispone de un total de 200 kilogramos de polvorones, 130 kilogramos de mantecados y 104 kilogramos de roscos de vino. La empresa de embalajes s lo le puede suministrar 1200 cajas. Cu ntos surtidos de cada tipo convendr a fabricar para que el beneficio sea m ximo?. Soluci n: Definimos las variables originales como: 1x = n mero de surtidos del tipo 1. 2x = n mero de surtidos del tipo 2. La funci n a maximizar, beneficio obtenido, ser : ()2121560450,xxxxf+= Las restricciones lineales del problema se formulan como: 20000020015021 +xx (para la disponibilidad de los polvorones) 13000010010021 +xx (para la disponibilidad de los mantecados) 1040001008021 +xx (para la disponibilidad de los roscos) 120021 +xx (para la disponibilidad de las cajas) Finalmente, por su definici n, tenemos las restricciones de no negatividad de las variables: 0,21 xx Programaci n Lineal para la Ingenier a T cnica 119 El planteamiento del problema queda, por tanto, de la siguiente manera.

6 Max ()2121560450,xxxxf+= : 20000020015021 +xx 13000010010021 +xx 1040001008021 +xx 120021 +xx 0,21 xx Observamos que la restricci n de la disponibilidad de cajas implica la restricci n de la disponibilidad de los mantecados, por lo que esta ltima puede ser eliminada del problema. Teniendo en cuenta esta circunstancia, y simplificando en el resto de las restricciones, obtenemos la forma est ndar: max 21560450xx+ : 2000223321=++Hxxx 104054421=++Hxxx 1200521=++Hxxx 0,,,,54321 HHHxxxxx La soluci n factible b sica inicial es: 021==xx, 20003=Hx, 10404=Hx, 12005=Hx As , obtenemos la tabla inicial del algoritmo del Simplex.

7 1x 2x Hx3 Hx4 Hx5 Hx3 2000 3/2 2 1 0 0 Hx4 1040 4/5 1 0 1 0 Hx5 1200 1 1 0 0 1 450 560 0 0 0 Programaci n Lineal para la Ingenier a T cnica 120 Continuamos con las siguientes iteraciones: 1x 2x Hx3 Hx4 Hx5 2x 1000 3/4 1 1/2 0 0 Hx4 40 1/20 0 -1/2 1 0 Hx5 200 1/4 0 -1/2 0 1 30 0 -280 0 0 1x 2x Hx3 Hx4 Hx5 2x 400 0 1 8 -15 0 1x 800 1 0 -10 20 0 Hx5 0 0 0 2 -5 1 0 0 20 -600

8 0 1x 2x Hx3 Hx4 Hx5 2x 400 0 1 0 5 -4 1x 800 1 0 0 -5 5 Hx3 0 0 0 1 -5/2 1/2 0 0 0 -550 -10 Obtenemos, por tanto, la soluci n ptima cuyo valor es: 800*1=x surtidos tipo 1, 400*2=x surtidos tipo 2, 584000*=Zpesetas. Notamos que al igual que ocurr a para el EJEMPLO 1, este problema puede ser resuelto tambi n gr ficamente, donde idenficamos las variables por comodidad como x e y (n mero de surtidos del tipo 1 y del tipo 2 respectivamente).

9 El m todo de resoluci n gr fica quedar de la siguiente manera: Programaci n Lineal para la Ingenier a T cnica 121 Ahora, calculamos los v rtices y el valor que toma en ellos la funci n objetivo. Notamos que el punto de corte de las tres rectas de las restriciones tomadas dos a dos, es el mismo punto C: A = (0,0), B = (1200,0), C = (800,400), D = (0,1000) f (A) = 0, f(B) = 540000, f(C) = 584000, f(D) = 560000 Por tanto, obtenemos la misma soluci n: 800 surtidos del tipo 1 y 400 del tipo 2, con un beneficio m ximo de 584000 pesetas. EJEMPLO 3. Cierto fabricante produce sillas y mesas para las que requiere la utilizaci n de dos secciones de producci n: la secci n de montaje y la secci n de pintura.

10 La producci n de una silla requiere 1 hora de trabajo en la secci n de montaje y de 2 horas en la de pintura. Por su parte, la fabricaci n de una mesa precisa de 3 horas en la secci n de montaje y de 1 hora en la de pintura. La secci n de montaje s lo puede estar 9 horas diarias en funcionamiento, mientras que la de pintura s lo 8 horas. El beneficio produciendo mesas es doble que el de sillas. Cu l ha de ser la producci n diaria de mesas y sillas para que el beneficio sea m ximo?. 150x + 200y = 200000 450x + 560y = 0 D CB A x + y = 1200 80x + 100y = 104000 Programaci n Lineal para la Ingenier a T cnica 122 Soluci n: Definimos las variables originales como: 1x = n mero de sillas.