Source: http://docplayer.es/61232057-Programacion-lineal-matematica-basica-2da-parte-fce-unl-equipo-docente-claudia-zanabria-maria-cecilia-municoy-cristina-rogiano-gabriela-roldan.html
Timestamp: 2018-11-21 06:58:19+00:00

Document:
PROGRAMACIÓN LINEAL. MATEMÁTICA BÁSICA 2da PARTE FCE UNL EQUIPO DOCENTE. Claudia Zanabria. María Cecilia Municoy Cristina Rogiano Gabriela Roldán - PDF
PROGRAMACIÓN LINEAL. MATEMÁTICA BÁSICA 2da PARTE FCE UNL EQUIPO DOCENTE. Claudia Zanabria. María Cecilia Municoy Cristina Rogiano Gabriela Roldán
Download "PROGRAMACIÓN LINEAL. MATEMÁTICA BÁSICA 2da PARTE FCE UNL EQUIPO DOCENTE. Claudia Zanabria. María Cecilia Municoy Cristina Rogiano Gabriela Roldán"
Jaime Mendoza de la Fuente
1 MATEMÁTICA BÁSICA 2da PARTE UNL 2017 FCE EQUIPO DOCENTE Profesor Titular Profesores Adjuntos Jefes de Trabajos Prácticos Susana Marcipar Katz Marta Nardoni Claudia Zanabria Matilde Banchik María Cecilia Municoy Cristina Rogiano Gabriela Roldán UNIDAD 6 PROGRAMACIÓN LINEAL Material Elaborado por: Cristina Rogiano Gabriela Roldán Claudia Zanabria
2 Zanabria, Claudia Programación lineal : problemas de optimización / Claudia Zanabria ; Gabriela Roldán ; Cristina Rogiano. - 1a ed. - Santa Fe : Universidad Nacional del Litoral, E-Book. ISBN Álgebra Lineal. 2. Ecuaciones. I. Roldán, Gabriela II. Rogiano, Cristina III. Título CDD Fecha de catalogación: 10/03/2015 1
3 UNIDAD Nro.6: Programación lineal En esta unidad se trabajará con problemas que refieren a la optimización de funciones de dos variables, máximización o minimización, que cumplen un conjunto de condiciones. El abordaje de estos problemas requiere de un proceso formado por distintas etapas. En el siguiente gráfico se visualizan los conceptos fundamentales de esta unidad que surgirán a medida que se transite por cada una de las etapas. 2
4 Programación Lineal 1. Introducción La Programación Lineal es una de las principales ramas de la Investigación Operativa relativamente reciente (siglo XX) que consiste en una serie de métodos y procedimientos que permiten resolver problemas de optimización en el ámbito, sobre todo, de las Ciencias Sociales, la Administración y la Investigación Operativa. Se trata de un área reciente de las matemáticas aplicadas, desarrollada a fines de los años cuarenta para resolver un problema del gobierno de Estados Unidos. Desde entonces, la Programación lineal se ha aplicó en una cantidad sorprendente de problemas en muchos campos. La Programación Lineal es un conjunto de técnicas racionales de análisis y de resolución de problemas que tiene por objeto ayudar a tomar decisiones sobre asuntos en los que interviene un gran número de variables y se aplica a la resolución de problemas del comercio y de la industria para tomar decisiones que maximizan o minimizan una cantidad determinada. Por ejemplo: la gerencia de una planta podría estar interesada en establecer una forma más económica de transportar la producción desde la fábrica hasta los mercados; un hospital, en diseñar una dieta que satisfaga ciertos requisitos nutricionales, a mínimo costo; o, un fabricante, en mezclar ingredientes según ciertas especificaciones, de modo que obtenga el mayor beneficio. También para Minimizar: Los gastos del presupuesto familiar Los costos de una dieta para el ganado vacuno La cantidad de kilómetros a recorrer para distribuir productos a distintas localidades O bien para Maximizar: El rendimiento en una operación comercial Los niveles de producción El nombre de Programación Lineal procede del término militar Programar, que significa realizar planes o propuestas de tiempo para el entrenamiento, la logística o el despliegue de las unidades de combate. Aunque parece ser que la Programación Lineal fue utilizada por G. Monge en 1776, se considera a L. V. Kantoróvich uno de sus creadores que la presentó en su libro Métodos matemáticos para la organización y la producción (1939) y la desarrolló en su trabajo Sobre la transferencia de masas (1942). Kantoróvich recibió el premio Nobel de economía en 1975 por sus aportes al problema de la asignación óptima de recursos humanos. La investigación de operaciones en general y la programación lineal en particular recibieron un gran impulso gracias a los ordenadores. Uno de los momentos más importantes fue la aparición del método del simplex. Este método, desarrollado por G. B. Dantzig en 1947, consiste en la utilización de un algoritmo para optimizar el valor de la función objetivo teniendo en cuenta las restricciones planteadas; el procedimiento es iterativo y mejora los resultados de la función objetivo en cada etapa hasta alcanzar la solución buscada. 3
5 2. Formulación del modelo matemático de un Problema de Programación Lineal Presentamos dos problemas: uno de Maximización de una ganancia y otro de Minimización de un costo. Ejemplo 1: Una fábrica de automóviles de colección construye dos tipos de autos, pequeños y grandes. La fabricación consta de dos procesos: Proceso 1 y Proceso 2. Los requerimientos de trabajo en los distintos procesos para cada tipo de auto, así como las horas necesarias y disponibles y las ganancias por unidad, se dan en la siguiente tabla: Tiempo (en horas) Auto pequeño Auto grande Horas disponibles Proceso 1 (en hs/ unidad) Proceso 2 (en hs/ unidad) Ganancia (en $ / unidad) En base a estos datos queremos saber cuántos autos de cada tipo se deben fabricar para maximizar la ganancia. Construcción del Modelo Definimos las variables x e y llamadas Variables de Decisión x: número de autos pequeños que pueden producirse y: número de autos grandes que pueden producirse Las necesidades de fabricación pueden sintetizarse así: Se requieren 3. x hs en el proceso 1 para fabricar x unidades de autos chicos y 5. y hs en el proceso 1 para fabricar y unidades de autos grandes. En consecuencia, los datos que corresponden a las necesidades de horas que se ocuparán durante el proceso 1 pueden expresarse en forma algebraica mediante la desigualdad: 3x + 5y 150 De manera similar, la información brindada por los datos que corresponden al proceso 2 podemos representarla mediante la desigualdad: 3x + 3y 120 Estas dos desigualdades se denominan Restricciones Estructurales del problema. Pero además, existen otras dos restricciones, llamadas Restricciones de no negatividad que surgen como consecuencia de que la empresa no produce cantidades negativas de sus artículos. Y son x 0, y 0 La función ganancia, que llamaremos G, está dada por la función G(x, y) = 50 x + 65 y Y nuestro objetivo es optimizarla, es decir, Maximizar G (x, y) = 50 x + 65 y sujeto a las restricciones formuladas anteriormente. 4
6 Reuniendo toda esta información, expresamos el modelo que responde al problema enunciado y que llamaremos Problema estándar de Programación Lineal de Máximo con única Solución. Luego, el modelo es: Maximizar: G (x, y) = 50 x + 65y (función objetivo) Sujeto a: (describe el conjunto de restricciones del problema) 3x + 5y 150 (restricción estructural 1) 3x + 3y 120 (restricción estructural 2) x 0, y 0 (restricciones de no negatividad) 3. Resolución Gráfica de los problemas de programación lineal. Resolver un problema de programación lineal significa encontrar los valores de las variables que verifican todas las restricciones del problema y que optimice la función objetivo. Dichos valores serán hallados a partir de la construcción de un gráfico. De esta manera llamaremos: Conjunto Restricción o Conjunto de Soluciones Factibles o Región Factible al conjunto de puntos del plano que satisface las restricciones de un problema. Solución Factible a todo punto que pertenece al Conjunto Restricción Para construir la región factible es necesario conocer los siguientes conceptos: 3. 1 Conceptos Previos Relación entre los conjuntos convexos y la programación lineal La región factible de un problema de programación lineal es un conjunto formado por puntos del plano que verifican simultáneamente cada restricción del problema. En general cada restricción es una inecuación lineal que responden a una de estas formas generales: ax + by > c ax + by c ax + by c ax + by < c donde a, b, c R y a y b no son ambos iguales a cero Qué representan estas inecuaciones en el plano cartesiano? Grafiquemos el conjunto de puntos del plano que satisfacen la desigualdad 3x + 2y 6. Un método práctico para graficar el conjunto de puntos que satisfacen la desigualdad es el siguiente: -Elegimos un punto, llamado punto de prueba, que puede ser el (0, 0). -Luego, verificamos si el punto cumple la desigualdad sustituyendo las coordenadas. 5
7 Como = 0 < 6 entonces el punto (0, 0) pertenece al conjunto formado por los puntos que cumplen la desigualdad 3x + 2y < 6 y entonces los puntos del plano que satisfacen la desigualdad 3x + 2y 6 son los que pertenecen a la recta 3x + 2y = 6 y los que están por sobre ella. Elegimos el (0, 0) porque las operaciones resultan más sencillas. No obstante, cualquier otro punto puede servirnos como punto de prueba. Luego, la gráfica de 3x + 2y 6 es la siguiente Gráfico 1 La recta 3x + 2y = 6 recibe el nombre de Recta Frontera y divide al plano en dos regiones denominadas semiplanos: El conjunto M ={(x, y) / 3x + 2y= 6} representa a los puntos que pertenecen a la recta El conjunto A = {(x, y) / 3x + 2y > 6} es el semiplano superior y el conjunto B ={(x, y) / 3x + 2y < 6} es el semiplano inferior. Todo punto (x, y) pertenece a uno de los tres conjuntos o M, o A o B. Luego, R 2 = M A B En el Gráfico 2 hemos dibujado los tres conjuntos Gráfico 2 Semiplano superior 3x +2y > 6 Semiplano inferior 3x +2y <6 3x + 2y = 6 En el Gráfico 3 hemos representado el conjunto A = {(x, y) / 3x + 2y > 6}. La recta 3x + 2y = 6 se dibuja con una línea discontinua porque los puntos del conjunto A no satisfacen la igualdad 3x + 2y = 6. 6
8 Gráfico Semiplanos abiertos y cerrados El conjunto de puntos que satisface desigualdades del tipo o se denomina semiplano cerrado. El conjunto de puntos que satisfacen desigualdades del tipo < o < se llama semiplano abierto Conjunto solución de dos o más desigualdades lineales Analizaremos cómo resolver sistemas de inecuaciones lineales con dos variables. Como ya vimos, el conjunto solución de una inecuación con dos variables es un semiplano. Intuitivamente podemos decir que el conjunto solución de un sistema de inecuaciones es la intersección de los semiplanos de cada una de las inecuaciones que forman el sistema. Hacemos notar que algunas veces el conjunto solución de un sistema de inecuaciones puede ser vacío Resolución gráfica de un sistema de inecuaciones En esta sección mostramos cómo resolver un sistema de inecuaciones lineales en forma gráfica. Te mostramos algunos ejemplos Ejemplo 2: Representemos gráficamente el conjunto solución del sistema: 3x 2y 6 x y 1 2x 3y 12 Primero trazamos las rectas fronteras de cada uno de los semiplanos: R 1: 3x + 2y = 6 R 2: x + y = 1 R 3: 2x + 3y = 12 El punto (0, 0) satisface las desigualdades x + y 1 y 2x + 3y 12 pero no la desigualdad 3 x + 2y 6. Esto implica que: El semiplano cerrado 2x + 3y 12 está formado por los puntos que están debajo y en la recta 2x + 3y = 6. El semiplano cerrado x + y 1 está formado por los puntos que están debajo y en la recta x + y = 1. El semiplano abierto 3x + 2y > 6 está formado por los puntos que se encuentran por encima de la recta 3x + 2y = 6. Luego, el conjunto solución del sistema es la intersección de los tres semiplanos, representado en el siguiente Gráfico: 7
9 Gráfico 4 Ejemplos 3: Grafiquemos el conjunto solución del sistema Las rectas fronteras son y = x + 2 e y = 4 x y x 2 x y 4 El punto (0, 0) satisface las inecuaciones y x+ 2 y x + y 4, por lo tanto los puntos del plano que pertenecen a estos semiplanos se encuentran por debajo y en la rectas y = x + 2 e y = 4 x Gráfico 5 Ejemplo 4: Ahora mostramos el conjunto solución de un sistema de 4 inecuaciones, en este caso, el conjunto solución se obtiene al intersecar 4 semiplanos y x 2 x y 4 y x 4 y x 4 Las rectas fronteras son y = x + 2, y = 4 x, y = x 4 e y = x 4 8
10 Gráfico Conjuntos convexos en R 2 Qué características tiene el conjunto solución de un sistema de inecuaciones? Consideremos la siguiente figura Si elegimos un par de puntos que pertenecen a ella y los unimos por un segmento observamos que dicho segmento queda incluido en ella. Y esto sucede para todo par de puntos que pertenecen a la figura y en este caso decimos que la figura es convexa. No sucede lo mismo con la siguiente figura: Observamos que existen al menos dos puntos que al unirlos por un segmento este queda incluido en la figura y existen otros pares de puntos de la figura que al unirlos por un segmento este no queda incluida en la misma. En este caso decimos que la figura es cóncava. En el caso de la figura convexa, cómo podemos escribir y demostrar analíticamente que para todo par de puntos de la figura, al unirlos por un segmento, éste queda incluido en la misma? Responderemos esta pregunta mostrando cómo expresar en forma analítica el conjunto de puntos que pertenecen a un segmento de recta. Para ello, primero vamos a conocer cómo se expresa la ecuación de una recta, dados dos puntos que pertenecen a ella Ecuaciones de la recta Recordemos que la ecuación de la recta que pasa por dos puntos A = (x 1, y 1) y B = (x 2, y 2) de la recta es: 9
11 L : y y2 y1 x x1 y1 x2 x1 siempre que L no sea una recta paralela a alguno de los ejes coordenados. Por ser x e y variables que pueden tomar cualquier valor real, podemos escribir: siendo t un parámetro que también toma valores reales. De donde deducimos que: y y2 x x 1 = t (x 2 x 1) entonces x = x 1 + t (x 2 x 1) y y 1 = t (y 2 y 1) entonces y = y 1 + t (y 2 y 1) y1 x x1 = t y1 x2 x1 Las ecuaciones x x1 t (x2 x1) y y 1 t (y 2 y 1 ) t R se conocen como ecuaciones paramétricas de la recta, donde A= (x 1, y 1) y B = (x 2, y 2) representan dos puntos de paso de la recta y el cociente y 2 y 1 x 2 x 1 es su pendiente. Ejemplo 5: Las ecuaciones paramétricas de la recta que pasa por los puntos (1,2) y (5,4) vienen dadas por: x 1 (5-1)t x 1 4t y 2 (4-2)t t R y 2 2t t R Si t = 0, reemplazando en las ecuaciones obtenemos el punto (1, 2) Si t = 2, reemplazando en las ecuaciones obtenemos el punto (9, 6) Si t = -5, reemplazando en las ecuaciones obtenemos el punto (-19, -8) Si t = 1/2, reemplazando en las ecuaciones obtenemos el punto (3, 3) Ecuación de la recta expresada como combinación lineal de dos puntos de ella El punto P = (x, y) de una recta se puede expresar como el par ordenado: (x, y) = (x 1+ t.(x 2 x 1), y 1+ t.(y 2 y 1))= (x 1+ t. x 2 t. x 1, y 1+ t. y 2 t.y 1)= = ((1 t). x 1+ t.x 2, (1 t).y 1+ t. y 2)= (1 t). (x 1,y 1) + t. ( x 2, y 2) La expresión (x, y) = (1 t).(x 1, y 1) + t.(x 2, y 2) t R Es la ecuación de la recta obtenida como combinación lineal de dos puntos que pertenecen a la misma. De esta manera: La ecuación de la recta se puede obtener como una combinación lineal de dos puntos de paso dados y a partir de esta es posible encontrar cualquier otro punto de la recta con solo dar valores reales al parámetro t. Ejemplo 6: Sean los puntos (1, 1) y (5, 1) los cuales determinan la ecuación 10
12 (x, y) = (1 t) (1,1) +t (5,1) t R que es una recta paralela al eje x Si t = 0 (x, y) = (1 0). (1, 1) + 0. (5, 1) = (1,1), que es el punto A Si t = 1 (x, y) = (11).(1,1) +1.(5, 1) = (5, 1) que es el punto B Si t = 1/4 (x, y) = (1 (1/4)). (1, 1) + (1/4).(5, 1) = (2, 1) que es el punto E Si t = 1/2 (x, y) = (1 (1/2)) (1, 1) + (1/2)(5, 1) = (3, 1) que es el punto F Si t = 2 (x, y) = (1 2) (1, 1) + 2 (5, 1) = (9, 1) que es el punto C Si t = 1 (x, y) = (1 (1)) (1,1) + (1)(5, 1) = (3, 1) que es el punto D Ejemplo 7: La ecuación de la recta que pasa por los puntos A = (1, 2) y B = (5, 3) es (x, y) = (1 t). (1,2) + t. (5,3) = (1 + 4t, 2 + t) con t R Si t = 0 (x, y) = (1 0).(1, 2) + 0. (5, 3) = (1,2) obtenemos el punto A Si t = 1 (x, y) = (11). (1,2) +1. (5, 3) = (5, 3) obtenemos el punto B Si t = 1/4 (x, y) = Si t = 1/2 (x, y) = (1, 2) +. (1, 2) (5, 3) = (2,9/4) obtenemos el punto C. (5, 3) = (3, 5/2) obtenemos el punto D Si t = 2 (x, y) = (-1) (1, 2) + 2. (5, 3) = (9, 4) obtenemos el punto E Si t = 1 (x, y) = 2. (1,2) + (1). (5, 3) = (3, 1) obtenemos el punto F 11
13 Observamos en el gráfico que: Si t = 0 o t =1 obtenemos los puntos A y B, respectivamente, que son los extremos del segmento que estos puntos determinan. Si 0 < t < 1 obtenemos puntos de la recta y que pertenecen al segmento determinado por A y B. Si t > 1 o t < 0 obtenemos puntos que pertenecen a la recta y No al segmento determinado por A y B. La ecuación del segmento de recta determinado por los puntos A = (x 1, y 1) y B =(x 2, y 2) es (x, y) = (1 t).(x 1, y 1) + t.(x 2, y 2) t [0,1] Que es una forma de expresar analíticamente el conjunto de puntos que pertenecen al segmento determinado por dos puntos A y B de una recta, restringiendo el valor del parámetro t al intervalo cerrado [0, 1]. La expresión (x, y) = (1 t).(x 1, y 1) + t.(x 2, y 2) t [0,1] Se denomina combinación lineal convexa obtenida a partir de los puntos A= (x 1, y 1) y B = (x 2, y 2) Definición de conjunto convexo Un conjunto C es convexo si y solo si para todo par de puntos A y B que pertenecen a C se cumple que cualquier combinación lineal convexa de A y B está incluida en el conjunto. Las siguientes figuras son convexas: Otras definiciones de conjunto convexo: 1) Sea M un subconjunto de R 2 M es un conjunto convexo si y solo si todo punto del segmento de recta que une dos puntos cualesquiera de M pertenece a M 2) Dados A y B M, M es convexo si y solo si toda combinación lineal convexa de A y B, esto es, P = (1 t). A + t. B M, t [0, 1] 12
14 Qué conjuntos del plano son conjuntos convexos? Los puntos, los segmentos y las rectas del plano son conjuntos convexos Propiedades de los conjuntos convexos Propiedad 1: La intersección de dos conjuntos convexos de R 2 es un conjunto convexo. Gráficamente M A B N Demostración: Sean M y N dos conjuntos convexos de R 2 y sea M N Sean A y B M N entonces A y B M N. Por lo tanto A y B M y A y B N. Como ambos son conjuntos convexos, (1 t). A + t.bb M y (1 t) A + t B N t [0, 1]. Entonces (1 t).a + t. B M N t [0, 1]. Con lo que se concluye que M N es convexo. Propiedad 2: La intersección de un número finito de conjuntos convexos es convexa. Propiedad 3: Los semiplanos son conjuntos convexos. En efecto, sea S el semiplano S = {(x, y) R 2 c 1 x + c 2 y c 3}. Probaremos que S es un conjunto convexo. Sean A, B S, esto significa que: A = (x 1, y 1) y satisface c 1 x 1 + c 2 y 1 c 3 y B = (x 2, y 2) y satisface c 1 x 2 + c 2 y 2 c 3 Veamos que toda combinación lineal convexa P = (x, y) de A y B está en el semiplano S. t [0, 1] es: P = (1 t). A + t. B = (1 t). (x 1, y 1) + t. (x 2, y 2) = ((1 t). x 1 + t x 2, (1 t) y 1 + t y 2). La primera componente de este par ordenado es x = (1 t) x 1 + t x 2 y la segunda componente es y = (1 t) y 1 + t y 2. Veamos que el par (x, y) S. En efecto, 13
15 c 1 x + c 2 y = c 1 (1 t) x 1+ c 1 t x 2 + c 2 (1 t) y 1 + c 2 t y 2 = = (1 t) (c 1 x 1 + c 2 y 1) + t (c 1 x 2 + c 2 y 2 ) (1 t) c 3 + t c 3 = c 3 Hemos demostrando que P = (1 t) A + t B es un punto de S, t [0,1] Valores de una función en un segmento Teorema: Si f es una función definida en R 2 de la forma f(x, y) = c 1 x+ c 2 y sean A =(x 1, y 1) y B = (x 2, y 2) puntos en R 2. Se cumple que para todo punto X que se encuentra en el segmento de recta determinado por los puntos A y B se verifica que f toma valores comprendidos entre f(a) y f(b). En consecuencia: Si f(a)=f(b)= K ϵ R entonces f(x) = K Ejemplo 8: Considerando el segmento: (x 1, x 2) = (1-t) ; t 10; la función: f(x 1; x 2) =z = 20 x x 2 con 0 t 1 y Analizaremos los valores que toma esta función en los puntos del segmento: Comenzamos evaluando la función en los puntos extremos: f ; = f 10 ; = Si consideramos ahora puntos interiores del segmento como f ; = ; 7 21 Aplicaremos los conceptos abordados en las secciones a para resolver problemas de programación lineal por método gráfico Resolución gráfica de un problema de programación lineal de máximo con única solución Retomamos el problema del ejemplo 1 cuyo modelo es: Maximizar: G (x, y) = 50 x + 65y (función objetivo) Sujeto a: (describe el conjunto de restricciones del problema) 3x + 5y 150 (restricción estructural 1) 3x + 3y 120 (restricción estructural 2) x 0, y 0 (restricciones de no negatividad) Debemos determinar la intersección de los cuatro semiplanos correspondientes a las restricciones del problema, la que nos va a permitir determinar la zona factible. 14
16 La zona factible está dada por el conjunto de puntos del plano que satisface simultáneamente las cuatro inecuaciones y la gráfica es: Conjunto de soluciones factibles (polígono convexo) Ahora se determinan los puntos de intersección de las rectas frontera de las restricciones del problema. x 0 y 0 (x, y) = (0, 0) 3x 5y 150 3x 3y 120 (x, y) = (25,15) 3x 5y 150 x 0 (x,y) = (0, 30) 3x 3y 120 x 0 (x,y) = (0, 40) 3x 5y 150 3x 3y 120 (x, y) = (50, 0) y 0 y 0 Observamos que NO todos estos puntos pertenecen a la zona factible (x, y) = (40, 0) Si un punto del conjunto de soluciones factibles es intersección de rectas fronteras es una Solución Factible Básica En este ejemplo son soluciones factibles básicas los puntos: (0, 0); (25,15); (0, 30) y (40,0). Los puntos (0, 40) y (50, 0) no son soluciones factibles. En qué punto la función G alcanza el máximo valor? Sabiendo que G (x, y) = 50 x + 65 y entonces y = 50 G(x, y) x, observamos que la ordenada al origen de esta recta depende del valor que tome G en algún punto del conjunto de soluciones factibles y que cuanto mayor sea la ordenada al origen más grande será el valor que tome la función objetivo. Para distintos valores de G las rectas tienen la misma pendiente y la ordenada al origen cada vez es mayor a medida que crece el valor de G. 15
17 El procedimiento para alcanzar el óptimo consiste en desplazar la función objetivo, dentro del conjunto de soluciones factibles, logrando que la ordenada al origen sea número cada vez más grande hasta alcanzar un punto de este conjunto en que la ordenada al origen sea lo más grande posible. Tratándose de una función objetivo lineal en un problema de programación lineal, la solución óptima se obtendrá en una solución factible básica que pertenece al área de soluciones factibles. Siendo G(x,y) = 50 x + 65 y, en el punto (0,0) el valor de la función objetivo es cero. Realizamos un traslado de la recta correspondiente a la función objetivo en una dirección paralela hasta alcanzar el punto (0;30) esto significa que si se producen 30 autos grandes y no se producen autos pequeños, el beneficio es de $1950. Trasladamos la recta función objetivo hasta alcanzar el punto (40,0), es decir que si no se producen autos grandes y 40 autos pequeños el beneficio es de G(40, 0) = $2000 (25,15) Trasladamos la recta correspondiente a la función objetivo hasta alcanzar el punto (25,15) Observamos que cuando una función objetivo se traslada a través del área convexa de soluciones factibles, el último punto que alcanza antes de abandonar el área es (25, 15), que es una solución factible básica. 16
18 Interpretamos que si se producen 25 autos pequeños y 15 autos grandes el beneficio es de $2225, como ya se recorrió todas las soluciones factibles básicas entonces hemos encontrado el óptimo. Respuesta: para obtener máximo beneficio conviene producir 25 autos chicos y 15 autos grandes y el beneficio será de $2225. Se llama Solución factible básica óptima a la solución factible básica que hace que la función objetivo alcance el máximo valor en el conjunto de soluciones factibles Resolución gráfica de un problema de máximo con alternativas Un problema de programación lineal de máximo con alternativas es un problema que no tiene única solución. Resolvamos el siguiente ejemplo: Maximizar f(x 1,x 2) = 6x x 2 sujeto a: x 1+x 2 4 x 2 2 3x 1+ 5x 2 15 x 1 0 x 2 0 Hallamos las intersecciones de las rectas fronteras y obtenemos los puntos: (0, 0); (5/3, 2); (5/2, 3/2); (4, 0); (0,4); (2, 2); (0, 3) y (0, 2). Solo los puntos (0, 0); (5/3, 2); (5/2, 3/2);(0, 2) y (4, 0) son soluciones factibles básicas Si desplazamos la función objetivo tratando de alcanzar el último punto del conjunto solución observamos que la función objetivo, en su última posición, coincide con la recta 3x 1+ 5x 2 = 15 y alcanza el máximo valor en todos los puntos que pertenecen al segmento de recta determinado por (5/3,2) y (5/2,3/2). Como la función objetivo es una función lineal y aplicando el Teorema 1, concluimos que la función f también alcanza el mismo máximo valor en los puntos que pertenecen al interior del segmento determinado por los puntos (5/3,2) y (5/2,3/2) Luego, las soluciones óptimas del problema son (x 1, x 2)=(1-t). (5/3,2) + t.(5/2,3/2) t [0,1] Los puntos (5/3,2) y (5/2,3/2) son soluciones factibles básicas óptimas y los puntos del interior del segmento son soluciones factibles No básicas óptimas Si queremos hallar una solución factible No básica óptima bastará darle un valor al parámetro t mayor que 0 y menor que 1. 17
19 En nuestro ejemplo, si t = 1/3, el punto (x 1, x 2) = óptima ,2., = 35 11, es una solución factible No básica Una solución factible No básica óptima es cualquier punto del interior del segmento determinado por las dos soluciones factibles básicas óptimas. Se obtienen asignándole al parámetro t un valor que pertenezca al intervalo abierto (0, 1). (5/3,2) SOLUCIÓN FACTIBLE BÁSICAÓPTIMA (5/2,3/2) SOLUCIÓN FACTIBLE BÁSICA ÓPTIMA F MÁXIMA f= Resolución gráfica de un Problema de mínimo con única solución Tomamos un ejemplo referido a un caso de minimización. Para resolver gráficamente problemas de mínimo el procedimiento es similar al de los problemas de máximo. Para hallar el punto donde la función alcanza su mínimo valor, buscaremos aquel que satisfaga todas las inecuaciones referidas a requerimientos y donde el funcional tenga el menor valor. Ejemplo 8: Un productor de pollos parrilleros necesita comprar alimentos que contengan dos tipos de vitaminas y hay dos productos que puede adquirir y que las contienen. Sus deseos son cumplimentar el mínimo requerido o más de cada vitamina al menor costo total. Debe utilizar alguno de los productos en particular, o los dos? Los datos referidos a los productos son: Producto 1 Producto 2 Costo $ 3/kg $ 2/kg Vitamina 1 10 u/kg 10 u/kg Vitamina 2 35 u/kg 20 u/kg El productor debe proporcionar, a cada pollo, en su alimentación, al menos 60 unidades de vitamina 1 y 180 unidades de vitamina 2. El objetivo es minimizar el costo necesario para comprar los productos que satisfagan los requerimientos de vitaminas. Podemos formalizar este problema así: 18
20 Los valores de x e y serán las cantidades de cada producto que hay que suministrar a cada animal. Luego, la función objetivo es: Minimizar: C (x, y) = 3x + 2 y Sujeto a 10 x + 10 y x + 20 y 180 x 0, y 0 De acuerdo a lo ya realizado, graficamos en primer término el conjunto de restricciones del problema de programación lineal en un sistema de coordenadas cartesianas y determinamos el conjunto de soluciones factibles. Consideramos ahora la función de costo C(x, y) = 3 x + 2 y donde C puede tomar diferentes valores. Para cada valor constante de C, cada una de las rectas C(x, y) = 3 x + 2, recibe el nombre de recta de costo constante. Trazamos la recta de costo nulo 3 x + 2 y = 0. Esta recta pasa por el origen de coordenadas. Todas las rectas de costo constante tienen la misma pendiente m = -3/2 y se escriben como y = - 3 C(x, y) 2 2 Si nos desplazamos hacia la derecha y hacia arriba el valor de la ordenada al origen C(x, y) 2, aumentando así el valor de la función y obtenemos costos mayores para puntos que están dentro del polígono de soluciones factibles. La zona factible correspondiente al problema se ve en el siguiente gráfico: Ahora se determinan las intersecciones de las rectas frontera 35x 20y x 10y 60 (x, y)= (4,2) 35x 20y 180 x 0 (x, y) = (0,9) 10x10y 60 x 0 (x, y) = (0,6) 35x 20y 180 y 0 (x, y) = (36/7,0) 10x10y 60 (x, y) = (6,0) y 0 Los puntos (6, 0); (4, 2) y (0, 9) son soluciones factibles básicas. La solución óptima del problema será aquel en donde la función objetivo tome el valor mínimo. 19
21 Siendo y = - 3 C(x, y), la función C está relacionada con la ordenada al origen y cuanto menor sea la ordenada al 2 2 origen más pequeño será el valor que tome la función objetivo. El procedimiento para alcanzar el óptimo consiste en desplazar la función objetivo dentro de la zona factible recorriendo las soluciones factibles básicas hasta alcanzar un punto en que la ordenada al origen tome el menor valor posible. Observamos en el siguientes gráfico que el valor mínimo se alcanza en el punto (4, 2),es decir que, para obtener un mínimo costo, conviene utilizar 4 unidades del producto 1 y 2 unidades del producto 2 y el costo será $16. Luego, la solución factible básica óptima es (4, 2) 3.5.Resolución gráfica de un Problema de mínimo con alternativas Al igual que en los problemas de máximo con alternativas, un problema de mínimo con alternativas No tiene única solución. Resolvamos un ejemplo Minimizar g(x, y) = 5 x + 10 y Sujeto a 2x + y 6 x + 2y 6 x +5 y 9 x 0 y 0 Una vez determinada la zona factible se grafica la recta g = 0 y luego se traslada esa recta en forma paralela hasta tocar por primera vez la zona factible que en este ejemplo toca un lado del conjunto convexo por ser la función objetivo paralela a la recta frontera x + 2y = 6 20
22 (0,6) (2,2) (4,1) (9,0) En este caso la función objetivo toma el mismo valor en los puntos (2,2) y (4,1). Es decir g(2,2) = g (4,1)= 30 por lo tanto los puntos (2,2) y (4,1) son las soluciones factibles básicas óptimas y el mínimo correspondiente es 30. El conjunto solución está formado por todos los puntos del segmento determinado por (2,2) y (4,1) que la podemos expresar en forma analítica de la siguiente manera: (x,y ) = (1-t). (2,2) + t.(4,1), t [0, 1] Es posible verificar que el valor de g es 30 para cualquier punto de la recta y en particular del segmento En efecto : (x,y ) = (1t). (2,2) + t. (4,1)= ((1t).2,(1t).2) + t.(4,1)= ((1t).2 + t.4, (1t).2 + t) = = (22t + 4t, 22t + t)= (2 + 2t, 2t) Luego, g(2 + 2t, 2t) = 5.( 2 + 2t ) (2t) = t t = 30 Esto nos muestra que el mínimo se alcanza en el segmento determinado los puntos (2,2) y (4,1). Los (x,y) = (1t) (2,2) + t.(4,1) t (0, 1) son soluciones factibles No básicas óptimas. Una solución factible No básica óptima se obtiene reemplazando t por un valor perteneciente al intervalo (0, 1) Por ejemplo, si t = ½ (x,y) = 1 2. (2,2) (4,1) = (1,1)+ 2, = 3, 2 2 Si se evalúa la función objetivo en 3 3 3, se obtiene g 3, = = 30 valor mínimo de la función objetivo. 4- Casos particulares: Problemas sin Solución 4.1 Problema no acotado Maximizar f(x,y) = 3x+5y Sujeto a: 3x+2y 6 2x+ 3y 6 x 0, y 0 21
23 Observamos en el gráfico que el conjunto de soluciones es no acotado y por lo tanto no es posible alcanzar el máximo y el funcional se puede seguir desplazando de tal forma que se logra continuar mejorando el funcional. 4.2 Problema incompatible Maximizar f(x,y) = 2x+5y Sujeto a: 3x+2y 6 x+ y 1 x 0, y 0 En este caso, no existe punto del plano que satisfaga las restricciones, los semiplanos no tienen punto en común. 5- Tipos de soluciones El planteo de un problema de programación lineal consiste en optimizar una función que es lineal (la función objetivo), sujeta a un número finito de desigualdades que también son lineales (las restricciones). Se puede demostrar que siempre es posible, matemáticamente, arribar a alguno de estos cuatro tipos de soluciones: 22
24 a) Existe una solución óptima, y es única (ejemplos 1 y 2). b) Existen infinitas soluciones óptimas que se encuentran a lo largo de un segmento determinado por dos puntos extremos. En este caso decimos que hay soluciones óptimas con alternativas (ejemplo 3). c) No existe una solución óptima porque siempre es posible mejorar la función objetivo. En este caso se dice que y que el problema es no acotado (ejemplo 4). d) No existen valores para las variables que satisfagan simultáneamente todas las desigualdades. Es decir, el conjunto de soluciones factibles es vacío, y este caso se dice que el problema es incompatible (ejemplo 5). 6- Resolución de problemas de programación lineal por el Método del Punto Extremo El método del punto extremo permite resolver problemas de programación lineal con dos variables. Consiste en: Identificar gráficamente el conjunto de soluciones factibles. Determinar las coordenadas de los puntos intersección de rectas fronteras llamados puntos esquina. Identificar los puntos esquinas que son soluciones factibles. Sustituir en la función objetivo las coordenadas de cada solución factible básica a fin de determinar el valor correspondiente del funcional. Una solución óptima en un problema de maximización (minimización) es una solución factible básica que produce el valor máximo (mínimo) de la función objetivo. Para analizar un ejemplo de este método retomemos los ejemplos anteriores. En el Ejemplo 1 x: número de autos pequeños ; y: número de autos grandes Maximizar: f (x, y) = 50 x + 65 y Sujeto a: 3x + 5y 150 3x + 3y 120 x 0, y 0 Según lo visto en la resolución gráfica tenemos puntos que son intersecciones de rectas fronteras, algunos son soluciones factibles y otros no. (0,0) punto esquina factible (25,15) punto esquina factible (0,30) punto esquina factible (0,40) punto esquina no factible (50,0) punto esquina no factible (40,0) punto esquina factible Sólo nos interesa ver qué valor toma la función objetivo en las soluciones factibles del problema. Lo veremos en la siguiente tabla: 23
25 (x, y) soluciones factibles del problema f(x,y) valor de la función objetivo (0,0) 0 (25,15) solución factible básica óptima 2225 máximo valor (0,30) 1950 (40,0) 2000 Conclusión: Para obtener máximo beneficio conviene producir 25 autos chicos y 15 autos grandes y se obtiene un beneficio de $2225. En el Ejemplo 2 x: número de unidades del producto 1; y: número de unidades del producto 2 Minimizar: g (x, y) = 3x + 2 y Sujeto a 10 x + 10 y x + 20 y 180 x 0, y 0 Según lo visto en la resolución gráfica tenemos puntos que son intersecciones de rectas fronteras, algunos son soluciones factibles y otros no. (4,2) punto esquina factible (0,9) punto esquina factible (0,6) punto esquina no factible (36/7,0) punto esquina no factible (6,0) punto esquina factible Evaluando la función objetivo en los puntos factibles del problema, observamos que el mínimo se encuentra en (4,2). (x,y) soluciones factibles del problema f(x,y) valor de la función objetivo (4,2) solución óptima 16 mínimo (0,9) 18 (6,0) 18 (4,1) solución óptima 30 mínimo (9,0) Otras situaciones que se pueden presentar: 7.1 Cómo determinar el conjunto de restricciones de un problema de programación lineal si conocemos la gráfica de la región factible? 24
26 Supongamos que tenemos el siguiente gráfico que representa la zona factible de un problema cuya función objetivo es Maximizar f(x, y) = 3x + 2y El gráfico de la zona factible surge de la intersección de 4 semiplanos S 1, S 2, S 3, S 4 S 1 S 2 S 3 S 4 Para determinar las ecuaciones de las rectas fronteras de la zona factible hallar dos puntos que pertenezcan a cada una de ellas. 25
27 La recta L1 es la recta frontera correspondiente al semiplano S 1 y dos puntos que pertenecen a ella pueden ser (4,0) y (0,4). Luego, la ecuación de la recta frontera es L 1: x + y = 4 y el semiplano S 1 es x + y 4 puesto que el punto (0, 0) verifica la restricción De la misma forma obtenemos la inecuación del semiplano S 2 La recta frontera L 2 está determinada por los puntos (6,0) y (0,2) y tiene como ecuación x + y = 2 o bien, una ecuación equivalente x + 3y = 6. La desigualdad que representa el semiplano S 2 es x + 3y 6 La siguiente figura muestra la intersección de los semiplanos S 1 y S Además debemos tener en cuenta que la zona factible de un problema de programación lineal está limitada al primer cuadrante, debemos agregar las restricciones x 0 e y 0. Luego, el conjunto restricción es x + y 4 x + 3y 6 x 0 y 0 Estamos en condiciones de realizar la Formulación del problema Maximizar f(x, y) = 3x+2y Sujeto a x + y 4 x + 3y 6 x 0 y Cómo determinar el Conjunto solución de un problema de programación lineal para un determinado valor de la función objetivo? El siguiente gráfico representa el área de soluciones factibles de un problema de programación lineal donde la función objetivo es: 26
28 Maximizar: f(x,y) = 3x + 2y Para encontrar las soluciones que verifican: a 1) f(x,y) = 6 a 2) f(x,y) = 12 Procedemos: a 1) Observamos en el gráfico que el conjunto de puntos donde la función objetivo vale 6 está dado por la intersección de la recta 3x + 2y = 6 con los ejes coordenados. Hallamos estas intersecciones con eje y x= 0 y = 3 (0,3) solución factible con eje x y= 0 x = 2 ( 2,0) solución factible El conjunto de soluciones factibles donde la función objetivo vale 6 es el segmento determinado por los puntos (0, 3) y (2, 0) es: (x, y) = (1-t). (0,3) + t. ( 2,0) t [0,1] a 2) Observamos en el gráfico que el conjunto de puntos donde la función objetivo vale 12 está dado por las intersecciones de la recta 3x + 2y = 12 con la recta y = 3 y de la recta 3x + 2y = 12 con el eje y. Hallamos estas intersecciones 27
29 En efecto si y = 0 x = 4 (4, 0) solución factible La intersección entre la recta 3x+ 2y = 12 y la recta y = 3 es (x,y) = ( 2,3). Entonces el conjunto de soluciones factibles donde la función objetivo vale 12 es (x, y) = (1-t). (2,3) + t. ( 4,0) t [0,1] Ejemplo 9 : Queremos expresar el conjunto de soluciones factibles donde la función objetivo es tal que: a) f(x,y) =1 b) f(x,y) = 3 c) f(x,y) = 4 d) f(x,y) = 6 e) f(x,y) = 11 f) f(x,y) = 11.5 g) f(x,y) = 12 h) f(x,y) = 18 a) Como f(x,y) = 1 es una recta que está fuera de la zona factible entonces no existe el conjunto de soluciones factibles donde la función objetivo tome el valor 1. Podemos observar en el gráfico f =1 28
30 b) f(x,y) = 3 es 3x+2y = 3 Gráficamente c) f(x,y) = 4 entonces 3x+2y = 4 Gráficamente Determinamos la intersección de la recta 3x + 2y = 3 con los ejes coordenados: (0,3/2) y ( 1,0. Como los puntos (0,3/2) y (1,0) son soluciones factibles y el segmento determinado por ellos es un conjunto convexo, los puntos del interior dl segmento también son soluciones factibles. El conjunto de soluciones factibles donde la función objetivo vale 3 es (x,y) = (1-t) (0,3/2) +t ( 1,0) t [0,1] d) f(x,y) = 6 entonces 3x+2y = 6 Determinamos la intersección de la recta 3x + 2y = 4 ésta recta con los ejes coordenados: (0, 2) y ( 4/3,0) que son soluciones factibles. El conjunto de soluciones factibles donde la función objetivo vale 6 es (x,y) = (1-t) (0,2) +t ( 4/3,0) t [0,1] e) f(x,y) =11 En este caso la intersección de la recta 3x+ 2y = 6 con los ejes no nos da la información como para poder hallar los puntos para determinan el segmento. El punto (0,3) no es solución factible Como vemos gráficamente es necesario determinar El conjunto de soluciones factibles donde la función objetivo vale11 es (x,y) = (1-t) (3,1) +t ( 11/3,0) t [0,1] 29
31 el punto de intersección entre la recta x + 3y = 6 y la recta 3x+ 2y = 6 que es el punto ( 6/7,12/7). Entonces el conjunto de soluciones factibles donde la función objetivo vale 6 es (x,y) = (1-t) (2,0) +t ( 6/7,12/7) t [0,1] f) f(x,y) = 11.5 El conjunto de soluciones factibles donde la función objetivo vale 11.5 es (x,y) = (1-t) (7/2,1/2) + t ( 23/6,0) t [0,1]. g) f(x,y) = 12 h) f(x,y) = 18 Como podemos observar gráficamente la única solución factible donde f = 12 es (4,0) que es una solución básica factible óptima y en donde f alcanza el valor máximo. Gráficamente vemos que no existe solución factible donde f = 18 ya que 18 es mayor al máximo que alcanza la función objetivo Cómo modificación de la función objetivo de un problema de programación lineal para que tenga soluciones alternativas? Analicemos el siguiente ejemplo Maximizar f(x, y) = 3x+2y Sujeto a x + y 4 x + 3y 6 x +y 1 x 0 y 0 30
32 La f(x, y) = 3x+2y debe ser cambiado por f(x, y)= x + y o f(x, y)= x + 3y o por ejemplo f(x, y)= 10x + 10y o f(x, y)= 5x + 15y En el caso de elegir f(x, y)= x + y el conjunto de soluciones óptimas será (x,y) = (1-t) (4,0) +t ( 3,1) t [0,1] donde el f máximo será 4 En el caso de elegir f(x, y)= 10x + 10y el conjunto de soluciones óptimas será (x,y) = (1-t) (4,0) +t ( 3,1) t [0,1] donde el f máximo será 40 En el caso de elegir f(x, y)= x + 3y el conjunto de soluciones óptimas será (x,y) = (1-t) (0,2) +t ( 3,1) t [0,1] donde el f máximo será 6 En el caso de elegir f(x, y)= 5x + 15y el conjunto de soluciones óptimas será (x,y) = (1-t) (0,2) +t ( 3,1) t [0,1] donde el f máximo será 30 Observaciones: En los problemas con alternativas tendremos soluciones factibles óptimas no básicas. No son los únicos cambios posibles, existen infinitos, siempre se debe verificar que para determinado valor de la función objetivo tengan la misma pendiente que una recta frontera que determina la zona factible. 31
33 8- SÍNTESIS CONCEPTUAL 8.1 Categorias de problemas de programación lineal: Como ya lo hemos analizados, al resolver un problema de programación lineal podemos encontrar las siguientes categorías: CON SOLUCIÓN ÚNICA PROBLEMA DE MÁXIMO CON SOLUCIONES ALTERNATIVAS CON SOLUCIÓN CON SOLUCIÓN ÚNICA PROBLEMA DE MÍNIMO CON SOLUCIONES ALTERNATIVAS POR NO EXISTIR REGIÓN FACTIBLE SIN SOLUCIÓN POR TRATARSE DE UN PROBLEMA DE MÁXIMO CON REGIÓN FACTIBLE NO ACOTADA 8.2- Modelación de un problema de programación lineal FUNCIÓN OBJETIVO RESTRICCIONES CONDICIONES DE NO NEGATIVIDAD 8.3- Métodos de Resolución: MétodoGráfico Métodosde Re solución Métododel Punto Esquina 8.4- Clasificación de soluciones: Las soluciones de un problema de programación lineal se pueden categorizar de acuerdo al siguiente cuadro ÓPTIMA BÁSICAS NO ÓPTIMA SOLUCIÓN FACTIBLE ÓPTIMA NO BÁSICAS NO ÓPTIMA Todo punto de la región factible es una solución factible del problema. La solución factible es básica cuando se encuentra en uno de los vértices de la región, en caso contrario es no básica. Si la solución básica optimiza la función objetivo, se denomina solución factible básica óptima Expresión de las soluciones alternativas (x, y) = (1 t).(x 1, y 1) + t.(x 2, y 2) t [0,1] 32
34 ACTIVIDADES Problema nº1: Grafica las siguientes inecuaciones y sistemas de inecuaciones a) x + y 5 b) 3x + 5y 15 4x y 4 4x 3y 24 2x 3y 6 x y 4 c) x 0 d) x 5 y 0 x 0 y 0 Problema nº2: Formula el sistema de desigualdades que representa los siguientes gráficos a) b) En los problemas 3 al 12 formula el modelo matemático de programación lineal correspondiente. Resuelve utilizando alguno de los dos métodos. Problema nº3: Una compañía fabrica y venden dos tipos de toallones T 1 y T 2. Para su fabricación se necesita un trabajo manual de 20 minutos para el tipo T 1 y de 30 minutos para el T 2; y un trabajo de máquina 20 minutos para T 1 y de 10 minutos para T 2. Se dispone para el trabajo manual de 100 horas al mes y para la máquina 80 horas al mes. Sabiendo que el beneficio por unidad es de $15 y $10 para T 1 y T 2, respectivamente, determina la producción para obtener el máximo beneficio. Problema nº4: Una librería decide lanzar ofertas de útiles escolares. Disponen de 600 gomas, 500 lápices y 400 biromes para la oferta, empaquetándolos de dos formas distintas; en el primer paquete P 1 pondrá 2 gomas, 1 lápiz y 2 biromes; en el segundo P 2, pondrán 3 gomas, 1 lápiz y 1 birome. Los precios de cada paquete serán $6,5 y $7, respectivamente. a) Cuántos paquetes se deben preparar de cada tipo para obtener el máximo ingreso? b) Cuál es el ingreso máximo? Problema nº5: Se dispone de 600 g de un determinado componente para fabricar medicamentos que se elaboran en comprimidos de tipo A y tipo B. Los de tipo A son de 40 g y los de tipo B de 30 g. Se necesitan al menos tres de tipo A, y al menos el doble de las de tipo B que del tipo A. Cada comprimido del tipo A proporciona una ganancia de $2 y la del tipo B de $1. Cuántos comprimidos se deben elaborar de cada tipo para que la ganancia sea máxima? 33
35 Problema nº6: Un revendedor acude a cierta fábrica de materiales de construcción a comprar cerámicos con $ Le ofrecen dos tipos de cerámicos: las de tipo A a $50 el m 2 y las de tipo B a $80 el m 2. Sólo dispone en su camioneta de un espacio para transportar 700 m 2 de cerámicos como máximo y que piensa vender el m 2 de cerámicos tipo A a $58 y el m 2 de tipo B a $90. a) Cuántos m 2 de cerámicos de cada tipo deberá comprar para obtener máximo beneficio? b) Cuál será ese beneficio máximo? Problema nº7: Una compañía posee dos minas: la mina A produce cada día 1 tonelada de hierro de alta calidad, 3 toneladas de calidad media y 5 de baja calidad. La mina B produce cada día 2 toneladas de cada una de las tres calidades. La compañía necesita al menos 80 toneladas de mineral de alta calidad, 160 toneladas de calidad media y 200 de baja calidad. Sabiendo que el costo diario de la operación es de $2000 en cada mina cuántos días debe trabajar cada mina para que el costo sea mínimo? Problema nº8: Imaginemos que las necesidades semanales mínimas de una persona en proteínas, hidratos de carbono y grasas son 8, 12 y 9 unidades, respectivamente. Supongamos que debemos obtener un preparado con esa composición mínima mezclando los productos A y B cuyos contenidos por kilogramo son los que se indican en la siguiente tabla: Proteínas Hidratos Grasas Costo (kg) Producto A Producto B Cuántos kilogramos de cada producto deberán comprarse semanalmente para que el costo de preparar la dieta sea mínimo? Problema nº9: Un pastelero tiene 150 kg de harina, 22 kg de azúcar y 28 kg de manteca para hacer dos tipos de tortas T1 y T2. Para hacer una docena de tortas de tipo T1 necesita 3 kg de harina, 1 kg de azúcar y 1kg de manteca y para hacer una docena de tipo T2 necesita 6 kg de harina, 0,5 kg de azúcar y 1 kg de manteca. El beneficio que obtiene por una docena de tortas tipo T1 es $30 y por una docena de tipo T2 es $30. Halla el número de docenas que tiene que hacer de cada tipo de torta para que el beneficio sea máximo. Problema nº10: Una empresa fabrica dos tipos de perfumes: A y B. La primera contiene un 15% de extracto de rosas, un 20% de alcohol y el resto es agua y la segunda lleva un 30% de extracto de rosas, un 15% de alcohol y el resto es agua. Diariamente se dispone de 60 litros de extracto de rosas y de 50 litros de alcohol. Cada día se pueden producir como máximo 150 litros del perfume B. El precio de venta por litro de perfume A es de $500 y el del perfume B es $2000. Halla los litros de cada tipo de perfume que deben producirse diariamente para que el beneficio sea máximo. Problema nº11: Una escuela prepara una excursión para 400 alumnos. La empresa de transporte tiene 8 micros de 40 plazas y 10 micros de 50 plazas, pero solo dispone de 9 conductores. El alquiler de un micro grande cuesta 80 pesos y el de uno pequeño, 60 pesos. Calcula cuántos micros de cada tipo hay que utilizar para que la excursión resulte lo mas económica posible para la escuela. Problema nº12: Se pretende cultivar en un terreno dos tipos de olivos: A y B. No se puede cultivar más de 8 ha con olivos de tipo A. Cada hectárea de olivos de tipo A necesita 4 m 3 de agua anuales y cada una de tipo B, 3 m 3. Se dispone anualmente de 44 m 3 de agua. Cada hectárea de tipo A requiere una inversión de $500 y cada una de tipo B, $225. Se dispone de $ 4500 para realizar dicha inversión. Si cada hectárea de olivar de tipo A y B producen, respectivamente, 500 y 300 litros anuales de aceite: a) Halla las hectáreas de cada tipo de olivo que se deben plantar para maximizar la producción de aceite. b) Determina la producción máxima. 34
36 Problema nº13: El siguiente gráfico representa el área de soluciones factibles de un problema de programación lineal donde la función objetivo es: Maximizar f(x, y) = 4 x + 2 y a) Formula el problema de programación lineal correspondiente. b) Resuelve el problema utilizando el método punto esquina. c) Resuelve el problema gráficamente d) Determina el conjunto de soluciones factibles donde f(x,y) = 20 e) Resuelve los ítems a) b) y c) pero suponiendo que la función objetivo corresponde a : Minimizar g(x, y) = 4 x + 2 y f) Modifica la función objetivo para que el problema de máximo tenga alternativa. Problema nº14: El siguiente gráfico representa el área de soluciones factibles de un problema de programación lineal donde la función objetivo es: Maximizar f(x, y) = x + 2 y. a) Formula el problema de programación lineal correspondiente. b) Resuelve el problema utilizando el método punto esquina. c) Resuelve el problema gráficamente Problema nº15: El siguiente gráfico corresponde a un problema de programación lineal de máximo cuya función objetivo es : f (x 1,x 2) = 50x 1 +50x 2 35
37 a) Determina el sistema de inecuaciones que lo verifica. b) Resuelve el problema gráficamente. c) Da las coordenadas de un punto que corresponda a: - una solución factible no básica - una solución factible básica no óptima - una solución factible básica óptima - una solución factible óptima no básica Problema nº16: Para el siguiente problema de programación lineal: Minimizar g(x,y) = x +3y sujeto a 13x +6y 25 x+3y 7 x0 y0 a) Determina las coordenadas de dos puntos esquina. b) Busca una solución factible (x,y) al problema planteado donde g(x,y) = 10 c) Resuelve gráficamente. Problema nº17: El siguiente conjunto de puntos P 1 = (0,0); P 2 = (4,0); P 3 = (3,2); P 4 = (1,3) ; P 5 = (0,3); constituyen los vértices de un conjunto convexo que es el conjunto de soluciones factibles de un problema de programación lineal de máximo. Los puntos P 3 y P 4 son soluciones óptimas del problema. a) Plantea el problema de programación lineal b) Grafica el conjunto de soluciones factibles, la función objetivo y el conjunto de soluciones óptimas. c) Determina, si existe, una solución básica donde la función objetivo asume el valor 4. Problema nº18: Para el siguiente problema de programación lineal: Maximizar ( x, y) = 2x + 5y sujeto a x + 2,5y 4 ; 2x + y 3; x 0 ; y 0 a) Determina las coordenadas de dos puntos de esquina. b) Busca una solución factible (x, y) al problema planteado donde (x, y) = (1, 0 ) c) Modifica la pendiente de para que el máximo de este problema esté en el punto (1,5, 0). Problema nº19: a) Investiga si los puntos están en el segmento determinado por los puntos (1, 5) y (2, 4) , ; (0, 6) y, Problema nº20: El siguiente gráfico representa el área de soluciones factibles de un problema de programación lineal donde la función objetivo es: Maximizar f(x, y) = 4 x + 2 y. 36
38 a) Completa la formulación del problema de programación lineal con el conjunto de restricciones estructurales y las condiciones de no negatividad. b) Expresa el conjunto de puntos del área de soluciones factibles donde el funcional sea: i) f (x, y) = 4 ii) f (x, y) = 8 iii) f (x, y) = 12 iv) f (x, y) = 14 Problema nº21: Una empresa produce dos productos P1 y P2 y desea maximizar las ganancias. Los requerimientos para cada producto 1 se dan en la siguiente tabla: Producto 1 Producto 2 Materia prima Materia prima Materia prima De la materia prima uno dispone de hasta 28 unidades, de la materia prima dos hasta 16 unidades y de la materia prima tres hasta 56 unidades. Si la ganancia de cada unidad del producto P1 es de $ 12 y la de cada unidad del producto P2 es de $ 9 Cuántas unidades del producto 1 y cuántas unidades del producto 2 se deben fabricar para obtener la máxima ganancia? a) Plantea el problema de programación lineal. b) Determina la solución óptima del problema de máximo con el correspondiente valor del funcional. c) En el problema de máximo, determine si (11, 4) es una solución factible óptima no básica. Problema nº22: Una maderera, que tiene dos sucursales, necesita producir al menos 80 artículos de madera de baja calidad, 140 de mediana calidad y 50 de alta calidad. Cada día, la sucursal I produce 20 artículos de baja calidad, 30 de mediana calidad y 10 de alta calidad, mientras que la sucursal II produce 10 artículos de baja calidad, 20 de media y 10 de alta calidad. Si los costos diarios son de $ 4000 para la sucursal I y de $3500 para la sucursal II. Cuántos días debe operar cada sucursal para satisfacer los requerimientos de producción a un costo mínimo? Cuál es el costo mínimo? Resuelve utilizando el método punto esquina Problema nº23: El siguiente gráfico representa el área de soluciones factibles de un problema de programación lineal donde la función objetivo es: Maximizar f(x, y) = 2 x + 3 y. a) Dé las coordenadas de un punto que corresponda a: - una solución factible no básica - una solución factible básica no optima - una solución factible básica optima b) Expresa el conjunto de puntos del área de soluciones factibles donde el funcional sea: i) f (x, y) = 6. ii) f (x, y) = 11 37
39 Respuestas: 1) a) b) c) d) 2) 38
40 a) x 4y 16 3x y 24 x 0 y 0 b) 3x 5y 15 y 2 x 4 x 0 y 0 3) Variables de decisión: x: nº de toallones de tipo T 1 y: nº de toallones de tipo T 2 Maximizar: f(x,y) = 15x+10y sujeto a: 20x+30y x+10y 4800 x 0, y 0 La solución óptima es fabricar 210 del tipo T 1 y 60 del tipo T 2 para obtener un beneficio de $3750 4) Variables de decisión: x: nº de paquetes de tipo P1 y: nº de paquetes de tipo P2 Maximizar: f(x,y) = 6,5x+7y sujeto a: 2x+3y 600 x+y 500 2x+y 400 x 0, y 0 La solución óptima es 150 P1 y 100 P2 con la que se obtienen $1675 5) Variables de decisión: x: nº de comprimidos de tipo A y: nº de comprimidos de tipo B Maximizar: f(x,y) = 2x+y sujeto a: 40x+30y 600 x 3 y 2x x 0, y 0 La máxima ganancia es de $24, y se obtiene fabricando 6 comprimidos de tipo A y 12 de tipo B. 6) Variables de decisión: x: nº de m 2 de cerámicos de tipo A y: nº de m 2 de cerámicos de tipo B Maximizar: f(x,y) = 8x+10y sujeto a: 50x+80y x+y 700 x 0, y 0 Se deben comprar 200 m 2 de cerámicos de tipo A y 500 m 2 de cerámicos tipo B para obtener un beneficio máximo de $ ) Variables de decisión: x: nº de días que se debe trabajar en la mina A y: nº de días que se debe trabajar en la mina B Minimizar: f(x,y) = 2000x+2000y sujeto a: x+2y 80 3x+2y 160 5x+2y 200 x 0, y 0 Se debe trabajar 40 días en la mina A y 20 en la B. Costo mínimo $ ) Variables de decisión: x: nº de kg del producto A y: nº de kg del producto A Minimizar: f(x,y) = 600x+400y sujeto a: 2x+y 8 39
41 6x+y 12 x+3y 9 x 0, y 0 Se deben comprar 3 kg del producto A y 2 kg del producto B. Costo mínimo $2600 9) Variables de decisión: x: nº de docenas de tortas de tipo T1 y: nº de docenas de tortas de tipo T2 Maximizar: f(x,y) = 30x+30y sujeto a: 3x+6y 150 x+1/2 y 22 x+y 28 x 0, y 0 Conjunto de soluciones óptimas (x, y) = (1t) (16, 12) + t (6,22) t [0,1] Beneficio máximo de $ ) Variables de decisión: x: nº de litros de perfume A y: nº de litros de perfume B Maximizar: f(x,y) = 500x+2000y sujeto a: 0.15x+0.30y x+0.15 y 50 y 150 x 0, y 0 Se deben producir 100 litros de perfume del tipo A y 150 litros de perfume del tipo B. Beneficio máximo $ ) Variables de decisión: x: nº de transportes grandes y: nº transportes pequeños Minimizar: f(x,y) = 80x+60y sujeto a: 50x+ 40y 400 x+ y 9 x 10 y 8 x 0, y 0 Se deben utilizar 4 transportes grandes y 5 pequeños. Costo mínimo $ ) Variables de decisión: x: nº de ha de olivo tipo A y: nº de ha de olivo tipo B Maximizar: f(x,y) = 500x+300y sujeto a: x 8 4x+3y x+225y 4500 x 0, y 0 a) Hay que cultivar 8 hectáreas de olivo de tipo A y 4 hectáreas del tipo B. b) La producción máxima es de 5200 litros 13) a) Max f(x,y) = 4x + 2y Sujeto a 2x + 3y 24 2x + 3y 12 2x + y 6 x + y 9 x 0 y 0 b) Método punto esquina 40
42 (x,y) f(x,y) = 4x+ 2y (3/2, 3) 12 (6,0) 2 (9,0) 36 máximo solución óptima (3,6) 24 (0,8) 16 (0,6) 12 C) Resolución gráfica d) Conjunto de soluciones factibles donde f (x,y)= 20 es (x,y) = (1-t)(9/2,1)+t(3/2,7) t[0,1] e) a) Minimizar g(x,y) = 4x + 2y Sujeto a 2x + 3y 24 2x + 3y 12 41
43 2x + y 6 x + y 9 x 0 y 0 b) Método punto esquina (x,y) g(x,y) = 4x+ 2y (3/2,3) solución 12 mínimo óptima (6,0) 24 (9,0) 36 (3,6) 24 (0,8) 16 (0,6) solución 12 mínimo óptima Conjunto de soluciones óptimas (x,y) = (1- t)(3/2,3)+t(0,6) t[0,1] g (x,y) = 12 mínimo c) Resolución gráfica Conjunto de soluciones óptimas (x,y) = (1-t)(3/2,3)+t(0,6) t[0,1] g (x,y) = 12 mínimo f) Ejemplos (existen muchas posibilidades) Maximizar f(x,y) = 2x + 3y en ese caso el conjunto de soluciones óptimas será (x,y) = (1-t)(3,6)+t(0,8) t[0,1] f(x,y) = 24 máximo otra posibilidad es Maximizar f(x,y) = x + y en ese caso el conjunto de soluciones óptimas será (x,y) = (1-t)(3,6)+t(9,0) t[0,1] f(x,y) = 9 máximo 14)a) Formulación Maximizar f(x,y) = x+2y 42
44 Sujeto a: x + y 12 -x + 2y 0-4x + y -7 x -3 y -12 x 0 y 0 b) Método punto esquina (x,y) f(x,y) = x+ 2y (2, 1) 4 (3,5) 13 (6,6) 18 máximo solución óptima (8,4) 16 c) Método gráfico 15) a) x 1 + x 2 4 x 2 3 2x 1 + x 2 6 x 1 0 x 2 0 b) Maximizar f (x 1,x 2) = 50x 1 +50x 2 x 1 + x 2 4 x 2 3 2x 1 + x 2 6 x 1 0 x
45 Conjunto de soluciones óptimas (x 1,x 2) = (1-t) (1,3) +t (2,2) t [0,1] Máximo f(x 1,x 2) = 200 c) (1,1) solución factible no básica (0,3) solución factible básica no óptima (2,2) solución factible básica óptima Para obtener una solución factible no básica óptima en (x 1,x 2) = (1-t) (1,3) +t (2,2) t [0,1] tomamos por ejemplo t = 1/2 (x, y) = (1-1/2) (1,3) +1/2 (2,2) = 1/2 (1,3) +1/2 (2,2) = (1/2,3/2)+(1,1) = (1/2+1,3/2+1) = (3/2,5/2). 16) a) Dos de los puntos esquinas factibles pueden ser (1,2) (0,25/6) b) Ejemplo (1,3) g(1,3) = 1+3.3=10 c) Resolución gráfica Conjunto de soluciones óptimas (y 1,y 2) = (1-t) (1,2) +t (7,0) t [0,1] Mínimo g(y 1,y 2) = 7 44
46 17) a) Resolución gráfica (x 1,x 2) = (1-t) (3,2) +t (1,3) t [0,1] Máximo f(x 1,x 2) = 7 b) Maximizar f(x 1,x 2) = x 1 + 2x 2 Sujeto a 2 x 1+ x 2 8 x 2 3 x 1+ 2x 2 7 x 1 0 x 2 0 d) (x 1,x 2) = (4,0) Es Solución Factible Básica donde f(4, 0) = 4 18)a) Dos de los puntos esquina pueden ser (3/2,0), (7/8,5/4) b) (1,0) es solución factible c) El nuevo problema sería Maximizar: f(x, y) = 4x+ y sujeto a x + 2,5y 4 ; 2x + y 3; x 0 ; y 0 45
47 19) 3 9, 2 2 pertenece al segmento; (0, 6) y 5 10, ) a) Maximizar f(x, y) = 4x + 2y Sujeta a: x 3; y 2; x + y 4; x 0; y 0 b) i) (x, y) = (1t) (1, 0) + t (0, 2) t [0,1] ii) (x, y) = (1t) (2, 0) + t (1, 2) t [0,1] iii) (x, y) = (1t) (3, 0) + t (2, 2) t [0,1] iv) (x, y) = (3, 1) no pertenecen al segmento. 21)a) x 1: nº de unidades del producto 1 x 2: nº de unidades del producto 2 Maximizar: f(x 1,x 2) = 12x 1+ 9x 2 sujeto a x 1 + 2x 2 28 x 1 + x x 1 + 3x 2 56 x 1 0 x 2 0 b) Solución óptima (x 1,x 2)= (1-t)(14,0)+t(8,8) t0,1 Máximo f = 168 c) (11,4)= (1-t). (14, 0) +t (8,8) = (14-14t, 0) + (8t, 8t)= (14-6t, 8t) 14 6t 11 (1) De (2) 8t = 4 t = ½ en (1) 14-6(1/2) = 14-3 = 11 8t 4 (2) Como (11,4) está en el segmento determinado por (14,0) y (8,8) es una solución factible no básica óptima. Otra forma de resolver el ítem c) f(11,4)= 12(11)+9(4) = 168 (11,4) es una solución factible ya que verifica todas las siguientes desigualdades (4) (11) + 3.(4)
48 22) y 1: nº de días que opera la sucursal I y 2: nº de días que opera la sucursal II Minimizar: f(y 1, y 2) = 4000 y y 2 20 y y y y y y 2 50 y 1 0, y 2 0 Gráfico (y 1, y 2) f (y 1, y 2) (5,0) (4,1)SFBO mínimo (2,4) (0,8) Rta: La sucursal I debe operar 4 días y la sucursal II 1 día y el costo mínimo es de $ ) a) (x,y) f (x,y)=2x+3y (0,0) 0 (4,0) 8 (4,1) 11 (2,3) SFBO 13 máximo (0,3) 9 SF no básica (1,1) SFB no óptima (4,1) SFBO (2,3) b) i) (x, y)=(1-t)(3,0)+t(0,2) t0,1 ii) 2x 3y 11 (1,3) y 3 (x, y)=(1-t)(4,1)+t(1,3) t0,1 47
49 TALLER de PROGRAMACIÔN LINEAL Actividad 1: El lenguaje de la programación lineal 1) Lee el siguiente problema: Una compañía de software para computadoras publica juegos y programas educativos. Su estrategia de negocios es comercializar por lo menos 32 nuevos software cada año, pero si se duplica la producción de programas educativos, el total de software no debe superar las 48 unidades. La compañía tiene una ganancia de 15 mil dólares por cada juego y 20 mil dólares por cada programa educativo. Determina cuántos juegos y cuántos programas educativos debe producir para maximizar su ganancia 1 a) Por qué el problema dado es de programación lineal? 1b) Modela la situación planteada en el problema identificando: FUNCIÓN OBJETIVO RESTRICCIO- NES - CONDICIONES DE NO NEGATIVIDAD 2) El siguiente es un modelo de un problema de un programación lineal y su representación gráfica. 2a) Ubica cada concepto según corresponda: FUNCIÓN OBJETIVO RESTRICCIONES - CONDICIONES DE NO NEGATIVIDAD- REGIÓN FACTIBLE SOLUCIÓN BÁSICA SOLUCIÓN BÁSICA ÓPTIMA SOLUCIÓN NO BÁSICA Maximizar: f(x;y) = 10 x + 10 y Sujeto a: 2x + y 8 2x + 3y 12 y 3 x 0 y 0 B C D A F E A (0; 0) B (0;3). C (3/2; 3) D (3; 2) E (4; 0) F (2;0). 2b) Cómo se debe definir la función objetivo para que la solución sea: (x; y) = (3; 2) (1-t) + (4;0) t, 0 t 1 2c) Cuál es la solución si se pretende que f(x;y) = 30? Actividad 2: Argumenta si los siguientes enunciados son verdaderos o falsos. a) Sabiendo que.: Una compañía de software para computadoras publica juegos y programas educativos. Su estrategia de negocios es comercializar por lo menos 32 nuevos software cada año, pero si se duplica la producción de programas educativos, el total de software no debe superar las 48 unidades. La compañía tiene una ganancia de 15 mil dólares por cada juego y 20 mil dólares por cada programa educativo. En estas condiciones se puede asegurar que: Producir 10 programas de cada tipo es una solución factible de este problema. 48
50 b) El segmento: (x; y) = (2;1) t + (4; 5) (1-t), siendo 0 t 1, es solución de un problema de programación lineal de máximo. Con esta información se puede asegurar que (10/3 ; 11/3) es una solución óptima de dicho problema. c) El punto (10/3, 13/3) pertenece al segmento determinado por (2,3) y (4,5). d) Dado el siguiente problema de Programación Lineal: Minimizar g(x,y) =6x+2y sujeto a: x+y 8 3x+y 12 x 0 y 0 una solución factible no básica óptima del problema es: (2;6) e) Dada la siguiente zona factible del problema de programación lineal cuya función objetivo es: Maximizar f(x,y) = x + y el conjunto de restricciones que representa la zona factible es: x + y 4 5x + 3y 15 y 2 x 0 y 0 REFLEXION FINAL: Supone que debes darle a un compañero, que va a cursar Matemática Básica, una opinión sobre el taller. Expresa que le dirías al respecto 49
Una variable, y, es función de otra, x, si existe una relación entre ambas de forma tal que: para cada valor de x existe solamente uno de y
Funciones Una variable, y, es función de otra, x, si existe una relación entre ambas de forma tal que: para cada valor de x existe solamente uno de y Notamos de la siguiente manera: y = f(x) Leemos: y

References: resolución 
 resolución 
 Resolución 
 Resolución 
 Resolución 
 Resolución 
 Resolución 
 Resolución 
 resolución 
 resolución 
 Resolución 
 Resolución 
 Resolución 
 Resolución