MEGAPapeo
MEGAPapeo
MEGAPapeo
Ejercicios
-.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%?
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?
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:
Nacional 25 87 40 000 8
Importado 15 98 60000 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)
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)
EJEMPLO 4.
Minas Universal opera tres minas en West Virginia. El meneral de cada una se separa,
antes de embarcarse, en dos garados. La capacidad diaria de producción de las mismas
así, como sus costos diarios de operación son los siguientes:
Mina I 4 4 20
Mina II 6 4 22
Mina III 1 6 18
EJEMPLO 5.
Una empresa fabrica los productos A, B y C y puede vender todo lo que produzca a los
siguientes precios: A 700; B 3.500; C 7.000.
Producir cada unidad de A necesita 1 hora de trabajo. Producir una unidad de B necesita 2
horas de trabajo, más 2 unidades de A. Producir una unidad de C necesita 3 horas de
trabajo, más 1 unidad de B. Cualquier unidad de A utilizada para producir B, no puede ser
vendida. Similarmente cualquier unidad de B utilizada para producir C, no puede ser
vendida.
Para este período de planificación están disponibles 40 horas de trabajo. Formule y
Construya el modelo Lineal que maximice los ingresos de la empresa.
Variables de descición
X1: Unidades de A producidas en total
X2: Unidades de B producidas en total
X3: Unidades de C producidas en total
X4: Unidades dse A vendidas
X5: Unidades de B vendidas.
Objetivo:
Max 700 X4 + 3.500 X5 + 7.000 X3
Restricciones:
X1 + 2X2 + 3X3 40
X1 =X4 + 2 X2
X2 = X5 + X3
X1, X2, X3,X4, X5 0
EJEMPLO 6.
La Cámara de Industriales de la región periódicamente promueve servicios públicos,
seminarios y programas. Actualmente los planes de promoción para este año están en
marcha. Los medios alternativos para realizar la publicidad así como los costos y la
audiencia estimados por unidad de publicidad, además de la cantidad máxima de unidades
de publicidad en que puede ser usado cada medio se muestran a continuación.
Para lograr un uso balanceado de los medios, la publicidad en radio no debe exceder el
50% del total de unidades de publicidad autorizados. Además la cantidad de unidades
solicitadas en televisión debe ser al menos 10% del total autorizado. El presupuesto total
para promociones se ha limitado a $18.500.
Restricción 5: Publicidad limitada a un máximo de 50% en radio, con relación al total de unidades a
contratar:
X2 <= 0.5 (X1+ X2+ X3)
Finalmente quedará expresada así: - 0.5 X1 + 0.5 X2 - 0.5 X3 <= 0
Restricción 6: La cantidad de unidades solicitadas en televisión debe ser al menos 10% del total
autorizado
X1 >= 0.10 (X1+ X2+ X3)
Finalmente quedará expresada así: 0.9 X1 – 0.1 X2 - 0.1 X3 >= 0
EJEMPLO 1.
Solución:
x1 = número de conejos.
x2 = número de pollos.
x1 , x2 ≥ 0
115
Programación Lineal para la Ingeniería Técnica
x1 x2 x3H x4H
x3H 100 2 3 1 0
H
x 4 180 3 2 0 1
500 300 0 0
x1 x2 x3H x4H
x1 50 1 1/2 1/2 0
x4H 30 0 1/2 -3/2 1
0 50 -250 0
116
Programación Lineal para la Ingeniería Técnica
x1 x2 x3H x4H
x1 20 1 0 2 -1
x2 60 0 1 -3 2
0 0 -100 -100
A
B 3x + 2y = 180
500x + 300y = 0 20x + 10y = 1000
117
Programación Lineal para la Ingeniería Técnica
EJEMPLO 2.
Solución:
x1 , x2 ≥ 0
118
Programación Lineal para la Ingeniería Técnica
119
Programación Lineal para la Ingeniería Técnica
x1* = 800 surtidos tipo 1, x2* = 400 surtidos tipo 2, Z * = 584000 pesetas.
Notamos que al igual que ocurría para el ejemplo 1, este problema puede ser
resuelto también gráficamente, donde idenficamos las variables por
comodidad como x e y (número de surtidos del tipo 1 y del tipo 2
respectivamente). El método de resolución gráfica quedará de la siguiente
manera:
120
Programación Lineal para la Ingeniería Técnica
Por tanto, obtenemos la misma solución: 800 surtidos del tipo 1 y 400 del
tipo 2, con un beneficio máximo de 584000 pesetas.
EJEMPLO 3.
Cierto fabricante produce sillas y mesas para las que requiere la utilización de dos
secciones de producción: la sección de montaje y la sección de pintura. La
producción de una silla requiere 1 hora de trabajo en la sección de montaje y de 2
horas en la de pintura. Por su parte, la fabricación de una mesa precisa de 3 horas
en la sección de montaje y de 1 hora en la de pintura. La sección de montaje sólo
puede estar 9 horas diarias en funcionamiento, mientras que la de pintura sólo 8
horas. El beneficio produciendo mesas es doble que el de sillas. ¿Cuál ha de ser la
producción diaria de mesas y sillas para que el beneficio sea máximo?.
121
Programación Lineal para la Ingeniería Técnica
Solución:
x1 = número de sillas.
x2 = número de mesas.
f (x1 , x2 ) = x1 + 2 x2
x1 , x2 ≥ 0
max f (x1 , x2 ) = x1 + 2 x2
s.a.: x1 + 3 x2 ≤ 9
2 x1 + x2 ≤ 8
x1 , x2 ≥ 0
max x1 + 2x2
s.a.: x1 + 3 x2 + x3H = 9
2 x1 + x2 + x4H = 8
x1 , x2 , x3H , x4H ≥ 0
122
Programación Lineal para la Ingeniería Técnica
x1 = x2 = 0 , x3H = 9 , x4H = 8
x1 x2 x3H x4H
x3H 9 1 3 1 0
H
x 4 8 2 1 0 1
1 2 0 0
x1 x2 x3H x4H
x2 3 1/3 1 1/3 0
x4H 5 5/3 0 -1/3 1
1/3 0 -2/3 0
x1 x2 x3H x4H
x2 2 0 1 2/5 -1/5
x1 3 1 0 -1/5 3/5
0 0 -3/5 -1/5
123
Programación Lineal para la Ingeniería Técnica
C
x + 3y = 9
A
B
2x + y = 8
x + 2y = 0
EJEMPLO 4.
124
Programación Lineal para la Ingeniería Técnica
Solución:
x1 , x2 , x3 ≥ 0
125
Programación Lineal para la Ingeniería Técnica
126
Programación Lineal para la Ingeniería Técnica
EJEMPLO 5.
Solución:
x1 = número de endodoncias.
x2 = número de sesiones de estomatología general.
127
Programación Lineal para la Ingeniería Técnica
x1 , x2 ≥ 0
max 5 x1 + 4 x2
s.a.: 0.75 x1 + 0.75 x2 + x3H = 16
1.5 x1 + x2 + x4H = 24
0.25 x1 + 0.5 x2 + x5H = 8
x1 , x2 , x3H , x4H , x5H ≥ 0
128
Programación Lineal para la Ingeniería Técnica
A 0.25x + 0.5y = 8
B
129
Programación Lineal para la Ingeniería Técnica
EJEMPLO 6.
Solución:
x1 A = toneladas transportadas de I a A.
x1B = toneladas transportadas de I a B.
x2 A = toneladas transportadas de II a A.
x2 B = toneladas transportadas de II a B.
130
Programación Lineal para la Ingeniería Técnica
x1 A , x1B , x2 A , x2 B ≥ 0
131
Programación Lineal para la Ingeniería Técnica
132
Programación Lineal para la Ingeniería Técnica
x1*A = 0 , x1*B = 120 , x2* A = 200 , x2* B = 30 , Z * = 1660 pesetas de coste mínimo.
EJEMPLO 7.
Hallar el coste mínimo de una dieta formada sólo por este tipo de alimentos y que
al menos aporte 3000 calorías y 100 gramos de proteínas.
Solución:
x1 = kilogramos de alimento A.
x2 = kilogramos de alimento B.
f (x1 , x2 ) = 60 x1 + 210 x2
133
Programación Lineal para la Ingeniería Técnica
x1 , x2 ≥ 0
134
Programación Lineal para la Ingeniería Técnica
x1 x2 x3H x4H
x1 2 1 0 -2 1 -60
x2 1/2 0 1 1/2 -1/2 -210
-60 -210 0 0
0 0 -15 -45
Este problema puede ser resuelto aplicando el método gráfico, sin más que
identificar a las variables x e y como las cantidades (kilogramos) de los
alimentos A y B respectivamente. Así pues, obtenemos el siguiente dibujo:
135
Programación Lineal para la Ingeniería Técnica
EJEMPLO 8.
136
Programación Lineal para la Ingeniería Técnica
hectárea de pinos y 4.5 u.m. por cada hectárea de chopos. Las normas de la
explotación obligan a utilizar al menos el 40% del total de la tierra en el cultivo de
los cereales, y como máximo un 35% de la tierra en cualquiera de las otras dos
labores, frutales o reforestación. Calcular cómo ha de repartirse la tierra para
obtener un máximo beneficio.
Solución:
x1 , x2 , x3 , x4 , x5 , x6 ≥ 0
137
Programación Lineal para la Ingeniería Técnica
138
Programación Lineal para la Ingeniería Técnica
139
PROBLEMA N°1
Unos grandes almacenes desean liquidar 200 camisas y 100 pantalones de la temporada anterior.
Para ello lanzan dos ofertas, A y B: la oferta A consiste en un lote de una camisa y un pantalón, que
se vende a 30 €; y la oferta B consiste en un lote de tres camisas y un pantalón, que se vende a 50
€. No se desea ofrecer menos de 20 lotes de la oferta A ni menos de 10 de la B. ¿Cuántos lotes ha
de vender de cada tipo para maximizar la ganancia?
1. Variables de decisión:
i. X1: N° Lotes oferta A.
ii. X2: N° Lotes oferta B.
2. Función Objetivo:
i. Maximizar
3. Restricciones:
i. Restricción del total de camisas
ii. Restricción del total de pantalones
iii. Restricción mínima de lotes oferta A
iv. Restricción mínima de lotes oferta B
v. Restricción de no negatividad
La región solución está representada de color amarillo, y la solución que maximiza el beneficio, se
encuentra en el punto B, donde se deben vender 50 lotes de A y de B para obtener una ganancia
de 4000 euros.
PROBLEMA N°2
Una empresa fabrica dos modelos de mesas para ordenador, M1 y M2. Para su producción se
necesita un trabajo manual de 20 minutos para el modelo M1 y de 30 minutos para el M2; y un
trabajo de máquina de 20 minutos para M1 y de 10 minutos para M2. Se dispone de 100 horas al
mes de trabajo manual y de 80 horas al mes de máquina. Sabiendo que el beneficio por unidad es
de 1,5 y 1 € para M1 y M2, respectivamente, planificar la producción para obtener el máximo
beneficio.
1. Variables de decisión:
i. X1: N° Mesas para ordenador M1 producidas en el mes.
ii. X2: N° Mesas para ordenador M2 producidas en el mes.
2. Función Objetivo:
i. Maximizar
3. Restricciones:
i. Restricción de horas trabajo manual.
ii. Restricción de horas trabajo de máquina.
iii. Restricción de no negatividad.
La región solución está representada de color amarillo, y la solución que maximiza el beneficio, se
encuentra en el punto B, donde se deben producir 210 mesa para ordenador M1 y 60 mesas M2,
obteniendo un beneficio de 375 euros.
PROBLEMA N°3
Una refinería de petróleo tiene dos fuentes de petróleo crudo: Crudo ligero, que cuesta 35 dólares
por barril y crudo pesado a 30 dólares el barril. Con cada barril de crudo ligero, la refinería produce
0,3 barriles de gasolina (G), 0,2 barriles de combustible para calefacción (C) y 0,3 barriles de
combustible para turbinas (T), mientras que con cada barril de crudo pesado produce 0,3 barriles
de G, 0,4 barriles de C y 0,2 barriles de T. La refinería ha contratado el suministro de 900000
barriles de G, 800000 barriles de C y 500000 barriles de T. Hallar las cantidades de crudo ligero y
pesado que debe comprar para poder cubrir sus necesidades al costo mínimo.
1. Variables de decisión:
i. X1: N° Barriles comprados de crudo ligero.
ii. X2: N° Barriles comprados de crudo pesado.
2. Función Objetivo:
i. Minimizar
3. Restricciones:
i. Restricción barriles de G
ii. Restricción barriles de C
iii. Restricción Barriles de T
iv. Restricción de no negatividad
La región solución es no acotada, sin embargo, es acotada para encontrar un mínimo y está
representada de color amarillo, y la solución que minimiza los costos asociados, se encuentra en el
punto A, donde se deben comprar 0 barriles de crudo ligero y 3 millones de barriles de crudo
pesado, obteniendo un costo asociado de 90 millones de dólares.
PROBLEMA N°1
Una empresa, especializada en la fabricación de mobiliario para casas de muñecas, produce cierto
tipo de minimesas y minisillas que vende a 2000 unidades monetarias (u. m.) y 3000 u. m. por cada
artículo, respectivamente. Desea saber cuántas unidades de cada artículo debe fabricar
diariamente un operario para maximizar los ingresos, teniendo las siguientes restricciones:
El número total de unidades de los dos tipos no podrá exceder de cuatro por día y
operario.
Cada minimesa requiere dos horas para su fabricación; cada minisilla, tres horas. La
jornada laboral máxima es de diez horas.
El material utilizado en cada minimesa cuesta 400 u.m. El utilizado en cada minisilla cuesta
200 u.m. Cada operario dispone de 1200 u.m. diarias para material.
Plantear y resolver el anterior problema como un modelo de programación lineal.
1. Variables de decisión:
• X1: N° de minimesas a producir diariamente por operario.
• X2: N° de minisillas a producir diariamente por operario.
2. Función Objetivo:
• Maximizar
3. Restricciones:
• Restricción total por día.
• Restricción total de horas.
• Restricción total de material.
• Restricción de no negatividad
La función objetivo alcanza un valor máximo en A(0,10/3) y en B(2,2), con Z=10000 u.m., esto
quiere decir que la recta de color azul que une los puntos A y B, contiene infinitos valores que
satisfacen el problema, es decir, existen infinitas soluciones. Sin embargo se podría descartar el
punto A debido a que no se puede producir 10/3 de minisillas, ya que se debe producir un valor
entero, pero analizando en cuanto a los valores, el problema presenta infinitas soluciones.
PROBLEMA N°2
La región factible de un problema de programación lineal es la intersección del primer cuadrante
del plano cartesiano con los tres semiplanos definidos por las siguientes inecuaciones:
La región factible acotada queda delimitada por los vértices A= (0,8), B= (10/3, 8/3) y C= (10,0), el
valor mínimo para la función objetivo, se encuentra en el vértice B, donde la función toma el valor
de 80/3, sin embargo, como el signo de las restricciones es estricto (< o >), nos dice que el valor de
B es una solución aproximada, esto quiere decir, que el valor real de optimización se encuentra en
los límites hacia la derecha o la izquierda de ese punto, falta moverse un valor infinitesimal
alrededor de ese punto para estar en la solución correcta, pero en términos generales se toma el
valor de B como óptimo.
PROBLEMA N°3
Una compañía tiene dos minas: la mina A produce diariamente 1 tonelada de carbón de antracita
de alta calidad, 2 toneladas de carbón de calidad media y 4 toneladas de carbón de baja calidad; la
mina B produce 2 toneladas de cada una de las tres clases. Esta compañía necesita 70 toneladas
de carbón de alta calidad, 130 de calidad media y 150 de baja calidad. Los gastos diarios de la mina
A ascienden a 500 u.m. y los de la mina B a 750 u.m. ¿Cuántos días deberán trabajar en cada mina
para que la función de coste sea mínima?
Plantear y resolver el anterior problema como un modelo de programación lineal.
1. Variables de decisión:
• X1: N° de días a explotar la mina A.
• X2: N° de días a explotar la mina B.
2. Función Objetivo:
• Minimizar
3. Restricciones:
• Restricción carbón de alta calidad.
• Restricción carbón de media calidad.
• Restricción carbón de baja calidad.
• Restricción de no negatividad
Se puede apreciar gráficamente que la región factible es no acotada, esto quiere decir, que para
encontrar un valor máximo no existe solución, sin embargo, en este problema se quiere
determinar un valor donde la función se minimice, ese valor se encuentra en el punto C= (60, 5),
donde para que la función Z tome el valor mínimo (Z= 33750 u.m.) se debe explotar la mina A 60
días, mientras que la mina B se debe explotar 5 días.
-Teoría y Problemas resueltos de Programación
Lineal
Objetivos:
1.) Desigualdades.
Una inecuación lineal con dos incógnitas es una expresión de alguna de las
formas siguientes:
Ejemplo:
Se llama conjunto convexo a una región del plano tal que para dos puntos
cualesquiera de la misma, el segmento que los une está íntegramente
contenido en dicha región. Como casos particulares, un conjunto convexo
puede quedar reducido a una recta, a una semirrecta, a un segmento, a un
punto o al conjunto vacío.
Ejemplo:
La recta:
x+y-1=0 corta al eje X (hacemos y=0) en (1, 0) y al eje Y (hacemos x=0) en (0,
1)
La recta :
La recta:
Se define una función lineal con dos variables como una expresión de la
forma f(x, y) = ax + by.
Ejemplo:
siendo, pues
A intersección de r y t:
B intersección de s y t:
C intersección de r y s:
Acero Aluminio
Paseo 1 3
Montaña 2 2
Función objetivo:
Restricciones:
Zona
de soluciones factibles:
Vértices del recinto (soluciones básicas):
A(0, 40)
B intersección de r y s:
C(40,0)
x= n: de plazas de fumadores.
y= n: de plazas de no fumadores.
La Función objetivo:
Restricciones:
Vértices:
A(0, 60)
B intersección de r y s:
C(90, 0)
A intersección de u,t:
B intersección de r,u:
C intersección de r,s:
D intersección de s,t:
f(x, y)=5x+7y
Las restricciones:
La zona de soluciones factibles es:
Vértices:
A(0, 100)
B intersección de s,t:
C intersección de r,t:
D (120, 0)
Y las restricciones:
A(0, 625)
B intersección de r,s:
C(700, 0)
x= número de trajes.
y= número de vestidos
Función objetivo:
Restricciones:
Vértices:
A(0, 40)
B intersección de r y s:
C(40, 0)
A intersección de r,s:
B intersección de r,t:
C (0, 0)
A intersección de r,t:
B intersección de t,u:
D(7, 0)
E(2, 0)
PROBLEMA #10 Una refinería de petróleo tiene dos fuentes de petróleo crudo:
crudo ligero, que cuesta 35 dólares por barril y crudo pesado a 30 dólares el
barril. Con cada barril de crudo ligero, la refinería produce 0,3 barriles de
gasolina (G), 0,2 barriles de combustible para calefacción (C) y 0,3 barriles de
combustible para turbinas (T), mientras que con cada barril de crudo pesado
produce 0,3 barriles de G, 0,4 barriles de C y 0,2 barriles de T. La refinería ha
contratado el suministro de 900000 barriles de G, 800000 barriles de C y
500000 barriles de T. Hallar las cantidades de crudo ligero y pesado que debe
comprar para poder cubrir sus necesidades al costo mínimo.
G C T
Ligero 0,3 0,2 0,3
Pesado 0,3 0,4 0,2
f(x, y)=35x+30y
Las restricciones:
A(0, 3000000)
B intersección de r,s:
C(4000000, 0)
Carpintería Acabado
Soldados 1 2
Trenes 1 1
Las restricciones:
A(0, 80)
B intersección de r,s:
C intersección de s,t:
D(40, 0).
En los que la función objetivo vale:
f(x, y)=ax+2ay
Y las restricciones:
La zona de soluciones factibles es:
A(0, 45000)
B(0, 30000)
C intersección de r y s:
Hay que fabricar, pues, 10.000 yogures de limón y 20.000 yogures de fresa
para un costo mínimo de 50.000a bolívares.
f(x, y)=6x+3y
Las restricciones:
B intersección de r,s:
PROBLEMA #14 Un pastelero fabrica dos tipos de tartas T1 y T2, para lo que
usa tres ingredientes A, B y C. Dispone de 150 kgs. de A, 90 kgs. de B y 150
kgs. de C. Para fabricar una tarta T1 debe mezclar 1 kgs. de A, 1 kgs. de B y 2
kgs. de C, mientras que para hacer una tarta T2 se necesitan 5 kgs. de A, 2
kgs. de B y 1 kgs. de C.
x= número de tartas T1
y= número de tartas T2
f(x, y)=1000x+2300y
Restricciones:
Vértices:
A(0, 30)
B intersección de r.s:
C intersección de s,t:
D (75, 0)
f(x, y)=1500x+py
El menor valor que cumple esta condición es p=3000 Bs. y con él el beneficio
sería:
Bolívares
Función objetivo:
Restricciones:
Vértices:
A(0, 7)
B intersección de s,t:
C intersección de r,s:
D (3,0)
PROBLEMA #17 La empresa FORD lanza una oferta especial en dos de sus
modelos, ofreciendo el modelo A a un precio de 1,5 millones de bolívares, y el
modelo B en 2 millones. La oferta está limitada por las existencias, que son 20
autos del modelo A y 10 del B, queriendo vender, al menos, tantas unidades de
A como de B. Por otra parte, para cubrir gastos de esa campaña, los ingresos
obtenidos en ella deben ser, al menos de 6 millones de bolívares ¿Cuántos
automóviles de cada modelo deberá vender para maximizar sus ingresos?
Función objetivo:
Restricciones:
Vértices:
A intersección de s,t:
B Intersección de r,s:
C(20, 0)
D(4, 0)
Valores de la función:
Siendo:
Las restricciones son:
Las coordenadas de los vértices son: A(3,0) ; B(5.5, 2.5) ; C(2.5, 5.5) ; D(0,3) y
O(0,0)
f(A) = 2000 millones de ptas. ; f(B) = 3500 millones de pesetas; f(C) = 4000
millones de pesetas ; f(D) = 3000 millones de pesetas y f(O)= 0 ptas.
b) Maximiza la función Z = x + y
a)
x+y 2
-2 x 2
-1 y 2
1. Disponemos de 210.000 euros para invertir en bolsa. Nos recomiendan
dos tipos de acciones. Las del tipo A, que rinden el 10% y las del tipo B, que
rinden el 8%. Decidimos invertir un máximo de 130.000 euros en las del tipo
A y como mínimo 60.000 en las del tipo B. Además queremos que la inversión
en las del tipo A sea menor que el doble de la inversión en B. ¿Cuál tiene que
ser la distribución de la inversión para obtener el máximo interés anual?
Solución
Es un problema de programación lineal.
Llamamos x a la cantidad que invertimos en acciones de tipo A
Llamamos y a la cantidad que invertimos en acciones de tipo B
inversión rendimiento
Tipo A x 0,1x
Tipo B y 0,08y
210000 0,1x+0,08y
Condiciones que deben cumplirse (restricciones):
R1
R2
R3
R4
Dibujamos las rectas auxiliares asociadas a las restricciones para conseguir
la región factible (conjunto de puntos que cumplen esas condiciones)
r1 r2 (paralela a OY) r3(paralela a OX) r4
X y x y x y x y
0 210000 130000 0 0 60000 0 0
210000 0 130000 65000
La región factible es la pintada de amarillo, de vértices A, B, C, D y E
A(0, 60000), B(120000, 60000), C(130000, 65000), D(130000, 80000) y
E(0, 210000)
La función objetivo es;
F(x, y)= 0,1x+0,08y
Si dibujamos la curva F(x, y) =0 (en rojo) y la desplazamos se puede
comprobar gráficamente que el vértice mas alejado es el D, y por tanto es
la solución óptima.
Comprobarlo analíticamente (es decir comprobar que el valor máximo de la
función objetivo, F, se alcanza en el vértice D)
2. En una pastelería se hacen dos tipos de tartas: Vienesa y Real. Cada tarta
Vienesa necesita un cuarto de relleno por cada Kg. de bizcocho y produce un
beneficio de 250 Pts, mientras que una tarta Real necesita medio Kg. de
relleno por cada Kg. de bizcocho y produce 400 Ptas. de beneficio. En la
pastelería se pueden hacer diariamente hasta 150 Kg. de bizcocho y 50 Kg.
de relleno, aunque por problemas de maquinaria no pueden hacer mas de 125
tartas de cada tipo. ¿Cuántas tartas Vienesas y cuantas Reales deben
vender al día para que sea máximo el beneficio?
Solución
En primer lugar hacemos una tabla para organizar los datos:
Los vértices son (0, 8), (0, 9) y el (5, 4), este último es el punto de
intersección de las rectas r3 y r4
por reducción
restando ambas ecuaciones se tiene x =5 y sustituyendo en la 1ª ecuación, y
=4
Resolviendo gráficamente se llega a que el punto (5, 4) es la solución del
problema. La solución óptima .
Comprobarlo sustituyendo en F(x, y) todos los vértices y que este es el que
da menor valor (método analítico).
4. 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 coste
diario de la operación es de 2000 euros en cada mina ¿cuántos días debe
trabajar cada mina para que el coste sea mínimo?.
Solución
Organizamos los datos en una tabla:
días Alta Calidad Baja calidad Coste diario
calidad media
Mina A x 1x 3x 5x 2000x
Mina B y 2y 2y 2y 2000y
80 160 200
La función objetivo C(x, y)=2000x + 2000y
Las restricciones:
La región factible:
INVESTIGACION DE OPERACIONES
OBJETIVOS:
GENERAL:
Conocer y aplicar los las principales características de las Líneas de
Espera de un servidor con uno o múltiples canales de servicio.
ESPECIFICOS
1. Conocer los principales componentes de un Sistema de Líneas de
Espera
2. Calcular indicadores de rendimiento para un Sistema de una Línea
de Espera y un Servidor
3. Calcular indicadores de rendimiento para un Sistema de una Línea
de Espera y Servidores Múltiples
CONDUCTA DE ENTRADA:
1.
3.
TEMATICA
DEFINICIONES
Población
Sistema
Disciplina de colas
Proceso de servicio
Ejemplo
Supongamos un lavadero automático de vehículos, que cuenta con
una máquina para estos propósitos. A solicitar el servicio llegan en
promedio 15 vehículos / hora y la máquina puede lavar un vehículo en
3 minutos. Calcule todos los indicadores de rendimiento.
1. Probabilidad de que no
haya clientes en el sistema
2. Número promedio
de clientes en la cola
3. Tiempo promedio
de espera en la cola
Tiempo promedio
en el sistema
7. Utilización
Ejemplo
Supongamos el mismo lavadero automático de vehículos, pero que
cuenta ahora con dos máquinas. A solicitar el servicio llegan en
promedio 36 vehículos / hora y cada máquina puede lavar un vehículo
en 3 minutos. Calcule todos los indicadores de rendimiento.
λ = 36 vehículos / hora
1/µ = 3 minutos / vehículo, de donde µ = 20 vehículos / hora
n<=c
n Pn
0 0.0526
1 0.0947
2 0.0852
n>c
3 0.0767
etc. Etc.
UTILIZACION (U)
EJERCICIOS
BIBLIOGRAFÍA
KAMLES, H.
Investigación de Operaciones, el arte de la toma de decisiones
Prentice Hall, 2002
TAHA, Hamdy A.
Investigación de Operaciones
Alfaomega, 2004
Investigación Operativa
Ingenierı́a Informática, UC3M
Curso 08/09
Solución.
∞
X
L= npn
n=0
X∞
= nρn (1 − ρ)
n=0
∞
X ∞
X
n
= nρ − nρn+1
n=0 n=0
∞
X
= ρn
n=1
X∞
=ρ ρn
n=0
ρ
= .
1−ρ
ρ2
Lq = .
1−ρ
Solución.
ρ ρ2
Lq = λWq = λ = .
µ(1 − ρ) 1−ρ
3. En un servidor de la universidad se mandan programas de ordenador para ser ejecutados. Los progra-
mas llegan al servidor con una tasa de 10 por minuto. El tiempo medio de ejecución de cada programa
es de 5 segundos y tanto los tiempos entre llegadas como los tiempos de ejecución se distribuyen ex-
ponencialmente.
1
b) ¿Cuál es el tiempo esperado total de salida de un programa?
c) ¿Cuál es el número medio de programas esperando en la cola del sistema?
Solución. El sistema es M/M/1 con λ = 10 trabajos por minuto y µ = 12 trabajos por minuto. Se
asumirá que el sistema es abierto y que la capacidad es infinita. Como ρ = 10/12 < 1, el sistema
alcanzará el estado estacionario y se pueden usar las fórmulas obtenidas en clase.
a) El servidor estará desocupado 1 − 5/6 = 1/6 del total, esto es, 10 segundos cada minuto (ya
que el ordenador está ocupado 5 × 10 = 50 segundos por minuto).
1 1
b) Tiempo medio total es W = µ(1−ρ)
= 12(1−5/6)
= 1/2 minuto por programa.
ρ2
c) El número medio de programas esperando en la cola es Lq = 1−ρ
= 4.16 trabajos.
4. La ventanilla de un banco realiza las transacciones en un tiempo medio de 2 minutos. los clientes
llegan con una tasa media de 20 clientes a la hora. Si se supone que las llegadas siguen un proceso de
Poisson y el tiempo de servicio es exponencial, determina
5. Una tienda de alimentación es atendida por una persona. Aparentemente el patrón de llegadas de
clientes durante los sábados se comporta siguiendo un proceso de Poisson con una tasa de llegadas de
10 personas por hora. A los clientes se les atiende siguiendo un orden tipo FIFO y debido al prestigio
de la tienda, una vez que llegan están dispuestos a esperar el servicio. Se estima que el tiempo que
se tarda en atender a un cliente se distribuye exponencialmente, con un tiempo medio de 4 minutos.
Determina:
2
6. En una fábrica existe una oficina de la Seguridad Social a la que los obreros tienen acceso durante
las horas de trabajo. El jefe de personal, que ha observado la afluencia de obreros a la ventanilla,
ha solicitado que se haga un estudio relativo al funcionamiento de este servicio. Se designa a un
especialista para que determine el tiempo medio de espera de los obreros en la cola y la duración
media de la conversación que cada uno mantiene con el empleado de la ventanilla. Este analista
llega a la conclusión de que durante la primera y la última media hora de la jornada la afluencia es
muy reducida y fluctuante, pero que durante el resto de la jornada el fenómeno se puede considerar
estacionario. Del análisis de 100 periodos de 5 minutos, sucesivos o no, pero situados en la fase
estacionaria, se dedujo que el número medio de obreros que acudı́an a la ventanilla era de 1.25 por
periodo y que el tiempo entre llegadas seguı́a una distribución exponencial. Un estudio similar sobre
la duración de las conversaciones, llevó a la conclusión de que se distribuı́an exponencialmente con
duración media de 3.33 minutos. Determina:
a) Lq = 4.166 obreros.
b) Wq = 16.66 minutos.
c) Durante cada hora hay, en media, Lq = 4.166 clientes haciendo cola. Es decir, el coste horario
por obreros ociosos es de 4.166 × 400 = 1666.66 euro. Por otro lado, 1 − ρ = 0.166, de forma
que el coste del tiempo que el oficinista está ocioso es de 250 × 0.166 = 41.5 euros horarios,
que es mucho inferior.
Si se pusiera otra ventanilla, el sistema serı́a M/M/2. En ese caso, p0 = 0.411 y p1 = 0.34, de
forma que el tiempo de oficinista que se perderı́a cada hora serı́a, en media, 2p0 + p1 = 1.166
horas. Lo que supone un coste de 291.5 euros cada hora. Por otro lado, cada hora habrı́a, en
media, Lq = 1.01 obreros en la cola. De forma que el tiempo perdido por los obreros tendria un
coste de 400 × 1.01 = 404 euros la hora.
La suma de los dos costes es mucho menor en este segundo caso, de forma que sı́ serı́a rentable
poner otra ventanilla.
7. Una entidad bancaria considera la posibilidad de instalar una red de cajeros en una de sus oficinas.
Dado que se desconoce la afluencia de público que va a demandar dicho servicio, coloca un único
cajero durante un mes. Diariamente se recogen datos sobre los tiempos de llegadas de los clientes,
ası́ como de los tiempos de servicio. Suponiendo que la sucursal se encuentra emplazada en un barrio
dende no existe otro servicio semejante, el cliente que llega prefiere esperar a poder utilizar el cajero,
cuando éste esté ocupado.
Tras el oportuno análisis de los datos recogidos, se estima que: (i) las llegadas siguen un proceso de
Poisson; (ii) la distribución del tiempo de servicio es exponencial; (iii) el tiempo medio transcurrido
3
entre dos llegadas consecutivas es de 7.5 minutos; (iv) el tiempo medio de servicio es de 5 minutos
por cliente.
Calcula:
a) Wq = 10 minutos.
b) El número medio de las colas es de Lq = 1.33 personas, y la probabilidad de que haya al menos
dos personas en el sistema es de 1 − p0 − p1 = 4/9.
8. Los trabajadores de una fábrica tienen que llevar su trabajo al departamento de control de calidad
antes de que el producto llegue al final del proceso de producción. Hay un gran número de empleados
y las llegadas son aproximadamente de 20 por hora, siguiendo un proceso de Poisson. El tiempo para
inspeccionar una pieza sigue una distribución exponencial de media 4 minutos. Calcula el número
medio de trabajadores en el control de calidad si hay:
a) 2 inspectores.
b) 3 inspectores.
Solución.
9. Un avión tarda unos 4 minutos de media en aterrizar a partir del momento en que la torre de control
le da la señal de aterrizaje. Si las llegadas de los aviones se producen por término medio, a razón de 8
por hora y siguiendo un proceso de Poisson, ¿cuánto va a esperar el piloto dando vueltas al aeropuerto
antes de recibir la señal de tierra?
Solución. Sistema M/M/1 con λ = 8 y µ = 15. Por tanto, Wq = 4.56 minutos.
10. Una compañı́a de ordenadores posee un ordenador central al que pueden acceder los clientes a través
de unos terminales (de distintos tipos) que se alquilan. Un cliente desea determinar la velocidad
óptima del terminal que deberı́a alquilar. Los trabajos del cliente se generan según un proceso de
Poisson con una tasa de 50 programas por dı́a de 8 horas. El tamaño medio de un programa es de
1000 sentencias. Se sabe que el tiempo de lectura de sentencias es exponencial. El cliente estima
en 10 euros el coste de retrasar un programa un dı́a. La compañı́a estima que una velocidad de 100
sentencias por minuto, y cualquier aumento semejante, incrementa el precio del alquiler diario del
terminal en 100 euros. Determina la velocidad óptima del terminal.
Solución. Sistema M/M/1 con λ = 50 programas mandados al dı́a y µ =? programas ejecutados
por dı́a (variable de decisión). El coste por retrasar un programa un dı́a es de 10 euros. Como 100
4
sentencias por minuto equivalen a 48 programas por dı́a, entonces el coste por programa por unidad
de incremento de µ y por dı́a es de 100/48 = 2.083 euros.
Por tanto, el coste total es igual a
10L + 2.083µ
que se maximiza en µ = 52.19 programas leı́dos al dı́a.
11. Una compañı́a ferroviaria pinta sus propios vagones, según se vayan necesitando, en sus propios
talleres donde se pinta a mano de uno en uno con una velocidad que se distribuye según una expo-
nencial de media un cada 4 horas y un coste anual de 4 millones de euros. Se ha determinado que los
vagones pueden llegar según un proceso de Poisson de media un cada 5 horas. Además el coste por
cada vagón que no está activo es de 500 euros la hora.
Se plantean otras dos posibilidades. Una es encargar dicho trabajo a una empresa de pintura que lo
harı́a con aerosol con el consiguiente ahorro de tiempo. Sin embargo el presupuesto para esta segunda
alternativa es de 10 millones de euros anuales. En este caso, el proceso se aproxima a uno de Poisson
con una tasa de uno cada 3 horas. La otra opción es poner otro taller exactamente igual al que hay
actualmente, con igual tasa de servicio y coste anual que permita pintar dos vagones a la vez.
En todos los casos el trabajo se considera ininterrumpido, esto es, se trabajan 24 × 365 = 8760 horas
anuales. ¿Cuál de los tres procedimientos es preferible?
Solución. Taller con pintura a mano: sistema M/M/1 con λ = 1/5 y µ = 1/4 vagones/hora. Por
tanto,
4 × 106
CT = 500L + = 2456.62 euros por vagón.
8760
Taller con pintura con aerosol: sistema M/M/1 con λ = 1/5 y µ = 1/3 vagones/hora. Por tanto,
10 × 106
CT = 500L + = 1891.55 euros por vagón.
8760
Dos talleres con pintura a mano: sistema M/M/2 con λ = 1/5 y µ = 1/4 vagones/hora. Por tanto,
8 × 106
CT = 500L + = 1389.43 euros por vagón.
8760
Coste anual por hora = 2456.62 . Coste con aerosol = 1891.55 . Coste con dos servidores = 1389.43 .
Por tanto, es preferible poner dos talleres.
12. Una empresa de reparación de ordenadores recibe una media de 10 solicitudes de reparación al dı́a,
que se distribuyen según un proceso de Poisson. Se supone que µ es la velocidad de reparación de
la persona reparadora en ordenadores/dı́a, y el tiempo de reparación es exponencial. Cada unidad de
velocidad de reparación supone un coste de 100 euros por semana. Además, se ha estimado que el
coste de tener ordenadores no reparados supone 200 euros por ordenador y semana, siendo este coste
proporcional al tiempo. Suponiendo que una semana tiene cinco dı́as laborables, se pide:
5
Solución. Sistema M/M/1 con λ = 10 y µ =?.
a) El coste total es 20µ + 40L euros diarios. Por tanto, la tasa óptima es de 14.47 ordenadores por
dı́a, con un coste diario de 378.43225 euros.
b) En este caso se trata de un sistema M/M/2. Por tanto, el coste diario de 395.184 euros, que es
peor que el anterior.
13. Una base de mantenimiento de aviones dispone de recursos para revisar únicamente un motor de
avión a la vez. Por tanto, para devolver los aviones lo antes posible, la polı́tica que se sigue consiste
en aplazar la revisión de los 4 motores de cada avión. En otras palabras, solamente se revisa un
motor del avión cada vez que un avión llega a la base. Con esta polı́tica, los aviones llegan según
una distribución de Poisson de tasa media uno al dı́a. El tiempo requerido para revisar un motor (una
vez que se empieza el trabajo) tiene una distribución exponencial de media 1/2 dı́a. Se ha hecho
una propuesta para cambiar la polı́tica de revisión de manera que los 4 motores se revisen de forma
consecutiva cada vez que un avión llegue a la base. A pesar de que ello supondrı́a cuadruplicar el
tiempo esperado de servicio, cada avión necesitarı́a ser revisado únicamente con una frecuencia 4
veces menor. Utilizar la teorı́a de colas para comparar las 2 alternativas.
Solución. En los dos casos se trata de colas M/M/1, puesto que tanto los tiempos entre llegadas como
los tiempos de servicio son variables aleatorias con distribución exponencial.
En la situación actual, la tasa de llegadas es λ = 1 avión al dı́a y la tasa de servicio es µ = 2 aviones
al dı́a. Con estos parámetros, ρ = 0.5 < 1, y por tanto existe el estado estacionario. Los valores de
las cantidades de interés son:
Si se siguiera la propuesta para cambiar la polı́tica, la cola seguiria siendo una M/M/1, pero ahora
las tasas de llegada y de servicio serian λ = 0.25 aviones al dı́a, y µ = 0.5 aviones al dı́a, respec-
tivamente. En este caso, ρ sigue siendo 0.5 y por tanto sigue existiendo el estado estacionario. Los
valores de las cantidades de interés son:
Con la configuración propuesta, cada vez que un avión vaya a ser revisado pasará en el sistema
el cuádruple del tiempo que pasaba con el sistema anterior, pero como cada avión va a ir con una
frecuencia cuatro veces menor, el tiempo perdido en el taller a largo plazo va a ser igual. En este caso,
la decisión entre una configuración y la otra deberı́a ser tomada en función de los costes de operación.