Optimización de Procesos: Métodos Esenciales en Programación Lineal

Fundamentos de Optimización y Métodos de Resolución

Propiedades de la Región Factible y Restricciones

• Restricciones no redundantes: Ninguna restricción es redundante, ya que al eliminar cualquiera de ellas, la región factible cambia.
• SBF (Solución Básica Factible): Corresponde a los vértices de la región factible.
• SBNF (Solución Básica No Factible): Corresponde al resto de cruces de rectas que no son vértices de la región factible.

Nota: Para la formulación de la función objetivo, consulte el ejercicio del libro azul (posiblemente página 75).

Cuellos de Botella en Programación Lineal

Los cuellos de botella son aquellas restricciones que tienen holgura cero respecto de la solución óptima. Gráficamente, se trata de las restricciones cuyas rectas frontera pasan por el punto de la solución óptima.

Transformación a Forma Estándar

• Para una restricción de tipo "menor o igual" (<=): Se suma una variable de holgura (h).
• Para una restricción de tipo "mayor o igual" (>=): Se resta una variable de exceso (s) y, si es necesario para el método Simplex, se suma una variable artificial (a).
• Si una variable x_i está restringida como x_i <= 0: Se sustituye por x_i = -x_i', donde x_i' >= 0.
• Si una variable x_i no está restringida en signo: Se sustituye por x_i = x_i1 - x_i2, con x_i1, x_i2 >= 0.

Método Simplex para Optimización Lineal

La solución óptima no es única si el valor de Z_j - C_j de una variable no básica (incluyendo variables de holgura o exceso) es igual a cero, y el resto de elementos de esa columna no son solo ceros y unos (es decir, no es una columna de una variable básica). Para hallar esta solución alternativa con el mismo valor de la función objetivo (Z), se hace entrar la variable correspondiente en la tabla Simplex.

Criterios de Entrada de Variables en el Simplex

• Para problemas de Maximización: Entra la variable con el Z_j - C_j más negativo (o menor valor).
• Para problemas de Minimización: Entra la variable con el Z_j - C_j más positivo (o mayor valor).

Método de la Esquina Noroeste para Problemas de Transporte

Este método se utiliza para encontrar una solución básica factible inicial en problemas de transporte.

• Existen restricciones por filas (oferta) y por columnas (demanda).
• Se comienza asignando la cantidad máxima posible a la casilla X_11 (esquina noroeste), limitada por la restricción de fila o columna más pequeña.
• Se avanza sistemáticamente hacia la derecha o hacia abajo, agotando los recursos de filas o columnas, hasta completar todas las asignaciones.
• El valor de la función objetivo (costo total) se calcula como: Z = Sumatorio (costo_unitario * cantidad_asignada).
• Las casillas rellenadas corresponden a las Variables Básicas (VB).

Determinación de la Variable Entrante (Método de los Multiplicadores o UV)

Para evaluar la optimidad de la solución inicial y determinar qué variable no básica debe entrar:

1. Calcular los multiplicadores U_i (para filas) y V_j (para columnas) para las celdas básicas (VB) utilizando la relación U_i + V_j = C_ij. Se fija arbitrariamente U_1 = 0.
2. Calcular los costos reducidos Z_ij - C_ij para las celdas vacías (Variables No Básicas, VNB) utilizando la fórmula Z_ij - C_ij = U_i + V_j - C_ij.
3. Si existen Z_ij - C_ij negativos (para minimización) o positivos (para maximización), la solución no es óptima. La variable que entra es aquella con el valor más negativo/positivo.
4. Para determinar la variable que sale, se traza un circuito cerrado (polígono) que incluye la variable que entra y solo celdas básicas, alternando signos (+/-) en sus vértices. La variable que sale es la básica con el menor valor en una posición negativa del circuito.

Método Húngaro para Problemas de Asignación

El Método Húngaro es un algoritmo eficiente para resolver problemas de asignación, donde se busca minimizar el costo o maximizar el beneficio al asignar tareas a recursos.

1. Reducción por filas: Restar el valor mínimo de cada fila a todos los elementos de esa fila.
2. Reducción por columnas: Restar el valor mínimo de cada columna a todos los elementos de esa columna.
3. Cubrir ceros: Trazar el mínimo número de líneas horizontales o verticales para cubrir todos los ceros de la matriz.
4. Criterio de Optimalidad: Si el número de líneas trazadas es igual al número de filas (o columnas) de la matriz (n), se ha alcanzado la Solución Óptima (S.O.). Si no, se procede al siguiente paso.
5. Mejora de la Matriz:
   • Identificar el valor mínimo de todos los números no cubiertos por ninguna línea.
   • Restar este valor a todas las celdas no cubiertas.
   • Sumar este mismo valor a las celdas cubiertas por dos líneas (intersecciones).
   Repetir desde el paso 3 hasta alcanzar la optimalidad.
6. Asignación de Tareas: Una vez alcanzada la optimalidad, asignar tareas comenzando por los ceros que son únicos en una fila o una columna, eliminando la fila y columna correspondientes a cada asignación.

El valor óptimo de la función objetivo (Z) se calcula como el sumatorio de los costos originales de las casillas que coinciden con las tareas asignadas al final del ejercicio.