Ejemplos De Programacion Lineal

-.PROGRAMACION LINEAL.-

Problemas resueltos

EJEMPLO 1.

Un expendio de carnes de la ciudad acostumbra preparar la carne para albondigón con una

combinación de carne molida de res y carne molida de cerdo. La carne de res contiene 80%

de carne y 20% de grasa, y le cuesta a la tienda 80$ por libra; la carne de cerdo contiene

68% de carne y 32% de grasa, y cuesta 60$ por libra. ¿Qué cantidad de cada tipo de carne

debe emplear la tienda en cada libra de albondigón, si se desea minimizar el costo y

mantener el contenido de grasa no mayor de 25%?

El objetivo es minimizar el costo (en centavos), z, de una libra de albondigón, donde:

Z = 80 veces el número de libras de carne molida de res, más 60 veces el número de libras de

carne molida de cerdo empleadas.

Si se define:

X1 = número de libras de carne molida de res empleadas en cada libra de albondigón .

X2 = número de libras de carne molida de cerdo empleadas en cada libra de albondigón,

el objetivo se expresa como:

minimícese: z = 80X1 + 60X2 (1)

Cada libra de albondigón tendrá 0.20 x1, libras de grasa provenientes de la carne de res y 0.32 x2

libras de grasa de la carne de cerdo. El contenido total de grasa de una libra de albondigón no

debe ser mayor de 0.25 libras. Entonces:

0.20X1 +0.32X2 <= 0.25 (2)

El número de libras de carne de res y de cerdo empleadas en cada libra de albondigón debe

sumar 1; entonces:

X1 + X2 = l (3)

Finalmente, la tienda no puede usar cantidades negativas de ninguna de las carnes, así que

hay dos restricciones de no negatividad: X1>= 0 y X2 >= 0. Combinando estas condiciones

con (1), (2) y (3), se tiene:

minimícese: z = 80X1 + 60X2

con las condiciones: 0.20X1 + 0.32X2 <= 0.25 (4)

X1 + X2 = 1

con: con todas las variables no negativas

El sistema (4) es un programa lineal. Como sólo hay dos variables, se puede dar

solución gráfica.

EJEMPLO 2.

Una excursionista planea salir de campamento. Hay cinco artículos que desea llevar

consigo, pero entre todos sobrepasan las 60 Ib que considera que puede cargar. Para

auxiliarse en la selección, ha asignado un valor a cada articulo en orden ascendente de

importancia:

Articulo 1 2 3 4 5

Peso, Ib 52 23 35 15 7

Valor 100 60 70 15 15

¿Qué artículos deberá llevar para maximizar el valor total, sin sobrepasar la restricción de

peso?

Haciendo que Xi (i = 1, 2, 3, 4, 5) indique la cantidad a llevar del artículo I, se puede

plantear el objetivo como:

maximícese: z = 1OO X1 + 60 X2 + 70 X3 + 15 X4 + 15 X5 (/)

La restricción de peso es:

52X1 + 23X2 + 35X3 + 15X4 + 7X5 <= 60 (2)

Ya que cada artículo se llevará o no se llevará, cada variable debe ser 1 o 0. Estas condiciones

se cumplirán, si se pide que cada variable sea no negativa, no mayor que 1 y entera.

Combinando estas restricciones con (1) y (2), se tiene el programa matemático:

maximícese: z = 1OO X1 + 60 X2 + 70 X3 + 15 X4 + 15 X5

con las condiciones: 52X1 + 23X2 + 35X3 + 15X4 + 7X5 <= 60

X1 <= 1

X2 <= 1 (3)

X3 <= 1

X4 <= 1

X5 <= 1

con: todas las variables enteras no negativas.

El sistema (3) es un programa entero

EJEMPLO 3.

La Refinería Azteca produce dos tipos de gasolina sin plomo, regular y extra los cuales

vende a su cadena de estaciones de servicio en $12 y $14 por barril, respectivamente.

Ambos tipos se preparan del inventario de la Azteca de petróleo nacional refinado y de

petróleo importado refinado, y deben cumplir con las siguientes especificaciones:

Presión

máxima

de vapor

Octanaje

minimo

Demanda

máxima,

barriles/

semana

Entregas

j mínimas,

barriles/

semana

Regular

Extra

23

23

88

93

100000

20000

50000

5000

Las características del inventario de petróleos refinados son las siguientes:

Presión

de vapor

Octanaje Inventario

barriles

Costo

S/barril

Nacional

Importado

25

15

87

98

40 000

60000

8

15

¿Qué cantidades de los dos petróleos (nacional e importado) deberá mezclar la Azteca en

ambas gasolinas, a fin de maximizar la ganancia semanal?

Haciendo:

X1 barriles de petróleo nacional mezclado en la regular

X2 barriles de petróleo importado mezclado en la regular

X3 barriles de petróleo nacional mezclado en la extra

X4 barriles de petróleo importado mezclado en la extra

Se producirá una cantidad X1 + X2 de gasolina regular y generará un ingreso de 12(X1 + X2),

se producirá una cantidad X3 + X4 de extra y generará un ingreso de 14(X1 + X2). Se usará

una cantidad X1 + X3 de petróleo nacional, a un costo de 8(X1 + X3); se usará una cantidad

X2 + X4 de importado, a un costo de 15(X1 + X3). La ganancia total, z, es el ingreso menos el

costo:

maximícese: z = 12(X1 + X2) + 14(X3 + X4) - 8(X1 + X3) - 15(X2 + X4)

= 4X1-3X2 + 6X3- X4 (1)

Hay limitaciones impuestas a la producción por la demanda, la disponibilidad de suministros

y las especificaciones de la mezcla. Se tiene de las demandas:

X1 + X2 <= 100 000 (demanda máxima de regular) (2)

X3 + X4 <= 20000 (demanda máxima de extra) (3)

X1 + X2 >= 50000 (requerimiento máximo regular) (4)

X3 + X4 >= 5000 (requerimiento mínimo de extra) (5)

De la disponibilidad:

X1 + X3 <= 40000 (nacional) (6)

X2 + X4 <= 60000 (importado) (7)

Los componentes de una mezcla contribuyen al octanaje general, según sus porcentajes por

peso; asimismo para la presión de vapor. Entonces, el octanaje de la regular es:

87 X1/(X1+X2) + 98 X2/(X1+X2)

y el requerimiento de que éste sea de por lo menos 88, lleva

...