Fundamentos y Métodos Esenciales de Optimización en Informática

Conceptos Fundamentales en Optimización y Álgebra Lineal

Definiciones Clave

• Operaciones: Se refiere a las manipulaciones y cálculos aplicados a estructuras matemáticas como matrices o conjuntos, así como a los procedimientos dentro de los métodos de optimización.
• Matriz: Conjunto de números o expresiones numéricas que se ordenan en filas y columnas.
• Matriz Cuadrada: Una matriz que tiene el mismo número de filas y columnas.
• Determinante: Número asociado a una matriz cuadrada, utilizado principalmente para resolver sistemas de ecuaciones lineales.
• Conjunto: Colección de objetos llamados elementos que comparten una propiedad en común.
• Función Objetivo: Expresión matemática que representa la medida de desempeño que se desea maximizar o minimizar en un problema de optimización.

Técnicas y Métodos de Optimización

Métodos Generales

• Método de Descomposición: Técnica analítica que consiste en dividir un problema complejo o un sistema grande en partes más pequeñas y manejables.
• Métodos Paramétricos en Programación Lineal: Herramientas valiosas para evaluar cómo se comportan las soluciones de un modelo de programación lineal ante cambios en sus parámetros.

Métodos Específicos de Programación y Optimización

• Árbol de Decisión:
  • Herramienta que ayuda a tomar decisiones y evaluar las consecuencias de una decisión.
  • Característica: Su forma de árbol con nodos y ramas.
• Método Gráfico:
  • Técnica utilizada para resolver problemas de programación lineal que involucran 2 variables de decisión.
  • Característica: Resuelve problemas que tienen 2 variables de decisión.
• Método Húngaro: Técnica de optimización para resolver problemas de asignación.
• Método de Vogel: Procedimiento utilizado para resolver problemas de optimización de transporte y costos.
• Método de Russell: Calcula el coeficiente para cada casilla vacía, incluyendo costos de las filas y columnas.
• Método Simplex: Algoritmo matemático utilizado para resolver problemas de programación lineal. Busca la solución óptima de un problema y se basa en conceptos geométricos.
• Método de la Esquina Noroeste: Algoritmo que se utiliza para resolver problemas de transporte o distribución. Busca una solución básica que cumpla con todas las restricciones.
• Método Stepping Stone: Técnica que garantiza una solución óptima y ahorro de costos.
• Análisis de Sensibilidad: Herramienta utilizada en el modelado financiero para evaluar el impacto de cambios en variables clave.

Ejercicios Prácticos y Aplicaciones

Ejemplo: Método del Árbol de Decisión

• Opción X: $120 con probabilidad del 70%
• Opción Y: $150 con probabilidad del 30%

La mejor decisión sería: X (mayor valor esperado).

Ejemplo: Método Gráfico (Maximización)

Se evaluaron los vértices de la región factible:

• (1,3): $45
• (5,6): $80
• (7,8): $75

El vértice óptimo es: (5,6) con ganancia máxima.

Ejemplo: Método de la Esquina Noroeste

Problema de transporte. Se asignaron las siguientes cantidades:

• Celda (1,3): 12 uds a $8 (12x8=96)
• Celda (2,2): 18 uds a $7 (18x7=126)
• Celda (3,1): 10 uds a $9 (10x9=90)

La suma total es: 96 + 126 + 90 = 312.

Ejemplo: Método de Vogel

Problema de transporte. Se seleccionaron las siguientes rutas:

• Ruta A-D: 20 uds a $5 (20x5=100)
• Ruta B-C: 15 uds a $6 (15x6=90)
• Ruta C-E: 10 uds a $8 (10x8=80)

La suma total es el costo total: $270. Función: minimizar costos.

Ejemplo: Método Húngaro (Asignación)

Se asignaron 4 trabajadores con los siguientes costos por tarea:

• Tarea 1: $25
• Tarea 2: $35
• Tarea 3: $40
• Tarea 4: $30

La suma total de todas las cifras será el costo total: $130.

Ejemplo: Árbol de Decisión (Probabilidad)

En un análisis se obtuvieron los siguientes valores esperados:

• Rama A: $200 con probabilidad del 40% (200x0.4=80)
• Rama B: $180 con probabilidad del 60% (180x0.6=108)

¿Cuál rama debe seleccionarse? Rama B (mayor valor esperado).

Ejemplo: Método Gráfico de Maximización

Se evaluaron los puntos de interés:

• Punto (1,3): $60
• Punto (4,5): $90
• Punto (6,9): $85

Se debe elegir el punto con mayor ganancia/valor. La mejor opción es (4,5).