Teoría de Colas – Colas Markovianas – de 1 solo canal

INTRODUCCIÓN

Todos alguna vez hemos hecho una cola, en un banco, supermercado, o un trámite donde muchas personas se congregan y existen definitivamente menos centros de atención que usuarios que desean realizar algún trámite. Las colas son un tópico de la investigación de operaciones que se aborda con la finalidad de optimizar el sistema, esto ocurre por lo siguiente pongámonos  en la situación que tenemos un banco en la cual tenemos un solo cajero en atención, estamos reduciendo costos pues al menos tenemos un cajero, pero no estamos pensando que podríamos perder clientes por los tiempos de espera prolongados, lo cual repercute en el rendimiento de las operaciones, ahora podemos ir al otro extremo en que colocamos muchos cajeros tal que cada cliente sea atendido inmediatamente por un cajero, esto ocasionaría un sobre costo aun cuando el cliente se sienta totalmente satisfecho, pero no resulta conveniente, es por ello que se busca la optimización en el equilibrio del sistema. Entonces tenemos un sistema de colas que puede ser de un solo canal (cajero) o multi-canal:

1canal
Un solo canal
multicanal
Multicanal

COMPONENTES

Tal como se puede observar en los gráficos, se pueden distinguir componentes que conforman el modelo de colas, estos son:

modelo

  • Fuente de Entrada:  Toma especial interés el tamaño de la población que puede requerir servicio en determinado momento, a esta población de clientes potenciales se le conoce como “población de entrada”, esta población puede ser de tamaño finito o infinito; sin embargo, y  por la facilidad de cálculo se suele tomar que es infinito, aun cuando se trate de un problema real que definitivamente tiene un tamaño finito se toma como supuesto que es infinito a menos que se establezca lo contrario. Así como el tamaño se debe de especificar  el patrón estadístico por el cual se generan los clientes, por lo general se asume que estos siguen una distribución de Poisson.
  • Cola: La cola es donde los clientes esperan antes de recibir servicio, se caracteriza por el número máximo de clientes que puede admitir, estas también pueden ser finitas o infinitas, el supuesto de infinito se aplica como un estándar de la mayoría de modelos, incluso cuando en la realidad existe una cota superior.
  • Disciplina de la Cola:  Se refiere al orden en el que sus miembros se seleccionan para recibir el servicio, puede ser: “primero en entrar, primero en salir -(FIFO)“, “último en entrar, primero en salir-(LIFO)” , aleatoria o algún otro procedimiento.
  • Mecanismo de Servicio: Consiste  en uno o más estaciones de servicio denominados servidores, en un modelo de colas siempre se debe especificar el arreglo de las estaciones y el número de los servidores. El tiempo que transcurre desde el inicio del servicio para un cliente hasta su terminación en una estación se llama tiempo de servicio.

NOTACIÓN  Y DISTRIBUCIÓN

En la notación se sigue la notación Kendall que se indica de la siguiente forma:

A/B/C

Donde:

  • A: Especifica el tipo de distribución en la llegada.
  • B: Especifica el proceso de servicio
  • C: Indica el número de servidores

Los códigos empleados son:

  • M: para Markoviano (las tasas de llegada siguen una distribución de Poisson), significando una distribución exponencial para los tiempos de llegada (un banco, cola de supermercado, etc.).
  • D: para unos tiempos deterministas, es decir, los tiempos de llegada no son probabilísticos  y son a intervalos constantes (una planta con un proceso automatizado en línea).
  • G: para una distribución general de los tiempos de llegada, es decir permite cualquier distribución arbitraria.

TERMINOLOGÍA

Se tiende a una terminología aunque cada autor podría diferir en la definición de los términos o símbolos que hace uso:

  • Estado del sistema: número de clientes en el sistema.
  • Longitud de la cola: número de clientes que esperan servicio o estado del sistema menos número de clientes a quiénes se les da el servicio.
  • N(t): número de clientes en el sistema de colas en el tiempo t (t≥0).
  • Pn(t): probabilidad de que exactamente n clientes estén en el sistema en el tiempo t dado el número en el tiempo 0.
  • s: número de servidores (canales de servicio en paralelo) en el sistema de colas.
  • λn: tasa media de llegadas (número esperado de llegadas por unidad de tiempo) de nuevos clientes cuando hay n clientes en el sistema.
  • μn: tasa media de servicio en todo el sistema (número esperado de clientes que completan su servicio por unidad de tiempo).

MEDIDAS DE RENDIMIENTO

Centradas en el cliente:

  • Wq: tiempo promedio de espera, en la cual un cliente llega y es atendido.
  • W: tiempo promedio total del sistema, que incluye el tiempo promedio de espera y el tiempo promedio del servicio.

Cuantitativas sobre el número de clientes:

  • P0: probabilidad de que no haya clientes en el sistema, puede ser empleado cuando se requiera la probabilidad de que haya n elementos en el sistema.

Relacionadas al costo:

  • Costo promedio por unidad de tiempo de operación del sistema
  • Cantidad de estaciones de trabajo necesarias para obtener la mayor efectividad en términos de costos.

RELACIONES ENTRE MEDIDAS DE RENDIMIENTO

El tiempo promedio del sistema, es el tiempo de espera y el tiempo de servicio, sí  “μ” es la cantidad de clientes atendidos por unidad de tiempo, la inversa será el tiempo que demore en atender a un cliente en una unidad de tiempo, entonces:

Tiempo total de un cliente en el sistema:form1

Sea que el tiempo que pasa el cliente en el sistema es W, y λ  por definición es la cantidad de clientes que llegan al sistema por unidad de tiempo, entonces podemos decir que la cantidad de clientes en el sistema  en cualquier tiempo dado será:

L=W*λ

Podemos hacer una analogía, para determinar la cantidad de clientes esperando en cualquier tiempo dado de la siguiente forma:

Cantidad de clientes en cola: Lq=Wq

ANÁLISIS DE COSTOS DEL SISTEMA DE COLAS

Para determinar el costo total debemos de hallar el costo total del personal:

Costo total de personal=(Costoxhoraxservidor) * (Cantidad de personal)

El costo total de los clientes en espera:

Costo total por la espera=(Costoxhoraxcliente_en_cola) * (Cantidad de clientes en cola)

Tal que el costo total es:

Costo total=Costo_total_personal + Costo_total_por_la_espera

ANÁLISIS DE UN SISTEMA DE COLAS DE TIPO (M/M/1)

Las fórmulas de rendimiento por lo general se han derivado a través del uso de las variables λ y μ tal que se llega a la expresión de la intensidad de tráfico o también denominado factor de uso (ρ)  que tiene la siguiente forma:

 Factor de uso: ρ=λ/μ

Si el factor de uso mientras más cerca a 1 significará que el sistema estará más cargado lo cual trae como resultados colas más largas y tiempos de espera más largos. Sí el factor de uso mide la intensidad de clientes en el sistema,  su complemento determina la probabilidad de que no exista clientes en el sistema:

Probabilidad de cero clientes en el sistema: P0=1-ρ

Esta probabilidad indica que un cliente que llega no tendrá que esperar a que se le proporcione servicio ya que la cola estará vacía.

Podemos de similar forma obtener la cantidad de clientes en espera o en la cola en función de ρ o de λ y μ.

Número de clientes en espera:col1

Este último resultado sirven de base para obtener el Wq y W acorde a las fórmulas planteadas líneas arriba.

Si deseamos determinar la probabilidad de que el sistema tenga exactamente “n” cantidad de clientes:

Cantidad n exacta de clientes en el sistema:col2

Esta última ecuación nos permite responder a las preguntas tales como: ¿Cuál es la probabilidad que no haya más de  n clientes en el sistema? , para ello debemos de tomar la suma desde 0 a n de las probabilidades:

col3

Y si en caso la pregunta fuera ¿Cuál es la probabilidad de encontrar hasta n clientes en el sistema?, se tomará el complemento, es decir:

1-Ptotal

EJEMPLOS DE APLICACIÓN

Ejercicio 1

Si la tasa de llegada a una estación de servicio es de 12 unidades por hora y el tiempo de atención por unidad es de 4 minutos siendo además que se pierde por unidad parada la cantidad de $80 por hora y que el costo por día del servicio es de $50, se pide:

  • La probabilidad de encontrar hasta 3 unidades en el sistema.
  • El costo total por día del sistema.
  • Determine si conviene contratar un ayudante por $20 diario si la tasa de atención mejora en 30%.

Resolución:

Tenemos que el tiempo de llegada es de λ: 12 unidades por hora, y la cantidad de unidades por unidad de tiempo es de  μ: 15 unidades por hora ya que cada unidad tarda 4 minutos en un servidor. Nos piden hallar la probabilidad de encontrar hasta 3 unidades en el sistema, para ello usaremos  1-Ptotal,entonces hallamos el total desde i=0 hasta i=n=3 en:

col2

Tenemos que λ/μ=0.8, entonces en P0=(0.8)0(0.2)=0.2, P1=(0.8)1(0.2)=0.16, P2=(0.8)2(0.2)=0.128 y P3=(0.8)3(0.2)=0.1024; la suma total es 0.5904, entonces la probabilidad de encontrar hasta 3 unidades es 1-0.5904=0.4096.

El costo total del sistema, tenemos como datos el costo del día del servicio que es de $50, tomaremos que el día está compuesto de  8 horas laborales, entonces debemos de hallar cuántos clientes se encuentran en cola cada hora; debemos de hallar la cantidad de elementos en cola, sabemos que Lq:

col1

tenemos que la cola cada hora está compuesta por 3.2 unidades, y el costo por unidad por hora es de $80, entonces el costo total de espera por hora es de $256 por hora, pero como son 8 horas laborales tenemos que el costo diario es de $2048, el costo del servicio es de $50 y la cantidad de servidores es de 1, finalmente el costo total será:

Costo total=$50+$2,048=$2098

Ahora debemos de evaluar que sucede si se incluye un ayudante que mejora la tasa de atención es un 30%, esto se traduce en 1.3μ, entonces el nuevo μ será de 19.5 unidades por hora con lo cual debemos de revisar el costo, para ello el nuevo Lq es 0.985 unidades en cola en cada hora, entonces el nuevo costo será:

Costo total=$50+$20+8*80*0.985=$700.154 teniendo como conclusión que sí resulta conveniente.

Ejercicio 2

El departamento de sistemas trata de determinar si alquila una copiadora lenta o rápida. El tiempo de un empleado vale 15 soles la hora, el alquiler de la copiadora lenta cuesta 4 soles la hora y un empleado tarda en promedio 10 minutos en terminar un trabajo, la copiadora rápida cuesta 15 soles la hora en arrendamiento y un empleado tarda un promedio de 6 minutos en terminar un trabajo, al departamento llegan en promedio 4 trabajos de copiado por  hora y el costo de la espera por cada uno de estos trabajos es de 7 soles por  hora. Se pide:

  • La probabilidad de que no haya trabajos en el sistema con copiadora lenta.
  • La probabilidad de que haya al menos dos trabajos en el sistema con copiadora rápida.
  • ¿Cuál es el costo total si se alquila la máquina lenta?
  • ¿Cuál es el costo total si se alquila la máquina rápida?
  • Si el promedio de llegadas de trabajos es de 7 por hora, ¿Cuál es la máquina que deberá utilizar?

Resolución:

Por los datos del problema sabemos que λ=4 trabajos por hora y μ0= 6 trabajos por hora y μ1= 10 trabajos por hora, siendo los sub-índices 0 y 1 para la copiadora lenta y rápida respectivamente, entonces para hallar el primer punto (con la copiadora lenta), debemos de usar:

Probabilidad de cero clientes en el sistema: P0=1-ρ

Entonces ρ=4/6 y P0=1-4/6=1/3=0.333.

Para el segundo punto, nos piden la probabilidad de al menos 2 trabajos para la copiadora rápida, con lo cual debemos de hallar las probabilidades desde 0 a 2, hacer su suma y luego obtener su complemento a 1. Tenemos que λ/μ=0.4 (copiadora rápida), entonces en P0=(0.4)0(0.6)=0.6, P1=(0.4)1(0.6)=0.24 y P2=(0.4)2(0.6)=0.096; la suma total es 0.936, entonces la probabilidad de encontrar hasta 3 unidades es 1-0.936=0.064.

El tercer punto sobre el costo con la copiadora rápida, tomaremos como unidad de tiempo la hora, sabemos que el costo del personal es de S/.15 por hora y el costo por alquiler de copiadora por hora es de S/. 4, con lo cual debemos de hallar cuántos clientes hay en promedio en la cola en la unidad de tiempo, entonces Lq=4/3 y el costo por trabajo por hora es de S/.7, con lo que obtenemos:

Costo total=4+15+(4/3)*7=S/.28.333 

El cuarto punto de forma similar solo que se usará los datos de la copiadora rápida, Lq=4/15, entonces:

Costo total=15+15+(4/15)*7=S/.31.867 

En el quinto punto, si tomamos que λ=7 al resolver Lq con la copiadora lenta nos saldrá un valor negativo, por lo cual queda descartado siendo finalmente la conclusión hacer uso de la copiadora rápida.

El Perceptrón – Aprendizajes hacia la IA – Parte 1

 Nuevamente con el aprendizaje hacia la Inteligencia Artificial, para ello, uno de los tópicos a revisar son las redes neuronales artificiales, estas básicamente son una representación computacional de las redes neuronales “naturales” en términos de su comportamiento; una red neuronal está compuesta por neuronas, pero ¿Qué es una neurona?, por definición:

“Célula del sistema nervioso formada por un núcleo y una serie de prolongaciones, una de las cuáles es más larga que las demás”

300px-Neurona.svg

Podríamos decir que la función básica de la neurona es un procesamiento que se da a través de recibir un input (estímulos eléctricos), realizar un procesamiento y transmitir un resultado hacia la siguiente neurona, McCulloch  y Pitts crearon la neurona que lleva su nombre y que es una unidad de cálculo que intenta modelar el comportamiento descrito de una neurona “natural“:

neuronaa

PLANTEANDO

Si describimos esta neurona las Xi representan las entradas y las Wij representan el peso asignado a cada una de las entradas que tenemos, la sumatoria representa la neurona y el axón inicialmente sin tomar el f() sería la salida, hago esto con el fin de explicarles de la misma forma que entendí la conformación de la neurona, entonces podemos decir lo siguiente:

1
Primer acercamiento

Para todas las entradas posibles la salida Y sería la suma de cada entrada multiplicada con su ponderada, pero esta ecuación no está completa aunque si ya nos permite esbozar que una red neuronal será una aproximación a una función matemática de pesos, al ser matemática implica que podemos hacer uso de toda la matemática disponible para su resolución, al expresarlo mediante una función hemos “modelado” el comportamiento, ahora tenemos que poner a prueba nuestro modelo.

Cuando deseamos comprobar si nuestro modelo es adecuado lo primero que se hace es poner a prueba nuestro modelo y que pueda responder a las funciones lógicas más básicas, entonces:

Primera Prueba – La función NOT

Una función de ese tipo en una tabla se expresa de la siguiente forma:

2

Podemos representarla de la siguiente forma:

3

 

Cuando reemplazamos los valores a la función que hemos obtenido nos queda:

4

Entonces este primer acercamiento no es correcto y debe de modificarse, ¿Cómo debe de modificarse?, pues si observamos  seria muy conveniente el agregar un término constante b (en el gráfico es θ) por cada neurona de la siguiente forma:

6
Segundo acercamiento

Entonces se puede representar de la

5

 

Resolvemos según la tabla y obtenemos:

7

Vemos que esto nos funciona cuando hacemos uso de un NOT, ahora veamos si es posible en un OR.

Segunda Prueba – función OR

La tabla de una función lógica OR es:

8

Podemos expresarlo de la siguiente forma:

9

Reemplazando tenemos:

10.png

Tal como podemos observar vamos a obtener una contradicción en el que los pesos “W” son 1 y en la última ecuación ambos suman 2 pero el resultado es 1.

REPLANTEANDO NUEVAMENTE!!! 

Si resolvemos con las demás funciones lógicas simples veríamos que tampoco se cumple, entonces ¿Qué es a lo que se llegó?, debía de implementarse una función, a la que llamaron función no lineal, para este caso desarrollaron la función step, tal que su representación final sea la del inicio:

neuronaa

Tal que la función step es:

11

Entonces validamos la función NOT:

12

Y si cumple, ahora validemos la función OR:

13

¿Qué ocurre entonces con la función AND?

Se cumple la tabla:

14

¿Cómo podemos interpretar una función AND?, pues una AND se expresa en la negación de la función OR; tal como está nuestra función no se adapta, para ello debemos de aumentar en 2 neuronas y  de hacer un cambio en nuestro parámetro y revisar si nuestro modelo actual sigue adaptándose, entonces tomaremos el valor -0.5 para el “OR” y vemos que cumple, finalmente esto se puede graficar de la siguiente forma:

16.png

Es factible usando el mismo modelo expresarlo con una sola neurona si el valor del parámetro fuese -1.5

Tercera Prueba función XOR:

El problema que XOR a de implicar el uso de una neurona más, veamos la tabla:

15

 

Esta función se expresa de la siguiente forma:

17

Si construimos la gráfica:

18.png

 

Matplotlib – Generador de Gráficos en Python

Una imagen es mejor que mil palabras, es un término recurrente cuando se desea resumir o explicar algún tópico, las imágenes pueden ser solo el sujeto que hemos de cambiar por un diagrama o cuadros o gráficos, imaginemos que tenemos una cantidad considerable de datos y queremos mostrar el comportamiento que estos siguen, para ello existe la librería matplotlib, el cual es una librería para la generación de gráficos a partir de datos contenidos en listas  y es usado por lo general a través de numpy, para esta breve descripción usaremos a VSCODE como editor de código, sin más que decir. empecemos:

INSTALACIÓN E IMPLEMENTACIÓN

La instalación se realiza a través del terminal (CMD si es que tu python está dentro del path) incorporado en VSCODE con la instrucción siguiente:

pip install matplotlib

Ahora debemos de abrir un fichero y en este debemos de importar la librería, se estila que la librería sea importada de la siguiente forma:

import matplotlib.pyplot as plt

matplotlib.pyplot es una colección de funciones que asemejan al estilo de comandos que tiene MATLAB, que supongo tendrá especial significancia para aquellos que ya están familiarizados con dicho software, en lo particular yo no, pero te encontrarás con muchos tutoriales que hacen referencia a este tipo de importación.

HACIENDO UNA LÍNEA RECTA

Hacer una línea recta es muy sencillo en esta librería, pues en su forma más básica debemos de tener dos listas que representen el eje X e Y y colocarlos dentro del método plot(), plot tiene un constructor amplio, pero por el momento vamos a reducirlo a la realización de un recta simple en donde requerimos tanto los elementos de las coordenadas X e Y y una etiqueta, entonces plot hace la recta pero cuando creamos un gráfico necesitamos saber que representan cada uno de los ejes, supongamos que tenemos intenciones de presentar la relación entre los metros cuadrados de una habitación con su precio de alquiler, para ello debemos de hacer uso de los métodos xlabel() y ylabel(), los  cuáles reciben como parámetro obligatorio  la cadena de texto que representa el eje en cuestión, podemos agregar un título a nuestro gráfico con title() y la leyenda que corresponde a la recta que se toma de la etiqueta al momento de su creación con el método legend(), finalmente debemos de mostrar la gráfica, y esta se muestra con el método show(), entonces:

import matplotlib.pyplot as plt

#creamos dos listas
x=[1,2,3]
y=[5,7,9]

plt.plot(x,y,label="linea1") # creación de la recta
plt.xlabel("Metros cuadrados") #etiqueta eje X
plt.ylabel("Costo en miles de soles") #etiqueta eje Y
plt.title("Relación Costo y m2") #Agregamos un título
plt.legend() #agregamos la leyenda
plt.show() #desplegamos el gráfico
El resultados es el siguiente:
mat1.png

HACIENDO UNA DIAGRAMA DE BARRAS

Para realizar un diagrama de barras es tan sencillo, ya que solo se requiere del método bar(), como requisito debemos de indicarle la serie en el eje X y en Y, una etiqueta, todo lo demás se mantiene de forma similar:

x=[2,4,6,8,10]
y=[6,7,8,2,4]

x2=[1,3,5,9,11]
y2=[7,8,2,4,2]

plt.bar(x,y,label="Bar 1")
plt.bar(x2,y2,label="Bar 2")

plt.xlabel("x")
plt.ylabel("y")

plt.title("Gráfica de Barras")
plt.legend()
plt.show()

Así de forma sucesiva podemos hacer una serie de gráficas, personalmente no creo que requiera mayor análisis que el que implique revisar la misma API de la librería.

Matrices en Python uso de Numpy

Numpy es la librería casi por defecto cuando hemos de tratar con matrices, y específicamente en el uso de big data por su menor consumo de tiempo de procesamiento computacional dando paso a una mayor cantidad de procesamiento, entonces en esta ocasión revisaremos las operaciones con matrices que se pueden realizar:

INSTALACIÓN

En primera instancia este tutorial asume que estás usando VSCODE  y que tu sistema operativo o distribución ya tiene instalado python, abrimos el terminal incorporado de VSCODE, abrimos el terminal y hacemos la siguiente instrucción:

pip install numpy

DECLARACIÓN DE UNA MATRIZ

Cuando hemos de usar numpy debemos de importar la librería en el top del fichero, entonces:

import numpy as np

 Esto significa que todo lo relacionado a la invocación de los métodos que pertenecen a numpy lo hemos de realizar haciendo “np.nombre_metodo“, como si métodos estáticos se trataran en su sintaxis (java ¿huh?).

Ahora bien, ¿Cómo se implementa una matriz en un lenguaje de programación?, pues esta se implementa a través de los arreglos, un arreglo es una estructura de datos que nos permiten almacenar elementos que dependiendo del lenguaje pueden ser del mismo tipo o no, java por ejemplo permite los arreglos de un mismo tipo y solo de primitivos si son de tipo referenciados pues tienen otros nombres; sin embargo, python considera que los elementos que conformen un arreglo no necesariamente tienen que ser todos del mismo tipo de dato (no hacemos referencia a primitivos pues todo es un objeto en python).

Python agrupa los arreglos de la siguiente forma:

Para las matrices en numpy se organiza la estructura de forma muy similar a las listas, aunque no son lo mismo, entonces hecha esta aclaración, una matriz se define de la siguiente forma:

a=np.array([1,2,3])#1 dimensión
b=np.array([[1,2,3],[4,5,6]]) #2 dimensiones
c=np.array([[1,2,3],[4,5,6],[7,8,9]]) # 3 dimensiones

El objeto principal en numpy es ndarray el cual representa un arreglo que puede ser multidimensional y es homogéneo en términos del tipo de objeto. Una de las formas de crear una matriz se realiza con el método array, y que su constructor es de la siguiente forma:

numpy.array(objectdtype=Nonecopy=Trueorder='K'subok=Falsendmin=0)

Aunque los demás términos ya están descritos en su definición, el parámetro obligatorio es un objeto el cual tal como se ha mostrado divide sus dimensiones siguiendo una estructura tipo lista. Podemos también transformar desde listas o tuplas (bueno en esencia es un objeto ¿no?), entonces sea:

arreglo=[1,2,3,4,5,6,7,8,9]
arreglo2=(1,2,3,4,5,6,7,8,9)

x=np.array(arreglo)
y=np.array(arreglo2)

y=np.reshape(y,(3,3))
x=np.reshape(x,(3,3))

Si ingresamos una lista o tupla, esta quedará como una matriz de una sola dimensión, si deseamos dar un ordenamiento específico como una matriz de 3×3, debemos de hacer uso del método reshape:

numpy.reshape(anewshapeorder='C')

Este método nos devuelve una matriz con el ordenamiento deseado, y es tal como la hemos usado, el tipo de orden debe indicar a través de una tupla, en nuestro caso de (3,3). Dicho esto como parte básica para la creación de las matrices, vamos a realizar las operaciones con ellas.

OPERACIONES BÁSICAS

Sean 2 matrices de 2×2 A y B que las obtenemos a través de listas, pero vamos a generarlo todo en una sola línea:

a=[1,2,3,4,]
b=[7,8,9,10]

a=np.reshape(np.array(a),(2,2))
b=np.reshape(np.array(b),(2,2))

La suma entonces:

c=b+a
print(c)

La resta:

c=b-a

Podemos hacer que todos los elementos de la matriz se eleven a un exponente determinado de la siguiente forma:

c=b**exponente
c=np.power(b,exponente)

Multiplicación

Las matrices tienen una particularidad al momento de la multiplicación, ya que siguen la forma de filas por columna, para realizarla podemos hacerlo de dos formas:

c=np.dot(a,b) #recibe las 2 matrices a multiplicar
d=a@b

La División

¿Por qué no tomamos la división?, pues por teoría la división de una matriz no es una operación que se realice como con los números reales, una división en una matriz se puede determinar a través de la multiplicación con la inversa de la matriz que estaría en el denominador, es decir:

A.B-1

Podemos obtener la inversa de una matriz a través del método inv, el cual pertenece a la subclase linalg, inv recibe como parámetro a la matriz  y devuelve su matriz inversa, entonces:

e=np.linalg.inv(b)

Ahora bien haciendo uso de las matrices de ejemplo a y b:

f=np.dot(a,np.linalg.inv(b))

DETERMINANTE DE UNA MATRIZ 

El determinante de una matriz podemos hallarlo haciendo uso del método det, que tiene como parámetro la matriz cuadrada que se desea hallar su determinante (no olvidar que el determinante siempre es un escalar y nunca un vector):

determinante=np.linalg.det(a)

MATRIZ TRANSPUESTA

La transpuesta de una matriz es la transformación en que las filas pasan a las columnas y viceversa, para realizar la transpuesta debemos de usar el método transpose, este es un método asociado directamente a la matriz, entonces:

g=a.transpose()

Por lo pronto es todo lo que podemos observar de las operaciones con matrices

 

Tecnologías de la Fabricación Digital – Escaneo 3D en dispositivos Móviles

Nuevos tiempos y nuevas formas de fabricar, con el tiempo pensar en una fabricación personalizada es cada vez menos descabellado, ya no hablamos de la segmentación y producción por perfiles agrupando a los usuarios por edad, ingresos, etc; sino por el conjunto de atributos que lo definen como tal y único y en consecuencia la serie de elecciones y transformaciones que puede realizar entre ellos los productos que pueda fabricar; a la corriente cultural que acercan al usuario a crear sus propios productos se ha denominado  cultura Maker, que es el símil en terrenos del hardware a lo que significó la apertura hacia el software libre en los terrenos de la informática, esta cultura maker se ha hecho tangible a través de la reducción del costo de adquisición de máquinas, acceso al conocimiento a su creación y a la fabricación de productos, dentro de las técnicas de fabricación, existe un conjunto de herramientas que se denominan fabricación digital, este tipo de fabricación tiene como flujo:

Átomos - Bits - Átomos

¿Qué es lo que muestra este flujo?, pues  que la fabricación de un producto puede darse desde el modelado del mismo a partir de la abstracción o la captura de un objeto físico ya existente, el primero es el diseño digital tal y como lo conocemos y que existen infinidad de programas para lograrlo, el segundo si bien es cierto tiene algo de tiempo en la escena tecnológica pero no ha sido muy popularizado, su principal representante es el escáner 3D   el cual por los altos costos que representó su adquisición no ayudó mucho a su difusión; sin embargo, con las mejoras de procesamiento y captura de imágenes (cámaras) de los teléfonos móviles, se abrió una posibilidad de acercar al usuario al escaneo 3D, así que en esta ocasión abordaremos las aplicaciones que nos permiten escanear objetos con nuestro teléfono móvil; ¿Qué deben tener en común las aplicaciones de escáner 3D? pues que puedan exportarse a un fichero STL que es el formato común entre diversas impresoras 3D y que además puede (no es obligatorio) permitir la manipulación en programas CAD, entonces empecemos:

Scann3D

unnamed

Es de descarga gratuita y solicita que te identifiques con tu cuenta de google, solicita acceso a la carpeta de fotos e imágenes ya que ha de hacer uso del espacio en memoria que dispongas, incluso te recomiendan que te hagas con espacio al usarlo. Los comentarios en la google play no son nada positivos, esto es quizá porque se espera mucho de una aplicación que de por sí se tiene que adaptar a todo tipo de arquitectura que compongan tu teléfono móvil, aunque hay que tomarlos un poco en cuenta. Su menú principal tiene 3 opciones:

  • Nuevo Modelo: Apertura indicaciones de como tomar las imágenes (tomar en cuenta mucho el tema de la luz, y eso aplica como norma incluso para los de tipo profesional), e incluso tiene un guía en tiempo real para la toma de imágenes.
  • Mis Modelos: Si en caso haz decidido guardar alguno de los modelos
  • Continuar (si ya estuviste realizando uno).

Al finalizar la secuencia de fotos, tienes la posibilidad de obtener tu modelo con todos los detalles o simplemente la básica, esta última es gratuita y las demás implican un coste de suscripción (versión PRO), de forma similar ofrece la posibilidad de exportar el modelo en el formato STL.

Nota Personal: Realicé pruebas con él en Huawei Mate 10 PRO, en la noche pero con fuerte iluminación, hice dos pruebas y no salieron como esperaba, hice pruebas en el día, y tampoco obtuve los resultados esperados, quizá sea sesgado pero puede que funcione solo con objetos grandes.

Qlone 3D Scanning & AR Solutions

qlone.png

Es otra de las aplicaciones populares, al igual que populares resultan las opiniones positivas y negativas en el centro de descarga, pero al menos hay opiniones positivas; sin embargo, aunque no es preponderante las opiniones nos sirven para darnos una idea de la adaptabilidad del software a las diversas arquitecturas que presentan los teléfonos móviles. El programa es de descarga gratuita, pide acceso a tu cámara mas no a tu memoria, así también te da indicaciones para la impresión de la hoja patrón de la cual hacen uso, esta hoja patrón puede ser redimensionada en función del tamaño del objeto que haz de escanear lo cual, definitivamente te da una idea que no es muy ideal para el escaneo de monumentos en plazas, por ejemplo. Aquí les dejo un vídeo de las impresiones con esta aplicación:

Nota Personal: Sinceramente lo restrictivo es la hoja de impresión para el registro del escaneo, lo que limita las dimensiones del objeto a escanear.

NOTA PERSONAL GENERAL

Las pruebas se realizaron en un Huawei Mate 10 PRO, y al menos en Android no funcionan de forma correcta las aplicaciones para escanear, he leído que en dispositivos Apple hay mejores resultados, esto dado porque la arquitectura está totalmente definida, lo que hace que ya no te preocupes de la versatilidad del software, lastimosamente no se pudo realizar pruebas al respecto al no tener un dispositivo de dicha marca.

¿Cuál es el principio en común?

El principio en común en muchas de las aplicaciones es la fotogrametría, así que me puse a revisar las diversas técnicas que implican su uso encontrando un vídeo muy explicativo de como realizar tu propio escaneo:

 

¿Cómo se hace en Perú? – o Al menos en algunos lados

Como tema experimental en Perú existen cursos que dentro de sus tópicos incluyen el desarrollo de asignaciones con el escaneo en 3 dimensiones, este curso se denomina fabacademy y es ofrecido por algunas universidades en Perú y en Latinoamérica.

 

 

Java desde Cero – Estructura de Control de Flujo – Bucles 2

Anteriormente:

Ya hemos revisado el bucle FOR, en esta ocasión vamos revisar la estructura de control de flujo While, tal como en la introducción mencionamos los bucles While son del tipo indeterminado, y es indeterminado ya que no se sabe cuántas veces se ejecutará ya que estas estructuras responden a una condición booleana, condición que deberá ser verdadera para que la ejecución continúe y falsa para que se detenga, su estructura es de la siguiente forma:

while (condición) {
     sentencias
}

Existen algunas observaciones respecto a while, puede ser que nuestra condición sea falsa con lo cual nunca ha de ejecutarse el while, o puede ser que sea verdadera y no exista un mecanismo que cambie dicha condición con lo cual la iteración de while será infinita, dicho esto debemos de tener especial cuidado cuando definamos la condición, sobre esta última observación, ¿Dónde conviene tener un bucle infinito? pues por lo general es un recurso que se emplea mucho en el desarrollo de los videojuegos y que se ejecutan hasta un cierre del mismo, pero mientras este cierre no se ejecute conviene mucho que todas las demás funcionalidades estén en ejecución, como el estar re-dibujando constantemente el canvas, si te encuentras en una situación que amerita su implementación simplemente puedes hacer esto:

while (true) {
     sentencias
}

No hay mucho que decir, así que veamos un ejemplo para visualizar el como trabaja esta estructura de control de flujo. Supongamos que tenemos  un número al azar entre 0 y 100, y tenemos que adivinar el número, tal que nuestro programa si en caso no acertemos nos de información de si el número que hemos ingresado es muy alto o muy bajo respecto al número que estamos buscando, cuando por fin acertemos el programa nos dará una felicitación, nos dirá que número era y cuántas veces hemos intentado hasta hallar el número.

import java.util.Scanner;

public class Bucles_2 {

  public static void main(String[] args) {

    int numero_buscado=(int)(Math.random()*100);
    boolean no_acerto=true;
    Scanner entrada=new Scanner(System.in);
    //System.out.println(numero_buscado);
    System.out.println("Bienvenido al juego");
    int intentos=0;

    while(no_acerto==true) {
      System.out.println("Ingrese un número");
      int variable=entrada.nextInt();
      if(variable>numero_buscado) {
        System.out.println("El número es muy alto");
        intentos++;
      }else if(variable<numero_buscado) {
        System.out.println("El número es muy bajo");
        intentos++;
      }else {
        System.out.println("Acertaste!");
        intentos++;
        no_acerto=false;
      }
    }
    entrada.close();

    System.out.println("El número buscado era: "+numero_buscado+" y lo obtuviste con un total de "+intentos+" intentos");

}

}

Revisamos un poco lo desarrollado, de arriba hacia abajo, tal como es el flujo natural de ejecución en Java, bueno, lo primero que hemos creado es el número aleatorio, este número aleatorio lo hemos obtenido con el uso del método estático de random de la clase Math del paquete java.lang, este método nos retorna un número aleatorio entre 0 y 1 y de tipo double, para obtener el número entre 0 y 100 basta que multipliquemos el valor que nos retorna por 100, ahora bien dado que un tipo double es esencia un decimal, nosotros vamos a restringir los resultados a valores de tipo entero, para lo cual debemos de realizar una conversión o casteo y por ello hacemos uso de (int) para tales fines.

Luego creamos la condición que estará en el while, en la línea siguiente definimos que dado que el usuario ha de ingresar datos a través del teclado, necesitamos capturarlos y esto lo hacemos a través de una instancia de la clase Scanner, finalmente creamos un contador de intentos; ahora bien, empieza la iteración dado que la condición es true, se le consulta por un número al usuario, se captura el número con la instancia de Scanner y se castea a un entero con el método nextInt(), y se evalúa en los condicionales si es mayor o es menor, o si en caso de no ser alguna de ellos, podemos tener la certeza de que es el número que estamos buscando y detenemos la iteración haciendo que la variable booleana cambie a false; en todos los componentes del condicional hacemos que los intentos se le suma una unidad aún incluso si acertamos se puede contabilizar como un intento.

No olvidemos jamás de cerrar el flujo de entrada de datos, haciendo uso del método close de la clase Scanner. Finalmente hacemos impresión de los resultados y nuestro programa habrá finalizado

Algoritmo de Regresión Lineal – Aprendizajes hacia la IA

La inteligencia artificial es algo que ya está en los comentarios académicos del día a día, está vinculada cuando se revisa el hacia donde van las tecnologías y  la rama específica a la que nos dedicamos, y es que definitivamente todo ha de estar involucrado en un futuro (esperemos que cercano) con la inteligencia artificial, yo, soy estudiante de ingeniería industrial, bien que mal entiendo por mis cursos de carrera que mi profesión básicamente se trata de tomar una buena decisión sobre qué hacer para responder a la gran interrogante de ¿Cuánto voy a ganar?, ese cuánto está determinado por las tomas de decisiones que se realicen para la consecución de maximizar dicho objetivo, una toma de decisión está influenciada por una infinidad de datos que nosotros delimitamos dada nuestras limitantes biológicas de análisis, pero imaginemos que tuviéramos un consejero que no tuviera esas limitantes de análisis y que nos pueda brindar información o conclusiones que realmente ponderen la evaluación entre una opción u otra o incluso agregar alguna desconocida en la toma de una decisión, esto es una de los principales objetivos de la inteligencia artificial, claro que tiene muchos más pero este es uno de ellos, y es el que se alinea mejor a mi profesión, supongo que tú al leer esto, tendrás que encontrar la significancia y el valor ponderado de la inteligencia artificial en tu carrera.

Ahora bien, mi especialidad en tópicos de programación se ha decantado por lo general hacia el desarrollo de plataformas web y proyectos varios, pero jamás sobre la inteligencia artificial, este el primer post de muchos en el cual intento crear mi propio True Path sobre la IA, esperando que con ello pueda ayudarte en construir tu propio camino.

REGRESIÓN LINEAL

Entonces el tema que nos atañe en esta publicación es la regresión lineal, un tópico que está demás decir en ingeniería siempre se aborda en distintos cursos que tengan que ver con la evaluación de datos como lo es la estadística. Para entender la regresión lineal vamos a realizarlo con un ejemplo; supongamos que nos tenemos que mudar (país, provincia, distrito sea cual sea el de tu comodidad), al mudarnos nosotros deseamos evaluar dónde mudarnos y empezamos la recolección de datos, decidimos que el costo de la habitación que hemos de usar está en función del área que la compone, hacemos una revisión y obtenemos los siguientes resultados.

regresion1

Este acto de definir la relación entre una variable independiente y dependiente para una representación de la realidad en función de relaciones se denomina modelar o establecer un modelo, cuando observamos nuestra gráfica, podemos intuir que podemos trazar una línea recta que atraviese la mayoría de puntos o que al menos esté lo más cercano a ellos.

regresion2

Y esto que acabamos de dibujar es un modelo, este modelo nos permite predecir que dado una cantidad de metros cuadrados de una habitación este tendrá un valor promedio correspondiente, ahora esto se le denomina un modelo de regresión lineal simple.

Nosotros sabemos que una recta se define como:

Y=w0+w1x

Tal que w0 representa al valor en la cual la recta corta al eje Y y w1 que es la pendiente, la pendiente que representa la inclinación de la recta es la relación que existe entre las variables de entrada X y las variables de salida Y; sin embargo, la realidad resulta ser mucho más compleja; el costo de una habitación no solo está restringido a las dimensiones en metros cuadrados, sino por ejemplo al X2=tipo de barrio en el que se encuentra, X3=cercanías a establecimientos y muchas otras variables más, cuando esto ocurre, y ocurre, nos encontramos ante un modelo de regresión lineal múltiple:

Y=w0+w1x1+w2x2+...+wnxn

En dicha circunstancias, ya no se trata de ubicar la recta para los datos bidimensionales sino del hiperplano que mejor se adapte a la nube de puntos, tal que cada una de las dimensiones representa uno de los atributos.

La forma más adecuada de representar nuestros resultados no es a través de ecuaciones como:

Y1=w0+w1x11+w2x12+w3x13  ...

Y2=w0+w1x21+w2x22+w3x23  ...

Y3=w0+w1x31+w2x32+w3x33  ...

.

.

Sino de forma matricial, donde cada columna es cada una de las características que hemos considerados (tipo de barrio, cercanías a establecimientos, etc.) es decir los datos de entrada y cada fila representa el valor de cada una de las mediciones, podemos llamar a dicha matriz como X, entonces:

regresion4

Así como existen los valores de entrada cada una de las mediciones de las filas de X, tendrá como salida un valor Y, el cual también podemos representar mediante una matriz:

regresion5

Esto ocurre de forma similar con los parámetros :

regresion6

Haciendo uso de la multiplicación de matrices, debemos de multiplicar la matriz X por la matriz transpuesta de W  y obtendremos la matriz Y:

Y=XWt

Lo cual al programarlos resultan más eficientes ya que el computador se entiende mejor con matrices, ahora bien para fines de comprensión vamos a restringir el post a una dimensión, entonces, Si tenemos que el costo de la habitación está relacionado directamente a la cantidad de metros cuadrados de la habitación, entonces nuestro modelo puede ser representado a través de una recta, pero ¿Cómo determinamos cuál es la mejor recta?, uno de los métodos que nos permite obtener la mejor recta es el método de los Mínimos Cuadrados,

MÉTODO DE MÍNIMOS CUADRADOS

entonces sea una función polinomial de la siguiente forma:

Y=a0+a1x+a2x2+...+anxn

Y que podemos representarla de la siguiente forma:

regresion7

Lo que vamos hallar son los residuos o también llamado el error, este residuo es la diferencia que existe entre los puntos de los datos obtenidos y el dato pronosticado por nuestra función, entonces podemos decir que en x1 el valor teórico es y(x1) y un valor experimental y1, y el residuo r1 será:

r1=y1-y(x1)

Podemos generalizar haciendo:

ri=yi-y(xi)

Entonces obtenemos el cuadrado:

regresion8

¿Por qué el cuadrado?, este residuo que estamos hallando podemos interpretarlo como el error del modelo en una variable de entrada (X), elevando al cuadrado estamos penalizando con mayor intensidad aquellos elementos que estén más alejados a nuestro modelo.

Ahora obtenemos la suma de todos los residuos, donde obtendremos un coste total del error, recordemos que el método busca obtener la combinación óptima de parámetros:

regresion9.png

Pero recordemos que y(xi) es la función polinomial, entonces reemplazando tenemos:

regresion10

Ahora nosotros estamos buscando la minimización del coste del error, sabemos que el valor mínimo de una función podemos hallarlo haciendo cero en su derivada, entonces hallemos la derivada de D respecto a cada uno de los parámetros, esta derivación es conocida como derivadas parciales.

regresion11.png

Donde igualamos a cero a cada uno de los resultados parciales:

regresion12

Entonces, volvamos a nuestro modelo de regresión lineal simple  en el que nuestro modelo está representado por la recta:

Y(xi)=w0+w1xi

Y si los datos experimentales son Yobtenemos la sumatoria de residuos:

regresion13

Desarrollamos D y obtenemos:

regresion15

Sabemos que la solución se encontrará en una cantidad n+1 de ecuaciones, de donde obtenemos las derivadas parciales:

regresion14

regresion16

De donde despejamos y obtenemos tal que N sea el total de elementos (ayudas de sumatorias):

regresion17

Ahora despejando w de la primera ecuación en función  de wy reemplazando en la segunda ecuación obtenemos el valor de w1, luego ese valor reemplazamos en la primera ecuación y nos queda:

regresion18

 

Y bueno, esto es lo que tenemos por el momento, cuando tenemos datos reales, podemos incluso someterlo a una matriz y hacer su resolución de forma más sencilla, pues imagina que fueran muchos más atributos.

Java desde Cero – Estructura de Control de Flujo – Bucles 1

Cuando hacemos uso de un programa existen o lo creamos podemos observar que existen operaciones que se han de repetir, por ejemplo imaginemos que nuestro programa tenga que imprimir en consola el conteo de 1 a 100, si lo hiciéramos de forma convencional tendríamos que:

System.out.println(1);
System.out.println(2);
System.out.println(3);
System.out.println(4);
...

Esto resulta ineficiente, al ser una operación que es repetitiva debería poder realizarse a través de una estructura de control de flujo, y estos son los bucles, los bucles también llamados iteradores,  permiten la ejecución reiterada de una sentencia o sentencias, ahora bien, los bucles pueden ser de dos tipos, determinados o indeterminados, los determinados se definen básicamente porque conocemos cuántas veces se han de repetir las operaciones (o cuántas iteraciones se han de realizar) mientras que los indeterminados no sabemos con exactitud cuando han de finalizar ya que dependen de una condición booleana (verdadera o falsa) para continuar o finalizar su ejecución. Java posee 3 estructuras de control de flujo de ejecución que son bucles, estos son la estructura For, While y Do While, vamos realizar una revisión del bucle “For“.

La estructura de un bucle for es la siguiente:

for (inicialización; finalización; incremento) {
       sentencias
}
  • Inicialización: Es una expresión, es de donde ha de iniciar el conteo de las iteraciones, podemos utilizar una variable que ya ha sido declarada e inicializada previamente o podemos hacerlo en esta sección (por ejemplo iniciamos en que a=1).
  • Finalización: Es una expresión booleana que se evalúa su condición de verdadero o falso en cada iteración en función a sí el valor de inicialización ya alcanzó un valor final específico (por ejemplo evaluamos si a <100) y mientras no se haya alcanzado dicho valor las iteraciones han de continuar.
  • Incremento: Es invocada luego de la iteración y posterior evaluación, aquí se define la política de incremento del valor de inicialización (por ejemplo hacemos que a tenga un incremento de 1 en 1 o podemos hacer que vaya de 2 en 2).

Nuestro anterior objetivo era el conteo del 1 al 100, entonces esto en la estructura “for” se implementa de la siguiente forma:

for (int i=0;i<100;i++) {
       System.out.println(i);
}

Observemos que hemos declarado e inicializado la variable “i” en la estructura, recuerda que en java siempre debes definir el tipo de dato, un aspecto a tomar en cuenta es que  el alcance de la variable “i” solo estará circunscrito a la estructura y no existe más allá de ella, sé que aún no hemos hablado del alcance de una variable, pero por el momento piensa en el alcance como la existencia de una variable en un programa, con esto quiero decir que fuera de la estructura la variable “i” no existe y podría marcar un error si es que pretendemos hacer uso de ella. Luego definimos que su terminación será cuando “i” ya no cumpla la condición de ser menor que 100, finalmente establecemos la política de incremento que está dada por un aumento de “i” de 1 en 1.

Ahora bien, en Java la inicialización donde se define la variable, no se puede hacer por fuera, si no nosotros hiciéramos:

int i=0;
for ( i; i < 10; i++) {
   System.out.println(i);
}

Esto nos marcaría un error; para poder hacer uso de una variable que ya está definida, lo que debemos de hacer es dejar el espacio en blanco de su inicialización:

int i=0;
for ( ; i < 10; i++) {
   System.out.println(i);
}

Hecha esta salvedad, veamos un ejemplo en el que le preguntamos al usuario que se ejecute un conteo la cantidad de veces que el desee  y que el defina la política de incremento.

import java.util.Scanner;

public class Bucles_1 {

public static void main(String[] args) {
  Scanner entrada=new Scanner(System.in);

  System.out.println("¿Cuántos números desea contar?");
  int cantidad=entrada.nextInt();
  System.out.println("¿Desde dónde desea iniciar?");
  int inicio=entrada.nextInt();
  System.out.println("¿De cuánto en cuánto desea avanzar?");
  int avance=entrada.nextInt();
  entrada.close();

  for(int i=0;i<cantidad;i++) {
    System.out.println(inicio);
    inicio+=avance;
  }
  }

}

¿Qué hemos hecho?, hemos importado la clase Scanner y hemos hecho las consultas a través de la consola, cada entrada de teclado que responde a las preguntas, se almacena en las variables, nos interesa exactamente la cantidad de veces que se ha de iterar, el cómo se avance y de donde se inicie es casi por así decirlo que será implementado mediante un artilugio, luego de ello implementamos la estructura FOR hacemos que se imprima el primer valor que se ha registrado y luego hacemos que se incremente en función del avance que se ha requerido.

El bucle FOR también puede ser usado con cadenas de texto, es decir las cadenas de texto pueden ser iterados a través  de su longitud, la longitud está determinada por la cantidad de caracteres o espacios en blanco que existan dentro de las comillas que la contienen, por ejemplo: “hola” tiene una longitud de 4 ya que son 4 caracteres que la componen, para determinar la longitud de una cadena que es de la Clase String, debemos hacer uso de uno de sus métodos que se define como length. Entonces podemos implementarlo de la siguiente forma, vamos a hacer que se imprima cada uno de los caracteres de la cadena “hola”, para ello también haremos uso del método chartA(index) que nos devuelve el caracter del indice indicado, debemos saber que la cadena si bien es cierto su longitud es de 4 su índice siempre inicia desde el valor cero, es decir que el índice está yendo de 0 a 3 tal que el índice 0 es “h”, 1 es “o” y así sucesivamente, entonces:

String saludo="hola";
for(int i=0;i<saludo.length();i++) {
    System.out.println(saludo.charAt(i));
}

De este modo, hemos visto las posibilidades del uso del bucle for.

 

 

 

 

Programación Dinámica Determinística – Investigación de Operaciones

Anteriormente:

Programación Dinámica

Ya hemos revisado las bases de la programación dinámica, una técnica empleada dentro de la ingeniería industrial para la optimización de procesos. Ahora vamos revisar la programación dinámica determinística, que se centra en los problemas que el estado de la siguiente etapa está determinado por completo por el estado y la política de la etapa actual. La programación determinística se puede describir por el siguiente gráfica:

pd_13

Siendo esto el único factor diferencial, todo el proceso y características posteriores se cumplen, entonces veamos algunos ejemplos de su aplicación para entender  bien su entendimiento.

AGENCIA DE PUBLICIDAD

Una agencia de publicidad está llevando a cabo una campaña de publicidad de una semana para una tienda local. La agencia ha determinado que es posible que la campaña más efectiva pudiera incluir la colocación de anuncios en cuatro medios. Un periódico diario, un periódico dominical, radio y televisión. Se tiene disponible $ 8,000 para esta campaña y la agencia le gustaría distribuir esa cantidad en incrementos de $1,000 en todos los medios, de manera que se maximice el índice de exposición a la publicidad. Investigaciones llevadas a cabo por la agencia permiten obtener las siguientes estimaciones de la exposición por cada $1,000 de gasto en cada uno de los medios.

pd_14

Determine cuánto debe invertir la agencia en cada uno de los medios para maximizar la exposición de los anuncios.

Resolución

Vemos que no se menciona de forma explícita las etapas, para ello debemos de ponernos a meditar sobre la toma decisión que ha de ocurrir, podemos decir que si empezamos de arriba hacia abajo en la tabla que se ha presentado, podríamos decir que nuestro estado inicial es S1=$8000 y tomaremos una decisión X1 que sería el valor de la inversión en uno de los medios informativos tal que nos lleve al  siguiente estado (el siguiente medio informativo) y en el siguiente estado tendremos S2=8000-X1, y así sucesivamente S3=S2-X2 tal que al final quedemos con 0, observemos la situación determinística que dicta que el estado n+1 está determinado enteramente por el estado anterior y su contribución , ahora bien bajo esto podríamos decir que los medios informativos son las etapas, ya que en ellos se concentran las tomas de decisiones, podemos entonces realizar la siguiente tabla:

pd_15.png

Sí cada etapa es cada medio informativo, observemos lo que sucede en la etapa 1; en la etapa 1 podemos elegir, invertir 0 a 8, no sabemos cuánto pero sabemos que esas son los valores posibles:

pd_16

Si encontramos una razón a ello podemos decir, sea:

  • Sea n el número de estados que es 4.
  • Sn: La cantidad actual para invertir en la etapa n
  • xn: La cantidad actual que se invertirá en la etapa n tal que xn ={0,1,2,3,4,5,6,7,8}
  • Sn+1: La cantidad restante de inversión en la etapa n+1.
  • Csn,sn+1: la contribución inmediata de ir de n a n+1.

Entonces:

Sn+1=Sn-Xn

Con estos datos podemos buscar la relación recursiva; nuestro objetivo es obtener la maximización de exposición en los medios, entonces en cada etapa se ha evaluado y obtenido un gn+1(Sn+1), entonces podemos decir que la maximización de exposición (Gmax) es:

Gmax=C(Sn,Sn+1)+gn+1(Sn+1) equivalente a C(Sn,Sn+1)+gn+1(Sn-Xn)

Entonces en la etapa 1, sea S1=8, si invertimos los 8 el cual es nuestro X1  en la etapa 1 nos quedamos con 0 el cual es nuestro Sn+1.Y la contribución de invertir esos 8 en la etapa 1 es  C(Sn,Sn+1)=82, según dato en tabla.Esto ocurre de forma similar con los otros posibles estados. Bajo esa misma lógica creamos los demás estados y etapas.

pd_17.png

Obtenemos una red de la forma en que se muestra, expliquemos un poco que es lo que está sucediendo:

pd_18

En la primera etapa el esfuerzo de invertir 6 trae como resultado 80 y me quedo con 2 que es el estado inicial para la etapa 2, luego yo puedo decidir invertir esos 2 en la etapa 2 y me quedaría con 0, el resultado de invertir 2 en la segunda etapa es 55, o podría solo invertir 1 y el resultado de invertir 1 es 15 en la segunda etapa o no podría invertir nada, quedándome con 2 y el resultado de no invertir nada es 0, no puedo invertir 3 ya que no poseo dicha cantidad, siguiendo esa misma lógica es que se ha desplegado toda la red. En la última etapa sea lo que quede se va a distribuir, entonces el último estado será de valor 0, con todo esto descrito pasamos a las tablas:

Etapa 4 (Televisión):

pd_19

Etapa 3 (Radio):

pd_20

 

Etapa 2 (Periódico dominical:

pd_21

Etapa 1 (Periódico diario):

Aquí se observa lo sucedido con el nodo de 8 a 2, existe una inversión 6, invertir 6 en la etapa 1 trae una exposición de 80, dejando esos 2 para la siguiente etapa, es ahí donde revisamos cual es la forma más óptima de distribuir 2, que en la siguiente etapa es de 40

pd_22

Finalmente la mayor exposición es de 167 y se logra a través de la distribución de inversión de:

2->3->1->2 o 2->2->1->3

Aquí nos detenemos por el momento, esperando que les haya sido de su agrado.

Programación Dinámica – Investigación de Operaciones

TEORÍA

La programación dinámica es un técnica muy útil para la toma de decisiones de problemas complejos que pueden ser discretizados y secuencializados, proporciona un procedimiento sistemático para determinar la combinación óptima de decisiones; este método no tiene una formulación estándar ya que las ecuaciones que se planteen responden al problema específico.

Esta técnica es muy útil para la reducción el tiempo de ejecución de un algoritmo mediante la utilización de subproblemas y subestructuras óptimas, todo ello haciendo uso del principio de optimalidad:

“Dada una secuencia óptima de decisiones, toda subsecuencia de ella es, a su vez, óptima”

Para la introducción de las características y terminologías de la programación dinámica se creo el problema de la diligencia por parte del profesor Harvey M Wagner:

Un cazafortunas mítico de Missouri que decide ir al oeste a sumergirse en la fiebre del oro que surgió en California a mediados del siglo XIX. Tiene que hacer ek viaje en diligencia a través de territorios sin ley, donde existen serios peligros de ser atacado por merodeadores. A pesar de que su punto de partida y su destino son fijos, tiene muchas opciones en cuanto a qué estados – o territorios – debe elegir como puntos intermedios (tomar en cuenta que el viaje es siempre de izquierda a derecha).

planos1

Para lograr el viaje se requieren de 4 etapas para ir desde el estado A a su destino en el estado J, este cazafortunas es un hombre prudente preocupado por su seguridad. Después de reflexionar un poco ideó una manera bastante ingeniosa para determinar la ruta más segura. Se ofrecen pólizas de seguros de vida a los pasajeros. Como el costo de la póliza de cualquier jornada en la diligencia está basado en una evaluación cuidadosa de la seguridad del recorrida, la ruta más segura debe ser aquella cuya póliza represente el menor costo total“.

El costo de la póliza estándar del viaje en diligencia, del estado i al estado j se denota como:

costo

Creamos las tablas asociadas a cada uno de estos costos tenemos:

pd_1

FORMULACIÓN

Vamos a dividir el problema en etapas, las etapas serán evaluadas en la solución más óptima y se agregarán en el análisis de la siguiente etapa hasta encontrar la solución más óptima general, entonces:

Sean Xn=El destino inmediato de la etapa n (el n-ésimo viaje que se hará en diligencia), tal que la ruta seleccionada final para este problema será:

A->X1->X2->X3->X4, donde X4=J

Sea fn(s,xn) el costo total de la mejor política global para enfrentar las etapas restantes, mientras el cazafortunas se encuentra en el estado “s“, listo para iniciar la etapa n y elige xn como destino inmediato. Dados s y n, sea yn el valor de xn – no necesariamente único – que minimiza fn(s,xn) y gn(s) el valor mínimo correspondiente de fn(s,xn). Entonces:

gn(s)=mínf(s,xn)=f(s,yn)

Donde:

 fn(s,xn)=costo inmediato (etapa n) + costo futuro mínimo (etapas n+1 en adelante)

Representado de la siguiente forma:

pd_3

Entonces nuestro objetivo es encontrar g1(A) y su ruta correspondiente, pero para encontrarlo debemos de resolver de forma sucesiva g4(s), g3(s), g2(s) para cada uno de los estados posibles de s y usar g2(s) para encontrar g1(A).  Entonces es una suerte de ir del fin hacia el inicio obteniendo el costo mínimo (para este caso) en cada una de las etapas.

PROCEDIMIENTO

Recordemos que hemos de ir de adelante hacia atrás, entonces partimos de la última etapa, en nuestro ejemplo esta es la etapa 4, la cual es la última etapa por recorrer, cuando esto sucede su ruta está perfectamente definida, sea por H o por I la ruta se dirige hacia J:

pd_1

Podemos entonces hacer lo siguiente:

pd_2

para el caso de la etapa 4 no existe un g(S) ya que es la última, podemos considerar entonces que este es cero, así que está solo calculado directamente con el costo que representa ir por cada una de las rutas H o I hacia J.

En la etapa 3 se nos representa que ahora se deben de recorrer 2 etapas, aquí debemos de tomar especial atención a lo siguiente; tomemos como base que desde F podemos ir sea hacia H o I:

pd_4

Sabemos por la resolución anterior que el g4(H)=3 y g4(I)=4, entonces si decidimos ir de F->H tendríamos un costo total 6+3=9, ya que estamos haciendo la ruta F->H->J; si hacemos F-I tendríamos un costo total de 3+4=7 siendo menor el costo  y haciendo que g3(F)=7, lo mismo ocurre con E y G, en consecuencia realizando la tabla:

pd_5

En cada una de las celdas hemos hecho la operación descrita para F.

Al resolver la segunda etapa, realizamos los mismos cálculos donde obtenemos la siguiente tabla:

pd_6

Solo podemos observar que el destino inmediato de B y D pueden ser E o F ya que minimizan el valor de “g“, ahora debemos de ocuparnos de la primera etapa:

pd_7

Resuelta la última etapa ya nos es  posible obtener la ruta o rutas óptimas para nuestro problema, tenemos entonces que:

A->C->E->H->J  o  A->D->E->H->J o A->D->F->I->J

Tenemos estas 3 rutas disponibles donde todas tienen el costo mínimo de 11.

CARACTERÍSTICAS

  • El problema se puede dividir por etapas, y cada una de las etapas requiere de una política de decisión.
  • Cada etapa tiene cierto número de estados, los estados son las distintas condiciones posibles en las que se puede encontrar el sistema en cada etapa.
  • El efecto de la política de decisión en cada etapa es transformar el estado actual en un estado asociado con el inicio de la siguiente etapa, entonces podemos decir que un estado es una columna de nodos, cada nodo representa un estado y cada rama una política de decisión.
  • El procedimiento de resolución de la programación dinámica está diseñado para encontrar una política óptima para cada etapa logrando así la política óptima general.
  • Dado el estado actual, una política óptima para las etapas restantes es independiente de la política adoptada en etapas anteriores, por ende la decisión inmediata óptima solo depende del estado actual y no de cómo se llegó ahí, esto es el principio de optimalidad de la programación dinámica.
  • Se dispone de una relación recursiva que identifica la política óptima para la etapa n, dada la política óptima para la etapa n+1. La relación recursiva en su forma difiere de un problema a otro, pero se puede emplear las notaciones que ya se han usado en el problema de la diligencia, tal que finalmente siempre será cuestión de hallar un máximo o un mínimo.
  • Cuando se hace uso de la relación recursiva, el procedimiento de solución comienza al final se mueve hacia atrás etapa por etapa hasta encontrar la política óptima en cada etapa hasta la etapa inicial.

APLICACIONES

La Ruta Crítica

Hallar la ruta crítica con programación dinámica:

pd_8

Resolución

Recordemos que debemos de dividir por etapas nuestra red, sabemos que una etapa es un conjunto nodos o estados y los arcos con su valor con las contribuciones directas; podemos notar que existe la particularidad que el estado 3 está conectado tanto al estado final como a un estado intermedio, este estado 3 en consecuencia estará presente en al menos 2 etapas, si hiciéramos un corte podríamos observar que nuestro problema puede segmentarse en 4 etapas, entonces:

La etapa 4 es la última etapa por recorrer, y el único estado siguiente es 7 y no existe un g5 por lo cual el esfuerzo o tiempo será solo la contribución directa del arco:

 

pd_9

La etapa 3, ahora son dos etapas que debemos de considerar, en este caso en particular, recuerda tomar en cuenta todos los estados previos que te permiten llegar a los estados futuros, para ello observemos el estado 4 que si bien se encuentra en un estado final para la etapa también es parte del estado actual ya que conecta con otros estados finales, se puede observar que por ejemplo en el estado 2 que va hacia el estado 6 y 4 la contribución inmediata de ir de 2 a 6 más el g4(6)  máximo que hasta el momento es 1, igualmente ocurre de 2 a 4, de entre ellos dos elegimos el máximo, ¿Por qué el máximo?, pues porqué estamos buscando la ruta crítica, la ruta crítica está representada por la ruta más larga que me permita ir de 1 a 7.

pd_10

La etapa 2, correspondería ubicar en los estados finales a 1, 2, 4 y 5, pero no tiene sentido colocar a 1 ya que no existe un estado previo para él, entonces solo colocaremos a 2, 4 y 5, hacemos la misma lógica que ya está sustentada en la relación recursiva que aplica para este caso:

pd_11

La etapa 1 y última etapa se consideran las 3 etapas anteriores, entonces tenemos:

pd_12

Hecho todo ello, ¿Cómo hallamos la ruta crítica?, debemos de seleccionar todos los valores máximos, si existe un estado (nodo) que se encuentre en más de una etapa debemos de seleccionar en cual de ellos es el mayor por ejemplo, revisemos la ruta de 1 a 2 y 1 a 3 aparentemente sea de 1 a 3 la ruta más larga; sin embargo, la ruta de 1 a 2 en la etapa 2  es mayor que la ruta de 1 a 3, es por ello que tomamos dicha ruta, luego, en la etapa 2 se obtuvo ese valor del estado 2 ya que provenía del estado 6 y de 6 a 7, entonces nuestra ruta crítica será:

1->2->6->7 longitud de 13