programación lineal

EDI – 4º año Primera División 2013

Programación Lineal

La programación lineal consiste en un conjunto de técnicas que facilitan la resolución de problemas de planificación económica o social. Su objetivo es el de optimizar, es decir, minimizar los costos o maximizar los beneficios, utilizando las restricciones o condiciones impuestas por el problema.

Problema de Aplicación:

Para satisfacer las demandas de sus distribuidores, un fabricante de jeans debe producir, por día, no menos de 300 y no más de 800 jeans azules y no menos de 100 y no más de 300 jeans negros. Además, para mantener una buena calidad, no debe producir en total más de 800 jeans por día. Sabiendo que se obtiene una ganancia de $16 por cada jean azul y de $8 por cada jean negro, desea saber cuál debe ser la producción diaria de cada tipo de jean para maximizar la ganancia.

Si simbolizamos con x la producción de jeans azules y con y la de jeans negros, podemos plantear las siguientes inecuaciones:

{300 ≤ x≤ 800(1)100≤ y ≤300 (2)

x+ y≤ 800(3)

Estas condiciones, que son las restricciones del problema, se deben cumplir simultáneamente (al mismo tiempo); por lo tanto, forman un sistema de inecuaciones.

Encontrar la solución del sistema significa hallar el conjunto de puntos del plano que cumplen todas las restricciones. A ese conjunto de puntos lo llamamos región factible.

Vamos a representar el conjunto de puntos del plano que cumplen todas las restricciones:

Documento elaborado por Prof. Leonel Ganga Página 1


La región factible es el conjunto de los puntos del plano que han quedado pintado con los tres colores. En este caso es un cuadrilátero (rodeado por los vértices), y suele ser un polígono convexo.

La solución del problema es un punto de la región factible. Para averiguar cuál es, debemos plantear la función objetivo: en nuestro caso, pretendemos maximizar la ganancia.

Si llamamos G a la ganancia, estamos en presencia de una función que depende de dos variables: de la producción de jeans azules (x) y de la producción de jeans negros ( y ); entonces, de acuerdo con el enunciado del problema, la función objetivo es:

G(x , y )=16 x+8 y

Maximizar esta función significa hallar, en la región factible, el punto que proporciona mayor ganancia.

Propiedad Fundamental: Si la región factible es un polígono convexo, la solución óptima de un problema de programación lineal se encuentra SIEMPRE en alguno de sus vértices.

De acuerdo con esa propiedad, nuestro problema se reduce a hallar el valor de la función objetivo para cada uno de los vértices del polígono que constituye la región factible; luego, aquel que dé el valor máximo, es la solución buscada.

Simbolizamos con las letras: A,B,C y D los vértices del polígono que contienen todos los puntos factibles.

Las coordenadas de cada vértice son:

A=(300,300 )

B=(300,100 )

C=(700,100 )

D=(500,300)

Calculamos a partir de la función G(x , y )=16 x+8 y la ganancia asociada en cada uno de los vértices que determinamos arriba:

Para el punto A :G(300,300)=16(300)+8 (300)=7200

Para el punto B:G (300,100)=16(300)+8(100)=5600

Para el punto C :G(700,100)=16 (700)+8(100)=12000



Para el punto D :G(500,300)=16(500)+8(300)=10400

De los cuatro vértices, el que otorga mayor valor a la función G es el punto C de coordenadas (700,100), entonces, podemos asegurar que si se produce diariamente 700 jeans azules y 100negros el fabricante obtiene la máxima ganancia que es de $ 12000 .

Para recordar:

La solución de un problema de programación lineal SIEMPRE está en uno de los vértices

Si debemos obtener la máxima ganancia o el máximo beneficio, buscaremos el vértice que maximiza (da el mayor valor) de la función objetivo.

Si debemos minimizar costos (dar el menor valor de los costos) de la función objetivo, buscaremos el vértice de menor valor.

Ejercicios

1) Un granjero dispone de cien hectáreas en las que debe sembrar los cultivos A y B. La semilla del cultivo A cuesta $4 por hectárea, y la del cultivo B, $6 por hectárea. Los costos totales de mano de obra son de $10 por hectárea de cultivo A y $20 por hectárea del cultivo B. El granjero espera obtener un ingreso de $110 por hectárea cosechada con el cultivo A y de $150 por hectárea cosechada con el cultivo B. Además, no puede invertir más de $480 en semillas ni más de $1400 en mano de obra. ¿Cuántas hectáreas de cada cultivo le conviene sembrar para obtener la máxima ganancia?a) Enunciar y representar gráficamente las restricciones asociadas al problema. b) Hallen la función objetivo y el punto que la maximiza.

NOTA: La función ganancia, se obtiene a partir de la ecuación:

Ganancia=Ingresos – Costos

2) Una compañía papelera produce dos tipos de cuadernos: los de tapa dura, que se venden a $1,25 cada uno, y los de tapa blanda, que se venden a $0,90 cada uno. Los costos de producción por unidad de cada cuaderno son de $1 para los de tapa dura y $0,75 para los de tapa blanda. La compañía puede producir, por día, entre 2000 y 3000 cuadernos de tapa dura y entre 3000 y 6000 cuadernos de tapa blanca. Además, la producción diaria no supera las 7000 unidades. El gerente de producción necesita saber cuantos cuadernos de cada tipo conviene fabricar por día para que la empresa obtenga la máxima ganancia. a) Enunciar y representar gráficamente las restricciones asociadas al problema.



b) Hallen la función objetivo y el punto que la maximiza.

3) Una tapicería está dedicada al tapizado de dos tipos de sillones a los que denominaremos tipo (A) y tipo (B). Cada unidad del sillón tipo (A) necesita 10 metros de tela de tapicería y 12 horas de trabajo, mientras cada unidad de los del tipo (B) necesita 15 metros de tela y 16 horas de trabajo. La tapicería dispone semanalmente de 300 m de tela y 336 horas de trabajo. Los sillones del tipo (A) dan a la empresa una utilidad de $ 1500, y los del tipo (B) una utilidad de $ 2100. Suponiendo que todos los sillones tapizados se venden y que no existe escasez de otros elementos como hilo, clavos, tachuelas, etc, se desea saber cuántos sillones de cada tipo deben tapizarse para que la empresa obtenga máxima ganancia

4) Una persona debe cumplir una dieta que le exige consumir por semana al menos 1 Kg. de carbohidratos y ½ Kg. de proteínas. Para ello cuenta con dos alimentos que llamaremos (A) y (B) que están constituidos exclusivamente por carbohidratos y proteínas.El alimento (A) contiene 90% (en peso) de carbohidratos y el resto de proteínas, mientras que el alimento (B) contiene 60% de carbohidratos y el resto de proteínas. El alimento (A) cuesta 20 $ / Kg. y el alimento (B), 40 $ / Kg. ¿Qué cantidad de cada alimento deberá consumir la persona para que el costo de su dieta sea mínimo?


programación lineal

Documents