Problema
Una fábrica textil, se dedica a la producción de 5 tipos de telas (i): Seda, Viscosa, Gabardina, Lycra y
Franela. Cada una genera distintas utilidades (ui) y tiene una demanda diaria promedio (di), datos
conocidos a través de un estudio de mercado. Por otra parte, cada tipo de tela (i) está compuesta
por cuatro tipos de materia prima (j): algodón (ai), polyester (pi), lycra (li) y seda (si) en distinta
proporción. La fábrica dispone diariamente de un stock limitado de estos productos (mj). El objetivo
del problema es calcular la cantidad (xi) a producir de cada tipo de tela para que la utilidad diaria de
la fábrica sea máxima. Asumiendo para esto, que tanto la mano de obra como la maquinaria podrán
adaptarse sin inconvenientes a los valores obtenidos.
1. Modele esta situación como un problema de programación lineal.
2. ¿El problema es convexo?, ¿Por qué?
3. Escriba el modelo en AMPL, (archivo .mod)
Problema
Considere el siguiente problema:
máx x1 + x2
s.a. −2 x1 + 5 x2 0
x1 + 4 x2 16
4 x1 − 3 x2 7
x1 0
x2 irrestricta
a) Escriba el problema en forma estándar.
b) Grafique el problema. Identifique la región factible
c) De los puntos que podrían describir una base, cuántos de estos puntos son factibles y cuál es el
óptimo del problema.
d) ¿Cuánto vale la Función Objetivo en el óptimo?
e) ¿Qué particularidad tiene el origen?,
f) ¿Qué bases describen el punto de origen?
g) ¿Es alguna infactible? Compruébelo.
h) ¿Necesitaría realizar Fase I para resolver el problema? ¿Por qué si o no?
j) Aplique Simplex partiendo desde el óptimo encontrado en la parte b).
Problema
Considere una variante del problema de flujo de mínimo costo: en un grafo dirigido G = (V, A),
queremos enviar k unidades de flujo desde el nodo s ∈ V al nodo t ∈ V, existiendo las habituales
restricciones de capacidad - cada arco (i, j) tiene una capacidad bij.
El costo del flujo es la suma de dos componentes:
- Costo por arco, cij, proporcional al flujo a través de un arco, como en el clásico problema de
costo de flujo mínimo. Por ejemplo, si enviamos f unidades de flujo por un arco (i, j), el costo
aportado por este arco es cijf.
- Un costo di por nodo, para todos los nodos (intermedios) i ∈ V \ {s, t} que es contado solamente
cuando el nodo es realmente atravesado por el flujo positivo. Si no hay flujo de entrada (y
tampoco de salida) el nodo en cuestión, no contribuye con costo.
Para el ejemplo descrito en la figura formular un modelo de programación entera para minimizar el
costo total (i.e., el costo de arco más el costo de nodo) de enviar k = 6 unidades de flujo desde el
nodo s = 3 al nodo t = 6. Suponga que todas las capacidades de arco son iguales a 4 (i.e., bij = 4 ∀ (i, j)
∈ A), todos los costos en los arcos son uno, y todos los costos en nodo son iguales a 10.
Traslade el modelo a un archivo en lenguaje AMPL, resuélvalo con CPLEX, informe los resultados.
2 6
4 7
5
3 8
Problema
Considere el problema del flujo de costos mínimo que se muestra abajo. Los números al lado de los
arcos son los costos y los números al lado de las flechas son los suministros/demandas. Todos los
arcos tienen flujo mínimo cero y flujo máximo infinito.
a) Determine tanto el flujo en los arcos como los potenciales en los nodos, correspondiente al árbol
formado por los arcos segmentados.
b) Determine si el árbol es fuertemente factible. Si no, encuentre un árbol fuertemente factible.
c) Solucione el problema usando el algoritmo simplex aplicado a redes. Comience con el árbol
indicado por los arcos segmentados.
Problema
Un granjero viaja con un lobo, un cordero y una caja de coles. En un punto de su viaje, debe cruzar el
rio, pero la barca de qué dispone no soporta más peso que el del granjero y un animal, o el granjero
y la caja. El granjero debe decidir cómo cruzar a los animales y las coles al otro lado del rio, sin dejar
en ningún momento solo al lobo con el cordero ni al cordero con las coles.
Represente la situación como el problema de encontrar el camino más corto entre dos nodos de
una red y resuelva.
Problema
El rompecabezas de la Torre de Hanoi fue inventado por el matemático francés Edouard Lucas en
1883. Se inspiró en una leyenda acerca de un templo hindú donde el rompecabezas fue presentado
a los jóvenes sacerdotes. Al principio de los tiempos, a los sacerdotes se les dieron tres postes y una
pila de 64 discos de oro, cada disco un poco más pequeño que el de debajo. Su misión era transferir
los 64 discos de uno de los tres postes a otro, con dos limitaciones importantes. Sólo podían mover
un disco a la vez, y nunca podían colocar un disco más grande encima de uno más pequeño. Los
sacerdotes trabajaban muy eficientemente, día y noche, moviendo un disco cada segundo. Cuando
terminaran su trabajo, dice la leyenda, el templo se destruiría y el mundo se acabaría.
a) Para el caso de 3 discos se pide plantear el juego como un problema de grafos y encuentre el
menor número de pasos para transferir los discos a otro poste.
b) Aunque la leyenda es interesante, explique cómo puede usted afirmar que el final del mundo
no ocurrirá en cualquier momento.
Problema
Encontrar el camino de valor mínimo entre los vértices 1 y 2
15
2 4 40
100
30 20 10 6
1 60
70
5 50
15
50 25
3 7
20
Problema
Encontrar el flujo máximo entre los vértices 1 y 11
5
2 5 6
9
4 9
8 9
10
1 3 6
5 11
9 2
6 4
9 15
6 3
4 7 10
5 9
9
8
Problema
Encontrar la red (árbol) de expansión mínima
28 9
2 17 4
43
40 29 10
6
37
1 35 33
5
20
15 26 25 46
8
3 7 22
42
Problema
Considerar que una estación depuradora de aguas residuales puede modelizarse por la expresión
discreta:
y(t) – a*y(t-1) = b*u(t-1)
y se quiere determinar el valor de sus parámetros. Por este motivo se ha diseñado un experimento y
se han obtenido los resultados de la tabla, siendo el periodo de adquisición de datos de 2 segundos.
tiempo Entrada Salida
0 -0.0592 -0.0899
2 -1.0106 -0.0799
4 0.6145 -0.1029
6 0.5077 -0.0687
8 1.6924 -0.0427
10 0.5913 0.0193
12 -0.6436 0.0364
14 0.3803 0.0102
16 -1.0091 0.0215
18 -0.0195 -0.0150
20 -0.0482 -0.0136
22 0.0000 -0.0134
24 -0.3179 -0.0116
26 1.0950 -0.0207
28 -1.8740 0.0185
30 0.4282 -0.0463
A partir de los datos y utilizando el método de mínimos cuadrados, estimar el valor de los parámetros
sin utilizar los 4 datos últimos. Utilizar los 4 últimos datos para validar el modelo estimado y
determinar la variancia del error de predicción.