El problema de Programación Dinámica

En matemáticas aplicadas, tenemos en ocasiones sistemas dinámicos como este

x_{k+1}=f_k(x_k,u_k,w_k), k=0,1,...,N-1

Donde k es el indicador de tiempo, en un periodo finito preestablecido que va desde cero hasta N. Aquí x_k es la variable de estado del sistema en el periodo k, u_k es la variable de control en este mismo periodo y w_k es un parámetro aleatorio.

En breve, lo que deseamos es controlar una función de costo

\mathbb{E} \left\{ g_N(x_N)+\sum_{k=0}^{N-1} g_k(x_k,u_k,w_k)\right\}

Note que estamos usando el operador de la esperanza y que hemos dividido las funciones de costo de los periodos desde 0 hasta N-1, dejando al final un costo terminal.

Un ejemplo clásico de la programación dinámica es el del control de inventarios. Si la variable de estado denota el inventario disponible en cada periodo, la de control son las órdenes pedidas y otorgadas en el mismo periodo y el parámetro aleatorio es la demanda en ese momento del tiempo (asumimos que w_0,w_1,...,w_{N-1} son variables aleatorias independientes entre si). Por lo tanto el sistema evoluciona de acuerdo a la siguiente ecuación en diferencias:

x_{k+1}=x_k+u_k-w_k

El costo se divide en dos partes, que consisten en un costo de que mantener inventarios en existencia o que haya faltante en los inventarios (el costo de oportunidad), y el costo de las órdenes mismas de inventario. Por lo tanto el objetivo es minimizar

\mathbb{E} \left\{ R(x_N)+\sum_{k=0}^{N-1} (r(x_k) + c u_k) \right\}

Con la limitante de que no pueden haber pedidos negativos, es decir, no se pueden regresar inventarios para reducir costos.

El problema es interesante porque no se trata de encontrar un número mínimo, sino mas bien una regla que optimice el sistema. Puesto de otra manera, tratamos de encontrar una secuencias de reglas o funciones \mu_k, k=0,...,N-1 que mapee de la variable de estado al control (esto tiene sentido porque el control depende de la retroalimentación que recibe del estado). A esta secuencia de reglas \pi=\{\mu_0,...,\mu_{N-1}\} se le conoce como política (en inglés es policy, pero aún no me acaba de convencer traducirlo literalmente de esta manera).

Para cada \pi, el costo correspondiente para un stock inicial de x_0 fijo es

J_\pi(x_0) =\mathbb{E} \left\{R(x_N)+\sum_{k=0}^{N-1}(r(x_k)+x\mu_x(x_k))\right\}

Queremos minimizar J_\pi(x_0) para un estado inicial x_0 dado sobre todas las políticas posibles. Sea S_k un umbral de stock aceptable, se puede demostrar que la secuencia de reglas óptimas son aquellas que igualan a S_k-x_k si x_k<S_k, y 0 en cualquier otra situación.

Bibliografia

Bertsekas, D. P., & Bertsekas, D. P. (1995). Dynamic programming and optimal control (Vol. 1, No. 2). Belmont, MA: Athena Scientific.

Matemáticas: ¿Cuál es tu problema?

Si me lo preguntan a mi, gran parte del problema con la enseñanza de las matemáticas deriva está en la forma en la que se enseña. En su libro “Math and love”, Edward Frenkel dice -y estoy parafraseando -que no es sorprendente que a los chicos no les gusten las matemáticas, cuando se les enseña sólo una parte muy técnica y, francamente, aburrida, de estas. Es como si tomando una clase de arte, sólo se les enseñara a pintar un cerco “porque es lo que van a necesitar en la vida” en vez de mostrarles las obras de Picasso, Rodin, Van Gogh, Andy Warhol, Da Vinci. Es verdad, no todos vamos a poder hacer un cuadro como Van Gogh en nuestras vidas con un entrenamiento básico, pero el conocer de esto es lo que nos va a inspirar. Y, creo yo, la educación tanto básica como especializada debe tener como objetivo central el inspirar, más que entrenar. Y esto es cierto simplemente porque a la larga resulta más eficiente inspirar que entrenar. Entrenando, adoctrinando, el conocimiento que se deja de practicar se ha perdido en seis meses o menos, mientras que cuando se inspira, es posible esperar que el mismo alumno indague más allá de lo que se vio en clase.

La capacidad de abstracción es muy importante para el ser humano y no debe ser despreciada. Sobre todo es importante no dejar que los alumnos confundan matemáticas y pensamiento abstracto con rigidez y mentalidad cuadrada. Es importante el uso del razonamiento lógico, pero es mucho más importante la imaginación y la creatividad para poder entender con facilidad conceptos abstractos. En matemáticas es necesario poder visualizar cosas abstractas, pero para eso se requiere imaginación. Un ejemplo está en las funcionales y en el control óptimo, donde hablamos de funciones de funciones. René Descartes hizo un trabajo increíble y maravilloso al descubrir la relación geométrica que nos ayuda a representar en planos bidimensionales las funciones con simples líneas en un plano cartesiano. Si queremos encontrar un máximo o mínimo en un plano, es fácil visualizarlo (el punto que está más cerca del techo o del piso en el pizarrón), pero cuando hablamos de funcionales es posible imaginar un terreno irregular (y usar la imaginación es mas económico en tiempo que hacer un modelo físico para representarlo, aunque es aún posible  y algún profesor tal vez lo crea buena idea) . Imaginando que si estamos en un punto alto ganamos puntos, y que lo estamos recorriendo en un go-kart, estamos optimizando si en cada momento del tiempo estamos pasando por las zonas más altas y ganando la mayor cantidad de puntos posibles. Esto funciona de manera análoga si estamos minimizando.

Cuando enseñan a un niño a multiplicar, nunca he comprendido porqué tanto esfuerzo en que memoricen unas tablas. Eso es aburrido y mucho de ese esfuerzo será vano y al final de cuentas, no les están diciendo el principio básico detrás de la multiplicación, que no es más que una suma de a, n veces. Al final de cuentas, en multiplicación, si se entiende el principio y cómo opera, al enseñar a multiplicar por 2, 3, 5, 7 y 9 se abarca todo (Que tienen en común estos números). Al duplicar se abarcan automáticamente 2, 4 y 8, con el 3 y ya conociendo el 2 se abarca también el 6, el 7 tal vez sea el único que pudiera ser complicado de algún modo, pues se le puede hacer evidente a los niños que al multiplicar por 9 el dígito en la posición decimal va aumentando mientras que el otro número se reduce en cualquier multiplicador de 9 del 1 al 10, que es lo que normalmente se enseña, puntos extra para el maestro si puede explicar porqué pasa esto. Dejar la multiplicación por cinco puede ser una idea genial, porque multiplicar por 10 es muy fácil y al saber duplicar es fácil entender a dividir por la mitad. Multiplicar por cinco es hacer estas dos operaciones.

 

Hago notar que estoy experimentando con mi primito estas formas de enseñar mates, les aviso de los resultados.

La era del polígono

En los noventas, cuando salió la primera generación de videojuegos tridimensionales yo creía que no había forma de mejorar eso, la transición de píxeles en plataformas bidimensionales a mundos hechos totalmente en tres dimensiones daba la impresión de que el salto era enorme, y lo fue.

Pero todo eso se debía al uso de las mallas poligonales (polymesh o polygon mesh).

El truco era crear superficies por medio de un método tridimensional generado por sistemas de vértices que se posicionan en un espacio virtual por un sistema de coordenadas que se crean con algún algoritmo. La malla se crea con un mínimo (obvio) de tres vértices, y cada uno de esas secciones del polígono se le llaman caras. Las caras son la unidad básica de un polígono en tres dimensiones.

En los juegos que estaban en consolas de 64 bits los polígonos eran la forma estándar de generar objetos tridimensionales y generalmente se solían mezclar con escenarios bidimensionales, que regularmente constituían escenarios u objetos que no necesariamente interactúan con el juego (alguien recuerda haberse subido a un árbol en “Super Mario 64”?, la cara del árbol, no importa hacia donde voltee la cámara, será siempre la misma).

Conforme la capacidad de procesamiento mejora, permite a los desarrolladores hacer uso de polígonos con un mayor número de caras, que significan movimientos más completos y un efecto visual más nítido.

El Vóxel se introdujo además, como una alternativa de los polígonos, pero no existían maneras eficientes de lograr hacer animaciones con vóxels, así que sólo se usaban para la generación de objetos no animados, como el terreno.

Multiplicación Japonesa: Cómo funciona

Este truco tiene mucho sentido, hace mucho más fácil la multiplicación de grandes números sin ayuda de calculadora y ayuda a entender un poco más el funcionamiento de la multiplicación. Para los maestros de sistema tradicional más ortodoxos les parecería trampa, pero en lo personal considero más tramposo obligar al alumno a memorizar. Eso es trampa en el sentido de que no se aprende nada del funcionamiento de las matemáticas.

Imagen

En fin, si observamos la foto notaremos que el 13 se representa con una línea roja y tres azules, mientras que el 12 son una línea verde y dos negras. Los círculos son los que rigen a los números que tendrá el resultado final, que se obtiene simplemente contando el número de intersecciones.

Este método tiene sentido, pues al contar las intersecciones que hay en la sección de las decenas, el número resultante son centenas (i.e. la primera intersección son 10×10, esto son 100, lo cual se agrega al número final. Si se hubiera hecho con 23×12 las intersecciones en el primer círculo serían dos).

Cuando cuentas el círculo del centro, estás contando el número de intersecciones de decenas con unidades, y sumando las que hay en las dos direcciones de la multiplicación. (i.e. estás realizando la suma (10×3)+(10×2)=50… y al agregarlo al 100 anterior, tenemos 150).

Finalmente, el número de intersecciones que generan tres líneas contra dos es igual que la multiplicación 3×2. Brillante, no?

Mi primer pensamiento al verlo fue… ¿Por qué no se me ocurrió antes? Eso es lo que generan las buenas ideas