Método Gráfico
Optimización lineal con 2 variables de decisión. Visualiza la región factible y encuentra la solución óptima.
Sustento Teórico
El Método Gráfico resuelve problemas de Programación Lineal con dos variables de decisión, representando las restricciones como rectas en el plano cartesiano.
Formulación:
Maximizar/Minimizar: Z = C₁·X₁ + C₂·X₂ Sujeto a: a₁₁·X₁ + a₁₂·X₂ ≤/≥/= b₁ a₂₁·X₁ + a₂₂·X₂ ≤/≥/= b₂ ... X₁, X₂ ≥ 0
La región factible es la intersección de todos los semiplanos definidos por las restricciones. Por el Teorema Fundamental de la Programación Lineal, la solución óptima se encuentra en un vértice de la región factible.
Complejidad: O(n²) donde n = número de restricciones.
Datos de Entrada
Modelado Matemático y Puntos de Graficación
Gráfica de la Región Factible
Vértices de la Región Factible
| Vértice | X₁ | X₂ | Z |
|---|
Método Simplex
Resuelve problemas de Programación Lineal con N variables y M restricciones mostrando cada iteración paso a paso.
Sustento Teórico
El Método Simplex es un algoritmo iterativo que recorre los vértices del poliedro factible buscando mejorar la función objetivo en cada paso.
Forma Estándar:
Max Z = C₁X₁ + C₂X₂ + ... + CₙXₙ Sujeto a: a₁₁X₁ + a₁₂X₂ + ... + a₁ₙXₙ + S₁ = b₁ a₂₁X₁ + a₂₂X₂ + ... + a₂ₙXₙ + S₂ = b₂ Xᵢ, Sⱼ ≥ 0 Criterio de Optimalidad: Todos los Cⱼ - Zⱼ ≤ 0 Columna Pivote: Mayor Cⱼ - Zⱼ positivo Fila Pivote: Min(bᵢ / aᵢⱼ) con aᵢⱼ > 0
Para minimización, se utiliza el Método Big-M: las variables artificiales reciben un coeficiente -M (un número muy grande) en la función objetivo.
Complejidad promedio: O(m) iteraciones, O(mn) por iteración.
Datos de Entrada
Método Húngaro
Problema de asignación óptima con matriz de costos N×N. Minimiza o maximiza el costo total de asignación.
Sustento Teórico
El Método Húngaro (o algoritmo de Kuhn-Munkres) resuelve el problema de asignación en tiempo polinomial O(n³).
Minimizar: Z = Σᵢ Σⱼ cᵢⱼ · xᵢⱼ
Sujeto a:
Σⱼ xᵢⱼ = 1 para cada fila i (cada tarea se asigna una vez)
Σᵢ xᵢⱼ = 1 para cada columna j (cada recurso se usa una vez)
xᵢⱼ ∈ {0, 1}
Pasos:
1. Reducción de filas (restar mín de cada fila)
2. Reducción de columnas (restar mín de cada columna)
3. Cubrir ceros con mínimo de líneas
4. Si líneas < N: ajustar matriz y repetir
5. Asignar basándose en los ceros
Complejidad: O(n³)
Datos de Entrada
Cadenas de Markov
Análisis de procesos estocásticos con matrices de transición. Calcula probabilidades futuras y estado estacionario.
Sustento Teórico
Una Cadena de Markov es un proceso estocástico donde la probabilidad de cada estado futuro depende únicamente del estado actual (Propiedad de Markov).
Matriz de Transición P (NxN): P[i][j] = Probabilidad de ir del estado i al estado j Σⱼ P[i][j] = 1 para cada fila i Estado en paso n: π(n) = π(0) · Pⁿ Estado Estacionario π*: π* · P = π* Σᵢ π*ᵢ = 1 Se resuelve como sistema de ecuaciones lineales.
El estado estacionario existe si la cadena es ergódica (irreducible y aperiódica).
Datos de Entrada
Cada fila debe sumar 1.0
Debe sumar 1.0
Evolución de Estados
Cálculo de Transiciones Paso a Paso
Vector de Estado Estacionario
Ruta Más Corta
Encuentra la ruta de menor costo entre dos nodos usando el algoritmo de Dijkstra con visualización interactiva.
Sustento Teórico
El Algoritmo de Dijkstra encuentra la ruta de menor peso desde un nodo origen hacia todos los demás nodos en un grafo con pesos no negativos.
Algoritmo de Dijkstra:
1. dist[origen] = 0, dist[v] = ∞ para todo v ≠ origen
2. prev[v] = indefinido para todo v
3. Q = conjunto de todos los nodos
Mientras Q no esté vacío:
u = nodo en Q con menor dist[u]
Remover u de Q
Para cada vecino v de u en Q:
alt = dist[u] + peso(u, v)
Si alt < dist[v]:
dist[v] = alt
prev[v] = u
Reconstruir ruta con prev[]
Complejidad: O((V + E) log V) con cola de prioridad.