EJERCICIOS DE REPASO

Formulaciones con variables de holgura y exceso

1) Se fabrican dos productos en dos máquinas secuenciales. La siguiente tabla
muestra los tiempos de maquinado en minutos por unidad para los dos productos.
Máquina Producto 1 Producto 2
1 5 3
2 6 2

Las cuotas de producción diarias para los dos productos son de 80 y 60 unidades.
Si no se cumple con estas cuotas se incurre en una penalización de $ 2 por unidad.
Si es necesario, pueden usarse horas extra para satisfacer las cuotas de
producción. Las horas extra tienen un valor de $ 3 por hora.
a) Formule el problema como un modelo de programación lineal.
b) Use la notación sigma y resuelva el modelo usando AMPL/Gurobi
2) Una compañía produce cuatro piezas que requieren el uso de un torno y un taladro
vertical. Las dos máquinas operan diez horas al día. La siguiente tabla proporciona
el tiempo en minutos que se requiere por pieza:
Tiempo de producción en min
Pieza Torno Taladro Vertical
1 5 3
2 6 2
3 4 6
4 7 4

Se pretende, en lo posible, que las dos máquinas operen exactamente la misma

cantidad de tiempo; sin embargo, esto puede resultar imposible, en la práctica una
máquina puede operar un tiempo mayor o menor a la otra. En cualquier caso, se
espera la diferencia en los tiempos de operación no exceda los 30 minutos. La
demanda de cada pieza es de al menos 10 unidades. Además, la cantidad de
unidades de la pieza 1 no puede exceder la de la pieza 2. Formule el problema
como un modelo de programación lineal, use Excel para resolverlo.
3) Una fábrica de ingeniería produce siete productos, en las siguientes máquinas:
cuatro molinos, dos taladros verticales, tres taladros horizontales, un barrenador,
y un cepillo. Cada producto genera cierta contribución al beneficio en $/u. Dicha
contribución, junto con los tiempos de producción (horas) requeridos en cada
proceso se presentan a continuación. Un guion implica que el producto no pasa por
el proceso relacionado.
Prod. 1 Prod. 2 Prod. 3 Prod. 4 Prod. 5 Prod. 6 Prod. 7
Contribución al beneficio 10 6 8 4 11 9 3
Molienda 0.5 0.7 - - 0.3 0.2 0.5
Taladrado vertical 0.1 0.2 - 0.3 - 0.6 -
Taladrado horizontal 0.2 - 0.8 - - - 0.6
Barrenado 0.05 0.03 - 0.07 0.1 - 0.08
Cepillado - - 0.01 - 0.05 - 0.05

En el presente mes (enero) y los siguientes cinco meses, ciertas máquinas serán
desconectadas para mantenimiento, como sigue:
Enero 1 Molino
Febrero 2 Taladros horizontales
Marzo 1 Barrenadora
Abril 1 Taladro vertical
Mayo 1 Molino y un taladro vertical
Junio 1 Cepilladura y un molino horizontal

Existen limitaciones de marketing para la producción de cada producto en cada

mes. Esta información se muestra en la siguiente tabla:
Prod. 1 Prod. 2 Prod. 3 Prod. 4 Prod. 5 Prod. 6 Prod. 7
Enero 500 1000 300 300 800 200 100
Febrero 600 500 200 0 400 300 150
Marzo 300 600 0 0 500 400 100
Abril 200 300 400 500 200 0 100
Mayo 0 100 500 100 1000 300 0
Junio 500 500 100 300 1100 500 60

Es posible almacenar hasta 100 unidades de cada producto por mes a un costo de
$ 0.5 por unidad y por mes. No existe un inventario al inicio del presente mes, pero
se desea tener en inventario 50 unidades de cada tipo de producto al final de junio.
La fábrica trabaja seis días a la semana con dos turnos de ocho horas cada día. Se
pueden horas extra por un valor de $ 2 por hora. En cualquier caso, las horas extra
no deben superar 8 h. El tiempo ocioso tiene un valor de $ 0.8 por hora.
a) Formule el problema como un modelo de programación lineal
b) Realice una formulación usando la notación sigma, use AMPL/Gurobi para
resolverlo
4) Una compañía produce cuatro piezas que requieren el uso de un torno, un taladro
vertical y un taladro horizontal. Las dos máquinas operan diez horas al día. La
siguiente tabla proporciona el tiempo en minutos que se requiere por pieza:
 Tiempo de producción en min
Pieza Torno Taladro Vertical Taladro horizontal
1 5 3 3
2 6 2 2
3 4 6 9
4 7 4 1

Se pretende, en lo posible, que las máquinas operen exactamente la misma

cantidad de tiempo; sin embargo, esto puede resultar imposible, en la práctica una
máquina puede operar un tiempo mayor o menor que las otras. En cualquier caso,
se espera que la diferencia en los tiempos de operación no exceda los 30 minutos.
La demanda de cada pieza es de al menos 10 unidades. Además, la cantidad de
unidades de la pieza 1 no puede exceder la de la pieza 2.

a) Formule el problema como un modelo de programación lineal que le permita

minimizar la suma de las diferencias de los tiempos de procesamiento entre
todas las máquinas, use Excel para resolverlo.
b) Formule un modelo de programación lineal que le permita minimizar la
máxima diferencia entre los tiempos de procesamiento de las diferentes
máquinas.

5) Una compañía manufacturera refina aceites vírgenes y los mezcla. Los aceites
vírgenes son de dos categorías:
Aceites vegetales
VEG1
VEG2
Aceites no vegetales
OIL1
OIL2
OIL3

Cada aceite puede ser comprado para despacho inmediato (enero) o comprado
para la entrega en un mes posterior. Los precios ($/ton) de cada tipo de aceite se
muestran en la siguiente tabla:
VEG1 VEG2 OIL1 OIL2 OIL3
Enero 110 120 130 110 115
Febrero 130 130 110 90 115
Marzo 110 140 130 100 95
Abril 120 110 120 120 125
Mayo 100 120 150 110 105
Junio 90 100 140 80 135

El producto final se vende a 150 $/gal. Los aceites vegetales y no vegetales

requieren diferentes líneas de producción. En cualquier mes no es posible vender
más de 200 ton de aceites vegetales, y no más de 250 ton de aceites no vegetales.
 Suponga que se pierde un 2% del aceite durante el proceso de refinería, y el costo
de esta puede ser ignorado.

Es posible almacenar hasta 1000 ton de cada aceite virgen para su uso posterior,
incurriendo en un costo de almacenamiento de 5 $/ton-mes. Asuma que se puede
subcontratar espacio de almacenamiento extra a un costo de 20 $/ton-mes; sin
embargo, este no puede superar las 200 ton. El producto final ni los aceites
refinados pueden ser almacenados.

Existen restricciones tecnológicas sobre la dureza del producto final. En las

unidades en las que se mida la dureza, esta debe estar entre 3 y 6. La dureza de los
aceites vírgenes es:
VEG1 8,8
VEG2 6,1
OIL1 2,0
OIL2 4,2
OIL3 5,0

En el presente hay 500 ton de cada tipo de aceite virgen en la bodega. Se requiere
que esta cantidad también esté disponible al final de junio. ¿Qué política de
compra y manufactura debería la compañía considerar para maximizar su
beneficio?

Formulaciones equivalentes
1) Considere el siguiente modelo de programación lineal:
min 𝑥1 − 3𝑥2 + 𝑥3 − 𝑥4 ,
s. a. 𝑥1 − 2𝑥2 − 3𝑥3 + 𝑥4 ≤ 10,
2𝑥1 + 𝑥2 + 𝑥3 − 2𝑥4 ≤ 6,
𝑥3 , 𝑥4 ≥ 0.
a) Reformule el problema de manera que todas las variables de decisión sean no
negativas.
b) Resuelva el problema usando Excel.
2) Reformule el siguiente problema como un modelo de programación lineal y
resuélvalo usando Excel.
min −6𝑥1 − 8𝑥2 − 5𝑥3 − 4𝑥4 ,
s. a. 3𝑥1 + 3𝑥2 + 8𝑥3 + 2𝑥4 = 50,
|2𝑥1 + 3𝑥2 + 2𝑥3 + 2𝑥4 | ≤ 20,
𝑥𝑗 ≤ 40, ∀𝑗 = 1, 2, 3, 4.
3) Sea 𝑓(𝑥𝑖 ) una funciones convexas en 𝑥𝑖 , y sean 𝑐𝑖 constantes conocidas. Complete
la siguiente tabla indicando si la formulación correspondiente puede reformularse
mediante una aproximación de 𝑓(𝑥𝑖 ) con segmentos lineales.
 Formulación Pueden usarse segmentos lineales?
𝑛

min ∑ 𝑐𝑖 𝑓(𝑥𝑖 ) Si
𝑖=1
𝑛

min ∑ 𝑐𝑖 𝑓(𝑥𝑖 )
𝑖=1
𝑛

s. a. ∑ 𝑓(𝑥𝑖 ) ≥ 𝑐𝑖 , ∀𝑖
𝑖=1
𝑛

s. a. ∑ 𝑓(𝑥𝑖 ) = 𝑐𝑖 , ∀𝑖
𝑖=1

6) Se sabe que la cantidad 𝑦 depende de la cantidad 𝑥. Se ha recolectado un conjunto

de valores ordenados de dichas cantidades, los cuales se muestran en la siguiente
tabla:
x 0.0 0.5 1.0 1.5 1.9 2.5 3.0 3.5 4.0 4.5
y 1.0 0.9 0.7 1.5 2.0 2.4 3.2 2.0 2.7 3.5

x 5.0 5.5 6.0 6.6 7.0 7.6 8.5 9.0 10.0

y 1.0 4.0 3.6 2.7 5.7 4.6 6.0 6.8 7.3

Se presume que la relación entre 𝑥 e 𝑦 es cuadrática de la forma 𝑦 = 𝑎𝑥 2 + 𝑏𝑥 + 𝑐,

dónde 𝑎, 𝑏 y 𝑐 son desconocidos aún. Encuentre los valores óptimos de los
términos 𝑎, 𝑏 y 𝑐 que minimizan la suma de las desviaciones absolutas entre los
valores observados en la tabla y los valores obtenidos con la ecuación cuadrática.
7) La compañía HMD es productora de leche compra leche cruda de granjeros en dos
regiones: A y B. Los precios, contenidos de grasa, y propiedades de separación de
la leche cruda difieren entre las dos regiones. HMD procesa la leche cruda para
producir crema y leche según especificaciones deseadas para la distribución a los
clientes.

Leche de la región A: El precio de compra en la región A se muestra en la siguiente

figura. La leche cruda de la región A contiene 25% de grasa y cuando se separa
(proceso que cuesta 5 $/gal) se obtienen dos leches, una con 41% de grasa y otra
con 12 % de grasa. Como se muestra en la figura abajo. El volumen de leche se
conserva en todo el proceso de separación.
 Costo
$/gal

Leche
41% grasa
Leche cruda Separación de la
58 25% grasa leche de la región A
Leche
12% grasa
54

500 Galones

Leche de la región B: El costo de compra se muestra en la siguiente gráfica. La leche

de la región B tiene el 15% de grasa y cuando se separa (proceso que cuesta 7
$/gal) se obtienen dos leches, una con 43% d3e grasa y la otra con 5% de grasa.
Como se muestra abajo. El volumen de leche es conservado durante el proceso de
separación.
Costo
$/gal

Leche
43% grasa
Leche cruda Separación de la
42 15% grasa leche de la región B
Leche
5% grasa
38

700 Galones

Proceso de producción: después de que la leche se compra y se recolecta en la

planta, esta se puede mezclar directamente o separar y después mezclar. El
mezclado, para producir crema y leche según especificaciones, no tiene costo. Por
ejemplo, parte de la leche cruda de la región A puede ser separada y después
mezclada, y parte de esta puede ser mezclada directamente (sin haber sido
separada).

Demanda y precio de venta: La demanda y el precio de venta se muestran en la

siguiente tabla. Por ejemplo, toda la crema producida debe tener al menos 40 % de
grasa; esta se vende a 150 $/galón. No más de 250 galones de crema de leche se
pueden vender.

Porcentaje mínimo Demanda máxima Precio de venta

de grasa en galones en $/gal
Crema 40 250 150
Leche 20 2000 70
Asume que la disposición final no tiene costo. Formule un modelo de
programación lineal que le permita a HMD maximizar sus beneficios.