Programación Lineal-ejemplos.docx

PROGRAMACIÓN LINEAL Situación Profesional: Bolsas Basurín La empresa Basurín es una pequeña compañía dedicada a la fabricación de bolsas de residuos domiciliaria únicamente. Su gerente de producción desea incursionar en el mercado con bolsas para consorcio. La inversión le resultará rentable siempre que pueda producir más de 700 bolsas domiciliarias y más de 500 para consorcio diariamente. Para ello encarga a su analista de sistemas que determine la conveniencia o no de realizar la inversión. El profesional realiza una cuidadosa investigación de los tiempos que demanda cada una de las etapas por las que deben pasar los dos productos. Las mismas son: 1.- Cortar y pegar 2.- Embalar Los datos que obtuvo el gerente fueron que cada 100 bolsas domiciliarias se necesitan 2 horas para cortar y pegar mientras que hacen falta 3 horas para desarrollar la misma tarea en las bolsas de consorcio. Averiguó también que se requiere 1 hora para embalar la misma cantidad de bolsas domiciliarias y 2 horas para las de consorcio. De acuerdo a las disponibilidades de su empresa, el gerente puede contar con 24 horas de trabajo diarias para cortar y pegar y 14 horas para embalar. De acuerdo a los datos, ¿le resultará conveniente a la empresa fabricar el nuevo tipo de bolsas?

Situación Profesional: Bolsas Basurín Retomemos la situación de la fábrica de bolsas para basura, pero ahora el problema será diferente. Se necesetica saber qué cantidad de bolsas de cada tipo debe fabricar esta empresa si dispone a lo sumo de 24 horas diarias para cortar y pegar y 14 horas diarias para embalar. Se quiere lograr que la ganancia sea óptima. Se sabe que las bolsas para consorcio dejan una ganancia de $12 cada 100 bolsas y las domiciliarias $7 por la misma cantidad.

Herramientas Sistemas de Inecuaciones Lineales. Programación Lineal La diferencia entre el planteo del módulo anterior y este es que anteriormente dábamos por seguro que la totalidad de horas disponibles se utilizaban, situación que no es del todo real, ya que habitualmente se tiene una disponibilidad, ya sea de horas de trabajo, de materia prima, de dinero, etc. lo cual no quiere decir que se ocupen en su totalidad. Dependerá de otros factores tales como los costos de producción de cada tipo de producto o la contribución a las utilidades que cada producto proporcione, que convenga producir más de un tipo que de otro, de modo que pueden llegar a quedar disponibles parte de los recursos. Pero volvamos a nuestra situación. Tratemos de responder la pregunta acerca de la modificación del planteo original. Sabemos que los tiempos que demanden ambas tareas para cada tipo de bolsas deberán ser a lo sumo igual a los disponibles, es decir podrán ser iguales o menores, por lo tanto el planteo ahora será:

2x  3y  24 (1)  x  2y  14 que se conoce con el nombre de sistema de inecuaciones lineales. Las dos desigualdades anteriores, representan las restricciones (disponibilidades); pero no son las únicas que existen ya que también podemos afirmar que no se pueden producir cantidades negativas, es decir (2) x0 ; y0

(1)

Pero aquí no termina el planteo, ya que falta plantear en símbolos la parte del problema que se refiere a la ganancia. Queremos que con las cantidades x y y de cada tipo de bolsas, la ganancia sea máxima; conocemos la ganancia que aporta cada tipo de bolsa cada 100 unidades. Por lo tanto: 1 )

7 . x + 12 . y = g

(3) representará la ganancia que la empresa puede obtener y que debe ser óptima. El conjunto de expresiones (1), (2) y (3) constituye el planteo de un problema de programación lineal. Las expresiones (1) y (2) se llaman restricciones y la expresión (3) función objetivo dado que el objetivo del problema es hacer que esta función tome el valor máximo posible respetando siempre las restricciones que la acompañan. El planteo suele presentarse de la siguiente manera: maximizar

7 . x + 12 . y

sujeta a 2x  3y  24 x  2y  14

x0 ; y0 Es tema de este módulo la resolución de este tipo de planteos; veremos dos formas de abordar el problema: gráfica y analítica.

Resolución de problemas de programación lineal  Método Gráfico Para no tener inconveniente en la comprensión de este método recomendamos al estudiante que revea, en el texto básico ((TB)), los temas referidos a función lineal y su representación gráfica. La explicación del método la desarrollaremos resolviendo la situación profesional.

Ejercicio resuleto gráficamente: En primer término interpretaremos gráficamente las restricciones a partir de la representación gráfica de las ecuaciones asociadas a ellas. A cada inecuación le podemos asociar una ecuación: a 2x + 3y  24 se le puede asociar y a x + 2y  14

se le puede asociar

2x + 3y = 24 (4) x + 2y = 14

(5)

Si representamos gráficamente la ecuación (4) obtenemos la recta que pasa por los puntos (0;8) y (12;0) y 8

figura 1 x 0

12

Si ahora pensamos en la inecuación correspondiente a esta ecuación, veremos que todos los puntos que están en el semiplano determinado por la recta (incluyendo a ésta) y al cual pertenece el origen son solución a la desigualdad considerada (2x + 3y  24). Si agregamos la condición de que x  0 y y  0 queda delimitada entonces, la zona sombreada de la figura 1. Tenemos hasta ahora que todos los puntos de la región sombreada son solución de las tres inecuaciones consideradas, si incorporamos la segunda inecuación del sistema trazando la ecuación (5), obtendremos la región sombreada en la figura 2 2

Región que incluye todos los puntos que son solución factible de las inecuaciones

y 8 7

figura 2 x 12

14

Consideremos la familia de rectas 12x + 6y = g (revise el concepto de pendiente en el texto básico) ((TB)) todas paralelas entre sí con la única diferencia de su ordenada al origen. En nuestro problema el valor de la ordenada al origen está directamente relacionado con la ganancia (g). Demos algunos valores a g y representemos las rectas y

7

x 0

12

7x + 12y = 84

7x + 12y = 42 7x + 12y = 0 El método gráfico consiste en desplazar, paralela a sí misma, una cualquiera de las rectas que representan la ganancia de modo de obtener la de mayor ordenada al origen (mayor ganancia), manteniéndonos siempre dentro del conjunto solución. y

Última recta paralela a la función objetivo que se puede trazar con intersección no vacía con el conjunto solución.

8 7 4

(6;4)

x 0

6

12

x 14

Significa que para obtener la ganancia óptima se deben producir 600 (6 centenas) bolsas domiciliarias y 400 bolsas de consorcio de acuerdo a los valores de ganancia indicados ($7 y $12 respectivamente). La ganancia obtenida se calcula a partir de la función objetivo 7 . 6 + 12 . 4 = 90 habrá una ganancia de $9.000. En este caso son aprovechados íntegramente los recursos, no siempre será así y habrá una holgura o excedente dada por la cantidad de recursos que no fueron utilizados. 3

Los pasos a seguir para resolver un problema de maximización de programación lineal por el método gráfico son:

1) Trazar las rectas correspondientes a cada una de las restricciones. 2) Determinar la región de soluciones factibles. 3) Trazar una recta de la familia de las rectas de la función objetivo. 4) Desplazar la recta paralela a sí misma hasta el punto de intersección con la región de soluciones factibles de modo que esta recta tenga la mayor ordenada al origen posible. 5) El punto de coordenadas (x,y) que se encuentre sobre esta recta y pertenezca a la región de soluciones factibles es una solución óptima.

Resolvamos ahora un problema de minimización. Ejemplo: Con base en los actuales niveles de inventario y de la demanda potencial para el siguiente mes, los administradores de una empresa láctea han especificado que la producción total combinada de los productos A y B debe ser, al menos, de 7700 litros. Por otro lado, se debe satisfacer también el pedido de un cliente de 2750 litros del producto A. El objetivo de los administradores de la empresa es satisfacer los requisitos anteriores incurriendo en un costo de producción mínimo. Los costos de producción son de $3 por litro de producto A y de $2 por litro para el producto B. Escribamos en primer lugar la función objetivo llamando x1 a la cantidad de litros del producto A y x2 a la cantidad de litros del producto B. Como los costos de producción son de $3 para cada litro de producto A y de $2 para cada litro del producto B se trata de: minimizar

3.x1 + 2.x2

en cuanto a las restricciones, tenemos que se deben producir no menos de 7700 litros, por lo tanto: x1 + x2  7700 además se debe satisfacer la demanda del cliente de 2750 litros del producto A, entonces: x1  2750 Determinadas la función objetivo y las restricciones, podemos formular el planteo de programación lineal correspondiente a este problema: minimizar

3.x1 + 2.x2

sujeto a x1 + x2  7700 x1

 2750

x1 , x2  0

Producción total Demanda del producto A Restricciones de no negatividad

4

x2

7700

0

2750

7700

x1

la región sombreada es la región de soluciones factibles. Debemos ahora representar una recta de la familia de la función objetivo y deslizarla hasta encontrar la recta con menor ordenada al origen y que tenga intersección con la región de soluciones factibles x2 3.x1 + 2.x2 = c 7700

solución óptima

recta de referencia que se desliza hasta encontrar la solución óptima 0

2750

7700

x1

Los pasos a seguir para resolver un problema de minimización de programación lineal por el método gráfico son: 1.- Trazar las rectas correspondientes a cada una de las restricciones. 2.- Determinar la región de soluciones factibles. 3.- Trazar una recta de la familia de las rectas de la función objetivo. 4.- Desplazar la recta paralela a sí misma hasta el punto de intesección con la región de soluciones factibles de modo que la recta tenga la menor ordenada al origen posible. 5.- El punto de coordenadas (x,y) que se encuentre sobre esta recta y pertenezca a la región de soluciones factibles es una solución óptima.

5

Por último es necesario aclarar que el método gráfico de resolución es sólo aproximado. Además es válido para cuando el problema tiene dos o tres variables (aunque el gráfico con tres variables se torna demasiado complicado).

Actividad de Autoevaluación Nº Formule el planteo de programación lineal y resuelva gráficamente. 1.-El administrador del sistema de suministro de agua de cierta ciudad debe hallar la manera de proporcionar por lo menos 10 millones de galones(mgd)de agua potable por día. El agua se debe tomar de los depósitos locales o de una tubería hacia una población vecina. Los depósitos locales pueden suministrar 5 mgd, cantidad que no puede ser excedida. La tubería debido a su tamaño puede suministrar un máximo de 10 mgd, debido a una cláusula contractual, dicha tubería debe bombear por lo menos 6 mgd. Por último, el costo del agua del depósito es de $ 300 por 1 millón de galones y el costo del agua de la tubería es de $ 500 por 1 millón de galones ¿ En que forma puede el administrador minimizar el costo diario del agua? 2.-Una empresa fabrica dos tipos de productos, para lo que dispone de una persona que trabaja 8 horas, y de un total de 9 kg de materia prima para fabricarlos. Se desea determinar el número de productos a fabricar de cada tipo para obtener el máximo beneficio, sabiendo que el beneficio por cada producto es de 2 mil pesos y 3 mil pesos respectivamente. Además se conocen los datos de la siguiente tabla que representan las horas empleadas para cada producto y la materia prima necesaria en cada uno: Producto A Producto B Horas de 1 2 trabajo Materia 3 1 Prima(kg) 3.- En su consumo diario promedio de alimento, un animal rapaz necesita 10 unidades del alimento A, 12 unidades del alimento B y 12 unidades del alimento c. Estos requerimientos se satisfacen cazando dos tipos de especies. Una presa de la especie I suministra 5, 2 y 1 unidades de los alimentos A, B y C respectivamente. Una presa de la especie II proporciona 1, 2 y 4 unidades de A, B y C respectivamente. Capturar y digerir una presa de la especie I requiere 3 unidades de energía, en promedio. El gasto de energía correspondiente a la especie II es de 2 unidades. ¿ Cuántas presas de cada especie deberá capturar el animal para satisfacer sus necesidades alimenticias, haciendo un gasto mínimo de energía? 4.- Un agricultor desea abonar un campo y sabe que precisa como mínimo 17 kg de fósforo y 8 kg de nitrógeno. El proveedor dispone de dos productos: el producto A contiene 20 por 100 de fósforo(0,2), 30 por 100 de nitrógeno (0,3) y cuesta $300 el kg; el producto B contiene 30 por 100 de fósforo, 10 por 100 de nitrógeno, y cuesta $300 el kg. ¿Qué cantidad ha de comprar de cada producto para que el gasto sea mínimo?

6

 Método Analítico Este método, llamado Método Simplex, no tiene las restricciones del anterior, ya que puede aplicarse a situaciones con cualquier número de variables. Fue desarrollado en 1947 por George Dantzig y es un método matricial (algorítmico) muy apto para programar en computadora. Generalizando el planteo de programación lineal para m restricciones con n variables tendremos:

optimizar

z  c1 x 1  c 2 x 2  . . .  c n x n

sujeta a a 11x 1  a 12x 2  . . .  a 1n x n  b1 a 21x 1  a 22x 2  . . .  a 2n x n  b 2 ........................................... ........................................... a m1x 1  a m2x 2  . . .  a mn x n  b m Para tener el planeo matricial estándar, en primer lugar deben transformarse las inecuaciones en ecuaciones agregando un término o variable en cada una de ellas, que indica la cantidad del recurso en cuestión que no fue utilizado, por lo tanto esta variable será mayor o igual que cero. La designaremos con la letra h dado que indica la holgura o excedente del recurso.

Ejercicio resuelto analíticamente: Haremos el planteo estándar para la situación profesional. Habíamos llegado a la siguiente formulación estándar: maximizar

7 . x + 12 . y = g

sujeta a 2x  3y  24 x  2y  14

x0 ; y0 introduciendo las variables de holgura será: 2x + 3y + h1 x + 2y

= 24 + h2 = 14

x  0 ; y  0 ; h1  0 ; h2  0 ¿què indican h1 y h2 en cada ecuación anterior? agregaremos estas variables a la función objetivo, pero como no aportan ganancia dado que son excedente, las incorporaremos con coeficiente 0. g = 7x + 12y + 0.h1 + 0.h2 El planteo anterior se escribe en forma de tabla llamada Tabla del Simplex

7

x

y

h1

h2

2

3

1

0

24

h1

1

2

0

1

14

h2

7

12

0

0

Variables Básicas

TABLA SIMPLEX

g

Indicadores Como tenemos 2 ecuaciones y 4 incógnitas debemos asignar valores a dos de ellas para obtener el valor de las otras dos. Haremos x = y = 0 de modo que h1 = 24 y h2 = 14, es decir no se produjo nada, por lo tanto todo es excedente. Las variables que no se igualan a cero se llaman variables básicas y son las que figuran en la última columna de la tabla; sus valores se pueden leer en la columna anterior. En la última fila de la tabla se colocan los coeficientes de cada variable en la función objetivo, estos coeficientes reciben el nombre de indicadores ya que nos dirán cuándo hemos arribado a la solución óptima. En el método simplex se deben realizar operaciones elementales por filas en la matriz de la tabla siguiendo los pasos que a continuación se indican hasta que ninguno de los indicadores sea positivo (deben ser 0 o negativos), en ese momento las variables básicas figurarán en la última columna y su valor en la columna a la izquierda de ella. El valor óptimo de la función objetivo lo obtendremos de la celda donde figura g. Paso 1: en primer término se elige cualquier columna de la tabla, que tenga un indicador positivo (preferentemente el mayor). Esta será la columna del pivote. Paso 2: se efectúan los cocientes entre los valores de las variables básicas y los elementos de su fila y de la columna del pivote (siempre que sean mayores que cero). El menor de los cocientes definirá la fila del pivote. De la intersección de la columna del pivote y la fila del pivote, se obtiene este elemento. En nuestro problema:

pivote

x

y

h1

h2

2

3

2

0

24

h1

1

2

0

1

14

h2

7

12

0

0

fila del pivote TABLA SIMPLEX

g

columna del pivote Paso 3: una vez que tenemos el pivote debemos realizar operaciones elementales por filas de modo de igualar el pivote a 1 y hacer cero los demás elementos de su columna. Paso 4: se reemplaza la variable básica de la fila del pivote por la variable no básica correspondiente a la columna del pivote. En nuestro problema obtenemos: 8

x

y

h1

h2

1/2

0

3

–3/2

3

h1

1/2

1

0

1/2

7

y

1

0

–6

0

TABLA SIMPLEX

g – 84

En esta tabla se indica que la variable de holgura h1 vale 3 es decir hay un excedente de horas dedicadas a cortar y pegar de 3 horas. La variable y toma el valor 7 es decir se fabrican 7 centenas de bolsas de consorcio y la ganancia es de $8400. Verifique que los valores obtenidos satisfacen las ecuaciones y las restricciones planteadas. Sin embargo esta no es la solución óptima dado que todavía hay indicadores positivos, por lo tanto debemos repetir el proceso tantas veces como sea necesario hasta que no queden indicadores positivos. Repetimos el proceso para nuestro problema y obtenemos: x

y

h1

h2

1

0

6

–3

6

x

0

1

–3

2

4

y

–6

–3

g – 90

0

0

TABLA SIMPLEX FINAL

Ahora sí, todos los indicadores son no positivos, por lo tanto esta es la tabla simplex final y nos indica los valores de cada una de las variables y el valor que asume la función objetivo. Las variables que no son básicas valen 0 y las básicas tienen su valor en la columna correspondiente de la tabla. Es decir: x = 6 ; y = 4 ; h 1 = 0 ; h2 = 0 y la última fila del diagrama es la ecuación equivalente a la función objetivo: 0.x + 0.y – 6.h1 – 3.h2 = g – 90 y dando a cada variable el valor obtenido 0.6 + 0.4 – 6.0 – 3.0 = g – 90 0 = g – 90 g = 90

9

Resumiendo: I.- Las desigualdades se transforman en igualdades, mediante la introducción de las variables de holgura. II.- Con toda la información se arma un tablero llamado Tabla Simplex, donde se consideran variables básicas las variables de holgura. III.- Se siguen los pasos 1 y 2 para elegir pivote en una columna con un indicador positivo (preferentemente el mayor). IV.- Se siguen los pasos 3 y 4 para pivotear con respecto al elemento elegido en III. V.- Se repiten III y IV hasta obtener un diagrama final, es decir, un diagrama sin indicadores positivos. VI.- La solución se obtiene leyendo el diagrama final: si (g – M) se encuentra en el cuadro inferior derecho, entonces el valor óptimo de g es M. Los valores de las variables básicas aparecen en la columna de la derecha. Todas las variables no básicas son cero.

Actividad de autoevaluación Nº 1.- Resuelva por método simplex, los ejercicios resueltos por método gráfico. 2.- Resuelva el siguiente programa lineal utilizando método simplex max

g = 2,5x1 + 5x2 + x3 + x4

sujeto a x1 + 1,4x2 + 0,2x3 + 0,8x4  1600 2x1 + 2x2 + 1,6x3 + 1,2x1 +

x2 +

x4  1300

x3 + 1,2x4  960

x1, x2, x3, x4  0 3.- Un negocio vende tres tipos de televisores: A, B y C. El beneficio por la venta de cada televisor es de: $ 30 , $ 50 y $ 60 respectivamente según sea del tipo A, B o C. Se sabe además que el Stock disponible es de 300 televisores como máximo por mes. No más de 100 personas pedirán el tipo A. No más de 50 personas pedirán el tipo B y no más de 200 personas pedirán los tipos B y C. a) ¿Cómo puede el negocio satisfacer esa demanda al máximo beneficio? b) ¿A cuánto ascendería ese beneficio máximo? c) Interprete las variables de holgura distintas de cero-si existen- en la solución final. 4.-Una empresa fabrica tres tipos de madera terciada. En los datos que aparecen en seguida se resumen las horas de producción por unidad en cada una de las tres operaciones de producción, adí como también otros datos para el problema. 10

Operaciones (horas) Madera Terciada

Utilidad

I

II

III

por unidad

Grado A

2

2

4

$40

Grado B

5

5

4

$30

Grado X

10

3

2

$20

900

400

Máximo tiempo

600

disponible ¿Cuántas unidades de cada clase de madera se deben fabricar con el fin de optimizar las utilidades?

Respuestas Actividad de Evaluación Nº 1.- x=300; y=300 2.- 55 productos A y 12 productos B 3.- 36 productos m y 24 productos n 4.- debe sembrar 5 hectáreas de maíz y 10 de trigo 5.- a) x=–2; y=1; z=3

b) x=1; y=0; z=–2

6.- x=3; y=2; z=0; t=–1 7.- a) sitema incompatible

7 1 b) sistema indeterminado. Las soluciones son: (1+ z , z, z ) 2 2

Actividad de evaluación Nº 1.- 4 millones de galones por día de los depósitos y 6 millones de la tubería. Costo mínimo $4200 2.- 2 unidades del producto A y 3 del B, con una utilidad máxima de $13000 3.- debe capturar 1 presa de la especie I y 5 de la especie II, con un gasto de energía mínimo de 13 unidades. 4.- debe comprar 10 unidades del producto A y 50 del B. con un gasto mínimo de $18000 Actividad de evaluación Nº 1.- Ver respuestas en apartado anterior anterior 2.- x1=0; x2=650; x3=0; x4=0; h1=690; h2=0; h3=310; g=3250 3.- x1=100; x2=50; x3=150; h1=0; h2=0; h3=0 ganancia = 6400 4.- x1=150; x2=0; x3=0; h1=600; h2=100; h3=0 ganancia = $6000

11