Modelación matemática - Optimización de recursos

La modelación matemática convierte un problema real y mal definido en un problema matemático resoluble. En el ejemplo inicial, una compañía de ferris debe decidir cuántos chalecos y botes salvavidas instalar para 1000 personas con un máximo de 85 metros cúbicos de espacio. Cada chaleco ocupa 0,05 metros cúbicos y cada bote, con capacidad para 20 personas, ocupa 2,1. Plantear el sistema de dos ecuaciones con dos incógnitas da una solución fraccionaria de 363,6 chalecos y 31,8 botes. Como se requieren números enteros, se ajusta a 31 botes y 380 chalecos, y luego a 30 botes y 400 chalecos por la restricción de un número par de botes. La lección clave es que no hay una única respuesta correcta, aunque algunas son mejores que otras, y el problema se plantea mejor como programación entera con restricciones de desigualdad. En teoría de grafos, un grafo es una colección de vértices conectados por aristas. Un árbol es un grafo conexo sin circuitos. El problema del viajante busca el camino más corto que visita cada nodo exactamente una vez y regresa al origen. No existe un algoritmo de tiempo polinomial conocido, pero se puede encontrar una ruta cuyo costo esté dentro de un factor de dos del óptimo usando un árbol de expansión mínima. Como los pesos satisfacen la desigualdad del triángulo, cualquier camino que pase por nodos ya visitados puede reemplazarse por una ruta directa sin aumentar el costo. El costo del árbol de expansión mínima da un límite inferior para el recorrido óptimo, y el recorrido derivado da un límite superior, información útil para algoritmos de ramificación y acotamiento. Una cadena cerrada euleriana es un camino que recorre cada arista del grafo exactamente una vez y regresa al punto de partida. El teorema de Euler de 1736 establece que un multigrafo tiene una cadena cerrada euleriana si y solo si está conectado y cada vértice tiene grado par. El grado es el número de aristas que pasan por un vértice. El problema de los puentes de Königsberg no tiene solución porque todos sus vértices tienen grado impar. Este resultado se aplica a la programación de quitanieves o barredoras de calles. En el análisis estadístico de simulaciones, la media muestral se calcula como la suma de los valores observados dividida entre el número de simulaciones. La varianza muestral usa el divisor N menos uno. Con la estrategia uno, la distribución de ganancias es aproximadamente normal por el teorema del límite central, con media 783 y desviación estándar 83. El valor observado estará entre 617 y 949 aproximadamente el 95 por ciento de las veces. Con la estrategia dos, la distribución no es normal, tiene media 439, desviación estándar 1020, y en el 26 por ciento de las simulaciones la ganancia fue negativa. Aunque una estrategia tenga mayor promedio, la de menor varianza puede ser preferible por tener menos riesgo. Las cadenas de Markov modelan sistemas que cambian de estado con probabilidades fijas. En el problema de descomposición de máquinas, el estado tres es un estado absorbente: sin importar el estado inicial, se termina allí con probabilidad uno. En el problema de horarios de trabajo, donde los empleados trabajan un día sí y un día no, no se alcanza un estado estacionario único sino un ciclo entre dos estados, porque los valores propios de la matriz de transición tienen magnitud uno. En el inventario de tanques de peces, el vector propio normalizado para el valor propio uno da la fracción de tiempo en cada estado, y la probabilidad de que un cliente sea servido es exactamente el 60 por ciento, coincidiendo con la simulación. El barajado por riffle de un mazo de cartas se modela con cadenas de Markov. Bayer y Diaconis redujeron los estados al número de secuencias ascendentes, que son secuencias maximales de cartas numeradas consecutivamente. Con 52 cartas se necesitan siete barajados para aleatorizar el mazo. Los números eulerianos satisfacen la recurrencia A de r,k igual a k por A de r menos uno,k más r menos k más uno por A de r menos uno